ULTRAMETRIC SUBSETS WITH LARGE HAUSDORFF DIMENSION

MANOR MENDEL AND ASSAF NAOR

Abstract. For every ε ∈ (0, 1) it is shown that every compact metric space X has a closed subset Y ⊆ X which embeds into an ultrametric space with distortion O(1/ε), and dim_{H}(Y) ⩾ (1 − ε) dim_{H}(X), where dim_{H}(·) denotes Hausdorff dimension.

Contents

1. Introduction 1 1.1. An overview of the proof of Theorem 1.5 4 1.2. The low distortion regime 5 1.3. Talagrand’s nonlinear Dvoretzky theorem 5 2. Preliminaries and notation 7 2.1. Combinatorial trees 7 2.2. Fragmentation maps 8 3. Reduction to finite metric spaces 9 4. The initial fragmentation map 11 5. An iterated Hölder argument for trees 13 6. Construction of ultrametric subsets 20 7. Impossibility results 30 7.1. Trees of metric spaces 31 7.2. Expander fractals 34 7.3. G (n, 1/2) fractals 34 References 35

1. Introduction

Given D ⩾ 1, a metric space (X, d_{X}) is said to embed with distortion D into a metric space (Y, d_{Y}) if there exists f : X → Y and λ > 0 such that for all x, y ∈ X we have

λd_{X}(x, y) ⩽ d_{Y} (f(x), f(y)) ⩽ Dλd_{X}(x, y).  (1)

Note that when Y is a Banach space the scaling factor λ can be dropped in the definition (1).

Answering positively a conjecture of Grothendieck [10], Dvoretzky proved [9] 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 [17, 16, 20] for the best known bounds on n(k, D).

M. M. was partially supported by ISF grant no. 221/07, BSF grant no. 2006009, and a gift from Cisco Research Center. A. N. was partially supported by NSF grant CCF-0832795, BSF grant 2006009, and the Packard Foundation. Part of this work was completed when A. N. was visiting the Discrete Analysis program at the Isaac Newton Institute for Mathematical Sciences.

Bourgain, Figiel and Milman [5] studied the following problem as a natural nonlinear variant of Dvoretzky’s theorem: given n ∈ ℕ and D > 1, what is the largest m ∈ ℕ such that any finite metric space (X, d) of cardinality n has a subset S ⊆ X with |S| ⩾ m such that the metric space (S, d) embeds with distortion D into Hilbert space? Denote this value of m by R(n, D). Bourgain-Figiel-Milman proved [5] that for all D > 1 there exists c(D) ∈ (0, ∞) such that R(n, D) ⩾ c(D) log n, and that R(n, 1.023) = O(log n). Following several investigations [12, 4, 1] that were motivated by algorithmic applications, a more complete description of the Bourgain-Figiel-Milman phenomenon was obtained in [2].

Theorem 1.1 ([2]). For D ∈ (1, ∞) there exist c(D), c′(D) ∈ (0, ∞) and δ(D), δ′(D) ∈ (0, 1) such that for every n ∈ ℕ,

• if D ∈ (1, 2) then c(D) log n ⩽ R(n, D) ⩽ c′(D) log n,

• if D ∈ (2, ∞) then n^{1−δ(D)} ⩽ R(n, D) ⩽ n^{1−δ′(D)}.

Highlighting the case of large D, which is most relevant for applications, we have the following theorem.

Theorem 1.2 ([2, 15, 19]). For every ε ∈ (0, 1) and n ∈ ℕ, any n-point metric space (X, d) has a subset S ⊆ X with |S| ⩾ n^{1−ε} that embeds into an ultrametric space with distortion 2e/ε. On the other hand, there exists a universal constant c > 0 with the following property. For every n ∈ ℕ there is an n-point metric space X_{n} such that for every ε ∈ (0, 1) all subsets Y ⊆ X with |Y | ⩾ n^{1−ε} incur distortion at least c/ε in any embedding into Hilbert space.

Recall that a metric space (U, ρ) is called an ultrametric space if for every x, y, z ∈ U we have ρ(x, y) ⩽ max {ρ(x, z), ρ(z, y)}. Any separable ultrametric space admits an isometric embedding into Hilbert space [23]. Hence the subset S from Theorem 1.2 also embeds with the stated distortion into Hilbert space, and therefore Theorem 1.2 fits into the Bourgain-Figiel-Milman framework. Note, however, that the stronger statement that S embeds into an ultrametric space is needed for the applications in [2, 15], and that the matching lower bound in Theorem 1.2 is for the weaker requirement of embeddability into Hilbert space. The existence of the metric spaces {X_{n}}_{n=1}^{∞} from Theorem 1.2 was established in [2]. The estimate 2e/ε on the Euclidean distortion of the subset S from Theorem 1.2 is due to [19], improving by a constant factor over the bound from [15], which itself improves (in an asymptotically optimal way) on the distortion bound of O (ε^{−1} log(2/ε)) from [2].

In what follows, dim_{H}(X) denotes the Hausdorff dimension of a metric space X. Inspired by the above theorems, Terence Tao proposed (unpublished, 2006) another natural variant of the nonlinear Dvoretzky problem: one can keep the statement of Dvoretzky’s theorem unchanged in the context of general metric spaces, while interpreting the notion of dimension in the appropriate category. Thus one arrives at the following question.

Question 1.3 (Tao’s nonlinear Dvoretzky problem). Given α > 0 and D > 1, what is the supremum over those β ⩾ 0 with the following property. Every compact metric space X with dim_{H}(X) ⩾ α has a subset S ⊆ X with dim_{H}(S) ⩾ β that embeds into Hilbert space with distortion D?

The restriction of Question 1.3 to compact metric spaces is not severe. For example, if X is complete and separable then one can first pass to a compact subset of X with the same Hausdorff dimension, and even the completeness of X can be replaced by weaker assumptions; see [7, 11]. We will not address this issue here and restrict our discussion to compact metric spaces, where the crucial subtleties of the problem are already present.

Our purpose here is to provide answers to Question 1.3 in various regimes, the main result being the following theorem.

Theorem 1.4. There exists a universal constant C ∈ (0, ∞) such that for every ε ∈ (0, 1), every compact metric space X has a closed subset S ⊆ X with dim_{H}(S) ⩾ (1 − ε) dim_{H}(X) that embeds with distortion C/ε into an ultrametric space. In the reverse direction, there is a universal constant c > 0 such that for every α > 0 there exists a compact metric space X_{α} with dim_{H}(X_{α}) = α such that if S ⊆ X satisfies dim_{H}(S) ⩾ (1 − ε)α then S incurs distortion at least c/ε in any embedding into Hilbert space.

The construction of the spaces X_{α} from Theorem 1.4 builds on the examples of [2], which are based on expander graphs. The limiting spaces X_{α} obtained this way can therefore be called “expander fractals”; their construction is discussed in Section 7. Our main new contribution leading to Theorem 1.4 is the following structural result for general metric measure spaces.

In what follows, by a metric measure space (X, d, μ) we mean a compact metric space (X, d), equipped with a Borel measure μ such that μ(X) < ∞. For r > 0 and x ∈ X, the corresponding closed ball is denoted B(x, r) = {y ∈ X : d(x, y) ⩽ r}.

Theorem 1.5. For every ε ∈ (0, 1) there exists c_{ε} ∈ (0, ∞) with the following property. Every metric measure space (X, d, μ) has a closed subset S ⊆ X such that (S, d) embeds into an ultrametric space with distortion 9/ε, and for every {x_{i}}_{i∈I} ⊆ X and {r_{i}}_{i∈I} ⊆ [0, ∞) such that the balls {B(x_{i}, r_{i})}_{i∈I} cover S, i.e.,

⋃_{i∈I} B(x_{i}, r_{i}) ⊇ S,  (2)

we have

∑_{i∈I} μ(B(x_{i}, c_{ε}r_{i}))^{1−ε} ⩾ μ(X)^{1−ε}.  (3)

Theorem 1.5 contains Theorem 1.2 as a simple special case. Indeed, consider the case when X is finite, say |X| = n, the measure μ is the counting measure, i.e., μ(A) = |A| for all A ⊆ X, and all the radii {r_{i}}_{i∈I} vanish. In this case B(x_{i}, r_{i}) = B(x_{i}, c_{ε}r_{i}) = {x_{i}}, and therefore the covering condition (2) implies that {x_{i}}_{i∈I} ⊇ S. Inequality (3) therefore implies that |S| ⩾ n^{1−ε}, which is the (asymptotically sharp) conclusion of Theorem 1.2, up to a constant multiplicative factor in the distortion.

Theorem 1.5 also implies Theorem 1.4. To see this assume that (X, d) is a compact metric space and dim_{H}(X) > α. The Frostman lemma (see [11] and [13, Ch. 8]) implies that there exists a constant K ∈ (0, ∞) and a Borel measure μ such that μ(X) > 0 and μ(B(x, r)) ⩽ Kr^{α} for all r > 0 and x ∈ X. An application of Theorem 1.5 to the metric measure space (X, d, μ) yields a closed subset S ⊆ X that embeds into an ultrametric space with distortion O(1/ε) and satisfies the covering condition (3). Thus, all the covers of S by balls {B(x_{i}, r_{i})}_{i∈I} satisfy

μ(X)^{1−ε} ⩽ ∑_{i∈I} μ(B(x_{i}, c_{ε}r_{i}))^{1−ε} ⩽ ∑_{i∈I} (Kc_{ε}^{α}r_{i}^{α})^{1−ε} .

Hence,

∑_{i∈I} r_{i}^{(1−ε)α} ⩾ \frac{μ(X)^{1−ε}}{K^{1−ε}c_{ε}^{(1−ε)α}} .

This means that the (1 − ε)α-Hausdorff content^{1} of S satisfies

H_{∞}^{(1−ε)α}(S) ⩾ \frac{μ(X)^{1−ε}}{K^{1−ε}c_{ε}^{(1−ε)α}} > 0,

and therefore dim_{H}(S) = inf {β ⩾ 0 : H_{∞}^{β}(S) = 0} ⩾ (1 − ε)α, as asserted in Theorem 1.4.

To summarize the above discussion, the general structural result for metric measure spaces that is contained in Theorem 1.5 implies the sharp Bourgain-Figiel-Milman style nonlinear Dvoretzky theorem when applied to trivial covers of S by singletons. Tao’s nonlinear Dvoretzky problem is more subtle since one has to argue about all possible covers of S, and this is achieved by applying Theorem 1.5 to the metric measure space induced by a Frostman measure. In both of these applications the value of the constant c_{ε} in Theorem 1.5 is irrelevant, but we anticipate that it will play a role in future applications of Theorem 1.5. Our argument yields the bound c_{ε} = e^{O(1/ε^{2})}, but we have no reason to believe that this dependence on ε is optimal. We therefore pose the following natural problem.

Question 1.6. What is the asymptotic behavior as ε → 0 of the best possible constant c_{ε} in Theorem 1.5?

1.1. An overview of the proof of Theorem 1.5. Theorem 1.1 was proved in [2] via a deterministic iterative construction of a sufficiently large almost ultrametric subset S of a given finite metric space (X, d). In contrast, Theorem 1.2 was proved in [15] via a significantly shorter probabilistic argument. It is shown in [15] how to specify a distribution (depending on the geometry of X) over random subsets S ⊆ X that embed into an ultrametric space with small distortion, yet their expected cardinality is large. The lower bound on the expected cardinality of S is obtained via a lower bound on the probability Pr [x ∈ S] for each fixed x ∈ X. Such a probabilistic estimate seems to be quite special, and we do not see how to argue probabilistically about all possible covers of a random subset S, as required in Theorem 1.5. For this reason our proof of Theorem 1.5 is a deterministic construction which uses in some of its steps adaptations of the methods of [2], in addition to a variety of new ingredients that are needed in order to handle a covering condition such as (3). Actually, in order to obtain the sharp O(1/ε) distortion bound of Theorem 1.5 we also use results of [15, 19] (see Theorem 6.2 below), so in fact Theorem 1.5 is based on a combination of deterministic and probabilistic methods, the deterministic steps being our most substantial new contribution.

The proof of Theorem 1.5 starts with a reduction of the problem to the case of finite metric spaces; see Section 3. Once this is achieved, the argument is a mixture of combinatorial, analytic and geometric arguments, the key objects of interest being fragmentation maps. These are maps that are defined on rooted combinatorial trees and assign to each vertex of the tree a subset of the metric space (X, d) in a way that respects the tree structure, i.e., the set corresponding to an offspring of a vertex is a subset of the set corresponding to the vertex itself, and vertices lying on distinct root-leaf paths are assigned to disjoint subsets of X. We also require that leaves are mapped to singletons.

1Recall that for β ⩾ 0 the β-Hausdorff content of a metric space (Z, d) is defined to be the infimum of ∑_{j∈J} r_{j}^{β} over all possible covers of Z by balls {B(z_{j}, r_{j})}_{j∈J}; see [13].

Each fragmentation map corresponds to a subset of X (the images of the leaves), and our goal is to produce a fragmentation map that corresponds to a subset of X which satisfies the conclusion of Theorem 1.5. To this end, we initiate the iteration via a bottom-up construction of a special fragmentation map; see Section 4. We then proceed to iteratively “prune” (or “sparsify”) this initial tree so as to produce a smaller tree whose leaves satisfy the conclusion of Theorem 1.5. At each step we argue that there must exist sufficiently many good pruning locations so that by a pigeonhole argument we can make the successive pruning locations align appropriately; see Section 5 and Section 6. The exact details of these steps are quite involved, and it is impossible to describe them without introducing a significant amount of notation and terminology, and specifying rather complicated inductive hypotheses. We therefore refer to the relevant sections for a detailed description.

1.2. The low distortion regime. We have thus far focused on Question 1.3 in the case of high distortion embeddings into ultrametric spaces. There is also a Hausdorff dimensional variant of the phase transition at distortion 2 that was described in Theorem 1.1.

Theorem 1.7 (Distortion 2 + δ). There exists a universal constant c ∈ (0, ∞) such that for every δ ∈ (0, 1/2), any compact metric space (X, d) has a closed subset S ⊆ X that embeds with distortion 2 + δ in an ultrametric space, and

dim_{H}(S) ⩾ \frac{cδ}{log(1/δ)} dim_{H}(X).  (4)

For distortion strictly less than 2 the following theorem shows that there is no nonlinear Dvoretzky phenomenon in terms of Hausdorff dimension.

Theorem 1.8. For every α > 0 there exists a compact metric space (X, d) of Hausdorff dimension α, such that if S ⊆ X embeds into Hilbert space with distortion strictly smaller than 2 then dim_{H}(S) = 0.

As in the case of the finite nonlinear Dvoretzky theorem, Question 1.3 at distortion 2 remains open. In the same vein, the correct asymptotic dependence on δ in (4) is unknown.

Theorem 1.7 follows from the following result in the spirit of Theorem 1.5, via the same Frostman measure argument.

Theorem 1.9. There exists a universal constant c ∈ (0, ∞) such that for every δ ∈ (0, 1/2) there exists c′_{δ} ∈ (0, ∞) with the following property. Every metric measure space (X, d, μ) has a closed subset S ⊆ X such that (S, d) embeds into an ultrametric space with distortion 2 + δ, and for every {x_{i}}_{i∈I} ⊆ X and {r_{i}}_{i∈I} ⊆ [0, ∞) such that the balls {B(x_{i}, r_{i})}_{i∈I} cover Y, we have

∑_{i∈I} μ(B(x_{i}, c′_{δ}r_{i}))^{\frac{cδ}{log(1/δ)}} ⩾ μ(X)^{\frac{cδ}{log(1/δ)}} .  (5)

1.3. Talagrand’s nonlinear Dvoretzky theorem. Despite the fact that Theorem 1.5 satisfactorily encompasses both the Bourgain-Figiel-Milman nonlinear Dvoretzky phenomenon and Tao’s nonlinear Dvoretzky phenomenon, there is an important nonlinear Dvoretzky theorem due to Talagrand that does not seem to fall into this framework. To describe it we recall the definition of Talagrand’s γ_{2} functional, which is defined for every compact metric space (X, d) as follows.

