COMPARISON OF METRIC SPECTRAL GAPS

ASSAF NAOR

Abstract. Let A = (a_{ij}) ∈ M_{n}(ℝ) be an n by n symmetric stochastic matrix. For p ∈ [1, ∞) and a metric space (X, d_{X}), let γ(A, d_{X}^{p}) be the infimum over those γ ∈ (0, ∞] for which every x_{1}, …, x_{n} ∈ X satisfy

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

Thus γ(A, d_{X}^{p}) measures the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel d_{X}^{p} : X×X → [0, ∞). We study pairs of metric spaces (X, d_{X}) and (Y, d_{Y}) for which there exists Ψ : (0, ∞) → (0, ∞) such that γ(A, d_{X}^{p}) ⩽ Ψ (γ(A, d_{Y}^{p})) for every symmetric stochastic A ∈ M_{n}(ℝ) with γ(A, d_{Y}^{p}) < ∞. When Ψ is linear a complete geometric characterization is obtained.

Our estimates on nonlinear spectral gaps yield new embeddability results as well as new nonembeddability results. For example, it is shown that if n ∈ ℕ and p ∈ (2, ∞) then for every f_{1}, …, f_{n} ∈ L_{p} there exist x_{1}, …, x_{n} ∈ L_{2} such that

∀ i, j ∈ {1, …, n}, ∥x_{i} − x_{j}∥_{2} ≲ p∥f_{i} − f_{j}∥_{p},  (1)

and

∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{2}^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} ∥f_{i} − f_{j}∥_{p}^{2}.

This statement is impossible for p ∈ [1, 2), and the asymptotic dependence on p in (1) is sharp. We also obtain the best known lower bound on the L_{p} distortion of Ramanujan graphs, improving over the work of Matoušek. Links to Bourgain–Milman–Wolfson type and a conjectural nonlinear Maurey–Pisier theorem are studied.

Contents

1. Introduction 2 1.1. Applications to bi-Lipschitz embeddings 8 1.2. Ozawa’s localization argument for Poincaré inequalities 9 1.3. Average distortion embeddings and nonlinear type 11

2010 Mathematics Subject Classification. 51F99,05C12,05C50,46B85. Key words and phrases. Metric embeddings, nonlinear spectral gaps, expanders,

nonlinear type.

Supported by NSF grant CCF-0832795, BSF grant 2010021, the Packard Foundation and the Simons Foundation.

2. Absolute spectral gaps 16 3. Duality 19 4. Interpolation and Markov type 22 4.1. Ramanujan graphs and Alon–Roichman graphs 28 4.2. Curved Banach spaces in the sense of Pisier 32 4.3. An interpolation inequality for nonlinear spectral gaps 34 5. Proof of Theorem 1.10 38 5.1. Limitations of Ozawa’s method 43 6. Bourgain–Milman–Wolfson type 46 6.1. On the Maurey–Pisier problem for BMW type 46 6.2. Obstructions to average distortion embeddings of cubes 52 7. Existence of average distortion embeddings 55 7.1. Random zero sets 55 7.2. Localized weakly bi-Lipschitz embeddings 58 7.3. Dimension reduction 61 7.4. Proofs of Proposition 7.1 and Proposition 7.5 64 Appendix: a refinement of Markov type 69 References 74

1. Introduction

The decreasing rearrangement of the eigenvalues of an n by n symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) is denoted below by

1 = λ_{1}(A) ⩾ λ_{2}(A) ⩾ … ⩾ λ_{n}(A).

We also set

λ(A) =^{def} max_{i∈{2,...,n}} |λ_{i}(A)| = max {λ_{2}(A), −λ_{n}(A)} .  (2)

For p ∈ [1, ∞) and a metric space (X, d_{X}), we denote by γ(A, d_{X}^{p}) the infimum over those γ ∈ (0, ∞] for which every x_{1}, …, x_{n} ∈ X satisfy

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

Thus for p = 2 and X = (ℝ, d_{ℝ}), where we denote d_{ℝ}(x, y) =^{def} |x − y| for every x, y ∈ ℝ, we have

γ(A, d_{ℝ}^{2}) = \frac{1}{1 − λ_{2}(A)}.  (4)

For this reason one thinks of γ(A, d_{X}^{p}) as measuring the magnitude of the nonlinear spectral gap of the matrix A with respect to the kernel d_{X}^{p} : X × X → [0, ∞). See [MN12] for more information on the topic of nonlinear spectral gaps.

Suppose that (X, d_{X}) is a metric space with |X| ⩾ 2 and fix distinct points a, b ∈ X. Fix also p ∈ [1, ∞), n ∈ ℕ, and an n by n symmetric stochastic matrix A = (a_{ij}). By considering x_{1}, …, x_{n} ∈ {a, b} in (3), we see that

γ(A, d_{X}^{p}) ⩾ max_{∅≠S⊊\{1,...,n\}} \frac{|S|(n − |S|)}{n ∑_{(i,j)∈S×(\{1,...,n\}∖S)} a_{ij}} .

It therefore follows from Cheeger’s inequality [Che70] (in our context, see [JS88] and [LS88]) that

γ(A, d_{X}^{p}) ≳ \frac{1}{\sqrt{1 − λ_{2}(A)}}.  (5)

Consequently, any finite upper bound on γ(A, d_{X}^{p}) immediately implies a spectral gap estimate for the matrix A. The ensuing discussion always tacitly assumes that metric spaces contain at least two points.

In (5), and in what follows, the notations U ≲ V and V ≳ U mean that U ⩽ CV for some universal constant C ∈ (0, ∞). If we need to allow C to depend on parameters, we indicate this by subscripts, thus e.g. U ≲_{β} V means that U ⩽ C(β)V for some C(β) ∈ (0, ∞) which is allowed to depend only on the parameter β. The notation U ≍ V stands for (U ≲ V) ∧ (V ≲ U), and correspondingly the notation U ≍_{β} V stands for (U ≲_{β} V) ∧ (V ≲_{β} U).

A simple application of the triangle inequality (see [MN12, Lem. 2.1]) shows that γ(A, d_{X}^{p}) is finite if and only if λ_{2}(A) < 1 (equivalently, the matrix A is ergodic, or the graph on {1, …, n} whose edges are the pais {i, j} for which a_{ij} > 0 is connected).

It is often quite difficult to obtain good estimates on nonlinear spectral gaps. This difficulty is exemplified by several problems in metric geometry that can be cast as estimates on nonlinear spectral gaps: see [Laf08, Laf09, MN12, MN13a, Lia13, dlS13] for some specific examples, as well as the ensuing discussion on nonlinear type. In this general direction, here we investigate the following basic “meta-problem.”

Question 1.1 (Comparison of nonlinear spectral gaps). Given p ∈ [1, ∞), characterize those pairs of metric spaces (X, d_{X}) and (Y, d_{Y}) for which there exists an increasing function Ψ = Ψ_{X,Y} : (0, ∞) → (0, ∞) such that for every n ∈ ℕ and every ergodic symmetric stochastic A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{p}) ⩽ Ψ (γ(A, d_{Y}^{p})) .  (6)

The case p = 2 and (Y, d_{Y}) = (ℝ, d_{ℝ}) of Question 1.1 is especially important, so we explicitly single it out as follows. See also the closely related question that Pisier posed as Problem 3.1 in [Pis10].

Question 1.2 (Bounding nonlinear gaps by linear gaps). Characterize those metric spaces (X, d_{X}) for which there exists an increasing function Ψ = Ψ_{X} : (0, ∞) → (0, ∞) such that for every n ∈ ℕ and every ergodic symmetric stochastic A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{p}) ⩽ Ψ (\frac{1}{1 − λ_{2}(A)}) .  (7)

Question 1.1 and Question 1.2 seem to be difficult, and they might not have a useful simple-to-state answer. As an indication of this, in [MN13a] it is shown that there exists a CAT (0) metric space (X, d_{X}), and for each k ∈ ℕ there exist n_{k} ∈ ℕ with lim_{k→∞} n_{k} = ∞ such that there are symmetric stochastic matrices A_{k}, B_{k} ∈ M_{n_{k}}(ℝ) with

sup_{k∈ℕ} λ_{2}(A_{k}) < 1 and  sup_{k∈ℕ} λ_{2}(B_{k}) < 1,

yet

sup_{k∈ℕ} γ(A_{k}, d_{X}^{2}) < ∞ and  sup_{k∈ℕ} γ(B_{k}, d_{X}^{2}) = ∞.

Such questions are difficult even in the setting of Banach spaces: a wellknown open question (see e.g. [Pis10]) asks whether (7) holds true when X is a uniformly convex Banach space. If true, this would yield a remarkable “linear to nonlinear transference principle for spectral gaps,” establishing in particular the existence of super-expanders (see [MN12]) with logarithmic girth, a result which could then be used in conjunction with Gromov’s random group construction [Gro03] to rule out the success of an approach to the Novikov conjecture that was discovered by Kasparov and Yu [KY06]. There is little evidence, however, that every uniformly convex Banach space admits an inequality such as (7), and we suspect that (7) fails for some uniformly convex Banach spaces.

When the function Ψ appearing in (6) can be taken to be linear, i.e., Ψ(t) = Kt for some K ∈ (0, ∞), Theorem 1.3 below provides the following geometric answer to Question 1.1. Given p ∈ [1, ∞) and a metric space (Y, d_{Y}), for every m ∈ ℕ we denote by ℓ_{p}^{m}(Y) the metric space Y^{m} equipped with the metric

∀ x, y ∈ Y^{m}, d_{ℓ_{p}^{m}(Y)}(x, y) =^{def} (∑_{i=1}^{m} d_{Y} (x_{i}, y_{i})^{p})^{\frac{1}{p}} .

Recall also the standard notation ℓ_{p}^{m} = ℓ_{p}^{m}(ℝ). A coordinate-wise application of (3) shows that every symmetric stochastic A satisfies

∀ m ∈ ℕ,  γ(A, d_{Y}^{p}) = γ(A, d_{ℓ_{p}^{m}(Y)}^{p}) .  (8)

Fixing D ∈ [1, ∞), suppose that (X, d_{X}) is a metric space such that for every n ∈ ℕ and x_{1}, …, x_{n} ∈ X there exists m ∈ ℕ and a nonconstant mapping f : {x_{1}, …, x_{n}} → ℓ_{p}^{m}(Y) such that

∑_{i=1}^{n} ∑_{j=1}^{n} d_{ℓ_{p}^{m}(Y)}(f(x_{i}), f(x_{j}))^{p} ⩾ \frac{∥f∥_{Lip}^{p}}{D} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}, (9)

where ∥f∥_{Lip} denotes the Lipschitz constant of f, i.e.,

∥f∥_{Lip} =^{def} max_{\begin{matrix}x,y∈\{x_{1},...,x_{n}\} \\ x≠y \end{matrix}} \frac{d_{ℓ_{p}^{m}(Y)}(f(x), f(y))}{d_{X}(x, y)}.

Then for every symmetric stochastic matrix A ∈ M_{n}(ℝ),

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p} ⩽^{(9)} \frac{D}{n^{2}∥f∥_{Lip}^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{ℓ_{p}^{m}(Y)}(f(x_{i}), f(x_{j}))^{p}

⩽^{(8)} \frac{Dγ(A, d_{Y}^{p})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij} \frac{d_{ℓ_{p}^{m}(Y)}(f(x_{i}), f(x_{j}))^{p}}{∥f∥_{Lip}^{p}}

⩽ \frac{Dγ(A, d_{Y}^{p})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}.  (10)

Consequently, γ(A, d_{X}^{p}) ⩽ Dγ(A, d_{Y}^{p}).

The above simple argument, combined with standard metric embedding methods, already implies that a variety of metric spaces satisfy the spectral inequality (7) with Ψ linear. This holds in particular when (X, d_{X}) belongs to one of the following classes of metric spaces: doubling metric spaces, compact Riemannian surfaces, Gromov hyperbolic spaces of bounded local geometry, Euclidean buildings, symmetric spaces, homogeneous Hadamard manifolds, and forbidden-minor (edgeweighted) graph families; this topic is treated in Section 7. We will also see below that the same holds true for certain Banach spaces, including L_{p}(μ) spaces for p ∈ [2, ∞).

The following theorem asserts that the above reasoning using metric embeddings is the only way to obtain an inequality such as (6) with Ψ linear. Its proof is a duality argument that is inspired by the proof of a lemma of K. Ball [Bal92, Lem. 1.1] (see also [MN13b, Lem 5.2]).

Theorem 1.3. Fix n ∈ ℕ and p, K ∈ [1, ∞). Given two metric spaces (X, d_{X}) and (Y, d_{Y}), the following assertions are equivalent.

(1) For every symmetric stochastic n by n matrix A we have

γ(A, d_{X}^{p}) ⩽ Kγ(A, d_{Y}^{p}).  (11)

(2) For every D ∈ (K, ∞) and every x_{1}, …, x_{n} ∈ X there exists m ∈ ℕ and a nonconstant mapping f : {x_{1}, …, x_{n}} → ℓ_{p}^{m}(Y) that satisfies

∑_{i=1}^{n} ∑_{j=1}^{n} d_{ℓ_{p}^{m}(Y)}(f(x_{i}), f(x_{j}))^{p} ⩾ \frac{∥f∥_{Lip}^{p}}{D} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.

It is worthwhile to single out the special case of Theorem 1.3 that corresponds to Question 1.2, in which case the embeddings are into ℓ_{2}.

Corollary 1.4. Fix n ∈ ℕ and K ∈ [1, ∞). Given a metric space (X, d_{X}), the following assertions are equivalent.

(1) For every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{2}) ⩽ \frac{K}{1 − λ_{2}(A)}.

(2) For every D ∈ (K, ∞) and every x_{1}, …, x_{n} ∈ X there exists a nonconstant mapping f : {x_{1}, …, x_{n}} → ℓ_{2} that satisfies

∑_{i=1}^{n} ∑_{j=1}^{n} ∥f(x_{i}) − f(x_{j})∥_{ℓ_{2}}^{2} ⩾ \frac{∥f∥_{Lip}^{2}}{D} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{2}.

In Section 4 below we prove the following theorem.

Theorem 1.5. For every p ∈ [2, ∞), every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{p^{2}}{1 − λ_{2}(A)}.  (12)

Inequality (12) is proved in Section 4 via a direct argument using analytic and probabilistic techniques, but once this inequality is established one can use duality through Corollary 1.4 to deduce the following new Hilbertian embedding result for arbitrary finite subsets of ℓ_{p}.

Corollary 1.6. If n ∈ ℕ and p ∈ (2, ∞) then for every x_{1}, …, x_{n} ∈ ℓ_{p} there exist y_{1}, …, y_{n} ∈ ℓ_{2} such that

∀ i, j ∈ {1, …, n},  ∥y_{i} − y_{j}∥_{ℓ_{2}} ≲ p∥x_{i} − x_{j}∥_{ℓ_{p}},  (13)

and

∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{2}}^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}.

The dependence on p in (13) is sharp up to the implicit universal constant, and the conclusion of Corollary 1.6 is false for p ∈ [1, 2) even if one allows any dependence on p in (13) (provided it is independent of n): for the former statement see Lemma 1.11 below and for the latter statement see Lemma 1.12 below. It would be interesting to find a constructive proof of Corollary 1.6, i.e., a direct proof that does not rely on duality to show that the desired embedding exists.

Remark 1.7. Questions in the spirit of Theorem1.5 have been previously studied by Matoušek [Mat97], who proved that there exists a universal constant C ∈ (0, ∞) such that for every n ∈ ℕ and every n by n symmetric stochastic matrix A ∈ M_{n}(ℝ),

p ∈ [2, ∞) ⟹ γ(A, ∥ · ∥_{ℓ_{p}}^{p}) ⩽ \frac{(Cp)^{p}}{(1 − λ_{2}(A))^{p/2}} .  (14)

See [BLMN05, Lem. 5.5] and [NS11, Lem. 4.4] for the formulation and proof of this fact (which is known as Matoušek’s extrapolation lemma for Poincaré inequalities) in the form stated in (14). In order to obtain an embedding result such as Corollary 1.6 one needs to bound γ(A, ∥ · ∥_{ℓ_{p}}^{2}) rather than γ(A, ∥ · ∥_{ℓ_{p}}^{p}) by a quantity that grows linearly with 1/(1 − λ_{2}(A)). We do not see how to use Matoušek’s approach in [Mat97] to obtain such an estimate, and we therefore use an entirely different method (specifically, complex interpolation and Markov type) to prove Theorem 1.5.

As stated above, when p ∈ [1, 2) the analogue of Theorem 1.5 can hold true only if we allow the right hand side of (12) to depend on n. Specifically, we ask the following question.

Question 1.8. Is it true that for every p ∈ [1, 2], every n ∈ ℕ and every n by n symmetric stochastic matrix A we have

γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{(log n)^{\frac{2}{p} −1}}{1 − λ_{2}(A)} ?

Due to Theorem 1.3, an affirmative answer to Question 1.8 is equivalent to the assertion that if p ∈ [1, 2] then for every x_{1}, …, x_{n} ∈ ℓ_{p} there exist y_{1}, …, y_{n} ∈ ℓ_{2} that satisfy

∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{2}^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{p}^{2},

and

∀ i, j ∈ \{1, …, n\}, ∥y_{i} − y_{j}∥_{2} ≲ (log n)^{\frac{1}{p} − \frac{1}{2}} ∥x_{i} − x_{j}∥_{p}.

We conjecture that the answer to Question 1.8 is positive. As partial motivation for this conjecture, we note that by an important theorem of Arora, Rao and Vazirani [ARV09] the answer is positive when p = 1.

A possible approach towards proving this conjecture for p ∈ (1, 2) is to investigate whether the quantity γ(A, ∥ · ∥_{X}^{2}) behaves well under interpolation. In our case one would write \frac{1}{p} = \frac{θ}{2} + \frac{1−θ}{1} for an appropriate θ ∈ (0, 1) and ask whether or not it is true that for every n ∈ ℕ every n by n symmetric stochastic matrix A satisfies

γ(A, ∥ · ∥_{p}^{2}) ≲ γ(A, ∥ · ∥_{2}^{2})^{θ} · γ(A, ∥ · ∥_{1}^{2})^{1−θ}.  (15)

Investigating the possible validity such interpolation inequalities for nonlinear spectral gaps is interesting in its own right; in Section 4.3 we derive a weaker interpolation inequality in this spirit.

1.1. Applications to bi-Lipschitz embeddings. The (bi-Lipschitz) distortion of a metric space (X, d_{X}) in a metric space (Y, d_{Y}), denoted c_{Y} (X), is define to be the infimum over those D ∈ [1, ∞) for which there exists s ∈ (0, ∞) and a mapping f : X → Y that satisfies

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

Set c_{Y} (x) = ∞ if no such D exists. When Y = ℓ_{p} for some p ∈ [1, ∞] we use the simpler notation c_{p}(X) = c_{ℓ_{p}}(X). The parameter c_{2}(X) is known in the literature as the Euclidean distortion of X.

The Fréchet–Kuratowski embedding (see e.g. [Hei01]) shows that c_{∞}(X) = 1 for every separable metric space X. We therefore define p(X) to be the infimum over those p ∈ [2, ∞] such that c_{p}(X) < 10. The choice of the number 10 here is arbitrary, and one can equally consider any fixed number bigger than 1 in place of 10 to define the parameter p(X); we made this arbitrary choice rather than adding an additional parameter only for the sake of notational simplicity.

For n ∈ ℕ and d ∈ {3, …, n − 1} let p(n, d) be the expectation of p(G) when G is distributed uniformly at random over all connected nvertex d-regular graphs, equipped with the shortest-path metric. Thus, if p = p(n, d) then in expectation a connected n-vertex d-regular graph G satisfies c_{p}(G) ⩽ 10. In [Mat97] Matoušek evaluated the asymptotic dependence of the largest possible distortion of an n-point metric space in ℓ_{p}, yielding the estimate p(n, d) ≳ log_{d} n, which is an asymptotically sharp bound if d = O(1). As a consequence of our proof of Theorem 1.5, it turns out that Matoušek’s bound is not sharp as a function of the degree d. Specifically, in Section 4.1 we prove the following result.

Proposition 1.9. For every n ∈ ℕ and d ∈ {3, …, n − 1} we have

d ⩽ e^{(log n)^{2/3}} ⟹ p(n, d) ≳ \frac{log n}{\sqrt{log d}},  (16)

and

d ⩾ e^{(log n)^{2/3}} ⟹ p(n, d) ≳ (log_{d} n)^{2} .  (17)

The significance of the quantity log_{d} n appearing in Matoušek’s bound is that up to universal constant factors it is the typical diameter of a uniformly random connected n-vertex d-regular graph [BFdlV82]. Thus, in (16) there must be some restriction on the size of d relative to n since when d is at least a constant power of n the typical diameter of G is O(1), and therefore c_{p}(G) ⩽ c_{2}(G) = O(1). Both (16) and (17) assert that p(n, d) tends to ∞ faster than the typical diameter of G when n^{o(1)} = d → ∞ (note also that (17) is consistent with the fact that p(n, d) must become bounded when d is large enough). While we initially expected Matoušek’s bound to be sharp, Proposition (1.9) indicates that the parameter p(n, d), and more generally the parameter p(X) for a finite metric space (X, d_{X}), deserves further investigation. In particular, we make no claim that Proposition (1.9) is sharp.

The link between Theorem 1.5 and Proposition 1.9 is that our proof of Theorem 1.5 yields the following bound, which holds for every n ∈ ℕ, every n by n symmetric stochastic matrix A, and every p ∈ [2, ∞).

γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{p}{1 − λ(A)^{2/p}} ,  (18)

where we recall that λ(A) was defined in (2). Proposition 1.9 is deduced in Section 4.1 from (18) through a classical argument of Linial, London and Rabinovich [LLR95]. The bounds appearing in Proposition 1.9 hold true with p(n, d) replaced by p(G) when G is an n-vertex d-regular Ramanujan graph [LPS88, Mar88], and it is an independently interesting open question to evaluate c_{p}(G) up to universal constant factors when G is Ramanujan. Some estimates in this direction are obtained in Section 4.1, where a similar question is also studied for Abelian Alon–Roichman graphs [AR94].

1.2. Ozawa’s localization argument for Poincaré inequalities. Theorem 1.10 below provides a partial answer to Question 1.1 when X and Y are certain Banach spaces. Its proof builds on an elegant idea of Ozawa [Oza04] that was used in [Oza04] to rule out coarse embeddings of expanders into certain Banach spaces. While Ozawa’s original argument did not yield a nonlinear spectral gap inequality in the form that we require here, it can be modified so as to yield Theorem 1.10; this is carried out in Section 5.

Throughout this article the unit ball of a Banach space (X, ∥ · ∥_{X}) is denoted by

B_{X} =^{def} {x ∈ X : ∥x∥_{X} ⩽ 1}.

Theorem 1.10. Let (X, ∥ · ∥_{X}) and (Y, ∥ · ∥_{Y}) be Banach spaces. Suppose that α, β : [0, ∞) → [0, ∞) are increasing functions, β is concave, and

lim_{t→0} α(t) = lim_{t→0} β(t) = 0.

Suppose also that there exists a mapping ϕ : B_{X} → Y that satisfies

∀ x, y ∈ B_{X}, α (∥x − y∥_{X}) ⩽ ∥ϕ(x) − ϕ(y)∥_{Y} ⩽ β (∥x − y∥_{X}) . (19)

Then for every q ∈ [1, ∞), every n ∈ ℕ, and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, ∥ · ∥_{X}^{q}) ⩽ 8^{q+1}γ(A, ∥ · ∥_{Y}^{q}) + \frac{8^{q}}{β^{−1} (_{\frac{α(1/4)}{8γ(A,∥·∥_{Y}^{q})^{1/q}}} )^{q}} .  (20)

The key point of Theorem 1.10 is that one can use local information such as (19) in order to deduce a Poincaré-type inequality such as (3).

Certain classes of Banach spaces X are known to satisfy the assumptions of Theorem 1.10 when Y is a Hilbert space. These include: L_{p}(μ) spaces for p ∈ [1, ∞), as shown by Mazur [Maz29] (see [BL00, Ch. 9, Sec. 1]); Banach spaces of finite cotype with an unconditional basis, as shown by Odell and Schlumprecht [OS94]; more generally, Banach lattices of finite cotype, as shown by Chaatit [Cha95] (see [BL00, Ch. 9, Sec. 2]); Schatten classes of finite cotype (and more general noncommutative L_{p} spaces), as shown by Raynaud [Ray02]. For these classes of Banach spaces Theorem 1.10 furnishes a positive answer to Question 1.2 with Ψ given by the right hand side of (20).

Mazur proved [Maz29] that for every p ∈ [1, ∞), if X = ℓ_{p} and Y = ℓ_{2} then there exists a mapping ϕ : X → Y that satisfies (19) with α(t) = 2(t/2)^{p/2} and β(t) = pt if p ∈ [2, ∞) and α(t) = t/3 and β(t) = 2t^{p/2} if p ∈ [1, 2] (these estimates are recalled in Section 3). Therefore, it follows from Theorem 1.10 that for every p ∈ [1, ∞), every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

1 ⩽ p ⩽ 2 ⟹ γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{1}{(1 − λ_{2}(A))^{2/p}} ,  (21)

and

2 ⩽ p < ∞ ⟹ γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{p^{2}8^{p}}{1 − λ_{2}(A)}.  (22)

As explained in Section 1.3.1, both (21) and (22) are sharp in terms of the asymptotic dependence on 1−λ_{2}(A), but in terms of the dependence on p the bound (22) is exponentially worse than the (sharp) bound (12). In Section 5.1 we show that this exponential loss is inherent to Ozawa’s method, in the sense that for p ∈ (2, ∞), if ϕ : ℓ_{p} → ℓ_{2} satisfies (19) with β(t) = Kt for some K ∈ (0, ∞) and every t ∈ (0, ∞) (this is to ensure that (20) yields an upper bound on γ(A, ∥ · ∥_{ℓ_{p}}^{2}) that grows linearly with (1 − λ_{2}(A))^{−1}), then necessarily K/α(1/4) ≳ 2^{3p/2}.

Note that (22) suffices via duality (i.e., Corollary 1.4) to obtain an embedding result for arbitrary subsets of ℓ_{p} as in Corollary 1.6, with exponentially worse dependence on p. Yet another proof of such an embedding statement appears in Section 7, though it also yields a bound in terms of p that is exponentially worse than Corollary 1.6. We do not know how to prove the sharp statement of Corollary 1.6 other than through Theorem 1.5, whose proof is not as elementary as the above mentioned proofs that yield an exponential dependence on p.

1.3. Average distortion embeddings and nonlinear type. For p, q ∈ (0, ∞) the (p, q)-average distortion of (X, d_{X}) into (Y, d_{Y}), denoted Av_{Y}^{(p,q)}(X) ∈ [1, ∞), is the infimum over those D ∈ [1, ∞] such that for every n ∈ ℕ and every x_{1}, …, x_{n} ∈ X there exists a nonconstant Lipschitz function f : {x_{1}, …, x_{n}} → Y that satisfies

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f(x_{i}), f(x_{j}))^{p})^{\frac{1}{p}} ⩾ \frac{∥f∥_{Lip}}{D} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{q})^{\frac{1}{q}} .

