Good coordinates in the Fourier entropy-influence conjecture
For a Boolean function $f$ let $E_i(f)=H(\mathbf 1[i\in U]\mid U\setminus\{i\})$, where $U$ is drawn from the spectral distribution $\hat f^2$. The Fourier entropy-influence conjecture holds if and only if the quantity $\mathsf{G}=\sup_f\min_i E_i(f)/\mathrm{Inf}_i(f)$ is finite, and then its constant lies between $\mathsf{G}$ and $\mathsf{G}+2/\ln 2$. We study $\mathsf{G}$ directly. A composition identity computes $E_i$ and $\mathrm{Inf}_i$ for iterated block compositions $g(h,\dots,h)$ exactly from the biased spectrum of $g$, and towers of transitive monotone gates give $\mathsf{G}_{\mathrm{mon}}\ge 4.50642846$, where $\mathsf{G}_{\mathrm{mon}}$ is the supremum over monotone functions. On the other side we show that every width-$w$ DNF has a coordinate with $E_i/\mathrm{Inf}_i\le 2+\log_2 e+\log_2(2^{w+1}-1)$, with no monotonicity or read restriction, and that every relevant leaf of a read-once AND/OR formula has $E_i/\mathrm{Inf}_i<\pi/\ln 2$, which is sharp. Finally we show that the coordinate of largest influence is not a valid selection rule, and that all but a vanishing fraction of the coordinates of a monotone function can have $E_i/\mathrm{Inf}_i$ bounded below by any constant. Nor can the ratios be averaged with weights $\mathrm{Inf}_i^{a+1}$ for any $a\ne0$.
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.24125398
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint