Noam Lifshitz: A new hypercontractivity inequality — The proof!

This is a guest post kindly contributed by Noam Lifshitz. Here is a pdf version.  This post is a continuation of the post  To cheer you up in difficult times 3: A guest post by Noam Lifshitz on the new hypercontractivity inequality of Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer, and it gives the proof of the new hypercontractive inequality. We plan a third post where various applications will be mentioned.

Before we get to the post I want to mention that there are a lot of activities on the web. I may devote a special post to links and discussion (and contributing links in the comment section is very welcome.) but meanwhile a few links:  1) Advances in Boolean Function Analysis Lecture Series (thanks to Avishay Tal and Prasad Raghavendra for letting me know); 2) Online course in Foundations of Algebraic Geometry Given by Ravi Vakil from Stanford. You can take the course at varying levels of involvement. (Thanks to Tami Ziegler for telling me) A very very interesting way of online teaching. 3) A site with online mathematical lectures.


Aline Bonami with Szilard Revesz and me (2006). Aline Bonami first proved the 2-point hypercontractive inequality which is very useful in the analysis of Boolean functions. (Leonard Gross proved it independently a few years later and William Beckner found important applications to harmonic analysis.)

Proof of the new hypercontractivity inequality

Our aim is to prove the hypercontractivity theorem for global functions. The proof here is taken from a joint paper with David Ellis and Guy Kindler that’ll soon be out on the Arxiv.

Theorem 1:

\displaystyle \|\mathrm{T}_{1/100}f\|_{4}^{4}\le\sum_{S\subseteq\left[n\right]}\mathbb{E}_{x\in\left\{ 1,\ldots,m\right\} ^{S}}\|L_{S}[f]_{S\rightarrow x}\|_{2}^{4},

Here we use the notations given in the last blog post. Let us first get a feel for our hypercontractivity theorem by proving the {n=1} case. Here the RHS is {\|f\|_{2}^{4}+\|f-\mathbb{E}\left[f\right]\|_{4}^{4}.}

1. Proof of the {n=1} case

We will prove the following slightly stronger version of Theorem 1 for the {n=1} case.

Proposition 2:

Let {f\colon\left\{ 1,\ldots,m\right\} \rightarrow\mathbb{C}.} Let {\rho\le\frac{1}{10}.} Then
\displaystyle \|\mathrm{T}_{\rho}f\|_{4}^{4}\le\|f\|_{2}^{4}+\|f-\mathbb{E}\left[f\right]\|_{4}^{4}.

Proof: Let us write {L\left[f\right]} for {L_{1}\left[f\right]=f-\mathbb{E}\left[f\right].} Rearranging, we have
\displaystyle f=\mathbb{E}\left[f\right]+L\left[f\right].
The noise operator in the {n=1} case is by definition equal to {\rho Id+\left(1-\rho\right)\mathbb{E},} where {\mathbb{E}} is the expectation over {\text{\ensuremath{\left\{ 1,\ldots,m\right\} }}} operator, and {Id} is the identity operator. Hence,
\displaystyle \mathrm{T}_{\rho}f=\mathbb{E}\left[f\right]+\rho L[f].

Now when expanding the 4-norm of the function {\|\mathrm{T}_{1/100}f\|_{4}^{4}}, we obtain

\displaystyle \|\mathrm{T}_{\rho}f\|_{4}^{4}  \le\left|\mathbb{E}\left[f\right]\right|^{4}
\displaystyle +6\rho^{2}\left|\mathbb{E}\left[f\right]\right|^{2}\|Lf\|_{2}^{2}+
\displaystyle  +4\rho^{3}\left|\mathbb{E}\left[f\right]\right|\|L\left[f\right]\|_{3}^{3}+
\displaystyle + \rho^{4}\|L\left[f\right]\|_{4}^{4},

where we used the fact that the expectation of {L\left[f\right]} is 0. When looking at the right hand side of the global hypercontractivity theorem, we see most of the above terms except for the one involving the third norm of the Laplacian. Indeed we have

\displaystyle RHS =\|f\|_{2}^{4}+\|L\left[f\right]\|_{4}^{4}
\displaystyle =\left|\mathbb{E}\left[f\right]\right|^{4}
\displaystyle +2\|L\left[f\right]\|_{2}^{2}\left|\mathbb{E}\left[f\right]\right|^{2}
\displaystyle +\|L\left[f\right]\|_{2}^{4}
\displaystyle +\|L\text{\ensuremath{\left[f\right]\|}}_{4}^{4}.

Hence we see that the only term in the left hand side that doesn’t appear with a greater coefficient in the left hand side is the term {\left|\mathbb{E}\left[f\right]\right|\|L\left[f\right]\|_{3}^{3},} and by AM-GM we have

