Peter Haïssinsky

Finite type coarse expanding conformal dynamics

We continue the study of noninvertible topological dynamical systems with expanding behavior. We introduce the class of finite type systems which are characterized by the condition that, up to rescaling and uniformly bounded distortion, there are only finitely many iterates. We show that subhyperbolic rational maps and finite subdivision rules (in the sense of Cannon, Floyd, Kenyon, and Parry) with bounded valence and mesh going to zero are of finite type. In addition, we show that the limit dynamical system associated to a selfsimilar, contracting, recurrent, level-transitive group action (in the sense of V. Nekrashevych) is of finite type. The proof makes essential use of an analog of the finiteness of cone types property enjoyed by hyperbolic groups.

Introduction

Consider a classical expanding conformal dynamical system on the Riemann sphere C equipped with its spherical metric-that is, a finitely generated convex cocompact Kleinian group Γ of Möbius transformations, or a hyperbolic rational function f . The chaotic set X (the limit set, in case of a group, or Julia set, in case of a map) is quasi-selfsimilar: given any ball B ⊂ X, there is a group element (or iterate) ψ : B → X which is nearly a similarity and whose image has a definite size independent of B. This is sometimes known as the principle of the conformal elevator: the dynamics transports geometric features at small scales to large (and, by taking inverses, large scales to small) with uniformly bounded distortion.

The expansive nature of such systems implies that they are finitely generated in the sense of Gromov [START_REF] Gromov | Hyperbolic groups[END_REF]. Roughly, this means that they are quotients of a subshift of finite type. Moreover, they are finitely presented, that is, the equivalence relation defining the quotient is again a subshift of finite type. Other finitely presented systems in which the principle of the conformal elevator holds include the action of a Gromov hyperbolic group on its boundary equipped with a visual metric. For such groups, the finiteness comes from the finiteness of cone types, observed by Cannon in the classical case. Not all finitely presented systems are conformal, since the former include e.g. Anosov maps on tori. For details, see [CP] and the references therein.

In one-dimensional complex dynamics, there are classes more general than hyperbolic for which the principle of the conformal elevator still holds. For example, it holds for subhyperbolic maps -those whose critical points are either in the Fatou set and converge to attracting cycles, or else in the Julia set and are eventually periodic. As topological dynamical systems, the set of conjugacy classes of such maps is countable. The principle holds as well for the more general semi-hyperbolic maps -those with neither recurrent critical points nor indifferent cycles. The latter class is much larger, however, containing uncountably many distinct topological conjugacy classes even in the family of quadratic polynomials.

In earlier work [HP], we introduced a broad class of metric noninvertible discrete-time dynamical systems f : X → X which generalizes the class of semi-hyperbolic rational maps. A key role is played by a finite cover U 0 of X by connected open sets and the sequence of covers U n+1 = f -1 (U n ), n = 1, 2, 3, . . . obtained by taking components of iterated preimages. Such systems, called metric coarse expanding conformal (cxc), are defined so that the principle of the conformal elevator holds. A metrization principle holds: under reasonable hypotheses, a suitably expanding (precisely, a "topologically cxc") dynamical system determines a natural quasisymmetry class of metrics in which the dynamics is metrically cxc. This allows us to adapt techniques from classical conformal dynamics to study noninvertible topological dynamical systems. Precise statements are given in Chapter 2 below. A distinguishing feature of such systems is that, like for subhyperbolic rational maps, the dynamics need not be locally injective on the chaotic set. In many respect, our results in [HP] suggest that our class of cxc maps share many properties with hyperbolic groups, thus extending Sullivan's dictionary to this wider setting. However, the fact that hyperbolic groups are automatic, which is a consequence of the finiteness of cone types for such groups, does not seem to have a counterpart for cxc dynamics in general.

In the present work, we single out a subset of the metric cxc systems comprising maps which satisfy finiteness features that we believe to be analogous to the finiteness of cone types. These dynamical systems are characterized by the existence of what we call a dynatlas-a finite set M of local model maps g m : V m → V m , m ∈ M such that the restriction of any (suitable) iterate f k : U → U , U ∈ U n+k , U ∈ U n is, after rescaling, nearly isometric to one of the model maps g m . We term such systems cxc systems of finite type. The set of finite type rational maps is exactly the set of so-called subhyperbolic rational maps. Perhaps over-optimistically, we suspect that such finite type cxc systems are finitely presented. The lack of available (to us) general techniques from dynamics and the few topological assumptions made on the underlying space X makes verification of this suspicion difficult.

Our main results identify two important natural sources of examples of cxc systems of finite type which do not necessarily arise from classical Riemannian conformal dynamics.

Finite subdivision rules. We study those finite subdivision rules (fsr's) of Cannon,Floyd,and Parry [CFP1] which have bounded valence and mesh going to zero; they yield postcritically finite branched, or Thurston, maps f : S 2 → S 2 of the two-sphere to itself without periodic critical points. Such fsr's arise naturally in geometrization questions such as the characterization of rational functions and Cannon's conjecture concerning hyperbolic groups with two-sphere boundary. These maps turn out to be topologically cxc, and the metrization principle in [HP], shows that such fsr's naturally yield metric cxc systems.

We show (Corollary 3.14) that in fact, the corresponding metric cxc dynamical systems are of finite type. More is actually true: in a natural metric, up to similarity (not quasisimilarity), there are only finitely many tiles. This is derived from a general metrization principle (Theorem 3.10) which asserts that a topological dynamical system with suitable finiteness properties admits a natural metric in which the dynamics is metrically of finite type.

Selfsimilar groups. In [START_REF] Nekrashevych | Self-similar groups[END_REF] a general theory of so-called selfsimilar groups is developed which connects group theory and dynamical systems in both directions. In one direction, to a dynamical system, f : X → X one may associate a selfsimilar group action, its iterated monodromy group. Under reasonable expansion hypotheses, this action is contracting and recurrent. In the other direction, to a selfsimilar contracting recurrent action is associated a topological dynamical system ∂F Σ : ∂Σ → ∂Σ. The underlying space ∂Σ is the boundary of an infinite Gromov hyperbolic graph, Σ, called the selfsimilarity complex associated to the action. The map ∂F Σ is induced by a graph endomorphism F Σ : Σ → Σ. Under appropriate topological regularity and expansion hypotheses, the circle of ideas can be completed. That is, given f : X → X, the iterated monodromy group associated to f yields a selfsimilar recurrent contracting action, and the associated topological dynamical system ∂F Σ : ∂Σ → ∂Σ is conjugate to f : X → X.

We prove a finiteness principle (Theorem 5.17) for the map F Σ analogous to the finiteness of cone types for a hyperbolic group. This is used to conclude (Theorem 6.15) that, in a visual metric on the boundary, such dynamical systems are metric cxc of finite type. As a corollary, we obtain that the quasi-isometry type of the selfsimilarity complex Σ and, therefore, the quasisymmetry class of metrics on its boundary are invariants of the induced topological dynamical system, hence of the group action. In particular, the Ahlfors regular conformal dimension is a numerical invariant of this group action. It would be interesting to know how this invariant is related to other such quantities, e.g. contraction coefficients, growth functions, etc.

Organization. In §2, we define the class of topological and metric cxc systems, concluding with the formal definition of metric finite type. In §3, we give natural first classes of examples, starting with unbranched systems. Next we prove that subhyperbolic maps are finite type. The proof given motivates the more abstract argument used to prove the metrization theorem, Theorem 3.10. § §4, 5, and 6 present the connections to selfsimilar groups.

Acknowledgements. The authors would like to thank Jim Cannon and Volodia Nekrashevych for useful conversations, and the anonymous referee for numerous detailed comments. Both authors were partially supported by the project ANR "Cannon" (ANR-06-BLAN-0366). The second author was supported by NSF grant DMS-0400852.

Definition and first properties

We first recall some definitions and results from [HP]. We then define the class of metric finite type maps, and show they are coarse expanding conformal.

Finite branched coverings

Suppose X, Y are locally compact Hausdorff spaces, and let f : X → Y be a finite-to-one continuous map. The degree of f is

deg(f ) = sup{#f -1 (y) : y ∈ Y }. For x ∈ X, the local degree of f at x is deg(f ; x) = inf U sup{#f -1 ({z}) ∩ U : z ∈ f (U )}
where U ranges over all neighborhoods of x. (ii) for every x 0 ∈ X, there are compact neighborhoods U and V of x 0 and f (x 0 ) respectively such that

x∈U,f (x)=y deg(f ; x) = deg(f ; x 0 )
for all y ∈ V .

When X, Y are connected, locally connected, and compact and f : X → Y is finiteto-one, closed, open, and continuous, the second condition (ii) is implied by the first; see [START_REF] Edmonds | Branched coverings and orbit maps[END_REF]Lemma 2.5].

The composition of fbc's is an fbc, and the degrees of fbc's multiply under compositions. In particular, local degrees of fbc's multiply under compositions.

Condition (ii) implies that if x n → x 0 , then deg(f ; Many arguments are done using pull-backs of sets and restricting to connected components. It is therefore necessary to work with fbc's defined on sets X and Y enjoying more properties. When X and Y , in addition to being locally compact and Hausdorff, are assumed locally connected, the following fundamental facts are known (cf. [Edm]).

x n ) ≤ deg(f ; x 0 ). It follows that the branch set B f = {x ∈ X : deg(f ; x) > 1} is closed. The set of branch values is defined as V f = f (B f ).
• If V ⊂ Y is open and connected, and U ⊂ X is a connected component of f -1 (V ), then f |U : U → V is an fbc as well.
• If y ∈ Y , and f -1 (y) = {x 1 , x 2 , . . . , x k }, then there exist arbitrarily small connected open neighborhoods V of y such that

f -1 (V ) = U 1 ⊔ U 2 ⊔ . . . ⊔ U k is a disjoint union of connected open neighborhoods U i of x i such that f |U i : U i → V is an fbc of degree deg(f ; x i ), i = 1, 2, . . . , k. • if f (x) = y, {V n } is sequence of nested open connected sets with ∩ n V n = {y}, and if V n is the component of f -1 (V n ) containing x, then ∩ n V n = {x}.

Topological cxc systems

In this section, we state the topological axioms underlying the definition of a cxc system. Let X 0 , X 1 be Hausdorff, locally compact, locally connected topological spaces, each with finitely many connected components. We further assume that X 1 is an open subset of X 0 and that X 1 is compact in X 0 . Note that this latter condition implies that if X 0 = X 1 , then X 0 is compact.

Let f : X 1 → X 0 be a finite branched covering map of degree d ≥ 2, and for n ≥ 0 put

X n+1 = f -1 (X n ).
Then f : X n+1 → X n is again an fbc of degree d and since f is proper, X n+1 is compact in X n , hence in X 0 . The nonescaping set, or repellor, of f :

X 1 → X 0 is X = {x ∈ X 1 |f n (x) ∈ X 1 ∀n > 0} = n X n .
We make the technical assumption that the restriction f |X : X → X is also an fbc of degree equal to d. This implies that #X ≥ 2. Also, X is totally invariant:

f -1 (X) = X = f (X).
The following is the essential ingredient in this work. Let U 0 be a finite cover of X by open, connected subsets of X 1 whose intersection with X is nonempty. A preimage of a connected set A is defined as a connected component of f -1 (A). Inductively, set U n+1 to be the open cover whose elements U are preimages of elements of U n . We denote by U = ∪ n≥0 U n the collection of all such open sets thus obtained. For U ∈ U, the level of U , denoted |U |, is the value of n for which U ∈ U n .

We say f : (X 1 , X) → (X 0 , X) is topologically coarse expanding conformal with repellor X (topologically cxc, for short) provided there exists a finite covering U 0 as above, such that the following axioms hold.

[Expans]

The mesh of the coverings U n tends to zero as n → ∞. That is, for any finite open cover Y of X by open sets of X 0 , there exists N such that for all n ≥ N and all U ∈ U n , there exists Y ∈ Y with U ⊂ Y .

2.

[Irred] The map f : X 1 → X 0 is locally eventually onto near X: for any x ∈ X and any neighborhood W of x in X 0 , there is some n with f n (W ) ⊃ X

[Deg]

The set of degrees of maps of the form

f k | U : U → U , where U ∈ U n , U ∈ U n+k ,
and n and k are arbitrary, has a finite maximum, denoted p.

Axiom [Expans] is equivalent to saying that, when X 0 is a metric space, the diameters of the elements of U n tend to zero as n → ∞.

The elements of U 0 will be referred to as level zero good open sets. While as subsets of X 0 they are assumed connected, their intersections with the repellor X need not be. Also, the elements of U, while connected, might nonetheless be quite complicated topologically-in particular they need not be contractible.

If X 0 = X 1 = X, then the elements of U are connected subsets of X.

Conjugacy. Suppose f : X 1 → X 0 and g : Y 1 → Y 0 are fbc's with repellors X, Y as in the definition of topologically cxc. A homeomorphism h :

X 0 → Y 0 is called a conjugacy if it makes the diagram (X 1 , X) h -→ (Y 1 , Y ) f ↓ ↓ g (X 0 , X) h -→ (Y 0 , Y ) commute.
(Strictly speaking, we should require only that h is defined near X; however, we will not need this more general point of view here.) It is clear that the property of being topologically cxc is closed under conjugation.

Metric cxc systems

In this section, we state the definition of metric cxc systems; we will henceforth drop the adjective, metric. Given a metric space, |a -b| denotes the distance between a and b, and B(a, r) denotes the open ball of radius r about a.

Roundness. Let Z be a metric space and let A be a bounded, proper subset of Z with nonempty interior. Given a ∈ int(A), define the outradius of A about a as

L(A, a) = sup{|a -b| : b ∈ A}
and the inradius of A about a as ℓ(A, a) = sup{r : r ≤ L(A, a) and B(a, r) ⊂ A}.

The condition r ≤ L(A, a) is necessary to guarantee that the outradius is at least the inradius. For instance, if A = {a} is an isolated point in Z, then

L(A, a) = 0 < sup{r : B(a, r) ⊂ A} = d(a, Z \ A) .
The outradius is intrinsic-it depends only on the restriction of the metric to A. In contrast, the inradius depends on how A sits in Z. The roundness of A about a is defined as

Round(A, a) = L(A, a)/ℓ(A, a) ∈ [1, ∞).
One says A is K-almost-round if Round(A, a) ≤ K for some a ∈ A, and this implies that for some s > 0,

B(a, s) ⊂ A ⊂ B(a, Ks).
Isometric open embeddings which are not surjective may distort roundness:

Example. Consider in R 2 the metric spaces X = R × {0} and Y = X ∪ ({0} × [c, ∞) ) for some constant c > 0.
Then the inclusion X ⊂ Y is an isometric and open embedding, and, for any interval (-r, r) × {0}, r > c, centered at the origin, its roundness at the origin in X is 1, but r/c in Y .

Metric cxc systems. Suppose we are given a topological cxc system f : X 1 → X 0 with level zero good neighborhoods U 0 , and that X 0 is now endowed with a metric compatible with its topology. The resulting metric dynamical system equipped with the covering U 0 is called coarse expanding conformal, abbreviated cxc, provided there exist ), the forward and backward roundness distortion functions, and

• continuous, increasing embeddings ρ ± : [1, ∞) → [1, ∞
• increasing homeomorphisms δ ± : R + → R + , the forward and backward relative diameter distortion functions satisfying the following axioms:

4.

[Round] (∀n, k) and for all

U ∈ U n , U ∈ U n+k , ỹ ∈ U , y ∈ U if f •k ( U ) = U, f •k (ỹ) = y
then the backward roundness bound

Round( U , ỹ) < ρ -(Round(U, y)) (1)
and the forward roundness bound

Round(U, y) < ρ + (Round( U , ỹ)).
(2) hold.

5.

[Diam] (∀n 0 , n 1 , k) and for all

U ∈ U n 0 , U ′ ∈ U n 1 , U ∈ U n 0 +k , U ′ ∈ U n 1 +k , U ′ ⊂ U , U ′ ⊂ U if f k ( U ) = U, f k ( U ′ ) = U ′ then diam U ′ diam U < δ - diamU ′ diamU and diamU ′ diamU < δ + diam U ′ diam U
For the Axiom [Diam], note that only the values smaller than 1 are relevant for δ ± . The Axiom [Expans] implies that the maximum diameters of the elements of U n tend to zero uniformly in n. Since U 0 is assumed finite, each covering U n is finite, so for each n there is a minimum diameter of an element of U n . By [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]Prop. 2.4.1], the space X is perfect, that is, contains no isolated points. By assumption, each U ∈ U contains a point of X. So, it contains many points of X, and so has positive diameter. Hence there exist decreasing positive sequences c n , d n → 0 such that the diameter bounds hold:

0 < c n ≤ inf U ∈Un diamU ≤ sup U ∈Un diamU ≤ d n .
(3)

Canonical gauge. A homeomorphism h between metric spaces (X, d X ) and (Y, d Y ) is called quasisymmetric provided there exists a homeomorphism η : [0, ∞) → [0, ∞) such that d X (x, a) ≤ td X (x, b) =⇒ d Y (h(x), h(a)) ≤ η(t)d Y (h(x), h(b))
for all triples of points x, a, b ∈ X and all t ≥ 0.

In [HP] the following results are proved.

