.

PYTHAGOREAN POWERS OF HYPERCUBES

ASSAF NAOR AND GIDEON SCHECHTMAN

Abstract. For n ∈ ℕ consider the n-dimensional hypercube as equal to the vector space 𝔽_{2}^{n}, where 𝔽_{2} is the field of size two. Endow 𝔽_{2}^{n} with the Hamming metric, i.e., with the metric induced by the ℓ_{1}^{n} norm when one identifies 𝔽_{2}^{n} with {0, 1}^{n} ⊆ ℝ^{n}. Denote by ℓ_{2}^{n}(𝔽_{2}^{n}) the n-fold Pythagorean product of 𝔽_{2}^{n}, i.e., the space of all x = (x_{1}, …, x_{n}) ∈ ∏_{j=1}^{n} 𝔽_{2}^{n}, equipped with the metric

∀ x, y ∈ ∏_{j=1}^{n} 𝔽_{2}^{n}, d_{ℓ_{2}^{n}(𝔽_{2}^{n})}(x, y) =^{def} \sqrt{∥x_{1} − y_{1}∥_{1}^{2} + … + ∥x_{n} − y_{n}∥_{1}^{2}}.

It is shown here that the bi-Lipschitz distortion of any embedding of ℓ_{2}^{n}(𝔽_{2}^{n}) into L_{1} is at least a constant multiple of \sqrt{n}. This is achieved through the following new bi-Lipschitz invariant, which is a metric version of (a slight variant of) a linear inequality of Kwapień and Schütt (1989). Letting {e_{jk}}_{j,k∈{1,...,n}} denote the standard basis of the space of all n by n matrices M_{n}(𝔽_{2}), say that a metric space (X, d_{X}) is a KS space if there exists C = C(X) > 0 such that for every n ∈ 2ℕ, every mapping f : M_{n}(𝔽_{2}) → X satisfies

\frac{1}{n} ∑_{j=1}^{n} 𝔼 [d_{X}(f(x + ∑_{k=1}^{n} e_{jk}), f(x))] ⩽ C𝔼 [d_{X}(f(x + ∑_{j=1}^{n} e_{jk_{j}} ), f(x))] ,

where the expectations above are with respect to x ∈ M_{n}(𝔽_{2}) and k = (k_{1}, …, k_{n}) ∈ {1, …, n}^{n} chosen uniformly at random. It is shown here that L_{1} is a KS space (with C = 2e^{2}/(e^{2} − 1), which is best possible), implying the above nonembeddability statement. Links to the Ribe program are discussed, as well as related open problems.

1. Introduction

For a metric space (X, d_{X}) and n ∈ ℕ, the n-fold Pythagorean power of (X, d_{X}), denoted ℓ_{2}^{n}(X), is the space X^{n}, equipped with the metric given by setting for every (x_{1}, …, x_{n}), (y_{1}, …, y_{n}) ∈ X,

d_{ℓ_{2}^{n}(X)}((x_{1}, …, x_{n}), (y_{1}, …, y_{n})) =^{def} \sqrt{d_{X}(x_{1}, y_{1})^{2} + … + d_{X}(x_{n}, y_{n})^{2}}.  (1)

For p ∈ [1, ∞], one analogously defines the ℓ_{p} powers of (X, d_{X}) by replacing in the right hand side of (1) the squares by p’th powers and the square root by the p’th root (with the obvious modification for p = ∞). When (X, ∥ · ∥_{X}) is a Banach space and p ∈ [1, ∞], one also commonly considers the Banach space ℓ_{p}(X) consisting of all the infinite sequences x = (x_{1}, x_{2}, …) ∈ X^{ℵ_{0}} such that ∥x∥_{ℓ_{p}(X)}^{p} = ∑_{j=1}^{∞} ∥x_{j}∥_{X}^{p} < ∞. One could give a similar definition of infinite ℓ_{p} powers for pointed metric spaces, but in the present article it will suffice to only consider n-fold powers of metric spaces for finite n ∈ ℕ.

Throughout the ensuing discussion we shall use standard notation and terminology from Banach space theory, as in [17]. In particular, for p ∈ [1, ∞] and n ∈ ℕ, we use the notations ℓ_{p} = ℓ_{p}(ℝ) and ℓ_{p}^{n} = ℓ_{p}^{n}(ℝ), and the space L_{p} refers to the Lebesgue function space L_{p}(0, 1). We shall also use standard notation and terminology from the theory of metric embeddings, as in [18, 25]. In particular, a metric space (X, d_{X}) is said to admit a bi-Lipschitz embedding into a metric space (Y, d_{Y}) if there exists s ∈ (0, ∞), D ∈ [1, ∞) and a mapping f : X → Y such that

∀ x, y ∈ X,  sd_{X}(x, y) ⩽ d_{Y} (f(x), f(y)) ⩽ Dsd_{X}(x, y)  (2)

A. N. was supported by the NSF, the BSF, the Packard Foundation and the Simons Foundation. G. S. was supported by the ISF and the BSF.

When this happens we say that (X, d_{X}) embeds into (Y, d_{Y}) with distortion at most D. We denote by c_{(Y,d_{Y} )}(X, d_{X}) (or simply c_{Y} (X), c_{Y} (X, d_{X}) if the metrics are clear from the context) the infimum over those D ∈ [1, ∞] for which (X, d_{X}) embeds into (Y, d_{Y}) with distortion at most D. When Y = L_{p} we use the shorter notation c_{L_{p}}(X, d_{X}) = c_{p}(X, d_{X}).

A folklore theorem asserts that ℓ_{2}(ℓ_{1}) is not isomorphic to a subspace of L_{1}. While this statement follows from a (nontrivial) gliding hump argument, we could not locate a reference to where it was first discovered; different proofs of certain stronger statements can be found in [14, Theorem 4.2],

[27] and [28, Section 3]. More generally, ℓ_{q}(ℓ_{p}) is not isomorphic to a subspace of L_{1} whenever q > p ⩾ 1; the present work yields new information on this stronger statement as well, but for the sake of simplicity we shall focus for the time being only on the case of Pythagorean products.

Finite dimensional versions of the above results were discovered by Kwapień and Schütt, who proved in [16] that for every n ∈ ℕ, if T : ℓ_{2}^{n}(ℓ_{1}^{n}) → L_{1} is an injective linear mapping then necessarily ∥T ∥ · ∥T^{−1}∥ ≳ \sqrt{n}. Here, and in what follows, we use the convention that for a, b ∈ [0, ∞) the notation a ≳ b (respectively a ≲ b) stands for a ⩾ cb (respectively a ⩽ cb) for some universal constant c ∈ (0, ∞). Below, the notation a ≍ b stands for (a ≲ b) ∧ (b ≲ a). By Cauchy–Schwarz, the identity mapping Id : ℓ_{2}^{n}(ℓ_{1}^{n}) → ℓ_{1}^{n}(ℓ_{1}^{n}) satisfies ∥Id∥ · ∥Id^{−1}∥ = \sqrt{n}. So, the above lower bound of Kwapień and Schütt is asymptotically sharp as n → ∞, up to the implicit universal constant.

By general principles, the above stated result of Kwapień and Schütt formally implies that

lim_{n→∞} c_{1}(ℓ_{2}^{n}(𝔽_{2}^{n})) = ∞,  (3)

