MathDB

The Fourier-Min-Entropy-Influence conjecture

About 3 years old · traced to

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 1Other wordings

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).

References

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
Posted

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.