Theorem 2.3 (Invariance of cxc) Suppose f : (X 1 , X) → (X 0 , X) and g : (Y 1 , Y ) → (Y 0 , Y
) are two topological cxc systems which are conjugate via a homeomorphism h : X 0 → Y 0 , where X 0 and Y 0 are metric spaces.

1. If f is metrically cxc and h is quasisymmetric, then g is metrically cxc, quantitatively.

2. If f, g are both metrically cxc, then h| X : X → Y is quasisymmetric, quantitatively.

The conformal gauge of a metric space (X, d X ) is the set of metric spaces quasisymmetric to X. The previous theorem shows that the gauge of X depends only on the conjugacy class of f : X 1 → X 0 . This is not quite intrinsic to the dynamics on X. However, if X 0 = X 1 = X then one has the following metrization theorem.

Theorem 2.4 (Canonical gauge) If f : X → X is a topological cxc map, where X 1 = X 0 = X, then there exists a unique conformal gauge on X defined by a metric d such that f : (X, d) → (X, d) is metric cxc.

The metric may be defined as follows (see [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]§3.1] for details). Suppose f : X 1 → X 0 is topologically cxc with respect to an open covering U 0 as in Theorem 2.4. Let U -1 be the open covering consisting of a single element, denoted o, defined as the union of the components of the interior of X 1 . Let Γ be the graph whose edges are the elements of U, together with the distinguished root vertex o. The set of edges is defined as a disjoint union of two types: horizontal edges join elements

U 1 , U 2 ∈ U n if and only if X ∩ U 1 ∩ U 2 = ∅, while vertical edges join elements U ∈ U n , V ∈ U n±1 at consecutive levels if and only if X ∩ U ∩ V = ∅.
There is a natural map F : Γ → Γ. Near the root o, it sends o to o, collapses vertical edges meeting o to o, sends each vertex U ∈ U 0 to o, collapses horizontal edges joining points of U 0 also to o, and send the edge between vertices (U 0 , U 1 ) ∈ U 0 × U 1 to the edge (o, f (U 1 )). At every other vertex, the map F is defined so that F (U ) = f (U ); it extends to a graph homomorphism on the subgraph spanned by vertices at level one and higher.

The usual graph-theoretic combinatorial distance d(, ) gives rise to a path metric on Γ such that edges are isometric to unit intervals.

One may define its compactification in the following way. Fix ε > 0. For x ∈ Γ let ̺ ε (x) = exp (-εd(o, x)). Define a new metric d ε on Γ by

d ε (x, y) = inf γ γ ̺ ε ds
where as usual the infimum is over all rectifiable curves in Γ joining x to y. The resulting metric space Γ ε is incomplete. Its complement in its completion defines the boundary ∂ ε Γ.

Since Γ is Gromov-hyperbolic [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]Thm 3.3.1], the metric d ε is a visual metric and the boundary ∂ ε Γ is the hyperbolic boundary as soon as ε is sufficiently small.

In that case, the boundary ∂ ε Γ coincides with the set of the classes of asymptotic geodesic rays (in the metric d) emanating from o, and is homeomorphic to X. More precisely, the natural map X → ∂ ε Γ given by φ(z) = lim U n (z) where z ∈ U n ∈ U n ⊂ Γ ε is well-defined and a homeomorphism conjugating f on X to the map on ∂ ε Γ induced by the cellular map F . The conformal gauge of the metric d ε defines the canonical gauge of f . We denote by B ε (x, r) the ball of radius r in the metric d ε . The metric d ε has the following properties ( [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]Prop. 3.2.2,3.2.3]):

• F k (B ε (x, r)) = B ε (F k (x)
, exp(kε)r) if r is sufficiently small, and

• if F k | Bε(x,4r) is injective, then f k | Bε(x,r
) is a similarity with factor exp(kε).

Maps of metric finite type

A random cxc system may appear rather inhomogeneous: for example, one may conjugate z → z 2 on the standard Euclidean circle S 1 with a horrible quasisymmetric map which is the identity off a neighborhood of the preperiodic point -1. In many cases, however, one finds an extra degree of homogeneity present in a cxc system.

Quasisimilarities. We will find the concept of quasisimilarity useful for capturing the notion that a family of maps is nearly a collection of similarities.

Definition 2.5 (Quasisimilarity) Let h : X → Y be a homeomorphism between metric spaces. We say that h is a C-quasisimilarity if there is some constant λ > 0 such that

1 C ≤ |h(a) -h(b)| λ|a -b| ≤ C
for all a, b ∈ X. A family H of homeomorphisms (perhaps defined on different spaces) consists of uniform quasisimilarities if there exists a constant C (independent of h) such that each h ∈ H is a C-quasisimilarity.

We will speak of (C, λ)-quasisimilarity if we want to emphasise the constant λ.

Example. Fix 0 < r < 1. If f : ∆ → C is an analytic function which is injective on the unit disk ∆, then the Koebe distortion principle implies that the restriction of f to any smaller disk {z : |z| < r} is a (C r , λ)-quasisimilarity, where λ = |f ′ (0)| and C r is independent of f .

One establishes easily:

1. If λ = (1/C ′ )λ ′ then a (C, λ)-quasisimilarity is also a (CC ′ , λ ′ )-quasisimilarity.
2. The inverse of a (C, λ)-quasisimilarity is a (C, 1/λ)-quasisimilarity.

3. A (C, λ)-quasisimilarity distorts ratios of diameters by at most the factor C 2 .

Definition 2.6 (Dynatlas) A dynatlas is a finite set M whose elements, called local model maps, are fbc's g : V → V , where V , V are locally compact, connected metric spaces of diameter 1. Given m ∈ M, the corresponding local model map is denoted Definition 2.7 (metric finite type) Let f : (X 1 , X) → (X 0 , X) be an fbc, and suppose X 0 is equipped with a metric compatible with its topology. Let U 0 be a finite covering of X by open connected subsets of X 1 , and let U = {U n } be the sequence of coverings obtained by pulling back U 0 under iterates of f . We say f : (X 1 , X) → (X 0 , X) is metric finite type with respect to U 0 if the axioms [Expans] and [Irred] hold, and if there exists a dynatlas (V, M) and a constant C ≥ 1 with the following properties:

g m : V m → V m . The sets V m , V m , m ∈ M,
1. ∀U ∈ U, there exists V ∈ V and a C-quasisimilarity ψ U : U → V , 2. every V ∈ V arises in this way-that is, ∀V ∈ V, there exists U ∈ U and a Cquasisimilarity ψ U : U → V .

3. Whenever U , U ∈ U and f k : U → U , the map

g U ,U := ψ U • f k | U • ψ -1 U ∈ M.
We may think of the set of maps ψ U as a set of "local coordinate charts" which comprise a family of uniform C-quasisimilarities. The property of being metric finite type may then be characterized as follows: up to quasisimilarity, there are only finitely many local models for the dynamics over the elements of the finite good cover U 0 . The second condition is a convenient minimality assumption: if a dynatlas satisfies the first and third, then by removing extraneous elements, it will satisfy the second.

The property of being metric finite type is not invariant under quasisymmetric conjugacies.

Theorem 2.8 (metric finite type implies cxc) If f : X 1 → X 0 is of metric finite type with respect to U 0 , then it is metric coarse expanding conformal with respect to U n 1 for some n 1 ≥ 0.

The proof, which occupies the remainder of this subsection, is essentially straightforward except for one subtlety. Since roundness is not an intrinsic quantity, care must be taken to show that the non-surjective embeddings ψ -1 do not distort roundness too much.

We first establish some properties of quasisimilarity embeddings, that is, maps which are quasisimilarities onto their images.

Properties of quasisimilarities. We assume here that V , Z are connected metric spaces, Z is complete and ψ : V → Z is a (C, λ)-quasisimilarity embedding with ψ(V ) = U open, and V bounded.

The following is easily verified: Proposition 2.9

1. Both ψ and ψ -1 extend as a quasisimilarity between the completion of V and the closure of U .

For any open subsets

W 1 , W 2 ⊂ V , 1 C 2 diamW 1 diamW 2 ≤ diamψ(W 1 ) diamψ(W 2 ) ≤ C 2 • diamW 1 diamW 2 .
3. If ψ is onto, then for W ⊂ V and x ∈ W ,

Round(ψ(W ), ψ(x)) ≤ C 2 Round(W, x) .
Next, we establish roundness distortion bounds for open embeddings which need not be onto.

Proposition 2.10 Let W ⊂ V and x ∈ W . The following hold

1. If diamW ≤ (1/2C 2 )diamV , then Round(ψ(W ), ψ(x)) ≤ max{C 2 Round(W, x), Round(U, ψ(x))} . 2. If Round(U, ψ(x)) ≤ R and diamW ≤ (1/2RC 2 )diamV , then Round(ψ(W ), ψ(x)) ≤ C 2 Round(W, x) .

Proof:

1. The definition of roundness implies that

Round(ψ(W ), ψ(x)) ≤ diamψ(W ) ℓ Z (ψ(W ), ψ(x))
.

Since ψ is a (C, λ)-quasisimilarity and B(x, ℓ V (W, x)) ⊂ W , we have (recalling

U = ψ(V )) that B ψ(x), λℓ V (W, x) C ∩ U ⊂ ψ(W ) .
Recall that by definition, B(ψ(x), ℓ Z (U, ψ(x))) ⊂ U .

We now consider two cases. If on the one hand ℓ Z (U, ψ(x)) ≤ λℓ V (W, x)/C, then

B(ψ(x), ℓ Z (U, ψ(x))) = B(ψ(x), ℓ Z (U, ψ(x))) ∩ U ⊂ ψ(W ) which implies ℓ Z (ψ(W ), ψ(x)) = ℓ Z (U, ψ(x)) .
But L Z (ψ(W ), ψ(x)) ≤ diamψ(W ) and by assumption diamψ(W ) ≤ (1/2)diamU , so

Round(ψ(W ), ψ(x)) ≤ diamU 2ℓ Z (U, ψ(x)) ≤ Round(U, ψ(x)) . If on the other hand ℓ Z (U, ψ(x)) ≥ λℓ V (W, x)/C, then B ψ(x), λℓ V (W, x) C ⊂ U
and so Round(ψ(W ), ψ(x)) ≤ C 2 Round(W, x) .

2. Since Round(U, ψ(x)) ≤ R, it follows that

ℓ Z (U, ψ(x)) ≥ L Z (U, ψ(x)) R ≥ diamU 2R ≥ λdiamV 2RC . But diamW ≤ (1/2RC 2 )diamV so that diamψ(W ) ≤ λCdiamW ≤ λdiamV 2RC ≤ ℓ Z (U, ψ(x)) .
Therefore,

ψ(W ) ⊂ B(ψ(x), ℓ Z (U, ψ(x))) ⊂ U
and (1) above implies Round(ψ(W ), ψ(x)) ≤ C 2 Round(W, x) .

We now assume that we are given dynamical system f : (X 1 , X) → (X 0 , X) of metric finite type.

Diameter bounds. Since all model maps appear in the dynamics of f , it follows that they are all uniformly continuous. Since the set M is finite, there exists a common modulus of continuity function δ+ : this is a self-homeomorphism of R + such that, given m ∈ M, any

x, y ∈ V m , |g m (x) -g m (y)| ≤ δ+ (|x -y|) .
Define the function δ-: [0, 1] → R + as follows. Given m ∈ M, W ⊂ V m , we let presize(W ) = max diam W where the supremum ranges over all connected components of

g -1 m (W ). For r ∈ [0, 1], set δ-(r) = max m∈M sup{presize(W ), W ⊂ V m , diamW ≤ r} .
By taking its upper hull, we may assume that δis a homeomorphism on its image, and we may extend it to be a homeomorphism of R + as well.

For future use, we note that, since our maps are open, there exists a positive increasing function ρ such that, for any m ∈ M, for any x ∈ V m , and any r < 1, g m (B(x, r)) contains the ball B(g m (x), ρ(r)). Indeed, we may use representatives given by appropriate restrictions of iterates of f : there is some n 0 such that every model map appears, up to a C-quasisimilarity, as f k : U → U , with U , U ∈ ∪ 0≤j≤n 0 U j , 1 ≤ k ≤ n 0 . Since f and its iterates are open maps, for each x ∈ X, r > 0 and n ≥ 1, there is some ρ = ρ(x, r, n) such that f n (B(x, r)) ⊃ B(f n (x), ρ). We then get a uniform bound ρ(r) independent of x and n by compactness of X and the finiteness of iterates to be considered.

Proposition 2.11 The map f satisfies the axiom [Diam] with

δ ± (r) = C 2 δ± (C 2 r) . Proof: Let n ≥ 0, k > 0, U ∈ U n+k and U = f k ( U ) ∈ U n . By definition of metric finite type, one can find m ∈ M such that U f k -→ U ψ ↓ ↓ ψ V g -→ V
where we have dropped the indices. Now suppose W ⊂ U and W = f k ( W ). Then since diamV = diam V = 1 and ψ and ψ distort ratios of diameters by at most a factor of C

2 , diamW diamU ≤ C 2 diamψ(W ) ≤ C 2 δ+ (diam ψ( W )) ≤ C 2 δ+ C 2 diam W diam U . Similarly, if W is a connected component of a connected set W ⊂ U , then diam W diam U ≤ C 2 diam ψ( W ) ≤ C 2 δ-(diamψ(W )) ≤ C 2 δ-C 2 diamW diamU .
By definition of δ± , δ ± are homeomorphisms of R + .

Roundness bounds for model maps. We assume that g :

V → V is a model map, W is a connected subset of V , W is a component of g -1 (W )
, and x ∈ W . We write x = g(x).

Lemma 2.12 Under these notations, the following hold.

1. If Round( W , x) ≤ K and diam W ≥ c > 0, then ℓ V (W, x) ≥ ρ(c/2K) . 2. If Round(W, x) ≤ K and diamW ≥ c > 0, then ℓ V ( W , x) ≥ δ-1 + (c/2K) .
Since model sets have diameter 1, roundness bounds follow at once.

Proof: 1. The definition of roundness and the hypothesis imply B x, diam W

2K

⊂ W .

Applying the model map g, we find B x,

ρ diam W 2K ⊂ W . Thus, ℓ V (W, x) ≥ ρ(c/2K) . 2. Similarly, B x, diamW 2K ⊂ W . Hence B x, δ-1 + diamW 2K ⊂ W and so ℓ V ( W , x) ≥ δ-1 + ((1/2K)diamW ) ≥ δ-1 + (c/2K) .
Roundness distortion. Recall that by the diameter bounds (3), there are decreasing positive sequences c n , d n such that

0 < c n ≤ inf U ∈Un diamU ≤ sup U ∈Un diamU ≤ d n .
Recall that the Lebesgue number of an open cover U of a compact metric space is the largest δ > 0 such that every subset of diameter δ is contained in an element of U . Let δ 0 denote the Lebesgue number of the covering U 0 . Since X is perfect, each ball B(x, r), x ∈ X, r > 0 has positive diameter. Fix r 0 < δ 0 /2 and cover X by balls of radius r 0 . Extracting a finite subcover we conclude that for some positive constant q 0 , every ball of radius r 0 has diameter at least 2q 0 . Set K 0 = d 0 /q 0 . It follows that for any x ∈ X, one can find

U 0 (x) ∈ U 0 such that Round(U 0 (x), x) ≤ K 0 . Define U n (x) ∈ U n to be the component of f -n (U 0 (f n (x))) which contains x.
Our first result says that by dropping down some uniform number of levels, every pair (x, U ), x ∈ U, U ∈ U, is contained "deep inside" a larger set in U.

Proposition 2.13

1. There is some n 0 such that, for any

n, k ≥ 0, if x ∈ U ∈ U n 0 +n+k , then U has compact closure in U n (x).
2. There is a constant R ≥ 1 such that, for any x ∈ X and any n ≥ 0, Round(U n (x), x) ≤ R.

Proof: We fix n 0 large enough so that, for n ≥ n 0 ,

d n ≤ c 0 min 1 3K 0 , δ-1 -(1/2C 2 ) C 2 . 1. It follows from d n ≤ c 0 3K 0 that if n ≥ n 0 , W ∈ U n and x ∈ W then W ⊂ U 0 (x).
To see this, notice that on the one hand, for any x ∈ X,

ℓ(U 0 (x), x) ≥ diamU 0 (x) 2K 0 ≥ c 0 2K 0 which implies B x, c 0 2K 0 ⊂ U 0 (x),
and on the other hand

W ⊂ B x, c 0 3K 0 ⊂ B(x, c 0 3K 0 ) ⊂ B(x, c 0 2K 0 ) ⊂ U 0 (x) . Therefore, for n, k ≥ 0, if x ∈ U ∈ U n 0 +n+k , then f n (U ) ∈ U n 0 +k so that f n (U ) ⊂ U 0 (f n (x)) . It follows that U ⊂ U n (x) since f n : U n (x) → U 0 (f n (x)) is proper. 2. By construction, for each x ∈ X, we have B(x, c 0 /K 0 ) ⊂ U 0 (x). The finite set of maps {f, f •2 , . . . , f •(2n 0 -1)
} is uniformly equicontinuous, so there exists r 0 > 0 such that for each x ∈ X and each n ∈ {1, . . . , 2n 0 -1}, we have

