The one-coordinate step in the Fourier entropy-influence conjecture
For a Boolean function $f$ and a coordinate $i$ let $D_i(f)=H(f)-\tfrac12 H(f_{i\to 1})-\tfrac12 H(f_{i\to -1})$ be the drop in Fourier entropy when $x_i$ is fixed. González, MacManus and Pereyra observed that the Fourier entropy-influence conjecture follows, by induction on the dimension, if every Boolean function has a coordinate with $D_i(f)\le K\,\mathrm{Inf}_i(f)$. We show that this condition is also necessary: if the conjecture holds with constant $C$, then every nonconstant Boolean function has a coordinate whose erasure entropy is at most $C\,\mathrm{Inf}_i(f)$, and hence one with $D_i(f)\le (C+2/\ln 2)\mathrm{Inf}_i(f)$. The constant $2/\ln 2$ is the sharp bound for the Jensen–Shannon part of $D_i$. We also give an equivalent pseudo-likelihood form of the conjecture, a bound on the influences of extremal functions, and an example showing that the condition cannot be required at every coordinate.
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.24125404
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint