ASSOUAD’S THEOREM WITH DIMENSION INDEPENDENT OF THE SNOWFLAKING

ASSAF NAOR AND OFER NEIMAN

Abstract. It is shown that for every K > 0 and ε ∈ (0, 1/2) there exist N = N(K) ∈ ℕ and D = D(K, ε) ∈ (1, ∞) with the following properties. For every metric space (X, d) with doubling constant at most K, the metric space (X, d^{1−ε}) admits a bi-Lipschitz embedding into ℝ^{N} with distortion at most D. The classical Assouad embedding theorem makes the same assertion, but with N → ∞ as ε → 0.

1. Introduction

In this paper all metric spaces are assumed to be separable and contain at least two points. Balls in metric spaces are always closed balls, i.e., for a metric space (X, d), x ∈ X and r ⩾ 0, we denote B(x, r) = {y ∈ X : d(x, y) ⩽ r}. A metric space (X, d) has doubling constant K ∈ (1, ∞) if every ball in X can be covered by at most K balls of half its radius, i.e., for every x ∈ X and r > 0 there exist A ⊆ X with |A| ⩽ K such that B(x, r) ⊆ ⋃_{y∈A} B(y, r/2). Note that since X contains at least two points, necessarily K ⩾ 2. (X, d) is said to be a doubling metric space if it has doubling constant K for some K ∈ (1, ∞).

A metric space (X, d) embeds into a normed space (Y, ∥ · ∥) with distortion D ∈ [1, ∞] if there exists f : X → Y such that for all x, y ∈ X we have d(x, y) ⩽ ∥f(x)−f(y)∥ ⩽ Dd(x, y). When X embeds into Y with finite distortion we say that X admits a bi-Lipschitz embedding into Y. The infimum over those D ⩾ 1 for which X embeds into Y is denoted c_{Y} (X). When Y = ℓ_{2} is infinite dimensional Hilbert space, we write c_{Y} (X) = c_{2}(X); this parameter is known in the literature as the Euclidean distortion of X. In what follows, when we refer to the space ℝ^{N} we always assume that it is equipped with the standard Euclidean metric. A standard argument (see, e.g., [4, Lem. 4.9]) shows that if Y is either ℓ_{2} or ℝ^{N}, we have

c_{Y} (X) = sup{c_{Y} (Z) : Z ⊆ X ∧ |Z| < ∞}.  (1)

If (X, d) is a metric space and α ∈ (0, 1] then (X, d^{α}) is also a metric space, known as the α-snowflake of X.

A major open problem of embedding theory is the bi-Lipschitz embeddability problem in ℝ^{N}. This problem asks for an intrinsic characterization of those separable metric spaces (X, d) that admit a bi-Lipschitz embedding into ℝ^{N} for some N ∈ ℕ. For a discussion of this important question, see for example the works of Semmes [28], Lang-Plaut [20] and Heinonen [16]. An obvious restriction on a metric space (X, d) that admits a bi-Lipschitz embedding into ℝ^{N} is that it must be doubling. In this context, Assouad discovered in [4] the following fundamental embedding theorem (see also Heinonen’s book [15] for a nice exposition of Assouad’s theorem).

A. N. was supported in part by NSF grant CCF-0832795, BSF grant 2006009, and the Packard Foundation.

O. N. was supported in part by NSF grant CCF-0832795.

Theorem 1.1 (Assouad’s embedding theorem). For every ε ∈ (0, 1) and K > 0, there exist N = N(K, ε) ∈ ℕ and D = D(K, ε) ∈ (1, ∞) such that for every separable metric space (X, d) with doubling constant K, the metric space (X, d^{1−ε}) admits a bi-Lipschitz embedding into ℝ^{N} with distortion at most D.

Assouad’s theorem falls short of solving the bi-Lipschitz embeddability problem in ℝ^{N}, since it only achieves an embedding of the snowflaked metric space (X, d^{1−ε}). Nevertheless, as ε → 0 this metric space becomes closer and closer to the original metric space (X, d). It is therefore of interest to investigate the behavior of N(K, ε) and D(K, ε) as ε → 0. It turns out that necessarily lim_{ε→0} D(K, ε) = ∞, due to the existence of doubling metric spaces that do not admit a bi-Lipschitz embedding into ℝ^{N}. The first known such example is the Heisenberg group, equipped with the Carnot-Carathéodory metric: Semmes observed in [27] that its bi-Lipschitz nonembeddability into ℝ^{N} is a consequence of Pansu’s differentiability theorem [25]. Additional examples of non-Euclidean doubling spaces were found by Laakso [19] and Bourdon-Pajot [7]; see the work of Cheeger [8] for a unified treatment of these results.

It seems to be inherent to Assouad’s embedding method that also lim_{ε→0} N(K, ε) = ∞. Note that if ε ∈ (0, 1/2) then the metric space (X, d^{1−ε}) has doubling constant K^{2}, so there is no obvious obstruction to (X, d^{1−ε}) admitting a bi-Lipschitz embedding into ℝ^{N} for some N that is independent of ε ∈ (0, 1/2). The issue that in Assouad’s theorem N depends on ε and is very large as ε → 0 was noted by many authors; this is mentioned, for example, in the works of David-Toro [10] and Semmes [28] (where much more refined bounds on N are obtained under additional assumptions). Assouad himself noticed this issue in [4], where he showed that N can be taken to be independent of ε ∈ (0, 1/2) when X = ℝ (more generally, Assouad deals in [4] with X = [0, 1]^{k}). The case of the “helix snowflakes” (ℝ, |x − y|^{1−ε}) was studied by Kahane [17] and Talagrand [29], who investigated the interplay between the dimension N and the distortion D (Kahane studied only the case ε = \frac{1}{2}, and obtained sharp results. Talagrand’s work applies to all ε ∈ (0, 1), but is not sharp).

Here we show that in Assouad’s theorem one can take N to depend only on the doubling constant K, but not on ε ∈ (0, 1/2).

Theorem 1.2. For every K > 0 there exists N = N(K) ∈ ℕ, and for every ε ∈ (0, 1/2) and K > 0 there exists D = D(K, ε) ∈ (1, ∞), such that for every separable metric space (X, d) with doubling constant K, the metric space (X, d^{1−ε}) admits a bi-Lipschitz embedding into ℝ^{N} with distortion at most D.

Our argument yields the bounds N(K) ≲ log K and D(K, ε) ≲ (\frac{log K}{ε} )^{2}. More generally, for every δ ∈ (0, 1] our argument yields the bounds

N(K) ≲ \frac{log K}{δ} and D(K, ε) ≲ (\frac{log K}{ε} )^{1+δ} .  (2)

Here and in what follows, the symbols ≲, ≳ indicate the corresponding inequalities up to an absolute multiplicative factor.

In the rest of this introduction we will describe some additional results and question related to the bi-Lipschitz embeddability problem in ℝ^{N}.

1.1. The Lang-Plaut problem and snowflakes of the Heisenberg group. Despite major efforts by many mathematicians, the bi-Lipschitz embeddability problem in ℝ^{N} remains wide open. A variety of sufficient intrinsic conditions on a metric space (X, d) are known which ensure that it admits a bi-Lipschitz embedding in some Euclidean space ℝ^{N}, but these conditions are far from necessary.

A necessary condition for a metric space (X, d) to admit a bi-Lipschitz embedding into some ℝ^{N} (in addition to being doubling) is that it admits a bi-Lipschitz embedding into ℓ_{2}, i.e., its Euclidean distortion satisfies c_{2}(X) < ∞. All the known examples of doubling metric spaces that do not admit a bi-Lipschitz embedding into any ℝ^{N} actually do not admit a bi-Lipschitz embedding into infinite dimensional Hilbert space as well. This led Lang and Plaut [20, Question 2.4] to ask the following question.

