SCALE-OBLIVIOUS METRIC FRAGMENTATION AND THE NONLINEAR DVORETZKY THEOREM

ASSAF NAOR AND TERENCE TAO

Abstract. We introduce a randomized iterative fragmentation procedure for finite metric spaces, which is guaranteed to result in a polynomially large subset that is D-equivalent to an ultrametric, where D ∈ (2, ∞) is a prescribed target distortion. Since this procedure works for D arbitrarily close to the nonlinear Dvoretzky phase transition at distortion 2, we thus obtain a much simpler probabilistic proof of the main result of [3], answering a question from [12], and yielding the best known bounds in the nonlinear Dvoretzky theorem.

Our method utilizes a sequence of random scales at which a given metric space is fragmented. As in many previous randomized arguments in embedding theory, these scales are chosen irrespective of the geometry of the metric space in question. We show that our bounds are sharp if one utilizes such a “scale-oblivious” fragmentation procedure.

1. Introduction

A metric space (X, d) is said to embed into Hilbert space with distortion D ⩾ 1 if there exists f : X → ℓ_{2} satisfying d(x, y) ⩽ ∥f(x)−f(y)∥_{2} ⩽ Dd(x, y) for all x, y ∈ X. Dvoretzky’s theorem [9] asserts that for every k ∈ ℕ and D > 1 there exists n = n(k, D) ∈ ℕ such that every n-dimensional normed space has a k-dimensional linear subspace that embeds into Hilbert space with distortion D; see [14, 13, 15] for the best known bounds on n(k, D).

Motivated by a possible analogue of Dvoretzky’s theorem in the class of general metric spaces, Bourgain, Figiel and Milman introduced in [6] the nonlinear Dvoretzky problem, which asks for the largest integer k = k(n, D) such that any n-point metric space has a subset of cardinality k that embeds into Hilbert space with distortion D. They showed [6] that for every D > 1 we have lim_{n→∞} k(n, D) = ∞, thus establishing the validity of a nonlinear Dvorezky phenomenon. Quantitatively, the main result of [6] asserts that k(n, D) ⩾ c(D) log n, and that there exists D_{0} > 1 for which k(n, D_{0}) = O(log n).

Renewed interest in the nonlinear Dvorezky problem due to the discovery of applications to the theory of online algorithms resulted in a sequence of works [11, 5, 1] which culminated in the following threshold phenomenon from [3] (see also [2, 4, 8] for related results):

Theorem 1.1 ([3]). For D > 1 there exist a(D), A(D) ∈ (0, ∞) and b(D), B(D) ∈ (0, 1) with the following properties:

(1) If D ∈ (1, 2) then any n-point metric space has a subset of cardinality ⩾ a(D) log n that embeds with distortion D into Hilbert space. On the other hand, there exist arbitrarily large n-point metric spaces X_{n} with the property that any Y ⊆ X_{n} that embeds into Hilbert space with distortion D necessarily satisfies |Y | ⩽ A(D) log n.

(2) If D ∈ (2, ∞) then any n-point metric space has a subset of cardinality ⩾ n^{1−b(D)} that embeds with distortion D into Hilbert space. On the other hand, there exist arbitrarily large n-point metric spaces X_{n} with the property that any Y ⊆ X_{n} that embeds into Hilbert space with distortion D necessarily satisfies |Y | ⩽ n^{1−B(D)}.

Note that the first assertion of part (1) of Theorem 1.1 is just a restatement of the Bourgain-Figiel-Milman nonlinear Dvoretzky theorem [6].

All the positive embedding results quoted above are actually stronger than embeddings into Hilbert space: they produce subsets which embed with distortion D into an ultrametric. Recall that a metric space (U, ρ) is an ultrametric if ρ(u, v) ⩽ max{ρ(u, w), ρ(w, v)} for every u, v, w ∈ U. Separable ultrametrics embed isometrically into Hilbert space [17], so the problem of finding a subset of a metric space which embeds with distortion D into an ultrametric is a (strictly) stronger statement than the nonlinear Dvoretzky problem. The fact that the embeddings of Theorem 1.1 are into ultrametrics is crucial for its applications. Note, however, that the impossibility results in Theorem 1.1 rule out embeddings into Hilbert space, and not just embeddings into ultrametrics.

The proofs of the nonlinear Dvoretzky theorems in [6, 11, 5, 1, 2, 4, 8] proceed via deterministic constructions. In [12] a new approach to the nonlinear Dvoretzky problem was introduced, based on a probabilistic argument which is closer in spirit to the proofs of the classical Dvoretzky theorem. This randomized approach, called the method of Ramsey partitions, has three main advantages. First, it leads to new algorithmic applications of the nonlinear Dvoretzky theorem which are very different from the applications in [11, 5, 1, 3]; we shall briefly describe one of these applications in Section 1.1. Second, Ramsey partitions yield a major simplification of the proof of part (2) in Theorem 1.1 for sufficiently large values of D (this part of Theorem 1.1 is by far the most complicated part of its proof in [3]). Third, the bound on the exponent b(D) obtained in [12] is asymptotically sharp as D → ∞, unlike the bound in [3], which is off by a logarithmic factor. Specifically, [12] yields b(D) ≲ 1/D, which is optimal up to the implied universal constant due to the bound B(D) ≳ 1/D of [3].