where 𝔽_{2}^{n} is the n-dimensional discrete hypercube, endowed with the metric inherited from ℓ_{1}^{n} via the identification 𝔽_{2}^{n} = {0, 1}^{n} ⊆ ℝ^{n}. The deduction of (3) is as follows. Suppose for contradiction that sup_{n∈ℕ} c_{1}(ℓ_{2}^{n}(𝔽_{2}^{n})) < ∞. Since for every ε > 0 every finite subset of ℓ_{1} embeds with distortion 1 + ε into 𝔽_{2}^{m} for some m ∈ ℕ (this can be seen e.g. by combining Proposition 4.2.2 and Proposition 4.2.4 of [7]), it follows from our contrapositive assumption that there exists K ∈ [1, ∞) such that for every finite subset X ⊆ ℓ_{1} and every n ∈ ℕ we have c_{1}(ℓ_{2}^{n}(X)) ⩽ K. By a standard ultrapower argument (as in [10]) this implies that sup_{n∈ℕ} c_{1}(ℓ_{2}^{n}(ℓ_{1}^{n})) ⩽ K. Next, by using a w^{∗}-Gâteaux differentiation argument combined with the fact that L_{1}^{∗∗} is an L_{1}(μ) space (see [11] or [4, Chapter 7])) it follows that there exists a linear operator T : ℓ_{2}^{n}(ℓ_{1}^{n}) → L_{1} with ∥T ∥ · ∥T^{−1}∥ ≲ 2K, contradicting the lower bound of Kwapień and Schütt. This proof of (3) does not yield information on the rate at which c_{1}(ℓ_{2}^{n}(𝔽_{2}^{n})) tends to ∞, a problem that we resolve here. Theorem 1.1. We have c_{1}(ℓ_{2}^{n}(𝔽_{2}^{n})) ≍ \sqrt{n}.

Note that if we write Y =^{def} ℓ_{2}^{n}(𝔽_{2}^{n}) then |Y | = 2^{n^{2}}, and therefore by Theorem 1.1 we have

c_{1}(Y) ≍ \sqrt[4]{log |Y |}.  (4)

In light of (4), the following interesting open question asks whether or not ℓ_{2}^{n}(𝔽_{2}^{n}) is the finite subset of ℓ_{2}(ℓ_{1}) that is asymptotically the furthest from a subset of L_{1} in terms of its cardinality.

Question 1.2. Suppose that S ⊆ ℓ_{2}(ℓ_{1}) is finite. Is it true that c_{1}(S) ≲ \sqrt[4]{log |S|}?

The following proposition (proved in Section 4 below) is a simple consequence of [2]. It shows that the answer to Question 1.2 is positive (up to lower order factors) for finite subsets S ⊆ ℓ_{2}(ℓ_{1}) that are product sets, i.e., those sets of the form S = X_{1} × … × X_{n} ⊆ ℓ_{2}^{n}(ℓ_{1}) for some n ∈ ℕ and finite subsets X_{1}, …, X_{n} ⊆ ℓ_{1}. This assertion is of course far from a full resolution of Question 1.2. We conjecture that the answer to Question 1.2 is positive, and it would be worthwhile to investigate whether or not variants of the methods used in the proof of the main result of [2] are relevant here. Proposition 1.3. Fix n ∈ ℕ and suppose that X_{1}, …, X_{n} ⊆ ℓ_{1} are finite subsets of ℓ_{1}. Denote S = X_{1} × … × X_{n} ⊆ ℓ_{2}^{n}(ℓ_{1}). Then

c_{1}(S) ≲ \sqrt[4]{log |S|} · \sqrt{log log |S|} = (log |S|)^{\frac{1}{4} +o(1)} .

1.1. Metric Kwapień–Schütt inequalities. In [16] (see also [15]) Kwapień and Schütt (implicitly) proved the following inequality, which holds for every n ∈ ℕ and every {z_{jk}}_{j,k∈{1,...,n}} ⊆ L_{1}.

\frac{1}{n} ∑_{j=1}^{n} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{k=1}^{n} ε_{k}z_{jk}∥_{1} ≲ \frac{1}{n!} ∑_{π∈S_{n}} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} ε_{j}z_{jπ(j)}∥_{1},  (5)

where S_{n} denotes as usual the group of all permutations of {1, …, n}.

The validity of (5) immediately implies the previously mentioned lower bound on the distortion of any linear embedding T : ℓ_{2}^{n}(ℓ_{1}^{n}) → L_{1}. To see this, identify from now on ℓ_{2}^{n}(ℓ_{1}^{n}) with M_{n}(ℝ) by considering for every x = (x_{1}, …, x_{n}) ∈ ℓ_{2}^{n}(ℓ_{1}^{n}) the matrix whose j’th row is x_{j} ∈ ℝ^{n}. With this convention, apply (5) to z_{jk} = T (e_{jk}), where e_{jk} is the n by n matrix whose (j, k) entry equals 1 and the rest of its entries vanish. Then for every ε ∈ {−1, 1}^{n} and j ∈ {1, …, n} we have

∥ ∑_{k=1}^{n} ε_{k}z_{jk}∥_{1} ⩾ \frac{∥ ∑_{k=1}^{n} ε_{k}e_{jk}∥_{ℓ_{2}^{n}(ℓ_{1}^{n})}}{∥T^{−1}∥} = \frac{n}{∥T^{−1}∥},  (6)

and for every π ∈ S_{n} and ε ∈ {−1, 1}^{n} we have

∥ ∑_{j=1}^{n} ε_{j}z_{jπ(j)}∥_{1} ⩽ ∥T ∥∥ ∑_{j=1}^{n} ε_{j}e_{jπ(j)}∥_{ℓ_{2}^{n}(ℓ_{1}^{n})} = ∥T ∥\sqrt{n}.  (7)

The only way for (6) and (7) to be compatible with (5) is if ∥T ∥ · ∥T^{−1}∥ ≳ \sqrt{n}.

In light of the above argument, it is natural to ask which Banach spaces satisfy (5), i.e., to obtain an understanding of those Banach spaces (Z, ∥ · ∥_{Z}) for which there exists K = K(Z) ∈ (0, ∞) such that for every n ∈ ℕ and every {z_{jk}}_{j,k∈{1,...,n}} ⊆ Z we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{k=1}^{n} ε_{k}z_{jk}∥_{Z} ⩽ \frac{K}{n!} ∑_{π∈S_{n}} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} ε_{j}z_{jπ(j)}∥_{Z}.  (8)

This question requires further investigation and obtaining a satisfactory characterization seems to be challenging. In particular, it seems to be unknown whether or not the Schatten trace class S_{1} satisfies (8). Regardless, it is clear that the requirement (8) is a local linear property, and therefore by Ribe’s rigidity theorem [29] it is preserved under uniform homeomorphisms of Banach spaces. In accordance with the Ribe program (see [3, 24]) one should ask for a bi-Lipschitz invariant of metric spaces that, when restricted to the class of Banach spaces, is equivalent to (8).

Following the methodology that was introduced by Enflo [8] (see also [9, 5]), a first attempt to obtain a bi-Lipschitz invariant that is (hopefully) equivalent to (8) is as follows. Consider those metric spaces (X, d_{X}) for which there exists K = K(X) ∈ (0, ∞) such that for every n ∈ ℕ and every f : M_{n}(𝔽_{2}) → X we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} d_{X}(f(x + ∑_{k=1}^{n} e_{jk}), f(x)) ⩽ \frac{K}{n!} ∑_{π∈S_{n}} ∑_{x∈M_{n}(𝔽_{2})} d_{X}(f(x + ∑_{j=1}^{n} e_{jπ(j)}), f(x)). (9)

If X is in addition a Banach space and {z_{jk}}_{j,k∈{1,...,n}} ⊆ X then for f(x) = ∑_{j=1}^{n} ∑_{k=1}^{n}(−1)^{x_{jk}}z_{jk} the inequality (9) becomes (8). However, for every integer n ⩾ 3 no metric space that contains at least two points can satisfy (9) with K < n/2, as explained in Remark 2.4 below. Thus, obtaining a metric characterization of the linear property (8) remains open.

We shall overcome this difficulty by first modifying the linear definition (8) so that it still implies the same nonembeddability result for ℓ_{2}^{n}(ℓ_{1}^{n}), and at the same time we can prove that the reasoning that led to the metric inequality (9) now leads to an analogous inequality which does hold true for nontrivial metric spaces (specifically, we shall prove that it holds true for L_{1}).

