рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

List of issues > Series «Mathematics». 2016. Vol. 16

Lower Bound of the Complexity of Functions over Finite Field of Order 4 in the Class of Polarized Polynomials

Author(s)
A. S. Baliuk, A. S. Zinchenko
Abstract

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
UDC
519.714.4

MSC

68Q17

References

1. Alekseev V.B., Voronenko A.A., Selezneva S.N. On the complexity of representations of k-valued functions by polarized polynomials (in Russian). In proceedings of V International conference «Discrete models in theory of control systems», Ratmino, May 26-29 2003, 2003, pp. 8–9.

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

3. Graham R., Knuth D., Patashnik O. Concrete Mathematics. A Foundation for Computer Science. Addison Wesley, 1994. 672 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. Complexity of Boolean functions in the class of polarized polynomial forms. Algebra and Logic, 1995, vol. 34, issue 3, pp. 177–179.

6. Selezneva S.N. On the complexity of the representation of functions of manyvalued logics by polarized polynomials. Discrete Mathematics and Applications, 2002, vol. 12, no 3, pp. 229–234.


Full text (russian)