. SPECTRAL CALCULUS AND LIPSCHITZ EXTENSION

FOR BARYCENTRIC METRIC SPACES

MANOR MENDEL AND ASSAF NAOR

Dedicated to Nigel Kalton

Abstract. The metric Markov cotype of barycentric metric spaces is computed, yielding the first class of metric spaces that are not Banach spaces for which this bi-Lipschitz invariant is understood. It is shown that this leads to new nonlinear spectral calculus inequalities, as well as a unified framework for Lipschitz extension, including new Lipschitz extension results for CAT (0) targets. An example that elucidates the relation between metric Markov cotype and Rademacher cotype is analyzed, showing that a classical Lipschitz extension theorem of Johnson, Lindenstrauss and Benyamini is asymptotically sharp.

1. Introduction

Our main purpose here is to compute a bi-Lipschitz invariant, called metric Markov cotype, for barycentric metric spaces; an important class of metric spaces that contains all uniformly convex Banach spaces as well as complete simply connected metric spaces that are nonpositively curved in the sense of Aleksandrov.

The notion of metric Markov cotype arises from the deep work [3] of K. Ball on the Lipschitz extension problem. Based mainly on Ball’s ideas in [3], combined with some additional geometric ingredients, we establish a fully nonlinear version of Ball’s extension theorem that allows for targets that are not necessarily Banach spaces. Due to our computation of metric Markov cotype for barycentric spaces, this yields a versatile Lipschitz extension theorem that contains as special cases many Lipschitz extension theorems that appeared in the literature, as well as Lipschitz extension results that were previously unknown.

Another use of metric Markov cotype is due to [43], where it is shown to yield spectral calculus inequalities for nonlinear spectral gaps. Consequently, our computation of metric Markov cotype for barycentric metric spaces implies new nonlinear spectral calculus inequalities which, in the special case of CAT (0) spaces, lay the groundwork for our forthcoming construction [44] of expanders with respect to certain Hadamard spaces and random graphs.

Finally, we show that a beautiful construction of Kalton [29] yields a closed linear subspace X of L_{1} (thus in particular X has Rademacher cotype 2) that fails to have finite metric Markov cotype. By obtaining a quantitative version of Kalton’s result, we show that a classical Lipschitz extension theorem of Johnson, Lindenstrauss and Benyamini [23] is asymptotically sharp.

In order to give precise formulations of the above results one needs to recall some background. This will be done in the subsequent sections that contain a detailed description of the contents of this paper.

1.1. Markov type and metric Markov cotype. Given n ∈ ℕ and π ∈ Δ^{n−1} =^{def} {x ∈ [0, 1]^{n} : ∑_{i=1}^{n} x_{i} = 1}, recall that a stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) (here and in what follows, M_{n}(ℝ) denotes as usual the n by n matrices with real entries) is said to be reversible relative to the probability vector π if π_{i}a_{ij} = π_{j}a_{ji} for all i, j ∈ {1, …, n}. The following important definition is due to K. Ball [3].

Definition 1.1 (Markov type p). A metric space (X, d_{X}) is a said to have Markov type p ∈ (0, ∞) with constant M ∈ (0, ∞) if for every n, t ∈ ℕ and every π ∈ Δ^{n−1}, if A = (a_{ij}) ∈ M_{n}(ℝ) is a stochastic matrix that is reversible relative to π then every x_{1}, …, x_{n} ∈ X satisfy

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ M^{p}t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(x_{i}, x_{j})^{p}. (1)

The infimum over those M ∈ (0, ∞) satisfying (1) is denoted M_{p}(X).

The triangle inequality implies that M_{1}(X) = 1 for every metric space (X, d_{X}), and Ball proved in [3] that M_{p}(ℓ_{p}) = 1 for p ∈ [1, 2]. In [50] it is shown that M_{2}(ℓ_{p}) ≲ \sqrt{p} for p ∈ [2, ∞) (here, and in what follows, A ≲ B and B ≳ A denotes the estimate A ⩽ CB for some absolute constant C ∈ (0, ∞)). Additional examples of computations of Markov type will be discussed in Section 1.5.

Markov type is a bi-Lipschitz invariant that has proved itself useful to a variety problems in metric geometry, one of which will be recalled below. We refer to [3] for the natural probabilistic interpretation of (1) that explains the above terminology (this interpretation is not needed in the present paper, but it is important elsewhere).

Definition 1.2 (metric Markov cotype p). A metric space (X, d_{X}) is said to have metric Markov cotype p ∈ (0, ∞) with constant N ∈ (0, ∞) if for every n, t ∈ ℕ and every π ∈ Δ^{n−1}, if A = (a_{ij}) ∈ M_{n}(ℝ) is a stochastic matrix that is reversible relative to π then for every x_{1}, …, x_{n} ∈ X there exist y_{1}, …, y_{n} ∈ X satisfying

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p}

⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i} (\frac{1}{t} ∑_{s=1}^{t} A^{s})_{ij} d_{X}(x_{i}, x_{j})^{p}. (2)

The infimum over those N ∈ (0, ∞) satisfying (1) is denoted N_{p}(X).

Definition 1.2 is taken from [43]. In [3] Ball suggested a seemingly different notion of Markov cotype, but it is in fact equivalent to Definition 1.2, as explained in Section 7. Due to applications of (2) that will be described later, we believe that it is beneficial to work with the above definition of metric Markov cotype rather than Ball’s original formulation. See Section 7 for a description of Ball’s approach.

Condition (2) originates from an attempt to introduce an invariant that is “dual” to Markov type by reversing the inequality in (1). However, no non-singleton metric space can satisfy (1) with the direction of the inequality reversed (this follows formally from observations in [51] and [42], and can be also easily verified directly). (2) achieves a similar reversal of (1) by allowing one to pass from the initial points x_{1}, …, x_{n} ∈ X to new points y_{1}, …, y_{n} ∈ X. The first summand in the left hand side of (2) ensures that on average (with respect to π) y_{i} is close to x_{i}. The remaining terms in (2) correspond to the reversal of (1), with {x_{i}}_{i=1}^{n} replaced by {y_{i}}_{i=1}^{n} in the left hand side, and the power A^{t} replaced by the Cesàro average \frac{1}{t} ∑_{s=1}^{t} A^{s}.

Due to [3, 43], Banach spaces that admit an equivalent norm whose modulus of convexity has power type p have metric Markov cotype p, in particular N_{p}(ℓ_{p}) ≲ 1 for p ∈ [2, ∞) and N_{2}(ℓ_{p}) ≲ 1/\sqrt{p − 1} for p ∈ (1, 2]. Prior to the present work this was the only nontrivial class of metric spaces whose metric Markov cotype was known. Here we enrich the repertoire of metric spaces for which one can prove a metric Markov cotype inequality such as (2), treating also spaces that are not necessarily Banach spaces.

1.2. Barycentric metric spaces. In order to avoid measurability considerations that are irrelevant to the discussion at hand, we will tacitly assume throughout this article that all measures are finitely supported and all σ-algebras are finite.

The set of probability measures on a set X is denoted 𝒫_{X}. Denoting the point mass at x ∈ X by δ_{x} ∈ 𝒫_{X}, every μ ∈ 𝒫_{X} can be written uniquely as μ = ∑_{i=1}^{n} λ_{i}δ_{x_{i}} for some n ∈ ℕ, distinct x_{1}, …, x_{n} ∈ X and (λ_{1}, …, λ_{n}) ∈ Δ^{n−1}∩(0, 1]^{n}. A coupling of μ, ν ∈ 𝒫_{X} is a measure π ∈ 𝒫_{X×X} such that ∑_{z∈X} π(x, z) = μ(x) and ∑_{z∈X} π(z, y) = ν(y) for every x, y ∈ X (both of these sums are finite). The set of all the couplings of μ and ν is denoted Π(μ, ν) ⊆ 𝒫_{X×X}. If (X, d_{X}) is a metric space and p ∈ [1, ∞) then the corresponding Wasserstein p metric on 𝒫_{X} is defined as usual by

∀ μ, ν ∈ 𝒫_{X}, W_{p}(μ, ν) =^{def} inf_{π∈Π(μ,ν)} (∫_{X×X} d_{X}(x, y)^{p}dπ(x, y))^{1/p} .

Definition 1.3 (W_{p} barycentric metric space). Fix p, Γ ∈ [1, ∞). A metric space (X, d_{X}) is said to be W_{p} barycentric with constant Γ if there exists a mapping 𝔅 : 𝒫_{X} → X satisfying 𝔅(δ_{x}) = x for every x ∈ X, and

∀ μ, ν ∈ 𝒫_{X},  d_{X}(𝔅(μ), 𝔅(ν)) ⩽ ΓW_{p}(μ, ν).  (3)

(X, d_{X}) is said to be W_{p} barycentric if it is W_{p} barycentric with constant Γ for some Γ ∈ [1, ∞).

In what follows, a mapping 𝔅 : 𝒫_{X} → X satisfying 𝔅(δ_{x}) = x for every x ∈ X will be called a barycenter map. The notion of W_{p} barycentric metric spaces was studied by several authors: see e.g. [33, 17, 60, 20, 54, 53]. Note that if (X, d_{X}) is W_{p} barycentric with constant Γ then it is also W_{q} barycentric with constant Γ for every q ⩾ p. Normed spaces are W_{1} barycentric with constant Γ = 1, as exhibited by the barycenter map 𝔅(μ) = ∫_{X} xdμ(x). Metric spaces that are nonpositively curved in the sense of Busemann (see [9]) are also W_{1} barycentric with constant Γ = 1, as shown in [17, 53].

Definition 1.4 (p-barycentric metric space). Fix p, K ∈ [1, ∞). A metric space (X, d_{X}) is said to be p-barycentric with constant K if there exists a mapping 𝔅 : 𝒫_{X} → X such that for every x ∈ X and μ ∈ 𝒫_{X} we have

d_{X} (x, 𝔅(μ))^{p} + \frac{1}{K^{p}} ∫_{X} d_{X}(𝔅(μ), y)^{p}dμ(y) ⩽ ∫_{X} d_{X}(x, y)^{p}dμ(y). (4)

(X, d_{X}) is said to be p-barycentric if it is p-barycentric with constant K for some K ∈ [1, ∞).

The appearance of the constant K in the left hand side of (4) is natural from the point of view of Banach space theory (see [3, Lem 3.1] and [43, Lem. 6.5]), but note that it means that (unless K = 1) 𝔅(μ) need not be a point x ∈ X which minimizes the right hand side of (4). In many cases of interest one defines barycenters as minimizers of the right hand side of (4), but as will become clear from the ensuing considerations, Definition 1.4 suffices for many purposes.

In what follows, whenever we say that a metric space is W_{p} barycentric with constant Γ and also q-barycentric with constant K we mean that Definition 1.3 and Definition 1.4 are satisfied with respect to the same barycenter map 𝔅 : 𝒫_{X} → X. Examples of such spaces include all complete CAT (0) metric spaces (Hadamard spaces), which are W_{1} barycentric with constant 1 (see [33, Lem. 4.2] or [60, Thm. 6.3]) and also 2-barycentric with constant 1 (see [33, Lem. 4.1] or [60, Lem. 4.4]). Banach spaces whose modulus of uniform convexity have power type p ∈ [2, ∞) are W_{1} barycentric with constant 1 and also p-barycentric (see [3, Lem 3.1] for p = 2 and [43, Lem. 6.5] for p ∈ [2, ∞)).

We refer to the books [6, 26, 9] for an extensive discussion of the important class of CAT (0) metric spaces, which includes e.g. complete simply connected Riemannian manifolds with nonpositive sectional curvature and Euclidean Tits buildings. For the sake of readers who are not familiar with this notion we state that the definition of the class of CAT (0) metric spaces can be taken to be those metric spaces (X, d_{X}) for which there exists a mapping 𝔅 : 𝒫_{X} → X that satisfies (4) with p = 2 and K = 1 for probability measures μ that are supported on at most two points [60, Thm. 4.9]. Readers who are not familiar with the theory of uniformly convex Banach spaces are referred to [18, 5].

1.3. Metric Markov cotype for barycentric metric spaces. In Section 3 we prove the following result.

Theorem 1.5. Fix p, K, Γ ∈ [1, ∞). Suppose that (X, d_{X}) is a metric space that is W_{p} barycentric with constant Γ and also p-barycentric with constant K. Then (X, d_{X}) has metric Markov cotype p with

N_{p}(X) ≲ ΓK.  (5)

The special case of Theorem 1.5 when X is a Banach space whose modulus of uniform convexity has power type p was proved in [3, 43]. Our proof of Theorem 1.5 is based on an extension of the method of [43] to the present nonlinear setting. In particular we prove for this purpose a nonlinear analogue of Pisier’s martingale cotype inequality [57]; see Section 2 below.

Remark 1.6. The property of having metric Markov cotype p is clearly a bi-Lipschitz invariant. Similarly, the property of being W_{p} barycentric is a bi-Lipschitz invariant, but this is not the case for the property of being p-barycentic. Thus Theorem 1.5 leaves something to be desired, since its assumption is not invariant under bi-Lipschitz deformations while its conclusion is. By examining the proof of Theorem 1.5 one can extract a somewhat tedious bi-Lipschitz invariant condition that implies the same conclusion (5). It would be interesting to obtain a clean intrinsic characterization of those metric spaces (X, d_{X}) that are bi-Lipschitz equivalent to a p-barycentric metric space. For Banach spaces this was done in [45], the desired metric invariant being the notion of Markov p-convexity (see [45] for the definition). The method of [45] relies on the Banach space structure, so it remains open to characterize intrinsically those W_{p} barycentric metric spaces that are bi-Lipschitz equivalent to a p-barycentric metric space. It would also be interesting to characterize those Finsler manifolds that are p-barycentric.

1.4. Calculus for nonlinear spectral gaps. Let A = (a_{ij}) ∈ M_{n}(ℝ) be a symmetric stochastic matrix. Denote the decreasing rearangment of the eigenvalues of A by 1 = λ_{1}(A) ⩾ λ_{2}(A) ⩾ λ_{n}(A) ⩾ −1, and write λ(A) = max_{i∈{2,...,n}} |λ_{i}(A)|.

Following [43], given a metric space (X, d_{X}) and p ∈ (0, ∞) let γ_{+}(A, d_{X}^{p}) denote the infimum over those γ_{+} ∈ (0, ∞] for which every x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ X satisfy

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, y_{j})^{p} ⩽ \frac{γ_{+}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, y_{j})^{p}.  (6)

Letting d_{ℝ} denote the standard metric on ℝ, i.e., d_{ℝ}(x, y) = |x−y|, by simple linear algebra we see that γ_{+}(A, d_{ℝ}^{2}) = 1/(1−λ(A)). One should therefore think of the quantity γ_{+}(A, d_{X}^{p}) as measuring the magnitude of the nonlinear absolute spectral gap of the matrix A with respect to the geometry of X. We refer to [43] for a detailed discussion of nonlinear spectral gaps and their applications.

Despite the fact that we call inequalities such as (6) “spectral inequalities”, there is no actual spectrum present here, and therefore tools that are straightforward in the linear setting due to the link to linear algebra fail to hold true in general. This is especially important in the context of nonlinear spectral calculus, where one aims to relate γ_{+}(A^{t}, d_{X}^{p}) to γ_{+}(A, d_{X}^{p}). We refer to [43] for an explanation of the importance of this problem, where the following theorem is proved.

Theorem 1.7. There exists a universal constant κ ∈ (0, ∞) with the following property. Suppose that p ∈ [1, ∞) and that (X, d_{X}) is a metric space that has metric Markov cotype p. Then for every n, t ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ_{+} (\frac{1}{t} ∑_{s=1}^{t} A^{s}, d_{X}^{p}) ⩽ (κN_{p}(X))^{p} max \{1, \frac{γ_{+}(A, d_{X}^{p})}{t}\} .

By combining Theorem 1.5 and Theorem 1.7 we conclude that the following result holds true. Theorem 1.8. There exists a universal constant c ∈ (1, ∞) such that for every p, K, Γ ∈ [1, ∞), if (X, d_{X}) is a metric space that is W_{p} barycentric with constant Γ and p-barycentric with constant K then for every n, t ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ_{+} (\frac{1}{t} ∑_{s=1}^{t} A^{s}, d_{X}^{p}) ⩽ (cΓK)^{p} max \{1, \frac{γ_{+}(A, d_{X}^{p})}{t}\} .  (7)

For future applications it is worthwhile to single out the following special case of Theorem 1.8. Corollary 1.9. Suppose that (X, d_{X}) is a CAT (0) space. Then for every n, t ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ_{+} (\frac{1}{t} ∑_{s=1}^{t} A^{s}, d_{X}^{2}) ≲ max \{1, \frac{γ_{+}(A, d_{X}^{2})}{t}\} .

Corollary 1.9 was the main motivation for the investigations that led to the present paper, since it plays a key role in our forthcoming work [44] that establishes for the first time the existence of expanders with respect to certain Hadamard spaces and random graphs.

