The KKL inequality and Rademacher type 2
- Mathematics, University of California, Irvine
- More about Paata Ivanisvili
- Mathematics, University of California, Irvine
- More about Yonathan Stone
Editorial introduction
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∑ϵ‖n∑i=1ϵixi‖2=n∑i=1‖xi‖2,
where the first sum is over all ϵ∈{−1,1}n. That is, the average square norm of a random ±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≤p≤2 and x1,…,xn belong to Lp, then we have the inequality
2−n∑ϵ‖n∑i=1ϵixi‖2≥cpn∑i=1‖xi‖2.
Note that we certainly do not have the reverse inequality here, since if x1,…,xn are disjointly supported functions of norm 1, then the left-hand side is equal to n2/p and the right-hand side (ignoring the constant cp) 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∑ϵ‖n∑i=1ϵixi‖p≤cpn∑i=1‖xi‖p.
If 2≤p<∞ 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 “Lp-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∑ϵ‖n∑i=1ϵixi‖p≤Cpn∑i=1‖xi‖p
for some constant Cp, and of cotype p if a similar inequality holds in the reverse direction. The remarks above tell us that if 1≤p≤2, then Lp is of type p and cotype 2, and if 2≤p<∞, then Lp is of type 2 and cotype p. (If we take all xi 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 ±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 Rj:{−1,1}n→{−1,1}n be the map that changes the jth coordinate of a point ϵ and leaves the other coordinates unaltered. If X is a metric space and f:{−1,1}n→X is any function, define djf(ϵ) to be d(f(ϵ),f(Rjϵ)). Then X is said to have Enflo type p if there is a constant Cp such that
Eϵd(f(ϵ),f(−ϵ))p≤Cpn∑j=1Eϵdjf(ϵ)p.
Note that in the special case that X is a Banach space and f(ϵ)=∑iϵixi, 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.