ULTRAMETRIC SKELETONS

MANOR MENDEL AND ASSAF NAOR

Abstract. We prove that for every ε ∈ (0, 1) there exists C_{ε} ∈ (0, ∞) with the following property. If (X, d) is a compact metric space and μ is a Borel probability measure on X then there exists a compact subset S ⊆ X that embeds into an ultrametric space with distortion O(1/ε), and a probability measure ν supported on S satisfying ν (B_{d}(x, r)) ⩽ (μ(B_{d}(x, C_{ε}r))^{1−ε} for all x ∈ X and r ∈ (0, ∞). The dependence of the distortion on ε is sharp. We discuss an extension of this statement to multiple measures, as well as how it implies Talagrand’s majorizing measure theorem.

1. Introduction

Our main result is the following theorem.

Theorem 1.1. For every ε ∈ (0, 1) there exists C_{ε} ∈ (0, ∞) with the following property. Let (X, d) be a compact metric space and let μ be a Borel probability measure on X. Then there exists a compact subset S ⊆ X satisfying

(1) S embeds into an utrametric space with distortion O(1/ε).

(2) There exists a Borel probability measure supported on S satisfying

ν (B_{d}(x, r)) ⩽ (μ(B_{d}(x, C_{ε}r))^{1−ε}  (1)

for all x ∈ X and r ∈ [0, ∞).

Recall that an ultrametric space is a metric space (U, ρ) satisfying the strengthened triangle inequality ρ(x, y) ⩽ max{ρ(x, z), ρ(y, z)} for all x, y, z ∈ U. Saying that (S, d) embeds with distortion D ∈ [1, ∞) into an ultrametric space means that there exists an ultrametric space (U, ρ) and an injection f : S → U satisfying d(x, y) ⩽ ρ(f(x), f(y)) ⩽ Dd(x, y) for all x, y ∈ S. In the statement of Theorem 1.1, and in the rest of this paper, given a metric space (X, d), a point x ∈ X and a radius r ∈ [0, ∞), the corresponding closed ball is denoted B_{d}(x, r) = {y ∈ X : d(y, x) ⩽ r}, and the corresponding open ball is denoted B_{d}^{∘}(x, r) = {y ∈ X : d(y, x) < r}. (We explicitly indicate the underlying metric since the ensuing discussion involves multiple metrics on the same set.)

We call the metric measure space (S, d, ν) from Theorem 1.1 an ultrametric skeleton of the metric measure space (X, d, μ). The literature contains several theorems about the existence of “large” ultrametric subsets of metric spaces; some of these results will be mentioned below. As we shall see, the subset S of Theorem 1.1 must indeed be large, but it is also geometrically “spread out” with respect to the initial probability measure μ. For example, if μ assigns positive mass to two balls B_{d}(x, r) and B_{d}(y, r), where x, y ∈ X satisfy d(x, y) > (C_{ε} +1)r, then the probability measure ν, which is supported on S, cannot assign full mass to any one of these balls. This is one reason why (S, d, ν) serves as a “skeleton” of (X, d, μ).

More significantly, we call (S, d, μ) an ultrametric skeleton because it can be used to deduce global information about the entire initial metric measure space (X, d, μ). Examples of such global applications of statements that are implied by Theorem 1.1 are described in [13, 14], and an additional example will be presented below. As a qualitative illustration of this phenomenon, consider a stochastic process {Z_{t}}_{t∈T}, assuming for simplicity that the index set T is finite and that each random variable Z_{t} has finite second moment. Equip T with the metric d(s, t) = \sqrt{𝔼 [(Z_{s} − Z_{t})^{2}]}. Assume that there exists a unique (random) point τ ∈ T satisfying Z_{τ} = max_{t∈T} Z_{t}. Let μ be the law of τ, and apply Theorem 1.1, say, with ε = 1/2, to the metric measure space (X, d, μ). One obtains a subset S ⊆ X that embeds into an ultrametric space with distortion O(1), and a probability measure ν that is supported on S and satisfies (1) (with ε = 1/2). If σ ∈ S is a random point of S whose law is ν, then it follows that for every x ∈ T, p ∈ (0, 1) and r ∈ [0, ∞), if σ falls into B_{d}(x, r) with probability at least p, then the global maximum τ falls into B_{d}(x, O(r)) with probability at least p^{2}. One can therefore always find a subset of T that is more structured due to the fact that it is approximately an ultrametric space (e.g., such structure can be harnessed for chaining-type arguments), yet this subset reflects the location of the global maximum of {Z_{t}}_{t∈T} in the above distributional/geometric sense. A quantitatively sharp variant of the above qualitative interpretation of Theorem 1.1 is discussed in Section 1.1.1 below.

M. M. was partially supported by ISF grants 221/07 and 93/11, BSF grants 2006009 and 2010021, and a gift from Cisco Research Center. A. N. was partially supported by NSF grant CCF-0832795, BSF grants 2006009 and 2010021, and the Packard Foundation. Part of this work was completed when M. M. was a visiting researcher at Microsoft Research and A. N. was visiting the Quantitative Geometry program at the Mathematical Sciences Research Institute.

1.1. Nonlinear Dvoretzky theorems. Nonlinear Dvoretzky theory, as initiated by Bourgain, Figiel and Milman [4], asks for theorems asserting that any “large” metric space contains a “large” subset that embeds with specified distortion into Hilbert space. We will see below examples of notions of “largeness” of a metric space for which a nonlinear Dvoretzky theorem can be proved. For an explanation of the relation of such problems to the classical Dvoretzky theorem [5], see [4, 1, 14]. Most known nonlinear Dvoretzky theorems actually obtain subsets that admit a low distortion embedding into an ultrametric space. Since ultrametric spaces admit an isometric embedding into Hilbert space [17], such a result falls into the Bourgain-Figiel-Milman framework. Often (see [4, 1]) one can prove an asymptotically matching impossibility result which shows that all subsets of a given metric space that admit a low distortion embedding into Hilbert space must be “small”. Thus, in essence, it is often the case that the best way to find an almost Hilbertian subset is actually to aim for a subset satisfying the seemingly more stringent requirement of being almost ultrametric.

Apply Theorem 1.1 to an n-point metric space (X, d), with μ({x}) = 1/n for all x ∈ X. Since ν is a probability measure on S, there exists x ∈ X with ν({x}) ⩾ 1/|S|. An application of (1) with r = 0 shows that 1/|S| ⩽ μ({x})^{1−ε} = 1/n^{1−ε}, or |S| ⩾ n^{1−ε}. Since S embeds into an ultrametric space with distortion O(1/ε), this shows that Theorem 1.1 implies the sharp solution of the Bourgain-Figiel-Milman nonlinear Dvoreztky problem that was first obtained in [13]. Sharpness in this context means that, as shown in [1], there exists a universal constant c ∈ (0, ∞) and for every n ∈ ℕ there exists an n-point metric space X_{n} such that every S ⊆ X_{n} with |S| ⩾ n^{1−ε} incurs distortion at least c/ε in any embedding into Hilbert space. Thus, the distortion bound in Theorem 1.1 cannot be improved (up to constants), even if we only require that S embeds into Hilbert space.

Assume that (X, d) is a compact metric space of Hausdorff dimension greater than α ∈ (0, ∞). Then there exists [9, 11] an α-Frostman measure on (X, d), i.e., a Borel probability measure μ satisfying μ(B_{d}(x, r)) ⩽ Kr^{α} for every x ∈ X and r ∈ (0, ∞), where K is a constants that may depend on X and α but not on x and r. An application of Theorem 1.1 to (X, d, μ) yields a compact subset S ⊆ X that embeds into an ultrametric space with distortion O(1/ε), and a Borel probability measure ν supported on S satisfying ν(B_{d}(x, r)) ⩽ μ(B_{d}(x, C_{ε}r))^{1−ε} ⩽ K^{1−ε}C_{ε}^{(1−ε)α}r^{(1−ε)α} for all x ∈ X and r ∈ (0, ∞). Hence ν is a (1 − ε)α-Frostman measure on S, implying [11] that S has Hausdorff dimension at least (1−ε)α. Thus Theorem 1.1 implies the sharp solution of the nonlinear Dvoretzky problem for Hausdorff dimension that was first obtained in [14].

More generally, the following result was proved in [14] as the main step towards the solution of a question of Tao concerning the nonlinear Dvoretzky problem for Hausdorff dimension.

Theorem 1.2. For every ε ∈ (0, 1) there exists c_{ε} = e^{O(1/ε^{2})} ∈ (0, ∞) with the following property. Let (X, d) be a compact metric space and let μ be a Borel probability measure on X. Then there exists a compact subset S ⊆ X satisfying

(1) S embeds into an utrametric space with distortion O(1/ε).

(2) If {x_{i}}_{i∈I} ⊆ X and {r_{i}}_{i∈I} ⊆ [0, ∞) satisfy ⋃_{∈I} B_{d}(x_{i}, r_{i}) ⊇ S then

∑_{i∈I} μ (B_{d}(x_{i}, c_{ε}r_{i}))^{1−ε} ⩾ 1.  (2)

Theorem 1.2 is a consequence of Theorem 1.1. Indeed, if S ⊆ X and ν are the subset and probability measure from Theorem 1.1, then 1 = ν(S) ⩽ ∑_{i∈I} ν(B_{d}(x_{i}, r_{i})) ⩽ ∑_{i∈I} μ(B_{d}(x_{i}, C_{ε}r_{i}))^{1−ε} whenever ⋃_{i∈I} B_{d}(x_{i}, r_{i}) ⊇ S. But, Theorem 1.2 is the main reason for the validity of the phenomenon described in Theorem 1.1: here we show how to formally deduce Theorem 1.1 from Theorem 1.2, with C_{ε} = O(c_{ε}/ε) = e^{O(1/ε^{2})}. Alternatively, with more work, one can repeat the proof of Theorem 1.2 in [14] while making changes to several lemmas in order to prove Theorem 1.1 directly, and obtain C_{ε} = c_{ε}. Since the proof of Theorem 1.2 in [14] is quite involved, we believe that it is instructive to establish Theorem 1.1 via the argument described here.

1.1.1. Majorizing measures and stochastic processes. Theorem 1.1 makes it possible to relate the nonlinear Dvoretzky framework of [14] to Talagrand’s nonlinear Dvoretzky theorem [16], and consequently to Talagrand’s majorizing measure theorem [16]. Given a metric space (X, d) let 𝒫_{X} be the Borel probability measures on X. The Fernique-Talagrand γ_{2} functional is defined as follows.

γ_{2}(X, d) = inf_{μ∈𝒫_{X}} sup_{x∈X} ∫_{0}^{∞} \sqrt{log (\frac{1}{μ(B_{d}(x, r))})}dr.  (3)

A nonlinear Dvoretzky-like theorem due to Talagrand [16] asserts that every finite metric space (X, d) has a subset S ⊆ X that embeds into an ultrametric space with distortion O(1) and^{1} γ_{2}(S, d) ≳ γ_{2}(X, d). Talagrand proved this nonlinear version of Dvoretzky’s theorem in order to prove his celebrated majorizing measure theorem, which asserts that if {G_{x}}_{x∈X} is a centered Gaussian process and for x, y ∈ X we set d(x, y) = \sqrt{𝔼 [(G_{x} − G_{y})^{2}]}, then 𝔼 [sup_{x∈X} G_{x}] ≳ γ_{2}(X, d). There is also a simpler earlier matching upper bound on 𝔼 [sup_{x∈X} G_{x}] due to Fernique [6], so 𝔼 [sup_{x∈X} G_{x}] ≍ γ_{2}(X, d). The fact that Talagrand’s nonlinear Dvoretzky theorem implies the majorizing measure theorem is simple; see [16, Prop. 13] and also the discussion in [14, Sec. 1.3].

To understand the link between Theorem 1.1 and Talagrand’s nonlinear Dvoretzky theorem, consider the following quantity, associated to every compact metric space (X, d).

δ_{2}(X, d) = sup_{μ∈𝒫_{X}} inf_{x∈X} ∫_{0}^{∞} \sqrt{log (\frac{1}{μ(B_{d}(x, r))})}dr.  (4)

Intuitively, γ_{2}(X, d) should be viewed as a multi-scale version of a covering number, while δ_{2}(X, d) should be viewed as a multi-scale version of a packing number. It is therefore not surprising that γ_{2}(X, d) ≍ δ_{2}(X, d). In fact, in Section 3 we note that γ_{2}(U, ρ) = δ_{2}(U, ρ) for every finite ultrametric space (U, ρ), and δ_{2}(X, d) ⩾ γ_{2}(X, d) for every finite metric space (X, d) (the latter inequality is an improvement of our original bound δ_{2}(X, d) ≳ γ_{2}(X, d), due to an elegant argument of Witold Bednorz [2]). The remaining estimate δ_{2}(X, d) ≲ γ_{2}(X, d) will not be needed here, though it follows from our discussion (see Remark 1.3), and it also has a simpler direct proof.

Let μ ∈ 𝒫_{X} satisfy δ_{2}(X, d) = inf_{x∈X} ∫_{0}^{∞} \sqrt{log (1/μ(B_{d}(x, r)))}dr. Theorem 1.1 applied to (X, d, μ) yields S ⊆ X and an ultrametric ρ : S ×S → [0, ∞) satisfying d(x, y) ⩽ ρ(x, y) ⩽ Kd(x, y) for all x, y ∈ S. There also exists ν ∈ 𝒫_{S} satisfying ν (B_{d}(x, r)) ⩽ \sqrt{μ(B_{d}(x, Kr))} for all x ∈ X and r ∈ [0, ∞). Here K ∈ (0, ∞) is a universal constant. Since B_{ρ}(x, r) ⊆ B_{d}(x, r)∩S ⊆ B_{ρ}(x, Kr) for all x ∈ S and r ∈ [0, ∞), we have δ_{2}(S, d) ⩽ δ_{2}(S, ρ) = γ_{2}(S, ρ) ⩽ Kγ_{2}(S, d), where we used the fact that γ_{2}(·) and δ_{2}(·) coincide for ultrametrics and a simple change of variable argument. Hence,

1Here, and in what follows, the relations ≲, ≳ indicate the corresponding inequalities up to factors which are universal constants. The relation A ≍ B stands for (A ≲ B) ∧ (A ≳ B).

Kγ_{2}(S, d) ⩾ δ_{2}(S, d) ⩾ inf_{x∈S} ∫_{0}^{∞} \sqrt{log (\frac{1}{ν(B_{d}(x, r))})}dr ⩾ inf_{x∈S} ∫_{0}^{∞} \sqrt{log (\frac{1}{\sqrt{μ(B_{d}(x, Kr))}})}dr

= \frac{1}{K\sqrt{2}} inf_{x∈S} ∫_{0}^{∞} \sqrt{log (\frac{1}{μ(B_{d}(x, r))})}dr ⩾ \frac{δ_{2}(X, d)}{K\sqrt{2}} ⩾ \frac{γ_{2}(X, d)}{K\sqrt{2}}. (5)

This completes the deduction of Talagrand’s nonlinear Dvoretzky theorem from Theorem 1.1.

Remark 1.3. It is easy to check (see [16, Lem. 6]) that γ_{2}(S, d) ⩽ 2γ_{2}(X, d) for every S ⊆ X (and, even more trivially, δ_{2}(S, d) ⩽ δ_{2}(X, d)). Thus, it follows from (5) that γ_{2}(X, d) ≳ δ_{2}(X, d) for every finite metric space (X, d).

Since the original 1987 publication of Talagrand’s majorizing measure theorem, this theorem has been reproved and simplified in several subsequent works, yielding important applications and generalizations (mainly due to Talagrand himself). These proofs are variants of the same basic idea: a greedy top-down construction, in which one looks at a given scale for a ball on which a certain functional is maximized, removes a neighborhood of this ball, and iterates this step on the remainder of the metric space. It seems that the framework described here is genuinely different. The proof of Theorem 1.2 in [14] has two phases. One first constructs a nested family of partitions in a bottom-up fashion: starting with singletons one iteratively groups the points together based on a gluing rule that is tailor-made in anticipation of the ensuing “pruning” or “sparsification” step. This second step is a top-down iterative removal of appropriately “sparse” regions of the partitions that were constructed in the first step; here one combines an analytic argument with the pigeonhole principle to show that there are sufficiently many potential pruning locations so that successive iterations of this step can be made to align appropriately. Our new approach has the advantage that it yields distributional statements such as (1), the majorizing measure theorem itself being a result of integrating these pointwise estimates.

1.2. Multiple measures. In anticipation of further applications of ultrametric skeletons, we end by addressing what is perhaps the simplest question that one might ask about these geometric objects: to what extent is the union of two ultrametric skeletons also an ultrametric skeleton?

We show in Remark 4.3 that for arbitrarily large D_{1}, D_{2} ∈ [1, ∞), one can find a finite metric space (X, d), and two disjoint subsets U_{1}, U_{2} ⊆ X, such that each U_{i} embeds into an ultrametric space with distortion D_{i}, yet any embedding of U_{1} ∪ U_{2} into an ultrametric space incurs distortion at least (D_{1} + 1)(D_{2} + 1) − 1. In Section 4 we prove the following geometric result of independent interest (which, as explained above, is sharp up to lower order terms).

Theorem 1.4. Fix D_{1}, D_{2} ∈ [1, ∞). Let (X, d) be a metric space and U_{1}, U_{2} ⊆ X. Assume that (U_{1}, d) embeds with distortion D_{1} into an ultrametric space and that (U_{2}, d) embeds with distortion D_{2} into an ultrametric space. Then the metric space (U_{1} ∪ U_{2}, d) embeds with distortion at most (D_{1} + 2)(D_{2} + 2) − 2 into an ultrametric space.

Consequently, one can always find an ultrametric skeleton that is “large” with respect to any finite list of probability measures.

Corollary 1.5. For every ε ∈ (0, 1) let C_{ε} be as in Theorem 1.1. Let (X, d) be a compact metric space, and let μ_{1}, …, μ_{k} be Borel probability measures on X. Then there exists a compact subset S ⊆ X, and Borel probability measures ν_{1}, …, ν_{k} supported on S, such that S emebds into an ultrametric space with distortion at most (O(1)/ε)^{k} and for every x ∈ X and r ∈ [0, ∞) we have ν_{i} (B_{d}(x, r)) ⩽ (μ_{i}(B_{d}(x, C_{ε}r))^{1−ε} for all i ∈ {1, …, k}.

2. Proof of Theorem 1.1

A submeasure on a set X is a function ξ : 2^{X} → [0, ∞) satisfying the following conditions.

(a) ξ(∅) = 0,

(b) A_{1} ⊆ A_{2} ⊆ X ⟹ ξ(A_{1}) ⩽ ξ(A_{2}),

(c) {A_{i}}_{i∈I} ⊆ X ⟹ ξ (⋃_{i∈I} A_{i}) ⩽ ∑_{i∈I} ξ(A_{i}). If in addition ξ(X) = 1 we call ξ a probability submeasure.

Lemma 2.1. Let (U, ρ) be a compact ultrametric space, and let ξ : 2^{U} → [0, ∞) be a probability submeasure. Then there exists a Borel probability measure ν on U satisfying ν(B_{ρ}(x, r)) ⩽ ξ(B_{ρ}(x, r)) for all x ∈ X and r ∈ [0, ∞).

Remark 2.2. It is known [8, 15] that there exist probability submeasures that do not dominate any nonzero measure (in the literature such measures are called pathological submeasures). Lemma 2.1 shows that probability submeasures on ultrametric spaces always dominate on all balls some probability measure.

Assuming the validity of Lemma 2.1 for the moment, we prove Theorem 1.1.

Proof of Theorem 1.1. Let (X, d) be a compact metric space and μ a Borel probability measure on X. By Theorem 1.2 there exists a compact subset S ⊆ X satisfying the covering estimate (2), and an ultrametric ρ : S × S → [0, ∞) satisfying d(x, y) ⩽ ρ(x, y) ⩽ \frac{K}{ε} d(x, y) for all x, y ∈ S, where K is a universal constant.

For every A ⊆ S define

ξ(A) = inf {∑_{i∈I} μ (B_{d}(x_{i}, c_{ε}r_{i}))^{1−ε} : {(x_{i}, r_{i})}_{i∈I} ⊆ X × [0, ∞) ∧ ⋃_{i∈I} B_{d}(x_{i}, r_{i}) ⊇ A} . (6)

In (6) the index set I can be countably infinite or finite, with the convention that an empty sum vanishes. One checks that ξ : 2^{S} → [0, ∞) is a submeasure on S. Moreover, for every x ∈ X and r ∈ [0, ∞), by considering B_{d}(x, r) as covering itself, we deduce from (6) that

ξ (S ∩ B_{d}(x, r)) ⩽ μ (B_{d}(x, c_{ε}r))^{1−ε} .  (7)

Since μ is a probability measure and X has bounded diameter, it follows from (7) that ξ(S) ⩽ 1. The covering estimate (2) implies that ξ(S) ⩾ 1, so in fact ξ is a probability submeasure on S.

An application of Lemma 2.1 to (S, ρ, ξ) yields a Borel probability measure ν supported on S and satisfying ν(B_{ρ}(y, r)) ⩽ ξ(B_{ρ}(y, r)) for all y ∈ S and r ∈ [0, ∞). Fix x ∈ X and r ∈ [0, ∞). The desired estimate (1) holds trivially if B_{d}(x, r) ∩ S = ∅, so we may assume that there exists y ∈ S with d(x, y) ⩽ r. Thus

S ∩ B_{d}(x, r) ⊆ S ∩ B_{d}(y, 2r) ⊆ B_{ρ} (y, \frac{2K}{ε} r) ⊆ S ∩ B_{d} (y, \frac{2K}{ε} r) ⊆ S ∩ B_{d} (x, (1 + \frac{2K}{ε} ) r) .

It follows that

ν(B_{d}(x, r)) ⩽ ν (B_{ρ} (y, \frac{2K}{ε} r)) ⩽ ξ (B_{ρ} (y, \frac{2K}{ε} r))

⩽ ξ (S ∩ B_{d} (x, (1 + \frac{2K}{ε} ) r)) ⩽ μ (B_{d} (x, c_{ε} (1 + \frac{2K}{ε} ) r))^{1−ε} .

This completes the deduction of Theorem 1.1 from Theorem 1.2 and Lemma 2.1. □

Prior to proving Lemma 2.1, we review some basic facts about compact ultrametric spaces; see [10] for an extended and more general treatment of this topic. Fix a compact ultrametric space (U, ρ). For every r ∈ (0, ∞) we have |{B_{ρ}(x, s) : (x, s) ∈ U × [r, ∞)}| < ∞, i.e., there are only finitely many closed balls in U of radius at least r. Indeed, by compactness U contains only finitely many disjoint closed balls of radius at least r. Since B_{ρ}(x, s) ∩ B_{ρ}(y, t) ∈ {∅, B_{ρ}(x, s), B_{ρ}(y, t)} for every x, y ∈ U and s, t ∈ [0, ∞), assuming for contradiction that {B_{ρ}(x, s) : (x, s) ∈ U × [r, ∞)} is infinite, we deduce that there exist {(x_{i}, s_{i})}_{i=1}^{∞} ⊆ U × [r, ∞) satisfying B_{ρ}(x_{i}, s_{i}) ⊊ B_{ρ}(x_{i+1}, s_{i+1}) for all i ∈ ℕ. Fix y_{i} ∈ B_{ρ}(x_{i+1}, s_{i+1}) ∖ B_{ρ}(x_{i}, s_{i}). If i < j then y_{j} ∉ B_{ρ}(x_{j}, s_{j}) ⊇ B_{ρ}(x_{i+1}, s_{i+1}) and y_{i} ∈ B_{ρ}(x_{i+1}, s_{i+1}). Hence s_{i+1} < ρ(y_{j}, x_{i+1}) ⩽ max{ρ(y_{j}, y_{i}), ρ(y_{i}, x_{i+1})} ⩽ max{ρ(y_{j}, y_{i}), s_{i+1}}. It follows that ρ(y_{i}, y_{j}) > s_{i+1} ⩾ r for all j > i, contradicting the compactness of (U, ρ).

A consequence of the above discussion is that for every x ∈ U and r ∈ (0, ∞) there exists ε ∈ (0, ∞) such that B_{ρ}(x, r) = B_{ρ}(x + ε). Therefore B_{ρ}(x, r) = B_{ρ}^{∘}(x, r + ε/2). Similarly, since B_{ρ}^{∘}(x, r) = ⋃_{δ∈(0,r/2]} B_{ρ}(x, r − δ), where there are only finitely many distinct balls appearing in this union, there exists δ ∈ (0, r/2] such that B_{ρ}^{∘}(x, r) = B_{ρ}(x, r − δ). Thus every open ball in U of positive radius is also a closed ball, and every closed ball in U of positive radius is also an open ball. Consider the equivalence relation on U given by x ∼ y ⟺ ρ(x, y) < diam_{ρ}(U). This is indeed an equivalence relation since ρ is an ultrametric. The corresponding equivalence classes are all of the form B_{ρ}^{∘}(x, diam_{ρ}(U)) for some x ∈ U. Being open sets that cover U, there are only finitely many such equivalence classes, say, {B_{1}^{1}, B^{2}, …, B_{1}^{k_{1}}}. By the above discussion, each of the open balls B_{1}^{i} is also a closed ball, and hence (B_{1}^{i}, ρ) is a compact ultrametric space. We can therefore continue the above construction iteratively, obtaining a sequence {P_{j}}_{j=0}^{∞} of partitions of U with the following properties.

(1) P_{0} = {U}.

(2) P_{j} is finite for all j.

(3) P_{j+1} is a refinement of P_{j} for all j.

(4) Every C ∈ P_{j} is of the form B_{ρ}^{∘}(x, r) for some x ∈ U and r ∈ [0, ∞).

(5) For every j, if C ∈ P_{j} is not a singleton then there exists x_{1}, …, x_{k} ∈ U such that {B_{ρ}^{∘}(x_{i}, diam_{ρ}(C))}_{i=1}^{k} ⊆ P_{j+1}, the open balls {B_{ρ}^{∘}(x_{i}, diam_{ρ}(C))}_{i=1}^{k} are disjoint, and C = ⋃_{i=1}^{k} B_{ρ}^{∘}(x_{i}, diam_{ρ}(C)).

(6) lim_{j→∞} max_{C∈P_{j}} diam_{ρ}(C) = 0.

(7) For every x ∈ U and r ∈ (0, ∞) there exists j such that B_{ρ}^{∘}(x, r) ∈ P_{j}.

The first five items above are valid by construction. The sixth item follows from the fact that for all j ∈ ℕ either P_{j−1} consists of singletons or max_{C∈P_{j}} diam_{ρ}(C) < max_{C∈P_{j−1}} diam_{ρ}(C). Since for every r ∈ (0, ∞) there are only finitely many balls of radius at least r in U, necessarily lim_{j→∞} max_{C∈P_{j}} diam_{ρ}(C) = 0. To prove the seventh item above, assume for contradiction that (x, r) ∈ U × (0, ∞) is such that B_{ρ}^{∘}(x, r) ∉ P_{j} for all j. Since the set {B_{ρ}^{∘}(x, s)}_{s⩾r} is finite, and B_{ρ}^{∘}(x, diam(U) + 1) = U ∈ P_{0}, by replacing, if necessary, B_{ρ}^{∘}(x, r) with the largest open ball centered at x that is not contained in ⋃_{j=0}^{∞} P_{j} we may assume without loss of generality that B_{ρ}^{∘}(x, s) ∈ ⋃_{j=0}^{∞} P_{j} for all s ∈ (r, ∞). But since B_{ρ}(x, r) = B_{ρ}^{∘}(x, s) for some s ∈ (r, ∞), it follows that B_{ρ}(x, r) ∈ P_{j} for some j. In particular, B_{ρ}^{∘}(x, r) ≠ B_{ρ}(x, r), implying that diam_{ρ}(B_{ρ}(x, r)) = r. Therefore by construction B_{ρ}^{∘}(x, r) ∈ P_{j+1}, a contradiction.

Proof of Lemma 2.1. Let {P_{j}}_{j=0}^{∞} be the sequence of partitions of U that was constructed above. We will first define ν on S = ⋃_{j=0}^{∞} P_{j} ∪ {∅}, which is the set of all open balls in U (allowing the radius to vanish, in which case the corresponding open ball is empty). Setting ν(X) = 1 and ν(∅) = 0, assume inductively that ν has been defined on P_{j}. For C ∈ P_{j+1} let D ∈ P_{j} be the unique set satisfying C ⊆ D. There exist disjoint sets C_{1}, …, C_{k} ∈ P_{j+1}, with C ∈ {C_{1}, …, C_{k}}, such that D = C_{1} ∪ ⋯ ∪ C_{k}. Define

ν(C) = \frac{ξ(C)}{∑_{i=1}^{k} ξ(C_{i})} · ν(D).  (8)

This completes the inductive definition of ν : S → [0, ∞).

We claim that one can apply the Carathéodory extension theorem to extend ν to a Borel measure on U. To this end, note that S is a semi-ring of sets. Indeed, S is closed under intersection since C∩D ∈ {∅, C, D} for all C, D ∈ S. We therefore need to check that for every C, D ∈ S, the set D∖C is a finite disjoint union of elements in S. For this purpose we may assume that D∖C ≠ ∅, implying that C ⊊ D. Assume that C ∈ P_{j} and D ∈ P_{i} for i < j. Let C_{1}, …, C_{k} ∈ P_{j} be the distinct elements of P_{j} that are contained in D, enumerated so that C = C_{1}. Then D ∖ C = C_{2} ∪ ⋯ ∪ C_{k}, and this union is disjoint, as required.

In order to apply the Carathéodory extension theorem, it remains to check that if {A_{i}}_{i=1}^{∞} ⊆ S are pairwise disjoint and ⋃_{i=1}^{∞} A_{i} ∈ S, then ν (⋃_{i=1}^{∞} A_{i}) = ∑_{i=1}^{∞} ν(A_{i}). Since all the elements of S are both open and closed, compactness implies that it suffices to show that if A_{1}, …, A_{m} ∈ S are pairwise disjoint and A_{1} ∪ ⋯ ∪ A_{m} ∈ S, then ν(A_{1} ∪ ⋯ ∪ A_{m}) = ∑_{i=1}^{m} ν(A_{i}). We proceed by induction on m, the case m = 1 being vacuous. For every i ∈ {1, …, m} there is a unique k_{i} ∈ ℕ such that A_{i} ∈ P_{k_{i}−1} ∖ P_{k_{i}}. Define k = max{k_{1}, …, k_{m}}. If k = 1 then necessarily m = 1 and A_{1} = U. Assume that k > 1 and fix j ∈ {1, …, m} satisfying k_{j} = k. Let D ∈ P_{k−2} be the unique element of P_{k−2} containing A_{j}, and let C_{1}, …, C_{ℓ} ∈ P_{k−1} be the distinct elements of P_{k−1} contained in D. Since A_{1} ∪ ⋯ ∪ A_{m} is a ball containing A_{j} ⊆ D, we have A_{1} ∪ ⋯ ∪ A_{m} ⊇ D = C_{1} ∪ ⋯ ∪ C_{ℓ}. By maximality of k it follows that A_{j} ∈ {C_{1}, …, C_{ℓ}} ⊆ {A_{1}, …, A_{m}}. For i ∈ {1, …, ℓ} let n_{i} ∈ {1, …, m} be such that C_{i} = A_{n_{i}}. Since (⋃_{i∈{1,...,m}∖{n_{1},...,n_{ℓ}}} A_{i}) ⋃ D = ⋃_{i=1}^{m} A_{i}, the inductive hypothesis implies that ∑_{i∈{1,...,m}∖{n_{1},...,n_{ℓ}}} ν(A_{i})+ν(D) = ν(A_{1} ∪⋯∪A_{m}). But by our definition (8) we have ν(D) = ν(A_{n_{1}}) + ⋯ + ν(A_{n_{ℓ}}), so that indeed ν(A_{1} ∪ ⋯ ∪ A_{m}) = ∑_{i=1}^{m} ν(A_{i}).

Having defined the Borel probability measure ν, it remains to check by induction on j that if C ∈ P_{j} then ν(C) ⩽ ξ(C). If j = 0 then C = U and ν(U) = ξ(U) = 1. If j ⩾ 1 then let D ∈ P_{j−1} satisfy C ⊆ D. There exist disjoint sets C_{1}, …, C_{k} ∈ P_{j+1}, with C ∈ {C_{1}, …, C_{k}}, such that D = C_{1} ∪ ⋯ ∪ C_{k}. Since ξ is a submeasure, ξ(D) ⩽ ξ(C_{1}) + ⋯ + ξ(C_{k}). By the inductive hypothesis ν(D) ⩽ ξ(D). Our definition (8) now implies that ν(C) ⩽ ξ(C). The proof of Lemma 2.1 is complete. □

3. γ_{2}(X, d) and δ_{2}(X, d)

Let (X, d) be a finite metric space. For every measurable ϕ : (0, ∞) → [0, ∞) define

γ_{ϕ}(X, d) = inf_{μ∈𝒫_{X}} sup_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{d}(x, r)))dr,

and

δ_{ϕ}(X, d) = sup_{μ∈𝒫_{X}} inf_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{d}(x, r)))dr.

