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 nonzero 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.

For citation:

Baliuk A.S., Zinchenko A.S. Lower Bound of the Complexity of Seven-Valued Functions in the Class of Polarized Polynomials. The Bulletin of Irkutsk State University. Series Mathematics, 2017, vol. 22, pp. 18-30. (In Russian). https://doi.org/10.26516/1997-7670.2017.22.18

MSC

68Q17

DOI

https://doi.org/10.26516/1997-7670.2017.22.18

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,pp 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., 2016, vol. 16, pp. 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., 2016, vol. 28, issue 4, pp. 29–37. (in Russian)

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., 2015, vol. 14, pp. 3–17. (in Russian)

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

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., 2016, vol. 17, pp. 37–45. (in Russian)

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., 2012. vol. 36. issue 3. pp. 150–154.

8. Peryazev N.A. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra and Logic, 1995, vol. 34, issue 3, pp. 177–179.

9. Selezneva S.N. On the complexity of the representation of functions of manyvalued logics by polarized polynomials. Discrete Math. Appl., 2002, vol. 12, no 3. pp. 229–234.