A variance form of Han's bound on the Fourier entropy
Han proved that every Boolean function $f$ satisfies \[ H(f)\le \frac{3}{\ln 2}\,I(f)+\sum_k \mathrm{Inf}_k(f)\log_2\frac{4}{\mathrm{Inf}_k(f)}, \] where $H$ is the Fourier entropy and $I$ the total influence. We show that the logarithm may be taken relative to the variance: \[ H(f)\le \Bigl(2+\frac{3}{\ln 2}\Bigr)I(f)+\sum_k \mathrm{Inf}_k(f)\log_2\Bigl(1+\frac{\mathrm{Var}(f)}{\mathrm{Inf}_k(f)}\Bigr). \] The bound implies Han's up to an additive $I(f)$ and is smaller by a factor of order $k$ for the AND of $k$ variables. It follows that the Fourier entropy-influence conjecture holds, with constant $2+3/\ln2+\log_2(1+1/\varepsilon)$, for every function whose influences are all at least $\varepsilon\mathrm{Var}(f)$, and that $H(f)\le I(f)\,(3+3/\ln 2+H(\pi))$, where $\pi_k=\mathrm{Inf}_k(f)/I(f)$ is the influence distribution. The proof combines the chain rule for the Fourier entropy along a decision tree with a one-coordinate estimate, and an adaptive version holds along any decision tree.
Authors
- Yitzchak Shmalo (ORCID: https://orcid.org/0000-0002-2886-3049)
Institutions
- Hebrew University of Jerusalem (IL)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-11
- DOI
- https://doi.org/10.5281/zenodo.24125394
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint