Modular periodicity of exponential sums of symmetric Boolean functions

详细信息    查看全文

• 作者：Francis N. Castro ^{franciscastr@gmail.com} ; Luis A. Medina ; ^{luis.medina17@upr.edu}
• 关键词：Symmetric Boolean functions ; Exponential sums ; Recurrences ; Pisano periods
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P3
• 页码：455-473
• 全文大小：541 K
• 卷排序：217

文摘

This work brings techniques from the theory of recurrent integer sequences to the problem of balancedness of symmetric Boolean functions. In particular, the periodicity modulo pp (pp odd prime) of exponential sums of symmetric Boolean functions is considered. Periods modulo pp, 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 nn variables of degree 12921292 is not balanced because the prime p=176129p=176129 does not divide its exponential sum for any positive integer nn. 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.