True trees are dense

Abstract

We show that any compact, connected set K in the plane can be approximated by the critical points of a polynomial with two critical values. Equivalently, K can be approximated in the Hausdorff metric by a true tree in the sense of Grothendieck’s dessins d’enfants.

1 Introduction

Polynomials with at most two critical values are called generalized Chebyshev polynomials or Shabat polynomials. If p is such a polynomial of degree n with critical values in {±1}, then it is not hard to see that T=p ⁻¹([−1,1]) is a finite planar tree with n edges. We call a tree of this form a “true tree” or the “true form” of the combinatorial planar tree T. True trees can have all possible combinatorics, i.e., every finite planar tree has a true form and this true form is unique up to orientation preserving Euclidean similarities (see Sect. 2). Can true trees attain all possible “shapes”? More precisely, given a continuum (i.e., a compact, connected set) in the plane, can we find a true tree that approximates it as closely as we wish? The Hausdorff distance between two sets is the minimum ϵ>0 so that each set is contained in an ϵ-neighborhood of the other. In this note we prove:

Theorem 1.1

For any compact, connected set $K \subset \mathbb{C}$ and any ϵ>0 there is a polynomial p(z) with critical values exactly ±1 so that T=p ⁻¹([−1,1]) approximates K to within ϵ in the Hausdorff metric. In other words, true trees are dense in all planar continua.

True trees are a special case of Grothendieck’s theory of dessins d’enfants in which a finite graph drawn on a compact topological surface X induces a conformal structure on the surface and a Belyi map to the Riemann sphere (i.e., a meromorphic map branched over three points). In the case of a tree drawn on the plane, the compact surface is the Riemann sphere and the Belyi map is a polynomial with two finite critical values (∞ is the third branch point). These maps have close connections to algebraic number theory and Galois theory, although we will not deal with those topics here. There is an extensive literature on dessins d’enfants, true trees and Belyi functions, e.g., see [4, 8, 11–14, 17, 19, 20, 24] and their references.

Our approach to proving Theorem 1.1 is based on interpreting true trees in terms of conformal maps. We will describe this alternate formulation and reduce the theorem to a more geometric sounding statement.

Suppose T is a finite tree in the plane with n edges. Then the complement Ω of T is the image of a conformal map f from $\mathbb{D}^{*} = \{ |z| >1\}$ to Ω with f(∞)=∞. We say that T is “conformally balanced” if every open edge of the tree is the image under f of two disjoint open arcs of length π/n on $\partial \mathbb{D}^{*}$, and f(z)=f(w) implies f′(z)=f′(w) for almost every $z, w \in \mathbb{T}$. Because conformal maps preserve harmonic measure, the conformally balanced condition can be restated in terms harmonic measure with respect to ∞ on T (i.e., the first hitting distribution of Brownian motion on the sphere started at ∞ and run until it hits T). On each edge of the tree, harmonic measure naturally decomposes as the sum of two measures, one corresponding to each side of the edge. The tree is conformally balanced if (1) every edge has the same harmonic measure, and (2) when we decompose harmonic measure on each edge into measures corresponding to the two sides, these two measures are identical. Note that we mean that these measures give the same mass to every measurable subset of the edge, not merely that the whole edge gets equal harmonic measure from both sides.

To see that conformally balanced trees are exactly the same as the true trees described above, suppose T is a conformally balanced tree and let f be a conformal map from $\mathbb{D}^{*} = \{|z| >1\}$ to $\varOmega= \mathbb{C}\setminus T$, preserving ∞ and such that $1 \in \mathbb{T}=\{|z|=1\} = \partial \mathbb{D}^{*}$ maps to a vertex. Let $g(z) = \frac{1}{2}(z + z^{-1})$. This is called the Joukowsky map and is the conformal map from $\mathbb{D}^{*}$ to $U = \mathbb{C}\setminus[-1,1]$ that fixes −1,1,∞. Each edge of T has two preimages under f of length π/d on $\mathbb{T}$. Under the map z→z ^d each interval is mapped to either the upper or lower half-circle and pairs of intervals corresponding to the same edge of the tree map to opposite half-circles. Points that are mapped by f to the same point are also identified by g. Thus the map g((f ⁻¹(z))^d) defines a d-to-1 holomorphic map from the complement of the tree to the complement of [−1,1]. This map extends continuously to the whole plane and hence is a d-to-1 entire function (see Lemma 2.4) and hence is a polynomial. The critical points of p are the vertices of degree >1 of the tree, the only critical values are −1 and 1 and the tree itself is p ⁻¹([−1,1]). See Fig. 1. The argument can be reversed, so we see that true trees are the same as conformally balanced trees. Thus Theorem 1.1 can be rewritten as

Fig. 1

For any tree T, the composition of the conformal map from $\varOmega= \mathbb{C}\setminus T$ to {|z|>1}, followed by z ^d, followed by $\frac{1}{2} (z +\frac{1}{z})$ is d-to-1 and holomorphic off T. T is conformally balanced (i.e., is a true tree) iff this map extends continuously across T and hence defines a polynomial with critical values in {−1,1}

Theorem 1.2

For any compact, connected set K and any ϵ>0 there is a conformally balanced tree T that is within ϵ of K in the Hausdorff metric.