When p = q we use the simpler notation Av_{Y}^{(p)}(X) =^{def} Av_{Y}^{(p,p)}(X).

The notion of average distortion and its relevance to approximation algorithms was brought to the fore in the influential work [Rab08] of Rabinovich. Parts of Section 7 below are inspired by Rabinovich’s ideas in [Rab08]. Earlier applications of this notion include the work of Alon, Boppana and Spencer [ABS98] that related average distortion to asymptotically sharp isoperimetric theorems on products spaces; see Remark 7.9 below. In the linear theory of Banach spaces average distortion embeddings have been studied in several contexts; see e.g. the work on random sign embeddings in [Elt83, FJS88].

With the above terminology, Theorem 1.3 asserts that the linear dependence (11) holds true if and only if for every finite subset S ⊆ X there exists m ∈ ℕ such that

Av_{ℓ_{p}^{m}(Y)}^{(p)}(S, d_{X}) ⩽ K^{1/p}.

By Corollary 1.6, if p ∈ [2, ∞) then

Av_{ℓ_{2}}^{(2)}(ℓ_{p}) ≲ p.  (23)

As stated earlier, the estimate (23) cannot be improved (up to the implicit constant factor): this is a special case of the following lemma.

Lemma 1.11. For every p, q, r, s ∈ [1, ∞) with 2 ⩽ q ⩽ p and every n ∈ ℕ there exist x_{1}, …, x_{n} ∈ ℓ_{p} such that if y_{1}, …, y_{n} ∈ ℓ_{q} satisfy

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{r})^{\frac{1}{r}} = (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{ℓ_{p}}^{s})^{\frac{1}{s}} , (24)

then there exist i, j ∈ {1, …, n} such that

∥y_{i} − y_{j}∥_{ℓ_{q}} ≳ \frac{p}{q + r} · ∥x_{i} − x_{j}∥_{ℓ_{p}} > 0.

The proof of Lemma 1.11 is given in Section 4.3. It suffices to say at this juncture that the points x_{1}, …, x_{n} ∈ ℓ_{p} are the images of the vertices of a bounded degree expanding n-vertex regular graph under Matoušek’s ℓ_{p}-variant [Mat97] of Bourgain’s embedding [Bou85].

We also stated earlier that Corollary 1.6 fails for p ∈ [1, 2): this is a special case of the following lemma.

Lemma 1.12. Fix p, q, r, s ∈ [1, ∞) with p ∈ [1, 2) and q ∈ (p, ∞). For arbitrarily large n ∈ ℕ there exist x_{1}, …, x_{n} ∈ ℓ_{p} such that for every y_{1}, …, y_{n} ∈ ℓ_{q} with

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{r})^{\frac{1}{r}} = (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{ℓ_{p}}^{s})^{\frac{1}{s}} ,

there exist i, j ∈ {1, …, n} such that

∥y_{i} − y_{j}∥_{ℓ_{q}} ≳ \frac{(log n)^{\frac{1}{p} − \frac{1}{min\{q,2\}}}}{\sqrt{q + r}} · ∥x_{i} − x_{j}∥_{ℓ_{p}} > 0.  (25)

1.3.1. Bourgain–Milman–Wolfson type. The reason for the validity of the lower bound (25) is best explained in the context of nonlinear type: a metric invariant that furnishes an obstruction to the existence of average distortion embeddings. Let 𝔽_{2} be the field of cardinality 2 and for n ∈ ℕ let e_{1}, …, e_{n} be the standard basis of 𝔽_{2}^{n}. We also write e = e_{1} + … + e_{n}. Following Bourgain, Milman and Wolfson [BMW86], given p, T ∈ (0, ∞), a metric space (X, d_{X}) is said to have BMW type p with constant T if for every n ∈ ℕ every f : 𝔽_{2}^{n} → X satisfies

∑_{x∈𝔽_{2}^{n}} d_{Y} (f(x), f(x+e))^{2} ⩽ T^{2}n^{\frac{2}{p} −1} ∑_{i=1}^{n} ∑_{x∈𝔽_{2}^{n}} d_{Y} (f(x), f(x + e_{i}))^{2} . (26)

(X, d_{X}) has BMW type p if it has BMW type p with constant T for some T ∈ (0, ∞); in this case the infimum over those T ∈ (0, ∞) for which (26) holds true is denoted BMW_{p}(X). For background on this notion we refer to [BMW86], as well as [Pis86, NS02, Nao12a]. These references also contain a description of the closely related important notion of Enflo type [Enf76], a notion whose definition is recalled below but will not be further investigated here.

The simple proof of the following lemma appears in Section 6.

Lemma 1.13. Fix p ∈ (0, ∞). For every two metric spaces (X, d_{X}) and (Y, d_{Y}) we have

BMW_{p}(X) ⩽ 2Av_{Y}^{(2)}(X) · BMW_{p}(Y).

The case r = s = 2 of Lemma 1.12 follows from Lemma 1.13 and the computations of BMW type that appear in the literature. The remaining cases of Lemma 1.12 are proved using similar ideas.

The Hamming cube is the Cayely graph on 𝔽_{2}^{n} corresponding to the set of generators {e_{1}, …, e_{n}}. The shortest path metric on this graph coincides with the ℓ_{1}^{n} metric under the identification of 𝔽_{2}^{n} with {0, 1}^{n} ⊆ ℝ^{n}. Let H_{n} be the 2^{n} by 2^{n} symmetric stochastic matrix which is the normalized adjacency matrix of the Hamming cube. Thus for x, y ∈ 𝔽_{2}^{n} the (x, y)-entry of H_{n} equals 0 unless x−y ∈ {e_{1}, …, e_{n}}, in which case it equals 1/n. It is well known (and easy to check) that λ_{2}(H_{n}) = 1 − 2/n, so γ(H_{n}, d_{ℝ}^{2}) ≍ n. A simple argument (that is explained in Section 6) shows that the definition (26) is equivalent to the requirement that γ(H_{n}, d_{X}^{2}) ≲_{X} n^{2/p} for every n ∈ ℕ. The notion of Enflo type p that was mentioned above is equivalent to the requirement that γ(H_{n}, d_{X}^{p}) ≲_{X} n for every n ∈ ℕ.

For p ∈ [1, 2], by considering the identity mapping of 𝔽_{2}^{n} into ℓ_{p}^{n} (observe that ∥x − y∥_{p}^{p} = ∥x − y∥_{1} for every x, y ∈ 𝔽_{2}^{n}) one sees that γ(H_{n}, ∥ · ∥_{p}^{2}) ≳ n^{2/p} ≍ 1/(1 − λ_{2}(H_{n}))^{2/p}. Thus (21) is sharp.

1.3.2. Towards a nonlinear Maurey–Pisier theorem. Every metric space has BMW type 1 and no metric space has BMW type greater than 2; see Remark 6.4 below. Thus, for a metric space (X, d_{X}) define

p_{X} =^{def} sup {p ∈ [1, 2] : BMW_{p}(X) < ∞} .  (27)

Maurey and Pisier [MP76] associate a quantity p_{X} to every Banach space X, which is defined analogously to (27) but with BMW type replaced by Rademacher type. The (linear) notion of Rademacher type is recalled in Section 6.2 below; at this juncture we just want to state, for the sake of readers who are accustomed to the standard Banach space terminology, that despite the apparent conflict of notation between (27) and [MP76], a beautiful theorem of Bourgain, Milman and Wolfson [BMW86] asserts that actually the two quantities coincide.

The following theorem is due to Bourgain, Milman and Wolfson.

Theorem 1.14 ([BMW86]). Suppose that (X, d_{X}) is a metric space with p_{X} = 1. Then c_{X}(𝔽_{2}^{n}, ∥ · ∥_{1}) = 1 for every n ∈ ℕ.

Thus, the only possible obstruction to a metric space (X, d_{X}) having BMW type p for some p > 1 is the presence of arbitrarily large Hamming cubes. This is a metric analogue of a classical theorem of Pisier [Pis73] asserting that the only obstruction to a Banach space having nontrivial Rademacher type is the presence of ℓ_{1}^{n} for every n ∈ ℕ.

In light of the Maurey–Pisier theorem [MP76] for Rademacher type, it is natural to ask if a similar result holds true for a general metric space X even when p_{X} > 1: Is it true that for every metric space (X, d_{X}) we have

sup_{n∈ℕ} c_{X}(𝔽_{2}^{n}, ∥ · ∥_{p_{X}}) < ∞?

The answer to this question is negative if p_{X} = 2. Indeed, we have p_{ℝ} = 2 yet c_{ℝ}(𝔽_{2}^{n}, ∥ · ∥_{2}) tends to infinity exponentially fast as n → ∞ because there is an exponentially large subset S of 𝔽_{2}^{n} with the property that ∥x − y∥_{2} ≍ \sqrt{n} for every distinct x, y ∈ S. If, however, p_{X} ∈ (1, 2) then the above question, called the Maurey–Pisier problem for BMW type, remains open.

The Maurey–Pisier problem for BMW type was posed by Bourgain, Milman and Wolfson in [BMW86], where they obtained a partial result about it: they gave a condition on a metric space (X, d_{X}) that involves its BMW type as well as an additional geometric restriction that ensures that sup_{n∈ℕ} c_{X}(𝔽_{2}^{n}, ∥ · ∥_{p_{X}}) < ∞; see Section 4 of [BMW86].

In Section 6.1 we prove the following theorem.

Theorem 1.15. For every metric space (X, d_{X}) and every d ∈ ℕ there exists N = N(d, X) ∈ ℕ such that

c_{ℓ_{2}^{N} (X)} (𝔽_{2}^{d}, ∥ · ∥_{p_{X}}) ⩽ BMW_{p_{X}}(X)^{2}.

Thus, if BMW_{p_{X}}(X) < ∞, i.e., the supremum defining p_{X} in (27) is attained, then for every d ∈ ℕ one can embed (𝔽_{2}^{d}, ∥ · ∥_{p_{X}}) into ℓ_{2}^{N}(X) for sufficiently large N ∈ ℕ. Note that it follows immediately from (27) that BMW_{p}(ℓ_{2}^{N}(X)) = BMW_{p}(X) for every N ∈ ℕ, so Theorem 1.15 is a complete metric characterization of the parameter p_{X} when the supremum defining p_{X} in (27) is attained. Note also that by passing to ℓ_{2}^{N}(X) we overcome the issue that was described above if p_{X} = 2, since trivially (𝔽_{2}^{n}, ∥ · ∥_{2}) is isometric to a subset of ℓ_{2}^{n}(ℝ). This indicates why Theorem 1.15 is easier than the actual Maurey–Pisier problem for BMW type, whose positive solution would require using the assumption p_{X} < 2. We therefore ask whether or not it is true that for every metric space (X, d_{X}) and every p ∈ (1, 2), if there is K ∈ (0, ∞) such that for every d ∈ ℕ there exists N ∈ ℕ for which (𝔽_{2}^{d}, ∥ · ∥_{p}) embeds with distortion K into ℓ_{2}^{N}(X), then sup_{d∈ℕ} c_{X}(𝔽_{2}^{d}, ∥ · ∥_{p}) < ∞? For p = 1 the answer to this question is positive due to Theorem 1.14, and by virtue of Theorem 1.15 a positive answer to this question would imply an affirmative solution of the Maurey–Pisier problem for BMW type.

Recalling Lemma 1.13, given the relation between BMW type and average distortion embeddings, it is natural to study the following weaker version of the Maurey–Pisier problem for BMW type: Is it true that for every metric space (X, d_{X}) we have

p_{X} < 2 ⟹ sup_{n∈ℕ} Av_{X}^{(2)}(𝔽_{2}^{n}, ∥ · ∥_{p_{X}}) < ∞?  (28)

In (28) we restrict to p_{X} < 2 because one can show that

Av_{ℝ}^{(2)}(𝔽_{2}^{n}, ∥ · ∥_{2}) ≍ \sqrt[4]{n}.  (29)

See Remark 6.9 below for the proof of (29).

By Theorem 1.14 and Lemma 1.13, for every metric space (X, d_{X}),

sup_{n∈ℕ} Av_{X}^{(2)} (𝔽_{2}^{n}, ∥ · ∥_{1}) < ∞ ⟹ sup_{n∈ℕ} c_{X} (𝔽_{2}^{n}, ∥ · ∥_{1}) = 1. (30)

Given p ∈ (1, ∞), it is therefore natural to ask whether or not for every metric space (X, d_{X}) we have

sup_{n∈ℕ} Av_{X}^{(2)} (𝔽_{2}^{n}, ∥ · ∥_{p}) < ∞ ⟹ sup_{n∈ℕ} c_{X} (𝔽_{2}^{n}, ∥ · ∥_{p}) < ∞?  (31)

If (31) were true for every p ∈ (1, 2) then a positive answer to the question that appears in (28) would imply a positive solution to the Maurey–Pisier problem for BMW type.

More generally, in light of the availability of results such as (31), it would be of interest to relate average distortion embeddings to bi-Lipschitz embeddings. For example, is it true that if a metric space (X, d_{X}) satisfies Av_{ℓ_{2}}^{(2)}(X) < ∞ then for every finite subset S ⊆ X we have c_{2}(S) = o_{X}(log |S|)? If the answer to this question is positive then Corollary 1.6 would imply that for p ∈ (2, ∞) any n-point subset of ℓ_{p} embeds into Hilbert space with distortion o_{p}(log n). No such improvement over Bourgain’s embedding theorem [Bou85] is known for finite subsets of ℓ_{p} if p ∈ (2, ∞); for p ∈ [1, 2) see [CGR08, ALN08].

Acknowledgements. I thank Noga Alon, Manor Mendel, and especially Yuval Rabani for very helpful discussions. I am also grateful for the hospitality of Université Pierre et Marie Curie, Paris, France, where part of this work was completed.

2. Absolute spectral gaps

Fix n ∈ ℕ and an n by n symmetric stochastic matrix A = (a_{ij}). Following [MN12], for p ∈ [1, ∞) and a metric space (X, d_{X}), denote by γ_{+}(A, d_{X}^{p}) 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}.  (32)

Note that by definition γ(A, d_{X}^{p}) ⩽ γ_{+}(A, d_{X}^{p}). Recalling (2), we have

γ_{+}(A, d_{ℝ}^{2}) = \frac{1}{1 − λ(A)}.

For this reason one thinks of γ_{+}(A, d_{X}^{p}) as measuring the magnitude of the nonlinear absolute spectral gap of the matrix A with respect to the kernel d_{X}^{p} : X × X → [0, ∞).

The parameter γ_{+}(A, d_{X}^{p}) is useful in various contexts (see [MN12]), and in particular it will be used in some of the ensuing arguments. It is natural to ask for the analogue of Question 1.1 with γ(·, ·) replaced by γ_{+}(·, ·). However, it turns out that this question is essentially the same as Question 1.1, as explained in Proposition 2.1 below.

Proposition 2.1. Fix p ∈ [1, ∞) and metric spaces (X, d_{X}), (Y, d_{Y}). Suppose that there exists an increasing function Ψ : (0, ∞) → (0, ∞) such that for every n ∈ ℕ and every n by n symmetric stochastic matrix A we have

γ(A, d_{X}^{p}) ⩽ Ψ (γ(A, d_{Y}^{p})) .  (33)

Then for every n ∈ ℕ and every n by n symmetric stochastic matrix A we also have

γ_{+}(A, d_{X}^{p}) ⩽ 2Ψ (2^{p}γ_{+}(A, d_{Y}^{p})) .  (34)

Conversely, suppose that Φ : (0, ∞) → (0, ∞) is an increasing function such that for every n ∈ ℕ and every n by n symmetric stochastic matrix A we have

γ_{+}(A, d_{X}^{p}) ⩽ Φ (γ_{+}(A, d_{Y}^{p})) .  (35)

Then for every n ∈ ℕ and every n by n symmetric stochastic matrix A we also have

γ(A, d_{X}^{p}) ⩽ \frac{1}{2}Φ (2^{2p+1}γ(A, d_{Y}^{p})) .  (36)

Before passing to the (simple) proof of Proposition 2.1, we record for future use some basic facts about nonlinear spectral gaps.

Lemma 2.2. Fix p ∈ [1, ∞), n ∈ ℕ and a metric space (X, d_{X}). Then every symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) satisfies

γ(A, d_{X}^{p}) ⩾ 1 − \frac{1}{n}  and  γ_{+}(A, d_{X}^{p}) ⩾ 1.  (37)

Proof. Fix distinct a, b ∈ X and let x_{1}, …, x_{n} ∈ X be i.i.d. points, each of which is chosen uniformly at random from {a, b}. Then every symmetric stochastic A ∈ M_{n}(ℝ) satisfies

𝔼 [\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}] = \frac{d_{X}(a, b)^{p}}{2n} ∑_{\begin{matrix}i,j∈\{1,...,n\} \\ i≠j \end{matrix}} a_{ij} ⩽ \frac{d_{X}(a, b)^{p}}{2} ,

while

𝔼 [\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}] = \frac{n(n − 1)}{2n^{2}}d_{X}(a, b)^{p}.

the desired conclusion now follows from the definition (3). The rightmost inequality in (37) follows by substituting x_{1} = … = x_{n} = a and y_{1} = … = y_{n} = b into (32). □

Lemma 2.3. Fix p ∈ [1, ∞) and a metric space (X, d_{X}). Then for every integer n ⩾ 2, every n by n symmetric stochastic matrix A = (a_{ij}) satisfies

2γ(A, d_{X}^{p}) ⩽ γ_{+}(\frac{I + A}{2}, d_{X}^{p}) ⩽ 2^{2p+1}γ(A, d_{X}^{p}).  (38)

Proof. Since the diagonal entries of A play no role in the definition of γ(A, d_{X}^{2}), it follows immediately from (3) that

γ(\frac{I + A}{2}, d_{X}^{p}) = 2γ(A, d_{X}^{p}).  (39)

Because γ_{+}(\frac{I+A}{2}, d_{X}^{p}) ⩾ γ(\frac{I+A}{2}, d_{X}^{p}), this implies the leftmost inequality in (38).

Next, fix x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ X. By the triangle inequality and the convexity of t ↦ |t|^{p}, for every i, j ∈ {1, …, n} we have

d_{X}(x_{i}, y_{j})^{p} ⩽ 2^{p−1} (d_{X}(x_{i}, x_{j})^{p} + d_{X}(x_{j}, y_{j})^{p}) ,  (40)

and

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

By averaging (40) and (41), and then averaging the resulting inequality over i, j ∈ {1, …, n}, we see that

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

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

Now, by the definition of γ(A, d_{X}^{p}) we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} (d_{X}(x_{i}, x_{j})^{p} + d_{X}(y_{i}, y_{j})^{p})

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

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

d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p−1} (d_{X}(x_{i}, y_{j})^{p} + d_{X}(y_{j}, x_{j})^{p}) ,  (44)
d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p−1} (d_{X}(x_{i}, y_{i})^{p} + d_{X}(y_{i}, x_{j})^{p}) ,  (45)
d_{X}(y_{i}, y_{j})^{p} ⩽ 2^{p−1} (d_{X}(y_{i}, x_{j})^{p} + d_{X}(x_{j}, y_{j})^{p}) ,  (46)

and

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

By averaging (44), (45), (46) and (47) we see that

d_{X}(x_{i}, x_{j})^{p} + d_{X}(y_{i}, y_{j})^{p}

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

By multiplying (48) by a_{ij}/n and summing over i, j ∈ {1, …, n} while using the fact that A is symmetric and stochastic we conclude that

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

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

A substitution of (49) into (43), and then a substitution of the resulting inequality into (42), yields the following estimate.

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

⩽ \frac{2^{p−1} + 2^{2p−2}γ(A, d_{X}^{p})}{n} ∑_{i=1}^{n} d_{X}(x_{i}, y_{i})^{p}

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

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

Since (50) holds true for every x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ X, we deduce from the definition of γ_{+}(·, ·) in (32) that

γ_{+}(\frac{I + A}{2}, d_{X}^{p}) ⩽ 2^{p} + 2^{2p−1}γ(A, d_{X}^{p}).  (51)

The rightmost inequality in (38) is a consequence of (51) since by Lemma 2.2 we have γ(A, d_{X}^{p}) ⩾ \frac{1}{2}. □

Proof of Proposition 2.1. Fix n ∈ ℕ and an n by n symmetric stochastic matrix A. Assuming the validity of (35) for the matrix (I + A)/2, we deduce (36). Next, by [MN12, Lem. 2.3] for every metric space (W, d_{W}) we have

\frac{2}{2^{p} + 1}γ(( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{W}^{p}) ⩽ γ_{+}(A, d_{W}^{p}) ⩽ 2γ(( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) , d_{W}^{p}) .  (52)

Therefore, assuming the validity of (33) for the matrix ( \begin{matrix}0 & A \\ A & 0 \end{matrix} ) ∈ M_{2n}(ℝ), the desired estimate (34) follows from (52). □

3. Duality

The implication (2) ⟹ (1) of Theorem 1.3 was already proved in (10). Below we prove the more substantial implication (1) ⟹ (2).

Proof of Theorem 1.3. Fix D ∈ (K, ∞) and let ε ∈ (0, ∞) be given by (1 + ε)(K + 2ε) = D. Fixing also x_{1}, …, x_{n} ∈ X, let C ⊆ M_{n}(ℝ) be the set of n by n symmetric matrices (c_{ij}) for which there exists y_{1}, …, y_{n} ∈ Y with |{y_{1}, …, y_{n}}| ⩾ 2 and

∀ i, j ∈ \{1, …, n\}, c_{ij} = \frac{∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p}}{∑_{r=1}^{n} ∑_{s=1}^{n} d_{Y} (y_{r}, y_{s})^{p}} · d_{Y} (y_{i}, y_{j})^{p}.

Letting P ⊆ M_{n}(ℝ) be the set of all symmetric n by n matrices with nonnegative entries and vanishing diagonal, denote

M =^{def} conv (C + P) .

For every i, j ∈ {1, …, n} write t_{ij} =^{def} (K + 2ε)d_{X}(x_{i}, x_{j})^{p}. We first claim that the matrix T = (t_{ij}) ∈ M_{n}(ℝ) belongs to M. Indeed, if this were not the case then by the separation theorem (Hahn–Banach) there would exist a symmetric matrix H = (h_{ij}) ∈ M_{n}(ℝ) which has at least one nonzero off-diagonal entry and whose diagonal vanishes, satisfying

inf_{B=(b_{ij})∈M} ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}b_{ij} ⩾ (K + 2ε) ∑_{i=1}^{n} ∑_{j=1}^{n} h_{ij}d_{X}(x_{i}, x_{j})^{p}.  (53)

Since P ⊆ M, the fact that the left hand side of (53) is bounded from below implies that h_{ij} ⩾ 0 for all i, j ∈ {1, …, n}. Fixing δ ∈ (0, 1), if we define

σ =^{def} max_{i∈{1,...,n}} ∑_{j∈{1,...,n}∖{i}}(h_{ij} + δ),

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

a_{ij} =^{def} \frac{1}{2σ} \{ \begin{matrix}2σ − ∑_{r∈\{1,...,n\}∖\{i\}}(h_{ir} + δ) & if i = j, \\ h_{ij} + δ & if i ≠ j, \end{matrix}

then, provided δ ∈ (0, 1) is small enough, A = (a_{ij}) ∈ M_{n}(ℝ) is a symmetric stochastic matrix all of whose entries are positive such that

inf_{B=(b_{ij})∈M} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}b_{ij} ⩾^{(53)} (K + ε) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}

⩾^{(11)} \frac{K + ε}{nγ(A, d_{X}^{p})} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}. (54)

By the definition of C ⊆ M_{n}(ℝ) and γ(A, d_{Y}^{p}) we have

inf_{B=(b_{ij})∈C} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}b_{ij}

= inf_{\begin{matrix}y_{1},...,y_{n}∈Y \\ |\{y_{1},...,y_{n}\}|⩾2 \end{matrix}} \frac{∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p}}{∑_{r=1}^{n} ∑_{s=1}^{n} d_{Y} (y_{r}, y_{s})^{p}} · ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{Y} (y_{i}, y_{j})^{p}

= \frac{1}{nγ(A, d_{Y}^{p})} ∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p}.  (55)

Because M ⊇ C it follows from (54) and (55) that

\frac{1}{nγ(A, d_{Y}^{p})} ∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p} ⩾ \frac{K + ε}{nγ(A, d_{X}^{p})} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}

⩾ \frac{K + ε}{Knγ(A, d_{Y}^{p})} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}, (56)

Since all the entries of A are positive, γ(A, d_{Y}^{p}) ∈ (0, ∞), and therefore (56) furnishes the desired contradiction.

Having proved that T ∈ M, it follows that there exist N ∈ ℕ and μ_{1}, …, μ_{N} ∈ (0, 1] with ∑_{k=1}^{N} μ_{k} = 1, and for every k ∈ {1, …, N} there are y_{1}^{k}, …, y_{n}^{k} ∈ Y with |{y_{1}^{k}, …, y_{n}^{k}}| ⩾ 2, such that for every i, j ∈ {1, …, n} we have

(K +2ε)d_{X}(x_{i}, x_{j})^{p} ⩾ ∑_{k=1}^{N} μ_{k} \frac{∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p}}{∑_{r=1}^{n} ∑_{s=1}^{n} d_{Y} (y_{r}^{k}, y_{s}^{k})^{p}} ·d_{Y} (y_{i}^{k}, y_{j}^{k})^{p}. (57)

There are integers q_{1}, …, q_{N}, Q ∈ ℕ such that

∀ k ∈ \{1, …, N\}, \frac{q_{k}}{Q} ⩽ μ_{k} \frac{∑_{r=1}^{n} ∑_{s=1}^{n} d_{X}(x_{r}, x_{s})^{p}}{∑_{r=1}^{n} ∑_{s=1}^{n} d_{Y} (y_{r}^{k}, y_{s}^{k})^{p}} ⩽ (1 + ε)\frac{q_{k}}{Q} . (58)

Setting q_{0} =^{def} 0 and m =^{def} ∑_{k=1}^{N} q_{k}, define f : {x_{1}, …, x_{n}} → ℓ_{p}^{m}(Y) by

∀ k ∈ {1, …, N}, ∀ u ∈ [1 + ∑_{j=0}^{k−1} q_{j}, ∑_{j=0}^{k} q_{j}] ∩ ℕ, f(x_{i})_{u} = y_{i}^{k}. (59)

Then for every i, j ∈ {1, …, n},

d_{ℓ_{p}^{m}(Y)}(f(x_{i}), f(x_{j})) =^{(59)} (∑_{k=1}^{N} q_{k}d_{Y} (y_{i}^{k}, y_{j}^{k})^{p})^{\frac{1}{p}}

⩽^{(57)∧(58)} Q^{1/p}(K + 2ε)^{1/p}d_{X}(x_{i}, x_{j}).

Consequently,

∥f∥_{Lip} ⩽ Q^{1/p}(K + 2ε)^{1/p}.  (60)

Hence,

∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f(x_{i}), f(x_{j}))^{p} =^{(59)} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{N} q_{k}d_{Y} (y_{i}^{k}, y_{j}^{k})^{p}

⩾^{(58)} \frac{Q}{1 + ε} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p} ⩾^{(60)} \frac{∥f∥_{Lip}^{p}}{(1 + ε)(K + 2ε)} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.

Since (1 + ε)(K + 2ε) = D, the proof of Theorem 1.3 is complete. □

4. Interpolation and Markov type

Fix p ∈ [1, ∞) and m ∈ ℕ. Following K. Ball [Bal92], given a metric space (X, d_{X}) define its Markov type p constant at time m, denoted M_{p}(X; m), to be the infimum over those M ∈ (0, ∞) such that for every n ∈ ℕ, every x_{1}, …, x_{n} ∈ X and every n by n symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ) we have

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

X is said to have Markov type p if M_{p}(X) =^{def} sup_{m∈ℕ} M_{p}(X; m) < ∞. Note that it follows from the triangle inequality that

∀ m ∈ ℕ, M_{p}(X; m) ⩽ m^{1− \frac{1}{p}} .

Remark 4.1. In Section 1.3 we recalled the notions of BMW type and Enflo type. The link between these notions and Ball’s notion of Markov type is that Markov type p implies Enflo type p (see [NS02]). One can also define natural variants of Markov type that imply BMW type (see the inequalities appearing in Theorem 4.4 of [NPSS06]). Recently Kondo proved [Kon11] that there exists a Hadamard space (see e.g. [BH99]) that fails to have Markov type p for any p > 1, answering a question posed in [NPSS06]. Since Hadamard spaces have Enflo type 2 (see [Oht09a]), this yields the only known example of a metric space that has Enflo type 2 but fails to have nontrivial Markov type (observe that the notions of Enflo type 2 and BMW type 2 coincide).

Lemma 4.2. Fix p ∈ [1, ∞) and m, n ∈ ℕ. Let (X, d_{X}) be a metric space and A = (a_{ij}) ∈ M_{n}(ℝ) be a symmetric stochastic matrix. Then

γ(A, d_{X}^{p}) ⩽ M_{p}(X; m)^{p}mγ(A^{m}, d_{X}^{p}) .

Proof. This is immediate from the definitions: for every x_{1}, …, x_{n} ∈ X we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p} ⩽^{(3)} \frac{γ(A^{m}, d_{X}^{p})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{p}

⩽^{(61)} \frac{M_{p}(X; m)^{p}mγ(A^{m}, d_{X}^{p})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}.  □

The modulus of uniform smoothness of a Banach space (X, ∥ · ∥_{X}) is defined for τ ∈ (0, ∞) as

ρ_{X}(τ) =^{def} sup \{\frac{∥x + τy∥_{X} + ∥x − τy∥_{X}}{2} − 1 : x, y ∈ B_{X}\} .

X is said to be uniformly smooth if lim_{τ→0} ρ_{X}(τ)/τ = 0. Furthermore, X is said to have modulus of smoothness of power type q ∈ (0, ∞) if there exists a constant C ∈ (0, ∞) such that ρ_{X}(τ) ⩽ Cτ^{q} for all τ ∈ (0, ∞). It is straightforward to check that in this case necessarily q ∈ [1, 2]. It is shown in [BCL94] that X has modulus of smoothness of power type q if and only if there exists a constant S ∈ [1, ∞) such that for every x, y ∈ X

\frac{∥x + y∥_{X}^{q} + ∥x − y∥_{X}^{q}}{2} ⩽ ∥x∥_{X}^{q} + S^{q}∥y∥_{X}^{q}.  (62)

The infimum over those S ∈ [1, ∞) for which (62) holds true is called the q-smoothness constant of X, and is denoted S_{q}(X). Observe that every Banach space satisfies S_{1}(X) = 1.

The following theorem is due to [NPSS06].

Theorem 4.3. Fix q ∈ [1, 2] and p ∈ [q, ∞). Suppose that (X, ∥·∥_{X}) is a Banach space whose modulus of smoothness has power type q. Then

∀ m ∈ ℕ,  M_{p}(X; m) ≲ (p^{\frac{1}{q}} + S_{q}(X)) m^{\frac{1}{q} − \frac{1}{p}} .  (63)

The statement corresponding to Theorem 4.3 in [NPSS06] (specifically, see Theorem 4.4 there), allows for a multiplicative constant with unspecified dependence on p and q, while in (63) we stated an explicit dependence on these parameters that will serve us later on several occasions. We shall therefore proceed to sketch the proof of Theorem 4.3 so as to explain why the dependence on p and q in (63) is indeed valid.

Proof of Theorem 4.3 (sketch). For every measure space (Ω, μ) we have

S_{q} (L_{p}(μ, X)) ≲ p^{\frac{1}{q}} + S_{q}(X).  (64)

The case q = 2 of (64) appears in [Nao12b], and the proof for general q ∈ [1, 2] follows mutatis mutandis from the proof in [Nao12b]. This has been carried out explicitly in Lemma 6.3 of [MN12], whose statement asserts the weaker bound S_{q} (L_{p}(μ, X)) ≲ p^{1/q}S_{q}(X), but the proof of [MN12, Lem. 6.3] without any change whatsoever yields (64).

As explained in the proof of Theorem 4.4 in [NPSS06], by a result of [Lin63] (see also [Pis75, Prop. 2.2]) it follows from (64) that every X-valued martingale {M_{k}}_{k=0}^{m} satisfies

𝔼 [∥M_{m} − M_{0}∥_{X}^{p}]

⩽ K^{p} (p^{\frac{p}{q}} + S_{q}(X)^{p}) (∑_{k=1}^{m} (𝔼 [∥M_{k} − M_{k−1}∥_{X}^{p}])^{\frac{q}{p}} )^{\frac{p}{q}}

⩽ K^{p} (p^{\frac{p}{q}} + S_{q}(X)^{p}) m^{\frac{p}{q} −1} ∑_{k=1}^{m} 𝔼 [∥M_{k} − M_{k−1}∥_{X}^{p}] ,  (65)

where K ∈ (0, ∞) is a universal constant. Now, substituting the martingale inequality (65) into the proof of Theorem 2.3 in [NPSS06], in place of the use of Pisier’s martingale inequality [Pis75], yields (63). □

We record for future use the following corollary, which is an immediate consequence of Lemma 4.2 and Theorem 4.3.

Corollary 4.4. Fix q ∈ (1, 2] and p ∈ [q, ∞). Suppose that (X, ∥ · ∥_{X}) is a Banach space whose modulus of smoothness has power type q. Then for every m, n ∈ ℕ and every symmetric stochastic A = (a_{ij}) ∈ M_{n}(ℝ),

γ(A, ∥ · ∥_{X}^{p}) ≲ C^{p} (p^{\frac{p}{q}} + S_{q}(X)^{p}) m^{\frac{p}{q}} γ(A^{m}, ∥ · ∥_{X}^{p}) ,  (66)

where C ∈ (0, ∞) is a universal constant.

We refer to [Cal64] for the background on complex interpolation that is used below. We also recall the definition of λ(A) in (2). The following theorem is the main result of this section.

Theorem 4.5. Let (H, Z) be a compatible pair of Banach spaces with H being a Hilbert space. Suppose that θ ∈ [0, 1] and consider the complex interpolation space X = [H, Z]_{θ}. Fix q ∈ [1, 2] and suppose that X has modulus of smoothness of power type q. Then for every n ∈ ℕ and every n by n symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, ∥ · ∥_{X}^{2}) ≲ \frac{S_{q}(X)^{2}}{(1 − λ(A)^{θ})^{2/q}} .  (67)

Before proving Theorem 4.5 we present some of its immediate corollaries. First, since in the setting of Theorem 4.5 we always have S_{q}(X) ≲ 1 for q = 2/(1+θ) (see [Pis79, CR82]), the following corollary is a special case of Theorem 4.5.

Corollary 4.6. Under the assumptions of Theorem 4.5 we have

γ(A, ∥ · ∥_{X}^{2}) ≲ \frac{1}{(1 − λ(A)^{θ})^{1+θ}} .

In order for the above results to fit into the framework of Question 1.2, we need to bound γ(A, ∥ · ∥_{X}^{2}) in terms of λ_{2}(A) rather than λ(A). This is the content of the next corollary.

Corollary 4.7. Under the assumptions of Theorem 4.5 we have

γ(A, ∥ · ∥_{X}^{2}) ≲ \frac{S_{q}(X)^{2}}{θ^{2/q}} · \frac{1}{(1 − λ_{2}(A))^{2/q}} .  (68)

Proof. Since A is symmetric and stochastic, all of its eigenvalues are in the interval [−1, 1]. Consequently, all the eigenvalues of the symmetric stochastic matrix (I + A)/2 are nonnegative, and hence

λ (\frac{I + A}{2}) = \frac{1 + λ_{2}(A)}{2}.  (69)

An application of Theorem 4.5 to the matrix (I + A)/2 while taking into account the identities (69) and (39) implies that

γ(A, ∥ · ∥_{X}^{2}) ≲ \frac{S_{q}(X)^{2}}{(1 − (\frac{1+λ_{2}(A)}{2})^{θ})^{2/q}} .

This yields the desired estimate (68) due to the elementary inequality

∀ x ∈ [−1, 1],  1 − (\frac{1 + x}{2})^{θ} ⩾ \frac{θ(1 − x)}{2}.  □

We can now complete the proof of Theorem 1.5, and consequently also its corresponding dual statement Corollary 1.6.

Proof of Theorem 1.5. Fix p ∈ [2, ∞) and apply Corollary 4.7 when X = ℓ_{p}. Then X = [ℓ_{2}, ℓ_{∞}]_{θ} for θ = 2/p. Moreover, by [Fig76, BCL94] we have S_{2}(ℓ_{p}) = \sqrt{p − 1}, and therefore the desired estimate (12) follows from (68) (with q = 2). □

As in the above proof of Theorem 1.5, by specializing Theorem 4.5 to X = ℓ_{p} for p ∈ [2, ∞), we obtain the following corollary, which was stated in the Introduction as inequality (18).

Corollary 4.8. For every p ∈ [2, ∞), every n ∈ ℕ and every n by n symmetric stochastic matrix A we have

γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{p}{1 − λ(A)^{2/p}} .

We now proceed to prove Theorem 4.5.

Proof of Theorem 4.5. In what follows, given a Banach space (Y, ∥·∥_{Y}) and n ∈ ℕ we let L_{2}^{n}(Y) denote the Banach space whose underlying vector space is Y^{n}, equipped with the norm

∀ y = (y_{1}, …, y_{n}) ∈ Y^{n}, ∥y∥_{L_{2}^{n}(Y)} =^{def} (\frac{1}{n} ∑_{i=1}^{n} ∥y_{i}∥_{Y}^{2} )^{\frac{1}{2}} .

If H is a Hilbert space with scalar product ⟨·, ·⟩_{H}, then L_{2}^{n}(H) is a Hilbert space whose scalar product is always understood to be given by ⟨x, y⟩_{L_{2}^{n}(H)} = \frac{1}{n} ∑_{i=1}^{n}⟨x_{i}, y_{i}⟩_{H} for every x, y ∈ H.

Let e_{1}(A), …, e_{n}(A) ∈ L_{2}^{n}(ℝ) be an orthonormal eigenbasis of A with e_{1}(A) = (1, …, 1) and Ae_{i}(A) = λ_{i}(A)e_{i}(A) for all i ∈ {1, …, n}. Define an operator T : L_{2}^{n}(ℝ) → L_{2}^{n}(ℝ) by setting for every x ∈ ℝ^{n} and i ∈ {1, …, n},

(T x)_{i} =^{def} ∑_{j=1}^{n} a_{ij} (x_{j} − \frac{1}{n} ∑_{k=1}^{n} x_{k}) .

Equivalently,

T x = ∑_{i=2}^{n} λ_{i}(A)⟨x, e_{i}(A)⟩_{L_{2}^{n}(ℝ)}e_{i}(A).  (70)

The operator T ⊗ I_{Y} : L_{2}^{n}(Y) → L_{2}^{n}(Y), where I_{Y} denotes the identity on Y, is then given by

∀ i ∈ \{1, …, n\},  ((T ⊗ I_{Y})y)_{i} =^{def} ∑_{j=1}^{n} a_{ij} (y_{j} − \frac{1}{n} ∑_{k=1}^{n} y_{k}) . (71)

Recalling (2) and (70), we have the following operator norm bounds.

∥T ⊗ I_{H}∥_{L_{2}^{n}(H)} = ∥T ∥_{L_{2}^{n}(ℝ)→L_{2}^{n}(ℝ)} = λ(A).  (72)

The norm of T ⊗ I_{Z} : L_{2}^{n}(Z) → L_{2}^{n}(Z) can be bounded crudely by using the fact that A is a symmetric stochastic matrix. Indeed, for every z ∈ L_{2}^{n}(Z) we have

∥T z∥_{L_{2}^{n}(Z)}^{2} = \frac{1}{n} ∑_{i=1}^{n} ∥∑_{j=1}^{n} a_{ij} (z_{j} − \frac{1}{n} ∑_{k=1}^{n} z_{k})∥_{Z}^{2}

⩽ \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} a_{ij}∥z_{j} − z_{k}∥_{Z}^{2}

⩽ \frac{2}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} a_{ij} (∥z_{j}∥_{Z}^{2} + ∥z_{k}∥_{Z}^{2}) = 4∥z∥_{L_{2}^{n}(Z)}^{2}. (73)

An interpolation of (72) and (73) (see [Cal64]) shows that

∥T ⊗ I_{X}∥_{L_{2}^{n}(X)→L_{2}^{n}(X)} ⩽ 2^{1−θ}λ(A)^{θ}.  (74)

For every x ∈ L_{2}^{n}(X) let \overline{x} ∈ L_{2}^{n}(X) be the vector whose ith coordinate equals x_{i} − S(x), where S(x) = \frac{1}{n} ∑_{k=1}^{n} x_{k}. Then

∥(I_{L_{2}^{n}(X)} − T ⊗ I_{X})\overline{x}∥_{L_{2}^{n}(X)}^{2} =^{(71)} \frac{1}{n} ∑_{i=1}^{n} ∥∑_{j=1}^{n} a_{ij}(x_{i} − x_{j})∥_{X}^{2}

⩽ \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{X}^{2}. (75)

At the same time,

∥(I_{L_{2}^{n}(X)} − T ⊗ I_{X})\overline{x}∥_{L_{2}^{n}(X)} ⩾ ∥\overline{x}∥_{L_{2}^{n}(X)} − ∥(T ⊗ I_{X})\overline{x}∥_{L_{2}^{n}(X)}
⩾^{(74)} (1 − 2^{1−θ}λ(A)^{θ}) ∥\overline{x}∥_{L_{2}^{n}(X)}. (76)

Hence, if we suppose that

2^{1−θ}λ(A)^{θ} < 1 ⟺ λ(A) < \frac{1}{2^{(1−θ)/θ}} ,  (77)

then

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{X}^{2} ⩽ \frac{2}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − S(x)∥_{X}^{2} + ∥x_{j} − S(x)∥_{X}^{2})

= 4∥\overline{x}∥_{L_{2}^{n}(X)}^{2} ⩽^{(75)∧(76)} \frac{4}{(1 − 2^{1−θ}λ(A)^{θ})^{2}} · \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{X}^{2}.

Equivalently,

γ(A, ∥ · ∥_{X}^{2}) ⩽ \frac{4}{(1 − 2^{1−θ}λ(A)^{θ})^{2}} .  (78)

We shall now apply a trick that was used by Pisier in [Pis10], where it is attributed to V. Lafforgue: we can ensure that the condition (77) holds true if we work with a large enough power of A. We will then be able to return back to an inequality that involves A rather than its power by using Markov type through Corollary 4.4. Specifically, define

m =^{def} ⌈\frac{(2 − θ) log 2}{θ log(1/λ(A))}⌉ .  (79)

This choice of m ensures that

2^{1−θ}λ(A^{m})^{θ} = 2^{1−θ}λ(A)^{mθ} ⩽ \frac{1}{2},

so we may apply (78) with A replaced by A^{m} to get the estimate

γ(A^{m}, ∥ · ∥_{X}^{2}) ⩽ 16.  (80)

An application of Corollary 4.4 with p = 2 now implies that

γ(A, ∥ · ∥_{X}^{2}) ≲^{(66)∧(80)} m^{\frac{2}{q}} S_{q}(X)^{2}

≲^{(79)} S_{q}(X)^{2} (1 + \frac{1}{θ log (1/λ(A))})^{\frac{2}{q}} ≲ \frac{S_{q}(X)^{2}}{(1 − λ(A)^{θ})^{2/q}} , (81)

where in (81) we used the elementary inequality

∀ x ∈ [0, 1], 1 + \frac{1}{log(1/x)} ⩽ \frac{2}{1 − x},

which holds true because exp (−\frac{1−x}{1+x}) ⩾ 1 − \frac{1−x}{1+x} = \frac{2x}{1+x} ⩾ x. □

4.1. Ramanujan graphs and Alon–Roichman graphs. Given a connected n-vertex graph G = ({1, …, n}, E_{G}), let d_{G}(·, ·) denote the shortest path metric that G induces on {1, …, n}. The diameter of the metric space ({1, …, n}, d_{G}) will be denoted below by diam(G). Suppose that d ∈ {3, …, n − 1} and that G is d-regular, i.e., for every i ∈ {1, …, n} the number of j ∈ {1, …, n} such that {i, j} ∈ E_{G} equals d. The normalized adjacency matrix of G will be denoted A_{G}, i.e., (A_{G})_{ij} = \frac{1}{d}1_{\{i,j\}∈E_{G}} for every i, j ∈ \{1, …, n\}. Thus A_{G} is an n by n symmetric stochastic matrix. We denote λ_{i}(G) = λ_{i}(A_{G}) for every i ∈ {1, …, n}, and we correspondingly set λ(G) = λ(A_{G}) and γ(G, d_{X}^{q}) = γ(A_{G}, d_{X}^{q}) for every metric space (X, d_{X}) and q ∈ [1, ∞).

Setting c_{X}(G) =^{def} c_{X}({1, …, n}, d_{G}), an important idea of Linial, London and Rabinovich [LLR95] relates γ(G, d_{X}^{q}) to a lower bound on c_{X}(G) as follows. Let f : {1, …, n} → X be a nonconstant function and apply (3) with A = A_{G} and x_{i} = f(i) for every i ∈ {1, …, n}, thus obtaining the estimate

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(f(i), f(j))^{q} ⩽ \frac{γ(G, d_{X}^{q})}{dn} ∑_{\begin{matrix}(i,j)∈\{1,...,n\}^{2} \\ \{i,j\}∈E_{G} \end{matrix}} d_{X}(f(i), f(j))^{q}

⩽ γ(G, d_{X}^{q})∥f∥_{Lip}^{q}.  (82)

Denoting Av_{X}^{(q)}(G) =^{def} Av_{X}^{(q)}({1, …, n}, d_{G}), it follows from (82) that

c_{X}(G) ⩾ Av_{X}^{(q)}(G) ⩾ \frac{1}{γ(G, d_{X}^{q})^{1/q}} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j)^{q})^{\frac{1}{q}} . (83)

For notational simplicity we will assume from now on that G is a vertex-transitive graph, since in this case we have

\frac{diam(G)}{2^{1+1/q}} ⩽ (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j)^{q})^{\frac{1}{q}} ⩽ diam(G).  (84)

One verifies the validity of (84) by arguing as in the proof of Proposition 3.4 of [NR09]: for every i ∈ {1, …, n} and r ∈ (0, ∞) let B_{G}(i, r) = {j ∈ {1, …, n} : d_{G}(i, j) ⩽ r} be the closed ball of radius r centered at i in the metric d_{G}. Since G is vertex-transitive, the cardinality of B_{G}(i, r) is independent of i. Hence, if we let r_{∗} be the minimum r ∈ ℕ such that |B_{G}(i, r)| > n/2 for every i ∈ {1, …, n}, then for every i ∈ {1, …, n} we have |{1, …, n}∖B_{G}(i, r_{∗}−1)| ⩾ n/2. In other words, for every i ∈ {1, …, n} there are at least n/2 vertices j ∈ {1, …, n} with d_{G}(i, j) ⩾ r_{∗}. Hence ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j)^{q} ⩾ n^{2}r_{∗}^{q}/2. At the same time, by the definition of r_{∗} we have B_{G}(i, r_{∗}) ∩ B_{G}(j, r_{∗}) ≠ ∅ for every i, j ∈ {1, …, n}, and therefore diam(G) ⩽ 2r_{∗}. This proves the leftmost inequality in (84) (the remaining inequality in (84) is trivial).

By combining (83) and (84), Matoušek’s argument in [Mat97] deduces from his bound (14) that if G = ({1, …, n}, E_{G}) is a vertextransitive graph such that λ_{2}(G) is bounded away from 1 by a universal constant then for every p ∈ [2, ∞) we have

c_{p}(G) ≳ \frac{diam(G)}{p}.  (85)

Denote p(G) =^{def} p({1, …, n}, d_{G}), where we recall that in Section 1.1 we defined for a separable metric space (X, d_{X}) the quantity p(X, d_{X}) (or simply p(X) if the metric is clear from the context) to be the infimum over those p ∈ [2, ∞] for which c_{p}(X) ⩽ 10. It follows from (85) that p(G) ≳ diam(G) (still under the assumption that λ_{2}(G) is bounded away from 1). Using Corollary 4.8, we now show that it is possible to improve over this estimate.

Proposition 4.9. Fix p ∈ [2, ∞) and let G = ({1, …, n}, E_{G}) be a vertex-transitive graph. Then

p ⩽ log (\frac{1}{λ(G)}) ⟹ c_{p}(G) ≳ \frac{diam(G)}{\sqrt{p}},

and

p ⩾ log (\frac{1}{λ(G)}) ⟹ c_{p}(G) ≳ \frac{diam(G)}{p}\sqrt{log (\frac{1}{λ(G)})}.

Proof. By combining (83) and (84) (for q = 2) with Corollary 4.8 we see that

c_{p}(G) ⩾ Av_{X}^{(2)}(G) ≳ \begin{matrix}√ & \overline{1 − λ(G)^{2/p}} \\ √ & \overline{p} \end{matrix} diam(G).  □

By the definition of p(G), the following corollary is a formal consequence of Proposition 4.9.

Corollary 4.10. Let G = ({1, …, n}, E_{G}) be a vertex-transitive graph. Then

λ(G) ⩽ e^{− diam(G)^{2}} ⟹ p(G) ≳ diam(G)^{2},

and

λ(G) ⩾ e^{− diam(G)^{2}} ⟹ p(G) ≳ diam(G)\sqrt{log (\frac{1}{λ(G)})}.

For every n ∈ ℕ and d ∈ {3, …, n − 1}, if G = ({1, …, n}, E_{G}) is a d-regular graph then by [Chu89] we have

\frac{log n}{log d} ≲ diam(G) ⩽ 1 + \frac{log n}{log(1/λ(G))}.

Consequently, if 1/λ(G) is at least d^{c} for some universal constant c > 0 then diam(G) ≍ log_{d} n. This happens in particular when G is a Ramanujan graph, i.e., λ(G) ⩽ 2\sqrt{d − 1}/d. Such graphs have been constructed in [LPS88, Mar88]. It is natural to ask for the asymptotic evaluation of c_{p}(G) when G is an n-vertex d-regular Ramanujan graph. While this question remains open, Proposition 4.11 below contains a lower bound on c_{p}(G) that improves over Matoušek’s bound.

Proposition 4.11. Fix n ∈ ℕ and d ∈ {3, …, n − 1}. Suppose that G = ({1, …, n}, E_{G}) is a Ramanujan graph. Then

2 ⩽ p ⩽ log d ⟹ c_{p}(G) ≳ \frac{log n}{\sqrt{p} log d}.  (86)
p ⩾ log d ⟹ c_{p}(G) ≳ \frac{log n}{p\sqrt{log d}}.  (87)

Proof. By combining (83) and (84) with Corollary 4.8 we see that

c_{p}(G) ≳ \begin{matrix}√ & \overline{1 − λ(G)^{2/p}} \\ √ & \overline{p} \end{matrix} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j)^{2})^{\frac{1}{2}}

≳ \begin{matrix}√ & \overline{1 − (2/\sqrt{d})^{2/p}} \\ √ & \overline{p} \end{matrix} log_{d} n,

where we used the fact that \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j)^{2} ≳ (log_{d} n)^{2} and that λ(G) ⩽ 2/\sqrt{d}. The latter bound uses the fact that G is a Ramanujan graph (in fact, weaker bounds on λ(G) suffice for our purposes), and the former bound holds true for any connected n-vertex d-regular graph (see [Mat97] for a simple proof of this). □

If G is a uniformly random n-vertex d-regular graph then by [BS87] λ(G) ⩽ 2/\sqrt[4]{d} with high probability (for the best known bound on λ(G) when G is a random d-regular graph, see [Fri08]). By arguing identically to the proof of Proposition 4.11, we see that with high probability (86) and (87) hold true for such G, implying Proposition 1.9.

Corollary 4.8 also implies new distortion bounds for Abelian Alon– Roichman graphs [AR94]. These are graphs that are obtained from the following random construction. Let Γ be a finite Abelian group, and think of Γ as the set {1, …, n}, equipped with an Abelian group operation. Fix ε ∈ (0, 1/2) and set k = ⌈\frac{3}{ε^{2}} log n⌉. Let g_{1}, …, g_{k} ∈ Γ be chosen independently and uniformly at random. This induces a random Cayley graph G whose generating multi-set is {g_{1}, g_{1}^{−1}, …, g_{k}, g_{k}^{−1}}. As explained in [AR94], with probability that tends to 1 as n → ∞ the graph G is connected. Note that since G is a Cayley graph it is vertextransitive. It follows from [CM08] that provided n is large enough we have λ(G) ⩽ ε with probability at least \frac{1}{2}. Moreover, by [NR09, Prop. 3.5] we have diam(G) ≳ (log n)/(log 1/ε). A substitution of these estimates into Proposition 4.9 shows that

2 ⩽ p ⩽ log(1/ε) ⟹ c_{p}(G) ≳ \frac{log n}{\sqrt{p} log(1/ε)},

and

p ⩾ log(1/ε) ⟹ c_{p}(G) ≳ \frac{log n}{p\sqrt{log(1/ε)}}.