Question 1 (Lang-Plaut problem). Is it necessary and sufficient for a metric space (X, d) to admit a bi-Lipschitz embedding into some ℝ^{N} that it is doubling and it admits a bi-Lipschitz embedding into Hilbert space? Equivalently, does every doubling subset of Hilbert space admit a bi-Lipschitz embedding into some ℝ^{N}?

By a simple argument (presented in Section 4), the Lang-Plaut problem can be restated quantitatively as follows. Is it true that for every K > 0 there is N = N(K) ∈ ℕ and D = D(K) ∈ (1, ∞) such that if X ⊆ ℓ_{2} has doubling constant K then c_{ℝ^{N}} (X) ⩽ D?

One might argue whether or not a positive answer to the Lang-Plaut problem would resolve the bi-Lipschitz embedding problem into ℝ^{N}, since it is not obvious that the condition that X admits a bi-Lipschitz embedding into Hilbert space can be restated in terms of the intrinsic geometry of X. But, it is possible to characterize bi-Lipschitz embeddability into ℓ_{2} in terms of a family of distance inequalities, i.e., intrinsically, without using the word “embedding”. Indeed, as shown by Linial-London-Rabinovich [23] (extending the corresponding classical result of Schoenberg [26] in the isometric category), c_{2}(X) ⩽ D if and only if for all n ∈ ℕ, x_{1}, …, x_{n} ∈ X and every n × n symmetric positive semidefinite matrix Q = (q_{ij}), all of whose rows sum to 0, the following inequality holds true:

∑_{i=1}^{n} ∑_{j=1}^{n} max{q_{ij}, 0}d(x_{i}, x_{j})^{2} ⩽ D^{2} ∑_{i=1}^{n} ∑_{j=1}^{n} max{−q_{ij}, 0}d(x_{i}, x_{j})^{2}.  (3)

Hence, a positive answer to the Lang-Plaut question would yield a characterization of bi-Lipschitz embeddability into some ℝ^{N} in terms of the doubling condition, and the family of distance inequalities (3). We believe that this would yield a satisfactory answer to the bi-Lipschitz embeddability problem in ℝ^{N}, though there does not seem to be evidence supporting a positive answer to the the Lang-Plaut question.

A potential source of doubling subsets of Hilbert space that might yield a counter-example to the Lang-Plaut problem is Assouad’s theorem itself. When allowing embeddings into infinite dimensional Hilbert space rather than into ℝ^{N}, the asymptotics in terms of ε of D(K, ε) in Assouad’s theorem are known [21] (see also [24]). Specifically, if (X, d) has doubling constant K then c_{2}(X) ⩽ C(K)/\sqrt{ε} for some C(K) ∈ (0, ∞). This dependence on ε is sharp up to the value of C(K), as shown in [21, Remark 5.4].

If (X, d) has doubling constant K then the space (X, d^{1−ε}) has doubling constant bounded uniformly in ε ∈ (0, 1/2), but, in its C(K)/\sqrt{ε}-distortion embedding into ℓ_{2} it might have an image that is not a doubling subset of ℓ_{2}, with doubling constant independent of ε, due to the large distortion. We therefore ask the following question:

Question 2. Is it true that for every K ∈ (1, ∞) there exist a(K), b(K) ∈ (0, ∞) with the following property. If (X, d) has doubling constant K and ε ∈ (0, 1/2) then there exists f : X → ℓ_{2} such that a(K)\sqrt{ε}d(x, y)^{1−ε} ⩽ ∥f(x) − f(y)∥ ⩽ d(x, y)^{1−ε} for all x, y ∈ X, and f(X) ⊆ ℓ_{2} has doubling constant b(K).

Observe that due to Theorem 1.2, with the explicit bounds stated in (2), if we replaced in Question 2 the term \sqrt{ε} by ε^{1+δ} for any δ ∈ (0, 1], then the answer would be positive, and even the image of the embedding would be finite dimensional with dimension depending only on K and δ.

In spite of the fact that we don’t know the answer to Question 2, we do know that the answer is positive for the Heisenberg group. For n ∈ ℕ, the n’th Heisenberg group ℍ_{n} is ℂ^{n} × ℝ, equipped with the following group product:

(w, s) · (z, t) = (w + z, s + t + 2 ∑_{j=1}^{n} ℑ (w_{j}\overline{z_{j}}))

∀w = (w_{1}, …, w_{n}), z = (z_{1}, …, z_{n}) ∈ ℂ^{n}, ∀s, t ∈ ℝ.

Thus (0, 0) is the identity of ℍ_{n} and for (z, t) ∈ ℍ_{n} we have (z, t)^{−1} = (−z, −t).

The Koranyi norm on ℍ_{n} is defined for (z, t) ∈ ℍ_{n} by N_{0}(z, t) = \sqrt[4]{|z|^{4} + t^{2}}, where |z|^{2} = ∑_{j=1}^{n} |z_{j}|^{2}. For g, h ∈ ℍ_{n} we have N_{0}(gh^{−1}) ⩽ N_{0}(g) + N_{0}(h) (see [18, 9]). Thus d_{N_{0}}(g, h) = N_{0}(h^{−1}g) is a left-invariant metric on ℍ_{n}. One can check that the Lebesgue measure is a Haar measure of ℍ_{n}, and that (ℍ_{n}, d_{N_{0}}) has doubling constant e^{O(n)}.

In Section 4 we observe that a result of [22] implies the following statement.

Theorem 1.3. For every ε ∈ (0, 1/2) and for every n ∈ ℕ, there exists f_{ε} : ℍ_{n} → ℓ_{2} satisfying \sqrt{ε}d_{N_{0}}(x, y)^{1−ε} ⩽ ∥f_{ε}(x) − f_{ε}(y)∥ ⩽ d_{N_{0}}(x, y)^{1−ε} for all x, y ∈ ℍ_{n}, and such that f_{ε}(ℍ_{n}) is a doubling subset of ℓ_{2}, with doubling constant e^{O(n)}.

We also show in Section 4 that Theorem 1.3 is sharp, even without the requirement that the image of ℍ_{n} is doubling with constant independent of ε:

c_{2} (ℍ_{n}, d_{N_{0}}^{1−ε}) ≳ \frac{1}{\sqrt{ε}} ∀ ε ∈ (0, 1/2).  (4)

This raises the following question:

Question 3. Is it true that for every fixed N ∈ ℕ we have lim_{ε→0} c_{ℝ^{N}} (ℍ_{1}, d_{N_{0}}^{1−ε}) \sqrt{ε} = ∞?

A positive answer to Question 3 would imply a negative answer to the Lang-Plaut problem, since otherwise there would be N ∈ ℕ and D ∈ (1, ∞) satisfying c_{ℝ^{N}} (f_{ε}(ℍ_{1})) ⩽ D for all ε ∈ (0, 1/2), where f_{ε} is the Euclidean embedding of (ℍ_{1}, d_{N_{0}}^{1−ε}) from Theorem 1.3. This would yield the bound c_{ℝ^{N}} (ℍ_{1}, d_{N_{0}}^{1−ε}) \sqrt{ε} ⩽ D.

1.2. Previous work and an overview of the proof of Theorem 1.2. The classical proof of Assouad’s theorem [4, 15] yields the dimension bound N(K, ε) ⩽ c(K)/ε^{O(1)}. In [13] Gupta-Krauthgamer-Lee announced a similar bound on N(K, ε) with a much better dependence of c(K) on K, yet the same bound in terms of ε (the proof of this assertion of [13] hasn’t appeared since the 2003 announcement, and in particular the dependence on ε was not stated there explicitly, but it seems to us that the proof technique suggested in [13] would lead to this bound). A similar bound follows from the work of Har-Peled and Mendel [14], who studied in addition embeddings into ℓ_{∞}^{N}, yielding a 1 + δ distortion result. The best previously known bound is due to Abraham-Bartal-Neiman [1], who proved that N(K, ε) ⩽ c(K) log(1/ε). In the context of the Lang-Plaut problem, Gottlieb-Krauthgamer [12], and Bartal-Recht-Schulman [6], proved that if X ⊆ ℓ_{2} has doubling constant K then for all δ ∈ (0, 1) the (1 − ε)-snowflake of X embeds with distortion 1 + δ into ℝ^{c(K,δ)/ε^{O(1)}}; the main point in these works, however, is to obtain a 1 + δ distortion embedding, which is impossible in the context of general doubling metric spaces that are not necessarily isometric to a subset of ℓ_{2}.