Thus γ_{2}(·) = γ_{ϕ}(·) and δ_{2}(·) = δ_{ϕ}(·) for ϕ(x) = \sqrt{log(1/x)}. The following lemma is a variant of an argument of Bednorz [2, Lem. 4]. The elegant proof below was shown to us by Keith Ball; it is a generalization and a major simplification of our original proof of the estimate δ_{2}(X, d) ≳ γ_{2}(X, d).

Lemma 3.1. Assume that ϕ : (0, ∞) → (0, ∞) is continuous and lim_{x→0^{+}} ϕ(x) = ∞. Then δ_{ϕ}(X, d) ⩾ γ_{ϕ}(X, d).

Proof. Write X = {x_{1}, …, x_{n}}. Thus 𝒫_{X} can be identified with the (n − 1)-dimensional simplex Δ_{n−1} = {(μ_{1}, …, μ_{n}) ∈ [0, 1]^{n}; μ_{1} + ⋯ + μ_{n} = 1} (by setting μ{x_{i}}) = μ_{i}).

Define f_{1}, …, f_{n} : Δ_{n−1} → [0, ∞) by

f_{i}(μ) = \{ \begin{matrix}0 & if μ_{i} = 0, \\ (1 + ∫_{0}^{∞} ϕ(μ(B(x_{i}, r)))dr)^{−1} & if μ_{i} > 0. \end{matrix}

Writing S(μ) = ∑_{i=1}^{n} f_{i}(μ), we define F : Δ_{n−1} → Δ_{n−1} by F (μ) = (f_{1}(μ), …, f_{n}(μ))/S(μ). Since ϕ is continuous and lim_{x→0^{+}} ϕ(x) = ∞, all the f_{i} are continuous on Δ_{n−1}. Since each μ ∈ Δ_{n−1} has at least one positive coordinate, S(μ) > 0. Thus F is continuous. Note that by definition F maps each face of Δ_{n−1} into itself. By a standard reformulation of the Brouwer fixed point theorem (see, e.g., [7, Sec. 4.29\frac{1}{2}_{+}]), it follows that f(Δ_{n−1}) = Δ_{n−1}. In particular, there exists μ ∈ Δ_{n−1} for which F (μ) = (1/n, …, 1/n). In other words, there exists μ ∈ 𝒫_{X} such that ∫_{0}^{∞} ϕ(μ(B_{d}(x, r)))dr does not depend on x ∈ X. Hence,

δ_{ϕ}(X, d) ⩾ inf_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{d}(x, r)))dr = sup_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{d}(x, r)))dr ⩾ γ_{ϕ}(X, d).  □