Remark 4.12. We warn that there is some subtlety in the definition of the parameter p(X) for a separable metric space (X, d_{X}). Given that X is isometric to a subset of ℓ_{∞}, it is indeed natural to ask for the smallest p ∈ [2, ∞] such that X embeds with bounded distortion, say, distortion 10, into ℓ_{p}. As an example of an application that was shown to us by Yuval Rabani, one can use the methods of [KOR00] to prove that subsets of ℓ_{p} admit an efficient approximate nearest neighbor data structure with approximation guarantee e^{O(p)}, so the parameter p(X) relates to approximate nearest neighbor search in X (it would be very interesting to determine the correct asymptotic dependence on p here). But, understanding the set of p ∈ [2, ∞) for which X admits a bi-Lipschitz embedding into ℓ_{p} can be subtle. In particular, it is not true that if X embeds into ℓ_{p} then for every q > p it also embeds into ℓ_{q}. In fact, we have the following estimates for every n ∈ ℕ and p, q ∈ (2, ∞).

2 < q < p ⟹ c_{q} (ℓ_{p}^{n}) ≍ n^{\frac{1}{q} − \frac{1}{p}} ,  (88)

and

2 < p < q ⟹ c_{q} (ℓ_{p}^{n}) ≍_{p,q} n^{\frac{(q−p)(p−2)}{(q−2)p^{2}}} .  (89)

The asymptotic identity (88) is a standard consequence of the fact that L_{q} has Rademacher cotype q (see e.g. [Woj91]). The remarkable asymptotic identity (89) is due to [FJS88] (using a computation of [GPP80]). The implicit dependence on p, q in (89) is unknown, and it would be of interest to evaluate it up to a universal constant factor. Observe that the exponent of n in (89) tends to (p − 2)/p^{2} > 0 as q → ∞, and therefore the implicit constant in (89) must tend to 0 as q → ∞.

4.2. Curved Banach spaces in the sense of Pisier. Motivated by his work on nonlinear spectral gaps [Laf08], V. Lafforgue associated the following modulus to a Banach space (X, ∥ · ∥_{X}), a modulus has been investigated extensively by Pisier in [Pis10]. Given ε ∈ (0, ∞) let Δ_{X}(ε) denote the infimum over those Δ ∈ (0, ∞) such that for every n ∈ ℕ, every matrix T = (t_{ij}) ∈ M_{n}(ℝ) with

∥T ∥_{L_{2}^{n}(ℝ)→L_{2}^{n}(ℝ)} ⩽ ε and ∥abs(T)∥_{L_{2}^{n}(ℝ)→L_{2}^{n}(ℝ)} ⩽ 1,

where abs(T) =^{def} (|t_{ij}|) is the entry-wise absolute value of T, satisfies

∥T ⊗ I_{X}∥_{L_{2}^{n}(X)→L_{2}^{n}(X)} ⩽ Δ.

Pisier introduced the following terminology in [Pis10]: X is said to be curved if Δ_{X}(ε) < 1 for some ε ∈ (0, 1). X is said to be fully curved if Δ_{X}(ε) < 1 for all ε ∈ (0, 1), and X is said to be uniformly curved if lim_{ε→0} Δ_{X}(ε) = 0. It is shown in [Pis10] that if X is either fully curved or uniformly curved then it admits an equivalent uniformly convex norm. A remarkable characterization of Pisier [Pis10] shows that Δ_{X}(ε) ≲ ε^{α} for some α ∈ (0, ∞) if and only if X arises from complex interpolation with Hilbert space: formally, this happens if and only if X is isomorphic to a quotient of a subspace of an ultraproduct of θ-Hilbertian Banach spaces for some θ ∈ (0, 1); we refer to [Pis10] for the definition of these notions. A more complicated structural characterization of uniformly curved spaces (based on real interpolation) is also obtained in [Pis10].

One can use the above notions to give a generalized abstract treatment of results in the spirit of Theorem 4.5. Fix ε ∈ (0, 1) and suppose that Δ_{X}(ε) < \frac{1}{2}. Let A ∈ M_{n}(ℝ) be symmetric and stochastic and let T = (t_{ij}) ∈ M_{n}(ℝ) be given as in (70). By (72) we have ∥T ∥_{L_{2}^{n}(ℝ)→L_{2}^{n}(ℝ)} = λ(A). Moreover, since abs(T) = (|a_{ij} − 1/n|) and A is symmetric and stochastic, it is immediate to check that ∥abs(T)∥_{L_{2}^{n}(ℝ)→L_{2}^{n}(ℝ)} ⩽ 2. By the definition of the modulus Δ_{X}(·) we therefore have ∥T ⊗ I_{X}∥_{L_{2}^{n}(X)→L_{2}^{n}(X)} ⩽ 2Δ_{X}(λ(A)/2). Define

m =^{def} ⌈\frac{log(1/(2ε))}{log(1/λ(A))}⌉ ,  (90)

so that λ(A^{m})/2 = λ(A)^{m}/2 ⩽ ε, and apply the above reasoning with A replaced by A^{m}. Arguing as in (75) and (76), we obtain the estimate

γ(A^{m}, ∥ · ∥_{X}^{2}) ⩽ \frac{4}{(1 − 2Δ_{X}(ε))^{2}} .

We can now use the notion of Markov type through Lemma 4.2 to deduce the following statement.

Theorem 4.13. Fix ε ∈ (0, 1) and let (X, ∥ · ∥_{X}) be a Banach that satisfies Δ_{X}(ε) < \frac{1}{2}. Then for every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, ∥ · ∥_{X}^{2})

⩽ \frac{4}{(1 − 2Δ_{X}(ε))^{2}} · M_{2} (X; ⌈\frac{log(1/(2ε))}{log(1/λ(A))}⌉)^{2} · ⌈\frac{log(1/(2ε))}{log(1/λ(A))}⌉ .

In particular, using Theorem 4.3 and arguing as in the proof of Corollary 4.7, if X has modulus of smoothness of power type 2 then every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ(A, ∥ · ∥_{X}^{2}) ≲_{X} \frac{1}{1 − λ_{2}(A)}.

In conjunction with Theorem 1.3 we deduce the following geometric embedding result for uniformly curved Banach space that can be renormed so as to have modulus of smoothness of power type 2.

Corollary 4.14. Suppose that (X, ∥ · ∥_{X}) is a uniformly curved Banach space that admits an equivalent norm whose modulus of uniform smoothness has power type 2. Then for every x_{1}, …, x_{n} ∈ X there exist y_{1}, …, y_{n} ∈ ℓ_{2} such that

∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{X}^{2} = ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{2}^{2},

and

∀ i, j ∈ {1, …, n}, ∥y_{i} − y_{j}∥_{2} ≲_{X} ∥x_{i} − x_{j}∥_{X}.

4.3. An interpolation inequality for nonlinear spectral gaps. The modulus of uniform convexity of a Banach space (X, ∥ · ∥_{X}) is defined for ε ∈ [0, 2] as

δ_{X}(ε) =^{def} inf \{1 − \frac{∥x + y∥_{X}}{2} : x, y ∈ B_{X} ∧ ∥x − y∥_{X} = ε\} .

X is said to be uniformly convex if δ_{X}(ε) > 0 for all ε ∈ (0, 2]. Furthermore, X is said to have modulus of convexity of power type p if there exists a constant c ∈ (0, ∞) such that δ_{X}(ε) ⩾ c ε^{p} for all ε ∈ [0, 2]. It is straightforward to check that in this case necessarily p ⩾ 2. By Proposition 7 in [BCL94] (see also [Fig76]), X has modulus of convexity of power type p if and only if there exists a constant K ∈ [1, ∞) such that for every x, y ∈ X

(∥x∥_{X}^{p} + \frac{1}{K^{p}} ∥y∥_{X}^{p})^{\frac{1}{p}} ⩽ (\frac{∥x + y∥_{X}^{p} + ∥x − y∥_{X}^{p}}{2} )^{\frac{1}{p}} .  (91)

The infimum over those K for which (91) holds true is called the pconvexity constant of X, and is denoted K_{p}(X). Note that every Banach space satisfies K_{∞}(X) = 1. Below we shall use the convention K_{p}(X) = ∞ if p ∈ [1, 2). For 1 ⩽ q ⩽ 2 ⩽ p, the p-convexity constant of X is related to the q-smoothness constant of X (recall (62)) via the following duality relation [BCL94, Lem. 5].

\frac{1}{p} + \frac{1}{q} = 1 ⟹ K_{p}(X) = S_{q}(X^{∗}).

Theorem 4.15. Let (X, Y) be a compatible pair of Banach spaces. Fix θ ∈ [0, 1] and consider the complex interpolation space Z = [X, Y]_{θ}. Fix also p, q ∈ [1, ∞] and r ∈ [1, 2]. Then for every n ∈ ℕ and every n by n symmetric stochastic matrix A we have

\frac{γ(A, ∥ · ∥_{Z}^{s})}{c^{s} (s^{\frac{s}{r}} + S_{r}(Z)^{s})}

⩽ (min \{\frac{(9K_{p}(X))^{p}γ(A, ∥ · ∥_{X}^{p})}{θ} , \frac{(9K_{q}(Y))^{q}γ(A, ∥ · ∥_{Y}^{q})}{1 − θ} \})^{\frac{s}{r}} ,

where c ∈ (0, ∞) is a universal constant and s ∈ [2, ∞] is given by

\frac{1}{s} = \frac{θ}{p} + \frac{1 − θ}{q}.

Observe that for every a, b ∈ (0, ∞) and every θ ∈ (0, 1) we have

min \{\frac{a}{θ}, \frac{b}{1 − θ}\} ⩽ \frac{2}{\frac{θ}{a} + \frac{1−θ}{b}} ⩽ a^{θ}b^{1−θ}.

Consequently, the conclusion of Theorem 4.15 implies that

γ(A, ∥ · ∥_{Z}^{s}) ≲_{X,Y,Z,s} γ(A, ∥ · ∥_{X}^{p})^{θs/r}γ(A, ∥ · ∥_{Y}^{q})^{(1−θ)s/r}.

Such an estimate is in the spirit of the interpolation inequality (15), but it is insufficient for the purpose of addressing Question 1.8. Theorem 4.15 does suffice to prove Lemma 1.11, so we assume the validity of Theorem 4.15 for the moment and proceed now to prove Lemma 1.11.

Proof of Lemma 1.11. Matoušek proved in [Mat97] that if (X, d_{X}) is an n-point metric space then for p ∈ [2, ∞) we have

c_{p}(X) ≲ 1 + \frac{log n}{p}.  (92)

The case p = 2 of (92) is Bourgain’s embedding theorem [Bou85]. Now, for every n ∈ ℕ let G_{n} = ({1, …, n}, E_{G_{n}}) be a 4-regular graph with sup_{n∈ℕ} λ_{2}(G_{n}) < 1, i.e., {G_{n}}_{n=1}^{∞} forms an expander sequence. Fixing n ⩾ e^{p}, by (92) we know that there exist x_{1}, …, x_{n} ∈ ℓ_{p} such that

∀ i, j ∈ \{1, …, n\},  d_{G_{n}}(i, j) ⩽ ∥x_{i} − x_{j}∥_{ℓ_{p}} ≲ \frac{log n}{p}d_{G_{n}}(i, j). (93)

Suppose that y_{1}, …, y_{n} ∈ ℓ_{q} satisfy (24), i.e.,

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{r})^{\frac{1}{r}} = (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{ℓ_{p}}^{s})^{\frac{1}{s}} , (94)

If ∥y_{i} − y_{j}∥_{ℓ_{q}} ⩽ D∥x_{i} − x_{j}∥_{ℓ_{p}} for every i, j ∈ {1, …, n} then we need to show that D ≳ p/(q + r). Note that since G_{n} is 4-regular, a constant fraction of the pairs (i, j) ∈ {1, …, n}^{2} satisfy d_{G_{n}}(i, j) ≳ log n (the standard argument showing this appears in e.g. [Mat97]). Hence, due to the leftmost inequality in (93), it follows from (94) that

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{r})^{\frac{1}{r}} ≳ log n.  (95)

Case 1. r ⩽ q. In this case we have

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{r})^{\frac{1}{r}} ⩽ (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{q})^{\frac{1}{q}}

⩽ γ(G_{n}, ∥ · ∥_{ℓ_{q}}^{q})^{\frac{1}{q}} (\frac{1}{4n} ∑_{\begin{matrix}(i,j)∈\{1,...,n\}^{2} \\ \{i,j\}∈E_{Gn} \end{matrix}} ∥y_{i} − y_{j}∥_{ℓ_{q}}^{q} )^{\frac{1}{q}} ≲ \frac{Dq log n}{p}, (96)

where in (96) we bounded γ(G_{n}, ∥·∥_{ℓ_{q}}^{q}) using (14), and we used the fact that if {i, j} ∈ E_{G_{n}} then ∥y_{i} − y_{j}∥_{ℓ_{q}} ⩽ D∥x_{i} − x_{j}∥_{ℓ_{p}} ≲ D(log n)/p, due to (93). By contrasting (96) with (95) we have D ≳ p/q, as required.

Case 2. r > q. Write θ =^{def} 1/(r − 1) and t =^{def} 2q(r − 2)/(2r − q − 2). Recalling that we are assuming in Lemma 1.11 that q ⩾ 2, it follows that θ ∈ (0, 1) and t ∈ [q, 2r]. Consequently, K_{2r}(ℓ_{t}) ⩽ K_{t}(ℓ_{t}) ⩽ 1 (see [BCL94]). Note also that 1/q = θ/2 + (1 − θ)/t, so ℓ_{q} = [ℓ_{2}, ℓ_{t}]_{θ}. Since 1/r = θ/2 + (1 − θ)/(2r) and S_{2}(ℓ_{q}) = \sqrt{q − 1} (see [BCL94]), it follows from Theorem 4.15 that for every n ∈ ℕ we have

γ(G_{n}, ∥ · ∥_{ℓ_{q}}^{r})^{1/r} ≲ \sqrt{r · min \{rγ(G_{n}, ∥ · ∥_{ℓ_{2}}^{2}), γ(G_{n}, ∥ · ∥_{ℓ_{t}}^{2r})\}} ≲ r.

Hence, if we argue as in (96) we see that D ≳ p/r, as required. □

We now prove Theorem 4.15.

Proof of Theorem 4.15. We may assume that A is ergodic, implying that γ(A, ∥ · ∥_{X}^{p}), γ(A, ∥ · ∥_{Y}^{q}) < ∞, since otherwise the conclusion of Theorem 4.15 is vacuous. So, by Lemma 2.3 we have

γ_{+}(\frac{I + A}{2}, ∥ · ∥_{X}^{p}) ⩽ 2^{2p+1}γ(A, ∥ · ∥_{X}^{p}) < ∞,  (97)

and

γ_{+}(\frac{I + A}{2}, ∥ · ∥_{Y}^{q} ) ⩽ 2^{2q+1}γ(A, ∥ · ∥_{X}^{q}) < ∞,  (98)

For a Banach space (W, ∥ · ∥_{W}) and t ∈ [1, ∞] let L_{t}^{n}(W)_{0} be the subspace of L_{t}^{n}(W) consisting of mean-zero vectors, i.e.,

L_{t}^{n}(W)_{0} =^{def} {(w_{1}, …, w_{n}) ∈ L_{t}^{n}(W) : ∑_{i=1}^{n} w_{i} = 0} .

Let Q : L_{t}^{n}(ℝ) → L_{t}^{n}(ℝ)_{0} be the canonical projection, i.e, for every v ∈ L_{t}^{n}(ℝ) and i ∈ {1, …, n},

(Qv)_{i} =^{def} v_{i} − \frac{1}{n} ∑_{j=1}^{n} v_{j}.

Then by the triangle inequality, ∥Q ⊗ I_{W} ∥_{L_{t}^{n}(W)→L_{t}^{n}(W)_{0}} ⩽ 2, and consequently for every B ∈ M_{n}(ℝ) such that B(L_{t}^{n}(ℝ)_{0}) ⊆ L_{t}^{n}(ℝ)_{0},

∥(BQ) ⊗ I_{W} ∥_{L_{t}^{n}(W)→L_{t}^{n}(W)} ⩽ 2∥B ⊗ I_{W} ∥_{L_{t}^{n}(ℝ)_{0}→L_{t}^{n}(ℝ)_{0}}. (99)

Note that if B is symmetric and stochastic then B(L_{t}^{n}(ℝ)_{0}) ⊆ L_{t}^{n}(ℝ)_{0}, and by [MN12, Lem. 6.6] for every t ∈ [1, ∞] we have

∥B ⊗ I_{W} ∥_{L_{t}^{n}(ℝ)_{0}→L_{t}^{n}(ℝ)_{0}} ⩽ e^{−2/(t(2K_{t}(W))^{t}γ_{+}(B,∥·∥_{W}^{t}))}.  (100)

(Observe that we always have ∥B ⊗ I_{W} ∥_{L_{t}^{n}(ℝ)_{0}→L_{t}^{n}(ℝ)_{0}} ⩽ 1 because B is symmetric and stochastic, so (100) is most meaningful when t ∈ [2, ∞) and K_{t}(W) < ∞.) Consequently, for every m ∈ ℕ we have

∥B^{m} ⊗ I_{W} ∥_{L_{t}^{n}(ℝ)_{0}→L_{t}^{n}(ℝ)_{0}} ⩽ (∥B ⊗ I_{W} ∥_{L_{t}^{n}(ℝ)_{0}→L_{t}^{n}(ℝ)_{0}})^{m}
⩽ e^{−2m/(t(2K_{t}(W))^{t}γ_{+}(B,∥·∥_{W}^{t}))}. (101)

Define T ∈ M_{n}(ℝ) by

T =^{def} (\frac{I + A}{2})^{m} Q.

An application of (101) and (99) with W = X and t = p while using (97) shows that

∥T ⊗ I_{X}∥_{L_{p}^{n}(X)→L_{p}^{n}(X)} ⩽ 2e^{−m/(4(9K_{p}(X))^{p}γ(A,∥·∥_{X}^{p}))}.  (102)

The same reasoning applied to W = Y and t = q while using (98) shows that

∥T ⊗ I_{Y} ∥_{L_{q}^{n}(Y)→L_{q}^{n}(Y)} ⩽ 2e^{−m/(4(9K_{q}(Y))^{q}γ(A,∥·∥_{Y}^{q} ))}.  (103)

Interpolation of (102) and (103) yields the following estimate.

∥(\frac{I + A}{2})^{m} ⊗ I_{Z} ∥_{L_{s}^{n}(Z)_{0}→L_{s}^{n}(Z)_{0}} ⩽ ∥T ⊗ I_{Y} ∥_{L_{s}^{n}(Z)→L_{s}^{n}(Z)}

⩽ 2e^{−mθ/(4(9K_{p}(X))^{p}γ(A,∥·∥_{X}^{p}))−m(1−θ)/(4(9K_{q}(Y))^{q}γ(A,∥·∥_{Y}^{q} ))}. (104)

Let m be given by

m =^{def} ⌈7 min \{\frac{(9K_{p}(X))^{p}γ(A, ∥ · ∥_{X}^{p})}{θ} , \frac{(9K_{q}(Y))^{q}γ(A, ∥ · ∥_{Y}^{q})}{1 − θ} \}⌉ .

Then by (104) we have

∥(\frac{I + A}{2})^{m} ⊗ I_{Z} ∥_{L_{s}^{n}(Z)_{0}→L_{s}^{n}(Z)_{0}} ⩽ \frac{1}{2}.

By [MN12, Lem. 6.1] this implies that

γ((\frac{I + A}{2})^{m} , ∥ · ∥_{Z}^{s}) ⩽ γ_{+}((\frac{I + A}{2})^{m} , ∥ · ∥_{Z}^{s}) ⩽ 9^{s}.  (105)

Hence, using Corollary 4.4 we deduce that

2γ(A, ∥ · ∥_{Z}^{s}) =^{(39)} γ(\frac{I + A}{2}, ∥ · ∥_{Z}^{s})

≲^{(66)} C^{s} (s^{\frac{s}{r}} + S_{r}(Z)^{s}) m^{\frac{s}{r}} γ((\frac{I + A}{2})^{m} , ∥ · ∥_{Z}^{s})
⩽^{(105)} (9C)^{s} (s^{\frac{s}{r}} + S_{r}(Z)^{s}) m^{\frac{s}{r}} ,

where C is the universal constant from Corollary 4.4. Recalling our choice of m, this completes the proof of Theorem 4.15. □

5. Proof of Theorem 1.10

Let (X, ∥ · ∥_{X}) and (Y, ∥ · ∥_{Y}) be Banach spaces. We first note that the assumptions of Theorem 1.10 are equivalent to the assertion that B_{X} is uniformly homeomorphic to a subset of Y, i.e, that there is an injection ϕ : B_{X} → Y such that both ϕ and ϕ^{−1} are uniformly continuous. Indeed, since B_{X} is metrically convex, the modulus of continuity of ϕ, namely the mapping ω_{ϕ} : [0, ∞) → [0, ∞) given by

ω_{ϕ}(t) =^{def} sup{∥ϕ(x) − ϕ(y)∥_{Y} : x, y ∈ B_{X} ∧ ∥x − y∥_{X} ⩽ t},

is sub-additive (see for example [BL00, Ch. 1, Sec. 1]). Consequently, as explained in [BL00, Ch. 1, Sec. 2], there exists an increasing concave function β : [0, ∞) → [0, ∞) such that ω_{ϕ} ⩽ β ⩽ 2ω_{ϕ}.

Since β : [0, ∞) → [0, ∞) is concave, increasing, and β(0) = 0, for every q ∈ [1, ∞) the mapping t ↦ β(t^{1/q})^{q} is concave. Indeed, it suffices to verify this when β is differentiable. Denote f(t) = β(t^{1/q})^{q}. Then

f′(t) = (\frac{β(t^{1/q})}{t^{1/q}})^{q−1} β′(t^{1/q}).  (106)

By our assumptions β′ is nonnegative and decreasing, and s ↦ β(s)/s is decreasing on (0, ∞). It therefore follows from (106) that f′ is decreasing on (0, ∞), as required.

The canonical radial retraction of X onto B_{X} is denoted below by ρ : X → B_{X}, i.e.,

ρ(x) =^{def} \{ \begin{matrix}x & if ∥x∥_{X} ⩽ 1, \\ \frac{x}{∥x∥_{X}} & if ∥x∥_{X} ⩾ 1. \end{matrix}  (107)

It is straightforward to check that ρ is 2-Lipschitz.

Lemma 5.1. Under the assumptions of Theorem 1.10, fix n ∈ ℕ, q ∈ [1, ∞) and x_{1}, …, x_{n} ∈ X with

\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{X}^{q} = 1.  (108)

For every i ∈ {1, …, n} let r_{i} ∈ (0, ∞) be the smallest r > 0 such that

|\{j ∈ \{1, …, n\} : ∥x_{j} − x_{i}∥_{X} ⩽ r\}| ⩾ \frac{n}{2}.  (109)

Then for every n by n symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ),

min_{i∈\{1,...,n\}} r_{i} ⩽ max \{2(8γ(A, ∥ · ∥_{Y}^{q}))^{1/q}, \frac{2}{β^{−1} (_{\frac{α(1/4)}{8γ(A,∥·∥_{Y}^{q})^{1/q}}} )}\} . (110)

Proof. Note that the fact that the function x ↦ β(x^{1/q})^{q} is concave on [0, ∞) implies that for every λ ∈ (0, ∞) we have

(\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}β (λ∥x_{i} − x_{j}∥_{X})^{q})^{\frac{1}{q}}

⩽ β (λ (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{X}^{q})^{\frac{1}{q}} ) =^{(108)} β(λ). (111)

By relabeling the points if necessary we may also assume without loss of generality that

r_{1} = min_{i∈{1,...,n}} r_{i}.  (112)

Denote

B =^{def} {j ∈ {1, …, n} : ∥x_{j} − x_{1}∥_{X} ⩽ r_{1}}.  (113)

So, by definition,

|B| ⩾ \frac{n}{2}.  (114)

For the sake of simplicity we denote below

γ =^{def} γ(A, ∥ · ∥_{Y}^{q}) .  (115)

For i ∈ {1, …, n} define

y_{i} =^{def} x_{1} + r_{1}ρ (\frac{x_{i} − x_{1}}{r_{1}} ) ,

where ρ : X → B_{X} is given in (107). Since ρ is 2-Lipschitz,

∀ i, j ∈ {1, …, n},  ∥y_{i} − y_{j}∥_{X} ⩽ 2∥x_{i} − x_{j}∥_{X}.  (116)

40 ASSAF NAOR

By definition y_{i} ∈ x_{1} + r_{1}B_{X}, so we may consider the vectors

z_{i} =^{def} ϕ (\frac{y_{i} − x_{1}}{r_{1}} ) ∈ Y.  (117)

Now,

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥z_{i} − z_{j}∥_{Y}^{q} ⩽^{(115)} \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥z_{i} − z_{j}∥_{Y}^{q}

⩽^{(19)∧(117)∧(116)} \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}β (\frac{2∥x_{i} − x_{j}∥_{X}}{r_{1}} )^{q} ⩽^{(111)} γβ (\frac{2}{r_{1}} )^{q} . (118)

Denoting

w =^{def} \frac{1}{n} ∑_{j=1}^{n} z_{j} ∈ Y,

by the convexity of ∥ · ∥_{Y}^{q} we have

\frac{1}{n} ∑_{i=1}^{n} ∥z_{j} − w∥_{Y}^{q} ⩽ \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥z_{i} − z_{j}∥_{Y}^{q} ⩽^{(118)} γβ (\frac{2}{r_{1}} )^{q} . (119)

It follows from (119) and Markov’s inequality that if we set

C =^{def} \{i ∈ \{1, …, n\} : ∥z_{i} − w∥_{Y} ⩽ (4γ)^{1/q}β (\frac{2}{r_{1}} )\} ,  (120)

then |C| ⩾ 3n/4. By (114) it follows that

|B ∩ C| ⩾ \frac{n}{4}.  (121)

Recalling the definitions (113), (120) and (117), for every i ∈ B ∩ C we have

z_{i} = ϕ (\frac{x_{i} − x_{1}}{r_{1}} )  and ∥z_{i} − w∥_{Y} ⩽ (4γ)^{1/q}β (\frac{2}{r_{1}} ) . (122)

Hence, for every i, j ∈ B ∩ C,

α (\frac{∥x_{i} − x_{j}∥_{X}}{r_{1}} ) ⩽^{(19)} ∥ϕ (\frac{x_{i} − x_{1}}{r_{1}} ) − ϕ (\frac{x_{j} − x_{1}}{r_{1}} )∥_{Y}

=^{(122)} ∥z_{i} − z_{j}∥_{Y} ⩽ ∥z_{i} − w∥_{Y} + ∥z_{j} − w∥_{Y} ⩽^{(122)} 2(4γ)^{1/q}β (\frac{2}{r_{1}} ) .

Consequently,

i, j ∈ B ∩ C ⟹ ∥x_{i} − x_{j}∥_{X} ⩽ r =^{def} r_{1}α^{−1} (2(4γ)^{1/q}β (\frac{2}{r_{1}} )) . (123)

