Approximation of restrictions of q -valued logic functions to linear manifolds by affine analogues
Vladimir Gennadievich Ryabov · Discrete Mathematics and Applications · 2021
Abstract For a finite q -element field F q , we established a relation between parameters characterizing the measure of affine approximation of a q -valued logic function and similar parameters for its restrictions to linear manifolds. For q > 2, an analogue of the Parseval identity with respect to these parameters is proved, which implies the meaningful upper estimates q n −1 ( q − 1) − q n /2−1 and q r −1 ( q − 1) − q r /2−1 , for the nonlinearity of an n -place q -valued logic function and of its restrictions to manifolds of dimension r . Estimates characterizing the distribution of nonlinearity on manifolds of fixed dimension are obtained.