1. Ultrametrics

In these notes we shall always assume the axiom of choice.

An ultrametric (or non-Archimedean metric) is a special type of metric in which the summation in the usual triangle inequality d(x, z) ⩽ d(x, y) + d(y, z) is strengthened to a maximum:

Definition 1.1 (Ultrametric). Let X be a set. An ultrametric d : X × X → ℝ^{+} on X is a non-negative function on X × X obeying the following axioms:

• (Strict positivity) For x, y ∈ X, d(x, y) = 0 if and only if x = y.

• (Symmetry) For x, y ∈ X, d(x, y) = d(y, x).

• (Ultratriangle inequality) For x, y, z ∈ X, we have d(x, z) ⩽ max(d(x, y), d(y, z)).

intex Example 1.2. Let X be the unit interval [0, 1] with all terminating decimals removed (so that all points have unique decimal expansions), and let d(x, y) := 10^{−n+1}, where n is the first digit place at which x and y differ (thus for instance d(0.142, 0.172) = 0.1). Then d(x, y) is an ultrametric which dominates the usual Euclidean metric (thus d(x, y) ⩾ |x − y| for all x, y).

treeex Example 1.3. Let X be a rooted tree, and let r_{0} > r_{1} > r_{2} > … > 0 be a sequence of numbers. If we set d(x, y) := r_{n}, where n is the level of the join of x and y, then d is an ultrametric.

Closely related to the concept of a ultrametric space is a mesh of cubes.

Definition 1.4 (Mesh of cubes). Let X be a set. A mesh of cubes (Q_{r})_{r>0} is a collection Q_{r} of “cubes” for each “radius” r > 0 with the following axioms:

• (Partition) For each r > 0, we have the partition X = ⋃_{Q∈Q_{r}} Q. In other words, for each x ∈ X there is exactly one cube of radius r which contains x.

• (Nesting) If r′ ⩾ r and Q ∈ Q_{r}, Q′ ∈ Q_{r′}, are cubes with non-empty intersection, then Q ⊆ Q′.

• (Parent) If Q ∈ Q_{r}, r′ ⩾ r then there is a unique cube Q′ ∈ Q_{r′} of radius r′ such that Q ⊆ Q′.

• (Separation) If x ≠ x′ are points in X, then there exist disjoint cubes Q, Q′ of some radius r > 0 which contain x and x′ respectively.

• (Finiteness) If x, x′ are points in X, then there exists a cube Q which contains both x and x′.

Remark 1.5. There is some redundancy among the axioms; for instance, assuming the partition property, the nesting and parent properties are equivalent.

Example 1.6 (Dyadic cubes). In [0, +∞)^{d} and every integer k, let Q_{2^{k}} be the collection of cubes 2^{k}(j + [0, 1)^{d}) for j ∈ ℤ_{+}^{d}, and then set Q_{r} := Q_{2^{k}} for all 2^{k} ⩽ r < 2^{k+1}. Then (Q_{r})_{r>0} is a mesh of cubes. (If one extended this mesh to all of ℝ^{d} then one loses the finiteness property but all other axioms remain intact.)

The following equivalence is easily verified:

Proposition 1.7 (Equivalence of ultrametrics and meshes). If d is an ultrametric on X, then the closed balls

Q_{r} := \{\overline{B}(x, r) : x ∈ X\} = \{\{y ∈ X : d(x, y) ⩽ r\} : x ∈ X\}

form a mesh of cubes in X. Conversely, if (Q_{r})_{r>0} is a mesh of cubes in X, then the function

d(x, y) := inf{r > 0 : x, y ∈ Q for some Q ∈ Q_{r}}

is an ultrametric on X. These two correspondences between ultrametrics and meshes of cubes invert each other.

Example 1.8. The cubes associated to Example^{\underline{intex}} 1.2 are the 10-ary intervals [10^{−n}k, 10^{−n}(k+ 1)] for integers n ⩾ 0 and 0 ⩽ k < 10^{n}, removing the terminating decimals as usual.

Example 1.9. The cubes associated to Example ^{\underline{treeex}} 1.3 are the complete subtrees of X.

2. Metric nets