f n (B(x, r 0 )) ⊂ B(f n (x), c 0 /K 0 ). It follows that Round(U n (x), x) ≤ K 1 where K 1 = r 0 /c 2n 0 -1 .
Let 0 ≤ ℓ ≤ n 0 -1 and j ≥ 1. We consider the model map given in the following diagram

U jn 0 (x) f jn 0 -→ U 0 (f jn 0 (x)) ψ ↓ ↓ ψ V g -→ V It follows from the point above that U n 0 +ℓ (f jn 0 (x)) ⊂ U 0 (f jn 0 (x)) and U (j+1)n 0 +ℓ (x) ⊂ U jn 0 (x).
Since the maps ψ are uniform quasisimilarities which are onto,

Round(ψ(U n 0 +ℓ (f jn 0 (x))), ψ(f jn 0 (x))) ≤ C 2 K 1 and diamψ(U n 0 +ℓ (f jn 0 (x))) ≥ 1 C 2 diamU n 0 +ℓ (f jn 0 (x)) diamU 0 (f jn 0 (x)) ≥ 1 C 2 c 2n 0 d 0 .
From Lemma 2.12 and the fact that diam V = 1, it follows that

Round( ψ(U (j+1)n 0 +ℓ (x)), ψ(x)) ≤ K 2 := 1 δ-1 + c 2n 0 2C 2 d 0 K 1 .
But by the definition of δand n 0 ,

diam ψ(U (j+1)n 0 +ℓ (x)) ≤ δ-C 2 d n 0 c 0 ≤ 1 2C 2 ,
so that Proposition 2.10 (1) (applied to ψ -1 and remembering diamV = 1) implies

Round(U (j+1)n 0 +ℓ (x), x) ≤ max{C 2 K 2 , Round(U jn 0 (x), x)} . But since Round(U n 0 (x), x) ≤ K 1 , it follows by induction that for any n ≥ n 0 , Round(U n (x), x) ≤ max{C 2 K 2 , K 1 } . Letting R = max{C 2 K 2 , K 1 , K 0 }, it follows that, for any x ∈ X and n ≥ 0, Round(U n (x), x) ≤ R .
We may now deduce the roundness bounds for n large enough: Proposition 2.14 Let n 0 and R be the constants provided by Proposition 2.13. There is some n 1 ≥ n 0 with the following properties.

Let n ≥ n 1 , k ≥ 1, U ∈ U n+k , x ∈ U , x = f k (x) and U = f k ( U ). Let c = 1 C 2 δ -1 + c n 1 d 0 . 1. If Round( U , x) ≤ K then Round(U, x) ≤ 1 2Rρ c 2K . 2. If Round(U, x) ≤ K then Round( U , x) ≤ 1 2R δ-1 + c 2K . Proof: Choose n 1 ≥ n 0 so that d n 1 ≤ c 0 C 2 δ-1 - 1 2C 2 R .
Set m = nn 1 and let U m+k (x) and U m (x) be the neighborhoods provided by Proposition 2.13(1), so that U ⊂ U m (x) and U ⊂ U m+k (x). Let us consider the model map

U m+k (x) f k -→ U m (x) ψ ↓ ↓ ψ V g -→ V
Note that n 1 is the difference in levels between U , U and their corresponding supersets

U m+k (x), U m (x).
Let us for the time being consider the dynchart

U ⊂ U m (x) f m -→ f m U m (x) = U 0 ⊃ f m (U ) ψ ↓ ↓ ψ 0 V g -→ V 0
Since the quasisimilarity ψ 0 distorts ratios of diameters by at most the factor C 2 and diamV

0 = diamV = 1, diamψ 0 (f m (U )) ≤ C 2 diamf m (U ) diamU 0 ≤ C 2 d n 1 c 0
and so, by the definition of δ-, we have

diamψ(U ) ≤ δ-C 2 d n 1 c 0 ≤ 1 2C 2 R (4)
where the last inequality follows by our choice of n 1 . By Proposition 2.11, one also finds

diamU diamU m (x) ≥ δ -1 + c n 1 d 0 .
The same argument applied to ( U , U m+k (x)) yields

diam ψ( U ) ≤ 1 2C 2 R and diam U diamU m+k (x) ≥ δ -1 + c n 1 d 0 . 1. If Round( U , x) ≤ K then since ψ is a surjective quasisimilarity, Round( ψ( U ), ψ(x)) ≤ C 2 K
and, by Lemma 2.12 (with K replaced with

C 2 K), ℓ V (ψ(U ), ψ(x)) ≥ ρ 1 2KC 2 δ -1 + c n 1 d 0 ≥ ρ c 2K . But since diamψ(U ) ≤ 1 2C 2 R ,
Proposition 2.10, (2) and inequality(4) imply that

Round(U, x) ≤ C 2 diamψ(U ) ℓ V (ψ(U ), ψ(x)) ≤ 1 2Rρ c 2K . 2. Similarly, if Round(U, x) ≤ K then Round(ψ(U ), ψ(x)) ≤ C 2 K,
and, by Lemma 2.12,

ℓ V ( ψ( U ), ψ(x)) ≥ δ-1 + 1 2KC 2 δ -1 + c n 1 d 0 ≥ δ-1 + c 2K But since diam ψ( U ) ≤ 1 2C 2 R , it follows that Round( U , x) ≤ 1 2R δ-1 + c 2K
.

Proof of Theorem 2.8: Let us first note that a map of metric finite type is topological cxc if the axiom [Deg] holds. But this axiom follows from the fact that M is a finite set.

The axiom [Diam] is given by Proposition 2.11, and the roundness control holds as soon as sets of level at least n 1 are considered, by Proposition 2.14.

3 Examples of metric finite type systems

Expanding maps on manifolds

If X is metric space, and f : X → X is continuous, we say that f is expanding if, for any x ∈ X, there is a neighborhood U of x such that, for any distinct y, z ∈ U , one has

|f (y) -f (z)| > |y -z|; cf. [Gro2, § 1].
We first recall the statement of [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]Thm 4.5.1] from which we will deduce that expanding maps are metric finite type.

Theorem 3.1 (From expanding to homothety) Let f : M → M be an expanding map of a compact connected Riemannian manifold to itself. Then there exists a distance function d on M and constants δ > 0 and ρ > 1 such that for all x, y ∈ M ,

d(x, y) < δ =⇒ d(f (x), f (y)) = ρ • d(x, y)
and such that balls of radius ≤ δ are connected and contractible.

Corollary 3.2 (Expanding implies metric finite type) The dynamical system ((M, d), f ) is metric finite type, hence cxc.

This refines Corollary 4.5.2 of [HP], which asserts that ((M, d), f ) is merely cxc.

Proof of Corollary 3.2: We remark that f : M → M is necessarily a covering map of degree D = deg f . Let U 0 be a finite open cover of M by open balls of radius δ. If U ∈ U then since U is contractible we have f -n (U ) = D n 1 U i
where the union is disjoint and where each f n | U i : U i → U is a homeomorphism which multiplies distances by exactly the factor ρ n . In the definition of metric finite type, let V = U 0 , and take the model maps all to be the identity maps. Given U ∈ U n we let 3) in the definition of metric finite type hold. Verification of axioms [Expans] and [Irred] are straightforward (details are in [HP]).

ψ U : U → U = f n ( U ). Then if f k : U → U we see that g U ,U = id U by construction. Since each chart ψ U is a similarity, it follows that conditions (1)-(

Subhyperbolic rational maps

A rational map f : C → C is subhyperbolic if it has neither critical points in the Julia set with infinite forward orbit, nor parabolic cycles. Equivalently, under iteration, each critical point either converges to or lands in an attracting cycle, or lands in a repelling periodic cycle. We begin by proving Theorem 3.3 (Subhyperbolic implies metric finite type) Let f be a subhyperbolic rational map with Julia set J. Then there are closed neighborhoods X 0 , X 1 of J in the sphere such that f : X 1 → X 0 is metric finite type with repellor J, with good open sets given by a finite collection U 0 of open spherical balls.

Before proceeding, we collect a few facts and concepts from the theory of univalent functions.

Distortion principles. Let ∆ s = {z ∈ C : |z| < s} and ∆ = ∆ 1 . We will need Lemma 3.4 For all s > 1 and small ρ > 0, there exists a constant C(s, ρ) > 1 such that if ψ : ∆ s → C is any holomorphic embedding whose image omits a spherical disk of radius ρ, then ψ|∆ is a (C(s, ρ), λ)-quasisimilarity (with respect to the Euclidean metric on ∆ and the spherical metric on ψ(∆)), where λ = |ψ ′ (0)|.

Proof: By composing with a spherical isometry we may assume the image lies in the Euclidean disk about the origin of radius R = R(ρ). On such a disk the Euclidean and spherical metrics are comparable, with constant depending only on R. The lemma then follows from the usual Koebe principle.

Concentric disks. We will also need the following concept. Suppose

x ∈ U ⊂ W
where U, W are conformally isomorphic to disks. We say that (W, U, x) is concentric if the triple (W, U, x) is holomorphically isomorphic to the triple (∆ s , ∆, 0) for some s > 1, i.e.

there exists a conformal isomorphism sending W → ∆ s , U → ∆, and x → 0. We denote by f : ( W , U , x) → (W, U, x) a proper holomorphic map f : W → W with the property that U = f -1 (U ) where U and U are disks, x ∈ U , x ∈ U , f , if ramified, is branched only at x, and

f (x) = x. If (W, U, x) is concentric and f : ( W , U , x) → (W, U, x)
then ( W , U , x) is also concentric.

Proof of Theorem 3.3: We begin by choosing carefully the covering U 0 . Since f is subhyperbolic, there exists a neighborhood X 0 of J such that

X 0 ∩ P f = {x i } p i=1 is a subset of J and X 1 = f -1 (X 0 ) is relatively compact in X 0 .
Choose r > 0 sufficiently small such that B(x, 3r/2) ⊂ X 1 for all x ∈ J, and B(x i , 3r/2)

∩ P f = {x i }, 1 ≤ i ≤ p. Let W i = B(x i , 3r/2) and U i = B(x i , r). Since J ′ = J -∪ i B(x i , r) is compact, there exist finitely many points x i ∈ J ′ , p + 1 ≤ i ≤ p ′ such that the collection U i = B(x i , r/2), i = p + 1, . . . , p ′ covers J ′ .
A simple comparison of the spherical and Euclidean metrics yields the existence of some radius r ′ ∈ (r/2, (3/4)r) such that the triples (B(0, r ′ ), B(0, r/2), 0) and (B(0, (3/2)r), B(0, r), 0) are isomorphic. Then by construction, if

W i = B(x i , r ′ ), i = p + 1, . . . , p ′ , we have that the collection {(W i , U i , x i )} 1≤i≤p ′ consists of isomorphic concentric triples such that U 0 = {U i } is a covering of J. Moreover, P f ∩W i = {x i } for 1 ≤ i ≤ p and is otherwise empty.
We call (W i , U i , x i ) a triple at level zero and drop the subscripts in what follows. A triple at level n consists of a component W of f -n (W ), a component U of f -n contained in W , and a preimage x ∈ f -n (x) ∩ U , where (W, U, x) is a triple at level zero. By construction, triples ( W , U , x) at level n are concentric, since f n | W is possibly ramified only at x. We set U n to be the elements U occuring in triples ( W , U , x) at level n. The degree D of a triple ( W , U , x) at level n is defined to be the degree of f n | W , and we let D ⊂ N denote the set of such degrees. Since f is subhyperbolic, D is finite.

The triples at level zero are all conformally isomorphic and concentric. Hence, there is s > 1 such that for any triple (W, U, x) at level zero, there exists a Riemann map to a fixed triple

ϕ W : (W, U, x) → (∆ s , ∆, 0)
which is unique up to postcomposition by a rotation about the origin. For each triple at level zero, we make such a choice arbitrarily. Given ( W , U , x) a triple at level n of degree D, let

ψ W : ( W , U , x) → (∆ s 1/D , ∆, 0)
be the conformal isomorphism given by

ψ W = ϕ W • f n | W 1/D
where the principal branch of root is used, and set ψ U = ψ W | U ; these will be the maps as in the definition of metric finite type. We now verify the conditions in the definition. If

f k : ( W , U , x) → (W, U, x)
sends a triple at level n + k of degree D to one at level n of degree D, then

ψ -1 U • f k • ψ U : (∆, 0) → (∆, 0) is just z → z m
, where m = D/D. Thus, the set of model maps is just the set of maps of the unit disk to itself given by g m (z) = z m , where m ranges over the set M of all local degrees of iterates of f at points in the Julia set. Since D is finite, M is finite as well.

The spherical diameters of the sets W arising in triples at level n tend to zero uniformly, in fact, exponentially, in n (cf. [Ste], Lemma 5.1.4.) Thus, for any triple (W, U, x) at any level, the set W omits a disk of some definite spherical radius ρ. Lemma 3.4 and the finiteness of the set of radii s 1/D , D ∈ D, then implies that

ψ U : ∆ → C, U ∈ n U n
is a family of uniform quasisimilarities, and the proof is complete.

We now provide a converse statement.

Theorem 3.5 Suppose f : S 2 → S 2 is orientation-preserving and metric finite type with respect to the standard spherical metric. Then f is quasisymmetrically, hence quasiconformally equivalent to a postcritically finite rational map whose Julia set is the whole sphere.

Proof: Theorem 2.8 implies that f is cxc with respect to the standard spherical metric, and Theorem 4.2.7 in [HP] implies that f is qs, hence qc conjugate to a semihyperbolic rational map. Theorem 3.13 (see below) implies that P f is finite.

Topologically finite type

The constructions in the proof of Theorem 2.4, combined with those of the proof of Theorem 3.3, yield a metrization result for a certain class of topological dynamical systems, which we now define precisely. Since we wish the gauge of the constructed metric to depend only on the topological dynamics, we assume X 0 = X 1 = X.

Topologically finite type dynamics. Let f : X → X be a finite branched covering with repellor X as in §2.2. Let U 0 be an open cover of X by connected subsets of X. An iterate over U 0 is a map of the form f k : U → U where U ∈ U n+k and U ∈ U n for some n and k. Definition 3.6 Elements U 1 , U 2 ∈ U are said to be orbit isomorphic provided there exists U ∈ U, k 1 , k 2 ∈ N, and a homeomorphism ψ :

U 1 → U 2 such that f k i : U i → U, i = 1, 2 and f k 2 • ψ = f k 1 . The map ψ is called an orbit isomorphism. For example, if f ℓ : U 1 → U 2 is a homeomorphism, then U 1 and U 2 are orbit isomor- phic. Similarly, if f k i : U i → U, i = 1, 2 are homeomorphisms, then U 1 and U 2 are orbit isomorphic. Recall that |U | = n means that U ∈ U n .
It is easily verified that in the definition of orbit isomorphism, one may replace U with f |U | (U ) ∈ U 0 i.e., one may assume that U ∈ U 0 . It follows easily that the relation of being orbit isomorphic is an equivalence relation. By definition, distinct elements of U 0 are never orbit isomorphic.

The proof of the following lemma is straightforward.

Lemma 3.7 If ψ : U 1 → U 2 is an orbit isomorphism and U ′ 1 ∈ U is a subset of U 1 , then U ′ 2 = ψ(U ′ 1 ) ∈ U and |U ′ 2 | -|U 2 | = |U ′ 1 | -|U 1 |. Definition 3.8 (Orbit isomorphism of iterates) Two iterates f k 1 : U 1 → U 1 and f k 2 : U 2 → U 2 over U 0 are orbit isomorphic if there exist orbit isomorphisms ψ : U 1 → U 2 and ψ : U 1 → U 2 such that the diagram U 1 ψ -→ U 2 f k 1 ↓ ↓ f k 2 U 1 ψ -→ U 2 commutes.
Definition 3.9 (Topologically finite type) The map f is said to be topologically finite type with respect to U 0 if it satisfies Axioms [Expans] and [Irred], and if in addition there are only finitely many orbit isomorphism types of iterates over U 0 .

For example, if f is a hyperbolic rational map with connected Julia set X and U 0 consists of open sets not separating P f , then f has exactly #U 0 isomorphism types of iterates and so is topologically finite type with respect to U 0 . If f is merely subhyperbolic, then it is topologically finite type with respect to the open covering U 0 defined in the proof of Theorem 3.3.

The following is the main result of this section.

Theorem 3.10 (Topological implies metric finite type) If f : X → X is topologically finite type with respect to U 0 , then when X is equipped with metric d ε constructed in §2.3, f is metric finite type, and the constant C in the definition of metric finite type can be taken to be 1.

Corollary 3.11 Let f : S 2 → S 2 be a postcritically finite Thurston map which is topologically cxc with respect to an open covering U 0 . Then in the metric d ε , f is metric finite type, and up to similarity, there are only finitely many possibilities for the sets U ∈ U.

In §3.5 we will discuss the implications of this corollary for finite subdivision rules. The proof will rest on the following observation. Recall that |x-y| ε denotes the distance between x and y in the metric d ε .

Proposition 3.12 Suppose ψ :

U 1 → U 2 is an orbit isomorphism and B ε (u, r) ⊂ U 1 . Let λ = exp(ε(|U 1 | -|U 2 |)). Then for all x, y ∈ B ε (u, r), |ψ(x) -ψ(y)| ε = λ|x -y| ε . In particular, ψ(B ε (u, r)) = B ε (ψ(u), λr)
and ψ| Bε(u,r) is a (1, λ)-quasisimilarity.

Proof: Let x 1 = x, y 1 = y, x 2 = ψ(x 1 ), y 2 = ψ(y 1 ). The points x 1 , y 1 lie in Γ ε , which is a complete length space. So there is a geodesic γ 1 : [0, L] → Γ ε joining x 1 and y 1 . By reparameterizing γ 1 as γ 1 : R → Γ, we may assume γ 1 (Z) ⊂ U (the vertex set of Γ), that lim t→-∞ = x 1 , and that lim t→+∞ γ 1 (t) = y 1 . By [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]Lemma 3.3.4],

