Metric Cotype

Manor Mendel California Institute of Technology

Assaf Naor Microsoft Research

Abstract

We introduce the notion of cotype of a metric space, and prove that for Banach spaces it coincides with the classical notion of Rademacher cotype. This yields a concrete version of Ribe’s theorem, settling a long standing open problem in the non-linear theory of Banach spaces. We apply our results to several problems in metric geometry. Namely, we use metric cotype in the study of uniform and coarse embeddings, settling in particular the problem of classifying when L_{p} coarsely or uniformly embeds into L_{q}. We also prove a non-linear analog of the Maurey-Pisier theorem, and use it to answer a question posed by Arora, Lovász, Newman, Rabani, Rabinovich and Vempala, and to obtain quantitative bounds in a metric Ramsey theorem due to Matoušek.

1 Introduction

In 1976 Ribe [61] (see also [62, 27, 9, 6]) proved that if X and Y are uniformly homeomorphic Banach spaces then X is finitely representable in Y, and vice versa (X is said to be finitely representable in Y if there exists a constant K > 0 such that any finite dimensional subspace of X is K-isomorphic to a subspace of Y). This theorem suggests that “local properties” of Banach spaces, i.e. properties whose definition involves statements about finitely many vectors, have a purely metric characterization. Finding explicit manifestations of this phenomenon for specific local properties of Banach spaces (such as type, cotype and superreflexivity), has long been a major driving force in the bi-Lipschitz theory of metric spaces (see Bourgain’s paper [8] for a discussion of this research program). Indeed, as will become clear below, the search for concrete versions of Ribe’s theorem has fueled some of the field’s most important achievements.

The notions of type and cotype of Banach spaces are the basis of a deep and rich theory which encompasses diverse aspects of the local theory of Banach spaces. We refer to [49, 58, 57, 67, 59, 36, 15, 70, 45] and the references therein for background on these topics. A Banach space X is said to have (Rademacher) type p > 0 if there exists a constant T < ∞ such that for every n and every x_{1}, …, x_{n} ∈ X,

ε∥∑_{j=1}^{n} ε_{j}x_{j} ∥_{X}^{p} ≤ T^{p} ∑_{j=1}^{n} ∥x_{j}∥_{X}^{p}.  (1)

where the expectation _{ε} is with respect to a uniform choice of signs ε_{1}, …, ε_{n} ∈ {−1, 1}^{n}. X is said to have (Rademacher) cotype q > 0 if there exists a constant C < ∞ such that for every n and every x_{1}, …, x_{n} ∈ X,

ε∥∑_{j=1}^{n} ε_{j}x_{j} ∥_{X}^{q} ≥ \frac{1}{C^{q}} ∑_{j=1}^{n} ∥x_{j}∥_{X}^{q}.  (2)

These notions are clearly linear notions, since their definition involves addition and multiplication by scalars. Ribe’s theorem implies that these notions are preserved under uniform homeomorphisms of Banach spaces, and therefore it would be desirable to reformulate them using only distances between points in the given Banach space. Once this is achieved, one could define the notion of type and cotype of a metric space, and then hopefully transfer some of the deep theory of type and cotype to the context of arbitrary metric spaces. The need for such a theory has recently received renewed impetus due to the discovery of striking applications of metric geometry to theoretical computer science (see [44, 28, 41] and the references therein for part of the recent developments in this direction).

Enflo’s pioneering work [18, 19, 20, 21] resulted in the formulation of a non-linear notion of type, known today as Enflo type. The basic idea is that given a Banach space X and x_{1}, …, x_{n} ∈ X, one can consider the linear function f : {−1, 1}^{n} → X given by f (ε) = ∑ _{j=1}^{n} ε_{j}x_{j}. Then (1) becomes

ε∥f (ε) − f (−ε)∥_{X}^{p} ≤ T^{p} ∑_{j=1}^{n} _{ε} ∥f (ε_{1}, …, ε_{j−1} , ε_{j}, ε_{j+1} , …, ε_{n}) − f (ε_{1}, …, ε_{j−1} , −ε_{j}, ε_{j+1} , …, ε_{n})∥_{X}^{p}. (3)

One can thus say that a metric space (M, d_{M}) has Enflo type p if there exists a constant T such that for every n ∈ and every f : {−1, 1}^{n} → M,

εd_{M} (f (ε), f (−ε)) ^{p}

≤ T^{p} ∑_{j=1}^{n} _{ε}d_{M} (f (ε_{1}, …, ε_{j−1} , ε_{j}, ε_{j+1} , …, ε_{n}), f (ε_{1}, …, ε_{j−1} , −ε_{j}, ε_{j+1} , …, ε_{n}))^{p} . (4)

There are two natural concerns about this definition. First of all, while in the category of Banach spaces (4) is clearly a strengthening of (3) (as we are not restricting only to linear functions f), it isn’t clear whether (4) follows from (3). Indeed, this problem was posed by Enflo in [21], and in full generality it remains open. Secondly, we do not know if (4) is a useful notion, in the sense that it yields metric variants of certain theorems from the linear theory of type (it should be remarked here that Enflo found striking applications of his notion of type to Hilbert’s fifth problem in infinite dimensions [19, 20, 21], and to the uniform classification of L_{p} spaces [18]). As we will presently see, in a certain sense both of these issues turned out not to be problematic. Variants of Enflo type were studied by Gromov [24] and Bourgain, Milman and Wolfson [11]. Following Bourgain-Milman and Wolfson [11] we shall say that a metric space (M, d_{M}) has BMW type p > 0 if there exists a constant K < ∞ such that for every n ∈ and every f : {−1, 1}^{n} → M,

εd_{M}(f (ε), f (−ε))^{2}

≤ K^{2}n^{\frac{2}{p}−1} ∑_{j=1}^{n} _{ε}d_{M} (f (ε_{1}, …, ε_{j−1} , ε_{j}, ε_{j+1} , …, ε_{n}), f (ε_{1}, …, ε_{j−1} , −ε_{j}, ε_{j+1} , …, ε_{n}))^{2} . (5)

Bourgain, Milman and Wolfson proved in [11] that if a Banach space has BMW type p > 0 then it also has Rademacher type p′ for all 0 < p′ < p. They also obtained a non-linear version of the Maurey-Pisier theorem for type [54, 46], yielding a characterization of metric spaces which contain bi-Lipschitz copies of the Hamming cube. In [58] Pisier proved that for Banach spaces, Rademacher type p implies Enflo type p′ for every 0 < p′ < p. Variants of these problems were studied by Naor and Schechtman in [52]. A stronger notion of non-linear type, known as Markov type, was introduced by Ball [4] in his study of the Lipschitz extension problem. This important notion has since found applications to various fundamental problems in metric geometry [50, 42, 5, 51, 48]

Despite the vast amount of research on non-linear type, a non-linear notion of cotype remained elusive. Indeed, the problem of finding a notion of cotype which makes sense for arbitrary metric spaces, and which coincides (or almost coincides) with the notion of Rademacher type when restricted to Banach spaces, became a central open problem in the field.

There are several difficulties involved in defining non-linear cotype. First of all, one cannot simply reverse inequalities (4) and (5), since the resulting condition fails to hold true even for Hilbert space (with p = 2). Secondly, if Hilbert space satisfies an inequality such as (4), then it must satisfy the same inequality where the distances are raised to any power 0 < r < p. This is because Hilbert space, equipped with the metric ∥x − y∥^{r/p}, is isometric to a subset of Hilbert space (see [64, 69]). In the context of non-linear type, this observation makes perfect sense, since if a Banach space has type p then it also has type r for every 0 < r < p. But, this is no longer true for cotype (in particular, no Banach space has cotype less than 2). One viable definition of cotype of a metric space X that was suggested in the early 1980s is the following: Let M be a metric space, and denote by Lip(M) the Banach space of all real valued Lipschitz functions on M, equipped with the Lipschitz norm. One can then define the non-linear cotype of M as the (Rademacher) cotype of the (linear) dual Lip(M)^{∗}. This is a natural definition when M is a Banach space, since we can view Lip(M) as a non-linear substitute for the dual space M^{∗} (note that in [37] it is shown that there is a norm 1 projection from Lip(M) onto M^{∗}). With this point of view, the above definition of cotype is natural due to the principle of local reflexivity [39, 30]. Unfortunately, Bourgain [8] has shown that under this definition subsets of L_{1} need not have finite non-linear cotype (while L_{1} has cotype 2). Additionally, the space Lip(M)^{∗} is very hard to compute- for example it is an intriguing open problem whether even the unit square [0, 1]^{2} has non-linear cotype 2 under the above definition.

In this paper we introduce a notion of cotype of metric spaces, and show that it coincides with Rademacher cotype when restricted to the category of Banach spaces. Namely, we introduce the following concept:

Definition 1.1 (Metric cotype). Let (M, d_{M}) be a metric space and q > 0. We shall say (M, d_{M}) has metric cotype q with constant Γ if for every integer n ∈ , there exists an even integer m, such that for every f : _{m}^{n} → M,

∑_{j=1}^{n} _{x}[d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{q}]≤ Γ^{q}m^{q} _{ε,x}[d_{M}(f (x + ε), f (x))^{q}] ,  (6)

where the expectations above are taken with respect to uniformly chosen x ∈ _{m}^{n} and ε ∈ {−1, 0, 1}^{n} (here, and in what follows we denote by {e_{j}}_{j=1}^{n} the standard basis of ^{n}). The smallest constant Γ with which inequality (6) holds true is denoted Γ_{q}(M).

The following theorem is the main result of this paper:

Theorem 1.2. Let X be a Banach space, and q ∈ [2, ∞). Then X has metric cotype q if and only if X has Rademacher cotype q. Moreover,

\frac{1}{2π}C_{q}(X) ≤ Γ_{q}(X) ≤ 90C_{q}(X).

Apart from settling the non-linear cotype problem described above, this notion has various applications. Thus, in the remainder of this paper we proceed to study metric cotype and some of its applications, which we describe below. We believe that additional applications of this notion and its variants will be discovered in the future. In particular, it seems worthwhile to study the interaction between metric type and metric cotype (such as in Kwapien’s theorem [35]), the possible “Markov” variants of metric cotype (à la Ball [4]) and their relation to the Lipschitz extension problem, and the relation between metric cotype and the nonlinear Dvoretzky theorem (see [10, 5] for information about the non-linear Dvoretzky theorem, and [22] for the connection between cotype and Dvoretzky’s theorem).

1.1 Some applications of metric cotype

1) A non-linear version of the Maurey-Pisier theorem. Given two metric spaces (M, d_{M}) and (N, d_{N}), and an injective mapping f : M ↪ N, we denote the distortion of f by

dist(f) ∥f ∥_{Lip} · ∥f^{−1}∥_{Lip} = sup_{\begin{matrix}x,y∈M \\ x y \end{matrix}} \frac{d_{N}(f (x), f (y))}{d_{M}(x, y)} · sup_{\begin{matrix}x,y∈M \\ x y \end{matrix}} \frac{d_{M}(x, y)}{d_{N}(f (x), f (y))}.

The smallest distortion with which M can be embedded into N is denoted c_{N}(M), i.e.

c_{N}(M) inf{dist(f) : f : M ↪ N}.

If c_{N}(M) ≤ α then we sometimes use the notation M ↪^{α} N. When N = L_{p} for some p ≥ 1 we write c_{N}(·) = c_{p}(·).

For a Banach space X write

p_{X} = sup{p ≥ 1 : T_{p}(X) < ∞} and q_{X} = inf{q ≥ 2 : C_{q}(X) < ∞}.

X is said to have non-trivial type if p_{X} > 1, and X is said to have non-trivial cotype if q_{X} < ∞.

In [54] Pisier proved that X has no non-trivial type if and only if for every n ∈ and every ε > 0, ℓ_{1}^{n} ↪^{1+ε} X. A non-linear analog of this result was proved by Bourgain, Milman and Wolfson [11] (see also Pisier’s proof in [58]). They showed that a metric space M does not have BMW type larger than 1 if and only if for every n ∈ and every ε > 0, ({0, 1}^{n}, ∥ · ∥_{1}) ↪^{1+ε} M. In [46] Maurey and Pisier proved that a Banach space X has no non-trivial cotype if and only for every n ∈ and every ε > 0, ℓ_{∞}^{n} ↪^{1+ε} X. To obtain a non-linear analog of this theorem we need to introduce a variant of metric cotype (which is analogous to the variant of Enflo type that was used by Bourgain, Milman and Wolfson).

Definition 1.3 (Variants of metric cotype à la Bourgain, Milman and Wolfson). Let (M, d_{M}) be a metric space and 0 < p ≤ q. We denote by Γ_{q}^{(p)}(M) the least constant Γ such that for every integer n ∈ there exists an even integer m, such that for every f : _{m}^{n} → M,

∑_{j=1}^{n} _{x}[d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p}]≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} _{ε,x}[d_{M}(f (x + ε), f (x))^{p}] ,  (7)

where the expectations above are taken with respect to uniformly chosen x ∈ _{m}^{n} and ε ∈ {−1, 0, 1}^{n}. The smallest constant Γ with which inequality (7) holds true is denoted Γ_{q}^{(p)}(M). In particular Γ_{q}^{(q)}(M) = Γ_{q}(M). When 1 ≤ p < q we shall refer to (7) as a weak metric cotype q inequality with exponent p and constant Γ.

The following theorem is analogous to Theorem 1.2.

Theorem 1.4. Let X be a Banach space, and assume that for some 1 ≤ p < q, Γ_{q}^{(p)}(X) < ∞. Then X has cotype q′for every q′ > q. If q = 2 then X has cotype 2. On the other hand,

Γ_{q}^{(p)}(X) ≤ c_{pq}C_{q}(X),

where c_{pq} is a universal constant depending only on p and q.

In what follows, for m, n ∈ and p ∈ [1, ∞] we let [m]_{p}^{n} denote the set {0, 1, …, m}^{n}, equipped with the metric induced by ℓ_{p}^{n}. The following theorem is a metric version of the Maurey-Pisier theorem (for cotype):

Theorem 1.5. Let M be a metric space such that Γ_{q}^{(2)}(M) = ∞ for all q < ∞. Then for every m, n ∈ and every ε > 0,

[m]_{∞}^{n} ↪^{1+ε} M.

We remark that in [46] Maurey and Pisier prove a stronger result, namely that for a Banach space X, for every n ∈ and every ε > 0, ℓ_{p_{X}}^{n} ↪^{1+ε} X and ℓ_{q_{X}}^{n} ↪^{1+ε} X. Even in the case of non-linear type, the results of Bourgain, Milman and Wolfson yield an incomplete analog of this result in the case of BMW type greater than 1. The same phenomenon seems to occur when one tries to obtain a non-linear analog of the full Maurey-Pisier theorem for cotype. We believe that this issue deserves more attention in future research.

2) Solution of a problem posed by Arora, Lovász, Newman, Rabani, Rabinovich and Vempala. The following question appears in [3] (see Conjecture 1 there):

Let F be a normal metric class which does not contain all finite metrics with distortion arbitrarily close to 1. Does this imply that there exists α > 0 and arbitrarily large n-point metric spaces M_{n} such that for every N ∈ F, c_{N}(M_{n}) ≥ (logn)^{α}?

We refer to [3] for the definition of a normal metric class (see Section 2 there), since we will not use this notion in what follows. We also refer to [3] for background and motivation from combinatorial optimization for this problem, where several partial results in this direction are obtained. Here we apply metric cotype to settle this conjecture positively, without any restriction on the class F.

To state our result we first introduce some notation. If F is a family of metric spaces we write

c_{F}(N) = inf {c_{M}(N) : M ∈ F } .

For an integer n ≥ 1 we define

D_{n}(F) = sup{c_{F}(N) : N is a metric space, |N| ≤ n}.

Observe that if, for example, F consists of all the subsets of Hilbert space (or L_{1}), then Bourgain’s embedding theorem [7] implies that D_{n}(F) = O(logn).

For K > 0 we define the K-cotype (with exponent 2) of a family of metric spaces F as

q_{F}^{(2)}(K) = sup_{M∈F} inf {q ∈ (0, ∞] : Γ_{q}^{(2)}(M) ≤ K} .

Finally we let

q_{F}^{(2)} = inf_{K>0} q_{F}^{(2)}(K).

The following theorem settles positively the problem stated above:

Theorem 1.6. Let F be a family of metric spaces. Then the following conditions are equivalent:

1. There exists a finite metric space M for which c_{F}(M) > 1.

2. q_{F}^{(2)} < ∞.

3. There exists 0 < α < ∞ such that D_{n}(F) = Ω ((logn)^{α}).

3) A quantitative version of Matoušek’s BD Ramsey theorem. In [43] Matoušek proved the following result, which he calls the Bounded Distortion (BD) Ramsey theorem. We refer to [43] for motivation and background on these types of results.