For the purpose of the applications in [44], the fact that the spectral calculus inequality (7) involves Cesàro averages of A rather than powers of A is immaterial, but it is natural to ask if it is possible to relate γ_{+}(A^{t}, d_{X}^{p}) to γ_{+}(A, d_{X}^{p}). In the setting of general barycentric metric spaces this question remains open, but for CAT (0) spaces, or more generally under the requirement K = 1 in (4), it is indeed possible to do so, albeit via an upper bound on γ_{+}(A^{t}, d_{X}^{p}) in terms of γ_{+}(A, d_{X}^{p}) that is weaker than the right hand side of (7). Theorem 1.10. There is a universal constant C ∈ (0, ∞) with the following property. Fix p, Γ ∈ [1, ∞) and suppose that (X, d_{X}) is a metric space that is W_{p} barycentric with constant Γ and p-barycentric with constant K = 1. Then for every n, t ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ_{+} (A^{t}, d_{X}^{p}) ⩽ (CΓ)^{p} (max \{1, p · \frac{γ_{+}(A, d_{X}^{p})}{t}\})^{p} .

Our proof of Theorem 1.10 relies on ideas from [43, Sec. 6], where a similar treatment is given to uniformly convex Banach spaces (in this special context the conclusion of Theorem 1.10 holds true even without the restriction K = 1). In the present nonlinear setting several modifications of the argument of [43] are required; see Section 4 below.

1.5. Lipschitz extension. If (X, d_{X}) and (Y, d_{Y}) are metric spaces then for every S ⊆ X denote by e(X, S, Y) the infimum over those L ∈ (0, ∞) such that for every Lipschitz function f : S → Y there exists F : X → Y with F (x) = f(x) for every x ∈ S such that ∥F ∥_{Lip} ⩽ L∥f∥_{Lip}, where ∥f∥_{Lip} denotes the Lipschitz constant of f. If no such L exists then set e(X, S, Y) = ∞.

Defining

e(X, Y) =^{def} sup {e(X, S, Y) : S ⊆ X} ,

the goal of the Lipschitz extension problem is to understand which pairs of metric spaces (X, d_{X}), (Y, d_{Y}) satisfy e(X, Y) < ∞, and, when that happens, to obtain good bounds on e(X, Y). Due to its intrinsic importance as well as many applications in analysis and geometry, the Lipschitz extension problem has been extensively investigated over the past century. We shall not attempt to indicate the vast literature on this topic, referring instead to the book [11] and the references therein.

K. Ball introduced [3] the notions of Markov type and cotype in order to prove an important Lipschitz extension theorem known today as Ball’s extension theorem. Based on Ball’s ideas in [3], the following result is proved in Section 5.

Theorem 1.11 (generalized Ball extension theorem). Fix p, Γ ∈ [1, ∞). Let (X, d_{X}) be a metric space of Markov type p and let (Y, d_{Y}) be a metric space of metric Markov cotype p that is W_{p} barycentric with constant Γ. Suppose that Z ⊆ X and f : Z → Y is Lipschitz. Then for every finite subset S ⊆ X there exists F : S → Y with F |_{S∩Z} = f|_{S∩Z} and

∥F ∥_{Lip} ≲ ΓM_{p}(X)N_{p}(Y)∥f∥_{Lip}.  (8)

By combining Theorem 1.11 with Theorem 1.5 we deduce the following Lipschitz extension result.

Corollary 1.12. Fix p, K, Γ ∈ [1, ∞). Suppose that (X, d_{X}) is a metric space of Markov type p and that (Y, d_{Y}) is a metric space that is W_{p} barycentric with constant Γ and also p-barycentric with constant K. Suppose that Z ⊆ X and f : Z → Y is Lipschitz. Then for every finite subset S ⊆ X there exists F : S → Y with F |_{S∩Z} = f|_{S∩Z} and

∥F ∥_{Lip} ≲ Γ^{2}KM_{p}(X)∥f∥_{Lip}.

In [3] Ball obtained the conclusion of Theorem 1.11 when Y is a Banach space, under the assumption that it satisfies a certain linear invariant that he called Markov cotype 2. He also proved that Banach spaces that admit an equivalent norm whose modulus of uniform convexity has power type 2 satisfy this assumption.

In [3, Sec. 6], Ball proposed a way to define Markov cotype 2 for metric spaces: he first defined a bi-Lipschitz invariant of metric spaces that he called “approximate convexity”, and for approximately convex metric spaces he defined a notion of metric Markov cotype which is the same as (2), except that in the right hand side of (2) the Cesàro average of A is replaced by a certain Green’s matrix corresponding to A. The precise formulation of these concepts is recalled in Section 7, where we show that Ball’s notion of metric Markov cotype coincides with the notion of metric Markov cotype as in Definition 2. Our contribution here is to show that Ball’s strategy yields the desired Lipschitz extension result, with the following differences: the W_{p} barycentric condition is used in a key duality step (Lemma 5.2 below), and Lemma 5.1 below removes the need to use the notion of approximate convexity. Other than these changes and some expository simplifications, Section 5 is nothing more than a realization of Ball’s plan as he originally envisaged it.

Theorem 1.11 yields an extension of f to finitely many additional points, with a bound on the Lipschitz constant that is independent of the number of the additional points. This result is the main geometric content of the Lipschitz extension phenomenon studied here, but using standard arguments one can formally deduce from Theorem 1.11 bona fide solutions of the Lipschitz extension problem.

Specifically, let I denote the set of all finite subsets of X and let 𝒰 be a free ultrafilter on I. Denoting by Y_{𝒰} the associated ultrapower of Y (see [30] for background on ultrapowers of metric spaces), Y is canonically embedded in Y_{𝒰} and it follows formally from Theorem 1.11 that there exists a mapping Φ : X → Y_{𝒰} that extends f and satisfies (8). If for some λ ∈ [1, ∞) there were a λ-Lipschitz retraction from Y_{𝒰} onto Y, then by composing Φ with this retraction we would deduce that

e(X, Y) ≲ λΓM_{p}(X)N_{p}(Y).  (9)

If Y is Banach space then Y_{𝒰} is also a Banach space, and, as proved in [22], it follows from the principle of local reflexivity [38, 25] that there is a linear isometry T : Y^{∗∗} → Y_{𝒰} such that T (Y^{∗∗}) contains the canonical image of Y in Y_{𝒰} , and there is a norm 1 projection of Y_{𝒰} onto T (Y^{∗∗}). It therefore follows from Theorem 1.11 that

e(X, Y^{∗∗}) ≲ M_{p}(X)N_{p}(Y).

If in addition there is a λ-Lipschitz retraction from Y^{∗∗} onto Y then it would follow that (9) holds true (with Γ = 1).

It is a long standing open problem whether for every separable Banach space Y there is a Lipschitz retraction from Y^{∗∗} onto Y, but in the nonseparable setting it has been recently proved by Kalton [28] that this need not hold true. A dual Banach space is always canonically norm 1 complemented in its bi-dual, and in [29, Sec. 5] Kalton proved that if Y either has an unconditional finite dimensional decomposition (UFDD) or is a separable order continuous Banach lattice then there is a Lipschitz retraction from Y^{∗∗} onto Y.

If Y is a complete CAT (0) metric space then so is Y_{𝒰} , and moreover Y is a closed convex subset of Y_{𝒰} . In this case there is a 1-Lipschitz retraction from Y_{𝒰} onto Y (the nearest point map); see [9, Ch. II.2].

The above discussion yields a variety of target spaces Y for which the assumptions of Theorem 1.11 implies that e(X, Y) < ∞. We single out in particular the following statement.

Corollary 1.13. Under the assumptions of Theorem 1.11, if in addition Y is a dual Banach space then e(X, Y) ≲ M_{p}(X)N_{p}(Y). If p = 2 and Y is a complete CAT (0) metric space then e(X, Y) ≲ M_{2}(X).

The Markov type of several important classes of metric spaces has been computed in the literature, and when one takes (X, d_{X}) to be one of those spaces Corollary 1.13 becomes a versatile Lipschitz extension theorem that encompasses a wide range of seemingly disparate Lipschitz extension results, that have been previously proved mostly via completely different methods.

Specifically, in [50] it was proved that Banach spaces that admit an equivalent norm whose modulus of uniform smoothness has power type p have Markov type p. It was also proved in [50] that trees, hyperbolic groups, complete simply connected Riemannian manifolds of pinched sectional curvature and Laakso graphs all have Markov type 2, and that spaces that admit a padded random partition (see [36]), in particular doubling metric spaces and planar graphs, have Markov type p for all p ∈ (0, 2). In [10] it was shown that series parallel graphs have Markov type 2, and finally in the recent work [13] it was shown that spaces that admit a padded random partition have Markov type 2. Thus, in particular, doubling spaces and planar graphs have Markov type 2. In [52] it was shown that spaces with finite Nagata dimension admit a padded random partition, and so by [13] they too have Markov type 2. In [55] it was shown that Aleksandrov spaces of nonnegative curvature have Markov type 2, and in [1] the Markov type of certain Wasserstein spaces was computed.

In light of these results, taking as an example the case when (Y, d_{Y}) is a Hadamard space in Corollary 1.13, we see that if (X, d_{X}) is a doubling space, planar graph, or a space with finite Nagata dimension, then e(X, Y) is finite. These results were previously proved in [36] via the method of random partitions (Lipschitz extension for spaces of bounded Nagata dimension was previously treated in [34] and only later it was shown in [52] that they admit a padded random partition and therefore the corresponding extension results are a special case of [36]). It also follows that if (X, d_{X}) has nonnegative curvature in the sense of Aleksandrov and (Y, d_{Y}) is a Hadamard space then e(X, Y) ≲ 1, a result that has been previously proved in [35], as a special case of an elegant generalization of the classical Kirszbraun extension theorem [31].

Given a metric space (X, d_{X}) and α ∈ (0, 1] let X^{α} denote the metric space (X, d_{X}^{α}). By the triangle inequality X^{α} has Markov type p with constant 1 for every p ∈ (1, 1/α]. It therefore follows from the above discussion that e(X^{α}, Y) < ∞ for every metric space X, provided that Y has metric Markov cotype p ∈ (1, 1/α] and there is a Lipschitz retraction from Y_{𝒰} onto Y. In particular, every 1/2-Hölder mapping from a subset of a metric space X into a Hadamard space Y can be extended to a Y -valued 1/2-Hölder mapping defined on all of X; this statement was previously known when Y is a Hilbert space due to the work of Minty [47]. One can state several additional examples of this type, but we single out only one more special case of Corollary 1.13 that does not seem to follow from previously known theorems: if X is a Banach space whose modulus of smoothness has power type 2 (thus by [50] X has Markov type 2), e.g. X can be an L_{p}(μ) space or the Schatten trace class S_{p} for p ∈ [2, ∞), and Y is a Hadamard space, then e(X, Y) < ∞.

1.6. On a construction of Kalton. Kalton recently used his “method of sections” to obtain several striking results on the nonlinear geometry of Banach spaces. Using Kalton’s beautiful work in [29], we prove the following result in Section 6.

Theorem 1.14. There exists a closed linear subspace of ℓ_{1} that fails to have metric Markov cotype p for every p ∈ (0, ∞).

Much of the impetus for research on bi-Lipschitz invariants stems from the search for nonlinear formulations of key concepts in Banach space theory; see the surveys [4, 49] and the references therein for more on this program. In particular, the use of the term “cotype” in Definition 1.2 arises from an analogy with the Banach space notion of Rademacher cotype (see e.g. [41]). ℓ_{1}, and hence all of its linear subspaces, has Rademacher cotype 2, so Theorem 1.14 shows that for Banach spaces metric Markov cotype and Rademacher cotype are different notions. Nevertheless, it would be very interesting to understand the metric Markov cotype of ℓ_{1} itself rather than its closed subspaces (note that, due to the existential quantifier in Definition 1.2, metric Markov cotype is not trivially inherited by subspaces).

Question 1.15. Does ℓ_{1} have metric Markov cotype 2? Less ambitiously, does ℓ_{1} have metric Markov cotype p for some p ∈ [2, ∞)?

If ℓ_{1} had metric Markov cotype 2 then it would follow from Corollary 1.13 that e(ℓ_{2}, ℓ_{1}) < ∞. Whether or not e(ℓ_{2}, ℓ_{1}) is finite is a long-standing open question that was asked by Ball in [3]; see [39] for algorithmic ramifications of this important question.

The proof of Theorem 1.14 yields the following quantitative statement. For every n ∈ ℕ there exists an n-dimensional subspace Z_{n} of ℓ_{1} such that

N_{2}(Z_{n}) ≳ \sqrt[4]{log n}.  (10)

Any n-dimensional subspace X of ℓ_{1} satisfies N_{2}(X) ≲ \sqrt{log n}. Indeed, by [61] we know that X is 2-isomorphic to a subspace of ℓ_{1}^{k}, with k ≲ n log n (for our purpose we can also use the weaker bound on k of [58]). By Hölder’s inequality ℓ_{1}^{k} is O(1)-isomorphic to a subspace of ℓ_{p} with p = 1 + 1/ log k, so the desired upper bound on N_{2}(X) follows from [3, 43]. We ask whether (10) can be sharpened.

Question 1.16. Is it true that for arbitrarily large n ∈ ℕ there exists an n-dimensional subspace X of ℓ_{1} with N_{2}(X) ≳ \sqrt{log n}?

An interesting byproduct of our quantitative analysis of Kalton’s construction is that it shows for the first time that an old Lipschitz extension result of Benyamini, Johnson and Lindenstrauss [23] cannot be improved. Given ε ∈ (0, 1) and spaces (X, d_{X}), (Y, d_{Y}), denote

e_{ε}(X, Y)

=^{def} sup \{e(X, S, Y) : S ⊆ X, and inf_{\begin{matrix}x,y∈S \\ x≠y \end{matrix}} d_{X}(x, y) ⩾ ε diam(S)\} ,

where diam(S) = sup_{x,y∈S} d_{X}(x, y) is the diameter of S. In other words, we are interested in the extension of Y -valued Lipschitz functions from ε-separated subsets of X, where ε-separated means that all positive distances in the subset are at least an ε-fraction of its diameter.

In [23] it was shown that for every ε ∈ (0, 1), every metric space (X, d_{X}) and every Banach space (Y, d_{Y}) we have

e_{ε}(X, Y) ≲ \frac{1}{ε}.  (11)

Specifically, a first proof of (11) was given by Johnson and Lindenstrauss in [23] when Y is a Hilbert space, and in the appendix of the same paper Johnson and Lindenstrauss include a different argument that was subsequently found by Benyamini establishing (11) when Y is a general Banach space. A very short proof of (11) was later found by Johnson, Lindenstrauss and Schechtman [24].

Johnson and Lindenstrauss proved [23] that e_{ε}(ℓ_{1}, ℓ_{2}) ≳ 1/\sqrt[4]{ε}. Constructions of Johnson, Lindenstrauss and Schechtman [24] and Lang [32] yield the estimate e_{ε}(ℓ_{∞}, ℓ_{2}) ≳ 1/\sqrt[3]{ε}. Here we show that (11) is sharp up to absolute constant factors, even when X is Hilbert space and Y is an appropriately chosen closed subspace of ℓ_{1}.

Theorem 1.17. There exists a closed subspace Y of ℓ_{1} that satisfies e_{ε}(ℓ_{2}, Y) ≳ 1/ε for every ε ∈ (0, 1). Specifically, for every n ∈ ℕ there exists a 5^{n}-dimensional subspace Y_{n} of ℓ_{1} and a 1/\sqrt[4]{n} net N of the unit ball of ℓ_{2}^{n} such that e(ℓ_{2}^{n}, N , Y_{n}) ≳ \sqrt[4]{n}.

It would be very interesting to understand those pairs of Banach spaces X, Y for which e_{ε}(X, Y) = o(1/ε) as ε → 0. We do not even know if there exist Banach spaces X, Y such that e_{ε}(X, Y) = o(1/ε) yet e(X, Y) = ∞. Our interest in this natural question is partially motivated by the forthcoming work [2], where it is asked whether e_{ε}(ℓ_{1}, ℓ_{1}) = o(1/ε), and it is shown that a positive answer to this question would have applications to dimension reduction in ℓ_{1} (e.g., it is shown in [2] that if e_{ε}(ℓ_{1}, ℓ_{1}) = o(1/ε) then any n-point subset of ℓ_{1} embeds with distortion O(1) into some Banach space of dimension (log n)^{O(1)}). Due to Theorem 1.17, one is tempted to believe that in fact e_{ε}(ℓ_{1}, ℓ_{1}) ≳ 1/ε, but the present approach does not seem to shed light on this question.

2. Pisier’s martingale inequality in barycentric spaces

Martingales in metric spaces have been studied for several decades; see e.g. [14, 16, 17, 59, 12]. Here we will use a natural notion of martingale in barycentric metric spaces, the main goal being to extend an important martingale inequality of Pisier [57] from the setting of uniformly convex Banach spaces to the setting of barycentric metric spaces. This inequality will be used crucially in the proof of Theorem 1.5.

Let Ω be a finite set and μ ∈ 𝒫_{Ω} be a probability measure such that μ(ω) > 0 for every ω ∈ Ω. Suppose that (X, d_{X}) is a metric space and fix a barycenter map 𝔅 : 𝒫_{X} → X. Let F ⊆ 2^{Ω} be a σ-algebra. For every ω ∈ Ω let F(ω) ⊆ Ω be the unique atom of F to which ω belongs. Given an X-valued random variable Z : Ω → X, its conditional barycenter 𝔅(Z|F) : Ω → X is defined as

∀ ω ∈ Ω, 𝔅(Z|F)(ω) =^{def} 𝔅 (\frac{1}{μ(F(ω))} ∑_{a∈F(ω)} μ(a)δ_{Z(a)}) . (12)

If m ∈ ℕ and {Ω, ∅} = F_{0} ⊆ F_{1} ⊆ … ⊆ F_{m} ⊆ 2^{Ω} are increasing σ-algebras (a filtration) then a sequence of X-valued random variables Z_{0}, …, Z_{n} : Ω → X is said to be a martingale if for every i ∈ {1, …, m} we have 𝔅(Z_{i}|F_{i−1}) = Z_{i−1}. We warn that in contrast to the usual setting of martingales in Banach spaces, this definition does not necessarily imply that 𝔅(Z_{i}|F_{j}) = Z_{j} for every j ∈ {0, …, i−2}. Nevertheless, the above notion of martingale suffices to prove the following inequality.

Lemma 2.1 (Pisier’s inequality for barycentric spaces). Fix m ∈ ℕ, p, K ∈ [1, ∞) and a metric space (X, d_{X}) that is p-barycentric with constant K. Let Ω be a finite set and fix μ ∈ 𝒫_{Ω} with μ(ω) > 0 for every ω ∈ Ω. Suppose that {Ω, ∅} = F_{0} ⊆ F_{1} ⊆ … ⊆ F_{m} ⊆ 2^{Ω} is a filtration with respect to which Z_{0}, …, Z_{n} : Ω → X is an X-valued martingale. Then for every z ∈ X we have

K^{p}d_{X}(Z_{0}, z)^{p} + ∑_{t=0}^{m−1} ∫_{Ω} d_{X}(Z_{t+1}, Z_{t})^{p}dμ ⩽ K^{p} ∫_{Ω} d_{X}(Z_{m}, z)^{p}dμ. (13)

Proof. Fix t ∈ {0, …, m−1} and ω ∈ Ω. Recalling (12), an application of (4) to the probability measure \frac{1}{μ(F_{t}(ω))} ∑_{a∈F_{t}(ω)} μ(a)δ_{Z_{t+1}(a)} yields the estimate

d_{X}(Z_{t}(ω), z)^{p} + \frac{1}{K^{p}} ∑_{a∈F_{t}(ω)} \frac{μ(a)}{μ(F_{t}(ω))}d_{X}(Z_{t}(ω), Z_{t+1}(a))^{p}

⩽ ∑_{a∈F_{t}(ω)} \frac{μ(a)}{μ(F_{t}(ω))}d_{X}(z, Z_{t+1}(a))^{p}, (14)

where we used the martingale assumption Z_{t} = 𝔅(Z_{t+1}|F_{t}). Let A_{1}, …, A_{k} ∈ F_{t} be the distinct atoms of F_{t} and fix ω_{i} ∈ A_{i} for every i ∈ {1, …, k} (thus A_{i} = F_{t}(ω_{i})). It follows from (14) that for every i ∈ {1, …, k},

∑_{a∈A_{i}} μ(a)d_{X}(Z_{t}(ω_{i}), Z_{t+1}(a))^{p}

⩽ K^{p} (∑_{a∈A_{i}} μ(a)d_{X}(z, Z_{t+1}(a))^{p} − μ(A_{i})d_{X}(Z_{t}(ω_{i}), z)^{p}) . (15)

Since Z_{t} is constant on each of the sets A_{1}, …, A_{k}, by summing (15) over i ∈ {1, …, k} we obtain the estimate

\frac{1}{K^{p}} ∫_{Ω} d_{X}(Z_{t+1}, Z_{t})^{p}dμ ⩽ ∫_{Ω} d_{X}(Z_{t+1}, z)^{p}dμ − ∫_{Ω} d_{X}(Z_{t}, z)^{p}dμ. (16)

The desired inequality (13) now follows since the right hand side of (16) telescopes upon summation over t ∈ {0, …, m − 1}. □

3. Proof of Theorem 1.5

Throughout the remainder of this paper it will be convenient to use the following notation for Cesáro averages.

𝒜_{t}(A) =^{def} \frac{1}{t} ∑_{s=1}^{t} A^{s}.  (17)

The following simple lemma will be used in the proof of Theorem 1.5, as well as in Section 7.

Lemma 3.1. Fix p ∈ [1, ∞) and n, t ∈ ℕ. Suppose that A ∈ M_{n}(ℝ) is a stochastic matrix that is reversible relative to π ∈ Δ^{n−1}. Then for every metric space (X, d_{X}) and every x_{1}, …, x_{n} ∈ X,

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}.

Proof. By the triangle inequality, for every i, j, k ∈ {1, …, n} we have

d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p−1}(d_{X}(x_{i}, x_{k})^{p} + d_{X}(x_{k}, x_{j})^{p}).  (18)

Consequently,

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p}

= \frac{1}{t} ∑_{s=1}^{t} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i} (∑_{k=1}^{n}(A^{s})_{ik}(A^{t−s})_{kj}) d_{X}(x_{i}, x_{j})^{p}

⩽^{(18)} \frac{2^{p−1}}{t} ∑_{s=1}^{t} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} π_{i}(A^{s})_{ik}(A^{t−s})_{kj}(d_{X}(x_{i}, x_{k})^{p} + d_{X}(x_{k}, x_{j})^{p})

=^{(17)} 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i} (𝒜_{t}(A)_{ij} + \frac{t − 1}{t}𝒜_{t−1}(A)_{ij}) d_{X}(x_{i}, x_{j})^{p}

⩽ 2^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}.  □

Proof of Theorem 1.5. Fix p, K, Γ ∈ [1, ∞), a metric space (X, d_{X}) and a barycenter map 𝔅 : 𝒫_{X} → X with respect to which (X, d_{X}) is both W_{p} barycentric with constant Γ and p-barycentric with constant K. We also fix n, t ∈ ℕ, a probability vector π ∈ Δ^{n−1} and a stochastic matrix A = (a_{ij}) that is reversible relative to π. Given x_{1}, …, x_{n} ∈ X our goal is to prove that there exist y_{1}, …, y_{n} ∈ X such that (2) is satisfied with N ≲ ΓK.

In the proof of Theorem 1.5 we may assume that the right hand side of (2) is nonzero. By restricting to the support of π we may also assume that π ∈ (0, 1)^{n}. Letting Π ∈ M_{n}(ℝ) be given by Π_{ij} = π_{j}, choose ε ∈ (0, 1/2) small enough so that for B = (1−ε)A+εΠ we have

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(B)_{ij}d_{X}(x_{i}, x_{j})^{p} ≲ ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}.

Since B_{ij} ⩾ (1 − ε)a_{ij} ⩾ \frac{1}{2}a_{ij}, for every y_{1}, …, y_{n} ∈ X we have

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}B_{ij}d_{X}(y_{i}, y_{j})^{p}

≳ ∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p}.

Since the matrix B is stochastic and reversible relative to π and none of its entries vanish, this shows that it suffices to prove Theorem 1.5 under the assumption that π_{i}, a_{ij} > 0 for every i, j ∈ {1, …, n}.

Denote Ω = {1, …, n}^{t}. Set F_{0} = {∅, Ω} and for every s ∈ {1, …, t} let F_{s} ⊆ 2^{Ω} be the σ-algebra generated by the first s coordinates, i.e., the atoms of F_{s} are {E_{τ}}_{τ∈{1,...,n}^{s}}, where we denote for every (i_{1}, …, i_{s}) ∈ {1, …, n}^{s},

E_{(i_{1},...,i_{s})} =^{def} {(j_{1}, …, j_{t}) ∈ Ω : (j_{1}, …, j_{s}) = (i_{1}, …, i_{s})}.

Fix ℓ ∈ {1, …, n} and define μ_{ℓ} ∈ 𝒫_{Ω} on Ω by

∀ (i_{1}, …, i_{t}) ∈ Ω, μ_{ℓ}(i_{1}, …, i_{t}) =^{def} a_{ℓ,i_{1}} ∏_{s=1}^{t−1} a_{i_{s},i_{s+1}}.

Thus (Ω, μ_{ℓ}) is the probability space of trajectories of length t of the Markov chain on {1, …, n} that starts at ℓ and whose transition matrix is A. By definition, μ_{ℓ}(ω) > 0 for every ω ∈ Ω.

We next define inductively mappings M_{0}^{(ℓ,t)}, …, M_{t}^{(ℓ,t)} : Ω → X as follows. For every (i_{1}, …, i_{t}) ∈ Ω,

M_{t}^{(ℓ,t)}(i_{1}, …, i_{t}) =^{def} x_{i_{t}},

and for every s ∈ {0, …, t − 1},

M_{s}^{(ℓ,t)}(i_{1}, …, i_{t}) =^{def} 𝔅 (∑_{j=1}^{n} a_{i_{s},j} · δ_{M_{s+1}^{(ℓ,t)}(i_{1},...,i_{s},j,1...,1)}) , (19)

where i_{0} = ℓ. Thus M_{s}^{(ℓ,t)}(i_{1}, …, i_{t}) depends only on (i_{1}, …, i_{s}). We may therefore think of M_{s}^{(ℓ,t)} as an X-valued function defined on {1, …, n}^{s}, and M_{0}^{(ℓ,t)} as a point in X.

Definition (19) implies that for s ∈ {0, …, t} and (i_{1}, …, i_{t}) ∈ Ω,

M_{s}^{(ℓ,t)}(i_{1}, …, i_{t}) = M_{0}^{(i_{s},t−s)}.  (20)

Moreover, recalling (12) it follows from (19) that for s ∈ {0, …, t − 1},

M_{s}^{(ℓ,t)} = 𝔅 (M_{s+1}^{(ℓ,t)}| F_{s}) .

Thus M_{0}^{(ℓ,t)}, …, M_{t}^{(ℓ,t)} is an X-valued martingale with respect to the measure μ_{ℓ} and the filtration F_{0} ⊆ …, ⊆ F_{t} = 2^{Ω}. An application of Lemma 2.1 (with z = x_{ℓ}) therefore yields the following estimate.

∑_{s=1}^{t} ∑_{i=1}^{n}(A^{s−1})_{ℓ,i} ∑_{j=1}^{n} a_{ij}d_{X} (M_{0}^{(i,t−s+1)}, M_{0}^{(j,t−s)})^{p}

⩽ K^{p} (∑_{j=1}^{n}(A^{t})_{ℓj}d_{X} (x_{j}, x_{ℓ})^{p} − d_{X} (x_{ℓ}, M_{0}^{(ℓ,t)})^{p}) . (21)

Multiplying (21) by π_{ℓ} and summing over ℓ ∈ {1, …, n} while using the fact that A^{s−1} is stochastic and reversible relative to π shows that

∑_{s=1}^{t} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X} (M_{0}^{(i,s)}, M_{0}^{(j,s−1)})^{p}

⩽ K^{p} (∑_{ℓ=1}^{n} ∑_{j=1}^{n} π_{ℓ}(A^{t})_{ℓj}d_{X}(x_{ℓ}, x_{j})^{p} − ∑_{ℓ=1}^{n} π_{ℓ}d_{X} (x_{ℓ}, M_{0}^{(ℓ,t)})^{p} ) . (22)

In order to bound the left hand side of (22) from below, observe that for every i, j ∈ {1, …, n} condition (3) of our assumption that (X, d_{X}) is W_{p} barycentric with constant Γ implies that

∑_{s=1}^{t} d_{X} (M_{0}^{(i,s)}, M_{0}^{(j,s−1)})^{p}

⩾ \frac{t}{Γ^{p}} d_{X} (𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(i,s)}}) , 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s−1)}}))^{p} . (23)

18 MANOR MENDEL AND ASSAF NAOR

Moreover, by the triangle inequality and convexity of u ↦ u^{p} on [0, ∞),

d_{X} (𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(i,s)}}) , 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s)}}))^{p}

⩽ 2^{p−1}d_{X} (𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(i,s)}}) , 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s−1)}}))^{p}

+ 2^{p−1}d_{X} (𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s)}}) , 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s−1)}}))^{p} . (24)

Another application of (3) shows that

d_{X} (𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s)}}) , 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(j,s−1)}}))

⩽ \frac{Γ}{t^{1/p}} d_{X} (M_{0}^{(j,t)}, M_{0}^{(j,0)}) = \frac{Γ}{t^{1/p}} d_{X} (M_{0}^{(j,t)}, x_{j}) . (25)

Consequently, if we define

y_{i} =^{def} 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(i,s)}}) ,  (26)

then it follows from (23), (24) and (25) that

∑_{s=1}^{t} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X} (M_{0}^{(i,s)}, M_{0}^{(j,s−1)})^{p}

⩾ \frac{2t}{(2Γ)^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p} − ∑_{j=1}^{n} π_{j}d_{X} (M_{0}^{(j,t)}, x_{j})^{p} . (27)

A substitution of (27) into (22) now yields the following estimate.

t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p}

⩽ \frac{(2ΓK)^{p}}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p}

− 2^{p−1}Γ^{p} (K^{p} − 1) ∑_{j=1}^{n} π_{j}d_{X} (M_{0}^{(j,t)}, x_{j})^{p}

⩽ \frac{(2ΓK)^{p}}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p}.  (28)

By combining (28) and Lemma 3.1 we deduce that

t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p} ⩽ (4ΓK)^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}. (29)

Next, we need to bound the quantity ∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p}. We first claim that for every i ∈ {1, …, n}, every s ∈ {0, …, t} and every z ∈ X we have

d_{X} (z, M_{0}^{(i,t)})^{p} ⩽ ∑_{j=1}^{n}(A^{s})_{ij}d_{X} (z, M_{0}^{(j,t−s)})^{p} .  (30)

The proof of (30) is by induction on s. For s = 0 the desired inequality (30) holds as equality. Assuming the validity of (30) for some s ∈ {0, …, t − 1}, and recalling (19) and (20), observe that for every j ∈ {1, …, n} we have

M_{0}^{(j,t−s)} = 𝔅 (∑_{k=1}^{n} a_{jk}δ_{M_{0}^{(k,t−s+1)}}) .

Consequently, it follows from (4) that

d_{X} (z, M_{0}^{(j,t−s)})^{p} ⩽ ∑_{k=1}^{n} a_{jk}d_{X} (z, M_{0}^{(k,t−s+1)})^{p} .  (31)

So,

d_{X} (z, M_{0}^{(i,t)})^{p} ⩽^{(30)∧(31)} ∑_{j=1}^{n}(A^{s})_{ij} ∑_{k=1}^{n} a_{jk}d_{X} (z, M_{0}^{(k,t−s+1)})^{p}

= ∑_{k=1}^{n}(A^{s+1})_{ik}d_{X} (z, M_{0}^{(k,t−s+1)})^{p} ,

thus completing the inductive verification of (30).

When s = t inequality (30) becomes

d_{X} (z, M_{0}^{(i,t)})^{p} ⩽ ∑_{j=1}^{n}(A^{t})_{ij}d_{X} (z, x_{j})^{p} .  (32)

Hence, for every i ∈ {1, …, n},

d_{X}(x_{i}, y_{i})^{p} =^{(26)} d_{X} (x_{i}, 𝔅 (\frac{1}{t} ∑_{s=1}^{t} δ_{M_{0}^{(i,s)}}))^{p} ⩽^{(4)} \frac{1}{t} ∑_{s=1}^{t} d_{X} (x_{i}, M_{0}^{(i,s)})^{p}

⩽^{(32)} \frac{1}{t} ∑_{s=1}^{t} ∑_{j=1}^{n}(A^{s})_{ij}d_{X} (x_{i}, x_{j})^{p} =^{(17)} ∑_{j=1}^{n} 𝒜_{t}(A)_{ij}d_{X} (x_{i}, x_{j})^{p} .

Consequently,

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} ⩽ ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X} (x_{i}, x_{j})^{p} .  (33)

By summing (29) and (33) we conclude that the desired inequality (2) holds true with y_{1}, …, y_{n} chosen as in (26) and N^{p} = (4ΓK)^{p} +1. This completes the proof of Theorem 1.5. □

4. Proof of Theorem 1.10