n∈Z γ(n) ⊂ B ε (u, r) ⊂ U 1 . Since ψ is an orbit isomorphism, ψ(γ 1 (n)) ∈ U for all n ∈ Z. Moreover, γ 1 (n) ∩ γ 1 (n + 1) = ∅ =⇒ ψ(γ 1 (n)) ∩ ψ(γ 1 (n + 1)) = ∅.
Lemma 3.7 implies that there exists γ 2 : Z → Γ given by γ 2 (n) = ψ(γ 1 (n)) and such that |γ

1 (n)| -|γ 2 (n)| = |U 1 | -|U 2 |. Moreover, γ 2 extends to a curve γ 2 : R → Γ such that for all n ∈ Z, γ 2 | [n,n+1] traverses a closed edge exactly once. Thus |x 2 -y 2 | ε ≤ γ 2 ̺ ε ds = λ γ 1 ̺ ε ds = λ|x 1 -y 1 | ε .
Hence B ε (ψ(u), λr) ⊂ U 2 . By considering ψ -1 and applying the same argument we conclude

|x 1 -y 1 | ε ≤ λ -1 |x 2 -y 2 | ε . Hence λ|x 1 -y 1 | ε ≤ λ • λ -1 |x 2 -y 2 | ε ≤ λ|x 1 -y 1 | ε so equality holds throughout.
Proof of Theorem 3.10: By [HP], Prop. 3.3.2(1), there exists an integer l > 0 with the following property. For any U ∈ U with |U | sufficiently large, there exists a ball B and

U ∈ U such that U ⊂ B ⊂ U and |U | -| U | = l.
The set U will play a role in this proof similar to that played by the set denoted W in the proof of Theorem 3.3: it will provide some "Koebe space"; the control of distortion will be provided here by Proposition 3.12.

In what follows, we assume that for each U ∈ U, a choice of such larger U ⊃ U has been made; we refer to the couple ( U , U ) as a pair. An orbit isomorphism of pairs is an orbit isomorphism ψ :

U 1 → U 2 such that the restriction ψ| U 1 : U 1 → U 2 is also an orbit isomorphism; in this case ψ : ( U 1 , U 1 ) → ( U 2 , U 2 ) is a map of pairs. An iterate of pairs is a map of pairs f k : ( U , U ) → ( U , U ). Two iterates of pairs f k 1 : ( U 1 , U 1 ) → ( U 1 , U 1 ) and f k 2 : ( U 2 , U 2 ) → ( U 2 , U 2 ) are orbit isomorphic provided there are orbit isomorphisms ψ : ( U 1 , U 1 ) → ( U 2 , U 2 ) and ψ : ( U 1 , U 1 ) → ( U 2 , U 2 ) such that the diagram ( U 1 , U 1 ) ψ -→ ( U 2 , U 2 ) f k 1 ↓ ↓ f k 2 ( U 1 , U 1 ) ψ -→ ( U 2 , U 2 )
commutes. Now suppose f : X → X is topologically finite type with respect to U 0 . It follows immediately that Axiom [Deg] holds, and consequently, that the graph Γ defined with respect to the open covering U 0 is uniformly locally finite. It follows that in Γ defined with the standard graph metric which makes each edge isometric to [0, 1], the ball of radius l about a given vertex corresponding to a set U contains at most finitely many, say T , vertices corresponding to sets U . Since the number of isomorphism classes of iterates f k : U → U is finite, the number of isomorphism classes of iterates of pairs f k : ( U , U ) → ( U , U ) is at most T times this number, hence is also finite.

Let M be an index set enumerating the isomorphism classes of iterates of pairs, so that each iterate of pairs is orbit isomorphic via isomorphisms ψ, ψ to a map of the form

g m : ( V m , V m ) → ( V m , V m ), m ∈ M.
By Proposition 3.12 and the construction of the neighborhoods U , in the metric d ε , the maps ψ, ψ are similarities when restricted to U , U , respectively. Hence, in the metric d ε , the set of maps {g m | V : V → V } m∈M form a dynatlas, and so f : X → X is metric finite type.

Proof of Corollary 3.11: Suppose f : S 2 → S 2 is a topologically cxc Thurston map. Axiom [Deg] implies in particular that f does not have periodic critical points. Choose U 0 to be any collection of open disks U such that, if the closure of U meets P f , then it does so in at most one point, and this point lies in U . It follows easily as in the proof of Theorem 3.3 that there are only finitely many orbit isomorphism types of iterates over U 0 . The Corollary then follows by Theorem 3.10.

Maps of finite type on a surface

When X 0 = X 1 = X is a compact surface without boundary, the possibilities for a finite type map are greatly restricted.

Theorem 3.13 Suppose f : X → X is topologically finite type, where X is a surface without boundary. Then either X is a torus or Klein bottle and f is an unramified covering map, or X = S 2 or RP 2 and the postcritical set P f is finite.

For a surface with boundary, the branch set of a topologically finite type map can be infinite: -2, 2]; as U 0 one may take slightly thickened neighborhoods of the four corner squares of side length two.

if f : [-2, 2] → [-2, 2] is the map f (x) = x 2 -2, then f × f is topologically finite type on [-2, 2] × [
Proof: The Riemann-Hurwitz formula implies that the possibilities for X are those given in the statement, and that f is unramified in the genus one case.

Let M be a finite set indexing representatives of orbit isomorphism classes. Thus, M = {g m : V m → V m } is a finite set of fbc's with the property that, given any U ∈ U 0 and f k : U → U , there exist a model map g m : V m → V m and maps ψ U : U → V m and

ψ U : U → V m such that ψ U • f k • ψ -1 U = g m .
The map f k : X → X has finitely many branch values, so there are only finitely many branch values of the model map g m . Since the set M of model maps is finite, for fixed U , as U and k vary, there are only finitely many branch values of f k in U . Hence U ∩ P f is finite. Since U 0 is finite, P f is finite.

Finite subdivision rules

In this subsection, we show that another natural source of examples of finite type dynamics comes from the finite subdivision rules considered by Cannon, Floyd, and Parry. We first briefly summarize their definition, focusing on the case when the underlying dynamics takes place on the two-sphere; cf. [START_REF] Cannon | Finite subdivision rules[END_REF].

Finite subdivision rules on the two-sphere. A finite subdivision rule (f. s. r.) R consists of a finite 2-dimensional CW complex S R , a subdivision R(S R ) of S R , and a continuous cellular map φ R : R(S R ) → S R whose restriction to each open cell is a homeomorphism. When the underlying space of S R is homeomorphic to the two-sphere S 2 (for concreteness, we consider only this case) and φ R is orientation-preserving, φ R is a postcritically finite branched covering of the sphere with the property that pulling back the tiles effects a recursive subdivision of the sphere; below, we denote such a map by f . That is, for each n ∈ N, there is a subdivision R n (S R ) of the sphere such that f is a cellular map from the nth to the (n -1)st subdivisions. Thus, we may speak of tiles (which are closed 2-cells), faces (which are the interiors of tiles), edges, vertices, etc. at level n. It is important to note that formally, an f. s. r. is not a combinatorial object, since the map f , which is part of the data, is assumed given. In other words: as a dynamical system on the sphere, the topological conjugacy class of f is well-defined. A subdivision rule R has mesh going to zero if for every open cover of S R , there is some integer n for which each tile at level n is contained in an element of the cover. It has bounded valence if there is a uniform upper bound on the valence of any vertex at any level. In this case, f is a Thurston map without periodic critical points.

In [HP] it is shown that if R is a bounded valence finite subdivision rule on the sphere with mesh going to zero, then there are integers n 0 , n 1 with the following property. Let t be a tile of R n 0 (S 2 ), let D t be the star of t in R n 0 +n 1 (S 2 ) (that is, a "one-tile neighborhood" of t), and let U t be the interior of D t . Let U 0 be the finite open covering of S 2 defined by sets of the form U t . Then each U belonging to U 0 and all of its iterated preimages are Jordan domains, and with respect to U 0 , the dynamical system f : S 2 → S 2 is topologically cxc.

The fact that R has bounded valence implies that up to cellular isomorphism, as t varies through tiles at all levels, there are only finitely many possibilities for the cell structure of D t in R n 0 +n 1 (S 2 ). Consequently, if t is a tile at level n+k, up to pre-and post-composition by cellular isomorphisms in domain and range, there are only finitely many possibilities for the cellular map f k : D t → f k (D t ). This implies that with respect to U 0 , such a map f is of topologically finite type. We conclude Corollary 3.14 Suppose R is a bounded valence finite subdivision rule on the two-sphere with mesh going to zero. Let U 0 be the level zero good open sets as constructed in [START_REF] Haïssinsky | Coarse expanding conformal dynamics[END_REF]§4.3]. Then in the natural metric d ε , the subdivision map f : S 2 → S 2 is of metric finite type with constant C = 1.

Compare [START_REF] Cannon | Expansion complexes for finite subdivision rules[END_REF]Lemma 4.3] and [START_REF] Bonk | Expanding Thurston maps[END_REF]§ 8].

The preceding corollary implies that, up to similarity, there are only finitely many possible shapes of tiles. We now explain this precisely.

Recall that by construction, each U ∈ U 0 is a union of tiles at level N 0 = n 0 +n 1 . Choose a representative collection of iterates comprising a dynatlas (V, M). Suppose V m ∈ V is a model open set. By construction, there is some k m such that f km : V m → U ∈ U 0 . Then V m is a union of finitely many cells at level N 0 + k m . Since M is finite, there exists M ∈ N such that each model open set V m is a union of finitely many tiles s at a uniform level M independent of m. Then the set of such tiles s arising in this way is finite. Now suppose U ∈ U is arbitrary and |U | = n. By construction, there is a model open set V m ∈ V and a similarity ψ U : U → V m . Let us say that a tile at level n + M is a set of the form ψ -1 U (s) where s ⊂ V m is a tile as in the previous paragraph. We conclude that up to similarity, there are only finitely many tiles.

Selfsimilar groups

In this chapter, we summarize some results of V. Nekrashevych from [START_REF] Nekrashevych | Self-similar groups[END_REF].

Group actions on rooted trees

Let X be an alphabet consisting of d ≥ 2 symbols. For n ≥ 1 denote by X n the set of words of length n in the alphabet X and let X 0 = {∅} consist of the empty word. Let X * = ∪ n X n and X -ω = {...x 3 x 2 x 1 : x i ∈ X}. The length, or level, of a word w will be denoted |w|. For x ∈ X and w ∈ X * , the left shift map τ : X * → X * is defined by τ (xw) = w and the right shift map σ : X * → X * is defined by σ(wx) = w. Obviously, these two shifts commute:

τ • σ = σ • τ .
Let G be a finitely generated group acting faithfully on X * in a manner which preserves the lengths of words and which is transitive on each X n . We write the action as a right action, so that w g is the image of w ∈ X * under the action of g. The action is called selfsimilar if for each g ∈ G and x ∈ X there exists h ∈ G such that for all w ∈ X * , (xw) g = x g w h .

The element h = h(x, g) is uniquely determined, is called the restriction of g to x, and is denoted g| x . More generally, given u ∈ X * and g ∈ G one finds that for all v ∈ X * , (uv) g = u g v g|u for a uniquely determined element g| u called the restriction of g to u. One finds readily the identities g| uv = (g| u )| v for all u, v ∈ X * and all g ∈ G, and (remembering that the action is on the right)

(gh)| v = (g| v )(h| v g ).
Example. Let T (X) denote the infinite rooted tree defined as follows. The vertex set is X * . For all w ∈ X * and x ∈ X, an edge joins w and wx. The root o is the empty word ∅. Let G = Aut(T (X)) denote the group of automorphisms of T (X). Note that G acts transitively on X n for each n. For x ∈ X let T x denote the rooted subtree spanned by the set of vertices xX * with the root x. Then the map

l x : T (X) → T x , w → xw
is an isomorphism of rooted trees. Given g ∈ G and x ∈ X, one has

g| x = l -1 x g • g| Tx • l x
on vertices. Indeed, the map

ρ : G → G d ⋊ Sym(X), ρ(g) = ((g| x 1 , . . . , g| x d ), σ(g))
is an isomorphism, where Sym(X) is the symmetric group on X and σ(g) is the action of g on X = X 1 . In particular, the action of G on X * is selfsimilar.

Contracting actions

In principle, the selfsimilarity of the action means that the image of a word under the action of a group element can be recursively computed. However, there exists the danger that the word lengths of restrictions may blow up as the recursive algorithm progresses.

The following definition is designed to capture a robust condition which ensures that this does not occur.

The action of G on X * is called contracting if there exists a finite subset K of G such that for each g ∈ G, there is a "magic level" m(g) with the following property: for all words v with |v| ≥ m(g), the restrictions g| v lie in K. The smallest such subset K is called the nucleus of the action, denoted N . It follows easily that there is always a "good generating set" S which contains the nucleus N and which is closed under restrictions. The proof is the greedy algorithm. Start with an arbitrary generating set S. Replace S with S ∪ {s| x : x ∈ X, s ∈ S}, and repeat. The process stabilizes, by the identities of restrictions given above and the definition of contracting.

The action is called recurrent if it acts transitively on the first level X 1 and for some (equivalently, for any) x ∈ X, the homomorphism Stab G (x) → G given by g → g| x is surjective. If the action is recurrent, then it is transitive at each level.

Selfsimilarity complexes

Suppose G is a finitely generated group equipped with a faithful, selfsimilar, level-preserving, transitive-on-each-level, contracting group action on X * as in the previous section, and let S be a finite generating set for G. Denote by ||g|| the minimum length of a word in the generators representing g.

Associated to this data is an infinite cellular 1-complex Σ = Σ(G, S) with labelled vertices, oriented labelled edges, and a basepoint, defined as follows. The 0-cells are the set of words X * , labelled by the word. The 1-cells come in two types: vertical edges, running "up" from w to xw and labelled x (yes, this is backwards from the construction of the tree T (X)) and horizontal edges, running "over" from w to w s and labelled s, where s ∈ S. The basepoint o is the vertex corresponding to the empty word. We denote by Σ ′ the subcomplex spanned by words of length at least 1, so that Σ ′ is obtained by removing the root o and all edges incident to o.

We think of the root o at the bottom. The subcomplex spanned by the vertical edges is isomorphic to the tree T (X), which branches upwards. For each n ∈ N, the subcomplex spanned by X n is the so-called Schreier graph of the action of G on X n with respect to the generating set S. Within such a Schreier graph, there may be multiple edges joining a pair of vertices, and edges may join a vertex to itself. The hypothesis that the action is transitive on each level implies that for each level n, this subgraph is connected.

We endow Σ with the unique length metric so that 1-cells are locally isometric to the unit interval; the distance between vertices is thus the usual combinatorial distance. We denote the distance between points p, q ∈ Σ by |p -q|. With this additional structure we may speak of geodesics, i.e. paths γ : [0, L] → Σ satisfying |γ(0)γ(t)| = t for all 0 ≤ t ≤ L, where L = +∞ is permitted. The space Σ is geodesic: any two points of Σ are joined by at least one, and possibly several, geodesics. It is also proper: closed balls (of finite radius) are compact.

The definitions easily imply that given any vertex w = x n . . . x 2 x 1 ∈ Σ, there is exactly one geodesic joining o to w, namely, the one whose image traverses the sequence of labelled vertical edges starting with x 1 , then x 2 , etc. and ending in x n . Similarly, an infinite geodesic starting at the root o, which we call a ray for short, necessarily consists entirely of vertical geodesic segments. The set of rays is thus identified with the set X -ω . Two rays (equivalently, two infinite sequences) . . . x 3 x 2 x 1 and . . . y 3 y 2 y 1 are asymptotically equivalent if there exists some constant C > 0 such that each is contained in some C-neighborhood of the other. Equivalently: there exists a sequence g 1 , g 2 , g 3 , . . . of elements of G, ranging over only a finite set, such that for each n ∈ N, (x n . . . x 1 ) gn = y n . . . y 1 . The following theorem summarizes the principal features of these objects (see Definition 6.3 for ∂Σ).

Theorem 4.1

1. The quasi-isometry type of Σ is independent of the chosen generating set S.

2. The space Σ is Gromov hyperbolic.

3. The ∼ asymp -equivalence classes are finite, of cardinality at most that of the nucleus, N . The Gromov boundary at infinity ∂Σ is homeomorphic to the quotient X -ω / ∼ asymp . It is compact, connected, metrizable, has topological dimension at most #N -1, and, if the action is recurrent, is locally connected.

