OpenFrontiers
Join
← Back to the index
OP-12086OpenComputational complexity

Fourier Entropy-Influence constant (C71C_{71})

Fourier Entropy-Influence constant: determine C71C_{71} or improve its bounds; the repository records 6.278 (6.521845710923046575*) (lower) and ∞\infty (upper).

MSC 06E30 · Boolean functionsMSC 94A17 · Measures of information, entropy

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Let f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} be a Boolean function with Fourier expansion f(x)=∑S⊆[n]f^(S)χS(x)f(x)=\sum_{S\subseteq[n]}\hat f(S)\chi_S(x). Its spectral entropy is

H(f^2) := ∑S⊆[n]f^(S)2log⁡21f^(S)2,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

Inf(f) := ∑S⊆[n]f^(S)2 ∣S∣.\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>0C>0 such that

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

for every Boolean ff.

[ODWZ2011-conj-attr]

We define

C71 := inf⁡{C>0: H(f^2)≤C Inf(f) for all Boolean f}.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 C71<∞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≥H/(I−1)C \ge H/(I-1), gives

C71 > 6.521845710923046575,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 < C71 ≤ ∞.6.521845710923046575\ <\ C_{71}\ \le\ \infty.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

References (from the repository page)

  • [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→{−1,1}f : \{-1, 1\}^n \to \{-1, 1\} it holds that H[f^2]≤C⋅I[f]H[\hat f^2] \le C \cdot I[f], where H[f^2]H[\hat f^2] is the spectral entropy of ff, I[f]I[f] is the total influence of ff, and CC is a universal constant."

  • [ODWZ2011-defs] loc: Author PDF p.2, Section 1, paragraph after the conjecture display quote: "The quantity H[f^2]=∑f^(S)2log⁡1f^(S)2H[\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 ff. It ranges between 00 and nn and measures how 'spread out' ff's Fourier spectrum is. The quantity I[f]=∑f^(S)2∣S∣I[f] = \sum \hat f(S)^2\lvert S\rvert appearing on the right is the total influence or average sensitivity of ff."

  • [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≥6.278C \ge 6.278 between H[f]H[f] and Inf[f]\mathrm{Inf}[f], improving on the previous lower bound of 4.6154.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 CC in Conjecture 1.1 satisfies C≥β(1/2)>6.4547837C\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."

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound 6.278 (6.521845710923046575*); best known upper bound ∞\infty. Values marked with an asterisk have minimal verification.

Known upper bounds

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

Known lower bounds

Bound Reference Comments
00 Trivial bound from nonnegativity.
6.2786.278 [OT2013] Explicit example with ratio at least 6.2786.278. [OT2013-lb-6-278]
>6.4547837>6.4547837 [Hod2017] Theorem 4.4 gives C≥β(1/2)>6.4547837C\ge \beta(1/2)>6.4547837, even when restricted to monotone functions. [Hod2017-thm4.4]
>6.4901128435233943>6.4901128435233943 [MI2026] finite balanced logic-monotone function on 14 variables (explicit truth table), via O'Donnell–Tan amplification C≥H/(I−1)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>6.514326913930565372 [MI2026b] Explicit balanced logic-monotone function on 17 variables via the [OT2013] amplification rule C≥H/(I−1)C \ge H/(I-1); exact influence 261/128261/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>6.521845710923046575 [Num2026] Explicit balanced logic-monotone function on 18 variables via the [OT2013] amplification rule C≥H/(I−1)C \ge H/(I-1); exact influence 261/128261/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 HH by exactly twice the moved spectral weight at identical influence — certified gain exactly 1/1331/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]
References
  1. [1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Fourier Entropy-Influence constant ($C_{71}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.