We now attempt to construct a mesh of cubes (or equivalently, an ultrametric) on an arbitrary metric space (X, d), which we now fix. As it turns out we will have to throw away a small set (cf. the terminating decimals in Example ^{\underline{intex}} 1.2) and work with a slightly smaller set X^{∘}.

The first step is to discretise the metric space at a fixed scale. For each integer k, we define the radius r_{k} := 100^{−k}.

ik Lemma 2.1 (Discretisation at scale r_{k}). Let k ∈ ℤ. Then there exists a map ϕ_{k} : X → X with the following properties.

(i) For any x ∈ X, we have d(ϕ_{k}(x), x) < r_{k}. In particular^{1}, d(x, ϕ_{k}(X)) < r_{k} for all x ∈ X.

(ii) If x, y ∈ X are such that d(ϕ_{k}(x), ϕ_{k}(y)) < r_{k}, then ϕ_{k}(x) = ϕ_{k}(y). (In other

words, the set ϕ_{k}(X) is discrete and r_{k}-separated.) (iii) If x, y ∈ X are such that d(x, ϕ_{k}(y)) < \frac{1}{2}r_{k}, then ϕ_{k}(x) = ϕ_{k}(y).

Proof. Let X_{k} be a maximal r_{k}-separated subset of X (which exists by Zorn’s lemma). Thus we have d(x_{k}, y_{k}) ⩾ r_{k} for any distinct x_{k}, y_{k} ∈ X_{k}, and for any x ∈ X there exists at least one x_{k} ∈ X_{k} such that d(x, x_{k}) < r_{k}. From the former property and the triangle inequality we also see that for any x ∈ X there is at most one x_{k} ∈ X_{k} such that d(x, x_{k}) < \frac{1}{2}r_{k}. We now define ϕ(x) to equal the unique x_{k} ∈ X_{k} with d(x, x_{k}) < \frac{1}{2}r_{k}, if such an x_{k} exists, or else define ϕ(x) to be an arbitrary x_{k} ∈ X_{k} with d(x, x_{k}) < r_{k} otherwise; such a function exists by the axiom of choice. The verification of all the desired properties are now routine.

Ex1 Example 2.2. Take X = ℝ^{+}, and let ϕ_{k}(x) be x rounded to the nearest half-integer multiple of r_{k} (breaking ties arbitrarily). More generally, one should think of ϕ_{k}(x) as a discretisation map at scale r_{k}.

Remark 2.3. if X has finite diameter, then it is easy to see that ϕ_{k} is constant for all sufficiently large negative k.

Henceforth we fix the maps ϕ_{k}. We can use them to create chains in a standard manner:

1We use the conventions d(E, F) := inf{d(x, y) : x ∈ E, y ∈ F } for non-empty sets E, F ⊂ X, and similarly define d(x, F), etc.

Definition 2.4 (Chains). A chain is a sequence x⃗ = (x_{k})_{k∈ℤ} of points in X such that

x_{k} = ϕ_{k}(x_{k+1}) for all k ∈ ℤ.  (2.1) causal

A point x ∈ X is generic if it is the limit lim_{k→+∞} x_{k} of exactly one chain. We let X^{∘} be the space of generic points, and if x is a generic point we let (x_{k})_{k∈ℤ} be the chain associated to it.

We define an ultrametric d_{Δ} on X^{∘} by the formula

d_{Δ}(x, y) := inf{r_{k} : x_{k} = y_{k}}.

It is routine to verify that d_{Δ} is indeed an ultrametric. In particular X^{∘} is equipped with a mesh of cubes.

Ex2 Example 2.5. Continuing Example ^{\underline{Ex1}} 2.2, one can identify the chains with the nonnegative (base 100) digit strings (which are leftward terminating but not necessarily rightward terminating). All chains have a limit, and a point x ∈ X is generic if and only if it is not a terminating base 100 decimal.

We now record some basic facts about generic points.

generic Lemma 2.6. Let x, y, z ∈ X^{∘} be generic points.

(i) (Convergence) We have d(x_{k}, x_{l}) < 2r_{k} for all k ⩽ l. In particular, d(x_{k}, x) < 2r_{k}.

(ii) (Ultrametric dominates metric) We have d(x_{k}, y_{k}) ⩽ 4d_{Δ}(x, y) for all k. In