Theorem 1.10 is a consequence of Lemma 4.2 and Lemma 4.3 below. These lemmas are meaningful without the restriction K = 1 of Theorem 1.10: this more stringent assumption will only be used later, when we combine Lemma 4.2 and Lemma 4.3 to deduce Theorem 1.10.

In order to state our results we need to first introduce a small amount of notation. Given a metric space (X, d_{X}) and p ∈ [1, ∞), for every n ∈ ℕ we denote by L_{p}^{n}(X) the space of all function f : {1, …, n} → X, equipped with the metric

∀ f, g ∈ L_{p}^{n}(X), d_{L_{p}^{n}(X)}(f, g) =^{def} (\frac{1}{n} ∑_{i=1}^{n} d_{X}(f(i), g(i))^{p})^{1/p} .

Suppose that 𝔅 : 𝒫_{X} → X is a barycenter map. In what follows it will be convenient to use the following slight abuse of notation: for every f : {1, …, n} → X write

𝔅(f) =^{def} 𝔅 (\frac{1}{n} ∑_{i=1}^{n} δ_{f(i)}) .

For a symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) define a mapping A ⊗ I_{X}^{n} : L_{p}^{n}(X) → L_{p}^{n}(X) by setting for every i ∈ {1, … n} and f : {1, …, n} → X,

(A ⊗ I_{X}^{n})(f)(i) =^{def} 𝔅 (∑_{j=1}^{n} a_{ij}δ_{f(j)}) .

We warn that, unlike in the setting of Banach space valued mappings, given two symmetric stochastic matrices A, B ∈ M_{n}(ℝ) the composition (A ⊗ I_{X}^{n}) ∘ (B ⊗ I_{X}^{n}) need not be of the form C ⊗ I_{X}^{n} for some symmetric stochastic matrix C ∈ M_{n}(ℝ), and in particular the identity (A ⊗ I_{X}^{n}) ∘ (B ⊗ I_{X}^{n}) = (AB) ⊗ I_{X} need not hold true.

Definition 4.1. Fix p ∈ [1, ∞) and a metric space (X, d_{X}) equipped with a barycenter map 𝔅 : 𝒫_{X} → X. Given T : L_{p}^{n}(X) → L_{p}^{n}(X), define λ_{p}(T) ∈ [0, ∞] to be the infimum over those λ ∈ (0, ∞] for which every f ∈ L_{p}^{n}(X) satisfies

d_{L_{p}^{n}(X)} (T (f), 𝔅 (T (f))) ⩽ λ · d_{L_{p}^{n}(X)} (f, 𝔅(f)) .

Lemma 4.2 below relates the quantities γ_{+}(A^{t}, d_{X}^{p}) and λ_{p} (A ⊗ I_{X}^{n}). Note that it assumes that (X, d_{X}) is p-barycentric with constant K, but K does not appear in the conclusion (34). The reason for this is that the proof of Lemma 4.2 uses a weaker version of (4) in which the rightmost term on the left hand side of (4) is dropped, i.e., the assumption that (X, d_{X}) is p-barycentric with constant K is used in Lemma 4.2 only through the requirement that every μ ∈ 𝒫_{X} satisfies

∀ x ∈ X, d_{X}(x, 𝔅(μ))^{p} ⩽ ∫_{X} d_{X}(x, y)^{p}dμ(y).

Lemma 4.2. Fix p, K, Γ ∈ [1, ∞) and n, t ∈ ℕ. Suppose that (X, d_{X}) is a metric space that is both W_{p} barycentric with constant Γ and pbarycentric with constant K. Let A = (a_{ij}) ∈ M_{n}(ℝ) be a symmetric stochastic matrix such that λ_{p} (A ⊗ I_{X}^{n}) < 1. Then

γ_{+}(A^{t}, d_{X}^{p}) ⩽ (Γ + \frac{4(Γ + 1)}{1 − λ_{p} (A ⊗ I_{X}^{n})^{2t}} )^{p} .  (34)

In what follows, for p, K ∈ [1, ∞) we denote by β_{p}(K) the unique β ∈ [1, ∞) satisfying

β^{p} + K^{p}(β − 1)^{p} = K^{p}.  (35)

Thus in particular,

β_{2}(K) = \frac{2K^{2}}{K^{2} + 1}.

Observe that β_{p}(K) ∈ [1, min{K, 2}] and β_{p}(K) = 1 if and only if K = 1. We also have

β_{p}(K) = max_{β∈[1,2]} min {β, K (1 − (β − 1)^{p})^{1/p}} .  (36)

To verify (36) note that the function β ↦ K (1 − (β − 1)^{p})^{1/p} decreases from K to 0 on [1, 2], so the maximum that appears in (36) is attained when β = K (1 − (β − 1)^{p})^{1/p}, or, due to (35), when β = β_{p}(K). An equivalent way to state (36) is that for every a ∈ [0, ∞) we have

0 ⩽ b ⩽ a ⟹ min {a + b, K (a^{p} − b^{p})^{1/p}} ⩽ β_{p}(K)a.  (37)

To deduce (37) from (36) simply write b = (β − 1)a for some β ∈ [1, 2].

Lemma 4.3. Fix p, K ∈ [1, ∞) and n ∈ ℕ. Suppose that (X, d_{X}) is a p-barycentric metric space with constant K. Then every symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) satisfies

λ_{p} (A ⊗ I_{X}^{n}) ⩽ β_{p}(K) (\frac{K^{2p}γ_{+}(A, d_{X}^{p}) − 1}{K^{2p}γ_{+}(A, d_{X}^{p}) + K^{p}} )^{1/p} .

Assuming the validity of Lemma 4.2 and Lemma 4.3 for the moment, we now show how they imply Theorem 1.10.

Proof of Theorem 1.10. We are now assuming that (X, d_{X}) is both W_{p} barycentric with constant Γ and p-barycentric with constant K = 1. Under the latter assumption the conclusion of Lemma 4.3 becomes

λ_{p} (A ⊗ I_{X}^{n}) ⩽ (\frac{γ_{+}(A, d_{X}^{p}) − 1}{γ_{+}(A, d_{X}^{p}) + 1})^{1/p} .  (38)

Thus in particular λ_{p} (A ⊗ I_{X}^{n}) < 1, so we may use Lemma 4.2 in conjunction with (38) to obtain the estimate

γ_{+}(A^{t}, d_{X}^{p})^{1/p} ≲ \frac{Γ}{1 − (\frac{γ_{+}(A,d_{X}^{p})−1}{γ_{+}(A,d_{X}^{p})+1})^{2t/p}} .

It now remains to note the elementary inequality

∀ p, γ, t ∈ [1, ∞), 1 − (\frac{γ − 1}{γ + 1})^{2t/p} ≳ min \{1, \frac{t}{pγ} \} ,

which follows by considering the cases t ⩾ pγ and t ⩽ pγ separately. □

We now proceed to prove Lemma 4.2 and Lemma 4.3. To this end, given n, t ∈ ℕ and T : L_{p}^{n}(X) → L_{p}^{n}(X), we denote the t-fold iterate of T by T^{[t]}, i.e.,

T^{[t]} =^{def} \underbrace{T ∘ … ∘ T}_{t times} .

We also use the convention that T^{[0]} is the identity mapping. If X is a Banach space then (A ⊗ I_{X}^{n})^{[t]} = A^{t} ⊗ I_{X}^{n}, but this need not hold true when X is not a Banach space. Observe that a direct iterative application of Definition 4.1 implies that

λ_{p} (T^{[t]}) ⩽ λ_{p}(T)^{t}.  (39)

Lemma 4.4. Fix p, K ∈ [1, ∞). Suppose that (X, d_{X}) is a p-barycentric metric space with constant K. Then for every n, t ∈ ℕ, every symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) and every f ∈ L_{p}^{n}(X),

d_{L_{p}^{n}(X)} (f, (A ⊗ I_{X}^{n})^{[t]}(f))^{p} ⩽ \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), f(j))^{p}. (40)

Proof. We will prove by induction on t that if B = (b_{ij}) ∈ M_{n}(ℝ) has nonnegative entries then

∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t]}(f)(j))^{p}

⩽ ∑_{i=1}^{n} ∑_{j=1}^{n}(BA^{t})_{ij}d_{X}(f(i), f(j))^{p}. (41)

The desired inequality (40) is then the special case of (41) when B is the identity matrix.

(41) holds as equality when t = 0, so assume inductively that (41) holds true for some t ∈ ℕ ∪ {0}. Fix i, j ∈ {1, …, n} and consider the probability measure μ_{j} ∈ 𝒫_{X} given by

μ_{j} =^{def} ∑_{k=1}^{n} a_{jk}δ_{(A⊗I_{X}^{n})^{[t]}(f)(k)}.

Then 𝔅(μ_{j}) = (A ⊗ I_{X}^{n})^{[t+1]}(f)(j). By (4) with μ = μ_{j} and x = f(i),

d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t+1]}(f)(j))^{p}

⩽ ∑_{k=1}^{n} a_{jk}d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t]}(f)(k))^{p} . (42)

Hence,

∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij}d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t+1]}(f)(j))^{p}

⩽ ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ij} ∑_{k=1}^{n} a_{jk}d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t]}(f)(k))^{p}  (43)

= ∑_{i=1}^{n} ∑_{k=1}^{n}(BA)_{ik}d_{X} (f(i), (A ⊗ I_{X}^{n})^{[t]}(f)(k))^{p}

⩽ ∑_{i=1}^{n} ∑_{k=1}^{n}(BA^{t+1})_{ik}d_{X}(f(i), f(k))^{p},  (44)

where in (43) uses (42) and (44) uses the inductive hypothesis. □

Lemma 4.5. Fix p, Γ ∈ [1, ∞). Suppose that (X, d_{X}) is a W_{p} barycentric metric space with constant Γ. Then for every f, g ∈ L_{p}^{n}(X),

|d_{L_{p}^{n}(X)}(f, 𝔅(f)) − d_{L_{p}^{n}(X)}(g, 𝔅(g))| ⩽ (Γ + 1)d_{L_{p}^{n}(X)}(f, g). (45)

Proof. By (3) we have

d_{X}(𝔅(f), 𝔅(g)) ⩽ Γ · d_{L_{p}^{n}(X)}(f, g).  (46)

By the triangle inequality in L_{p}^{n}(ℝ) we have

|d_{L_{p}^{n}(X)}(f, 𝔅(f)) − d_{L_{p}^{n}(X)}(g, 𝔅(g))|

⩽ (\frac{1}{n} ∑_{i=1}^{n} |d_{X}(f(i), 𝔅(f)) − d_{X}(g(i), 𝔅(g))|^{p})^{1/p} . (47)

For every i ∈ {1, …, n} the triangle inequality in (X, d_{X}) implies that

|d_{X}(f(i), 𝔅(f)) − d_{X}(g(i), 𝔅(g))| ⩽ d_{X}(f(i), g(i)) + d_{X}(𝔅(f), 𝔅(g)).

In combination with (47) and another application of the triangle inequality in L_{p}^{n}(ℝ) we deduce that

|d_{L_{p}^{n}(X)}(f, 𝔅(f)) − d_{L_{p}^{n}(X)}(g, 𝔅(g))| ⩽ d_{L_{p}^{n}(X)}(f, g) + d_{X}(𝔅(f), 𝔅(g)).

Due to (46), this implies the desired inequality (45). □

Lemma 4.6. Fix p, K, Γ ∈ [1, ∞) and n, t ∈ ℕ. Suppose that (X, d_{X}) is a metric space that is both W_{p} barycentric with constant Γ and pbarycentric with constant K. Let A ∈ M_{n}(ℝ) be a symmetric stochastic matrix such that λ_{p} ((A ⊗ I_{X}^{n})^{[2t]}) < 1. Then

γ_{+}(A^{t}, d_{X}^{p}) ⩽ (Γ + \frac{4(Γ + 1)}{1 − λ_{p} ((A ⊗ I_{X}^{n})^{[2t]})})^{p} .  (48)

Proof. For every f, g : {1, …, n} → X we have

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(f(i), g(j))^{p})^{1/p}

⩽ d_{X}(𝔅(f), 𝔅(g)) + d_{L_{p}^{n}(X)}(f, 𝔅(f)) + d_{L_{p}^{n}(X)}(g, 𝔅(g)). (49)

We proceed to bound each of the terms on the right hand side of (49) separately.

First, define μ_{f}, μ_{g} ∈ 𝒫_{X} by

μ_{f} =^{def} \frac{1}{n} ∑_{i=1}^{n} δ_{f(i)} and μ_{g} =^{def} \frac{1}{n} ∑_{i=1}^{n} δ_{g(i)}.

Then 𝔅(f) = 𝔅(μ_{f}) and 𝔅(g) = 𝔅(μ_{g}). If we define π ∈ 𝒫_{X×X} by

π = \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}δ_{(f(i),g(j))},

then, since A^{t} is a symmetric stochastic matrix, π ∈ Π(μ_{f}, μ_{g}), i.e., π is a coupling of μ_{f} and μ_{g}. It therefore follows from (3) that

d_{X}(𝔅(f), 𝔅(g)) ⩽ Γ (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), g(j))^{p})^{1/p} . (50)

Next, since

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})^{[2t]}(f), 𝔅 ((A ⊗ I_{X}^{n})^{[2t]}(f))) ⩽ λ_{p} ((A ⊗ I_{X}^{n})^{[2t]}) d_{L_{p}^{n}(X)}(f, 𝔅(f)),

and λ_{p} ((A ⊗ I_{X}^{n})^{[2t]}) < 1, we have

\frac{d_{L_{p}^{n}(X)}(f, 𝔅(f)) − d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})^{[2t]}(f), 𝔅 ((A ⊗ I_{X}^{n})^{[2t]}(f)))}{1 − λ_{p} ((A ⊗ I_{X}^{n})^{[2t]})}

⩾ d_{L_{p}^{n}(X)}(f, 𝔅(f)). (51)

Now,

d_{L_{p}^{n}(X)}(f, 𝔅(f)) − d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})^{[2t]}(f), 𝔅 ((A ⊗ I_{X}^{n})^{[2t]}(f)))
⩽ (Γ + 1)d_{L_{p}^{n}(X)} (f, (A ⊗ I_{X}^{n})^{[2t]}(f))  (52)
⩽ (Γ + 1) (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{2t})_{ij}d_{X}(f(i), f(j))^{p})^{1/p} .  (53)

where (52) uses Lemma 4.5 and (53) uses Lemma 4.4.

Observe that

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{2t})_{ij}d_{X}(f(i), f(j))^{p}

= ∑_{i=1}^{n} ∑_{j=1}^{n} (∑_{k=1}^{n}(A^{t})_{ik}(A^{t})_{kj}) d_{X}(f(i), f(j))^{p}

⩽ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n}(A^{t})_{ik}(A^{t})_{kj}(d_{X}(f(i), g(k))^{p} + d_{X}(g(k), f(j))^{p})

= 2^{p} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), g(j))^{p}.  (54)

By combining (51) with (53) and (54) we have,

d_{L_{p}^{n}(X)}(f, 𝔅(f))

⩽ \frac{2(Γ + 1)}{1 − λ_{p} ((A ⊗ I_{X}^{n})^{[2t]})} (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), g(j))^{p})^{1/p} . (55)

By the same reasoning,

d_{L_{p}^{n}(X)}(g, 𝔅(g))

⩽ \frac{2(Γ + 1)}{1 − λ_{p} ((A ⊗ I_{X}^{n})^{[2t]})} (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), g(j))^{p})^{1/p} . (56)

Finally, a substitution of (50), (55) and (56) into (49) shows that

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(f(i), g(j))^{p}

⩽ (Γ + \frac{4(Γ + 1)}{1 − λ_{p} ((A ⊗ I_{X}^{n})^{[2t]})})^{p} · \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(f(i), g(j))^{p}. (57)

Since (57) holds true for every f, g : {1, …, n} → X, the desired estimate (48) now follows by recalling the definition of γ_{+}(A, d_{X}^{p}). □

Proof of Lemma 4.2. The desired estimate (34) is a consequence of (39) and Lemma 4.6. □

We now proceed to prove Lemma 4.3. Recalling the definition of β_{p}(K) in (35), we first establish the following estimate.

Lemma 4.7. Fix p, K ∈ [1, ∞). Suppose that (X, d_{X}) is a p-barycentric metric space with constant K. Then for every n ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) and every f ∈ L_{p}^{n}(X) we have

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅 ((A ⊗ I_{X}^{n})(f))) ⩽ β_{p}(K) · d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f)) . (58)

Proof. Write

a =^{def} d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f)) ,  (59)

and

b =^{def} d_{L_{p}^{n}(X)} (𝔅(f), 𝔅 ((A ⊗ I_{X}^{n})(f))) .  (60)

Then by the triangle inequality in L_{p}^{n}(X),

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅 ((A ⊗ I_{X}^{n})(f))) ⩽ a + b.  (61)

Next, define ν ∈ 𝒫_{X} by

ν =^{def} \frac{1}{n} ∑_{i=1}^{n} δ_{(A⊗I_{X}^{n})(f)(i)}.  (62)

