An upper bound on the number of iterations for transforming a Boolean function of degree greater or equal than 4 to a function of degree 3 (Q5960285)

The Hamming weight of a Boolean function is the number of ones in its truth table. In order to facilitate the study of the weight distribution of all Boolean functions of degree \(\geq 3\), a method is presented that transforms a Boolean function of degree \(\geq 4\) to one of degree \(3\) in a way that the Hamming weight only changes in a very controlled way. (Degree here means the degree of the function as a multilinear polynomial over \(\text{ GF}[2]^m\), where \(m\) is the arity of the function.) It is shown how precisely the Hamming weight of the obtained function depends on the weight of the original function and the number of iterations of an algorithm performing the transformation. Compared to previous approaches, the method of the present paper generally needs only a smaller number of iterations.