Recursion polynomial for cubic rotation symmetric Boolean functions

Rotation symmetric (RS) Boolean functions have been extensively studied for over twenty years because of their applications in cryptography and coding theory. The present paper studies degree 3 RS functions, and relies extensively on the theory of the affine equivalence of such functions developed in [3] . It is known [1] that if f(x₁,x₂,…,x_n) is the RS Boolean function in n variables generated by the monomial x₁,x₂,…x_i (notation (x1,x2,…,xi)_n), then the sequence wt((x1,x2,…,xi)_n),n=i,i+1,…, where wt((x1,x2,…,xi)_n) denotes the Hamming weight of the function, satisfies a linear recursion with integer coefficients and this recursion can be explicitly computed with a method given in [1] . It was observed in [10, Lemma 3.5, p. 396] that the functions (1,2,4)_n and (1,2,5)_n have the same weights for every n even though the two functions are not affine equivalent for infinitely many values of n . It was not clear what the explanation for that is. This paper answers that question and gives a general theory that provides many more examples of similar behavior for function pairs (1,r,s)_n and (1,t,u)_n.