Weight Recursions for Any Rotation Symmetric Boolean Functions
Thomas W. Cusick · IEEE Transactions on Information Theory · 2017
Let fn(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, α2,⋯, αd)ndenote the function fnof degree d in n variables generated by the monomial x1xα2⋯xαd. Such a function fnis called monomial rotation symmetric (MRS). It was proved in a 2012 paper that for any MRS fnwith d = 3, the sequence of weights {wk= wt(fk) : k = 3, 4,⋯} satisfies 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.