Theorems 1.1 and 1.2 were conjectured by Alex Eremenko. I thank him for the enlightening discussion of these problems during his visit to Stony Brook in March 2011. I thank Lasse Rempe for his comments on an earlier draft of this note. I also thank the referee for a careful reading of the manuscript and numerous corrections and suggestions for improving the paper.

Kevin Pilgrim has observed that the results in this paper, combined with his arguments in [18], prove that Julia sets of post-critically finite polynomials are dense in all planar continua. The details will appear in [3]. A related result was given using different methods by Kathryn Lindsey and William Thurston in [15].

For the Shabat polynomials p _n (z)=2z ⁿ−1, the only critical point is 0, whereas the corresponding trees $T_{n}= p_{n}^{-1}([-1,1])$ become dense in the unit disk as n increases. Thus it is possible for a sequence of true trees to approximate a set K, but the corresponding sets of critical points not to approximate K. However, it will be clear from our construction that the set K in the theorems is approximated by both a true tree and its corresponding set of critical points (i.e., the vertices of T of degree >1). Moreover, the trees we construct will have a number of “bounded geomery” properties, e.g., the maximum vertex degree is 4 and the edges are all analytic arcs with uniform estimates (i.e., each edge is the image of I=[−1,1] under a map that is conformal on a uniform neighborhood Ω of I).

Don Marshall and Steffen Rohde have recently adapted Marshall’s conformal mapping program zipper to approximate the true form of a given planar tree, [16]. The program can handle examples with thousands of edges and is highly accurate. See Fig. 2 for some examples.

Fig. 2

Two true trees drawn by Marshall and Rohde’s program. The data on the left was a randomly constructed tree with 75 edges. The tree edges are approximated by polygons so are not highly accurate, but the vertices (i.e., the roots of the Shabat polynomials) can be computed to over a 1000 digits of accuracy. The tree on the right has 1250 edges whose combinatorics were chosen to match those of the Julia set of a certain quadratic polynomial and the resulting true tree accurately matches the shape of the Julia set

The paper [2] contains a generalization of Theorem 1.1 from polynomials to entire functions. Given an infinite tree T in the plane satisfying certain bounded geometry conditions, this paper gives a construction of an entire function with only two critical values, so that f ⁻¹([−1,1]) approximates T in a precise sense. Section 15 of [2] describes how Theorem 1.1 in this paper can be deduced from the more intricate construction in that paper. Other applications are also given, e.g., the construction of Belyi functions on certain non-compact surfaces and the existence of an entire function with bounded singular set that has a wandering Fatou component (this is impossible for entire functions with finite singular sets by a modification of Dennis Sullivan’s “non-wandering” argument for rational functions. See [5, 6, 22]).

If we require the harmonic measures for the two sides of a tree edge to be identical, but don’t require all edges to have the same harmonic measure, we get what is called a minimal continuum. These sets arise as the continua of minimal capacity that connect a given finite set. Minimal continua are studied by Herbert Stahl in [21]; this authoritative paper contains extensive history and references for the topic. I thank Alex Eremenko for pointing out the connection between balanced trees and minimal continua to me.

2 Basic properties of conformally balanced trees

In this paper, a finite plane tree T will be a connected compact set in $\mathbb{C}$ that does not separate the plane and is a union of a finite collection of closed Jordan arcs, any two of which are either disjoint or have exactly one endpoint in common. The edges of the tree are the interiors of these arcs and the vertices are the endpoints. We shall say that two finite trees in the plane are equivalent if there is homeomorphism of the plane that takes one to the other. Note that this is more restrictive than saying there is a homeomorphism from one tree to the other since such a map can swap branches in a way that a planar homeomorphism cannot. See Fig. 3.

Fig. 3

Two planar trees that are homeomorphic but not equivalent (no homeomorphism of the plane maps one to the other)

A planar tree is locally connected, so a conformal map from $\mathbb{D}^{*}$ to $\varOmega= \mathbb{C}\setminus T$, extends continuously to $\mathbb{T}$. We shall always assume that such a map fixes ∞.

Let $R_{n} \subset \mathbb{T}$ be the set of nth roots of unity. A finite tree with n edges is conformally balanced if there is a conformal map $f: \mathbb{D}^{*} \to \varOmega= \mathbb{C}\setminus T$ so that each component of $\mathbb{T}\setminus R_{2n}$ is mapped 1-1 onto an edge of the tree and if I,J are two distinct components that map to the same edge, then f ⁻¹∘f defines a length preserving, orientation reversing map from one component to the other. This expresses precisely the idea that every edge has the same harmonic measure and that harmonic measure on each edge is the sum of harmonic measures corresponding to each side separately, and that these two measures are identical.

An orientation preserving homeomorphism ϕ of the plane to itself is called quasiconformal (or QC for short) if it is absolutely continuous on almost all vertical and horizontal lines and satisfies $|f_{\overline{z}}| \leq k |f_{z}|$ almost everywhere for some k<1. Such a map is also called K-quasiconformal where K=(k+1)/(k−1) measures the eccentricity of image ellipses of infinitesimal circles under f. The smallest such K is called the quasiconstant of f. The collection of K-quasiconformal maps for a fixed K form a compact family with respect to uniform convergence on compact sets (assuming the maps are normalized to fix ∞ and two finite points). See Alhfors’ book [1] for this and other properties of such maps. The function $\mu= f_{\overline{z}}/f_{z}$ is called the dilatation of the map f and the size of |μ| measures how far f is from conformal; if μ=0 on an open set, then f is conformal on that set. There is a composition law for dilatations that implies that if f and g have the same dilatation on an open set, then f ⁻¹∘g is conformal on that set. If f has zero dilatation on the whole plane, then f is a conformal linear map, i.e., f(z)=az+b. A well known quantitative version of this fact is:

