Skip to main navigation Skip to search Skip to main content

Hamming weights of symmetric Boolean functions

Research output: Contribution to journalArticlepeer-review

9 Scopus citations

Abstract

It has been known since 1996 (work of Cai et al.) that the sequence of Hamming weights {wt(fn(x1,…,xn))}, where fn is a symmetric Boolean function of degree d in n variables, satisfies a linear recurrence with integer coefficients. In 2011, Castro and Medina used this result to show that a 2008 conjecture of Cusick, Li and Stănică about when an elementary symmetric Boolean function can be balanced is true for all sufficiently large n. Quite a few papers have been written about this conjecture, but it is still not completely settled. Recently, Guo, Gao and Zhao proved that the conjecture is equivalent to the statement that all balanced elementary symmetric Boolean functions are trivially balanced. This motivates the further study of the weights of symmetric Boolean functions fn. In this paper we prove various new results on the trivially balanced functions. We also determine a period (sometimes the minimal one) for the sequence of weights wt(fn) modulo any odd prime p, where fn is any symmetric function, and we prove some related results about the balanced symmetric functions.

Original languageEnglish
Pages (from-to)14-19
Number of pages6
JournalDiscrete Applied Mathematics
Volume215
DOIs
StatePublished - Dec 31 2016

Keywords

  • Boolean functions
  • Hamming weight
  • Recursion
  • Symmetric
  • Walsh value

Fingerprint

Dive into the research topics of 'Hamming weights of symmetric Boolean functions'. Together they form a unique fingerprint.

Cite this