Our proof of Theorem 1.2 builds heavily on the method of Abraham-Bartal-Neiman [1]. In essence, our proof should be viewed as an optimization of the argument of [1] which uses degrees of freedom that were available in the construction of [1] but were not previously exploited. This requires subtle changes in the proof of [1], and in particular we were surprised that such changes can lead to a complete removal of the dependence on ε of the dimension N in Assouad’s theorem. Though somewhat delicate, these changes are of a technical nature, and the key conceptual ideas can be found in [1].

The proof of Theorem 1.2 is based on a construction of a distribution over random embeddings, arising from a certain family of random multi-scale partitions of the metric space (X, d). At every possible distance scale we provide a mapping to ℝ which is essentially the truncated distance to the “boundary” of the random partition. We then combine all the possible scales into a single embedding into ℝ, using an idea of Assouad [4] which multiplies every scale by an appropriate factor that enables us to control the total expansion over all scales. The lower bound on the distance of the image of every pair of points in X will come from a single critical scale. Instead of showing sufficient contribution for every pair, we first focus on certain nets of the space at appropriate scales, showing that this suffices to prove the desired lower bound on all pairs. The bulk of the proof consists of arguing that not only the net pairs will have sufficient contribution, but that this will happen with high probability (depending on ε), and with very few dependencies on other net points. To show this we use, as in [1], a localization property of the “padding event” of the random partitions: this event is stochastically independent of the “far away” structure of the partition. The ball expected to be padded is very small (which causes additional distortion), but on the other hand the padding probability is high. The fact that the radius of our padded ball is small (as a function of ε) forces us to define the original distance scales to be also be a function of ε. Finally, to argue that the desired lower bound happens for all pairs with positive probability, even though the number of dimensions at our disposal is small, we use the Lovász Local Lemma.

Acknowledgements. We are grateful to Tim Austin and Bruce Kleiner for helpful discussions.

2. Preliminaries

Due to (1) it suffices to prove Theorem 1.2 when X is finite, provided that the resulting distortion D(K, ε) and dimension N(K) do not depend on |X|. We will therefore assume from now on that X is finite. This assumption is actually not necessary for our argument, but it serves the role of allowing us to ignore measurability issues that might arise in the random partitioning arguments.

For a partition P of X and x ∈ X let P (x) ∈ P be the set in P to which x belongs. For s > 0 the partition P is called s-bounded if the diameter of P (x) is at most s for all x ∈ X.

There is a canonical way to obtain partitions from balls. Given x_{1}, …, x_{n} ∈ X and r_{1}, …, r_{n} ∈ (0, ∞), define a partition P_{r_{1},...,r_{n}}^{x_{1},...,x_{n}} of ⋃_{j=1}^{n} B(x_{j}, r_{j}) by

P_{r_{1},...,r_{n}}^{x_{1},...,x_{n}} =^{def} {B(x_{1}, r_{1})} ⋃ {B(x_{j}, r_{j}) ∖ ⋃_{i=1}^{j−1} B(x_{i}, r_{i})}_{j=2}^{n} ∖ {∅}.  (5)

In particular, given s > 0 the partition P_{r_{1},...,r_{n}}^{x_{1},...,x_{n}} is an s-bounded partition of X whenever {x_{1}, …, x_{n}} is an s/4-net of X and r_{1}, …, r_{n} ∈ [s/4, s/2].

As in [1], we will use random partitions of the form P_{r_{1},...,r_{n}}^{x_{1},...,x_{n}}, where the radii r_{1}, …, r_{n} are appropriately chosen random variables. We present the proofs of the necessary properties of these partitions below, even though they follow from [1]. We do so since the argument of [1] is carried out in much greater generality because in [1] these methods are used for other purposes for which more general constructions are needed. Our argument below is simpler than the proof in [1] both because it deals with the special case that we need, but also because the proof here is different from [1] (relying, of course, on the same ideas).

Lemma 2.1. Fix x ∈ X. For s > 0 and K > 1 let R be a random variable with the following density

ϕ_{s}(r) =^{def} \frac{16K^{8} log K}{s(K^{4} − 1)} K^{−16r/s}1_{[s/4,s/2]}(r).  (6)

Then for every β > 0 and every y ∈ X we have

ℙ [B(x, R) ∩ B(y, βs) ∉ {∅, B(y, βs)}]

⩽ (1 − K^{−32β}) (ℙ [B(y, βs) ∩ B(x, R) ≠ ∅] + \frac{1}{K^{4} − 1}) . (7)

Proof. Fix x, y ∈ X and define

a =^{def} min_{z∈B(y,βs)} d(x, z) and b =^{def} max_{z∈B(y,βs)} d(x, z).

By the triangle inequality,

b − a ⩽ 2βs.  (8)

Hence,

ℙ [B(x, R) ∩ B(y, βs) ∉ {∅, B(y, βs)}] = ∫_{max{a,s/4}}^{b} ϕ_{s}(r)dr

⩽ \frac{K^{8}}{K^{4} − 1} (K^{−16 max\{a,s/4\}/s} − K^{−16b/s}) ⩽^{(8)} \frac{K^{8}}{K^{4} − 1}K^{−16 max\{a,s/4\}/s} (1 − K^{−32β}) . (9)

Similarly,

ℙ [B(y, βs) ∩ B(x, R) ≠ ∅] = ∫_{max\{a,s/4\}}^{s/2} ϕ_{s}(r)dr = \frac{K^{8}}{K^{4} − 1} (K^{−16 max\{a,s/4\}/s} − K^{−8}) . (10)

The desired inequality (7) now follows from (9) and (10). □

Lemma 2.2. Fix s > 0, K ⩾ 2. Assume that (X, d) has doubling constant at most K. Let {x_{1}, …, x_{n}} ⊆ X be an s/4-net of X, and let R_{1}, …, R_{n} be i.i.d. random variables whose distribution is given by (6). Then for every y ∈ X and β ∈ (0, 1/40) we have,

ℙ [B(y, βs) ⊆ P_{R_{1},...,R_{n}}^{x_{1},...,x_{n}}(y)] ⩾ K^{−64β}.

Proof. For every j ∈ {1, …, n} consider the following event:

A_{j} =^{def} (⋂_{i=1}^{j−1} {B(x_{i}, R_{i}) ∩ B(y, βs) = ∅}) ⋂ {B(x_{j}, R_{j}) ∩ B(y, βs) ∉ {∅, B(y, βs)} }.

For A_{j} to occur we need in particular to have B(x_{j}, R_{j}) ∩ B(y, βs) ≠ ∅. Since R_{j}, βs ⩽ s/2, this implies that j ∈ J_{y}, where

J_{y} =^{def} {j ∈ {1, …, n} : x_{j} ∈ B (y, s)} .

We can cover B(y, s) by at most K^{3} balls of radius s/8. Since {x_{1}, …, x_{n}} is an s/4-net, each of these balls can contain at most one of the x_{i}. Thus

|J_{y}| ⩽ K^{3}.  (11)

We must have B(x_{j}, R_{j})∩B(y, βs) ≠ ∅ for some j ∈ J_{y}, and therefore using the independence of R_{1}, … R_{n} we see that,

1 = ∑_{j∈J_{y}} ℙ [B(x_{j}, R_{j}) ∩ B(y, βs) ≠ ∅ ∧ B(x_{i}, R_{i}) ∩ B(y, βs) = ∅ ∀i < j]

