MathDB

The Fourier-Min-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 with Fourier-Walsh coefficients f^(S)\hat{f}(S) for S⊂[n]S\subset [n]. Let I(f)I(f) denote its total influence,

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

Fourier-Min-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\\},

min⁡S⊂[n]log⁡2f^2(S)<cI(f).\min\limits_{S\subset [n]} \log_2{\hat{f}^2(S)}<cI(f).

This is presented as a weaker conjecture than the Fourier-Entropy-Influence conjecture, but the supplied text gives no evidence resolving it.

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 Min-Entropy–Influence conjecture

    Let f ⁣:{−1,1}n→{−1,1}f \colon \{-1,1\}^n \to \{-1,1\} be a Boolean function. Define its Fourier min-entropy by

    H∞[f]=min⁡S{log⁡1f^(S)2},\mathbf{H}_{\infty}[f]=\min_S\left\{\log\frac{1}{\widehat{f}(S)^2}\right\},

    and let I[f]{\bf I}[f] denote its total influence. Fourier Min-Entropy–Influence conjecture. There exists a constant C>0C>0 such that

    H∞[f]≤C⋅I[f].\mathbf{H}_{\infty}[f]\leq C\cdot {\bf I}[f].

    This is a weaker relaxation of the Fourier Entropy–Influence conjecture because spectral entropy dominates Fourier min-entropy. The paper proves the conjecture for regular read-kk DNFs, while its general validity remains open.

    source: Guy Shalev, “On the Fourier Entropy Influence Conjecture for Extremal Classes”, arXiv:1806.03646 (2019).

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.