COMPARISON OF METRIC SPECTRAL GAPS 41

Fix an arbitrary index k ∈ B ∩ C and define

S =^{def} {j ∈ {1, …, n} : ∥x_{k} − x_{j}∥_{X} ⩽ r}.  (124)

It follows from (123) that S ⊇ B ∩ C, and therefore by (121) we have

|S| ⩾ \frac{n}{4}.  (125)

Moreover, by the definition (124),

\frac{1}{n} ∑_{i∈S} ∥x_{i} − x_{k}∥_{X}^{q} ⩽ \frac{|S|r^{q}}{n} .  (126)

Now, define for every i ∈ {1, …, n},

v_{i} =^{def} max {0, ∥x_{i} − x_{k}∥_{X} − r} ∈ [0, ∞).  (127)

Then for every i ∈ {1, …, n} ∖ S and j ∈ S,

∥x_{i} − x_{k}∥_{X}^{q} ⩽ 2^{q−1} (∥x_{i} − x_{k}∥_{X} − r)^{q} + 2^{q−1}r^{q}
=^{(127)} 2^{q−1}|v_{i} − v_{j}|^{q} + 2^{q−1}r^{q}.  (128)

Hence,

\frac{1}{n} ∑_{i∈\{1,...,n\}∖S} ∥x_{i} − x_{k}∥_{X}^{q}

⩽^{(128)} \frac{2^{q−1}}{n|S|} ∑_{i=1}^{n} ∑_{j=1}^{n} |v_{i} − v_{j}|^{q} + \frac{2^{q−1}(n − |S|)r^{q}}{n}

⩽^{(125)} \frac{2^{q+1}γ(A, d_{ℝ}^{q})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}|v_{i} − v_{j}|^{q} + \frac{2^{q−1}(n − |S|)r^{q}}{n}

⩽ 2^{q+1}γ + \frac{2^{q−1}(n − |S|)r^{q}}{n} ,  (129)

where the last step of (125) uses the trivial fact γ(A, d_{ℝ}^{q}) ⩽ γ (since Y contains an isometric copy of ℝ) and

\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}|v_{i} − v_{j}|^{q} ⩽^{(127)} \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{X}^{q} =^{(108)} 1.

A combination of (126) and (129) yields the estimate

\frac{1}{n} ∑_{i=1}^{n} ∥x_{i} − x_{k}∥_{X}^{q} ⩽ 2^{q+1}γ + 2^{q−1}r^{q}.

Consequently, an application of Markov’s inequality shows that

|\{i ∈ \{1, …, n\} : ∥x_{i} − x_{k}∥_{X} ⩽ 2^{1/q} (2^{q+1}γ + 2^{q−1}r^{q})^{1/q}\}| ⩾ \frac{n}{2}.

Recalling the definition of r_{k} (see (109)), it follows that

r_{1} ⩽^{(112)} r_{k} ⩽ 2^{1/q} (2^{q+1}γ + 2^{q−1}r^{q})^{1/q} .  (130)

If (2r)^{q} ⩽ r_{1}^{q}/2 then it follows from (130) that r_{1}^{q} ⩽ 2^{q+3}γ, implying the desired estimate (110). So, suppose that (2r)^{q} > r_{1}^{q}/2, which, by recalling the definition of r in (123), is the same as

\frac{r_{1}^{q}}{2} < (2r_{1}α^{−1} (2(4γ)^{1/q}β (\frac{2}{r_{1}} )))^{q} ,

or

α (\frac{1}{4}) ⩽ α (\frac{1}{2^{1+1/q}} ) ⩽ 2(4γ)^{1/q}β (\frac{2}{r_{1}} ) ⩽ 8γ^{1/q}β (\frac{2}{r_{1}} ) ,

implying the validity of (110) in this case as well. □

Proof of Theorem 1.10. We continue to use the notation that was introduced in the statement and the proof of Lemma 5.1. In particular, the assumptions (108) and (112) are (without loss of generality) still in force.

Recalling the definition of B in (113), we have

\frac{1}{n} ∑_{i∈B} ∥x_{i} − x_{1}∥_{X}^{q} ⩽ \frac{r_{1}^{q}|B|}{n}.  (131)

For i ∈ {1, …, n} define

u_{i} =^{def} max{0, ∥x_{i} − x_{1}∥_{X} − r_{1}} ∈ [0, ∞).  (132)

Then for every i ∈ {1, …, n} ∖ B and j ∈ B we have

∥x_{i} − x_{1}∥_{X}^{q} ⩽ 2^{q−1} (∥x_{i} − x_{1}∥_{X} − r_{1})^{q} + 2^{q−1}r_{1}^{q}
=^{(132)} 2^{q−1}|u_{i} − u_{j}|^{q} + 2^{q−1}r_{1}^{q}.

Arguing exactly as in (129) (with the use of (125) replaced by the use of (114)), it follows that

\frac{1}{n} ∑_{i∈\{1,...,n\}∖B} ∥x_{i} − x_{1}∥_{X}^{q} ⩽ 2^{q}γ + \frac{2^{q−1}(n − |B|)r_{1}^{q}}{n} .  (133)

Consequently,

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{X}^{q} ⩽ \frac{2^{q−1}}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − x_{1}∥_{X}^{q} + ∥x_{1} − x_{j}∥_{X}^{q})

= \frac{2^{q}}{n} ∑_{i=1}^{n} ∥x_{i} − x_{1}∥_{X}^{q} ⩽^{(131)∧(133)} 4^{q}γ + \frac{4^{q}r_{1}^{q}}{2} . (134)

The desired estimate (20) now follows substituting (110) into (134). □

5.1. Limitations of Ozawa’s method. In the discussion immediately preceding the estimates (21) and (22) we stated that for every p ∈ [1, ∞) there exists a mapping ϕ : ℓ_{p} → ℓ_{2} such that for every x, y ∈ ℓ_{p} we have

p ∈ (2, ∞) ⟹ \frac{∥x − y∥_{ℓ_{p}}^{p/2}}{2^{(p−2)/2}} ⩽ ∥ϕ(x) − ϕ(y)∥_{ℓ_{2}} ⩽ p∥x − y∥_{ℓ_{p}}, (135)

and

p ∈ [1, 2) ⟹ \frac{∥x − y∥_{ℓ_{p}}}{3} ⩽ ∥ϕ(x) − ϕ(y)∥_{ℓ_{2}} ⩽ 2∥x − y∥_{ℓ_{p}}^{p/2}. (136)

The estimates (135) and (136) are a special case of the following bounds on the modulus of uniform continuity of the Mazur map [Maz29] (see also [BL00, Ch.9]). Let (Ω, μ) be a measure space and fix p, q ∈ [1, ∞). Define M_{p,q} : L_{p}(μ) → L_{q}(μ) by

∀ f ∈ L_{p}(μ), M_{p,q}(f) =^{def} |f|^{p/q}sign(f).

If p ⩾ q then for every f, g ∈ L_{p}(μ) with ∥f∥_{L_{p}(μ)}, ∥g∥_{L_{p}(μ)} ⩽ 1 we have

\frac{∥f − g∥_{L_{p}(μ)}^{p/q}}{2^{(p−q)/q}} ⩽ ∥M_{p,q}(f) − M_{p,q}(g)∥_{L_{q}(μ)} ⩽ \frac{2^{\frac{1}{q} − \frac{1}{p}} p∥f − g∥_{L_{p}(μ)}}{q} . (137)

Note that (135) is a special case of (137), and (136) is also a consequence of (137) because M_{p,q}^{−1} = M_{q,p}. While the bounds appearing in (137) are entirely standard, they seem to have been always stated in the literature while either using implicit multiplicative constant factors, or with suboptimal constant factors. These constants play a role in our context, so we briefly include the proof of (137), following the lines of the proof of [BL00, Prop. 9.2]. The elementary inequality

||u|^{θ}sign(u) − |v|^{θ}sign(v)| ⩾ \frac{|u − v|^{θ}}{2^{θ−1}} ,

which holds for every u, v ∈ ℝ and θ ∈ [1, ∞), immediately implies (with θ = p/q) the leftmost inequality in (137). To prove the rightmost inequality of (137), note the following elementary inequality, which also holds for every u, v ∈ ℝ and θ ∈ [1, ∞).

||u|^{θ}sign(u) − |v|^{θ}sign(v)| ⩽ θ|u − v| max {|u|^{θ−1}, |v|^{θ−1}} .

Consequently,

∥M_{p,q}(f) − M_{p,q}(g)∥_{L_{q}(μ)}^{q}

⩽ \frac{p^{q}}{q^{q}} ∫_{Ω} |f − g|^{q} max \{|f|, |g|\}^{p−q} dμ

⩽ \frac{p^{q}}{q^{q}} ∥f − g∥_{L_{p}(μ)}^{q} · ∥max\{|f|, |g|\}∥_{L_{p}(μ)}^{p−q}  (138)
⩽ \frac{p^{q} · 2^{(p−q)/p}}{q^{q}} ∥f − g∥_{L_{p}(μ)}^{q},  (139)

where (138) follows from an application of Hölder’s inequality with exponents p/q and p/(p − q) and (139) holds true because we have ∥ max{|f|, |g|}∥_{L_{p}(μ)}^{p} ⩽ ∥f∥_{L_{p}(μ)}^{p} + ∥g∥_{L_{p}(μ)}^{p} ⩽ 2.

Returning to Theorem 1.10 (in particular using the notation and assumptions that were introduced in the statement of Theorem 1.10), if one wants the bound (20) to be compatible with the assumption of Theorem 1.3 one needs (20) to yield an upper bound on γ(A, ∥·∥_{X}^{q}) that grows linearly with γ(A, ∥ · ∥_{Y}^{q}). This is equivalent to the requirement

β^{−1} (\frac{α(1/4)}{8γ(A, ∥ · ∥_{Y}^{q})^{1/q}} )^{q} ≳_{X,Y} \frac{1}{γ(A, ∥ · ∥_{Y}^{q})} .  (140)

Since (140) is supposed to hold for every n ∈ ℕ and every n by n symmetric stochastic matrix A, (140) is the same as requiring that β(t) ≲_{X,Y} t for every t ∈ (0, ∞].

Specializing the above discussion to Y = ℓ_{2} and q = 2, if β(t) ⩽ Kt for some K ∈ (0, ∞) and every t ∈ (0, ∞) then (20) yields the estimate

γ(A, ∥ · ∥_{X}^{q}) ≲ \frac{(K/α(1/4))^{2}}{1 − λ_{2}(A)} .

By Corollary 1.4, this implies that

Av_{ℓ_{2}}^{(2)}(X) ≲ \frac{K}{α(1/4)}.

In particular, if p ∈ (2, ∞) then due to (135) we get the estimate

Av_{ℓ_{2}}^{(2)}(ℓ_{p}) ≲ p2^{3p/2},

which is exponentially worse than (23). The following lemma shows that this exponential loss is inherent to the use of Theorem 1.10 for the purpose of obtaining average distortion embedding of finite subsets of ℓ_{p} into ℓ_{2}, i.e., that K/α(1/4) must grow exponentially in p as p → ∞.

Lemma 5.2. Suppose that p ∈ (2, ∞) and that ϕ : B_{X} → ℓ_{2} satisfies

α (∥x − y∥_{ℓ_{p}}) ⩽ ∥ϕ(x) − ϕ(y)∥_{ℓ_{2}} ⩽ K∥x − y∥_{ℓ_{p}},  (141)

for every x, y ∈ B_{ℓ_{p}}, where α : (0, 2] → (0, ∞) is increasing. Then

∀ ε ∈ (0, 2),  \frac{K}{α(2 − ε)} ≳ \frac{1}{(1 − ε/2)^{p/2}} .  (142)

In particular, for ε = 7/4 we have K/α(1/4) ≳ 2^{3p/2}.

Proof. Fix m, n ∈ ℕ and s ∈ (0, 1]. For every x ∈ ℤ^{n} define ψ(x) ∈ ℓ_{p} to be the vector whose jth coordinate equals

\frac{s}{n^{1/p}} e^{2πx_{j}i/m}

if j ∈ {1, …, n}, and whose remaining coordinates vanish. Then we have ∥ψ(x)∥_{ℓ_{p}} ⩽ s ⩽ 1 for every x ∈ ℤ^{n}.

By the results of Section 3 of [MN08], if m is divisible by 4 and m ⩾ \frac{2}{3}π\sqrt{n} then we have

\frac{1}{m^{n}} ∑_{j=1}^{n} ∑_{x∈\{0,...,m−1\}^{n}} ∥ϕ (ψ (x + \frac{m}{2}e_{j})) − ϕ(ψ(x))∥_{ℓ_{2}}^{2}

≲ \frac{m^{2}}{(3m)^{n}} ∑_{ω∈\{−1,0,1\}^{n}} ∑_{x∈\{0,...,m−1\}^{n}} ∥ϕ (ψ(x + ω)) − ϕ(ψ(x))∥_{ℓ_{2}}^{2} . (143)

Now, by the leftmost inequality in (141) for every x ∈ {0, …, m − 1}^{n} and j ∈ {1, …, n} we have

∥ϕ (ψ (x + \frac{m}{2}e_{j})) − ϕ(ψ(x))∥_{ℓ_{2}} ⩾ α (\frac{s |e^{2π(x_{j}+m/2)i/m} − e^{2πx_{j}i/m}|}{n^{1/p}})

= α (\frac{2s}{n^{1/p}} ) .  (144)

Also, by the rightmost inequality in (141), for every x ∈ {0, …, m−1}^{n} and ω ∈ {−1, 0, 1}^{n} we have

∥ϕ (ψ(x + ω)) − ϕ(ψ(x))∥_{ℓ_{2}} ⩽ \frac{Ks}{n^{1/p}} (∑_{j=1}^{n} |e^{2π(x_{j}+ω_{j})i/m} − e^{2πx_{j}i/m}|^{p})^{\frac{1}{p}}

≲ \frac{Ks}{m}.  (145)

Choose n =^{def} ⌊1/(1 − ε/2)^{p}⌋ and s =^{def} (1 − ε/2)n^{1/p} ∈ (0, 1]. Then, if m is the smallest integer that is divisible by 4 and satisfies m ⩾ \frac{2}{3}π\sqrt{n}, by substituting (145) and (144) into (143) we see that

nα (2 − ε)^{2} ≲ m^{2} · \frac{K^{2}s^{2}}{m^{2}} ≲ n\frac{K^{2}(1 − ε/2)^{2}}{n^{1−2/p}} ≲ nK^{2}(1 − ε/2)^{p},

which simplifies to give the desired estimate (142). □

6. Bourgain–Milman–Wolfson type

Here we study aspects of nonlinear type in the sense of Bourgain, Milman and Wolfson [BMW86], proving in particular Lemma 1.12, Lemma 1.13 and Theorem 1.15 that were stated in the Introduction.

6.1. On the Maurey–Pisier problem for BMW type. In what follows, for every finite set Ω and p ∈ [1, ∞), the space L_{p}(Ω) consists of all mappings f : Ω → ℝ, equipped with the norm

∥f∥_{L_{p}(Ω)} =^{def} (\frac{1}{|Ω|} ∑_{ω∈Ω} |f(ω)|^{p})^{\frac{1}{p}} .

For every k ∈ {1, …, n} let Ω_{k}^{n} ⊆ 𝔽_{2}^{n} × 2^{{1,...,n}} be defined by

Ω_{k}^{n} =^{def} 𝔽_{2}^{n} × \binom{\{1, …, n\}}{k} = 𝔽_{2}^{n} × \{I ⊆ \{1, …, n\} : |I| = k\} .

Thus |Ω_{k}^{n}| = 2^{n}\binom{n}{k}.

Fixing a metric space (X, d_{X}) and f : 𝔽_{2}^{n} → X, define

∀(z, I) ∈ 𝔽_{2}^{n} × 2^{𝔽_{2}^{n}},  D_{f}(z, I) =^{def} d_{X} (f (z + e_{I}) , f(z)) , (146)

where for I ⊆ {1, …, n} we set

e_{I} =^{def} ∑_{i∈I} e_{i} ∈ 𝔽_{2}^{n}.

Thus, using the notation of the Introduction, we have e_{{1,...,n}} = e. For q ∈ (0, ∞) define E_{k}^{(q)}(f) ∈ [0, ∞) by

E_{k}^{(q)}(f)^{q} =^{def} ∥D_{f}∥_{L_{q}(Ω_{k}^{n})}^{q}
= \frac{1}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}I⊆\{1,...,n\} \\ |I|=k \end{matrix}} ∑_{z∈𝔽_{2}^{n}} d_{X} (f (z + e_{I}) , f(z))^{q} .  (147)

Note that since for every I, J ⊆ {1, …, n} with |I| = |J| the number of permutations σ ∈ S_{n} satisfying σ(I) = J equals |I|!(n − |I|)!,

∀ I ⊆ \{1, …, n\},  E_{|I|}^{(q)}(f)^{q} = \frac{1}{2^{n}n!} ∑_{x∈𝔽_{2}^{n}} ∑_{σ∈S_{n}} D_{f}(x, σ(I))^{q}. (148)

We also record for future use the following simple consequence of the triangle inequality in (X, d_{X}). Lemma 6.1. Fix n ∈ ℕ and q ∈ [1, ∞). Suppose that (X, d_{X}) is a metric space and f : 𝔽_{2}^{n} → X. Then for every k, m ∈ {1, …, n} with k + m ⩽ n we have

E_{k+m}^{(q)}(f) ⩽ E_{k}^{(q)}(f) + E_{m}^{(q)}(f).  (149)

Proof. Fix I ⊆ {1, …, n} with |I| = k + m. Recalling (146), for every J ⊆ I with |J| = k and every z ∈ 𝔽_{2}^{n} we have

D_{f}(z, I) ⩽ D_{f}(z, I ∖ J) + D_{f}(z + e_{I∖J}, J).

Consequently,

∀(z, I) ∈ Ω_{k+m}^{n},  D_{f}(z, I) ⩽ U_{f}(z, I) + V_{f}(z, I),  (150)

where

U_{f}(z, I) =^{def} \frac{1}{\binom{k+m}{k}} ∑_{\begin{matrix}J⊆I \\ |J|=k \end{matrix}} D_{f}(z, I ∖ J).

and

V_{f}(z, I) =^{def} \frac{1}{\binom{k+m}{k}} ∑_{\begin{matrix}J⊆I \\ |J|=k \end{matrix}} D_{f}(z + e_{I∖J}, J).

The point-wise estimate (150) combined with the triangle inequality in L_{q}(Ω_{k+m}^{n}) implies that

E_{k+m}^{(q)}(f) = ∥D_{f}∥_{L_{q}(Ω_{k+m}^{n})} ⩽ ∥U_{f}∥_{L_{q}(Ω_{k+m}^{n})} + ∥V_{f}∥_{L_{q}(Ω_{k+m}^{n})} . (151)

By the convexity of t ↦ |t|^{q} we have

∥U_{f}∥_{L_{q}(Ω_{k+m}^{n})}^{q} ⩽ \frac{1}{2^{n}\binom{n}{k+m}} ∑_{\begin{matrix}I⊆\{1,...,n\} \\ |I|=k+m \end{matrix}} ∑_{z∈𝔽_{2}^{n}} \frac{1}{\binom{k+m}{k}} ∑_{\begin{matrix}J⊆I \\ |J|=k \end{matrix}} D_{f}(z, I ∖ J)^{q}

= \frac{1}{2^{n}\binom{n}{k+m}\binom{k+m}{k}} ∑_{z∈𝔽_{2}^{n}} ∑_{\begin{matrix}S⊆\{1,...,n\} \\ |S|=m \end{matrix}} \binom{n − m}{k}D_{f}(z, S)^{q} = E_{m}^{(q)}(f)^{q}, (152)

and

∥V_{f}∥_{L_{q}(Ω_{k+m}^{n})}^{q} ⩽ \frac{1}{2^{n}\binom{n}{k+m}} ∑_{\begin{matrix}I⊆\{1,...,n\} \\ |I|=k+m \end{matrix}} ∑_{z∈𝔽_{2}^{n}} \frac{1}{\binom{k+m}{k}} ∑_{\begin{matrix}J⊆I \\ |J|=k \end{matrix}} D_{f}(z + e_{I∖J}, J)^{q}

= \frac{1}{2^{n}\binom{n}{k+m}\binom{k+m}{k}} ∑_{\begin{matrix}I⊆\{1,...,n\} \\ |I|=k+m \end{matrix}} ∑_{\begin{matrix}J⊆I \\ |J|=k \end{matrix}} ∑_{w∈𝔽_{2}^{n}} D_{f}(w, J)^{q} = E_{k}^{(q)}(f)^{q}. (153)

The desired estimate (149) now follows from a substitution of (152) and (153) into (151). □

For m, n ∈ ℕ with n ⩾ m, for every f : 𝔽_{2}^{m} → X denote its natural lifting to 𝔽_{2}^{n} by f^{↑n} : 𝔽_{2}^{n} → X, that is,

∀ z ∈ 𝔽_{2}^{n}, f^{↑n}(z) =^{def} f(z_{1}, …, z_{m}).

We then have the following identity for every k ∈ {1, …, n}.

E_{k}^{(q)} (f^{↑n})^{q} = \frac{1}{2^{n}\binom{n}{k}} ∑_{\begin{matrix}I⊆\{1,...,n\} \\ |I|=k \end{matrix}} 2^{n−m} ∑_{w∈𝔽_{2}^{m}} D_{f}(w, I ∩ \{1, …, m\})^{q} (154)

= \frac{1}{\binom{n}{k}} ∑_{ℓ=max\{1,m+k−n\}}^{min\{k,m\}} \binom{n − m}{k − ℓ}\binom{m}{ℓ}E_{ℓ}^{(q)}(f)^{q},  (155)

where (154) uses (146) and (147), and the identity (155) follows by observing that if I ⊆ {1, …, n} satisfies |I ∩ {1, …, m}| = ℓ then necessarily ℓ ⩾ m + k − n and for each J ⊆ {1, …, m} with |J| = ℓ the number of subsets I ⊆ \{1, …, n\} with I ∩ \{1, …, m\} = J is \binom{n−m}{k−ℓ}. Note in particular the following two special cases of (155).

E_{n}^{(q)} (f^{↑n}) = E_{n}^{(q)}(f) and E_{1}^{(q)} (f^{↑n}) = (\frac{m}{n})^{1/q} E_{1}^{(q)}(f). (156)

When q = 2 in (147) we write E_{k}(f) =^{def} E_{k}^{(2)}(f). With this notation, a metric space (X, d_{X}) has BMW type p ∈ (0, ∞) if and only if there exists T ∈ (0, ∞) such that for every n ∈ ℕ and every f : 𝔽_{2}^{n} → X,

E_{n}(f) ⩽ T n^{1/p}E_{1}(f).  (157)

Let BMW_{p}^{n}(X) denote the infimum over those T ∈ (0, ∞) for which (157) holds true for every f : 𝔽_{2}^{n} → X. Thus

BMW_{p}(X) = sup_{n∈ℕ} BMW_{p}^{n}(X).

Remark 6.2. By definition we have BMW_{p}^{n}(X)n^{1/p} = BMW_{q}^{n}(X)n^{1/q} for every p, q ∈ (0, ∞). Also, unless |X| = 1 we have BMW_{p}^{1}(X) = 1.

Remark 6.3. By Lemma 6.1 we have E_{n}(f) ⩽ nE_{1}(f), so

∀ n ∈ ℕ, BMW_{p}^{n}(X) ⩽ n^{1− \frac{1}{p}} .

Moreover, given m, n ∈ ℕ with n ⩾ m and f : 𝔽_{2}^{m} → X with E_{1}(f) > 0, by (156) we have

\frac{E_{m}(f)}{E_{1}(f)} = \frac{E_{n} (f^{↑n})}{E_{1} (f^{↑n})} · \sqrt{\frac{n}{m}}.

Consequently,

∀ m, n ∈ ℕ, m ⩽ n ⟹ BMW_{p}^{m}(X)\sqrt{m} ⩽ BMW_{p}^{n}(X)\sqrt{n}. (158)

Remark 6.4. Let (X, d_{X}) be a metric space and p ∈ (1, ∞) be such that X has BMW type p. Then necessarily p ⩽ 2. Indeed, choose distinct x_{0}, x_{1} ∈ X and for every n ∈ ℕ define f_{n} : 𝔽_{2}^{n} → X by f_{n}(z) = x_{z_{1}}. Then E_{1}(f_{n}) = d_{X}(x_{0}, x_{1})/\sqrt{n} and E_{n}(f_{n}) = d_{X}(x_{0}, x_{1}). This means that n^{1/p}BMW_{p}(X) ⩾ \sqrt{n} for all n ∈ ℕ, which implies that p ⩽ 2. A straightforward application of the triangle inequality (see [BMW86]) implies that every metric space has BMW type 1 with BMW_{1}(X) = 1.

Recalling the definition of p_{X} ∈ [1, 2] in (27), we have the following lemma that relies on a sub-multiplicativity argument that was introduced by Pisier [Pis73] in the context of Rademacher type of normed spaces, and has been implemented in the context of nonlinear type by Bourgain, Milman and Wolfson [BMW86] (see also [Pis86]).

Lemma 6.5. For every metric space (X, d_{X}) we have

∀ n ∈ ℕ, BMW_{p_{X}}^{n}(X) ⩾ 1.

Proof. Write p = p_{X} and suppose for the sake of obtaining a contradiction that there exists m ∈ ℕ and ε ∈ (0, 1) such that BMW_{p}^{m}(X) < ε. We may also assume without loss of generality that ε > 1/\sqrt{m}. Since BMW_{p}^{1}(X) = 1, we have m ⩾ 2. If we define

q =^{def} \frac{1}{\frac{1}{p} − \frac{log(1/ε)}{log m}}  (159)

then q ∈ (p, ∞) because p ⩾ 1/2 (recall Remark 6.4) and ε > 1/\sqrt{m}. By [BMW86, Lem. 2.3] (see also [Pis86, Lem.7.2]), for every k, n ∈ ℕ,

BMW_{p}^{kn}(X) ⩽ BMW_{p}^{k}(X) · BMW_{p}^{n}(X).

Consequently, for every i ∈ ℕ we have

BMW_{p}^{m^{i}}(X) ⩽ BMW_{p}^{m}(X)^{i} < ε^{i} =^{(159)} m^{−i(\frac{1}{p} − \frac{1}{q})}.  (160)

For every n ∈ ℕ choose i ∈ ℕ such that m^{i−1} ⩽ n < m^{i}. Since, by (158), BMW_{p}^{n}(X)\sqrt{n} increases with n, it follows from (160) that

BMW_{q}^{n}(X) = n^{\frac{1}{p} − \frac{1}{q} − \frac{1}{2}} · BMW_{p}^{n}(X)\sqrt{n} ⩽ n^{\frac{1}{p} − \frac{1}{q} − \frac{1}{2}} · BMW_{p}^{m^{i}}(X)m^{\frac{i}{2}}