Lemma 3.2. Assume that ϕ : (0, ∞) → [0, ∞) is non-increasing. Let (U, ρ) be a finite ultrametric space. Then δ_{ϕ}(U, ρ) ⩽ γ_{ϕ}(U, ρ).

Proof. We claim that if μ, ν are nonnegative measures on U satisfying μ(U) ⩽ ν(U) then there exists a ∈ U satisfying μ(B_{ρ}(a, r)) ⩽ ν(B_{ρ}(a, r)) for all r ∈ (0, ∞). This would imply the desired estimate since if μ, ν ∈ 𝒫_{X} are chosen so that sup_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{ρ}(x, r)))dr = γ_{ϕ}(U, ρ) and inf_{x∈X} ∫_{0}^{∞} ϕ(μ(B_{ρ}(x, r)))dr = δ_{ϕ}(U, ρ), then

γ_{ϕ}(U, ρ) ⩾ ∫_{0}^{∞} ϕ(μ(B_{ρ}(a, r)))dr ⩾ ∫_{0}^{∞} ϕ(ν(B_{ρ}(a, r)))dr ⩾ δ_{ϕ}(U, ρ).

The proof of the existence of a ∈ U is by induction on |U|. If |U| = 1 there is nothing to prove. Otherwise, as explained in Section 2, there exist x_{1}, …, x_{k} ∈ U such that the balls {B_{ρ}^{∘}(x_{i}, diam_{ρ}(U))}_{i=1}^{k} are nonempty, pairwise disjoint, and ⋃_{i=1}^{k} B_{ρ}^{∘}(x_{i}, diam_{ρ}(U)) = U. It follows that ∑_{i=1}^{k} μ(B_{ρ}^{∘}(x_{i}, diam_{ρ}(U))) = μ(U) ⩽ ν(U) = ∑_{i=1}^{k} ν(B_{ρ}^{∘}(x_{i}, diam_{ρ}(U))). Consequently there exists i ∈ {1, …, k} such that μ(B_{ρ}^{∘}(x_{i}, diam_{ρ}(U))) ⩽ ν(B_{ρ}^{∘}(x_{i}, diam_{ρ}(U))). By the inductive hypothesis there exists a ∈ B_{ρ}^{∘}(x_{i}, diam_{ρ}(U)) satisfying μ(B_{ρ}(a, r)) ⩽ ν(B_{ρ}(a, r)) for all r < diam_{ρ}(U). Since for r ⩾ diam_{ρ}(U) we have B_{ρ}(a, r) = U, the proof is complete. □

