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

This is a guest post kindly contributed by Noam Lifshitz.

My short introduction: There is nothing like a new hypercontractivity inequality to cheer you up in difficult times and this post describes an amazing new hypercontractivity inequality.  The post describes a recent hypercontractive inequality by Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer (KLLM) from their paper: Hypercontractivity for global functions and sharp thresholds. (We reported on this development in this post. By now, there are quite a few important applications.) And for Talagrand’s generic chaining inequality, see this beautiful blog post by Luca Trevisan.

Barry Simon coined the term “hypercontractivity” in the 70s.  (We asked about it here and Nick Read was the first to answer.) A few months ago Barry told us about the early history of hypercontractivity inequalities, and, in particular, the very entertaining story on William Beckner’s Ph. D. qualifying exam.

And now to Noam Lifshitz’s guest post.

Hypercontractivity on product spaces

Analysis of Boolean functions (ABS) is a very rich subject. There are many works whose concern is generalising some of the results on analysis of Boolean functions to other (product) settings, such as functions on the multicube {\left[m\right]^{n},} where {m} is very large. However, in some of these cases the fundemental tools of AOBF seem to be false for functions on the multicube {f\colon\left[m\right]^{n}\rightarrow\mathbb{R}.} However, in the recent work of Keevash, Long, Minzer, and I. We introduce the notion of global functions. These are functions that do not strongly depend on a small set of coordinates. We then show that most of the rich classical theory of AOBF can in fact be generalised to these global functions. Using our machinery we were able to strengthen an isoperimetric stability result of Bourgain, and to make progress on some Erdos-Ko-Rado type open problem.

We now discuss some background on the Fourier analysis on functions on the multicube {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}.}

Derivatives and Laplacians

