Entropy influence conjecture

This article includes a list of general references but lacks sufficient corresponding inline citations. Please help improve this article by introducing more precise citations. (April 2011) (Learn how and when to remove this message)

In mathematics, the entropy influence conjecture is a statement about Boolean functions originally conjectured by Ehud Friedgut and Gil Kalai in 1996.

Statement

For a function ${\displaystyle f:\{-1,1\}^{n}\to \{-1,1\},}$ note its Fourier expansion

${\displaystyle f(x)=\sum _{S\subset [n]}{\widehat {f}}(S)x_{S},{\text{ where }}x_{S}=\prod _{i\in S}x_{i}.}$

The entropy–influence conjecture states that there exists an absolute constant C such that ${\displaystyle H(f)\leq CI(f),}$ where the total influence ${\displaystyle I}$ is defined by

${\displaystyle I(f)=\sum _{S}|S|{\widehat {f}}(S)^{2},}$

and the entropy ${\displaystyle H}$ (of the spectrum) is defined by

${\displaystyle H(f)=-\sum _{S}{\widehat {f}}(S)^{2}\log {\widehat {f}}(S)^{2},}$

(where x log x is taken to be 0 when x = 0).

See also

• Analysis of Boolean functions

References

• Unsolved Problems in Number Theory, Logic and Cryptography
• The Open Problems Project, discrete and computational geometry problems