Lemma 2.1

Given K<∞ and ϵ>0 there is a δ>0 so the following holds. If ψ is a K-quasiconformal map of the plane fixing 0,1,∞ and if its dilatation is zero except on a measure δ subset of $\mathbb{D}$, then |f(z)−z|<ϵ for every $z \in \mathbb{D}$.

Proof

One can give more precise estimates, but this version is simply a compactness argument. If δ↘0, then the maps must converge on compact sets to a conformal map fixing 0,1,∞, i.e., the identity. □

The measurable Riemann mapping theorem says that given any measurable μ on the plane with ∥μ∥_∞<1, there is a quasiconformal map f with dilatation μ. This is the key result about quasiconformal maps that we need, as illustrated by the following definition and lemma.

A tree T is QC-balanced if there is a quasiconformal mapping $\phi: \mathbb{D}^{*} \to\varOmega$ so that components of $\mathbb{T}\setminus R_{2n}$ are mapped to edges of T and when two components are mapped to the same edge, ϕ ⁻¹∘ϕ is length preserving and orientation reversing between the components (this is the same the definition of conformally balanced, except that we have replaced the conformal map by a quasiconformal map).

Lemma 2.2

Suppose T is a QC-balanced tree. Then there is a quasiconformal map of the plane to itself sending T to a conformally balanced tree.

Proof

Let $\phi: \mathbb{D}^{*} \to\varOmega$ be the QC map in the definition of QC-balanced and let μ be the dilatation of ϕ ⁻¹ on Ω. By the measurable Riemann mapping theorem there is a quasiconformal ψ on the plane with the same dilatation and thus ψ∘ϕ is conformal. Hence ψ(T) is conformally balanced. □

To say this in a slightly different way, if we compose the QC map $\phi^{-1}: \varOmega\to \mathbb{D}$ with z ^d and the Joukowsky map we get a locally QC map g from Ω to $U = \mathbb{C}\setminus[-1,1]$ that extends continuously to the whole plane. Then g is a d-to-1 quasiregular map with singular values ±1 and the measurable Riemann mapping theorem implies there is a quasiconformal map ϕ so that f=g∘ϕ ⁻¹ is a d-to-1 holomorphic map with the same singular values as g, i.e., f is a Shabat polynomial.

Thus we can construct a conformally balanced tree by first constructing a QC-balanced tree and “fixing it” with a QC map.

Lemma 2.3

Every finite tree in the plane can be mapped to a conformally balanced tree by a homeomorphism of the plane.

Proof

By the previous lemma, it suffices to map T to a QC-balanced tree. Every planar tree is equivalent to one with straight segments for edges and such a tree is clearly equivalent to one with smooth edges meeting with equal angles at each vertex (i.e., at a degree three vertex the edges meet at angle 120^∘). For such a tree the harmonic measures for two sides of any edge decay at the same rate at each endpoints (the decay rate may be different at the two endpoints of an edge if the endpoints have different degrees) and this means the harmonic measures for the two sides of an edge are within a bounded factor of each other (depending on the tree and the edge).

Let E be the preimages of the vertices under f. If T has n edges, there are 2n points in E. The 2n components of $\mathbb{T}\setminus E$ are paired by the relation of mapping to the same edge of T. Suppose I,J is such a pair. Then f ⁻¹∘f:I→J defines a biLipschitz map between such a pair of corresponding arcs I,J. In what follows, f ⁻¹∘f will always refer this type of map (between different intervals), rather than the identity from an interval to itself.

Let L:J→I be the map that multiplies length by a factor of |I|/|J| and reverses orientation. Define L on I to be the inverse of this map. Then g=L∘f ⁻¹∘f maps I to I, preserves orientation and is biLipschitz. Define g:J→J to be the identity. Then define g and L on every other pair of edge-arcs in the same way. The result is a biLipschitz, orientation preserving map of the circle to itself so that f(g(x))=f(L(x)) for every $x \in \mathbb{T}$. Note that g can be extended to a quasiconformal self-map ϕ of $\mathbb{D}^{*}$. Let F=g(E). Then there is a quasiconformal self-map h of $\mathbb{D}^{*}$ that maps E to R _2n (roots of unity) and |h′| is constant on each complementary arc.

Consider the map Φ=f∘g ⁻¹∘h ⁻¹. It is quasiconformal on $\mathbb{D}^{*}$, maps $\mathbb{T}$ onto T, and sends R _2n to the vertices. If two arcs of $\mathbb{T}\setminus R_{2n}$ are mapped to the same edge, then Φ ⁻¹∘Φ is length preserving. Hence T is QC-balanced and thus has a QC image that is conformally balanced. □

Lemma 2.4

