Part 3. Mathematical models

Estimation of the maximum number of nonzero coefficients of a function polynomial under the action of a permutation group on a table of function values

A. O. Gremyakov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: For coefficients of polynomials of functions over finite fields $ F_q $, we consider the problem of finding a lower bound for the maximum minimum of the number of nonzero coefficients in the polynomial, where the maximum is taken over all functions and the minimum is taken from their transformations corresponding to various field assignments. Moreover, various types of such transformations are considered. The main results of the paper relate to two types of transformations, the description of which is given in the first section of the paper. The paper estimates $L (q) \geq q-2 $ for the maximum minimum of the number of nonzero coefficients in the polynomial for the certain type of transformations that leave the zero field element in place.

Keywords: sagemath, coefficients of polynomials, Boolean functions, polynomial of a Boolean function, table of values of a function, sagemath.