Theorem 1.7 (Matoušek’s BD Ramsey theorem). Let X be a finite metric space and ε > 0, γ > 1. Then there exists a metric space Y = Y(X, ε, γ), such that for every metric space Z,

c_{Z}(Y) < γ ⟹ c_{Z}(X) < 1 + ε.

We obtain a new proof of Theorem 1.7, which is quantitative and concrete:

Theorem 1.8 (Quantitative version of Matoušek’s BD Ramsey theorem). There exists a universal constant C with the following properties. Let X be an n-point metric space and ε ∈ (0, 1), γ > 1. Then for every integer N ≥ (Cγ)^{2^{5A}}, where

A = max\{ \frac{4 diam(X)}{ε · min_{x y} d_{X}(x, y)}, n\},

if a metric space Z satisfies c_{Z}(X) > 1 + ε then, c_{Z} ([N^{5}]_{∞}^{N}) > γ.

We note that Matoušek’s argument in [43] uses Ramsey theory, and is non-constructive (at best it can yield tower-type bounds on the size of Z, which are much worse than what the cotype-based approach gives).

4) Uniform embeddings and Smirnov’s problem. Let (M, d_{M}) and (N, d_{N}) be metric spaces. A mapping f : M → N is called a uniform embedding if f is injective, and both f and f^{−1} are uniformly continuous. There is a large body of work on the uniform classification of metric spaces- we refer to the survey article [38], the book [6], and the references therein for background on this topic. In spite of this, several fundamental questions remain open. For example, it wasn’t known for which values of 0 < p, q < ∞, L_{p} embeds uniformly into L_{q}. As we will presently see, our results yield a complete characterization of these values of p, q.

In the late 1950’s Smirnov asked whether every separable metric space embeds uniformly into L_{2} (see [23]). Smirnov’s problem was settled negatively by Enflo in [17]. Following Enflo, we shall say that a metric space M is a universal uniform embedding space if every separable metric space embeds uniformly into M. Since every separable metric space is isometric to a subset of C[0, 1], this is equivalent to asking whether C[0, 1] is uniformly homeomorphic to a subset of M (the space C[0, 1] can be replaced here by c_{0} due to Aharoni’s theorem [1]). Enflo proved that c_{0} does not uniformly embed into Hilbert space. In [2] Aharoni, Maurey and Mityagin systematically studied metric spaces which are uniformly homeomorphic to a subset of Hilbert space, and obtained an elegant characterization of Banach spaces which are uniformly homeomorphic to a subset of L_{2}. In particular, the results of [2] imply that for p > 2, L_{p} is not uniformly homeomorphic to a subset of L_{2}.

Here we prove that in the class of Banach spaces with non-trivial type, if Y embeds uniformly into X, then Y inherits the cotype of X. More precisely:

Theorem 1.9. Let X be a Banach space with non-trivial type. Assume that Y is a Banach space which uniformly embeds into X. Then q_{Y} ≤ q_{X}.

As a corollary, we complete the characterization of the values of 0 < p, q < ∞ for which L_{p} embeds uniformly into L_{q}:

Theorem 1.10. For p, q > 0, L_{p} embeds uniformly into L_{q} if and only if p ≤ q or q ≤ p ≤ 2.

We believe that the assumption that X has non-trivial type in Theorem 1.9 can be removed- in Section 8 we present a concrete problem which would imply this fact. If true, this would imply that cotype is preserved under uniform embeddings of Banach spaces. In particular, it would follow that a universal uniform embedding space cannot have non-trivial cotype, and thus by the Maurey-Pisier theorem [46] it must contain ℓ_{∞}^{n} ’s with distortion uniformly bounded in n.

5) Coarse embeddings. Let (M, d_{M}) and (N, d_{N}) be metric spaces. A mapping f : M → N is called a coarse embedding if there exists two non-decreasing functions α, β : [0, ∞) → [0, ∞) such that lim_{t→∞} α(t) = ∞, and for every x, y ∈ M,

α(d_{M}(x, y)) ≤ d_{N}(f (x), f (y)) ≤ β(d_{M}(x, y)).

This (seemingly weak) notion of embedding was introduced by Gromov (see [25]), and has several important geometric applications. In particular, Yu [71] obtained a striking connection between the Novikov and Baum-Connes conjectures and coarse embeddings into Hilbert spaces. In [33] Kasparov and Yu generalized this to coarse embeddings into arbitrary uniformly convex Banach spaces. It was unclear, however, whether this is indeed a strict generalization, i.e. whether or not the existence of a coarse embedding into a uniformly convex Banach space implies the existence of a coarse embedding into a Hilbert space. This was resolved by Johnson and Randrianarivony in [29], who proved that for p > 2, L_{p} does not coarsely embed into L_{2}. In [60], Randrianarivony proceeded to obtain a characterization of Banach spaces which embed coarsely into L_{2}, in the spirit of the result of Aharoni, Maurey and Mityagin [2]. There are very few known methods of proving coarse non-embeddability results. Apart from the papers [29, 60] quoted above, we refer to [26, 16, 53] for results of this type. Here we use metric cotype to prove the following coarse variants of Theorem 1.9 and Theorem 1.10, which generalize, in particular, the theorem of Johnson and Randrianarivony.

Theorem 1.11. Let X be a Banach space with non-trivial type. Assume that Y is a Banach space which coarsely embeds into X. Then q_{Y} ≤ q_{X}. In particular, for p, q > 0, L_{p} embeds coarsely into L_{q} if and only if p ≤ q or q ≤ p ≤ 2.

6) Bi-Lipschitz embeddings of the integer lattice. Bi-Lipschitz embeddings of the integer lattice [m]_{p}^{n} were investigated by Bourgain in [9] and by the present authors in [48]. In [48] is was shown that if 2 ≤ p < ∞ and Y is a Banach space which admits an equivalent norm whose modulus of uniform convexity has power type 2, then

c_{Y}([m]_{p}^{n})= Θ (min\{n^{\frac{1}{2}− \frac{1}{p}} , m^{1− \frac{2}{p}} \}),  (8)

where the implied constants in the above asymptotic equivalence depend on p and on the 2-convexity constant of Y. Moreover, it was shown in [48] that

c_{Y}([m]_{∞}^{n} ) = Ω (min \{ \sqrt{\frac{n}{logn}}, \frac{m}{\sqrt{logm}}\}).

It was conjectured in [48] that the logarithmic terms above are unnecessary. Using our results on metric cotype we settle this conjecture positively, by proving the following general theorem:

Theorem 1.12. Let Y be a Banach space with non-trivial type which has cotype q. Then

c_{Y}([m]_{∞}^{n} ) = Ω (min{n^{1/q}, m}).

Similarly, our methods imply that (8) holds true for any Banach space Y with non-trivial type and cotype 2 (note that these conditions are strictly weaker than being 2-convex, as shown e.g. in [40]). Moreover, it is possible to generalize the lower bound in (8) to Banach spaces with non-trivial type, and cotype 2 ≤ q ≤ p, in which case the lower bound becomes min\{n^{\frac{1}{q}− \frac{1}{p}} , m^{1− \frac{q}{p}} \}.

7) Quadratic inequalities on the cut-cone. An intriguing aspect of Theorem 1.2 is that L_{1} has metric cotype 2. Thus, we obtain a non-trivial inequality on L_{1} which involves distances squared. To the best of our knowledge, all the known non-embeddability results for L_{1} are based on Poincaré type inequalities in which distances are raised to the power 1. Clearly, any such inequality reduces to an inequality on the real line. Equivalently, by the cut-cone representation of L_{1} metrics (see [14]) it is enough to prove any such inequality for cut metrics, which are particularly simple. Theorem 1.2 seems to be the first truly “infinite dimensional” metric inequality in L_{1}, in the sense that its non-linearity does not allow a straightforward reduction to the one-dimensional case. We believe that understanding such inequalities on L_{1} deserves further scrutiny, especially as they hint at certain non-trivial (and non-linear) interactions between cuts.

2 Preliminaries and notation

We start by setting some notation and conventions. Consider the standard ℓ_{∞} Cayley graph on _{m}^{n}, namely x, y ∈ _{m}^{n}are joined by an edge if and only if they are distinct and x−y ∈ {−1, 0, 1}^{n}. This induces a shortestpath metric on _{m}^{n} which we denote by d_{_{m}^{n}}(·, ·). Equivalently, the metric space ( _{m}^{n}, d_{_{m}^{n}}) is precisely the quotient ( ^{n}, ∥ · ∥_{∞} )/(m )^{n} (for background on quotient metrics see [13, 25]). The ball of radius r around x ∈ _{m}^{n} will be denoted B_{_{m}^{n}}(x, r). We denote by μ the normalized counting measure on _{m}^{n} (which is clearly the Haar measure on this group). We also denote by σ the normalized counting measure on {−1, 0, 1}^{n}. In what follows, whenever we average over uniformly chosen signs ε ∈ {−1, 1}^{n} we use the probabilistic notation _{ε} (in this sense we break from the notation used in the introduction, for the sake of clarity of the ensuing arguments).

In what follows all Banach spaces are assumed to be over the complex numbers . All of our results hold for real Banach spaces as well, by a straightforward complexification argument.

Given a Banach space X and p, q ∈ [1, ∞) we denote by C_{q}^{(p)}(X) the infimum over all constants C > 0 such that for every integer n ∈ and every x_{1}, …, x_{n} ∈ X,

( _{ε}∥∑_{j=1}^{n} ε_{j}x_{j} ∥_{X}^{p})^{1/p} ≥ \frac{1}{C}(∑_{j=1}^{n} ∥x_{j}∥_{X}^{q})^{1/q}.  (9)

Thus, using our previous notation, C_{q}^{(q)}(X) = C_{q}(X). Kahane’s inequality [31] says that for 1 ≤ p, q < ∞ there exists a constant 1 ≤ A_{pq} < ∞ such that for every Banach space X, every integer n ∈ , and every x_{1}, …, x_{n} ∈ X,

( _{ε}∥∑_{j=1}^{n} ε_{j}x_{j} ∥_{X}^{p})^{1/p} ≤ A_{pq}( _{ε}∥∑_{j=1}^{n} ε_{j}x_{j} ∥_{X}^{q})^{1/q}.  (10)

Where clearly A_{pq} = 1 if p ≤ q, and for every 1 ≤ q < p < ∞, A_{pq} = O ( \sqrt{p}) (see [65]). It follows in particular from (10) that if X has cotype q then for every p ∈ [1, ∞), C_{q}^{(p)}(X) = O_{p,q}(C_{q}(X)), where the implied constant may depend on p and q.

Given A ⊆ {1, …, n}, we consider the Walsh functions W_{A}: {−1, 1}^{n} → , defined as

W_{A}(ε_{1}, …, ε_{m}) = ∏_{j∈A} ε_{j}.

Every f : {−1, 1}^{n} → X can be written as

f (ε_{1}, …, ε_{n}) = ∑_{A⊆{1,...,n}}f̂(A)W_{A},

where f̂(A) ∈ X are given by

f̂(A) = _{ε}(f (ε)W_{A}).

The Rademacher projection of f is defined by

Rad(f) = ∑_{j=1}^{n} f̂(A)W_{{j}}.

The K-convexity constant of X, denoted K(X), is the smallest constant K such that for every n and every f : {−1, 1}^{n} → X,

ε∥Rad(f)(ε)∥_{X}^{2} ≤ K^{2} _{ε}∥f (ε)∥_{X}^{2}.

In other words,

K(X) = sup_{n∈}∥Rad∥_{L_{2}({−1,1}^{n},X)→L_{2}({−1,1}^{n},X)}.

X is said to be K-convex if K(X) < ∞. More generally, for p ≥ 1 we define

K_{p}(X) = sup_{n∈}∥Rad∥_{L_{p}({−1,1}^{n},X)→L_{p}({−1,1}^{n},X)}.

It is a well known consequence of Kahane’s inequality and duality that for every p > 1,

K_{p}(X) ≤ O( \frac{p}{\sqrt{p − 1}} ) · K(X).

The following deep theorem was proved by Pisier in [56]:

Theorem 2.1 (Pisier’s K-convexity theorem [56]). Let X be a Banach space. Then

q_{X} > 1 ⟺ K(X) < ∞.

Next, we recall some facts concerning Fourier analysis on the group _{m}^{n}. Given k = (k_{1}, …, k_{n}) ∈ _{m}^{n} we consider the Walsh function W_{k} : _{m}^{n} → :

W_{k}(x) = exp(\frac{2πi}{m} ∑_{j=1}^{m} k_{j}x_{j}).

Then, for any Banach space X, any f : Z_{m}^{n} → X can be decomposed as follows:

f (x) = ∑_{k∈ _{m}^{n}} W_{k}(x)f̂(k),

where

f̂(k) = ∫_{_{m}^{n}} f (y)\overline{W_{k}(y)}dμ(y) ∈ X.

If X is a Hilbert space then Parseval’s identity becomes:

∫_{Z_{m}^{n}}∥f (x)∥_{X}^{2}dμ(x) = ∑_{k∈ _{m}^{n}} ∥f̂(k)∥_{X}^{2}.

2.1 Definitions and basic facts related to metric cotype

Definition 2.2. Given 1 ≤ p ≤ q, an integer n and an even integer m, let Γ_{q}^{(p)}(M; n, m) be the infimum over all Γ > 0 such that for every f : _{m}^{n} → M,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x) ≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} d_{M} (f (x + ε) , f (x))^{p} dμ(x)dσ(ε). (11)

If p = q then we write Γ_{q}^{(p)}(M; n, m) = Γ_{q}(M; n, m). With this notation,

Γ_{q}^{(p)}(M) = sup_{n∈}( inf_{m∈2} Γ_{q}^{(p)}(M; n, m)).

We also denote by m_{q}^{(p)}(M; n, Γ) the smallest even integer m for which (11) holds. As usual, when p = q we write m_{q}^{(p)}(M; n, Γ) = m_{q}(M; n, Γ).

The following lemma is a direct consequence of our definitions. It shows that for most “interesting” metric spaces M, m_{q}(M; n, Γ) must be large.

Lemma 2.3. For every integer n, every Γ > 0, and every p, q > 0,

m_{q}^{(p)}(EQ; n, Γ) ≥ \frac{n^{1/q}}{Γ},

where EQ denotes the trivial metric on . i.e. d_{EQ}(ℓ, k) = 1_{ℓ k}. Thus, for every infinite dimensional Banach space X,

m_{q}^{(p)}(X; n, Γ) ≥ \frac{n^{1/q}}{Γ}.

Lemma 2.4. For every two integer n, k, and every even integer m,

Γ_{q}^{(p)}(M; n, km) ≤ Γ_{q}^{(p)}(M; n, m).

Proof. Fix f : _{km}^{n}→ M. For every y ∈ _{k}^{n} define f_{y} : _{m}^{n} → M by

f_{y}(x) = f (kx + y).

Fix Γ > Γ_{q}^{(p)}(M; n, m). Applying the definition of Γ_{q}^{(p)}(M; n, m) to f_{y}, we get that

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (kx + \frac{km}{2}e_{j} + y) , f (kx + y))^{p} dμ_{_{m}^{n}}(x)

≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} d_{M} (f (kx + kε + y), f (kx + y))^{p} dμ_{_{m}^{n}}(x)dσ(ε).

Integrating this inequality with respect to y ∈ _{k}^{n} we see that

∑_{j=1}^{n} ∫_{_{km}^{n}} d_{M} (f (z + \frac{km}{2}e_{j}) , f (z))^{p} dμ_{_{km}^{n}}(z)

= ∑_{j=1}^{n} ∫_{_{k}^{n}} ∫_{_{m}^{n}} d_{M} (f (kx + \frac{km}{2}e_{j} + y) , f (kx + y))^{p} dμ_{_{m}^{n}}(x)dμ_{_{k}^{n}}(y)
≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{k}^{n}} ∫_{_{m}^{n}} d_{M} (f (kx + kε + y), f (kx + y))^{p} dμ_{_{m}^{n}}(x)dμ_{_{k}^{n}}(y)dσ(ε)
= Γ^{p}m^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{km}^{n}} d_{M} (f (z + kε), f (z))^{p} dμ_{_{km}^{n}}(z)dσ(ε)
≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{km}^{n}} k^{p−1} ∑_{s=1}^{k} d_{M} (f (z + sε) , f (z + (s − 1)ε)) ^{p} dμ_{_{km}^{n}}(z)dσ(ε)
= Γ^{p}(km)^{p}n^{1− \frac{p}{q}} ∫_{\{−1,0,1\}^{n}}∫_{_{km}^{n}} d_{M} (f (z + ε) , f (z))^{p} dμ_{_{km}^{n}}(z)dσ(ε)

