Euclidean Quotients of Finite Metric Spaces

Manor Mendel

School of Engineering and Computer Science, Hebrew University, Jerusalem, Israel.

                         mendelma@cs.huji.ac.il

Assaf Naor Microsoft Research, Redmond, Washington

                          anaor@microsoft.com

Abstract This paper is devoted to the study of quotients of finite metric spaces. The basic type of question we ask is: Given a finite metric space M and α ≥ 1, what is the largest quotient of (a subset of) M which well embeds into Hilbert space. We obtain asymptotically tight bounds for these questions, and prove that they exhibit phase transitions. We also study the analogous problem for embedings into ℓ_{p}, and the particular case of the hypercube.

“ Our approach to general metric spaces bears the undeniable imprint of early exposure to Euclidean geometry. We just love spaces sharing a common feature with ℝ^{n}.”

Misha Gromov.

1 Introduction

A classical theorem due to A. Dvoretzky states that for every n-dimensional normed space X and every ε > 0 there is a linear subspace Y ⊆ X with k = dim Y ≥ c(ε) log n such that d(Y, ℓ_{2}^{k}) ≤ 1 + ε. Here d(·, ·) denotes the Banach-Mazur distance and c(·) depends only on ε. The first result of this type appeared in [15], and the logarithmic lower bound on the dimension is due to V. Milman [20]. If in addition to taking subspaces, we also allow passing to quotients, the dimension k above can be greatly improved. This is V. Milman’s Quotient of Subspace Theorem [21] (commonly referred to as the QS Theorem), a precise formulation of which reads as follows:

Theorem 1.1 (Milman’s QS Theorem [21]). For every 0 < δ < 1 there is a constant f(δ) ∈ (0, ∞) such that for every n-dimensional normed space X there are linear subspaces Z ⊆ Y ⊆ X with dim(Y/Z) = k ≥ (1 − δ)n and d(Y/Z, ℓ_{2}^{k}) ≤ f(δ).

Over the past two decades, several theorems in the local theory of Banach spaces were shown to have non-linear analogs. The present paper, which is a continuation of this theme, is devoted to the proof of a natural non-linear analog of the QS Theorem, which we present below.

A mapping between two metric spaces f : M → X, is called an embedding of M in X. The distortion of the embedding is defined as

dist(f) = sup_{\begin{matrix}x,y∈M \\ x≠y \end{matrix}} \frac{d_{X}(f(x), f(y))}{d_{M}(x, y)} · sup_{\begin{matrix}x,y∈M \\ x≠y \end{matrix}} \frac{d_{M}(x, y)}{d_{X}(f(x), f(y))}.

The least distortion required to embed M in X is denoted by c_{X}(M). When c_{X}(M) ≤ α we say that M α-embeds in X. If M is a class of metric spaces then we denote c_{M}(M) = inf_{X∈M} c_{X}(M).

In order to motivate our treatment of the non-linear QS problem, we first describe a nonlinear analog of Dvoretzky’s Theorem, which is based on the following notion: Given a class M of metric spaces, we denote by R_{M}(α, n) the largest integer m such that any n-point metric space has a subspace of size m that α-embeds into X. When M = {ℓ_{p}} we use the notations c_{p} and R_{p}. The parameter c_{2}(X) is known as the Euclidean distortion of X. In [11] Bourgain, Figiel, and Milman study this function, as a non-linear analog of Dvoretzky’s theorem. They prove

Theorem 1.2 (Non-Linear Dvoretzky Theorem [11]). For any α > 1 there exists C(α) > 0 such that R_{2}(α, n) ≥ C(α) log n. Furthermore, there exists α_{0} > 1 such that R_{2}(α_{0}, n) = O(log n).

In [5] the metric Ramsey problem is studied comprehensively. In particular, the following phase transition is proved.

Theorem 1.3 ([5]). The following two assertions hold true:

1. For every n ∈ ℕ and 1 < α < 2: c(α) log n ≤ R_{2}(α, n) ≤ 2 log n+C(α), where c(α), C(α) may depend only on α.

2. For every α > 2 there is an integer n_{0} such that for n ≥ n_{0}: n^{c′(α)} ≤ R_{2}(α, n) ≤ n^{C′(α)}, where c′(α), C′(α) depend only on α and 0 < c′(α) ≤ C′(α) < 1.

The following result, which deals with the metric Ramsey problem for large distortion, was also proved in [5]:

Theorem 1.4 ([5]). For every ε > 0, every n-point metric space X contains a subset of cardinality at least n^{1−ε} whose Euclidean distortion is O (\frac{log(1/ε)}{ε}).

With these results in mind, how should we formulate a non-linear analog of the QS Theorem? We now present a natural formulation of the problem, as posed by Vitali Milman.

The linear quotient operation starts with a normed space X, and a subspace Y ⊆ X, and partitions X into the cosets X/Y = {x + Y }_{x∈X}. The metric on X/Y is given by d(x+Y, x′ +Y) = inf{∥a−b∥; a ∈ x+Y, b ∈ x′ +Y }. This operation is naturally generalizable to the context of arbirary metric spaces as follows: Given a finite metric space M, partition M into pairwise disjoint subsets U_{1}, …, U_{k}. Unlike the case of normed spaces, The function d_{M}(U_{i}, U_{j}) = inf{d_{M}(u, v); u ∈ U_{i}, v ∈ U_{j}} is not necessarily a metric on U = {U_{1}, …, U_{k}}. We therefore consider the maximal metric on U majorized by d_{M}, which is easily seen to be the geodesic metric given by:

d_{geo}(U_{i}, U_{j}) = inf {∑_{r=1}^{k} d_{M}(V_{r}, V_{r−1}); V_{0}, …, V_{k} ∈ U, V_{0} = U_{i}, V_{r} = U_{j}} .

This operation clearly coincides with the usual quotient operation, when restricted to the class of normed spaces. When considering the QS operation, we first pass to a subset of M, and then construct a quotient space as above. We summarize this discussion in the following definition:

Definition 1.5. Let M be a finite metric space. A Q space of M is a metric space that can be obtained from M by the following operation: Partition M into s pairwise disjoint subsets U_{1}, …, U_{s} and equip U = {U_{1}, …, U_{s}} with the geodesic metric d_{geo}. Equivalently, consider the weighted complete graph whose vertices are U with edge weights: w(U_{i}, U_{j}) = d_{M}(U_{i}, U_{j}). The metric on U can now be defined to be the shortest-path metric on this weighted graph. A Q space of a subset of M will be called a QS space of M. Similarly, a subspace of a Q space of M will be called a SQ space of M.

The above notion of a quotient of a metric space is due to M. Gromov (see Section 1.16_{+} in [17]). The formulation of the non-linear QS problem is as follows: Given n ∈ ℕ and α ≥ 1, find the largest s ∈ ℕ such that any n-point metric space M has a QS space of size s that is α embeddable in ℓ_{2}. More generally, we consider the following parameters:

Definition 1.6. Let M be a class of metric spaces. For every n ∈ ℕ and α ≥ 1 we denote by Q_{M}(α, n) (respectively QS_{M}(α, n), SQ_{M}(α, n)) the largest integer m such that every npoint metric space has a Q space (respectively QS, SQ space) of size m that α-embeds into a member of M. When M = {ℓ_{p}} we use the notations Q_{p}, QS_{p} and SQ_{p}.

In the linear setting there is a natural duality between subspaces and quotients. In particular, one can replace in Dvoretzky’s theorem the word ”subspace” by the word ”quotient”, and the resulting estimate for the dimension will be identical. Similarly, the statement of the QS Theorem remains unchanged if we replace ”quotient of subspace” by ”subspace of quotient”. In the non-linear setting these simple observations are no longer clear. In view of Theorem 1.3, it is natural to ask if the same is true for Q spaces. Similarly, it is natural to ask if the QS and SQ functions behave asymptotically the same. In this paper we present a comprehensive analysis of the functions Q_{2}, QS_{2} and SQ_{2}. It turns out that the answer to the former question is no, while the answer to the latter question is yes. On the other hand, as conjectured by Milman, our results show that just as is the case in the linear setting, once we allow the additional quotient operation, the size of the Euclidean spaces obtained increases significantly.

Below is a summary of our results concerning the QS and SQ problems:

Theorem 1.7. For every 1 < α < 2 there are constants 0 < c(α), C(α) < 1 such that for every n ∈ ℕ,

n^{c(α)} ≤ QS_{2}(α, n), SQ_{2}(α, n) ≤ n^{C(α)}.

On the other hand, for every α ≥ 2 there is an integer n_{0} and there are constants 0 < c′(α), C′(α) < 1 such that for every n ≥ n_{0},

c′(α)n ≤ QS_{2}(α, n), SQ_{2}(α, n) ≤ C′(α)n.

As mentioned above, the Q problem exhibits a different behavior. In fact, we have a double phase transition in this case:

Theorem 1.8. For every 1 < α < \sqrt{2} there is a constant C_{1}(α) such that for every n ∈ ℕ, Q_{2}(α, n) ≤ C_{1}(α). For every \sqrt{2} < α < 2 there are constants c(α), C(α) such that for every n ∈ ℕ, n^{c(α)} ≤ Q_{2}(α, n) ≤ n^{C(α)}. Finally, for every α ≥ 2 there is an integer n_{0} and there are constants 0 < c′(α), C′(α) < 1 such that for every n ≥ n_{0}, c′(α)n ≤ Q_{2}(α, n) ≤ C′(α)n.

In other words, for α > \sqrt{2} the asymptotic behavior of the function Q_{2} is the same as the behavior of the functions QS_{2} and SQ_{2}. We summarize the qualitative behavior of the size of subspaces, quotients, quotients of subspaces and subspaces of quotients of arbitrary metric spaces in Table 1. For aesthetic reasons, in this table we write S_{2} = R_{2} (i.e. R_{2} is the ”subspace” function). The first row contains results from [5]. We mention here that the behavior of S_{2}(2, n) remains unknown. Furthermore, we do not know the behavior of the function Q_{2} at \sqrt{2}. Finally, we mention that in [6] it is shown that R_{2}(1, n) = 3 for all n ≥ 3. We did not study the functions Q_{2}, QS_{2}, SQ_{2} in the isometric case.

Distortion

(1, \sqrt{2})  (\sqrt{2}, 2)  (2, ∞)
S_{2}  logarithmic  polynomial
Q_{2}  constant polynomial proportional
QS_{2}  polynomial  proportional
SQ_{2}  polynomial  proportional

Table 1: The qualitative behavior of the Euclidean quotient/ subspace functions, for different distortions.

For large distortions we prove the following analog of Theorem 1.4:

Theorem 1.9. For any n ∈ ℕ and ε > 0, every n-point metric space has a Q space of size (1 − ε)n whose Euclidean distortion is O( log(2/ε)). On the other hand, there are arbitrarily large n-point metric spaces every QS or SQ space of which, of size at least (1 − ε)n, has Euclidean distortion Ω( log(2/ε)).

This result should be viewed in comparison to Bourgain’s embedding theorem [10], which states that for every n-point metric spaces X, c_{2}(X) = O(log n). Theorem 1.9 states that if one is allowed to identify an arbitrarily small proportion of the elements of X, it possible to arrive at a metric space whose Euclidean distortion is bounded independently of n. In fact, Theorem 1.9 is proved via a modification of Bourgain’s original proof. This is unlike the situation for the non-linear Dvoretzky problem, since in [7] an example is constructed which shows that Bourgain’s embedding method cannot yield results such as Theorem 1.4.

Except for a loss in the dependence on ε, it is possible to give a more refined description of the Q spaces obtained in Theorem 1.9. Using a different embedding method, we can actually ensure that for every ε > 0, every n point metric space has a Q space of size (1−ε)n which well embeds into an ultrametric. This is of interest since such spaces have a simple hierarchically clustered structure, which is best described through their representation as a hierarchically well-separated tree (see Section 3 for the definition). This special structure is useful in several algorithmic contexts, which will be discussed in a forthcoming (Computer Science oriented) paper.

Theorem 1.10. For every ε > 0 and n ∈ ℕ, any n point metric space X contains a subset A ⊆ X of size at most εn such that the quotient of X induced by the partition {{a}}_{a∈X\A}∪{A}

is O [\frac{log(1/ε)}{ε}] equivalent to an ultrametric. On the other hand, there are arbitrarily large npoint metric spaces every QS or SQ space of which, of size at least (1−ε)n, cannot be embedded into an ultrametric with distortion O(1/ε).

In Section 5 we study the QS problem for the hypercube Ω_{d} = {0, 1}^{d} (although the embedding results used there may also be of independent interest). The cube-analog of Theorem 1.4 was studied in [5], where it was shown that if B ⊂ Ω_{d} satisfies c_{2}(B) ≤ α then |B| ≤ C2^{1−c/α^{2}}, and on the other hand there is a subset B_{0} ⊂ Ω_{d} with Euclidean distortion at most α and which contains at least 2^{1−[log(c′α)]/α^{2}} points (here c, c′, C are positive universal constant). In Section 5 we prove the following QS counterpart of this result:

Theorem 1.11. There is an absolute constant c > 0 such that for all d ∈ ℕ and 0 < ε < 1/2, every QS space of Ω_{d} containing more than (1 − ε)2^{d} points has Euclidean distortion at least:

c\sqrt{\frac{log(1/ε)}{1 + log (\frac{d}{log(1/ε)})}}.

On the other hand, there are QS spaces of Ω_{d}, of size greater than (1 − ε)2^{d} whose Euclidean distortion matches this bound.

In Section 6 we briefly study another notion of quotient introduced by Bates, Johnson, Lindenstrauss, Preiss and Schechtman [8], which has been the focus of considerable attention in the last few years. It turns that this notion of quotient, while being useful in many contexts, does not yield a satisfactory non-linear version of the QS theorem (at least for distortion greater than 2). Namely, we show that using this notion of quotient we cannot expect to obtain quotients of subspaces which are asymptotically larger than what is obtained by just passing to subspaces (i.e. what is ensured by Theorem 1.3).

In order to describe this notion we recall the following standard notation which will be used throughout this paper. Given a metric space M, x ∈ M and ρ > 0, denote B_{M}(x, ρ) = {y ∈ M; d_{M}(x, y) ≤ ρ} and B_{M}^{∘}(x, ρ) = {y ∈ M; d_{M}(x, y) < ρ}.

Let (X, d_{X}) and (Y, d_{Y}) be metric spaces and c > 0. A function f : X → Y is called c-co-Lipschitz if for every x ∈ X and every r > 0, f(B_{X}(x, r)) ⊇ B_{Y} (f(x), r/c). The function f is called co-Lipschitz if it is c-co-Lipschitz for some c > 0. The smallest such c is denoted by coLip(f). A surjection f : X → Y is called a Lipschitz quotient if it is both Lipschitz and co-Lipschitz. The notion of co-Lipschitz mappings was introduced by Gromov (see Section 1.25 in [17]), and the definition of Lipschitz quotients is due to Bates, Johnson, Lindenstrauss, Preiss and Schechtman [8]. The basic motivation is the fact that the Open Mapping Theorem ensures that surjective continuous linear operators between Banach spaces are automatically co-Lipschitz.

In the context of finite metric spaces these notions only make sense with additional quantitative control of the parameters involved. Given α > 0 and two metric spaces (X, d_{X}), (Y, d_{Y}) we say that X has an α-Lipschitz quotient in Y if there is a subset Z ⊂ Y and a Lipschitz quotient f : X → Z such that Lip(f) · coLip(f) ≤ α. The following definition is the analog of Definition 1.6 in the context of Lipschitz quotients.

Definition 1.12. Let M be a class of metric spaces. For every n ∈ ℕ and α ≥ 1 we denote by QS_{M}^{Lip}(α, n) the largest integer m such that every n-point metric space has a subspace which has an α-Lipschitz quotient in a member of M. When M = {ℓ_{p}} then we use the notation