A combination of Lemma 3.1 and Lemma 3.2 yields the following corollary.

Corollary 3.3. If ϕ : (0, ∞) → [0, ∞) is non-increasing, continuous, and lim_{x→0^{+}} ϕ(x) = ∞, then δ_{ϕ}(U, ρ) = γ_{ϕ}(U, ρ) for all finite ultrametric spaces (U, ρ).

Remark 3.4. Consider the star metric d_{n} on {0, 1, …, n}, i.e., d_{n}(0, i) = 1 for all i ∈ {1, …, n} and d_{n}(p, q) = 2 for all distinct p, q ∈ {1, …, n}. The measure ν on {0, 1, …, n} given by ν({0}) = 0 and ν(\{i\}) = 1/n for i ∈ \{1, …, n\}, shows that δ_{2}(\{0, 1, …, n\}, d_{n}) ⩾ 2\sqrt{log n}. At the same time, the measure μ on {0, 1, …, n} given by μ({0}) = 1/2 and μ({i}) = 1/(2n) for i ∈ {1, …, n}, shows that γ_{2}(\{0, 1, …, n\}, d_{n}) ⩽ \sqrt{log(2n)}+\sqrt{log(2n/(n + 1))} ⩽ (1/2+o(1))δ_{2}(\{0, 1, …, n\}, d_{n}). Thus, unlike the case of ultrametric spaces, for general metric spaces it is not always true that γ_{2}(X, d) = δ_{2}(X, d). Of course, due to Lemma 3.1 and Remark 1.3 we know that γ_{2}(X, d) ≍ δ_{2}(X, d). It seems plausible that always δ_{2}(X, d) ⩽ 2γ_{2}(X, d), but we do not investigate this here.

