Finding Hamming weights without looking at truth tables

This paper studies degree 3 Boolean functions in n variables x₁, ..., x_n which are rotation symmetric, that is, invariant under any cyclic shift of the indices of the variables. These rotation symmetric functions have been extensively studied in the last dozen years or so because of their importance in cryptography. We start from the 2012 paper of Bileschi, Cusick and Padgett, which gave an algorithm for finding a recursion for the truth table of any n-variable cubic rotation symmetric Boolean function generated by a monomial, as well as a homogeneous recursion for its (Hamming) weight as n increases. This greatly reduced the computational complexity of computing the weights of such functions for large n, but it was still necessary to calculate the truth tables of the functions for the values of n needed to give the initial conditions for the recursion. This computation could be infeasible if the recursion order is large, since the truth tables have 2ⁿ entries. The present paper shows how to use the roots of the characteristic polynomial of the recursion to find the initial conditions without looking at any truth tables, given the mild and plausible assumption that these roots are distinct. This results in a huge decrease in the computational complexity (including the time needed to find the roots) to something linear in n, apart from logarithmic factors.