particular, d(x, y) ⩽ 4d_{Δ}(x, y). (iii) (Absorption) If k is such that d(x, y_{k}) < \frac{1}{4}r_{k}, then x_{k} = y_{k}. (iv) (Determinism) If x_{k} = y_{k}, then x_{k′} = y_{k′} for all k′ ⩽ k.

Proof. From Lemma ^{\underline{ik}} 2.1(i) and (^{\underline{causal}} 2.1) we have d(x_{k}, x_{k+1}) ⩽ r_{k} for all k, and so claim (i) follows from the triangle inequality. To prove (ii), we may take x, y distinct, then there exists k such that d_{Δ}(x, y) = r_{k} and x_{k} = y_{k}. But by (i) we have d(x, x_{k}), d(y, y_{k}) < 2r_{k}, and the claim follows from the triangle inequality.

To prove (iii), observe from (i) that d(x, x_{k+1}) < 2r_{k+1} = \frac{1}{50}r_{k}. By the triangle inequality and (^{\underline{causal}} 2.1), this gives d(x_{k+1}, ϕ(y_{k+1})) = d(x_{k+1}, y_{k}) < \frac{1}{2}r_{k}. By Lemma ^{\underline{ik}} 2.1(iii), this gives ϕ(x_{k+1}) = ϕ(y_{k+1}), and so (iii) follows from (^{\underline{causal}} 2.1). Finally, (iv) is immediate from (^{\underline{causal}} 2.1) and induction.

Remark 2.7. From Lemma ^{\underline{generic}} 2.6(ii),(iii) we see that

B_{X^{∘},d}(y_{k}, \frac{1}{4}r_{k}) ⊂ B_{X^{∘},d_{Δ}}(y, r_{k}) ⊂ B_{X^{∘},d}(y_{k}, 4r_{k})

for all y ∈ X^{∘} and k ∈ ℤ. Thus the cubes B_{X^{∘},d_{Δ}}(y, r) are comparable in some sense to the balls B_{X,d}(y, r) restricted to X^{∘}.

We have not yet demonstrated the existence of any generic points whatsoever. However we have the following useful criterion:

test Lemma 2.8 (Test for genericity). If x ∈ X is such that d(x, ϕ_{k}(X)) < \frac{1}{4}r_{k} for infinitely many positive k, then x is generic.

Proof. Fix x ∈ X as above. By hypothesis we have an increasing sequence k_{n} → +∞ and x_{k_{n}} ∈ ϕ_{k_{n}}(X) such that

d(x, x_{k_{n}}) < \frac{1}{4}r_{k_{n}}.  (2.2) xxn

Define the partial chain (x_{k,n})_{k⩽k_{n}} by setting x_{k_{n},n} := x_{k_{n}} and x_{k,n} := ϕ(x_{k+1,n}) for k < k_{n}.

We now claim that each partial chain (x_{k,n})_{k⩽k_{n}} is a subchain of the following chain (x_{k,n+1})_{k⩽k_{n+1}}, or in other words that x_{k,n} = x_{k,n+1} for all k ⩽ k_{n}. Since x_{k,n} is determined by x_{k+1,n} for k < k_{n}, it suffices by induction to show that x_{k_{n}} = x_{k_{n},n+1}. But by repeating the proof of Lemma ^{\underline{generic}} 2.6(i) we have

d(x_{k_{n}+1,n+1}, x_{k_{n+1}}) < 2r_{k_{n+1}};

from this, (^{\underline{xxn}} 2.2), and the triangle inequality ew conclude

d(x_{k_{n}+1,n+1}, x_{k_{n}}) ⩽ \frac{1}{4}r_{k_{n}} + 2r_{k_{n+1}} + \frac{1}{4}r_{k_{n+1}} < \frac{1}{2}r_{k_{n}}.

Since x_{k_{n}} ∈ ϕ_{k_{n}}(X), we conclude from Lemma ^{\underline{ik}} 2.1(iii) that ϕ_{k_{n}}(x_{k_{n}+1,n+1}) = x_{k_{n}}, and thus x_{k_{n}} = x_{k_{n},n+1} as claimed.