4. Unions of approximate ultrametrics

In this section we prove Theorem 1.4 and present some related examples. Below, given a partition P of a set X, for x ∈ X we denote by P (x) the element of P to which x belongs.

Lemma 4.1. Fix D_{1}, D_{2} ⩾ 1. Let (X, d) be a metric space and let U_{1}, U_{2} ⊆ X be two bounded subsets of X. Assume that (U_{1}, d) embeds with distortion D_{1} into an ultrametric space and that (U_{2}, d) embeds with distortion D_{2} into an ultrametric space. Then for every ε ∈ (0, 1) there is a partition P of U_{1} ∪ U_{2} with the following properties.

• For every C ∈ P,

diam_{d}(C) ⩽ (1 − δ) diam_{d}(U_{1} ∪ U_{2}),  (9)

where

δ =^{def} \frac{2εD_{2}}{(D_{1}D_{2} + 2D_{1} + 2D_{2} + 2)(D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε)}.  (10)

• For every distinct C_{1}, C_{2} ∈ P,

d(C_{1}, C_{2}) ⩾ \frac{diam_{d}(U_{1} ∪ U_{2})}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε}.  (11)

Proof. By rescaling we may assume that diam_{d}(U_{1} ∪ U_{2}) = 1. Let ρ_{1} be an ultrametric on U_{1} satisfying d(x, y) ⩽ ρ_{1}(x, y) ⩽ D_{1}d(x, y) for all x, y ∈ U_{1}. Define

