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.[1]

Statement

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

f ( x ) = ∑ S ⊂ [ n ] f ^ ( S ) x S ,  where  x S = ∏ i ∈ S x i . {\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 H ( f ) ≤ C I ( f ) , {\displaystyle H(f)\leq CI(f),} where the total influence I {\displaystyle I} is defined by

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

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

H ( f ) = − ∑ S f ^ ( S ) 2 log ⁡ f ^ ( S ) 2 , {\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

References

  1. ^ Friedgut, Ehud; Kalai, Gil (1996). "Every monotone graph property has a sharp threshold". Proceedings of the American Mathematical Society. 124 (10): 2993–3002. doi:10.1090/s0002-9939-96-03732-x.
  • Unsolved Problems in Number Theory, Logic and Cryptography
  • The Open Problems Project, discrete and computational geometry problems