Nondegenerate normal forms of Boolean functions. (Q1432316)

For a Boolean function of \(n\) variables \(f(x)=f(x_{1},\ldots ,x_{n})\), the degree of its Zhegalkin polynomial is called the degree of nonlinearity of the Boolean function and is denoted by deg\(f\). The derivative of a Boolean function \(f(x)\) in direction \(\sigma \in V_{n}\) is the Boolean function defined as \(\frac{df}{d\sigma }(x)=f(x\oplus \sigma )\oplus f(x)\), where \(V_{n}\) is the vector space of dimension \(n\) over the field \(F_{2}=\{0,1\}\) and \(\oplus \) denotes the coordinatewise summation modulo 2 of vectors of equal lengths. The nonlinarity degree of \(f\) is said to be equal to \(r\) if and only if the nonlinearity degree of each of its derivatives does not exceed \(r-1\) and there exists a direction in which the derivative has the nonlinearity degree \(r-1\). A Boolean function \(f\) is said to be nondegenerate if the operation of taking the derivative in any nonzero direction reduces their degree of nonlinearity exactly by one. In this paper the nondegeneracy property of a Boolean function is expressed in terms of linear algebra such as dimension, basis, linear and bilinear mappings or symplectic matrix of a quadratic form, which makes the analysis of nondegenerate Boolean functions very efficient. Among other things it is shown, e.g., that any Boolean function is RM-equivalent to some nondegenerate form (two Boolean functions of the same degree of nonlinearity denoted by deg\(f\) are said to be RM-equivalent if they can be obtained from each other by making an affine change of variables and by adding a function whose degree of nonlinearity does not exceed deg\(f-1\)). Also, from the well-known classification of quadratic forms it follows that nondegenerate homogeneous forms of degree 2 of \(n\) variables exist only for even \(n\), and for \(n=2m\) these forms can be reduced by an affine change of variables to the form \(x_{1}y_{1}\oplus \ldots \oplus x_{m}y_{m}\). These results can be viewed as a step on the path to the solution of the problem of affine classification of Boolean functions.