4. The right shift σ preserves the asymptotic equivalence relation and defines a natural cellular d-to-one covering map F : Σ ′ → Σ whose boundary values ∂F : ∂Σ → ∂Σ coincide with the map on the quotient space X -ω / ∼ asymp induced by σ. The map ∂F is continuous, surjective, and at most finite-to-1.

5. If the action is recurrent, then ∂F is a branched covering map of degree d.

The boundary value map ∂F : ∂Σ → ∂Σ is defined as follows. Given ξ ∈ ∂Σ, to compute ∂F (ξ), choose a representing geodesic ray R; then ∂F (ξ) is represented by the geodesic ray F (R ∩ Σ ′ ).

Proof: (1), (2), and (3) are implied by Lemma 3.8.4, Theorem 3.8.6, and Theorem 3.6.3 of [START_REF] Nekrashevych | Self-similar groups[END_REF], respectively; see also [START_REF] Nekrashevych | Hyperbolic spaces from self-similar group actions[END_REF]. ( 4) is a general consequence of hyperbolicity and the fact that F is cellular. It is clear that ∂F is continuous and surjective. It is finite-to-one since a point of the boundary is represented by at most finitely many rays, and every ray has finitely many preimages. (5) seems to be implied by the discussion in [Nek1, §4.6.1] but for completeness we include a proof in §6.4.

Augmented trees. If in addition S is a good generating set for a contracting action i.e., one which contains the nucleus and which is closed under restrictions, then the selfsimilarity complex inherits additional structure making it an augmented rooted tree in the sense of V. Kaimanovich [Kai]: if vertices u 1 = x 1 v 1 and u 2 = x 2 v 2 at the same level are joined by a horizontal edge, then so are v 1 and v 2 (we allow v 1 = v 2 ). That is, the complex Σ is built out of "squares" of the form

xw s ----→ (xw) s = x s w s|x x    x s w ----→ s|x w s|x (5)
where the vertices w and w s|x possibly coincide. It follows easily that any geodesic can be inductively modified so it is in normal form. That is, it consists of first a (possibly empty) vertical segment traversed downward, then a horizontal segment, followed finally by a (possibly empty) vertical segment traversed upwards.

Shift maps. This has the following geometric/dynamic implication. The right shift σ : X * → X * induces a cellular, label-preserving, degree d covering map F : Σ ′ → Σ. On vertices, the left shift map τ simply pushes each vertex to the vertex immediately below it; for k ≤ |v| we denote τ k (v) = v [-k] . Since the left and right shifts commute, F • τ = τ • F on vertices. Note that the map F is 1-Lipshitz, hence so is any iterate of F .

Geometric interpretation of contraction. In the next chapter, we will make essential use of an interpretation of the contracting condition into geometric language. First, note that by concatenating diagrams as in ( 5) along vertical edges, we see that for all g ∈ G and for all u ∈ X * , we have || g| u || ≤ ||g||. Now let l ≥ 1 be a positive integer. Suppose u 1 , u 2 are vertices at the same level n, and suppose l = min g∈G {||g|| : u g 1 = u 2 }, so that l is the length of the shortest horizontal edge-path at level n from u 1 to u 2 . The contracting property implies that there is "magic level" m(l) such that whenever |v| ≥ m(l), we have g| v ∈ N , and so g| v ∈ S since S is assumed good. In particular, ||g| v || ≤ 1. This means that in the selfsimilarity complex Σ, we have the following "quadrilateral" whose side lengths are indicated (the top horizontal segment need not be geodesic in Σ):

u 1 = vw l=||g|| ----→ (vw) g = v g w g|v = u 2 |v|     |v g | w ----→ ≤1 w g|v (6)
Fix now l ≥ 0 and n ≥ m(l), and consider the Schreier subgraph spanned by X n , with the restricted graph "horizontal" metric d hor . Then for arbitrary u 1 , u 2 ∈ X n , the restriction

τ m(l) : X n → X n-m(l) satisfies d hor (τ m(l) (u 1 ), τ m(l) (u 2 )) ≤ ⌈d hor (u 1 , u 2 )/l⌉
where ⌈x⌉ is the smallest integer greater than or equal to x.

We also note the following. Let l ≥ 1 be a positive integer, and suppose there exists a horizontal path in Σ between vertices which is a geodesic of length m(l) • l in the ambient metric on Σ (here, we do not mean the restriction of the metric to a horizontal subset). By concatening m(l) copies of the diagram in (6) along vertical edges, it is clear that then

m(l) • l ≤ m(l) + m(l) + m(l) = 3 • m(l).
It follows that l ≤ 3 and so the maximum length of a horizontal geodesic is bounded above by H Σ := m(3) • 3. From this observation the hyperbolicity of Σ follows easily; cf. [START_REF] Nekrashevych | Self-similar groups[END_REF]§3.8], [Kai] and [Pil]. In addition, for any geodesic in normal form, its horizontal segment has length at most H Σ .

Finiteness principles for selfsimilarity complexes

In this chapter, we assume we are given a faithful level-transitive selfsimilar contracting recurrent action of a finitely generated group G on the set of words X * in a finite alphabet X, and are given a symmetric generating set S which is closed under restrictions and which contains the nucleus N of the action. Let Σ denote the selfsimilarity complex associated to G and S; it is a Gromov hyperbolic augmented tree.

The main result of this chapter is a fundamental finiteness result (Theorem 5.17) concerning the induced dynamics F : Σ ′ → Σ that is reminiscent of the finiteness of cone types for a Gromov hyperbolic group, which we now describe.

Let G be a finitely generated group and S a generating set such that if s ∈ S, then s -1 ∈ S. Any element g in G can thus be written as as a product of elements, i.e. a word, in S. The minimum number of elements of S required to write g as product of elements of S is by definition the word length ||g|| of g. Let Σ denote the Cayley graph of G with respect to S. Its vertex set is the set of elements of G, and (g, g ′ ) ∈ G × G defines an edge if g -1 g ′ ∈ S. The edges of Σ are naturally labelled by elements of S. The length metric on Σ in which each edge is isfometric to a unit interval turns Σ into a proper, geodesic metric space on which G acts isometrically by left-translation. The distance from g to the neutral element e is the word length of g, and to any other vertex g ′ is ||g -1 g ′ ||.

The cone C g of an element g ∈ G is the set of vertices w ∈ G such that g lies in a geodesic segment joining e to w i.e., ||w|| = ||g|| + ||g -1 w||.

The cone type T g of g is

T g = g -1 C g i.e., T g = {w ∈ G : gw ∈ C g }. By definition, if T g = T h , then the restriction φ : C g → C h , x → hg -1 x of the left-translation map L hg -1 : Σ → Σ is a well-defined isometry.
Given a positive integer k and g ∈ G, the k-tail of g is the set of those h ∈ G for which ||h|| ≤ k and ||gh|| < ||g||. The following theorem was proved by Cannon in the case of cocompact Kleinian groups; the proof of the general case is very similar and may be found in [START_REF] Bridson | Metric spaces of non-positive curvature, volume 319 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences[END_REF]Theorem III.Γ.2.18].

Theorem 5.1 (Cone types finite) Let G be a δ-hyperbolic group. Then the cone type of g is determined by the (2δ + 3)-tail of g. Hence, there are only finitely many cone types.

That is, the geometry of the cone C g of Σ is determined by a uniformly small amount of combinatorial data associated to g. Another result with a similar flavor (and proof) is an analogous result for so-called half-spaces defined by geodesic segments; cf. [START_REF] Cannon | Recognizing constant curvature discrete groups in dimension 3[END_REF]Theorem 3.21].

Subcomplexes, cones, shadows

We emphasize that we regard the selfsimilarity complex Σ as a CW 1-complex with edges locally isometric to Euclidean unit intervals. Each 1-cell is equipped with a distinguished orientation and a distinguished label drawn from the finite set S. The local picture near each vertex at level > 0 is the same. We denote by |a -b| the distance between points a, b.

The following observation will be of central importance in the following chapter. From the hyperbolicity of Σ, it follows that there exists a constant C with the following property.

Suppose R 1 , R 2 : [0, ∞) → Σ are two infinite vertical rays from the basepoint o. Then R 1 ∼ R 2 if and only if |R 1 (t) -R 2 (t)| ≤ C for all t ≥ 0.
In our setting we have C = 1; see [START_REF] Nekrashevych | Self-similar groups[END_REF]Theorem 3.6.3] and §6.1 below. Thus in addition to the scale of H Σ , the maximum length of a horizontal geodesic segment, the scale of 1 arises as an important quantity as well.

In the remainder of this section, we work exclusively in the complex Σ, equipped with the path-metric of §4. In the next section, we transfer the results obtained here to the boundary ∂Σ.

Horizontal, vertical

The level of a subset of Σ is its distance from the origin. A subset of Σ is horizontal if all its vertices lie at the same level; it is vertical if no two vertices have the same level. Given two vertices a, b at the same level, the horizontal distance |a -b| hor = min{l(γ) : γ is horizontal and joins a to b}. If V ⊂ Σ is horizontal we set diam hor (V ) = sup{|a -b| hor : a, b ∈ V }.

Notation. If w = uv with |u| = k we set, following Kaimanovich, v = w [-k] . The notation [ov] stands for the vertical geodesic ray joining the basepoint o and a vertex v; it is unique. More generally, [a, b] denotes a geodesic segment joining a and b; it is unique if it is vertical. For a horizontal subset V ⊂ Σ we will write |V | for the level of V .

Balls and neighborhoods

Given a vertex v of Σ and an integer r ≥ 1 we denote by B(v, r) the set of vertices w such that |v -w| ≤ r and by B hor (v, r) the intersection of B(v, r) with the set of vertices at level |v|. We emphasize that B(v, r) is a set of vertices and not a union of vertices and edges. Given a subset A of the vertices of Σ we denote by B(A, r) = ∪ a∈A B(a, r) and set B hor (A, r) = ∪ a∈A B hor (a, r) similarly.

Lemma 5.2 (Balls map to balls) Fix an integer k > 0. Then for all v ∈ X * , all ṽ ∈ F -k (v), and all r ≤ diam hor X |v| we have F k (B hor (ṽ, r)) = B hor (v, r).

Proof: The inclusion ⊂ follows immediately since F k is cellular, and the inclusion ⊃ follows by path-lifting, using the fact that F k is a covering map.

Distances between subsets; neighborhoods

Let A, B be subsets of Σ. We set

|A -B| = inf{|a -b| : a ∈ A, b ∈ B}.

Cones

Given a vertex v ∈ Σ we define the cone C v as the subset of vertices of Σ given by

C v = {wv|w ∈ X * }.
See Figure 5.1.4. Note that given vertices v 1 , v 2 we have that exactly one of the following holds:

C v 1 ∩ C v 2 = ∅ or C v 1 ⊂ C v 2 or C v 2 ⊂ C v 1 . If v = wx then F (C v ) = C w
since F acts as the right shift on vertices.

Induced subcomplexes

Given a set V of vertices of Σ, we denote by Σ(V ) the induced subcomplex on V , i.e. the subcomplex of Σ whose 0-cells are the elements of V and whose 1-cells consist of those 1-cells of Σ whose endpoints lie in V . Often we will denote such subcomplexes by the symbol Γ.

The isomorphism type of a subcomplex is its equivalence class under the equivalence relation generated by label-and orientation-preserving cellular isomorphisms.

A connected component of an induced subcomplex is again an induced subcomplex. In particular, if Γ is a connected induced subcomplex and Γ is a component of F -k (Γ) then Γ is again an induced subcomplex. The following lemma will be important.

Lemma 5.3 (At least two apart) Let V ⊂ X * be a set of vertices, Γ = Σ(V ), and let

Γ i , i = 1, 2 be two connected components of Γ. Then Γ 1 = Γ 2 iff |Γ 1 -Γ 2 | ≥ 2. Proof: If v i ∈ Γ i satisfy |v 1 -v 2 | = 1,
then v 1 and v 2 are incident to the same edge in Σ. This edge lies in Γ since Γ is an induced subcomplex. Therefore Γ 1 = Γ 2 .

Shadows

Given a set of vertices V we define the shadow S(V ) by

S(V ) = Σ(∪ v∈V C v ).
See Figure 5.1.4. The shadow S(B hor (v, r)) of a horizontal ball of radius r about v will be denoted more succinctly by S(v, r).

If V is a point or a horizontal ball, a shadow is somewhat analogous to a half-space in the Cayley graph of a Gromov hyperbolic group. Many of the geometric results below have analogies in the group setting; compare [START_REF] Cannon | Recognizing constant curvature discrete groups in dimension 3[END_REF]§3.3].

The following properties are easily verified. Below, c A denotes the complement of A; a set A is Q-quasiconvex if every geodesic between points in A lies in a Q-neighborhood of A.

Lemma 5.4 (Properties of shadows) , i = 1, 2 are in S(V ) and either coincide or are joined by a horizontal edge. Hence, any horizontal path in S(V ) can be "pushed down" to a horizontal path in Σ(V ) of the same or shorter length.

Let V ⊂ X * . 1. u ∈ c S(V ) ∩ X * =⇒ [ou] ⊂ c S(V ). If in addition |u| > max{|v| : v ∈ V } then C u ⊂ c S(V ). 2. If V is horizontal, u i ∈ S(V ), |u 1 | = |u 2 | > |V |,
3. S(V ) is connected iff Σ(V ) is connected. 4. S(V ) is Q-quasiconvex where Q = max{⌈diamV /2⌉, ⌈H Σ /2⌉} + 1. 5. If V 1 , V 2 are horizontal subsets at the same level, and |V 1 -V 2 | ≥ 2 then |S(V 1 ) - S(V 2 )| ≥ 2.
6. Let V , V be horizontal vertex sets and k > 0 an integer. Then

F k (Σ( V )) = Σ(V ) ⇐⇒ F k (S( V )) = S(V ). 7. Suppose Γ = Σ(V ) is connected. Let V = F -k (V ), Γ = Σ( V ). Then (a) F k ( Γ) = Γ; (b) if Γ i is a connected component of Γ then F k ( Γ i ) = Γ; (c) if Γ i , i = 1, 2 are distinct components of Γ then | Γ 1 -Γ 2 | ≥ 2 and hence |S( V 1 ) -S( V 2 )| ≥ 2.
We give proofs of the not-so-straightforward assertions. Proof: Assertion 2. follows immediately from the definitions, since we have assumed Σ is an augmented tree.

3. Suppose Σ(V ) is connected. It is enough to show that any pair of vertices w 1 , w 2 ∈ S(V ) ∩ X * are joined by a path in S(V ). By definition, there are

v i ∈ V such that w i ∈ C v i ⊂ S(V ). Since S(V ) is an induced subcomplex this implies that the vertical geodesic segment [v i w i ] ⊂ S(V ). Since v i ∈ Σ(V ) and Σ(V ) is connected, there is a horizontal path joining v 1 to v 2 in Σ(V ) ⊂ S(V ). Hence w 1 , w 2 are joined by a path in S(V ). Conversely, suppose Σ(V ) is disconnected. Write Σ(V ) = Γ = Γ 1 ⊔ Γ 2 where Γ 1 , Γ 2 are disjoint nonempty induced subcomplexes. Then |Γ 1 -Γ 2 | ≥ 2 by Lemma 5.3. If w i ∈ C v i for some v i ∈ Γ i , then |w 1 -w 2 | ≥ 2 since
otherwise pushing down to the level of V will yield points at distance at most 1, a contradiction. Hence S(V ) is disconnected.

4. Let u 1 , u 2 be two vertices in S(V ) and let γ be a normal form geodesic joining them. Suppose the horizontal portion γ ′ of this geodesic lies at a level larger than |V |. Then we may write γ = γ 1 * γ ′ * γ 2 where γ i are vertical and lie in S(V ). Since the length of γ ′ is at most H Σ we have that γ lies in a ⌈H Σ /2⌉ + 1-neighborhood of S(V ). Otherwise, the definition of shadows implies that γ meets V in two points v 1 , v 2 , so that γ = γ 1 * γ ′ * γ 2 where the γ i are vertical and in S(V ) and γ ′ is a normal form geodesic joining v 1 and v 2 . Again, the length of γ ′ is at most diamV , hence every point on it lies in a ⌈diamV /2⌉ + 1-neighborhood of V , hence of S(V ) as well.

5. This follows from the previous paragraph on induced subcomplexes. 6. The right and left shifts commute.

This subsection concludes with some technical results regarding preimages of balls and of their corresponding shadows. The former will later be used in the proof of Theorem 5.16; the latter will be used in Chapter 6.

Lemma 5.5 (Pullbacks of balls) Suppose that k, r > 0 are integers and v ∈ X * . Let

Γ = Σ(B hor (v, r)). Then 1. F -k (B hor (v, r)) = F k (ṽ)=v B hor (ṽ, r). 2. If Γ is a connected component of F -k (Γ) and V = F -k (v) ∩ Γ then Γ = Σ ∪ ṽ∈ V B hor (ṽ, r) .
Moreover: given any pair ṽ′ , ṽ′′ ∈ V there are ṽi ∈ V , i = 0, . . . , p such that ṽ0 = ṽ′ , ṽp = ṽ′′ , and for each 1 ≤ i ≤ p we have |ṽ i-1ṽi | hor ≤ 2r + 1.

If