QS_{p}^{Lip}

The main result of Section 6 is:

Theorem 1.13. The following two assertions hold true:

1. For every α > 2 there is an integer n_{0} such that for n ≥ n_{0}: n^{c(α)} ≤ QS_{2}^{Lip}(α, n) ≤ n^{C(α)}, where c(α), C(α) depend only on α and 0 < c(α) ≤ C(α) < 1.

2. For every 1 ≤ α < 2 there is an integer n_{0} such that for n ≥ n_{0}:

e^{c′(α)\sqrt{log n}} ≤ QS_{2}^{Lip}(α, n) ≤ e^{C′(α)\sqrt{(log n)(log log n)}},

where c′(α), C′(α) depend only on α.

Thus, the additional Lipschitz quotient operation only yields an improvement for distortion smaller than 2. We have not studied the analogous questions for the Q and SQ problems.

Throughout this paper we also study the functions Q_{p}, SQ_{p}, QS_{p} for general 1 ≤ p < ∞. In most cases we obtain matching or nearly matching upper and lower bounds for the various functions, but some interesting problems remain open. We summarize in Table 2 and Table 3 the qualitative nature of our results (in which we write once more R_{p} = S_{p}). As is to be expected, it turns out that there is a difference between the cases 1 ≤ p ≤ 2 and p > 2. In both tables, the first row contains results from [5] and [6]. In Table 3 the question marks refer to the fact that for p > 2 our lower and upper bounds do not match in the range (2^{2/p}, 2).

Distortion

(1, 2^{1− \frac{1}{p}}) (2^{1− \frac{1}{p}} , 2)  (2, ∞)
S_{p} logarithmic polynomial
Q_{p}  constant polynomial proportional
QS_{p}  polynomial  proportional
SQ_{p}  polynomial  proportional

Table 2: The qualitative behavior of the ℓ_{p} quotient/ subspace function for p ≤ 2, and different distortions.

Distortion

(1, 2^{\frac{1}{p}})  (2^{\frac{1}{p}} , 2^{\frac{2}{p}}) (2^{\frac{2}{p}} , 2)  (2, ∞)
S_{p}  logarithmic  ?  polynomial
Q_{p}  constant polynomial  ?  proportional
QS_{p}  polynomial  ?  proportional
SQ_{p}  polynomial  ?  proportional

Table 3: The qualitative behavior of the ℓ_{p} quotient/ subspace function for p ≥ 2, and different distortions.

This paper is organized as follows. Section 2 deals with the various upper bounds for Q_{p}, QS_{p}, SQ_{p}. In Section 3 we prove Theorem 1.9 and Theorem 1.10. In Section 4 we prove the various lower bounds for Q_{p}(α, n) , QS_{p}(α, n) and SQ_{p}(α, n) for α ≤ 2. Section 5 deals with the QS problem for the hypercube (in the context of embeddings into ℓ_{p} for general p ≥ 1). Finally, Section 6 deals with the QS problem for Lipschitz quotients.

2 Upper Bounds

In this section we present the various upper bounds for the Q, QS and SQ problems presented in the introduction. In the following two sections we will provide matching lower bounds for these problems.

We begin with an abstract method with which one can obtain upper bounds for QS_{M}(α, n), for various classes of metric spaces M.

Lemma 2.1. Let M be a class of metric spaces and α > 1. Assume that there exists a k-point metric space X such that c_{M}(X) > α. Then for every integer n,

max \{SQ_{M}(α, nk), QS_{M}(α, nk)\} ≤ (k − \frac{1}{2}) n.

Proof. Define Y = X × {1, …, n}. We equip Y with the following metric:

