Chapter 9: Basics of hypercontractivity

In 1970, Bonami proved the following central result:

The Hypercontractivity Theorem Let $f : \{-1,1\}^n \to {\mathbb R}$ and let ${1 \leq p \leq q \leq \infty}$. Then $\|\mathrm{T}_\rho f\|_q \leq \|f\|_p$ for $0 \leq \rho \leq \sqrt{\tfrac{p-1}{q-1}}$.

As stated, this theorem may look somewhat opaque. In this chapter we consider some special cases of it which are easier to understand, easier to prove, and which encompass almost all of the theorem’s uses. The proof of the full theorem is deferred to Chapter 10. The special cases in this chapter are the following:

Bonami Lemma Let $f : \{-1,1\}^n \to {\mathbb R}$ have degree $k$. Then $\|f\|_4 \leq \sqrt{3}^k \|f\|_2$

The fundamental idea of this statement is that if ${\boldsymbol{x}} \sim \{-1,1\}^n$ and $f : \{-1,1\}^n \to {\mathbb R}$ has low degree then the random variable $f({\boldsymbol{x}})$ is quite “reasonable”; e.g., it is “nicely” distributed around its mean. The Bonami Lemma has a very easy inductive proof and is already powerful enough to obtain many of the well-known applications of “hypercontractivity”, including the KKL Theorem (proven at the end of this chapter) and the Invariance Principle.

$\mathbf{(2,q)}$-Hypercontractivity Theorem Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $2 \leq q \leq \infty$. Then $\|\mathrm{T}_{1/\sqrt{q-1}} f\|_q \leq \|f\|_2$. As a consequence, if $f$ has degree at most $k$ then $\|f\|_q \leq \sqrt{q-1}^k \|f\|_2$.

This theorem quantifies the extent to which $\mathrm{T}_\rho$ is a “smoothing” operator; equivalently, it gives even more control over the “reasonableness” of low-degree polynomials. Its consequences include a generalization of the Level-$1$ Inequality (from Chapter 5.4) to “Level-$k$ Inequalities”, as well as a Chernoff-like tail bound for low-degree polynomials of random bits.

$\mathbf{(p,2)}$-Hypercontractivity Theorem Let $f : \{-1,1\}^n \to {\mathbb R}$ and let $1 \leq p \leq 2$. Then $\|\mathrm{T}_{\sqrt{p-1}} f\|_2 \leq \|f\|_p$. Equivalently, $\mathbf{Stab}_\rho[f] \leq \|f\|_{1+\rho}^2$ for $0 \leq \rho \leq 1$.

This theorem is actually “equivalent” to the $(2,q)$-Hypercontractivity Theorem by virtue of Hölder’s inequality. When specialized to the case of $f : \{-1,1\}^n \to \{0,1\}$ it gives a precise quantification of the fact that the “noisy hypercube graph” is a “small-set expander”. Qualitatively, this means that if $A \subseteq \{-1,1\}^n$ is “small”, ${\boldsymbol{x}} \sim A$, and $\boldsymbol{y} \sim N_\rho(x)$, then $\boldsymbol{y}$ is very unlikely to be in $A$.

2 comments to Chapter 9: Basics of hypercontractivity

  • david

    Shouldn’t the statement of the Hypercontractivity lemma cover the case $p = q$ as well? (i.e., $p \le q$ instead of $p < q$). It follows from your statemente by continuity, but since you're already using the equality case in the $(2,q)$-Hypercontractivity Theorem it makes sense to include it.

Leave a Reply to david Cancel reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>