Strengthening Han's Fourier Entropy-Influence Inequality via an Information-Theoretic Proof

Abstract

We strengthen Han's Fourier entropy-influence inequality $$H[\hat{f}]\le C_{1}I(f)+C_2\sum _{i\in [n]}{I}_i(f)\ln \frac{1}{I_i(f)}$$ originally proved for $\{-1,1\}$-valued Boolean functions with $C_1=3+2\ln 2$ and $C_2=1$. We show, by a short information-theoretic proof, that it in fact holds with sharp constants $C_1=C_2=1$ for all real-valued Boolean functions of unit $L^2$-norm, thereby establishing the inequality as an elementary structural property of Shannon entropy and influence.

The result has already appeared in Claim 4.1 "A Note on the Entropy Influence Conjecture" by N. Keller, E. Mossel, and T. Schlank, on arXiv eprint: arXiv:1105.2651