Search

An n-place function over a field F q with q elements is called maximally nonlinear if it has the largest nonlinearity among all q-valued n-place functions. We show that, for even n=2, a function is maximally nonlinear if and only if its nonlinearity is q n − 1 (q − 1) − q n 2 − 1 ; for n=1, the corresponding criterion for maximal nonlinearity is q − 2. For q > 2 and even n=2, we describe the set of all maximally nonlinear quadratic functions and find its cardinality. In this case, all maximally nonlinear quadratic functions are quadratic bent functions and their number is smaller than the halved number of the bent functions. [ABSTRACT FROM AUTHOR]

For a finite q-element field Fq, 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 qn−1(q − 1) − qn/2−1 and qr−1(q − 1) − qr/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. [ABSTRACT FROM AUTHOR]

We obtain estimates for the probability that for a randomly selected k-dimensional n-place q-valued logic vector function there exists a linear manifold of fixed dimension such that the degree of the restriction of the function to this manifold is not larger than the given value. The asymptotics of the number of manifolds on which the restrictions are affine is obtained. It is shown that if n → ∞ and k ≤ n/q, then for almost all k-dimensional n-place vector functions the maximum dimension of a manifold on which the restriction is affine lies in the interval [⌊logqn/k + logq logq n/k⌋, ⌈logqn/k + logq logq n/k⌉], while the analogous parameter for the case of fixed variables lies in the range [⌊logqn/k⌋, ⌈logqn/k⌉]. [ABSTRACT FROM AUTHOR]