a =^{def} \frac{D_{1}D_{2} + 2D_{1}}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2},  (12)

and consider the equivalence relation on U_{1} given by x ∼_{1} y ⟺ ρ_{1}(x, y) ⩽ a (this is an equivalence relation since ρ_{1} is an ultrametric). Let {E_{i}}_{i∈I} ⊆ 2^{U_{1}} be the corresponding equivalence classes. Thus

diam_{d}(E_{i}) ⩽ diam_{ρ_{1}}(E_{i}) ⩽ a  (13)

for all i ∈ I, and for distinct i, j ∈ I we have

d(E_{i}, E_{j}) ⩾ \frac{ρ_{1}(E_{i}, E_{j})}{D_{1}} ⩾ \frac{a}{D_{1}} .  (14)

Let ρ_{2} be an ultrametric on U_{2} satisfying d(x, y) ⩽ ρ_{2}(x, y) ⩽ D_{2}d(x, y) for all x, y ∈ U_{2}. Define

b =^{def} \frac{D_{2}}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε},  (15)

and consider similarly the equivalence relation on U_{2} given by x ∼_{2} y ⟺ ρ_{2}(x, y) ⩽ b. The corresponding equivalence classes will be denoted {F_{j}}_{j∈J} ⊆ 2^{U_{2}}. Thus