Lemma 2.5. Let k, n be integers such that k ≤ n, and let m be an even integer. Then

Γ_{q}^{(p)}(M; k, m) ≤ (\frac{n}{k})^{1− \frac{p}{q}} · Γ_{q}^{(p)}(M; n, m).

Proof. Given and f : _{m}^{k} → M, we define an M-valued function on _{m}^{n} _{m}^{k} × _{m}^{n−k} by g(x, y) = f (x). Applying the definition Γ_{q}^{(p)}(M; n, m) to g yields the required inequality.

We end this section by recording some general inequalities which will be used in the ensuing arguments. In what follows (M, d_{M}) is an arbitrary metric space. Lemma 2.6. For every f : _{m}^{n} → M,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x) ≤ 3 · 2^{p−1}n · ∫_{{−1,0,1}^{n}}∫_{_{m}^{n}} d_{M} (f (x + ε), f (x)) ^{p} dμ(x)dσ(ε).

Proof. For every x ∈ _{m}^{n} and ε ∈ {−1, 0, 1}^{n},

d_{M}(f (x + e_{j}), f (x))^{p} ≤ 2^{p−1}d_{M}(f (x + e_{j}), f (x + ε))^{p} + 2^{p−1}d_{M}(f (x + ε), f (x))^{p}.

Thus

\frac{2}{3} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x) = σ(\{ε ∈ \{−1, 0, 1\}^{n} : ε_{j} −1\}) · ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x)

≤ 2^{p−1} ∫_{{ε∈{−1,0,1}^{n}: ε_{j} −1}}∫_{_{m}^{n}} (d_{M} (f (x + e_{j}), f (x + ε)) ^{p} + d_{M}(f (x + ε), f (x))^{p}) dμ(x)dσ(ε)
= 2^{p−1} ∫_{{ε∈{−1,0,1}^{n}: ε_{j} 1}}∫_{_{m}^{n}} d_{M}(f (y + ε), f (y))^{p}dμ(y)dσ(ε) +
2^{p−1} ∫_{{ε∈{−1,0,1}^{n}: ε_{j} −1}}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{p}dμ(x)dσ(ε)
≤ 2^{p} ∫_{{−1,0,1}^{n}}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{p}dμ(x)dσ(ε).

Summing over j = 1, …, n yields the required result. Lemma 2.7. Let (M, d_{M}) be a metric space. Assume that for an integer n and an even integer m,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x)

≤ C^{p}m^{p}n^{1− \frac{p}{q}} ( _{ε}∫_{_{m}^{n}} d_{M} (f (x + ε), f (x)) ^{p} dμ(x) + \frac{1}{n} ∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x)).

Then

Γ_{q}^{(p)}(M; n, m) ≤ 5C.

Proof. Fix f : _{m}^{n} → M and ∅ A ⊆ {1, …, n}. Our assumption implies that

∑_{j∈A} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x)

≤ C^{p}m^{p}n^{1− \frac{p}{q}} ( _{ε}∫_{_{m}^{n}} d_{M}(f (x + ∑_{j∈A} ε_{j}e_{j}), f (x))^{p}dμ(x) + \frac{1}{|A|}∑_{j∈A} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x)).

Multiplying this inequality by \frac{2^{|A|}}{3^{n}}, and summing over all ∅ A ⊆ \{1, …, n\}, we see that

\frac{2}{3} ∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x) = ∑_{∅ A⊆\{1,...,n\}} \frac{2^{|A|}}{3^{n}} ∑_{j∈A} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x)

≤ C^{p}m^{p}n^{1− \frac{p}{q}} ( ∑_{∅ A⊆\{1,...,n\}} \frac{2^{|A|}}{3^{n}} _{ε}∫_{_{m}^{n}} d_{M}(f (x + ∑_{j∈A} ε_{j}e_{j}), f (x))^{p}dμ(x) +
∑_{∅ A⊆\{1,...,n\}} \frac{2^{|A|}}{|A|3^{n}}∑_{j∈A} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x))  (12)
≤ C^{p}m^{p}n^{1− \frac{p}{q}} (∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} d_{M} (f (x + δ) , f (x))^{p} dμ(x)dσ(δ) + \frac{1}{n} ∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + e_{j}), f (x))^{p} dμ(x))
≤ C^{p}m^{p}n^{1− \frac{p}{q}} (3^{p} + 1) ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} d_{M} (f (x + δ) , f (x))^{p} dμ(x)dσ(δ),  (13)

where we used the fact that in (12), the coefficient of d_{M} (f (x + e_{j}), f (x))^{p} equals ∑ _{k=1}^{n} \frac{2^{k}}{k3^{n}}\binom{n−1}{k−1} ≤ \frac{1}{n}, and in (13) we used Lemma 2.6.

3 Warmup: the case of Hilbert space

The fact that Hilbert spaces have metric cotype 2 is particularly simple to prove. This is contained in the following proposition.

Proposition 3.1. Let H be a Hilbert space. Then for every integer n, and every integer m ≥ \frac{2}{3}π \sqrt{n}which is divisible by 4,

Γ_{2}(H; n, m) ≤ \frac{\sqrt{6}}{π}.

Proof. Fix f : Z_{m}^{n} → H and decompose it into Fourier coefficients:

f (x) = ∑_{k∈ _{m}^{n}} W_{k}(x)f̂(k),

For every j = 1, 2, …, n we have that

f (x + \frac{m}{2}e_{j}) − f (x) = ∑_{k∈ _{m}^{n}} W_{k}(x) (e^{πik_{j}} − 1) f̂(k).

Thus

∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{H}^{2} dμ(x) = ∑_{k∈ _{m}^{n}}(∑_{j=1}^{n} |e^{πik_{j}} − 1|^{2}) ∥f̂(k)∥_{H}^{2}

= 4 ∑_{k∈ _{m}^{n}} |{j : k_{j} ≡ 1 mod 2}| · ∥f̂(k)∥_{H}^{2} .

Additionally, for every ε ∈ {−1, 0, 1}^{n},

f (x + ε) − f (x) = ∑_{k∈ _{m}^{n}} W_{k}(x)(W_{k}(ε) − 1)f̂(k).

Thus

∫_{{−1,0,1}^{n}}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{H}^{2}dμ(x)dσ(ε) = ∑_{k∈ _{m}^{n}} (∫_{{−1,0,1}^{n}}|W_{k}(ε) − 1|^{2} dσ(ε)) ∥f̂(k)∥_{H}^{2} .

Observe that

∫_{\{−1,0,1\}^{n}}|W_{k}(ε) − 1|^{2} dσ(ε) = ∫_{\{−1,0,1\}^{n}}|exp(\frac{2πi}{m} ∑_{j=1}^{m} k_{j}ε_{j})−1|^{2}dσ(ε)

= 2 − 2 ∫_{\{−1,0,1\}^{n}}cos(\frac{2π}{m} ∑_{j=1}^{m} k_{j}ε_{j})dσ(ε)

= 2 − 2 ∫_{\{−1,0,1\}^{n}}exp(\frac{2πi}{m} ∑_{j=1}^{m} k_{j}ε_{j})dσ(ε)

= 2 − 2 ∏_{j=1}^{n} ∫_{\{−1,0,1\}^{n}}exp(\frac{2πi}{m}k_{j}ε_{j})dσ(ε)

= 2 − 2 ∏_{j=1}^{n} \frac{1 + 2 cos(\frac{2π}{m}k_{j})}{3}

≥ 2 − 2 ∏_{j: k_{j}≡1 mod 2} \frac{1 + 2 |cos(\frac{2π}{m}k_{j})|}{3}.

Note that if m is divisible by 4 and ℓ ∈ {0, …, m − 1} is an odd integer, then

|cos(\frac{2πℓ}{m})| ≤ |cos(\frac{2π}{m})| ≤ 1 − \frac{π^{2}}{m^{2}}.

Hence

∫_{\{−1,0,1\}^{n}}|W_{k}(ε) − 1|^{2} dσ(ε) ≥ 2(1 − (1 − \frac{2π^{2}}{3m^{2}})^{|\{j: k_{j}≡1 mod 2\}|})
≥ 2(1 − e^{− \frac{2|\{j: k_{j} ≡1 mod 2\}|π^{2}}{3m^{2}}})
≥ |\{j : k_{j} ≡ 1 mod 2\}| · \frac{2π^{2}}{3m^{2}},

provided that m ≥ \frac{2}{3}π \sqrt{n}.

4 K-convex spaces

In this section we prove the “hard direction” of Theorem 1.2 and Theorem 1.4 when X is a K-convex Banach space, namely we show that in this case Rademacher cotype q implies metric cotype q. There are two reasons why we single out this case before passing to the proofs of these theorems in full generality. First of all, the proof for K-convex spaces is different and simpler than the general case. More importantly, in the case of K-convex spaces we are able to obtain optimal bounds on the value of m in Definition 1.1 and Definition 1.3. Namely, we show that if X is a K-convex Banach space of cotype q, then for every 1 ≤ p ≤ q, m_{q}^{(p)}(X; n, Γ) = O(n^{1/q}), for some Γ = Γ(X). This is best possible due to Lemma 2.3. In the case of general Banach spaces we obtain worse bounds, and this is why we have the restriction that X is K-convex in Theorem 1.9 and Theorem 1.11. This issue is taken up again in Section 8.

Theorem 4.1. Let X be a K-convex Banach space with cotype q. Then for every integer n and every integer m which is divisible by 4,

m ≥ \frac{2n^{1/q}}{C_{q}^{(p)}(X)K_{p}(X)} ⟹ Γ_{q}^{(p)}(X; n, m) ≤ 15C_{q}^{(p)}(X)K_{p}(X).

Proof. For f : _{m}^{n} → X we define the following operators:

˜∂_{j}f (x) = f (x + e_{j}) − f (x − e_{j}),

E_{j}f (x) = _{ε}f (x + ∑_{ℓ j} ε_{ℓ}e_{ℓ}),

and for ε ∈ {−1, 0, 1}^{n},

∂_{ε}f (x) = f (x + ε) − f (x).

These operators operate diagonally on the Walsh basis {W_{k}}_{k∈ _{m}^{n}} as follows:

˜∂_{j}W_{k} = (W_{k}(e_{j}) − W_{k}(−e_{j}))W_{k} = 2 sin(\frac{2πik_{j}}{m}) · W_{k}.  (14)

E_{j}W_{k} = ( _{ε} ∏_{ℓ j} e^{\frac{2πiε_{ℓ}k_{ℓ}}{m}})W_{k} = (∏_{ℓ j} cos(\frac{2πk_{ℓ}}{m}))W_{k},  (15)

and for ε ∈ {−1, 1}^{n},

∂_{ε}W_{k} = (W(ε) − 1)W_{k}
= (∏_{j=1}^{n} e^{\frac{2πiε_{j} k_{j}}{m}} − 1)W_{k}

= (∏_{j=1}^{n} (cos(\frac{2πiε_{j}k_{j}}{m}) + i sin(\frac{2πiε_{j}k_{j}}{m})) − 1)W_{k}

= (∏_{j=1}^{n} (cos(\frac{2πik_{j}}{m}) + iε_{j} sin(\frac{2πik_{j}}{m})) − 1)W_{k}.  (16)

The last step was a crucial observation, using the fact that ε_{j} ∈ {−1, 1}. Thinking of ∂_{ε}W_{k} as a function of ε ∈ {−1, 1}^{n}, equations (14), (15) and (16) imply that

Rad(∂_{ε}W_{k}) = i(∑_{j=1}^{n} ε_{j} sin(\frac{2πik_{j}}{m}) · ∏_{ℓ j} cos(\frac{2πk_{ℓ}}{m}))W_{k} = \frac{i}{2}(∑_{j=1}^{n} ε_{j}˜∂_{j}E_{j})W_{k}.

Thus for every x ∈ _{m}^{n} and f : _{m}^{n} → X,

Rad(∂_{ε}f (x)) = \frac{i}{2}(∑_{j=1}^{n} ε_{j}˜∂_{j}E_{j})f (x).

It follows that

∫_{_{m}^{n}} _{ε}∥∑_{j=1}^{n} ε_{j}[E_{j}f (x + e_{j}) − E_{j}f (x − e_{j})]∥_{X}^{p}dμ(x) = ∫_{_{m}^{n}} _{ε}∥∑_{j=1}^{n} ε_{j}˜∂_{j}E_{j}f (x)∥_{X}^{p}dμ(x)

= ∫_{_{m}^{n}} _{ε}∥Rad(∂_{ε}f (x))∥_{X}^{p}dμ(x)
≤ K_{p}(X)^{p} ∫_{_{m}^{n}} _{ε}∥∂_{ε}f (x)∥_{X}^{p}dμ(x). (17)

By (17) and the definition of C_{q}^{(p)}(X), for every C > C_{q}^{(p)}(X) we have that

[K_{p}(X)C]^{p} _{ε}∫_{G}∥f (x + ε) − f (x)∥_{X}^{p}dμ(x)
≥ C^{p} · _{ε}∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j}[E_{j}f (x + e_{j}) − E_{j}f (x − e_{j})]∥_{X}^{p}dμ(x)

≥ ∫_{_{m}^{n}}(∑_{j=1}^{n} ∥E_{j}f (x + e_{j}) − E_{j}f (x − e_{j})∥ _{X}^{q})^{p/q}dμ(x)

≥ \frac{1}{n^{1−p/q}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥E_{j}f (x + e_{j}) − E_{j}f (x − e_{j})∥ _{X}^{p}dμ(x).  (18)

Now, for j ∈ {1, …, n},

∫_{_{m}^{n}} ∥E_{j}f (x + \frac{m}{2}e_{j}) − E_{j}f (x)∥ _{X}^{p}dμ(x) ≤ (\frac{m}{4})^{p−1} ∑_{s=1}^{m/4}∫_{_{m}^{n}} ∥E_{j}f (x + 2se_{j}) − E_{j}f (x + 2(s − 1)e_{j}) ∥ _{X}^{p}dμ(x)
= (\frac{m}{4})^{p} ∫_{_{m}^{n}} ∥E_{j}f (x + e_{j}) − E_{j}f (x − e_{j})∥ _{X}^{p}dμ(x).  (19)

Plugging (19) into (18) we get

(\frac{m}{4})^{p} n^{1− \frac{p}{q}} [K_{p}(X)C]^{p} _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x) ≥ ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥E_{j}f (x + \frac{m}{2}e_{j}) − E_{j}f (x)∥ _{X}^{p}dμ(x)

≥ \frac{1}{3^{p−1}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2 ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥E_{j}f (x)− f (x)∥ _{X}^{p}dμ(x)

= \frac{1}{3^{p−1}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2 ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥ _{ε}(f (x + ∑_{ℓ j} ε_{ℓ}e_{ℓ}) − f (x))∥_{X}^{p}dμ(x)

≥ \frac{1}{3^{p−1}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2 ∑_{j=1}^{n} _{ε}∫_{_{m}^{n}} ∥f (x + ∑_{ℓ j} ε_{ℓ}e_{ℓ}) − f (x)∥_{X}^{p}dμ(x)

≥ \frac{1}{3^{p−1}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2^{p}n _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥ _{X}^{p}dμ(x) −

2^{p} ∑_{j=1}^{n} _{ε}∫_{_{m}^{n}} ∥f (x + ε_{j}e_{j}) − f (x)∥ _{X}^{p}dμ(x).

Thus, the required result follows from Lemma 2.7.

The above argument actually gives the following generalization of Theorem 4.1, which holds for products of arbitrary compact Abelian groups.

Theorem 4.2. Let G_{1}, …, G_{n} be compact Abelian groups, (g_{1}, …, g_{n}) ∈ G_{1} × ⋯× G_{n}, and let X be a K-convex Banach space. Then for every integer k and every f : G_{1} × ⋯ × G_{n} → X,

∑_{j=1}^{n} ∫_{G_{1}×··· ×G_{n}} ∥f (x + 2kg_{j}e_{j}) − f (x)∥_{X}^{p}d(μ_{G_{1}} ⊗ ⋯ ⊗ μ_{G_{n}})(x)

≤ C^{p} ∫_{{−1,0,1}^{n}}∫_{G_{1}×··· ×G_{n}} ∥f (x + ∑_{j=1}^{n} ε_{j}g_{j}e_{j}) − f (x)∥_{X}^{p}d(μ_{G_{1}} ⊗ ⋯ ⊗ μ_{G_{n}})(x)dσ(ε),

where

C ≤ 5 max\{C_{q}^{(p)}(X)K_{p}(X)kn^{\frac{1}{p}− \frac{1}{q}} , n^{\frac{1}{p}}\}.

Here μ_{G} denotes the normalized Haar measure on a compact Abelian group G. We refer the interested reader to the book [63], which contains the necessary background required to generalize the proof of Theorem 4.1 to this setting.

5 The equivalence of Rademacher cotype and metric cotype

We start by establishing the easy direction in Theorem 1.2 and Theorem 1.4, i.e. that metric cotype implies Rademacher cotype.

5.1 Metric cotype implies Rademacher cotype

Let X be a Banach space and assume that Γ_{q}^{(p)}(X) < ∞ for some 1 ≤ p ≤ q. Fix Γ > Γ_{q}^{(p)}(X), v_{1}, …, v_{n} ∈ X, and let m be an even integer. Define f : _{m}^{n} → X by

f (x_{1}, …, x_{n}) = ∑_{j=1}^{n} e^{\frac{2πix_{j}}{m}} v_{j}.

Then

∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) = 2^{p} ∑_{j=1}^{n} ∥v_{j}∥_{X}^{p},  (20)

and

∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥f (x + δ) − f (x)∥ _{X}^{p}dμ(x)dσ(ε) = ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥∑_{j=1}^{n} e^{\frac{2πix_{j}}{m}} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ). (21)

We recall the contraction principle (see [36]), which states that for every a_{1}, …, a_{n} ∈ ,

ε∥∑_{j=1}^{n} ε_{j}a_{j}v_{j} ∥_{X}^{p} ≤ (max_{1≤j≤n} |a_{j}|)^{p} · _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p}.

Observe that for every ε = (ε_{1}, …, ε_{n}) ∈ {−1, 1}^{n},

∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥∑_{j=1}^{n} e^{\frac{2πix_{j}}{m}} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ)

= ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥∑_{j=1}^{n} e^{^{\frac{2πi}{m}}(x_{j}+ \frac{m(1−ε_{j})}{4})} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ)

= ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j}e^{\frac{2πix_{j}}{m}} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ).

Taking expectation with respect to ε, and using the contraction principle, we see that

∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥∑_{j=1}^{n} e^{\frac{2πix_{j}}{m}} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ)

= ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} _{ε}∥∑_{j=1}^{n} ε_{j}e^{\frac{2πix_{j}}{m}} (e^{\frac{2πiδ_{j}}{m}} − 1) v_{j} ∥_{X}^{p}dμ(x)dσ(δ)

≤ ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} 2^{p} (max_{1≤j≤n} |e^{\frac{2πiδ_{j}}{m}} − 1|)^{p} _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p}dμ(x)dσ(δ) ≤ (\frac{4π}{m})^{p} _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p}, (22)

where in the last inequality above we used the fact that for θ ∈ [0, π], |e^{iθ} − 1| ≤ θ.

Combining (7), (20), (21), and (22), we get that

2^{p} ∑_{j=1}^{n} ∥v_{j}∥_{X}^{p} ≤ Γ^{p}m^{p} (\frac{4π}{m})^{p} n^{1− \frac{p}{q}} _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p} = (4πΓ)^{p} n^{1− \frac{p}{q}} _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p}.

If p = q we see that C_{q}(X) ≤ 2πΓ_{q}(X). If p < q then when ∥v_{1}∥_{X} = ⋯= ∥v_{n}∥_{X} = 1 we get that

( _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{q})^{1/q} ≥ ( _{ε}∥∑_{j=1}^{n} ε_{j}v_{j} ∥_{X}^{p})^{1/p} = Ω (\frac{n^{1/q}}{Γ}).

This means that X has “equal norm cotype q”, implying that X has cotype q′for every q′ > q (see [68, 34, 67] for quantitative versions of this statement). When q = 2 this implies that X has cotype 2 (see [68] and the references therein).

5.2 Proof of Theorem 1.2 and Theorem 1.4

The proof of Theorem 1.2 and Theorem 1.4 is based on several lemmas. Fix an odd integer k ∈ , with k < \frac{m}{2}, and assume that 1 ≤ p ≤ q. Given j ∈ \{1, …, n\} define S(j, k) ⊆ _{m}^{n} by

S(j, k) {y ∈ [−k, k]^{n} ⊆ _{m}^{n}: y_{j} ≡ 0 mod 2 and ∀ ℓ j, y_{ℓ} ≡ 1 mod 2} .

For f : _{m}^{n} → X we define

E_{j}^{(k)}f (x) = (f ∗ \frac{1_{S(j,k)}}{μ(S(j, k))} ) (x) = \frac{1}{μ(S(j, k))} ∫_{S(j,k)} f (x + y)dμ(y).  (23)

Lemma 5.1. For every p ≥ 1, every j ∈ {1, …, n}, and every f : _{m}^{n} → X,

∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x) − f (x)∥ _{X}^{p}dμ(x) ≤ 2^{p}k^{p} _{ε}∫_{_{m}^{n}} ∥f (x+ε)−f (x)∥_{X}^{p}dμ(x)+2^{p−1} ∫_{_{m}^{n}} ∥f (x+e_{j})−f (x)∥_{X}^{p}dμ(x).

Proof. By convexity, for every x ∈ _{m}^{n},

∥E_{j}^{(k)}f (x) − f (x)∥ _{X}^{p} = ∥\frac{1}{μ(S(j, k))} ∫_{S(j,k)}[f (x + y) − f (x)]dμ(y)∥ _{X}^{p}
≤ \frac{1}{μ(S(j, k))} ∫_{S(j,k)} ∥f (x) − f (x + y)∥_{X}^{p}dμ(y).  (24)

Let x ∈ [0, k]^{n} be such that for all j ∈ {1, …, n}, x_{j} is a positive odd integer. Observe that there exists a geodesic γ : {0, 1, …, ∥x∥_{∞} } → _{m}^{n} such that γ(0) = 0, γ(∥x∥_{∞} ) = x and for every t ∈ {1, …, ∥x∥_{∞} }, γ(t) − γ(t − 1) ∈ {−1, 1}^{n}. Indeed, we define γ(t) inductively as follows: γ(0) = 0, γ(1) = (1, 1, …, 1), and if t ≥ 2 is odd then

γ(t) = γ(t − 1) + ∑_{s=1}^{n} e_{s} and γ(t + 1) = γ(t − 1) + 2 ∑_{\begin{matrix}s∈\{1,...,n\} \\ γ(t−1)_{s}<x_{s} \end{matrix}}e_{s}.

Since all the coordinates of x are odd, γ(∥x∥_{∞} ) = x. In what follows we fix an arbitrary geodesic γ_{x} : {0, 1, …, ∥x∥_{∞} } → _{m}^{n} as above. For x ∈ ( _{m} \ {0})^{n} we denote |x| = (|x_{1}|, …, |x_{n}|) and sign(x) = (sign(x_{1}), …, sign(x_{n})). If x ∈ [−k, k]^{n} is such that all of its coordinates are odd, then we define γ_{x} = sign(x) · γ_{|x|}(where the multiplication is coordinate-wise).

If y ∈ S(j, k) then all the coordinates of y ± e_{j} are odd. We can thus define two geodesic paths

γ_{x,y}^{+1} = x + e_{j} + γ_{y−e_{j}} and γ_{x,y}^{−1} = x − e_{j} + γ_{y+e_{j}},

where the addition is point-wise.

For z ∈ _{m}^{n} and ε ∈ {−1, 1}^{n} define

F^{+1}(z, ε) = {(x, y) ∈ _{m}^{n}× S(j, k) : ∃t ∈ {1, …, ∥y − e_{j}∥_{∞} }, γ_{x,y}^{+1}(t − 1) = z, γ_{x,y}^{+1}(t) = z + ε},

and

F^{−1}(z, ε) = {(x, y) ∈ _{m}^{n}× S(j, k) : ∃t ∈ {1, …, ∥y + e_{j}∥_{∞} }, γ_{x,y}^{−1}(t − 1) = z, γ_{x,y}^{−1}(t) = z + ε}.

Claim 5.2. For every z, w ∈ _{m}^{n} and ε, δ ∈ {−1, 1}^{n},

|F^{+1}(z, ε)| + |F^{−1}(z, ε)| = |F^{+1}(w, δ)| + |F^{−1}(w, δ)|.

Proof. Define ψ : _{m}^{n}× S(j, k) → _{m}^{n}× S(j, k) by

ψ(x, y) = (w − εδz + εδx, εδy).

We claim that ψ is a bijection between F^{+1}(z, ε) and F^{ε_{j}δ_{j}}(w, δ), and also ψ is a bijection between F^{−1}(z, ε) and F^{−ε_{j}δ_{j}} (w, δ). Indeed, if (x, y) ∈ F^{+1}(z, ε) then there exists t ∈ {1, …, ∥y − e_{j}∥_{∞} } such that γ_{x,y}^{+1}(t − 1) = z and γ_{x,y}^{+1}(t) = z + ε. The path w − εδz + εδγ_{x,y}^{+1} equals the path γ_{ψ(x,y)}^{ε_{j}δ_{j}}, which by definition goes through w at time t − 1 and w + δ at time t. Since these transformations are clearly invertible, we obtain the required result for F^{+1}(z, ε). The proof for F^{−1}(z, ε) is analogous.

Claim 5.3. Denote N = |F^{+1}(z, ε)| + |F^{−1}(z, ε)|, which is independent of z ∈ _{m}^{n} and ε ∈ {−1, 1}^{n}, by Claim 5.2. Then

N ≤ \frac{k · |S(j, k)|}{2^{n−1}}.

Proof. We have that

N · m^{n} · 2^{n} = ∑_{(z,ε)∈ _{m}^{n}×{−1,1}^{n}}(|F^{+1}(z, ε)| + |F^{−1}(z, ε)|)

= ∑_{(z,ε)∈ _{m}^{n}×{−1,1}^{n}}( ∑_{(x,y)∈ _{m}^{n}×S(j,k)} ∑_{t=1}^{∥y−e_{j}∥_{∞}} 1_{{γ_{x,y}^{+1}(t−1)=z ∧ γ_{x,y}^{+1}(t)=z+ε}}) +

∑_{(z,ε)∈ _{m}^{n}×{−1,1}^{n}}( ∑_{(x,y)∈ _{m}^{n}×S(j,k)} ∑_{t=1}^{∥y+e_{j}∥_{∞}} 1_{{γ_{x,y}^{−1}(t−1)=z ∧ γ_{x,y}^{−1}(t)=z+ε}})

= ∑_{(x,y)∈ _{m}^{n}×S(j,k)} ∥y − e_{j}∥_{∞} + ∑_{(x,y)∈ _{m}^{n}×S(j,k)} ∥y + e_{j}∥_{∞}
≤ 2k · m^{n} · |S(j, k)|.

We now conclude the proof of Lemma 5.1. Observe that for x ∈ _{m}^{n} and y ∈ S(j, k),

\frac{∥f (x) − f (x + y)∥_{X}^{p}}{2^{p−1}} ≤ ∥f (x) − f (x + e_{j})∥_{X}^{p} + ∥y − e_{j}∥_{∞}^{p−1} ∑_{t=1}^{∥y−e_{j}∥_{∞}} ∥γ_{x,y}^{+1}(t) − γ_{x,y}^{+1}(t − 1)∥_{X}^{p}

≤ ∥f (x) − f (x + e_{j})∥_{X}^{p} + k^{p−1} ∑_{t=1}^{∥y−e_{j}∥_{∞}} ∥γ_{x,y}^{+1}(t) − γ_{x,y}^{+1}(t − 1)∥_{X}^{p},  (25)

and

\frac{∥f (x) − f (x + y)∥_{X}^{p}}{2^{p−1}} ≤ ∥f (x) − f (x − e_{j})∥_{X}^{p} + ∥y + e_{j}∥_{∞}^{p−1} ∑_{t=1}^{∥y+e_{j}∥_{∞}} ∥γ_{x,y}^{−1}(t) − γ_{x,y}^{−1}(t − 1)∥_{X}^{p}

≤ ∥f (x) − f (x − e_{j})∥_{X}^{p} + k^{p−1} ∑_{t=1}^{∥y+e_{j}∥_{∞}} ∥γ_{x,y}^{−1}(t) − γ_{x,y}^{−1}(t − 1)∥_{X}^{p}.  (26)

Averaging inequalities (25) and (26), and integrating, we get that

\frac{1}{μ(S(j, k))} ∫_{_{m}^{n}} ∫_{S(j,k)} ∥f (x) − f (x + y)∥_{X}^{p}dμ(y)dμ(x)

≤ 2^{p−1} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x) + (2k)^{p−1} \frac{N · 2^{n}}{|S(j, k)|} _{ε}∫_{_{m}^{n}} ∥f (z + ε) − f (z)∥_{X}^{p}dμ(z)  (27)
≤ 2^{p−1} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x) + (2k)^{p} _{ε}∫_{_{m}^{n}} ∥f (z + ε) − f (z)∥_{X}^{p}dμ(z),  (28)

where in (27) we used Claim 5.2 and in (28) we used Claim 5.3. By (24), this completes the proof of Lemma 5.1.

Lemma 5.4 below is the heart of our proof. It contains the cancellation of terms which is key to the validity of Theorem 1.2 and Theorem 1.4.

Lemma 5.4. For every f : _{m}^{n} → X, every integer n, every even integer m, every ε ∈ {−1, 1}^{n}, every odd integer k < m/2, and every p ≥ 1,

∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] ∥_{X}^{p}dμ(x)

≤ 3^{p−1} ∫_{_{m}^{n}} ∥f (x + ε) − f (x − ε)∥_{X}^{p}dμ(x) + \frac{·24^{p}n^{2p−1}}{k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x).

We postpone the proof of Lemma 5.4 to Section 5.3, and proceed to prove Theorem 1.2 and Theorem 1.4 assuming its validity.

Proof of Theorem 1.2 and Theorem 1.4. Taking expectations with respect to ε ∈ {−1, 1}^{n} in Lemma 5.4 we get that

ε∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] ∥_{X}^{p}dμ(x)

≤ 3^{p−1} _{ε}∫_{_{m}^{n}} 2^{p−1} (∥f (x + ε) − f (x)∥_{X}^{p} + ∥f (x) − f (x − ε)∥_{X}^{p}) dμ(x) +

\frac{24^{p}n^{2p−1}}{k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x)

≤ \frac{6^{p}}{3} _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x) + \frac{24^{p}n^{2p−1}}{k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x).  (29)

Fix x ∈ _{m}^{n} and let m be an integer which is divisible by 4 such that m ≥ 6n^{2+1/q}. Fixing C > C_{q}^{(p)}(X), and applying the definition of C_{q}^{(p)}(X) to the vectors {E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})} _{j=1}^{n}, we get

ε∥∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] ∥_{X}^{p} ≥ \frac{1}{C^{p} · n^{1−p/q}}∑_{j=1}^{n} ∥E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})∥ _{X}^{p}. (30)

Now, for every j ∈ {1, …, n},

∑_{s=1}^{m/4} ∥E_{j}^{(k)}f (x + 2se_{j}) − E_{j}^{(k)}f (x + 2(s − 1)e_{j}) ∥ _{X}^{p} ≥ (\frac{4}{m})^{p−1} ∥E_{j}^{(k)}f (x + \frac{m}{2}e_{j}) − E_{j}^{(k)}f (x)∥ _{X}^{p}.  (31)

Averaging (31) over x ∈ _{m}^{n} we get that

∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})∥ _{X}^{p}dμ(x) ≥ (\frac{4}{m})^{p} ∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x + \frac{m}{2}e_{j}) − E_{j}^{(k)}f (x)∥ _{X}^{p}dμ(x).  (32)

Combining (30) and (32) we get the inequality

ε∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] ∥_{X}^{p}dμ(x)

≥ \frac{1}{C^{p} · n^{1−p/q}}· (\frac{4}{m})^{p} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x + \frac{m}{2}e_{j}) − E_{j}^{(k)}f (x)∥ _{X}^{p}dμ(x). (33)

Now, for every j ∈ {1, …, n},

∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x + \frac{m}{2}e_{j}) − E_{j}^{(k)}f (x)∥ _{X}^{p}dμ(x) ≥ \frac{1}{3^{p−1}} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) −

∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x + \frac{m}{2}e_{j}) − f (x + \frac{m}{2}e_{j})∥ _{X}^{p}dμ(x) − ∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x)− f (x)∥ _{X}^{p}dμ(x)

= \frac{1}{3^{p−1}} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2 ∫_{_{m}^{n}} ∥E_{j}^{(k)}f (x)− f (x)∥ _{X}^{p}dμ(x)
≥ \frac{1}{3^{p−1}} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x) − 2^{p+1}k^{p} _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x) −
2^{p} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x),  (34)

where we used Lemma 5.1.

Combining (34) with (33), we see that

∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}e_{j}) − f (x)∥ _{X}^{p}dμ(x)

≤ \frac{(3Cm)^{p}n^{1− \frac{p}{q}}}{3 · 4^{p}} _{ε}∫_{_{m}^{n}} ∥∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] ∥_{X}^{p}dμ(x) +