Then

𝔅(ν) = 𝔅 ((A ⊗ I_{X}^{n})(f)) ,  (63)

and therefore

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅 ((A ⊗ I_{X}^{n})(f)))

= (∫_{X} d_{X}(y, 𝔅(ν))^{p}dν(y))^{1/p} . (64)

It also follows from (59) and (62) that

a = (∫_{X} d_{X}(y, 𝔅(f))^{p}dν(y))^{1/p} .  (65)

By combining (60), (63), (64) and (65), an application of (4) to the measure μ = ν with x = 𝔅(f) yields the estimate

b^{p} + \frac{1}{K^{p}} · d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅 ((A ⊗ I_{X}^{n})(f)))^{p} ⩽ a^{p}.  (66)

The desired estimate (58) now follows by combining (61) and (66) with (37). □

Lemma 4.8. Fix p, K ∈ [1, ∞). Suppose that (X, d_{X}) is a p-barycentric metric space with constant K. Then for every n ∈ ℕ, every symmetric stochastic matirx A = (a_{ij}) ∈ M_{n}(ℝ) and every f ∈ L_{p}^{n}(X) we have

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f))

⩽ (\frac{K^{2p}γ_{+}(A, d_{X}^{p}) − 1}{K^{2p}γ_{+}(A, d_{X}^{p}) + K^{p}} )^{1/p} d_{L_{p}^{n}(X)} (f, 𝔅(f)) . (67)

Proof. For every i ∈ {1, …, n} define ν_{i} ∈ 𝒫_{X} by

ν_{i} =^{def} ∑_{i=1}^{n} a_{ij}δ_{f(j)}.  (68)

Thus

(A ⊗ I_{X}^{n})(f)(i) = 𝔅(ν_{i}),

∫_{X} d_{X}(y, 𝔅(ν_{i}))^{p}dν_{i}(y) = ∑_{j=1}^{n} a_{ij}d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p} ,

and

∫_{X} d_{X}(y, 𝔅(f))^{p}dν_{i}(y) = ∑_{j=1}^{n} a_{ij}d_{X}(f(j), 𝔅(f))^{p}.

An application of (4) with μ = ν_{i} and x = 𝔅(f) therefore implies that

d_{X} ((A ⊗ I_{X}^{n})(f)(i), 𝔅(f))^{p} + \frac{1}{K^{p}} ∑_{j=1}^{n} a_{ij}d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p}

⩽ ∑_{j=1}^{n} a_{ij}d_{X}(f(j), 𝔅(f))^{p}. (69)

By averaging (69) over i ∈ {1, …, n} we conclude that

d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f))^{p}

+ \frac{1}{nK^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p}

⩽ \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(f(j), 𝔅(f))^{p} = d_{L_{p}^{n}(X)} (f, 𝔅(f))^{p} .  (70)

Next, the definition of γ_{+}(A, d_{X}^{p}) implies that

\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p}

⩾ \frac{1}{γ_{+}(A, d_{X}^{p})} · \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p} . (71)

For every i ∈ \{1, …, n\}, an application of (4) with μ = \frac{1}{n} ∑_{j=1}^{n} δ_{f(j)} and x = (A ⊗ I_{X}^{n})(f)(i) implies the estimate

d_{X} ((A ⊗ I_{X}^{n})(f)(i), 𝔅(f))^{p} + \frac{1}{K^{p}} · d_{L_{p}^{n}(X)}(f, 𝔅(f))^{p}

⩽ \frac{1}{n} ∑_{j=1}^{n} d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p} . (72)

By averaging (72) over i ∈ {1, …, n} we see that

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X} (f(j), (A ⊗ I_{X}^{n})(f)(i))^{p}

⩾ d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f))^{p} + \frac{1}{K^{p}} · d_{L_{p}^{n}(X)}(f, 𝔅(f))^{p}. (73)

By substituting (73) into (71), and plugging the resulting estimate into (70), we conclude that

(1 + \frac{1}{K^{p}γ_{+}(A, d_{X}^{p})}) d_{L_{p}^{n}(X)} ((A ⊗ I_{X}^{n})(f), 𝔅(f))^{p}

⩽ (1 − \frac{1}{K^{2p}γ_{+}(A, d_{X}^{p})}) d_{L_{p}^{n}(X)}(f, 𝔅(f))^{p},

which simplifies to give the desired inequality (67). □

Proof of Lemma 4.3. Simply combine Lemma 4.7 and Lemma 4.8. □

5. Proof of Theorem 1.11

Lemma 5.1 below plays an important role in our proof of Theorem 1.11. It was proved by the second named author in collaboration with M. Csörnyei (2001); we thank her for letting us include it here.

Lemma 5.1. Fix m, n ∈ ℕ and p ∈ [1, ∞). Let B = (b_{ij}) ∈ M_{n×m}(ℝ) and C = (c_{ij}) ∈ M_{n}(ℝ) be stochastic matrices (of dimensions n by m and n by n, respectively). Fix π ∈ Δ^{n−1} and suppose that C is reversible relative to π. Then for every metric space (X, d_{X}) and every z_{1}, …, z_{m} ∈ X there exist w_{1}, …, w_{n} ∈ X such that

max {∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{X}(w_{i}, z_{r})^{p}, ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}d_{X}(w_{i}, w_{j})^{p}}

⩽ 3^{p} ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}, (74)

where

D_{π} = (\begin{matrix}π_{1} & 0 & … & 0 \\ 0 & π_{2} & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & … & 0 & π_{n} \end{matrix}) ∈ M_{n}(ℝ).  (75)

Proof. Let f : {z_{1}, …, z_{m}} → ℓ_{∞}^{m} be an isometric embedding (e.g. one can take f(z) = ∑_{r=1}^{m} d_{X}(z, z_{r})e_{r}, where {e_{r}}_{r=1}^{m} is the standard basis of ℝ^{m}). Define y_{1}, …, y_{n} ∈ ℓ_{∞}^{m} by

∀ i ∈ {1, …, n}, y_{i} =^{def} ∑_{r=1}^{m} b_{ir}f(z_{r}).  (76)

Next, for every i ∈ {1, …, n} choose w_{i} ∈ {z_{1}, …, z_{m}} such that

∥y_{i} − f(w_{i})∥_{∞} = min_{z∈{z_{1},...,z_{m}}} ∥y_{i} − f(z)∥_{∞}.  (77)

By the triangle inequality, for every i, j ∈ {1, …, m} we have

d_{X}(w_{i}, w_{j})^{p} = ∥f(w_{i}) − f(w_{j})∥_{∞}^{p}

⩽ 3^{p−1} (∥f(w_{i}) − y_{i}∥_{∞}^{p} + ∥y_{i} − y_{j}∥_{∞}^{p} + ∥y_{j} − f(w_{j})∥_{∞}^{p}) .

Consequently, using the stochasticity of C and its reversibility relative to π,

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}d_{X}(w_{i}, w_{j})^{p}

⩽ 3^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}∥y_{i} − y_{j}∥_{∞}^{p} + 2 · 3^{p−1} ∑_{i=1}^{n} π_{i}∥y_{i} − f(w_{i})∥_{∞}^{p}. (78)

Recalling (76), the convexity of the function v ↦ ∥v∥_{∞}^{p} implies that

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}∥y_{i} − y_{j}∥_{∞}^{p} ⩽ ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij} ∑_{r=1}^{m} ∑_{s=1}^{m} b_{ir}b_{js}∥f(z_{r}) − f(z_{s})∥_{∞}^{p}

= ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}. (79)

Next, due to (77) and the fact that CB is a stochastic matrix,

∀ i ∈ {1, …, n}, ∥y_{i} − f(w_{i})∥_{∞}^{p} ⩽ ∑_{r=1}^{m}(CB)_{ir}∥y_{i} − f(z_{r})∥_{∞}^{p}.

Recalling (76) and using the convexity of the function v ↦ ∥v∥_{∞}^{p} once more, we deduce that

∑_{i=1}^{n} π_{i}∥y_{i} − f(w_{i})∥_{∞}^{p} ⩽ ∑_{i=1}^{n} π_{i} ∑_{r=1}^{m}(CB)_{ir} ∑_{s=1}^{m} b_{is}∥f(z_{s}) − f(z_{r})∥_{∞}^{p}

= ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}. (80)

A combination of (78), (79) and (80) now implies that

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}d_{X}(w_{i}, w_{j})^{p} ⩽ 3^{p} ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}. (81)

Next, note that by the triangle inequality for every i, j ∈ {1, …, n} and r ∈ {1, …, m} we have

d_{X}(w_{i}, z_{r})^{p} = ∥f(w_{i}) − f(z_{r})∥_{∞}^{p}

⩽ 3^{p−1} (∥f(w_{i}) − y_{i}∥_{∞}^{p} + ∥y_{i} − y_{j}∥_{∞}^{p} + ∥y_{j} − f(z_{r})∥_{∞}^{p}) . (82)

By multiplying inequality (82) by π_{i}b_{ir}c_{ij}, summing over r ∈ {1, …, m} and i, j ∈ {1, …, n}, and using the stochasticity of B and C, we deduce that

\frac{1}{3^{p−1}} ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{X}(w_{i}, z_{r})^{p} ⩽ ∑_{i=1}^{n} π_{i}∥f(w_{i}) − y_{i}∥_{∞}^{p}

+ ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}∥y_{i} − y_{j}∥_{∞}^{p} + ∑_{j=1}^{n} ∑_{r=1}^{m}(B^{∗}D_{π}C)_{rj}∥y_{j} − f(z_{r})∥_{∞}^{p}. (83)

Recalling (76) and using the convexity of the function v ↦ ∥v∥_{∞}^{p}, we have

∑_{j=1}^{n} ∑_{r=1}^{m}(B^{∗}D_{π}C)_{rj}∥y_{j} − f(z_{r})∥_{∞}^{p}

⩽ ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}. (84)

A combination of (83) with (79), (80), and (84) yields the estimate

∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{X}(w_{i}, z_{r})^{p} ⩽ 3^{p} ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p},

which, due to (81), yields the desired estimate (74). □

The following lemma is a natural variant of [3, Lem. 1.1].

Lemma 5.2 (dual extension criterion). Fix p, Λ, Γ ∈ [1, ∞), an integer n, and ε ∈ (0, 1). Suppose that (X, d_{X}) and (Y, d_{Y}) are metric spaces with (Y, d_{Y}) being W_{p} barycentric with constant Γ. Fix Z ⊆ X, a Lipschitz function f : Z → Y and distinct x_{1}, …, x_{n} ∈ X. Suppose that for every symmetric n by n matrix H = (h_{ij}) with nonnegative entries there exists Φ^{H} : {x_{1}, …, x_{n}} → Y with Φ^{H}|_{{x_{1},...,x_{n}}∩Z} = f|_{{x_{1},...,x_{n}}∩Z} such that

∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}d_{Y} (Φ^{H}(x_{i}), Φ^{H}(x_{j}))^{p} ⩽ Λ^{p}∥f∥_{Lip}^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}d_{X}(x_{i}, x_{j})^{p}.

Then there is F : {x_{1}, …, x_{n}} → Y with F |_{{x_{1},...,x_{n}}∩Z} = f|_{{x_{1},...,x_{n}}∩Z} and ∥F ∥_{Lip} ⩽ (1 + ε)ΓΛ∥f∥_{Lip}.

Proof. We proceed via the following duality argument due to Ball [3] (which is itself inspired by the work of Maurey [40]), with a slight twist that brings in the assumption that Y is W_{p} barycentric.

Consider the following set of n by n symmetric matrices.

C =^{def} { (d_{Y} (Φ(x_{i}), Φ(x_{j}))^{p}) ∈ M_{n}(ℝ) :

Φ : {x_{1}, …, x_{n}} → Y ∧ Φ|_{{x_{1},...,x_{n}}∩Z} = f|_{{x_{1},...,x_{n}}∩Z}}.

Let D ⊆ M_{n}(ℝ) be the set of all n by n symmetric matrices with nonnegative entries and define

E =^{def} \overline{conv (C + D)}.

For every i, j ∈ {1, …, n} write t_{ij} =^{def} Λ^{p}∥f∥_{Lip}^{p}d_{X}(x_{i}, x_{j})^{p}. The assumption of Lemma 5.2 can be rephrased as

sup_{H∈D} inf_{M∈C} ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij} (m_{ij} − t_{ij}) ⩽ 0.  (85)

It follows that the matrix T = (t_{ij}) belongs to E, since otherwise by the separation theorem (Hahn-Banach) there would exist a symmetric matrix H = (h_{ij}) such that

inf_{M∈E} ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}m_{ij} > ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}t_{ij}  (86)

Since E ⊇ C + D it follows from (86) that the entries of H are nonnegative, i.e., H ∈ D. Now (86) contradicts (85) since E ⊇ C.

Having shown that T ∈ E, we deduce that there exists m ∈ ℕ and λ_{1}, …, λ_{m} ∈ [0, 1] with ∑_{k=1}^{m} λ_{k} = 1, and in addition there are Φ^{1}, …, Φ^{m} : {x_{1}, …, x_{n}} → Y with Φ^{k}|_{{x_{1},...,x_{n}}∩Z} = f|_{{x_{1},...,x_{n}}∩Z} for all k ∈ {1, …, m}, such that for every i, j ∈ {1, …, m},

(1 + ε)^{p}Λ^{p}∥f∥_{Lip}^{p}d_{X}(x_{i}, x_{j})^{p} − ∑_{k=1}^{m} λ_{k}d_{Y} (Φ^{k}(x_{i}), Φ^{k}(x_{j}))^{p} ⩾ 0. (87)

For every i ∈ {1, …, n} consider the finitely supported probability measure μ_{i} on Y given by

μ_{i} =^{def} ∑_{k=1}^{m} λ_{k}δ_{Φ^{k}(x_{i})},

and set

F (x_{i}) =^{def} 𝔅 (μ_{i}) .

If x_{i} ∈ Z then μ_{i} = δ_{f(x_{i})} and therefore F (x_{i}) = f(x_{i}). In other words, F |_{{x_{1},...,x_{n}}∩Z} = f|_{{x_{1},...,x_{n}}∩Z}. Also, for every i, j ∈ {1, …, n} we have

d_{Y} (F (x_{i}), F (x_{j})) ⩽^{(3)} ΓW_{p}(μ_{i}, μ_{j})
⩽ Γ (∑_{k=1}^{m} λ_{k}d_{Y} (Φ^{k}(x_{i}), Φ^{k}(x_{j}))^{p})^{1/p}

⩽^{(87)} (1 + ε)ΓΛ∥f∥_{Lip}d_{Y} (x_{i}, x_{j}).

Thus ∥F ∥_{Lip} ⩽ (1 + ε)ΓΛ∥f∥_{Lip}, as required. □

Proof of Theorem 1.11. Fix m, n ∈ ℕ. Take x_{1}, …, x_{n} ∈ X ∖ Z and z_{1}, …, z_{m} ∈ Z. If H = (h_{ij}) ∈ M_{n+m}(ℝ) is symmetric then write

H = (\begin{matrix}U(H) & W (H)^{∗} \\ W (H) & V (H) \end{matrix}) ,

where U(H) ∈ M_{m}(ℝ), V (H) ∈ M_{n}(ℝ) and W (H) ∈ M_{n×m}(ℝ). With this notation, define

R_{H} =^{def} ∑_{r=1}^{m} ∑_{s=1}^{m} U(H)_{rs}d_{X}(z_{r}, z_{s})^{p}

+ 2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{X}(x_{i}, z_{r})^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{X}(x_{i}, x_{j})^{p},

and for every y_{1}, …, y_{n} ∈ Y,

L_{H}(y_{1}, …, y_{n}) =^{def} ∑_{r=1}^{m} ∑_{s=1}^{m} U(H)_{rs}d_{Y} (f(z_{r}), f(z_{s}))^{p}

+ 2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{Y} (y_{i}, y_{j})^{p}.

Fix from now on M ∈ (M_{p}(X), 2M_{p}(X)] and N ∈ (N_{p}(Y), 2N_{p}(Y)]. Due to Lemma 5.2 it suffices to show that for every symmetric matrix H = (h_{ij}) ∈ M_{n+m}(ℝ) with nonnegative entries and for every δ ∈ (0, 1) one can find y_{1}, …, y_{n} ∈ Y such that

L_{H}(y_{1}, …, y_{n}) ⩽ Λ(R_{H} + δ),

where

Λ =^{def} \frac{18^{p}}{3} (N^{p} + 1)M^{p}∥f∥_{Lip}^{p}.  (88)

Since the Lipschitz condition of f on {z_{1}, …, z_{m}} implies that

∑_{r=1}^{m} ∑_{s=1}^{m} U(H)_{rs}d_{Y} (f(z_{r}), f(z_{s}))^{p} ⩽ ∥f∥_{Lip}^{p} ∑_{r=1}^{m} ∑_{s=1}^{m} U(H)_{rs}d_{X}(z_{r}, z_{s})^{p},

