Skip to content

71a.md

Latest commit

 

History

History
121 lines (87 loc) · 8.91 KB

71a.md

File metadata and controls

121 lines (87 loc) · 8.91 KB
Raw

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]
$&gt;6.4547837$ [Hod2017] Theorem 4.4 gives $C\ge \beta(1/2)&gt;6.4547837$, even when restricted to monotone functions. [Hod2017-thm4.4]
$&gt;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]
$&gt;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]
$&gt;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

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)&gt;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

Prepared with assistance from ChatGPT 5.2 Pro. This update was prepared with assistance from Codex. Citations and mathematical details were reviewed by the human contributor.