6^{p}k^{p}n _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x) + 6^{p} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x)

≤ (\frac{(18Cm)^{p}n^{1− \frac{p}{q}}}{4^{p}} + 6^{p}k^{p}n) _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x) +

(\frac{(3Cm)^{p}n^{1− \frac{p}{q}}}{4^{p}} · \frac{24^{p}n^{2p−1}}{k^{p}} + 6^{p}) ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x)  (35)

≤ (18Cm)^{p}n^{1− \frac{p}{q}} ( _{ε}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{X}^{p}dμ(x)dσ(ε) + \frac{1}{n} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥_{X}^{p}dμ(x)), (36)

where in (35) we used (29), and (36) holds true when we choose 4n^{2} ≤ k ≤ \frac{3m}{4n^{1/q}} (which is possible if we assume that m ≥ 6n^{2+1/q}). By Lemma 2.7, this completes the proof of Theorem 1.4.

5.3 Proof of Lemma 5.4

Fix ε ∈ {−1, 1}^{n}, and x ∈ _{m}^{n}. Consider the following two sums:

A_{f} (x, ε) = ∑_{j=1}^{n} ε_{j} [E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}f (x − e_{j})] = \frac{1}{k(k + 1)^{n−1}} ∑_{y∈ _{m}^{n}} a_{y}(x, ε)f (y),  (37)

and

B_{f} (x, ε) = \frac{1}{k(k + 1)^{n−1}} ∑_{z−x∈(−k,k)^{n}∩(2 )^{n}} [f (z + ε) − f (z − ε)] = \frac{1}{k(k + 1)^{n−1}} ∑_{y∈ _{m}^{n}} b_{y}(x, ε)f (y),  (38)

where a_{y}(x, ε), b_{y}(x, ε) ∈ are appropriately chosen coefficients, which are independent of f. For x ∈ _{m}^{n} define S(x) ⊂ _{m}^{n},

S(x) = {y ∈ x + (2 + 1)^{n} : d_{_{m}^{n}}(y, x) = k, and |{j : |y_{j} − x_{j}| ≡ k mod m}| ≥ 2}.

Claim 5.5. For x ∈ _{m}^{n} and y S(x), a_{y}(x, ε) = b_{y}(x, ε).

Proof. If there exists a coordinate j ∈ {1, …, n} such that x_{j} − y_{j} is even, then it follows from our definitions that a_{y}(x, ε) = b_{y}(x, ε) = 0. Similarly, if d_{_{m}^{n}}(x, y) > k then a_{y}(x, ε) = b_{y}(x, ε) = 0 (because k is odd). Assume that x − y ∈ (2 + 1)^{n}. If d_{_{m}^{n}}(y, x) < k then for each j the term f (y) cancels in E_{j}^{(k)}f (x + e_{j}) − E_{j}^{(k)}(x − e_{j}), implying that a_{y}(x, ε) = 0. Similarly, in the sum defining B_{f} (x, ε) the term f (y) appears twice, with opposite signs, so that b_{y}(x, ε) = 0.

It remains to deal with the case |{j : |y_{j} − x_{j}| ≡ k mod m}| = 1. We may assume without loss of generality that

|y_{1} − x_{1}| ≡ k mod m and for j ≥ 2 , y_{j} − x_{j} ∈ (−k, k) mod m.

If y_{1} − x_{1} ≡ k mod m then a_{y}(x, ε) = ε_{1}, since in the terms corresponding to j ≥ 2 in the definition of A_{f} (x, ε) the summand f (y) cancels out. We also claim that in this case b_{y}(x, ε) = ε_{1}. Indeed, if ε_{1} = 1 then f (y) appears in the sum defining B_{f} (x, ε) only in the term corresponding to z = y − ε, while if ε_{1} = −1 then f (y) appears in this sum only in the term corresponding to z = y + ε, in which case its coefficient is −1. In the case y_{1} − x_{1} ≡ −k mod m the same reasoning shows that a_{y}(x, ε) = b_{y}(x, ε) = −ε_{1}.

By Claim 5.5 we have

A_{f} (x, ε) − B_{f} (x, ε) = \frac{1}{k(k + 1)^{n−1}} ∑_{y∈S(x)}[a_{y}(x, ε) − b_{y}(x, ε)]f (y).  (39)

Thus,

∫_{_{m}^{n}} ∥A_{f} (x, ε)∥_{X}^{p}dμ(x) ≤ 3^{p−1} ∫_{_{m}^{n}} ∥B_{f} (x, ε)∥_{X}^{p}dμ(x) + 3^{p−1} ∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈S(x)}a_{y}(x, ε)f (y)∥_{X}^{p}dμ(x) +

3^{p−1} ∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈S(x)}b_{y}(x, ε)f (y)∥_{X}^{p}dμ(x).

Thus Lemma 5.4 will be proved once we establish the following inequalities

∫_{_{m}^{n}} ∥B_{f} (x, ε)∥_{X}^{p}dμ(x) ≤ ∫_{_{m}^{n}} ∥f (x + ε) − f (x − ε)∥_{X}^{p}dμ(x),  (40)

∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈S(x)}a_{y}(x, ε)f (y)∥_{X}^{p}dμ(x) ≤ \frac{8^{p}n^{2p−1}}{k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥ _{X}^{p},  (41)

and

∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{y∈S(x)}b_{y}(x, ε)f (y)∥_{X}^{p}dμ(x) ≤ \frac{8^{p}n^{2p−1}}{k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥ _{X}^{p}.  (42)

Inequality (40) follows directly from the definition of B_{f} (x, ε), by convexity. Thus, we pass to the proof of (41) and (42).

For j = 1, 2, …, n define for y ∈ S(x),

τ_{j}^{x}(y) = \{ \begin{matrix}y − 2ke_{j} & y_{j} − x_{j} ≡ k mod m, \\ y & otherwise, \end{matrix}

and set τ_{j}^{x}(y) = y when y S(x). Observe that the following identity holds true:

τ_{j}^{x}(y) = τ_{j}^{0}(y − x) + x.  (43)

Claim 5.6. Assume that for every j ∈ {1, 2, …, n}, x, y ∈ _{m}^{n} and ε ∈ {−1, 1}^{n}, we are given a real number η_{j}(x, y, ε) ∈ [−1, 1]. Then

∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} η_{j}(x, y, ε) [f (y) − f (τ_{j}^{x}(y))] ∥_{X}^{p}dμ(x) ≤ \frac{8^{p}n^{2p−1}}{2k^{p}} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + e_{j}) − f (x)∥ _{X}^{p}dμ(x).

Proof. Denote by N(x, ε) the number of non-zero summands in

∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} η_{j}(x, y, ε) [f (y) − f (τ_{j}^{x}(y))] .

For every ℓ ≥ 2 let S^{ℓ}(x) be the set of all y ∈ S(x) for which the number of coordinates j such that y_{j} − x_{j} ∈ \{k, −k\} mod m equals ℓ. Then |S^{ℓ}(x)| = \binom{n}{ℓ}2^{ℓ}(k − 1)^{n−ℓ}. Moreover, for y ∈ S^{ℓ}(x) we have that y τ_{j}^{x}(y) for at most ℓ values of j. Hence

N(x, ε) ≤ ∑_{ℓ=2}^{n} |S^{ℓ}(x)|ℓ = ∑_{ℓ=2}^{n} \binom{n}{ℓ}2^{ℓ}(k − 1)^{n−ℓ}ℓ = 2n [(k + 1)^{n−1} − (k − 1)^{n−1}] ≤ \frac{4n^{2}}{k^{2}}k(k + 1)^{n−1}.

Now, using (43), we get

∫_{_{m}^{n}} ∥\frac{1}{k(k + 1)^{n−1}} ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} η_{j}(x, y, ε) [f (y) − f (τ_{j}^{x}(y))] ∥_{X}^{p}dμ(x)

= ∫_{_{m}^{n}} (\frac{N(x, ε)}{k(k + 1)^{n−1}})^{p} ∥\frac{1}{N(x, ε)} ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} η_{j}(x, y, ε) [f (y) − f (τ_{j}^{x}(y))] ∥_{X}^{p}dμ(x)

≤ ∫_{_{m}^{n}} \frac{N(x, ε)^{p−1}}{k^{p}(k + 1)^{(n−1)p}} ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} ∥f (y) − f (τ_{j}^{x}(y))∥_{X}^{p}dμ(x)

≤ \frac{4^{p−1}n^{2p−2}}{k^{2p−1}(k + 1)^{n−1}} ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} ∫_{_{m}^{n}} ∥f (y) − f (τ_{j}^{x}(y))∥_{X}^{p}dμ(x)

= \frac{4^{p−1}n^{2p−2}}{k^{2p−1}(k + 1)^{n−1}} ∑_{j=1}^{n} ∑_{z∈ _{m}^{n}} ∫_{_{m}^{n}} ∥f (z + x) − f (τ_{j}^{0}(z) + x)∥ _{X}^{p}dμ(x).  (44)

Consider the following set:

E_{j} = {z ∈ _{m}^{n}: τ_{j}^{0}(z) = z − 2ke_{j}}.

Observe that that for every j,

|E_{j}| = ∑_{ℓ=1}^{n−1} \binom{n − 1}{ℓ}2^{ℓ}(k − 1)^{n−1−ℓ} ≤ (k + 1)^{n−1} − (k − 1)^{n−1} ≤ \frac{2n}{k}(k + 1)^{n−1}.  (45)

Using the translation invariance of the Haar measure on _{m}^{n} we get that

∑_{j=1}^{n} ∑_{z∈ _{m}^{n}} ∫_{_{m}^{n}} ∥f (z + x) − f (τ_{j}^{0}(z) + x)∥ _{X}^{p}dμ(x) = ∑_{j=1}^{n} ∑_{z∈E_{j}} ∫_{_{m}^{n}} ∥f (z + x) − f (z + x − 2ke_{j})∥_{X}^{p}dμ(x)

= ∑_{j=1}^{n} |E_{j}| ∫_{_{m}^{n}} ∥f (w) − f (w − 2ke_{j})∥_{X}^{p}dμ(w)

≤ \frac{2n}{k}(k + 1)^{n−1} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (w) − f (w − 2ke_{j})∥_{X}^{p}dμ(w)  (46)

≤ \frac{2n}{k}(k + 1)^{n−1} ∑_{j=1}^{n} ∫_{_{m}^{n}}((2k)^{p−1} ∑_{t=1}^{2k} ∥f (w − (t − 1)e_{j}) − f (w − te_{j})∥_{X}^{p})dμ(w)

≤ 2^{p+1}nk^{p−1}(k + 1)^{n−1} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (z + e_{j}) − f (z)∥_{X}^{p}dμ(z),  (47)

where in (46) we used (45). Combining (44) and (47) completes the proof of Claim 5.6.

By Claim 5.6, inequalities (41) and (42), and hence also Lemma 5.4, will be proved once we establish the following identities:

∑_{y∈S(x)}a_{y}(x, ε)f (y) = ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} ε_{j} [f (y) − f (τ_{j}^{x}(y))] .  (48)

and

∑_{y∈S(x)}b_{y}(x, ε)f (y) = ∑_{j=1}^{n} ∑_{y∈ _{m}^{n}} δ_{j}(x, y, ε) [f (y) − f (τ_{j}^{x}(y))] ,  (49)

for some δ_{j}(x, y, ε) ∈ {−1, 0, 1}.

Identity (48) follows directly from the fact that (37) implies that for every y ∈ S(x),

a_{y}(x, ε) = ∑_{j: y_{j}−x_{j}≡k mod m} ε_{j} − ∑_{j: y_{j}−x_{j}≡−k mod m} ε_{j}.

It is enough to prove identity (49) for x = 0, since b_{y}(x, ε) = b_{y−x}(0, ε). To this end we note that it follows directly from (38) that for every y ∈ S(0)

b_{y}(0, ε) = \{ \begin{matrix}1 & ∃j y_{j} ≡ ε_{j}k mod m and ∀ℓ y_{ℓ} −ε_{j}k mod m \\ −1 & ∃j y_{j} ≡ −ε_{j}k mod m and ∀ℓ y_{ℓ} ε_{j}k mod m \\ 0 & otherwise. \end{matrix}

For y ∈ S(0) define

y_{j}^{⊖} = \{ \begin{matrix}−y_{j} & y_{j} ∈ \{k, −k\} mod m \\ y_{j} & otherwise. \end{matrix}

Since b_{y}(0, ε) = −b_{y^{⊖}}(0, ε) we get that

∑_{y∈S(0)} b_{y}(0, ε)f (y) = \frac{1}{2} ∑_{y∈S(0)} b_{y}(0, ε) [f (y) − f (y^{⊖})] .  (50)

Define for ℓ ∈ {1, …, n + 1} a vector y^{⊖_{ℓ}} ∈ _{m}^{n} by

y_{j}^{⊖_{ℓ}} = \{ \begin{matrix}−y_{j} & j < ℓ and y_{j} ∈ \{k, −k\} mod m \\ y_{j} & otherwise. \end{matrix}

Then y^{⊖_{n+1}} = y^{⊖}, y^{⊖_{1}} = y and by (50)

∑_{y∈S(0)} b_{y}(0, ε)f (y) = \frac{1}{2} ∑_{ℓ=1}^{n} ∑_{y∈S(0)} b_{y}(0, ε) [f (y^{⊖_{ℓ}}) − f (y^{⊖_{ℓ+1}} )] .

Since whenever y^{⊖_{ℓ}} y^{⊖_{ℓ+1}} , each of these vectors is obtained from the other by flipping the sign of the ℓ-th coordinate, which is in {k, −k} mod m, this implies the representation (49). The proof of Lemma 5.4 is complete.

6 A nonlinear version of the Maurey-Pisier theorem

In what follows we denote by diag( _{m}^{n}) the graph on _{m}^{n} in which x, y ∈ _{m}^{n} are adjacent if for every i ∈ {1, …, n}, x_{i} − y_{i} ∈ {±1 mod m}.

For technical reasons that will become clear presently, given ℓ, n ∈ we denote by B(M; n, ℓ) the infimum over B > 0 such that for every even m ∈ and for every f : _{m}^{n} → M,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + ℓe_{j}), f (x))^{2} dμ(x) ≤ B^{2}ℓ^{2}n _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2}dμ(x).

Lemma 6.1. For every metric space (M, d_{M}), every n, a ∈ , every even m, r ∈ with 0 ≤ r < m, and every f : _{m}^{n} → M,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + (am + r)e_{j}) , f (x))^{2} dμ(x) ≤ min{r^{2}, (m − r)^{2}}· n _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2}dμ(x).(51)

In particular, B(M; n, ℓ) ≤ 1 for every n ∈ and every even ℓ ∈ .

Proof. The left-hand side of (51) depends only on r, and remains unchanged if we replace r by m − r. We may thus assume that a = 0 and r ≤ m − r. Fix x ∈ _{m}^{n} and j ∈ {1, …n}. Observe that

\{x + \frac{1 − (−1)^{k}}{2} ∑_{r j} e_{r} + ke_{j} \} _{k=0}^{r}

is a path of length r joining x and x + re_{j} in the graph diag( _{m}^{n}). Thus the distance between x and x + re_{j} in the graph diag( _{m}^{n}) equals r. If (x = w_{0}, w_{1}, …, w_{r} = x+re_{j}) is a geodesic joining x and x+re_{j} in diag( _{m}^{n}), then by the triangle inequality

d_{M}(f (x + re_{j}), f (x))^{2} ≤ r ∑_{k=1}^{r} d_{M}(f (w_{k}), f (w_{k−1}))^{2}.  (52)

Observe that if we sum (52) over all geodesics joining x and x + re_{j} in diag( _{m}^{n}), and then over all x ∈ _{m}^{n}, then in the resulting sum each edge in diag( _{m}^{n}) appears the same number of times. Thus, averaging this inequality over x ∈ _{m}^{n} we get that

∫_{_{m}^{n}} d_{M}(f (x + re_{j}), f (x))^{2}dμ(x) ≤ r^{2} _{ε}[d_{M}(f (x + ε), f (x))]^{2}.

Summing over j = 1, …n we obtain the required result.

Lemma 6.2. For every four integers ℓ, k, s, t ∈ ,

B (M; ℓk, st)≤ B (M; ℓ, s) · B (M; k, t).

Proof. Let m be an even integer and take a function f : _{m}^{ℓk} → M. Fix x ∈ _{m}^{ℓk} and ε ∈ {−1, 1}^{ℓk}. Define g : _{m}^{ℓ} → M by

g(y) = f (x + ∑_{r=1}^{k} ∑_{j=1}^{ℓ} ε_{j+(r−1)ℓ} · y_{j} · e_{j+(r−1)ℓ} ).