An obvious question, raised in [12], suggests itself: can the randomized approach of [12] yield a proof Theorem 1.1 in which the target distortion D > 2 is allowed to go all the way down to the phase transition at 2? The main result of [12] states that for D > 2, any n-point metric space X has a subset Y ⊆ X with |Y | ⩾ n^{1−128/D} which embeds with distortion D into an ultrametric. [12] did not attempt to optimize the constant 128 in this result, and indeed by a more careful analysis of the arguments of [12] one can ensure that |Y | ⩾ n^{1−16/(D−2)} (even this estimate can be slightly improved, but not by much). In any case, it is clear that these statements become vacuous for D smaller than a universal constant close enough to 2. Thus, the full D > 2 range of part (2) of Theorem 1.1 still required the use of the deterministic approach of [3].

It was stated in [12] that there does not seem to be a simple way to use Ramsey partitions to handle distortions arbitrarily close to 2. In Section 1.1 we make a very simple observation which proves that if D < 3, then the method of Ramsey partitions cannot yield a subset Y as above of size tending to ∞ with n. Thus, in fact, it is impossible to approach the phase transition at 2 using Ramsey partitions. Here we present a new randomized approach, building on the multiplicative telescoping argument of [12], which proves the nonlinear Dvoretzky theorem for any distortion D > 2. Specifically, we prove the following result:

Theorem 1.2. For every D > 2, any n-point metric space has a subset of cardinality n^{θ(D)} which embeds with distortion D into an ultrametric. Here θ = θ(D) ∈ (0, 1) is the unique solution of the equation

\frac{2}{D} = (1 − θ)θ^{\frac{θ}{1−θ}} .

It is elementary to check that θ(D) ⩾ 1 − \frac{2e}{D} for all D > 2, and that as ε ↘ 0 we have

θ(2+ε) = \frac{ε}{2 log(1/ε)} +O (\frac{ε log log(1/ε)}{(log(1/ε))^{2}}). Theorem 1.2 yields a very short proof (complete details in 3 pages) of the the nonlinear Dvoretzky theorem for all distortions D > 2, with the best known bounds on the exponent θ(D). In a sense that is made precise in Section 1.2, the above value of θ(D) is optimal for our method.

1.1. Approximate distance oracles and limitations of Ramsey partitions. We recall some terminology and results from [12]. Fix δ ∈ (0, 1) and let (X, d) be an n-point metric space of diameter 1. A sequence {𝒫_{k}}_{k=0}^{∞} of partitions of X is called a partition tree of rate δ if 𝒫_{0} is the trivial partition {X}, for all k ⩾ 0 𝒫_{k+1} is a refinement of 𝒫_{k}, and each set in 𝒫_{k} has diameter at most δ^{k}.

The main tool in [12] is random partition trees. Let Pr be a probability distribution over partition trees of rate δ. For ℓ > 0 consider the the random subset Y ⊆ X consisting of those x ∈ X such that for all k ∈ ℕ the entire closed ball B(x, δ^{k}/ℓ) is contained in the element of 𝒫_{k} to which x belongs. Assume that each x ∈ X falls in Y with Pr-probability at least n^{−β}. Then 𝔼 [|Y |] ⩾ n^{1−β}. Define for distinct x, y ∈ X the random quantity ρ(x, y) = δ^{k(x,y)}, where k(x, y) is the largest integer k such that both x and y fall in the same element of 𝒫_{k}. Then ρ is an ultrametric on X, and for x ∈ X and y ∈ Y we have ρ(x, y) ⩾ d(x, y) ⩾ \frac{δ}{ℓ}ρ(x, y) [12, Lem. 2.1]. Thus, on Y, ρ is bi-Lipschitz equivalent to the original metric d with distortion ⩽ ℓ/δ. But more is true: the ultrametric ρ is defined on all of X, and approximates up to a factor ⩽ ℓ/δ all distances from points of Y to all the other points of X.

In [12] random partition trees were constructed with the desired bounds on β and the distortion ℓ/δ. It was shown in [12] that the existence of an ultrametric ρ on X which has the above property of approximating distances from points of a large subset Y ⊆ X to all other points of X, has a variety of implications to the theory of data structures. Here we need to briefly recall the connection to approximate distance oracles.

