Classifying balanced elementary symmetric Boolean functions
For integers $n \ge d \ge 2$ let $$\sigma_{n,d}(x_1, \dots, x_n) = \bigoplus_{1 \le i_1 < \dots < i_d \le n} x_{i_1} \cdots x_{i_d}, \qquad x \in \mathbb{F}_2^n,$$ be the elementary symmetric Boolean function of degree $d$, where $\oplus$ is addition modulo two. A Boolean function on $\mathbb{F}_2^n$ is balanced if it takes the value $1$ on exactly $2^{n-1}$ inputs. Cusick, Li and Stănică proved that $\sigma_{n,d}$ is balanced when $d = 2^t$ and $n = 2^{t+1}\ell - 1$ (2008); they also proved that $\sigma_{n,d}$ is not balanced when $d$ is odd, and that for $d = 2^t$ it is balanced only for these $n$ (2009). For each $d$, the equivalence below holds for all sufficiently large $n$ (Castro and Medina; Gao, Guo and Zhao, with an explicit bound), and Castro and Medina showed that $\sigma_{n,d}$ is never balanced when $d < 2048$ is not a power of two. Su, Tang and Pott reduced the question to two families of pairs $(n,d)$ with $n = 2^{t+1}\ell + r$, $\ell \ge 3$ odd and $-1 \le r \le 2$.
Problem. Is it true that, for all integers $n \ge d \ge 2$, $\sigma_{n,d}$ is balanced if and only if $d = 2^t$ and $n = 2^{t+1}\ell - 1$ for some integers $t, \ell \ge 1$?
Source: Cusick, Li and Stănică (2008); see Su, Tang and Pott (2013), Conjecture 1.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- IT, NT
- Keywords
- AIM Open Applied Problems, elementary symmetric polynomials, symmetric Boolean functions
References
@article{cusick2008,
author = {Cusick, Thomas W. and Li, Yuan and St{\u{a}}nic{\u{a}}, Pantelimon},
title = {Balanced symmetric functions over {GF}$(p)$},
journal = {IEEE Trans. Inform. Theory},
volume = {54},
number = {3},
year = {2008},
pages = {1304--1307},
doi = {10.1109/TIT.2007.915920},
eprint = {math/0608369},
archivePrefix = {arXiv},
}
@article{cusick2009,
author = {Cusick, Thomas W. and Li, Yuan and St{\u{a}}nic{\u{a}}, Pantelimon},
title = {On a conjecture for balanced symmetric {B}oolean functions},
journal = {J. Math. Cryptol.},
volume = {3},
number = {4},
year = {2009},
pages = {273--290},
doi = {10.1515/JMC.2009.017},
}
@article{su2013,
author = {Su, Wei and Tang, Xiaohu and Pott, Alexander},
title = {A note on a conjecture for balanced elementary symmetric {B}oolean functions},
journal = {IEEE Trans. Inform. Theory},
volume = {59},
number = {1},
year = {2013},
pages = {665--671},
doi = {10.1109/TIT.2012.2215576},
eprint = {1203.1418},
archivePrefix = {arXiv},
}
@article{castro2011,
author = {Castro, Francis N. and Medina, Luis A.},
title = {Linear recurrences and asymptotic behavior of exponential sums of symmetric {B}oolean functions},
journal = {Electron. J. Combin.},
volume = {18},
number = {2},
year = {2011},
pages = {P8},
doi = {10.37236/2004},
eprint = {1101.4682},
archivePrefix = {arXiv},
}
@article{gao2016,
author = {Gao, Guangpu and Guo, Yingming and Zhao, Yaqun},
title = {Recent results on balanced symmetric {B}oolean functions},
journal = {IEEE Trans. Inform. Theory},
volume = {62},
number = {9},
year = {2016},
pages = {5199--5203},
doi = {10.1109/TIT.2015.2455052},
}
@article{castro2017,
author = {Castro, Francis N. and Medina, Luis A.},
title = {Modular periodicity of exponential sums of symmetric {B}oolean functions},
journal = {Discrete Appl. Math.},
volume = {217},
year = {2017},
pages = {455--473},
doi = {10.1016/j.dam.2016.10.005},
eprint = {1603.00534},
archivePrefix = {arXiv},
}
@misc{aim-balanced-elementary-boolean,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Classifying balanced elementary symmetric Boolean functions}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/589-balanced-elementary-boolean.md},
note = {Entry 589 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00330, "Classifying balanced elementary symmetric Boolean functions", clopen.solutions.