Fourier Entropy-Influence constant

Description of constant

Let $$\begin{gathered} f: \\ {-1,1 \\ }^n\to \\ -1,1 \end{gathered}$$ be a Boolean function with Fourier expansion $f(x)={\sum }_{S\subseteq [n]}\hat{f}(S){\chi }_S(x)$. Its spectral entropy is

$$H({\hat{f}}^2):=\sum _{S\subseteq [n]}\hat{f}(S{)}^2{\log }_2\frac{1}{\hat{f}(S{)}^2},$$

and its total influence is

$$\mathrm{Inf}(f):=\sum _{S\subseteq [n]}\hat{f}(S{)}^2|S|.$$

<a href="#ODWZ2011-defs">[ODWZ2011-defs]</a>

Friedgut and Kalai conjectured that there is a universal constant $C>0$ such that

$$H({\hat{f}}^2)\le C\mathrm{Inf}(f)$$

for every Boolean $f$.

<a href="#ODWZ2011-conj-attr">[ODWZ2011-conj-attr]</a>

We define

$$C_{71}:=\inf \{C>0:H({\hat{f}}^2)\le C\mathrm{Inf}(f)\text{for all Boolean }f\}.$$

The conjecture is equivalent to $C_{71}<\infty$, and this remains open. <a href="#ODWZ2011-open-problem">[ODWZ2011-open-problem]</a>

An explicit balanced, logic-monotone function on 18 variables (exact integer Fourier spectrum and truth table certified exactly), via the O'Donnell--Tan amplification rule $C\ge H/(I-1)$, gives

$$C_{71}>6.521845710923046575,$$

and the same certificate shows the bound holds even restricted to monotone functions.

<a href="#Num2026">[Num2026]</a>

Hence the best established range is

$$6.521845710923046575<C_{71}\le \infty .$$

Known upper bounds

Known lower bounds

Additional comments and links

• Background page on analysis of Boolean functions

References

• <a id="ODWZ2011"></a>[ODWZ2011] O'Donnell, Ryan; Wright, John; Zhou, Yuan. The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2011), Lecture Notes in Computer Science, pp. 330-341 (2011). DOI: https://doi.org/10.1007/978-3-642-22006-7_28. Author PDF: https://www.cs.cmu.edu/~odonnell/papers/fei.pdf. Google Scholar
• <a id="ODWZ2011-conj-attr"></a>[ODWZ2011-conj-attr] loc: Author PDF p.1, Abstract quote: "In 1996, Friedgut and Kalai made the Fourier Entropy-Influence Conjecture: For every Boolean function $$\begin{gathered} f: \\ {-1,1 \\ }^n\to \\ -1,1 \end{gathered}$$ it holds that $H[{\hat{f}}^2]\le C\cdot I[f]$, where $H[{\hat{f}}^2]$ is the spectral entropy of $f$, $I[f]$ is the total influence of $f$, and $C$ is a universal constant."
• <a id="ODWZ2011-defs"></a>[ODWZ2011-defs] loc: Author PDF p.2, Section 1, paragraph after the conjecture display quote: "The quantity $H[{\hat{f}}^2]=\sum \hat{f}(S{)}^2\log \frac{1}{\hat{f}(S{)}^2}$ on the left is the spectral entropy or Fourier entropy of $f$. It ranges between $0$ and $n$ and measures how 'spread out' $f$'s Fourier spectrum is. The quantity $I[f]=\sum \hat{f}(S{)}^2|S|$ appearing on the right is the total influence or average sensitivity of $f$."
• <a id="ODWZ2011-open-problem"></a>[ODWZ2011-open-problem] loc: Author PDF p.2, Section 1, paragraph beginning "One of the most longstanding..." quote: "One of the most longstanding and important open problems in the field is the Fourier Entropy-Influence (FEI) Conjecture made by Friedgut and Kalai in 1996 [6]:"

• <a id="OT2013"></a>[OT2013] O'Donnell, Ryan; Tan, Li-Yang. A Composition Theorem for the Fourier Entropy-Influence Conjecture. In: Automata, Languages, and Programming (ICALP 2013), Lecture Notes in Computer Science, pp. 780-791 (2013). DOI: https://doi.org/10.1007/978-3-642-39206-1_66. arXiv PDF: https://arxiv.org/pdf/1304.1347.pdf. Google Scholar
• <a id="OT2013-lb-6-278"></a>[OT2013-lb-6-278] loc: arXiv PDF p.1, Abstract quote: "Our techniques also yield an explicit function with the largest known ratio of $C\ge 6.278$ between $H[f]$ and $\mathrm{Inf}[f]$, improving on the previous lower bound of $4.615$."

• <a id="Hod2017"></a>[Hod2017] Hod, Rani. Improved Lower Bounds for the Fourier Entropy/Influence Conjecture via Lexicographic Functions. arXiv:1711.00762, 2017. arXiv. PDF.
• <a id="Hod2017-thm4.4"></a>[Hod2017-thm4.4] loc: arXiv PDF p. 15, Theorem 4.4 quote: "Any constant $C$ in Conjecture 1.1 satisfies $C\ge \beta (1/2)>6.4547837$, even when restricted to monotone functions."

• <a id="MI2026"></a>[MI2026] Mosaic Intelligence (@111111). An improved lower bound for the Fourier Entropy-Influence constant from explicit balanced functions. Certificate archive, submitted to this repository (2026).
• <a id="MI2026-bound"></a>[MI2026-bound] loc: certificate archive and this pull request quote: "C_71 > 6.4901128435233943 — and, by the same logic-monotone certificate, even restricted to monotone functions (full floor-truncated value 6.49011284352339435967722960726821776674269968263998854502375); certified by the replayable script below."

• <a id="MI2026b"></a>[MI2026b] Mosaic Intelligence (@111111). A certified n=17 lower bound for the Fourier Entropy-Influence constant. Certificate archive, submitted to this repository (2026).
• <a id="MI2026b-bound"></a>[MI2026b-bound] loc: certificate archive and this pull request quote: "C_71 > 6.514326913930565372 — and, by the same logic-monotone certificate, even restricted to monotone functions (full floor-truncated value 6.51432691393056537265062517595609726535914349523745739524537); certified by the replayable script below."

• <a id="Num2026"></a>[Num2026] Numaro (numaro.tech). A certified n=18 lower bound for the Fourier Entropy-Influence constant. Certificate archive, submitted to this repository (2026).
• <a id="Num2026-bound"></a>[Num2026-bound] loc: certificate archive, README and check_c71_n18.py output. quote: "C_71 > 6.521845710923046575 — and, by the same logic-monotone certificate, even restricted to monotone functions (full floor-truncated value 6.5218457109230465756581439729485784683666); certified by the replayable script; the strict-improvement comparison is made against the previous record's certified upper endpoint, so the gain — exactly 1/133 — is itself certified."

What counts as progress

• A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
• A formal proof (Lean) of a known bound, or a precise error in a claimed one.
• New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.