Geodesic
On upper bound of the complexity of quasi polynomial representations of functions over finite fields
The Bulletin of Irkutsk State University. Series Mathematics, Tome 10 (2014), pp. 3-12 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $x_i^0, \dots, x_i^{k-1}$ of selected variable $x_i$ is replaced by a function from a set $\{g_0(x_i), \dots, g_{k-1}(x_i)\}$ 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 $\frac{k}{k+1}k^n$. 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 \geqslant 3$. Namely, the quasi polynomial complexity of any $n$-ary function over finite field of order $q$ is at most $ \frac{q-1}{q-q^{1-q}}q^n$.
Keywords: finite field, complexity.
Mots-clés : polynomial, quasi polynomial 
@article{IIGUM_2014_10_a0,
     author = {A. S. Baliuk},
     title = {On upper bound of the complexity of quasi polynomial representations of functions over finite fields},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {3--12},
     year = {2014},
     volume = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2014_10_a0/}
}
TY  - JOUR
AU  - A. S. Baliuk
TI  - On upper bound of the complexity of quasi polynomial representations of functions over finite fields
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2014
SP  - 3
EP  - 12
VL  - 10
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2014_10_a0/
LA  - ru
ID  - IIGUM_2014_10_a0
ER  - 
%0 Journal Article
%A A. S. Baliuk
%T On upper bound of the complexity of quasi polynomial representations of functions over finite fields
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2014
%P 3-12
%V 10
%U http://geodesic.mathdoc.fr/item/IIGUM_2014_10_a0/
%G ru
%F IIGUM_2014_10_a0
A. S. Baliuk. On upper bound of the complexity of quasi polynomial representations of functions over finite fields. The Bulletin of Irkutsk State University. Series Mathematics, Tome 10 (2014), pp. 3-12. http://geodesic.mathdoc.fr/item/IIGUM_2014_10_a0/

[1] Panteleev V. I., “Polynomial representations of $k$-valued functions by derivative and normalization operators”, Russian Mathematics (Iz. VUZ). Izvestiya VUZ. Matematika, 1998, no. 1, 17–21 (in Russian)

[2] Peryazev N. A., “The complexity of Boolean functions in the class of polarized polynomial forms”, Algebra and Logic, 34:3 (1995), 323–326 (in Russian)

[3] Selezneva S. N., “On the complexity of $k$-valued functions in one class of polynomials”, Problemy Theoreticheskoi Kibernetiki, University of Nizhny Novgorod, Nizhny Novgorod, 2011, 430–434 (in Russian)

[4] Selezneva S. N., “On the complexity of representations of functions over multivalued logics by polarized polynomials”, Discrete Mathematics and Applications, 14:2 (2002), 48–53 (in Russian) | DOI