We can glue all the partial chains together to form a complete chain (x_{k})_{k∈ℤ} which is compatible with the previously chosen x_{k_{n}}. From (^{\underline{xxn}} 2.2) we see that a subsequence of the x_{k} converges to x. On the other hand, from the proof of Lemma ^{\underline{generic}} 2.6(i) we know that x_{k} is a Cauchy sequence, and so x_{k} converges to x.

To complete the proof we need to demonstrate uniqueness. Suppose for contradiction that there was another chain (y_{k})_{k∈ℤ} which converged to x. Let n be arbitrary. By the proof of Lemma ^{\underline{generic}} 2.6(i) we see that d(x, y_{k_{n}+1}) < 2r_{k_{n}+1}. From (^{\underline{xxn}} 2.2) and the triangle inequality we conclude

d(y_{k_{n}+1}, x_{k_{n}}) < 2r_{k_{n}+1} + \frac{1}{4}r_{k_{n}} < \frac{1}{2}r_{k_{n}}.

Since x_{k_{n}} = ϕ(x_{k_{n}+1}), we thus see from Lemma ^{\underline{ik}} 2.1(iii) that ϕ(y_{k_{n}+1}) = x_{k_{n}}, and thus x_{k_{n}} = y_{k_{n}} for all n. By Lemma ^{\underline{generic}} 2.6(iv) we conclude that x_{k} = y_{k} for all k, a contradiction.

3. Doubling measures

Now suppose the metric space (X, d) also comes with a non-negative Borel measure μ which is locally finite in the sense that μ(B(x, r)) < ∞ for all balls B(x, r), and also obeys the doubling condition

μ(B(x, 2r)) ⩽ Aμ(B(x, r))  (3.1) doubling

for all balls B(x, r) and some fixed doubling constant A ⩾ 1. We also assume that μ is not identically zero, which implies (by doubling) that μ(B(x, r)) > 0 for all balls B(x, r).

Proposition 3.1. μ-almost every point is generic. (In particular, the set of generic points is dense.)

Proof. In view of Lemma ^{\underline{test}} 2.8 and countable additivity, it suffices to show that for every k_{0}, the set

E_{k_{0}} := ⋃_{k⩾k_{0}} ⋃_{y_{k}∈ϕ_{k}(X)} B(y_{k}, \frac{1}{4}r_{k})  (3.2) eko

has full measure in X (i.e. its complement has measure zero).

Fix k_{0}. Clearly E_{k_{0}} is open and hence measurable. Suppose for contradiction that E_{k_{0}} did not have full measure. By the Lebesgue differentiation theorem (which holds

5

for any metric space with a locally finite non-trivial doubling measure, see e.g. ^{\underline{stein:large}} [3]), there thus exists a point x ∈ X such that

lim_{r→0} \frac{μ(B(x, r) ∩ E_{k_{0}})}{μ(B(x, r))} = 0.

In particular

lim_{k→+∞} \frac{μ(B(x, 2r_{k}) ∩ E_{k_{0}})}{μ(B(x, 2r_{k}))} = 0.

On the other hand, for any k ⩾ k_{0}, we see from Lemma ^{\underline{ik}} 2.1(i) and the triangle inequality that

B(ϕ_{k}(x), \frac{1}{4}r_{k}) ⊂ B(x, 2r_{k}) ∩ E_{k_{0}}

and

B(x, 2r_{k}) ⊂ B(ϕ_{k}(x), 3r_{k}).

Thus we have

lim_{k→+∞} \frac{μ(B(ϕ_{k}(x), \frac{1}{4}r_{k}))}{μ(B(ϕ_{k}(x), 3r_{k}))} = 0.

But this contradicts the doubling condition (^{\underline{doubling}} 3.1).

For any cube Q and any η > 0 define the η-boundary ∂_{η}Q of Q as

∂_{η}Q := {x ∈ Q : d(Q, X^{∘}\Q) ⩽ ηr_{k}};

prelim Proposition 3.2 (Preliminary boundary estimate). For any integer N ⩾ 1, and any cube Q of generation k we have

μ(∂_{100^{−N−1}}Q) ⩽ \frac{A^{10}}{N} μ(Q).  (3.3) muq