Definition 1.4 (Linear KS space). Say that a Banach space (Z, ∥ · ∥_{Z}) is a linear KS space if there exists C = C(X) ∈ (0, ∞) such that for every n ∈ ℕ and every {z_{jk}}_{j,k∈{1,...,n}} ⊆ Z we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{k=1}^{n} ε_{k}z_{jk}∥_{Z} ⩽ \frac{C}{n^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{ε∈\{−1,1\}^{n}} ∥ ∑_{j=1}^{n} ε_{j}z_{jk_{j}} ∥_{Z}.  (10)

The difference between (10) and (8) is that we replace the averaging over all permutations π ∈ S_{n} by averaging over all mappings π : {1, …, n} → {1, …, n}. We shall see below that L_{1} is a linear KS space. The same reasoning that leads to (9) now leads us to consider the following new bi-Lipschitz invariant for metric spaces.

Definition 1.5 (KS metric space). Say that a metric space (X, d_{X}) is a KS space if there exists C = C(X) ∈ (0, ∞) such that for every n ∈ 2ℕ and every f : M_{n}(𝔽_{2}) → X we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} d_{X}(f(x+∑_{k=1}^{n} e_{jk}), f(x)) ⩽ \frac{C}{n^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} d_{X}(f(x+∑_{j=1}^{n} e_{jk_{j}}), f(x)). (11)

Remark 1.6. The reason why in Definition 1.5 we require (11) to hold true only when n ∈ ℕ is even is that no non-singleton metric space (X, d_{X}) satisfies (11) when n ⩾ 3 is an odd integer. Indeed, suppose that a, b ∈ X are distinct and that n ⩾ 3 is an odd integer. For x ∈ M_{n}(𝔽_{2}) write σ(x) = ∑_{j=1}^{n−1} ∑_{k=1}^{n} x_{jk} ∈ 𝔽_{2}. Define f : M_{n}(𝔽_{2}) → X by setting f(x) = a if σ(x) = 0 and f(x) = b if σ(x) = 1. For every j ∈ {1, …, n−1} and x ∈ M_{n}(𝔽_{2}) we have σ(x+∑_{k=1}^{n} e_{jk}) = σ(x)+n ≠ σ(x), since n is odd. Consequently the left hand side of (11) is nonzero (since a and b are distinct). But, for every x ∈ M_{n}(𝔽_{2}) and k ∈ {1, …, n}^{n} we have σ(x+∑_{j=1}^{n} e_{jk_{j}}) = σ(x)+n−1 = σ(x), since n is odd. Consequently the right hand side of (11) vanishes. This parity issue is of minor significance: in Remark 2.3 below we describe an inequality that is slightly more complicated than (11) but makes sense for every n ∈ ℕ and in any metric space, and we show that it holds true for L_{1}- valued functions. This variant has the same nonembeddability consequences as (11), albeit yielding distortion lower bounds that are weaker by a constant factor.

The following theorem is the main result of the present article. We shall soon see, in Section 1.2 below, how it quickly implies Theorem 1.1 (and more).

Theorem 1.7. L_{1} is a KS space. Namely, for all n ∈ 2ℕ and every f : M_{n}(𝔽_{2}) → L_{1} we have

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{k=1}^{n} e_{jk})−f(x)∥_{1} ⩽ \frac{2n}{n^{n} − (n − 2)^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{j=1}^{n} e_{jk_{j}})−f(x)∥_{1}.

For every fixed n ∈ 2ℕ, the factor 2n/(n^{n}−(n−2)^{n}) above cannot be improved. So, L_{1} satisfies (11) for every n ∈ 2ℕ with

C = sup_{n∈2ℕ} \frac{2}{1 − (1 − \frac{2}{n})^{n}} = \frac{2e^{2}}{e^{2} − 1},

and this value of C cannot be improved.

Note that if (Z, ∥·∥_{Z}) is a Banach space and {z_{jk}}_{j,k∈{1,...,n}} ⊆ Z then by considering the mapping f : M_{n}(𝔽_{2}) → Z given by f(x) = ∑_{j=1}^{n} ∑_{k=1}^{n}(−1)^{x_{jk}}z_{jk} we see that if Z is a KS space as a metric space then it is also a linear KS space (with the same constant C). We do not know whether or not the converse holds true, i.e., we ask the following interesting open question: if a Banach space (Z, ∥ · ∥_{Z}) is a linear KS space then is it also a KS space as a metric space? Understanding which Banach spaces are linear KS spaces is a wide-open research direction. In particular, we ask whether the Schatten trace class S_{1} is a KS space as a metric space, or even whether it is a linear KS space.

There are inherent conceptual difficulties that indicate that our proof of Theorem 1.7 cannot be extended to the case of S_{1} without a substantial new idea; see Remark 3.3 below.

Our proof of Theorem 1.7 consists of simple Fourier analysis combined with a nonlinear transformation; see Section 2 below. The simplicity of this proof indicates one of the advantages of generalizing linear inequalities such as (10) to their stronger nonlinear counterparts, since this brings genuinely nonlinear tools into play. In particular, we thus obtain a very simple proof of the linear inequality (10) through an argument which would have probably not been found without the need to generalize (10) to a metric inequality as part of the Ribe program.

1.2. Embeddings of ℓ_{q}(𝔽_{2}^{n}, ∥ · ∥_{p}) into L_{1}. Suppose that q > p ⩾ 1. By arguing as in (6) and (7) one deduces from the Kwapień–Schütt inequality (5) that for every n ∈ ℕ, every injective linear mapping T : ℓ_{q}^{n}(ℓ_{p}^{n}) → L_{1} must satisfy

∥T ∥ · ∥T^{−1}∥ ≳ n^{\frac{1}{p} − \frac{1}{q}} .  (12)

Note that this conclusion was stated by Kwapień and Schütt in [16, Corollary 3.4] under the additional assumption that q ⩽ 2, but this restriction is not necessary. By a differentiation argument (see [11] or [4, Chapter 7]), it follows from (12) that

c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n})) ≳ n^{\frac{1}{p} − \frac{1}{q}} .  (13)

We previously deduced from the case q = 2 and p = 1 of (13) that lim_{n→∞} c_{1}(ℓ_{2}^{n}(𝔽_{2}^{n})) = ∞. This was done in the paragraph that followed (3), relying on the fact that any finite subset of ℓ_{1} admits an embedding with O(1) distortion into 𝔽_{2}^{m} for some m ∈ ℕ. The analogous assertion is not true for p > 1, and therefore despite the validity of (13) it was previously unknown whether or not sup_{n∈ℕ} c_{1}(ℓ_{q}(𝔽_{2}^{n}, ∥ · ∥_{p})) = ∞. Our metric KS inequality of Theorem 1.7 answers this question.

Theorem 1.8. Suppose that 1 ⩽ p < q and n ∈ ℕ then

c_{1} (ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) ≍ n^{\frac{1}{p} − \frac{1}{q}} .  (14)

It is worthwhile to note here that while Theorem 1.8 yields a sharp asymptotic evaluation of c_{1} (ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})), the corresponding bound (13) in the continuous setting is not always sharp. Specifically, in Section 4 we explain that

c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n})) ≍ \{ \begin{matrix}n^{\frac{1}{p} − \frac{1}{q}} & if 1 ⩽ p < q and p ⩽ 2, \\ n^{1− \frac{1}{p} − \frac{1}{q}} & if 2 ⩽ p < q. \end{matrix}  (15)

From (14) and (15) we see that if 1 ⩽ p < q and p ⩽ 2 then c_{1} (ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) ≍ c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n})), while if 2 < p < q then since 1/p − 1/q < 1 − 1/p − 1/q we have c_{1} (ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) = o (c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n}))).

The upper bound on c_{1}(ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) that appears in (14) will be proven in Section 4. We shall now show how the lower bound on c_{1}(ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) that appears in (14) quickly follows from Theorem 1.7. This will also establish Theorem 1.1 as a special case. So, suppose that D ∈ [1, ∞) and f : M_{n}(𝔽_{2}) → L_{1} satisfies ∥x − y∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} ⩽ ∥f(x) − f(y)∥_{1} ⩽ D∥x − y∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} for every x, y ∈ M_{n}(𝔽_{2}). Our goal is to bound D from below. Since ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p}) contains an isometric copy of ℓ_{q}^{n−1} (𝔽_{2}^{n−1}, ∥ · ∥_{p}), we may assume that n is even. By Theorem 1.7 applied to f we have

\frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x + ∑_{k=1}^{n} e_{jk}) − f(x)∥_{1} ≲ \frac{1}{n^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x + ∑_{j=1}^{n} e_{jk_{j}}) − f(x)∥_{1}. (16)