An n-point metric space (X, d) can be thought of as table of \binom{n}{2} numbers, corresponding to the distances between all unordered pairs x, y ∈ X. In the approximate distance oracle problem the goal is, given D > 1, to do “one time work” (preprocessing) that produces a data structure (called an approximate distance oracle) of size o(n^{2}) such that given a “query” x, y ∈ X, one can quickly produce a number E(x, y) satisfying d(x, y) ⩽ E(x, y) ⩽ Dd(x, y). We call D the stretch of the approximate distance oracle.

The seminal work on approximate distance oracles is due to Thorup and Zwick [16], who showed that for all odd D ∈ ℕ one can design a data structure of size O(Dn^{1+2/D}) using which one can compute in time O(D) a number E(x, y) satisfying d(x, y) ⩽ E(x, y) ⩽ Dd(x, y). In [12] it was shown^{1} that if every n-point metric space (X, d) admits an ultrametric ρ (defined on all of X) and a subset Y ⊆ X with |Y | ⩾ n^{1−c/D}, such that for every x ∈ X and y ∈ Y we have d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y), then any n-point metric space can be preprocessed to yield a data structure of size O(n^{1+c/D}) using which one can compute in time O(1) a number E(x, y) satisfying d(x, y) ⩽ E(x, y) ⩽ Dd(x, y). A key new point here is that the query time is a universal constant, and does not depend on D as in [16].

1This assertion is not stated explicitly in [12], but it follows directly from the proof of [12, Th. 1.2]: using the notation of [12], as noted in the proof of [12, Th. 1.2], the ultrametric ρ_{j} is only required to be defined, and satisfy the conclusion of [12, Lem. 4.2], on X_{j−1} and not on all of X. This property is guaranteed by our assumption. Thus there is no loss of constant factor since for the purpose of [12, Th. 1.2] (unlike other applications of [12, Lem. 4.2] in [12]), we do not need to use [12, Lem. 4.1].

It was also shown in [16] that any approximate distance oracle that answers distance queries with stretch D < 3 must use ≳ n^{2} bits of storage. Combining this lower bound with the above construction of [12], we see that if D < 3 there must exist arbitrarily large n-point metric spaces (X_{n}, d_{n}) such that if ρ is an ultrametric on X_{n} and Y ⊆ X_{n} is such that d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y) for all x ∈ X_{n} and y ∈ Y, then |Y | ≲ n^{o(1)}. It is actually not difficult to unravel the arguments of [16, 12] to give a direct proof of the fact that Ramsey partitions cannot yield the nonlinear Dvoretzky theorem for distortions in (2, 3). We will not do so here since it would be a digression from the topic of the present paper; the purpose of the above discussion is only to explain why a method other than Ramsey partitions is required in order to to go all the way down to distortion 2.

1.2. The fragmentation procedure and admissible exponents. Having realized that a proof of part (2) of Theorem 1.1 for D arbitrarily close to 2 cannot produce a large Y ⊆ X and an ultrametric ρ that is defined on all of X and satisfies d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y) for all x ∈ X and y ∈ Y, it is natural to try to design a procedure which results in an ultrametric that is defined on the subset Y alone. This is what our fragmentation procedure does.

In order to state our main results, we require the following definition:

Definition 1.3 (Admissible exponent). Fix D > 2. We say that σ > 0 is an admissible exponent for D if there exist a sequence of (not necessarily independent) random variables 1 = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0 with lim_{n→∞} r_{n} = 0, such that for every real number r > 0, we have

∑_{n=1}^{∞} Pr [r_{n} < r ⩽ r_{n} + \frac{2r_{n−1}}{D} ] ⩽ σ.  (1)

Theorem 1.4 (Ultrametrics via admissible exponents). Fix D > 2, and let σ > 0 be an admissible exponent for D. Let X = (X, d) be a finite metric space. Then there exists a subset S of X of cardinality |S| ⩾ |X|^{1−σ} which embeds with distortion D into an ultrametric.

Let σ^{∗}(D) denote the infimum of those σ > 0 which are admissible exponents for D. Due to Theorem 1.4, we would like to estimate σ^{∗}(D). In fact, it turns out that we can compute it exactly; the following theorem, in combination with Theorem 1.4, implies Theorem 1.2.

Theorem 1.5 (Optimization of admissible exponents). For every D > 2 we have σ^{∗}(D) = β, where β ∈ (0, 1) is the unique solution of the equation

\frac{2}{D} = β(1 − β)^{\frac{1−β}{β}} .  (2)

Moreover, σ^{∗}(D) is attained at the following random variables: r_{0} = 1, and for n ∈ ℕ,

r_{n} =^{def} (1 − β)^{\frac{U+n−1}{β}} ,  (3)

where U is a random variable that is uniformly distributed on the interval [0, 1]. For this choice of 1 = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0, the supremum of the left hand side of (1) over r > 0 equals the value of β in (2).

The construction of the subset S in Theorem 1.4 is most natural to describe in the context of compact metric spaces, though it will be applied here only to finite metric spaces.