\displaystyle \left|\mathbb{E}\left[f\right]\right|\|L\left[f\right]\|_{3}^{3} \displaystyle =\mathbb{E}\left[\left|\mathbb{E}\left[f\right]\right|\left|L\left[f\right]\right|^{3}\right]
\displaystyle \le\mathbb{E}\left[\frac{\left|\mathbb{E}\left[f\right]\right|^{2}\left|L\left[f\right]\right|^{2}+\left|L\text{\ensuremath{\left[f\right]}}\right|^{4}}{2}\right]
\displaystyle =\frac{1}{2}\left|\mathbb{E}\left[f\right]\right|^{2}\|L\left[f\right]\|_{2}^{2}+\frac{1}{2}\|L\left[f\right]\|_{4}^{4},

which allows us to upper bound the only term appearing in the left hand side but not in the right hand side by corresponding terms that do appear in the right hand side. \Box

2. Tensorisation lemma

Next we are going to prove a theorem that doesn’t seem to fit to our setting, but we’re going to fit it in by force. Let {X,Y} be finite sets. Let us write {\mathcal{F}\left(X\right)} for the linear space of complex valued functions on {X}. The space {\mathcal{F}\left(X\times Y\right)} can be identified with the space {\mathcal{F}\left(X\right)\otimes\mathcal{F}\left(Y\right),} where a pair of function {f\otimes g} is identified with the function
\displaystyle \left(x,y\right)\mapsto f\left(x\right)g\left(y\right)
in {\mathcal{F}\left(X\times Y\right).}

Given two operators {A_{1}\colon\mathcal{F}\left(X_{1}\right)\rightarrow\mathcal{F}\left(Y_{1}\right),A_{2}\colon\mathcal{F}\left(X_{2}\right)\rightarrow\mathcal{F}\left(Y_{2}\right)}, the operator {A_{1}\otimes A_{2}\colon\mathcal{F}\left(X_{1}\times X_{2}\right)\rightarrow\mathcal{F}\left(Y_{1}\times Y_{2}\right)} is the unique operator sending {f\otimes g} to {A_{1}f\otimes A_{2}g}. We write {A^{\otimes n}} for {A\otimes\cdots\otimes A.} The operator {A_{1}\otimes A_{2}} can also be defined more explictly in terms of its values on functions. The operator {A_{1}\otimes A_{2}} can be understood more explicitly by noting that it is the composition of the operators {A_{1}\otimes I} and {I\otimes A_{2}.} Now the operator {A\otimes I} is given by {A\otimes If\left(x,y\right)=Af_{y}\left(x\right),} where {f_{y}\left(x\right)=f\left(x,y\right).}

Lemma 3: Let {X,Y,Z} be measure spaces with finite underlying sets. Let {A\colon\mathcal{F}\left(X\right)\rightarrow\mathcal{F}\left(Y\right),B\colon\mathcal{F}\left(X\right)\rightarrow\mathcal{F}\left(Z\right)} be operators satisfying

\displaystyle \|Af\|_{4}\le\|Bf\|_{4}

for all functions {f\in\mathcal{F}\left(X\right).}

\displaystyle \|A^{\otimes n}f\|_{4}\le\|B^{\otimes n}f\|_{4}

for all {f\in\mathcal{F}\left(X^{n}\right).}

Here the spaces {X^{n},Y^{n},} and {Z^{n}} are equipped with the product measure, where the measure of an atom is the product of the measures of its coordiates.

Proof: For each {y\in X,} let {g_{y}} be given by {g_{y}:=A^{\otimes\left(n-1\right)}f\left(\cdot,y\right).} As mentioned {A^{\otimes n}f\left(x,y\right)=Ag_{y}\left(x\right).} Hence by hypothesis, we have

\displaystyle \mathbb{E}\left[\left|\mathrm{A}^{\otimes n}f\right|^{4}\right] \displaystyle =\mathbb{E}_{y}\mathbb{E}_{x}\left|Ag_{y}\left(x\right)\right|^{4}
\displaystyle  \le\mathbb{E}_{y}\mathbb{E}_{x}\left|Bg_{y}\left(x\right)\right|^{4}
\displaystyle =\|A^{\otimes n-1}\otimes B\|_{4}^{4}. We may now repeat the same process on each of the other coordinates to replace the {A}s by {B}s one by one. \Box

3. The main idea: Fourifying the 2-norms.

The strategy of our proof is to take the theorem

\displaystyle \|\mathrm{T}_{\rho}f\|_{4}\le\|f\|_{2}^{4}+\|f-\mathbb{E}\left[f\right]\|_{4}^{4},