γ_{2}(X, d) = inf_{\begin{matrix}\{A_{s}\}_{s=0}^{∞}⊆2^{X} \\ ∀s⩾0, |A_{s}|⩽2^{2^{s}} \end{matrix}} sup_{x∈X} ∑_{s=0}^{∞} 2^{s/2}d(x, A_{s}).

In 1987 Talagrand proved [21] the following nonlinear Dvoretzky theorem, where the notion of dimension of (X, d) is interpreted to be γ_{2}(X, d). Theorem 1.10 ([21]). There are universal constants c, D ∈ (0, ∞) such that every finite metric space (X, d) has a subset S ⊆ X that embeds into an ultrametric space with distortion D and γ_{2}(S, d) ⩾ cγ_{2}(X, d).

Theorem 1.10 is stated slightly differently in [21], but it easily follows from a combination of [21, Lem. 6], [21, Thm. 11], and [21, Prop. 13]. Also, in [21] a different definition of γ_{2} is used, but it is equivalent to the definition described above, as explained in [22].

Talagrand’s nonlinear Dvoretzky theorem is of major importance since it easily implies the majorizing measures theorem. Specifically, assume that {G_{x}}_{x∈X} is a Gaussian process and for x, y ∈ X we have d(x, y) = \sqrt{𝔼[(G_{x} − G_{y})^{2}]}. Talagrand’s majorizing measures theorem asserts that 𝔼[sup_{x∈X} G_{x}] ⩾ Kγ_{2}(X, d), where K ∈ (0, ∞) is a universal constant. Let S ⊆ X be the subset obtained from an application of Theorem 1.10 to (X, d). Since ultrametric spaces are isometric to subsets of Hilbert space, there is a Gaussian process {H_{x}}_{x∈S} such that ρ(x, y) = \sqrt{𝔼[(H_{x} − H_{y})^{2}]} is an ultrametric on S and d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y) for all x, y ∈ S. Hence γ_{2}(S, ρ) ⩾ γ_{2}(S, d) ⩾ cγ_{2}(X, d), and a standard application of Slepian’s lemma (see [21, Prop. 5]) yields 𝔼[sup_{x∈X} G_{x}] ⩾ 𝔼[sup_{x∈S} G_{x}] ⩾ D^{−1}𝔼[sup_{x∈S} H_{x}]. This shows that due to Theorem 1.10 it suffices to prove the majorizing measures theorem when (X, d) is an ultrametric space itself. Ultrametric spaces have a natural tree structure (based on nested partitions into balls; see e.g. [2, Sec. 3.1]), and they can be embedded into Hilbert space so that disjoint subtrees are orthogonal. For Gaussian processes orthogonality means independence, which indicates how the ultrametric structure can be harnessed to yield a direct and short proof of the majorizing measures theorem for ultrametrics; see [21, Prop. 13]. This striking application of a metric Dvoretzky-type theorem is of great importance to several areas; we refer to [22] for an exposition of some of its many applications.

We do not know how to use our approach to Theorem 1.5 to deduce Theorem 1.10, nor do we see a way to use Talagrand’s methods to prove Theorem 1.5. The nonlinear Dvoretzky theorems that are currently known, including variants of Theorem 1.10 for other functionals that are defined similarly to γ_{2}, differ from each other in the notion of “dimension”, or “largeness”, of a metric space that they use. It is natural to ask if there is a common theme to these results, perhaps even a general nonlinear Dvoretzky theorem that contains the Bourgain-Figiel-Milman, Talagrand and Tao phenomena as special cases. We leave this as an open-ended and somewhat vague direction for future research. Additional discussion along these lines is deferred to our forthcoming survey [14]. Question 1.11. What are the notions of “dimension” of metric spaces that yield a nonlinear Dvoretzky theorem in the sense that every (compact) metric space can be shown to contain a subset of proportional dimension that well-embeds into an ultrametric space? At present we know this for the following notions of dimension: log |X|, dim_{H}(X), γ_{2}(X) (and some natural variants of these notions). Is there an overarching principle here?

2. Preliminaries and notation

In this section we describe the basic concepts and definitions that will be used throughout the ensuing sections. As we have already noted earlier, given a metric space (X, d) and r > 0, the closed ball centered at x ∈ X of radius r is denoted B(x, r) = {y ∈ X : d(x, y) ⩽ r}. Open balls are denoted by B^{∘}(x, r) = {y ∈ X : d(x, y) < r}. We shall use this notation whenever the metric space in question will be clear from the context of the discussion, but when we will need to argue about several metrics at once we will add a subscript indicating the metric with respect to which balls are taken. Thus, we will sometimes use the notation B_{d}(x, r), B_{d}^{∘}(x, r). Similar conventions hold for diameters of subsets of X: given a nonempty A ⊆ X we denote diam(A) = sup_{x,y∈A} d(x, y) whenever the underlying metric is clear from the context, and otherwise we denote this quantity by diam_{d}(A).

Given two nonempty subsets A, B ⊆ X we denote as usual

d(A, B) = inf_{\begin{matrix}x∈A \\ y∈B \end{matrix}} d(x, y),  (6)

and we will also use the standard notation d(x, A) = d({x}, A). The Hausdorff distance between A and B is denoted

d_{H}(A, B) = max {sup_{x∈A} d(x, B), sup_{y∈B} d(y, A)} .  (7)

2.1. Combinatorial trees. The ensuing arguments rely on a variety of constructions involving combinatorial trees. We will work only with finite rooted trees, i.e., finite graphtheoretical trees T with a distinguished vertex r(T) called the root of T. We will slightly abuse notation by identifying T with its vertex set, i.e., when we write v ∈ T we mean that v is a vertex of T. We shall say that u ∈ T is an ancestor of v ∈ T ∖ {u} if u lies on the path joining v and r(T). In this case we also say that v is a descendant of u. We say that v is a weak descendant (respectively weak ancestor) of u if it is either a descendant (respectively ancestor) of u or v = u. If u is either a weak ancestor of v or a weak descendant of v we say that u and v are comparable, and otherwise we say that they are incomparable. The leaves of T, denoted L(T) ⊆ T, is the set of vertices of T that do not have descendants.

Definition 2.1 (Cut set). Let T be a rooted tree. A subset S ⊆ T is called a cut set of T if any root-leaf path in T intersects S. Equivalently, S is a cut set of T if every u ∈ T is comparable to a vertex in S. See [18, Ch. 4 & Sec. 12.4].

If v ∈ T ∖{r(T)} then we denote by p(v) = p_{T} (v) its parent in T, i.e., the vertex adjacent to v on the path joining v and r(T). We say that v ∈ T ∖ {r(t)} is a child of u ∈ T if p(v) = u, and the set p^{−1}(u) = {v ∈ T : p(v) = u} is the set of children of u. Thus L(T) = {u ∈ T : p^{−1}(u) = ∅}. If u, v ∈ T ∖ {r(T)} are distinct and satisfy p(u) = p(v) then we say that u and v are siblings in T.

The depth of u ∈ T, denoted depth_{T} (u), is the number of edges on the path joining u and r(T). Thus depth_{T} (r(T)) = 0. The least common ancestor of u, v ∈ T, denoted lca(u, v) = lca_{T} (u, v), is the vertex of maximal depth that is an ancestor of both u and v.

Given u ∈ T, we denote by T_{u} ⊆ T the subtree rooted at u, i.e., the tree consisting of all the weak descendants of u in T, with the edges inherited from T. Thus r(T_{u}) = u.

Definition 2.2. Let T be a rooted tree and A ⊆ T. For u ∈ T define D_{T} (u, A) ⊆ T to be the set of all v ∈ A such that v is a descendant of u and no ancestor of v is also in A and is a descendant of u. Note that D_{T} (u, A) = ∅ if u has no descendants in A, and D_{T} (u, A) is a cut set of the subtree T_{u} if A ∩ T_{u} is a cut-set in T_{u} (this happens in particular if A contains the leaves of T_{u}). We also define

D_{T}^{∗} (u, A) = \{ \begin{matrix}D_{T} (u, A) & if u ∈ T ∖ A, \\ \{u\} & if u ∈ A. \end{matrix}  (8)

2.2. Fragmentation maps. Trees interact with metric spaces via the notion of fragmentation maps.

Definition 2.3 (Fragmentation map). Let (X, d) be a finite metric space. A fragmentation map of X is a function F : T → 2^{X}, where T is a finite rooted tree, that satisfies the following conditions.

• F(r(T)) = X.

• If v ∈ L(T) is a leaf of T then F(v) is a singleton, i.e., F(v) = {x} for some x ∈ X.

• If v ∈ T ∖ {r(T)} the F(v) ⊆ F(p(v)).

• If u, v ∈ T are incomparable then F(u) ∩ F(v) = ∅. In what follows, given a fragmentation map F : T → 2^{X}, we will use the notation F_{u} = F(u).

Definition 2.4 (Boundary of a fragmentation map). The boundary of a fragmentation map F : T → 2^{X} is a new map ∂F : T → 2^{X} defined as follows. For u ∈ T the set ∂F(u) = ∂F_{u} is the subset of X corresponding to the image under F of the leaves of the subtree T_{u}, i.e.,

∂F_{u} = ⋃_{v∈L(T_{u})} F_{v}.

Note that we always have ∂F_{u} ⊆ F_{u}.

Definition 2.5 (Partition map). A partition map is a fragmentation map F : T → 2^{X} such that ∂F_{r(T)} = X.

Up to this point the metric on X did not play any role. The following two crucial definitions measure the interaction between partition maps of X and the geometry of X.

Definition 2.6 (Lacunary fragmentation map). Given K, γ ∈ (0, ∞), a fragmentation map F : T → 2^{X} is (K, γ)-lacunary if for every q ∈ T and every u ∈ T such that u is a weak descendant of q and u has at least two children, i.e., |p^{−1}(u)| > 1, we have

diam (F_{q}) ⩽ Kγ^{depth_{T} (u)−depth_{T} (q)} · min_{\begin{matrix}v,w∈p^{−1}(u) \\ v≠w \end{matrix}} d (∂F_{v}, ∂F_{w}) .  (9)

Definition 2.7 (Separated fragmentation map). Given β > 0 and a fragmentation map F : T → 2^{X}, a vertex u ∈ T is called β-separated if for every x ∈ (∂F_{r(T)}) ∖ (∂F_{u}) we have

d (x, F_{u}) ⩾ β · diam (F_{u}) .  (10)

The map F : T → 2^{X} is called β-separated if all the vertices u ∈ T are β-separated.

Lemma 2.8. Let F : T → X be a (K, γ)-lacunary fragmentation map of a metric space (X, d). Then (∂F_{r(T)}, d) embeds with distortion K into an ultrametric space.

Proof. For x, y ∈ ∂F_{r(T)} there are a, b ∈ L(T) such that F_{a} = {x} and F_{b} = {y}. Define

ρ(x, y) = diam (F_{lca(a,b)}) .

Since x, y ∈ F_{lca(a,b)} we have d(x, y) ⩽ ρ(x, y). Assume that x ≠ y. Then lca(a, b) has distinct children v, w ∈ p^{−1}(lca(a, b)) such that x ∈ ∂F_{v} and y ∈ ∂F_{w}. An application of (9) to q = u = lca(a, b) shows that ρ(x, y) ⩽ Kd(x, y). It remains to note that ρ is an ultrametric. Indeed, take a, b, c ∈ L(T) and write F_{a} = {x}, F_{b} = {y}, F_{c} = {w}. If lca(a, b) is a weak descendant of lca(b, c) then F_{lca(a,b)} ⊆ F_{lca(b,c)}, implying that ρ(x, y) ⩽ ρ(y, z). Otherwise lca(a, b) ∈ {lca(a, c), lca(b, c)}, implying that ρ(x, y) = max{ρ(x, z), ρ(y, z)}. □

3. Reduction to finite metric spaces

The following simple compactness lemma shows that it suffices to prove Theorem 1.5 and Theorem 1.9 when (X, d) is a finite metric space.

Lemma 3.1. Fix D, c ⩾ 1 and θ ∈ (0, 1]. Suppose that any finite metric measure space (X, d, μ) has a subset S ⊆ X that embeds with distortion D into an ultrametric space, such that every family of balls {B(x_{i}, r_{i})}_{i∈I} that covers S satisfies

∑_{i∈I} μ (B(x_{i}, cr_{i}))^{θ} ⩾ μ(X)^{θ}.  (11)

Then any metric measure space (X, d, μ) has a closed subset S ⊆ X that embeds with distortion D into an ultrametric space, such that every family of balls {B(x_{i}, r_{i})}_{i∈I} that covers S satisfies (11).

Proof. Let (X, d, μ) be a metric measure space and let X_{n} be a \frac{1}{n}-net in X, i.e., d(x, y) > \frac{1}{n} for all distinct x, y ∈ X_{n}, and d(x, X_{n}) ⩽ \frac{1}{n} for all x ∈ X. Since X is compact, X_{n} is finite. Write X_{n} = {x_{1}^{n}, x_{2}^{n}, …, x_{k_{n}}^{n}} and for j ∈ {1, …, k_{n}} define

j_{n}(x) =^{def} min {i ∈ {1, …, k_{n}} : d (x, x_{i}^{n}) = d(x, X_{n})} .

Consider the Voronoi tessellation {V_{1}^{n}, …, V_{k_{n}}^{n}} ⊆ 2^{X} given by

V_{j}^{n} =^{def} {x ∈ X : j_{n}(x) = j} .

Thus {V_{1}^{n}, …, V_{k_{n}}^{n}} is a Borel partition of X, and we can define a measure μ_{n} on X_{n} by μ_{n}(x_{j}^{n}) = μ(V_{j}). Note that by definition μ_{n}(X_{n}) = μ(X).

The assumption of Lemma 3.1 applied to the finite metric measure space (X_{n}, d, μ_{n}) yields a subset S_{n} ⊆ X_{n}, an ultrametric space (U_{n}, ρ_{n}) and a mapping f_{n} : S_{n} → U_{n} such that d(x, y) ⩽ ρ_{n}(f_{n}(x), f_{n}(y)) ⩽ Dd(x, y) for all x, y ∈ S_{n}. Moreover, if {z_{j}}_{j∈J} ⊆ X_{n} and {r_{j}}_{j∈J} ⊆ [0, ∞) satisfy ⋃_{j∈J} B(z_{j}, r_{j}) ⊇ S_{n} then

∑_{j∈J} μ_{n} (X_{n} ∩ B(z_{j}, cr_{j}))^{θ} ⩾ μ_{n}(X_{n})^{θ} = μ(X)^{θ}.  (12)

Let 𝒰 be a free ultrafilter over ℕ. Since the Hausdorff metric d_{H} (recall (7)) on the space of closed subsets of X is compact (e.g. [6, Thm. 7.3.8]), there exists a closed subset S ⊆ X such that lim_{n→𝒰} d_{H}(S, S_{n}) = 0.

Define ρ : S × S → [0, ∞) as follows. For x, y ∈ S there are (x_{n})_{n=1}^{∞}, (y_{n})_{n=1}^{∞} ∈ ∏_{n=1}^{∞} S_{n} such that lim_{n→𝒰} d(x, x_{n}) = lim_{n→𝒰} d(y, y_{n}) = 0. Set ρ(x, y) = lim_{n→𝒰} ρ_{n}(f_{n}(x_{n}), f_{n}(y_{n})).

This is well defined, i.e., ρ(x, y) does not depend on the choice of (x_{n})_{n=1}^{∞}, (y_{n})_{n=1}^{∞}. Indeed, if (x′_{n})_{n=1}^{∞}, (y′_{n})_{n=1}^{∞} ∈ ∏_{n=1}^{∞} S_{n} also satisfy lim_{n→𝒰} d(x, x′_{n}) = lim_{n→𝒰} d(y, y′_{n}) = 0 then

lim_{n→𝒰} ρ_{n}(f_{n}(x_{n}), f_{n}(y_{n}))

⩽ lim_{n→𝒰} ρ_{n}(f_{n}(x′_{n}), f_{n}(y′_{n})) + lim_{n→𝒰} ρ_{n}(f_{n}(x_{n}), f_{n}(x′_{n})) + lim_{n→𝒰} ρ_{n}(f_{n}(y_{n}), f_{n}(y′_{n}))
⩽ lim_{n→𝒰} ρ_{n}(f_{n}(x′_{n}), f_{n}(y′_{n})) + D lim_{n→𝒰} d(x_{n}, x′_{n}) + D lim_{n→𝒰} d(y_{n}, y′_{n})
= lim_{n→𝒰} ρ_{n}(f_{n}(x′_{n}), f_{n}(y′_{n})),

so that by symmetry lim_{n→𝒰} ρ_{n}(f_{n}(x_{n}), f_{n}(y_{n})) = lim_{n→𝒰} ρ_{n}(f_{n}(x′_{n}), f_{n}(y′_{n})). It is immediate to check that d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y) for all x, y ∈ S and that ρ is an ultrametric on S.