= ∑_{j∈J_{y}} (∏_{i=1}^{j−1} ℙ [B(x_{i}, R_{i}) ∩ B(y, βs) = ∅]) ℙ [B(x_{j}, R_{j}) ∩ B(y, βs) ≠ ∅] . (12)

Now, by the definition of the partition P_{R_{1},...,R_{n}}^{x_{1},...,x_{n}} we have

{B(y, βs) ⊈ P_{R_{1},...,R_{n}}^{x_{1},...,x_{n}}(x)} = ⋃_{j∈J_{y}} A_{j}.

Thus, using the independence of R_{1}, … R_{n} once more,

1 − ℙ [B(y, βs) ⊆ P_{R_{1},...,R_{n}}^{x_{1},...,x_{n}}(x)] ⩽ ∑_{j∈J_{y}} ℙ [A_{j}]

= ∑_{j∈J_{y}} (∏_{i=1}^{j−1} ℙ [B(x_{i}, R_{i}) ∩ B(y, βs) = ∅]) ℙ[B(x_{j}, R_{j}) ∩ B(y, βs) ∉ {∅, B(y, βs)} ]

⩽^{(7)∧(12)} (1 − K^{−32β}) + (1 − K^{−32β}) \frac{|J_{y}|}{K^{4} − 1}
⩽^{(11)} (1 − K^{−32β}) (1 + \frac{K^{3}}{K^{4} − 1})
⩽ 1 − K^{−64β},  (13)

Where in (13) we used the fact that since K ⩾ 2 and β < 1/40, we have \frac{K^{3}}{K^{4}−1} ⩽ K^{−32β}. Indeed, this is equivalent to 32β ⩽ \frac{log(K−K^{−3})}{log K}. But, the function K ↦ \frac{log(K−K^{−3})}{log K} is increasing on (1, ∞), since its derivative is \frac{4}{(K^{5}−K) log K} + \frac{log(K^{4}/(K^{4}−1))}{K(log K)^{2}} ⩾ 0. Thus it suffices to check

that 32β ⩽ \frac{log(2−2^{−3})}{log 2}, which is true since β < 1/40. □

3. The random embedding

Fix ε ∈ (0, 1/2), θ ∈ (0, 1) and K ⩾ 2. Write K = e^{γ}, and define

N =^{def} ⌈\frac{cγ}{θ} ⌉ = ⌈\frac{c log K}{θ} ⌉ ,  (14)

where c > 0 is a universal constant that will be determined later. It will also be convenient to write

τ =^{def} \frac{ε^{θ}}{32γ^{θ}} .  (15)

Let (X, d) be a finite metric space whose doubling constant is at most K. By normalization assume that diam(X) = 1. For every i ∈ ℕ let \{x_{1}^{i}, …, x_{n_{i}}^{i}\} be a \frac{1}{4}τ^{i/(1−ε)}-net of X. For every i, k ∈ ℕ and j ∈ {1, …, n_{i}} let R_{ij}^{k} be a random variable whose density is ϕ_{s}, as given in (6), with s = τ^{i/(1−ε)}. We will also use random variables {U_{i}^{k}(C) : i, k ∈ ℕ, C ⊆ X}, each of which is uniformly distributed on the interval [0, 1] (thus for each i, k ∈ ℕ we have 2^{|X|} such random variables). Throughout the argument below it is assumed that the random variables

{R_{ij}^{k} : i, k ∈ ℕ, j ∈ {1, …, n_{i}}} ⋃ {U_{i}^{k}(C) : i, k ∈ ℕ, C ⊆ X}  (16)

are mutually independent and defined on some probability space (Ω, ℙ).

We will now consider the random partitions

P_{i}^{k} =^{def} P_{R_{i1}^{k},...,R_{in_{i}}^{k}}^{x_{1}^{i},...,x_{n_{i}}^{i}},  (17)

where P_{R_{i1}^{k},...,R_{in_{i}}^{k}}^{x_{1},...,x_{n_{i}}} is defined as in (5). For i ∈ ℕ and k ∈ {1, …, N} define a random mapping

f_{i}^{k} : X → ℝ by

f_{i}^{k}(x) =^{def} U_{i}^{k} (P_{i}^{k}(x)) · min \{τ^{i}, 64γτ^{− \frac{iε}{1−ε} −1}d (x, X ∖ P_{i}^{k}(x))\} .  (18)

Finally, we define a random embedding F : X → ℝ^{N} as follows:

F (x) = (\frac{∑_{i=1}^{∞} f_{i}^{1}(x)}{\sqrt{N}}, …, \frac{∑_{i=1}^{∞} f_{i}^{N}(x)}{\sqrt{N}}) ∈ ℝ^{N}.  (19)

Note that by the definition of f_{i}^{k}, the sums appearing in (19) converge geometrically.

Although F is random, it satisfies the desired (1 − ε)-Hölder condition deterministically. The randomness will enter when we prove that with positive probability ∥F (x) − F (y)∥_{2} satisfies the desired lower bound for all x, y ∈ X.

Lemma 3.1. For every x, y ∈ X we have

∥F (x) − F (y)∥_{2} ⩽ max_{k∈\{1,...,N\}} ∑_{i=1}^{∞} |f_{i}^{k}(x) − f_{i}^{k}(y)| ≲ \frac{γ^{(1+θ)(1−ε)}}{ε^{1+θ}} d(x, y)^{1−ε}

≲ (\frac{log K}{ε} )^{1+θ} d(x, y)^{1−ε}. (20)

Proof. We first claim that for all i ∈ ℕ and k ∈ {1, …, N} we have

|f_{i}^{k}(x) − f_{i}^{k}(y)| ⩽ min \{τ^{i}, 64γτ^{− \frac{iε}{1−ε} −1}d(x, y)\} .  (21)

To verify (21) we may assume without loss of generality that f_{i}^{k}(x) > f_{i}^{k}(y). If P_{i}^{k}(x) ≠ P_{i}^{k}(y) then,

f_{i}^{k}(x) − f_{i}^{k}(y) ⩽ f_{i}^{k}(x) ⩽ min \{τ^{i}, 64γτ^{− \frac{iε}{1−ε} −1}d (x, X ∖ P_{i}^{k}(x))\} ,

which is trivially bounded from above by the right hand side of (21) since y ∈ X ∖ P_{i}^{k}(x). If P_{i}^{k}(x) = P_{i}^{k}(y) = C, then it cannot be the case that f_{i}^{k}(y) = U_{i}^{k} (C) τ^{i}, since otherwise f_{i}^{k}(x) ⩽ f_{i}^{k}(y), contrary to our assumption. We therefore necessarily have

f_{i}^{k}(x) − f_{i}^{k}(y) = f_{i}^{k}(x) − 64U_{i}^{k}(C)γτ^{− \frac{iε}{1−ε} −1}d(y, X ∖ C)

⩽ 64U_{i}^{k}(C)γτ^{− \frac{iε}{1−ε} −1} (d(x, X ∖ C) − d(y, X ∖ C)) ⩽ 64γτ^{− \frac{iε}{1−ε} −1}d(x, y). (22)

Since, by the definition (18), f_{i}^{k}(x), f_{i}^{k}(y) ∈ [0, τ^{i}], we also have f_{i}^{k}(x) − f_{i}^{k}(y) ⩽ τ^{i}. This, in conjunction with (22), concludes the proof of (21).

The first inequality of (20) is an immediate consequence of the definition (19). As K = e^{γ}, the third inequality in (20) is a trivial overestimate. Note also that since for all z ∈ X we have ∥F (z)∥_{2} ⩽ ∑_{i=1}^{∞} τ^{i} ≲ τ, the bound in the second inequality of (20) holds true if d(x, y) > τ^{1+ \frac{1}{1−ε}} /(64γ). We may therefore assume that d(x, y) ⩽ τ^{1+ \frac{1}{1−ε}} /(64γ). Let m ∈ ℕ be the integer satisfying