d_{Y} ((x, i), (y, j)) = \{ \begin{matrix}d_{X}(x, y) & i = j \\ β & i ≠ j \end{matrix}

It is straightforward to verify that provided β ≥ diam(X), d_{Y} is indeed a metric.

Since |Y | = nk, it is enough to show that Y has no QS or SQ space of size greater than (k − \frac{1}{2}) n which α-embeds into a member on M. Let U_{1} …, U_{r} ⊆ Y be disjoint subsets and r > (k − \frac{1}{2}) n. Denote m = |\{1 ≤ i ≤ r; |U_{i}| = 1\}|. Then:

kn ≥ |⋃_{i=1}^{r} U_{i}| = ∑_{i=1}^{r} |U_{i}| ≥ m + 2(r − m) > 2 (k − \frac{1}{2}) n − m = 2kn − n − m.

Hence m > kn − n, which implies that there is i ∈ {1, …, n} such that the singletons {{(x, i)}}_{x∈X} are all elements of U = {U_{1}, …, U_{r}}. If Y has either a QS space or a SQ space of size greater than r which α-embed into a member of M then we could find such U which could be completed to a partition V of a subset S ⊆ Y such that U, equipped with the quotient metric induced by V, α-embeds into a member of M. By taking β = diam(X) we guarantee that both the QS and the SQ metrics induced by V, when restricted to X × {i} are isometric to X. This contradicts the fact that c_{M}(X) > α.

The next two corollaries are the upper bounds contained in Theorem 1.9 and the second part of Theorem 1.7.

Corollary 2.2. For every ε ∈ (0, 1) and 1 ≤ p < ∞ there are arbitrarily large n-point metric spaces every QS or SQ space of which, U, of size at least (1 − ε)n, satisfies c_{p}(U) ≥ Ω([log(2/ε)]/p).

Proof. By [19] there are constants c, ε_{0} > 0 such that for ε ≤ ε_{0} there is a k-point metric spaces X with k ≤ \frac{1}{3ε}, for which c_{p}(X) ≥ c[log(1/ε)]/p. By Lemma 2.1, for every integer m there is a metric space of size km, such that every QS or SQ space of which, of size at least (k − \frac{1}{3}) m ≤ (1 − ε)km, cannot be embedded in ℓ_{p} with distortion smaller than c[log(2/ε)]/p.

Corollary 2.3. For every α > 1 there exists a constant c(α) < 1 such that for every 1 ≤ p < ∞ there is an integer n_{0} = n_{0}(p) such that for every n ≥ n_{0}, QS_{p}(α, n), SQ_{p}(α, n) ≤ c(α) · n.

Proof. By [19] there is a constant c > 0 such that for every k large enough there is a metric space X_{k} such that for every 1 ≤ p < ∞, c_{p}(X_{k}) ≥ [c log k]/p. So, for k = ⌊e^{αp/c}⌋ + 1, c_{p}(X_{k}) > α. If n > 8k^{2} then we can find an integer m such that \frac{n}{k} ≤ m ≤ \frac{4k−1}{4k−2} · \frac{n}{k}. By Lemma 2.1,

max \{QS_{p}(α, n), SQ_{p}(α, n)\} ≤ max \{QS_{p}(α, mk), SQ_{p}(α, mk)\} ≤ (k − \frac{1}{2}) m ≤ (1 − \frac{1}{4k} ) n.

The upper bound for embedding into the class of ultrametrics, analogous to Corollary 2.2, shows that in this case the asymptotic dependence on ε is worse. In order to prove it we need the following simple lemma. Recall that a metric space (X, d) is called ultrametric if for every x, y, z ∈ X, d(x, y) ≤ max{d(x, z), d(y, z)}. In what follows we denote by UM the class of all ultrametrics.

Lemma 2.4. Let {a_{i}}_{i=1}^{n} be an increasing sequence of real numbers, equipped with the metric induced by the real line. Then:

c_{UM}(\{a_{1}, …, a_{n}\}) ≥ \frac{a_{n} − a_{1}}{max_{1≤i≤n−1}(a_{i+1} − a_{i})}.

In particular, c_{UM}({1, …, n}) ≥ n − 1, i.e. the least distortion embedding of {1, …, n} into an ultrametric is an embedding into an equilateral space.

Proof. Let X be an ultrametric and f : {a_{1}, …, a_{n}} → X be an embedding such that for all 1 ≤ i, j ≤ n, d_{X}(f(a_{i}), f(a_{j})) ≥ |a_{i} − a_{j}| and there exist 1 ≤ i < j ≤ n for which d_{X}(f(a_{i}), f(a_{j})) = |a_{i} − a_{j}|. For 1 ≤ i, j ≤ n write i ∼ j if d_{X}(f(a_{i}), f(a_{j})) < a_{n} − a_{1}. The fact that X is an ultrametric implies that ∼ is an equivalence relation. Moreover, our assumption of f implies that 1 ≁ n. It follows that there exists 1 ≤ i ≤ n − 1 such that a_{i} ≁ a_{i+1}, i.e. d_{X}(f(a_{i+1}), f(a_{i})) ≥ a_{n} − a_{1}, which implies the lower bound on the distortion of f.

Corollary 2.5. For every 0 < ε < 1 there are arbitrarily large n-point metric spaces every QS or SQ space of which, U, of size at least (1 − ε)n, satisfies c_{UM}(U) ≥ ⌊\frac{1}{2ε}⌋ − 2.

Additionally, for every α ≥ 1 and every n ≥ 8(⌊α⌋ + 2)^{2}, c_{UM}(α, n) ≤ \frac{7+4⌊α⌋}{8+4⌊α⌋}n.

Proof. The proof is analogous to the proofs of Corollary 2.2 and Corollary 2.3. In the first case we set k = ⌊\frac{1}{2ε}⌋ and take X = \{1, …, k\}. By Lemma 2.4, c_{UM}(X) ≥ k − 1 > k − 2, and the required result follows from Lemma 2.1. In the second case we set k = ⌊α⌋ + 2 so that c_{UM}({1, …, k}) > α. We conclude exactly as in the proof of Corollary 2.3.

The following proposition bounds from above the functions QS_{p} and SQ_{p} for distortions smaller than 2^{min{1,2/p}}. Our proof is a modification of the technique used in [6].

Proposition 2.6. There is an absolute constant c > 0 such that for every δ ∈ (0, 1), and every n ∈ N, if 1 ≤ p ≤ 2 then:

max {QS_{p}(2 − δ, n), SQ_{p}(2 − δ, n)} ≤ n^{1−cδ^{2}},

and if 2 < p < ∞ then:

max {QS_{p}(2^{2/p} − δ, n), SQ_{p}(2^{2/p} − δ, n)} ≤ n^{1−cp^{2}δ^{2}},

Proof. Fix an integer m, and denote by K_{m,m} the complete bipartite m×m graph. It is shown in [6] that:

c_{p}(K_{m,m}) ≥ \{ \begin{matrix}2 (\frac{m−1}{m})^{1/p} & 1 ≤ p ≤ 2 \\ 2^{2/p} (\frac{m−1}{m})^{1/p} & 2 < p < ∞. \end{matrix}

It follows in particular that for m = ⌊\frac{4}{pδ} ⌋, c_{p}(K_{m,m}) > 2^{min\{1,2/p\}} − δ.

Fix 0 < q < 1, the exact value of which will be specified later. Let G = (V, E) be a random graph from G(n, q) (i.e. a graph on n vertices, such that each pair of vertices forms an edge independently with probability q). Define a metric on V by requiring that for u, v ∈ V, u ≠ v, d(u, v) = 1 if [u, v] ∈ E and d(u, v) = 2 if [u, v] ∉ E. Fix an integer s. Consider a set of s disjoint subsets of V, U = {U_{1}, …, U_{s}}. We observe that when U is viewed as either a QS or SQ space of (V, d), in both cases the metrics induced by U are actually the same (and equal min\{d(x, y); x ∈ U_{i}, y ∈ U_{j}\}). Denote W = \{U_{i}; 1 ≤ i ≤ s, |U_{i}| ≤ \frac{2n}{s}\}. Clearly |W| ≥ s/2. Without loss of generality, W ⊇ {U_{1}, U_{2}, …, U_{⌈s/2⌉}}.

For 1 ≤ i < j ≤ ⌈s/2⌉ denote by γ_{ij} the probability that there is an edge between U_{i} and U_{j}. Clearly γ_{ij} = 1 − (1 − q)^{|U_{i}|·|U_{j}|}, so that:

q ≤ γ_{ij} ≤ 1 − (1 − q)^{(2n/s)^{2}}.

Since K_{m,m} has m^{2} edges, the probability that the metric induced by U (in both of the SQ and QS cases) on a given 2m-tuple in {U_{1}, U_{2}, …, U_{⌈s/2⌉}} coincides with the metric on K_{m,m} is therefore at least:

q^{m^{2}}[(1 − q)^{(2n/s)^{2}}]^{\binom{2m}{2}−m^{2}} ≥ [q(1 − q)^{(2n/s)^{2}}]^{m^{2}}.

As shown in [6], there are (\frac{s}{4m})^{2} 2m-tuples of elements of \{U_{1}, U_{2}, …, U_{⌈s/2⌉}\}, such that any two intersect in at most one point. Therefore, the probability that U does not contain a subspace isometric to K_{m,m} is at most:

\{1 − [q(1 − q)^{(2n/s)^{2}}]^{m^{2}}\}^{(^{\frac{s}{4m}})}^{2} .

Observe that the number of partitions of V into at least s subsets is s^{n} + (s + 1)^{n} + … + n^{n} ≤ (n + 1)^{n}, so that the probability that all the s-point QS (or SQ) spaces of (V, d) contain an isometric copy of K_{m,m}, and hence cannot be embedded into ℓ_{p} with distortion smaller that 2^{min{1,2/p}} − δ, is at least:

1 − (n + 1)^{n} \{1 − [q(1 − q)^{(2n/s)^{2}}]^{m^{2}}\}^{(^{\frac{s}{4m}})}^{2} .

We will therefore conclude the proof once we verify that for s ≈ n^{1−cp^{2}δ^{2}}, we can choose q such that this probability is positive. Write s = n^{1−η} and q = p^{2}δ^{2}n^{−2η}. Then, since m ≤ \frac{4}{pδ}, there is an absolute constant C > 0 such that:

[q(1 − q)^{(2n/s)^{2}}]^{m^{2}} ≥ Cn^{−32η/(p^{2}δ^{2})}.

Hence:

1 − (n + 1)^{n} \{1 − [q(1 − q)^{(2n/s)^{2}}]^{m^{2}}\}^{(^{\frac{s}{4m}})}^{2} ≥ 1 − (n + 1)^{n} [1 − Cn^{−32η/(p^{2}δ^{2})}]^{p^{2}δ^{2}n^{2−2η}/16^{2}}
≥ 1 − e^{n log(n+1)−C′p^{2}δ^{2}n^{2−64η/(p^{2}δ^{2})}} > 0

where we have assumed that C′p^{2}δ^{2} < 1 (which we are clearly allowed to do), and chosen η = cp^{2}δ^{2} for a small enough constant c.

We end this section by showing that for α ≤ 2^{min{1/p,1−1/p}} we cannot hope to extract quotients of metric spaces which embed in ℓ_{p} with distortion α and that contain more than a bounded number of points. This is quite easy to see, by considering the star metric (defined below). What is perhaps less obvious is that star metrics are the only obstruction for the existence of unboundedly large quotients of any sufficiently large metric space, as shown in Section 4.

Given an integer n we denote by ⋆_{n} the metric on {0, 1, …, n} given by d_{⋆_{n}}(i, 0) = 1 for 1 ≤ i ≤ n, and d_{⋆_{n}}(i, j) = 2 for 1 ≤ i < j ≤ 2. The metrics ⋆_{n} are naturally called star metrics.

Lemma 2.7. For every integer n,

c_{p}(⋆_{n}) ≥ \{ \begin{matrix}2^{1−1/p} (1 − \frac{1}{n})^{1/p} & 1 ≤ p ≤ 2 \\ 2^{1/p} (1 − \frac{1}{n})^{1/p} & 2 ≤ p < ∞. \end{matrix}  (1)

Proof. Let f : ⋆_{n} → ℓ_{p} be an embedding such that for every x, y ∈ ⋆_{n},

d_{⋆_{n}}(x, y) ≤ ∥f(x) − f(y)∥_{p} ≤ Ld_{⋆_{n}}(x, y).

We begin with case 1 ≤ p ≤ 2. In this case, as shown in [18], for every x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℓ_{p},

∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − x_{j}∥_{p}^{p} + ∥y_{i} − y_{j}∥_{p}^{p}) ≤ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − y_{j}∥_{p}^{p}.

Applying this inequality to x_{i} = f(i) and y_{i} = f(0) we get that:

n(n − 1)2^{p} ≤ ∑_{i=1}^{n} ∑_{j=1}^{n} ∥f(i) − f(j)∥_{p}^{p} ≤ 2 ∑_{i=1}^{n} ∑_{j=1}^{n} ∥f(i) − f(0)∥_{p}^{p} ≤ 2n^{2}L^{p}.

This proves the required result for 1 ≤ p ≤ 2. For p ≥ 2 we apply the same argument, but use the following inequality valid for every x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℓ_{p} (see Corollary 7 in [4]):

∑_{i=1}^{n} ∑_{j=1}^{n} (∥x_{i} − x_{j}∥_{p}^{p} + ∥y_{i} − y_{j}∥_{p}^{p}) ≤ 2^{p−1} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{p}^{p}.

In the following corollary (and also later on in this paper), we use the convention Q_{p}(α, n) = 0 when α < 1.

Corollary 2.8. For every integer n and every 0 < δ < 1, if 1 < p ≤ 2 then:

Q_{p}(2^{1−1/p}(1 − δ)^{1/p}, n) ≤ 1 + \frac{1}{δ},

and if 2 ≤ p < ∞ then:

Q_{p}(2^{1/p}(1 − δ)^{1/p}, n) ≤ 1 + \frac{1}{δ}.

Proof. It is straightforward to verify that any Q space of ⋆_{n−1} of size k + 1 is isometric to ⋆_{k} (the new ”root” will be the class containing the old ”root” of the star). The result now follows from the lower bounds in Lemma 2.7.

3 Lower Bounds for Large Distortions

In this section we study the following problem: Given ε > 0, what is the least distortion α such that every n point metric space has a Q space of size (1 − ε)n which α embeds into ℓ_{p}? We prove a lower bound which matches the upper bound proved in Section 2. The proof is based on a modification of Bourgain’s fundamental embedding method [10]. Next, we further refine the structural information on the quotients obtained. Namely, we construct for arbitrary n-point metric spaces quotients of size (1 − ε)n which c(ε)-embed into an ultrametric. In fact, in both cases we obtain the following special kind of quotients:

Definition 3.1. Let M be an n-point metric space and A ⊆ M. Let U be the partition of M consisting of A and the elements of M \ A as singletons. The Q space of M induced by U will be denoted M/A. By the definition of the quotient operation it is easy to verify that for every x, y ∈ M \ A,

d_{M/A}(x, y) = min{d_{M}(x, y), d_{M}(x, A) + d_{M}(y, A)}.  (2)

Additionally, for x ∈ M \ A, d_{M/A}(x, A) = d_{M}(x, A).

This simple description of the quotients we construct, together with the fact that we can ensure they have the hierarchical structure of ultrametrics, has algorithmic significance, which will be pursued in a future paper.

The following definition will be useful:

Definition 3.2. Let X be a metric space, x ∈ X and m ≥ 1. We shall say x is an m-center of X if for every y ∈ X and every r > 0, if |B_{X}(y, r)| ≥ m then x ∈ B_{X}(y, r).

Lemma 3.3. Let M be an n-point metric space and 0 < ε < 1. Then there exists a subset T ⊆ M such that |T | ≤ εn and T is a \frac{2 log(2/ε)}{ε}-center of M/T.

Proof. Set m = \frac{2 log(2/ε)}{ε}. For every x ∈ M denote by ρ_{x}(m) the smallest ρ > 0 for which |B_{M}(x, ρ)| ≥ m. Choose a random subset T ⊆ M as follows: Let S be the random subset of M obtained by choosing each point with probability ε/2. Define:

T = S ∪ {x ∈ M; S ∩ B_{M}(x, ρ_{x}(m)) = ∅} .

Then:

𝔼|T | = 𝔼|S| + ∑_{x∈M} Pr [S ∩ B_{M}(x, ρ_{x}(m)) = ∅] ≤ \frac{εn}{2} + (1 − \frac{ε}{2})^{m} n < εn.

Denote U = M/T. The proof will be complete once we show that:

∀w ∈ U, ∀r > 0 |B_{U}(w, r)| ≥ m ⟹ T ∈ B_{U}(w, r).

Indeed, if w = T then there is nothing to prove. Otherwise, assume for the sake of contradiction that w = x for some x ∈ M \ T with d_{U}(w, T) = d_{M}(x, T) > r. By (2), for every y ∈ M \ T, d_{U}(x, y) = min{d_{M}(x, y), d_{M}(x, T) + d_{M}(y, T)}. In particular, if d_{U}(x, y) ≤ r then d_{M}(x, y) = d_{U}(x, y). Hence |B_{M}(x, r)| ≥ m, so that by the construction of T, T ∩ B_{M}(x, r) ≠ ∅, contrary to our assumption.

The following lemma shows that metric spaces with an m-center well embed into ℓ_{p}. The proof is essentially a repetition of Bourgain’s original argument [10] (we actually follow Matoušek’s ℓ_{p}- variant of Bourgain’s theorem [19]).

Lemma 3.4. Fix m ≥ 1 and let X be metric space which has an m-center. Then for every 1 ≤ p < ∞,

c_{p}(X) ≤ 96 ⌈\frac{log m}{p}⌉ .

Proof. Let x be an m-center of X. Set q = ⌈\frac{log m}{p}⌉. Fix u, v ∈ X, u ≠ v. For i ∈ \{0, 1, …, q\} let r_{i} be the smallest radius such that |B_{X}(u, r_{i})| ≥ e^{pi} and |B_{X}(v, r_{i})| ≥ e^{pi}. Observe that by the definition of q, |B_{X}(u, r_{q})|, |B_{X}(v, r_{q})| ≥ e^{pq} ≥ m, so that since x is an m-center of X, x ∈ B_{X}(u, r_{q}) ∩ B_{X}(v, r_{q}). This implies that r_{q} ≥ \frac{d_{X}(u,v)}{2}. Fix i ∈ \{1, …, q\}. By the definition of r_{i} we may assume without loss of generality that |B_{X}^{∘}(u, r_{i})| ≤ e^{pi}. If A ⊆ X is such that A ∩ B_{X}^{∘}(u, r_{i}) = ∅ and A ∩ B_{X}(v, r_{i−1}) ≠ ∅ then d_{X}(u, A) − d_{X}(v, A) ≥ r_{i} − r_{i−1}. If A is chosen randomly such that each point of X is picked independently with probability e^{−pi} then the probability of the former event is at least:

[1 − (1 − \frac{1}{e^{pi}} )^{|B_{U} (v,r_{i−1})|}]·(1 − \frac{1}{e^{pi}} )^{|B_{U} (u,r_{i})|} ≥ [1 − (1 − \frac{1}{e^{pi}} )^{e^{p(i−1)}}]·(1 − \frac{1}{e^{pi}} )^{e^{pi}} ≥ \frac{1}{8e^{p}} .

For A ⊆ X, denote by π_{i}(A) the probability that a random subset of A, with points picked independently with probability e^{−pi}, equals A. The above reasoning implies that:

∑_{A⊆X} π_{i}(A)|d_{X}(u, A) − d_{X}(v, A)|^{p} ≥ \frac{(r_{i} − r_{i−1})^{p}}{8e^{p}} ,

so that if we define α_{A} = \frac{1}{q} ∑_{i=1}^{q} π_{i}(A) then:

∑_{A⊆X} α_{A}|d_{X}(u, A) − d_{X}(v, A)|^{p} ≥ \frac{1}{8qe^{p}} ∑_{i=1}^{q}(r_{i} − r_{i−1})^{p}

≥ \frac{1}{8q^{p}e^{p}} (∑_{i=1}^{q}(r_{i} − r_{i−1}))^{p}

= \frac{(r_{q} − r_{0})^{p}}{8q^{p}e^{p}} ≥ \frac{[d_{X}(u, v)]^{p}}{16 · 2^{p}q^{p}e^{p}} .

Now, the embedding of X sends an element u ∈ X to a vector indexed by the subsets of X, such that the coordinate corresponding to A ⊆ X is α_{A}^{1/p} ·d_{X}(u, A). Since ∑_{A⊆X} α_{A} = 1, such a mapping is obviously non-expanding, and the above calculation shows that the Lipschitz constant of its inverse is at most 16^{1/p} · 2eq ≤ 96q, as required.

The following corollary is a direct consequence of Lemma 3.3 and Lemma 3.4:

Corollary 3.5. There is an absolute constant c > 0 such that for every 1 ≤ p < ∞ and every 0 < ε < 1, any n-point metric space M has a subset A ⊆ M such that |A| < εn and:

c_{p}(M/A) ≤ 1 + \frac{c}{p} log (\frac{2}{ε}) .

We can also apply Lemma 3.3 to obtain quotients which embed into ultrametrics. The basic fact about ultrametrics, already put to good use in [5], is that they are isometric to subsets of Hilbert space. Another useful trait of finite ultrametrics is that they have a natural representation as hierarchically well-separated trees (HSTs). We recall the following useful definition, due to Y. Bartal [2]:

Definition 3.6. Given k ≥ 1, a k-HST is a metric space whose elements are leaves of a rooted tree T. To each vertex u ∈ T, a label Δ(u) is associated such that Δ(u) = 0 if and only if u is a leaf of T. The labels are strongly decreasing in the sense that Δ(u) ≤ Δ(v)/k whenever u is a child of v. The distance between two leaves x, y ∈ T is defined as Δ(lca(x, y)), where lca(x, y) denotes the the least common ancestor of x and y in T. In what follows, T is called the defining tree of the k-HST. For simplicity we call a 1-HST a HST. It is an easy fact to verify that the notion of a finite ultrametric coincides with that of a HST. Although k-HSTs will not appear in this section, this proper subclass of ultrametrics will play a key role in Section 4.

Lemma 3.7. Let m ≥ 1 be an integer and let X be an n-point metric space which has an m-center. Then X 2m-embeds into an ultrametric.

Proof. We prove by induction on n that there is a HST H with diam(H) = diam(X) and a bijection f : X → H such that for every u, v ∈ X, d_{X}(u, v) ≤ d_{H}(f(u), f(v)) ≤ 2md_{X}(u, v). For n = 1 there is nothing to prove. Assuming n > 1, let x be an m-center of X. Denote Δ = diam(X), and let a, b ∈ X be such that d_{X}(a, b) = Δ. We may assume without loss of generality that d_{X}(x, a) ≥ Δ/2. For every k = 1, …, m, define:

A_{i} = \{y ∈ X; \frac{Δ(i − 1)}{2m} ≤ d_{X}(y, a) < \frac{Δi}{2m}\} .

Now, ∪_{i=1}^{m}A_{i} = B_{X}^{∘}(a, Δ/2) = {y ∈ X; d_{X}(a, y) < Δ/2}. Since X is finite, there is some r < Δ/2 such that B_{X}^{∘}(a, Δ/2) = B_{X}(a, r). But x ∉ B_{X}(a, r), and since x is an m-center of X, it follows that |B_{X}(a, r)| < m. Since the set {A_{i}}_{i=1}^{m} are disjoint, and A_{1} ≠ ∅, it follows that there exists 1 ≤ i ≤ m − 1 for which A_{i+1} = ∅.

Denote B = ∪_{j=1}^{i}A_{j} = B_{X}^{∘}(a, Δi/(2m)). Observe that X \ B has an m-center (namely x), and B has an m-center vacuously (since |B| < m). By the inductive hypothesis there are HSTs H_{1}, H_{2}, defined by trees T_{1}, T_{2}, respectively, such that diam(H_{1}) = diam(B), diam(H_{2}) = diam(X \B), and there are bijections f_{1} : B → H_{1}, f_{2} : X \B → H_{2} which are non-contracting and 2m-Lipschitz. Let r_{1}, r_{2} be the roots of H_{1}, H_{2}, respectively. Let T be the labelled tree T rooted at r such that Δ(r) = diam(X) = Δ, r_{1}, r_{2} are the only children of r, and the subtrees rooted at r_{1}, r_{2} are isomorphic to H_{1}, H_{2}, respectively. Since Δ(r_{1}) = diam(H_{1}) = diam(B) ≤ diam(X), and similarly for r_{2}, T defines a HST on its leaves H = H_{1} ∪ H_{2}. We define f : X → H by f|_{B} = f_{1}, and f|_{X\B} = f_{2}. If u ∈ B and v ∈ X \B then d_{H}(f(u), f(v)) = Δ(r) = Δ ≥ d_{X}(u, v). Furthermore, d_{X}(u, a) < Δi/2m and d_{X}(v, a) ≥ Δ(i + 1)/2m (since A_{i+1} = ∅). Hence:

d_{X}(u, v) ≥ d_{X}(v, a) − d_{X}(u, a) > \frac{Δ}{2m} = \frac{d_{H}(f(u), f(v))}{2m}.

This concludes the proof.

Lemma 3.3 and Lemma 3.7 imply the following corollary:

Corollary 3.8. For every 0 < ε < 1 and every integer n, every n-point metric space M contains a subset A ⊆ M such that |A| ≤ εn and:

c_{UM}(M/A) ≤ \frac{6 log(2/ε)}{ε}.

4 Lower Bounds for Small Distortions

In this section we give lower bounds for Q_{p}(α, n), QS_{p}(α, n), SQ_{p}(α, n) when α ≤ 2. We begin by showing that for distortion α greater than 2^{min{1−1/p,1/p}}, every n-point metric space has a polynomially large Q space which α-embeds in ℓ_{p}. The following combinatorial lemma will be used several times in this section. In what follows, given an integer n ∈ ℕ we use the notation [n] = \{1, …, n\}. We also denote by \binom{[n]}{2} the set of all unordered pairs of distinct integers in [n].

Lemma 4.1. Fix n, k ∈ ℕ, n ≥ 2. For every function χ : \binom{[n]}{2} → [k] there is an integer s ≥ ⌊\frac{n^{1/k}}{8 log n}⌋ and there are disjoint subsets A_{1}, …, A_{s} ⊆ \{1, …, n\} and ℓ ∈ \{1, …, k\} such that for every 1 ≤ i < j ≤ s,

min {χ(p, q); p ∈ A_{i}, q ∈ A_{j}} = ℓ.

Furthermore, for every 1 ≤ i, j ≤ s, i ≠ j, and every p ∈ A_{i}, there exists q ∈ A_{j} such that χ(p, q) = ℓ.

Proof. The proof is by induction on k. For k = 1 there is nothing to prove. Assume that k > 1 and denote m = |\{(i, j); χ(i, j) = 1\}|. Define s = ⌊\frac{n^{1/k}}{8 log n}⌋. We first deal with the case m ≥

\frac{1}{2}n^{1+1/k}. For each i ∈ \{1, …, n\} let B_{i} = \{j; χ(i, j) = 1\}. Denote C = \{i; |B_{i}| ≥ n^{1/k}/4\}. Then:

\frac{n^{1+1/k}}{2} ≤ m = ∑_{i=1}^{n} |B_{i}| ≤ |C|n + (n − |C|)\frac{n^{1/k}}{4} ≤ |C|n + \frac{n^{1+1/k}}{4} ,

i.e. |C| ≥ n^{1/k}/4.

Consider a random partition of C into s subsets A_{1}, …, A_{s}, obtained by assigning to each i ∈ C an integer 1 ≤ j ≤ s uniformly and independently. The partition A_{1}, …, A_{s} satisfies the required result with ℓ = 1 if for every 1 ≤ u ≤ s, every i ∈ A_{u} and every v ≠ u, B_{i} ∩ A_{v} ≠ ∅. The probability that this even doesn’t occur is at most:

∑_{u=1}^{s} ∑_{i∈C} ∑_{v=1}^{s} Pr(i ∈ A_{u}, B_{i} ∩ A_{v} = ∅) = ∑_{u=1}^{s} ∑_{i∈C} ∑_{v=1}^{s} \frac{1}{s} (1 − \frac{1}{s})^{|B_{i}|}

≤ ns (1 − \frac{1}{s})^{n^{1/k}/4}
≤ \frac{n^{1+1/k}}{8 log n} exp (−\frac{n^{1/k}}{4} · \frac{8 log n}{n^{1/k}})
≤ \frac{1}{8 log n} < 1,

so that the required partition exists with positive probability.

It remains to deal with the case m < \frac{1}{2}n^{1+1/k}. In this case consider the set D = \{i; |B_{i}| < n^{1/k}\}. Then \frac{1}{2}n^{1+1/k} > m ≥ n^{1/k}(n − |D|), so that |D| > n/2. Consider the graph on D in which i and j are adjacent if and only if χ(i, j) = 1. By the definition of D, this graph has maximal degree less than n^{1/k}, so that it has an independent set I ⊆ D of size at least |D|/n^{1/k} > \frac{1}{2}n^{1−1/k} (to see this, color D with n^{1/k} colors and take the maximal color class). The fact that I is an independent set means that for i, j ∈ I, χ(i, j) > 1, so that we may apply the inductive hypothesis to I and obtain the desired partition of size at least ⌊\frac{|I|^{1/(k−1)}}{8 log |I|} ⌋. We

may assume that n^{1/k} ≥ 2e, since otherwise the required result is vacuous. In this case the lower bound on |I| implies that we are in the range where the function x ↦ x^{1/(k−1)}/ log x is increasing, in which case:

\frac{|I|^{1/(k−1)}}{8 log |I|} ≥ \frac{(\frac{1}{2}n^{1−1/k})^{1/(k−1)}}{8(1 − 1/k) log n} ≥ \frac{n^{1/k}}{8 log n},

where we have used the inequality (1 − 1/k)2^{1/(k−1)} ≤ 1.

The relevance of Lemma 4.1 to the QS problem is clear. We record below one simple consequence of it. Recall that the aspect ratio of a finite metric space M is defined as:

Φ(M) = \frac{diam(M)}{min_{x≠y} d_{M}(x, y)}.  (3)

Lemma 4.2. Let M be an n-point metric space and 1 < α ≤ 2. Then there is a QS space of M, U, which is α equivalent to an equilateral metric space and:

|U| ≥ ⌊\frac{n^{(log α)/[2 log Φ(M)]}}{8 log n} ⌋ .

Proof. By normalization we may assume that min_{x≠y} d_{M}(x, y) = 1. We may also assume that α < Φ(M). Write Φ = Φ(M) and set k = ⌊\frac{log Φ}{log α}⌋ + 1. For every x, y ∈ M, x ≠ y there is a

unique integer χ(x, y) ∈ [k] such that d_{M}(x, y) ∈ [α^{χ(x,y)−1}, α^{χ(x,y)}). Lemma 4.1 implies that there are disjoint subsets U_{1}, …, U_{s} ⊂ M and an integer ℓ ∈ [k] such that s ≥ ⌊\frac{n^{(log α)/[2 log Φ(M)]}}{8 log n} ⌋

and for every 1 ≤ i < j ≤ s, d_{M}(U_{i}, U_{j}) ∈ [α^{ℓ−1}, α^{ℓ}). Consider the QS space U = {U_{1}, …, U_{s}}, and observe that since α ≤ 2, any minimal geodesic joining U_{i} and U_{j} must contain only two points (namely U_{i} and U_{j}). This implies that U is α-equivalent to an equilateral space.

In what follows we use the following definition:

Definition 4.3. Let M be a finite metric space. For x ∈ M we denote by r_{M}(x) the distance of x to its closest neighbor in M:

r_{M}(x) = d_{M}(x, M \ {x}) = min{d_{M}(x, y); y ∈ M, y ≠ x}.

For 0 < a < b it will be convenient to also introduce the following notation:

M[a, b) = {x ∈ M; a ≤ r_{M}(x) < b} .

For the sake of simplicity, we denote θ(p) = min \{\frac{1}{p}, 1 − \frac{1}{p}\}.

In the following lemma we use the notation introduced in Definition 3.1 in Section 4.

Lemma 4.4. Let M be an n-point metric space. Then there exist two subsets S, T ⊆ M with the following properties:

a) S ∩ T = ∅.

b) |T | ≥ n/4.