Now, let {x_{i}}_{i=1}^{∞} ⊆ X and {r_{i}}_{i=1}^{∞} ⊆ [0, ∞) satisfy ⋃_{i=1}^{∞} B(x_{i}, r_{i}) ⊇ S. Fix η > 0. For every i ∈ ℕ there is ε_{i} ∈ (0, 1) such that

μ (B(x_{i}, cr_{i} + cε_{i})) ⩽ μ (B(x_{i}, cr_{i})) + (\frac{η}{2^{i}} )^{1/θ} .  (13)

Since S is compact, there exists a finite subset I_{η} ⊆ ℕ such that ⋃_{i∈I_{η}} B(x_{i}, r_{i} + ε_{i}/2) ⊇ S. Denote ε = min_{i∈I_{η}} ε_{i}. By definition of S there exists n ∈ ℕ such that n > 8/ε and d_{H}(S_{n}, S) < ε/8. For every i ∈ I_{η} let z_{i}^{n} ∈ X_{n} satisfy d(z_{i}^{n}, x_{i}) = d(x_{i}, X_{n}) ⩽ 1/n < ε/8. Now, ⋃_{i∈I_{η}} B(z_{i}^{n}, r_{i} + 3ε_{i}/4) ⊇ S_{n} because d_{H}(S_{n}, S) < ε/8 and ⋃_{i∈I_{η}} B(x_{i}, r_{i} + ε_{i}/2) ⊇ S. An application of (12) now yields the bound

∑_{i∈I_{η}} μ_{n} (X_{n} ∩ B (z_{i}^{n}, cr_{i} + \frac{3cε_{i}}{4} ))^{θ} ⩾ μ(X)^{θ}.  (14)

By the definition of μ_{n},

μ_{n} (X_{n} ∩ B (z_{i}^{n}, cr_{i} + \frac{3cε_{i}}{4} ))

= μ (⋃ \{V_{j}^{n} : j ∈ \{1, …, k_{n}\} ∧ x_{j}^{n} ∈ B (z_{i}^{n}, cr_{i} + \frac{3cε_{i}}{4} )\})
⩽ μ (B (z_{i}^{n}, cr_{i} + \frac{3cε_{i}}{4} + \frac{1}{n}))
⩽ μ (B (x_{i}, cr_{i} + \frac{3cε_{i}}{4} + \frac{2}{n}))
⩽ μ (B (x_{i}, cr_{i} + cε_{i}))
⩽^{(13)} μ (B(x_{i}, cr_{i})) + (\frac{η}{2^{i}} )^{1/θ} .  (15)

Hence,

μ(X)^{θ} ⩽^{(14)∧(15)} ∑_{i∈I_{η}} (μ (B(x_{i}, cr_{i})) + (\frac{η}{2^{i}} )^{1/θ})^{θ}

⩽ ∑_{i∈I_{η}} (μ (B(x_{i}, cr_{i}))^{θ} + \frac{η}{2^{i}} ) ⩽ η + ∑_{i=1}^{∞} μ (B(x_{i}, cr_{i}))^{θ} . (16)

Since (16) holds for all η > 0, the proof of Lemma 3.1 is complete. □

4. The initial fragmentation map

Due to Lemma 3.1 we may assume from now on that (X, d, μ) is a finite metric measure space. By restricting to the support of μ, we assume throughout that μ({x}) > 0 for all x ∈ X. By rescaling the metric, assume also that diam(X) = 1. Our proof of Theorem 1.5 in this case will start with an initial fragmentation map F : T → 2^{X} which we will now construct in a bottom-up fashion. Once this is achieved, our goal will be to iteratively modify this fragmentation map so as to gradually arrive at the conclusion of Theorem 1.5.

Observe that any fragmentation map F : T → 2^{X} induces a weighting w : T → (0, ∞) of the vertices of T given by w(u) = μ(F_{u}). The following definition describes a way to measure the size of subtrees of a weighted tree. The exact notion of “size” here is tailored to be compatible with the ensuing arguments.

Definition 4.1 (Modified weight function). Fix integers h, k ⩾ 2 and let T be a finite graph-theoretical rooted tree, all of whose leaves are at the same depth, which is divisible by h. Assume that we are given w : T → (0, ∞). Define a new function w_{h}^{k} : T → (0, ∞) as follows. If u ∈ L(T) then

w_{h}^{k}(u) = w(u)^{\frac{k−1}{k}} .

Continue defining w_{h}^{k}(u) by reverse induction on depth_{T} (u) as follows.