A conformally balanced tree with n edges is of the form T=p ⁻¹([−1,1]) for some polynomial p that has exactly two critical values at {−1,1}. The vertices of degree >1 of T are exactly the critical points of p and the degree equals the order of the zero of p′ plus 1. The edges of T are analytic curves.

Proof

The proof is essentially given in the introduction. The only step that was not justified there was the statement that g(f(z)^d) “extends continuously to the whole plane and hence is entire and hence a polynomial”. This requires some proof.

We have already seen that a conformally balanced tree T is the planar quasiconformal image of a finite tree with smooth edges such that all angles at vertices are non-zero. This means the complement of T is a John domain and hence is removable for W ^1,2 mappings (one derivative in L ²; a QC map raised to a power is in this class locally). See [9, 10]. Thus if g(f(z)^d) is a continuous function that is holomorphic off T, then it is entire. This finishes the proof sketched in the introduction. □

Lemma 2.5

Two equivalent conformally balanced trees are the same up to a conformal linear map.

Proof

If two conformally balanced trees have the same topology, then there is a conformal map between their complements that extends continuously to the whole plane. Since the edges of balanced tree must be analytic, they are removable for conformal maps, so the map is conformal everywhere and hence is linear. □

Corollary 2.6

Every finite planar tree is equivalent to a conformally balanced tree that is unique up to linear maps.

In particular, the number of conformally balanced trees with n vertices (up to linear equivalence) is the same as the number of plane trees with n vertices. These can be counted using Pólya’s enumeration method as in [7, 23].

3 The construction on $\mathbb{T}$

The proof of Theorem 1.2 consists of constructing a tree T approximating K, pre-composing the conformal map $f: \mathbb{D}^{*} \to\varOmega= \mathbb{C}\setminus T$ by a QC self-map ϕ of $\mathbb{D}$ and finally post-composing f by a QC map ψ of Ω onto $\varOmega' = \mathbb{C}\setminus T'$ where T′ is a QC-balanced tree containing T and is close to it in the Hausdorff metric. The QC map ψ∘f∘ϕ associated to T′ will have uniformly bounded dilation and the support of the dilatation will have as small area as we wish, so invoking the measurable Riemann mapping theorem and Lemma 2.1 gives a conformally balanced tree that approximates K.

In this section we construct T and the pre-composition map ϕ of $\mathbb{D}^{*}$. The tree T′ and the QC map ψ:Ω→Ω′ will be constructed in the next section.

Suppose K is a compact connected set. Choose a large integer D and let ${\mathcal{C}}$ be the collection of dyadic square of size 2^−D that hit K. The corners and edges of these squares form a finite graph in the plane and we take a spanning tree for this graph. Then add segments of length $\frac{1}{4} 2^{-D}$ to any vertices of degree <4 so that every vertex in the resulting tree T has degree 1 or 4, every edge is still vertical or horizontal and every edge has length either 2^−D or 2^−D−2. See Fig. 4. The tree T approximates K to within 2^−D+1 in the Hausdorff metric.

Fig. 4

A continua is covered by dyadic boxes and an approximated tree is formed from the boxes’ edges. Some extra segments are added to make every degree 1 or 4 and every edge have length 2^−D or 2^−D−2

Why did we add the extra segments to make every degree 1 or 4? This is more of a convenience than a necessity. The condition insures that for any edge, the harmonic measures for the two sides have the same behavior as we approach an endpoint, i.e., $\frac{d \omega_{1}}{d \omega_{2}}$ is bounded above and below on the whole edge (in fact, this function extends to be analytic on a neighborhood of the edge). The precise version of this fact that we will use is:

Lemma 3.1

Suppose e is an open edge of T, $f:\mathbb{D}^{*} \to\varOmega$ is a conformal map onto the exterior of T and $I, J \subset \mathbb{T}$ are the two components of f ⁻¹(e). The map g=f ⁻¹∘f defined from I to J has an extension to a conformal map from a neighborhood Ω _I of I to a neighborhood Ω _J of J. Moreover,

$$\mathrm{dist}(I, \partial\varOmega_I) \geq C_1 |I|, $$

for some absolute C ₁>0. The same estimate holds for J and Ω _J . Also,

$$C_2^{-1} \leq|g'| \frac{|I|}{|J|} \leq C_2 $$

on I for some absolute C ₂<∞.

Proof

This is just an application of the Schwarz reflection principle. We first consider the case when the endpoints of e both have degree 4, as in Fig. 5. Let e′ be the edge e with perpendicular segments of length $\frac{1}{4} |e|$ added at either end, so as to bound three sides of a rectangle R, whose preimage under f is an open set $\varOmega_{I}^{+}$ in $\mathbb{D}^{*}$ with I in its boundary. This open set, together with its boundary I′ on $\mathbb{T}$ and its reflection across $\mathbb{T}$ will be the set Ω _I .

Fig. 5

Proof that g=f ⁻¹∘f has a conformal extension to a neighborhood of I if the image connects two vertices of degree 4

Map $\varOmega_{I}^{+}$ to R by f, follow by a reflection across e to another rectangle, map this to a set $\varOmega_{J}^{+}$ by f ⁻¹ and reflect this across $\mathbb{T}$ to the set $\varOmega_{J}^{-}$. Let Ω _J be the union of $\varOmega_{J}^{+}, \varOmega_{J}^{-}$ and the interior (in $\mathbb{T}$) of their common boundary J′.