Throughout this paper a metric probability space (X, d, μ) is a compact metric space (X, d) equipped with a Borel probability measure μ. For x ∈ X and r ⩾ 0 we shall use the standard notation for (closed) balls: B(x, r) = {y ∈ X : d(x, y) ⩽ r}. To avoid degeneracies we assume that for every r > 0 we have μ(B(x, r)) > 0, and that the function x ↦ μ(B(x, r)) is measurable. Of course, these hypotheses are automatic in the case of finite metric spaces with uniform measure.

Fix a metric probability space (X, d, μ), normalized to have diameter 2, and a decreasing sequence of radii 1 = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0. Define inductively a decreasing sequence of random subsets X = S_{0} ⊇ S_{1} ⊇ S_{2} … as follows. Having defined S_{i}, let {x_{n}}_{n=1}^{∞} be an i.i.d. sequence of points in X, each distributed according to μ. The set S_{i+1} is defined to be those points x ∈ S_{i} for which the first point in the sequence \{x_{n}\}_{n=1}^{∞} that fell in B (x, r_{n} + \frac{2r_{n−1}}{D} ), actually fell in the smaller ball B(x, r_{n}). Letting S = ⋃_{i=0}^{∞} S_{i}, we argue (see Lemma 2.1 and Lemma 2.2) that (S, d) embeds with distortion D into an ultrametric, and that,

𝔼 [μ(S)] ⩾ ∫_{X} (∏_{n=1}^{∞} \frac{μ(B(x, r_{n}))}{μ (B (x, r_{n} + \frac{2r_{n−1}}{D} ))}) dμ(x).  (4)

So far we did not use the fact that the radii {r_{n}}_{n=0}^{∞} are themselves random. The additional randomness allows us to use a refinement of an idea of [12] in order to control the infinite product appearing in (4) using Jensen’s inequality (the corresponding step in [12] used the AM-GM inequality). This is how the notion of admissible exponent appears in Theorem 1.4; the details appear in Section 2. Note that the proof of Theorem 1.2 is simple to describe: it follows the above outline with the specific sequence of random radii given in (3). (Observe that this sequence of radii involves a choice of only one random number U, unlike the construction of [12], and its predecessors [7, 10], in which r_{n} was uniformly distributed on [8^{−n}/4, 8^{−n}/2], and the {r_{n}}_{n=0}^{∞} were independent random variables.)

The obvious weakness of the above approach is that the random radii {r_{n}}_{n=0}^{∞} are chosen without consideration of the particular geometry of the metric space X. It makes sense that in order to obtain sharper results one would need to investigate how different scales in X interact, and reflect this understanding in a choice of radii which are not “scale-oblivious”. Theorem 1.5 shows that in order to improve our bounds in Theorem 1.2 one would need to use a fragmentation procedure that is not scale-oblivious (or, find a way to control an expression such as (4) without using Jensen’s inequality; this seems quite difficult).

A particular question of interest in this context is as follows: for D > 2 let θ^{∗}(D) be the supremum of those θ > 0 such that there exists n_{0} ∈ ℕ for which any metric space of cardinality n ⩾ n_{0} has a subset of size ⩾ n^{θ} that embeds with distortion D into an ultrametric. Both [3] and our new proof give the bound θ^{∗}(2 + ε) ≳ ε/ log(2/ε) (for different reasons). Must it be the case that θ^{∗}(2 + ε) tends to 0 as ε ↘ 0? This is of course related the unknown behavior of the nonlinear Dvoretzky problem at distortion D = 2. Computing the value of lim sup_{D→∞} D(1 − θ^{∗}(D)) is also of interest; due to Theorem 1.5 we know that using our scale-oblivious metric fragmentation procedure we cannot bound this number by less than 2e.

Acknowledgements. We thank Manor Mendel for helpful discussions on the Thorup-Zwick lower bound. A. N. is supported by NSF grants CCF-0635078 and CCF-0832795, BSF grant 2006009, and the Packard Foundation. T. T. is supported by a grant from the MacArthur foundation, by NSF grant DMS-0649473, and by the NSF Waterman award.

2. Randomized fragmentation

We begin with a lemma that fragments a metric space at a single pair of scales R > r > 0.

Lemma 2.1 (Fragmentation lemma). Let (X, d, μ) be a metric probability space, and let S ⊆ X be a compact subset of X. Fix R > r > 0 and a Borel-measurable non-negative function w : S → [0, ∞). Then there exists a compact subset T ⊆ S with

∫_{T} \frac{μ(B(x, R))}{μ(B(x, r))}w(x) dμ(x) ⩾ ∫_{S} w(x) dμ(x),  (5)

such that T can be partitioned as T = ⋃_{n=1}^{∞} T_{n}, where each (possibly empty) T_{n} is compact and contained in a ball of radius r, and any two non-empty T_{n}, T_{m} are separated by a distance of at least R − r.

