The KKL inequality and Rademacher type 2

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 p<\infty$ we get similar inequalities in the opposite direction.

These observations suggest that the inequalities that hold in a particular Banach space might be a useful parameter of that space, telling us to what extent and for which $p$ it is “$L_p$-like”. And that is indeed the case: they play a central role in the local theory of Banach spaces. In particular, a Banach space is said to be of type p if it satisfies the inequality
$$2^{-n}\sum_\epsilon\|\sum_{i=1}^n\epsilon_ix_i\|^p\leq C_p\sum_{i=1}^n\|x_i\|^p$$
for some constant $C_p$, and of cotype p if a similar inequality holds in the reverse direction. The remarks above tell us that if $1\leq p\leq 2$, then $L_p$ is of type $p$ and cotype 2, and if $2\leq p<\infty$, then $L_p$ is of type 2 and cotype $p$. (If we take all $x_i$ to be equal then we see that it is not possible for a space to be of type $p$ if $p>2$ 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}^nj\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.