c) For every x ∈ T and every subset S ⊆ W ⊆ M \ {x}, d_{M}(x, W) = r_{M}(x).

d) For every A ⊇ M \ T and every x, y ∈ M \ A:

d_{M/A}(x, y) = min{d_{M}(x, y), r_{M}(x) + r_{M}(y)}, d_{M/A}(x, A) = r_{M}(x).

Proof. Choose a random subset S ⊆ M by picking each point independently with probability 1/2. Define:

T = {x ∈ M \ S; d_{M}(x, S) = r_{M}(x)} .

To estimate the expected number of points in T for every x ∈ M denote by N_{x} ⊆ M the set of all points y ∈ M such that r_{M}(x) = d_{M}(x, M \ {x}) = d_{M}(x, y). Then x ∈ T if an only if x ∉ S and N_{x} ∩ S ≠ ∅. These two events are independent and their probability is at least 1/2. Hence 𝔼|T | ≥ n/4. Parts a),b) and c) are now evidently true. Part d) follows from part c) due to (2).

Given an integer n and 0 < τ ≤ 2, we denote by ⋆_{n}^{τ} the metric on {0, 1, …, n} given by d_{⋆_{n}^{τ}}(i, 0) = 1 for 1 ≤ i ≤ n, and d_{⋆_{n}^{τ}}(i, j) = τ for 1 ≤ i < j ≤ 2. The metrics ⋆_{n}^{τ} will also be called star metrics (recall that when τ = 2 we have previously used the notation ⋆_{n} = ⋆_{n}^{2}).

Lemma 4.5. Let M be an n-point metric space, 0 < a < b < 2a and b/a ≤ α ≤ 2b/a. Let S, T ⊆ M be as in Lemma 4.4. Write m = |T ∩ M[a, b)|. Then there is some 0 < τ ≤ \frac{2b}{aα} ≤ 2 and a Q space of M, U, which is α -equivalent to ⋆_{|U|}^{τ} and:

|U| ≥ ⌊\frac{m^{(log α)/6}}{8 log m} ⌋ .

Proof. Consider the set N = T ∩ M[a, b). By definition, for every x, y ∈ N, x ≠ y,

min{d_{M}(x, y), r_{M}(x) + r_{M}(y)} ∈ [a, 2b).

Setting k = ⌈\frac{log(2b/a)}{log α}⌉ − 1, it follows that there is a unique integer χ(x, y) ∈ [0, k] such that

\frac{2b}{α^{χ(x,y)+1}} ≤ min\{d_{M}(x, y), r_{M}(x) + r_{M}(y)\} < \frac{2b}{α^{χ(x,y)}} .  (4)

Denote s = ⌊\frac{m^{1/(k+1)}}{8 log m} ⌋, and apply Lemma 4.1 to get an integer ℓ ∈ [0, k] and disjoint subsets A_{1}, …, A_{s} ⊆ N such that for every 1 ≤ i < j ≤ s:

min{χ(x, y); x ∈ A_{i}, y ∈ A_{j}} = ℓ.

Let U be the Q space of M whose elements are A_{1}, …, A_{s} and A_{0} = M \ ∪_{i=1}^{s}A_{i}. The metric on U is described in the following claim:

Claim 4.6. For every 1 ≤ i ≤ s, d_{U}(A_{i}, A_{0}) ∈ [a, b). Furthermore, for every 1 ≤ i < j ≤ s,

\frac{2b}{α^{ℓ+1}} ≤ d_{U}(A_{i}, A_{j}) ≤ \frac{2b}{α^{ℓ}} .

Proof. By part c) of Lemma 4.4, for every 1 ≤ i ≤ s and every x ∈ A_{i}, d_{M}(x, A_{0}) = r_{M}(x) ∈ [a, b). Moreover, for every 0 ≤ i < j ≤ s, d_{M}(A_{i}, A_{j}) ≥ a. Since 2a > b, this shows that any geodesic in U connecting A_{0} and A_{i} cannot contain more than two elements, i.e. d_{U}(A_{i}, A_{0}) = d_{M}(A_{i}, A_{0}) ∈ [a, b). Now, take any 1 ≤ i < j ≤ s. By (4), d_{M}(A_{i}, A_{j}) ≥ \frac{2b}{α^{ℓ+1}} and:

d_{U}(A_{i}, A_{j}) ≤ min{d_{M}(A_{i}, A_{j}), d_{M}(A_{i}, A_{0}) + d_{M}(A_{j}, A_{0})}
= min_{x∈A_{i}, y∈A_{j}} min\{d_{M}(x, y), r_{M}(x) + r_{M}(y)\} ∈ [\frac{2b}{α^{ℓ+1}} , \frac{2b}{α^{ℓ}} ) .  (5)

Consider a geodesic connecting A_{i} and A_{j}. It is either (A_{i}, A_{j}), (A_{i}, A_{0}, A_{j}) or else it contains either a consecutive pair (A_{u}, A_{v}) for some 1 ≤ u ≤ v ≤ s, u ≠ v, or four consecutive pairs (A_{i}, A_{0}), (A_{0}, A_{u}), (A_{u}, A_{0}), (A_{0}, A_{v}) for some 1 ≤ u, v ≤ s. In the first three cases we get that d_{U}(A_{i}, A_{j}) ≥ \frac{2b}{α^{ℓ+1}} . The fourth case can be ruled out since in this case the length of the geodesic is at least 4a > 2b ≥ \frac{2b}{α^{ℓ}}, which is a contradiction to the upper bound in (5).

Setting τ = \frac{2b}{aα^{ℓ+1}} ≤ 2, it follows from Claim 4.6 that U is α-equivalent to ⋆_{s}^{τ}.

The relevance of the metrics ⋆_{n}^{τ} to the Q problem is that when τ is small enough they isometrically embed into L_{p}:

Lemma 4.7. For every integer n, every 1 ≤ p ≤ ∞ and every 0 < τ ≤ 2^{1−θ(p)}, ⋆_{n}^{τ} isometrically embeds into L_{p}.

Proof. We begin with the case 1 ≤ p ≤ 2. In this case our assumption implies that there exists 0 ≤ δ < 1 such that τ = 2^{1/p}(1 − δ)^{1/p}. Our claim follows from the fact that there are w_{1}, …, w_{n} ∈ L_{p} such that ∥w_{i}∥_{p} = 1 and for i ≠ j, ∥w_{i} − w_{j}∥_{p} = τ. Indeed, if δ = 0 then we can take these vectors to be the first n standard unit vectors in ℓ_{p}. For δ > 0 we take w_{1}, …, w_{s} to be i.i.d. random variables which take the value δ^{−1/p} with probability δ and the value 0 with probability 1 − δ.

The case p > 2 is slightly different. In this case our assumption is that τ ≤ 2^{1−1/p}, so that we may find 0 ≤ δ ≤ 1 such that τ = 2^{1+1/p}[δ(1 − δ)]^{1/p}. We claim that there are w_{1}, …, w_{s} ∈ L_{p} such that ∥w_{i}∥_{p} = 1 and for 1 ≤ i < j ≤ s, ∥w_{i} − w_{j}∥_{p} = τ. Indeed, we can take w_{1}, …, w_{s} to be i.i.d. random variables which take the value +1 with probability δ and the value −1 with probability 1 − δ.

We will require the following definition from [4].

Definition 4.8. Fix k ≥ 1. A metric d on {1, …, n} is called k-lacunary if there is a sequence a_{1} ≥ a_{2} ≥ … ≥ a_{n−1} ≥ 0 such that a_{i+1} ≤ a_{i}/k and for 1 ≤ i < j ≤ n, d(i, j) = a_{i}.

It is clear that k-lacunary spaces are ultrametrics, so that they embed isometrically in Hilbert space.

Proposition 4.9. Let M be an n-point metric space, n ≥ 2. Fix k ≥ 1, 1 < β ≤ 2 and β < α < 2β. Then M has a Q space, U, which is α-equivalent to either a k-lacunary space or a star metric ⋆_{|U|}^{τ} for some 0 < τ ≤ 2/β, and:

|U| ≥ \frac{1}{32 log n} [\frac{n log(α/β)}{max\{log(2k), log[1/(β − 1)]\}}]^{(log α)/6} .

Proof. Let T be as in Lemma 4.4. For every integer i ∈ ℤ set:

C_{i} = \{x ∈ T; (\frac{α}{β})^{i} ≤ r_{M}(x) < (\frac{α}{β})^{i+1}\} = T ∩ M[(α/β)^{i}, (α/β)^{i+1}).

Define m = ⌈\frac{max\{log k,log[1/(β−1)]\}}{log(α/β)}⌉. For every j ∈ \{0, 1, …, m−1\} define D_{j} = ∪_{i≡j mod (m)}C_{i}. Let q be such that |D_{q}| = max_{i∈{0,...,m−1}} |D_{i}|. Then |D_{q}| ≥ |T |/m ≥ n/(4m) + 1.

Set ℓ = |{r ∈ ℤ; C_{q+rm} ≠ ∅}|. There are r_{1} > r_{2} > ⋯ > r_{ℓ} such that C_{q+r_{i}m} ≠ ∅. Fix v_{i} ∈ C_{q+r_{i}m}. Consider the subset A = M \ {v_{1}, …, v_{ℓ}} ⊇ M \ T. By our choice of T:

d_{M/A}(v_{i}, A) = r_{M}(v_{i}) ∈ [(\frac{α}{β})^{q+r_{i}m} , (\frac{α}{β})^{q+r_{i}m+1}) ,

and

d_{M/A}(v_{i}, v_{j}) = min{d_{M}(v_{i}, v_{j}), r_{M}(v_{i}) + r_{M}(v_{j})}.

In particular, since d_{M}(v_{i}, v_{j}) ≥ max{r_{M}(v_{i}), r_{M}(v_{j})},

d_{M/A}(v_{i}, v_{j}) ≥ d_{M}(v_{j}, S) ≥ (\frac{α}{β})^{q+r_{j}m} .

Additionally, for i < j, since r_{i} ≥ r_{j} + 1,

d_{M/A}(v_{i}, v_{j}) ≤ dr_{M}(v_{i}) + r_{M}(v_{j})
≤ (\frac{α}{β})^{q+r_{i}m+1} + (\frac{α}{β})^{q+r_{j}m+1}
≤ (\frac{α}{β})^{q+r_{i}m} \frac{α}{β} [1 + (\frac{β}{α})^{m}]
≤ α (\frac{α}{β})^{q+r_{i}m} ,

by our choice of m. Denote a_{i} = (α/β)^{q+r_{i}m}. Then a_{i+1} ≤ (β/α)^{m}a_{i} ≤ a_{i}/k and we have shown that M/A is α-equivalent to the k-lacunary induced by (a_{i}) on {1, …, ℓ + 1}.

Let r be such that |C_{q+rm}| = max_{i∈ℤ} |C_{q+im}|. Then |C_{q+rm}| ≥ |D_{q}|/ℓ ≥ n/(4mℓ). By Lemma 4.5, M has a Q space V which is α equivalent to ⋆_{|V|}^{τ} for some 0 < τ ≤ 2/β, and:

