Theory of 2-rotation symmetric cubic Boolean functions

A Boolean function in n variables is 2-rotation symmetric if it is invariant under even powers of the cyclic permutation (Formula Presented.) of the variables, but not under the first power (ordinary rotation symmetry); for brevity, we call such a function a 2-function. A 2-function is said to be monomial rotation symmetric (MRS) if it is generated by applying powers of (Formula Presented.) to a single monomial. This paper develops the theory of cubic MRS 2-functions in 2n variables generated by a monomial (Formula Presented.) with (Formula Presented.) and r and s not both odd (notation (Formula Presented.); it turns out that such functions with r and s both odd are essentially the same as ordinary cubic MRS functions in only n variables. A complete description of affine equivalence for these cubic MRS 2-functions is given, including a simple necessary and sufficient condition for two such functions to be affine equivalent. It is proved that affine equivalence for these functions is the same as affine equivalence under permutations which preserve 2-rotation symmetry. This is the first time that all affine equivalence classes have been explicitly determined for any large general family of Boolean functions with degree >2. An exact count of the equivalence classes is given and their number is proved to be very small, in fact (Formula Presented.) for any (Formula Presented.). It is proved that the sequence of Hamming weights (Formula Presented.) satisfies a linear recursion with integer coefficients. A similar result for ordinary cubic MRS functions was proved recently (papers by Bileschi, Cusick and Padgett, and by Brown and Cusick), but this paper uses a new method for the 2-functions proof. Unlike the ordinary MRS function case, both the orders of the recursions for the 2-functions and the precise values of the roots of the corresponding recursion polynomials can be given explicitly. Finally, a precise value for the weights of the 2-functions is proved, using a 2011 formula of Cusick and Padgett. These weights are connected to powers of members of the well known Lucas sequence, and so the weights can be found without computing initial values for the recursions.