But,

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x + ∑_{k=1}^{n} e_{jk}) − f(x)∥_{1} ⩾ 2^{n^{2}} ∑_{j=1}^{n} ∥ ∑_{k=1}^{n} e_{jk}∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} = 2^{n^{2}}n^{1+ \frac{1}{p}} ,  (17)

and

∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{j=1}^{n} e_{jk_{j}})−f(x)∥_{1} ⩽ D2^{n^{2}} ∑_{k∈\{1,...,n\}^{n}} ∥ ∑_{j=1}^{n} e_{jk_{j}} ∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} = D2^{n^{2}}n^{n+ \frac{1}{q}} . (18)

For (16) to be compatible with (17) and (18) we must have D ≳ n^{\frac{1}{p} − \frac{1}{q}}. □

Remark 1.9. We only discussed L_{1} embeddings of ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p}), but it is natural to also ask about embeddings of ℓ_{q}^{m} (𝔽_{2}^{n}, ∥ · ∥_{p}). However, it turns out that the case m = n is the heart of the matter, i.e., the L_{1} distortion of ℓ_{q}^{m} (𝔽_{2}^{n}, ∥ · ∥_{p}) is up to a constant factor the same as the L_{1} distortion of ℓ_{q}^{k} (𝔽_{2}^{k}, ∥ · ∥_{p}) with k = min{m, n}; see Remark 4.1 below.

2. Proof of Theorem 1.7

The stated sharpness of Theorem 1.7 is simple: consider the function φ : M_{n}(𝔽_{2}) → ℝ given by φ(x) = (−1)^{x_{11}+...+x_{nn}}. For this choice of φ we have φ(x + ∑_{k=1}^{n} e_{jk}) = −φ(x) ∈ {−1, 1} for every x ∈ M_{n}(𝔽_{2}) and j ∈ {1, …, n}. Consequently,

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} |φ(x + ∑_{k=1}^{n} e_{jk}) − φ(x)| = n2^{n^{2}+1}.  (19)

Also, for every x ∈ M_{n}(𝔽_{2}) and k ∈ {1, …, n}^{n} we have φ(x + ∑_{j=1}^{n} e_{jk_{j}}) = (−1)^{ℓ(k)}φ(x), where ℓ(k) = |{j ∈ {1, …, n} : k_{j} = j}| = ∑_{j=1}^{n} 1_{{k_{j}=j}}. Consequently,

∑_{k∈{1,...,n}^{n}} ∑_{x∈M_{n}(𝔽_{2})} |φ(x + ∑_{j=1}^{n} e_{jk_{j}}) − φ(x)| = 2^{n^{2}} ∑_{k∈{1,...,n}^{n}} (1 − (−1)^{∑_{j=1}^{n} 1_{{k_{j} =j}}})

= 2^{n^{2}}n^{n} − 2^{n^{2}} ∏_{j=1}^{n} ∑_{k=1}^{n}(−1)^{1_{{k=j}}} = 2^{n^{2}} (n^{n} − (n − 2)^{n}) . (20)

The identities (19) and (20) demonstrate that for every fixed n ∈ ℕ the factor 2n/(n^{n} − (n − 2)^{n}) in Theorem 1.7 cannot be replaced by any strictly smaller number.

Passing now to the proof of Theorem 1.7, we will actually prove the following statement, the case p = 1 of which is Theorem 1.7 itself.

Theorem 2.1. Suppose that p ∈ (0, 2] and n ∈ 2ℕ. Then for every f : M_{n}(𝔽_{2}) → L_{p} we have

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{k=1}^{n} e_{jk})−f(x)∥_{p}^{p} ⩽ \frac{2n}{n^{n} − (n − 2)^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{j=1}^{n} e_{jk_{j}})−f(x)∥_{p}^{p}.

Proof. By a classical theorem of Schoenberg [30], the metric space (L_{p}, ∥x − y∥_{p}^{p/2}) admits an isometric embedding into L_{2}. Since the desired inequality is purely metric, i.e., it involves only distances between various values of f, it suffices to prove it for p = 2 and then apply it to the composition of f with the Schoenberg isometry so as to deduce the desired inequality for general p ∈ (0, 2]. In order to prove the case p = 2, it suffices to prove the desired inequality when f is real-valued (deducing the case of L_{2}-valued f by integrating the resulting point-wise inequality).

Suppose then that f : M_{n}(𝔽_{2}) → ℝ. We shall use below standard Fourier-analytic arguments on M_{n}(𝔽_{2}), considered as a vector space (of dimension n^{2}) over 𝔽_{2}. Specifically, one can write

f(x) = ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n})(−1)^{∑_{j=1}^{n} ∑_{k∈A_{j}} x_{jk}},

where for every A_{1}, …, A_{n} ⊆ {1, …, n},

f̂(A_{1}, …, A_{n}) =^{def} \frac{1}{2^{n^{2}}} ∑_{x∈M_{n}(𝔽_{2})}(−1)^{∑_{j=1}^{n} ∑_{k∈A_{j}} x_{jk}}f(x).

Then, for every x ∈ M_{n}(𝔽_{2}) and j ∈ {1, …, n} we have

f(x + ∑_{k=1}^{n} e_{jk}) − f(x) = ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n}) ((−1)^{|A_{j}|} − 1) (−1)^{∑_{s=1}^{n} ∑_{k∈As} x_{sk}}

= −2 ∑_{\begin{matrix}A_{1},...,A_{n}⊆\{1,...,n\} \\ |A_{j}|≡1 mod 2 \end{matrix}} f̂(A_{1}, …, A_{n})(−1)^{∑_{s=1}^{n} ∑_{k∈As} x_{sk}}.

Hence, by the orthogonality of the functions {x ↦ (−1)^{∑_{s=1}^{n} ∑_{k∈As} x_{sk}}}_{A_{1},...,A_{n}⊆{1,...,n}} on M_{n}(𝔽_{2}),

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})}(f(x + ∑_{k=1}^{n} e_{jk}) − f(x))^{2}
= 2^{n^{2}+2} ∑_{A_{1},...,A_{n}⊆{1,...,n}} |{j ∈ {1, …, n} : |A_{j}| ≡ 1 mod 2}| f̂(A_{1}, …, A_{n})^{2}. (21)

At the same time, for every x ∈ M_{n}(𝔽_{2}) and k ∈ {1, …, n}^{n} we have

f(x + ∑_{j=1}^{n} e_{jk_{j}}) − f(x) = ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n}) ((−1)^{∑_{j=1}^{n} 1_{A_{j}} (k_{j})} − 1) (−1)^{∑_{j=1}^{n} ∑_{k∈A_{j}} x_{jk}}.

Using orthogonality again, we therefore have

∑_{k∈{1,...,n}^{n}} ∑_{x∈M_{n}(𝔽_{2})} (f(x + ∑_{j=1}^{n} e_{jk_{j}}) − f(x))^{2}

= 2^{n^{2}} ∑_{k∈{1,...,n}^{n}} ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n})^{2} ((−1)^{∑_{j=1}^{n} 1_{A_{j}} (k_{j})} − 1)^{2}

= 2^{n^{2}+1} ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n})^{2} ∑_{k∈{1,...,n}^{n}} (1 − (−1)^{∑_{j=1}^{n} 1_{A_{j}} (k_{j})}) . (22)

Fixing A_{1}, …, A_{n} ⊆ {1, …, n}, denote S =^{def} {j ∈ {1, …, n} : |A_{j}| ≡ 1 mod 2}. Since n is even,

if j ∈ S then |A_{j}| ∈ {1, …, n − 1}, and consequently |2|A_{j}| − n| ⩽ n − 2. Hence,

∑_{k∈{1,...,n}^{n}} (1 − (−1)^{∑_{j=1}^{n} 1_{A_{j}} (k_{j})}) = n^{n} − ∏_{j=1}^{n} ∑_{k=1}^{n}(−1)^{1_{A_{j}} (k)}

= n^{n} − ∏_{j=1}^{n} (n − 2|A_{j}|) ⩾ n^{n} − ∏_{j=1}^{n} |2|A_{j}| − n| ⩾ n^{n} − n^{n−|S|}(n − 2)^{|S|}. (23)

Since the mapping |S| ↦ (n^{n} − n^{n−|S|}(n − 2)^{|S|}) /|S| is decreasing in |S|, it follows from (23) that