Proof. We use the probabilistic method. Let {x_{n}}_{n=1}^{∞} be an i.i.d. sequence of points in X, selected using the measure μ. Observe that as B(x, R) has positive measure for all x ∈ X, we will almost surely have x_{n} ∈ B(x, R) for at least one n ∈ ℕ. Thus if we define the (random) quantity

n(x) =^{def} inf{n ∈ ℕ : x_{n} ∈ B(x, R)},  (6)

then n(x) is finite for almost every x ∈ X, and x ↦ n(x) is a measurable function of x. Define a (random) subset A ⊆ S by

A =^{def} {x ∈ S : n(x) < ∞ ∧ x_{n(x)} ∈ B(x, r)}.  (7)

Then A = ⋃_{n=1}^{∞} A_{n}, where

A_{n} =^{def} {x ∈ S : n(x) = n ∧ x_{n} ∈ B(x, r)}.  (8)

By definition we have A_{n} ⊆ B(x_{n}, r). Also, if x ∈ A_{n} and y ∈ A_{m} for some 1 ⩽ n < m, then by the definitions (6), (8) we have d(x_{n}, x) ⩽ r and d(x_{n}, y) > R, and hence by the triangle inequality we have d(x, y) > R − r. Thus if we set T_{n} =^{def} \overline{A_{n}}, then T_{n} and T_{m} are compact and separated by a distance of at least R − r (this shows that only finitely many of the T_{n} are non-empty). If we define T =^{def} ⋃_{n=1}^{∞} T_{n}, then T is a compact subset of S.

Since T ⊇ A, in order to conclude the proof of Lemma 2.1 it suffices to prove the identity

𝔼 [∫_{A} \frac{μ(B(x, R))}{μ(B(x, r))}w(x) dμ(x)] = ∫_{S} w(x) dμ(x).  (9)

By the Fubini-Tonelli theorem, in order to prove (9) it suffices to show that for all x ∈ S we have,

Pr[x ∈ A] = \frac{μ(B(x, r))}{μ(B(x, R))}.  (10)

Since n(x) is finite almost surely, the definition (7), together with the joint independence of x_{1}, x_{2} …, immediately implies that:

Pr[x ∈ A] = ∑_{n=1}^{∞} Pr [x_{n} ∈ B(x, r) ∧ x_{1}, …, x_{n−1} ∉ B(x, R)]

= ∑_{n=1}^{∞} μ(B(x, r)) (1 − μ(B(x, R)))^{n−1} = \frac{μ(B(x, r))}{μ(B(x, R))}. (11)

This proves (10), and thus concludes the proof of Lemma 2.1. □

We can iterate Lemma 2.1 as follows.

Lemma 2.2 (Iterated fragmentation lemma). Fix R, D > 0. Let (X, d, μ) be a metric probability space of diameter at most 2R, and let

R = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0

be a sequence of radii converging to zero. Then there exists a compact subset S of X such that

μ(S) ⩾ ∫_{X} (∏_{n=1}^{∞} \frac{μ(B(x, r_{n}))}{μ (B (x, r_{n} + \frac{2r_{n−1}}{D} ))}) dμ(x),  (12)

and (S, d) embeds with distortion D into an ultrametric.

Proof. By applying Lemma 2.1 repeatedly, we obtain a decreasing sequence of compact subsets of X,

X = S_{0} ⊇ S_{1} ⊇ S_{2} ⊇ …

satisfying for n ⩾ 1,

∫_{S_{n}} ( ∏_{m=n+1}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) dμ(x) ⩾ ∫_{S_{n−1}} ( ∏_{m=n}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) dμ(x),

such that for each n ∈ ℕ we have S_{n} = ⋃_{j=1}^{∞} S_{n,j}, where each S_{n,j} is compact and contained in a ball of radius r_{n}, and if S_{n,j}, S_{n,ℓ} ≠ ∅ then d(S_{n,j}, S_{n,ℓ}) ⩾ 2r_{n−1}/D. It follows inductively that

∫_{S_{n}} ( ∏_{m=n+1}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) dμ(x) ⩾ ∫_{X} (∏_{m=1}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) dμ(x),

and in particular

μ(S_{n}) ⩾ ∫_{X} (∏_{m=1}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) dμ(x).

If we set S =^{def} ⋂_{n=1}^{∞} S_{n}, then S is compact and obeys (12).

If x, y ∈ S are distinct, let n(x, y) be the largest integer n such that for all m ∈ {1, …, n} there is j(m) ∈ ℕ for which x, y ∈ S_{m,j(m)}. Note that since the diameter of S_{m,j} is at most 2r_{m}, and lim_{m→∞} r_{m} = 0, such an n must exist. Now define an ultrametric ρ on S by

ρ(x, y) =^{def} 2r_{n(x,y)}.