it suffices to establish the existence of y_{1}, …, y_{n} ∈ Y that satisfy the inequality

\frac{1}{Λ} (2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{Y} (y_{i}, y_{j})^{p})

⩽ 2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{X}(x_{i}, z_{r})^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{X}(x_{i}, x_{j})^{p} + δ. (89)

Fix t ∈ [2, ∞) and ε ∈ (0, 1) that will be determined later. Note that the diagonal entries {V (H)_{ii}}_{i=1}^{n} are irrelevant for the validity of (89), so we may assume from now on that V (H)_{ii} = 0 for all i ∈ {1, …, n}.

Define π ∈ ℝ^{n} by

∀ i ∈ \{1, …, n\}, π_{i} =^{def} \frac{mε + ∑_{r=1}^{m} W (H)_{ir}}{mnε + ∑_{j=1}^{n} ∑_{r=1}^{m} W (H)_{jr}} .  (90)

Thus π ∈ Δ^{n−1}. Next, define B = (b_{ir}) ∈ M_{n×m}(ℝ) by setting for every i ∈ {1, …, n} and r ∈ {1, …, m},

b_{ir} =^{def} \frac{ε + W (H)_{ir}}{mε + ∑_{s=1}^{m} W (H)_{is}} .  (91)

Thus B is a stochastic matrix. Finally, define A = (a_{ij}) ∈ M_{n}(ℝ) by setting for i ∈ {1, …, n},

a_{ii} =^{def} 1 − \frac{1}{t} · \frac{∑_{j=1}^{n} V (H)_{ij}}{mε + ∑_{r=1}^{m} W (H)_{ir}} ,  (92)

and for distinct i, j ∈ {1, …, n},

a_{ij} =^{def} \frac{1}{t} · \frac{V (H)_{ij}}{mε + ∑_{r=1}^{m} W (H)_{ir}} .  (93)

The role of ε is only to ensure that the denominators that appear in (90), (91), (92) and (93) do not vanish. Fixing ε, we will assume from now on that t is sufficiently large so as to ensure that a_{11}, …, a_{nn} are all nonnegative. Thus A is a stochastic matrix. Note also that since V (H) is symmetric, an inspection of (90) and (93) reveals that A is reversible relative to π.

Set

τ =^{def} ⌈\frac{t}{2^{p}} ⌉ .  (94)

By Lemma 5.1 applied with C = 𝒜_{τ}(A) there exist w_{1}, …, w_{n} ∈ Y such that

max {∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (w_{i}, f(z_{r}))^{p}, ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{τ}(A)_{ij}d_{Y} (w_{i}, w_{j})^{p}}

⩽ 3^{p} ∑_{r=1}^{m} ∑_{s=1}^{m} (B^{∗}D_{π}𝒜_{τ}(A)B) _{rs} d_{Y} (f(z_{r}), f(z_{s}))^{p} . (95)

Since N > N_{p}(Y) there exist y_{1}, …, y_{n} ∈ Y such that

∑_{i=1}^{n} π_{i}d_{Y} (w_{i}, y_{i})^{p} + \frac{t}{2^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{Y} (y_{i}, y_{j})^{p}

⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{τ}(A)_{ij}d_{Y} (w_{i}, w_{j})^{p}. (96)

We will now show that the points y_{1}, …, y_{n} thus found satisfy the desired inequality (89).

To estimate the left hand side of (89) from above, denote

θ =^{def} mnε + ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir},  (97)

and observe that due to (90), (91) and (97) we have

∀(i, r) ∈ {1, …, n} × {1, …, m}, W (H)_{ir} + ε = θπ_{i}b_{ir}. (98)

Similarly, due to (90), (92) and (93) we have

(i, j ∈ {1, …, n} ∧ i ≠ j) ⟹ V (H)_{ij} = θtπ_{i}a_{ij}.  (99)

Hence,

\frac{1}{θ} (2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{Y} (y_{i}, y_{j})^{p})

⩽ 2 ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{Y} (y_{i}, y_{j})^{p}. (100)

By the triangle inequality, for every i ∈ {1, …, n} and r ∈ {1, …, m} we have

d_{Y} (y_{i}, f(z_{r}))^{p} ⩽ 2^{p−1}d_{Y} (y_{i}, w_{i})^{p} + 2^{p−1}d_{Y} (w_{i}, f(z_{r}))^{p}.

Consequently,

∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (y_{i}, f(z_{r}))^{p}

⩽ 2^{p−1} ∑_{i=1}^{n} π_{i}d_{Y} (y_{i}, w_{i})^{p} + 2^{p−1} ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (w_{i}, f(z_{r}))^{p}. (101)

SPECTRAL CALCULUS AND LIPSCHITZ EXTENSION 37

We can therefore bound the right hand side of (100) as follows.

2 ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{Y} (y_{i}, y_{j})^{p}

⩽^{(101)} 2^{p} ∑_{i=1}^{n} π_{i}d_{Y} (y_{i}, w_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{Y} (y_{i}, y_{j})^{p}

+ 2^{p} ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (w_{i}, f(z_{r}))^{p}

⩽^{(96)} (2N)^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{τ}(A)_{ij}d_{Y} (w_{i}, w_{j})^{p} + 2^{p} ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{Y} (w_{i}, f(z_{r}))^{p}

⩽^{(95)} 6^{p} (N^{p} + 1) ∑_{r=1}^{m} ∑_{s=1}^{m} (B^{∗}D_{π}𝒜_{τ}(A)B) _{rs} d_{Y} (f(z_{r}), f(z_{s}))^{p}

⩽ 6^{p} (N^{p} + 1) ∥f∥_{Lip}^{p} ∑_{r=1}^{m} ∑_{s=1}^{m} (B^{∗}D_{π}𝒜_{τ}(A)B) _{rs} d_{X}(z_{r}, z_{s})^{p}.  (102)

For every i, j ∈ {1, …, n} and r, s ∈ {1, …, m} we have d_{X}(z_{r}, z_{s})^{p} ⩽ 3^{p−1}d_{X}(z_{r}, x_{i})^{p} + 3^{p−1}d_{X}(x_{i}, x_{j})^{p} + 3^{p−1}d_{X}(x_{j}, z_{s})^{p}.

Consequently,

∑_{r=1}^{m} ∑_{s=1}^{m} (B^{∗}D_{π}𝒜_{τ}(A)B) _{rs} d_{X}(z_{r}, z_{s})^{p}

= ∑_{r=1}^{m} ∑_{s=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ir}b_{js}π_{i}𝒜_{τ}(A)_{ij}d_{X}(z_{r}, z_{s})^{p}

⩽ 3^{p−1}(S_{1} + S_{2} + S_{3}),  (103)

where, using the stochasticity of A and B,

S_{1} =^{def} ∑_{r=1}^{m} ∑_{s=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ir}b_{js}π_{i}𝒜_{τ}(A)_{ij}d_{X}(z_{r}, x_{i})^{p}
= ∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{X}(x_{i}, z_{r})^{p},  (104)

using the stochasticity of A and B and the fact that X has Markov type p with M > M_{p}(X),

S_{2} =^{def} ∑_{r=1}^{m} ∑_{s=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ir}b_{js}π_{i}𝒜_{τ}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}

= \frac{1}{τ} ∑_{k=1}^{τ} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{k})_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽^{(1)} \frac{M^{p}}{τ} ∑_{k=1}^{τ} k ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(x_{i}, x_{j})^{p}

= \frac{M^{p}(τ + 1)}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽^{(94)} \frac{(2^{p+1} + t)M^{p}}{2^{p+1}} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(x_{i}, x_{j})^{p},  (105)

and, using the stochasticity of A and B, and the reversibility of 𝒜_{τ}(A) relative to π,

S_{3} =^{def} ∑_{r=1}^{m} ∑_{s=1}^{m} ∑_{i=1}^{n} ∑_{j=1}^{n} b_{ir}b_{js}π_{i}𝒜_{τ}(A)_{ij}d_{X}(x_{j}, z_{s})^{p}

= ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{s=1}^{m} b_{js}π_{j}𝒜_{τ}(A)_{ji}d_{X}(x_{j}, z_{s})^{p}

= ∑_{j=1}^{n} ∑_{s=1}^{m} π_{j}b_{js}d_{X}(x_{j}, z_{s})^{p} = S_{1}.  (106)

By substituting (104), (105) and (106) into (103), and combining the resulting estimate with (102) and (100) while recalling the definition of Λ in (88), we arrive at

\frac{1}{Λ} (2 ∑_{i=1}^{n} ∑_{r=1}^{m} W (H)_{ir}d_{Y} (y_{i}, f(z_{r}))^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{Y} (y_{i}, y_{j})^{p})

⩽ \frac{2}{M^{p}} ∑_{i=1}^{n} ∑_{r=1}^{m} θπ_{i}b_{ir}d_{X}(x_{i}, z_{r})^{p} + \frac{2^{p+1} + t}{2^{p+1}t} ∑_{i=1}^{n} ∑_{j=1}^{n} tθπ_{i}a_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽ 2 ∑_{i=1}^{n} ∑_{r=1}^{m} (W (H)_{ir} + ε) d_{X}(x_{i}, z_{r})^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} V (H)_{ij}d_{X}(x_{i}, x_{j})^{p},

where we used M > M_{p}(X) ⩾ 1 and 2^{p+1}t ⩾ 2^{p+1}+t (recall that t ⩾ 2), combined with the identities (98) and (99). Choosing ε ∈ (0, 1) so that 2ε ∑_{i=1}^{n} ∑_{r=1}^{m} d_{X}(x_{i}, z_{r})^{p} ⩽ δ yields the desired estimate (89). □

6. Proof of Theorem 1.14 and Theorem 1.17

Both Theorem 1.14 and Theorem 1.17 rely on a quantitative variant of a beautiful construction of Kalton [27, 29]. Before passing to the construction itself, we record some basic facts on metric Markov cotype.

Lemma 6.1. Fix p ∈ (0, ∞) and let (X, d_{X}) be a metric space with metric Markov cotype p. Suppose that S ⊆ X is a Lipschitz retract of X, i.e., there exists a Lipschitz mapping ρ : X → S such that ρ(s) = s for every s ∈ S. Then S also has metric Markov cotype p, and in fact

N_{p}(S) ⩽ ∥ρ∥_{Lip}N_{p}(X).

Proof. Fix N > N_{p}(X) and n, t ∈ ℕ. Suppose that A = (a_{ij}) ∈ M_{n}(ℝ) is a stochastic matrix that is reversible relative to π ∈ Δ^{n−1}. For every x_{1}, …, x_{n} ∈ S there exist y_{1}, …, y_{n} ∈ X such that

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p}

⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}.

Then, since ρ(x_{i}) = x_{i} for every i ∈ {1, …, n},

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, ρ(y_{i}))^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(ρ(y_{i}), ρ(y_{j}))^{p}

⩽ ∥ρ∥_{Lip}^{p} (∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + t ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij}d_{X}(y_{i}, y_{j})^{p})

⩽ ∥ρ∥_{Lip}^{p}N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}.  □

We next show that the real line ℝ (equipped with the standard metric) fails to have metric Markov cotype p for any p ∈ (0, 2). Lemma 6.2 below contains a simple explicit example that exhibits this fact, but when p ∈ [1, 2) there is a also a roundabout way to see that ℝ fails to have metric Markov cotype p via the link to Lipschitz extension. Indeed, it follows from the definition of metric Markov cotype that N_{p}(ℓ_{p}) = N_{p}(ℝ). Ball proved [3] that the Markov type p constant of ℓ_{p} satisfies M_{p}(ℓ_{p}) = 1 for p ∈ [1, 2). Corollary 1.13 therefore implies that e(ℓ_{p}, ℓ_{p}) ≲ N_{p}(ℝ). But it is known that e(ℓ_{p}, ℓ_{p}) = ∞ for every p ∈ [1, 2): for p ∈ (1, 2) see [48], and for p = 1 it is observed in [39] that this follows from [8] or [19] ([39] also provides an interesting third proof of the fact that e(ℓ_{1}, ℓ_{1}) = ∞).

Lemma 6.2. For every p ∈ (0, 2) the real line ℝ (equipped with the standard metric) fails to have metric Markov cotype p.

Proof. Fix p ∈ (0, 2) and suppose for the sake of obtaining a contradiction that N_{p}(ℝ) < ∞. Fixing n ∈ ℕ, define A = (a_{ij}) ∈ M_{n}(ℝ) by a_{11} = a_{nn} = 1/2 and a_{i,i+1} = a_{i+1,i} = 1/2 for every i ∈ {1, …, n − 1}, and the remaining entries of A vanish. Thus A is a symmetric stochastic matrix, corresponding to the standard random walk on {1, …, n} in which if the walker is at either 1 or n then with probability 1/2 it does nothing in the next step, and with probability 1/2 it moves in the next step to its unique neighbor in {2, n − 1}. Let {W_{0}, W_{1}, W_{2}, …} denote this walk, i.e., W_{0} is uniformly distributed on {1, …, n} and conditioned on W_{t} = i the probability that W_{t+1} = j equals a_{ij}. Thus, for every t ∈ ℕ we have

(\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}|i − j|^{p})^{1/p} = (𝔼 [|W_{t} − W_{0}|^{p}])^{1/p}

⩽ (𝔼 [|W_{t} − W_{0}|^{2}])^{1/2} ⩽ \sqrt{t}. (107)

To justify the final inequality in (107), proceed by induction on t as follows. Since |W_{t+1} − W_{t}| ⩽ 1 point-wise,

𝔼 [|W_{t+1} − W_{0}|^{2}] ⩽ 𝔼 [|W_{t} − W_{0}|^{2}] + 2 𝔼 [(W_{t} − W_{0})(W_{t+1} − W_{t})] + 1,

so for the induction step it suffices to show that for every t ∈ ℕ we have 𝔼 [(W_{t} − W_{0})(W_{t+1} − W_{t})] ⩽ 0. By conditioning on W_{0}, W_{t}, it suffices to check the point-wise inequality

(W_{t} − W_{0}) 𝔼 [W_{t+1} − W_{t}|W_{0}, W_{t}] ⩽ 0.  (108)

(108) is easy to verify: if W_{t} ∈ {2, …, n−1} then W_{t+1}−W_{t} is uniformly distributed on {−1, 1} and therefore 𝔼 [W_{t+1} − W_{t}|W_{0}, W_{t}] = 0, if W_{t} = 1 then W_{t} − W_{0} ⩽ 0 and W_{t+1} − W_{t} ⩾ 0, and if W_{t} = n then W_{t} − W_{0} ⩾ 0 and W_{t+1} − W_{t} ⩽ 0.

Due to (107), for every t ∈ ℕ we have

\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} 𝒜_{t}(A)_{ij}|i − j|^{p} ⩽ \frac{1}{t} ∑_{s=1}^{t} s^{p/2} ⩽ t^{p/2}.

The definition of metric Markov cotype p therefore implies that there exist y_{1}, …, y_{n} ∈ ℝ such that

\frac{1}{n} ∑_{i=1}^{n} |i − y_{i}|^{p} + \frac{t}{n} ∑_{i=1}^{n−1} |y_{i+1} − y_{i}|^{p} ⩽ N_{p}(ℝ)^{p}t^{p/2}.  (109)

Suppose first that p ∈ [1, 2). In this case we choose

t = ⌈(4N_{p}(ℝ))^{\frac{2p}{2−p}} ⌉ .  (110)

Using Hölder’s inequality and (109) we deduce that

∑_{i=1}^{n−1} |y_{i+1} − y_{i}| ⩽ (n − 1)^{1− \frac{1}{p}} (∑_{i=1}^{n−1} |y_{i+1} − y_{i}|^{p})^{1/p} ⩽ \frac{N_{p}(ℝ)n}{t^{\frac{1}{p} − \frac{1}{2}}}.

Consequently, for every i ∈ {2, …, n} we have

|y_{i} − y_{1}| ⩽ ∑_{j=1}^{i−1} |y_{j+1} − y_{j}| ⩽ \frac{N_{p}(ℝ)n}{t^{\frac{1}{p} − \frac{1}{2}}} ⩽^{(110)} \frac{n}{4}.  (111)

(111) implies that if y_{1} ⩽ n/2 then y_{i} ⩽ 3n/4 for every i ∈ {1, …, n} and if y_{1} ⩾ n/2 then y_{i} ⩾ n/4 for every i ∈ {1, …, n}. Hence,

\frac{1}{n} ∑_{i=1}^{n} |i − y_{i}|^{p} ⩾ \frac{1}{n} ∑_{i=1}^{⌊n/8⌋} |i − y_{i}|^{p} + \frac{1}{n} ∑_{i=⌈7n/8⌉}^{n} |i − y_{i}|^{p} ≳ n^{p}. (112)

By substituting (112) into (109) and recalling (110) we conclude that

n ⩽ 4^{\frac{p}{2−p}} N_{p}(ℝ)^{\frac{2}{2−p}} ,

