Back to Boolean Function Analysis
Back to notes

Hypercontractivity

80%

Introduction

Name Result
Bonami Lemma For degree $k$ polynomial $f$, $\|f\|_4\leq\sqrt{3}^k\|f\|_2$
$(2,4)$-Hypercontractivity Theorem $\|T_{1/\sqrt{3}}f\|_4\leq\|f\|_2$
$(4/3,2)$-Hypercontractivity Theorem $\|T_{1/\sqrt{3}}f\|_{4/3}\leq\|f\|_2$
$(2,q)$-Hypercontractivity Theorem For any $2\leq q\leq\infty$, $\|T_{1/\sqrt{q-1}}f\|_{q}\leq\|f\|_2$
$(p,2)$-Hypercontractivity Theorem For any $1\leq p\leq2$, $\|T_{\sqrt{p-1}}f\|_2\leq\|f\|_p$
Two-Function Hypercontractivity Induction Theorem For any $0\leq\rho\leq1$, $\mathbb{E}_{\bx,\sim_{\rho}\by}[f(\bx)f(\by)]\leq\|f\|_p\|g\|_{q}$
The Hypercontractivity Theorem For any $1\leq p\leq q\leq\infty$ and $0<\rho<\sqrt{\frac{p-1}{q-1}}$, $\|T_{\rho}f\|_q\leq\|f\|_p$
The General Hypercontractivity Theorem

Bonami Lemma

Let $f:\Bit^n\rightarrow\bbR$ be a polynomial with degree up to $k$. Then, $$\norm{f}_4\leq\sqrt{3}^k\norm{f}_2.$$

Let’s prove by induction on the number of input bits. Clearly that the inequality holds for polynomial with one input bit. Now, suppose the inequality holds for polynomial with $n-1$ input bits.

Consider the decomposition on derivatives: $f(x)=x_nD_{n-1}+E_{n-1}(x’)$ where $x’=(x_1,\dots,x_{n-1})$, $D_{n-1}=\frac{d}{dx_n}f(x)$, and $E_{n-1}[x’]=\mathbb{E}_{\bx_n}[f(x)]$.

As $\mathbb{E}[\bx_n^tg(\bx’)]=\mathbf{1}_{t\text{ is even}}\cdot\mathbb{E}[g(\bx’)]$, we have \begin{align} \norm{f}_4^4 &= \mathbb{E}[\bx_n^4D_{n-1}(\bx’)^4+4\bx_n^3D_{n-1}(\bx’)^3E_{n-1}(\bx’)+6\bx_n^2D_{n-1}(\bx’)^2E_{n-1}(\bx’)^2\nonumber\\
&+4\bx_nD_{n-1}(\bx’)E_{n-1}(\bx’)^3+E_{n-1}(\bx’)^4]\\
&=\mathbb{E}[D_{n-1}(\bx’)^4 + 6D_{n-1}(\bx’)^2E_{n-1}(\bx’)^2+E_{n-1}(\bx’)^4]. \end{align}

By induction hypothesis, we have $\mathbb{E}[D_{n-1}(\bx’)^4]\leq9^{k-1}\norm{D_{n-1}}_2^2$ and $\mathbb{E}[E_{n-1}(\bx’)^4]\leq9^k\norm{E_{n-1}}_2^2$. Thus, \begin{align} \norm{f}_4^4 &\leq9^{k-1}\norm{D_{n-1}}_2^2+6\norm{D_{n-1}}_2\cdot\norm{E_{n-1}}_2+9^k\norm{E_{n-1}}_2^2\\
&\leq9^k(\norm{D_{n-1}}_2^2+2\norm{D_{n-1}}_2\cdot\norm{E_{n-1}}_2+\norm{E_{n-1}}_2^2)\\
&=9^k(\norm{D_{n-1}}_2+\norm{E_{n-1}}_2)^2 = 9^k\norm{f}_2^4. \end{align} The last inequality is because $$\norm{f}_2^2 = \mathbb{E}[(x_nD_{n-1}+E_{n-1}(x’))^2]=\norm{D_{n-1}}_2^2+\norm{E_{n-1}}_2^2.$$

$(2,4)$-Hypercontractivity Theorem

Let $f:\Bit^n\rightarrow\bbR$, $$\norm{T_{1/\sqrt{3}}f}_4\leq\norm{f}_2.$$

The theorem can be proved from Bonami lemma with the tensorization trick. See Exercise 9.6 here. The basic idea is the following inequality. $$\norm{T_{1/\sqrt{3}}f^{=k}}_4=\frac{1}{\sqrt{3}^k}\norm{f^{=k}}_4\leq\norm{f^{=k}}_2.$$