By the definition of B (M; ℓ, s), applied to g, for every B_{1} > B (M; ℓ, s) we have that

∑_{a=1}^{ℓ} ∫_{_{m}^{ℓ}} d_{M}(f (x + ∑_{r=1}^{k} ∑_{j=1}^{ℓ} ε_{j+(r−1)ℓ} · y_{j} · e_{j+(r−1)ℓ} + s ∑_{r=1}^{k} ε_{a+(r−1)ℓ} · e_{a+(r−1)ℓ}),

f (x + ∑_{r=1}^{k} ∑_{j=1}^{ℓ} ε_{j+(r−1)ℓ} · y_{j} · e_{j+(r−1)ℓ} ))^{2}dμ_{_{m}^{ℓ}}(y)

≤ B_{1}^{2}s^{2}ℓ · _{δ}∫_{_{m}^{ℓ}} d_{M}(f (x + ∑_{r=1}^{k} ∑_{j=1}^{ℓ} ε_{j+(r−1)ℓ} · (y_{j} + δ_{j}) · e_{j+(r−1)ℓ} ),

f (x + ∑_{r=1}^{k} ∑_{j=1}^{ℓ} ε_{j+(r−1)ℓ} · y_{j} · e_{j+(r−1)ℓ} ))^{2}dμ_{_{m}^{ℓ}}(y).

Averaging this inequality over x ∈ _{m}^{ℓk} and ε ∈ {−1, 1}^{ℓk}, and using the translation invariance of the Haar measure, we get that

ε ∑_{a=1}^{ℓ} ∫_{_{m}^{ℓk}} d_{M}(f (x + s ∑_{r=1}^{k} ε_{a+(r−1)ℓ} · e_{a+(r−1)ℓ}), f (x))^{2}dμ_{_{m}^{ℓk}}(x)

≤ B_{1}^{2}s^{2}ℓ _{ε}∫_{_{m}^{ℓk}} d_{M} (f (x + ε) , f (x))^{2} dμ_{_{m}^{ℓk}}(x). (53)

Next we fix x ∈ _{m}^{ℓk}, u ∈ {1, …, ℓ}, and define h_{u} : _{m}^{k} → M by

h_{u}(y) = f (x + s ∑_{r=1}^{k} y_{r} · e_{u+(r−1)ℓ}).

By the definition of B (M; k, t), applied to h_{u}, for every B_{2} > B (M; k, t)we have that

∑_{j=1}^{k} ∫_{_{m}^{k}} d_{M}(f (x + s ∑_{r=1}^{k} y_{r} · e_{u+(r−1)ℓ} + st· e_{u+(j−1)ℓ} ), f (x + s ∑_{r=1}^{k} y_{r} · e_{u+(r−1)ℓ}))^{2}dμ_{_{m}^{k}}(y)

= ∑_{j=1}^{k} ∫_{_{m}^{k}} d_{M}(h_{u}(y + te_{j}), h_{u}(y))^{2}dμ_{_{m}^{k}}(y)

≤ B_{2}^{2}t^{2}k · _{ε}∫_{_{m}^{k}} d (h_{u}(y + ε), h_{u}(y))^{2} dμ_{_{m}^{k}}(y)

= B_{2}^{2}t^{2}k _{ε}∫_{_{m}^{k}} d_{M}(f (x + s ∑_{r=1}^{k}(y_{r} + ε_{u+(r−1)ℓ}) · e_{u+(r−1)ℓ}), f (x + s ∑_{r=1}^{k} y_{r} · e_{u+(r−1)ℓ}))^{2}dμ_{_{m}^{k}}(y).

Summing this inequality over u ∈ {1, …, ℓ} and averaging over x ∈ _{m}^{ℓk}, we get, using (53), that

∑_{a=1}^{ℓk} ∫_{_{m}^{ℓk}} d_{M} (f (x + ste_{a}) , f (x))^{2} dμ(x) ≤ B_{2}^{2}t^{2}k _{ε} ∑_{u=1}^{ℓ} ∫_{_{m}^{ℓk}} d_{M}(f (x + s ∑_{r=1}^{k} ε_{u+(r−1)ℓ} · e_{u+(r−1)ℓ}), f (x))^{2}dμ(x)

≤ B_{2}^{2}t^{2}k · B_{1}^{2}s^{2}ℓ _{ε}∫_{_{m}^{ℓk}} d_{M} (f (x + ε) , f (x))^{2} dμ(x).

This implies the required result.

Lemma 6.3. Assume that there exist integers n_{0}, ℓ_{0} > 1 such that B(M; n_{0}, s_{0}) < 1. Then there exists 0 < q < ∞ such that for every integer n,

m_{q}^{(2)}(M; n, 3n_{0}) ≤ 2ℓ_{0}n^{log_{n_{0}} ℓ_{0}}.

In particular, Γ_{q}^{(2)}(M) < ∞.

Proof. Let q < ∞ satisfy B(M, n_{0}, ℓ_{0}) < n_{0}^{−1/q}. Iterating Lemma 6.2 we get that for every integer k, B(n_{0}^{k}, ℓ_{0}^{k}) ≤ n_{0}^{−k/q}. Denoting n = n_{0}^{k} and m = 2ℓ_{0}^{k}, this implies that for every f : _{m}^{n} → M,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{2} dμ(x) ≤ \frac{1}{4}m^{2}n^{1− \frac{2}{q}} _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2}dμ(x).

By Lemma 2.7 we deduce that Γ_{q}^{(2)}(M; n_{0}^{k}, 2ℓ_{0}^{k}) ≤ 3. For general n, let k be the minimal integer such that k ≤ n_{0}^{k}. By Lemma 2.5 we get that Γ(M; n, 2ℓ_{0}^{k}) ≤ 3n_{0}^{1−2/q} ≤ 3n_{0}. In other words,

m_{q}^{(2)}(M; n, 3n_{0}) ≤ 2ℓ_{0}^{k} ≤ 2ℓ_{0}n^{log_{n_{0}} ℓ_{0}}.

Theorem 6.4. Let n > 1 be an integer, m an even integer, and s an integer divisible by 4. Assume that η ∈ (0, 1) satisfies 8^{sn} \sqrt{η} < \frac{1}{2}, and that there exists a mapping f : _{m}^{n} → M such that

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + se_{j}) , f (x))^{2} dμ(x) > (1 − η)s^{2}n _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2}dμ(x).  (54)

Then

c_{M} ([s/4]_{∞}^{n} ) ≤ 1 + 8^{sn} \sqrt{η}.

In particular, if B(M; n, s) = 1 then c_{M} ([s/4]_{∞}^{n} ) = 1.

Proof. Observe first of all that (54) and Lemma 6.1 imply that m ≥ 2s \sqrt{1 − η} > 2s − 1, so that m ≥ 2s. In what follows we will use the following numerical fact: If a_{1}, …, a_{r} ≥ 0 and 0 ≤ b ≤ \frac{1}{r} ∑ _{j=1}^{r} a_{j}, then

∑_{j=1}^{r} (a_{j} − b)^{2} ≤ ∑_{j=1}^{r} a_{j}^{2} − rb^{2}.  (55)

For x ∈ _{m}^{n} let G_{j}^{+}(x) (resp. G_{j}^{−}(x)) be the set of all geodesics joining x and x + se_{j} (resp. x − se_{j}) in the graph diag( _{m}^{n}). As we have seen in the proof of Lemma 6.1, since s is even, these sets are nonempty. Notice that if m = 2s then G_{j}^{+}(x) = G_{j}^{−}(x), otherwise G_{j}^{+}(x) ∩ G_{j}^{−}(x) = ∅. Denote by G_{j}^{±}(x) = G_{j}^{+}(x) ∪ G_{j}^{−}(x), and for π ∈ G_{j}^{±}(x),

sgn(π) = \begin{cases}+1 & if π ∈ G_{j}^{+}(x) \\ −1 & o/w. \end{cases}

Each geodesic in G_{j}^{±}(x) has length s. We write each π ∈ G_{j}^{±}(x) as a sequence of vertices π = (π_{0} = x, π_{1}, …, π_{s} = x + sgn(π)se_{j}). Using (55) with a_{j} = d_{M}(f (π_{j}), f (π_{j−1} )) and b = \frac{1}{s}d_{M} (f (x + se_{j}) , f (x)), which satisfy the the conditions of (55) due to the triangle inequality, we get that for each π ∈ G_{j}^{±}(x),

∑_{ℓ=1}^{s} [d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (x + sgn(π)se_{j}) , f (x))] ^{2}

≤ ∑_{k=1}^{s} d_{M}(f (π_{ℓ}), f (π_{ℓ−1}))^{2} − \frac{1}{s}d_{M} (f (x + sgn(π)se_{j}) , f (x))^{2} . (56)

By symmetry |G_{j}^{+}(x)| = |G_{j}^{−}(x)|, and this value is independent of x ∈ _{m}^{n} and j ∈ {1, …, n}. Denote g = |G_{j}^{±}(x)|, and observe that g ≤ 2 · 2^{ns}. Averaging (56) over all x ∈ _{m}^{n} and π ∈ G_{j}^{±}(x), and summing over j ∈ {1, …, n}, we get that

\frac{1}{g} ∑_{j=1}^{n} ∫_{_{m}^{n}} ∑_{π∈G_{j}^{±}(x)} ∑_{ℓ=1}^{s} [d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (x + sgn(π)se_{j}) , f (x))] ^{2} dμ(x)

≤ sn _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2} dμ(x) − \frac{1}{s} ∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + se_{j}) , f (x))^{2} dμ(x)

< ηsn _{ε}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2} dμ(x).  (57)

Define ψ : _{m}^{n} → by

ψ(x) = 2ηsn2^{sn} _{ε}[d_{M}(f (x + ε), f (x))^{2}]−

∑_{j=1}^{n} ∑_{π∈G_{j}^{±}(x)} ∑_{ℓ=1}^{s} [d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (x + sgn(π)se_{j}) , f (x))] ^{2} .

Inequality (57), together with the bound on g, implies that

0 < ∫_{_{m}^{n}} ψ(x)dμ(x) = \frac{1}{(2s − 1)^{n}} ∫_{_{m}^{n}} ∑_{\begin{matrix}y∈ _{m}^{n} \\ d_{^{n}_{m}}(x,y)<s \end{matrix}}ψ(y)dμ(x).

It follows that there exists x^{0} ∈ _{m}^{n} such that

∑_{\begin{matrix}y∈ _{m}^{n} \\ d_{^{n}_{m}}(x^{0},y)<s \end{matrix}} ∑_{j=1}^{n} ∑ ; π∈G_{j}^{+}(x) ⋃ G_{j}^{−}(x)∑_{ℓ=1}^{s} [d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (y + sgn(π)se_{j}) , f (y))] ^{2}

< 2ηsn2^{sn} ∑_{\begin{matrix}y∈ _{m}^{n} \\ d_{^{n}_{m}}(x^{0},y)<s \end{matrix}} _{ε}[d_{M}(f (y + ε), f (y))^{2}] . (58)

By scaling the metric d_{M} we may assume without loss of generality that

\frac{1}{(2s − 1)^{n}} ∑_{\begin{matrix}y∈ _{m}^{n} \\ d_{^{n}_{m}}(x^{0},y)<s \end{matrix}} _{ε}[d_{M}(f (y + ε), f (y))^{2}] = 1.  (59)

It follows that there exists y^{0} ∈ _{m}^{n} satisfying d_{_{m}^{n}}(x^{0}, y^{0}) < s such that

ε[d_{M}(f (y^{0} + ε), f (y^{0}))^{2}] ≥ 1.  (60)

By translating the argument of f, and multiplying (coordinate-wise) by an appropriate sign vector in {−1, 1}^{n}, we may assume that y^{0} = 0 and all the coordinates of x^{0} are non-negative. Observe that this implies that every y ∈ {0, 1, …, s − 1}^{n} satisfies d_{_{m}^{n}}(x^{0}, y) < s. Thus (58), and (59) imply that for every y ∈ {0, 1, …, s − 1}^{n}, every j ∈ {1, …, n}, every π ∈ G_{j}^{±}(y), and every ℓ ∈ {1, …, s},

|d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (y + sgn(π)se_{j}) , f (y))| ≤ \sqrt{2η(2s − 1)^{n}sn2^{sn}} ≤ 2^{2sn} \sqrt{η}.  (61)

Claim 6.5. For every ε, δ ∈ {−1, 1}^{n} and every x ∈ _{m}^{n}, such that x + ε ∈ {0, 1, …, s − 1}^{n},

|d_{M}(f (x + ε), f (x)) − d_{M}(f (x + δ), f (x))| ≤ 2 \sqrt{η} · 2^{2sn}.

Proof. If ε = δ then there is nothing to prove, so assume that ε_{ℓ} = −δ_{ℓ}. Denote S = {j ∈ {1, …, n} : ε_{j} = −δ_{j}} and define θ, τ ∈ {−1, 1}^{n} by

θ_{j} = \begin{cases}−ε_{ℓ} & j = ℓ \\ ε_{j} & j ∈ S \ \{ℓ\} \\ 1 & j S \end{cases}  and  τ_{j} = \begin{cases}−ε_{ℓ} & j = ℓ \\ ε_{j} & j ∈ S \ \{ℓ\} \\ −1 & j S. \end{cases}

Consider the following path π in diag( _{m}^{n}): Start at x + ε ∈ {0, 1, …, s − 1}^{n}, go in direction −ε (i.e. pass to x), then go in direction δ (i.e. pass to x + δ), then go in direction θ (i.e. pass to x + δ + θ), then go in direction τ (i.e. pass to x + δ + θ + τ), and repeat this process s/4 times. It is clear from the construction that π ∈ G_{ℓ}^{ε_{ℓ}}(x + ε). Thus, by (61) we get that

|d_{M}(f (x + ε), f (x)) − d_{M}(f (x + δ), f (x))| = |d_{M}(f (π_{1}), f (π_{0})) − d_{M}(f (π_{2}), f (π_{1}))| ≤ 2 \sqrt{η} · 2^{2sn}.

Corollary 6.6. There exists a number A ≥ 1 such that for every ε ∈ {−1, 1}^{n},

(1 − 4 \sqrt{η} · 2^{2sn})A ≤ d_{M}(f (ε), f (0)) ≤ (1 + 4 \sqrt{η} · 2^{2sn})A.

Proof. Denote e = ∑ _{j=1}^{n} e_{j} = (1, 1, …, 1) and take

A = ( _{δ}[d_{M}(f (δ), f (0))^{2}])^{1/2}.

By (60), A ≥ 1. By Claim 6.5 we know that for every ε, δ ∈ {−1, 1}^{2^{s}},

d_{M}(f (ε), f (0)) ≤ d_{M}(f (e), f (0)) + 2 \sqrt{η} · 2^{2sn} ≤ d_{M}(f (δ), f (0)) + 4 \sqrt{η} · 2^{2sn}.

Averaging over δ, and using the Cauchy-Schwartz inequality, we get that

d_{M}(f (ε), f (0)) ≤ ( _{δ}[d_{M}(f (δ), f (0))^{2}])^{1/2} + 4 \sqrt{η} · 2^{2sn} = A + 4 \sqrt{η} · 2^{2sn} ≤ (1 + 4 \sqrt{η} · 2^{2sn})A.

In the reverse direction we also know that

A^{2} = _{δ}[d_{M}(f (δ), f (0))^{2}] ≤ [d_{M}(f (ε), f (0)) + 4 \sqrt{η} · 2^{2sn}]^{2} ,

which implies the required result since A ≥ 1.

Claim 6.7. Denote

V = \{x ∈ _{m}^{n}: ∀j 0 ≤ x_{j} ≤ \frac{s}{2} and x_{j} is even\} .  (62)

Then the following assertions hold true:

1. For every x, y ∈ V there is some z ∈ {x, y}, j ∈ {1, …, n}, and a path π ∈ G_{j}^{+}(z) of length s which goes through x and y. Moreover, we can ensure that if π = (π_{0}, …, π_{s}) then for all ℓ ∈ {1, …, s}, {π_{ℓ}, π_{ℓ−1}} ∩ {0, …, s − 1}^{n} ∅.

2. For every x, y ∈ V, d_{diag( _{m}^{n})}(x, y) = d_{_{m}^{n}}(x, y) = ∥x − y∥_{∞} .

Proof. Let j ∈ {1, …, n} be such that |y_{j} − x_{j}| = ∥x − y∥_{∞} t. Without loss of generality y_{j} ≥ x_{j}. We will construct a path of length s in G_{j}^{+}(x) which goes through y. To begin with, we define ε^{ℓ}, δ^{ℓ} ∈ {−1, 1}^{n} inductively as follows:

