List of issues > Series «Mathematics». 2014. Vol. 10
On Upper Bound of the Complexity of Quasi Polynomial Representations of Functions over Finite Fields
Representations of functions over finite fields, including polynomial representations, are being actively investigated. The complexity of such representations is one of main directions of research.
This paper is about quasi polynomial complexity of functions over finite fields. Quasi polynomial can be considered as a regular polynomial with the following transformation: every occurence xi0, . . . , xik−1 of selected variable xi is replaced by a function from a set {g0(xi), . . . , gk−1(xi)} of linearly independent unary functions.
The number of terms, the number of occurences of variables, or the degree of a polynomial are usually used as a measure of complexity. In the case of quasi polynomials one can use the number of terms as a natural measure of complexity, while further generalization are required for the number of occurences of variables and the degree of a polynomial. In this paper the number of terms is used as a measure of complexity. Previously, the upper bound of such a complexity was known for polynomials over finite fields of prime order. Namely, the quasi polynomial complexity of n-ary function over finite field of prime order k is at most k·kn/(k+1).
In this paper an upper bound for the quasi polynomial complexity of functions over finite fields of arbitrary order q has been obtained, which significantly improves previously known upper bound for modulo prime quasi polynomials, if q ≥ 3. Namely, the quasi polynomial complexity of any n-ary function over finite field of order q is at most (q-1)·qn/(q-q1-q).
1. Panteleev V. I. Polynomial representations of k-valued functions by derivative and normalization operators (in Russian). Russian Mathematics (Iz. VUZ). Izvestiya VUZ. Matematika., 1998, no. 1, pp. 17–21.
2. 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.
3. Selezneva S. N. On the complexity of k-valued functions in one class of polynomials (in Russian). Problemy Theoreticheskoi Kibernetiki, Nizhny Novgorod, University of Nizhny Novgorod, 2011, pp. 430–434.
4. 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.