2017/01/10 by Thomas W. Cusick, Cusick, Thomas W.
Computer Science · Engineering · #Coding theory and cryptography #graph theory and CDMA systems #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.1701.06648
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, 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 \em 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, …\ 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. The last section of the paper gives a Mathematica program 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.