w_{h}^{k}(u) = \{ \begin{matrix}w(u)^{\frac{k−1}{k}} & if h | depth_{T} (u), \\ ∑_{v∈p^{−1}(u)} w_{h}^{k}(v) & if h ∤ depth_{T} (u). \end{matrix}  (17)

Equivalently, if u ∈ T and (j − 1)h < depth_{T} (u) ⩽ jh for some integer j then

w_{h}^{k}(u) = ∑_{\begin{matrix}v∈T_{u} \\ depth_{T} (v)=jh \end{matrix}} w(v)^{\frac{k−1}{k}} .  (18)

The following lemma shows how to construct an initial fragmentation map of (X, d, μ) which has some desirable properties. In particular, the initial tree contains “pointers” to the “largest” child, where size is measured in terms of the modified weight function w_{h}^{k} of Definition 4.1. We will need this information in the ensuing pruning steps, since we will want to avoid discarding (as much as possible) these large “designated children”.

Lemma 4.2. Let (X, d, μ) be a finite metric measure space of diameter 1 and τ ∈ (0, 1/3). For every triple of integers m, h, k ⩾ 2 there exists a fragmentation map F : T → 2^{X} with the following properties.

• All the leaves of the tree T are at depth mh.

• F is a partition map, i.e., ∂F_{r(T)} = X.

• For every u ∈ T we have

diam(F_{u}) ⩽ τ^{depth_{T} (u)}.  (19)

• Every non-leaf vertex u ∈ T ∖ L(T) has a “designated child” c(u) ∈ p^{−1}(u) such that

w_{h}^{k}(c(u)) = max_{v∈p^{−1}(u)} w_{h}^{k} (v) ,  (20)

where w : T → (0, ∞) is given by w(u) = μ(F_{u}) and w_{h}^{k} : T → (0, ∞) is the modified weight function from Definition 4.1.

• Suppose that u, v ∈ T ∖ L(T) satisfy depth_{T} (u) = depth_{T} (v) and u ≠ v. Then
d (F_{c(u)}, F_{c(v)}) > \frac{1 − 3τ}{2} · τ^{depth_{T} (u)}.  (21)

Proof. The construction will be in a bottom-up fashion: the tree T will be decomposed as a disjoint union on “levels” V_{0}, V_{1}, …, V_{mh}, where V_{i} are the vertices at depth i. We will construct these levels V_{i} and the mappings F : V_{i} → 2^{X} and w_{h}^{k} : V_{i} → (0, ∞) by reverse induction on i, and describe inductively for each v ∈ V_{i+1} its parent u ∈ V_{i}, as well as the designated child c(u). At the end of this construction V_{0} will consist of a single vertex, the root of T.

Define ℓ_{mh} = |X| and write X = {x_{1}, …, x_{ℓ_{mh}}}. The initial level V_{mh} consists of the leaves of T, and it is defined to be V_{mh} = {v_{j}^{mh}}_{j=1}^{ℓ_{mh}}. We also set

F_{v_{j}^{mh}} = \{x_{j}\} and w_{h}^{k}(v_{j}^{mh}) = w(x_{j})^{\frac{k−1}{k}} = μ(\{x_{j}\})^{\frac{k−1}{k}}

for all j ∈ {1, …, ℓ_{mh}}.

Assume inductively that for i ∈ {1, …, mh − 1} we have already defined

V_{i+1} = {v_{1}^{i+1}, v_{2}^{i+1}, …, v_{ℓ_{i+1}}^{i+1}} ,

and the mappings F : V_{i+1} → 2^{X} and w_{h}^{k} : V_{i+1} → (0, ∞).

Choose j(1) ∈ {1, …, ℓ_{i+1}} such that

w_{h}^{k} (v_{j(1)}^{i+1}) = max_{j∈{1,...,ℓ_{i+1}}} w_{h}^{k} (v_{j}^{i+1}) .

Define

A_{1}^{i} = \{s ∈ \{1, …, ℓ_{i+1}\} : d (F_{v_{j(1)}^{i+1}}, F_{v_{s}^{i+1}}) ⩽ \frac{1 − 3τ}{2} τ^{i}\} .

Create a new vertex v_{1}^{i} ∈ V_{i} and define

F_{v_{1}^{i}} = ⋃_{s∈A_{1}^{i}} F_{v_{s}^{i+1}}.

Also, declare the vertices {v_{s}^{i+1}}_{s∈A_{1}^{i}} ⊆ V_{i+1} to be the children of v_{1}^{i}, and in accordance with (17) define

w_{h}^{k} (v_{1}^{i}) = \{ \begin{matrix}w (v_{1}^{i})^{\frac{k−1}{k}} & if h | i, \\ ∑_{s∈A_{1}^{i}} w_{h}^{k} (v_{s}^{i+1}) & if h ∤ i. \end{matrix}

Finally, set

c (v_{1}^{i}) = v_{j(1)}^{i+1}.

Continuing inductively, assume that we have defined v_{1}^{i}, v_{2}^{i}, …, v_{r}^{i} ∈ V_{i}, together with nonempty disjoint sets

A_{1}^{i}, …, A_{r}^{i} ⊆ {1, …, ℓ_{i+1}}.

If ⋃_{t=1}^{r} A_{t}^{i} = {1, …, ℓ_{i+1}} then define ℓ_{i} = r and V_{i} = {v_{1}^{i}, v_{2}^{i}, …, v_{r}^{i}}. Otherwise, choose j(r + 1) ∈ {1, …, ℓ_{i+1}} ∖ ⋃_{t=1}^{r} A_{t}^{i} such that

w_{h}^{k} (v_{j(r+1)}^{i+1}) = max ; j∈{1,...,ℓ_{i+1}}∖⋃_{t=1}^{r} A_{t}^{i} w_{h}^{k} (v_{j}^{i+1}) ,  (22)

and define

A_{r+1}^{i} = \{s ∈ \{1, …, ℓ_{i+1}\} ∖ ⋃_{t=1}^{r} A_{t}^{i} : d (F_{v_{j(r+1)}^{i+1}}, F_{v_{s}^{i+1}}) ⩽ \frac{1 − 3τ}{2} τ^{i}\} .  (23)

Create a new vertex v_{r+1}^{i} ∈ V_{i} and define

F_{v_{r+1}^{i}} = ⋃_{s∈A_{r+1}^{i}} F_{v_{s}^{i+1}}.  (24)

Also, declare the vertices {v_{s}^{i+1}}_{s∈A_{r+1}^{i}} ⊆ V_{i+1} to be the children of v_{r+1}^{i} and define

w_{h}^{k} (v_{r+1}^{i}) = \{ \begin{matrix}w (v_{r+1}^{i})^{\frac{k−1}{k}} & if k | i, \\ ∑_{s∈A_{r+1}^{i}} w_{h}^{k} (v_{s}^{i+1}) & if k ∤ i. \end{matrix}

Finally, set

c (v_{r+1}^{i}) = v_{j(r+1)}^{i+1}.  (25)

The above recursive procedure must terminate, yielding the level i set V_{i}. We then proceed inductively until the set V_{1} has been defined. We conclude by defining V_{0} to be a single new vertex r(T) (the root) with all the vertices in V_{1} its children. The designated child of the root, c(r(T)), is chosen to be a vertex u ∈ V_{1} such that w_{h}^{k} (u) = max_{v∈V_{1}} w_{h}^{k} (v). We also set F_{r(T)} = X and w_{h}^{k}(r(T)) = μ(X)^{\frac{k−1}{k}}.

The resulting fragmentation map F : T → 2^{X} is by definition a partition map, since F(V_{mh}) = F(L(T)) = X. Also, the construction above guarantees the validity of (20) due to (22) and (25).

We shall now prove (19) by reverse induction on depth_{T} (u). If depth_{T} (u) = mh then diam(F_{u}) = 0 and there is nothing to prove. Assuming the validity of (19) whenever depth_{T} (u) = i + 1, suppose that depth_{T} (u) = i and moreover that u = v_{r+1}^{i} in the above construction. By virtue of (23) and (24) we know that

diam (F_{u}) = diam (F_{v_{r+1}^{i}}) ⩽ 3 max_{s∈A_{r+1}^{i}} diam (F_{v_{s}}^{i+1}) + 2\frac{1 − 3τ}{2} τ^{i} ⩽ 3τ^{i+1} + (1 − 3τ)τ^{i} = τ^{i}.

Since (19) is also valid for i = 0 (because diam(X) = 1), this concludes the proof of (19).

It remains to prove (21). Since we are assuming that u ≠ v are non-leaf vertices and depth_{T} (u) = depth_{T} (v), we may write u = v_{s}^{i} and v = v_{t}^{i} for some i ∈ {1, …, mh − 1} and s < t. Then by the above construction c (v_{s}^{i}) = v_{j(s)}^{i+1}, c (v_{t}^{i}) = v_{j(t)}^{i+1} and

j(t) ∈ {1, …, ℓ_{i+1}} ∖ ⋃_{ℓ=1}^{t−1} A_{ℓ}^{i} ⊆ {1, …, ℓ_{i+1}} ∖ ⋃_{ℓ=1}^{s−1} A_{ℓ}^{i},

yet j(t) ∉ A_{s}^{i}. The validity of (21) now follows from the definition of A_{s}^{i}; see (23). □

5. An iterated Hölder argument for trees

Lemma 4.2 yields a partition map that will serve as the base case of an inductive construction. This construction will iteratively remove parts of the tree T of Lemma 4.2 while maintaining certain properties of the resulting tree. To simplify matters, it is worthwhile to formulate some of the ensuing steps as combinatorial statements for weighted trees.

As we discussed earlier, the partition map F : T → 2^{X} of Lemma 4.2 induces a weighting w : T → (0, ∞) of the vertices of T given by w(u) = μ(F_{u}). In this section we will prove inequalities for weighted trees that will be used crucially in our proof of Theorem 1.5. Lemma 5.4 below is inspired by an argument of [2, Lem. 3.25], though our assumptions, proof, and conclusion are different. These changes are crucial for later applications. The appropriate setting for the discussion is a certain class of weighted trees, which we now introduce; the definition below contains the tree of Lemma 4.2 as a special case.

Definition 5.1 (Subadditive weighted tree with designated children). Fix integers h, k ⩾ 2. A subadditive weighted tree with designated children is a triple (T, w, c) consisting of a finite rooted graph-theoretical tree T, a mapping w : T → (0, ∞) and for every non-leaf vertex u ∈ T ∖ L(T) a “designated child” c(u) ∈ p^{−1}(u), such that the following conditions hold true.

• All the leaves of T are at the same depth, which is divisible by h.

• For every non-leaf vertex u ∈ T ∖ L(T),

w(u) ⩽ ∑_{v∈p^{−1}(u)} w(v).  (26)

• For every non-leaf vertex u ∈ T ∖ L(T),

w_{h}^{k}(c(u)) = max_{v∈p^{−1}(u)} w_{h}^{k}(v),  (27)

where w_{h}^{k} : T → (0, ∞) is the modified weight function of Definition 4.1.

Definition 5.2 (Subtree). Let T be a finite rooted tree. A subtree T′ of T is a connected rooted subgraph of T whose set of leaves is a subset of the leaves of T, i.e., L(T′) ⊆ L(T).

Definition 5.3 (Sparsified tree). Fix integers h, k ⩾ 2 and let (T, w, c) be a subadditive weighted tree with designated children. For i ∈ ℤ define a subtree T^{(i)} of T as follows.

T^{(i)} = T ∖ ( ⋃_{\begin{matrix}u∈T \\ depth_{T} (u)=i−1 \end{matrix}} ⋃_{v∈p^{−1}(u)∖\{c(u)\}} T_{v}) .  (28)

Thus T^{(i)} is obtained from T by removing all the subtrees rooted at vertices of depth i that are not designated children. Note that by definition T^{(i)} = T if either i ⩽ 0 or T has no vertices at depth i.

Lemma 5.4. Fix h, k ∈ ℕ satisfying h ⩾ k ⩾ 2 and let (T, w, c) be a subadditive weighted tree with designated children. Assume that all the leaves of T are at depth h. Then there exists L ⊆ {1, …, h} with |L| ⩾ h − k + 1 such that for every i ∈ L we have

∑_{ℓ∈L(T^{(i)})} w(ℓ)^{\frac{k−1}{k}} ⩾ w(r)^{\frac{k−1}{k}} ,

where r = r(T) is the root of T and T^{(i)} is as in Definition 5.3.

Proof. For i ∈ {1, …, h} and u ∈ T define f_{i}(u) ∈ (0, ∞) by reverse induction on depth_{T} (u) as follows. If depth_{T} (u) = h, i.e., u is a leaf of T, set

f_{i}(u) = w(u)^{\frac{k−1}{k}} .  (29)

If depth_{T} (u) < h define recursively

f_{i}(u) = \{ \begin{matrix}max_{v∈p^{−1}(u)} f_{i}(v) & if i = depth_{T} (u) + 1, \\ ∑_{v∈p^{−1}(u)} f_{i}(v) & if i ≠ depth_{T} (u) + 1. \end{matrix}  (30)

We observe that for all i ∈ {1, …, h} and u ∈ T we have

i ⩽ depth_{T} (u) ⟹ f_{i}(u) = ∑_{ℓ∈L(T_{u})} w(ℓ)^{\frac{k−1}{k}} ,  (31)

and

i > depth_{T} (u) ⟹ f_{i}(u) = ∑_{ℓ∈L((T_{u})^{(i)})} w(ℓ)^{\frac{k−1}{k}} ,  (32)

where analogously to (28) we define

(T_{u})^{(i)} = T_{u} ∖ ( ⋃_{\begin{matrix}a∈T \\ depth_{T} (a)=i−1 \end{matrix}} ⋃_{b∈p^{−1}(a)∖\{c(a)\}} T_{b}) .  (33)

In other words, recalling that T_{u} is the subtree of T rooted at u, the subtree (T_{u})^{(i)} is obtained from T_{u} by deleting all the subtrees rooted at vertices of depth i that are not designated children (here depth is measured in T, i.e., the distance from the original root r(T)).

Identities (31) and (32) follow by reverse induction on depth_{T} (u) from the recursive definition of f_{i}(u). Indeed, if depth_{T} (u) = h then (32) is vacuous and (31) follows from (29). Assume that u ∈ T is not a leaf of T and that (31) and (32) hold true for the children of u. If i ⩽ depth_{T} (u) then by (30) and the inductive hypothesis we have

f_{i}(u) = ∑_{v∈p^{−1}(u)} f_{i}(v) = ∑_{v∈p^{−1}(u)} ∑_{ℓ∈L(T_{v})} w(ℓ)^{\frac{k−1}{k}} = ∑_{ℓ∈L(T_{u})} w(ℓ)^{\frac{k−1}{k}} .

If i = depth_{T} (u) + 1 then since we are assuming that (31) holds for each v ∈ p^{−1}(u),

f_{i}(u) =^{(30)} max_{v∈p^{−1}(u)} f_{i}(v) = max_{v∈p^{−1}(u)} ∑_{ℓ∈L(T_{v})} w(ℓ)^{\frac{k−1}{k}} =^{(18)} max_{v∈p^{−1}(u)} w_{h}^{k}(v)

=^{(27)} w_{h}^{k}(c(u)) =^{(18)} ∑_{ℓ∈L(T_{c(u)})} w(ℓ)^{\frac{k−1}{k}} =^{(33)} ∑_{ℓ∈L((T_{u})^{(i)})} w(ℓ)^{\frac{k−1}{k}} .

Finally, if i > depth_{T} (u) + 1 then we are assuming that (32) holds for each v ∈ p^{−1}(u), and therefore

f_{i}(u) =^{(30)} ∑_{v∈p^{−1}(u)} f_{i}(v) =^{(32)} ∑_{v∈p^{−1}(u)} ∑_{ℓ∈L((T_{v})^{(i)})} w(ℓ)^{\frac{k−1}{k}} =^{(33)} ∑_{ℓ∈L((T_{u})^{(i)})} w(ℓ)^{\frac{k−1}{k}} .

This completes the inductive verification of the identities (31) and (32).

Our next goal is to prove by reverse induction on depth_{T} (u) that for every H ⊆ {1, …, h} with |H| = k we have,

∏_{i∈H} f_{i}(u) ⩾ w(u)^{k−1}.  (34)

Indeed, if depth_{T} (u) = h then (34) holds as equality due to (29). Assume inductively that depth_{T} (u) < h and that (34) holds for all the children of u. We claim that there exists j ∈ H such that

∏_{i∈H} f_{i}(u) ⩾ ( max_{v∈p^{−1}(u)} f_{j}(v)) ∏_{i∈H∖{j}} ( ∑_{v∈p^{−1}(u)} f_{i}(v)) .  (35)

Indeed, if depth_{T} (u) + 1 ∈ H then take j = depth_{T} (u) + 1 and note that (35) holds as equality due to (30). On the other hand, if depth_{T} (u) + 1 ∉ H then let j be an arbitrary element of H, and note that due to (30) we have

∏_{i∈H} f_{i}(u) = ( ∑_{v∈p^{−1}(u)} f_{j}(v)) ∏_{i∈H∖{j}} ( ∑_{v∈p^{−1}(u)} f_{i}(v))

⩾ ( max_{v∈p^{−1}(u)} f_{j}(v)) ∏_{i∈H∖{j}} ( ∑_{v∈p^{−1}(u)} f_{i}(v)) ,

as required. Now,

∏_{i∈H} f_{i}(u) ⩾^{(∗)} ( max_{v∈p^{−1}(u)} f_{j}(v)) ( ∑_{v∈p^{−1}(u)} ∏_{i∈H∖\{j\}} f_{i}(v)^{\frac{1}{k−1}} )^{k−1}

⩾ ( ∑_{v∈p^{−1}(u)} ∏_{i∈H} f_{i}(v)^{\frac{1}{k−1}} )^{k−1} ⩾^{(∗∗)} ( ∑_{v∈p^{−1}(u)} w(v))^{k−1} ⩾^{(26)} w(u)^{k−1},

where in (∗) we used (35) and Hölder’s inequality, and in (∗∗) we used the inductive hypothesis. This concludes the proof of (34).

We are now in position to complete the proof of Lemma 5.4. Set H_{1} = {1, …, k}. Then

max_{i∈H_{1}} ∑_{ℓ∈L(T^{(i)})} w(ℓ)^{\frac{k−1}{k}} ⩾ ( ∏_{i∈H_{1}} ∑_{ℓ∈L(T^{(i)})} w(ℓ)^{\frac{k−1}{k}} )^{\frac{1}{k}} =^{(32)} ( ∏_{i∈H_{1}} f_{i}(r))^{\frac{1}{k}} ⩾^{(34)} w(r)^{\frac{k−1}{k}} .

Hence there is i_{1} ∈ H_{1} satisfying

∑_{ℓ∈L(T^{(i_{1})})} w(ℓ)^{\frac{k−1}{k}} ⩾ w(r)^{\frac{k−1}{k}} .

Now define H_{2} = (H_{1} ∖ {i_{1}}) ∪ {k + 1} and repeat the above argument with H_{2} replacing H_{1}. We deduce that there exists i_{2} ∈ H_{2} satisfying

∑_{ℓ∈L(T^{(i_{2})})} w(ℓ)^{\frac{k−1}{k}} ⩾ w(r)^{\frac{k−1}{k}} .

We may repeat this process inductively h − k + 1 times, and let L = {i_{1}, i_{2}, …, i_{h−k+1}}. □

Definition 5.5 (Subtree sparsified at a subset). Fix two integers h, k ⩾ 2 and let let (T, w, c) be a subadditive weighted tree with designated children (recall Definition 5.1). Let T′ be a subtree of T (see Definition 5.2) and S ⊆ T′. We say that the subtree T′ is sparsified at S if every v ∈ S is a designated child and has no siblings in T′. For the purpose of this definition we declare the root r(T) to be a designated child, i.e., we allow r(T) ∈ S. Thus v ∈ T is a designated child if it is either the root of T or c(p(v)) = v.

Lemma 5.6. Fix two integers h, k ⩾ 2 with h ⩾ 2k^{2}. Let (T, w, c) be a subadditive weighted tree with designated children as in Definition 5.1 (thus all the leaves of T are at the same depth, which is divisible by h, and the designated child map c satisfies (27)). Then there exists a subtree T′ of T with the same root as T, and two subsets R, S ⊆ T′, both containing the root of T′, with the following properties:

• For any non-leaf u ∈ T′ we have c(u) ∈ T′.

• R = {v ∈ T′ : h | depth_{T} (v)}.

• For any non-leaf vertex u ∈ R,

∑_{v∈D_{T′}(u,R)} w(v)^{(1− \frac{1}{k})^{2}} ⩾ w(u)^{(1− \frac{1}{k})^{2}}.  (36)

Recall that D_{T′}(·, ·) is given in Definition 2.2.

• For every u, v ∈ R such that depth_{T} (v) = depth_{T} (u) + h and v is a descendant of u, there is one and only one w ∈ S such that w lies on the path joining u and v and depth_{T} (u) < depth_{T} (w) ⩽ depth_{T} (v).

• For any u ∈ T′ such that D_{T′}(u, S) ≠ ∅, all the vertices of D_{T′}(u, S) are at the same depth in T′_{u}, which is an integer between 1 and 2h.

• T′ is sparsified at the subset S.

Proof. The proof of Lemma 5.6 is by induction on the height of the tree, but we need the following strengthening of the inductive hypothesis so as to deal with multiple trees. Suppose that we are given a collection of (disjoint) subadditive weighted trees with designated children (T_{1}, w, c) …, (T_{ℓ}, w, c), each T_{i} is rooted at r_{i} and all of them having the same height, which is divisible by h (formally we should denote the weighting of T_{i} by w_{i}, but since the trees are disjoint, denoting all the weightings by w will not create any confusion). We will prove that there exists a subset C ⊆ {1, …, ℓ} with the following properties.

• For every i ∈ C there is a subtree T′_{i} of T_{i} rooted at r_{i}, and subsets S_{i}, R_{i} ⊆ T′_{i}, both containing the root of T′_{i}, such that for any non-leaf u ∈ T′_{i} we have c(u) ∈ T′_{i}.

• R_{i} = {v ∈ T′_{i} : h | depth_{T_{i}}(v)}.

• For any non-leaf vertex u ∈ R_{i},

∑_{v∈D_{T′_{i}}(u,R_{i})} w(v)^{(1− \frac{1}{k})^{2}} ⩾ w(u)^{(1− \frac{1}{k})^{2}}.  (37)

• For every u, v ∈ R_{i} such that depth_{T_{i}}(v) = depth_{T_{i}}(u) + h and v is a descendant of u, there is one and only one w ∈ S_{i} such that w lies on the path joining u and v and depth_{T_{i}}(u) < depth_{T_{i}}(w) ⩽ depth_{T_{i}}(v).

• For any u ∈ T′_{i} such that D_{T′_{i}}(u, S_{i}) ≠ ∅, all the vertices of D_{T′_{i}}(u, S_{i}) are at the same depth in (T′_{i})_{u}, which is an integer between 1 and 2h.

• T′_{i} is sparsified at the subset S_{i}.

• The vertices in ⋃_{i∈C} D_{T′_{i}}(r_{i}, S_{i}) have the same depth (in their respective tree), regardless of i, and

∑_{i∈C} w(r_{i})^{(1− \frac{1}{k})^{2}} ⩾ (∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{1− \frac{1}{k}} .  (38)

Note that Lemma 5.6 is the case ℓ = 1 of this statement, but it will be beneficial to prove the more general statement as formulated above.

When the height of all the T_{i} is 0 we simply set C = {1, …, ℓ} and T′_{i} = S_{i} = R_{i} = T_{i}. Most of the above conditions hold vacuously in this case (there are no non-leaf vertices and D_{T′_{i}}(u, S_{i}) = ∅). Condition (38) follows from subadditivity of the function (0, ∞) ∋ t ↦ t^{1− \frac{1}{k}}.

Assume next that the leaves of {T_{i}}_{i=1}^{ℓ} are all at depth mh for some m ∈ ℕ. Let T̂_{j} be the subgraph of T_{j} induced on all the vertices of depth at most h in T_{j}. Note that by (18) the restriction of the induced weight function w_{h}^{k} to T̂_{j} coincides with the corresponding weight function induced by the weighted tree (T̂_{j}, w), and consequently the same can be said about

the designated child map c|T̂_{j}. Therefore, an application of Lemma 5.4 to (T̂_{j}, w, c) yields a subset L_{j} ⊆ {1, …, h} with |L_{j}| = h − k + 1 such that for all i ∈ L_{j} we have

∑_{\begin{matrix}u∈T̂_{j}^{(i)} \\ depth_{T_{j}} (u)=h \end{matrix}} w(u)^{1− \frac{1}{k}} ⩾ w(r_{j})^{1− \frac{1}{k}} ,  (39)

where T̂_{j}^{(i)} is the subtree of T̂_{j} that is obtained by sparsifying the ith level as in Definition 5.3.

Let j_{0} ∈ {1, …, ℓ} satisfy

w(r_{j_{0}}) = max_{j∈{1,...,ℓ}} w(r_{j}).  (40)

For j ∈ {1, …, ℓ} denote L′_{j} = L_{j} ∩ L_{j_{0}}. Then

|L′_{j}| = |L_{j}| + |L_{j_{0}}| − |L_{j} ∪ L_{j_{0}}| ⩾ (h − k + 1) + (h − k + 1) − h = h − 2(k − 1). (41)

If ℓ = 1 let s_{0} ∈ {1, …, h} be an arbitrary integer in L_{j_{0}}. If ℓ ⩾ 2 let s_{0} ∈ {1, …, h} satisfy

∑_{\begin{matrix}j∈\{1,...,ℓ\}∖\{j_{0}\} \\ s_{0}∈L′_{j} \end{matrix}} w(r_{j})^{1− \frac{1}{k}} = max_{s∈\{1,...,h\}} ∑_{\begin{matrix}j∈\{1,...,ℓ\}∖\{j_{0}\} \\ s∈L′_{j} \end{matrix}} w(r_{j})^{1− \frac{1}{k}} .  (42)

By averaging we see that

∑_{\begin{matrix}j∈\{1,...,ℓ\}∖\{j_{0}\} \\ s_{0}∈L′_{j} \end{matrix}} w(r_{j})^{1− \frac{1}{k}} ⩾ \frac{1}{h − k + 1} ∑_{s∈L_{j_{0}}} ∑_{\begin{matrix}j∈\{1,...,ℓ\}∖\{j_{0}\} \\ s∈L′_{j} \end{matrix}} w(r_{j})^{1− \frac{1}{k}}

= \frac{1}{h − k + 1} ∑_{j∈\{1,...,ℓ\}∖\{j_{0}\}} |L′_{j}|w(r_{j})^{1− \frac{1}{k}} ⩾^{(41)} \frac{h − 2(k − 1)}{h − (k − 1)} ∑_{j∈\{1,...,ℓ\}∖\{j_{0}\}} w(r_{j})^{1− \frac{1}{k}} . (43)

Now define

C = {j ∈ {1, …, ℓ} : s_{0} ∈ L_{j}} .  (44)

We know that j_{0} ∈ C, since this is trivial if ℓ = 1 and if ℓ ⩾ 2 then s_{0} ∈ L′_{j} ⊆ L_{j_{0}} for some j ∈ {1, …, ℓ} ∖ {j_{0}}. This also means that if ℓ ⩾ 2 then |C| ⩾ 2. We shall now prove (38). By the choice of j_{0} in (40) we know that for all j ∈ {1, …, ℓ} ∖ {j_{0}} we have

w (r_{j})^{1− \frac{1}{k}} ⩽ \frac{1}{2} ∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} .  (45)

This implies that for all j ∈ {1, …, ℓ} ∖ {j_{0}},

w(r_{j})^{(1− \frac{1}{k})^{2}} ⩾ \frac{h − (k − 1)}{h − 2(k − 1)} · \frac{w(r_{j})^{1− \frac{1}{k}}}{(∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{\frac{1}{k}}} .  (46)

To check (46) note that it is equivalent to the inequality

\frac{h − (k − 1)}{h − 2(k − 1)} (\frac{w(r_{j})^{1− \frac{1}{k}}}{∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}}} )^{\frac{1}{k}} ⩽ 1.

By (45) and the fact that h ⩾ 2k^{2}, it suffices to show that (2k^{2} −k +1)/(2k^{2} −2k +2) ⩽ 2^{1/k}. Since 2^{1/k} ⩾ 1 + 1/(2k) it suffices to check that 2k(2k^{2} − k + 1) ⩽ (2k + 1)(2k^{2} − 2k + 2), which is immediate to verify.

Having established (46), we proceed as follows.

∑_{j∈C} w(r_{j})^{(1− \frac{1}{k})^{2}}  =  \frac{w(r_{j_{0}})^{1− \frac{1}{k}}}{w(r_{j_{0}})^{(1− \frac{1}{k})^{\frac{1}{k}}}} + ∑_{j∈C∖\{j_{0}\}} w(r_{j})^{(1− \frac{1}{k})^{2}}

⩾^{(46)}  \frac{w(r_{j_{0}})^{1− \frac{1}{k}}}{(∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{\frac{1}{k}}} + \frac{h − (k − 1)}{h − 2(k − 1)} · \frac{∑_{j∈C∖\{j_{0}\}} w(r_{j})^{1− \frac{1}{k}}}{(∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{\frac{1}{k}}}

⩾^{(43)∧(44)} \frac{w(r_{j_{0}})^{1− \frac{1}{k}}}{(∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{\frac{1}{k}}} + \frac{∑_{j∈\{1,...,ℓ\}∖\{j_{0}\}} w(r_{j})^{1− \frac{1}{k}}}{(∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{\frac{1}{k}}}

= (∑_{i=1}^{ℓ} w(r_{i})^{1− \frac{1}{k}} )^{1− \frac{1}{k}} ,

completing the proof of (38).

We can now complete the proof of Lemma 5.6 by applying the inductive hypothesis. For every j ∈ C let u_{1}^{j}, u_{2}^{j}, …, u_{ℓ_{j}}^{j} be the leaves of the tree T̂_{j}^{(s_{0})}, i.e., the subtree of T̂_{j} that was sparsified at level s_{0}. Consider the subtrees of T_{j} that are rooted at u_{1}^{j}, u_{2}^{j}, …, u_{ℓ_{j}}^{j}, i.e., (T_{j})_{u_{1}^{j}}, (T_{j})_{u_{2}^{j}}, …, (T_{j})_{u_{ℓ_{j}}^{j}}. By the inductive hypothesis applied to these trees there exists a

subset C_{j} ⊆ {1, …, ℓ_{j}} such that for each i ∈ C_{j} there is a subtree (T_{j})′_{u_{i}^{j}} of (T_{j})_{u_{i}^{j}} and subsets S_{ji}, R_{ji} ⊆ (T_{j})′_{u_{i}^{j}} that satisfy the inductive hypotheses.

Denote for j ∈ C,

T′_{j} = ( ⋃_{i∈C_{j}}(T_{j})′_{u_{i}^{j}} ) ⋃ ( ⋃_{i∈C_{j}} {u ∈ T̂_{j}^{(s_{0})} : u ancestor of u_{i}^{j}}) .

Thus T′_{j} is obtained by taking the subtree of T̂_{j}^{(s_{0})} whose leaves are {u_{i}^{j}}_{i∈C_{j}}, and replacing

every leaf u_{i}^{j} by the tree (T_{j})′_{u_{i}^{j}}. We also define R_{j} = (⋃_{i=1}^{ℓ_{j}} R_{ji}) ⋃{r_{j}}, and

S_{j} = (⋃_{i=1}^{ℓ_{j}} (S_{ji} ∖ {u_{i}^{j}})) ⋃ {u ∈ T̂_{j}^{(s_{0})} : depth_{T_{j}}(u) = s_{0}} ⋃{r_{j}}.

Note by the definition of T̂_{j}^{(s_{0})} every u ∈ T̂_{j}^{(s_{0})} with depth_{T_{j}}(u) = s_{0} has no siblings in T̂_{j}^{(s_{0})}.

All the desired properties of T′_{j}, R_{j}, S_{j} follow immediately for the construction; only (37) when u = r_{j} requires justification as follows.

∑_{v∈D_{T′_{j}} (r_{j},R_{j})} w(v)^{(1− \frac{1}{k})^{2}} = ∑_{i∈C_{j}} w (u_{i}^{j})^{(1− \frac{1}{k})^{2}} ⩾^{(38)} (∑_{i=1}^{ℓ_{j}} w (u_{i}^{j})^{1− \frac{1}{k}} )^{1− \frac{1}{k}} ⩾^{(39)} w(r_{j})^{(1− \frac{1}{k})^{2}}. □

6. Construction of ultrametric subsets

An application of Lemma 5.6 to the initial fragmentation tree of Lemma 4.2 yields a fragmentation tree with useful geometric properties that will be exploited heavily in the subsequent steps of the proof of Theorem 1.5.

Corollary 6.1. Fix τ ∈ (0, 1/3) and integers m, h, k ⩾ 2 with h ⩾ 2k^{2}. Let (X, d, μ) be a finite metric measure space of diameter 1. Then there exists a fragmentation map F : T → 2^{X} with the following properties. universal c > 0) {1} All the leaves of the tree T are at depth mh. {2} For every u ∈ T we have

diam(F_{u}) ⩽ τ^{depth_{T} (u)}.  (47)

{3} Denote by R ⊆ T the set of vertices at depths which are integer multiples of h. Then for every non-leaf u ∈ R,

∑_{v∈D_{T} (u,R)} μ (F_{v})^{(1− \frac{1}{k})^{2}} ⩾ μ (F_{u})^{(1− \frac{1}{k})^{2}} .  (48)

{4} There is a subset S ⊆ T containing the root of T such that every u ∈ S is either the root or has no sibling in T. Moreover, R and S are “alternating” in the following sense. For every u, v ∈ R such that depth_{T} (v) = depth_{T} (u) + h and v is a descendant of u, there is one and only one w ∈ S such that w lies on the path joining u and v and depth_{T} (u) < depth_{T} (w) ⩽ depth_{T} (v).

\{5\} The vertices of S are \frac{1−3τ}{2τ} -separated (recall Definition 2.7). {6} For every u ∈ R, all the vertices in D_{T} (u, S) have the same depth in T, which is at most

depth_{T} (u) + h. \{7\} F is (\frac{2}{1−3τ} τ^{−2h}, τ^{−1})-lacunary (recall Definition 2.6).

Proof. Let F^{0} : T^{0} → 2^{X} be the partition map of Lemma 4.2, constructed with parameters m, h, k, and having the associated designated child map c from Lemma 4.2. Let T be the tree obtained by applying Lemma 5.6 to (T^{0}, w, c), where w : T^{0} → (0, ∞) is given by w(v) = μ(F_{v}^{0}). Define a fragmentation map F : T → 2^{X} by F = F^{0}|_{T}, i.e., by restricting F^{0} to the subtree T. Properties {1}, {2} are satisfied by F^{0} due to Lemma 4.2, and therefore they are also satisfied by F since T has the same root as T^{0}. Properties {3}, {4}, {6} are part of the conclusion of Lemma 5.6. It remains to prove properties {5} and {7}.

Assume that u ∈ S. Take y ∈ (∂F_{r(T)}) ∖ (∂F_{u}). In order to prove property {5} it suffices to show that d(y, F_{u}) ⩾ \frac{1−3τ}{2τ} diam(F_{u}). By property \{4\} it follows that u = c(p(u)). Let w = lca_{T} (u, y) and take u′, y′ ∈ D_{T} (w, S) such that u′ is a weak ancestor of u and y′ is a weak ancestor of y. By Lemma 5.6 we know that depth_{T} (u′) = depth_{T} (y′), and therefore by conclusion (21) of Lemma 4.2 and using the fact that c(p(u′)) = u′ and c(p(y′)) = y′ (because u′, y′ ∈ S),

d (y, F_{u}) ⩾ d (F_{y′}, F_{u′}) ⩾ \frac{1 − 3τ}{2} τ^{depth_{T} (u′)−1} ⩾ \frac{1 − 3τ}{2τ} τ^{depth_{T} (u)} ⩾^{(47)} \frac{1 − 3τ}{2τ} diam(F_{u}).

It remains to prove property {7}. Take q ∈ T and let u ∈ T be a weak descendent of q that has at least two children in T, i.e., v, w ∈ p^{−1}(u) ∩ T, v ≠ w. Our goal is to show that

diam (F_{q}) ⩽ \frac{2τ^{−2h}}{1 − 3τ} · τ^{depth_{T} (q)−depth_{T} (u)} · d (∂F_{v}, ∂F_{w}) .  (49)

Since v and w are siblings in T we know by {4} that {u, v} ∩ S = ∅. Note that

∂F_{v} = ⋃_{y∈D(v,S)} ∂F_{y} and ∂F_{w} = ⋃_{x∈D(w,S)} ∂F_{x},

and therefore

d (∂F_{v}, ∂F_{w}) = min_{\begin{matrix}y∈D(v,S) \\ x∈D(w,S) \end{matrix}} d (∂F_{y}, ∂F_{x}) .  (50)

Note that since {v, w} ∩ S = ∅ we have D(v, S) ∪ D(w, S) ⊆ D(u, S). By Lemma 5.6 it follows that all the vertices in D(v, S) ∪ D(w, S) are at the same depth in T. Denote this depth by ℓ. Due to Lemma 5.6 we know that ℓ ⩽ depth_{T} (u) + 2h. By conclusion (21) of Lemma 4.2 we deduce that for all y ∈ D(v, S) and x ∈ D(w, S) we have

d (∂F_{y}, ∂F_{x}) ⩾ d (F_{y}, F_{x}) = d (F_{c(p(y))}, F_{c(p(x))}) > \frac{1 − 3τ}{2} τ^{ℓ} ⩾ \frac{1 − 3τ}{2} τ^{depth_{T} (u)+2h}. (51)

Hence,

d (∂F_{v}, ∂F_{w}) >^{(50)∧(51)} \frac{1 − 3τ}{2} τ^{depth_{T} (u)+2h} ⩾^{(47)} \frac{1 − 3τ}{2} τ^{depth_{T} (u)−depth_{T} (q)+2h} diam(F_{q}),

proving (49). □

In order to proceed with the proof of Theorem 1.5 we will need to use a weighted version of the results of [15, 19]. Theorem 6.2 below follows from a slight modification of the argument in [19], though it is not stated there explicitly. We will therefore explain how [19] can be modified to deduce this statement. Alternatively, a similar statement (with slightly worse distortion bound) can be obtained by natural modifications of the argument in [15].

Theorem 6.2. Let (X, d) be a finite metric space and w_{1}, w_{2} : X → [0, ∞) two nonnegative weight functions. Then for every ε ∈ (0, 1) there exists a subset S ⊆ X that embeds into an ultrametric space with distortion

D = \frac{2}{ε(1 − ε)^{\frac{1−ε}{ε}}} ,  (52)

and satisfying

(∑_{x∈S} w_{1}(x)) (∑_{x∈X} w_{2}(x))^{ε} ⩾ ∑_{x∈X} w_{1}(x)w_{2}(x)^{ε}.  (53)

Remark 6.3. Theorem 6.2 implies the finite nonlinear Dvoretzky theorem (Theorem 1.2) in the special case w_{1} = w_{2} = 1. Another special case of interest is when w_{1} = w and w_{2} = w^{1−ε}. In this case conclusion (53) becomes

∑_{x∈S} w(x)^{1−ε} ⩾ (∑_{x∈X} w(x))^{1−ε} .  (54)

This type of requirement was studied in [2] under the name of “the weighted metric Ramsey problem”, where is was shown that there always exists S ⊆ X satisfying (54) that embeds into an ultrametric space with distortion O (ε^{−1} log(2/ε)).

Proof of Lemma 6.2. The beginning of the argument is most natural to state in the context of general metric measure spaces (X, d, μ). So, assume that (X, d, μ) is a metric measure space; we will later specialize the discussion to the case of finite spaces.

Let f : X → [0, ∞) be a nonnegative Borel measurable function. Lemma 2.1 of [19] states that for every compact S ⊆ X and every R > r > 0 there exists a compact subset T ⊆ S satisfying

∫_{T} \frac{μ(B(x, R))}{μ(B(x, r))}f(x)dμ(x) ⩾ ∫_{S} fdμ,  (55)

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.

Fix a nonnegative Borel measurable w ∈ L_{1}(μ). Iterate the above statement as follows; the same iteration is carried out for the special case w = 1 in Lemma 2.2 of [19]. Assume that we are given a non-increasing sequence of positive numbers R = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ ⋯ > 0 converging to zero. Assume also that diam(X) ⩽ 2R. For n ∈ ℕ define f_{n} : X → [0, ∞) by

f_{n}(x) = ( ∏_{m=n}^{∞} \frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))}) w(x),  (56)

Where D be given by (52). Note that 0 ⩽ f_{n} ⩽ w for all n ∈ ℕ. Assume that we already defined a compact subset S_{n−1} ⊆ X. An application of Lemma 2.1 of [19], with radii r_{n} + \frac{2r_{n−1}}{D} > r_{n} and weight function f_{n}, yields a compact subset S_{n} ⊆ S_{n−1} satisfying

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

Hence for all n ∈ ℕ we have,

∫_{S_{n}} wdμ ⩾ ∫_{X} f_{1}dμ.

Consider the compact subset S = ⋂_{n=1}^{∞} S_{n}. By the dominated convergence theorem,

∫_{S} wdμ ⩾ ∫_{X} f_{1}dμ.  (57)

In [19, Lem. 2.2] it is shown that S embeds with distortion D into an ultrametric space.

Assume now that the radii 1 = r_{0} ⩾ r_{1} ⩾ r_{2} ⩾ ⋯ > 0 are random variables satisfying lim_{n→∞} r_{n} = 0 and for every real number r > 0

Pr [r_{n} < r ⩽ r_{n} + \frac{2r_{n−1}}{D} ] ⩽ ε.  (58)

For the existence of such random variables, as well as the optimality for this purpose of the choice of D in (52), see [19, Thm. 1.5]. Specializing to the case of a finite metric measure space (X, d, μ) of diameter at most 2, apply (57) when w(x) = w_{1}(x)/μ({x}) and w_{2}(x) = μ({x}), and the radii are the random radii chosen above. By taking expectation of the resulting (random) inequality and using Jensen’s inequality we arrive at the following estimate.

𝔼 [∑_{x∈S} w_{1}(x)] ⩾^{(56)∧(57)} ∑_{x∈X} w_{1}(x) exp (𝔼 [∑_{n=1}^{∞} log (\frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))})]) . (59)

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., μ({x}) = μ(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) = ∞). Then we have the following straightforward identity (see equation (15) in [19]), which holds for every x ∈ X.