ε_{r}^{ℓ} = \begin{cases}1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) < y_{r} \\ −1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) > y_{r} \\ 1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) = y_{r} \end{cases}  and  δ_{j}^{r} = \begin{cases}1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) < y_{r} \\ −1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) > y_{r} \\ −1 & x_{r} + 2 ∑ _{k=1}^{ℓ−1}(ε_{r}^{k} + δ_{r}^{k}) = y_{r}. \end{cases}

If we define a_{ℓ} = x + ∑ _{k=1}^{ℓ} ε^{k} + ∑ _{k=1}^{ℓ−1} δ^{k} and b_{ℓ} = x + ∑ _{k=1}^{ℓ} ε^{k} + ∑ _{k=1}^{ℓ} δ^{k} then the sequence

(x, a_{1}, b_{1}, a_{2}, b_{2}, …, a_{t/2−1}, b_{t/2}= y)

is a path of length t in diag( _{m}^{n}) joining x and y. This proves the second assertion above. We extend this path to a path of length s (in diag( _{m}^{n})) from x to x + se_{j} as follows. Observe that for every 1 ≤ ℓ ≤ t/2, ε_{j}^{ℓ} = δ_{j}^{ℓ} = 1. Thus −ε^{ℓ} + 2e_{j}, −δ^{ℓ} + 2e_{j} ∈ {−1, 1}^{n}. If we define c_{ℓ} = y + ∑ _{k=1}^{ℓ}(−ε^{k} + 2e_{j}) + ∑ _{k=1}^{ℓ−1}(−δ^{k} + 2e_{j}) and d_{ℓ} = y + ∑ _{k=1}^{ℓ}(−ε^{k} + 2e_{j}) + ∑ _{k=1}^{ℓ}(−δ^{k} + 2e_{j}), then d_{t/2} = x + 2te_{j}. Observe that by the definition of V, 2t ≤ s, and s − 2t is even. Thus we can continue the path from x + 2te_{j} to x + se_{j} by alternatively using the directions e_{j} + ∑ _{ℓ j} e_{ℓ} and e_{j} − ∑ _{ℓ j} e_{ℓ}.

Corollary 6.8. Assume that x ∈ V. Then for A as in Corollary 6.6, we have for all ε ∈ {−1, 1}^{n},

(1 − 10 \sqrt{η} · 2^{2sn})A ≤ d_{M}(f (x + ε), f (x)) ≤ (1 + 10 \sqrt{η} · 2^{2sn})A.

Proof. By Claim 6.7 (and its proof), there exists j ∈ {1, …, n} and π ∈ G_{j}^{+}(0) such that π_{1} = e = (1, …, 1) and for some k ∈ {1, …, s}, π_{k} = x. Now, by (61) we have that

|d_{M} (f (e), f (0)) − d_{M} (f (π_{k−1}), f (x)) | ≤ 2 \sqrt{η} · 2^{2sn}.

Observe that since x ∈ V, x + e ∈ {0, …, s − 1}^{n}. Thus by Claim 6.5

|d_{M} (f (x + ε), f (x)) − d_{M} (f (e), f (0)) | ≤ |d_{M} (f (e), f (0)) − d_{M} (f (π_{k−1}), f (x)) |+
|d_{M} (f (π_{k−1}), f (x)) − d_{M} (f (x + e), f (x)) |+ |d_{M} (f (x + ε), f (x)) − d_{M} (f (x + e), f (x)) |
≤ 6 \sqrt{η} · 2^{2sn},

so that the required inequalities follow from Corollary 6.6.

Corollary 6.9. For every distinct x, y ∈ V,

(1 − 12 \sqrt{η} · 2^{2sn})A ≤ \frac{d_{M}(f (x), f (y))}{∥x − y∥_{∞}} ≤ (1 + 12 \sqrt{η} · 2^{2sn})A,

where A is as in Corollary 6.6.

Proof. Denote t = ∥x − y∥_{∞} , and we may assume that there exists j ∈ {1, …, n} such that y_{j} − x_{j} = t. By Claim 6.7 there is a path π ∈ G_{j}^{+}(x) of length s such that π_{t} = y. By (61) and Corollary 6.8 we have for every ℓ ∈ {1, …, s}

|d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) − \frac{1}{s}d_{M} (f (x + se_{j}) , f (x)) | ≤ \sqrt{η} · 2^{2sn},

and

(1 − 10 \sqrt{η} · 2^{2sn})A ≤ d_{M}(f (π_{0}), f ((π_{1})) ≤ (1 + 10 \sqrt{η} · 2^{2sn})A.

Thus, for all ℓ ∈ {1, …, s},

(1 − 12 \sqrt{η} · 2^{2sn})A ≤ d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) ≤ (1 + 12 \sqrt{η} · 2^{2sn})A.

Thus

d_{M}(f (x), f (y)) ≤ ∑_{ℓ=1}^{t} d_{M}(f (π_{ℓ}), f (π_{ℓ−1})) ≤ t · (1 + 12 \sqrt{η} · 2^{2sn})A = ∥x − y∥_{∞} · (1 + 12 \sqrt{η} · 2^{2sn})A.

On the other hand

d_{M}(f (x), f (y)) ≥ d_{M}(f (x + se_{j}), f (x)) − d_{M}(f (x + se_{j}), f (y))
≥ sd_{M}(f (x), f (π_{1})) − s \sqrt{η} · 2^{2sn} − ∑_{ℓ=t+1}^{s} d_{M}(f (π_{ℓ}), f (π_{ℓ−1}))
≥ s (1 − 10 \sqrt{η} · 2^{2sn})A − s \sqrt{η} · 2^{2sn} − (s − t) (1 − 12 \sqrt{η} · 2^{2sn})A
≥ ∥x − y∥_{∞} · (1 − 12 \sqrt{η} · 2^{2sn})A.

This concludes the proof of Theorem 6.4, since the mapping x ↦ x/2 is a distortion 1 bijection between (V, d_{_{m}^{n}}) and [s/4]_{∞}^{n} .

We are now in position to prove Theorem 1.5.

Proof of Theorem 1.5. We are assuming that Γ_{q}^{(2)}(M) = ∞ for all q < ∞. By Lemma 6.3 it follows that for every two integers n, s > 1, B(M; n, s) = 1. Now the required result follows from Theorem 6.4.

Lemma 6.10. Let M be a metric space and K > 0. Fix q < ∞ and assume that m m_{q}^{(2)}(M; n, K) < ∞. Then

c_{M} ( _{m}^{n}) ≥ \frac{n^{1/q}}{2K},

Proof. Fix a bijection f : _{m}^{n} → M. Then

\frac{nm^{2}}{4∥f^{−1}∥_{Lip}^{2}} ≤ ∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{2} dμ(x)

≤ K^{2}m^{2}n^{1− \frac{2}{q}} ∫_{\{−1,01\}^{n}}∫_{_{m}^{n}} d_{M}(f (x + ε), f (x))^{2}dμ(x)dσ(ε)
≤ K^{2}m^{2}n^{1− \frac{2}{q}} ∥f ∥_{Lip}^{2}.

It follows that dist(f) ≥ \frac{n^{1/q}}{2K}.

Corollary 6.11. Let F be a family of metric spaces and 0 < q, K, c < ∞. Assume that for all n ∈ , Γ_{q}^{(2)}(M; n, n^{c}) ≤ K for every M ∈ F. Then for every integer N,

D_{N}(F) ≥ \frac{1}{2cK} (\frac{logN}{loglogN})^{1/q}.

We require the following simple lemma, which shows that the problems of embedding [m]_{∞}^{n} and _{m}^{n} are essentially equivalent.

Lemma 6.12. The grid [m]_{∞}^{n} embeds isometrically into _{2m}^{n}. Conversely, _{2m}^{n} embeds isometrically into [m + 1]_{∞}^{2mn}. Moreover, for each ε > 0, _{2m}^{n} embeds with distortion 1 + 6ε into [m + 1]^{(⌈1/ε⌉+1)n}.

Proof. The first assertion follows by considering only elements of _{2m}^{n}whose coordinates are at most m − 1. Next, the Fréchet embedding x ↦ (d_{_{2m}}(x, 0), d_{_{2m}}(x, 1), …, d_{_{2m}}(x, 2m − 1)) ∈ [m + 1]_{∞}^{2m}, is an isometric embedding of _{2m}. Thus _{2m}^{n}embeds isometrically into [m+1]_{∞}^{2mn}. The final assertion is proved analogously by showing that _{2m} embeds with distortion 1 + ε into [m + 1]_{∞}^{⌈1/ε⌉+1}. This is done by considering the embedding

x ↦ (d_{_{m}}(x, 0), d_{_{m}}(x, ⌊2εm⌋), d_{_{m}}(x, ⌊4εm⌋), d_{_{m}}(x, ⌊6εm⌋), …, d_{_{m}}(x, ⌊2⌈1/ε⌉εm⌋)),

which is easily seen to have distortion at most 1 + 6ε.

We are now in position to prove Theorem 1.6.

Proof of Theorem 1.6. We first prove the implication 1) ⟹ 2). Let Z be the disjoint union of all finite subsets of members of F, i.e.

Z = ⨆ {N : |N| < ∞ and ∃ M ∈ F , N ⊆ M} .

For every k > 1 we define a metric d_{k} on Z by

d_{k}(x, y) = \{ \begin{matrix}\frac{d_{N}(x,y)}{diam(N)} & ∃ M ∈ F , ∃ N ⊆ M s.t.|N| < ∞ and x, y ∈ N \\ k & otherwise. \end{matrix}

Clearly d_{k} is a metric. Moreover, by construction, for every K, k > 1,

q_{(Z,d_{k})}(K) ≥ q_{F}(K).

Assume for the sake of contradiction that for every K, k > 1, q_{(Z,d_{k})}(K) = ∞. In other words, for every q < ∞, and k ≥ 1, Γ_{q}^{(2)}(Z, d_{k}) = ∞. By Lemma 6.3 it follows that for every k ≥ 1, and every two integers n, s > 1,

B ((Z, d_{k}); n, s)= 1.

Theorem 6.4 implies that c_{(Z,d_{k})}([m]_{∞}^{n} )= 1.

By our assumption there exists a metric space X such that c_{F}(X) D > 1. Define a metric space X′ = X × {1, 2} via d_{X′}((x, 1), (y, 1)) = d_{X′}((x, 2), (y, 2)) = d_{X}(x, y) and d_{X′}((x, 1), (y, 2)) = 2 diam(X). For large enough s we have that c_{[2^{s−3}]_{∞}^{2^{s}}}(X′) < D. Thus c_{(Z,d_{k})}(X′) < D for all k. Define

k = \frac{4 diam(X)}{min\begin{matrix}x,y∈X \\ x y \end{matrix}d_{X}(x, y)}.

Then there exists a bijection f : X′ → (Z, d_{k}) with dist(f) < min{2, D}. Denote L = ∥f ∥_{Lip}.

We first claim that there exists M ∈ F, and a finite subset N ⊆ M, such that |f (X′) ∩ N| ≥ 2. Indeed, otherwise, by the definition of d_{k}, for all x′, y′ ∈ X′, d_{k}(f (x′), f (y′)) = k. Choosing distinct x, y ∈ X, we deduce that

k = d_{k}(f (x, 1), f (y, 1)) ≤ Ld_{X}(x, y) ≤ L diam(X),

and

k = d_{k}(f (x, 1), f (y, 2)) ≥ \frac{L}{dist(f)} · d_{X′}((x, 1), (y, 2)) > \frac{L}{2} · 2 diam(X) = L diam(X),

which is a contradiction.

Thus, there exists M ∈ F and a finite subset N ⊆ M such that |f (X′) ∩ N| ≥ 2. We claim that this implies that f (X′) ⊆ N. This will conclude the proof of 1) ⟹ 2), since the metric induced by d_{k} on N is a re-scaling of d_{N}, so that X embeds with distortion smaller than D into N ⊆ M ∈ F, which is a contradiction to the definition of D.

Assume for the sake of a contradiction that there exists x′ ∈ X′such that f (x′) N. By our assumption there are distinct a′, b′ ∈ X′such that f (a′), f (b′) ∈ N. Now,

1 ≥ d_{k}(f (a′), f ((b′)) ≥ \frac{L}{dist(f)} · d_{X′}(a′, b′) > \frac{L}{2} · min_{\begin{matrix}u,v∈X \\ u v \end{matrix}}d_{X}(u, v),

while

\frac{4 diam(X)}{min\begin{matrix}u,v∈X \\ u v \end{matrix}d_{X}(u, v)}= k = d_{k}(f (x′), f ((a′)) ≤ Ld(x′, a′) ≤ L diam(X′) = 2L diam(X),

which is a contradiction.

To prove the implication 2) ⟹ 3) observe that in the above argument we have shown that there exists k, q < ∞ such that Γ_{q}^{(2)}(Z, d_{k}) < ∞. It follows that for some integer n_{0}, B((Z, d_{k}); n_{0}, n_{0}) < 1, since otherwise by Theorem 6.4 we would get that (Z, d_{k}) contains, uniformly in n, bi-Lipschitz copies of [n]_{∞}^{n} . Combining Lemma 6.12 and Lemma 6.10 we arrive at a contradiction. By Lemma 6.3, the fact that B((Z, d_{k}); n_{0}, n_{0}) < 1, combined with Corollary 6.11, implies that D_{n}(Z, d_{k}) = Ω((logn)^{α}) for some α > 0. By the definition of (Z, d_{k}), this implies the required result.

We end this section by proving Theorem 1.8:

Proof. Denote |X| = n and

Φ = \frac{diam(X)}{min_{x y} d(x, y)}.

Write t = 4Φ/ε and let s be an integer divisible by 4 such that s ≥ max\{n, t\}. Then c_{[s]_{∞}^{s}} (X) ≤ 1 + \frac{ε}{4}. Fix a metric space Z and assume that c_{Z}(X) > 1 + ε. It follows that c_{Z}([s]_{∞}^{s} ) ≥ 1 + \frac{ε}{2}. By Theorem 6.4 we deduce that

B(Z, s, 4s) ≤ 1 − \frac{ε^{2}}{2^{s^{2}}} .

By Lemma 6.3 we have that m_{q}^{(2)}(M; n, 3s) ≤ 8sn^{log_{s}(4s)}, where q ≤ \frac{10^{s}}{ε^{2}}. Thus by Lemma 6.10 and Lemma 6.12 we see that for any integer n ≥ 8s,

c_{Z} ([n^{5}]_{∞}^{n} ) ≥ \frac{n^{1/q}}{4s} = \frac{n^{ε^{2}/10^{s}}}{4s}.

Choosing N ≈ (Cγ)^{\frac{2^{4s}}{ε^{2}}} , for an appropriate universal constant C, yields the required result.

7 Applications to bi-Lipschitz, uniform, and coarse embeddings

Let (N, d_{N}) and (M, d_{M}) be metric spaces. For f : N → M and t > 0 we define

Ω_{f} (t) = sup{d_{M}(f (x), f (y)); d_{N}(x, y) ≤ t},

and

ω_{f} (t) = inf{d_{M}(f (x), f (y)); d_{N}(x, y) ≥ t}.

Clearly Ω_{f} and ω_{f} are non-decreasing, and for every x, y ∈ N,

ω_{f} (d_{N}(x, y))≤ d_{M}(f (x), f (y)) ≤ Ω_{f} (d_{N}(x, y))

With these definitions, f is uniformly continuous if lim_{t→0} Ω_{f} (t) = 0, and f is a uniform embedding if f is injective and both f and f^{−1} are uniformly continuous. Also, f is a coarse embedding if Ω_{f} (t) < ∞ for all t > 0 and lim_{t→∞} ω_{f} (t) = ∞.

Lemma 7.1. Let (M, d_{M}) be a metric space, n an integer, Γ > 0, and 0 < p ≤ q ≤ r. Then for every function f : ℓ_{r}^{n} → M, and every s > 0,

n^{1/q}ω_{f} (2s) ≤ Γm_{q}^{(p)}(M; n, Γ) · Ω_{f} (\frac{2πsn^{1/r}}{m_{q}^{(p)}(M; n, Γ)}).

Proof. Denote m = m_{q}^{(p)}(M; n, Γ), and define g : _{m}^{n} → M by

g(x_{1}, …, x_{n}) = f (∑_{j=1}^{n} se^{\frac{2πix_{j}}{m}} e_{j}).

Then

∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} d_{M}(g(x + ε), g(x))^{p}dμ(x)dσ(ε) ≤ max_{ε∈\{−1,01,\}^{n}}Ω_{f} (s(∑_{j=1}^{n} |e^{\frac{2πiε_{j}}{m}} − 1|^{r})^{1/r})^{p} ≤ Ω_{f} (\frac{2πsn^{1/r}}{m})^{p} .

On the other hand,

∑_{j=1}^{n} ∫_{_{m}^{n}} d_{M} (f (x + \frac{m}{2}e_{j}) , f (x))^{p} dμ(x) ≥ nω_{f} (2s)^{p}.

