Polynomial representations of Boolean functions have been studied well enough. Recently, the interest to polynomial representations of functions over finite fields and over finite rings is being increased. There are a lot of difficulties in studying of the complexity of these representations. Only not equal upper and lower bounds has been obtained, even for sagnificantly simple classes of polynomials.

This paper is about polarized polynomials over finite fields and their generalizations: differentially and generically polarized polynomials. Such a polynomial is a finite sum of products. The difference between classes of polynomials is in constraints, applied to the products. Every polynomial represents an n-variable function over finite field. A complexity of a polynomial is a number of nonzero summands in it. Every function can be represented by several polynomials, which are belongs to the same class. A complexity of a function in a class of polynomials is the minimal complexity of polynomials in the class, which represent this function.

Previously, the upper bounds were known for arbitrary n-variable function over primary finite field of order, greater than 2, for the classes of polarized and differentially polarized polynomials, as well as for the class of generically polarized polynomials.

A representation of an n-ary function over finite field of order q by a polarized polynomial or its generalization can be considered as a Kroneker form. This means, that the function, considered as a vector in appropriate linear space, is computed by a linear transformation of a vector of coefficients of the polynomial, where the matrix of this linear transformation is a Kroneker product of n nonsingular matrices with rank q. This approach helped us to improve the upper bound for polarized and differentially polarized polynomials for the case of any finite field of odd order, and to improve the upper bound for generically polarized polynomials for the case of any finite field of order, greater than 2.

1. Graham R., Knuth D., Patashnik O. Concrete Mathmatics. A Foundation for Computer Science. Addison Wesley, 1994. 672 p.

2. Zinchenko A.S., Panteleev V.I. Polinomialnie operatornie predstavlenija funkcij kznachnoj logiki (in Russain). Diskretnyi Analiz i Issledovanie Operatsii. Series 1. – 2006, vol. 13, no 3, pp. 13-26.

3. Lidl R., Niederreiter H. Finite Fields (Encyclopedia of Mathematics and its Applications). Cambridge University Press, England, 1984. 660 p.

4. Markelov N.K. A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials. Moscow University Computational Mathematics and Cybernetics. 2012, vol. 36, Issue 3, pp. 150–154.

5. Peryazev N.A. The complexity of Boolean functions in the class of polarized polynomial forms (in Russian). Algebra and Logic, 1995, vol. 34, no 3, pp. 323–326.

6. Selezneva S.N. On the complexity of representation of k-valued functions by generalised polarised polynomials. Discrete Mathematics and Applications, 2010, vol. 19, Issue 6, pp. 653–663.

7. Selezneva S.N. On the complexity of representations of functions over multivalued logics by polarized polynomials (in Russian). Discrete Mathematics and Applications, 2002, vol. 14, no 2. pp. 48–53.