It is immediate to check that ρ is symmetric, and obeys the ultratriangle inequality

∀x, y, z ∈ S, ρ(x, z) ⩽ max{ρ(x, z), ρ(y, z)}.

If x, y ∈ S are distinct and n = n(x, y), then by definition x, y ∈ S_{n,j} for some j ∈ ℕ and x ∈ S_{n+1,k}, y ∈ S_{n+1,ℓ}, where k ≠ ℓ. Thus d(x, y) ⩽ diam(S_{n,j}) ⩽ 2r_{n} = ρ(x, y) and d(x, y) ⩾ d(S_{n+1,k}, S_{n+1,ℓ}) ⩾ 2r_{n}/D = ρ(x, y)/D. It follows that the identity map from (S, d) to (S, ρ) has distortion at most D, completing the proof of Lemma 2.2. □

Now suppose that (X, d) is a finite metric space, and that μ is the counting measure on X. Then Lemma 2.2 specializes to Corollary 2.3 (Iterated fragmentation lemma, finite case). Fix D, R > 0. Let X = (X, d) be a finite metric space of diameter at most 2R, and let

R = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0

be a sequence of radii converging to zero. Then there exists a subset S of X such that

|S| ⩾ ∑_{x∈X} ∏_{n=1}^{∞} \frac{|B(x, r_{n})|}{|B (x, r_{n} + \frac{2r_{n−1}}{D} )|},  (13)

and (S, d) embeds with distortion D into an ultrametric.

The condition (13) is difficult to work with. However, using a random choice of r_{n}, and Jensen’s inequality, one can obtain a more workable condition in terms of the notion of admissible exponent as in Definition 1.3. This is contained in Theorem 1.4, which we are now in position to prove.

Proof of Theorem 1.4. By rescaling we may assume that X has diameter at most 2. We let r_{0}, r_{1}, … be the random variables in Definition 1.3, i.e., (1) holds for all r > 0. Applying Corollary 2.3 we thus obtain a (random) subset S ⊆ X obeying (13), which embeds with distortion D into an ultrametric. Taking expectations we obtain

𝔼 [|S|] ⩾ ∑_{x∈X} 𝔼 [∏_{n=1}^{∞} \frac{|B(x, r_{n})|}{|B (x, r_{n} + \frac{2r_{n−1}}{D} ) |}] ,

and hence by Jensen’s inequality,

𝔼 [|S|] ⩾ ∑_{x∈X} exp (𝔼 [∑_{n=1}^{∞} log (\frac{|B(x, r_{n})|}{|B (x, r_{n} + \frac{2r_{n−1}}{D} ) |})]) .  (14)

For every x ∈ X let 0 = t_{1}(x) < t_{2}(x) < … < t_{k(x)}(x) be the radii at which |B(x, t)| jumps, i.e., 1 = |B(x, t_{1}(x))| < |B(x, t_{2}(x))| < … < |B(x, t_{k(x)}(x))| = |X|, and B(x, t) = B(x, t_{j}(x)) if t_{j}(x) ⩽ t < t_{j+1}(x) (where we use the convention t_{k(x)+1}(x) = ∞). Note that for every random variable r ⩾ 0 we have the following simple identity:

𝔼 [log |B(x, r)|] = ∑_{j=1}^{k(x)} Pr [t_{j}(x) ⩽ r < t_{j+1}(x)] log |B(x, t_{j}(x))|

= ∑_{j=1}^{k(x)} (Pr [r ⩾ t_{j}(x)] − Pr [r ⩾ t_{j+1}(x)]) log |B(x, t_{j}(x))|

= ∑_{j=2}^{k(x)} Pr [r ⩾ t_{j}(x)] log (\frac{|B(x, t_{j}(x))|}{|B(x, t_{j−1}(x))|}) .  (15)

Applying (15) to r = r_{n} and r = r_{n} + \frac{2r_{n−1}}{D}, we see that (14) can be written as

𝔼 [|S|]

⩾ ∑_{x∈X} exp (− ∑_{j=2}^{k(x)} (∑_{n=1}^{∞} Pr [r_{n} < t_{j}(x) ⩽ r_{n} + \frac{2r_{n−1}}{D} ]) log (\frac{|B(x, t_{j}(x))|}{|B(x, t_{j−1}(x))|})) . (16)

Applying (1) we conclude that

𝔼 [|S|] ⩾ ∑_{x∈X} exp (−σ ∑_{j=2}^{k(x)} log (\frac{|B(x, t_{j}(x))|}{|B(x, t_{j−1}(x))|})) = ∑_{x∈X} |X|^{−σ} = |X|^{1−σ},

where we used the fact that |B(x, t_{1}(x))| = 1 and |B(x, t_{k(x)}(x))| = |X|. The proof of Theorem 1.4 is complete. □

3. Proof of Theorem 1.5