<^{(160)} n^{\frac{1}{p} − \frac{1}{q} − \frac{1}{2}} · m^{−i(\frac{1}{p} − \frac{1}{q} − \frac{1}{2})} ⩽ m^{\frac{1}{2} − \frac{1}{p} + \frac{1}{q}} =^{(159)} ε\sqrt{m},

where we used the fact that 1/2 − 1/p + 1/q > 0 (by (159) and the assumption ε > 1/\sqrt{m}). Consequently BMW_{q}(X) < ∞, i.e., X has BMW type q. Since q > p, this contradicts the definition of p_{X} = p. □

Lemma 6.6. Fix p ∈ [1, 2], n ∈ ℕ, and k_{1}, …, k_{m} ∈ {1, …, n} such that k_{1} + … + k_{m} ⩽ n. Then for every metric space (X, d_{X}) and every f : 𝔽_{2}^{n} → X we have

E_{k_{1}+...+k_{m}}(f) ⩽ BMW_{p}(X)m^{\frac{1}{p} − \frac{1}{2}} (∑_{j=1}^{m} E_{k_{j}}(f)^{2})^{\frac{1}{2}} .  (161)

Proof. Write k_{0} = 0 and I = {1, …, k_{1} + … + k_{m}} ⊆ {1, …, n}. For every j ∈ {1, …, m} set I_{j} = {k_{1} +…+k_{j−1} +1, …, k_{1} +…+k_{j}} ⊆ I. Fixing x ∈ 𝔽_{2}^{n} and a permutation σ ∈ S_{n}, define ϕ_{x}^{σ} : 𝔽_{2}^{m} → X by

ϕ_{x}^{σ}(z) =^{def} f (x + ∑_{s=1}^{m} z_{s}e_{σ(I_{s})}) .

An application of the definition of BMW_{p}(X) to ϕ_{x}^{σ} yields the inequality

\frac{1}{2^{m}} ∑_{z∈𝔽_{2}^{m}} D_{f} (x + ∑_{s=1}^{m} z_{s}e_{σ(I_{s})}, σ(I))^{2}

⩽ \frac{BMW_{p}(X)^{2}m^{\frac{2}{p} −1}}{2^{m}} ∑_{z∈𝔽_{2}^{m}} ∑_{j=1}^{m} D_{f} (x + ∑_{s=1}^{m} z_{s}e_{σ(I_{s})}, σ(I_{j}))^{2} . (162)

Recalling (148), by averaging (162) over x ∈ 𝔽_{2}^{n} and σ ∈ S_{n} we obtain

E_{k_{1}+...+k_{m}}(f)^{2} = \frac{1}{2^{n}n!} ∑_{y∈𝔽_{2}^{n}} ∑_{σ∈S_{n}} D_{f} (y, σ(I))^{2}

⩽ \frac{BMW_{p}(X)^{2}m^{\frac{2}{p} −1}}{2^{n}n!} ∑_{j=1}^{m} ∑_{y∈𝔽_{2}^{n}} ∑_{σ∈S_{n}} D_{f}(y, σ(I_{j}))^{2}

= BMW_{p}(X)^{2}m^{\frac{2}{p} −1} ∑_{j=1}^{m} E_{k_{j}}(f)^{2}.  □

Proof of Theorem 1.15. Denote p_{X} = p. Fix ε ∈ (0, 1/3) and define

n =^{def} ⌈\frac{BMW_{p}(X)^{4}}{ε} d⌉ .  (163)

Since n ⩾ d, we can consider 𝔽_{p}^{d} as a subset of 𝔽_{p}^{n} (say, canonically embedded as the first d coordinates).

By Lemma 6.5 we have BMW_{p}^{n}(X) ⩾ 1, and therefore by the definition of BMW_{p}^{n}(X) there exists f : 𝔽_{p}^{n} → X such that

E_{n}(f) ⩾ (1 − ε)n^{1/p}E_{1}(f) > 0.  (164)

Write

Y =^{def} ℓ_{2}^{𝔽_{2}^{n}×S_{n}}(X) ≅ ℓ_{2}^{2^{n}n!}(X).

Define F : 𝔽_{2}^{n} → Y by setting

∀(x, z, π) ∈ 𝔽_{2}^{n} × 𝔽_{2}^{n} × S_{n}, F (x)_{(z,π)} =^{def} f(π(x) + z),

where π(x) =^{def} ∑_{i=1}^{n} x_{π(i)}e_{i}. Recalling (147), every x, y ∈ 𝔽_{2}^{n} satisfy

d_{Y} (F (x), F (y)) = \sqrt{2^{n}n!} · E_{∥x−y∥_{1}}(f),  (165)

By Lemma 6.6 with m = ∥x − y∥_{1} and k_{1} = … = k_{m} = 1, for every x, y ∈ 𝔽_{p}^{n} we have

\frac{d_{Y} (F (x), F (y))}{\sqrt{2^{n}n!}} ⩽^{(161)∧(165)} BMW_{p}(X)∥x − y∥_{1}^{\frac{1}{p} − \frac{1}{2}} · \sqrt{∥x − y∥_{1}}E_{1}(f)
=  BMW_{p}(X)E_{1}(f)∥x − y∥_{p}.  (166)

Fixing x, y ∈ 𝔽_{p}^{d} ⊆ 𝔽_{p}^{n}, write n = a∥x−y∥_{1}+b for appropriate integers a and b ∈ [0, ∥x−y∥_{1}). By Lemma 6.6 with m = b and k_{1} = … = k_{m} = 1,

E_{b}(f) ⩽ BMW_{p}(X)b^{1/p}E_{1}(f) ⩽ BMW_{p}(X)∥x − y∥_{1}^{1/p}E_{1}(f). (167)

Using Lemma 6.6 once more, this time with m = a + 1, k_{1} = b and k_{2} = … = k_{a+1} = ∥x − y∥_{1}, and noting that since ∥x − y∥_{1} ⩽ d ⩽ εn we have m ⩽ (1 + ε)n/∥x − y∥_{1}, we conclude that

E_{n}(f) ⩽ BMW_{p}(X) (\frac{(1 + ε)n}{∥x − y∥_{1}} )^{\frac{1}{p} − \frac{1}{2}} \sqrt{\frac{n}{∥x − y∥_{1}} E_{∥x−y∥_{1}}(f)^{2} + E_{b}(f)^{2}}.

In combination with (167) and our assumption (164), this implies

(1 − ε)^{2}n^{2/p}E_{1}(f)^{2} ⩽ (1 + ε)BMW_{p}(X)^{2} (\frac{n}{∥x − y∥_{1}} )^{2/p} E_{∥x−y∥_{1}}(f)^{2}

+ (1 + ε)n^{2/p}BMW_{p}(X)^{4} \frac{∥x − y∥_{1}}{n} E_{1}(f)^{2}. (168)

Recalling (163), we have ∥x − y∥_{1}/n ⩽ d/n ⩽ εBMW_{p}(X)^{4} (since x, y ∈ 𝔽_{2}^{d}), and it therefore follows from (168) that

\frac{d_{Y} (F (x), F (y))}{\sqrt{2^{n}n!}} =^{(165)} E_{∥x−y∥_{1}}(f) ⩾ \frac{∥x − y∥_{p}E_{1}(f)}{BMW_{p}(X)}\sqrt{\frac{1 − 3ε}{1 + ε}}. (169)

Since ε ∈ (0, 1/3) can be taken to be arbitrarily small, by combining (166) and (169) we conclude that

c_{Y} (𝔽_{2}^{d}, ∥x − y∥_{p}) ⩽ BMW_{p}(X)^{2}.  □

6.2. Obstructions to average distortion embeddings of cubes. We start by proving Lemma 1.13, whose proof is very simple.

Proof of Lemma 1.13. Fix D > Av_{Y}^{(2)}(X) and n ∈ ℕ. If f : 𝔽_{2}^{n} → X then there exists a nonconstant mapping g : f(𝔽_{2}^{n}) → Y such that

∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} d_{Y} (g(f(x)), g(f(y)))^{2} ⩾ \frac{∥g∥_{Lip}^{2}}{D^{2}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} d_{X}(f(x), f(y))^{2}.

Consequently,

\frac{1}{2^{n}} ∑_{x∈𝔽_{2}^{n}} d_{X}(f(x), f(x + e))^{2}

⩽ \frac{2}{4^{n}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} (d_{X}(f(x), f(y))^{2} + d_{X}(f(y), f(x + e))^{2})

= \frac{1}{4^{n−1}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} d_{X}(f(x), f(y))^{2}

⩽ \frac{D^{2}}{4^{n−1}∥g∥_{Lip}^{2}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} d_{Y} (g(f(x)), g(f(y)))^{2}.  (170)

Now,

\frac{1}{4^{n}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} d_{Y} (g(f(x)), g(f(y)))^{2} =^{(147)} \frac{1}{2^{n}} ∑_{k=1}^{n} \binom{n}{k}E_{k}(g ∘ f)^{2}

⩽^{(161)} \frac{1}{2^{n}} ∑_{k=1}^{n} \binom{n}{k}BMW_{p}(Y)^{2}k^{2/p}E_{1}(g ∘ f)^{2}. (171)

Since E_{1}(g ∘ f) ⩽ ∥g∥_{Lip}E_{1}(f), it follows from (170) and (171) that BMW_{p}(X) ⩽ 2Av_{Y}^{(2)}(X)BMW_{p}(Y). □

Recall that (see e.g. [Mau03]) a Banach space (X, ∥ · ∥_{X}) is said to have Rademacher type p constant T ∈ (0, ∞) if for every m ∈ ℕ and every x_{1}, …, x_{m} ∈ X we have

(𝔼_{ε} [∥∑_{i=1}^{m} ε_{i}x_{i}∥_{X}^{2} ])^{\frac{1}{2}} ⩽ T (∑_{i=1}^{m} ∥x_{i}∥_{X}^{p})^{\frac{1}{p}} ,  (172)

where 𝔼_{ε}[·] is the expectation with respect to i.i.d. ±1 Bernoulli random variables ε_{1}, …, ε_{n}. The infimum over those T ∈ (0, ∞) for which X has Rademacher type p constant T is denoted T_{p}(X). If no such T exists then we write T_{p}(X) = ∞.

Lemma 6.7. Assume that p ∈ [1, 2) and fix q ∈ (p, 2] and r, s ∈ [1, ∞). Suppose that (Y, ∥ · ∥_{Y}) is a Banach space with T_{q}(Y) < ∞ and that f : 𝔽_{2}^{m} → Y satisfies

(\frac{1}{4^{m}} ∑_{(x,y)∈𝔽_{2}^{m}×𝔽_{2}^{m}} ∥f(x) − f(y)∥_{Y}^{r} )^{\frac{1}{r}}

= (\frac{1}{4^{m}} ∑_{(x,y)∈𝔽_{2}^{m}×𝔽_{2}^{m}} ∥x − y∥_{ℓ_{p}}^{s})^{\frac{1}{s}} ≍ m^{1/p}. (173)

Then there exists x ∈ 𝔽_{2}^{m} and i ∈ {1, …, n} such that

∥f(x) − f(x + e_{i})∥_{Y} ≳ \frac{1}{\sqrt{r}T_{q}(Y)} · \frac{m^{\frac{1}{p} − \frac{1}{q}}}{log m} .  (174)

Proof. By Pisier’s inequality [Pis86] we have

m^{1/p} ≲^{(173)} (\frac{1}{4^{m}} ∑_{(x,y)∈𝔽_{2}^{m}×𝔽_{2}^{m}} ∥f(x) − f(y)∥_{Y}^{r} )^{\frac{1}{r}}

≲ log m (\frac{1}{2^{m}} ∑_{x∈𝔽_{2}^{n}} 𝔼_{ε} [∥∑_{i=1}^{m} ε_{i}(f(x + e_{i}) − f(x))∥_{Y}^{r} ])^{\frac{1}{r}} . (175)

For every fixed x ∈ 𝔽_{2}^{m} it follows from Kahane’s inequality (with asymptotically optimal dependence on r; see e.g. [Tal88]) that

(𝔼_{ε} [∥∑_{i=1}^{m} ε_{i}(f(x + e_{i}) − f(x))∥_{Y}^{r} ])^{\frac{1}{r}}

≲ \sqrt{r} (𝔼_{ε} [∥∑_{i=1}^{m} ε_{i}(f(x + e_{i}) − f(x))∥_{Y}^{2} ])^{\frac{1}{2}}

⩽ \sqrt{r}T_{q}(Y) (∑_{i=1}^{m} ∥f(x + e_{i}) − f(x)∥_{Y}^{q} )^{\frac{1}{q}} .

Combined with (175), this implies that

max_{\begin{matrix}x∈𝔽_{2}^{m} \\ i∈\{1,...,m\} \end{matrix}} ∥f(x + e_{i}) − f(x)∥_{Y} ≳ \frac{1}{\sqrt{r}T_{q}(Y)} · \frac{m^{\frac{1}{p} − \frac{1}{q}}}{log m} .  □

There are classes of Banach spaces Y, including Banach lattices of nontrivial type and UMD spaces, for which it is known that Pisier’s inequality (175) holds true with the log m factor replaced by a constant that may depend on Y and r but not on m; see [NS02, HN13]. For such spaces we therefore obtain (174) without the log m term.

Lemma 6.8. Assume that p ∈ [1, 2) and fix q ∈ (p, 2] and r, s ∈ [1, ∞). Suppose that (Y, ∥ · ∥_{Y}) is a Banach space with S_{q}(Y) < ∞, i.e., Y has modulus of uniform smoothness of power type q. If f : 𝔽_{2}^{m} → Y satisfies (173) then there exists x ∈ 𝔽_{2}^{m} and i ∈ {1, …, n} such that

∥f(x) − f(x + e_{i})∥_{Y} ≳ \frac{m^{\frac{1}{p} − \frac{1}{q}}}{r^{1/q} + S_{q}(Y)}.  (176)

Proof. Due to (173), in order to prove (176) it suffices to show that for every h : 𝔽_{2}^{m} → Y,

(\frac{1}{4^{m}} ∑_{(x,y)∈𝔽_{2}^{m}×𝔽_{2}^{m}} ∥h(x) − h(y)∥_{Y}^{r} )^{\frac{1}{r}}

≲ (r^{\frac{1}{q}} + S_{q}(Y)) m^{\frac{1}{q}} (\frac{1}{m2^{m}} ∑_{i=1}^{m} ∑_{x∈𝔽_{2}^{m}} ∥h(x + e_{i}) − h(x)∥_{Y}^{r} )^{\frac{1}{r}} . (177)

Note that it suffices to prove (177) when r ⩾ 2, since otherwise we could replace q by r and use the fact that S_{r}(Y) ⩽ S_{q}(Y).

By considering the standard random walk on the Hamming cube 𝔽_{2}^{n} and arguing mutatis mutandis as in [NS02, Sec. 5], (177) is a formal consequence of the Markov type estimate of Theorem 4.3. Alternatively, once can deduce (177) directly via the martingale argument in [KN06, Sec. 5], the only difference being the use of the martingale inequality (65) in place of Pisier’s inequality [Pis75]. □

Proof of Lemma 1.12. Since for q ∈ [2, ∞) we have S_{2}(ℓ_{q}) ⩽ \sqrt{q − 1}, Lemma 1.12 is a special case of Lemma 6.8 with Y = ℓ_{q}, n = 2^{m} and x_{1}, …, x_{2^{m}} being an arbitrary enumeration of 𝔽_{2}^{m} ⊆ Y. □

Remark 6.9. As promised in the Introduction, here we justify (29). The fact that Av_{ℝ}(𝔽_{2}^{n}, ∥ · ∥_{2}) ≲ \sqrt[4]{n} is simple: consider the mapping ϕ : 𝔽_{2}^{n} → ℝ given by ϕ(x) = \sqrt{max\{∥x∥_{1} − n/2, 0\}}. Then ϕ is 1-Lipschitz with respect to the metric induced on 𝔽_{2}^{n} by the Euclidean norm ∥ · ∥_{2}. By the central limit theorem the average of |ϕ(x) − ϕ(y)|^{2} over (x, y) ∈ 𝔽_{2}^{n} × 𝔽_{2}^{n} is of order \sqrt{n}.

The corresponding lower bound Av_{ℝ}(𝔽_{2}^{n}, ∥ · ∥_{2}) ≳ \sqrt[4]{n} is an example of a lower bound on the average distortion of the cube 𝔽_{2}^{n} that is not proved through the use on nonlinear type. Suppose that f : 𝔽_{2}^{n} → ℝ satisfies |f(x)−f(y)| ⩽ ∥x−y∥_{2} for every x, y ∈ 𝔽_{2}^{n}. Suppose also that S ⊆ 𝔽_{2}^{n} satisfies |S| ⩾ 2^{n−1}. Then by Harper’s inequality [Har66] (see also [Led01, Thm. 2.11]), for every t ∈ (0, ∞) we have

\frac{|\{x ∈ 𝔽_{2}^{n} : ∀ y ∈ S, ∥x − y∥_{2} ⩾ t\}|}{2^{n}}

= \frac{|\{x ∈ 𝔽_{2}^{n} : ∀ y ∈ S, ∥x − y∥_{1} ⩾ t^{2}\}|}{2^{n}} ⩽ e^{−2t^{4}/n}.

Consequently, if M_{f} ∈ ℝ is a median of f then by [Led01, Prop.1.3] we have |{x ∈ 𝔽_{2}^{n} : |f(x) − M_{f}| ⩾ t}| /2^{n} ⩽ 2e^{−2t^{4}/n}. Hence,

(\frac{1}{4^{n}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} |f(x) − f(y)|^{2})^{\frac{1}{2}} ⩽ 2 (\frac{1}{2^{n}} ∑_{(x,y)∈𝔽_{2}^{n}×𝔽_{2}^{n}} |f(x) − M_{f}|^{2})^{\frac{1}{2}}

⩽ (∫_{0}^{∞} 4te^{−2t^{4}/n}dt)^{\frac{1}{2}} ≲ \sqrt[4]{n}.

Remark 6.10. Additional obstructions to average distortion embeddings that do not fall into the framework described in this section have been obtained in the context of integrality gap lower bounds for the Goemans–Linial semidefinite relaxation for the Uniform Sparsest Cut Problem. The best known result in this direction is due to [KM13] (improving over the works [DKSV06, KR09]), where it is shown that for arbitrarily large n ∈ ℕ there exists an n-point metric space (X, d_{X}) such that the metric space (X, \sqrt{d_{X}}) emebds isometrically into ℓ_{2}, yet Av_{ℓ_{1}}^{(1)}(X) ⩾ exp (c\sqrt{log log n}), where c ∈ (0, ∞) is a universal constant. Finding the correct asymptotic dependence here remains open.

7. Existence of average distortion embeddings

The main purpose of this section is to state criteria for the existence of average distortion embeddings. In what follows we often discuss probability distributions over random subsets or random partitions of metric spaces. To avoid measurability issues we focus our discussion on finite metric spaces. Such topics can be treated for infinite spaces as well, as done in [LN05].

7.1. Random zero sets. Fix Δ, ζ ∈ (0, ∞) and δ ∈ (0, 1). Following [ALN08], a finite metric space (X, d_{X}) is said to admit a random zero set at scale Δ which is ζ-spreading with probability δ if there exists a probability distribution μ over 2^{X} such that every x, y ∈ X satisfy

d_{X}(x, y) ⩾ Δ ⟹ μ (\{Z ∈ 2^{X} : x ∈ Z ∧ d_{X}(y, Z) ⩾ \frac{Δ}{ζ}\}) ⩾ δ.

(178)

We denote by ζ(X; δ) the infimum over those ζ ∈ (0, ∞) such that for every scale Δ ∈ (0, ∞) the finite metric space (X, d_{X}) admits a random zero set at scale Δ which is ζ-spreading with probability δ. If (X, d_{X}) is an infinite metric space then we write

ζ(X; δ) =^{def} sup_{\begin{matrix}S⊆X \\ |S|<∞ \end{matrix}} ζ(X; δ).  (179)

The following proposition asserts that random zero sets can be used to obtain embeddings into the real line ℝ with low average distortion.

Proposition 7.1. Fix n ∈ ℕ and δ ∈ (0, 1). Suppose that (X, d_{X}) is a metric space with ζ(X; δ) < ∞. Then for every p ∈ [1, ∞) and every x_{1}, …, x_{n} ∈ X there exists a 1-Lipschitz function f : X → ℝ such that

∑_{i=1}^{n} ∑_{j=1}^{n} |f(x_{i}) − f(x_{j})|^{p} ⩾ \frac{δ}{2^{11p}ζ(X; δ)^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.

Thus, using the notation of Section 1.3, Av_{ℝ}^{(p)}(X) ≲ ζ(X; δ)/δ^{1/p}.

Proposition 7.1 will be proven in Section 7.4 below. We will now explain how Proposition 7.1 can be applied to a variety of metric spaces. Due to the discussion preceding Theorem 1.3, such spaces will satisfy the spectral inequality (7) with Ψ linear.

7.1.1. Random partitions. Many spaces are known to admit good random zero sets. Such examples often (though not always) arise from metric spaces for which one can construct random padded partitions. If (X, d_{X}) is a finite metric space let 𝒫(X) denote the set of all partitions of X. For P ∈ 𝒫(X) and x ∈ X, the unique element of P to which x belongs is denoted P (x) ⊆ X. Given ε, δ ∈ (0, 1), the metric space (X, d_{X}) is said to admit an ε-padded random partition with probability δ if for every Δ ∈ (0, ∞) there exists a probability distribution μ_{Δ} over partitions of X with the following properties.

• ∀ P ∈ 𝒫(X), μ_{Δ}(P) > 0 ⟹ max_{x∈X} diam P (x) ⩽ Δ.

• For every x ∈ X we have

μ_{Δ} ({P ∈ 𝒫(X) : B_{X}(x, εΔ) ⊆ P (x)} ) ⩾ δ,

where B_{X}(x, r) =^{def} {y ∈ X : d_{X}(x, y) ⩽ r} for every r ∈ [0, ∞).

Let ε(X; δ) denote the supremum over those ε ∈ (0, 1) for which (X, d_{X}) admits an ε-padded random partition with probability δ. As in (179), we extend this definition to infinite metric spaces (X, d_{X}) by setting

ε(X; δ) =^{def} inf_{\begin{matrix}S⊆X \\ |S|<∞ \end{matrix}} ε(X; δ).

Fact 3.4 in [ALN08] (which itself uses an idea of [Rao99]) asserts that for every δ ∈ (0, 1), if (X, d_{X}) is a finite metric space then

ε(X; δ) · ζ (X; \frac{δ}{4}) ⩽ 1.  (180)

([ALN08, Fact 3.4] states this for the arbitrary choice δ = \frac{1}{2}, but its proof does not use this specific value of δ in any way.) One should interpret (180) as asserting that a lower bound on ε(X; δ) implies an upper bound on ζ(X, δ/4). The following classes of metric spaces (X, d_{X}) are known to satisfy ε(X; δ) > 0 for some δ ∈ (0, 1): doubling metric spaces, compact Riemannian surfaces, Gromov hyperbolic spaces of bounded local geometry, Euclidean buildings, symmetric spaces, homogeneous Hadamard manifolds, and forbidden-minor (edge-weighted) graph families. The case of doubling spaces goes back to [Ass83], with subsequent improved bounds on ε(X; δ) > 0 obtained in [GKL03]. The case of forbidden-minor graph families is due to [KPR93], with subsequent improved bounds on ε(X; δ) > 0 obtained in [FT03]. The case of compact Riemannian surfaces is due to [LN05], with subsequent improved bounds on ε(X; δ) > 0 obtained in [LS10]. The remaining cases follow from the general fact [NS11] that if (X, d_{X}) has bounded Nagata dimension then ε(X; δ) > 0 for some δ ∈ (0, 1) (see [LS05] for more information on Nagata dimension of metric spaces). We single out the following two consequences of Proposition 7.1 and (the easy direction of) Theorem 1.3, with explicit quantitative bounds arising from the estimates on ε(X; δ) obtained in [GKL03, LS10].

Corollary 7.2. Suppose that (X, d_{X}) is a metric space that is doubling with constant K ∈ [2, ∞). Then for every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{2}) ≲ \frac{(log K)^{2}}{1 − λ_{2}(A)}.

Corollary 7.3. Suppose that (X, d_{X}) is a two dimensional Riemannian manifold of genus g ∈ ℕ ∪ {0}. Then for every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{2}) ≲ \frac{(log(g + 1))^{2}}{1 − λ_{2}(A)} .

The fact that the conclusion of Proposition 7.1 holds true under the assumption that ε(X; δ) > 0 for every δ ∈ (0, ∞) (as follows by combining Proposition 7.1 with (180)) was proved by Rabinovich in [Rab08] in the case p = 1. It has long been well known to experts (and stated explicitly in [BLR10]), that the original proof of Rabinovich extends mutatis mutandis to every p ∈ [1, ∞). The (simple) proof of Proposition 7.1 below builds on the ideas of Rabinovich in [Rab08].

An example of a class of metric spaces that admits good random zero sets for reasons other than the existence of random padded partitions is the class of spaces that admit a quasisymmetric embedding into Hilbert space. We refer to [Hei01] and the references therein for more information on quasisymmetric embeddings; it suffices to say here that L_{1}(μ) spaces provide such examples (see [DL97, Ch. 6]). It follows from [ALN08] (using in part ideas of [ARV09, NRS05, Lee05, CGR08]) that if (X, d_{X}) is a metric space that admits a quasisymmetric embedding into Hilbert space then there exist ε, δ ∈ (0, 1) (depending only on the modulus of quasisymmetry of the implicit embedding) such that for every n ∈ ℕ, any n-point subset S ⊆ X satisfies ε(S; δ) ⩾ ε/\sqrt{log n}. Consequently we have the following statement.

Corollary 7.4. Suppose that (X, d_{X}) is a metric space that admits a quasisymmetric embedding into a Hilbert space. Then there exists a constant C ∈ (0, ∞) (depending only on the modulus of quasisymmetry of the implicit embedding) such that for every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ(A, d_{X}^{2}) ⩽ \frac{C log n}{1 − λ_{2}(A)}.  (181)

Note that Bourgain’s embedding theorem [Bou85] implies that (181) holds true for every metric space (X, d_{X}) if one replaces the term log n by (log n)^{2} (in which case C can be taken to be a universal constant).

7.2. Localized weakly bi-Lipschitz embeddings. Following the terminology of [NPSS06], for D ∈ [1, ∞) say that a metric space (X, d_{X}) admits a weakly bi-Lipschitz embedding with distortion D into a metric space (Y, d_{Y}) if for every Δ ∈ (0, ∞) there exists a nonconstant Lipschitz mapping f_{Δ} : X → Y such that for every x, y ∈ X,

d_{X}(x, y) ⩾ Δ ⟹ d_{Y} (f_{Δ}(x), f_{Δ}(y)) ⩾ \frac{∥f_{Δ}∥_{Lip}}{D} Δ.  (182)

