Modular periodicity of exponential sums of symmetric Boolean functions

by Francis N. Castro and Luis A. Medina

Discrete Applied Mathematics , 217, 2017, 455-473.

This work brings techniques from the theory of recurrent integer sequences to the problem of balancedness of symmetric Booleans functions. In particular, the periodicity modulo p (p odd prime) of exponential sums of symmetric Boolean functions is considered. Periods modulo p, bounds for periods and relations between them are obtained for these exponential sums. The concept of avoiding primes is also introduced. This concept and the bounds presented in this work are used to show that some classes of symmetric Boolean functions are not balanced. In particular, every elementary symmetric Boolean function of degree not a power of 2 and less than 2048 is not balanced. For instance, the elementary symmetric Boolean function in n variables of degree 1292 is not balanced because the prime p = 176129 does not divide its exponential sum for any positive integer n. It is showed that for some symmetric Boolean functions, the set of primes avoided by the sequence of exponential sums contains a subset that has positive density within the set of primes. Finally, in the last section, a brief study for the set of primes that divide some term of the sequence of exponential sums is presented.

Article


arXiv Front End


Papers by Luis A. Medina


Luis A. Medina's homepage