Define f : [0, 1] → [0, 1] by f(β) = β(1 − β)^{\frac{1−β}{β}}, where f(0) = 0 and f(1) = 1. Note that (log f)′(β) = −\frac{1}{β^{2}} log(1 − β), and therefore f is strictly increasing on [0, 1]. It follows that for each α ∈ [0, 1] there is a unique β = β(α) satisfying the identity

α = β(1 − β)^{\frac{1−β}{β}} .  (17)

Fix D > 2 and set β = β(2/D). Let U be a random variable that is uniformly distributed on [0, 1]. We shall define a sequence of random variables r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ … > 0 as in (3), i.e., by setting r_{0} = 1, and for n ∈ ℕ,

r_{n} =^{def} (1 − β)^{\frac{U+n−1}{β}} .

Writing α = 2/D, for every r > 0 we have the following bound on the left hand side of (1):

∑_{n=1}^{∞} Pr [r_{n} < r ⩽ r_{n} + \frac{2r_{n−1}}{D} ]

⩽ ∑_{n=1}^{∞} Pr [(1 − β)^{\frac{U+n−1}{β}} < r ⩽ (1 − β)^{\frac{U+n−1}{β}} + α(1 − β)^{\frac{U+n−2}{β}} ] = ∑_{n=1}^{∞} Pr [U ∈ I_{n}] , (18)

where I_{n} is the interval:

I_{n} =^{def} (\frac{β log r}{log(1 − β)} − n + 1, \frac{β log r}{log(1 − β)} − n + 1 − \frac{β log (1 + \frac{α}{(1−β)^{1/β}} )}{log(1 − β)}] =^{def} (a − n, b − n].

The identity (17) implies that b − a = β. In particular, b − a ⩽ 1, and hence the intervals {I_{n}}_{n=1}^{∞} are disjoint, at most two of them intersect [0, 1], and the total length of the intersection of ⋃_{n=1}^{∞} I_{n} with [0, 1] is at most b − a. Combined with (18), this observation implies that

∑_{n=1}^{∞} Pr [r_{n} < r ⩽ r_{n} + \frac{2r_{n−1}}{D} ] ⩽ length ((⋃_{n=1}^{∞} I_{n}) ∩ [0, 1]) ⩽ b − a = β.

This proves the second assertion of Theorem 1.5. It remains to prove that for all D > 2 we have σ^{∗}(D) ⩾ β(2/D). To this end let {r_{n}}_{n=0}^{∞} be a sequence of random variables decreasing to zero as in Definition 1.3, so that (1) holds for some σ > 0. Our goal is to show that σ ⩾ β(2/D).

For α, p ∈ (0, 1) denote

β_{p}(α) =^{def} inf_{x>1} \frac{(1 + αx)^{p} − 1}{x^{p} − 1}.  (19)

By homogeneity, for every y ⩾ x > 0 we have (x + αy)^{p} − x^{p} ⩾ β_{p}(α) (y^{p} − x^{p}). Thus for all n ∈ ℕ,

∑_{n=1}^{∞} 𝔼 [(r_{n} + \frac{2r_{n−1}}{D} )^{p} − r_{n}^{p}] ⩾ β_{p} (\frac{2}{D}) 𝔼 [∑_{n=1}^{∞} (r_{n−1}^{p} − r_{n}^{p})] = β_{p} (\frac{2}{D}) ,  (20)

where we used the fact that lim_{n→∞} r_{n} = 0 and r_{0} = 1.

Now,

∑_{n=1}^{∞} 𝔼 [(r_{n} + \frac{2r_{n−1}}{D} )^{p} − r_{n}^{p}] = ∑_{n=1}^{∞} ∫_{0}^{∞} pr^{p−1} (Pr [r_{n} + \frac{2r_{n−1}}{D} ⩾ r] − Pr [r_{n} ⩾ r]) dr

= ∑_{n=1}^{∞} ∫_{0}^{1+ \frac{2}{D}} pr^{p−1} Pr [r_{n} < r ⩽ r_{n} + \frac{2r_{n−1}}{D} ] dr ⩽^{(1)} σ (1 + \frac{2}{D})^{p} . (21)

By combining (20) and (21) (which hold for all p ∈ (0, 1)), we see that the bound σ ⩾ β(2/D) will be proven if we manage to show that for all α ∈ (0, 1),

lim sup_{p→0} β_{p}(α) ⩾ β(α),  (22)

where β(α) is the unique β ∈ (0, 1) satisfying (17).