diam_{d}(F_{i}) ⩽ diam_{ρ_{1}}(F_{i}) ⩽ b  (16)

for all i ∈ J, and for distinct i, j ∈ J we have

d(F_{i}, F_{j}) ⩾ \frac{ρ_{2}(F_{i}, F_{j})}{D_{2}} ⩾ \frac{b}{D_{2}} .  (17)

For every i ∈ I denote

J_{i} =^{def} {j ∈ J : d(E_{i}, F_{j}) ⩽ c} ,  (18)

where

c =^{def} \frac{1}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2}.  (19)

Note that for every j ∈ J there is at most one i ∈ I for which j ∈ J_{i}. Indeed, if j ∈ J_{i} ∩ J_{ℓ}, where i ≠ ℓ, then

d(E_{i}, E_{ℓ})  ⩽  d(E_{i}, F_{j}) + diam_{d}(F_{j}) + d(F_{j}, E_{ℓ})
⩽^{(16)∧(18)} 2c + b
=^{(15)∧(19)} \frac{2}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2} + \frac{D_{2}}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε}
<  \frac{2 + D_{2}}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2} =^{(12)} \frac{a}{D_{1}} ,

Contradicting (14).

Consider the partition P of U_{1} ∪ U_{2} consisting of the sets

{E_{i} ∪ ( ⋃_{j∈J_{i}} F_{j})}_{i∈I} and {F_{j} ∖ U_{1}}_{j∈J∖(⋃_{i∈I} J_{i})}.

It follows from (14), (17) and (18) that for every distinct C_{1}, C_{2} ∈ P,

d(C_{1}, C_{2}) ⩾ min \{\frac{a}{D_{1}} , \frac{b}{D_{2}} , c\} = \frac{1}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε}.

Thus the partition P satisfies (11). It also follows from (13), (16) and (18) that for every C ∈ P,

diam_{d}(C) ⩽ a + 2b + 2c = (1 − δ),

where we used the definitions (10), (12), (15), (19). Thus the partition P satisfies (9), completing the proof of Lemma 4.1. □

Proof of Theorem 1.4. Assume first that U_{1}, U_{2} are bounded. Define a sequence {P_{k}}_{k=0}^{∞} of partitions of U_{1} ∪ U_{2} as follows. Start with the trivial partition P_{0} = {U_{1} ∪ U_{2}}, and having defined P_{k}, the partition P_{k+1} is obtained by applying Lemma 4.1 to the sets U_{1} ∩ C and U_{2} ∩ C for each C ∈ P_{k}. Then the partitions {P_{k}}_{k=0}^{∞} have the following properties.

• P_{k+1} is a refinement of P_{k},

• for every C ∈ P_{k} we have

diam_{d}(C) ⩽ (1 − δ)^{k} diam_{d}(U_{1} ∪ U_{2}),  (20)

• for every distinct C_{1}, C_{2} ∈ P_{k+1} such that C_{1}, C_{2} ⊆ C for some C ∈ P_{k}, we have

d(C_{1}, C_{2}) ⩾ \frac{diam_{d}(C)}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε}.  (21)

It follows from (20) that for every distinct x, y ∈ U_{1} ∪ U_{2} we have P_{k}(x) ≠ P_{k}(y) for k ⩾ 0 large enough. Thus for distinct x, y ∈ U_{1} ∪ U_{2} let k(x, y) denote the largest integer k ⩾ 0 such that P_{k}(x) = P_{k}(y). Define

ρ(x, y) = \{ \begin{matrix}diam_{d} (P_{k(x,y)}(x)) & x ≠ y, \\ 0 & x = y. \end{matrix}

Then ρ is an ultrametric on U_{1} ∪ U_{2}. Indeed, for distinct x, y, z ∈ U_{1} ∪ U_{2} let k ⩾ 0 be the largest integer such that P_{k}(x) = P_{k}(y) = P_{k}(z). Then k = min{k(x, z), k(y, z)} and P_{k}(x) ⊇ P_{k(x,y)}(x), implying that ρ(x, y) = diam_{d} (P_{k(x,y)}(x)) ⩽ diam_{d} (P_{k}(x)) = max{ρ(x, z), ρ(y, z)}. For distinct x, y ∈ U_{1} ∪ U_{2}, since x, y ∈ P_{k(x,y)}(x), we have ρ(x, y) = diam_{d} (P_{k(x,y)}(x)) ⩾ d(x, y), while since P_{k(x,y)+1}(x) ≠ P_{k(x,y)+1}(y), we deduce from (21) that

d(x, y) ⩾ d (P_{k(x,y)+1}(x), P_{k(x,y)+1}(y))

⩾ \frac{diam_{d} (P_{k(x,y)}(x))}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε} = \frac{ρ(x, y)}{D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε}.

The above argument shows that if U_{1}, U_{2} are bounded, the metric space (U_{1} ∪ U_{2}, d) embeds with distortion D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + ε into an ultrametric space for every ε ∈ (0, 1).

For possibly unbounded U_{1}, U_{2} ⊆ X, fix x_{0} ∈ X, and for every n ∈ ℕ let ρ_{n} be an ultrametric on (U_{1} ∩ B_{d}(x_{0}, n)) ∪ (U_{2} ∩ B_{d}(x_{0}, n)) satisfying

d(x, y) ⩽ ρ_{n}(x, y) ⩽ (D_{1}D_{2} + 2D_{1} + 2D_{2} + 2 + \frac{1}{n}) d(x, y)