This composition is made up of two conformal maps and two reflections, so is a conformal map $\varOmega_{I}^{+} \to\varOmega_{J}^{-}$ and sends I′ to J′, so by the Schwarz reflection principle, it extends to be a conformal map from Ω _I to Ω _J .

Clearly the harmonic measure of e in $\varOmega= \mathbb{C}\setminus T$ from any point of the opposite side of R is bounded uniformly away from one, so the same is true of I in $\mathbb{D}^{*}$ from any point of $\partial\varOmega_{I} \cap \mathbb{D}^{*}$. This implies ∂Ω _I is at least distance C ₁|I| from I for some absolute C ₁. The same applies to J and Ω _J . The Koebe $\frac{1}{4}$-theorem now implies that g has derivative comparable to |J|/|I| on I, again with absolute constants.

If e has one vertex of degree 1 and the other of degree 4, the argument is very similar. In this case, the intervals I and J are adjacent and we take R as shown in Fig. 6. Its preimage under f is the light gray region above the circle that we will denote $\varOmega_{IJ}^{+}$, and the darker region below the circle is its reflection $\varOmega_{IJ}^{-}$. As before, the composition of the four maps is conformal between these domains, and hence it has a conformal extension from the obvious domain Ω _IJ to itself. The remaining conclusions follow just as before.

Fig. 6

Proof that g=f ⁻¹∘f has a conformal extension to a neighborhood of I if the image connects a degree 1 and degree 4 vertex

 □

So the restriction of the mapping g=f ⁻¹∘f to any component of $\mathbb{T}\setminus E$ has a conformal extension to a uniformly larger neighborhood (recall E are the preimages under f of the vertices of T), although the map itself may have jump discontinuities at the points of E. This is not quite the same as “piecewise analytic” since this term usually includes continuity at the endpoints. We want to approximate g by a piecewise linear map on each component of $\mathbb{T}\setminus E$ by adding more points into the gaps between E and linearly interpolating the values of g between these points.

Lemma 3.2

Suppose g is as above. Then there is a quasiconformal map ϕ of $\mathbb{D}^{*}$ to itself, and a finite set $F \subset \mathbb{T}$ so that ϕ(F) contains E and so that ϕ ⁻¹∘g∘ϕ is piecewise linear on each component of $\mathbb{T}\setminus F$. The quasiconstant of ϕ is uniformly bounded and the dilatation μ of ϕ can be chosen to be supported in any neighborhood of $\mathbb{T}$ that we want (depending on our choice of F). We let ${\mathcal{I}}$ denote the connected components of $\mathbb{T}\setminus F$. The length of each interval in ${\mathcal{I}}$ may be chosen to be of the form 2π2⁻ⁿ for some integer n (possibly different n’s for different intervals), the lengths of adjacent intervals are within a factor of 2 of each other and every interval has the same length as at least one of its two neighbors. If two intervals in ${ \mathcal{I}}$ are adjacent and their common endpoint is mapped by f to a vertex of T, then they have the same length.

Proof

Consider a pair I,J of components of $\mathbb{T}\setminus E$ that map to the same edge of T. Subdivide I and on each subinterval, let ϕ be defined as g followed by the linear map from J=g(I) back to I that inverts g at the endpoints. On the interval J=g(I), ϕ is defined to be the identity. Since g is smooth, ϕ is biLipschitz with constant as close to 1 as we want if the subdivision of I is fine enough. We can therefore extend it to a quasiconformal map of the Carleson region

$$Q_I = \bigl\{ z \in \mathbb{D}^*: z/|z| \in I, |z|-1 < |I| \bigr\} , $$

to itself that is the identity on ∂Q _I ∖I. Define ϕ on the rest of $\mathbb{D}^{*}$ as the identity and define it in $\mathbb{D}$ by reflection. This map has the desired piecewise linear property, but we still need to adjust the sizes of the intervals.

To make adjacent intervals have comparable length with a factor of 2, we simply split the larger in 2 equal pieces whenever this fails; the shortest interval will never be split and a shorter interval will never be produced, so the process ends after a finite number of steps.

To make notation easier, we normalize arclength on the circle to be 1. To make sure that the normalized interval lengths are powers of 2, cover the circle by disjoint dyadic intervals that are at most 1/4 as long as any of the intervals from the collection that they hit, and that are maximal with respect to this property. Such a dyadic interval has at least $\frac{1}{8}$th of the length of the shortest interval it hits, and is contained in the union of this interval and one of its neighbors, which is at most twice as long. Thus each of our dyadic intervals has length between $\frac{1}{4}$ and $\frac{1}{16}$ times the length of any interval in our collection that it intersects.

If we replace each interval I in ${\mathcal{I}}$ by the union of dyadic intervals in ${\mathcal{D}}$ that are contained in I or contain I’s left endpoint, the new interval I′ has comparable length and is a union of between 4 and 16 dyadic intervals. By splitting some of the dyadic intervals in two, we can insure it is always a union of 16 dyadic intervals.

