Geodesic
Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 18-30 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

One of the directions of the investigation of functions over finite fields is the study of their representations, including polynomial ones. In the area of polynomial representations of functions the problem of estimating the complexity of such representations can be highlighted. The complexity of the polynomial, representing the function, is the number of its non-zero terms. Each function can be represented by several different polynomials from the same class. The complexity of a function in the class of polynomials is the least possible complexity of a polynomial from this class, representing the function. The complexity of the given set of functions in the class of polynomials is the maximal complexity of a function from the set in this class of polynomials. In the case of functions over a finite field of order 2 (Boolean functions), exact values of the complexity of such representations are known for many classes of polynomial forms. But for functions over finite fields of order greater than two, even in fairly simple classes of polynomials, only mismatched upper and lower bounds of complexity have been found. This paper is devoted to the study of the representation of seven-valued functions by polarized polynomials. The polynomials of this class have the form of a sum of a finite number of products of a certain type. For the case of Boolean and three-valued functions, effective lower bounds for the complexity in the class of polarized polynomials are known, as well as a weaker power estimate for functions over a finite field of prime order. In previous papers, the authors obtained effective lower bounds for the complexity of functions over finite fields of order 4 and 5 in the class of polarized polynomials. In this paper an effective lower bound for the complexity of seven-valued functions in the class of polarized polynomials has been obtained.
Keywords: finite field, polarized polynomial, Kroneker form, complexity, lower bounds. 
@article{IIGUM_2017_22_a1,
     author = {A. S. Baliuk and A. S. Zinchenko},
     title = {Lower bound of the complexity of seven-valued functions in the class of polarized polynomials},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {18--30},
     year = {2017},
     volume = {22},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a1/}
}
TY  - JOUR
AU  - A. S. Baliuk
AU  - A. S. Zinchenko
TI  - Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2017
SP  - 18
EP  - 30
VL  - 22
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a1/
LA  - ru
ID  - IIGUM_2017_22_a1
ER  - 
%0 Journal Article
%A A. S. Baliuk
%A A. S. Zinchenko
%T Lower bound of the complexity of seven-valued functions in the class of polarized polynomials
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2017
%P 18-30
%V 22
%U http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a1/
%G ru
%F IIGUM_2017_22_a1
A. S. Baliuk; A. S. Zinchenko. Lower bound of the complexity of seven-valued functions in the class of polarized polynomials. The Bulletin of Irkutsk State University. Series Mathematics, Tome 22 (2017), pp. 18-30. http://geodesic.mathdoc.fr/item/IIGUM_2017_22_a1/

[1] Alekseev V. B., Voronenko A. A., Selezneva S. N., “On the complexity of representations of $k$-valued functions by polarized polynomials”, Proc. of the Int. Workshop on Discrete Mathematics and Mathematical Cybernetics (Ratmino, 2003), 8–9 (in Russian)

[2] Baliuk A. S., Zinchenko A. S., “Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 16 (2016), 19–29 (in Russian)

[3] Baliuk A. S., Zinchenko A. S., “Lower bound of the complexity of five-valued functions in the class of polarized polynomials”, Diskr. Mat., 28:4 (2016), 29–37 (in Russian) | DOI

[4] Baliuk A. S., Yanushkovsky G. V., “Upper bounds of the complexity of functions over finite fields in some classes of Kroneker forms”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 14 (2015), 3–17 (in Russian)

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

[6] Kazimirov A. S., Reymerov S. Yu., “On upper bounds of the complexity of functions over nonprime finite fields in some classes of polarized polynomials”, Izv. Irkutsk. Gos. Univ., Ser. Mat., 17 (2016), 37–45 (in Russian) | Zbl

[7] Markelov N. K., “A lower estimate of the complexity of three-valued logic functions in the class of polarized polynomials”, Vestn. Mosk. Univ., Ser. 15: Vychisl. Matem. Kibern., 36:3 (2012), 150–154 | MR | Zbl

[8] 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

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