\frac{τ}{64γ} · τ^{\frac{m+1}{1−ε}} < d(x, y) ⩽ \frac{τ}{64γ} · τ^{\frac{m}{1−ε}} .  (23)

Then

∥F (x) − F (y)∥_{2} ⩽ \sqrt{\frac{1}{N} ∑_{k=1}^{N} (∑_{i=1}^{∞} |f_{i}^{k}(x) − f_{i}^{k}(y)|)^{2}} ⩽ max_{k∈\{1,...,N\}} ∑_{i=1}^{∞} |f_{i}^{k}(x) − f_{i}^{k}(y)|

≲^{(21)} \frac{γ}{τ} d(x, y) ∑_{i=1}^{m} τ^{− \frac{iε}{1−ε}} + ∑_{i=m+1}^{∞} τ^{i} ≲^{(15)} \frac{γ^{1+θ}}{ε^{θ}} d(x, y) ∑_{i=1}^{m} τ^{− \frac{iε}{1−ε}} + ∑_{i=m+1}^{∞} τ^{i}. (24)

We estimate the two sums in (24) separately (recalling that 0 < ε, τ < 1/2):

∑_{i=1}^{m} τ^{− \frac{iε}{1−ε}} = \frac{τ^{− \frac{mε}{1−ε}} − 1}{1 − τ^{\frac{ε}{1−ε}}} ≲ \frac{1}{ε}τ^{− \frac{mε}{1−ε}} ≲^{(23)} \frac{τ^{ε}}{εγ^{ε}d(x, y)^{ε}} ≲^{(15)} \frac{1}{εγ^{(1+θ)ε}d(x, y)^{ε}} .  (25)

Similarly,

∑_{i=m+1}^{∞} τ^{i} = \frac{τ^{m+1}}{1 − τ} ≲^{(23)} \frac{γ^{1−ε}}{τ^{1−ε}} d(x, y)^{1−ε} ≲^{(15)} \frac{γ^{(1+θ)(1−ε)}}{ε^{θ}} d(x, y)^{1−ε}.  (26)

The desired bound (20) now follows from substituting (25) and (26) into (24). □

3.1. The Hölder lower bound holds with positive probability. For every i ∈ ℕ write

δ_{i} =^{def} τ^{\frac{i+2}{1−ε}} (\frac{4ε}{c^{∗}γ} )^{\frac{1}{1−ε}} ,  (27)

where c^{∗} is the implied universal constant in the final inequality of (20). Let 𝒩_{i} be a δ_{i}-net of X.

Consider the following set:

M =^{def} \{(i, u, v) ∈ ℕ × 𝒩_{i} × 𝒩_{i} : τ^{\frac{i}{1−ε}} < d(u, v) ⩽ 3τ^{\frac{i−1}{1−ε}} \} .  (28)

For every (i, u, v) ∈ M define G(i, u, v) ⊆ {1, …, N} as follows.

G(i, u, v) =^{def} \{k ∈ \{1, …, N\} : |∑_{j=1}^{∞} f_{j}^{k}(u) − ∑_{j=1}^{∞} f_{j}^{k}(v)| ⩾ \frac{τ^{i+1}}{2} \} .  (29)

For every (i, u, v) ∈ M let E(i, u, v) ⊆ Ω be the following event:

E(i, u, v) =^{def} \{|G(i, u, v)| ⩾ \frac{N}{2} \} ,  (30)

and consider the event E ⊆ Ω given by:

E =^{def} ⋂_{(i,u,v)∈M} E(i, u, v).  (31)

The relevance of the event E is explained in the following lemma.

Lemma 3.2. If the event E occurs then for all x, y ∈ X we have

∥F (x) − F (y)∥_{2} ≳ (\frac{ε}{log K} )^{2θ} d(x, y)^{1−ε}.

Proof. Let i be the integer such that

τ^{\frac{i}{1−ε}} < d(x, y) ⩽ τ^{\frac{i−1}{1−ε}}  (32)

Since 𝒩_{i} is a δ_{i}-net, where δ_{i} is given in (27), there exist u, v ∈ 𝒩_{i} such that

max\{d(u, x), d(v, y)\} ⩽ τ^{\frac{i+2}{1−ε}} (\frac{4ε}{c^{∗}γ} )^{\frac{1}{1−ε}} .  (33)

Assume that k ∈ G(i, u, v). By Lemma 3.1 we have

max {|∑_{j=1}^{∞} f_{j}^{k}(u) − ∑_{j=1}^{∞} f_{j}^{k}(x)| , |∑_{j=1}^{∞} f_{j}^{k}(v) − ∑_{j=1}^{∞} f_{j}^{k}(y)|}

⩽^{(20)∧(33)} c^{∗} (\frac{γ}{ε} )^{1+θ} \frac{4τ^{i+2}ε}{c^{∗}γ} =^{(15)} \frac{τ^{i+1}}{8} . (34)

Since k ∈ G(i, u, v) it follows that

|∑_{j=1}^{∞} f_{j}^{k}(x) − ∑_{j=1}^{∞} f_{j}^{k}(y)| ⩾^{(29)∧(34)} \frac{τ^{i+1}}{2} − 2 · \frac{τ^{i+1}}{8} = \frac{τ^{i+1}}{4} .  (35)

Since we are assuming that the event E occurs, the lower bound (35) holds for at least N/2 values of k ∈ {1, …, N}. Thus, by the definition of F,

∥F (x) − F (y)∥_{2} ≳ τ^{i+1} ≳^{(15)∧(32)} (\frac{ε}{γ} )^{2θ} d(x, y)^{1−ε}.  □

Due to Lemma 3.1 and Lemma 3.2, Theorem 1.2 will be proven (with the bounds claimed in (2), with δ = 3θ), once we establish the following lemma.

Lemma 3.3. We have ℙ[E] > 0, provided c in (14) is a large enough universal constant.

The key tool used in the proof of Lemma 3.3 is the Lovász Local Lemma [11]. The variant of this lemma that is stated below is not the same as the classical formulation of the Lovász Local Lemma, but it is a consequence of it, as explained in [1], where a more general statement is needed. For more information on the Lovász Local Lemma and some of its striking applications, see for example the survey of Alon [2].

Lemma 3.4 (Lovász Local Lemma). Fix q ∈ (0, 1) and d ∈ ℕ. Let A_{1}, A_{2}, … A_{n} be measurable sets in some probability space (Ω, ℙ). Let G = (V, E_{G}) be a graph on the vertex set V = {A_{1}, A_{2}, … A_{n}} with maximal degree d. Let ρ : {A_{1}, A_{2}, … A_{n}} → ℕ be a mapping that satisfies the condition

{A_{i}, A_{j}} ∈ E_{G} ⟹ ρ(A_{i}) = ρ(A_{j}).

Assume that for any i ∈ {1, …, n} we have

ℙ [⋂_{j∈Q}(Ω ∖ A_{j}) ∩ A_{i}] ⩽ qℙ [⋂_{j∈Q}(Ω ∖ A_{j})]

for all

Q ⊆ {j ∈ {1, …, n} : {A_{i}, A_{j}} ∉ E_{G} ∧ ρ(A_{i}) ⩾ ρ(A_{j})} .

Assume also that

eq(d + 1) ⩽ 1.  (36)

Then

ℙ [⋂_{i=1}^{n}(Ω ∖ A_{i})] > 0

To use Lemma 3.4 we proceed as follows. For (i, u, v) ∈ M consider the following random subset of {1, …, k}:

L(i, u, v) =^{def} {k ∈ {1, …, N} : |∑_{j=1}^{i} f_{j}^{k}(u) − ∑_{j=1}^{i} f_{j}^{k}(v)| ⩾ 2τ^{i+1}} .  (37)

For (i, u, v) ∈ M and k ∈ {1, …, N} define the following event:

S(i, u, v, k) =^{def} {k ∈ L(i, u, v)}.  (38)