If necessary, we can repeat the “split the larger neighbor” argument to insure adjacent intervals have lengths within a factor of 2 of each other. We end by splitting every interval into four equal subintervals to make sure every interval has at least one equal sized neighbor. If I and J are both adjacent to a point mapping to a vertex, but are not of equal length, then one is exactly twice as long as the other. Subdivide the longer one and the adjacent interval of the same length. Then the two segments adjacent to the vertex preimage are equal and all the intervals still satisfy all the other requirements. This final collection is the desired collection ${\mathcal{I}}$. □

4 The construction on T

In this section, we define a tree T′ containing T and a series of quasiconformal maps

$$\mathbb{C}\setminus T = \varOmega\to\varOmega_0 \to \varOmega_1 \to\varOmega_2 \to\varOmega_3 \to \varOmega_4 = \mathbb{C}\setminus T'. $$

If we denote the composition by ψ, then our construction will have the property that T′ is a QC-balanced tree via the map $\psi\circ f \circ\phi: \mathbb{D}^{*} \to \mathbb{C}\setminus T'$. Moreover, the dilatation of this map will be uniformly bounded and the support of its dilation is mapped into as small a neighborhood of T as we wish (equivalently, the inverse map, which automatically has the same quasiconstant, has dilatation supported in an arbitrarily small neighborhood of T). Thus using Lemmas 2.1 and 2.2 will yield a conformally balanced tree that approximates T, and hence K.

To simplify, we will rescale T to correspond to a unit grid (i.e., take D=0).

In order to draw simpler pictures, we want to avoid the corners in T created by the vertices of degree 4. The first map ψ ₀:Ω→Ω ₀⊂Ω simply pulls the domain way from these corners in a uniformly QC way. Choose 0<δ≪1 to be a small power of 2 (how small will be determined during the course of the construction) and for each degree 4 vertex in T remove the four δ×δ subsquares of Ω that have this vertex as a corner. This gives Ω ₀. Let Ω′ be Ω with slits of length $\sqrt{2} \delta$ bisecting each corner of Ω removed (these are diagonals of the squares we just removed). There is a uniformly quasiconformal map ψ ₀:Ω′→Ω ₀ that is affine on each edge and equals the identity outside a δ-neighborhood of T. See Fig. 7. (Note that ψ ₀ is not quasiconformal on Ω because it is not continuous along the slits defining Ω′, but we will finish the construction by composing with $\psi_{0}^{-1}$ to “fill in” the corners and the composed map will have a continuous, quasiconformal extension to all of Ω.)

Fig. 7

The map ψ ₀:Ω→Ω ₀. It pulls the domain away from the corners

Now we define Ω ₁ as the set of points z∈Ω ₀ such that

$$\mathrm{dist}(z, T) > \delta\quad\text{or} \quad \mathrm{dist}(z, T) > \sqrt{2} \mathrm{dist}(z, V_1), $$

where V ₁ is the finite set of degree 1 vertices of T. Thus Ω ₁ is a polygon where most of the edges are parallel to edges of T, except in a neighborhood of each degree one vertex where the boundary slopes down to hit T at the vertex. We can clearly map Ω ₀→Ω ₁ by a uniformly QC map with dilatation supported in a δ-neighborhood of T. See Fig. 8. If δ is small enough then any interval of length δ with one endpoint at a degree 1 vertex of T is contained in the image of the two ${\mathcal{I}}$ intervals on the circle that are adjacent to that vertex. Assume δ has been chosen small enough to make this happen at every degree 1 vertex.

Fig. 8

The map ψ ₁:Ω ₀→Ω ₁

Let ${\mathcal{J}}$ denote the segments in T that are of the form ∂Ω ₀∩e for some edge e of T. Each edge e of T either connects two vertices of degree four or connects a vertex of degree four to a vertex of degree one. In the first case, segments in ${\mathcal{J}}$ consist of e with two intervals of length δ removed (one at each endpoint), and in the second case we only remove an interval at the degree four vertex.

The map ψ ₀∘f∘ϕ ⁻¹ sends each element of ${\mathcal{I}}$ into some element of ${\mathcal{J}}$. Since each element of ${\mathcal{I}}$ has measure that is a power of 2, there is a smallest and largest power that occur and we denote these by 2⁻ⁿ and 2^N−n. Then the measure of each element that occurs can be written as 2^m2^−n−N where N≤m≤2N. By taking N larger, if necessary, we can assume 2^−n−N evenly divides 1−2δ and $\frac{1}{4} -\delta$ (the two possible lengths of edges in ${\mathcal{J}}$). Thus each element of ${\mathcal{J}}$ can be divided into an integer number of disjoint sub-segments of length 2^−n−N. This collection of subintervals is called ${\mathcal{K}}$. Taking N larger, if necessary, we may assume 2N2^−n−N<δ.

Each element $K \in{ \mathcal{K}}$ is associated to two elements of ${\mathcal{I}}$ whose images contain K and that correspond to the two sides of K. If the measure of one of these intervals is 2^m2^−n−N we call m one of the two “heights” associated to K. Each height is associated to one side of K. Lemma 3.2 implies that the heights of intervals in K do not change very quickly. In fact, that lemma implies the following facts about intervals in ${\mathcal{K}}$:

• (1) adjacent intervals have heights differing by at most 1,

• (2) every interval has the same height as at least one of its neighboring intervals,

