Theory of Computing
-------------------
Title : Hypercontractivity Via the Entropy Method
Authors : Eric Blais and Li-Yang Tan
Volume : 9
Number : 29
Pages : 889-896
URL : http://www.theoryofcomputing.org/articles/v009a029
Abstract
--------
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 Rodl
(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$.