An Information-Theoretic Proof of a Hypercontractive Inequality

Abstract

The famous hypercontractive estimate discovered independently by Gross, Bonami and Beckner has had a great impact on combinatorics and theoretical computer science since it was first used in this setting in a seminal paper by Kahn, Kalai and Linial. The usual proofs of this inequality begin with two-point space, where some elementary calculus is used and then generalised immediately by introducing another dimension using submultiplicativity (Minkowski’s integral inequality). In this paper, we prove this inequality using information theory. We compare the entropy of a pair of correlated vectors in {0,1}n to their separate entropies, analysing them bit by bit (not as a figure of speech, but as the bits are revealed) using the chain rule of entropy.

Keywords

• entropy
• hypercontractive inequality
• boolean functions