|V| ≥ \frac{1}{16 log n} (\frac{n}{4mℓ})^{(log α)/6} .

Summarizing, we have proved the existence of the required Q space of M whose cardinality is at least:

min_{ℓ≥1} max \{ℓ, \frac{1}{16 log n} (\frac{n}{4mℓ})^{(log α)/6}\} ,

from which the required result easily follows.

Corollary 4.10. For every 0 < ε < 1 and 1 < p < ∞ there exists a constant c = c(p, ε) > 0 such that for every integer n,

Q_{p}(2^{θ(p)}(1 + ε), n) ≥ cn^{[θ(p)+log(1+ε)]/10}.

Proof. Apply Proposition 4.9 with k = 1, α = 2^{θ(p)}(1 + ε) and β = 2^{θ(p)}. By Lemma 4.7, the resulting Q space is α-equivalent to a subset of L_{p}.

Corollary 4.11. Fix 0 < ε < 1. For every integer n ≥ 2 and every 1 ≤ p ≤ ∞:

SQ_{p}(1 + ε, n) ≥ \frac{n^{ε/12}}{100 log n}.

In fact, for every k ≥ 1, any n-point metric space M has a SQ space U which is 1 + ε embeddable in either a k-lacunary space or an equilateral space, and:

|U| ≥ \frac{1}{100 log n} (\frac{n}{log(2k)})^{ε/12} .

Proof. Apply Proposition 4.9 with α = 1 + ε and β = \sqrt{1 + ε}. If the resulting Q space is a star metric then pass to a SQ space by deleting the root of the star, so that the remaining space is equilateral.

Before passing to the QS problem, we show that for distortion 2 we can obtain proportionally large Q spaces of arbitrary metric spaces.

Lemma 4.12. For every integer n and every 1 ≤ p ≤ ∞, Q_{p}(2, n) ≥ \frac{n}{4} + 1.

Proof. Let M be an n-point metric space and let T be as in Lemma 4.4. Write T = k and consider the Q space M/A, where A = M \ T. We relabel the elements of M/A by writing T = {1, …, k}, A = k + 1, where r_{M}(1) ≥ r_{M}(2) … ≥ r_{M}(k). For every 1 ≤ i ≤ k, d_{M/A}(i, k + 1) = r_{M}(i), and for every 1 ≤ i < j ≤ k:

d_{M/A}(i, j) = min{d_{M}(i, j), r_{M}(i) + r_{M}(j)} ∈ [r_{M}(i), 2r_{M}(i)].

This shows that M/A is 2 equivalent to the 1-lacunary space induced on {1, …, k + 1} by the sequence {r_{M}(i)}_{i=1}^{k}.

As we have seen in the proof Corollary 4.11, the reason why the SQ problem is ”easier” than the Q problem is that we are allowed to discard the ”root” of Q spaces which are approximately stars. This ”easy solution” is not allowed when dealing with the QS problem. The solution of the QS problem for distortions less than 2 is therefore more complicated, and the remainder of this section is devoted to it.

Our approach to the QS problem builds heavily on the techniques and results of [5]. Among other things, as in [5], we will approach the problem by tackling a more general weighted version of the QS problem, which we now introduce.

Definition 4.13. A weighted metric space (M, d_{M}, w) is a metric space (M, d_{M}) with nonnegative weights w : M → [0, ∞). Given A ⊆ M we denote w_{∞}(A) = sup_{x∈A} w(x).

Given two classes of metric spaces M, A, and α ≥ 1 we denote by σ_{A}(M, α) the largest σ ≤ 1 such that any weighted metric space (M, d_{M}, w) ∈ M has a QS space U which is α-embeddable in a member of A and satisfies:

∑_{A∈U} w_{∞}(A)^{σ} ≥ ( ∑_{x∈M} w(x))^{σ} .

When A is the class of all k-HSTs we use the notation σ_{k} = σ_{A}. The case w ≡ 1 shows that lower bounds for σ_{k}(M, α) also imply lower bounds for the QS problem.

Having introduced the weighted QS problem, it is natural that we require a weighted version of Lemma 4.1:

Lemma 4.14. Fix n, k ∈ ℕ, n ≥ 2, a function χ : \binom{[n]}{2} → [k] and a weight function w : [n] → [0, ∞). There are disjoint subsets A_{1}, …, A_{s} ⊆ {1, …, n} and ℓ ∈ {1, …, k} such that for every 1 ≤ i < j ≤ s,

min {χ(p, q); p ∈ A_{i}, q ∈ A_{j}} = ℓ,  (6)

and:

∑_{i=1}^{s} w_{∞}(A_{i})^{1/[8k log(k+1)]} ≥ (∑_{r=1}^{n} w(r))^{1/[8k log(k+1)]} .

Proof. We use the following fact proved in [3]: Let x = {x_{i}}_{i=1}^{∞} be a sequence of non-increasing non-negative real numbers. Then there exists a sequence y = {y_{i}}_{i=1}^{∞} such that y_{i} ≤ x_{i} for all

i ≥ 1, ∑_{i≥1} y_{i}^{1/2} ≥ (∑_{i≥1} x_{i})^{1/2}, and either y_{i} = 0 for all i > 2 or there exits w > 0 such that for all i ≥ 1, y_{i} ∈ {w, 0}. Applying this fact to the weight function w : [n] → [0, ∞) we get in the first case i, j ∈ [n] such that \sqrt{w(i)} + \sqrt{w(j)} ≥ (∑_{r=1}^{n} w(r))^{1/2}, and we take A_{1} = \{i\}, A_{2} = {j}, ℓ = χ(i, j). In the second case we find w > 0 and A ⊆ [n], |A| ≥ 3, such that for i ∈ A w(i) ≥ w and |A|\sqrt{w} ≥ (∑_{r=1}^{n} w(r))^{1/2}. In this case we may apply Lemma 4.1 to A and get an integer ℓ ∈ [k] and disjoint subsets A_{1}, …, A_{s} ⊆ A satisfying (6) and such that s ≥ ⌊\frac{|A|^{1/k}}{8 log |A|}⌋. We can obviously also always ensure that s ≥ 2. Hence, using the elementary

inequality max \{\frac{x^{1/k}}{8 log x}, 2\} ≥ x^{1/[4k log(k+1)]}, valid for all x ≥ 3 and k ≥ 1, we get that:

∑_{i=1}^{s} w_{∞}(A_{i})^{1/[8k log(k+1)]} ≥ (|A|\sqrt{w})^{1/[4k log(k+1)]} ≥ (∑_{r=1}^{n} w(r))^{1/[8k log(k+1)]} .

For Φ ≥ 1 denote by M(Φ) the class of all metric spaces with aspect ratio at most Φ. The class M(1) consists of all equilateral metric spaces, and is denoted by EQ. We have as a corollary the following weighted version of Lemma 4.2:

Corollary 4.15. For every Φ ≥ 2 and 1 ≤ α ≤ 2,

σ_{EQ}(M(Φ), α) ≥ \frac{log α}{16(log Φ) log (\frac{2 log Φ}{log α})}.

We recall below the notion of metric composition, which was used extensively in [5].

Definition 4.16 (Metric Composition [5]). Let M be a finite metric space. Suppose that there is a collection of disjoint finite metric spaces N_{x} associated with the elements x of M. Let N = {N_{x}}_{x∈M}. For β ≥ 1/2, the β-composition of M and N, denoted by C = M_{β}[N], is a metric space on the disjoint union ˙∪_{x}N_{x}. Distances in C are defined as follows. Let x, y ∈ M and u ∈ N_{x}, v ∈ N_{y}, then:

d_{C}(u, v) = \begin{cases}d_{N_{x}}(u, v) & x = y \\ βγd_{M}(x, y) & x ≠ y. \end{cases}

where γ = \frac{max_{z∈M} diam(N_{z})}{min_{x≠y∈M} d_{M} (x,y)}. It is easily checked that the choice of the factor βγ guarantees that d_{C} is indeed a metric.

Definition 4.17 (Composition Closure [5]). Given a class M of finite metric spaces, we consider comp_{β}(M), its closure under ≥ β-compositions. Namely, this is the smallest class C of metric spaces that contains all spaces in M, and satisfies the following condition: Let M ∈ M, and associate with every x ∈ M a metric space N_{x} that is isometric to a space in C. Also, let β′ ≥ β. Then M_{β′}[N] is also in C.

Lemma 4.18. Let M be a class of metric spaces, k ≥ 1, α > 1 and β ≥ αk. Then:

σ_{k}(comp_{β}(M), (1 + 1/β)α) ≥ σ_{k}(M, α),

Proof. Set σ = σ_{k}(M, α) and take X ∈ comp_{β}(M). We will prove that for any w : X → [0, ∞) there exists a QS space Y of X and a k-HST H such that Y is α-equivalent to H via a noncontractive (1 + 1/β)α-Lipschitz embedding, and:

∑_{x∈Y} w(x)^{σ} ≥ (∑_{x∈X} w(x))^{σ} .

The proof is by structural induction on the metric composition. If X ∈ M then this holds by the definition of σ. Otherwise, let M ∈ M and N = {N_{z}}_{z∈M} ⊆ comp_{β}(M) be such that X = M_{β}[N].

For every z ∈ M define w′(z) = ∑_{u∈N_{z}} w(u). By the definition of σ there are disjoint subsets U_{1}, …, U_{s} ⊆ M such that the QS space of M, U = {U_{1}, …, U_{s}}, is α-equivalent to a k-HST H_{M}, defined by the tree T_{M}, via a non-contractive α-Lipschitz embedding, and:

∑_{i=1}^{s} w′_{∞}(U_{i})^{σ} ≥ ( ∑_{z∈M} w′(z))^{σ} = (∑_{x∈X} w(x))^{σ} .

By induction for each z ∈ M there are disjoint subsets U_{1}^{z}, …, U_{s(z)}^{z} ⊆ N_{z} such that the QS space of N_{z}, U_{z} = {U_{1}^{z}, …, U_{s(z)}^{z}} is (1 + 1/β)α-equivalent to a k-HST, H_{z}, defined by the tree T_{z}, via a non-contractive (1 + 1/β)α-Lipschitz embedding, and:

∑_{i=1}^{s(z)} w_{∞}(U_{i}^{z})^{σ} ≥ ( ∑_{u∈N_{z}} w(u))^{σ} .

For every 1 ≤ i ≤ s let z_{i} ∈ M be such that w′(z_{i}) = w′_{∞}(U_{i}). Define V_{1}^{z_{i}}, …, V_{s(z_{i})}^{z_{i}} ⊆ X by:

V_{1}^{z_{i}} = U_{1}^{z_{i}} ⋃ ( ⋃_{z∈U_{i}\{z_{i}}} N_{z})  and  V_{j}^{z_{i}} = U_{j}^{z_{i}} for j = 2, 3, …, s(z_{i}).

Consider the QS space of X: V = {V_{j}^{z_{i}}; i = 1, …, s j = 1, …, s(z_{i})}. First of all:

∑_{A∈V} w_{∞}(A)^{σ} = ∑_{i=1}^{s} ∑_{j=1}^{s(z_{i})} [ max_{x∈V_{j}^{z_{i}}} w(x)]^{σ} ≥ ∑_{i=1}^{s} ∑_{j=1}^{s(z_{i})} [ max_{x∈U_{j}^{z_{i}}} w(x)]^{σ}

≥ ∑_{i=1}^{s} ( ∑_{u∈N_{z_{i}}} w(u))^{σ} = ∑_{i=1}^{s} w′(N_{z_{i}})^{σ} = ∑_{i=1}^{s} w′_{∞}(U_{i})^{σ} ≥ (∑_{x∈X} w(x))^{σ} .

Therefore, all that remains is to show that V is (1 + 1/β)α-equivalent to a k-HST via a noncontractive, (1 + 1/β)α-Lipschitz embedding. For this purpose we first describe the metric on V:

Claim 4.19. For every 1 ≤ i ≤ s and every 1 ≤ p < q ≤ s(z_{i}),

d_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}) = d_{U_{z_{i}}} (U_{p}^{z_{i}}, U_{q}^{z_{i}}).  (7)

Furthermore, for every 1 ≤ i < j ≤ s and every 1 ≤ p ≤ s(z_{i}), 1 ≤ q ≤ s(z_{j}):

βγd_{U}(U_{i}, U_{j}) ≤ d_{V}(V_{p}^{z_{i}}, V_{q}^{z_{j}}) ≤ (β + 1)γd_{U}(U_{i}, U_{j}).  (8)

Proof. By the definition of metric composition, if z ≠ z_{i}, u ∈ N_{z_{i}}, v ∈ N_{z}, then d_{X}(u, v) ≥ β diam(N_{z_{i}}) > diam(N(z_{i})). Since for every 1 ≤ j ≤ s(z_{i}), N_{z_{i}} ∩ V_{j}^{z_{i}} = U_{j}^{z_{i}}, this implies that d_{X}(V_{p}^{z_{i}}, V_{q}^{z_{i}}) = d_{N_{z_{i}}} (U_{p}^{z_{i}}, U_{q}^{z_{i}}). In particular, it follows that d_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}) ≤ d_{U_{z_{i}}} (U_{p}^{z_{i}}, U_{q}^{z_{i}}) ≤ diam(N_{z_{i}}). A geodesic connecting V_{p}^{z_{i}} and V_{q}^{z_{i}} in V cannot go out of {V_{1}^{z_{i}}, …, V_{s(z_{i})}^{z_{i}}}, since by the above observation it would contain a step of length greater that diam(N_{z_{i}}). This concludes the proof of (7).

Next take 1 ≤ i, j ≤ s and 1 ≤ p ≤ s(z_{i}), 1 ≤ q ≤ s(z_{j}) and observe that d_{X}(V_{p}^{z_{i}}, V_{q}^{z_{j}}) ≥ βγd_{M}(U_{i}, U_{j}). Indeed, if i = j there is nothing to prove, and if i ≠ j then this follows from the definition of metric composition and the fact that V_{p}^{z_{i}} ⊆ ∪_{z∈U_{i}}N_{z} and V_{p}^{z_{j}} ⊆ ∪_{z∈U_{j}}N_{z}. This observation implies the left-hand side inequality in (8).

To prove the right-hand side inequality in (8), take a geodesic U_{i} = W_{0}, W_{1}, …, W_{m} = U_{j} ∈ U such that m is minimal. This implies that W_{r} ≠ W_{r−1} for all r, and:

d_{U}(U_{i}, U_{j}) = ∑_{r=1}^{m} d_{M}(W_{r−1}, W_{r}),

Let a_{r} ∈ W_{r−1}, b_{r} ∈ W_{r} be such that d_{M}(a_{r}, b_{r}) = d_{M}(W_{r−1}, W_{r}). By construction, for each r there are A_{r}, B_{r} ∈ V such that A_{r} ⊆ N_{a_{r}} and B_{r} ⊆ N_{b_{r}}. Consider the following path in V connecting V_{p}^{z_{i}} and V_{q}^{z_{j}}: Γ = (V_{p}^{z_{i}}, A_{1}, B_{1}, A_{2}, B_{2}, …, A_{m}, B_{m}, V_{q}^{z_{j}}). Observe that since V_{p}^{z_{i}}, A_{1} contain points from N_{z_{i}} and A_{1}, B_{1} do not contain points from a common N_{z}, the definition of metric composition implies that d_{X}(A_{1}, B_{1}) ≥ βd_{X}(V_{p}^{z_{i}}, A_{1}). In other words, d_{X}(V_{p}^{z_{i}}, A_{1}) + d_{X}(A_{1}, B_{1}) ≤ (1 + 1/β)d_{X}(A_{1}, B_{1}) = (β + 1)γd_{M}(W_{0}, W_{1}). Similarly, for r ≥ 2, d_{X}(B_{r−1}, A_{r})+d_{X}(A_{r}, B_{r}) ≤ (β +1)γd_{M}(W_{r−1}, W_{r}) and d_{X}(A_{m}, B_{m})+d_{X}(B_{m}, V_{q}^{z_{j}}) ≤ (β + 1)γd_{M}(A_{m}, B_{m}). Hence, the length of Γ is at most (β + 1)γd_{U}(U_{i}, U_{j}), as required.

