Nondegenerate normal forms of Boolean functions.
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.
- Polynomial expansions of Boolean functions with respect to nondegenerate functions
- On the Degree, Nonlinearity, Algebraic Thickness, and Nonnormality of Boolean Functions, With Developments on Symmetric Functions
- Nondegenerate functions and permutations
- Polynomial decomposition of Boolean functions by images of homogeneous operators of nondegenerate functions
- A polynomial decomposition of Boolean functions
- Normal Boolean functions
- On some invariants under the action of an extension of \(\mathrm{GA}(n, 2)\) on the set of Boolean functions
- scientific article; zbMATH DE number 732057 (Why is no real title available?)
- On the number of homogeneous nondegenerate p-ary functions of a given degree
- On a property of quadratic Boolean functions
- The existence of nonnormal Boolean functions with high algebraic degrees
- On the relationship between local affinities of a Boolean function and some types of its degeneracy
- Nondegenerate functions and permutations
This page was built for publication: Nondegenerate normal forms of Boolean functions.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1432316)