Proof. Observe that

∂_{100^{−N−1}}Q = \{x ∈ Q : d(x, y) < \frac{1}{100^{N+1}} r_{k} and x_{k} ≠ y_{k} for some y ∈ X^{∘}\}. (3.4) edef

Let S denote the set

S := \{x ∈ Q, d(x_{k+j}, x_{k+j+1}) ⩾ \frac{1}{10}r_{k+j} for all 1 ⩽ j ⩽ N\}.  (3.5) sdef

claim1 Claim 3.3. [Boundary points have lacunary chains] ∂_{100^{−N−1}}Q ⊂ S.

Proof. Let x ∈ ∂_{100^{−N−1}}Q, and let y be as in (^{\underline{edef}} 3.4). Since x_{k} ≠ y_{k}, we also have x_{k+N} ≠ y_{k+N}, and thus by the contrapositive of Lemma ^{\underline{generic}} 2.6(iii)

d(y, x_{k+N}) ⩾ \frac{1}{4}r_{k+N}.

On the other hand, from Lemma ^{\underline{generic}} 2.6(i) we have

d(x, x_{k+N+1}) ⩽ 2r_{k+N+1} = \frac{1}{50}r_{k+N}.

Also,

d(x, y) ⩽ \frac{1}{100^{N+1}} r_{k} = \frac{1}{100}r_{k+N}.

From the triangle inequality we conclude

d(x_{k+j}, x_{k+j+1}) ⩾ \frac{1}{10}r_{k+j}

and hence x_{k+j} ∈ S_{j} as claimed.

claim2 Claim 3.4 (Lacunary chains are separated). If 1 ⩽ j ⩽ j′ ⩽ N and x, y ∈ S are such that d(x_{k+j}, y_{k+j′}) ⩽ \frac{1}{20}r_{k+j}, then j = j′ and x_{k+j} = y_{k+j}.

Proof. If j = j′ then the claim follows from Lemma ^{\underline{ik}} 2.1(iii), so suppose j′ > j. From Lemma ^{\underline{generic}} 2.6(i) we have

d(y_{k+j+1}, y_{k+j′}) ⩽ 2r_{k+j+1} = \frac{1}{50}r_{k+j}

and hence by the triangle inequality

d(x_{k+j}, y_{k+j+1}) < \frac{1}{10}r_{k+j}.

By Lemma ^{\underline{generic}} 2.6(iii) this forces x_{k+j} = y_{k+j}. But then this contradicts (^{\underline{sdef}} 3.5) since y ∈ S.

Let 1 ⩽ j ⩽ N, and let S_{j} := \{x_{k+j} : x ∈ S\}. From Claim ^{\underline{claim1}} 3.3 and Lemma ^{\underline{generic}} 2.6(i) we see that E_{Q,100^{−N−1}} ⊂ ⋃_{y∈S_{j}} B(y, 2r_{k+j}), and thus

μ(E_{Q,100^{−N−1}}) ⩽ ∑_{y∈S_{j}} μ(B(y, 2r_{k+j}))

and thus by the doubling property

μ(E_{Q,100^{−N−1}}) ⩽ A^{10} ∑_{y∈S_{j}} μ(B(y, \frac{1}{40}r_{k+j}))

(say). Averaging this in j we obtain

μ(E_{Q,100^{−N−1}}) ⩽ \frac{A^{10}}{N} ∑_{j=1}^{N} ∑_{y∈S_{j}} μ(B(y, \frac{1}{40}r_{k+j}))

On the other hand, from Claim ^{\underline{claim2}} 3.4 we see that the balls B(y, \frac{1}{40}r_{k+j}) are all disjoint, while from Lemma ^{\underline{generic}} 2.6(iii) we see that the balls all lie in Q. We conclude

μ(E_{Q,100^{−N−1}}) ⩽ \frac{A^{10}}{N} μ(Q)

as desired.

Proposition 3.5 (Final boundary estimate). For any cube Q of generation k and any η > 0 we have

μ(∂_{η}Q) ⩽ Cη^{c/A^{10}}μ(Q)  (3.6) ceta

for some absolute constants C, c > 0.

