Submit progress

on Fourier Entropy-Influence constant ($C_{71}$)

The statement

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.

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.