The KKL inequality and Rademacher type 2

Abstract

The KKL inequality and Rademacher type 2, Discrete Analysis 2024:2, 14 pp. The parallelepiped identity in a Euclidean space is the identity $$\|x+y\|^2+\|x-y\|^2=2(\|x\|^2+\|y\|^2),$$ which can easily be checked directly, and which generalizes to the statement $$2^{-n}\sum_\epsilon\|\sum_{i=1}^n\epsilon_ix_i\|^2=\sum_{i=1}^n\|x_i\|^2,$$ where the first sum is over all $\epsilon\in\{-1,1\}^n$. That is, the average square norm of a random $\pm 1$ combination of $n$ vectors is the sum of the square norms of the vectors themselves. (This is trivial if the vectors are orthogonal to each other, but becomes interesting for a general set of vectors.) It is natural to wonder what can be said about such averages in more general Banach spaces. One does not expect the identity to hold -- in fact, it can be shown quite easily to characterize Hilbert spaces -- but it turns out that for many interesting Banach spaces one can at least prove an inequality in one direction or the other, up to a constant. For example, if $1\leq p\leq 2$ and $x_1,\dots,x_n$ belong to $L_p$, then we have the inequality $$2^{-n}\sum_\epsilon\|\sum_{i=1}^n\epsilon_ix_i\|^2\geq c_p\sum_{i=1}^n\|x_i\|^2.$$ Note that we certainly do not have the reverse inequality here, since if $x_1,\dots,x_n$ are disjointly supported functions of norm 1, then the left-hand side is equal to $n^{2/p}$ and the right-hand side (ignoring the constant $c_p$) is equal to $n$. This turns out to be the extremal example, from which one can show that we do at least have the inequality $$2^{-n}\sum_\epsilon\|\sum_{i=1}^n\epsilon_ix_i\|^p\leq c_p\sum_{i=1}^n\|x_i\|^p.$$ If $2\leq p2$ or of cotype $p$ if $p<2$.) Generalizations of these notions are also of great importance in metric geometry. In the 1970’s Per Enflo introduced a non-linear version of type 2 (now called Enflo type 2) in which the parallelepiped of all $\pm 1$ sums of $n$ vectors was replaced by an arbitrary mapping of the discrete cube into the Banach space, yielding a definition that makes sense for arbitrary metric spaces. The definition is as follows. Let $R_j:\{-1,1\}^n\to\{-1,1\}^n$ be the map that changes the $j$th coordinate of a point $\epsilon$ and leaves the other coordinates unaltered. If $X$ is a metric space and $f:\{-1,1\}^n\to X$ is any function, define $d_jf(\epsilon)$ to be $d(f(\epsilon),f(R_j\epsilon))$. Then $X$ is said to have _Enflo type p_ if there is a constant $C_p$ such that $$\mathbb E_\epsilon d(f(\epsilon),f(-\epsilon))^p\leq C_p\sum_{j=1}^n\mathbb E_\epsilon d_jf(\epsilon)^p.$$ Note that in the special case that $X$ is a Banach space and $f(\epsilon)=\sum_i\epsilon_ix_i$, this reduces to the definition of $X$ having type $p$. It follows that if a Banach space $X$ has Enflo type $p$, then it has type $p$. However, since there are many other ways to choose the function $f$, the converse is far from obvious. Enflo conjectured that it was true, but this was not proved until 2020, by the first author of this paper, with Ramon van Handel and Alexander Volberg. This paper goes even further, proving that type 2 implies a "strong form” of Enflo type 2 where the inequality holds even while the left-hand side of the inequality is divided by an extra logarithmic factor (see the paper for details) that arises naturally from work of Talagrand and also the famous KKL theorem of Kahn, Kalai and Linial. The resulting inequality, for mappings of the discrete cube into arbitrary type-2 Banach spaces, is a far-reaching generalization of a similar inequality for Boolean mappings which was essentially proved by Kahn, Kalai and Linial as part of the KKL theorem. The paper ends with progress on a conjectured inequality for type 2 spaces that goes even further than the KKL inequality for Banach spaces.