• (3) given a degree 1 vertex v of T, every interval within distance δ of v has the same height,

• (4) given one of the δ×δ squares removed from Ω to form Ω ₀, the two intervals adjacent to that square have the same height. They also have the same heights as the neighboring intervals that are not adjacent to the removed square.

Next we build Ω ₂. For each segment $K \in{ \mathcal{K}}$ in ∂Ω ₀ we add a rectangle or trapezoid to both sides as follows. First suppose K=[a,b] is within distance δ of a degree 1 vertex v. This means that the heights of K for either side are the same by Lemma 3.2 if δ has been chosen small enough (since intervals adjacent to a vertex of the tree have equal measure). If m denotes the height associated to K, and if

$$m |K| \geq \mathrm{dist}(K,v_1) +|K| $$

then we add a rectangle of size |K|×m|K| to both sides of K. Otherwise we add a trapezoid with one side K, two sides perpendicular to K and the fourth side on ∂Ω ₁. See Fig. 9.

Fig. 9

We map ψ ₂:Ω ₁→Ω ₂ by pushing the boundary back towards T. The map is the identity for points more than δ from T

If K is more than distance δ from any degree one vertex then consider one side of K and the two adjacent intervals. If all three intervals have the same height m, then we add a |K|×m|K| rectangle with K as one side. Otherwise, one of the adjacent intervals has the same height m as K and the other has height m ^∗ differing by 1. We add a trapezoid with base K, and two parallel sides that are perpendicular to K with side lengths m|K| and m ^∗|K|. The fourth side of the trapezoid is opposite K and has length $\sqrt{2} |K|$.

If K has only one neighbor, it must be adjacent to one of the removed “corner squares” of Ω ₀. As noted earlier, it must have the same height as its immediate neighbor, as well as the other interval of ${\mathcal{K}}$ adjacent to the same corner square.

Let W be the union of all these closed rectangles and trapezoids, together with the closures of δ×δ squares removed from Ω to form Ω ₀. The union is a closed connected set and the complement is the open set Ω ₂. Clearly Ω ₁ can be mapped to Ω ₂ by a quasiconformal map ψ ₂ that is piecewise affine, has uniformly bounded quasiconstant and has dilatation supported in a δ-neighborhood of T. See Fig. 9.

If we add all the open rectangles and trapezoids to Ω ₁, along with their edge on ∂Ω ₂, we get an open set Ω ₃ containing Ω ₂. We define $\varOmega_{4} = \psi_{0}^{-1} (\varOmega_{3})$ and T′=∂Ω _r . Clearly this is a linear tree that contains T. See Fig. 10.

Fig. 10

The map ψ ₃:Ω ₂→Ω ₃ fills in rectangles and trapezoids and then $\psi_{0}^{-1}$ “refills” the corners. The composition $\psi= \psi_{0}^{-1} \circ\psi_{3} \circ\psi_{2} \circ\psi_{1} \circ\psi_{0}$ has uniformly bounded dilatation, is the identity outside a δ-neighborhood of T and has a continuous extension Ω→Ω ₄

The only object not yet defined is the quasiconformal map ψ ₃:Ω ₂→Ω ₃. Again, the map is the identity far from T, and each connected component of Ω ₃∖Ω ₂ is a rectangle or a trapezoid (we will denote either type of region by R) and is the image under ψ ₃ of a square in Ω ₂ that shares a side with R. See Fig. 11. There are three types of maps to describe: m-rectangle maps, m-trapezoid maps and m-tip maps. Each of these maps takes a region in Ω ₂ (either a triangle or square) with one boundary segment I on ∂Ω ₂ and expands it into the component of Ω ₃∖Ω ₂ attached along I (this component is either a rectangle, a trapezoid or a triangle). See Fig. 11. Each map is the identity on ∂R∩Ω ₂, so the map can be extended as the identity to the rest of the plane. We will describe each type of map separately.

Fig. 11

The map ψ ₃:Ω ₂→Ω ₃ is made up of three types of maps that expand a square or triangle in Ω ₂ into a rectangle or trapezoid in Ω ₃∖Ω ₂

Rectangle maps

An m-rectangle map sends a unit square S to a 1×m rectangle R. We write R as a union of m adjacent unit squares $R = \bigcup_{k=1^{m}} S_{k}$ with S ₁=S. The boundary values of the map are as follows. The map is the identity on ∂S∩∂R (this is three sides of the square) and the fourth side is mapped to the rest of R. starting at the endpoints, divide the fourth side symmetrically into two intervals of lengths 4^−k for k=1,…,m (the longest adjacent to the endpoints, the shortest adjacent to the midpoint). For k=1,…m intervals of length 4^−k are mapped affinely to the part of ∂S _k on the long sides of R. The union of the two intervals of length 2^−m is mapped affinely to the short side of R on ∂S _k . That these boundary values can be attained by a uniformly quasiconformal map is apparent from the diagrams in Figs. 12 and 13.

Fig. 12

This shows in more detail how the map in Fig. 11 expands Ω ₂ into Ω ₃. In each case the domain is cut into decreasing, nested pieces and the pieces are expanded to shapes that fill the image. The boundary expansion on the kth piece is 2^k in a sense that is made precise in the text. The details of each type of map are shown in Figs. 13, 14 and 15

