Revised: June 30, 2013

Published: December 7, 2013

**Keywords:**Boolean functions, harmonic analysis, hypercontractivity, information theory, entropy method

**Categories:**Boolean functions, harmonic analysis, hypercontractivity, information theory, entropy, special issue, Boolean special issue, note

**ACM Classification:**G.2, G.3, F.1.3

**AMS Classification:**68Q87

**Abstract:**
[Plain Text Version]

The Hypercontractive Inequality of Bonami (1968, 1970) and Gross (1975) is equivalent to the following statement: for every $q > 2$ and every function $f : \{-1,1\}^n \to \R$ of Fourier degree at most $m$, $$ \|f \|_q \le (q-1)^{m/2} \|f\|_2. $$ The original proof of this inequality is analytical. Friedgut and Rödl (2001) gave an alternative proof of the slightly weaker Hypercontractive Inequality $ \| f \|_4 \le 28^{m/4} \| f \|_2 $ by combining tools from information theory and combinatorics. Specifically, they recast the problem as a statement about multi-hypergraphs, generalized Shearer's lemma, and used probabilistic arguments to obtain the inequality.

We show that Shearer's Lemma and elementary arguments about the entropy of random variables are sufficient to recover the optimal Hypercontractive Inequality for all even integers $q$.