Upper bound for the length of functions over a finite field in the class of pseudopolynomials
Светлана Николаевна Селезнева · Computational Mathematics and Mathematical Physics · 2017
An exclusive-OR sum of pseudoproducts (ESPP), or a pseudopolynomial over a finite field is a sum of products of linear functions. The length of an ESPP is defined as the number of its pairwise distinct summands. The length of a function f over this field in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ESPP (n) on the set of functions over a finite field of k elements in the class of ESPPs is considered; it is defined as the maximum length of a function of n variables over this field in the class of ESPPs. It is proved that L ESPP (n) = O(k n /n 2).