PreprintarXiv licencearXiv
Tameness of transitive Boolean functions
Abstract
Let fn:{0,1}n→{0,1} be Boolean functions, and let Cn count their changes in a unit time interval under stationary dynamics in which each coordinate is independently resampled at rate one from the Bernoulli(pn) distribution. We prove that, if fn is transitive and nmin{pn,1−pn}r→∞ for every r>0, then tightness of (Cn) implies Var(fn)→0. This settles Forsström's conjecture in the pn≤ 1/2 regime and extends it symmetrically to arbitrary biases. The proof uses a mixed jump sum whose second moment is bounded by the generator of a low degree Fourier projection.
Related
- On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions
- Sensitivity of Rotation Symmetric Boolean Functions via Binary Necklaces
- The Maximum Nonlinearity of 8-variable Balanced Boolean Functions is 116
- The Hellinger Conjecture for Antipodal Boolean Functions
- Construction of New Complete Complementary Codes Using Extended Boolean Functions and Permutations
BibTeX
@misc{long2026tameness,
title = {{Tameness of transitive Boolean functions}},
author = {Xinyu Long},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09725},
eprint = {2610.09725},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09725},
}
RIS
TY - UNPB
TI - Tameness of transitive Boolean functions
AU - Xinyu Long
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.09725
UR - https://arxiv.org/abs/2610.09725
AB - Let f_n:{0,1}^n→{0,1} be Boolean functions, and let C_n count their changes in a unit time interval under stationary dynamics in which each coordinate is independently resampled at rate one from the Bernoulli(p_n) distribution. We prove that, if f_n is transitive and nmin{p_n,1−p_n}^r→∞ for every r>0, then tightness of (C_n) implies Var(f_n)→0. This settles Forsström's conjecture in the p_n≤ 1/2 regime and extends it symmetrically to arbitrary biases. The proof uses a mixed jump sum whose second moment is bounded by the generator of a low degree Fourier projection.
ER -