Entropy influence conjecture

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 [math]\displaystyle{ f: \{-1,1\}^n \to \{-1,1\}, }[/math] note its Fourier expansion

[math]\displaystyle{ f(x) = \sum_{S \subset [n]} \widehat{f}(S) x_S, \text{ where } x_S = \prod_{i \in S} x_i. }[/math]

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

[math]\displaystyle{ I(f) = \sum_S |S| \widehat{f}(S)^2, }[/math]

and the entropy [math]\displaystyle{ H }[/math] (of the spectrum) is defined by

[math]\displaystyle{ H(f) = - \sum_S \widehat{f}(S)^2 \log \widehat{f}(S)^2 , }[/math]

(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