Finally, we also define the following event for all (i, u, v) ∈ M:

T (i, u, v) =^{def} \{|L(i, u, v)| ⩾ \frac{N}{2} \} .  (39)

Lemma 3.5. For all (i, u, v) ∈ M we have T (i, u, v) ⊆ E(i, u, v).

Proof. Using (21) we see that for all k ∈ {1, …, N},

| ∑_{j=i+1}^{∞} f_{j}^{k}(u) − ∑_{j=i+1}^{∞} f_{j}^{k}(v)| ⩽ ∑_{j=i+1}^{∞} τ^{j} ⩽ \frac{3}{2}τ^{i+1}.  (40)

Hence, if k ∈ L(i, u, v) then

|∑_{j=1}^{∞} f_{j}^{k}(u) − ∑_{j=1}^{∞} f_{j}^{k}(v)| ⩾ |∑_{j=1}^{i} f_{j}^{k}(u) − ∑_{j=1}^{i} f_{j}^{k}(v)| − | ∑_{j=i+1}^{∞} f_{j}^{k}(u) − ∑_{j=i+1}^{∞} f_{j}^{k}(v)| ⩾^{(37)∧(40)} \frac{τ^{i+1}}{2} .

This means that L(i, u, v) ⊆ G(i, u, v), and hence |L(i, u, v)| ⩾ \frac{N}{2} ⟹ |G(i, u, v)| ⩾ \frac{N}{2} . □

Before proceeding with the proof of Lemma 3.3, it is beneficial for us to introduce some notation related to the random partitions that are used in the definition of the embedding F. For i ∈ ℕ and k ∈ {1, …, N} the partition P_{i}^{k} was defined in (17), where {x_{1}^{i}, …, x_{n_{i}}^{i}} is a fixed \frac{1}{4}τ^{i/(1−ε)}-net of X, and R_{i1}^{k}, …, R_{in_{i}}^{k} are i.i.d. random variables whose density is ϕ_{s} as given in (6), with s = τ^{i/(1−ε)}. For every y ∈ X define

J(i, y) =^{def} \{j ∈ \{1, …, n_{i}\} : d (y, x_{j}^{i}) ⩽ 2τ^{\frac{i}{1−ε}} \} .  (41)

We will consider the following random variable

j(i, k, y) =^{def} min {j ∈ J(i, y) : y ∈ B (x_{j}^{i}, R_{ij}^{k})} .  (42)

To see that j(i, k, y) is well-defined, note that since \{x_{1}^{i}, …, x_{n_{i}}^{i}\} is a \frac{1}{4}τ^{i/(1−ε)}-net of X and R_{i1}^{k}, …, R_{in_{i}}^{k} ⩾ \frac{1}{4}τ^{i/(1−ε)}, there must be some j ∈ \{1, …, N\} for which y ∈ B (x_{j}^{i}, R_{ij}^{k}), and since R_{ij}^{k} ⩽ \frac{1}{2}τ^{i/(1−ε)} necessarily j ∈ J(i, y).

¿From the definition (5) we see that

P_{i}^{k}(y) = B (x_{j(i,k,y)}^{i}, R_{ij(i,k,y)}^{k}) ∖ ⋃_{ℓ=1}^{j(i,k,y)−1} B (x_{ℓ}^{i}, R_{iℓ}^{k}) .  (43)

But note that if there exists z ∈ B (x_{ℓ}^{i}, R_{iℓ}^{k}) ∩ B (x_{j(i,k,y)}^{i}, R_{ij(i,k,y)}^{k}) then

d (x_{ℓ}^{i}, y) ⩽ d (x_{ℓ}^{i}, z) + d (z, x_{j(i,k,y)}^{i}) + d (x_{j(i,k,y)}^{i}, y) ⩽ R_{iℓ}^{k} + 2R_{ij(i,k,y)}^{k} ⩽ 2τ^{\frac{i}{1−ε}} ,

implying that ℓ ∈ J(i, y) . It follows from this that (43) can be rewritten as follows:

P_{i}^{k}(y) = B (x_{j(i,k,y)}^{i}, R_{ij(i,k,y)}^{k}) ∖ ⋃_{ℓ∈J(i,y)∩{1,...,j(i,k,y)−1}} B (x_{ℓ}^{i}, R_{iℓ}^{k}) .  (44)

To continue with our plan to use Lemma 3.4, we define a graph H = (V, E_{H}), where V =^{def} {T (i, u, v) : (i, u, v) ∈ M}, and a mapping ρ : V → ℕ, as follows.

\{T (i, u, v), T (i′, u′, v′)\} ∈ E_{H} ⟺ i = i′ ∧ d (\{u, v\}, \{u′, v′\}) ⩽ 4τ^{\frac{i}{1−ε}} ,  (45)
ρ(T (i, u, v)) = i.  (46)

Lemma 3.6. The maximal degree of H is at most K^{c^{∗∗}(log log K+log(1/ε))}, where c^{∗∗} ∈ (0, ∞) is a universal constant.

Proof. Given (i, u, v) ∈ M, we need to bound the number of (i, u′, v′) ∈ M satisfying d ({u, v}, {u′, v′}) ⩽ 4τ^{i/(1−ε)}. We may assume that d (u, u′) ⩽ 4τ^{i/(1−ε)}. Recall that from the definition of M in (28) we know that d(u, v), d(u′, v′) ⩽ 3τ^{(i−1)/(1−ε)}. Hence the points v, u′, v′ are all in the ball B of radius r = 4τ^{(i−1)/(1−ε)} centered at u, implying that the number of (i, u′, v′) as above is at most |B ∩ 𝒩_{i}|^{2}. Since (X, d) is K-doubling, B can be covered by at most K^{1+log_{2}(2r/δ_{i})} balls of radius δ_{i}/2, each of which contains at most one point from the δ_{i}-net 𝒩_{i} (recall (27) for the definition of δ_{i}). Hence, the maximal degree of H is at most

K^{4+2 log_{2}(r/δ_{i})} = K^{O(log log K+log(1/ε))}.  □

Lemma 3.7. For every (i, u, v) ∈ M and for every

Q ⊆ {(i′, u′, v′) ∈ M : i ⩾ i′ ∧ {T (i, u, v), T (i′, u′, v′)} ∉ E_{H}},  (47)

we have

ℙ [ ⋂_{(i′,u′,v′)∈Q} T (i′, v′, u′) ∖ T (i, u, v)] ⩽ (\frac{ε}{log K} )^{θN/2} ℙ [ ⋂_{(i′,u′,v′)∈Q} T (i′, v′, u′)] .  (48)

Proof. Denote

W =^{def} ⋂_{(i′,u′,v′)∈Q} T (i′, v′, u′).

Consider the following subsets 𝒳 , 𝒴 of the random variables given in (16):

𝒳 =^{def} {R_{i′j}^{k} : i′ ∈ {1, …, i − 1}, j ∈ {1, …, n_{i′}}, k ∈ {1, …, N}}

⋃ {U_{i′}^{k}(C) : i′ ∈ {1, …, i − 1}, k ∈ {1, …, N}, C ⊆ X},

𝒴 =^{def} {R_{ij}^{k} : j ∈ {1, …, n_{i}} ∖ J(i, u), k ∈ {1, …, N}}

⋃ {U_{i}^{k}(C) : k ∈ {1, …, N}, C ⊆ X ∖ B (u, 2τ^{i/(1−ε)}) }.

