Weight Recursions for Any Rotation Symmetric Boolean Functions

Let f_n(x1, x2,.., xn) denote the algebraic normal form (polynomial form) of a rotation symmetric Boolean function of degree d in n ≥ d variables and let wt(fn) denote the Hamming weight of this function. Let (1, a2,.., ad)n denote the function fn of degree d in n variables generated by the monomial x1xa2.. xad. Such a function fn is called monomial rotation symmetric (MRS). It was proved in a 2012 paper that for any MRS fn with d=3, the sequence of weights wk = wt(fk):k = 3, 4,.. a homogeneous linear recursion with integer coefficients. In this paper, it is proved that such recursions exist for any rotation symmetric function fn; such a function is generated by some sum of t monomials of various degrees. A Mathematica program is available on arxiv.org which explicitly computes the homogeneous linear recursion for the weights, given any rotation symmetric fn. The reader who is only interested in finding some recursions can use the program and not be concerned with the details of the rather complicated proofs in this paper.