∑_{k∈\{1,...,n\}^{n}} (1 − (−1)^{∑_{j=1}^{n} 1_{A_{j}} (k_{j})}) ⩾ \frac{n^{n} − (n − 2)^{n}}{n} |\{j ∈ \{1, …, n\} : |A_{j}| ≡ 1 mod 2\}| . (24)

The desired inequality now follows by substituting (24) into (22) and recalling (21). □

Remark 2.2. By the cut-cone decomposition of L_{1} metrics (see e.g. [7, Chapter 4]), the inequality of Theorem (1.7) is equivalent to the following (also sharp) isoperimetric-type inequality. For every and n ∈ 2ℕ and S ⊆ M_{n}(𝔽_{2}) we have

∑_{j=1}^{n} |\{x ∈ S : x + ∑_{k=1}^{n} e_{jk} ∉ S\}| ⩽ \frac{2n}{n^{n} − (n − 2)^{n}} ∑_{k∈\{1,...,n\}^{n}} |\{x ∈ S : x + ∑_{j=1}^{n} e_{jk_{j}} ∉ S\}|. (25)

Due to the simplicity of our proof of Theorem 1.7, we did not attempt to obtain a direct combinatorial proof of (25), though we believe that this should be doable (and potentially instructive). We also did not attempt to characterize the equality cases in (25).

Remark 2.3. In Remark 1.6 we have seen that (11) can hold true only if n ∈ ℕ is even. However, this parity issue can be remedied through the following (sharp) inequality, which holds true for every n ∈ ℕ, every p ∈ (0, 2] and every f : M_{n}(𝔽_{2}) → L_{p}.

\frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x + ∑_{k=1}^{n} e_{jk}) − f(x)∥_{p}^{p}

