Fourier Entropy-Influence constant

Description of constant

Let $f:\{-1,1\}^n\to\{-1,1\}$ 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\,\lvert S\rvert.\]

[ODWZ2011-defs]

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$.

[ODWZ2011-conj-attr]

We define

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

The conjecture is equivalent to $C_{71}<\infty$, and this remains open. [ODWZ2011-open-problem]

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.

[Num2026]

Hence the best established range is

\[6.521845710923046575\ <\ C_{71}\ \le\ \infty.\]

Known upper bounds

Bound	Reference	Comments
$\infty$		No finite universal constant is currently known. [ODWZ2011-open-problem]

Known lower bounds

Bound	Reference	Comments
$0$		Trivial bound from nonnegativity.
$6.278$	[OT2013]	Explicit example with ratio at least $6.278$. [OT2013-lb-6-278]
$>6.4547837$	[Hod2017]	Theorem 4.4 gives $C\ge \beta(1/2)>6.4547837$, even when restricted to monotone functions. [Hod2017-thm4.4]
$>6.4901128435233943$	[MI2026]	finite balanced logic-monotone function on 14 variables (explicit truth table), via O’Donnell–Tan amplification $C \ge H/(I-1)$; certified by exact-rational spectrum + interval arithmetic. The seed is monotone and composition preserves monotonicity, so the same bound holds even restricted to monotone functions. [MI2026-bound]
$>6.514326913930565372$	[MI2026b]	Explicit balanced logic-monotone function on 17 variables via the [OT2013] amplification rule $C \ge H/(I-1)$; exact influence $261/128$; certified by exact-rational spectrum + interval arithmetic; replayable certificate, see PR. The function is monotone, so the same bound holds even restricted to monotone functions. [MI2026b-bound]
$>6.521845710923046575$	[Num2026]	Explicit balanced logic-monotone function on 18 variables via the [OT2013] amplification rule $C \ge H/(I-1)$; exact influence $261/128$; obtained from the [MI2026b] function by equalising the auxiliary-variable action (the single 4-cell auxiliary is split 2+2 with the new 18th variable), raising $H$ by exactly twice the moved spectral weight at identical influence — certified gain exactly $1/133$; exact-rational spectrum + interval arithmetic; replayable single-file certificate. The function is monotone, so the same bound holds even restricted to monotone functions. [Num2026-bound]

Additional comments and links

Background page on analysis of Boolean functions

References

[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
- [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 $f : \{-1, 1\}^n \to \{-1, 1\}$ 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.”
- [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\lvert S\rvert$ appearing on the right is the total influence or average sensitivity of $f$.”
- [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]:”
[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
- [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$.”
[Hod2017] Hod, Rani. Improved Lower Bounds for the Fourier Entropy/Influence Conjecture via Lexicographic Functions. arXiv:1711.00762, 2017. arXiv. PDF.
- [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.”
[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).
- [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.”
[MI2026b] Mosaic Intelligence (@111111). A certified n=17 lower bound for the Fourier Entropy-Influence constant. Certificate archive, submitted to this repository (2026).
- [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.”
[Num2026] Numaro (numaro.tech). A certified n=18 lower bound for the Fourier Entropy-Influence constant. Certificate archive, submitted to this repository (2026).
- [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.”
  Contribution notes