Lower bound of the complexity of functions over finite field of order 4 in the class of polarized polynomials

A. S. Baliuk ; A. S. Zinchenko

The Bulletin of Irkutsk State University. Series Mathematics, Tome 16 (2016), pp. 19-29

Résumé

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.

Détail

Keywords: finite field, polarized polynomial, Kroneker form, complexity, lower bounds.