which we established in the {n=1} case for {\rho\le\frac{1}{10}}, and to turn it into an essentially equivalent statement about 4-norms. We will then get a tensorised statement for general {n}, which we will be able to convert back into our hypercontractivity theorem for global functions. Our idea is to encode our function {f} as a function {\mathrm{En}\left(f\right)\colon\left\{ -1,1\right\} ^{n\left(p-1\right)}\rightarrow\mathbb{R}} satisfying

\displaystyle \mathrm{En}\circ T_{\rho}=\mathrm{T}_{\rho}\circ\mathrm{En}


\displaystyle \|\mathrm{En}f\|_{2}=\|f\|_{2}.

The benefit of working with {\mathrm{En}f} rather than {f} is that in {\left\{ 0,1\right\} ^{n\left(p-1\right)}} one may move between 4-norms and 2-norms by appealing to the hypercontractivity theorem there, which gives

\displaystyle \|\mathrm{T}_{\frac{1}{\sqrt{3}}}\circ\mathrm{En}f\|_{4}\le\|\mathrm{E}nf\|_{2}\le\|\mathrm{En}f\|_{4}

at the cost of some noise.

To define {\mathrm{En}} we use Fourier analysis of Abelian groups. Let us briefly recall it. For simplicity let us assume that {f\colon\left(\mathbb{Z}/p\mathbb{Z}\right)^{n}\rightarrow\mathbb{C},} where {p} is a prime. Let {\omega} be a {p}th root of unity. For any {\gamma\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{n}} we have a character {\chi_{\gamma}\colon\left(\mathbb{Z}/p\mathbb{Z}\right)^{n}\rightarrow\mathbb{C}} given by {\chi_{\gamma}\left(x\right)=\omega^{\left\langle \gamma,x\right\rangle }.} The {\chi_{\gamma}} are an orthonormal basis of {\left(\mathbb{Z}/p\right)^{n}} and we write {f=\sum\hat{f}\left(\gamma\right)\chi_{\gamma}}, where {\hat{f}\left(\gamma\right)=\left\langle f,\chi_{\gamma}\right\rangle .} Note that {\chi_{0}} is the constant function, and so we have

\displaystyle \hat{f}\left(0\right)=\left\langle f,\chi_{0}\right\rangle =\mathbb{E}\left[f\right],

which gives

\displaystyle f=\mathbb{E}\left[f\right]+\sum\hat{f}\left(i\right)\chi_{i}.

Our mission will first be to convert the {2}-norm of a function {f\colon\mathbb{Z}/p\rightarrow\mathbb{R}} to the {4-}norm of a different function.

We define an encoding operator {\mathrm{En}\colon\mathbb{Z}/p\mathbb{Z}\rightarrow\left\{ -1,1\right\} ^{p-1}} by setting

\displaystyle f\mapsto\mathbb{E}\left[f\right]+\sum_{i\in\left\{ 1,\ldots,p-1\right\} }\hat{f}\left(i\right)x_{i}.

We have

\displaystyle \|f\|_{2}^{2}=\|\mathrm{En}f\|_{2}^{2},

as the {\chi_{i}} are orthonormal and so are the {x_{i}.} Moreover, {\mathrm{T}_{\rho}\circ\mathrm{En}=\mathrm{En}\circ T_{\rho}} by the Fourier formula for {\mathrm{T}_{\rho}.} Since {2}-norms are always smaller than 4-norms on probability spaces, we’ve got the following corollary of Proposition 2.

Lemma 4. For all {\rho\le\frac{1}{10}} and all {f\colon\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{C}} we have

\displaystyle \|\mathrm{T}_{\rho}f\|_{4}^{4}\le\|\mathrm{En}\left(f\right)\|_{4}^{4}+\|f-\mathbb{E}\left[f\right]\|_{4}^{4}.

We now reach the final little trick. We define a measure space {Y} whose underlying set is {\mathbb{Z}/p\mathbb{Z}\sqcup\left\{ 0,1\right\} ^{\left\{ p-1\right\} },} and where the measure is given by {\mu\left(i\right)=\frac{1}{p}} for {i\in\mathbb{Z}/p\mathbb{Z}} and {\mu\left(x\right)=\frac{1}{2}^{p-1}} for {x\in\left\{ -1,1\right\} ^{p-1}.} We let {B\colon\mathcal{F}\left(X\right)\rightarrow\mathcal{F}\left(Y\right)} be given by {Bf=\mathrm{En}f} on {\left\{ -1,1\right\} ^{p-1}} and letting it be {f-\mathbb{E}\left[f\right]} on {\mathbb{Z}/p\mathbb{Z}.} This way Lemma 4 takes the form {\|\mathrm{T}_{\rho}f\|_{4}\le\|Bf\|_{4}.}

4. Tensorised operators