for all x, y ∈ (U_{1} ∩ B_{d}(x_{0}, n)) ∪ (U_{2} ∩ B_{d}(x_{0}, n)). Define also ρ_{n}(x, y) = 0 if {x, y} is not contained in (U_{1} ∩ B_{d}(x_{0}, n)) ∪ (U_{2} ∩ B_{d}(x_{0}, n)). Let 𝒰 be a free ultrafilter on ℕ and set

ρ_{∞}(x, y) =^{def} lim_{n→𝒰} ρ_{n}(x, y).

Then ρ_{∞} is an ultrametric on U_{1} ∪ U_{2} satisfying d ⩽ ρ_{∞} ⩽ (D_{1}D_{2} + 2D_{1} + 2D_{2} + 2)d. □

Remark 4.2. There are several interesting variants of the problem studied in Theorem 1.4. For example, answering our initial question, Konstantin Makarychev and Yury Makarychev proved (private communication) that if (X, d) is a metric space and E_{1}, E_{2} ⊆ X embed into Hilbert space with distortion D ⩾ 1 then (E_{1} ∪ E_{2}, d) embeds into Hilbert space with distortion f(D). Their argument crucially uses Hilbert space geometry, and therefore the following natural question remains open: if (X, d) is a metric space and E_{1}, E_{2} ⊆ X embed into L_{1} with distortion D ⩾ 1, does it follow that (E_{1} ∪E_{2}, d) embeds into L_{1} with distortion f(D)? Regarding unions of more than two subsets, perhaps even the following (ambitious) question has a positive answer: if E_{1}, …, E_{n} ⊆ X embed into Hilbert space with distortion D ⩾ 1, does it follow that (E_{1} ∪ … ∪ E_{n}, d) embeds into Hilbert space with distortion O(log n)f(D)? If true, this statement (in the isometric case D = 1) would yield a very interesting strengthening of Bourgain’s embedding theorem [3], which asserts that any n-point metric space embeds into Hilbert space with distortion O(log n).

Remark 4.3. The following example shows that Theorem 1.4 is sharp up to lower order terms. Fix two integers M, N ⩾ 2, and write MN = K(M+N)+L, where K ∈ ℕ and L ∈ {0, 1, …, M+N−1}. Consider the following two subsets of the real line:

U_{1} =^{def} ⋃_{i=0}^{K−1} {i(M + N), i(M + N) + 1, …, i(M + N) + M − 1} ,

U_{2} =^{def} ⋃_{i=0}^{K−1} {i(M + N) + M, i(M + N) + M + 1, …, (i + 1)(M + N) − 1} .

For i ∈ {1, 2}, let D_{i} ⩾ 1 be the best possible distortion of U_{i} (with the metric inherited from ℝ) in an ultrametric space. For i_{1}, i_{2} ∈ {0, …, K − 1} and j_{1}, j_{2} ∈ {0, …, M − 1} define

ρ_{1} (i_{1}(M + N) + j_{1}, i_{2}(M + N) + j_{2}) =^{def} \{ \begin{matrix}0 & i_{1} = i_{2} ∧ j_{1} = j_{2}, \\ M − 1 & i_{1} = i_{2} ∧ j_{1} ≠ j_{2}, \\ (K − 1)(M + N) + M − 1 & i_{1} ≠ i_{2}. \end{matrix}

Then ρ_{1} is an ultrametric on U_{1} satisfying |x − y| ⩽ ρ_{1}(x, y) ⩽ (M − 1)|x − y| for all x, y ∈ U_{1}. Hence D_{1} ⩽ M − 1. Similarly, for i_{1}, i_{2} ∈ {0, …, K − 1} and j_{1}, j_{2} ∈ {M, …, M + N − 1} define

ρ_{2} (i_{1}(M + N) + j_{1}, i_{2}(M + N) + j_{2}) =^{def} \{ \begin{matrix}0 & i_{1} = i_{2} ∧ j_{1} = j_{2}, \\ N − 1 & i_{1} = i_{2} ∧ j_{1} ≠ j_{2}, \\ (K − 1)(M + N) + N − 1 & i_{1} ≠ i_{2}. \end{matrix}

Then ρ_{2} is an ultrametric on U_{2} satisfying |x−y| ⩽ ρ_{1}(x, y) ⩽ (N −1)|x−y| for all x, y ∈ U_{2}. Hence D_{2} ⩽ N − 1. But U_{1} ∪ U_{2} = {0, 1, …, K(M + N) − 1}, and hence any embedding of U_{1} ∪ U_{2} into an ultrametric space incurs distortion at least K(M +N)−1 (see for example [12, Lem. 2.4]). Observe that this lower bound on the distortion equals MN − L − 1 ⩾ (M − 1)(N − 1) − 1 ⩾ D_{1}D_{2} − 1. When L = 0 (e.g., when M = N = 2S or M = 2N = 6S for some S ∈ ℕ), the above distortion lower bound becomes MN − L − 1 ⩾ (D_{1} + 1)(D_{2} + 1) − 1. Thus one cannot improve the bound in Theorem 1.4 to D_{1}D_{2}, i.e., additional lower order terms are necessary.

Acknowledgements. We are grateful to the following people for helpful suggestions: Keith Ball, Witold Bednorz, Rafał Latała, Gilles Pisier, Gideon Schechtman, Michel Talagrand.

References

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

[2] W. Bednorz. The measure approach to sample boundedness. Preprint, 2011.

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

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

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

[6] X. Fernique. Évaluations de processus gaussiens composés. In Probability in Banach spaces (Proc. First Internat. Conf., Oberwolfach, 1975), pages 67–83. Lecture Notes in Math., Vol. 526. Springer, Berlin, 1976.

[7] M. Gromov. Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, english edition, 2007. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates.

[8] W. Herer and J. P. R. Christensen. On the existence of pathological submeasures and the construction of exotic topological groups. Math. Ann., 213:203–210, 1975.

[9] J. D. Howroyd. On dimension and on the existence of sets of finite positive Hausdorff measure. Proc. London Math. Soc. (3), 70(3):581–604, 1995.

[10] B. Hughes. Trees and ultrametric spaces: a categorical equivalence. Adv. Math., 189(1):148–191, 2004.

[11] P. Mattila. Geometry of sets and measures in Euclidean spaces, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. Fractals and rectifiability.

[12] M. Mendel and A. Naor. Euclidean quotients of finite metric spaces. Adv. Math., 189(2):451–494, 2004.

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

[14] M. Mendel and A. Naor. Ultrametric subsets with large Hausdorff dimension. To appear in Invent. Math.,

preprint available at http://arxiv.org/abs/1106.0879, 2011.

[15] M. Talagrand. A simple example of pathological submeasure. Math. Ann., 252(2):97–102, 1979/80.

[16] M. Talagrand. Regularity of Gaussian processes. Acta Math., 159(1-2):99–149, 1987.

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

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

E-mail address: mendelma@gmail.com

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

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