which is a contradiction for large enough n.

It remains to deal with the case p ∈ (0, 1]. Now our choice of t is

t = ⌈(4N_{p}(ℝ))^{\frac{2p}{2−p}} n^{\frac{2(1−p)}{2−p}} ⌉ .  (113)

Observe that since p ∈ (0, 1], for every i ∈ {2, …, n},

|y_{i} − y_{1}| ⩽ ∑_{j=1}^{i−1} |y_{j+1} − y_{j}|

⩽ (∑_{j=1}^{i−1} |y_{j+1} − y_{j}|^{p})^{1/p} ⩽^{(109)} \frac{N_{p}(ℝ)n^{\frac{1}{p}}}{t^{\frac{1}{p} − \frac{1}{2}}} ⩽^{(113)} \frac{n}{4}.

We thus arrived at the same conclusion as (111), and therefore (112) holds true. In combination with (109) and our current choice of t in (113), we see that

n ≲ N_{p}(ℝ)^{\frac{2}{2−p}} n^{\frac{1−p}{2−p}} ,

which simplifies to n ≲ N_{p}(ℝ)^{2}, a contradiction for large enough n. □

Corollary 6.3. Every Banach space (X, ∥ · ∥_{X}) fails to have metric Markov cotype p for all p ∈ (0, 2).

Proof. X contains an isometric copy of ℝ. Since ℝ is a 1-absolute Lipschitz retract (see [7, Ch. 1]), it follows from Lemma 6.1 that N_{p}(X) ⩾ N_{p}(ℝ). For p ∈ (0, 2) we have N_{p}(ℝ) = ∞ by Lemma 6.2. □

6.1. Kalton’s construction. For p ∈ [1, ∞) let ℓ_{p}^{n} denote (as usual) the space ℝ^{n} equipped with the norm ∥x∥_{p} = (|x_{1}|^{p} + … + |x_{n}|^{p})^{1/p}. The unit ball of ℓ_{p}^{n} is denoted below B_{p}^{n} = {x ∈ ℝ^{n} : ∥x∥_{p} ⩽ 1}. For every ε ∈ (0, 1) there exists a subset N of B_{2}^{n} such that |N | ⩽ (1+2/ε)^{n} and min_{y∈N} ∥x−y∥_{2} ⩽ ε for every x ∈ B_{2}^{n} (see e.g. [46]). In particular, there exists a linear operator Q_{n} : ℓ_{1}^{5^{n}} → ℓ_{2}^{n} such that

B_{2}^{n} ⊇ Q_{n} (B_{1}^{5^{n}}) ⊇ \frac{1}{2}B_{2}^{n}.  (114)

Indeed, choose {x_{1}, …, x_{5^{n}}} ⊆ B_{2}^{n} with min_{i∈{1,...,5^{n}}} ∥x − x_{i}∥_{2} ⩽ 1/2 for every x ∈ B_{2}^{n}. This implies that the convex hull of {±x_{1}, … ± x_{5^{n}}} contains \frac{1}{2}B_{2}^{n}. Hence, if we set Q_{n}(e_{i}) = x_{i}, where e_{1}, …, e_{5^{n}} is the standard basis of ℓ_{1}^{5^{n}}, then the linear extension of Q_{n} satisfies (114).

In what follows we fix a linear mapping Q_{n} : ℓ_{1}^{5^{n}} → ℓ_{2}^{n} for which (114) holds true, and we also fix a mapping ϕ_{n} : B_{2}^{n} → 2B_{1}^{5^{n}} such that ϕ_{n}(−x) = −ϕ_{n}(x) for every x ∈ B_{2}^{n} and Q_{n} ∘ϕ_{n} is the identity mapping on B_{2}^{n}. The fact that such a ϕ_{n} exists is an immediate consequence of (114): simply choose a section φ : B_{2}^{n} → 2B_{1}^{5^{n}} of Q_{n} and define ϕ_{n}(x) = (φ(x) − φ(−x))/2.

For every θ ∈ (0, 1] consider the following linear subspace of ℓ_{1}^{5^{n}} ⊕ℓ_{2}^{n}.

Y_{θ}^{n} =^{def} \{(\frac{x}{n^{θ/4}} , Q_{n}(x)) : x ∈ ℓ_{1}^{5^{n}}\} ⊆ ℓ_{1}^{5^{n}} ⊕ ℓ_{2}^{n}.  (115)

Below it will always be understood that Y_{n} is equipped with the norm inherited from (ℓ_{1}^{5^{n}} ⊕ ℓ_{2}^{n})_{1}, i.e., ∥(x, y)∥_{(ℓ_{1}^{5^{n}}⊕ℓ_{2}^{n})_{1}} = ∥x∥_{1} + ∥y∥_{2} for every (x, y) ∈ ℓ_{1}^{5^{n}} ⊕ ℓ_{2}^{n}.

Let A_{n} ⊆ S^{n−1} = ∂B_{2}^{n} be a maximal (with respect to inclusion) symmetric set (i.e., x ∈ A_{n} ⟺ −x ∈ A_{n}) such that ∥a−b∥_{2} > 1/\sqrt[4]{n} for every distinct a, b ∈ A_{n} . Thus min_{a∈A_{n}} ∥x − a∥_{2} ⩽ 1/\sqrt[4]{n} for every x ∈ S^{n−1}. Define a mapping f_{θ}^{n} : A_{n} → Y_{n} by

∀ a ∈ A_{n},  f_{θ}^{n}(a) =^{def} (\frac{ϕ_{n}(a)}{n^{θ/4}}, a) .  (116)

Observe that f_{θ}^{n}(−a) = −f_{θ}^{n}(a) for every a ∈ A_{n}.

Lemma 6.4. For every n ∈ ℕ, θ ∈ (0, 1] and τ ∈ [θ, 1] we have

∀ a, b ∈ A_{n}, ∥f_{θ}^{n}(a) − f_{θ}^{n}(b)∥_{Y_{θ}^{n}} ≲ n^{(τ−θ)/4}∥a − b∥_{2}^{τ}.

Proof. We may assume that a ≠ b, in which case 1/\sqrt[4]{n} ⩽ ∥a−b∥_{2} ⩽ 2. Consequently,

∥f_{θ}^{n}(a) − f_{θ}^{n}(b)∥_{Y_{θ}^{n}} = \frac{∥ϕ_{n}(a) − ϕ_{n}(b)∥_{1}}{n^{θ/4}} + ∥a − b∥_{2}

⩽ \frac{∥ϕ_{n}(a)∥_{1} + ∥ϕ_{n}(b)∥_{1}}{n^{θ/4}} + 2^{1−τ}∥a − b∥_{2}^{τ}

⩽ (4n^{(τ−θ)/4} + 2^{1−τ}) ∥a − b∥_{2}^{τ}.  □

Lemma 6.5. Fix n ∈ ℕ, L ∈ (0, ∞), θ ∈ (0, 1] and τ ∈ [θ, 1]. Suppose that F : S^{n−1} → Y_{θ}^{n} satisfies

∀ x, y ∈ S^{n−1},  ∥F (x) − F (y)∥_{Y_{θ}^{n}} ⩽ Ln^{(τ−θ)/4}∥x − y∥_{2}^{τ}, (117)

and that F (a) = f_{θ}^{n}(a) for every a ∈ A_{n}. Then L ≳ n^{θ/4}.

Proof. By replacing F (x) with (F (x)−F (−x))/2 we may assume without loss of generality that F (−x) = −F (x) for every x ∈ S^{n−1}. Since F takes values in Y_{θ}^{n}, it follows from (115) that there exists a mapping ψ : S^{n−1} → ℓ_{1}^{5^{n}} such that

∀ x ∈ S^{n−1},  F (x) = (\frac{ψ(x)}{n^{θ/4}}, Q_{n}(ψ(x))) .  (118)

Let σ_{n−1} denote the normalized Haar measure on S^{n−1}. We claim that for every y ∈ B_{∞}^{5^{n}} = [−1, 1]^{5^{n}} we have

∫_{S^{n−1}} |⟨ψ(x), y⟩|dσ_{n−1}(x) ≲ \frac{L}{n^{τ/4}} .  (119)

The proof of (119) is a standard application of the concentration of measure phenomenon on S^{n−1}. Indeed, consider the set

U_{y} =^{def} {x ∈ S^{n−1} : ⟨ψ(x), y⟩ ⩽ 0} ⊆ S^{n−1}.

Since ψ(−x) = −ψ(x) for every x ∈ S^{n−1} we have σ_{n−1}(U_{y}) ⩾ \frac{1}{2}. For x ∈ S^{n−1} and t ∈ (0, ∞) note that

⟨ψ(x), y⟩ ⩾ t ⟹ inf_{u∈U_{y}} ∥x − u∥_{2} ⩾ (\frac{t}{Ln^{τ/4}} )^{1/τ} .  (120)

Indeed, if ⟨ψ(x), y⟩ ⩾ t then for every u ∈ U_{y}, since ⟨ψ(u), y⟩ ⩽ 0,

t ⩽ ⟨ψ(x) − ψ(u), y⟩ ⩽ ∥ψ(x) − ψ(u)∥_{1}

⩽^{(118)} n^{θ/4}∥F (x) − F (u)∥_{Y_{θ}^{n}} ⩽^{(117)} Ln^{τ/4} · ∥x − u∥_{2}^{τ},

implying (120). By the isoperimetric inequality on S^{n−1} (see e.g. [46]) it follows from (120) that

σ_{n−1} (\{x ∈ S^{n−1} : ⟨ψ(x), y⟩ ⩾ t\}) ≲ exp (−cn (\frac{t}{Ln^{τ/4}} )^{2/τ}) ,

where c ∈ (0, ∞) is a universal constant. By symmetry, the same estimate holds true for σ_{n−1} ({x ∈ S^{n−1} : ⟨ψ(x), y⟩ ⩽ −t}), and therefore

σ_{n−1} (\{x ∈ S^{n−1} : |⟨ψ(x), y⟩| ⩾ t\}) ≲ exp (−c (\frac{tn^{τ/4}}{L} )^{2/τ}) .

Consequently,

∫_{S^{n−1}} |⟨ψ(x), y⟩|dσ_{n−1}(x) ≲ ∫_{0}^{∞} exp (−c (\frac{tn^{τ/4}}{L} )^{2/τ}) dt

= \frac{Lτ}{2c^{τ/2}n^{τ/4}} ∫_{0}^{∞} s^{^{\frac{τ}{2}} −1}e^{−s}ds = \frac{LΓ(1 + τ/2)}{c^{τ/2}n^{τ/4}} ≲ \frac{L}{n^{τ/4}} ,

completing the proof of (119).

The Pietsch Domination Theorem [56] (see also [37, Prop. 3.1]) implies that there exists a Borel probability measure μ on B_{∞}^{5^{n}} such that

∀ x ∈ ℓ_{1}^{5^{n}},  ∥Q_{n}(x)∥_{2} ⩽ π_{1}(Q_{n}) ∫_{B_{∞}^{5^{n}}} |⟨x, y⟩|dμ(y),  (121)

where π_{1}(Q_{n}) is the 1-summing norm of Q_{n}, i.e.,

π_{1}(Q_{n}) = sup_{k∈ℕ} sup {∑_{i=1}^{k} ∥Q_{n}(x_{i})∥_{2} : sup_{y∈B_{∞}^{5^{n}}} ∑_{i=1}^{k} |⟨x_{i}, y⟩| ⩽ 1} .

A theorem of Grothendieck [21, Cor. 1] (see also [37, Thm. 4.1]) implies that π_{1}(Q_{n}) ⩽ K_{G}∥Q_{n}∥_{ℓ_{1}^{5^{n}}→ℓ_{2}^{n}}, where K_{G} ∈ [1, 2] is the Grothendieck constant. Recalling (114), we have ∥Q_{n}∥_{ℓ_{1}^{5^{n}}→ℓ_{2}^{n}} ⩽ 1. Hence,

∫_{S^{n−1}} ∥Q_{n}(ψ(x))∥_{2}dσ_{n−1}(x)

≲^{(121)} ∫_{S^{n−1}} ∫_{B_{∞}^{5^{n}}} |⟨ψ(x), y⟩|dμ(y)dσ_{n−1}(x) ≲^{(119)} \frac{L}{n^{τ/4}} . (122)

For x ∈ S^{n−1} choose a ∈ A_{n} such that ∥x − a∥_{2} ⩽ 1/\sqrt[4]{n}. Recalling (116) and (118), since F (a) = f_{θ}^{n}(a) we have Q_{n}(ψ(a)) = a. Hence,

∥Q_{n}(ψ(x))∥_{2} ⩾ 1 − ∥Q_{n}(ψ(x)) − Q_{n}(ψ(a))∥_{2}

⩾^{(118)} 1 − ∥F (x) − F (a)∥_{Y_{θ}^{n}} ⩾^{(117)} 1 − \frac{Ln^{(τ−θ)/4}}{n^{τ/4}} = 1 − \frac{L}{n^{θ/4}} . (123)

By combining (122) and (123), and recalling that τ ⩾ θ, the proof of Lemma 6.5 is complete. □

Proof of Theorem 1.14. The ensuing deduction of Theorem 1.14 from Lemma 6.5 follows an idea of [48]. Fix n ∈ ℕ and p ∈ [2, n]. Consider the metric on ℓ_{2} given by

∀ x, y ∈ ℓ_{2}, d_{p}(x, y) =^{def} ∥x − y∥_{2}^{2/p}.

Since by [3] the Markov type 2 constant of ℓ_{2} satisfies M_{2}(ℓ_{2}) = 1, the Markov type p constant of (ℓ_{2}, d_{p}) satisfies

M_{p}(ℓ_{2}, d_{p}) = M_{2}(ℓ_{2}) = 1.  (124)

Lemma 6.4 with θ = 2/n and τ = 2/p asserts that the function

f_{2/n}^{2^{n^{2}}} : A_{2^{n^{2}}} → Y_{2/n}^{2^{n^{2}}}

is K-Lipschitz in the metric d_{p}, where

K ≲ 2^{^{\frac{n^{2}}{4}} (\frac{2}{p} − \frac{2}{n})}.

In light of (124), since the Y_{2/n}^{2^{n^{2}}} is finite dimensional it follows from Corollary 1.13 that there exists a function

F : ℓ_{2}^{2^{n^{2}}} → Y_{2/n}^{2^{n^{2}}}

that extends f_{2/n}^{2^{n^{2}}} and satisfies (117) with θ = 2/n, τ = 2/p and

L ≲ N_{p} (Y_{2/n}^{2^{n^{2}}}) .

We therefore deduce from Lemma 6.5 that

∀ p ∈ [2, n],  N_{p} (Y_{2/n}^{2^{n^{2}}}) ≳ 2^{n/2}.  (125)

Consider the ℓ_{1} direct sum

Y =^{def} (⨁_{n=1}^{∞} Y_{2/n}^{2^{n^{2}}})_{1} .

For every n ∈ ℕ the restriction to the nth coordinate is a 1-Lipschitz retraction from Y onto Y_{2/n}^{2^{n^{2}}}, so by Lemma 6.1 we have

∀ p ∈ [2, ∞), N_{p}(Y) ⩾ sup_{n∈ℕ} N_{p} (Y_{2/n}^{2^{n^{2}}}) =^{(125)} ∞.

By Corollary 6.3 we also have N_{p}(Y) = ∞ for p ∈ (0, 2), so in order to complete the proof of Theorem 1.14 it remains to show that Y is isomorphic to a subspace of ℓ_{1}. Since Y is the ℓ_{1} direct sum of the spaces

Y_{2/n}^{2^{n^{2}}} ⊆ ℓ_{1}^{5^{2^{n^{2}}}} ⊕ ℓ_{2}^{2^{n^{2}}},

it remains to recall that ℓ_{2}^{k} is (1 + ε)-isomorphic to a subspace of ℓ_{1} for every ε ∈ (0, 1) and k ∈ ℕ (e.g. by Dvoretzky’s theorem [15]). □

Proof of Theorem 1.17. By Lemma 6.4 and Lemma 6.5 with θ = τ = 1,

e (S^{n−1}, A_{n}, Y_{1}^{n}) ≳ \sqrt[4]{n}.  (126)

Since the diameter of A_{n} is at most 2 and the minimal nonzero distance in A_{n} is at least 1/\sqrt[4]{n}, the proof of Theorem 1.17 is complete. □

Observe in passing that since Y_{1}^{n} is 5^{n}-dimensional, (126) also implies (10) with Z_{5^{n}} = Y_{1}^{n}. For general m ∈ ℕ, choose n ∈ ℕ such that 5^{n−1} ⩽ m < 5^{n} and set Z_{m} = (Y_{1}^{n−1} ⊕ ℓ_{1}^{m−5^{n−1}})_{1}.

7. Comparison with Ball’s approach