Fig. 13

The m-rectangle map sends a square to a 1×m rectangle. The map is composed from three types of pieces: one each for mapping onto the “top” box (lighter shading in Fig. 12) and “bottom” (darker) and another that is repeated in all the “middle” boxes (white). The triangulations define piecewise affine maps between the polygons

The first figure shows how to subdivide the square into m−1 nested polygonal regions P ₁,…,P _m−1; P ₁ maps to a 1×2 sub-rectangle in R, P ₂,…,P _m−2 are all similar to each other and map to squares, and P _m−1 is a square mapping to a square (but not in the obvious way, since one of its sides must map to three sides in the image). These three maps are constructed in Fig. 13 by showing compatible triangulations for domains and ranges (i.e., the triangulations are in a 1-1 correspondence that preserves adjacency). Given compatible triangulations of two regions we can define a quasiconformal map between them by taking the obvious piecewise affine maps between triangles. It is now an easy exercise to check that the mappings induced by the triangulations have the boundary values described above.

Trapezoid maps

A m-trapezoid map also maps into a 1×m rectangle R as above, but the domain of this map is now a right triangle that we may identify with one half of the top square cut by a diagonal. The boundary map is the identity on the legs of this triangle. There is an asymmetry to the construction and we assume the picture is as shown in Fig. 12, so that the domain of the map is the upper right half of the top square. The hypotenuse of the triangle is divided into pairs of intervals of size 4^−k, k=1,… as before and the left half is mapped to the left side of the rectangle as before. On the right side the rightmost interval has length $\frac{1}{4}$ and is folded onto itself to form a slit of length 1/8 in the rectangle; this slit is not in the image of the interior. The remaining smaller intervals are mapped to the right side of the rectangle just as before. Figure 14 shows how to divide the triangle into regions and map these regions into the rectangle. We only show the details for the top piece; the lower pieces are affinely stretched to be similar to the rectangle map pieces and then mapped exactly as in the rectangle maps.

Fig. 14

The m-trapezoid map sends the triangle to a 1×m rectangle. The middle and bottom maps are the same, after an affine stretching, to the middle and bottom maps of the rectangle map, so we only show the construction for the top piece. Note that the image is not a simple polygon; a piece of the boundary is folded onto itself to form a slit in the image. This is necessary for the trapezoid map to match rectangle maps of different heights on either side

Note that m-trapezoid maps interpolate between m-rectangle maps and (m−1)-rectangle maps. The boundary segments of ∂Ω ₂ corresponding to each map have measure 2^m2^−n−M. Dividing these segments into 2^m+1 equal, disjoint subsegments and applying the “filling map” partitions the sides and bottom of the rectangular image into intervals. Whenever two rectangles or trapezoids share a side, we want the partitions of these sides to be identical. Each piece of the partition is one edge of our QC-balanced tree and we want them to have equal measure. Obviously two rectangles maps of the same height match up and the definition of the m-trapezoid map is designed so that it matches a m-rectangle map on one side and a (m−1)-rectangle map on the other. The top side of an (m−1)-rectangle map has half the measure of the top of a m-rectangle, so the trapezoid map matches up intervals of equal measure.

Tip maps

The third type of map is the m-tip map. The details are described in Fig. 15. Each m-tip map is designed to match a (m+1)-tip map (or a m-rectangle map) on its longer vertical side and a (m−1)-tip map on its shorter vertical side. Once again the boundary map is the identity on the top three sides of the domain, and maps the bottom side to the sides and bottom of the image trapezoid. The bottom side of the domain square is again divided into symmetric pairs of intervals of length 4^−m. The leftmost and rightmost are mapped to the unit segments of the trapezoids vertical sides, but since these sides are different lengths, the images are displaced vertically with respect to each other, so they form the vertical sides of a parallelogram. Intervals of length 4^−k are mapped to vertical sides of the lower parallelograms. After m steps, the parallelogram hits the bottom edge and the rest of the domain square is mapped to the bottom triangle as illustrated in Fig. 15. The last map, adjacent to the tip, is a special case that is illustrated in Fig. 15.

Fig. 15

The m tip maps also fills in a trapezoid, but is different from a trapezoid map because it has to match other tip maps, not two rectangle maps of different heights. Again, it is built from three types of map: top, bottom and middle. Along its left side (for the orientation shown) it matches a m-rectangle map or the right side of a (m+1)-tip map and on the right it matches the right side of a (m−1)-tip map. The 1-tip map requires a special construction, as shown at lower right

All the top intervals of the tip trapezoids have the same measure, so the tip maps match intervals of the same measure along the vertical sides. Tip maps for opposite sides of an interval $K \in{ \mathcal{K}}$ are the same and such intervals have the same measure from both sides, so the maps match here as well.

This completes the construction of the map ψ:Ω→Ω ₄ and the verification that ψ∘f∘ϕ ⁻¹ makes T′ a QC-balanced tree. The construction also clearly shows this map is uniformly quasiconformal and is conformal except on a small neighborhood of T. In particular, the quasiconstant is independent of δ, and as δ→0, the support of the dilatation is as small as we wish, so that the “correction” map obtained from the measurable Riemann mapping theorem is as close to the identity as we want. This completes the proof of Theorem 1.2.