⩽ \frac{2}{1 − (1 − \frac{1}{n})^{n}} · \frac{1}{(2n)^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∑_{y∈𝔽_{2}^{n}} ∥f(x + ∑_{j=1}^{n} y_{j}e_{jk_{j}}) − f(x)∥_{p}^{p}

⩽ \frac{2e}{e − 1} · \frac{1}{(2n)^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∑_{y∈𝔽_{2}^{n}} ∥f(x + ∑_{j=1}^{n} y_{j}e_{jk_{j}}) − f(x)∥_{p}^{p}.  (26)

The distortion lower bounds that we obtained as a consequence of Theorem 1.7 also follow mutatis mutandis from (26).

To prove (26), note that, exactly as in the beginning of the proof of Theorem 2.1, it suffices to prove (26) when p = 2 and f : M_{n}(𝔽_{2}) → ℝ. Now, argue as in (22) to obtain the following identity.

∑_{k∈{1,...,n}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∑_{y∈𝔽_{2}^{n}} (f(x + ∑_{j=1}^{n} y_{j}e_{jk_{j}}) − f(x))^{2}

= 2^{n^{2}+1} ∑_{A_{1},...,A_{n}⊆{1,...,n}} f̂(A_{1}, …, A_{n})^{2} ∑_{k∈{1,...,n}^{n}} ∑_{y∈𝔽_{2}^{n}} (1 − (−1)^{∑_{j=1}^{n} y_{j}1_{A_{j}} (k_{j})}) . (27)

For every A_{1}, …, A_{n} ⊆ {1, …, n} and k ∈ {1, …, n}^{n} we have

∑_{y∈𝔽_{2}^{n}} (1 − (−1)^{∑_{j=1}^{n} y_{j}1_{A_{j}} (k_{j})}) = \{ \begin{matrix}2^{n} & if k_{j} ∈ A_{j} for some j ∈ \{1, …, n\}, \\ 0 & otherwise. \end{matrix}

Hence, denoting T =^{def} {j ∈ {1, …, n} : A_{j} ≠ ∅} ⊇ {j ∈ {1, …, n} : |A_{j}| ≡ 1 mod 2} =^{def} S,

∑_{k∈{1,...,n}^{n}} ∑_{y∈𝔽_{2}^{n}} (1 − (−1)^{∑_{j=1}^{n} y_{j}1_{A_{j}} (k_{j})}) = 2^{n} ∑_{k∈{1,...,n}^{n}} (1 − 1_{{∀ j∈{1,...,n}, k_{j} ∉A_{j}}})

= 2^{n}(n^{n} − ∏_{j=1}^{n}(n − |A_{j}|)^{n}) ⩾ 2^{n}(n^{n} − n^{n−|T |}(n − 1)^{|T |}) ⩾ 2^{n} (n^{n} − (n − 1)^{n}) \frac{|T |}{n}. (28)

Consequently, by (27) and (28), combined with the fact that |T | ⩾ |S|, we have

∑_{k∈{1,...,n}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∑_{y∈𝔽_{2}^{n}} (f(x + ∑_{j=1}^{n} y_{j}e_{jk_{j}}) − f(x))^{2}

⩾ \frac{2^{n^{2}+n+1} (n^{n} − (n − 1)^{n})}{n} ∑_{A_{1},...,A_{n}⊆\{1,...,n\}} |\{j ∈ \{1, …, n\} : |A_{j}| ≡ 1 mod 2\}| f̂(A_{1}, …, A_{n})^{2}

=^{(21)} \frac{2^{n} (n^{n} − (n − 1)^{n})}{2n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} (f(x + ∑_{k=1}^{n} e_{jk}) − f(x))^{2}.

This completes the proof of (26).

Remark 2.4. As stated in the Introduction, the “vanilla” metric Kwapień–Schütt inequality (9) cannot hold true in any non-singleton metric space (X, d_{X}). To see this, note first that we have already seen in Remark 1.6 that if n ∈ ℕ is odd then (9) fails to hold true for any K > 0. So, suppose that n ⩾ 4 is an even integer. It suffice to deal with X = {−1, 1} ⊆ ℝ. Define ψ : M_{n}(𝔽_{2}) → {−1, 1} by ψ(x) = (−1)^{x_{11}+∑_{j=2}^{n} ∑_{k=4}^{n} x_{jk}}. For every x ∈ M_{n}(𝔽_{2}) we have ψ(x+∑_{k=1}^{n} e_{1k}) = −ψ(x), and for j ∈ {2, …, n} we have ψ(x + ∑_{k=1}^{n} e_{jk}) = (−1)^{n−3}ψ(x) = −ψ(x), since n is even. Consequently,

∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} |ψ(x + ∑_{k=1}^{n} e_{jk}) − ψ(x)| = n2^{n^{2}+1}.  (29)

At the same time, for every x ∈ M_{n}(𝔽_{2}) and π ∈ S_{n} we have

ψ(x + ∑_{j=1}^{n} e_{jπ(j)}) = (−1)^{1_{{π(1)=1}}+∑_{j=2}^{n} 1_{{π(j)⩾4}}}ψ(x).  (30)

If π(1) = 1 then {2, 3} ⊆ {π(2), …, π(n)} and therefore 1_{{π(1)=1}} + ∑_{j=2}^{n} 1_{{π(j)⩾4}} = n − 2 is even. If π(1) ∈ {1, …, n} ∖ {1, 2, 3} then {π(2), …, π(n)} ⊇ {1, 2, 3} and consequently we have that 1_{{π(1)=1}} + ∑_{j=2}^{n} 1_{{π(j)⩾4}} = n − 4 is even. In the remaining case π(1) ∈ {2, 3} we have that 1_{{π(1)=1}} + ∑_{j=2}^{n} 1_{{π(j)⩾4}} = n − 3 is odd. Hence, by (30) we have

∑_{π∈S_{n}} ∑_{x∈M_{n}(𝔽_{2})} |ψ(x + ∑_{j=1}^{n} e_{jπ(j)}) − ψ(x)| = 2^{n^{2}+1} |{π ∈ S_{n} : π(1) ∈ {2, 3}}| = 2^{n^{2}+2}(n − 1)!. (31)

By contrasting (29) with (31) we see that if (9) holds true then necessarily K ⩾ n/2.

3. Uniform and coarse nonembeddability

A metric space (X, d_{X}) is said to admit a uniform embedding into a Banach space (Z, ∥ · ∥_{Z}) if there exists an injective mapping f : X → Z and nondecreasing functions α, β : (0, ∞) → (0, ∞) with lim_{t→0} β(t) = 0 such that α(d_{X}(a, b)) ⩽ ∥f(a) − f(b)∥_{Z} ⩽ β(d_{X}(a, b)) for all distinct a, b ∈ X. Similarly, (X, d_{X}) is said to admit a coarse embedding into a Banach space (Z, ∥ · ∥_{Z}) if there exists a mapping f : X → Z and nondecreasing functions α, β : (0, ∞) → (0, ∞) with lim_{t→∞} α(t) = ∞ for which α(d_{X}(a, b)) ⩽ ∥f(a) − f(b)∥_{Z} ⩽ β(d_{X}(a, b)) for all distinct a, b ∈ X.

The space ℓ_{2}(ℓ_{1}) does not admit a uniform or coarse embedding into L_{1}. Indeed, by [1] in the case of uniform embeddings and by [26] in the case of coarse embeddings, this would imply that ℓ_{2}(ℓ_{1}) is linearly isomorphic to a subspace of L_{0}, which is proved to be impossible in [14, Theorem 4.2].

Theorem 1.7 yields a new proof that ℓ_{2}(ℓ_{1}) does not admit a uniform or coarse embedding into L_{1}. Indeed, suppose that α, β : (0, ∞) → (0, ∞) are nondecreasing and f : ℓ_{2}(ℓ_{1}) → L_{1} satisfies

∀ x, y ∈ ℓ_{2}(ℓ_{1}),  α (∥f(x) − f(y)∥_{ℓ_{2}(ℓ_{1})}) ⩽ ∥f(x) − f(y)∥_{1} ⩽ β (∥f(x) − f(y)∥_{ℓ_{2}(ℓ_{1})}) . (32)

For every s ∈ (0, ∞) and n ∈ 2ℕ, apply Theorem 1.7 to the mapping f_{s} : M_{n}(𝔽_{2}) → L_{1} given by f_{s}(x) = f(sx). The resulting inequality, when combined with (32), implies that α(sn) ≲ β(s\sqrt{n}). Choosing s = 1/\sqrt{n} shows that α(\sqrt{n}) ≲ β(1), so f is not a coarse embedding, and choosing s = 1/n shows that β(1/\sqrt{n}) ≳ α(1) > 0, so f is not a uniform embedding.

Observe that since, by [13], L_{p} is isometric to a subset of L_{1} when p ∈ [1, 2], the above discussion implies that ℓ_{2}(ℓ_{1}) does not admit a uniform or coarse embedding into L_{p} for every p ∈ [1, 2]. Passing now to an examination of the uniform and coarse embeddability of ℓ_{2}(ℓ_{1}) into L_{p} for p > 2, observe first that since, by [1] and [12], when p > 2 there is no uniform or coarse embedding of L_{p} into L_{1}, the fact that ℓ_{2}(ℓ_{1}) does not admit a uniform or coarse embedding into L_{1} does not imply that ℓ_{2}(ℓ_{1}) fails to admit such an embedding into L_{p}. An inspection of the above argument reveals that in order to show that ℓ_{2}(ℓ_{1}) does not admit a uniform or coarse embedding into L_{p} it would suffice to establish the following variant of Theorem 2.1 when p > 2: there exits C_{p}, θ_{p} ∈ (0, ∞) such that for every n ∈ 2ℕ, every f : M_{n}(𝔽_{2}) → L_{p} satisfies

\frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{k=1}^{n} e_{jk})−f(x)∥_{p}^{θ_{p}} ⩽ \frac{C_{p}}{n^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥f(x+∑_{j=1}^{n} e_{jk_{j}})−f(x)∥_{p}^{θ_{p}}. (33)

However, no such extension of Theorem 2.1 to the range p > 2 is possible. Indeed, since ℓ_{2} is linearly isometric to a subspace of L_{p}, we may fix a linear isometry U : ℓ_{p}^{n}(ℓ_{2}^{n}) → L_{p}. Define f : M_{n}(𝔽_{2}) → L_{p} by f(x) = ∑_{j=1}^{n} ∑_{k=1}^{n} x_{jk}U(e_{jk}). For this choice of f, (33) becomes

2^{n^{2}}n^{\frac{θp}{2}} = \frac{1}{n} ∑_{j=1}^{n} ∑_{x∈M_{n}(𝔽_{2})} ∥ ∑_{k=1}^{n} e_{jk}∥_{ℓ_{p}^{n}(ℓ_{2}^{n})}^{θ_{p}} ⩽^{(33)} \frac{C_{p}}{n^{n}} ∑_{k∈\{1,...,n\}^{n}} ∑_{x∈M_{n}(𝔽_{2})} ∥ ∑_{j=1}^{n} e_{jk_{j}} ∥_{ℓ_{p}^{n}(ℓ_{2}^{n})}^{θ_{p}} = 2^{n^{2}}C_{p}n^{\frac{θp}{p}} ,

which is a contradiction for large enough n ∈ 2ℕ, because p > 2. Thus, it was crucial to assume in Theorem 2.1 that p ⩽ 2. When p ⩾ 4, this is accentuated by the following proposition.

Proposition 3.1. For every p ⩾ 4 there exists a mapping F_{p} : ℓ_{2}(ℓ_{1}) → L_{p} that satisfies

∀ x, y ∈ ℓ_{2}(ℓ_{1}),  ∥F_{p}(x) − F_{p}(y)∥_{p} = ∥x − y∥ℓ_{2}(ℓ_{1})^{\frac{2}{p}}.  (34)

Thus ℓ_{2}(ℓ_{1}) admits an embedding into L_{p} that is both uniform and coarse.

Proof. Fix T : ℓ_{1} → L_{2} such that

∀ x, y ∈ ℓ_{1},  ∥T (x) − T (y)∥_{2} = \sqrt{∥x − y∥_{1}}.  (35)

See [7, page 288] for the existence of such T (an explicit formula for T appears in [23, Section 3]). By a theorem of Schoenberg [30], since 4/p ⩽ 1 there exists a mapping σ_{p} : L_{2} → L_{2} that satisfies

∀ x, y ∈ L_{2}  ∥σ_{p}(x) − σ_{p}(y)∥_{2} = ∥x − y∥2^{\frac{4}{p}} .  (36)

Fix also an isometric embedding S : L_{2} → L_{p} and define F_{p} : ℓ_{2}(ℓ_{1}) → ℓ_{p}(L_{p}) ≅ L_{p} by

∀ x ∈ ℓ_{2}(ℓ_{1}), F_{p}(x) =^{def} (S ∘ σ_{p} ∘ T (x_{j}))_{j=1}^{∞} .

Then, for every x, y ∈ ℓ_{2}(ℓ_{1}) we have

∥F_{p}(x) − F_{p}(y)∥_{ℓ_{p}(L_{p})} = ( ∑_{j=1}^{∞} ∥S(σ_{p}(T (x_{j}))) − S(σ_{p}(T (y_{j})))∥_{p}^{p} )^{\frac{1}{p}}

= ( ∑_{j=1}^{∞} ∥σ_{p}(T (x_{j})) − σ_{p}(T (y_{j}))∥_{2}^{p} )^{\frac{1}{p}} =^{(36)} ( ∑_{j=1}^{∞} ∥T (x_{j}) − T (y_{j})∥_{2}^{4} )^{\frac{1}{p}} =^{(35)} ( ∑_{j=1}^{∞} ∥x_{j} − y_{j}∥_{1}^{2} )^{\frac{1}{p}} ,

which is precisely the desired requirement (34). □

The above proof of Proposition 3.1 used the fact that p ⩾ 4 in order for (36) to hold true. It is therefore natural to ask Question 3.2 below. Analogous questions could be asked for uniform and coarse embeddings of ℓ_{p_{1}}(ℓ_{p_{2}}) into L_{p_{3}} (or even into ℓ_{p_{3}}(L_{p_{4}})), and various partial results could be obtained using similar arguments (at times with the embedding in (36) replaced by the embedding of [21, Remark 5.10]). We shall not pursue this direction here because it yields incomplete results.

Question 3.2. Suppose that 2 < p < 4. Does ℓ_{2}(ℓ_{1}) admit a uniform or coarse embedding into L_{p}?

Remark 3.3. In the Introduction we asked whether or not the Schatten trace class S_{1} is a KS metric space. The approach of Section 2 seems inherently insufficient to address this question. Indeed, we treated L_{1} by relating its metric to Hilbert space through the isometric embedding of (L_{1}, \sqrt{∥x − y∥_{1}}), while S_{1} is not even uniformly homeomorphic to a subset of Hilbert space (this follows from [1] combined with e.g. [14] and the classical linear nonembeddability result of [20]). For this reason we believe that asking about the validity of (11) in S_{1} is worthwhile beyond its intrinsic interest, as a potential step towards addressing more general situations in which one cannot reduce the question to (nonlinear) Hilbertian considerations.

4. Embeddings

In this section we shall justify the remaining (simple) embedding statements that were given without proof in the Introduction, starting with the proof of Proposition 1.3.

Proof of Proposition 1.3. Recall that we are given n ∈ ℕ, finite subsets X_{1}, …, X_{n} ⊆ ℓ_{1}, and we denote S = X_{1} × … × X_{n} ⊆ ℓ_{2}^{n}(ℓ_{1}). Thus |S| = ∏_{j=1}^{n} |X_{i}|. We may assume without loss of generality that |X_{j}| > 1 for all j ∈ {1, …, n}. Write

J =^{def} \{j ∈ \{1, …, n\} : |X_{j}| > exp (\frac{\sqrt{log |S|}}{log log |S|})\} .  (37)

Then

|S| ⩾ ∏_{j∈J} |X_{j}| > exp (\frac{|J|\sqrt{log |S|}}{log log |S|}) ⟹ |J| < \sqrt{log |S|} log log |S|.  (38)

By the main result of [2], for every j ∈ {1, …, n} there exists f_{j} : X_{j} → ℓ_{2} such that

∀ u, v ∈ X_{j},  ∥u − v∥_{1} ⩽ ∥f_{j}(u) − f_{j}(v)∥_{2} ≲ \sqrt{log |X_{j}|} log log |X_{j}| · ∥u − v∥_{1}.  (39)

We shall fix from now on an isometric embedding T : ℓ_{2}^{{1,...,n}∖J}(ℓ_{2}) → L_{1}.

Define ϕ : S → (ℓ_{1}^{J}(ℓ_{1})⊕L_{1})_{1}, where (ℓ_{1}^{J}(ℓ_{1})⊕L_{1})_{1} is the corresponding ℓ_{1}-direct sum, by setting

ϕ(u) =^{def} ((u_{j})_{j∈J}) ⊕ T ((f_{j}(u_{j}))_{j∈{1,...,n}∖J}) .

Then for every u, v ∈ S we have

∥ϕ(u) − ϕ(v)∥_{(ℓ_{1}^{J} (ℓ_{1})⊕L_{1})_{1}} = ∑_{j∈J} ∥u_{j} − v_{j}∥_{1} + ( ∑_{j∈\{1,...,n\}∖J} ∥f_{j}(u_{j}) − f_{j}(v_{j})∥_{2}^{2} )^{\frac{1}{2}}

⩾ ( ∑_{j∈J} ∥u_{j} − v_{j}∥_{1}^{2})^{\frac{1}{2}} + ( ∑_{j∈\{1,...,n\}∖J} ∥u_{j} − v_{j}∥_{1}^{2} )^{\frac{1}{2}} ⩾ ∥u − v∥_{ℓ_{2}^{n}(ℓ_{1})}, (40)

where in the first inequality of (40) we used the leftmost inequality in (39). The corresponding upper bound is deduced as follows from Cauchy–Schwarz, the rightmost inequality in (39), the definition of J in (37), and the upper bound on |J| in (38).

∥ϕ(u) − ϕ(v)∥_{(ℓ_{1}^{J} (ℓ_{1})⊕L_{1})_{1}}

= ∑_{j∈J} ∥u_{j} − v_{j}∥_{1} + ( ∑_{j∈\{1,...,n\}∖J} ∥f_{j}(u_{j}) − f_{j}(v_{j})∥_{2}^{2} )^{\frac{1}{2}}

≲ \sqrt{J|}( ∑_{j∈J} ∥u_{j} − v_{j}∥_{1}^{2})^{\frac{1}{2}} + ( max_{j∈\{1,...,n\}∖J} \sqrt{log |X_{j}|} log log |X_{j}|) ( ∑_{j∈\{1,...,n\}∖J} ∥u_{j} − v_{j}∥_{1}^{2} )^{\frac{1}{2}}

⩽ \sqrt[4]{log |S|}\sqrt{log log |S|}( ∑_{j∈J} ∥u_{j} − v_{j}∥_{1}^{2})^{\frac{1}{2}} + \begin{matrix}\sqrt[4]{log |S|} & log & (\frac{\sqrt{log |S|}}{log log |S|}) \\ √ & \overline{log log |S|} \end{matrix}( ∑_{j∈\{1,...,n\}∖J} ∥u_{j} − v_{j}∥_{1}^{2} )^{\frac{1}{2}}

≲ \sqrt[4]{log |S|}\sqrt{log log |S|} · ∥u − v∥_{ℓ_{2}^{n}(ℓ_{1})}.  □

We shall next justify the upper bound on c_{1}(ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) in (14), thus concluding the proof of Theorem 1.8 (the proof of the reverse inequality was presented in Section 1.2). Recall that we are assuming here that q > p ⩾ 1. Since for every x, y ∈ M_{n}(𝔽_{2}) we have

∥x − y∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} = ( ∑_{j=1}^{n} ∥x_{j} − y_{j}∥_{p}^{q})^{\frac{1}{q}} = ( ∑_{j=1}^{n} ∥x_{j} − y_{j}∥1^{\frac{q}{p}} )^{\frac{1}{q}} ,

by Hölder’s inequality

\frac{∥x − y∥ℓ_{1}^{n}(ℓ_{1}^{n})^{\frac{1}{p}}}{n^{\frac{1}{p} − \frac{1}{q}}} ⩽ ∥x − y∥_{ℓ_{q}^{n}(ℓ_{p}^{n})} ⩽ ∥x − y∥ℓ_{1}^{n}(ℓ_{1}^{n})^{\frac{1}{p}}.  (41)

By a classical theorem of Bretagnolle, Dacunha-Castelle and Krivine [6] (see also [31, Theorem 5.11]), for every α ∈ (0, 1] the metric space (L_{1}, ∥x − y∥_{1}^{α}) admits an isometric embedding into L_{1}. Hence, the metric space

(M_{n}(𝔽_{2}), ∥x − y∥ℓ_{1}^{n}(ℓ_{1}^{n})^{\frac{1}{p}})

admits an isometric embedding into L_{1}, and consequently (41) implies that

c_{1} (ℓ_{q}^{n} (𝔽_{2}^{n}, ∥ · ∥_{p})) ⩽ n^{\frac{1}{p} − \frac{1}{q}} .  □

Remark 4.1. Arguing similarly to the above discussion also justifies the assertion in Remark 1.9. Indeed, suppose that m, n ∈ ℕ and q > p ⩾ 1. Then by Hölder’s inequality for every x, y ∈ ℓ_{q}^{m}(𝔽_{2}^{n}),

\frac{∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{p}}}{m^{\frac{1}{p} − \frac{1}{q}}} = \frac{∥x − y∥_{ℓ_{p}^{m}(ℓ_{p}^{n})}}{m^{\frac{1}{p} − \frac{1}{q}}} ⩽ ∥x − y∥_{ℓ_{q}^{m}(ℓ_{p}^{n})} ⩽ ∥x − y∥_{ℓ_{p}^{m}(ℓ_{p}^{n})} = ∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{p}}.  (42)

Also, because for every x, y ∈ ℓ_{q}^{m}(𝔽_{2}^{n}) and j ∈ {1, …, m} we have ∥x_{j} − y_{j}∥_{1} ∈ {0, …, n},

∥x − y∥_{ℓ_{q}^{m}(ℓ_{p}^{n})} = ( ∑_{j=1}^{m} ∥x_{j} − y_{j}∥1^{\frac{q}{p}} )^{\frac{1}{q}} ∈ [∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{q}}, n^{\frac{1}{p} − \frac{1}{q}} ∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{q}}] .  (43)