To prove (22), define f : [0, ∞) → ℝ by f(x) = (1 + αx)^{p} − 1 − β_{p}(α) (x^{p} − 1). Note that f takes only non-negative values, due to the definition (19). By considering the limit as x → ∞ of the right hand side of (19), we see that β_{p}(α) ⩽ α^{p}. But, it cannot be the case that β_{p}(α) = α^{p}, since otherwise f(x) = (1 + αx)^{p} − (αx)^{p} − (1 − α^{p}), which, since p ∈ (0, 1), tends to −(1 − α^{p}) < 0 as x → ∞, contradicting the non-negativity of f on [1, ∞). Thus β_{p}(α) < α^{p}. It follows in particular that the infimum in (19) is actually a minimum, i.e., there exists x_{0} ∈ (1, ∞) for which β_{p}(α) = \frac{(1+αx_{0})^{p}−1}{x_{0}^{p}−1}. This is the same as f(x_{0}) = 0, and since f is non-negative, x_{0} must be a global minimum of f, and hence f′(x_{0}) = 0.

From 0 = f′(x_{0}) = pα(1 + αx_{0})^{p−1} − pβ_{p}(α)x_{0}^{p−1} we see that

x_{0} = \frac{1}{(α/β_{p}(α))^{1/(1−p)} − α}.  (23)

Substituting this value of x_{0} into the equation f(x_{0}) = 0, we see that

\begin{matrix}(α/β_{p}(α)) & p/(1−p) \\ ((α/β_{p}(α))^{1/(1−p)} − α) & p \end{matrix} − 1 = β_{p}(α) (\frac{1}{((α/β_{p}(α))^{1/(1−p)} − α)^{p}} − 1) .  (24)

Denote β = lim sup_{p→0} β_{p}(α). If β = 1 then (22) holds trivially. We may therefore assume that β < 1. Moreover, (23) combined with x_{0} > 1 implies that (α/β_{p}(α))^{1/(1−p)} − α < 1, or β_{p}(α) > \frac{α}{(1+α)^{1−p}}. Thus β ⩾ \frac{α}{1+α} (all that we will need below is that β ≠ 0).

If {p_{k}}_{k=1}^{∞} ⊆ (0, 1) is such that lim_{k→∞} p_{k} = 0 and lim_{k→∞} β_{p_{k}}(α) = β, then it follows from (24) that:

p_{k} (log (\frac{α}{β}) − log (\frac{α}{β} − α)) + o(p_{k}) = −p_{k}β log (\frac{α}{β} − α) + o(p_{k}).  (25)

Since, as argued above, \frac{α}{β}, \frac{α}{β} − α ∈ (0, ∞), the asymptotic identity (25) implies that

log (\frac{α}{β}) − log (\frac{α}{β} − α) = −β log (\frac{α}{β} − α) ,

which simplifies to give α = β(1 − β)^{(1−β)/β}. Since we already argued (in the paragraph preceding (17)), that β(α) is the unique solution of the equation (17), we deduce that β = β(α). The proof of (22), and hence also the proof of Theorem 1.5, is complete. □

References

[1] Y. Bartal, B. Bollobás, and M. Mendel. Ramsey-type theorems for metric spaces with applications to online problems. J. Comput. System Sci., 72(5):890–921, 2006.

[2] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type dichotomies. J. London Math. Soc. (2), 71(2):289–303, 2005.

[3] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[4] Y. Bartal, N. Linial, M. Mendel, and A. Naor. Some low distortion metric Ramsey problems. Discrete Comput. Geom., 33(1):27–41, 2005.

[5] A. Blum, H. Karloff, Y. Rabani, and M. Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM J. Comput., 30(5):1624–1661 (electronic), 2000.

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

[7] G. Calinescu, H. Karloff, and Y. Rabani. Approximation algorithms for the 0-extension problem. SIAM J. Comput., 34(2):358–372 (electronic), 2004/05.

[8] M. Charikar and A. Karagiozova. A tight threshold for metric Ramsey phenomena. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 129–136 (electronic), New York, 2005. ACM.

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

[10] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci., 69(3):485–497, 2004.

[11] H. Karloff, Y. Rabani, and Y. Ravid. Lower bounds for randomized k-server and motion-planning algorithms. SIAM J. Comput., 23(2):293–312, 1994.

[12] M. Mendel and A. Naor. Ramsey partitions and proximity data structures. J. Eur. Math. Soc., 9(2):253– 275, 2007.

[13] V. Milman and G. Schechtman. An “isomorphic” version of Dvoretzky’s theorem. II. In Convex geometric analysis (Berkeley, CA, 1996), volume 34 of Math. Sci. Res. Inst. Publ., pages 159–164. Cambridge Univ. Press, Cambridge, 1999.

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

[15] G. Schechtman. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math., 200(1):125–135, 2006.

[16] M. Thorup and U. Zwick. Approximate distance oracles. J. ACM, 52(1):1–24 (electronic), 2005.

[17] I. A. Vestfrid and A. F. Timan. A universality property of Hilbert spaces. Dokl. Akad. Nauk SSSR, 246(3):528–530, 1979.

Courant Institute, New York University, New York NY 10012

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

Department of Mathematics, UCLA, Los Angeles CA 90095-1555

E-mail address: tao@math.ucla.edu