𝔼 [∑_{n=1}^{∞} log (\frac{μ(B(x, r_{m}))}{μ (B (x, r_{m} + \frac{2r_{m−1}}{D} ))})]

= − ∑_{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)))}) . (60)

Hence,

𝔼 [∑_{x∈S} w_{1}(x)] ⩾^{(58)∧(59)∧(60)} ∑_{x∈X} w_{1}(x) exp (−ε ∑_{j=2}^{k(x)} log (\frac{μ (B(x, t_{j}(x)))}{μ (B(x, t_{j−1}(x)))}))

= ∑_{x∈X} w_{1}(x) (\frac{μ(\{x\})}{μ(X)})^{ε} = \frac{∑_{x∈X} w_{1}(x)w_{2}(x)^{ε}}{(∑_{y∈X} w_{2}(y))^{ε}} .

We have shown that the required estimate (53) holds in expectation for our random subset S ⊆ X, completing the proof of Theorem 6.2. □

Definition 6.4. As in [19], given D ∈ (2, ∞) we let θ(D) ∈ (0, 1) denote the unique solution of the equation

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

By Remark 6.3 we then know that for every D > 2, every finite metric space (X, d) and every w : X → (0, ∞), there exists S ⊆ X that embeds with distortion D into an ultrametric space and satisfies,