Γ i , i = 1, 2 are two distinct components of F -k (Γ) then | Γ 1 -Γ 2 | ≥ 2.
Remark: We have always diam hor V ≤ diam hor Σ(V ) ≤ diam hor V + 1. Equality in the upper bound can occur, e.g. when there are loops at each vertex of a pair of vertices whose horizontal distance realizes diam hor V , and one or both of these loops fails to lift under F .

Proof: 1. This follows easily from [Lemma 5.2, Balls map to balls]. 3. is a special case of Lemma 5.4(7).

We now prove the inclusion ⊂ in 2.. First, the set of vertices Ṽ is clearly contained in the induced complex on the right-hand side. Let w ∈ τ ⊂ Γ map under F k to w, where τ is an edge. Let τ = F k (τ ) ⊂ Γ be a closed one-cell of Σ containing w and let v ′ i , i = 1, 2 denote the (possibly indistinct) vertices comprising ∂τ . Since Γ = Σ(B hor (v, r)) is connected, there are horizontal paths γ i ⊂ Γ which are geodesics with respect to the intrinsic path metric in Γ joining v to v ′ i of length ≤ r. Let e ⊂ Γ be the edge-path given by γ 1 * τ * γ -1 2 where * denotes concatenation. Since Γ is a component of the preimage of Γ, the map Γ → Γ is a covering map and thus has the path-lifting property. Let ẽ be the unique lift of this edge-path containing w. Then ẽ contains as a sub-edge-path an edge-path given by γ1 * τ * γ2 where γi → γ i under F k . Thus γi joins some ṽi ∈ V to some ṽ′ i ∈ F -k (v ′ i ). Hence ṽ′ i ∈ B hor (ṽ i , r) and so τ ⊂ Σ(∪ ṽ∈ V B hor (ṽ, r)). To prove the other inclusion, suppose w ∈ Σ(∪ ṽ∈ V B hor (ṽ, r)). Then w ∈ τ , a 1-cell with ∂ τ = {ṽ ′ 1 , ṽ′ 2 }. Let γi be a geodesic in Σ(∪ ṽ∈ V B hor (ṽ, r)) joining ṽ′ i to some ṽi ∈ V , so that |ṽ

′ i -ṽi | = |ṽ ′ i -V |, i = 1, 2.
Since V ⊂ Γ and Γ is connected, there exists a path γ in Γ joining ṽ1 to ṽ2 . Thus, the edge-path γ1 * γ * γ-1 2 lies in Γ and joins ṽ′ 1 to ṽ′ 2 . Therefore ṽ′ i ∈ Γ and hence τ ⊂ Γ since Γ is an induced subcomplex. Hence w, which lies in τ , is in Γ.

To prove the second assertion, suppose there is a nontrivial partition of

V into disjoint subsets V 1 ∪ V 2 such that | V 1 -V 2 | > 2r + 1. This implies that | ∪ ṽ1 ∈ V 1 B hor (ṽ 1 , r) -∪ ṽ2 ∈ V 2 B hor (ṽ 2 , r)| > 1.
Hence the induced subcomplex Γ is not connected. Lemma 5.9 (Unit speed penetration) Suppose u ∈ U (V ) and v ∈ C u . Then

|v -c S(V )| ≥ |v| -(|u| + m(H Σ )).
Proof: Let y ∈ c S(V ). If |y| ≤ |u| then |v -y| ≥ |v| -|u| and we are done. So now suppose |y| > |u|. We have [oy] ⊂ c S(V ) by Lemma 5.4(1). Let [v ′ y ′ ] be the horizontal segment of a normal form geodesic joining v and y. The level l of this segment is at most |u| + m(H Σ ), for otherwise, pushing this segment down to the level of u will yield

|u -[oy]| ≤ 1 =⇒ |u -c S(V )| ≤ 1, contradicting u ∈ U (V ). Thus l ≤ |u| + m(H Σ ). But |v -y| ≥ |v| -l ≥ |v| -(|u| + m(H Σ ))
, yielding the result.

Isometry types of shadows

In this section, we prove a static finiteness result: the isometry type of a shadow S(V ) is determined by the isomorphism type of the induced subcomplex Σ( V ) of a certain neighborhood V of the defining subset V called the hull of V . In the next section we add dynamics and prove a related finiteness result.

We begin with an easier result which has the same flavor.

Theorem 5.10 (Cone types) Suppose v i are vertices of Σ and let

Γ i = Σ(B hor (v i , H Σ )), i = 1, 2. If φ : Γ 1 → Γ 2 is an isomorphism of 1-complexes with labelled edges such that v 2 = φ(v 1 ), then the map φ : C v 1 → C v 2
given by wv 1 → wv 2 , w ∈ X * is an isometry with respect to the distance function of Σ.

Corollary 5.11 (Finitely many cone types) There are only finitely many isometry classes of cone types.

Proof of Corollary 5.11: There are only finitely many possible isomorphism types of labelled 1-complexes of the form B hor (v, H Σ ) since the horizontal valence of any vertex is bounded by #S.

We view this as an analog of Cannon's observation of the finiteness of cone types for (Gromov) hyperbolic groups; cf. Theorem 5.1. Compare with [START_REF] Nekrashevych | Self-similar groups[END_REF]§3.3].

Proof of Theorem 5.10: For convenience we write Let w 1 , w 2 ∈ C v . Let γ be a normal form geodesic joining w 1 , w 2 . Then q ≥ |v| where q is the level of the horizontal segment of γ.

v = v 1 , v φ = v 2 , Γ = Γ 1 , Γ φ = Γ
Write w i = p i u i v where |u i | = q -|v|, i = 1, 2 (see Figure 5.2). The horizontal segment of γ joins u 1 v to u 2 v and is a horizontal edge-path representing an element h ∈ G where ||h|| ≤ H Σ . Then

|w 1 -w 2 | = |p 1 | + ||h|| + |p 2 |.
The theorem follows once we show (u

1 v φ ) h = u 2 v φ . Assuming this, it follows that the edge-path from w φ 1 = p 1 u 1 v φ to w φ 2 = p 2 u 2 v φ
given by going first down towards the root along p 1 to u 1 v φ , over via the horizontal edge-path representing h to (u 1 v φ ) h = u 2 v φ , and then up along p 2 has length equal to |w 1w 2 | and thus

|w φ 1 -w φ 2 | ≤ |w 1 -w 2 |. The inequality |w 1 -w 2 | ≤ |w φ 1 -w φ 2 | then follows by considering φ -1 .
Theorem 5.13 (Finitely many shadow types) For i = 1, 2, suppose V i are horizontal sets of vertices of Σ of diameter ≤ D, let V i be the corresponding D-hulls, and let Γ i = Σ( V i ). If φ : Γ 1 → Γ 2 is an isomorphism (of 1-complexes with labelled edges) then the map

φ : S(V 1 ) → S(V 2 )
given by φ(wv

) = wφ(v), v ∈ V 1 , w ∈ X *
is an isometry with respect to the distance function of Σ and an isomorphism of complexes.

The proof is more or less exactly the same as the proof of Theorem 5.10 above. Proof:

Again write V = V 1 , V φ = V 2 , Γ = Γ 1 , Γ φ = Γ 2 . Suppose w 1 , w 2 ∈ S(V ). Let v i ∈ V ∩ [ow i ], i = 1, 2.
Conceptually it is easiest to consider now two cases.

Case 1: There exists a normal form geodesic γ from w 1 to w 2 whose level (that is, the level of its horizontal part), l, is at least |V |.

Write

w i = p i u i v i , i = 1, 2, |u 1 | = |u 2 |, |v 1 | = |v 2 |, |u 1 v 1 | = l.
Then by definition, there is some h ∈ G such that (u

1 v 1 ) h = u 2 v 2 = u h 1 v h|u 1 1
where ||h|| ≤ H Σ . The restriction h| u 1 again satisfies || h| u 1 || ≤ H Σ and so viewed as an edge-path based at v 1 is a path of length ≤ H Σ . So |v 1 -v 2 | ≤ H Σ . Thus this edge-path lies in Γ. Since φ : Γ → Γ φ is an isomorphism, we find that (v φ 1 ) h|u 1 = v φ 2 and consequently (u 1 v φ 1 ) h = u 2 v φ 2 . With the same reasoning as in the previous proof we conclude |w φ 1w φ 2 | ≤ |w 1w 2 |. By symmetry, equality holds.

Case 2: Otherwise, the level of the horizontal part of γ is strictly less than |V |. The subsegment γ ′ of γ joining v 1 to v 2 is a geodesic, hence has length bounded by diamV . The vertical distance between the horizontal segment of γ and V is at most ⌈D/2⌉. Hence γ ′ ⊂ Γ. If we write w i = p i v i , then the concatenation of the geodesic segments

[p 1 v φ 1 , v φ 1 ], φ(γ ′ ) and [v φ 2 , p 2 v φ 2 ] is a curve joining φ(w 1 ) to φ(w 2 ) of length |w 1 -w 2 | so |w φ 1 -w φ 2 | ≤ |w 1 -w 2 |.
By symmetry, equality holds.

Isometry types of maps between shadows

In this section, we prove a dynamical version of Theorem 5.13. Let F i : Z i → Z i , i = 1, 2 be maps between metric spaces. We say that F 1 , F 2 are isometrically isomorphic as maps if there are isometries φ : Z 1 → Z 2 and φ :

Z 1 → Z 2 such that the diagram Z 1 φ -→ Z 2 F 1 ↓ ↓ F 2 Z 1 φ -→ Z 2
commutes. The isometry type of a map F : Z → Z between metric spaces is its equivalence class under this equivalence relation. We define similarly the isomorphism type of a cellular label-preserving map between CW 1-complexes with labelled edges.

The following theorem says that the isometry type of a map between shadows is determined by the isomorphism type of the map between induced subcomplexes of hulls.

Theorem 5.14 (Shadow map determined by hull map) Suppose V i , V i are horizontal vertex sets of diameter ≤ D, let V i , V i denote the corresponding D-hulls, and suppose

F k i : Σ( V i ) → Σ(V i ). Suppose φ : Σ( V 1 ) → Σ( V 2 ) and φ : Σ( V 1 ) → Σ( V 2 ) are isomorphisms of labelled complexes which satisfy F k 2 • φ = φ • F k 1 on Σ( V 1 ). Then F k i : S( V i ) → S(V i ), i = 1, 2 and the isometries φ : S( V 1 ) → S( V 2 ), φ : S(V 1 ) → S(V 2 )
given by Theorem 5.13 also satisfy

F k 2 • φ = φ • F k 1 .
Proof: Lemma 5.4(6) implies that F k i : S( V i ) → S(V i ), i = 1, 2. It remains only to prove the claimed commutativity property.

Let ũ1 ∈ S( V 1 ) and write (as in the definition of φ) ũ1 = wũ ′ 1 where ũ′ 1 ∈ V 1 and w ∈ X * . Let u 1 = F k 1 (ũ 1 ) and u ′ 1 = F k 1 (ũ ′ 1 ), so that F k 1 (ũ 1 ) = wu ′ 1 . Let l = |w|. The desired commutativity follows immediately since the two shifts commute:

Corollary 5.15 (Diameter bound implies finite) For a fixed diameter bound D, there are only finitely many isometry types of maps of shadows F k : S( V ) → S(V ) where V is a horizontal subset of diameter < D and where F k : Σ( V ) → Σ(V ).

Proof: Up to isomorphism, there are only finitely many isomorphism types of labelled graphs of the form Σ( V ), Σ( V ), where V , V are horizontal subsets of diameter ≤ D. Hence, up to isomorphism, there are only finitely many cellular, label-preserving maps Σ( V ) → Σ( V ).

Finiteness principles

Let v ∈ X * and r > 0 be an integer. If B hor (v, r) is a ball and Γ = Σ(B hor (v, r)) is the induced subcomplex, then a component of F -k (Γ) need not be the induced subcomplex of a ball. Instead, it may be the induced subcomplex of a union of overlapping balls. The theorem below says that these components cannot be too large, provided the level |v| is large enough. More precisely, it says that at sufficiently high levels, for all iterates, components of preimages of induced subcomplexes of horizontal balls map by uniformly bounded degree.

Theorem 5.16 (Bounded degree) Let r > 0 be an integer. Then there exists a positive integer bound C = C(r) and a level n = n(r) such that (∀v, |v| > n)(∀k > 0)(∀ṽ

∈ F -k (v)) if Γ = Σ(B hor (v, r)), Γ is a component of F -k (Γ), and V = F -k (v) ∩ Γ, then 1. # V < C
2. diam hor V < D := (2r + 1)(C + 1).

Using Theorem 5.16, we first derive the main result of this section.

Theorem 5.17 (Finiteness Principles) Fix an integer r > 0. Then there are only finitely many isometry types of maps of the form Theorem 5.18 (Orbits under vertex stabilizers) Let G be a finitely generated group, equipped with a selfsimilar, contracting group action on T (X). Fix a finite "good" generating set S for G so that (i) S is closed under restriction, and (ii) N ⊂ S. Let N = #N . Then for all w ∈ X * , and for all L ≥ 1, if |v| ≥ m((N + 1)L), we have

# Stab G (v) ∩ B G (1, L) .vw ≤ 1 + q + q 2 + . . . + q N +1 where q = #Stab G (v) ∩ B G (1, L).
Proof of Thm. 5.18: Let H v,L = Stab(v) ∩ B G (1, L), w ∈ X * , and consider the onecomplex K with vertex set equal to the set of elements ṽ in the orbit H v,L .vw and edges from ṽ to ṽh , h ∈ H v,L . (This is just the Schreier graph of the action of H v,L on the orbit of vw.) Note that by construction, K is connected.

Suppose |v| ≥ m((N + 1)L) holds and that in the intrinsic graph metric of K there exists a geodesic edge-path W with N + 1 vertices. On the one hand, the restriction to W of the iterated left shift τ m(L(N +1)) | W is injective, since the right-hand substrings of length |w| are all distinct. On the other hand, by contraction and the definition of m(•), the vertices in the image τ m(L(N +1)) (W ) are all joined to one another by edges labelled by elements of the nucleus. We conclude that the graph-diameter of K is at most N .

In the 1-skeleton of the complex K, the valence of each vertex is at most q. Hence the number of vertices in a sphere of radius n is bounded by q n . Since diam K is bounded by N , it follows that the total number of vertices in K is bounded by 1 + q + q 2 + . . . + q N +1 and the proof is complete.

Proof of Thm. 5.16: Conclusion 2 follows immediately from 1, Lemma 5.5, and the triangle inequality. To prove 1, let ṽ0 = vw 0 , ṽp = vw p ∈ V be arbitrary. By Lemma 5.5(2) there exist ṽi = vw i ∈ V , i = 1, . . . , p -1 such that for 1 ≤ i ≤ p we have |ṽ i-1ṽi | hor ≤ 2r + 1 = L. This implies ṽp ∈ Stab(v) ∩ B G (1, L) .vw 0 . Since ṽp ∈ V is arbitrary we conclude that V ⊂ Stab(v) ∩ B G (1, 2r + 1) .vw 0 and so the cardinality of this set is bounded by C(L), the constant in Theorem 5.18.

∂F : ∂Σ → ∂Σ is finite type

As in the previous chapter, we assume we are given a faithful, selfsimilar, level-transitive, contracting, recurrent action of a finitely generated group G on the set of words X * in a finite alphabet X, and are given a symmetric generating set S which is closed under restrictions and which contains the nucleus N of the action. Let Σ denote the selfsimilarity complex associated to G and S; it is a Gromov hyperbolic augmented tree.

In this chapter, we apply the finiteness principle, Theorem 5.17, to prove that the induced dynamics ∂F : ∂Σ → ∂Σ is metrically of finite type with respect to a certain covering U 0 when equipped with the visual metric on the boundary (Theorem 6.15). The covering U 0 will consist of connected components of the boundary of umbrae associated to the shadows of horizontal balls of radius one at a sufficiently deep level.

Recall that an infinite geodesic ray based at o is necessarily vertical.

Metrics on the boundary

Definition 6.1 Let (u 1 , u 2 ) be an ordered pair of vertices of Σ, and let R 1 , R 2 : [0, ∞) → Σ be infinite geodesic rays starting from o.

1. The Gromov inner product with respect to the basepoint o is

(u 1 |u 2 ) = 1 2 (|u 1 | + |u 2 | -|u 1 -u 2 |) .
2. The normal form geodesic inner product is

[u 1 |u 2 ] = min γ {|γ|}
where the minimum is over the set of normal form geodesics joining u 1 to u 2 .

3. The divergence inner product is

{R 1 |R 2 } = max{t : |R 1 (t) -R 2 (t)| ≤ 1}.
The lemma below says that these three products are all comparable.

Lemma 6.2 1. For all pairs (u 1 , u 2 ) of vertices, we have

[u 1 |u 2 ] - H Σ 2 ≤ (u 1 |u 2 ) ≤ [u 1 |u 2 ]. 2. (a) d haus (R 1 , R 2 ) < ∞ ⇐⇒ {R 1 |R 2 } = ∞ (b) if {R 1 |R 2 } < ∞, then ∀s, t > {R 1 |R 2 }, {R 1 |R 2 } ≤ [R 1 (s)|R 2 (t)] ≤ {R 1 |R 2 } + m(H Σ ).
Proof: 1. If u 1 , u 2 lie on the same geodesic ray through o then (u

1 |u 2 ) = min{|u 1 |, |u 2 |} = [u 1 |u 2 ]. Otherwise, let γ = [u 1 u ′ 1 ] ∪ [u ′ 1 u ′ 2 ] ∪ [u ′ 2 u 2
] be a normal form geodesic, where the middle segment is the horizontal portion. Then

