The Fourier entropy–influence conjecture
Let $f : \{-1,1\}^n \to \{-1,1\}$, with the uniform probability measure on the cube, and for $S \subseteq [n] = \{1, \dots, n\}$ let $$\widehat f(S) = 2^{-n} \sum_{x \in \{-1,1\}^n} f(x) \prod_{i \in S} x_i$$ be its Fourier–Walsh coefficients, so that $\sum_S \widehat f(S)^2 = 1$. The Fourier entropy of $f$ is the Shannon entropy, in bits, of the distribution $S \mapsto \widehat f(S)^2$ on subsets of $[n]$ (the empty set included), $$H(f) = \sum_{S \subseteq [n]} \widehat f(S)^2 \log_2 \frac{1}{\widehat f(S)^2},$$ with terms where $\widehat f(S) = 0$ read as zero. Its total influence is $$I(f) = \sum_{i=1}^n \Pr\{f(X) \ne f(X^{(i)})\} = \sum_{S \subseteq [n]} |S|\, \widehat f(S)^2,$$ where $X$ is uniform on the cube and $X^{(i)}$ is $X$ with its $i$th coordinate flipped. Friedgut and Kalai's motivation was the theory of sharp thresholds for monotone graph properties. O'Donnell, Wright and Zhou proved the inequality below for symmetric functions, with $C = 12.04$, and for functions computed by read-once decision trees, with $C = 4.88$. Kelman, Kindler, Lifshitz, Minzer and Safra proved that the Fourier weight of a Boolean function of constant variance is concentrated on $2^{O(I(f) \log I(f))}$ sets $S$. Keller, Mossel and Schlank, and later Han, proved that $H(f) \le C\bigl(I(f) + \sum_{i} \operatorname{Inf}_i(f) \log (1/\operatorname{Inf}_i(f))\bigr)$ for a universal constant $C$, where $\operatorname{Inf}_i(f) = \Pr\{f(X) \ne f(X^{(i)})\}$, terms with $\operatorname{Inf}_i(f) = 0$ being read as zero.
Problem. Is there a finite constant $C > 0$, independent of $n$ and $f$, such that $$H(f) \le C\, I(f)$$ for every $n \ge 1$ and every $f : \{-1,1\}^n \to \{-1,1\}$? No balance, monotonicity, symmetry or degree condition is imposed on $f$.
Source: Friedgut and Kalai (1996), the Fourier entropy–influence conjecture; see O'Donnell, Wright and Zhou (2011).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- FA, PR
- Keywords
- AIM Open Applied Problems, Boolean functions, Fourier coefficients, influences
References
@article{friedgut1996,
author = {Friedgut, Ehud and Kalai, Gil},
title = {Every monotone graph property has a sharp threshold},
journal = {Proc. Amer. Math. Soc.},
volume = {124},
number = {10},
year = {1996},
pages = {2993--3002},
doi = {10.1090/S0002-9939-96-03732-X},
}
@inproceedings{odonnell2011,
author = {O'Donnell, Ryan and Wright, John and Zhou, Yuan},
title = {The {F}ourier entropy--influence conjecture for certain classes of {B}oolean functions},
booktitle = {Automata, Languages and Programming (ICALP 2011), Part I},
series = {Lecture Notes in Comput. Sci.},
volume = {6755},
publisher = {Springer},
address = {Heidelberg},
year = {2011},
pages = {330--341},
doi = {10.1007/978-3-642-22006-7_28},
}
@article{kelman2020,
author = {Kelman, Esty and Kindler, Guy and Lifshitz, Noam and Minzer, Dor and Safra, Muli},
title = {Towards a proof of the {F}ourier-entropy conjecture?},
journal = {Geom. Funct. Anal.},
volume = {30},
number = {4},
year = {2020},
pages = {1097--1138},
doi = {10.1007/s00039-020-00544-2},
eprint = {1911.10579},
archivePrefix = {arXiv},
}
@article{keller2012,
author = {Keller, Nathan and Mossel, Elchanan and Schlank, Tomer},
title = {A note on the entropy/influence conjecture},
journal = {Discrete Math.},
volume = {312},
number = {22},
year = {2012},
pages = {3364--3372},
doi = {10.1016/j.disc.2012.07.031},
eprint = {1105.2651},
archivePrefix = {arXiv},
}
@article{han2025,
author = {Han, Xiao},
title = {A new bound for the {F}ourier-entropy-influence conjecture},
journal = {Combinatorica},
volume = {45},
number = {1},
year = {2025},
pages = {4},
doi = {10.1007/s00493-024-00133-z},
eprint = {2312.08271},
archivePrefix = {arXiv},
}
@misc{aim-fourier-entropy-influence,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{The Fourier entropy–influence conjecture}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/488-fourier-entropy-influence.md},
note = {Entry 488 at commit a153f46, 2026-10-13},
}
Resolution claims
We prove the Fourier entropy--influence inequality for every linear threshold function, with a constant below $8.937$ and no restrictions on its weights or threshold. The argument applies to regular Boolean functions and gives logarithmic bounds for their Boolean combinations and for unions with bounded variable overlap. Character multiplication preserves the estimates and yields bounds by influence minus variance. Under arbitrary …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-23 | Open → Partially resolved | The registry's curators | Fourier entropy of threshold functions and their compositions v1 recorded from arXiv:2610.16069v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00345, "The Fourier entropy–influence conjecture", clopen.solutions.