Letting M_{m×n}(𝔽_{2}) denote the space of m by n matrices with entries in 𝔽_{2}, since the metric spaces

(M_{m×n}(𝔽_{2}), ∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{p}})  and  (M_{m×n}(𝔽_{2}), ∥x − y∥ℓ_{1}^{m}(ℓ_{1}^{n})^{\frac{1}{q}})

admit an isometric embedding into L_{1}, it follows from (42) and (43) that

c_{1} (ℓ_{q}^{m} (𝔽_{2}^{n}, ∥ · ∥_{p})) ⩽ min \{m^{\frac{1}{p} − \frac{1}{q}} , n^{\frac{1}{p} − \frac{1}{q}} \} .  (44)

Since ℓ_{q}^{m} (𝔽_{2}^{n}, ∥ · ∥_{p}) contains an isometric copy of ℓ_{q}^{min{m,n}} (𝔽_{2}^{min{m,n}}, ∥ · ∥_{p}), by (14) and (44),

c_{1} (ℓ_{q}^{m} (𝔽_{2}^{n}, ∥ · ∥_{p})) ≍ c_{1} (ℓ_{q}^{min{m,n}} (𝔽_{2}^{min{m,n}}, ∥ · ∥_{p})) ,

as required.

We end with a brief justification of (15). If 1 ⩽ p < q and p ⩽ 2 then c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n})) ≳ n^{1/p−1/q}, as proved by Kwapień and Schütt [16]. The reverse inequality follows from the fact that the ℓ_{q}^{n}(ℓ_{p}^{n}) norm is n^{1/p−1/q}-equivalent to the ℓ_{p}^{n}(ℓ_{p}^{n}) norm, and from the fact [13] that ℓ_{p} is isometric to a subspace of L_{1} when p ⩽ 2. When q > p > 2, the ℓ_{p}^{n} norm is n^{1/2−1/p}-equivalent to the ℓ_{2}^{n} norm and the ℓ_{q}^{n} norm is n^{1/2−1/q}-equivalent to the ℓ_{2}^{n} norm. So, the ℓ_{q}^{n}(ℓ_{p}^{n}) norm is n^{1−1/p−1/q}-equivalent to the ℓ_{2}^{n}(ℓ_{2}^{n}) norm, which embeds isometrically into L_{1}. For the matching lower bound, suppose that T : ℓ_{q}^{n}(ℓ_{p}^{n}) → L_{1} is an injective linear mapping. Since L_{1} has cotype 2 (see e.g. [19]),