(u 1 |u 2 ) = 1 2 (|u 1 | + |u 2 | -(|u 1 | -|u ′ 1 | + |u ′ 1 -u ′ 2 | + |u 2 | -|u ′ 2 |)) = [u 1 |u 2 ] -1 2 |u ′ 1 -u ′ 2 | so [u 1 |u 2 ] - H Σ 2 ≤ (u 1 |u 2 ) ≤ [u 1 |u 2 ].
2. (a) The implication ⇐ is obvious. Note that for any rays R 1 and R 2 and for any s

, t ≥ 0, |R 1 (s) -R 2 (t)| ≥ |s -t| so that if d haus (R 1 , R 2 ) ≤ D, then for all t we have |R 1 (t) -R 2 (t)| ≤ 2D. Hence for all t, |R 1 (t -m(2D)) -R 2 (t -m(2D))| ≤ 1. (b)
The lower bound is obvious, since any geodesic joining two points at horizontal distance one is necessarily horizontal. The upper bound follows easily. Definition 6.3 (∂Σ) The limit space ∂Σ of the action is the quotient space

∂Σ = {geodesic rays R : [0, ∞) → Σ|R(0) = o}/ ∼
where the asymptotic equivalence relation ∼ is defined by

R 1 ∼ R 2 ⇐⇒ d haus (R 1 , R 2 ) < ∞.
Cf. §4.1. We will often denote by ξ or by R(∞) the equivalence class of a geodesic ray R.

One may define another topology on ∂Σ as follows. Given a geodesic ray R 0 , a fundamental system of neighborhoods of R 0 (∞) is given by the sets V (R 0 , t) of points R(∞) which admit a representative with {R 0 |R} > t. This topology coincides with the quotient topology defined above.

Remarks: In fact, in our case the following conditions are equivalent:

1. d haus (R 1 , R 2 ) < ∞ 2. d haus (R 1 , R 2 ) ≤ 8δ
where δ is the constant of hyperbolicity (in the Gromov inner product definition).

3.

d haus (R 1 , R 2 ) ≤ 1.
The equivalence of ( 1) and ( 2) holds for general δ-hyperbolic spaces; see [GdlH]. The equivalence of (3) and ( 1) is implied by Lemma 6.2. By (3) and the definition of Σ, there are at most #S + 1 elements in any asymptotic equivalence class; with a bit more work one can improve this bound to #N , the cardinality of the nucleus. The Gromov, normal form geodesic, and divergence inner products of a pair of points on ∂Σ are defined as follows:

Definition 6.4 Let ξ 1 , ξ 2 ∈ ∂Σ. Then (ξ 1 |ξ 2 ) = sup R 1 ∈ξ 1 ,R 2 ∈ξ 2 lim inf s i ,t j →∞ (R 1 (t i )|R 2 (s j ))
with analogous formulae used for

[•|•] and {•|•}.
The following fact is known; see [GdlH]. For all

R 1 ∈ ξ 1 , R 2 ∈ ξ 2 , we have (ξ 1 |ξ 2 ) -2δ ≤ lim inf s i ,t j →∞ (R 1 (t i )|R 2 (s j )) ≤ (ξ 1 |ξ 2 ) .
Thus, up to a universal additive constant, the choice of representative ray and the choice of points (at sufficiently high level) on these rays used in the computation is irrelevant. Moreover, by Lemma 6.2, there exists a constant C 0 such that for all ξ 1 , ξ 2 ,

|max{(ξ 1 |ξ 2 ), [ξ 1 |ξ 2 ], {ξ 1 |ξ 2 }} -min{(ξ 1 |ξ 2 ), [ξ 1 |ξ 2 ], {ξ 1 |ξ 2 }}| < C 0
Therefore, any one of these quantities may be approximated, to within C 0 , by computing [R 1 (t)|R 2 (t)] for any t which is sufficiently large.

Tracing through the dependencies shows that one may in fact take this additive constant to be C 0 = 100(δ + m(H Σ )).

It is known that

1. (ξ 1 |ξ 2 ) = (ξ 2 |ξ 1 ) 2. (ξ 1 |ξ 2 ) = ∞ ⇐⇒ ξ 1 = ξ 2 3. (ξ 1 |ξ 3 ) ≥ min{(ξ 1 |ξ 2 ), (ξ 2 |ξ 3 )} -δ.
and we have similar statements for the other two products.

For ǫ > 0 let ̺ ǫ (ξ 1 , ξ 2 ) = exp(-ǫ[ξ 1 |ξ 2 ]). The function ̺ ǫ does not quite define a distance function, as the triangle inequality fails slightly due in particular to the constant present in (3) above. But, by choosing ǫ small enough and by using chains, however, this does define a metric, a so-called visual metric, and the resulting distance function turns out to be comparable to ̺ ǫ to within universal mutliplicative constants which tend to one as ǫ decreases to 0.

By using the normal form geodesic inner product, we then have Proposition 6.5 (existence of visual metrics on Σ) There exists a constant ǫ 0 > 0 depending only on δ (equivalently, on H Σ ) such that for all ǫ < ǫ 0 , there exist a metric d ǫ compatible with the topology of ∂Σ and a constant C ǫ ≥ 1 (with C ǫ → 1 as ǫ → 0) with the following property. For all ξ 1 , ξ 2 ∈ ∂Σ,

1 C ǫ ≤ d ǫ (ξ 1 , ξ 2 ) ̺ ǫ (ξ 1 , ξ 2 ) ≤ C ǫ .

Invariance properties of boundaries

Definition 6.6 (Starlike) Let W ⊂ Σ. We say that W is starlike if, for any geodesic ray R, R(t) ∈ W =⇒ R([t, ∞)) ⊂ W . Equivalently: for any vertex v, v ∈ W implies C v ⊂ W . If W is starlike, its boundary ∂W is ∂W = {ξ ∈ ∂Σ : ∃R ∈ ξ, t > 0 with R([t, ∞)) ⊂ W }.
Cones and shadows are starlike by definition and umbrae are starlike by Lemma 5.4(1). We will often use the following facts without reference: Lemma 6.7 For i = 1, 2 let V i be horizontal sets of vertices at the same level, and let

U i = U (V i ) be their corresponding umbrae. If ∂U 1 ∩ ∂U 2 = ∅, then |V 1 -V 2 | hor ≤ 1.
Proof: Let ξ denote an element of the common intersection and suppose (ξ n i ) are sequences in ∂U i such that ξ n i → ξ as n → ∞, i = 1, 2. Then for all n, there exist rays