The origin of this terminology is that such embeddings preserve (by design) weak (p, q) metric Poincaré inequalities. Specifically, a standard way by which one rules out the existence of bi-Lipschitz embeddings is via generalized Poincaré-type inequalities as follows. Suppose that n ∈ ℕ and p, q, K ∈ (0, ∞), and there exist two measures μ, ν on {1, …, n}^{2} such that every y_{1}, …, y_{n} ∈ Y satisfy

(∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (y_{i}, y_{j})^{p}μ(i, j))^{\frac{1}{p}} ⩽ (∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (y_{i}, y_{j})^{q}ν(i, j))^{\frac{1}{q}} . (183)

Clearly if f : X → Y is a bi-Lipschitz embedding then the inequality (183) holds for (X, d_{X}) as well, with the right hand side of (183) multiplied by ∥f∥_{Lip}∥f^{−1}∥_{Lip}. Thus a strong (p, q) inequality such as (183) are bi-Lipschitz invariants that can be used to show that certain spaces (X, d_{X}) must incur large distortion in any bi-Lipschitz embedding into (Y, d_{Y}). The obvious weak (p, q) variant of (183) is the assertion that for every u ∈ (0, ∞) and every y_{1}, …, y_{n} ∈ Y we have

μ (\{(i, j) ∈ \{1, …, n\}^{2} : d_{Y} (y_{i}, y_{j}) ⩾ u\})^{\frac{1}{p}}

⩽ \frac{1}{u} (∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (y_{i}, y_{j})^{q}ν(i, j))^{\frac{1}{q}} . (184)

By definition, if a metric space (X, d_{X}) admits a weakly bi-Lipschitz embedding with distortion D into a metric space (Y, d_{Y}) satisfying (184) then for every n ∈ ℕ, any x_{1}, …, x_{n} ∈ X satisfy

μ (\{(i, j) ∈ \{1, …, n\}^{2} : d_{X}(x_{i}, x_{j}) ⩾ u\})^{\frac{1}{p}}

⩽ \frac{D}{u} (∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{q}ν(i, j))^{\frac{1}{q}} .

We will see below that one can prove nonlinear spectral gap inequality such as (6) with Ψ linear by showing that (X, d_{X}) admits a weakly bi-Lipschitz embedding into (Y, d_{Y}). To this end it suffices to localize the condition (182) to balls of proportional scale, as follows. For D ∈ [1, ∞) say that a metric space (X, d_{X}) admits a localized weakly bi-Lipschitz embedding with distortion D into a metric space (Y, d_{Y}) if for every z ∈ X and Δ ∈ (0, ∞) there exists a non-constant Lipschitz mapping f_{Δ}^{z} : X → Y such that for every x, y ∈ B_{X}(z, 32Δ) we have

d_{X}(x, y) ⩾ Δ ⟹ d_{Y} (f_{Δ}^{z}(x), f_{Δ}^{z}(y)) ⩾ \frac{∥f_{Δ}^{z}∥_{Lip}}{D} Δ.  (185)

The factor 32 here was chosen to be convenient for the ensuing arguments, but it is otherwise arbitrary.

Proposition 7.5. Fix n ∈ ℕ and p, D ∈ [1, ∞). Suppose that (X, d_{X}) is a metric space that admits a localized weakly bi-Lipschitz embedding with distortion D into a metric space (Y, d_{Y}). Then for every x_{1}, …, x_{n} ∈ X there is a nonconstant mapping f : {x_{1}, …, x_{n}} → Z, for at least one of the spaces Z ∈ {Y, ℝ}, such that

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{Z}(f(x_{i}), f(x_{j}))^{p})^{\frac{1}{p}} ≳ \frac{∥f∥_{Lip}}{D} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} .

Observe that if (Y, d_{Y}) contains an isometric copy of an interval [a, b] ⊆ ℝ (in particular if Y is a Banach space) then the conclusion of Proposition 7.5 can be taken to be Av_{Y}^{(p)}(X) ≲ D.

Lemma 3.5 in [ALN08] asserts that for every δ ∈ (0, 1), every finite metric space (X, d_{X}) admits a weakly bi-Lipschitz embedding into ℓ_{2} with distortion ζ(X; δ)/\sqrt{δ}. Consequently, all the examples that arise from random padded partitions as described in Section 7.1.1 fall into the framework of Proposition 7.5, with the only difference being that an application of Proposition 7.5 rather than Proposition 7.1 yields an embedding into Hilbert space rather than into the real line. This difference is discussed further in Section 7.3 below. The following lemma shows that Proposition 7.5 has wider applicability than Proposition 7.1: in combination with Proposition 7.5 it yields a different proof of the case p ∈ (2, ∞) of (22) that avoids the use of Theorem 1.3.

Lemma 7.6. Suppose that (X, ∥·∥_{X}) and (Y, ∥·∥_{Y}) are Banach spaces that satisfy the assumptions of Theorem 1.10. Suppose furthermore that there exists K ∈ (0, ∞) such that β(t) = Kt for all t ∈ [0, ∞). Then (X, ∥ · ∥_{X}) admits a localized weakly bi-Lipschitz embedding with distortion 2K/α(1/32) into (Y, ∥ · ∥_{Y}).

Proof. Fix Δ ∈ (0, ∞) and a mapping f : B_{X} → Y that satisfies (19). For z ∈ X define f_{Δ}^{z} : X → Y by

f_{Δ}^{z}(x) =^{def} 32Δf (ρ (\frac{x − z}{32Δ} )) ,

where ρ is given as in (107). Since ρ is 2-Lipschitz, ∥f_{Δ}^{z}∥_{Lip} ⩽ 2K. If x, y ∈ z + 32ΔB_{X} satisfy ∥x − y∥_{X} ⩾ Δ then

∥f_{Δ}^{z}(x) − f_{Δ}^{z}(y)∥_{Y} ⩾ Δα (\frac{∥x − y∥_{X}}{32Δ} ) ⩾ \frac{α (\frac{1}{32}) ∥f_{Δ}^{z}∥_{Lip}}{2K} Δ. □

For p ∈ [1, 2), due to Lemma 1.12 and Proposition 7.5, ℓ_{p} does not admit a localized weakly bi-Lipschitz embedding into Hilbert space (this can also be proved directly via a shorter argument). Since finite subsets of ℓ_{p} embed isometrically into ℓ_{1} (see e.g. [DL97]), it follows from [ARV09] that every n-point subset of ℓ_{p} admits a weakly bi-Lipschitz embedding into ℓ_{2} with distortion O(\sqrt{log n}). By [Lee05], it is also true that every n-point subset of ℓ_{p} admits a weakly bi-Lipschitz embedding into ℓ_{2} with distortion O((log n)^{(2−p)/p^{2}}), which is better than the O(\sqrt{log n}) bound of [ARV09] if \sqrt{5} − 1 < p ⩽ 2. Therefore for every n ∈ ℕ and every n by n symmetric stochastic matrix A,

p ∈ [1, \sqrt{5} − 1] ⟹ γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{log n}{1 − λ_{2}(A)},

and

p ∈ [\sqrt{5} − 1, 2] ⟹ γ(A, ∥ · ∥_{ℓ_{p}}^{2}) ≲ \frac{(log n)^{\frac{2(2−p)}{p^{2}}}}{1 − λ_{2}(A)} .

These are the currently best known bounds towards Question 1.8.

7.3. Dimension reduction. As discussed in Section 7.2, Proposition 7.1 yields an average distortion embedding into the real line, while Proposition 7.5, when applied in the context of spaces with random zero sets, yields an average distortion embedding into Hilbert space. Here we briefly compare these two notions. The following lemma is a simple application of the classical Johnson-Lindenstrauss dimension reduction lemma [JL84].

Lemma 7.7. If (X, d_{X}) is an n-point metric space then

\frac{Av_{ℝ}^{(2)}(X)}{\sqrt{log n}} ⩽ Av_{ℓ_{2}}^{(2)}(X) ≲ Av_{ℝ}^{(2)}(X).  (186)

Proof. The rightmost inequality in (186) is trivial. Write D = Av_{ℓ_{2}}^{(2)}(X) and take x_{1}, …, x_{m} ∈ X. By the Johnson-Lindenstrauss lemma [JL84] there exists k ∈ ℕ such that k ≲ log n and there exists a 1-Lipschitz function f = (f_{1}, …, f_{k}) : {x_{1}, …, x_{m}} → ℝ^{k} such that

∑_{i=1}^{m} ∑_{j=1}^{m} ∥f(x_{i}) − f(x_{j})∥_{2}^{2} ⩾ \frac{1}{2D^{2}} ∑_{i=1}^{m} ∑_{j=1}^{m} d_{X}(x_{i}, x_{j})^{2}.

Therefore there exists s ∈ {1, …, k} such that

∑_{i=1}^{m} ∑_{j=1}^{m} |f_{s}(x_{i}) − f_{s}(x_{j})|^{2} ⩾ \frac{1}{2kD^{2}} ∑_{i=1}^{m} ∑_{j=1}^{m} d_{X}(x_{i}, x_{j})^{2}.

Since f_{s} : {x_{1}, …, x_{m}} → ℝ is also 1-Lipschitz, we conclude that Av_{ℝ}^{(2)}(X) ⩽ \sqrt{2k}D ≲ \sqrt{log n}D. □

The following lemma shows that Lemma 7.7 is almost asymptotically sharp. Lemma 7.8. For arbitrarily large n ∈ ℕ there exists an n-point metric space X_{n} such that

Av_{ℝ}^{(2)}(X_{n}) ≳ Av_{ℓ_{2}}^{(2)}(X_{n}) · \sqrt{\frac{log n}{log log n}}.  (187)

Proof. Fix ε ∈ (0, 1) and an integer m ⩾ 2. Let σ denote the normalized surface measure on the unit sphere S^{m−1} ⊆ ℓ_{2}^{m}. By Lemma 21 in [FS02] there exists a partition {C_{1}, …, C_{n}} of S^{m−1} into nonempty measurable sets such that σ(C_{i}) = 1/n and diam(C_{i}) ⩽ ε for all i ∈ {1, …, n}, and n ⩽ (κ/ε)^{m} for some universal constant κ ∈ (0, ∞).

Choose an arbitrary point x_{i} ∈ C_{i} and set X_{n} = {x_{1}, …, x_{n}} ⊆ ℓ_{2}^{m−1}. Since X_{n} is isometric to a subset of Hilbert space, Av_{ℓ_{2}}^{(2)}(X_{n}) = 1. Suppose that f : {x_{1}, …, x_{n}} → ℝ is a 1-Lipschitz function. By the nonlinear Hahn-Banach theorem (see [BL00]) we can think of f as the restriction to X_{n} of a 1-Lipschitz function defined on all of S^{m−1}. The Poincaré inequality on the sphere S^{m−1} (see e.g. [Cha84, Led01]) asserts that

∫_{S^{m−1}} ∫_{S^{m−1}} |f(x) − f(y)|^{2}dσ(x)dσ(y)

⩽ \frac{2}{m − 1} ∫_{S^{m−1}} ∥∇f(x)∥_{2}^{2} dσ(x) ⩽ \frac{4}{m}. (188)

For every i, j ∈ {1, …, n} and every (x, y) ∈ C_{i} × C_{j} we have

\frac{|f(x_{i}) − f(x_{j})|^{2}}{3} ⩽ |f(x_{i}) − f(x)|^{2} + |f(x) − f(y)|^{2} + |f(y) − f(x_{j})|^{2}
⩽ |f(x) − f(y)|^{2} + diam(C_{i})^{2} + diam(C_{j})^{2}
⩽ |f(x) − f(y)|^{2} + 2ε^{2},  (189)

and similarly,

∥x − y∥_{2}^{2} ⩽ 3∥x_{i} − x_{j}∥_{2}^{2} + 6ε^{2}.  (190)

Consequently,

\frac{|f(x_{i}) − f(x_{j})|^{2} − 6ε^{2}}{n^{2}} = σ(C_{i})σ(C_{j}) (|f(x_{i}) − f(x_{j})|^{2} − 6ε^{2})

⩽^{(189)} 3 ∫_{C_{i}} ∫_{C_{j}} |f(x) − f(y)|^{2}dσ(x)dσ(y). (191)

and

\frac{∥x_{i} − x_{j}∥_{2}^{2}}{n^{2}} ⩾ \frac{1}{3} ∫_{C_{i}} ∫_{C_{j}} ∥x − y∥_{2}^{2}dσ(x)dσ(y) − \frac{2ε^{2}}{n^{2}} .  (192)

Hence,

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} |f(x_{i}) − f(x_{j})|^{2}

⩽^{(191)} 3 ∫_{S^{m−1}} ∫_{S^{m−1}} |f(x) − f(y)|^{2}dσ(x)dσ(y) + 6ε^{2} ⩽^{(188)} \frac{12}{m} + 6ε^{2},

and

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{2}^{2} ⩾^{(192)} \frac{1}{3} ∫_{S^{m−1}} ∫_{S^{m−1}} ∥x − y∥_{2}^{2}dσ(x)dσ(y) − 2ε^{2}

= \frac{2}{3} − 2ε^{2}.

By choosing ε = 1/(2\sqrt{m}), we have shown that every 1-Lipschitz function f : X_{n} → ℝ satisfies

∑_{i=1}^{n} ∑_{j=1}^{n} |f(x_{i}) − f(x_{j})|^{2} ≲ \frac{1}{m} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{2}^{2}.

Recalling that n ⩽ (κ/ε)^{m} = (2κ\sqrt{m})^{m}, or m ≳ \sqrt{log n/ log log n}, the proof of (187) is complete. □

Remark 7.9. Given an n-point metric space (X, d_{X}) let 𝔖(X) denote the maximum of \frac{1}{2n^{2}} ∑_{(x,y)∈X×X} |f(x)−f(y)|^{2} over all 1-Lipschitz functions f : X → ℝ. The quantity 𝔖(X) was introduced by Alon, Boppana and Spencer in [ABS98], where they called it the spread constant of X. They proved that the spread constant of X governs the asymptotic isoperimetric behavior of ℓ_{1}^{n}(X) as n → ∞. They also state that “The spread constant appears to be new and may well be of independent interest.” We agree with this assertion. In particular, it would be worthwhile to investigate the computational complexity of the problem that takes as input an n-point metric space (X, d_{X}) and is supposed to output in polynomial time a number that is guaranteed to be a good approximation of its spread constant. We are not aware of hardness of approximation results for this question. Let 𝔖_{ℓ_{2}}(X) denote the maximum of \frac{1}{2n^{2}} ∑_{(x,y)∈X×X} ∥f(x) − f(y)∥_{2}^{2} over all 1-Lipschitz functions f : X → ℓ_{2}. The quantity 𝔖_{ℓ_{2}}(X) can be computed in polynomial time with arbitrarily good precision, since (by definition) it can be cast as a semidefinite program (see [GLS93]). The proof of Lemma 7.7 can be viewed as a simple approximation algorithm to the spread constant, achieving an approximation guarantee of O(log n). Lemma 7.8 can be viewed as yielding an almost matching integrality gap lower bound for the semidefinite program. Note that the parameter 𝔖_{ℓ_{2}}(X) itself has also been studied in the literature in the context of the problem of finding the fastest mixing Markov process on a given graph; see [SBXD06]. See also the works [Fie89, GHW08, GHR12] that study this quantity in the context of the absolute algebraic connectivity of a graph. Clearly (Av_{ℝ}^{(2)}(X))^{2} is closely related to 𝔖(X): it amounts to finding the (multi)subset of X with largest spread constant. The same can be said for the relation between (Av_{ℓ_{2}}^{(2)}(X))^{2} and 𝔖_{ℓ_{2}}(X).

7.4. Proofs of Proposition 7.1 and Proposition 7.5. We start by recording the following very simple lemma, whose proof is a straightforward application of the triangle inequality.

Lemma 7.10. Fix p ∈ [1, ∞) and n ∈ ℕ. Let (X, d_{X}) be a metric space and x_{1}, …, x_{n}, ∈ X. Define

r =^{def} min_{i∈\{1,...,n\}} (\frac{1}{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} .  (193)

Then

r ⩽ (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} ⩽ 2r.  (194)

Proof. Choose k ∈ {1, …, n} such that

r = (\frac{1}{n} ∑_{j=1}^{n} d_{X}(x_{k}, x_{j})^{p})^{\frac{1}{p}} .  (195)

The rightmost inequality in (194) follows from averaging the estimate d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p−1}d_{X}(x_{i}, x_{k})^{p} + 2^{p−1}d_{X}(x_{k}, x_{j})^{p} over i, j ∈ {1, …, n}. The leftmost inequality in (194) follows from the definition of r. □

Lemma 7.11. Continuing with the notation of the statement and proof of Lemma 7.10, in particular choosing k ∈ {1, …, n} so as to satisfy (195), write

B =^{def} {i ∈ {1, …, n} : d_{X}(x_{i}, x_{k}) ⩽ 4r} ,  (196)

and

M =^{def} \{(i, j) ∈ B × B : d_{X}(x_{i}, x_{j}) ⩾ \frac{r}{8}\} .  (197)

Then,

|M| ⩽ \frac{n^{2}}{2^{7p}} ⟹ (\frac{1}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{j}, x_{k})^{p})^{\frac{1}{p}} ⩾ \frac{r}{8}.  (198)

Proof. Suppose that

|M| ⩽ \frac{n^{2}}{2^{7p}} .  (199)

Recalling (195) and (196), it follows from Markov’s inequality that

\frac{n − |B|}{n} ⩽ \frac{1}{4^{p}} .  (200)

Hence,

\frac{2}{n^{2}} ∑_{i=1}^{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{i}, x_{j})^{p}

⩽ \frac{2^{p}}{n^{2}} ∑_{i=1}^{n} ∑_{j∈\{1,...,n\}∖B} (d_{X}(x_{i}, x_{k})^{p} + d_{X}(x_{k}, x_{j})^{p})
=^{(195)} \frac{2^{p}(n − |B|)}{n}r^{p} + \frac{2^{p}}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{k}, x_{j})^{p}
⩽^{(200)} \frac{r^{p}}{2^{p}} + \frac{2^{p}}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{k}, x_{j})^{p}.  (201)

Since every i, j ∈ B satisfy d_{X}(x_{i}, x_{j}) ⩽ d_{X}(x_{i}, x_{k}) + d_{X}(x_{j}, x_{k}) ⩽ 8r,

\frac{1}{n^{2}} ∑_{(i,j)∈B×B} d_{X}(x_{i}, x_{j})^{p} ⩽^{(196)∧(197)} \frac{8^{p}r^{p}|M|}{n^{2}} + \frac{|B|^{2} − |M|}{n^{2}} · \frac{r^{p}}{8^{p}}
⩽^{(199)}  \frac{r^{p}}{2^{4p}} + \frac{r^{p}}{2^{3p}} .  (202)

It follows that

r^{p}  ⩽^{(194)}  \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}
⩽^{(201)∧(202)} \frac{r^{p}}{2^{4p}} + \frac{r^{p}}{2^{3p}} + \frac{r^{p}}{2^{p}} + \frac{2^{p}}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{k}, x_{j})^{p},

which (since p ⩾ 1) implies that

\frac{1}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{k}, x_{j})^{p} ⩾ \frac{r^{p}}{8^{p}} .  □

Lemma 7.12. Continuing with the notation of the statements and proofs of Lemma 7.10 and Lemma 7.11, define

∀ i ∈ {1, …, n}, s_{i} =^{def} max {0, d_{X}(x_{i}, x_{k}) − 2r} .

If |M| ⩽ n^{2}/2^{7p} then

∑_{i=1}^{n} ∑_{j=1}^{n} |s_{i} − s_{j}|^{p} ⩾ \frac{1}{2^{5p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{k})^{p}.

Proof. Due to Lemma 7.11 we know that

\frac{1}{n} ∑_{j∈\{1,...,n\}∖B} d_{X}(x_{k}, x_{j})^{p} ⩾ \frac{r^{p}}{8^{p}}  (203)

Define B′ =^{def} {i ∈ {1, …, n} : d_{X}(x_{i}, x_{k}) ⩽ 2r}. If i ∈ B′ then s_{i} = 0,

and if j ∈ \{1, …, n\} ∖ B then s_{j} = d_{X}(x_{j}, x_{k}) − 2r ⩾ \frac{1}{2}d_{X}(x_{j}, x_{k}). Also, recalling (195), it follows from Markov’s inequality that

\frac{n − |B′|}{n} ⩽ \frac{1}{2^{p}} .  (204)

Consequently,

∑_{i=1}^{n} ∑_{j=1}^{n} |s_{i} − s_{j}|^{p} ⩾ 2|B′| ∑_{j∈\{1,...,n\}∖B} \frac{d_{X}(x_{j}, x_{k})^{p}}{2^{p}}

⩾^{(203)∧(204)} \frac{n (1 − \frac{1}{2^{p}} )}{2^{p−1}} · \frac{nr^{p}}{8^{p}} ⩾^{(194)} \frac{1}{2^{5p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.  □

Proof of Proposition 7.1. Fix n ∈ ℕ. Suppose that x_{1}, …, x_{n} ∈ X and write S = {x_{1}, …, x_{n}} ⊆ X. Define r ∈ (0, ∞) as in (193) and let μ be a probability distribution over 2^{X} that satisfies (178) with Δ = r/8 and ζ = ζ(S; δ). Let M be defined as in (197) and suppose that |M| > n^{2}/2^{7p}. Then

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∫_{2^{X}} |d_{X}(x_{i}, Z) − d_{X}(x_{j}, Z)|^{p} dμ(Z)

⩾ \frac{1}{n^{2}} ∑_{(i,j)∈M} (\frac{r}{8ζ} )^{p} μ (\{Z ∈ 2^{X} : x_{i} ∈ Z ∧ d_{X}(x_{j}, Z) ⩾ \frac{r}{8ζ} \})

⩾ \frac{|M|}{n^{2}} · \frac{δr^{p}}{8^{p}ζ^{p}}  (205)
⩾ \frac{δ}{2^{11p}ζ^{p}} · \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p},  (206)

where (205) uses (178) and (197), and (206) uses (194) and the assumption |M| > n^{2}/2^{7p}. It follows that there exists Z ⊆ X such that the 1-Lipschitz function f : X → ℝ given by f(x) = d_{X}(x, Z) satisfies

∑_{i=1}^{n} ∑_{j=1}^{n} |f(x_{i}) − f(x_{j})|^{p} ⩾ \frac{δ}{2^{11p}ζ^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.

If, on the hand, |M| ⩽ n^{2}/2^{7p} then the desired estimate follows by choosing f(x) = max{0, d_{X}(x, x_{k})−2r} and applying Lemma 7.12. □

Proof of Proposition 7.5. Fix n ∈ ℕ and choose x_{1}, …, x_{n} ∈ X. Define r ∈ (0, ∞) as in (193) and k ∈ {1, …, n} as in (195). Let M be defined as in (197) and suppose that |M| > n^{2}/2^{7p}. An application of (185) with Δ = r/8 and z = x_{k} shows that

∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f_{Δ}^{x_{k}}(x_{i}), f_{Δ}^{x_{k}}(x_{j}))^{p} ⩾ ∑_{(i,j)∈M} d_{Y} (f_{Δ}^{x_{k}}(x_{i}), f_{Δ}^{x_{k}}(x_{j}))^{p}

⩾ |M|\frac{∥f∥_{Lip}^{p}}{D^{p}} · \frac{r^{p}}{8^{p}} ⩾ \frac{n^{2}r^{p}∥f∥_{Lip}^{p}}{2^{10p}D^{p}} ⩾ \frac{∥f∥_{Lip}^{p}}{2^{11p}D^{p}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}.

This yields the desired average distortion embedding into Y. If, on the hand, |M| ⩽ n^{2}/2^{7p} then the existence of the desired embedding into ℝ follows by choosing f(x) = max{0, d_{X}(x, x_{k})−2r} and applying Lemma 7.12. □

It is natural to ask how the quantities Av_{Y}^{(p)}(X) and Av_{Y}^{(q)}(X) are related to each other for distinct p, q ∈ [1, ∞) and two metric space (X, d_{X}) and (Y, d_{Y}). We shall now briefly address this matter.

Suppose that D > Av_{Y}^{(q)}(X) and fix x_{1}, …, x_{n} ∈ X. Then there exists a nonconstant mapping f : {x_{1}, …, x_{n}} → Y such that

∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f(x_{i}), f(x_{j}))^{q} ⩾ \frac{∥f∥_{Lip}^{q}}{D^{q}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{q}.  (207)

Suppose first that q < p, and continue using the notation of Lemma 7.10 and Lemma 7.11. If |M| > n^{2}/2^{7p} then

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{q})^{\frac{1}{q}} ⩾ (\frac{1}{n^{2}} ∑_{(i,j)∈M} d_{X}(x_{i}, x_{j})^{q})^{\frac{1}{q}}

⩾^{(197)} (\frac{1}{2^{7p}} · \frac{r^{q}}{8^{q}} )^{\frac{1}{q}} ≳^{(194)} \frac{1}{2^{7p/q}} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} . (208)

Consequently,

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f(x_{i}), f(x_{j}))^{p})^{\frac{1}{p}} ⩾ (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (f(x_{i}), f(x_{j}))^{q})^{\frac{1}{q}}

≳^{(207)∧(208)} \frac{∥f∥_{Lip}}{2^{7p/q}D} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} . (209)

By using Lemma 7.12 if |M| ⩽ n^{2}/2^{7p}, we deduce from (209) that

q < p ⟹ Av_{Y ×ℝ}^{(p)}(X) ≲ 2^{7p/q}Av_{Y}^{(q)}(X),  (210)

where Y ×ℝ is understood to be equipped with, say, the ℓ_{1}-sum metric, i.e., d_{Y ×ℝ}((x, s), (y, t)) = d(x, y) + |s − t| for every (x, s), (y, t) ∈ Y × ℝ (as in Proposition 7.5, we can conclude here that there exists an average distortion embedding into either Y or ℝ, but we choose to work with Y × ℝ for notational simplicity).

If p < q then the following argument establishes an estimate analogous to (210), but under an additional assumption. The Lipschitz extension constant for the pair of metric spaces (X, Y), denoted e(X, Y), is the infimum over those K ∈ [1, ∞) such that for every S ⊆ X every Lipschitz function f : S → Y admits an extension F : X → Y with ∥F ∥_{Lip} ⩽ K∥f∥_{Lip}. If no such K exists then set e(X, Y) = ∞. Suppose that p < q and that |M| > n^{2}/2^{7p}. By the definition of D there exists a nonconstant mapping ϕ : B → Y such that

∑_{(i,j)∈B×B} d_{Y} (ϕ(x_{i}), ϕ(x_{j}))^{q} ⩾ \frac{∥ϕ∥_{Lip}^{q}}{D^{q}} ∑_{(i,j)∈B×B} d_{X}(x_{i}, x_{j})^{q}.  (211)

Note that since for every i, j ∈ B we have d_{X}(x_{i}, x_{j}) ⩽ 8r,