The operator {\mathrm{T}_{\rho}} on {\mathbb{Z}/p\mathbb{Z}^{n}} satisfies {\mathrm{T}_{\rho}=\mathrm{T}_{\rho}^{\otimes n},} where the latter {\mathrm{T}_{\rho}} refers to the noise operator on {\mathbb{Z}/p.} The characters {\chi_{\gamma}} satisfy {\chi_{\gamma}=\bigotimes\chi_{\gamma_{i}},} and so we have the Fourier formula

\displaystyle \mathrm{T}_{\rho}f  =\sum_{\gamma}\rho^{\#\left\{ i:\gamma_{i}\ne0\right\} }\hat{f}\left(\gamma\right)\chi_{\gamma}.

We also have

\displaystyle L_{S}\left[f\right]=\bigotimes_{i\in S}\left(f\mapsto f-\mathbb{E}\left[f\right]\right)\otimes\bigotimes_{i\notin S}Id,

and so

\displaystyle L_{S}\left[f\right]=\sum_{\gamma:\gamma_{i}\ne0\text{ for all }i\in S}\hat{f}\left(\gamma\right)\chi_{\gamma}.

This will allow us to conclude that

\displaystyle L_{S}\left[\mathrm{T}_{\rho}f\right]_{S\rightarrow x}=\rho^{\left|S\right|}T_{\rho}L_{S}[f]_{S\rightarrow x}.

We will also encounter the operator {\mathrm{En}^{\otimes n},} which by abusing notation we also call {\mathrm{En}} encodes

\displaystyle f=\sum_{\gamma}\hat{f}\left(\gamma\right)\chi_{\gamma}

as the function {\sum_{\gamma}\widehat{f}\left(\gamma\right)\prod_{i=1}^{n}x_{pi+\gamma_{i}}} on {\left\{ -1,1\right\} ^{n\left(p-1\right)}.}
Now finally we can get to the understanding of the operator {B^{\otimes n}.} The space {Y^{n}} is the disjoint union of {2^{n}} spaces of the form

\displaystyle \left(\mathbb{Z}/p\mathbb{Z}\right)^{S}\times\left(\left\{ -1,1\right\} ^{p-1}\right)^{\left[n\right]\setminus S}.

By definition of the tensor product, for {x,y\in\left(\mathbb{Z}/p\mathbb{Z}\right)^{S}\times\left(\left\{ -1,1\right\} ^{p-1}\right)^{\left[n\right]\setminus S}} is the function

\displaystyle B^{n}f\left(x,y\right)=\mathrm{En}\left(L_{S}[f]_{S\rightarrow x}\right)\left(y\right).

5. Finishing the proof

Proof: Lemmas 3 and 4 yield:

\displaystyle \|\mathrm{T}_{\rho}f\|_{4}^{4}  \le\|B^{\otimes n}f\|_{4}^{4} \displaystyle =\sum_{S\subseteq\left[n\right]}\mathbb{E}_{x\sim\mathbb{Z}/p\mathbb{Z}^{S}}\|\mathrm{En}\left(L_{S}[f]_{S\rightarrow x}\right)\|_{4}^{4},

for any {\rho\le\frac{1}{10}.} We now have

\displaystyle \|\mathrm{T}_{\frac{\rho}{\sqrt{3}}}f\|_{4}^{4} \displaystyle =\sum_{S\subseteq\left[n\right]}(\frac{1}{\sqrt{3}})^{\left|S\right|}\mathbb{E}_{x\sim\mathbb{Z}/p\mathbb{Z}^{S}}\|\mathrm{T}_{\frac{1}{\sqrt{3}}}\left(\mathrm{En}\left(L_{S}[f]_{S\rightarrow x}\right)\right)\|_{4}^{4},
\displaystyle  \le\sum_{S\subseteq\left[n\right]}\mathbb{E}_{x\sim\mathbb{Z}/p\mathbb{Z}^{S}}\|\mathrm{En}\left(L_{S}[f]_{S\rightarrow x}\right)\|_{2}^{4}
\displaystyle =\sum_{S\subseteq\left[n\right]}\mathbb{E}_{x\sim\mathbb{Z}/p\mathbb{Z}^{S}}\|L_{S}[f]_{S\rightarrow x}\|_{2}^{4}.

The first equality follows from the formula {L_{S}\left[\mathrm{T}_{\rho}f\right]_{S\rightarrow x}=\rho^{\left|S\right|}\mathrm{T}_{\rho}L_{S}\left[f\right]_{S\rightarrow x}} and the fact that {\mathrm{T_{\rho}}} commutes with the encoding. The inequality used hypercontractivity on the discrete cube. The last equality follows from the fact that the {\mathrm{En}} operator preserves 2-norms. \Box






This entry was posted in Analysis, Combinatorics, Guest blogger and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s