MathDB

The Fourier-Entropy-Influence conjecture

Let x=(x1,…,xn)x=(x_1,\dots,x_n) be uniform on −1,1n\\{-1,1\\}^n, and let f:−1,1n→−1,1f:\\{-1,1\\}^n\to\\{-1,1\\} be a Boolean function. Write its Fourier-Walsh coefficients as f^(S)\hat{f}(S) for S⊂[n]S\subset [n], define the total influence by

I(f)=∑S⊂[n]∣S∣f^(S)2,I(f)=\sum_{S\subset[n]}|S|\hat{f}(S)^2,

and define the Fourier entropy by

Ent(f):=∑S⊂[n]f^(S)2log⁡21f^(S)2.Ent(f):=\sum_{S\subset [n]}\hat{f}(S)^2\log_2\frac{1}{\hat{f}(S)^2}.

Fourier-Entropy-Influence conjecture. There exists a constant c>0c>0 such that, for every Boolean function f:−1,1n→−1,1f:\\{-1,1\\}^n\to\\{-1,1\\},

Ent(f)<cI(f).Ent(f)<cI(f).

If true, this would imply that the Fourier spectrum is concentrated on exponentially few coefficients in the total influence. The conjecture was first proposed by Friedgut and Kalai in the 1990s; its status is not specified in the supplied text.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Fourier entropy–influence conjecture

    Let f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\} be a Boolean function. Its Fourier entropy and total influence are

    H⁡(f)=∑S⊂[n]∣f^(S)∣2log⁡1∣f^(S)∣2,I⁡(f)=∑S⊂[n]∣f^(S)∣2∣S∣.\operatorname{\mathbf{H}}(f)=\sum_{S\subset[n]}|\widehat f(S)|^2\log\frac{1}{|\widehat f(S)|^2},\qquad \operatorname{\mathbf{I}}(f)=\sum_{S\subset[n]}|\widehat f(S)|^2|S|.

    Fourier entropy–influence conjecture. There exists a constant c>0c>0 such that, for every nn and every Boolean function ff,

    H⁡(f)≤cI⁡(f).\operatorname{\mathbf{H}}(f)\leq c\operatorname{\mathbf{I}}(f).

    The conjecture asserts that a Boolean function whose Fourier distribution is highly dispersed must have substantial total influence. It is known for several canonical classes and for symmetric Boolean functions, but the general conjecture remains open.

    source: María José González, Paul MacManus and María Cristina Pereyra, “Las funciones booleans y el lema de Bonami”, arXiv:2502.13231 (2025).

Sources & referencesView supporting material

Primary source

Xiao Han, “A new bound for the Fourier-Entropy-Influence conjecture”, arXiv:2312.08271 (2025).

Additional references

2 papers in this index state this conjecture (2023). The statement above is taken from the most recent of them; the others are arXiv:2308.00509.

boolean-functionsfourier-analysisinfluence

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.