Fix n ∈ ℕ, t ∈ [1, ∞) and let A ∈ M_{n}(ℝ) be a stochastic matrix that is reversible with respect to π ∈ Δ^{n−1}. Since A has norm 1 when viewed as an operator on L_{2}(π), we can consider the following matrix.

ℬ_{t}(A) =^{def} \frac{1}{t} ∑_{s=1}^{∞} (1 − \frac{1}{t})^{s} A^{s} ∈ M_{n}(ℝ).  (127)

We also denote the corresponding Green’s matrix by

G_{t}(A) =^{def} \frac{1}{t}I_{n} + ℬ_{t}(A) = \frac{1}{t} (I_{n} − (1 − \frac{1}{t}) A)^{−1} ,

where I_{n} ∈ M_{n}(ℝ) denotes the identity matrix.

In [3] Ball worked with following linear invariant of Banach spaces. For p ∈ (0, ∞) say that a Banach space (X, ∥ · ∥_{X}) has Markov cotype p with constant N ∈ (0, ∞) if for every n ∈ ℕ and t ∈ [1, ∞), if A = (a_{ij}) ∈ M_{n}(ℝ) is a symmetric stochastic matrix that is reversible relative to π ∈ Δ^{n−1} and x_{1}, …, x_{n} ∈ X then

(t − 1) ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}a_{ij} ∥∑_{k=1}^{n} G_{t}(A)_{ik}x_{k} − ∑_{ℓ=1}^{n} G_{t}(A)_{jℓ}x_{ℓ}∥_{X}^{p}

+ ∑_{i=1}^{n} π_{i} ∥x_{i} − ∑_{j=1}^{n} G_{t}(A)_{ij}x_{j}∥_{X}^{p} ⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}ℬ_{t}(A)_{ij}∥x_{i} − x_{j}∥_{X}^{p}.

As we shall see shortly, in Banach spaces Markov cotype p implies metric Markov cotype p as in Definition 2, but their equivalence remains open. Note that Ball proved in [3] that ℓ_{1} fails to have Markov cotype 2, so this question has relevance to Question 1.15.

In the closing remarks of his paper [3], Ball proposed the following two step definition of metric Markov cotype for metric spaces. First, given p ∈ [1, ∞) say that a metric space (X, d_{X}) is p-approximately convex if there exists K ∈ (0, ∞) with the following property. Fix m, n ∈ ℕ and let B = (b_{ij}) ∈ M_{n×m}(ℝ) and C = (c_{ij}) ∈ M_{n}(ℝ) be stochastic matrices, such that C is reversible relative to π ∈ Δ^{n−1}. Then for every z_{1}, …, z_{m} ∈ X there exist w_{1}, …, w_{n} ∈ X such that

∑_{i=1}^{n} ∑_{r=1}^{m} π_{i}b_{ir}d_{X}(w_{i}, z_{r})^{p} + ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}c_{ij}d_{X}(w_{i}, w_{j})^{p}

⩽ K^{p} ∑_{r=1}^{m} ∑_{s=1}^{m}(B^{∗}D_{π}CB)_{rs}d_{X}(z_{r}, z_{s})^{p}, (128)

where D_{π} ∈ M_{n}(ℝ) is given as in (75), i.e., it is the diagonal matrix whose diagonal equals π. Assuming that (X, d_{X}) is approximately convex, Ball defined it to have metric Markov cotype p if there exists N ∈ (0, ∞) such that for every n, t ∈ ℕ, if A = (a_{ij}) ∈ M_{n}(ℝ) is stochastic and reversible relative to π ∈ Δ^{n−1} then for every x_{1}, …, x_{n} ∈ X there exist y_{1}, …, y_{n} ∈ X such that

∑_{i=1}^{n} π_{i}d_{X}(x_{i}, y_{i})^{p} + (t − 1) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}π_{i}d_{X}(y_{i}, y_{j})^{p}

⩽ N^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}ℬ_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}. (129)

Denote by N_{p}^{B}(X) the infimum over those N ∈ (0, ∞) for which (129) holds true.

By Lemma 5.1 every metric space is a p-approximately convex (with K in (128) at most 6). So, the first step of Ball’s definition is not needed. Observe also that for Banach spaces Markov cotype p trivially implies (129). Moreover, there is an immediate link between (129) and (2): due to (127) we have 𝒜_{t}(A)_{ij} ≲ ℬ_{t}(A)_{ij} for every integer t ⩾ 2 and i, j ∈ {1, …, n}. Therefore every metric space (X, d_{X}) satisfies N_{p}^{B}(X) ≲ N_{p}(X). Despite the fact that one cannot bound from above (entry-wise) the matrix ℬ_{t}(A) by a constant multiple of the matrix 𝒜_{t}(A), the following lemma implies that N_{p}(X) ≲ N_{p}^{B}(X).

Lemma 7.1. Let (X, d_{X}) be a metric space. Suppose that n, t ∈ ℕ and A ∈ M_{n}(ℝ) is a stochastic matrix that is reversible relative to π ∈ Δ^{n−1}. Then for every p ∈ [1, ∞) and x_{1}, …, x_{n} ∈ X we have

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}ℬ_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}

≲ p2^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{⌈pt⌉}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}. (130)

Proof. Write u =^{def} ⌈pt⌉ and note that for every m ∈ ℕ we have

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{mu})_{ij}d_{X}(x_{i}, x_{j})^{p}

= ∑_{i∈{1,...,n}^{m+1}} π_{i_{1}} (∏_{a=1}^{m}(A^{u})_{i_{a},i_{a+1}}) d_{X}(x_{i_{1}}, x_{i_{m+1}})^{p}

⩽ ∑_{i∈{1,...,n}^{m+1}} π_{i_{1}} (∏_{a=1}^{m}(A^{u})_{i_{a},i_{a+1}}) m^{p−1} ∑_{a=1}^{m} d_{X}(x_{i_{a}}, x_{i_{a+1}})^{p} (131)

= m^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{u})_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽ (2m)^{p} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{u}(A)_{ij}d_{X}(x_{i}, x_{j})^{p},  (132)

where in (131) we used the triangle inequality and Hölder’s inequality, and in (132) we used Lemma 3.1.

SPECTRAL CALCULUS AND LIPSCHITZ EXTENSION 49

For every m ∈ ℕ ∪ {0} and r ∈ {0, …, u − 1} we have

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{mu+r})_{ij}d_{X}(x_{i}, x_{j})^{p}

= ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} π_{i}(A^{mu})_{ik}(A^{r})_{kj}d_{X}(x_{i}, x_{j})^{p}

⩽ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} π_{i}(A^{mu})_{ik}(A^{r})_{kj}(d_{X}(x_{i}, x_{k})^{p} + d_{X}(x_{k}, x_{j})^{p})

= 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{mu})_{ij}d_{X}(x_{i}, x_{j})^{p} + 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}(A^{r})_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽ \frac{1}{2} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}((4m)^{p}𝒜_{u}(A)_{ij} + 2^{p}(A^{r})_{ij})d_{X}(x_{i}, x_{j})^{p},  (133)

where in (133) we used (132).

Recalling the definition of ℬ_{t}(A) in (127), by writing every s ∈ ℕ as s = mu + r for unique m ∈ ℕ ∪ {0} and r ∈ {0, …, u − 1}, it follows from (133) that

∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}ℬ_{t}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}

= \frac{1}{t} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{m=0}^{∞} ∑_{r=0}^{u−1} (1 − \frac{1}{t})^{mu+r} π_{i}(A^{mu+r})_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽ \frac{4^{p}}{t} (∑_{m=0}^{∞} ∑_{r=0}^{u−1} m^{p} (1 − \frac{1}{t})^{mu+r}) ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i}𝒜_{u}(A)_{ij}d_{X}(x_{i}, x_{j})^{p}

+ \frac{2^{p}}{t} ∑_{i=1}^{n} ∑_{j=1}^{n} π_{i} (∑_{m=0}^{∞} ∑_{r=1}^{u} (1 − \frac{1}{t})^{mu+r} (A^{r})_{ij}) d_{X}(x_{i}, x_{j})^{p}. (134)

Recalling that u = ⌈pt⌉, we have

\frac{1}{t} ∑_{m=0}^{∞} ∑_{r=0}^{u−1} m^{p} (1 − \frac{1}{t})^{mu+r} ≲ p ∑_{m=1}^{∞} \frac{m^{p}}{e^{pm}}
⩽ \frac{p}{e^{p}} + p ∫_{0}^{∞} \frac{x^{p}}{e^{px}} dx  (135)
= \frac{p}{e^{p}} + \frac{Γ(p + 1)}{p^{p}} ≲ \frac{p}{e^{p}} ,  (136)

where (135) uses the fact that x ↦ x^{p}e^{−px} achieves its global maximum on [0, ∞) at x = 1, and (136) uses Stirling’s formula.

Next, for every i, j ∈ {1, …, n} we have

\frac{1}{t} ∑_{m=0}^{∞} ∑_{r=1}^{u} (1 − \frac{1}{t})^{mu+r} (A^{r})_{ij} ⩽ \frac{u}{t} (∑_{m=0}^{∞} e^{−mu/t}) 𝒜_{u}(A)_{ij}
≲ p𝒜_{u}(A)_{ij}.  (137)

(130) now follows by substituting (136) and (137) into (134). □

Acknowledgements. We are grateful to the anonymous referees for their helpful suggestions. M. M. was supported by ISF grants 221/07 and 93/11, BSF grant 2010021, and NSF grant CCF-0832797. Part of this work was completed while M. M. was a member of the Institute for Advanced Study at Princeton, NJ. A. N. was supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation. Part of this work was completed while A. N. was visiting Université Pierre et Marie Curie, Paris, France.

References

[1] A. Andoni, A. Naor, and O. Neiman. Snowflake universality of Wasserstein spaces. Preprint, 2010.

[2] A. Andoni, A. Naor, and O. Neiman. On isomorphic dimension reduction in ℓ_{1}. Preprint, 2011.

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

[4] K. Ball. The Ribe programme. Séminaire Bourbaki, exposé 1047, 2012.

[5] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[6] W. Ballmann. Lectures on spaces of nonpositive curvature, volume 25 of DMV Seminar. Birkhäuser Verlag, Basel, 1995. With an appendix by Misha Brin.

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

[8] J. Bourgain. A counterexample to a complementation problem. Compositio Math., 43(1):133–144, 1981.

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

[10] B. Brinkman, A. Karagiozova, and J. R. Lee. Vertex cuts, random walks, and dimension reduction in series-parallel graphs. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 621–630. ACM, New York, 2007.

[11] A. Brudnyi and Y. Brudnyi. Methods of geometric analysis in extension and trace problems. Volume 2, volume 103 of Monographs in Mathematics. Birkhäuser/Springer Basel AG, Basel, 2012.

[12] T. Christiansen and K. T. Sturm. Expectations and martingales in metric spaces. Stochastics, 80(1):1–17, 2008.

[13] J. Ding, J. R. Lee, and Y. Peres. Markov type and threshold embeddings.

Preprint available at http://arxiv.org/abs/1208.6088, 2012.

[14] S. Doss. Moyennes conditionnelles et martingales dans un espace métrique. C. R. Acad. Sci. Paris, 254:3630–3632, 1962.

[15] A. Dvoretzky. Some results on convex bodies and Banach spaces. In Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), pages 123–160. Jerusalem Academic Press, Jerusalem, 1961.

[16] M. Émery. Stochastic calculus in manifolds. Universitext. Springer-Verlag, Berlin, 1989. With an appendix by P.-A. Meyer.

[17] A. Es-Sahib and H. Heinich. Barycentre canonique pour un espace métrique à courbure négative. In Séminaire de Probabilités, XXXIII, volume 1709 of Lecture Notes in Math., pages 355–370. Springer, Berlin, 1999.

[18] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56:121– 155, 1976.

[19] T. Figiel, W. B. Johnson, and G. Schechtman. Factorizations of natural embeddings of l_{p}^{n} into L_{r}. I. Studia Math., 89(1):79–103, 1988.

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

[21] A. Grothendieck. Résumé de la théorie métrique des produits tensoriels topologiques. Bol. Soc. Mat. São Paulo, 8:1–79, 1953.

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

[23] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[24] W. B. Johnson, J. Lindenstrauss, and G. Schechtman. Extensions of Lipschitz maps into Banach spaces. Israel J. Math., 54(2):129–138, 1986.

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

[26] J. Jost. Nonpositive curvature: geometric and analytic aspects. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1997.

[27] N. J. Kalton. Spaces of Lipschitz and Hölder functions and their applications. Collect. Math., 55(2):171–217, 2004.

[28] N. J. Kalton. Lipschitz and uniform embeddings into ℓ_{∞}. Fund. Math., 212(1):53–69, 2011.

[29] N. J. Kalton. The uniform structure of Banach spaces. Math. Ann., 354(4):1247–1288, 2012.

[30] M. Kapovich and B. Leeb. On asymptotic cones and quasi-isometry classes of fundamental groups of 3-manifolds. Geom. Funct. Anal., 5(3):582–603, 1995.

[31] M. D. Kirszbraun. Über die zusammenziehenden und Lipschitzchen Transformationen. Fundam. Math., 22:77–108, 1934.

[32] U. Lang. Extendability of large-scale Lipschitz maps. Trans. Amer. Math. Soc., 351(10):3975–3988, 1999.

[33] U. Lang, B. Pavlović, and V. Schroeder. Extensions of Lipschitz maps into Hadamard spaces. Geom. Funct. Anal., 10(6):1527–1553, 2000.

[34] U. Lang and T. Schlichenmaier. Nagata dimension, quasisymmetric embeddings, and Lipschitz extensions. Int. Math. Res. Not., (58):3625–3655, 2005.

[35] U. Lang and V. Schroeder. Kirszbraun’s theorem and metric spaces of bounded curvature. Geom. Funct. Anal., 7(3):535–560, 1997.

[36] J. R. Lee and A. Naor. Extending Lipschitz functions via random metric partitions. Invent. Math., 160(1):59–95, 2005.

[37] J. Lindenstrauss and A. Pełczyński. Absolutely summing operators in L_{p}- spaces and their applications. Studia Math., 29:275–326, 1968.

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

[39] K. Makarychev and Y. Makarychev. Metric extension operators, vertex sparsifiers and Lipschitz extendability. In 51th Annual IEEE Symposium on Foundations of Computer Science, pages 255–264, 2010.

[40] B. Maurey. Théorèmes de factorisation pour les opérateurs linéaires à valeurs dans les espaces L^{p}. Société Mathématique de France, Paris, 1974. With an English summary, Astérisque, No. 11.

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

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

[43] M. Mendel and A. Naor. Nonlinear spectral calculus and super-expanders. To appear in Inst. Hautes Études Sci. Publ. Math., available at

http://arxiv.org/abs/1207.4705, 2012.

[44] M. Mendel and A. Naor. Expanders with respect to Hadamard spaces and random graphs. Preprint, 2013.

[45] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics. J. Eur. Math. Soc. (JEMS), 15(1):287–337, 2013.

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

[47] G. J. Minty. On the extension of Lipschitz, Lipschitz-Hölder continuous, and monotone functions. Bull. Amer. Math. Soc., 76:334–339, 1970.

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

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

[50] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces. Duke Math. J., 134(1):165– 197, 2006.

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

[52] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Compos. Math., 147(5):1546–1572, 2011.

[53] A. Navas. An L^{1} ergodic theorem with values in a non-positively curved space via a canonical barycenter map. Ergodic Theory Dynam. Systems, FirstView:1– 15.

[54] S.-i. Ohta. Extending Lipschitz and Hölder maps between metric spaces. Positivity, 13(2):407–425, 2009.

[55] S.-i. Ohta. Markov type of Alexandrov spaces of non-negative curvature. Mathematika, 55(1-2):177–189, 2009.

[56] A. Pietsch. Absolut p-summierende Abbildungen in normierten Räumen. Studia Math., 28:333–353, 1966/1967.

[57] G. Pisier. Martingales with values in uniformly convex spaces. Israel J. Math., 20(3-4):326–350, 1975.

[58] G. Schechtman. More on embedding subspaces of L_{p} in l_{r}^{n}. Compositio Math., 61(2):159–169, 1987.

[59] K.-T. Sturm. Nonlinear martingale theory for processes with values in metric spaces of nonpositive curvature. Ann. Probab., 30(3):1195–1222, 2002.

[60] K.-T. Sturm. Probability measures on metric spaces of nonpositive curvature. In Heat kernels and analysis on manifolds, graphs, and metric spaces (Paris, 2002), volume 338 of Contemp. Math., pages 357–390. Amer. Math. Soc., Providence, RI, 2003.

[61] M. Talagrand. Embedding subspaces of L_{1} into l_{1}^{N}. Proc. Amer. Math. Soc., 108(2):363–369, 1990.

Mathematics and Computer Science Department, The Open University of Israel, 1 University Road, P.O. Box 808, Raanana 43107,Israel

E-mail address: manorme@openu.ac.il

Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York NY 10012, USA

E-mail address: naor@cims.nyu.edu