∑_{x∈S} w(x)^{θ(D)} ⩾ (∑_{x∈X} w(x))^{θ(D)} .  (62)

It is elementary to check that

∀D ∈ (2, ∞), θ(D) ⩾ 1 − \frac{2e}{D},  (63)

and

∀δ ∈ (0, 1/2), θ(2 + δ) ⩾ \frac{cδ}{log(1/δ)},  (64)

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

The following very simple lemma exploits the fact that the class of ultrametrics is closed under truncation. This fact will be a useful normalization in the ensuing arguments.

Lemma 6.5. Let (X, d) be a bounded metric space that embeds with distortion D into an ultrametric space. Then there exists an ultrametric ρ on X satisfying

• d(x, y) ⩽ ρ(x, y) ⩽ Dd(x, y) for all x, y ∈ X,

• diam_{d}(X) = diam_{ρ}(X).

Proof. We are assuming that there exist A, B > 0 and an ultrametric ρ_{0} on X that satisfies Ad(x, y) ⩽ ρ_{0}(x, y) ⩽ Bd(x, y) for all x, y ∈ X, where B/A ⩽ D. We can therefore define ρ = min{ρ_{0}/A, diam_{d}(X)}. □

Lemma 6.6. Fix D ∈ (2, ∞) and β ∈ (0, ∞). Let (X, d) be a finite metric space. Suppose that F : T → 2^{X} is a fragmentation map which is β-separated. Suppose also that there is a weight function w : T → (0, ∞) which is subadditive, i.e., that for every non-leaf vertex u ∈ T ∖ L(T),

∑_{v∈p_{T}^{−1}(u)} w(v) ⩾ w(u),  (65)

Then there exists a substree T′ of T with the same root such that the restricted fragmentation map G = F|_{T′} satisfies the following properties.

• (∂G_{r(T′)}, d) embeds into an ultrametric space with distortion D (1 + \frac{2}{β} ).

• Every non-leaf vertex u ∈ T′ ∖ L(T′) satisfies

∑_{v∈p_{T′}^{−1}(u)} w(v)^{θ(D)} ⩾ w(u)^{θ(D)}.  (66)

Proof. We use the “metric composition technique” of [2]. For every vertex u ∈ T ∖ L(T) let C_{u} = p_{T}^{−1}(u) be the set of children of u in T. Let \overline{d}_{u} be a metric defined on C_{u} as follows

\overline{d}_{u}(x, y) = \{ \begin{matrix}diam_{d} ((∂F_{x}) ∪ (∂F_{y})) & if x ≠ y, \\ 0 & if x = y. \end{matrix}  (67)

The validity of the triangle inequality for \overline{d}_{u} is immediate to verify. By the definition of θ(D) there exists a subset S_{u} ⊆ C_{u} such that

∑_{x∈S_{u}^{1}} w(x)^{θ(D)} ⩾^{(62)} ( ∑_{x∈C_{u}} w(x))^{θ(D)} ⩾^{(65)} w(u)^{θ(D)}.  (68)

and (S_{u}, \overline{d}_{u}) embeds with distortion D into an ultrametric space. By Lemma 6.5 there exists an ultrametric ρ_{u} on S_{u} such that every x, y ∈ S_{u} satisfy

\overline{d}_{u}(x, y) ⩽ ρ_{u}(x, y) ⩽ min \{diam_{\overline{d}_{u}}(S_{u}), D\overline{d}_{u}(x, y)\}

⩽^{(67)} min \{diam_{d} ( ⋃_{x∈S_{u}} ∂F_{x}) , D\overline{d}_{u}(x, y)\} . (69)

The subtree T′ ⊆ T is now defined inductively in a top-down fashion as follows: declare r(T) ∈ T′ and if u ∈ T is a non-leaf vertex that was already declared to be in T′, add the vertices in S_{u} to T′ as well. Inequality (66) follows from (68). It remains to prove that (∂G_{r(T′)}, d) embeds into an ultrametric space with distortion D (1 + 2/β). To this end fix p, q ∈ ∂G_{r(T′)} and choose the corresponding a, b ∈ L(T′) such that G_{a} = {p} and G_{b} = {q}. Let u = lca_{T′}(a, b) = lca_{T} (a, b) and choose x, y ∈ S_{u} that are weak ancestors of a and b, respectively. Define ρ(p, q) = ρ_{u}(x, y). Now,

d(p, q) = d(G_{a}, G_{b}) ⩽ diam_{d} ((∂F_{x}) ∪ (∂F_{y})) =^{(67)} \overline{d}_{u}(x, y) ⩽^{(69)} ρ_{u}(x, y) = ρ(p, q).

The corresponding lower bound on d(p, q) is proved as follows, using the assumption that the fragmentation tree F is β-separated.

\frac{ρ(p, q)}{D} ⩽^{(69)} \overline{d}_{u}(x, y) ⩽^{(67)} diam_{d} (∂F_{x}) + diam_{d} (∂F_{y}) + d (∂F_{x}, ∂F_{y}) ⩽^{(10)} (1 + \frac{2}{β} ) d(p, q).

We now argue that ρ is an ultrametric on ∂G_{r(T′)}. This is where we will use the truncation in (69), i.e., that for all u ∈ T ∖ L(T) we have diam_{ρ_{u}}(S_{u}) ⩽ diam_{d} (⋃_{x∈S_{u}} ∂F_{x}) . Take p_{1}, p_{2}, p_{3} ∈ ∂G_{r(T′)} and choose the corresponding a_{1}, a_{2}, a_{3} ∈ L(T′) such that G_{a_{i}} = {p_{i}} for i ∈ {1, 2, 3}. By relabeling the points if necessary, we may assume that u = lca_{T} (a_{1}, a_{2}) is a weak descendant of v = lca_{T} (a_{2}, a_{3}). If u = v take x_{1}, x_{2}, x_{3} ∈ S_{u} that are weak ancestors of a_{1}, a_{2}, a_{3}, respectively. Since ρ_{u} is an ultrametric, it follows that

ρ(p_{1}, p_{2}) = ρ_{u}(x_{1}, x_{2}) ⩽ max {ρ_{u}(x_{1}, x_{3}), ρ_{u}(x_{3}, x_{2})} = max {ρ_{u}(p_{1}, p_{3}), ρ_{u}(p_{3}, p_{2})} .

If, on the other hand, u is a proper descendant of v then choose x_{1}, x_{2} ∈ S_{u} that are weak ancestors of a_{1}, a_{2} (respectively), and choose s, t ∈ S_{v} that are weak ancestors of u, a_{3} (respectively). Then,

ρ(p_{1}, p_{2}) = ρ_{u}(x, y) ⩽^{(69)} diam_{d} ( ⋃_{w∈S_{u}} ∂F_{w}) ⩽ diam_{d}(∂F_{s})

⩽ diam_{d} ((∂F_{s}) ∪ (∂F_{t})) =^{(67)} \overline{d}_{v}(s, t) ⩽^{(69)} ρ_{v}(s, t) = ρ(p_{1}, p_{3}) = ρ(p_{2}, p_{3}).

This establishes the ultratriangle inequality for ρ, completing the proof of Lemma 6.6. □

Lemma 6.7. Fix D ∈ (2, ∞), an integer k ⩾ 2, and τ ∈ (0, \frac{D−2}{3D+2}). Let (X, d, μ) be a finite metric measure space of diameter 1. Then there exists a fragmentation map G : T → 2^{X} with the following properties.

• Every leaf ℓ ∈ L(T) has no siblings, and furthermore G_{p_{T} (ℓ)} = G_{ℓ}.

• G is \frac{1−3τ}{2τ} -separated and (\frac{2}{1−3τ} τ^{−4k^{2}}, τ^{−4k^{2}})-lacunary.

• (∂G_{r(T)}, d) embeds into an ultrametric space with distortion D.

• Every cut-set G ⊆ T (recall Definition 2.1) satisfies

∑_{v∈G} μ (p_{T} (v))^{(1− \frac{1}{k})^{2}θ(\frac{1−3τ}{1+τ} D)} ⩾ μ(X)^{(1− \frac{1}{k})^{2}θ(\frac{1−3τ}{1+τ} D)},  (70)

where p_{T} (v) is the parent of v in T if v is not the root, and the root if v is the root.

Proof. Denote h = 2k^{2} and fix m ∈ ℕ satisfying

min_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} d(x, y) > τ^{(m−2)h+1}.  (71)

Apply Corollary 6.1 with parameters τ, m, h, k as above, obtaining a fragmentation tree F : T^{1} → 2^{X} with corresponding subsets S, R ⊆ T^{1}. Let T^{2} be the tree induced by T^{1} on S, i.e., join u, v ∈ S by an edge of T^{2} if u is an ancestor of v in T^{1} and any w ∈ S that is an ancestor of v in T^{1} is a weak ancestor of u. This is the same as the requirement v ∈ D_{T^{1}}(u, S). Let S : T^{2} → 2^{X} be the fragmentation map obtained by restricting F to S. To check that S is indeed a fragmentation map we need to verify that if u ∈ L(T^{2}) then F_{u} is a singleton. To see this let v = p_{T^{2}}(u) be the parent in T^{2} of u. Since all the leaves of T are at depth mh, we have depth_{T^{1}}(v) ⩾ (m − 2)h + 1. Using (47) we deduce that diam(F_{u}) ⩽ diam(F_{v}) ⩽ τ^{(m−2)h+1}, implying that S_{u} and S_{v} are both singletons due to (71).

Since by Corollary 6.1 we know that the vertices in S are \frac{1−3τ}{2τ} -separated in the fragmentation map F, it follows that the fragmentation map S is \frac{1−3τ}{2τ} -separated. Corollary 6.1 also ensures that F is (\frac{2}{1−3τ} τ^{−2h}, τ^{−1})-lacunary. This implies that S is (\frac{2}{1−3τ} τ^{−2h}, τ^{−2h})-lacunary. Indeed, due to Corollary 6.1 we know that if u ∈ S and v ∈ D_{T^{1}}(u, S) is a child of u in T^{2} then depth_{T^{1}}(u) ⩽ depth_{T^{1}}(u) + 2h − 1. This implies that if q, u ∈ S are such that u is a weak descendant of q in T^{2} then depth_{T^{1}}(u) − depth_{T^{1}}(q) ⩽ 2h (depth_{T^{2}}(u) − depth_{T^{2}}(q)). Hence, if v, w ∈ D_{T^{1}}(u, S) are distinct children of u in T^{2}, choose distinct x, y ∈ T^{1} that are children of u in T^{1} and weak ancestors of v, w (respectively), and use the fact that F is (\frac{2}{1−3τ} τ^{−2h}, τ^{−1})-lacunary to deduce that

diam_{d}(S_{q}) = diam_{d}(F_{q}) ⩽ \frac{2τ^{−2h}}{1 − 3τ} · τ^{−(depth_{T^{1}}(u)−depth_{T^{1}}(q))}d (∂F_{x}, ∂F_{y})

⩽ \frac{2τ^{−2h}}{1 − 3τ} · τ^{−2h(depth_{T^{2}}(u)−depth_{T^{2}}(q))}d (∂S_{x}, ∂S_{y}) .

Define w_{R} : R → (0, ∞) by top-down induction as follows. Set

w_{R}(r) = μ(X)^{(1− \frac{1}{k})^{2}},  (72)

where r is the root of T^{1}. If u ∈ R is not a leaf and v ∈ D_{T^{1}}(u, R) then define

w_{R}(v) = \frac{w_{R}(u)}{∑_{z∈D_{T^{1}}(u,R)} μ(F_{z})^{(1− \frac{1}{k})^{2}}} · μ(F_{v})^{(1− \frac{1}{k})^{2}}.  (73)

Thus for every non-leaf u ∈ R we have

w_{R}(u) = ∑_{v∈D_{T^{1}}(u,R)} w_{R}(v).  (74)

Moreover, it follows from the recursive definition (73) combined with (48) that

∀ u ∈ R, w_{R}(u) ⩽ μ(F_{u})^{(1− \frac{1}{k})^{2}}.  (75)

Recalling the notation D_{T}^{∗} (x, A) as given in (8), by summing (74) we see that for all u ∈ S ∖ L(T^{2}) we have

∑_{x∈D_{T^{1}}^{∗}(u,R)} ∑_{y∈D_{T^{1}}(x,R)} w_{R}(y) = ∑_{x∈D_{T^{1}}^{∗}(u,R)} w_{R}(x).  (76)

Notice that

⋃_{x∈D_{T^{1}}^{∗}(u,R)} D_{T^{1}}(x, R) = ⋃_{v∈D_{T^{1}}(u,S)} D_{T^{1}}^{∗}(v, R),  (77)

where the unions on both sides of (77) are disjoint. Hence,

∑_{x∈D_{T^{1}}^{∗}(u,R)} w_{R}(x) =^{(76)∧(77)} ∑_{v∈D_{T^{1}}(u,S)} ∑_{z∈D_{T^{1}}^{∗}(v,R)} w_{R}(z).  (78)

Define w_{S} : S → (0, ∞) by

w_{S}(u) = ∑_{z∈D_{T^{1}}^{∗}(u,R)} w_{R}(z).  (79)

Then for all u ∈ S ∖ L(T^{2}) we have

∑_{v∈p_{T^{2}}^{−1}(u)} w_{S}(v) = ∑_{v∈D_{T^{1}}(u,S)} w_{S}(v) =^{(78)∧(79)} ∑_{x∈D_{T^{1}}^{∗}(u,R)} w_{R}(x) =^{(79)} w_{S}(u).

This establishes condition (65) of Lemma 6.6 for the weighting w_{S} of T^{2}. Before applying Lemma 6.6 we record one more useful fact about w_{S}. Recall that for u ∈ S the vertex p_{T^{2}}(u) is r if u = r, and otherwise it is the first proper ancestor of u in T^{1} which is in S. Take u′ ∈ D_{T^{1}}^{∗}(p_{T^{2}}(u), R) which is a weak ancestor of u. Then F_{p_{T^{2}}(u)} ⊇ F_{u′}, and therefore

μ (F_{p_{T^{2}}(u)})^{(1− \frac{1}{k})^{2}} ⩾ μ (F_{u′})^{(1− \frac{1}{k})^{2}} ⩾^{(75)} w_{R}(u′)

=^{(74)} ∑_{x∈D_{T^{1}}(u′,R)} w_{R}(x) = ∑_{x∈D_{T^{1}}^{∗}(u,R)} w_{R}(x) =^{(79)} w_{S}(u). (80)

Apply Lemma 6.6 to S : T^{2} → 2^{X} and w_{S} : T^{2} → (0, ∞), with β = (1 − 3τ)/(2τ) and the parameter D of Lemma 6.6 replaced by D/(1 + 2/β) = D(1 − 3τ)/(1 + τ). Note that our assumption τ < (D −2)/(3D +2) guarantees that this new value of D is bigger than 2, so we are indeed allowed to use Lemma 6.6. We therefore obtain a subtree T ⊆ T^{2} with the same root, such that the restricted fragmentation map G = S|_{T} satisfies the following properties.

• (∂G_{r(T)}, d) embeds into an ultrametric space with distortion D.

• Every non-leaf vertex u ∈ T ∖ L(T) satisfies

∑_{v∈p_{T}^{−1}(u)} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} ⩾^{(66)} w_{S}(u)^{θ(\frac{1−3τ}{1+τ} D)}.  (81)

