Geodesic
Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials
The Bulletin of Irkutsk State University. Series Mathematics, Tome 16 (2016), pp. 19-29 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The representations, including polynomial, of functions over final fields have been actively investigated. The complexity of such representations is the main stream of research. Polynomial representations of Boolean functions have been studied well enough. The exact values of the complexity have been found for a lot of polynomial classes. 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 field of order 4. Such a polynomial is a finite sum of 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 constructive lower bounds in the class of polarized polynomials have been known only for the case of Boolean and three-valued functions. Also, the weaker, non-constructive lower bound has been known for the case of functions over arbitrary prime finite field. In this paper the constructive lower bound has been obtained for functions over finite field of order 4 in the class of polarized polynomials. The lower bound is equivalent to previously known lower bound for Boolean and three-valued functions.
Keywords: finite field, polarized polynomial, Kroneker form, complexity, lower bounds. 
@article{IIGUM_2016_16_a1,
     author = {A. S. Baliuk and A. S. Zinchenko},
     title = {Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {19--29},
     year = {2016},
     volume = {16},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a1/}
}
TY  - JOUR
AU  - A. S. Baliuk
AU  - A. S. Zinchenko
TI  - Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2016
SP  - 19
EP  - 29
VL  - 16
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a1/
LA  - ru
ID  - IIGUM_2016_16_a1
ER  - 
%0 Journal Article
%A A. S. Baliuk
%A A. S. Zinchenko
%T Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2016
%P 19-29
%V 16
%U http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a1/
%G ru
%F IIGUM_2016_16_a1
A. S. Baliuk; A. S. Zinchenko. Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials. The Bulletin of Irkutsk State University. Series Mathematics, Tome 16 (2016), pp. 19-29. http://geodesic.mathdoc.fr/item/IIGUM_2016_16_a1/

[1] Alekseev V. B., Voronenko A. A., Selezneva S. N., “On the complexity of representations of $k$-valued functions by polarized polynomials”, Discrete models in theory of control systems, Proceedings of V International conference (Ratmino, May 26–29, 2003), 2003, 8–9 (in Russian)

[2] Baliuk A. S., Yanushkovsky G. V., “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, IIGU Ser. Matematika, 14 (2015), 3–17 (in Russian) | MR

[3] Graham R., Knuth D., Patashnik O., Concrete Mathmatics. A Foundation for Computer Science, Addison Wesley, 1994, 672 pp. | MR

[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, 36:3 (2012), 150–154 | DOI | MR | MR | Zbl

[5] Peryazev N. A., “Complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34:3 (1995), 177–179 | DOI | MR | Zbl

[6] Selezneva S. N., “On the complexity of the representation of functions of many-valued logics by polarized polynomials”, Discrete Mathematics and Applications, 12:3 (2002), 229–234 | DOI | DOI | MR | Zbl