Proof. Using Proposition ^{\underline{prelim}} 3.2, we can find an integer 1 ⩽ N ⩽ O(A^{10}) such that

μ(∂_{100^{−N+1}}) ⩽ \frac{1}{2}μ(Q)  (3.7) half

for all cubes Q. We fix this N. We make the following claim: if C, c > 0 and η > 0 is such that (^{\underline{ceta}} 3.6) holds for all η > η_{0}, C is sufficiently large depending on N, and c is sufficiently small, then (^{\underline{ceta}} 3.6) also holds (with the same C, c) for all η > 100^{−N}η_{0}. Since (^{\underline{ceta}} 3.6) is trivially true for η > 1, the proposition then follows by induction.

It remains to verify the claim. We may assume that 100^{−N} > η > 100^{−N}η_{0} since again the claim is trivial otherwise. Observe that if x ∈ ∂_{η}Q, then there exists a cube Q_{k+N} of generation k + N in Q which contains x, and furthermore x ∈ ∂_{100^{N} η}Q_{k+N}. Thus if we let Q_{k+N} denote the collection of all such Q_{k+N} we have

∂_{η}Q ⊂ ⋃_{Q_{k+N} ∈Q_{k+N}} ∂_{100^{N} η}Q_{k+N}.

By induction hypothesis we thus have

μ(∂_{η}Q) ⩽ ∑_{Q_{k+N} ∈Q_{k+N}} C(100^{−N}η)^{c/A^{10}}μ(Q_{k+N}).

On the other hand, by Lemma^{\underline{generic}} 2.6(ii), Q_{k+N} has diameter at most 4r_{k+N}, thus d(y, X^{∘}\Q) < 5r_{k+N} < 100^{−N+1}r_{k} for all y ∈ Q_{k+N}. In particular

⋃_{Q_{k+N} ∈Q_{k+N}} Q_{k+N} ⊂ ∂_{100^{−N+1}}Q

and hence by (^{\underline{half}} 3.7)

∑_{Q_{k+N} ∈Q_{k+N}} μ(Q_{k+N}) ⩽ \frac{1}{2}μ(Q).

Putting all this together we obtain

μ(∂_{η}Q) ⩽ 2 × 100^{−cN/A^{10}} × Cη^{c/A^{10}}μ(Q)

and the claim follows if c is small enough.

We summarise the above results as the following theorem of Christ^{2}.

Theorem 3.6 (Christ’s cube construction). ^{\underline{christ}} [1] Let (X, d) be a metric space, and let μ be a non-negative non-trivial locally finite Borel measure with the doubling property (^{\underline{doubling}} 3.1) for some A > 0. Then there exists a subset X^{∘} ⊂ X of full measure, and a mesh of cubes (Q_{r})_{r>0} on X^{∘}, with the following properties:

• (Discreteness) If 100^{−k} ⩽ r < 100^{−k+1} for some integer k, then Q_{r} = Q_{100^{−k}}.

• (Comparability) If Q is a cube of radius r_{k} = 100^{−k}, then Q has diameter at most 4r_{k}, and contains a ball in X^{∘} of radius \frac{1}{4}r_{k}.

• (Boundary estimate) If Q is a cube of radius r_{k} = 100^{−k} and η > 0, then

μ({x ∈ Q : d(Q, X^{∘}\Q) ⩽ ηr_{k}}) ⩽ Cη^{c/A^{10}}μ(Q)

for some absolute constants C, c > 0.

Remark 3.7. In ^{\underline{christ}} [1], Christ extends the above result from metric spaces to quasimetric spaces (with appropriate changes in absolute constants such as 100), however it is possible to show that every quasi-metric space is equivalent to a power of a metric, and so the metric case actually implies the quasi-metric case.

References

christ [1] M. Christ, A T (b) theorem with remarks on analytic capacity and the Cauchy integral, Colloq.

Math. 50/51 (1990), 601–628.

david [2] G. David, Morceaux de graphes Lipschitziens et Intégrales Singulariéres sur une surface, Revista Mat. Iberoamericana 1 (1985), 1–56.

stein:large [3] E. M. Stein, Harmonic Analysis, Princeton University Press, 1993.

2A related construction also appears in \underline{david} [2].

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

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