The event W depends only on the variables 𝒳 ∪ 𝒴 . Indeed, for (i′, u′, v′) ∈ Q with i′ < i it follows from the definitions (39),(37),(18) that the event T (i′, u′, v′) depends only on the variables 𝒳 . If (i, u′, v′) ∈ Q and {T (i, u, v), T (i, u′, v′)} ∉ E_{H} then it follows from (45) that d(u′, u), d(v′, u) > 4τ^{i/(1−ε)}. Since the diameter of P_{i}^{k}(u′), P_{i}^{k}(v′) is at most τ^{i/(1−ε)}, it follows that P_{i}^{k}(u′), P_{i}^{k}(v′) ⊆ X ∖B (u, 2τ^{i/(1−ε)}), and hence U_{i}^{k}(P_{i}^{k}(u′)), U_{i}^{k}(P_{i}^{k}(v′)) ∈ 𝒴 . Similarly, we know that J(i, u)∩J(i, u′) = ∅ and J(i, u)∩J(i, v′) = ∅, and hence from the identity (44) we know that P_{i}^{k}(u′), P_{i}^{k}(v′) depend only on the variables 𝒴 . These observations, combined with the definition (18), imply that f_{i}^{k}(u′), f_{i}^{k}(v′) depend only on the variables 𝒴 , and from the definitions (39),(37) we conclude that the event T (i, u′, v′) depends only on the variables 𝒳 ∪ 𝒴 , as required.

Recalling the definitions (37), (38), (39), it follows from the above argument that

ℙ [W ∩ T (i, u, v)] = ∫_{W} ℙ [∑_{k=1}^{N} 1_{S(i,u,v,k)} ⩾ \frac{N}{2} | 𝒳 ∪ 𝒴 ] dℙ.  (49)

To estimate the right hand side of (49), for each k ∈ {1, …, n} consider the event

Z_{k} =^{def} S(i, u, v, k) ∩ \{B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u)\} .  (50)

From (49) we then see that

ℙ [W ∩ T (i, u, v)] ⩾ ∫_{W} ℙ [∑_{k=1}^{N} 1_{Z_{k}} ⩾ \frac{N}{2} | 𝒳 ∪ 𝒴 ] dℙ.  (51)

An application of Lemma 2.2 with β = \frac{τ}{64γ} yields the estimate

ℙ [B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u)] ⩾ K^{−τ/γ} = e^{−τ}.  (52)

Moreover, it follows from the definition (18) that if B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u) then we have

f_{i}^{k}(u) = U_{i}^{k} (P_{i}^{k}(u)) τ^{i}. Hence, recalling the definition (38), we see that

Z_{k} = \{B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u)\}

⋂ {|∑_{j=1}^{i−1} (f_{j}^{k}(u) − f_{j}^{k}(v)) + U_{i}^{k} (P_{i}^{k}(u)) τ^{i} − f_{i}^{k}(v)| ⩾ 2τ^{i+1}} . (53)

¿From the identity (44) we see that the event \{B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u)\} is independent of

𝒳 ∪ 𝒴 . Thus, denoting a =^{def} τ^{−i} ∑_{j=1}^{i−1} (f_{j}^{k}(u) − f_{j}^{k}(v)) − τ^{−i}f_{i}^{k}(v), we have

p =^{def} ℙ [Z_{k}|𝒳 ∪ 𝒴 ]  (54)
=^{(53)} ℙ [B (u, \frac{τ}{64γ} τ^{\frac{i}{1−ε}} ) ⊆ P_{i}^{k}(u)] · ℙ [U_{i}^{k} (P_{i}^{k}(u)) ∉ (a − 2τ, a + 2τ) |𝒳 ∪ 𝒴 ]
⩾^{(52)} e^{−τ}(1 − 4τ)  (55)
⩾ 1 − 5τ,  (56)

where in (55) we used the fact that since d(u, v) > τ^{i/(1−ε)} (by the definition (28) of M), and diam(P_{i}^{k}(u)) ⩽ τ^{i/(1−ε)}, we have P_{i}^{k}(u) ≠ P_{i}^{k}(v), and therefore the random variable U_{i}^{k}(P_{i}^{k}(u)), which is uniformly distributed on [0, 1], is independent of a and 𝒳 ∪ 𝒴 .

Since after fixing the values of 𝒳 ∪𝒴 , the events Z_{1}, …, Z_{N} are independent, the Chernoff bound (see [3, Thm. A.1.12]) implies that

ℙ [∑_{k=1}^{N} 1_{Z_{k}} ⩾ \frac{N}{2} | 𝒳 ∪ 𝒴 ] = 1 − ℙ [∑_{k=1}^{N} 1_{Ω∖Z_{k}} > \frac{N}{2} | 𝒳 ∪ 𝒴 ]

⩾^{(54)} 1 − (e^{p− \frac{1}{2}} \sqrt{2(1 − p)})^{N} ⩾^{(56)} 1 − (10eτ)^{N/2}. (57)

Substituting (57) into (51) shows that

ℙ [W ∩ T (i, u, v)] ⩾ (1 − (30τ)^{N/2}) ℙ[W] ⩾^{(15)} (1 − (\frac{ε}{log K} )^{θN/2}) ℙ[W],

which is the same statement as (48). □

Proof of Lemma 3.3. By Lemma 3.5 we have

ℙ[E] ⩾ ℙ [ ⋂_{(i,u,v)∈M} T (i, u, v)] .

Hence, due to Lemma 3.6 and Lemma 3.7, Lemma 3.3 will follow from Lemma 3.4 if the condition corresponding to (36) holds, i.e.,

e (\frac{ε}{log K} )^{θN/2} (K^{O(log log K+log(1/ε))} + 1) ⩽ 1.

This holds true provided the constant c in the definition (14) of N is large enough. □

4. Snowflakes of the Heisenberg group

As promised in the introduction, we first argue that a positive answer to the qualitative version of the Lang-Plaut question, as appearing in Question 1, implies its quantitative variant, i.e., that for every K > 0 there is N = N(K) ∈ ℕ and D = D(K) ∈ (1, ∞) such that if X ⊆ ℓ_{2} has doubling constant K then c_{ℝ^{N}} (X) ⩽ D. Indeed, if not then there would be some K > 0 and a sequence {X_{n}}_{n=1}^{∞} of subsets of ℓ_{2} with doubling constant K and satisfying c_{ℝ^{n}}(X_{n}) > n. By (1) there are finite subsets F_{n} ⊆ X_{n} with c_{ℝ^{n}}(F_{n}) > n, and by translation and rescaling we may assume that 0 ∈ F_{n} and that F_{n} is contained in the ball of ℓ_{2} centered at 0 of radius 1. Let Y ⊆ ℓ_{2} × ℝ be given by Y = ⋃_{n=1}^{∞} F_{n} × {4^{n}}. One checks that Y has doubling constant O(K), and clearly all the F_{n} embed into Y isometrically. By the assumed positive answer to the Lang-Plaut problem it follows that c_{ℝ^{N}} (F_{n}) ⩽ D for some N ∈ ℕ and D ∈ (1, ∞), a contradicting the fact that c_{ℝ^{N}} (F_{n}) > n for n ⩾ N.

Proof of Theorem 1.3. For θ > 0 define δ_{θ} : ℍ_{n} → ℍ_{n} by δ_{θ}(z, t) = (θz, θ^{2}t). Note that for every measurable A ⊆ ℍ_{n} = ℂ^{n} × ℝ we have vol(δ_{θ}(A)) = θ^{2n+2}vol(A). For p ∈ [1, 2) and (z, t) ∈ ℍ_{n} define

M_{p}(z, t) =^{def} \sqrt[4]{|z|^{4} + t^{2}} (cos (\frac{p}{2} arccos (\frac{|z|^{2}}{\sqrt{|z|^{4} + t^{2}}} )))^{1/p} .

It was shown in [22] that M_{p}(xy^{−1}) ⩽ M_{p}(x) + M_{p}(y) for all x, y ∈ ℍ_{n}. Therefore d_{M_{p}}(x, y) = M_{p}(y^{−1}x) is a left-invariant metric on ℍ_{n}. It was also shown in [22] that \sqrt{1 − \frac{p}{2}}N_{0}(x) ⩽ M_{p}(x) ⩽ N_{0}(x) for all x ∈ ℍ_{n}, and there exists f : ℍ_{n} → ℓ_{2} satisfying ∥f(x) − f(y)∥ = d_{M_{p}}(x, y)^{p/2} for all x, y ∈ ℍ_{n}. Setting p = 2(1 − ε), we see that for all distinct x, y ∈ ℍ_{n} we have