We now construct H a k-HST that is defined by a tree T, as follows. Start with a tree T′ that is isomorphic to T_{M} and has labels Δ(u) = (β + 1)γ · Δ_{T_{M}} (u). At each leaf of the tree corresponding to a point U_{i} ∈ U, create a labelled subtree rooted at U_{i} that is isomorphic to T_{z_{i}} with labels as in T_{z_{i}}. Denote the resulting tree by T. Since we have a non-contractive (1 + 1/β)α-embedding of Y_{z_{i}} in H_{z_{i}}, it follows that Δ(z_{i}) = diam(H_{z_{i}}) ≤ (1 + 1/β)α diam(Y_{z_{i}}) ≤ (1 + 1/β)α diam(N_{z_{i}}). Let p be a parent of U_{i} in T_{M}. Since we have a non-contractive α-embedding of U in H_{M} it follows that Δ_{T_{M}} (p) ≥ d_{M}(A, B) for some A, B ∈ U. Therefore Δ(p) ≥ (β + 1)γ · min{d_{M}(x, y); x ≠ y ∈ M}. Consequently, Δ(p)/Δ(z) ≥ (β + 1)/[(1 + 1/β)α] ≥ k, by our restriction on β. Since H_{M} and H_{z_{i}} are k-HSTs, it follows that T also defines a k-HST.

It is left to show that V is α-equivalent to H. Recall that for each z ∈ M there is a noncontractive Lipschitz bijection f_{z} : U_{z} → H_{z} that satisfies for every A, B ∈ U_{z}, d_{U_{z}}(A, B) ≤ d_{H_{z}}(f_{z}(A), f_{z}(B)) ≤ αd_{U_{z}}(A, B). Define f : V → H by f(V_{j}^{z_{i}}) = f_{z_{i}}(U_{j}^{z_{i}}). Then, by Claim 4.19 for every 1 ≤ p < q ≤ s(z_{i}):

d_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}) = d_{U_{z_{i}}} (U_{p}^{z_{i}}, U_{q}^{z_{i}})
≤ d_{H_{z_{i}}} (f_{z_{i}}(U_{p}^{z_{i}}), f_{z_{i}}(U_{q}^{z_{i}})) = d_{H}(f(V_{p}^{z_{i}}), f(V_{q}^{z_{i}}))
≤ (1 + 1/β)αd_{U_{z_{i}}} (U_{p}^{z_{i}}, U_{q}^{z_{i}}) = (1 + 1/β)αd_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}).

Additionally, we have a non-contractive Lipschitz bijection f_{M} : U → H_{M} that satisfies for every U_{i}, U_{j} ∈ U, d_{U}(U_{i}, U_{j}) ≤ d_{H_{M}} (f_{M}(U_{i}), f_{M}(U_{j})) ≤ αd_{U}(U_{i}, U_{j}). Hence, by Claim 4.19, for every 1 ≤ i < j ≤ s and every 1 ≤ p ≤ s(z_{i}), 1 ≤ q ≤ s(z_{j}):

d_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}) ≤ (β + 1)γd_{U}(U_{i}, U_{j})
≤ (β + 1)γd_{H_{M}} (f_{M}(U_{i}), f_{M}(U_{j})) = d_{H}(f(V_{p}^{z_{i}}), f(V_{q}^{z_{j}}))
≤ α(β + 1)γd_{U}(U_{i}, U_{j}) ≤ (1 + 1/β)αd_{V}(V_{p}^{z_{i}}, V_{q}^{z_{i}}).

The proof of Lemma 4.18 is complete.

We will also require the following two results from from [5]:

Lemma 4.20 ([5]). For any α, β ≥ 1, if a metric space M is α-equivalent to a αβ-HST, then M is (1 + 2/β)-equivalent to a metric space in comp_{β}(M(α)).

Theorem 4.21 ([5]). There exists a universal constant c > 0 such that for every 0 < ε ≤ 1 and k ≥ 1 every n-point metric space M contains a subset N ⊆ M which (2 + ε)-embeds into a k-HST and:

|N| ≥ n^{\frac{cε}{log(2k/ε)}} .

We are now in position to present the announced lower bound for the QS problem for small distortion:

Proposition 4.22. There exists a universal constant C > 0 such that whenever M is an n-point metric space and 0 < ε ≤ 1/2, there is a QS space of M, U, which is (1+ε)-equivalent to a 1/ε-HST and:

|U| ≥ n^{\frac{Cε}{[log(1/ε)]^{2}}} .

In particular, for every 1 ≤ p ≤ ∞:

QS_{p}(1 + ε, n) ≥ n^{\frac{Cε}{[log(1/ε)]^{2}}} .

Proof. Fix k ≥ 8 which will be specified later. By Theorem 4.21, M contains a subset N which is 4-equivalent to a k-HST and |N| ≥ n^{c/ log(2k)}. By Lemma 4.20, N is (1 + 8/k)-equivalent to a metric space in comp_{k/4}(M(4)). By Corollary 4.15,

σ_{EQ} (M(4), 1 + \frac{1}{k} ) ≥ \frac{c′}{k log k} ,

for some absolute constant c′. By Lemma 4.18,

σ_{k/8} (comp_{k/4}(M(4)), (1 + \frac{4}{k} ) (1 + \frac{1}{k} )) ≥ σ_{k/8} (M(4), 1 + \frac{1}{k} )
≥ σ_{EQ} (M(4), 1 + \frac{1}{k} ) ≥ \frac{c′}{k log k} .

Since N is (1 + 8/k)-equivalent to a metric space in comp_{k/4}(M(4)), it follows that it has a QS space U which is (1 + 8/k)(1 + 4/k)(1 + 1/k) ≤ 1 + 20/k equivalent to a k/8-HST, and:

|U| ≥ |N|^{c′/(k log k)} ≥ n^{c′′/[k(log k)^{2}]},

where c′′ is an absolute constant. Taking k = 20/ε concludes the proof.

5 The QS Problem for the Hypercube

For every integer d ≥ 1 denote Ω_{d} = {0, 1}^{d}, equipped with the Hamming (ℓ_{1}) metric. Our goal in this section is to prove Theorem 1.11, stated in the introduction. As proved by P. Enflo in [16], for 1 ≤ p ≤ 2, c_{p}(Ω_{d}) = d^{1−1/p}. For 2 ≤ p < ∞ it was shown in [22] that there is a constant a(p) > 0 such that for all d, c_{p}(Ω_{d}) ≥ a(p)\sqrt{d}. The following lemma complements these lower bounds:

Lemma 5.1. For every 1 ≤ p < ∞ there is an absolute constant c = c(p) > 0 such that for every integer d ≥ 1 and every 2^{−d} ≤ ε < 1/4, if U is a QS space of Ω_{d} such that |U| > (1−ε)2^{d} then for 1 ≤ p ≤ 2:

c_{p}(U) ≥ c [\frac{log(1/ε)}{1 + log (\frac{d}{log(1/ε)})}]^{min\{1− \frac{1}{p} , \frac{1}{2} \}} .

Proof. By adjusting the value of c, we may assume that that ε < d^{−50}. In this case, if we set:

r = \frac{1}{16} ⌊\frac{log(1/ε)}{log (\frac{d}{log(1/ε)})}⌋ ,

then 3 ≤ r < d/2. The ball of radius 2r in Ω_{d} contains \binom{d}{2r} ≤ (\frac{ed}{2r})^{2r} ≤ e^{4r log(d/r)} points. Therefore, the cube Ω_{d} contains at least 2^{d} · e^{−4r log(d/r)} disjoint balls of radius r. We may assume that ε ≥ e^{−d/70}, since we may once more adjust the constant c, if necessary. Hence, writing x = d/ log(1/ε) we have 16x log x ≤ x^{2}, so that 4r log(d/r) ≤ \frac{1}{4} log(1/ε) · \frac{log[16x log x]}{log x} ≤ log[1/(2ε)]. This reasoning shows that Ω_{d} contains at least 2ε2^{d} disjoint balls of radius r.

Let U = {U_{1}, …, U_{k}} be a QS space of Ω_{d} with k > (1 − ε)2^{d}. As in the proof of Lemma 2.1, U must contain more than (1 − 2ε)2^{d} singletons. Since Ω_{d} contains at least 2ε2^{d} disjoint balls of radius r, it follows that U must contain the elements of some ball B of radius r as singletons. Let x be the center of B. Write k = ⌊\frac{r}{3}⌋ and consider the subcube C = {0, 1}^{k} × {x_{k+1}} × ⋯ × {x_{d}}. Observe that C ⊆ B, and the diameter of C is at most 2r/3. Moreover, since U contains the elements of B as singletons, the distance in Ω_{d} between an element of C and a non-singleton element of U is at least 2r/3. This shows that when calculating the geodesic distance in U between two points in C, it is enough to restrict ourselves to paths which pass only through singletons. It follows that the metric induced by U on C coincides with the Hamming metric. By the results of [16] and [22], it follows that c_{p}(U) ≥ c_{p}(C) ≥ a(p)k^{min{1−1/p,1/2}}, for some constant a(p) depending only on p. This completes the proof.

We now turn our attention to the construction of large QS spaces of the hypercube which well embed into ℓ_{p}. Our proof yields several embedding results which may be useful in other circumstances. The case p = 2 is simpler, so deal with it first.

Given a metric space M and D > 0, we denote by M^{≤D} the metric space (M, d_{M^{≤D}}), where d_{M^{≤D}}(x, y) = min{d_{M}(x, y), D}.

Lemma 5.2. For every D > 0, c_{2}(ℓ_{2}^{≤D}) ≤ \sqrt{\frac{e}{e−1}}. In fact, ℓ_{2}^{≤D} \sqrt{\frac{e}{e−1}}-embeds into the ℓ_{2}- sphere of radius D.

Proof. Let {g_{i}}_{i=1}^{∞} i.i.d. standard Gaussian random variables. Assume that they are defined on some probability space Ω. Consider the Hilbert space H = L_{2}(Ω) where we think of L_{2}(Ω) as all the complex valued square integrable functions on Ω. Define F : ℓ_{2} → H by:

F (x_{1}, x_{2}, …) = D exp (\frac{i}{D} ∑_{j=1}^{∞} x_{j}g_{j}) .

Clearly ∥F (x)∥_{2} = D for every x ∈ ℓ_{2}. Observe that for every x, y ∈ ℓ_{2},

|F (x) − F (y)|^{2} =
= D^{2} |exp (\frac{i}{D} ∑_{j=1}^{∞} x_{j}g_{j}) − exp (\frac{i}{D} ∑_{j=1}^{∞} y_{j}g_{j})|^{2}

= D^{2} |exp (\frac{i}{D} ∑_{j=1}^{∞} y_{j}g_{j}) [exp (\frac{i}{D} ∑_{j=1}^{∞}(x_{j} − y_{j})g_{j}) − 1]|^{2}

= D^{2} |exp (\frac{i}{D} ∑_{j=1}^{∞}(x_{j} − y_{j})g_{j}) − 1|^{2}

= 2D^{2} [1 − cos (\frac{1}{D} ∑_{j=1}^{∞}(x_{j} − y_{j})g_{j})] .

Now, ∑_{i=1}^{∞}(x_{j} − y_{j})g_{j} has the same distribution as g_{1}\sqrt{∑_{j=1}^{∞}(x_{j} − y_{j})^{2}}. Hence:

𝔼|F (x) − F (y)|^{2} = 2D^{2} [1 − 𝔼 cos (\frac{g_{1}}{D} ∥x − y∥_{2})] .

Observe that by symmetry, 𝔼 sin (\frac{g_{1}}{D} ∥x − y∥_{2}) = 0, so that:

𝔼 cos (\frac{g_{1}}{D} ∥x − y∥_{2}) = 𝔼 exp (i\frac{g_{1}}{D} ∥x − y∥_{2}) = exp (−\frac{∥x − y∥_{2}^{2}}{2D^{2}} ) ,

where we use the fact that 𝔼e^{iag_{1}} = e^{−a^{2}/2}.

Putting it all together, we have shown that:

∥F (x) − F (y)∥_{2} = \sqrt{2}D\sqrt{1 − e^{− \frac{∥x−y∥^{2}_{2}}{2D^{2}}}} .

Using the elementary inequality:

\frac{e − 1}{e} min\{1, a\} ≤ 1 − e^{−a} ≤ min\{1, a\} a > 0,

we deduce that:

\sqrt{\frac{e − 1}{e}} min\{D, ∥x − y∥_{2}\} ≤ ∥F (x) − F (y)∥_{2} ≤ min\{D, ∥x − y∥_{2}\}.

Remark 5.3. Lemma 5.2 cannot be replaced by an isometric result. In fact, for every D > 0,

c_{2}(ℓ_{2}^{≤D}) ≥ \frac{2\sqrt{5 − \sqrt{7}}}{3} > 1.02.

To see this let T : ℝ^{2} → ℓ_{2} be such that for every x, y ∈ ℝ^{2}, min{∥x − y∥_{2}, D} ≤ ∥T (x) − T (y)∥_{2} ≤ A min{∥x − y∥_{2}, D}. It is straightforward to verify that when viewed as a subset of ℓ_{2}^{≤D}, the points {(0, 0), (D, 0), (D/2, D), (D/2, 0)} cannot be isometrically embedded in Hilbert space. To lower-bound the distortion, define a = T (0, 0), b = T (D, 0), c = T (D/2, D), d = T (D/2, 0). By the parallelogram identity:

\frac{D^{2}A^{2}}{2} ≥ ∥a − d∥_{2}^{2} + ∥b − d∥_{2}^{2} = \frac{∥a + b − 2d∥_{2}^{2} + ∥a − b∥_{2}^{2}}{2} ≥ 2 ∥\frac{a + b}{2} − d∥_{2}^{2} + \frac{D^{2}}{2} .

Hence:

∥\frac{a + b}{2} − d∥_{2} ≤ \frac{D\sqrt{A^{2} − 1}}{2}.

Similarly:

2D^{2}A^{2} ≥ ∥a − c∥_{2}^{2} + ∥b − c∥_{2}^{2} = \frac{∥a + b − 2c∥_{2}^{2} + ∥a − b∥_{2}^{2}}{2} ≥ 2 ∥\frac{a + b}{2} − c∥_{2}^{2} + \frac{D^{2}}{2} ,

or

∥\frac{a + b}{2} − c∥_{2} ≤ \frac{D\sqrt{4A^{2} − 1}}{2}.

But:

D ≤ ∥c − d∥_{2} ≤ ∥\frac{a + b}{2} − d∥_{2} + ∥\frac{a + b}{2} − c∥_{2} ≤ \frac{D\sqrt{A^{2} − 1}}{2} + \frac{D\sqrt{4A^{2} − 1}}{2},

which simplifies to give the required result.