∑_{(i,j)∈B×B} d_{Y} (ϕ(x_{i}), ϕ(x_{j}))^{q}

⩽ (8r∥ϕ∥_{Lip})^{q−p} ∑_{(i,j)∈B×B} d_{Y} (ϕ(x_{i}), ϕ(x_{j}))^{p}. (212)

Also, arguing as in (208) we have

\frac{1}{n^{2}} ∑_{(i,j)∈B×B} d_{X}(x_{i}, x_{j})^{q} ≳ (cr)^{q},  (213)

where c ∈ (0, ∞) is a universal constant. By substituting (212) and (213) into (211) we therefore have

(\frac{1}{n^{2}} ∑_{(i,j)∈B×B} d_{Y} (ϕ(x_{i}), ϕ(x_{j}))^{p})^{\frac{1}{p}} ⩾ \frac{(c/8)^{q/p}∥ϕ∥_{Lip}r}{D^{q/p}}

⩾^{(194)} \frac{(c/8)^{q/p}∥ϕ∥_{Lip}}{D^{q/p}} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} . (214)

By extending ϕ to a mapping Φ : X → Y with ∥Φ∥_{Lip} ≲ e(X, Y)∥ϕ∥_{Lip} we see that

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{Y} (Φ(x_{i}), Φ(x_{j}))^{p})^{\frac{1}{p}} ⩾ (\frac{1}{n^{2}} ∑_{(i,j)∈B×B} d_{Y} (ϕ(x_{i}), ϕ(x_{j}))^{p})^{\frac{1}{p}}

⩾^{(214)} \frac{∥Φ∥_{Lip}}{(CD)^{q/p}e(X, Y)} (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p})^{\frac{1}{p}} ,  (215)

where C ∈ (0, ∞) is a universal constant. By using Lemma 7.12 if |M| ⩽ n^{2}/2^{7p}, we deduce from (215) that

p < q ⟹ Av_{Y ×ℝ}^{(p)}(X) ≲ e(X, Y) (CAv_{Y}^{(q)}(X))^{q/p} .  (216)

By [Bal92, NPSS06] for p ∈ [2, ∞) we have e(ℓ_{p}, ℓ_{2}) ≲ \sqrt{p}. It therefore follows from (210) and (216) combined with Corollary 1.6 that for every p ∈ [2, ∞) and q ∈ [1, ∞) we have

Av_{ℓ_{2}}^{(q)}(ℓ_{p}) ≲ \{ \begin{matrix}2^{4q}p & if q ⩾ 2, \\ p^{\frac{2}{q} + \frac{1}{2}} & if q < 2. \end{matrix}  (217)

It seems unlikely that (217) is sharp.

Appendix: a refinement of Markov type

Below is an application of Theorem 1.5 that I found in collaboration with Yuval Peres. I thank him for agreeing to include it here.

Fix n ∈ ℕ and an n by n symmetric stochastic matrix A = (a_{ij}). Then for every m ∈ ℕ and x_{1}, …, x_{n} ∈ ℝ we have

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}(x_{i} − x_{j})^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}(x_{i} − x_{j})^{2}} ⩽ ∑_{t=0}^{m−1} λ_{2}(A)^{t}.  (218)

(218) becomes evident when one expresses the vector (x_{1}, …, x_{n}) ∈ ℝ^{n} in an orthonormal eigenbasis of A, showing also that the multiplicative factor 1 + λ_{2}(A) + … + λ_{2}(A)^{m−1} is sharp. By using the estimate |λ_{2}(A)| ⩽ 1, it follows from (218) that Hilbert space has Markov type 2 with M_{2}(ℓ_{2}) = 1; this was Ball’s original proof of this fact in [Bal92].

Suppose that p ∈ (2, ∞). In [NPSS06] it was shown that ℓ_{p} has Markov type 2, and in fact that M_{2}(ℓ_{p}) ≲ \sqrt{p}. This is the same as asserting the following inequality, which holds true for every n by n symmetric stochastic matrix A = (a_{ij}) and every x_{1}, …, x_{n} ∈ ℓ_{p}.

∀ m ∈ ℕ,  \frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}} ≲ pm.  (219)

It is natural to ask whether or not one can refine inequality (219) in the spirit of (218) so as to yield an estimate in terms of λ_{2}(A) that becomes (219) if one uses the a priori bound |λ_{2}(A)| ⩽ 1. Below we will show how a combination of [NPSS06] and Theorem 1.5 yields the following estimate, thus answering this question positively.

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}} ≲ p ∑_{t=0}^{m−1} (1 − \frac{2}{p} (1 − λ_{2}(A)))^{t} . (220)

To explain the similarity of (220) to (218), note that if m ⩾ p/2 then (220) has the following equivalent form.

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}} ≲ p^{2} ∑_{t=1}^{⌈2m/p⌉} λ_{2}(A)^{t}.  (221)

Also, if λ_{2}(A) is positive and bounded away from 0, say, if λ_{2}(A) ⩾ 1/2, then inequality (220) has the following equivalent form.

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥_{ℓ_{p}}^{2}} ≲ p ∑_{t=0}^{m−1} λ_{2}(A)^{2t/p}.  (222)

The proof of Lemma 7.13 below is a simple variant of an unpublished argument of Mark Braverman (2009), who proved the same statement for p = 1; see Exercise 13.10 in [LP13]. The factor 2^{p} in inequality (223) below is asymptotically sharp as n → ∞: this follows mutatis mutandis from an unpublished argument of Oded Schramm (2007), who proved the same statement when p = 1; see Exercise 13.10 in [LP13].

Lemma 7.13. Fix p ∈ [1, ∞) and a metric space (X, d_{X}). Fix also n ∈ ℕ and an n by n symmetric stochastic matrix A = (a_{ij}). Then for every s, t ∈ ℕ with t ⩾ s and every x_{1}, …, x_{n} ∈ X we have

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

and

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{2s+1})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ 3^{p} ∑_{i=1}^{n} ∑_{j=1}^{n}(A^{t})_{ij}d_{X}(x_{i}, x_{j})^{p}. (224)

Proof. We have d_{X}(x_{i}, x_{j})^{p} ⩽ 2^{p−1}d_{X}(x_{i}, x_{k})^{p} + 2^{p−1}d_{X}(x_{j}, x_{k})^{p} for every i, j, k ∈ {1, …, n}. For every ℓ ∈ {1, …, n} multiply this inequality by (A^{s})_{iℓ}(A^{s})_{jℓ}(A^{t−s})_{kℓ} and sum the resulting inequality over i, j, k, ℓ ∈ {1, …, n}, thus obtaining the following estimate.

∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(A^{s})_{iℓ}(A^{s})_{jℓ}(A^{t−s})_{kℓ}d_{X}(x_{i}, x_{j})^{p}

⩽ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(A^{s})_{iℓ}(A^{s})_{jℓ}(A^{t−s})_{kℓ}d_{X}(x_{i}, x_{k})^{p}

+ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(A^{s})_{iℓ}(A^{s})_{jℓ}(A^{t−s})_{kℓ}d_{X}(x_{j}, x_{k})^{p}.  (225)

Since A is symmetric and stochastic, (225) is the same as (223).

To deduce (224), observe that the convexity of u ↦ |u|^{p} implies that for every i, j, k ∈ {1, …, n} we have

d_{X}(x_{i}, x_{j})^{p} ⩽ (\frac{3}{2})^{p−1} d_{X}(x_{i}, x_{k})^{p} + 3^{p−1}d_{X}(x_{j}, x_{k})^{p}.  (226)

(224) now follows by multiplying (226) by (A^{2s})_{ik}a_{kj}, summing the resulting inequality over i, j, k ∈ {1, …, n}, and using (223). □

Corollary 7.14. Fix p ∈ [1, ∞) and m, n ∈ ℕ. Suppose that A = (a_{ij}) is an n by n symmetric stochastic matrix. Then for every metric space (X, d_{X}) and every x_{1}, …, x_{n} ∈ X we have

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ 3^{p}γ(A, d_{X}^{p}) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}.

Proof. We may assume without loss of generality that γ(A, d_{X}^{p}) < ∞, i.e., that A is ergodic. In this case we have lim_{t→∞}(A^{t})_{ij} = 1/n for every i, j ∈ {1, …, n}. Therefore by Lemma 7.13 (with t → ∞),

∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{p} ⩽ \frac{3^{p}}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{X}(x_{i}, x_{j})^{p}

⩽^{(3)} 3^{p}γ(A, d_{X}^{p}) ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}. □

The following corollary is an immediate consequence of Corollary 7.14 and the definition of the Markov type p constant M_{p}(X; m).

Corollary 7.15. Fix p ∈ [1, ∞) and let (X, d_{X}) be a metric space with Markov type p, i.e., M_{p}(X) < ∞. Then for every m, n ∈ ℕ, every n by n symmetric stochastic matrix A = (a_{ij}) and every x_{1}, …, x_{n} ∈ X,

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{p}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{p}} ⩽ min \{M_{p}(X; m)^{p}m, 3^{p}γ(A, d_{X}^{p})\}.

Assume from now on that n ⩾ 3, so that λ_{2}(A) ⩾ −1/2 (recall Lemma 2.2). Since 1 + (1 − u) + … + (1 − u)^{m−1} ≍ min{m, 1/u} for every u ∈ (0, 3/2] and m ∈ ℕ, inequality (220) is a consequence of Corollary 7.15 (with X = ℓ_{p} and p = 2), Theorem 1.5, and (219).

To state two additional examples of consequences of this type, fix K ∈ [2, ∞) and let (X, d_{X}) be a metric space that is doubling with constant K. In [DLP13] it is shown that M_{2}(X) ≲ log K, so in combination with Corollary 7.2 we deduce from Corollary 7.15 that

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{2}} ≲ (log K)^{2} ∑_{t=0}^{m−1} λ_{2}(A)^{t}.  (227)

Similarly, it was shown that if G is a connected planar graph then M_{2}(G, d_{G}) ≲ 1, so in combination with Corollary 7.2 we deduce from Corollary 7.15 that

\frac{∑_{i=1}^{n} ∑_{j=1}^{n}(A^{m})_{ij}d_{X}(x_{i}, x_{j})^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{X}(x_{i}, x_{j})^{2}} ≲ ∑_{t=0}^{m−1} λ_{2}(A)^{t}.  (228)

Despite the validity of satisfactory spectral estimates such as (220), (221), (222), (227) and (228), they do not follow automatically only from the fact that the metric space in question has Markov type 2. Specifically, there exists a metric space (X, d_{X}) that has Markov type 2, yet it is not true that γ(A, d_{X}^{2}) ≲_{X} 1/(1−λ_{2}(A)) for every symmetric stochastic matrix A. To see this, by Theorem 1.3 it suffices to prove the following result.

Theorem 7.16. There is a metric space (X, d_{X}) with Av_{ℓ_{2}}^{(2)}(X) = ∞, yet M_{2}(X) < ∞, i.e., X has Markov type 2.

Proof. If Λ ⊆ ℝ^{n} is a lattice of rank n then denote the length of the shortest nonzero vector in Λ by N(Λ). Also, let r(Λ) denote the infimum over those r ∈ (0, ∞) such that Euclidean balls of radius r centered at Λ cover ℝ^{n}. The dual lattice of Λ is denoted Λ^{∗}; thus Λ^{∗} is the set of all x ∈ ℝ^{n} such that ∑_{i=1}^{n} x_{i}y_{i} is an integer for every y ∈ Λ.

For every n ∈ ℕ choose an arbitrary rank n lattice Λ_{n} ⊆ ℝ^{n} that satisfies r(Λ_{n}) ≲ N(Λ_{n}). See [Rog50] for the existence of such lattices. Let ℝ^{n}/Λ_{n}^{∗} be the corresponding flat torus, equipped with the natural Riemannian quotient metric d_{ℝ^{n}/Λ_{n}^{∗}}(·, ·). Also, let μ_{n} denote the normalized Riemannian volume measure on ℝ^{n}/Λ_{n}^{∗}.

Consider the ℓ_{2} product

X =^{def} (⨁_{n=1}^{∞} (ℝ^{n}/Λ_{n}^{∗}))_{2} .

Thus X consists of all the sequences x = (x_{n})_{n=1}^{∞} ∈ ∏_{n=1}^{∞} (ℝ^{n}/Λ_{n}^{∗}) such that ∑_{n=1}^{∞} d_{ℝ^{n}/Λ_{n}^{∗}}(x_{n}, 0)^{2} < ∞, equipped with the metric given by d_{X} (x, y)^{2} = ∑_{n=1}^{∞} d_{ℝ^{n}/Λ_{n}^{∗}}(x_{n}, y_{n})^{2} for every x, y ∈ X. Since ℝ^{n}/Λ_{n}^{∗} has vanishing sectional curvature, it is an Aleksandrov space of nonnegative curvature (see [Oht09b, Sec. 3]), and therefore by a theorem of Ohta [Oht09b] it has Markov type 2 constant at most 1+\sqrt{2}. Being an ℓ_{2} product of spaces with uniformly bounded Markov type 2 constant, X also has Markov type 2.

Fix ε ∈ (0, 1). By covering the fundamental parallelepiped of Λ_{n}^{∗} by homothetic copies of itself, we see that there exists a finite measurable partition {U_{1}, …, U_{k}} of the torus ℝ^{n}/Λ_{n}^{∗} into sets of diameter at most ε and μ_{n}(U_{i}) = 1/k for every i ∈ {1, …, k}.

Fix an arbitrary point x_{i} ∈ U_{i} and suppose that f : {x_{1}, …, x_{k}} → ℓ_{2} is 1-Lipschitz. Since M_{2}(ℝ^{n}/Λ_{n}^{∗}) ⩽ 1 + \sqrt{2} ⩽ 3, by Ball’s extension theorem [Bal92] there exists F : ℝ^{n}/Λ_{n}^{∗} → ℓ_{2} that extends f and satisfies ∥F ∥_{Lip} ⩽ 3. By arguing as in the proof of Lemma 7.8, we have

\frac{1}{k^{2}} ∑_{i=1}^{k} ∑_{j=1}^{k} ∥f(x_{i}) − f(x_{j})∥_{ℓ_{2}}^{2}

⩽ 3 ∫_{ℝ^{n}/Λ_{n}^{∗}} ∫_{ℝ^{n}/Λ_{n}^{∗}} ∥F (x) − F (y)∥_{ℓ_{2}}^{2}dμ_{n}(x)dμ_{n}(y) + 54ε^{2}, (229)

and

\frac{1}{k^{2}} ∑_{i=1}^{k} d_{ℝ^{n}/Λ_{n}^{∗}}(x_{i}, x_{j})

⩾ \frac{1}{3} ∫_{ℝ^{n}/Λ_{n}^{∗}} ∫_{ℝ^{n}/Λ_{n}^{∗}} d_{ℝ^{n}/Λ_{n}^{∗}}(x, y)^{2}dμ_{n}(x)dμ_{n}(y) − 2ε^{2}, (230)

By [KN06, Lem. 11], for every Lipschitz mapping g : ℝ^{n}/Λ_{n}^{∗} → ℓ_{2},

∫_{ℝ^{n}/Λ_{n}^{∗}} ∫_{ℝ^{n}/Λ_{n}^{∗}} ∥g(x) − g(y)∥_{ℓ_{2}}^{2}dμ_{n}(x)dμ_{n}(y) ≲ \frac{n∥g∥_{Lip}^{2}}{N(Λ_{n}^{∗})^{2}} .  (231)

Also, by [KN06, Lem. 10] we have

∫_{ℝ^{n}/Λ_{n}^{∗}} ∫_{ℝ^{n}/Λ_{n}^{∗}} d_{ℝ^{n}/Λ_{n}^{∗}}(x, y)^{2}dμ_{n}(x)dμ_{n}(y) ≳ \frac{n^{2}}{r(Λ_{n}^{∗})^{2}} .  (232)

Hence, by letting ε → 0 in (229) and (230), it follows from (231) and (232) that

Av_{ℓ_{2}}^{(2)} (ℝ^{n}/Λ_{n}^{∗}) ≳ \frac{N(Λ_{n}^{∗})}{r(Λ_{n}^{∗})}\sqrt{n} ≳ \sqrt{n},  (233)

where we used the assumption r(Λ_{n}) ≲ N(Λ_{n}). Now Av_{ℓ_{2}}^{(2)}(X) = ∞ follows from (233) and the definition of X. □

Remark 7.17. The use of Ball’s extension theorem in the proof of Theorem 7.16 can be replaced by the use of Kirszbraun’s extension theorem [Kir34] combined with the fact [KN06, Thm. 6] (see also [HR13]) that c_{2}(ℝ^{n}/Λ_{n}^{∗}) ≲_{n} 1; in this case the factor 54 in (229) would be replaced by a factor that depends on n, but since we let ε → 0 this does not affect the rest of the proof (however, if one desires to bound k as a function of n, this approach would yield an inferior estimate).

References

[ABS98] N. Alon, R. Boppana, and J. Spencer. An asymptotic isoperimetric inequality. Geom. Funct. Anal., 8(3):411–436, 1998.

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

[AR94] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271–284, 1994.

[ARV09] S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):Art. 5, 37, 2009.

[Ass83] P. Assouad. Plongements lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

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

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

[BFdlV82] B. Bollobás and W. Fernandez de la Vega. The diameter of random regular graphs. Combinatorica, 2(2):125–134, 1982.

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

[BL00] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, [BLMN05] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type

phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[BLR10] P. Biswal, J. R. Lee, and S. Rao. Eigenvalue bounds, spectral partitioning, and metrical deformations via flows. J. ACM, 57(3):Art. 13, 23, 2010.

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

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

[BS87] A. Z. Broder and E. Shamir. On the second eigenvalue of random regular graphs. In 28th Annual Symposium on Foundations of Computer Science, pages 286–294. 1987.

[Cal64] A.-P. Calderón. Intermediate spaces and interpolation, the complex method. Studia Math., 24:113–190, 1964.

[CGR08] S. Chawla, A. Gupta, and H. Räcke. Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut. ACM Trans. Algorithms, 4(2):Art. 22, 18, 2008.

[Cha84] I. Chavel. Eigenvalues in Riemannian geometry, volume 115 of Pure and Applied Mathematics. Academic Press Inc., Orlando, FL, 1984. Including a chapter by Burton Randol, With an appendix by Jozef Dodziuk.

[Cha95] F. Chaatit. On uniform homeomorphisms of the unit spheres of certain Banach lattices. Pacific J. Math., 168(1):11–31, 1995.

[Che70] J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. In Problems in analysis (Papers dedicated to Salomon Bochner, 1969), pages 195–199. Princeton Univ. Press, Princeton, N. J., 1970.

[Chu89] F. Chung. Diameters and eigenvalues. J. Amer. Math. Soc., 2(2):187– 195, 1989.

[CM08] D. Christofides and K. Markström. Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales. Random Structures Algorithms, 32(1):88–100, 2008.

[CR82] M. Cwikel and S. Reisner. Interpolation of uniformly convex Banach spaces. Proc. Amer. Math. Soc., 84(4):555–559, 1982.

[DKSV06] N. R. Devanur, S. A. Khot, R. Saket, and N. K. Vishnoi. Integrality gaps for sparsest cut and minimum linear arrangement problems. In STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 537–546. ACM, New York, 2006.

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

[DLP13] J. Ding, J. R. Lee, and Y. Peres. Markov type and threshold embeddings. Geom. Funct. Anal., 23(4):1207–1229, 2013.

[dlS13] M. de la Salle. Towards Banach space strong property (T) for SL(3, ℝ),

2013. Preprint available at http://arxiv.org/abs/1307.2475.

[Elt83] J. Elton. Sign-embeddings of l_{1}^{n}. Trans. Amer. Math. Soc., 279(1):113– 124, 1983.

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

[Fie89] M. Fiedler. Laplacian of graphs and algebraic connectivity. In Combinatorics and graph theory (Warsaw, 1987), volume 25 of Banach Center Publ., pages 57–70. PWN, Warsaw, 1989.

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

[FJS88] T. Figiel, W. B. Johnson, and G. Schechtman. Random sign embeddings from l_{r}^{n}, 2 < r < ∞. Proc. Amer. Math. Soc., 102(1):102–106, 1988.

[Fri08] J. Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., 195(910):viii+100, 2008.

[FS02] U. Feige and G. Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. Random Structures Algorithms, 20(3):403–440, 2002. Probabilistic methods in combinatorial optimization.

[FT03] J. Fakcharoenphol and K. Talwar. An improved decomposition theorem for graphs excluding a fixed minor. In Approximation, randomization, and combinatorial optimization, volume 2764 of Lecture Notes in Comput. Sci., pages 36–46. Springer, Berlin, 2003.

[GHR12] F. Göring, C. Helmberg, and S. Reiss. Graph realizations associated with minimizing the maximum eigenvalue of the Laplacian. Math. Program., 131(1-2, Ser. A):95–111, 2012.

[GHW08] F. Göring, C. Helmberg, and M. Wappler. Embedded in the shadow of the separator. SIAM J. Optim., 19(1):472–501, 2008.

[GKL03] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, pages 534–543. 2003.

[GLS93] M. Grötschel, L. Lovász, and A. Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin, second edition, 1993.

[GPP80] E. D. Gluskin, A. Pietsch, and J. Puhl. A generalization of Khintchine’s inequality and its application in the theory of operator ideals. Studia Math., 67(2):149–155, 1980.

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

[Har66] L. H. Harper. Optimal numberings and isoperimetric problems on graphs. J. Combinatorial Theory, 1:385–393, 1966.

[Hei01] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[HN13] T. Hytönen and A. Naor. Pisier’s inequality revisited. Studia Math., 215(3):221–235, 2013.

[HR13] I. Haviv and O. Regev. The Euclidean distortion of flat tori. J. Topol. Anal., 5(2):205–223, 2013.

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

[JS88] M. Jerrum and A. Sinclair. Conductance and the rapid mixing property for markov chains: the approximation of the permanent resolved (preliminary version). In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 235–244. 1988.

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

[KM13] D. M. Kane and R. Meka. A PRG for Lipschitz functions of polynomials with applications to sparsest cut. In STOC’13: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pages 1–10. 2013.

[KN06] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821–852, 2006.

[Kon11] T. Kondo. CAT(0) spaces and expanders. Mathematische Zeitschrift, pages 1–13, 2011.

[KOR00] E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput., 30(2):457–474 (electronic), 2000.

[KPR93] P. N. Klein, S. A. Plotkin, and S. Rao. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 682–690. 1993.

[KR09] R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L_{1}. SIAM J. Comput., 38(6):2487–2498, 2009.

[KY06] G. Kasparov and G. Yu. The coarse geometric Novikov conjecture and uniform convexity. Adv. Math., 206(1):1–56, 2006.

[Laf08] V. Lafforgue. Un renforcement de la propriété (T). Duke Math. J., 143(3):559–602, 2008.

[Laf09] V. Lafforgue. Propriété (T) renforcée Banachique et transformation de Fourier rapide. J. Topol. Anal., 1(3):191–206, 2009.

[Led01] M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 2001.

[Lee05] J. R. Lee. On distance scales, embeddings, and efficient relaxations of the cut cone. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 92–101 (electronic). ACM, New York, 2005.

[Lia13] B. Liao. Strong Banach property (T) for simple algebraic groups of higher rank, 2013. Preprint available at

http://arxiv.org/abs/1301.1861.

[Lin63] J. Lindenstrauss. On the modulus of smoothness and divergent series in Banach spaces. Michigan Math. J., 10:241–252, 1963.

[LLR95] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

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

[LP13] R. Lyons and Y. Peres. Probability on Trees and

Networks,  2013.  Forthcoming  book,  available  at

http://mypage.iu.edu/~rdlyons/prbtree/book.pdf.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[LS88] G. F. Lawler and A. D. Sokal. Bounds on the L^{2} spectrum for Markov chains and Markov processes: a generalization of Cheeger’s inequality. Trans. Amer. Math. Soc., 309(2):557–580, 1988.

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

[LS10] J. R. Lee and A. Sidiropoulos. Genus and the geometry of the cut graph. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 193–201. 2010.

[Mar88] G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

[Mat97] J. Matoušek. On embedding expanders into ℓ_{p} spaces. Israel J. Math., 102:189–197, 1997.

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

[Maz29] S. Mazur. Une remarque sur l’homéomorphie des champs fonctionels. Studia Math., 1:83–85, 1929.

[MN08] M. Mendel and A. Naor. Metric cotype. Ann. of Math. (2), 168(1):247– 298, 2008. Preliminary version in SODA ’06.

[MN12] M. Mendel and A. Naor. Nonlinear spectral calculus and superexpanders, 2012. To appear in Inst. Hautes Études Sci. Publ. Math.,

available at http://arxiv.org/abs/1207.4705.

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

http://arxiv.org/abs/1306.5434.

[MN13b] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1:163–199, 2013.

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

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

[Nao12b] A. Naor. On the Banach-space-valued Azuma inequality and smallset isoperimetry of Alon-Roichman graphs. Comb. Probab. Comput., 21(4):623–634, 2012.

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

[NR09] I. Newman and Y. Rabinovich. Hard metrics from Cayley graphs of abelian groups. Theory Comput., 5:125–134, 2009.

[NRS05] A. Naor, Y. Rabani, and A. Sinclair. Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs. J. Funct. Anal., 227(2):273–303, 2005.

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

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

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

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

[OS94] E. Odell and T. Schlumprecht. The distortion problem. Acta Math., 173(2):259–281, 1994.

[Oza04] N. Ozawa. A note on non-amenability of ℬ(l_{p}) for p = 1, 2. Internat. J. Math., 15(6):557–565, 2004.

[Pis73] G. Pisier. Sur les espaces de Banach qui ne contiennent pas uniformément de l_{n}^{1}. C. R. Acad. Sci. Paris Sér. A-B, 277:A991–A994, 1973.

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

[Pis79] G. Pisier. La méthode d’interpolation complexe: applications aux treillis de Banach. In Séminaire d’Analyse Fonctionnelle (1978–1979), pages Exp. No. 17, 18. École Polytech., Palaiseau, 1979.

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

[Pis10] G. Pisier. Complex interpolation between Hilbert, Banach and operator spaces. Mem. Amer. Math. Soc., 208(978):vi+78, 2010.

[Rab08] Y. Rabinovich. On average distortion of embedding metrics into the line. Discrete Comput. Geom., 39(4):720–733, 2008.

[Rao99] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the Fifteenth Annual Symposium on Computational Geometry (Miami Beach, FL, 1999), pages 300–306 (electronic). ACM, New York, 1999.

[Ray02] Y. Raynaud. On ultrapowers of non commutative L_{p} spaces. J. Operator Theory, 48(1):41–68, 2002.

[Rog50] C. A. Rogers. A note on coverings and packings. J. London Math. Soc., 25:327–331, 1950.

[SBXD06] J. Sun, S. Boyd, L. Xiao, and P. Diaconis. The fastest mixing Markov process on a graph and a connection to a maximum variance unfolding problem. SIAM Rev., 48(4):681–699, 2006.

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

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

Courant Institute, New York University

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