Let G ⊆ T be a cut-set of T. Define G_{0} to be a subset of G which is still a cut-set and is minimal with respect to inclusion. Assume inductively that we defined a cut-set G_{i} of T which is minimal with respect to inclusion. Let v ∈ G_{i} be such that depth_{T} (v) is maximal. Let u = p_{T} (v). By the maximality of depth_{T} (v), since G_{i} is a minimal cut-set of T we necessarily have p_{T}^{−1}(u) ⊆ G_{i}, i.e., all the siblings of v in T are also in G_{i}. Note that G′_{i} = (G_{i} ∪ {u}) ∖ p_{T}^{−1}(u) is also a cut-set of T, so let G_{i+1} be a subset of G′_{i} which is still a cut-set of T and is minimal with respect to inclusion. Then,

∑_{v∈G_{i}} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} = ∑_{v∈G_{i}∖p_{T}^{−1}(u)} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} + ∑_{v∈p_{T}^{−1}(u)} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)}

⩾^{(81)} ∑_{v∈G′_{i}} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} ⩾ ∑_{v∈G_{i+1}} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)}. (82)

After finitely many iterations of the above process we will arrive at G_{j} = {r}. By concatenating the inequalities (82) we see that

∑_{v∈G} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} ⩾ ∑_{v∈G_{0}} w_{S}(v)^{θ(\frac{1−3τ}{1+τ} D)} ⩾ w_{S}(r)^{θ(\frac{1−3τ}{1+τ} D)} =^{(72)∧(79)} μ(X)^{(1− \frac{1}{k})^{2}θ(\frac{1−3τ}{1+τ} D)}. (83)

The desired inequality (70) follows from (83) and (80). Since S is \frac{1−3τ}{2τ} -separated and

(\frac{2}{1−3τ} τ^{−4k^{2}}, τ^{−4k^{2}})-lacunary (recall that h = 2k^{2}), the same holds true for G since it is the restriction of S to the subtree of T^{2}. □

Lemma 6.8. Fix K, γ ∈ (0, ∞) and θ ∈ (0, 1). Let (X, d, μ) be a finite metric measure space. Assume that there exists a (K, γ)-lacunary fragmentation map G : T → 2^{X} such that every leaf ℓ ∈ L(T) has no siblings, and furthermore G_{p(ℓ)} = G_{ℓ}. Suppose also that for any cut-set G of T we have

∑_{v∈G} μ(G_{p(v)})^{θ} ⩾ μ(X)^{θ},

where as usual, if v ∈ T is the root then we set p(v) = v. Then for any {x_{i}}_{i∈I} ⊆ X and {r_{i}}_{i∈I} ⊆ [0, ∞) such that the d-balls {B_{d}(x_{i}, r_{i})}_{i∈I} cover ∂G_{r(T)}, we have

∑_{i∈I} μ (B_{d} (x_{i}, (1 + 2K^{2}γ) r_{i}))^{θ} ⩾ μ(X)^{θ}.  (84)

Proof. Without loss of generality assume that ∂G_{r(T)} ∩ B_{d}(x_{i}, r_{i}) ≠ ∅ for all i ∈ I. Let ρ be the ultrametric induced by G on ∂G_{r(T)}, as constructed in the proof of Lemma 2.8. Thus for x, y ∈ ∂G_{r(T)} we have ρ(x, y) = diam_{d} (G_{lca(a,b)}), where a, b ∈ L(T) satisfy G_{a} = {x} and G_{b} = {y}. Note that this definition implies that

∀v ∈ T, diam_{ρ}(∂G_{v}) = diam_{d}(G_{v}).  (85)

By Lemma 2.8 we know that

∀x, y ∈ ∂G_{r(T)}, d(x, y) ⩽ ρ(x, y) ⩽ Kd(x, y).  (86)

For every i ∈ I choose y_{i} ∈ ∂G_{r(T)} satisfying

d(x_{i}, y_{i}) = min_{y∈∂G_{r(T)}} d(x_{i}, y) ⩽ r_{i}.  (87)

Then B_{d}(y_{i}, 2r_{i}) ⊇ B_{d}(x_{i}, r_{i}). Hence the balls {B_{d}(y_{i}, 2r_{i})}_{i∈I} also cover ∂G_{r(T)}. By (86) we have B_{ρ}(y_{i}, 2Kr_{i}) ⊇ B_{d}(y_{i}, 2r_{i}) ∩ ∂G_{r(T)}, so we also know that the ρ-balls {B_{ρ}(y_{i}, 2Kr_{i})}_{i∈I} cover ∂G_{r(T)}.

For i ∈ I choose v_{i} ∈ T as follows. If B_{ρ}(y_{i}, 2Kr_{i}) is a singleton then v_{i} is defined to be the leaf of T such that G_{v_{i}} = {y_{i}}. Otherwise pick v_{i} to be the highest ancestor of y_{i} in T such that

diam_{ρ}(∂G_{v_{i}}) ⩽ 2Kr_{i}  (88)

and v_{i} has at least two children. Then B_{ρ}(y_{i}, 2Kr_{i}) = ∂G_{v_{i}}. Hence, since {B_{ρ}(y_{i}, 2Kr_{i})}_{i∈I} cover ∂G_{r(T)}, we have ⋃_{i∈I} L (T_{v_{i}}) = L(T). If we set G = {v_{i}}_{i∈I} then we conclude that G is a cut-set of T. Our assumption therefore implies that

∑_{i∈I} μ (G_{p(v_{i})})^{θ} ⩾ μ(X)^{θ}.  (89)

When v_{i} has at least two children we deduce from the fact that G is (K, γ)-lacunary that

diam_{d} (G_{p(v_{i})}) ⩽ Kγ diam_{d}(∂G_{v_{i}}).  (90)

(Recall Definition 2.6 with q = p(v_{i}) and u = v_{i}.) When v_{i} is a leaf our assumptions imply that G_{v_{i}} and G_{p(v_{i})} are both singletons, and therefore diam_{d} (G_{p(v_{i})}) = diam_{d} (∂G_{v_{i}}) = 0, so (90) holds in this case as well. Hence for every i ∈ I and z ∈ G_{p(v_{i})} we have

d(z, x_{i}) ⩽ d(x_{i}, y_{i}) + d(z, y_{i}) ⩽^{(87)} r_{i} + d(z, y_{i}) ⩽^{(♣)} r_{i} + diam_{d} (G_{p(v_{i})})

⩽^{(90)} r_{i} + Kγ diam_{d}(∂G_{v_{i}}) ⩽^{(86)} r_{i} + Kγ diam_{ρ}(∂G_{v_{i}}) ⩽^{(88)} r_{i} + 2K^{2}γr_{i}, (91)

where (♣) follows from the fact that y_{i} ∈ ∂G_{v_{i}} ⊆ G_{v_{i}} ⊆ G_{p(v_{i})}. The validity of (91) for all z ∈ G_{p(v_{i})} is the same as the inclusion G_{p(v_{i})} ⊆ B_{d} (x_{i}, (1 + 2K^{2}γ) r_{i}). Now (84) follows from (89). □

Proof of Theorem 1.5. By Lemma 3.1 we may assume that (X, d, μ) is a finite metric measure space. Fix an integer \frac{10}{ε} ⩽ k ⩽ \frac{11}{ε} and set τ = \frac{1}{20}. Then (1 − ε) (1 − \frac{1}{k})^{−2} ∈ (0, 1), so we can define

D = \frac{1 + τ}{1 − 3τ} · θ^{−1} (\frac{1 − ε}{(1 − \frac{1}{k})^{2}} ) = \frac{11}{7}θ^{−1} (\frac{1 − ε}{(1 − \frac{1}{k})^{2}} ) .  (92)

Equivalently,

(1 − \frac{1}{k})^{2} θ (\frac{1 − 3τ}{1 + τ} D) = 1 − ε.

Due to (62), for every s ∈ (0, 1) we have θ^{−1}(s) = 2(1 − s)^{−1}s^{−s/(1−s)} > 2. Hence it follows from (92) that D > 2(1 + τ)/(1 − 3τ), or equivalently τ < (D − 2)/(3D + 2). By (63) we have θ^{−1}(s) ⩽ 2e/(1 − s). Therefore,

D ⩽ \frac{11}{7} · \frac{2e}{1 − \frac{1−ε}{(1−ε/10)^{2}}} = \frac{42e(10 − ε)^{2}}{17ε(8 + ε)} ⩽ \frac{9}{ε},  (93)

where the last inequality in (93) is elementary. The required conclusion now follows from Lemma 6.7 and Lemma 6.8. Note that we get the bound c_{ε} = τ^{−O(k^{2})} = e^{O(1/ε^{2})}. □

Proof of Theorem 1.9. Again, using Lemma 3.1 we may assume that (X, d, μ) is a finite metric measure space. Apply Lemma 6.7 with D = 2 + δ, k = 2 and τ = δ/9. Denote the exponent in (70) by s = \frac{1}{2}θ ((9 − 3δ)(2 + δ)/(9 + δ)). By (63) there is a universal constant c ∈ (0, ∞) such that s ⩾ t, where t = cδ/ log(1/δ). Let G : T → 2^{X} be fragmentation tree obtained using Lemma 6.7, and let G be a cut-set in T. Then by (70) we have,

(∑_{v∈G} μ (p_{T} (v))^{t})^{1/t} ⩾ (∑_{v∈G} μ (p_{T} (v))^{s})^{1/s} ⩾ μ(X).

We can therefore apply Lemma 6.8 with θ = t, K = 2τ^{−16}/(1 − 3τ) and γ = τ^{−16}, obtaining Theorem 1.9. Note that this shows that c′_{δ} can be taken to be a constant multiple of δ^{−16}. □

7. Impossibility results

The purpose of this section is to prove the second part of Theorem 1.4 and Theorem 1.8. In both cases the goal is to construct a metric space having the property that all its “almost Euclidean” subsets have small Hausdorff dimension. We will do so by gluing together the finite examples from [2]: in the high distortion regime corresponding to Theorem 1.4 these building blocks are expander graphs, and in the low distortion regime corresponding to Theorem 1.8 these building blocks arise from dense random graphs. The gluing procedure, which is an infinitary variant of the “metric composition” method from [2], starts with a sequence of finite metric spaces and joins them in a tree-like fashion. The details of the construction are contained in Section 7.1 below, and the specializations to prove Theorem 1.4 and Theorem 1.8 are described in Section 7.2 and Section 7.3, respectively.

7.1. Trees of metric spaces. Fix {n_{k}}_{k=0}^{∞} ⊆ ℕ with n_{0} = 1 and n_{k} > 1 for k ⩾ 1. Fix also {δ_{k}}_{k=1}^{∞} ⊆ (0, ∞). Assume that for each k ∈ ℕ we are given a metric d_{k} on {1, …, n_{k}} with

diam_{d_{k}} ({1, …, n_{k}}) = 1 and min_{i,j∈{1,...,n_{k}}} d_{k}(i, j) = δ_{k}.  (94)

For distinct x = (x_{k})_{k=1}^{∞}, y = (y_{k})_{k=1}^{∞} ∈ ∏_{k=1}^{∞}{1, …, n_{k}} let k(x, y) be the smallest k ∈ ℕ such that x_{k} ≠ y_{k}. For α ∈ (0, ∞) define

ρ_{α}(x, y) = \frac{d_{k(x,y)} (x_{k(x,y)}, y_{k(x,y)})}{∏_{i=0}^{k(x,y)−1} n_{i}^{1/α}}.  (95)

Also, set ρ_{α}(x, x) = ρ_{α}(y, y) = 0.

Remark 7.1. One can visualize the above construction as follows. Let T be the infinite rooted tree such for i ⩾ 0 each vertex at depth i in T has exactly n_{i+1} children. Then ∏_{k=1}^{∞}{1, …, n_{k}} can be identified with the set of all infinite branches of T. With this identification, the distance ρ_{α} has the following meaning: given two infinite branches in T, find the vertex v ∈ T at which they split (i.e., their deepest common vertex). Say that the depth of v is i − 1. The metric d_{i} induces a metric space structure on the n_{i} children of v, and the distance between the two given branches is a multiple of the distance between the two children of v that belong to these branches.

Lemma 7.2. (∏_{k=1}^{∞}{1, …, n_{k}}, ρ_{α}) is a compact metric space provided that

∀k ∈ ℕ, δ_{k} > \frac{1}{n_{k}^{1/α}} .  (96)

Proof. Take x, y, z ∈ ∏_{k=1}^{∞}{1, …, n_{k}}. If k(x, y) = k(y, z) = k(x, z) = k then because d_{k} satisfies the triangle inequality, ρ_{α}(x, z) ⩽ ρ_{α}(x, y) + ρ_{α}(y, z). If k(x, y) > k(x, z) then necessarily k(x, z) = k(y, z) = k and x_{k} = y_{k}. Hence ρ_{α}(x, z) = ρ_{α}(x, y) ⩽ ρ_{α}(x, y)+ρ_{α}(y, z). The remaining case k(x, z) > k(x, y) is dealt with as follows.

ρ_{α}(x, z) = \frac{d_{k(x,z)} (x_{k(x,z)}, z_{k(x,z)})}{∏_{i=0}^{k(x,z)−1} n_{i}^{1/α}} ⩽^{(94)} \frac{1}{∏_{i=0}^{k(x,z)−1} n_{i}^{1/α}} ⩽^{(96)} \frac{δ_{k(x,y)}}{∏_{i=0}^{k(x,y)−1} n_{i}^{1/α}} ⩽^{(94)} ρ_{α}(x, y).

This proves the triangle inequality. Compactness follows from Tychonoff’s theorem since ρ_{α} induces the product topology on ∏_{k=1}^{∞}{1, …, n_{k}}. □

Lemma 7.3. Assume that in addition to (96) we have

lim_{k→∞} \frac{log(1/δ_{k})}{∑_{i=1}^{k−1} log n_{i}} = 0.  (97)

Then

dim_{H} (∏_{k=1}^{∞}{1, …, n_{k}}, ρ_{α}) = α.

Proof. Define Δ = dim_{H} (∏_{k=1}^{∞}{1, …, n_{k}}, ρ_{α}). The fact that Δ ⩽ α is simple. Indeed, for k ∈ ℕ consider the sets {B_{x}^{k}}_{x∈∏_{i=1}^{k}{1,...,n_{i}}} given by

B_{x}^{k} = (∏_{i=1}^{k}{x_{i}}) × ( ∏_{i=k+1}^{∞}{1, …, n_{i}}) .  (98)

Then diam_{ρ_{α}}(B_{x}^{k}) = ∏_{i=1}^{k} n_{i}^{−1/α} and {B_{x}^{k}}_{x∈∏_{i=1}^{k}{1,...,n_{i}}} cover ∏_{i=1}^{∞}{1, …, n_{i}}. Hence for β > α the β-Hausdorff content of (∏_{i=1}^{∞}{1, …, n_{i}}, ρ_{α}) can be estimated as follows.

H_{∞}^{β} (∏_{i=1}^{∞}\{1, …, n_{i}\}, ρ_{α}) ⩽ inf_{k∈ℕ} ∑ ; x∈∏_{i=1}^{k}\{1,...,n_{i}\} \frac{1}{∏_{i=0}^{k} n_{i}^{β/α}} = inf_{k∈ℕ} \frac{1}{∏_{i=0}^{k} n_{i}^{(β−α)/α}} = 0.

Thus Δ ⩽ α.

We now pass to the proof of Δ ⩾ α. We first prove the following preliminary statement. Assume that x^{1}, …, x^{m} ∈ ∏_{i=1}^{∞}{1, …, n_{i}} and k_{1}, …, k_{m} ∈ ℕ ∪ {0} are such that {B_{x^{j}}^{k_{j}}}_{j=1}^{m} cover ∏_{i=1}^{∞}{1, …, n_{i}}, where B_{x}^{k} is given in (98) and we use the convention B_{x}^{0} = ∏_{i=1}^{∞}{1, …, n_{i}}. We claim that this implies that

∑_{j=1}^{m} \frac{1}{∏_{i=0}^{k_{j}} n_{i}} ⩾ 1.  (99)