\frac{n^{2}}{∥T^{−1}∥^{2}} ⩽ ∑_{j=1}^{n} ∑_{k=1}^{n} ∥T e_{jk}∥_{1}^{2} ≲ \frac{1}{2^{n^{2}}} ∑_{ε∈\{−1,1\}^{n^{2}}} ∥ ∑_{j=1}^{n} ∑_{k=1}^{n} ε_{jk}T e_{jk}∥_{1}^{2}

⩽ \frac{∥T ∥^{2}}{2^{n^{2}}} ∑_{ε∈\{−1,1\}^{n^{2}}} ∥ ∑_{j=1}^{n} ∑_{k=1}^{n} e_{jk}∥_{ℓ_{q}^{n}(ℓ_{p}^{n})}^{2} = ∥T ∥^{2} · n^{\frac{2}{p} + \frac{2}{q}} . (45)

By (45) we have ∥T ∥ · ∥T^{−1}∥ ≳ n^{1−1/p−1/q}. The fact that c_{1} (ℓ_{q}^{n}(ℓ_{p}^{n})) ≳ n^{1−1/p−1/q} now follows by a standard differentiation argument; see e.g. [4, Chapter 7] (alternatively, one could repeat the above argument mutatis mutandis, while using the fact that L_{1} has metric cotype 2 directly; see [22]).

References

[1] I. Aharoni, B. Maurey, and B. S. Mityagin. Uniform embeddings of metric spaces and of Banach spaces into Hilbert spaces. Israel J. Math., 52(3):251–265, 1985.

[2] S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1–21 (electronic), 2008.

[3] K. Ball. The Ribe programme. Astérisque, (352):Exp. No. 1047, viii, 147–159, 2013. Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058.

[4] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[5] J. Bourgain, V. Milman, and H. Wolfson. On type of metric spaces. Trans. Amer. Math. Soc., 294(1):295–317, 1986.

[6] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Lois stables et espaces L^{p}. Ann. Inst. H. Poincaré Sect. B (N.S.), 2:231–259, 1965/1966.

[7] M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.

[8] P. Enflo. Uniform homeomorphisms between Banach spaces. In Séminaire Maurey-Schwartz (1975–1976), Espaces L^{p}, applications radonifiantes et géométrie des espaces de Banach, Exp. No. 18, page 7. Centre Math., École Polytech., Palaiseau, 1976.

[9] M. Gromov. Filling Riemannian manifolds. J. Differential Geom., 18(1):1–147, 1983.

[10] S. Heinrich. Ultraproducts in Banach space theory. J. Reine Angew. Math., 313:72–104, 1980.

[11] S. Heinrich and P. Mankiewicz. Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces. Studia Math., 73(3):225–251, 1982.

[12] W. B. Johnson and N. L. Randrianarivony. l_{p} (p > 2) does not coarsely embed into a Hilbert space. Proc. Amer. Math. Soc., 134(4):1045–1050 (electronic), 2006.

[13] M. Ĭ. Kadec′. Linear dimension of the spaces L_{p} and l_{q}. Uspehi Mat. Nauk, 13(6 (84)):95–98, 1958.

[14] N. J. Kalton. Banach spaces embedding into L_{0}. Israel J. Math., 52(4):305–319, 1985.

[15] S. Kwapień and C. Schütt. Some combinatorial and probabilistic inequalities and their application to Banach space theory. Studia Math., 82(1):91–106, 1985.

[16] S. Kwapień and C. Schütt. Some combinatorial and probabilistic inequalities and their application to Banach space theory. II. Studia Math., 95(2):141–154, 1989.

[17] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. I. Springer-Verlag, Berlin-New York, 1977. Sequence spaces, Ergebnisse der Mathematik und ihrer Grenzgebiete, Vol. 92.

[18] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[19] B. Maurey. Type, cotype and K-convexity. In Handbook of the geometry of Banach spaces, Vol. 2, pages 1299– 1332. North-Holland, Amsterdam, 2003.

[20] C. A. McCarthy. c_{p}. Israel J. Math., 5:249–271, 1967.

[21] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

[22] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247–298, 2008.

[23] A. Naor. L_{1} embeddings of the Heisenberg group and fast estimation of graph isoperimetry. In Proceedings of the International Congress of Mathematicians. Volume III, pages 1549–1575. Hindustan Book Agency, New Delhi, 2010.

[24] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2):167–233, 2012.

[25] M. I. Ostrovskii. Metric embeddings, volume 49 of De Gruyter Studies in Mathematics. De Gruyter, Berlin, 2013. Bilipschitz and coarse embeddings into Banach spaces.

[26] N. L. Randrianarivony. Characterization of quasi-Banach spaces which coarsely embed into a Hilbert space. Proc. Amer. Math. Soc., 134(5):1315–1317 (electronic), 2006.

[27] Y. Raynaud. Sur les sous-espaces de L^{p}(L^{q}). In Séminaire d’Analyse Fonctionelle 1984/1985, volume 26 of Publ. Math. Univ. Paris VII, pages 49–71. Univ. Paris VII, Paris, 1986.

[28] Y. Raynaud and C. Schütt. Some results on symmetric subspaces of L_{1}. Studia Math., 89(1):27–35, 1988.

[29] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14(2):237–244, 1976.

[30] I. J. Schoenberg. Metric spaces and positive definite functions. Trans. Amer. Math. Soc., 44(3):522–536, 1938.

[31] J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, New York-Heidelberg, 1975. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 84.

Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA

   E-mail address: naor@math.princeton.edu

Department of Mathematics, Weizmann Institute of Science, Rehovot 76100, Israel

   E-mail address: gideon@weizmann.ac.il