PreprintarXiv licencearXiv
An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
Abstract
In this work, we prove that any Boolean function of degree d on ℤqn, q≥ 3, has at most mqqd relevant variables, where mq=(2q(q2+4q+1))/((q−1)4). For q∈ {3,4,5,6,7}, we improve this bound to 2.854· 3d, 1.749· 4d, 1.263· 5d, 0.994· 6d, and 0.814· 7d, respectively.
Related
- Optimal central limit theorem for bounded random variables in high dimensions
- On the most informative Boolean function under noise
- Almost every Boolean function has central threshold degree
- Task-Oriented Boolean Function Computation: Practical Code Constructions
- A Proof of the Most Informative Boolean Function Conjecture
BibTeX
@misc{valyuzhenich2026upper,
title = {{An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph}},
author = {Alexandr Valyuzhenich},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12540},
eprint = {2609.12540},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12540},
}
RIS
TY - UNPB
TI - An upper bound on the number of relevant variables in a bounded degree Boolean function on the Hamming graph
AU - Alexandr Valyuzhenich
PY - 2026
DA - 2026/09/11
PB - arXiv
DO - 10.48550/arxiv.2609.12540
UR - https://arxiv.org/abs/2609.12540
AB - In this work, we prove that any Boolean function of degree d on ℤ_q^n, q≥ 3, has at most m_qq^d relevant variables, where m_q=(2q(q^2+4q+1))/((q−1)^4). For q∈ {3,4,5,6,7}, we improve this bound to 2.854· 3^d, 1.749· 4^d, 1.263· 5^d, 0.994· 6^d, and 0.814· 7^d, respectively.
ER -