R n i representing ξ n i such that R n i ∩ V i = ∅ and {R n 1 |R n 2 } → ∞. Hence there exists n with {R n 1 |R n 2 } greater than the common level of V 1 , V 2 . It follows that |V 1 -V 2 | hor ≤ 1. Lemma 6.8 (Naturality of boundaries) Suppose W , W are starlike. If F k ( W ) = W , then ∂F k (∂ W ) = ∂W . Proof: The containment ⊂ is trivial. To prove the other inclusion, suppose R(∞) ∈ ∂W and w = R(t) ∈ W . Let γ = [w, R(∞)]; it is a vertical geodesic ray. Let R denote the lift of this segment based at w ∈ W . Since W is starlike, R(∞) ∈ W . Clearly ∂F k ( R(∞)) = R(∞).
Recall from §2 the definition of quasisimilarity. The proof of the lemma below is a direct consequence of the definitions. Lemma 6.9 (Induced quasisimilarities) Let W i , be shadows or umbrae of horizontal sets V i at levels n i , i = 1, 2. Let φ : W 1 → W 2 be an isometry which preserves the relation of being at the same level. Then φ induces a homeomorphism ∂φ : ∂W 1 → ∂W 2 which is a (C 2 ǫ , exp(-ǫ(n 2n 1 ))-quasisimilarity, where C ǫ is the constant as in the definition of the visual metric; see §6.1.

Metric estimates for boundaries of umbrae

Notation. Let R be a geodesic ray and t ∈ N. We denote by S(R, t) = S(B hor (R(t), 1)) the shadow corresponding to the closed horizontal ball of radius one centered at R(t), and by U (R, t) the corresponding umbra. Clearly, the shadow S(R, t) contains its umbra. The following lemma provides a partial converse. Lemma 6.10 (Umbrae contain shadows) Let R be a geodesic ray.

1. For all s > t, R(s) ∈ U (R, t).

2. Let V be any horizontal vertex set. If R(t) ∈ U (V ) then S(R, t + c) ⊂ U (V ) where c = m(H Σ ) + 3.

3. In particular: U (R, t) ⊃ S(R, t + c).

Proof: 1. Suppose v is any vertex with |R(s) -v| hor = 1. Then |R(t) -v [s-t] | hor ≤ 1, or in other words v [s-t] ∈ B hor (R(t), 1); hence v ∈ S(B hor (R(t), 1)) = S(R, t). Since v is arbitrary, we have then that |R(s) -S(R(t)) c | > 1. By the definition of umbra, R(s) ∈ U (R, t). 2. Let u = R(t), v = R(t + c), w ∈ S(R, t + c) and w ′ = [ow] ∩ B hor (v, 1). Note that |v -w ′ | ≤ 1. By Lemma [5.9, Unit speed penetration], |v -c S(V )| ≥ t + c -(t + m(H Σ )) = 3. Hence |w ′ -c S(V )| ≥ ||w ′ -v| -|v -c S(V )|| ≥ 2
and so B(w ′ , 1) ⊂ S(V ). Hence w ′ ∈ U (V ) and so w ∈ U (V ) since umbrae are starlike.

3. This is an immediate consequence of (1) and (2).

In the remainder of this section,

• C 0 denotes the universal additive constant as in §6.1;

• ǫ 0 is the positive constant as in Proposition 6.5;

• ǫ < ǫ 0 is fixed;

• C ǫ , d ǫ denote the constant and metric in Proposition 6.5.

Lemma 6.11 (Diameter estimates) For all t > C 0 + 4m(H Σ ), and for all geodesic rays R, we have the following diameter estimates:

1.

B ǫ R(∞), 1 C 1 exp(-ǫt) ⊂ ∂S(R, t) ⊂ B ǫ (R(∞), C 1 exp(-ǫt))
where

C 1 = 2C ǫ exp(ǫ(C 0 + m(H Σ ))) 2. B ǫ R(∞), 1 C 2 exp(-ǫt) ⊂ ∂U (R, t) ⊂ B ǫ (R(∞), C 2 exp(-ǫt))
where

C 2 = 2C ǫ exp(ǫ(C 0 + 4m(H Σ ))) 3. 1 C 3 exp(-ǫt) < diam ǫ ∂C R(t) < C 3 exp(-ǫt)
where C 3 = C ǫ exp(ǫ(C 0 + ⌈log d B⌉ + 1)), d = #X, and B ≤ #S + 1 is the maximum cardinality of a horizontal unit ball (here, C R(t) is the cone above the vertex R(t)).

4. For all k ∈ N, for all r < (1/C 1 ) exp(-ǫk), and for all ξ, if ξ = ∂F k ( ξ) then

B ǫ ξ, 1 C 4 exp(kǫ)r ⊂ ∂F k (B ǫ ( ξ, r)) ⊂ B ǫ (ξ, C 4 exp(kǫ)r).
where C 4 = C 2 1 .

Proof: 1. We prove the upper bound first. Let u 1 , u 2 ∈ S(R, t) and suppose u

′ i ∈ [ou i ] ∩ B hor (R(t), 1), i = 1, 2. Then |u ′ 1 -u ′ 2 | ≤ 2 which implies that [u 1 |u 2 ] ≥ t -1. Since u 1 , u 2 are arbitrary elements of S(R, t) it follows that d ǫ (ξ 1 , ξ 2 ) ≤ C ǫ exp(-ǫ(t-1)) < C 1 exp(-ǫt) for all ξ 1 , ξ 2 ∈ ∂S(R, t).
To prove the lower bound, let ξ = R(∞), and suppose ξ ′ ∈ ∂Σ satisfies [ξ|ξ ′ ] > t + m(H Σ ) + C 0 . Let R ′ represent ξ ′ . Then there exists infinitely many integers s such that [R(s)|R ′ (s)] > t + m(H Σ ). This implies that R ′ ∩ B(R(t), 1) = ∅, i.e. that ξ ′ ∈ ∂S(R, t) and the estimate follows.

2. By Lemma [6.10, Umbrae contain shadows, (2)] we have U (R, t) ⊃ S(R, t + c). This together with part (1) above yields the estimates.

3. The upper bound is clear. To find the lower bound, let k = ⌈log d (B)⌉ + 1 where B is the maximum cardinality of a horizontal unit ball. Note that there are d k elements of the cone C R(t) at level t + k. Thus some point u of C R(t) at level t + k lies at horizontal distance greater than 1 from R(t + k). Let R ′ be a ray through u. Then {R|R ′ } ∈ [t, t + k] and the claim follows easily.

4. This follows immediately from the fact that shadows map to shadows: F k (S(R, t)) = S(F k (R), tk), and estimate (1) above. The condition on r ensures that we may choose t > k.

Corollary 6.12 (Umbrae are open) Let V be any vertex set and U its umbra. Then ∂U is an open subset.

Proof: U is nonempty if and only if ∂U is nonempty, since umbrae are starlike. Suppose ξ ∈ ∂U . By definition (see § §5.1.7 and 6.2), this means there exists a ray R and a level t with R(∞) = ξ and R(t) ∈ U . Hence by Lemma [6.10, Umbrae contain shadows] S(R, t+c) ⊂ U . Hence B ǫ (R(∞), 1

C 1 exp(-ǫ(t + c))) ⊂ ∂S(R, t + c) ⊂ ∂U by Lemma 6.11(1).

∂F is a branched covering

Recall from Section 2.1 the definition of a finite branched covering. The main result of this section is Theorem 6.13 (∂F is a branched covering) The map ∂F : ∂Σ → ∂Σ is a finite branched covering map of degree d = #X.

Proof: Theorem 4.1(4) implies that ∂F is continuous, open and finite-to-one. Lemma 6.8 and Corollary 6.12 imply that ∂F is open. The map ∂F is also closed since ∂Σ is compact and Hausdorff. Therefore, since ∂Σ is locally connected (Theorem 4.1), it is enough to show ∀ξ ∈ ∂Σ,

ξ∈∂F -1 (ξ) deg(∂F, ξ) = d.
In the sequel, we will denote by ξ, ξ, ζ, etc. elements of ∂Σ. Recall the definition of local degree: deg(∂F, ξ) = inf

U ∋ ξ{#∂F
where the infimum is over all open U containing ξ. The proof will proceed by first interpreting the degree at a point on ∂Σ in terms of the map F on Σ itself, and then using the fact that F is a covering map of degree d.

To this end, recall that a point ξ ∈ ∂Σ is an equivalence class of rays emanating from o. Also, recall that balls are by definition subsets of vertices, and that for any subset V of vertices, Σ(V ) denotes the induced subcomplex of Σ containing V .

Let us denote by Σ(ξ) n = Σ (∪ R∈ξ B hor (R(n), 1)) .

Observe that for all n ∈ N and all ξ ∈ ∂Σ, Claim: For all n sufficiently large, the map

Σ(ξ) [-1] n ⊂ Σ(ξ) n-1 (
F : Γ( ξ) n+1 → Σ(ξ) n
is a covering map of degree δ( ξ).

Proof of Claim: The definition of δ( ξ) shows that for all n sufficiently large, the degree of the covering map F : Γ( ξ) n+1 → Σ(ξ) n is at least δ( ξ). We now establish the upper bound.

Suppose n is large and v ∈ Σ(ξ) n is any vertex. Write v = uw where w = v [-m(D)] , and consider now the set F -1 (v) ∩ Γ( ξ) n+1 = {uwx 1 , . . . , uwx k }. provided that n is sufficiently large.

Claim.

Since F is a covering map of degree d, the previous claim implies immediately that for all ξ ∈ ∂Σ, ξ∈∂F -1 (ξ) δ( ξ) = d.

The following lemma completes the proof of Theorem 6.13. provided that n is sufficiently large.

To establish the other bound, we make use of the following claim. The idea is that if f : X → Y is an fbc, then the image of the branch locus in Y is nowhere dense, so that any y ∈ Y is a limit of points each having the maximal number d = deg(f ) of distinct preimages. This is what we are going to show by means of the claim below. Roughly, here is the idea of the proof. Suppose instead of ∂F we consider a subhyperbolic rational map. Take a very small ball B which intersects the Julia set. Take a sequence of inverse branches of this ball which realizes the maximum of the degree over all inverse branches to obtain an iterated preimage B of B. Then all further iterated preimages of B must be unramified, and the union of all of these further preimages is dense in the Julia set.

Claim: There are a universal level n 0 and a constant M such that for any vertex ṽ with |ṽ| ≥ n 0 , there exists a vertex w with |ṽ| = | w| such that (i) |ṽ -w| hor ≤ M , and (ii) for all k ∈ N, any pair of distinct preimages of w under F -k are at least two (horizontal) units apart.

Proof of Claim: Let r = 1 and let n = n(r) be the constant given by Theorem 5.16. Choose a vertex u ∈ X n at level n arbitrarily, and set Γ 0 = Σ(B hor (u, 1)).

By Theorem 5.16,

p 0 = sup{deg(F k : Γ 0 → Γ 0 ) : k ∈ N, Γ 0 is a component of F -k (Γ 0 )}
is finite. Suppose F k 0 : Γ 0 → Γ 0 realizes this supremum. For convenience set Γ = Γ 0 . Then for all k ∈ N and all components Γ of F -k (Γ), deg(F k : Γ → Γ) = 1.

Let n 0 = n + k 0 be the level of Γ. Since by assumption the action is level-transitive, each horizontal subcomplex is connected. Hence the quantity M , defined as the maximum horizontal distance of a vertex at level n 0 to a vertex in Γ, exists.

We emphasize that the elements of U n are sets equipped with basepoints. While this leads to redundancy which could be avoided, it is convenient since it aids in the bookkeeping of preimages that follows. By abuse of notation, the index n will here be called the level of (U, R) ∈ Umb n , even though |o -U | = n + n 0 . Since ∂F is a finite branched covering (Theorem 6.4), we have

U n+1 = ∂F -1 U n (8)
in the sense that U n+1 is the set of all pairs ( ℧, ξ) which map under ∂F to a pair (℧, ξ) ∈ U n ; note that the same underlying set ℧ may arise more than once when equipped with different basepoints. This completes the definition of the family U n , n ∈ N.

Application of finiteness principles. By Theorem [5.17, Finiteness Principles] and the choice of n 0 , there are only finitely many isometry classes of maps of the form

F k : U → U
where (U, R) ∈ Umb n . The elements of Umb n are sets with basepoints. The supremum of the degrees p = sup

k sup ( U , R)∈Umb n+k deg(F k | U → U ) < ∞
is finite, and Umb 0 is finite, so we conclude:

There are only finitely many isometry classes of maps of pairs

F k : ( U , R) → (U, R)
where ( U , R) ∈ Umb n+k and (U, R) ∈ Umb n .

Boundary dynamics is metrically finite type

In this section, we prove that the boundary dynamics on Σ is of finite type, hence is cxc by Theorem 2.8. Actually, we will show the following slightly stronger statement in which the control of diameters is more precise: Theorem 6.15 (Boundary dynamics is of finite type) The dynamics on ∂Σ is metrically finite type, hence is cxc.

More precisely, we have the following. There exists a family of open covers U n , n = 0, 1, 2, . . ., constants C, λ > 1 and a finite set of M of pointed model maps

g m : ( V m , v m ) → (V m , v m ), m ∈ M

  Definition 2.1 (finite branched covering) The map f is a finite branched covering (abbrev. fbc) provided deg(f ) < ∞ and (i) x∈f -1 (y) deg(f ; x) = deg f holds for each y ∈ Y ;

Lemma 2. 2

 2 Let X, Y be Hausdorff locally compact topological spaces. An fbc f : X → Y of degree d is onto, proper and open: the inverse image of a compact subset is compact and the image of an open set is open. Furthermore, B f and V f are nowhere dense.

  are called the model open sets, and the collection of model open sets is denoted V, i.e. V = { V m : m ∈ M} ∪ {V m : m ∈ M}.

If

  A and B are horizontal at the same level, we analogously set |A -B| hor = inf{|a -b| hor : a ∈ A, b ∈ B}. Thus, the level of a set A is |A| = |A -o|. For r > 0 denote by N r (A) = {x ∈ Σ : ∃a ∈ A, |x -a| < r} the open r-neighborhood of A. The Hausdorff distance between A and B is d haus (A, B) = inf{r : A ⊂ N r (B), B ⊂ N r (A)}.

Figure 5

 5 Figure 5.1.4: At left, the cone C v . At right, the shadow S(V ) (light) and the umbra U (V ) (dark).

  and |u 1u 2 | = 1 (i.e. they are joined by a horizontal edge) then u [-1] i

  2 , and φ(wv) = wv φ .

Figure 5 . 2 :

 52 Figure 5.2: Finitely many cone types. The path γ is shown in bold. The edge-path based at v representing h| u 1 is contained in the horizontal ball of radius H Σ based at v and is shown in bold.

F

  k : S → S and of the form F k : U → U where S = S(v, r), |v| > n(r), S is a connected component of F -k (S), and U , U are their corresponding umbrae. Proof: By Corollary 5.15 and Lemma 5.8, it suffices to show that the diameter of a component Γ of F -k (Γ) is uniformly bounded whenever Γ = Σ(B(v, r)) and |v| is sufficiently large. The bound is implied by [Theorem 5.16, Bounded degree]. We now establish Theorem 5.16. The proof depends on a purely algebraic result about contracting selfsimilar group actions. Recall that m(L) = max{m(g) : ||g|| ≤ L} where m(g) is as in §4.2. In the theorem below, Stab G (v) is the stabilizer of v in G, B G (1, L) is the ball of radius L about the identity in G with respect to the word metric ||•||, the group Stab(v) ∩ B G (1, L) is the subgroup of G generated by their intersection, and Stab(v) ∩ B G (1, L) .vw is the orbit of the vertex vw under the action of this subgroup.

[

  7)since Σ is an augmented tree. Recall that F maps equivalence classes of rays surjectively onto equivalence classes of rays, and maps horizontal balls of radius one surjectively onto horizontal balls of radius one (cf. Lemma 5.2). It follows that whenever ∂F ( ξ) = ξ, the restrictionF : Σ( ξ) n+1 → Σ(ξ) nis surjective for all n ≥ 0. Then the quantityδ( ξ) n+1 = max v∈Σ(ξ)n #{x : vx ∈ Σ( ξ) n+1 } = max{#F -1 (F (ṽ)) ∩ Σ( ξ) n+1 : ṽ ∈ Σ( ξ) n+1 }is the maximum cardinality of a fiber of this restriction. It follows that δ( ξ) n+1 ≤ δ( ξ) n holds so that the limit δ( ξ) = lim n→∞ δ( ξ) n exists. We are going to show that in fact δ( ξ) = deg(∂F, ξ).Although F (Σ( ξ) n+1 ) = Σ(ξ) n , the restriction F | Σ( ξ) n+1 need not be proper. Let Γ( ξ) n+1 denote the unique component of F -1 (Σ(ξ) n ) which intersects Σ( ξ) n+1 ; a priori, it is larger than Σ( ξ) n+1 . Its diameter, however, is uniformly bounded by a constant D depending only on d and the number of generators in S. Let m(D) denote the "magic level" such that for any pair of vertices v 1 , v 2 at the same level, |v 1v 2 | hor ≤ D implies v

  By definition, there exists a rayR ∈ ξ such that |R(n) -v| ≤ 1. Choose a lift R of R under F representing ξ such that F ( R) = R. Then by definition | R(n + 1)uwx i | hor ≤ D, i = 1, . . . , k.By the definition of m(D) we have| R(n + 1m(D))wx i | hor ≤ 1, i = 1, . . . , k which implies that wx i ∈ Σ( ξ) n+1-m(D) and hence that k ≤ δ( ξ, v [-m(D)] ) n+1-m(D) ≤ δ( ξ) n+1-m(D) = δ( ξ)

  Lemma 6.14 (Interpretation of local degree) For all ξ ∈ ∂Σ, deg(∂F, ξ) = δ( ξ).Proof: We first establish ≤. Suppose ∂F ( ξ) = ξ and k is the local degree at ξ. For n ∈ N letU n = { ζ ∈ ∂Σ : ( ξ| ζ) > n + C 0 } and U n = ∂F ( U n ) where C 0 is as in §6.1. Then { U n } is a basis of neighborhoods of ξ.Then by the definition of local degree, for all large n, we havek = deg(∂F, ξ) = max ζ∈Un {#∂F -1 (ζ) ∩ U n }.Let us fix such an n and consider a point ζ ∈ U n which realizes the above supremum. Let R ∈ ξ, S ∈ ζ, R ∈ ξ be representing rays. Then by the definition of U n , there exist preimages S i , i = 1, . . . , k, of S under F such that for each such i, the divergence level satisfies { R| S i } > n. Note that the rays S i are all distinct, since they are preimages of a ray. By the definition of divergence level, for all such i,| R(n) -S i (n)| hor ≤ 1. Hence S i (n) ∈ Σ( ξ) nand so since each S i (n) maps to the same point F ( S i (n)) = S(n -1) we havek ≤ δ( ξ) n = δ( ξ)

From the properties of shadows (Lemma 5.4) we get a result similar to the previous one for shadows.

Lemma 5.6 (Pullbacks of shadows) Fix a positive integer r > 0, and let v be a vertex at level > r. Denote by S the shadow S(v, r). Then for all k > 0, 1. F -k (S) ∩ X * = F k (ṽ)=v S(ṽ, r) ∩ X * .

2. If S is a component of F -k (S) and V = F -k (v) ∩ S then S = S( V ) = Σ ∪ ṽ∈ V S(ṽ, r) ∩ X * .

3. If S i , i = 1, 2 are two distinct components of F -k (S) then | S 1 -S 2 | ≥ 2.

Umbrae

The darkest part of a shadow is called its umbra.

Given a vertex set V we define its umbra U (V ) as the subcomplex induced by the set of vertices u ∈ S(V ) ∩ X * such that |u -c S(V )| > 1; see Figure 5.1.4. Then

The lemma below gives a sufficient condition for an umbra to be nonempty. Easy examples (e.g. [START_REF] Nekrashevych | Self-similar groups[END_REF]Figure 3.1]) show that it is not, however, a necessary condition.

Lemma 5.7 (Unit ball inside implies umbra is nonempty) If B hor (v, 1) ⊂ V then for all x ∈ X we have C xv ⊂ U (V ).

Proof: Briefly: the map G induced by the left-shift is 1-Lipschitz. In more detail: let y ∈ c S(V ) ∩ X * and suppose |wv -y| hor = 1 for some word w ∈ X * \ {∅}. Let y ′ = y [-|w|] . Then |vy ′ | ≤ 1 by Lemma 5.4,(2), and so y ′ ∈ B hor (v, 1). But since y ∈ c S(V ), we have y ′ ∈ c S(V ) by Lemma 5.4(1) and so B hor (v, 1) ⊂ V .

Since the maps F, G induced by the right and left shifts commute, Lemma 5.4 implies Lemma 5.8 (Naturality of umbrae) When restricted to components, umbrae are natural with respect to the dynamics. That is: suppose

The following observation will be used later (in the proof of Lemma 6.10) to show that boundaries at infinity of umbrae are open.

We now show (u 1 v φ ) h = u 2 v φ . By the definition of a selfsimilar action,

We have

Recalling the definition of Γ, it follows that the restriction h| u 1 is represented by an edge-path in Γ starting at v. It is a loop since v h|u 1 = v. Since φ : Γ → Γ φ is an isomorphism of labelled graphs, the same edge-path representing h| u 1 , when starting at v φ , is also a loop. Hence (v φ )

If D = diamV , the hull of V is approximately a horizontal H Σ -neighborhood of the convex hull of V . The hull of V contains all vertices lying on normal form geodesic segments joining elements of V . To see this, let γ be any such geodesic; it has length at most D and so its vertical portions each have length bounded by ⌈D/2⌉.

Since the horizontal portion has length at most H Σ it follows that the vertices of γ lie in the hull. Hence, the induced subgraph Σ( V ) of the hull of V is always connected.

Lemma 5.12 (Naturality of hulls) We say that two induced subcomplexes of Σ are isometric if there is a cellular isomorphism between them which is distance-preserving. The relation generated by this property is clearly an equivalence relation. The isometry type of a subcomplex is defined as its corresponding equivalence class.

The theorem below enunciates the following principle: the isometry type of a shadow of a horizontal subset is determined by the isomorphism type of a (suitably large, depending on its diameter) associated hull.

Given now any vertex ṽ at level n > n 0 , put l = nn 0 , and let v = F l (ṽ). By the definition of M , there exists a vertex w ∈ Γ and a horizontal edge-path γ of length at most M joining v to w. Let w be the endpoint of the lift of γ under F l based at ṽ. Then |ṽ -w| hor ≤ M .

By construction, for all j > 0, each connected component Γ of the preimage of Γ under F j maps to Γ by degree one. Hence there are d j such preimages. By Lemma 5.4, for a fixed j, any two such preimages Γ i , i = 1, 2 are at least two units apart. In particular, this holds for j = k + l. We conclude that each of the d k inverse images of w under F -k are at least two apart, and the Claim follows.

Claim

Now suppose that k = δ( ξ). Then for all large n we have

Fix n large, let v ∈ Σ(ξ) n , and suppose δ( ξ, v) = δ( ξ) n+1 , so that

Apply the Claim (with ṽ = v in the hypothesis) to obtain a vertex w (called w in the conclusion) for which |v -w| hor ≤ M , and for which all of the iterated preimages of w at a given level are at least two horizontal units apart. Let γ be a horizontal edge-path joining v and w and let wi be the unique preimage of w obtained by lifting γ under F based at vx i = ṽi . Then the wi 's are all distinct. Let S be a ray through w and let S i be the lifts of S through wi . Since the wi 's are at least two apart, the rays S i are in distinct equivalence classes ζi , (Lemma 5.3), each of which maps to ζ = [S]. Since this occurs for all n large, we have deg(∂F, ξ) ≥ k = δ( ξ).

Lemma

Theorem 6.13

Dynamics on ∂Σ

In the next two sections, we prove that the dynamics on ∂Σ is of finite type with respect to the visual metric. In this section, we define the family U n , n = 0, 1, 2, . . . of open covers of ∂Σ, and collect the necessary finiteness results. In the next section, we show that the dynamics on the boundary is of finite type. The construction of the family U n , n ∈ N, is somewhat technical, so we first give the general idea. Recall the definition of the cone C v associated to a vertex v ∈ X ( §5.1).

Let us pretend for the moment that the boundary at infinity of any cone is both open and connected. We would like to take U 0 to be the set {∂C v : |v| = n 0 } of boundaries at infinity of the set of cones at some fixed level n 0 . Suppose C is such a cone, C a preimage of C under some iterate F k , and p = deg(F k : C → C). Since probably C is not a cone but rather a union of cones, we may lose control of the degree p . However, as the level n 0 of the vertex defining C increases, the cone C gets smaller. Eventually, it is small enough so that the degree p is uniformly bounded independent of k. To make this rigorous, we use the finiteness principles, which assert that up to isometry, there are only finitely many local models for the map

Unfortunately, a priori we do not know if the boundaries of cones are open and connected. So, to make the above heuristic argument precise:

• we work with shadows and umbrae, to get open sets of the boundary;

• we take a finite covering by connected components of umbrae at some fixed level n 0 sufficiently large so that the finiteness principles apply;

• we add basepoints to these connected components to aid in indexing preimages.

Remark: There are known conditions which imply that the boundaries of cones are connected and equal to the closure of their interiors; see [START_REF] Nekrashevych | Self-similar groups[END_REF]§3.3.3].

Construction of U n . Take r = 1 and let n 0 = n(r) as in the statement of Theorem [5.17, Finiteness Principles]. Let

covers ∂Σ, where ℧(U, R) denotes the connected component of ∂U containing R(∞). This set exists since umbrae are open (Corollary 6.12) and ∂Σ is locally connected (Theorem 4.1).

Let

Given (U, R) ∈ Umb n we let ℧(U, R) denote the connected component of ∂U which contains R(∞), equipped with the basepoint R(∞). Finally, we set

where V m , V m are connected metric spaces, ṽm ∈ V m , v m ∈ V m , with the following property.

If

U n+k ∋ ( ℧, ξ) → (℧, ξ) ∈ U n under ∂F k , then there exist homeomorphisms ψ : ℧ → V m and ψ : ℧ → V m depending only on ℧, ℧ respectively such that

commutes, and such that ψ, ψ are respectively (C, λ n+k ) and (C, λ n )-quasisimilarities.

Like the metric constructed in Section 3.3 for topologically finite type maps, the metric d ε above has the property that diamU ≍ exp(-εn) where the constants are independent of U and n.

Proof: First, axiom [Expans] holds immediately from Lemma 6.11, since any open set on the boundary contains the boundary of a cone. Since any cone eventually maps onto all of Σ, its boundary eventually maps onto all of ∂Σ, so axiom [Irred] holds as well.

We now establish the existence of a dynatlas. Let M denote the set of isometry classes of maps of pairs

one may choose this representative to have minimal level if desired (it is more convenient here not to normalize the sets to have diameter 1). Let ( V m , ṽm ) = (℧( U m , R m ), R m (∞)), (V m , v m ) = (℧(U m , R m ), R m (∞)), and g m = ∂F km | Vm .

Suppose now U n+k ∋ ( ℧, ξ) → (℧, ξ) ∈ U n is induced by ∂F k : ( U , R) → (U, R) where ℧ = ℧( U , R) and ℧ = ℧(U, R). Then there exists m ∈ M and isometries φ : U → U m , φ : U → U m such that the diagram below commutes:

Suppose U m has level n m . Then U has level n m + k m while the levels of U , U are n + k and n, respectively. By Lemma 6.9, the maps