There are two fundemental types of operators on Boolean functions {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.} The first ones are the discrete derivatives, defined by {D_{i}[f]=\frac{f_{i\rightarrow1}-f_{i\rightarrow0}}{2},} where {f_{i\rightarrow x}} denotes the we plug in the value {x} for the {i}th coordinate. The other closely related ones are the laplacians defined by {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate.

The laplacians and the derivatives are closely related. In fact, when we plug in {1} in the {i}th coordinate, we obtain {L_{i}[f]_{i\rightarrow1}=D_{i}[f]}, and when we plug in {0} in it, we obtain {L_{i}[f]_{i\rightarrow0}=-D_{i}[f].}

The 2-norm of the {i}th derivative is called the {i}th influence of {f} as it measures the impact of the {i}th coordinate on the value of {f}. It’s usually denoted by {\mathrm{Inf}_{i}[f]}.

Generalisation to functions on the multicube

For functions on the multicube we don’t have a very good notion of a discrete derivative, but it turns out that it will be enough to talk about the laplacians and their restrictions. The Laplacians are again defined via {L_{i}f\left(x\right):=f\left(x\right)-\mathbb{E}f\left(\mathbf{y}\right),} where {\mathbf{y}} is obtained from {x} by resampling its {i}th coordinate. It turns out that in the continuous cube it’s not enough to talk about Laplacians of coordinate, and we will also have to concern ourselves with Laplacians of sets. We define the generalised Laplacians of a set {S} by composing the laplacians corresponding to each coordinate in {S} {L_{\left\{ i_{1},i_{2},\ldots,i_{r}\right\} }\left[f\right]:=L_{i_{1}}\circ\cdots\circ L_{i_{r}}\left[f\right].}

We now need to convince ourselves that these laplacians have something to do with the impact of {S} on the outcome of {f.} In fact, the following notions are equivalent

  1. For each {x,y\in\left[m\right]^{S}}we have {\|f_{S\rightarrow x}-f_{S\rightarrow y}\|_{2}<\delta_{1}}
  2. For each {x\in\left[m\right]^{S}} we have {\|L_{S}[f]_{S\rightarrow x}\|_{2}<\delta_{2},}

in the sense that if (1) holds then (2) holds with {\delta_{2}=C^{\left|S\right|}\delta_{1}} and conversely if (2) holds, then (1) holds with {\delta_{1}=C^{\left|S\right|}\delta_{2}.}

The main theme of our work is that one can understand global function on the continuous cube, and these are functions that satisfy the above equivalent notions for all small sets {S}.

Noise operator, hypercontractivity, and small set expansion

For {\rho\in\left(0,1\right),} the noise operator is given by {\mathrm{T}_{\rho}\left[f\right]\left(x\right)=\mathbb{E}f\left(\mathbf{y}\right)} when {\mathbf{y}} is obtained from {x} by independently setting each coordinate {\mathbf{y}_{i}} to be {\mathbf{x}_{i}} with probability {\rho} and resampling it with uniformly out of {\left\{ -1,1\right\} } otherwise. The process which given {x} outputs {\mathbf{y}} is called the {\rho}-noisy process, and we write {\mathbf{y}\sim N_{\rho}\left(x\right).}

The Bonami hypercontractivity theorem, which was then generalised by Gross and Beckner states that the noise operator {T_{\frac{1}{\sqrt{3}}}} is a contraction from {L^{2}\left(\left\{ 0,1\right\} ^{n}\right)} to {L^{4}\left(\left\{ 0,1\right\} ^{n}\right),} i.e.

\displaystyle \|\mathrm{T}_{\frac{1}{\sqrt{3}}}f\|_{4}\le\|f\|_{2}
for any function {f.}

One consequence of the hypercontractivity theorem is the small set expansion theorem of KKL. It concerns fixed {\rho\in\left(0,1\right)} and a sequence of sets {A_{n}\subseteq\{0,1\}^{n}} with {\left|A_{n}\right|=o\left(2^{n}\right).} The small set expansion theorem states that if we choose {\mathbf{x}\sim A_{n}} uniformly and a noisy {\mathbf{y}\sim N_{\rho}\left(\mathbf{x}\right),} then {\mathbf{y}} will reside outside of {A_{n}} almost surely.

The Generalisation to the multicube:

The small set expansion theorem and the hypercontractivity theorem both fail for function on the multicube that are of a very local nature. For instance, let {A} be the set of all {x\in\left\{ 1,\ldots,m\right\} ^{n},} such that {x_{1}} is {m.} Then {A} is of size {m^{n-1},} which is {o\left(m^{n}\right)} if we allow {m} to be a growing function of {n}. However, the {\rho}-noisy process from the set stays within the set with probability {\rho.} For a similar reason the hypercontractivity theorem fails as is for functions on {\left\{ 1,\ldots,m\right\} ^{n}.} However we were able to generalise the hypercontractivity theorem by taking the globalness of {f} into consideration.

Our main hypercontractive inequality is the following

Theorem 1.

\displaystyle \|\mathrm{T}_{\frac{1}{100}}f\|_{4}^{4}\le\sum_{S\subseteq\left[n\right]}\mathbb{E}_{\mathbf{x}\sim\left\{ 1,\ldots,m\right\} ^{m}}\left(\|L_{S}\left[f\right]_{S\rightarrow\mathbf{x}}\|_{2}^{4}\right).

The terms {\|L_{S}\left[f\right]_{S\rightarrow x}\|_{2}} appearing on the right hand side are small whenever {f} has a small dependency on {S} and it turns out that you have the following corrolary of it, which looks a bit more similar to the hypercontractive intequality.

 

Corollary 2.

Let {f\colon\left\{ 1,\ldots,m\right\} ^{n}\rightarrow\mathbb{R}}, and uppose that {\|L_{S}[f]_{S\rightarrow x}\|_{2}\le4^{\left|S\right|}\|f\|_{2}} for all sets {S.}

Then {\mathrm{\|\mathrm{T}_{\frac{1}{1000}}f\|_{4}\le\|f\|_{2}.}}

Finally, one might ask wonder why this globalness notion appears only when we look at large values of {m} and not when {m=2.} I think the corollary is a good explanation for that as {\|f\|_{2}^{2}\ge\left(\frac{1}{2}\right)^{\left|S\right|}\|f_{S\rightarrow x}\|_{2}^{2}} holds trivially for any Boolean function {f\colon\left\{ 0,1\right\} ^{n}\rightarrow\mathbb{R}.}

This entry was posted in Analysis, Combinatorics, Computer Science and Optimization, Guest post, Poetry, Probability and tagged , , , , . Bookmark the permalink.

3 Responses to 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

  1. Tom Gur says:

    Excellent post! Would you consider writing a followup post with a high-level overview of the key technical ideas?

  2. Very nice!

    Erratum: in both Bonami’s Theorem and yours, the noise operator is a contraction from L^2 to L^4 and not the the reverse.

  3. ‪noam Lifshitz‬‏ says:

    Thanks! These kind of stuff always manage to confuse me.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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