Remark 5.4. Let ω : [0, ∞) → [0, ∞) be a concave non-decreasing function such that ω(0) = 0 and ω(t) > 0 for t > 0. It is straightforward to verify that if we define for x, y ∈ ℓ_{2}, d_{ω}(x, y) = ω(∥x − y∥_{2}), then d_{ω} is a metric. Lemma 5.2 dealt with the case ω(t) = min{t, D}, but we claim that in fact there is a constant C > 0 such that for every such ω, c_{2}(ℓ_{2}, d_{ω}) ≤ C. To see this observe that ϕ(t) = ω (\sqrt{t})^{2} is still concave and non-decreasing (assume by approximation that ω is differentiable and observe that ϕ′(t^{2}) = ω′(t)ω(t)/t. By our assumptions, both ω′(t) and ω(t)/t are non-negative and non-increasing, so that the required result follows). Now, it is well known (see for example Proposition 3.2.6. in [13]) that we may therefore write ϕ(t) ≈ ∑_{i=1}^{∞} min{λ_{i}, μ_{i}t} for some λ_{i}, μ_{i} > 0, where the symbol ≈ means that the two functions are equivalent up to absolute multiplicative constants. By Lemma 5.2, for every i there is a function F_{i} : ℓ_{2} → ℓ_{2} such that for every x, y ∈ ℓ_{2} ∥F_{i}(x) − F_{i}(y)∥_{2} ≈ min\{\sqrt{λ_{i}}, \sqrt{μ_{i}}∥x − y∥_{2}\}. Define F : ℓ_{2} → ℓ_{2}(L_{2}) by setting the i’th coordinate of F to be F_{i}. Then for every x, y ∈ ℓ_{2}:

∥F (x)−F (y)∥_{2}^{2} = ∑_{i=1}^{∞} ∥F_{i}(x)−F_{i}(y)∥_{2}^{2} ≈ ∑_{i=1}^{∞} min{λ_{i}, μ_{i}∥x−y∥_{2}^{2}} ≈ ϕ(∥x−y∥_{2}^{2}) = ω(∥x−y∥_{2})^{2}.

Lemma 5.5. Let X be a metric space such that min_{x≠y} d_{X}(x, y) ≥ 1 and the metric space

(X, \sqrt{d_{X}}) is isometric to a subset of ℓ_{2}. Then for every D ≥ 1, c_{2}(X^{≤D}) ≤ \sqrt{\frac{eD}{e−1}}. Moreover,

exists a 1-Lipschitz embedding f : X^{≤D} → ℓ_{2} such that dist(f) ≤ \sqrt{\frac{eD}{e−1}} and for every x ∈ X,

∥f(x)∥_{2} = \sqrt{D}.

Proof. All we have to do is to observe that for every x, y ∈ X,

min\{\sqrt{D}, \sqrt{d_{X}(x, y)}\} ≤ min\{D, d_{X}(x, y)\} ≤ \sqrt{D} · min\{\sqrt{D}, \sqrt{d_{X}(x, y)}\},

and then apply Lemma 5.2.

Corollary 5.6. For every integer d ≥ 1, c_{2}(Ω_{d}^{≤D}) ≤ \sqrt{\frac{eD}{e−1}}, where the embedding is 1-Lipschitz

and takes values in the ℓ_{2}-sphere of radius \sqrt{D}.

Proof. This follows from Lemma 5.5 and the classical fact [23] that ℓ_{1} equipped with the metric \sqrt{∥x − y∥_{1}} is isometric to a subset of ℓ_{2}.

Lemma 5.7. There is a universal constant C > 0 such that for every integer d ≥ 1 and every 2^{−d} ≤ ε < 1/4 there exists a QS space of Ω_{d}, U, such that |U| ≥ (1 − ε)2^{d} and:

c_{2}(U) ≤ C\sqrt{\frac{log(1/ε)}{1 + log (\frac{d}{log(1/ε)})}}.

Proof. By adjusting the constant C, we may assume that ε ≥ e^{−d/400}. Define r to be the smallest even integer greater than:

2 ⌈\frac{log(1/ε)}{log (\frac{d}{log(1/ε)})}⌉ .

We first construct a subset A ⊆ Ω_{d} via the following iterative procedure: Pick any x_{1} ∈ Ω_{d}. Having chosen x_{1}, …, x_{k−1}, as long as Ω_{d} \ ∪_{j=1}^{k−1}B_{Ω_{d}}(x_{j}, 2r) ≠ ∅, pick any x_{i} ∈ Ω_{d} \ ∪_{j=1}^{k−1}B_{Ω_{d}}(x_{j}, 2r). When this procedure terminates we set A = {x_{1}, x_{2}, …}.

Define S ⊆ Ω_{d} by:

S = Ω_{d} \ ( ⋃_{x∈A} B_{Ω_{d}}(x, r/2) \ {x}) .

The QS space of Ω_{d} which we consider is U = S/A.

We first bound the cardinality of U from below. Observe that by the construction, the balls \{B_{Ω_{d}}(x, r)\}_{x∈A} are disjoint, so that |A|\binom{d}{r} ≤ 2^{d}. Hence:

|U| = 2^{d} − |A| · \binom{d}{r/2} + 1 > (1 − \begin{matrix}( & {d \atop r/2} & ) \\ ( & {d \atop r} & ) \end{matrix}) 2^{d} ≥ (1 − ^{\begin{matrix}(\frac{ed}{r/2}) & r/2 \\ (\frac{d}{r}) & r \end{matrix}} ) 2^{d} = (1 − e^{− \frac{r}{2} log(\frac{d}{2er})}) 2^{d}.

By our choice of r, and the restriction ε ≥ e^{−d/400}, it is straightforward to verify that e^{− \frac{r}{2} log(\frac{d}{2er})} ≤ ε. We have shown that |U| ≥ (1 − ε)2^{d}.

By our construction, for every x ∈ S \A, r/2 ≤ d_{Ω_{d}}(x, A) ≤ 2r. This implies that for every x, y ∈ U \ {A},

min{d_{Ω_{d}}(x, y), r} ≤ d_{U}(x, y) ≤ min{d_{Ω_{d}}(x, y), 4r}.

By Corollary 5.6 there is an embedding f : U \ {A} → ℓ_{2} such that for every x ∈ U \ {A}, ∥f(x)∥_{2} = \sqrt{r} and for every x, y ∈ U \ \{A\}:

\sqrt{\frac{e − 1}{16er}} · d_{U}(x, y) ≤ ∥f(x) − f(y)∥_{2} ≤ d_{U}(x, y).

Since for every x ∈ U \ {A}, r/2 ≤ d_{U}(x, A) ≤ 2r, we may extend f to U by setting f(A) = 0. As f takes values in the ℓ_{2}-sphere of radius \sqrt{r}, dist(f) = O(\sqrt{r}), as required.

Since ℓ_{2} embeds isometrically into L_{p}, p ≥ 1, Lemma 5.7 implies that Lemma 5.1 is optimal (up to the dependence of the constant on p) for p ≥ 2. The case 1 ≤ p ≤ 2 seems to be more delicate, but we can still match the bound in Lemma 5.1 up to logarithmic factors.

Recall that for 1 ≤ p ≤ 2 the exists a symmetric p-stable random variable g. This means that there exists a constant c = c(p) > 0 such that for every t ∈ ℝ, 𝔼e^{itg} = e^{−c|t|^{p}}. In what follows we fix 1 ≤ p < 2 and ignore the dependence of all the constants on p. Moreover, given two quantities A, B the notation A ≈_{p} B means that there are constants C_{1}, C_{2}, which may depend only on p, such that C_{1}A ≤ B ≤ C_{2}A. Denote the density of g by φ. It is well known (see [24]) that φ(t) ≈_{p} \frac{1}{1+t^{p+1}} .

Lemma 5.8. Fix 1 ≤ p < 2 and let g be a symmetric p-stable random variable. Then for every a > 0,

𝔼 [1 − cos(ag)]^{p/2} ≈_{p} min \{a^{p} log (\frac{1}{a} + 1) , 1\} .

Proof. Since for 0 ≤ x ≤ 1, 1 − cos x ≈ x^{2}, we have that:

𝔼 [1 − cos(ag)]^{p/2} = 2 ∫_{0}^{∞} [1 − cos(au)]^{p/2} φ(u)du
≈_{p} ∫_{0}^{1/a} \frac{a^{p}u^{p}}{1 + u^{p+1}} du + ∫_{1/a}^{∞} \frac{1}{1 + u^{p+1}} du ≈_{p} min \{a^{p} log (\frac{1}{a} + 1) , 1\} .

The following lemma is analogous to Lemma 5.2:

Lemma 5.9. For every 1 ≤ p < 2 and every D > 0 there exists a mapping F : ℓ_{p} → L_{p} such that for every x ∈ ℓ_{p}, ∥F (x)∥_{p} = D and for every x, y ∈ ℓ_{p},

∥F (x) − F (y)∥_{p} ≈_{p} min \{∥x − y∥_{p} [log (\frac{D}{∥x − y∥_{p}} + 1)]^{1/p} , D\} .

Proof. Let {g_{i}}_{i=1}^{∞} i.i.d. symmetric p-stable random variables. Assume that they are defined on some probability space Ω. Consider the space L_{p}(Ω), where we think of L_{p}(Ω) as all the complex valued p-integrable functions on Ω. Define F : ℓ_{p} → H by:

F (x_{1}, x_{2}, …) = D exp (\frac{i}{D} ∑_{j=1}^{∞} x_{j}g_{j}) .

Clearly ∥F (x)∥_{p} = D for every x ∈ ℓ_{p}. As we have seen in the proof of Lemma 5.2, for x, y ∈ ℓ_{p}:

|F (x) − F (y)|^{p} = 2^{p}D^{p} [1 − cos (\frac{1}{D} ∑_{j=1}^{∞}(x_{j} − y_{j})g_{j})]^{p/2} .

Now, ∑_{i=1}^{∞}(x_{j} − y_{j})g_{j} has the same distribution as g_{1}∥x − y∥_{p}. Hence by Lemma 5.8:

𝔼|F (x) − F (y)|^{p} = 2^{p}D^{p}𝔼 [1 − cos (\frac{g_{1}}{D} ∥x − y∥_{p})]^{p/2}
≈_{p} D^{p} min \{\frac{∥x − y∥_{p}^{p}}{D^{p}} log (\frac{D}{∥x − y∥_{p}} + 1) , 1\} .

Remark 5.10. The above argument also shows that for every 1 ≤ q < p ≤ 2 there is a constant C = C(p, q) such that for every D > 0, ℓ_{p}^{≤D} is C-equivalent to a subset of L_{q} (since in this case there is no logarithmic term in Lemma 5.8). For every 1 ≤ q < p ≤ 2, the metric space (L_{q}, ∥x − y∥_{q}^{q/p}) is isometric to a subset of L_{p}. When p ≤ 2 this follows from general results of Bretagnolle, Dacunha-Castelle and Krivine [12] (see also the book [23]). It is of interest, however, to give a concrete formula for this embedding, which works for every 1 ≤ q < p < ∞. To this end observe that by a change of variable it follows that for every 0 < α < 2β there exists a constant c_{α,β} > 0 such that for every x ∈ ℝ, |x|^{α} = c_{α,β} ∫_{−∞}^{∞} \frac{(1−cos tx)^{β}}{|t|^{α+1}} dt. Define

T : L_{q}(ℝ) → L_{p}(ℝ × ℝ) by T (f)(s, t) = \frac{1−e^{itf(s)}}{|t|^{(q+1)/p}}. For every f, g ∈ L_{p}(ℝ) we have:

∥T (f) − T (g)∥_{p}^{p} = ∫_{−∞}^{∞} ∫_{−∞}^{∞} \frac{|1 − e^{it[f(s)−g(s)]}|^{p}}{|t|^{q+1}} dtds
= 2^{p/2} ∫_{−∞}^{∞} ∫_{−∞}^{∞} \frac{\{1 − cos[t(f(s) − g(s))]\}^{p/2}}{|t|^{q+1}} dtds = 2^{p/2}c_{q+1,p/2}∥f − g∥_{q}^{q},

so that T is the required isometry.

A corollary of these observations is that for every ε > 0 there is a constant C(ε) > 0 such that for every D > 0 the metric min{∥x − y∥_{p}^{1−ε}, D} on ℓ_{p}, 1 ≤ p ≤ 2, is C(ε)-equivalent to a subset of L_{p}. We do not know whether the exponent 1 − ε can be removed in this statement.

Remark 5.11. The same reasoning as in Remark 5.4 shows that for every ω : [0, ∞) → [0, ∞) which is concave, non-decreasing, ω(0) = 0 and ω(t) > 0 for t > 0, the metric ω(∥x − y∥_{p}) on ℓ_{p} is c(p, q)-equivalent to a subset of L_{q} for every 1 ≤ q < p ≤ 2. The only difference in the proof is that one should apply the same argument to show that ϕ(t) = ω(t^{1/q})^{q} shares the same properties as ω. Similarly, the metric ω(∥x − y∥_{p}^{1−ε}) is C(ε)-equivalent to a subset of L_{p}.

Remark 5.12. Remark 5.10 is false for p > 2. In fact, for every 0 < γ ≤ 1, and D > 0, the metric min{∥x − y∥_{p}^{γ}, D} is not Lipschitz equivalent to a subset of L_{q} for any 1 ≤ q < ∞. To see this observe that if we assume the contrary then this metric would be Lipschitz equivalent to a bounded subset of L_{q}. An application of Mazur’s map (see [9]) shows that this implies that L_{p} is uniformly homeomorphic to a subset of L_{2}. Since L_{p}, p > 2 has type 2, a theorem of Aharoni, Maurey and Mityagin [1] implies that L_{p} would be linearly isomorphic to a subspace of L_{1}. This is a contradiction since L_{1} has cotype 2 while L_{p}, p > 2 has cotype p. Actually, by the results presented in Chapter 9 of [9], this argument implies that the above metric is not Lipschitz equivalent to a subset of any separable Banach lattice with finite cotype.

Corollary 5.13. Fix 1 ≤ p < 2. Let X be a finite subset of L_{1} such that for every x, y ∈ X, ∥x − y∥_{1} ≥ 1. Then for every D ≥ 2 there is an embedding ψ : X → L_{p} such that for every x ∈ X, ∥ψ(x)∥_{p} = D^{1/p} and for every x, y ∈ X,

\frac{C_{1}(p)}{D^{1−1/p}} min\{∥x − y∥_{1}, D\} ≤ ∥ψ(x) − ψ(y)∥_{p} ≤ C_{2}(p)(log D)^{1/p} min\{∥x − y∥_{1}, D\},

where C_{1}(p), C_{2}(p) are constants which depend only on p.

Proof. We begin by noting that as in Remark 5.10, there is a mapping G : L_{1} → L_{p} such that for every x, y ∈ L_{1}, ∥G(x) − G(y)∥_{p} = ∥x − y∥_{1}^{1/p}. Since X is finite, there is an isometric embedding T : G(X) → ℓ_{p} (see [14]). Let F be as in Lemma 5.9, with D replaced by D^{1/p}, and define ψ = F ∘ T ∘ G. Now, ∥ψ(x)∥_{p} = D^{1/p} for every x ∈ X and:

∥ψ(x) − ψ(y)∥_{p} ≈_{p} min \{∥x − y∥_{1}^{1/p} · [log (\frac{D}{∥x − y∥_{1}} + 1)]^{1/p} , D^{1/p}\}
≤ C(p)(log D)^{1/p} min{∥x − y∥_{1}^{1/p}, D^{1/p}}
≤ C(p)(log D)^{1/p} min{∥x − y∥_{1}, D},

where we have used the fact that ∥x − y∥_{1} ≥ 1. Similarly, we have the inequality:

∥ψ(x) − ψ(y)∥_{p} ≥ \frac{C′(p)}{D^{1−1/p}} min\{∥x − y∥_{1}, D\}.

The proof is complete.

A proof identical to the proof of Lemma 5.7 now gives a bound which nearly matches the bound in Lemma 5.1:

Lemma 5.14. For every 1 ≤ p < 2 there is a constant C(p) > 0 such that for every integer d ≥ 1 and every 2^{−d} ≤ ε < 1/4 there exists a QS space of Ω_{d}, U, such that |U| ≥ (1 − ε)2^{d} and:

c_{p}(U) ≤ C(p) [\frac{log(1/ε)}{1 + log (\frac{d}{log(1/ε)})}]^{1−1/p} · [log (\frac{log(1/ε)}{1 + log (\frac{d}{log(1/ε)})})]^{1/p} .

6 Lipschitz Quotients

In this section we prove Theorem 1.13. We shall use the notation introduced in the introduction.

Recall that for a metric space X and two subsets U, V ⊂ X, the Hausdorff distance between U and V is defined as:

H_{X}(U, V) = sup{max{d_{X}(u, V), d_{X}(v, U)}; u ∈ U, v ∈ V }.

The following straightforward lemma is the way we will use the Lipschitz and co-Lipschitz conditions:

Lemma 6.1. Let X, Y be metric spaces and A > 0. For every surjection f : X → Y the following assertions hold:

1. Lip(f) ≤ A if and only if for every y, z ∈ Y, d_{Y} (y, z) ≤ Ad_{X}(f^{−1}(y), f^{−1}(z)).

2. coLip(f) ≤ A if and only if for every y, z ∈ Y, H_{X}(f^{−1}(y), f^{−1}(z)) ≤ Ad_{Y} (y, z).

Remark 6.2. A simple corollary of Lemma 6.1, which will be useful later, is that if f : X → Y is a Lipschitz quotient and we set U = f^{−1}({y ∈ Y; |f^{−1}(y)| = 1}) then f|_{U} is a Lipschitz equivalence between U and f(U) and dist(f|_{U}) ≤ Lip(f) · coLip(f).

In the following lemma we prove two recursive inequalities which will be used to give upper bounds for QS^{Lip}. In this lemma we use the notation R_{M}(·, ·) which was introduced in the introduction.

Lemma 6.3. Let M be a class of metric spaces. Then for every two integers k, m ≥ 1 and every α ≥ 1,

1. QS_{M}^{Lip}(α, km) ≤ QS_{M}^{Lip}(α, k) · QS_{M}^{Lip}(α, m).

2. QS_{M}^{Lip}(α, km) ≤ k + R_{M}(α, k) · QS_{M}^{Lip}(α, m).

Proof. We will start by proving the first assertion. Denote a = QS_{M}^{Lip}(α, k), b = QS_{M}^{Lip}(α, m). Let X be a k-point metric space such that the largest α-Lipschitz quotient of a subspace of X which is in a member of M has a points. Similarly, let Y be an m-point metric space such that the largest α-Lipschitz quotient of a subspace of Y which is in a member of M has b points. We think of X as a metric d_{X} on [k] = {1, …, k}. Fix any:

μ > αΦ(Y) = \frac{α diam(Y)}{min_{y≠z} d_{Y} (y, z)}  and  θ ≥ αμ^{k} \frac{diam(Y)}{min_{1≤i<j≤k} d_{X}(i, j)}.

Set Z = Y × [k] and define:

d_{Z}((y, i), (z, j)) = \begin{cases}μ^{i}d_{Y} (y, z) & i = j \\ θd_{X}(i, j) & i ≠ j. \end{cases}

This definition is clearly a particular case of metric composition, and the choice of parameters ensures that d_{Z} is indeed a metric.

Assume that there is S ⊆ Z, M ∈ M and N ⊆ M such that there is an α-Lipschitz quotient f : S → N. Our goal is to show that |N| ≤ ab.

Observe that by the definition of the metric on Z we have that for every i ∈ [k] and p, q ∈ N, p ≠ q, if f^{−1}(p) ∩ (Y × {i}), f^{−1}(q) ∩ (Y × {i}) ≠ ∅ then d_{Z}(f^{−1}(p), f^{−1}(q)) ≤ μ^{i} diam(Y) ≤ μ^{k} diam(Y). On the other hand, if in addition for some j ∈ [k], j ≠ i, f^{−1}(p) ∩ (Y × {j}) ≠ ∅ but f^{−1}(q) ∩ (Y × {j}) = ∅ then H_{Z}(f^{−1}(p), f^{−1}(q)) ≥ θ min_{1≤i<j≤k} d_{X}(i, j) > αμ^{k} diam(Y). This is a contradiction since Lemma 6.1 implies in particular that

\frac{H_{Z}(f^{−1}(p), f^{−1}(q))}{d_{Z}(f^{−1}(p), f^{−1}(q))} ≤ α.  (9)

Hence f^{−1}(q) ∩ (Y × {j}) ≠ ∅. Without loss of generality assume that j > i. Then:

H_{Z}(f^{−1}(p), f^{−1}(q)) ≥ μ^{j} min_{y≠z} d_{Y} (y, z) > μ^{j−1}α diam(Y) ≥ μ^{i}α diam(Y),

and we arrive once more to a contradiction with (9).

Summarizing, we have shown that for every i ∈ [k] and p ∈ N, if f^{−1}(p)∩(Y ×{i}) ≠ ∅ then either f^{−1}(p) ⊆ Y ×{i} or f^{−1}(p) ⊇ f^{−1}(N)∩(Y ×{i}). In particular, if we write for p, q ∈ N, p ∼ q if there is i ∈ [k] such that f^{−1}(p) ∩ (Y × {i}) ≠ ∅ and f^{−1}(q) ∩ (Y × {i}) ≠ ∅. Then ∼ is an equivalence relation. Let C_{1}, …, C_{s} be the equivalence classes of ∼. Take any p_{j} ∈ C_{j} and let A_{j} ⊂ [k] be the set of indices i ∈ [k] such that there exists y ∈ Y for which (y, i) ∈ f^{−1}(p_{j}). By the definition of ∼, A_{1}, …, A_{s} are disjoint. Let A = ∪_{j=1}^{s}A_{j} and define g : A → {p_{1}, …, p_{s}} by: if i ∈ A_{j} then g(i) = p_{j}. By the definition of d_{Z}, if j ≠ ℓ and h ∈ A_{j}, i ∈ A_{ℓ} then for every y, z ∈ Y, d_{X}(h, i) = d_{Z}((y, h), (z, i))/θ. Hence d_{A}(g^{−1}(p_{j}), g^{−1}(p_{ℓ})) = d_{Z}(f^{−1}(p_{j}), f^{−1}(p_{ℓ}))/θ, H_{A}(g^{−1}(p_{j}), g^{−1}(p_{ℓ})) = H_{Z}(f^{−1}(p_{j}), f^{−1}(p_{ℓ}))/θ. By Lemma 6.1, g is an α-Lipschitz quotient from the subspace A ⊂ [k] onto {p_{1}, …, p_{s}}. It follows that s ≤ a.

We will conclude once we show that for every j, |C_{j}| ≤ b. If |C_{j}| = 1 then there is nothing to prove. Otherwise there is i ∈ [k] such that for every p ∈ C_{j}, f^{−1}(p) ⊂ Y × {i}. Lemma 6.1 implies that f|_{f^{−1}(C_{j})} is an α-Lipschitz quotient of a subspace of Y × {i}, and since the metric on Y × {i} is a dilation of d_{Y}, it follows from the definition of b that |C_{j}| ≤ b.

To prove the second assertion in Lemma 6.3 we repeat the same construction, but now with Y as before, and X a k-point metric space whose largest subspace which α-embeds into a member of M has c = R_{M}(α, k) points. The rest of the notation will be as above.

Consider the equivalence classes C_{1}, …, C_{s} ⊆ N, and enumerate them in such a way that |C_{1}| = … = |C_{t}| = 1 and |C_{t+1}|, …, |C_{s}| ≥ 2. As we have seen above, for 1 ≤ j ≤ t, since C_{j} = {p_{j}}, there is a subset I_{j} ⊂ [k] such that f^{−1}(p_{j}) = f^{−1}(N) ∩ (Y × I_{j}). Since I_{1}, …, I_{t} are disjoint, t ≤ k. Now, by the construction, for t < j ≤ s, |g^{−1}(p_{j})| = 1, so that by Remark 6.2 we get that {g^{−1}(p_{t+1}), …, g^{−1}(p_{s})} ⊆ [k] α-embeds into N. By the definition of c, it follows that s − t ≤ c. Finally, we have also shown that for every j |C_{j}| ≤ b, so that |N| ≤ t + (s − t)b ≤ k + cb, as required.

Corollary 6.4. Let M be a class of finite metric spaces and α ≥ 1. Assume that there is a finite metric space M such that c_{M}(M) > α. Then there is 0 ≤ δ < 1 such that for infinitely many n’s, QS_{M}^{Lip}(α, n) ≤ n^{δ}.

Proof. Our assumption implies that there is 0 ≤ δ < 1 such that QS_{M}^{Lip}(α, |M|) ≤ |M| − 1 ≤ |M|^{δ}. An iteration of Lemma 6.3 now implies that for every i ≥ 1, QS_{M}^{Lip}(α, |M|^{i}) ≤ |M|^{δi}.

Remark 6.5. For every 1 ≤ p < ∞ and α > 2 there is an integer n_{0} = n_{0}(p, α) and constants c = c(p, α), C = C(p, α) such that 0 < c ≤ C < 1 and for every n ≥ n_{0}, n^{c} ≤ QS_{p}^{Lip}(α, n) ≤ n^{C}. This follows from Corollary 6.4 and the trivial inequality QS_{p}^{Lip}(α, n) ≥ R_{p}(α, n), together with the results of [5].

Corollary 6.6. For every 1 ≤ α < 2 and 1 ≤ p ≤ 2 there is an integer n_{0} = n_{0}(p, α) and a constant C = C(p, α) such that for every n ≥ n_{0}:

QS_{p}^{Lip}(α, n) ≤ e^{C\sqrt{(log n)(log log n)}}.

For p > 2 the same conclusion holds for every 1 ≤ α < 2^{2/p}.

Proof. As shown in [6] for every 1 ≤ p < ∞ and 1 ≤ α < 2^{min{1,2/p}} there is a constant c = c(p, α) such that for every k, R_{p}(α, k) ≤ c log k. It follows from Lemma 6.3 that for every ℓ ∈ ℕ,

QS_{p}^{Lip}(α, k^{ℓ}) ≤ k + (c log k)QS_{p}^{Lip}(α, k^{ℓ−1}).

Since QS_{p}^{Lip}(α, k) ≤ k, by induction we deduce that:

QS_{p}^{Lip}(α, k^{ℓ}) ≤ ∑_{j=0}^{ℓ−1} k(c log k)^{j} ≤ k(c log k)^{ℓ}.

Choosing k of the order of e^{\sqrt{(log n)(log log n)}} and ℓ of the order of \sqrt{\frac{log n}{log log n}} gives the required result.

We now prove a nearly matching lower bound for QS_{p}(α, n). In order to do so we first observe that Lemma 4.2 holds also in the context of Lipschitz quotients.

Lemma 6.7. Let M be an n-point metric space and 1 < α ≤ 2. Then there is a subspace of M which has an α Lipschitz quotient in an equilateral metric space and:

|U| ≥ ⌊\frac{n^{(log α)/[2 log Φ(M)]}}{8 log n} ⌋ .

Proof. The proof is exactly the same as the proof of Lemma 4.2. Using the notation of this proof, the only difference is that we observe that Lemma 4.1 actually ensures that for every i ≠ j, d_{M}(U_{i}, U_{j}), H_{M}(U_{i}, U_{j}) ∈ [α^{ℓ−1}, α^{ℓ}), so that the quotient obtained is actually a Lipschitz quotient due to Lemma 6.1.

We also require the following fact, which is essentially proved in [4] (see Proposition 16 there). Since the result of [4] was stated for parameters other than what we need below, we will sketch the proof for the sake of completeness.

Lemma 6.8. Fix 0 < ε < 1 and let M be an n-point metric space. Then there is a subset N ⊆ M which is either (1 + ε)-equivalent to an ultrametric, or 3-equivalent to an equilateral space, and:

|N| ≥ exp (c\sqrt{\frac{log n}{log(2/ε)}}) .

Proof. Set k = 2(1/ε + 1). By Theorem 4.21 there is a universal constant c > 0 such that M contains a subset M′ ⊆ M which is 3-equivalent to a (3k)-HST, X, via a non-contractive bijection f : M′ → X, and |M′| ≥ n^{c/ log(2/ε)}. Let T be the tree defining X. Set h = exp (\sqrt{c\frac{log n}{log(2/ε)}}). If T has a vertex u with out-degree exceeding h then by choosing one leaf from each subtree emerging from u we obtain a h-point subset of M′ which is 3-equivalent to an ultrametric. We may therefore assume that all the vertices in T have out-degree at most h. In this case by Lemma 14 in [4] T contains a binary subtree S with at least |M′|^{1/ log_{2} h} ≥ exp (\sqrt{c\frac{log n}{log(2/ε)}}) leaves. Now, denote by Δ(·) the original labels on S (inherited from T). We define new labels Δ′(·) on S as follows. For each vertex u ∈ S, denote by T_{1} and T_{2} the subtrees rooted at u’s children. We define Δ′(u) = max{d_{M}(x, y); x ∈ f^{−1}(T_{1}), y ∈ f^{−1}(T_{2})}. As shown in the proof of Case 2 in Proposition 16 of [4], this relabelling results in a binary k-HST which is k/(k − 2) = 1 + ε equivalent to N = f^{−1}(S).

Lemma 6.9. For every 1 ≤ α < 2 there is a constant c = c(α) > 0 such that for every integer n and every 1 ≤ α < 2,

QS_{2}^{Lip}(α, n) ≥ e^{c\sqrt{log n}}.

Proof. By Lemma 6.8 for every ε > 0 there is a constant c = c(ε) such that every n point metric space contains a subset of size at least e^{c\sqrt{log n}} which is either (1 + ε)-equivalent to an ultrametric, in which case we are already done, or 3-equivalent to an equilateral space. In the latter case the subspace obtained has aspect ration at most 3, so that the required result follows from Lemma 6.7.

Acknowledgements. We are grateful to Vitali Milman for proposing the non-linear QS problem to us, and for many insightful suggestions. We thank Yoav Benyamini and Gideon Schechtman for helpful comments. We would also like to acknowledge enjoyable conversions with Shahar Mendel.

References

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

[2] Y. Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In 37th Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996), pages 184–193. IEEE Comput. Soc. Press, Los Alamitos, CA, 1996.

[3] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems. Technical report, The Hebrew University, Jerusalem, 2002. http://www.cs.huji.ac.il/∼mendelma/mypapers.

[4] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-type Dichotomies, 2002. Preprint.

[5] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Metric Ramsey-type Phenomena, 2002. Preprint.

[6] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Some Low Distortion Metric Ramsey Problems, 2002. Preprint.

[7] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On Fréchet Embedding of Metric Spaces, 2003. Preprint.

[8] S. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092– 1127, 1999.

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

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

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

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

[13] Yu. A. Brudnyĭ and N. Ya. Krugljak. Interpolation functors and interpolation spaces. Vol. I, volume 47 of North-Holland Mathematical Library. North-Holland Publishing Co., Amsterdam, 1991. Translated from the Russian by Natalie Wadhwa, With a preface by Jaak Peetre.

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

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

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

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

[18] C. J. Lennard, A. M. Tonge, and A. Weston. Generalized roundness and negative type. Michigan Math. J., 44(1):37–45, 1997.

[19] J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

[20] V. D. Milman. A new proof of A. Dvoretzky’s theorem on cross-sections of convex bodies. Funkcional. Anal. i Priložen., 5(4):28–37, 1971.

[21] V. D. Milman. Almost Euclidean quotient spaces of subspaces of a finite-dimensional normed space. Proc. Amer. Math. Soc., 94(3):445–449, 1985.

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

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

[24] V. M. Zolotarev. One-dimensional stable distributions, volume 65 of Translations of Mathematical Monographs. American Mathematical Society, Providence, RI, 1986. Translated from the Russian by H. H. McFaden, Translation edited by Ben Silver.