By the definition of m_{q}^{(p)}(M; n, Γ) it follows that

nω_{f} (2s)^{p} ≤ Γ^{p}m^{p}n^{1− \frac{p}{q}} Ω_{f} (\frac{2πsn^{1/r}}{m})^{p} ,

as required.

Corollary 7.2. Let M be a metric space which contains arbitrarily large equilateral subsets (e.g. M can be an infinite dimensional Banach space). Assume that there exist constants c, Γ > 0 such that for infinitely many integers n, m_{q}^{(p)}(M; n, Γ) ≤ cn^{1/q}. Then for every r > q, ℓ_{r} does not uniformly or coarsely embed into M.

Proof. To rule out the existence of a coarse embedding choose s = n^{\frac{1}{q}− \frac{1}{r}} in Lemma 7.1. Using Lemma 2.3 we get that

ω_{f} (2n^{\frac{1}{q}− \frac{1}{r}} ) ≤ cΓΩ_{f} (2πΓ)

Since q < r, it follows that lim inf_{t→∞} ω_{f} (t) < ∞, so f is not a coarse embedding.

To rule out the existence of a uniform embedding, assume that f : ℓ_{r} → X is invertible and f^{−1} is uniformly continuous. Then there exists δ > 0 such that for x, y ∈ ℓ_{r}, if d_{M}(f (x), f (y)) < δ then ∥x − y∥_{r} < 2. It follows that ω_{f} (2) ≥ δ. Choosing s = 1 in Lemma 7.1, and using Lemma 2.3, we get that

0 < δ ≤ ω_{f} (2) ≤ cΓΩ_{f} (2πΓ · n^{\frac{1}{r}− \frac{1}{q}} ).

Since r > q it follows that lim sup_{t→0} Ω_{f} (t) > 0, so that f is not uniformly continuous.

The following corollary contains Theorem 1.9, Theorem 1.10 and Theorem 1.11.

Corollary 7.3. Let X be an infinite dimensional K-convex Banach space. Assume that Y is a Banach space which coarsely or uniformly embeds into X. Then q_{Y} ≤ q_{X}. In particular, for p, q > 0, L_{p} embeds uniformly or coarsely into L_{q} if and only if p ≤ q or q ≤ p ≤ 2.

Proof. By the Maurey-Pisier theorem [46], for every ε > 0 and every n ∈ , Y contains a (1 + ε) distorted copy of ℓ_{q_{Y}}^{n}. By Theorem 4.1, since X is K-convex, for every q > q_{X} there exists Γ < ∞ such that m_{q}(M; n, Γ) = O (n^{1/q}). Thus, by the proof of Corollary 7.2, if Y embeds coarsely or uniformly into X then q_{Y} ≤ q, as required.

The fact that if p ≤ q then L_{p} embeds coarsely and uniformly into L_{q} follows from the fact that in this case L_{p}, equipped with the metric ∥x − y∥_{p}^{p/q}, embeds isometrically into L_{q} (for p ≤ q ≤ 2 this is proved in [12, 69]. For the remaining cases see Remark 5.10 in [47]). If 2 ≥ p ≥ q then L_{p} is linearly isometric to a subspace of L_{q} (see e.g. [70]). It remains to prove that if p > q and p > 2 then L_{p} does not coarsely or uniformly embed into L_{q}. We may assume that q ≥ 2, since for q ≤ 2, L_{q} embeds coarsely and uniformly into L_{2}. But, now the required result follows from the fact that L_{q} is K convex and q_{L_{q}} = q, q_{L_{p}} = p (see [49]).

We now pass to the proof of Theorem 1.12. Before doing so we remark that Theorem 1.12 is almost optimal in the following sense. The identity mapping embeds [m]_{∞}^{n} into ℓ_{q}^{n} with distortion n^{1/q}. By the Maurey-Pisier theorem [46], Y contains a copy of ℓ_{q_{Y}}^{n} with distortion 1 + ε for every ε > 0. Thus c_{Y}([m]_{∞}^{n} ) ≤ n^{1/q_{Y}}. Additionally, [m]_{∞}^{n} is m-equivalent to an equilateral metric. Thus, if Y is infinite dimensional then c_{Y}([m]_{∞}^{n} ) ≤ m. It follows that

c_{Y}([m]_{∞}^{n} ) ≤ min{n^{1/q_{Y}}, m}.

Proof of Theorem 1.12. Assume that m is divisible by 4 and

m ≥ \frac{2n^{1/q}}{C_{q}(Y)K(Y)}.

By Theorem 4.1, for every f : _{m}^{n} → Y,

∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}) − f (x)∥ _{Y}^{q}dμ(x) ≤ [15C_{q}(Y)K(Y)]^{q}m^{q}∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{Y}^{q}dμ(x)dσ(ε).

Thus, assuming that f is bi-Lipschitz we get that

\frac{nm^{q}}{2^{q}∥f^{−1}∥_{Lip}^{q}} ≤ [15C_{q}(Y)K(Y)]^{q}m^{q} · ∥f ∥_{Lip}^{q},

i.e.

dist(f) ≥ \frac{n^{1/q}}{30C_{q}(Y)K(Y)}.

By Lemma 6.12 this shows that for m ≥ \frac{2n^{1/q}}{C_{q}(Y)K(Y)}, such that m is divisible by 4, c_{Y}([m]_{∞}^{n} ) = Ω (n^{1/q}). If

m < \frac{2n^{1/q}}{C_{q}(Y)K(Y)}then the required lower bound follows from the fact that [m]_{∞}^{n} contains an isometric copy

of [m_{1}]_{∞}^{n_{1}}, where m_{1} is an integer divisible by 4, m_{1} ≥ \frac{2n_{1}^{1/q}}{C_{q}(Y)K(Y)}, and m_{1} = Θ(m), n_{1} = Θ(m^{q}). Passing to integers m which are not necessarily divisible by 4 is just as simple.

Remark 7.4. Similar arguments yield bounds on c_{Y}([m]_{p}^{n}), which strengthen the bounds in [48].

Remark 7.5. Although L_{1} is not K-convex, we can still show that

c_{1}([m]_{∞}^{n} ) = Θ (min\{\sqrt{n}, m\}).

This is proved as follows. Assume that f : _{m}^{n} → L_{1} is bi-Lipschitz. If m is divisible by 4, and m ≥ π \sqrt{n}, then the fact that L_{1}, equipped with the metric \sqrt{∥x − y∥_{1}}, is isometric to a subset of Hilbert space [69, 14], together with Proposition 3.1, shows that

∑_{j=1}^{n} ∫_{_{m}^{n}} ∥f (x + \frac{m}{2}) − f (x)∥ _{1} dμ(x) ≤ m^{2} ∫_{\{−1,0,1\}^{n}}∫_{_{m}^{n}} ∥f (x + ε) − f (x)∥_{1}dμ(x)dσ(ε).

Arguing as in the proof of Theorem 1.12, we see that for m ≈ \sqrt{n}, c_{1}([m]_{∞}^{n} ) = Ω ( \sqrt{n}). This implies the required result, as in the proof of Theorem 1.12.

8 Discussion and open problems

1. Perhaps the most important open problem related to the non-linear cotype inequality on Banach spaces is whether for every Banach space X with cotype q < ∞, for every 1 ≤ p ≤ q there is a constant Γ < ∞ such that m_{q}^{(p)}(X; n, Γ) = O (n^{1/q}). By Lemma 2.3 this is best possible. In theorem 4.1 we proved that this is indeed the case when X is K-convex, while our proof of Theorem 1.2 only gives m_{q}^{(p)}(X; n, Γ) = O (n^{2+1/q}).

2. L_{1} is not K-convex, yet we do know that m_{2}^{(1)}(L_{1}; n, 4) = O ( \sqrt{n}). This follows directly from Remark 7.5, Lemma 2.4 and Lemma 2.5. It would be interesting to prove the same thing for m_{2}(L_{1}; n, Γ).

3. We conjecture that the K-convexity assumption in Theorem 1.9 and Theorem 1.11 is not necessary. Since L_{1} embeds coarsely and uniformly into L_{2}, these theorems do hold for L_{1}. It seems to be unknown whether any Banach space with finite cotype embeds uniformly or coarsely into a K-convex Banach space. The simplest space for which we do not know the conclusion of these theorems is the Schatten trace class C_{1} (see [70]. In [66] it is shown that this space has cotype 2). The fact that C_{1} does not embed uniformly into Hilbert space follows from the results of [2], together with [55, 32]. For more details we refer to the discussion in [6] (a similar argument works for coarse embeddings of C_{1} into Hilbert space, using [60]). We remark that the arguments presented here show that a positive solution of the first problem stated above would yield a proof of Theorem 1.9 and Theorem 1.11 without the K-convexity assumption.

9 Acknowledgments

We are grateful to Keith Ball for several valuable discussions. We also thank Yuri Rabinovich for pointing out the connection to Matoušek’s BD Ramsey theorem.

References

[1] I. Aharoni. Every separable metric space is Lipschitz equivalent to a subset of c_{0}^{+}. Israel J. Math., 19:284–291, 1974.

[2] 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.

[3] S. Arora, L. Lovász, I. Newman, Y. Rabani, Y. Rabinovich, and S. Vempala. Local versus global properties of metric spaces. Manuscript, 2005.

[4] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[5] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. of Math., 2005. To appear.

[6] 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.

[7] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46–52, 1985.

[8] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222–230, 1986.

[9] J. Bourgain. Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 157–167. Springer, Berlin, 1987.

[10] J. Bourgain, T. Figiel, and V. Milman. On Hilbertian subsets of finite metric spaces. Israel J. Math., 55(2):147–152, 1986.

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

[12] J. Bretagnolle, D. Dacunha-Castelle, and J.-L. Krivine. Fonctions de type positif sur les espaces L^{p}. C. R. Acad. Sci. Paris, 261:2153–2156, 1965.

[13] M. R. Bridson and A. Haefliger. Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1999.

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

[15] J. Diestel, H. Jarchow, and A. Tonge. Absolutely summing operators, volume 43 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995.

[16] A. Dranishnikov, G. Gong, V. Lafforgue, and G. Yu. Uniform embeddings into Hilbert space and a question of Gromov. Can. Math. Bull., 45(1):60–70, 2002.

[17] P. Enflo. On a problem of Smirnov. Ark. Mat., 8:107–109, 1969.

[18] P. Enflo. On the nonexistence of uniform homeomorphisms between L_{p}-spaces. Ark. Mat., 8:103–105, 1969.

[19] P. Enflo. Topological groups in which multiplication on one side is differentiable or linear. Math. Scand., 24:195–207 (1970), 1969.

[20] P. Enflo. Uniform structures and square roots in topological groups. I, II. Israel J. Math. 8 (1970), 230-252; ibid., 8:253–272, 1970.

[21] P. Enflo. On infinite-dimensional topological groups. In Séminaire sur la Géométrie des Espaces de Banach (1977–1978), pages Exp. No. 10–11, 11. École Polytech., Palaiseau, 1978.

[22] T. Figiel, J. Lindenstrauss, and V. D. Milman. The dimension of almost spherical sections of convex bodies. Acta Math., 139(1-2):53–94, 1977.

[23] E. A. Gorin. On uniformly topological imbedding of metric spaces in Euclidean and in Hilbert space. Uspehi Mat. Nauk, 14(5 (89)):129–134, 1959.

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

[25] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces, volume 152 of Progress in Mathematics. Birkhäuser Boston Inc., Boston, MA, 1999. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.

[26] M. Gromov. Random walk in random groups. Geom. Funct. Anal., 13(1):73–146, 2003.

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

[28] P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In 42nd Annual Symposium on Foundations of Computer Science, pages 10–33. IEEE Computer Society, 2001.

[29] W. B. Johnson and N. L. Randrianarivony. ℓ_{p} (p > 2) does not coarsely embed into a Hilbert space. Manuscript, 2004.

[30] W. B. Johnson, H. P. Rosenthal, and M. Zippin. On bases, finite dimensional decompositions and weaker structures in Banach spaces. Israel J. Math., 9:488–506, 1971.

[31] J.-P. Kahane. Sur les sommes vectorielles ∑ ±u_{n}. C. R. Acad. Sci. Paris, 259:2577–2580, 1964.

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

[33] G. Kasparov and G. Yu. The coarse geometric Novikov conjecture and uniform convexity. Manuscript, 2004.

[34] H. König and L. Tzafriri. Some estimates for type and cotype constants. Math. Ann., 256(1):85–94, 1981.

[35] S. Kwapien. Isomorphic characterizations of inner product spaces by orthogonal series with vector valued coefficients. Studia Math., 44:583–595, 1972.

[36] M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes.

[37] J. Lindenstrauss. On nonlinear projections in Banach spaces. Mich. Math. J., 11:263–287, 1964.

[38] J. Lindenstrauss. Uniform embeddings, homeomorphisms and quotient maps between Banach spaces (a short survey). Topology Appl., 85(1-3):265–279, 1998.

[39] J. Lindenstrauss and H. P. Rosenthal. The L_{p} spaces. Israel J. Math., 7:325–349, 1969.

[40] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin, 1979. Function spaces.

[41] N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, pages 573–586, 2002.

[42] N. Linial, A. Magen, and A. Naor. Girth and Euclidean distortion. Geom. Funct. Anal., 12(2):380–394, 2002.

[43] J. Matoušek. Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces. Comment. Math. Univ. Carolin., 33(3):451–463, 1992.

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

[45] B. Maurey. Type, cotype and K-convexity. In Johnson, W. B. and Lindenstrauss, J. (ed.), Handbook of the geometry of Banach spaces. Volume 2. Amsterdam: North-Holland. 1299-1332. 2003.

[46] B. Maurey and G. Pisier. Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach. Studia Math., 58(1):45–90, 1976.

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

[48] M. Mendel and A. Naor. Some application of Ball’s extension theorem. Proc. Amer. Math. Soc., 2005. To appear.

[49] V. D. Milman and G. Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[50] A. Naor. A phase transition phenomenon between the isometric and isomorphic extension problems for Hölder functions between L_{p} spaces. Mathematika, 48(1-2):253–271 (2003), 2001.

[51] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov hyperbolic metric spaces. Preprint, 2004.

[52] A. Naor and G. Schechtman. Remarks on non linear type and Pisier’s inequality. J. Reine Angew. Math., 552:213–236, 2002.

[53] N. Ozawa. A note on non-amenability of B(ℓ_{p}) for p = 1, 2. Int. J. Math., 15(6):557–565, 2004.

[54] G. Pisier. Sur les espaces qui ne contiennent pas de l_{n}^{1} uniformement. In Sémin. Maurey-Schwartz 1973-1974, Espaces L^{p}, Appl. radonif., Géom. Espaces de Banach, Exposé VII. 1974.

[55] G. Pisier. Some results on Banach spaces without local unconditional structure. Compositio Math., 37(1):3–19, 1978.

[56] G. Pisier. Holomorphic semigroups and the geometry of Banach spaces. Ann. of Math. (2), 115(2):375– 392, 1982.

[57] G. Pisier. Factorization of linear operators and geometry of Banach spaces, volume 60 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1986.

[58] G. Pisier. Probabilistic methods in the geometry of Banach spaces. In Probability and analysis (Varenna, 1985), volume 1206 of Lecture Notes in Math., pages 167–241. Springer, Berlin, 1986.

[59] G. Pisier. The volume of convex bodies and Banach space geometry, volume 94 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1989.

[60] N. L. Randrianarivony. Characterization of quasi-Banach spaces which coarsely embed into a Hilbert space. Manuscript, 2004.

[61] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14:237–244, 1976.

[62] M. Ribe. On uniformly homeomorphic normed spaces. II. Ark. Mat., 16:1–9, 1978.

[63] W. Rudin. Fourier analysis on groups. Wiley Classics Library. John Wiley & Sons Inc., New York, 1990. Reprint of the 1962 original, A Wiley-Interscience Publication.

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

[65] M. Talagrand. An isoperimetric theorem on the cube and the Kintchine-Kahane inequalities. Proc. Amer. Math. Soc., 104(3):905–909, 1988.

[66] N. Tomczak-Jaegermann. The moduli of smoothness and convexity and the Rademacher averages of trace classes S_{p}(1 ≤ p < ∞). Studia Math., 50:163–182, 1974.

[67] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow, 1989.

[68] L. Tzafriri. On the type and cotype of Banach spaces. Israel J. Math., 32(1):32–38, 1979.

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

[70] P. Wojtaszczyk. Banach spaces for analysts, volume 25 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1991.

[71] G. Yu. The coarse Baum-Connes conjecture for spaces which admit a uniform embedding into Hilbert space. Invent. Math., 139(1):201–240, 2000.