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 where is very large. However, in some of these cases the fundemental tools of AOBF seem to be false for functions on the multicube 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
Derivatives and Laplacians
There are two fundemental types of operators on Boolean functions The first ones are the discrete derivatives, defined by where denotes the we plug in the value for the th coordinate. The other closely related ones are the laplacians defined by where is obtained from by resampling its th coordinate.
The laplacians and the derivatives are closely related. In fact, when we plug in in the th coordinate, we obtain , and when we plug in in it, we obtain
The 2-norm of the th derivative is called the th influence of as it measures the impact of the th coordinate on the value of . It’s usually denoted by .
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 where is obtained from by resampling its 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 by composing the laplacians corresponding to each coordinate in
We now need to convince ourselves that these laplacians have something to do with the impact of on the outcome of In fact, the following notions are equivalent
- For each we have
- For each we have
in the sense that if (1) holds then (2) holds with and conversely if (2) holds, then (1) holds with
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 .
Noise operator, hypercontractivity, and small set expansion
For the noise operator is given by when is obtained from by independently setting each coordinate to be with probability and resampling it with uniformly out of otherwise. The process which given outputs is called the -noisy process, and we write
The Bonami hypercontractivity theorem, which was then generalised by Gross and Beckner states that the noise operator is a contraction from to i.e.
for any function
One consequence of the hypercontractivity theorem is the small set expansion theorem of KKL. It concerns fixed and a sequence of sets with The small set expansion theorem states that if we choose uniformly and a noisy then will reside outside of 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 be the set of all such that is Then is of size which is if we allow to be a growing function of . However, the -noisy process from the set stays within the set with probability For a similar reason the hypercontractivity theorem fails as is for functions on However we were able to generalise the hypercontractivity theorem by taking the globalness of into consideration.
Our main hypercontractive inequality is the following
The terms appearing on the right hand side are small whenever has a small dependency on and it turns out that you have the following corrolary of it, which looks a bit more similar to the hypercontractive intequality.
Let , and uppose that for all sets
Finally, one might ask wonder why this globalness notion appears only when we look at large values of and not when I think the corollary is a good explanation for that as holds trivially for any Boolean function