The proof is by induction on m. If m = 1 then k_{1} = 0 and (99) follows. Assume that m ⩾ 2, no subset of {B_{x^{j}}^{k_{j}}}_{j=1}^{m} covers ∏_{i=1}^{∞}{1, …, n_{i}}, and that k_{1} ⩽ k_{2} ⩽ ⋯ ⩽ k_{m}. For every y ∈ {1, …, n_{k_{m}}} let x^{k_{m}}(y) ∈ ∏_{i=1}^{∞}{1, …, n_{i}} have y in the k_{m}’th coordinate, and coincide with x^{k_{m}} in all other coordinates. The sets {B_{x^{km}(y)}^{k_{m}}}_{y∈{1,...,n_{km}}} are pair-

wise disjoint, and are either contained in or disjoint from B_{x^{j}}^{k_{j}} for each j ∈ {1, …, m}. Hence, by the minimality of the cover {B_{x^{j}}^{k_{j}}}_{j=1}^{m} we have k_{m} = k_{m−1} = ⋯ = k_{m−n_{km}+1} and {B_{x^{j}}^{k_{j}}}_{j=m−n_{km}+1}^{k_{m}} = {B_{x^{km}(y)}^{k_{m}}}_{y∈{1,...,n_{km}}}. This implies that

∑_{j=1}^{m} \frac{1}{∏_{i=0}^{k_{j}} n_{i}} = ∑_{j=1}^{m−n_{km}} \frac{1}{∏_{i=0}^{k_{j}} n_{i}} + ∑_{y∈\{1,...,n_{km}\}} \frac{1}{∏_{i=0}^{k_{m}} n_{i}} = ∑_{j=1}^{m−n_{km}} \frac{1}{∏_{i=0}^{k_{j}} n_{i}} + \frac{1}{∏_{i=0}^{k_{m}−1} n_{i}} .

The induction hypothesis applied to {B_{x^{j}}^{k_{j}}}_{j=1}^{m−n_{km}} ∪ {B_{x^{m}}^{k_{m}−1}} concludes the proof of (99). Fix β ∈ (0, α). Due to (97) there exists C ∈ (0, ∞) such that for all k ∈ ℕ,

\frac{1}{δ_{k}} ⩽ C ∏_{i=1}^{k−1} n_{i}^{(α−β)/α^{2}}.  (100)

Let {B_{ρ_{α}}(x^{j}, r_{j})}_{j∈J} be a family of balls that covers ∏_{i=1}^{∞}{1, …, n_{i}}. We will show that

∑_{j∈J} r_{j}^{β} ⩾ \frac{1}{C^{α}} .  (101)

This would mean that H_{∞}^{β} (∏_{i=1}^{∞}{1, …, n_{i}}, ρ_{α}) > 0 for all β ∈ (0, α), proving that Δ ⩾ α. By compactness of (∏_{i=1}^{∞}{1, …, n_{i}}, ρ_{α}) it suffices to prove (101) when J is finite. For every j ∈ J choose k_{j} ∈ ℕ such that ∏_{i=0}^{k_{j}} n_{i}^{−1/α} < r_{j} ⩽ ∏_{i=0}^{k_{j}−1} n_{i}^{−1/α}. Define

r_{j}^{∗} = \{ \begin{matrix}∏_{i=1}^{k_{j}−1} n_{i}^{−1/α} & if δ_{k_{j}} ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α} ⩽ r_{j} ⩽ ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α}, \\ ∏_{i=1}^{k_{j}} n_{i}^{−1/α} & if ∏_{i=1}^{k_{j}} n_{i}^{−1/α} < r_{j} < δ_{k_{j}} ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α}. \end{matrix}  (102)

If δ_{k_{j}} ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α} ⩽ r_{j} ⩽ ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α} then r_{j}^{∗} ⩾ r_{j}, hence B_{ρ_{α}}(x^{j}, r_{j}) ⊆ B_{ρ_{α}}(x^{j}, r_{j}^{∗}) = B_{x^{j}}^{k_{j}−1}.

Also, observe that ρ_{α} does not take values in the interval (∏_{i=1}^{k_{j}} n_{i}^{−1/α}, δ_{k_{j}} ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α}).

This implies that B_{ρ_{α}}(x^{j}, r_{j}) = B_{ρ_{α}}(x^{j}, r_{j}^{∗}) = B_{x^{j}}^{k_{j}} when ∏_{i=1}^{k_{j}} n_{i}^{−1/α} < r_{j} < δ_{k_{j}} ∏_{i=1}^{k_{j}−1} n_{i}^{−1/α}. We deduce that the balls B_{ρ_{α}}(x^{j}, r_{j}^{∗}) cover ∏_{i=1}^{∞}{1, …, n_{i}}, and they are all sets of the form B_{x}^{k}. It therefore follows from (99) that

1 ⩽ ∑_{j∈J} (r_{j}^{∗})^{α} ⩽^{(102)} ∑_{j∈J} (\frac{r_{j}}{δ_{k_{j}}} )^{α} ⩽^{(100)} C^{α} ∑_{j∈J} r_{j}^{α} ∏_{i=0}^{k_{j}−1} n_{i}^{(α−β)/α} ⩽ C^{α} ∑_{j∈J} r_{j}^{β},  (103)

where in the last inequality of (103) we used the fact that r_{j} ⩽ ∏_{i=0}^{k_{j}−1} n_{i}^{−1/α}. □

Remark 7.4. A less direct way to prove the bound Δ ⩾ α in Lemma 7.3 is to define μ(B_{x}^{k}) = ∏_{i=0}^{k} n_{i}^{−1} and to argue that the Carathéodory extension theorem applies here and yields an extension of μ to a Borel measure on ∏_{i=1}^{∞}{1, …, n_{i}}. One can then show analogously to (103) that this measure is a β-Frostman measure for (∏_{i=1}^{∞}{1, …, n_{i}}, ρ_{α}).

In what follows we say that a property 𝒫 of metric spaces is a metric property if whenever (X, d_{X}) ∈ P and (Y, d_{Y}) is isometric to (X, d_{X}) then also (Y, d_{Y}) ∈ 𝒫. We say that 𝒫 is hereditary if whenever (X, d) ∈ 𝒫 and Y ⊆ X then also (Y, d) ∈ 𝒫. Finally, we say that 𝒫 is dilation-invariant if whenever (X, d) ∈ 𝒫 and λ ∈ (0, ∞) also (X, λd) ∈ 𝒫.

Theorem 7.5. Fix α > 0. Fix also {n_{k}}_{k=0}^{∞} ⊆ ℕ with n_{0} = 1 and n_{k} > 1 for k ⩾ 1, a sequence {δ_{k}}_{k=1}^{∞} ⊆ (0, ∞), and for each k ∈ ℕ a metric d_{k} on {1, …, n_{k}}. Assume that (94),

(96) and (97) hold true. Then there exists a metric space (Y, ρ) with dim_{H}(Y, ρ) = α that satisfies the following property. Let {𝒫_{k}}_{i=1}^{∞} is a non-decreasing (with respect to inclusion) sequence of hereditary dilation-invariant metric properties and for every k ∈ ℕ let m_{k} be the cardinality of the largest subset S of {1, …, n_{k}} such that (S, d_{k}) has the property 𝒫_{k}. Then every Z ⊆ Y that has the property ⋃_{k=1}^{∞} 𝒫_{k} satisfies

dim_{H}(Z, ρ) ⩽ lim sup_{k→∞} \frac{α log m_{k}}{log n_{k}} .

Proof. Take (Y, ρ) = (∏_{k=1}^{∞}{1, …, n_{k}}, ρ_{α}), where ρ_{α} is given in (95). By Lemma 7.3 and Lemma 7.2 we know that (Y, ρ) is a compact metric space of Hausdorff dimension α.

Assume that Z ⊆ Y and (Z, ρ) ∈ 𝒫_{K} for some K ∈ ℕ. Since {𝒫_{k}}_{i=1}^{∞} are non-decreasing properties, we know that (Z, ρ) ∈ 𝒫_{k} for all k ⩾ K. For every x ∈ Y and k ∈ ℕ denote

S_{x}^{k} = {j ∈ {1, …, n_{k}} : Z ∩ ((∏_{i=1}^{k−1}{x_{i}}) × {j} × ( ∏_{i=k+1}^{∞}{1, …, n_{i}})) ≠ ∅} .

If j ∈ S_{x}^{k} choose x^{k}(j) ∈ Z whose first k − 1 coordinates coincide with the corresponding coordinates of x, and whose k’th coordinate equals j. Then {x^{k}(j)}_{j∈S_{x}^{k}} is a subset of Z whose metric is isometric to a dilation of the metric d_{k} on S_{x}^{k}. Since 𝒫_{k} is a hereditary dilationinvariant metric property, it follows that S_{x}^{k} ∈ 𝒫_{k} for all k ⩾ K. Hence |S_{x}^{k}| ⩽ m_{k}. Let Z_{k} be the projection of the set Z onto the first k coordinates, i.e., the set of all x ∈ ∏_{i=1}^{k}{1, …, n_{i}} such that B_{x}^{k} ∩ Z ≠ ∅, where B_{x}^{k} is given in (98). Then it follows by induction that for every k ⩾ K we have |Z_{k}| ⩽ ∏_{i=0}^{K−1} n_{i} · ∏_{i=K}^{k} m_{i}. Denote γ = lim sup_{k→∞} \frac{α log m_{k}}{log n_{k}}. If β > γ then

there exists K′ ⩾ K such that for every k ⩾ K′ we have m_{k} ⩽ n_{k}^{(β+γ)/(2α)}. Since the sets {B_{x}^{k}}_{x∈Z_{k}} cover Z and have ρ-diameter ∏_{i=0}^{k} n_{i}^{−1/α},

H_{∞}^{β}(Z, ρ) ⩽ inf_{k⩾K′} ∑_{x∈Z_{k}} \frac{1}{∏_{i=0}^{k} n_{i}^{β/α}} ⩽ inf_{k⩾K′} \frac{∏_{i=0}^{K−1} n_{i} · ∏_{i=K}^{k} m_{i}}{∏_{i=0}^{k} n_{i}^{β/α}}

⩽ inf_{k⩾K′} \frac{∏_{i=0}^{K′−1} n_{i} · ∏_{i=K′}^{k} n_{i}^{(β+γ)/(2α)}}{∏_{i=0}^{k} n_{i}^{β/α}} ⩽ inf_{k⩾K′} \frac{∏_{i=0}^{K′−1} n_{i}}{∏_{i=K′}^{k} n_{i}^{(β−γ)/(2α)}} = 0.

Hence dim_{H}(Z, ρ) ⩽ γ. □

Corollary 7.6. Fix an integer n ⩾ 2. Let (X, d) be an n-point metric space, and assume that Ψ ∈ (0, ∞) satisfies

Ψ · min_{\begin{matrix}x,y∈X \\ x≠y \end{matrix}} d(x, y) > diam(X).

Then there exists a compact metric space (Y, ρ) with dim_{H}(Y, ρ) = log_{Ψ} n that has the following property. Fix m ∈ {1, …, n − 1} and assume that 𝒫 is a hereditary dilation-invariant metric property such that the largest subset of X having the property 𝒫 is of size m. Then dim_{H}(Z, ρ) ⩽ log_{Ψ} m for every Z ⊆ Y with property 𝒫.

Proof. By rescaling assume that diam(X) = 1. Now apply Theorem 7.5 with X_{i} = X, n_{i} = n, 𝒫_{i} = 𝒫 and α = log_{Ψ} n. □

7.2. Expander fractals. It is shown in [2] that there is c ∈ (0, ∞) such that for any n ∈ ℕ there exists an n-point metric space X_{n} such that for every ε ∈ (0, 1) all the subsets of X_{n} of cardinality greater than n^{1−ε} incur distortion greater than c/ε in any embedding into Hilbert space. In fact, the spaces X_{n} are the shortest-path metrics on expander graphs, implying that diam X_{n} ⩽ C log n for some C ∈ (0, ∞) and all n ∈ ℕ (see [8]). We will apply Corollary 7.6 to these spaces, thus obtaining compact metric spaces that can be called “expander fractals”. The property 𝒫 that will be used is “X embeds with distortion c/ε into Hilbert space”, which is clearly a hereditary dilation-invariant metric property.

Proof of the second part of Theorem 1.4. Let c, C, X_{n} be as above. Fix α > 0 and choose an integer n ⩾ 2 such that n^{1/α} > C log n. We may therefore use Corollary 7.6 with X = X_{n} and Ψ = n^{1/α}. The resulting compact metric space (Y, ρ) will then have Hausdorff dimension equal to α. For every ε ∈ (0, 1) let 𝒫_{ε} be the property “X embeds with distortion c/ε into Hilbert space”. Then all the subsets Z of Y that embed into Hilbert space with distortion c/ε satisfy dim_{H}(Z, ρ) ⩽ log_{Ψ} (n^{1−ε}) = (1 − ε)α = (1 − ε) dim_{H}(Y, ρ). □

7.3. G (n, 1/2) fractals. It is shown in [2] that there exists K ∈ (1, ∞) such that for any n ∈ ℕ there exists an n-point metric space W_{n} such that for every δ ∈ (0, 1) any subset of W_{n} of size larger than 2 log_{2} n + K (δ^{−2} log(2/δ))^{2} must incur distortion at least 2 − δ when embedded into Hilbert space. The space W_{n} comes from a random construction: consider a random graph G on n vertices, drawn from the Erdős-Reyni model G(n, 1/2) (thus every edge is present independently with probability 1/2). The space W_{n} is obtained from G by declaring two vertices that are joined by an edge to be at distance 1, and two distinct vertices that are not joined by an edge are declared to be at distance 2. Therefore the positive distances in W_{n} are either 1 or 2. This description of W_{n} is implicit in [2] but follows immediately from the proof of [2]; see [3] for an alternative proof of this fact (yielding a worse asymptotic dependence on δ that is immaterial for our purposes). We will apply Corollary 7.6 to {W_{n}}_{n=2}^{∞}, thus obtaining compact metric spaces that can be called “G(n, 1/2) fractals”.

Proof of Theorem 1.8. Let K and {W_{n}}_{n=2}^{∞} be as in the above discussion. Set X_{n} = W_{n+⌈3^{α}⌉}. Hence |X_{n}|^{1/α} > 2. Let 𝒫_{n} be the property “X embeds with distortion 2 − 1/ log log n into Hilbert space”. Then {P_{n}}_{n⩾20} is a non-decreasing sequence of hereditary dilation-invariant metric properties. Moreover, ⋃_{n⩾20} 𝒫_{n} is the property “X embeds into Hilbert space with distortion smaller than 2”. By the above discussion, letting m_{n} be the size of the largest subset of X_{n} that has the property 𝒫_{n}, we have m_{n} ⩽ 2 log_{2} n+O ((log log)^{2}(log log log n)^{2}). Hence lim sup_{n→∞} \frac{α log m_{n}}{log |X_{n}|} = 0. By Theorem 7.5 it follows there exists a compact metric space (Y, ρ) with Hausdorff dimension α such that all of its subsets with positive Hausdorff dimension do not have property ⋃_{n⩾20} 𝒫_{n}, namely any embeding of such a subset into Hilbert space must incur distortion at least 2. □

Acknowledgements. We are grateful to Terence Tao for sharing with us his initial attempts to solve Question 1.3.

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 phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

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

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

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

[6] D. Burago, Y. Burago, and S. Ivanov. A course in metric geometry, volume 33 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2001.

[7] L. Carleson. Selected problems on exceptional sets. Van Nostrand Mathematical Studies, No. 13. D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto, Ont.-London, 1967.

[8] F. R. K. Chung. Diameters and eigenvalues. J. Amer. Math. Soc., 2(2):187–196, 1989.

[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] A. Grothendieck. Sur certaines classes de suites dans les espaces de Banach et le théorème de Dvoretzky-Rogers. Bol. Soc. Mat. São Paulo, 8:81–110 (1956), 1953.

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

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

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

[14] M. Mendel and A. Naor. Nonlinear Dvoretzky theory. In preparation.

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

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

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

[18] P. Mörters and Y. Peres. Brownian motion. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. With an appendix by Oded Schramm and Wendelin Werner.

[19] A. Naor and T. Tao. Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem, 2010. Preprint available at http://arxiv.org/abs/1003.4013. To appear in Israel J. Math.

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

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

[22] M. Talagrand. The generic chaining. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes.

[23] 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