For simplicity, we adopt the induction method to prove the theorem. Let $x=(x_1,\dots,x_n)$, $x’=(x_1,\dots,x_{n-1})$, and $T=T_{1/\sqrt{3}}$, we have $T_{1/\sqrt{3}}f = \frac{1}{\sqrt{3}}x_nTD_{n-1}+TE_{n-1}$. Furthermore, \begin{align} \norm{T_{1/\sqrt{3}}f}_4^4 &= \mathbb{E}[(\frac{1}{\sqrt{3}}x_nTD_{n-1}+TE_{n-1})^4]\\
&= \mathbb{E}[\frac{1}{9}\cdot \bx_n^4TD_{n-1}(\bx’)^4+\frac{4}{3\sqrt{3}}\cdot\bx_n^3TD_{n-1}(\bx’)^3TE_{n-1}(\bx’)\\
&+\frac{6}{9}\cdot\bx_n^2TD_{n-1}(\bx’)^2TE_{n-1}(\bx’)^2+\frac{4}{\sqrt{3}}\bx_nTD_{n-1}(\bx’)TE_{n-1}(\bx’)^3+TE_{n-1}(\bx’)^4]\\
&=\mathbb{E}[\frac{1}{9}\cdot TD_{n-1}(\bx’)^4+\frac{2}{3}\cdot TD_{n-1}(\bx’)^2TE_{n-1}(\bx’)^2+TE_{n-1}(\bx’)^4] \end{align}

By induction hypothesis, $\mathbb{E}[TD_{n-1}(\bx’)^4]\leq \mathbb{E}[D_{n-1}^2]^2$ and $\mathbb{E}[TE_{n-1}(\bx’)^4]\leq \mathbb{E}[E_{n-1}^2]^2$. That is, \begin{align} \norm{T_{1/\sqrt{3}}f}_4^4 &\leq \mathbb{E}[D_{n-1}(\bx’)^2]^2+2\mathbb{E}[D_{n-1}(\bx’)^2E_{n-1}(\bx’)^2]+\mathbb{E}[E_{n-1}(\bx’)^2]^2\\
&\leq (\norm{D_{n-1}}_1^2+\norm{E_{n-1}}_2^2)^2\\
&= \norm{f}_2^4. \end{align}

$(4/3,2)$-Hypercontractivity Theorem

Let $f:\Bit^n\rightarrow\bbR$, $$\norm{T_{1/\sqrt{3}}f}_{2}\leq\norm{f}_2.$$

The proof is simply based on Hölder inequality and (2,4)-Hypercontractivity. \begin{align} \norm{T_{1/\sqrt{3}}f}_2^2 &= \langle T_{1/\sqrt{3}}f,T_{1/\sqrt{3}}f \rangle\\
&= \langle f,T_{1/3}f\rangle\\
&\leq \norm{f}_{4/3}\cdot\norm{T_{1/3}f}_{2}=\norm{f}_{4/3}\cdot\norm{T_{1/\sqrt{3}}T_{1/\sqrt{3}}f}_2\\
&\leq \norm{f}_{4/3}\cdot\norm{T_{1/\sqrt{3}}f}_2. \end{align} By dividing $\norm{T_{1/\sqrt{3}}f}_2$ on both side, we yield the (4/3,2)-Hypercontractivity.

Hypercontractivity Theorem for single bit

Let $\bfX$ be a random variable, $1\leq p<q<\infty$, and $0\leq\rho\leq1$. We say $\bfX$ is $(p,q,\rho)$-hypercontractive if for any $a,b\in\bbR$, $$\norm{a+\rho b\bfX}_q\leq\norm{a+b\bfX}_p.$$

• If $\bfX$ is hypercontractive, then $\mathbb{E}[\bfX]=0$.
• If $\bfX$ is $(p,q,\rho)$-hypercontractive, then for any $0\leq\rho’\leq\rho$, $\bfX$ is $(p,q,\rho’)$-hypercontractive.

$(p,2)$-Hypercontractivity Theorem

Let $\bfX$ be uniformly distributed on $\Bit$, then for any $1\leq p\leq2$, $\bfX$ is $(p,2,\sqrt{p-1})$-hypercontractive.

As Euclidean norm is scaling invariant, it suffices to consider $a=1$ and $b\in\bbR$. Also, we can assume $a+b\bfX\geq0$. That is, assume $\card{b}\leq1$. Note that the case when $b=1$ can be extended by continuity. Thus, in the following we assume $\card{b}<1$.

Our goal is to show that $$\norm{1+\sqrt{p-1}b\bfX}_2^2\leq\norm{1+b\bfX}_p^2.$$

$(2,q)$-Hypercontractivity Theorem

Let $\bfX$ be uniformly distributed on $\Bit$, then for any $q\geq2$, $\bfX$ is $(2,q,1/\sqrt{q-1})$-hypercontractive.