\frac{∥f(x) − f(y)∥}{d_{N_{0}}(x, y)^{1−ε}} = (\frac{d_{M_{p}}(x, y)}{d_{N_{0}}(x, y)})^{p/2} ∈ [ε^{(1−ε)/2}, 1] ⊆ [\sqrt{ε}, 1].

For x ∈ ℍ_{n} and r > 0 denote B_{p}(x, r) = {y ∈ ℍ_{n} : d_{M_{p}}(x, y)^{p/2} ⩽ r}. Note that B_{p}(0, r) = δ_{2^{2/p}}(B_{p}(0, r/2)), since for every θ > 0 and x, y ∈ ℍ_{n} we have d_{M_{p}} (δ_{θ}(x), δ_{θ}(y)) = θd_{M_{p}}(x, y). Hence, by left-invariance of d_{M_{p}}^{p/2} and the Lebesgue measure vol(·), for all x ∈ ℍ_{n} and r > 0

we have vol(B_{p}(x, r)) = 2^{4(n+1)/p}vol(B_{p}(x, r/2)). This implies that (ℍ_{n}, d_{M_{p}}^{p/2}) = (ℍ_{n}, d_{M_{p}}^{1−ε}),

and hence also its isometric copy f(ℍ_{n}) ⊆ ℓ_{2}, has doubling constant 2^{8(n+1)/p} ⩽ 2^{16(n+1)}. □

We end with the proof of the distortion lower bound (4). Assume that f : ℍ_{1} → ℓ_{2} satisfies

d_{N_{0}}(x, y)^{1−ε} ⩽ ∥f(x) − f(y)∥ ⩽ Dd_{N_{0}}(x, y)^{1−ε} ∀ x, y ∈ ℍ_{1}.  (58)

Our goal is to prove that D ≳ 1/\sqrt{ε}. Denote a = (1, 0) ∈ ℍ_{1}, b = (i, 0) ∈ ℍ_{1} and c = aba^{−1}b^{−1} = (0, −4). Writing

B_{m} = {(u + iv, t) ∈ ℍ_{1} : u, v, t ∈ ℤ ∧ N_{0}(u + iv, t) ⩽ m} ,

it follows from [5] that there exists a universal constant C > 0 such that for all m ∈ ℕ we have

∑_{x∈B_{m}} ∑_{k=1}^{m^{2}} \frac{∥f(xc^{k}) − f(x)∥^{2}}{k^{2}} ≲ ∑_{x∈B_{Cm}} (∥f(xa) − f(x)∥^{2} + ∥f(xb) − f(x)∥^{2}) . (59)

Note that for all x ∈ ℍ_{1} we have d_{N_{0}}(xa, x) = N_{0}(a) = 1 and similarly d_{N_{0}}(xb, x) = 1. Moreover, for all k ∈ ℕ and x ∈ ℍ_{1} we have d_{N_{0}}(xc^{k}, x) = N_{0}(c^{k}) = N_{0}(0, −4k) = 2\sqrt{k}. Hence, using (58) and the fact that the cardinality of B_{m} is bounded above and below by universal multiples of m^{4}, inequality (59) becomes D^{2} ≳ ∑_{k=1}^{m^{2}} \frac{N_{0}(c^{k})^{2(1−ε)}}{k^{2}} ≳ ∑_{k=1}^{m^{2}} \frac{1}{k^{1+ε}}. Letting m tend to ∞ we deduce that D^{2} ≳ ∑_{k=1}^{∞} \frac{1}{k^{1+ε}} ≳ \frac{1}{ε}, as required. □

References

[1] I. Abraham, Y. Bartal, and O. Neiman. Embedding metric spaces in their intrinsic dimension. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 363–372, New York, 2008. ACM.

[2] N. Alon. Probabilistic proofs of existence of rare events. In Geometric aspects of functional analysis (1987–88), volume 1376 of Lecture Notes in Math., pages 186–201. Springer, Berlin, 1989.

[3] N. Alon and J. H. Spencer. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken, NJ, third edition, 2008. With an appendix on the life and work of Paul Erdős.

[4] P. Assouad. Plongements lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429–448, 1983.

[5] T. Austin, A. Naor, and R. Tessera. Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces. Preprint available at

http://www.cims.nyu.edu/~naor/homepage%20files/UCHeis9.pdf, 2010.

[6] Y. Bartal, B. Recht, and L. Schulman. Dimensionality reduction: beyond the Johnson-Lindenstrauss bound. To appear in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’2011). Preprint available at

http://pages.cs.wisc.edu/~brecht/papers/07.BRS.local-dim-REVISED.pdf, 2011.

[7] M. Bourdon and H. Pajot. Poincaré inequalities and quasiconformal structure on the boundary of some hyperbolic buildings. Proc. Amer. Math. Soc., 127(8):2315–2324, 1999.

[8] J. Cheeger. Differentiability of Lipschitz functions on metric measure spaces. Geom. Funct. Anal., 9(3):428–517, 1999.

[9] J. Cygan. Subadditivity of homogeneous norms on certain nilpotent Lie groups. Proc. Amer. Math. Soc., 83(1):69–70, 1981.

[10] G. David and T. Toro. Reifenberg flat metric spaces, snowballs, and embeddings. Math. Ann., 315(4):641–710, 1999.

[11] P. Erdős and L. Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam, 1975.

[12] L.-A. Gottlieb and R. Krauthgamer. A nonlinear approach to dimension reduction. To appear in Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’2011).

Preprint available at http://arxiv.org/abs/0907.5477, 2011.

[13] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, pages 534–543. IEEE Computer Society, 2003.

[14] S. Har-Peled and M. Mendel. Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput., 35(5):1148–1184 (electronic), 2006.

[15] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[16] J. Heinonen. Geometric embeddings of metric spaces, volume 90 of Report. University of Jyväskylä Department of Mathematics and Statistics. University of Jyväskylä, Jyväskylä, 2003.

[17] J.-P. Kahane. Hélices et quasi-hélices. In Mathematical analysis and applications, Part B, volume 7 of Adv. in Math. Suppl. Stud., pages 417–433. Academic Press, New York, 1981.

[18] A. Korányi and H. M. Reimann. Quasiconformal mappings on the Heisenberg group. Invent. Math., 80(2):309–338, 1985.

[19] T. J. Laakso. Plane with A_{∞}-weighted metric not bi-Lipschitz embeddable to ℝ^{N}. Bull. London Math. Soc., 34(6):667–676, 2002.

[20] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285–307, 2001.

[21] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180–1190, 2005.

[22] J. R. Lee and A. Naor. L_{p} metrics on the Heisenberg group and the Goemans-Linial conjecture. In 47th Annual IEEE Symposium on Foundations of Computer Science, pages 99–108, 2006. Available at

http://www.cims.nyu.edu/~naor/homepage%20files/L_pHGL.pdf.

[23] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[24] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Preprint available at

http://www.cims.nyu.edu/~naor/homepage%20files/wilder.pdf, 2010.

[25] P. Pansu. Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un. Ann. of Math. (2), 129(1):1–60, 1989.

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

[27] S. Semmes. On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A_{∞}- weights. Rev. Mat. Iberoamericana, 12(2):337–410, 1996.

[28] S. Semmes. Bilipschitz embeddings of metric spaces into Euclidean spaces. Publ. Mat., 43(2):571–653, 1999.

[29] M. Talagrand. Approximating a helix in finitely many dimensions. Ann. Inst. H. Poincaré Probab. Statist., 28(3):355–363, 1992.

Courant Institute, New York University, New York NY 10012

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

Computer Science Department, Princeton University, Princeton NJ 08544-2087

E-mail address: oneiman@princeton.edu