pdf icon
Volume 9 (2013) Article 29 pp. 889-896 [Note]
Special Issue on Analysis of Boolean Functions
Hypercontractivity Via the Entropy Method
Received: January 15, 2013
Revised: June 30, 2013
Published: December 7, 2013
Download article from ToC site:
[PDF (205K)]    [PS (606K)]    [PS.GZ (219K)]
[Source ZIP]
Keywords: Boolean functions, harmonic analysis, hypercontractivity, information theory, entropy method
ACM Classification: G.2, G.3, F.1.3
AMS Classification: 68Q87

Abstract: [Plain Text Version]

$ \newcommand{\R}{{\mathbb R}} $

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$.