Quasiconvex Subgroups and Nets in Hyperbolic Groups Citation Mack, Thomas Patrick (2006) Quasiconvex Subgroups and Nets in Hyperbolic Groups. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/35GG-W072. https://resolver.caltech.edu/CaltechETD:etd-06052006-141903 Abstract Consider a hyperbolic group G and a quasiconvex subgroup H of G with [G:H] infinite. We construct a set-theoretic section s:G/H -> G of the quotient map (of sets) G -> G/H such that s(G/H) is a net in G; that is, any element of G is a bounded distance from s(G/H). This set arises naturally as a set of points minimizing word-length in each fixed coset gH. The left action of G on G/H induces an action on s(G/H), which we use to prove that H contains no infinite subgroups normal in G. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: cone type; finite automata; hyperbolic geometry; nets; quasiconvex; quasiconvexity; section Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Calegari, Danny C. Thesis Committee: Calegari, Danny C. (chair) Oh, Hee Aschbacher, Michael Dunfield, Nathan M. Defense Date: 12 May 2006 Record Number: CaltechETD:etd-06052006-141903 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-06052006-141903 DOI: 10.7907/35GG-W072 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 2461 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 05 Jun 2006 Last Modified: 21 May 2025 22:46 Thesis Files Preview PDF - Final Version See Usage Policy. 315kB Repository Staff Only: item control page

Quasiconvex Subgroups and Nets in Hyperbolic Groups Thesis by Thomas Patrick Mack In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 2006 (Defended May 12, 2006) ii c 2006 Thomas Patrick Mack All Rights Reserved iii For my grandparents Acknowledgements I would like to thank my adviser, Danny Calegari, for his advice and guidance; Nathan Dunfield and Dinakar Ramakrishnan for their helpfulness in preparing this work; Michael Aschbacher and Hee Oh for graciously agreeing to serve on my Thesis Advisory Committee; and my family and friends for their patience and support during my research. iv Abstract Consider a hyperbolic group G and a quasiconvex subgroup H ⊂ G with [G : H] = ∞. We construct a set-theoretic section s : G/H → G of the quotient map (of sets) G → G/H such that s(G/H) is a net in G; that is, any element of G is a bounded distance from s(G/H). This section arises naturally as a set of points minimizing word-length in each fixed coset gH. The left action of G on G/H induces an action on s(G/H), which we use to prove that H contains no infinite subgroups normal in G. v Contents Acknowledgements iv Abstract v 1 Introduction 1 2 The Geometry of Hyperbolic Spaces 3 3 Quasiconvexity 16 4 Finite Automata 22 5 Nets in Groups 32 6 Nets in Hyperbolic Groups 36 Bibliography 45 vi Chapter 1 Introduction Let G be a group with finite generating set Σ. The Cayley graph Γ = C(G, Σ) is defined to be the graph with vertex set G and edges connecting those g, g 0 ∈ G with g = g 0 σ for some σ ∈ Σ. (We assume that Σ is closed under inversion, so that this relation is symmetric.) A hyperbolic group is one for which Γ has the large-scale structure of a tree. That is, geodesics are “almost” unique, in the sense that there exists a constant C > 0 such that any two geodesics γ(t), γ 0 (t) between the same points satisfy d(γ(t), γ 0 (t)) < C for all t. Let H be a finitely generated subgroup of G, and choose a finite generating set Σ0 for it. Assume without loss of generality that Σ0 ⊂ Σ. Then the Cayley graph Γ0 = C(H, Σ0 ) naturally embeds in Γ, and so there are two natural metrics on Γ0 ⊂ Γ: the path-length metric d0 considering chains that remain in Γ0 for all time, and the path-length metric d condering all chains in Γ. A quasiconvex subgroup is one for which these two metrics differ by no more than a constant multiplicative factor. The purpose of this paper is to prove the following theorem: Theorem. Let G be a hyperbolic group, and let H ⊂ G be a quasiconvex subgroup. If [G : H] = ∞, then there exists a (set-theoretic) section s : G/H → H of the quotient map G → G/H such that s(G/H) is a net in G; that is, supg∈G d(g, s(G/H)) is finite. The argument depends on showing that for suitable s, there exists a finite automaton recognizing the language L of points in s(G/H). By a geometric argument, any point in Γ lies within a bounded distance of the prefix closure L of L. Since L is a regular language, it follows that any point in L is a bounded distance from a point in L, proving the theorem. The first three preliminary sections of the paper summarize general results in hyperbolic geometry that are used in the subsequent sections. Section 2 is a broad overview of hyperbolic topological spaces and hyperbolic groups, including many examples of such objects. Section 3 covers the properties of quasiconvex subgroups and several methods of their construction. General references for these two sections include [7], which discusses hyperbolic spaces and groups in detail; [2], which covers the large-scale geometry of general metric spaces; and [8], which outlines many results in combinatorial 2 group theory used throughout the paper. Section 4 is an overview of finite automata and regular languages. This machinery is useful not only for its direct use in the proof of the main theorem, but also because arbitrary hyperbolic groups have an automatic structure; the set of geodesics in Γ can be recognized by a finite automaton. The general material on finite automata can be found in [5], and [3] contains specific applications to hyperbolic groups. Section 5 is a brief summary of the problem of finding nets as in the main theorem for arbitrary groups, including a few examples and counter-examples. Section 6 contains the proof of the main theorem and a result about normal subgroups embedded in quasiconvex subgroups that follows from it. 3 Chapter 2 The Geometry of Hyperbolic Spaces In this section, we recall the basic definitions of hyperbolic spaces and machinery of coarse geometry. Most of the material on hyperbolic geometry below is contained in [7] or [2], and the general machinery of combinatorial group theory is covered in [8]. There are many equivalent definitions of hyperbolic metric spaces, but we will mainly consider them as spaces in which geodesic triangles are thin: any side is contained in a bounded neighborhood of the other two sides, with the size of that bound independent of the particular triangle chosen. It is clear that Euclidean space does not have this property above dimension 1. On the other hand, it does hold in hyperbolic space Hn . A group is hyperbolic if it has the large-scale geometry of a hyperbolic space when considered as a metric space. In order to make this more precise, we first make two definitions. Definition. Let (X, d) be a metric space. A geodesic on X is a map f from a interval [0, N ] or [0, ∞) in R to X such that d(f t, f t0 ) = |t0 − t| for all t, t0 . If the former case, we call f a geodesic segment of length N ; otherwise, we call f a geodesic ray. For fixed K > 0 and  ≥ 0, a (K, )-quasigeodesic segment (resp. (K, )-quasigeodesic ray) is a map f : [0, N ] → X (resp. f : [0, ∞) → X) such that K −1 |t0 − t| ≤ d(f t, f t0 ) ≤ K |t0 − t| +  for all t, t0 . The space X is geodesic if there exists a geodesic between any two of its points. A geodesic is thus an isometry from an interval of R≥0 into X. We denote a geodesic f : [0, N ] → X with endpoints f (0) = p and f (N ) = p0 by [pp0 ]. Such a path is not necessarily unique; consider geodesics joining antipodal points on S n , for example. Definition. A geodesic metric space X is hyperbolic if it satisfies the following two equivalent properties: (i) There exists a constant δ ≥ 0 such that for any geodesic triangle in Γ with vertices p, q, r, the side [pq] lies in Nδ ([pr] ∪ [qr]), where N (S) = {x ∈ X : d(x, p) ≤  for some p ∈ S} denotes the closed -neighborhood around S. 4 (ii) There exists a constant δ ≥ 0 such that (p.q)x ≥ min {(p.r)x , (q.r)x } − δ (2.1) for all p, q, r, x ∈ Γ, where (·.·)· denotes the Gromov product (p.q)x = 1 (d(p, x) + d(q, x) − d(p, q)) . 2 To motivate the definition of the Gromov product, consider a tree X. Fix vertices p, q, r ∈ X. Since X is a tree, there exists a unique simple path between any two of its nodes. Any simple path in X is therefore a geodesic; in particular, geodesics in X are unique. Thus X satisfies condition (i) in the definition above for any δ > 0. Consider the geodesics [rp] and [rq], and write [rp] = (r = x0 , . . . , xn = p) and [rq] = (r = y0 , . . . , ym = q) for some xi , yi ∈ X. Let k denote the largest index such that xi = yi . Suppose that xi = yi for some l > k. Assuming without loss of generality that l is the smallest such index, the chains (xk , . . . , xl ) and (yk , . . . , yl ) are distinct simple paths from xk = yk to xl = yl . Thus xi 6= yi for all i > k. The chain (p = xn , xn−1 , . . . , xk , yk+1 , . . . , ym−1 , ym = q) is then a simple path from p to q, and is thus a geodesic. Thus 1 (d(p, r) + d(q, r) − d(p, q)) 2 1 = (|(x0 , . . . , xn )| + |(x0 , . . . , xm )| − |(xn , xn−1 , . . . , xk , yk+1 , . . . , ym−1 , ym )|) 2 (p.q)r = = k. (2.2) Thus (p, q)r measures the length of time for which geodesics [rp] and [rq] coincide. It follows immediately from (2.2) or this geometric interpretation that (p.q)x ≥ min {(p.r)x , (q.r)x } for all p, q, r, x ∈ X. If X satisfies condition (i) or (ii) in the preceding definition for some value of δ, then it also satisfies it for all δ 0 ≥ δ. Thus call X δ0 -hyperbolic if it satisfies conditions (i) and (ii) above with δ = δ0 ; X is then hyperbolic iff it is δ-hyperbolic for some δ. One of the most important basic results in hyperbolic geometry is the Morse Lemma, which states that quasigeodesics stay uniformly close to geodesics. In fact, this property characterizes hyperbolic spaces; any geodesic space for which the conclusion of the Morse Lemma holds is necessarily hyperbolic [2, 8.4]. Using this criterion, it is easily verified that hyperbolic space Hn is indeed a hyperbolic metric space for all n. Lemma 2.1 (Morse Lemma, [2, 8.4.20]). Let (X, d) be a δ-hyperbolic geodesic space. For any K > 0 and  ≥ 0, there exists a constant C > 0, depending only on δ, K, and , such that any (K, )-quasigeodesic segment with endpoints p, q ∈ X lies in the C-neighborhood of a geodesic [pq]. Since we are interested in only the coarse geometry of metric spaces, it is useful to consider a 5 class of maps slightly broader than isometries. For any metric spaces (X, dX ) and (Y, dY ), a function f : X → Y (not necessarily continuous) is a (C, )-quasi-isometric embedding for C > 0,  ≥ 0 if the inequalities C −1 dY (f x, f x0 ) ≤ dX (x, x0 ) ≤ CdY (f x, f x0 ) +  hold for all x, x0 ∈ X. If the precise values of C or  are irrelevant, call f a C-quasi-isometric embedding or simply a quasi-isometric embedding. A quasi-isometry X → Y is a quasi-isometric embedding f : X → Y such that Nr (f (X)) = Y for some r. Two spaces X, Y are quasi-isometric if there exists a quasi-isometry X → Y . The equivalence relation of quasi-isometry is the largescale analogue of isometry. As such, it is important to note that hyperbolicity is a quasi-isometry invariant. Corollary 2.2. Let X, X 0 be quasi-isometric length spaces. If X is hyperbolic, then so is X 0 . Proof. The corollary follows immediately from the Morse Lemma. Since geodesic triangles in a hyperbolic space are thin, geodesics to nearby points remain close for long periods of time. For trees, it was shown above that two geodesics [rp], [rq] coincide for a time equal to the Gromov product (p.q)r . A similar result holds in an arbitrary hyperbolic space. Lemma 2.3. Let (X, d) be a δ-hyperbolic geodesic space. Suppose r, r 0 are geodesic segments in X that have endpoints q, q 0 , respectively, and the same initial point p. For all 0 ≤ t ≤ (q.q 0 )p , we have d(rt , rt0 ) ≤ 4δ. In particular, we have d(rt , rt0 ) ≤ 4δ for all time t if q = q 0 . Proof ([2, 8.4.2]). Fix a geodesic [qq 0 ]. For any x ∈ [qq 0 ] and y ∈ X, we have 1 (d(q, x) − d(y, q) + d(q 0 , x) − d(y, q 0 )) 2 1 = d(y, x) + (d(q, q 0 ) − d(y, q) − d(y, q 0 )) 2 (y.q)x + (y.q 0 )x = d(y, x) + = d(y, x) − (q.q 0 )y . It follows that d(y, [qq 0 ]) ≥ (q.q 0 )y . For any t, we have 1 (d(q, rt ) + d(q 0 , rt ) − d(q, q 0 )) 2 1 ≥ (d(q, p) + d(q 0 , p) − d(q, q 0 )) − d(p, rt ) 2 (q.q 0 )rt = = (q.q 0 )p − t. Thus if t < hq, q 0 ip − δ, then d(rt , [qq 0 ]) ≥ (q.q 0 )rt > δ. Since X is δ-hyperbolic, the point rt ∈ [pq] must therefore lie in Nδ (r0 ). Hence d(rt , rt0 ) ≤ 2δ for t < (q.q 0 )p − δ. The lemma follows. 6 Corollary 2.4. Let (X, d) be a δ-hyperbolic geodesic space, and let r and r 0 be geodesic rays from a point p. If d(rt , rt0 ) is bounded as t → ∞, then d(rt , rt0 ) ≤ 4δ for all time t. Proof. Set C = supt d(rt , rt0 ). For any t ≥ 0, 1 (|r(t + C)| + |r0 (t + C)| − d(r(t + C), r 0 (t + C))) 2 1 = t + C − d(r(t + C), r0 (t + C)) 2 (r(t + C).r0 (t + C)) = ≥ t. Thus d(rt , rt0 ) ≤ 4δ for all time t ≥ 0 by Lemma 2.3. Corollary 2.5. Let X be a δ-hyperbolic space. For any p, q, q 0 ∈ X, let αp (q, q 0 ) denote the minimum value of t for which there exist geodesic segments γ = [pq] and γ 0 = [pq 0 ] such that d(γt , γt0 ) ≥ 4δ; if all such geodesics remain remain a distance less than 4δ apart for all time, set α p (q, q 0 ) = min {d(p, q), d(p, q 0 )}. Then (q, q 0 )p ≤ αp (q, q 0 ) ≤ (q, q 0 )p + 2δ. Proof. Let p, q, q 0 ∈ X, and choose geodesic segments γ = [pq] and γ 0 = [pq 0 ]. To simplify notation, set t = αp (q, q 0 ). By the definition of α, we have d(γt , γt0 ) ≤ 4δ. Hence 2 (q, q 0 )p = d(p, q) + d(p, q 0 ) − d(q, q 0 ) = d(p, γt ) + d(γt , q) + d(p, γt0 ) + d(γt0 , q) − d(q, q 0 ) = 2t + d(γt , q) + d(γt0 , q) − d(q, q 0 ) ≥ 2t − 4δ + d(γt , q) + d(γt , q 0 ) − d(q, q 0 ) ≥ 2t − 4δ. Thus t ≤ (q, q 0 )p + 2δ. The opposite inequality follows immediately from Lemma 2.3. In order to apply this geometric machinery to a group G, we consider its canonical action on a certain space, its Cayley graph. Hyperbolic groups are ones for which this associated space is hyperbolic in the sense defined above. Since G acts freely on this graph by isometries, hyperbolicity of the Cayley graph imposes important constraints on the algebraic structure of G. To simplify notation, we make the following convention throughout this paper: Convention. All generating sets are assumed to be finite and closed under inversion. Definition. Let G be a group with generating set Σ. Define the Cayley graph Γ = C(G, Σ) to be the graph with vertex set G and edges connecting those vertices g, g 0 with g 0 = gc for some c ∈ Σ. We often implicitly identify G with the set of vertices in Γ = C(G, Σ), or even with Γ itself. The free group F (Σ) with basis Σ admits a homomorphism onto G sending a word [c1 ] · · · [cn ] to the 7 corresponding element c1 · · · cn of G. Denote this evaluation map by either w → π(w) or w → w. To simplify notation, we often write w or π(w) simply as w when the intended meaning is clear. For any g ∈ G, the length of G with respect to Σ is defined to be  |g|Σ = min |w| : α ∈ π −1 (w) , where |w| is the usual word length in F (Σ); explicitly, |1| = 0 and |σ1n1 . . . σrnr | = |n1 | + · · · + |nr | for any nontrivial reduced word in F (Σ). Metrize Γ by setting d(x, y) = |x−1 y|Σ for all vertices x, y ∈ G, and extend this metric over the edges to make Γ into a geodesic length space. In particular, the length of a chain (x0 , . . . , xn ) in the graph Γ is simply n. Definition. A group G with generating set Σ is (word- or Gromov-)hyperbolic if the Cayley graph C(G, Σ) is a hyperbolic geodesic space. Any two generating sets Σ, Σ0 of G satisfy C −1 |x|Σ0 ≤ |x|Σ ≤ C|x|Σ0 , where C ≥ max {|σ|Σ0 : σ ∈ Σ} , max {|σ|Σ : σ ∈ Σ0 } . Hence the identity map C(G, Σ) → C(G, Σ0 ) is a quasi-isometry. By Corollary 2.2, word-hyperbolicity is therefore independent of the choice of generating set Σ. Since the Cayley graph of G is independent of the choice of generating set up to quasi-isometry, we write C(G) for C(G, Σ) when only its coarse geometry is important. It was shown above that any tree is 0-hyperbolic. Arbitrary hyperbolic spaces are therefore ones that have, in a rough sense, the large-scale geometry of a tree. For any free group G with basis  ±1 ) is a tree of degree 2n. Conversely, any Cayley {x1 , . . . , xn }, the Cayley graph C(G, x±1 1 , . . . , xn graph Γ = C(G, Σ) of an arbitrary group G defines a presentation G = hΣ | Ri, where R is the set of cycles in Γ with basepoint 1. Thus if Γ is a tree, then G is the free group generated by Σ. Hyperbolic groups therefore represent, in the same sense as above, groups with large-scale structure similar to that of a free group. To illustrate this correspondence, we list several examples of hyperbolic groups below. (i) Any finite group G has a Cayley graph quasi-isometric to a single point, which is clearly 0-hyperbolic. Hence G is also hyperbolic. (ii) Let G be a discrete, cocompact subgroup of the group Isom+ (Hn ) = SO+ (n, 1) of orientationpreserving isometries of Hn . If G acts freely on Hn , then the map g → x0 .g is a quasi-isometry C(G) → Hn for any basepoint x0 ∈ Hn [3]. Hence G is hyperbolic. The quotient Hn /G is 8 also a compact hyperbolic manifold, and its fundamental group is isomorphic to G. In low dimensions, we have SO + (1, 1) = R, SO+ (2, 1) = P SL2 (R), and SO+ (3, 1) = P SL2 (C). (iii) Conversely, let M n be a closed, hyperbolic manifold. The fundamental group G = π1 M acts on the universal cover M̃ = Hn by isometries. Fix a basepoint x0 ∈ Hn . The map g → x0 .g is then a quasi-isometry C(G) → Hn by the same proof as in (ii). Hence G is hyperbolic. (iv) More generally, consider a group G acting on a proper geodesic metric space X by isometries. If the action is proper and cocompact, then G is quasi-isometric to X [8, IV.23]. Thus if X is a hyperbolic space, then G is a hyperbolic group. (v) As indicated above, free groups of finite rank are hyperbolic. (vi) Under certain conditions, discussed in Propositions 3.9 and 3.10 below, amalgamated free products and HNN-extensions of hyperbolic groups are also hyperbolic. (For the definitions of these two constructions, see Section 3 below.) (vii) Let G be a hyperbolic group, and let H ⊂ G. Supppose [G : H] is finite. Choose a generating set Σ for H, then extend it to a generating set Σ0 of G. Then the inclusion C(H, Σ) → C(G, Σ0 ) is a quasi-isometry, so H is hyperbolic. Conversely, the same quasi-isometry shows that a group G is hyperbolic if it contains a hyperbolic subgroup of finite index. For example, the commutator subgroup of SL2 (Z) has index 12 and is free of rank 2 [1, IX.6], so SL2 (Z) is hyperbolic. (viii) As a special case of the preceding construction, extensions of hyperbolic groups by finite groups are also hyperbolic. An elementary hyperbolic group G is one that is a finite extension of a cyclic group. Thus G is either finite or an extension of Z by a finite group. (ix) Let N be a closed surface of genus g ≥ 2. Consider two foliations F s , F u on N that are transverse except at a common set of singularities x1 , . . . , xn . Assume each xi is a pi -pronged saddle singularity for some pi ≥ 3, as shown in Figure 2.1. Let µs and µu be transverse measures on F s and F u , respectively. An orientation-preserving homeomorphism ϕ : N → N is pseudo-Anosov [4, §6] if there exists a constant λ > 1 such that ϕ∗ µs (α) = λµs (α); ϕ∗ µu (β) = λ−1 µu (β) for all arcs α transverse to F s and β transverse to F u . Given such a map, define M to be its mapping torus. Thus M = N × [0, 1]/ ∼, where (x, 0) ∼ (ϕ(x), 1) for all x ∈ N . By Thurston’s Hyperbolization Theorem [13], M is a hyperbolic manifold. Hence π1 M is a hyperbolic group. Since N and M are hyperbolic and thus have contractible universal covers, all πi N and πi M 9 xi Figure 2.1: A p-pronged saddle singularity at xi for p = 3 (cf. Figure 5 in [14]). The foliations F s and F u are shown with dashed and solid lines, respectively. vanish for i ≥ 2. The long exact sequence corresponding to the bundle N → M → S 1 gives an exact sequence 1 // π1 N // π1 M // Z // 1, (2.3) where a generator t of Z acts on π1 N by t−1 xt = ϕ∗ (x). This sequence splits, giving an isomorphism π1 M = π1 N o Z. Thus if N has genus g ≥ 2, then π1 M has a presentation D E π1 M = x1 , y1 , · · · , xg , yg , t [x1 , y1 ] · · · [xg , yg ] = 1, t−1 xi t = ϕ∗ (xi ), t−1 yi t = ϕ∗ (yi ) . (2.4) To simplify notation, we adopt the following convention: Convention. Throughout this paper, G denotes a hyperbolic group with some fixed generating set Σ and Cayley graph Γ = C(G, Σ). Denote the metric on Γ by d(·, ·), and write |g| for |g| Σ = d(g, 1). Since the Cayley graph Γ of a hyperbolic group is a hyperbolic geodesic space with only finitely many geodesics between any two points, we can extend the Morse Lemma 2.1 to geodesic rays on Γ. Lemma 2.6. Let G be a δ-hyperbolic group, and set Γ = C(G, Σ) for some generating set Σ of G. 10 For any K > 0 and  ≥ 0, there exists a constant C > 0, depending only on δ, K, and , such that any (K, )-quasigeodesic ray from a point p lies within a distance C of a geodesic ray from p. Proof. Let r : [0, ∞) → Γ be a (K, )-quasigeodesic ray from p. Let r t denote the geodesic segment r | [0, t] for each t ≥ 0. By the Morse Lemma, there exists some constant C > 0 and geodesic segments γ t = [pr(t)] for all integers t > 0 such that d(r t (s), γ t (s)) < C for all time 0 ≤ s ≤ t. Define a sequence x0 , x1 , · · · ∈ Γ inductively as follows. Set x0 = 1. For each n > 0, choose some xn ∈ Γ such that d(p, xn ) = n and there exist infinitely many t such that x0 , . . . , xn−1 , xn ∈ γ t ; since the set {g ∈ G : d(p, g) = n} is finite, such a point xn must exist. For any i, j ≥ 0, there exists some t > i, j such that xi , xj ∈ γ t . Then d(xi , xj ) = d(γ t (i), γ t (j)) = |i − j|. Hence the set {xi } defines a geodesic ray from p. Furthermore, we have d(xi , r) = d(γ t (i), r) ≤ d(γ t , rt (i)) < C. Thus r is the required geodesic. Any isometry of Hn extends across the sphere at infinity ∂Hn . Thus any group of isometries acts on ∂Hn = S n−1 by homeomorphisms. Similarly, an arbitrary hyperbolic group acts on another analogous topological space, its hyperbolic boundary. Definition. Let X be a hyperbolic space, and fix x0 ∈ X. Let Ω(X) denote the set of sequences of points in X with (pi .pj )x0 → ∞ as i, j → ∞. Write (pi ) ∼ (p0i ) if lim inf i,j→∞ (pi .p0i )x0 = ∞. By (2.1), ∼ is an equivalence relation on Ω(X). The set of equivalence classes Ω(X)/ ∼ is the hyperbolic boundary ∂X. For a hyperbolic group G, set Ω(G) = Ω(Γ) and ∂G = ∂Γ. Definition. Let X and Y be hyperbolic spaces. For any quasi-isometry f : X → Y , let f∞ : ∂X → ∂Y denote the map f (pi ) = (f pi ). It is clear that ∂G is independent of the choice of generating set Σ. We also have (p.q)x − (p.q)x0 = 1 |d(p, x) − d(p, x0 ) + d(q, x) − d(q, x0 )| ≤ d(x, x0 ) 2 (2.5) for any x, x0 ∈ G, so the definition is also independent of the choice of x0 . To simplify notation, we take x0 = 1 in defining ∂G and write x.x0 = (x.x0 )1 . Let Ω0 (X) denote the set of geodesic rays from this fixed basepoint in X. For a group G, set Ω0 (G) = Ω0 (Γ); by the Morse Lemma, Ω0 (G) is independent of the choice of Σ up to quasi-isometry. Each r ∈ Ω0 (X) satisfies rt .rt0 = 1 0 0 0 2 (|t| + |t | − |t − t |) = min {t, t }, so (rt ) lies in ∂X. The next lemma shows that every element of the boundary arises in this way. Lemma 2.7. For any δ-hyperbolic space X, the map Ω0 (X) → ∂X given by r → (rt ) is surjective. Proof. Let (pi ) be an arbitrary sequence in ∂X. Since pi .pj → ∞, there exists for each t > 0 some Nt such that pi .pj > t for i, j ≥ Nt . Choose a geodesic [1pNt ] for each t, and let qt denote the point a distance t from 1 along this path. It is clear from the definition of ∂X that the sequence 11 (p0i ) = (pNi ) is equivalent to (pi ). For each i and j, we have p0i .p0j > min {i, j}. Since qj lies on the
chosen geodesic [1p0j ], the Gromov product qj .p0j = 21 |qj | + p0j − d(qj , p0j ) = |qj | = j. Thus  p0i .qj ≥ min p0i .p0j , qj .p0j − δ ≥ min {i, j} − δ. Hence lim inf p0i .qj = ∞, and so (p0i ) ∼ (qi ). For any t ≤ t0 , any geodesics [1pNt ] and [1pNt0 ] stay a distance of at most 4δ apart until time t by Lemma 2.3. Hence t0 − t = |qt0 | − |qt | ≤ d(qt , qt0 ) = t + t0 − 2 (t, t0 ) ≤ t0 − t + 4δ. (2.6) For each i, choose a geodesic si connecting qi to qi+1 . Let s denote the infinite chain (s0 , s1 , . . . ). By (2.6), s is a quasigeodesic. Thus by Lemma 2.7, there exists a geodesic ray such that d(r t , s) is bounded. The geodesic rt0 = r0−1 rt ∈ Ω0 (X) satisfies rt0 .st = 1 0 1 (|rt | + |st | − d(rt0 , st )) ≥ t − d(rt0 , st ) 2 2 for all time t. Thus rt0 .st → ∞ as t → ∞, and so (rt0 ) ∼ (st ) ∼ (qt ) ∼ (pt ). The map in Lemma 2.7 is not a bijection in general. Consider G = Z × Z2 , for example. The chains    (t, 0) if t ≤ k;    γk (t) = (k, 1) if t = k + 1;     (t − 1, 1) if t ≥ k + 2 are distinct geodesics in G for all positive k. All the sequences (γk (t)) are equivalent, however, since d(γk (t), γk0 (t)) is bounded for each k, k 0 . On the other hand, Z × Z2 is quasi-isometric to its finite index subgroup Z. The Cayley graph C(Z, {±1}) is a tree, and the only geodesic rays from 0 in it are the two paths γt = t and γt0 = −t. Since γt .γt00 = 21 (t + t0 − (t0 + t)) = 0 for all t and t0 , the sequences (γt ) and (γt0 ) in ∂G are inequivalent. The map Ω0 (G) → ∂G is thus a bijection in this case. For a hyperbolic space, the map Ω0 (Hn ) → ∂Hn is also bijective. To prove this result, suppose (pi ) ∼ (p0i ) in Ω(Hn ). By Lemma 2.7, there exist geodesics r, r 0 ∈ Ω0 (Hn ) such that (pt ) ∼ (rt ) and (p0t ) ∼ (rt0 ). Thus rt .rt0 → ∞ as t → ∞. Thus d(rt , rt0 ) ≤ 4δ for all time t by Lemma 2.3. But it follows from a brief computation [12, 11.6.8] that no two distinct geodesics in H n stay a bounded distance from each other for all time, so r = r 0 . The Gromov product can be extended across the boundary ∂X, and the resulting function defines 12 a metric on ∂X. Fix some basepoint p0 ∈ X. For any x, y ∈ ∂X, define (x.y)p0 = sup lim inf (xi .yj )p0 . (xi )∼x i,j→∞ (yj )∼y (2.7) For any sequences (xi ) ∼ (x0i ) in Ω(G), we have lim inf (x0i .yj )p0 ≥ lim inf min {(x0i .xj )p0 , (xi .yj )p0 } − δ i,j→∞ i,j→∞ = lim inf (xi .yj )p0 − δ, i,j→∞
since lim inf xi .p0j p = ∞. Applying the same argument to pi gives 0 lim inf (pi .qj )p0 − δ ≤ lim inf (p0i .qj )p0 ≤ lim inf (pi .qj )p0 + δ. i,j→∞ i,j→∞ i,j→∞ In particular, the supremum in (2.7) is finite. Give ∂X the topology generated by the basis of closed sets Nr (x) = {y ∈ ∂X : (x.y)p0 ≥ r} for all x ∈ ∂X and r ≥ 0. Note that this topology is independent of the choice of the basepoint by (2.5). The following proposition describes the structure of ∂X as a metrizable space. Since we do not directly use any of the topological properties of ∂X below, we omit its proof. Proposition 2.8. Let X be a hyperbolic space. (i) The topology defined above for ∂X is metrizable. (ii) If X is proper, then ∂X is compact. (iii) For any hyperbolic space Y and any quasi-isometry f : X → Y , the map f ∞ : ∂X → ∂Y is continuous. Proof. See Section 1.8 in [7]. In hyperbolic space Hn , it can be shown [12, 11.6] that the boundary ∂Hn defined above is homeomorphic to the usual sphere at infinity S n−1 . Furthermore, the point in ∂Hn corresponding to a sequence (pi ) ∈ Ω(Hn ) is its limit in this sphere [8, V.58]. By considering the geometric action of an arbitrary hyperbolic group G on its boundary ∂G, many algebraic properties of G can be determined. The following three useful propositions are examples of the results this technique produces. Proposition 2.9 ([8, V.58]). Let g ∈ G. If g is not torsion, then the centralizer CG (g) of g is virtually cyclic. (That is, CG (g) is a finite extension of a cyclic group.) Proposition 2.10 ([8, V.58]). If G is not elementary, then it contains a nonabelian free group. 13 In Example (iii) above, we showed that any closed, hyperbolic manifold has word-hyperbolic fundamental group. This result does not hold without the assumption of compactness. Consider the manifold M obtained by removing a tubular neighborhood of the figure-8 knot in R3 . This space can be constructed by gluing two regular ideal tetrahedra together, and therefore has the structure of a hyperbolic manifold of finite volume [11, 4.4.2]. The manifold M is the total space of a bundle over S 1 with fiber T 0 , where T 0 denotes the torus T 2 with a point removed. The long exact sequence in homology corresponding to the bundle T 0 → M → S 1 gives an exact sequence 1 // F2 // π1 M // Z // 1, where F2 = ha, bi is the free group of rank 2. Considering the monodromy of this bundle gives a presentation π1 M = ha, b, t | t−1 at = aba, t−1 bt = bai; (2.8) that is, π1 M is the HNN-extension of F2 by the homomorphism a → aba, b → ba [11, 4.4.3]. Thus t−1 [a−1 , b−1 ]t = t−1 aba−1 b−1 t = (aba)(ba)(a−1 b−1 a−1 )(a−1 b−1 ) = aba−1 b−1 = [a−1 , b−1 ]. It is clear from the presentation (2.8) that hti and h[a, b]i have trivial intersection, so t, [a−1 , b−1 ] = Z2 . But no hyperbolic group can contain a subgroup isomorphic to Z2 by Propostion (2.9), so π1 M is not word-hyperbolic. In addition to its boundary, an arbitrary hyperbolic space also acts on its corresponding Rips complex, another topological object associated to it. This space is a finite-dimensional CW-complex, and its quotient under the action by G is compact. Although we do not use it directly, we define the Rips complex and sketch a few of its most useful applications below. Definition. For any fixed d ≥ 0, define the Rips complex Pd (G) of G to be the simplicial complex consisting of all subsets S ⊂ G such that d(x, y) ≤ d for all x, y ∈ S. Since G acts on Γ by isometries, it also acts on Pd (G) by gS = {gs : s ∈ S} for any S ∈ Pd (G). The significance of the Rips complex to hyperbolic groups is a consequence of the proposition below. Proposition 2.11. For d ≥ 4δ + 1, the Rips complex Pd (G) is finite-dimensional, cocompact, and contractible. Proof. For any fixed g0 ∈ G, there are at most #Nd (g0 ) = #Nd (1) points g ∈ G with d(g, g0 ) ≤ d. Thus dim Pd (G) ≤ #Nd (1). For any S ∈ Pd (G) and s ∈ S, the set sS −1 ⊂ G contains 1. Hence each element of the quotient G\Pd (G) has a representative containing 1. Any element of G\Pd (G) 14 therefore has a representative in the finite set Nd (1). Thus Pd (G) is cocompact under the action of G. For the proof of the contractibility of Pd (G), see [7, 1.7]. The contractibility of Pd (X) for sufficiently large d actually holds for any hyperbolic space X, not just Cayley graphs of hyperbolic groups. We only use the Rips complex in the context of the two results below, however, which are specific to hyperbolic groups. The first follows from the fact that Pd (G) is simply-connected, and the second can be proved by considering the action of G on Pd (G). Proposition 2.12 ([8, V.56]). The hyperbolic group G has a finite presentation. Proposition 2.13 ([8, V.56]). There are only finitely many conjugacy classes of G that consist of torsion. As a final application of the Rips complex, we prove that hyperbolic groups have finite cohomology over Q. The proof below is adapted from the derivation in [1, VII] of a spectral sequence computing the homology H∗ (G\X) for a free G-complex X in terms of the homology of G with coefficients in the G-module H∗ (X). The basic argument is given in [1, VII.7], and the preliminary details are covered in [1, VII.5]. Proposition 2.14. The Q-module H ∗ (G, Q) (where G acts trivially on Q) is finitely generated. In particular, G has finite cohomological dimension over Q. Proof. Set X = P4δ+1 (G). Let C∗ = C∗ (X) ⊗ Q denote its cellular chain complex over Q, considered as a module over ZG. For any projective resolution F∗ of G, we have a spectral sequence [1, VII.5.3] 1 Epq = Hq (G, Cp ) = Hq (F∗ ⊗ZG Cp ) ⇒ Hp+q (F∗ ⊗ZG C∗ ). Let Xp denote the set of p-cells of X, and let Σp denote the set of equivalence classes of Xp modulo the action of G. Since G\X is a finite complex, Σp is finite for each p. Consider the action of G on each σ ∈ Σp . Since Σp is finite, there exists a subgroup G0 ⊂ G of finite index such that each g ∈ G0 acts on all σ ∈ Σp by orientation-preserving maps. The index [G : G0 ] is invertible in Q, so H ∗ (G, Q) embeds in H ∗ (G0 , Q) [1, III.10.4]. It is therefore sufficient to prove the result for G0 . Thus assume without loss of generality that all g ∈ G preserve the orientation of each cell of Σ p . As an abelian group, the cellular chain complex Cp satisfies Cp = M σ∈Xp Q. 15 Thus we have an isomorphism of ZG-modules Cp = M IndG Gσ Q. M   Q Hq G, IndG Gσ M Hq (Gσ , Q) M Hq (Gσ ) ⊗ Q σ∈Σp For fixed p, we therefore have H∗ (G, Cp ) = σ∈Σp = σ∈Σp = (2.9) σ∈Σp by Shapiro’s lemma [1, III.6.2]. Let g ∈ Gσ for some p-cell σ of X. The group Gσ permutes the p + 1 vertices of σ, so |Gσ | ≤ (p + 1)! |H|, where H is the stabilizer of some fixed vertex {x0 , . . . , xp } of σ. Each h ∈ H satisfies {hx0 , . . . , hxp } = {x0 , . . . , xp }. It follows that either H is trivial or {x0 , . . . , xp } = {1, g, . . . , g p−1 } for some g ∈ G of order p. In either case, H is cyclic of order dividing p. Thus Gσ is finite for all σ. Each group Hp (Gσ ) is hence annihilated by |Gσ | for p > 0 [1, III.10.1]. Thus Hp (Gσ ) ⊗ Q = 0 for all such p. By (2.9), we therefore have H∗ (G, Cp ) = M H0 (Gσ ) ⊗ Q = Q|Σp | . (2.10) σ∈Σp for all p. We have a spectral sequence [1, VII.7.2] 2 Kpq = Hq (G, Hq (X, Q)) = Hq (Fp ⊗ZG Hq (C∗ )) = Hq (Fp ⊗ZG C∗ ) ⇒ Hp+q (F∗ ⊗ZG C∗ ). (2.11) By Lemma 2.11, the space X is contractible. Thus the sequence (2.11) degenerates to an isomorphism Hp (G, Q) = Hp+q (F∗ ⊗ZG C∗ ). Hence 1 Epq = Hq (G, Cp ) ⇒ Hp+q (G, Q). 1 1 Since each Epq is a finite Q-vector space with Epq = 0 for q > dim X, each Hq (G, Q) is finite- dimensional with Hq (G, Q) = 0 for sufficiently large q. The required statement follows from the universal coefficient theorem for cohomology. 16 Chapter 3 Quasiconvexity In a hyperbolic space, quasigeodesics remain uniformly close to geodesics by the Morse Lemma. Quasiconvex subspaces, those in which geodesic segments starting in the subspace remain in a bounded neighborhood of it for all time, therefore share many of the properties of convex subspaces. In the case of hyperbolic groups, many constructions hence carry over to quasiconvex subgroups. In particular, any quasiconvex subgroup of a hyperbolic group is also hyperbolic by the Morse Lemma. Recall that we continue to use the convention that G denotes a δ-hyperbolic group with generating set Σ and Cayley graph Γ = C(G, Σ). Definition. Let X be a hyperbolic space, and let Y ⊂ X. For any constant K ≥ 0, the subspace Y is K-quasiconvex if any geodesic [pq] with p, q ∈ Y lies in NK (Y ). Call Y quasiconvex if it is K-quasiconvex for some K. For a hyperbolic group G with generating set Σ, a subgroup H ⊂ G is quasiconvex if the set of vertices of the Cayley graph Γ(G, Σ) corresponding to elements of H is quasiconvex. Since geodesics in G between points in H remain a bounded distance from H for all time, the word-length of elements of H over a generating set of H should approximate word-length over a generating set of the larger group G. Geodesics in G between the same points remain a bounded distance apart for all time, so the same property holds for geodesics in H; that is, H is hyperbolic. In order to make this argument rigorous, we require the following lemma. Lemma 3.1 ([8, IV.49]). Let H ⊂ G. If H is K-quasiconvex in G, then H is finitely generated. Proof. For each x ∈ Γ, choose a point f (x) ∈ H minimizing d(x, f x). Fix an arbitrary point x ∈ H, and choose a shortest path [1x] in Γ. Write [1x] as a chain (1 = x0 , . . . , xn = x) for some xi ∈ G. Since H is K-quasigeodesic, d(f xi+1 , f xi ) ≤ d(xi , f xi ) + d(xi+1 , f xi+1 ) + d(xi+1 , xi ) = 2K + 1 17 for all i. Thus x = f vn (f vn−1 )−1 f vn−1 (f vn−2 )−1 · · · (f v2 )−1 f v2 (f v1 )−1 f v1 with each f vi+1 (f vi )−1 ∈ H ∩ N2K+1 (1). The finite set H ∩ N2K+1 (1) therefore generates H. Any quasiconvex subgroup H ⊂ G therefore has a (finite) generating set Σ0 . Assume without loss of generality that Σ0 ⊂ Σ. Then the Cayley graph Γ0 = C(H, Σ0 ) embeds in C(G, Σ). By the Morse Lemma, this inclusion is a quasi-isometric embedding. The following lemma shows that this condition is not only necessary for quasiconvexity, but also sufficient. Lemma 3.2. Let G be a hyperbolic group, and let H ⊂ G be a finitely generated subgroup. Choose a finite generating set Σ0 for H, and assume without loss of generality that Σ ⊃ Σ0 . Set Γ0 = C(H, Σ0 ), and let d0 denote the metric on Γ0 . Then H is quasiconvex in G iff the inclusion map (Γ0 , d0 ) → (Γ, d) is a quasi-isometric embedding. Proof. Suppose H is K-quasiconvex in G. For each x ∈ Γ, choose a point f (x) ∈ Γ0 minimizing d(x, f x). Any geodesic [yy 0 ] in Γ with endpoints in Γ0 lies in NK (Γ0 ), so any two points p, p0 ∈ [yy 0 ] satisfy d(f p, f p0 ) ≤ d(p, p0 ) + 2K. Write [yy 0 ] as a minimum-length chain (y = x0 , . . . , xn = y 0 ). Then d(f xi , f xi+1 ) ≤ 2K + 1 for all i, so d0 (f xi , f xi+1 ) ≤ K 0 , where K 0 = max {|g|Σ0 / |g|Σ : |g|Σ ≤ 2K + 1}. Thus f [yy 0 ] is a K 0 -quasigeodesic in Γ0 . Hence d0 (y, y 0 ) ≤ K 0 d(y, y 0 ) for all y, y 0 ∈ Γ0 . Clearly d0 (y, y 0 ) ≤ d(y, y 0 ), so (Γ0 , d0 ) ,→ (Γ, d) is a quasi-isometric embedding. The converse follows immediately from the Morse Lemma. Corollary 3.3. Let G be a hyperbolic subgroup, and let H ⊂ G. Then the hyperbolicity of a subgroup H ⊂ G is independent of the choice of generating set for Σ. This corollary does not hold without the hyperbolicity assumption. For example, the subgroup H = h(1, 1)i of Z2 is clearly quasiconvex with respect to the generating set {±(1, 0), ±(1, 1)}. The chain γt =   (0, t) if t = 0, . . . , n;  (t − n, n) if t = n + 1, . . . , 2n, however, is a shortest path with respect to the generating set {±(1, 0), ±(0, 1)}, but maxt d(γt , H) is unbounded as n → ∞ [8, IV.49]. Corollary 3.4. Let G be a hyperbolic group, and let H ⊂ G. If H is quasiconvex, then it is a hyperbolic group. 18 Proof. Suppose H is K-quasiconvex in G. By Lemma 3.1, H is finitely generated. Choose a generating set Σ0 for H, and set Γ = C(H, Σ0 ). Let p1 , p2 , p3 be arbitrary distinct points in Γ0 , and let γ1 = [p2 p3 ], γ2 = [p3 p1 ], γ3 = [p1 p2 ] be geodesics in Γ. For each x ∈ Γ, choose a point f (x) ∈ Γ0 minimizing d(f (x), x). It was shown in the proof of Lemma 3.2 that each f γi is a (1, 2K)quasigeodesic in Γ0 . Let C 0 denote the constant in the Morse Lemma corresponding to C = 1 and  = 2K (in the notation of Lemma 2.1). Then there exist geodesics γi0 in Γ0 that have the same endpoints of γi and satisfy d(γi0 (t), γi (t)) < C 0 for all time t. Since G is hyperbolic, we have γ1 ⊂ Nδ (γ2 ∪ γ3 ). It follows that γ1 ⊂ Nδ+C 0 (γ20 ∪ γ30 ), and so H is (δ + C 0 )-hyperbolic. Lemma 3.1 can be used to prove that a given subgroup is not quasiconvex. In the opposite direction, the following lemmas give constructions for creating quasiconvex subgroups. Lemma 3.5 ([8, IV.49]). Let G be either a free group of finite rank or the fundamental group of a closed, hyperbolic surface. Then any finitely generated subgroup H ⊂ G is quasiconvex. Lemma 3.6 ([8, IV.49]). Let H, K ⊂ G. If H and K are both quasiconvex in G, so is H ∩ K. Lemma 3.7. Let G be a δ-hyperbolic group, and let ϕ ∈ Aut(G). If ϕ has finite order, then the group Gϕ = {g ∈ G : ϕ(g) = g} is quasiconvex in G. Proof. Choose a finite generating set for G closed under ϕ. Fix g ∈ G, and let g1 · · · gn be a geodesic path to g. Then ϕ(g1 ) · · · ϕ(gn ) is also a geodesic path to g, so xk = g1 · · · gk satisfies d(xk , ϕ(xk )) ≤ 4δ for k = 1, . . . , n. For each c ∈ N4δ (1), fix some hc with h−1 c ϕ(hc ) = c if such an element exists. For any x, y ∈ G, we have x−1 ϕ(x) = y −1 ϕ(y) iff x−1 y ∈ Gϕ . It follows that for each k, we have xk ∈ Gϕ hc for some hc . Hence Gϕ is K-quasiconvex for K = max |hc | . Thus, for example, the centralizer CG (x) of any torsion element of G is a quasiconvex subgroup. For elements of infinite order, the following lemma shows that hxi itself is quasiconvex. By Proposition 2.9, CG (x) is also quasiconvex in this case. Lemma 3.8 ([7, 8.1.D]). Any cyclic subgroup of G is quasiconvex. This result does not hold in arbitrary groups; in fact, it is useful as a criterion to determine whether a group is hyperbolic. For example, consider the Heisenberg group        1 a b        H = 0 1 c  : a, b, c ∈ Z ⊂ SL3 (Z).           0 0 1 19 Set  1 0 1     Z = 0 1 0 .   0 0 1  For all integers n,  n   n     1 1 0 1 0 0 1 0 0 1 n 0                   0 1 0 , 0 1 1  = 0 1 0 , 0 1 n          0 0 1 0 0 1 0 0 1 0 0 1      1 0 0 1 −n 0 1 0 0 1 n 0           = 0 1 0 0 1 n 0 1 0 0 1 −n      0 0 1 0 0 1 0 0 1 0 0 1   1 0 n2     = 0 1 0    0 0 1 2 = Zn . (3.1) 2 Thus over some generating set of H, the inequality |Z n | ≤ 4n holds for all n > 0. The subgroup hZi ⊂ H is therefore not quasiconvex. For any positive integers p and q, the Baumslag-Solitar group B(p, q) is defined by the presentation a, b | a−1 bp a = bq ; it is the HNN-extension of Z by the isomorphism pZ → qZ given by n → (q/p)n. Suppose p < q. For any n, we have n a−n bp an = a−(n−1) a−1 bp a n
pn−1 an−1 = a−(n−1) bp n−1 q n−1 a  q n−1 = a−(n−1) bp an−1 . n n It follows that a−n bp an = bq for all n. Thus over some generating set of B(p, q), we have |bq | ≤ 2n + pn = o(q n ) as n → ∞, since p < q. The subgroup hbi ⊂ B(p, q) is therefore not quasiconvex. Furthermore, no hyperbolic group can contain a subgroup isomorphic to B(p, q) for p < q. Clearly B(p, q) = B(q, p), and B(p, p) contains a subgroup ha, bp i isomorphic to Z2 . By Proposition 2.9, hyperbolic groups also do not contain a subgroup isomorphic to B(p, q) for any p, q > 0. Quasiconvexity is also useful in constructing hyperbolic groups. Let X and X 0 be groups with (not necessarily finite) presentations X = hS | Ri and X 0 = hS 0 | R0 i. For any subgroups A ⊂ X and A0 ⊂ X 0 and isomorphism α : X → X 0 , define the amalgamated free product X ∗α X 0 by the presentation hS, S 0 | R, R0 , a = α(a) for all a ∈ Ai. When there is a canonical choice of α (for example, X and X 0 are subgroups of another group Y , A = A0 , and α is the map resulting from 20 the inclusion of X and X 0 in Y ), the product X ∗α X 0 is often denoted by X ∗A X 0 or X ∗A0 X 0 . For X = X 0 , define the HNN-extension X∗α = hS, t | R, t−1 st = α(s) for all s ∈ Si. As the name implies, this group is an extension of X; that is, the canonical map X → X∗α is injective. Hence the isomorphism α : A → A0 in X extends to an inner automorphism of X∗α . Both of these constructions are independent of the particular choices of presentations for X and X 0 [10, IV.2]. Arbitrary amalgamated free products and HNN-extensions of hyperbolic groups are not necessarily hyperbolic; for example, the Baumslag-Solitar group B(p, q) is an HNN-extension of the elementary hyperbolic group Z. With a few additional assumptions, however, these groups remain hyperbolic in the quasiconvex case. Following [9], call a subgroup H ⊂ G conjugate separated if H ∩ H g is finite for all g 6∈ H, where H g = g −1 Hg. Proposition 3.9 ([9]). Let G be a hyperbolic group, and let α : H → K be an isomorphism between two subgroups H, K ⊂ G. Suppose that H ∩ K g is finite for all g ∈ G and that H is conjugate separated in G. If H and K are quasiconvex in G, then the HNN-extension G∗ α is a hyperbolic group. Proposition 3.10 ([9]). Let G and G0 be hyperbolic groups, and let α : H → H 0 be an isomorphism between subgroups H ⊂ G and H 0 ⊂ G0 . Suppose H is conjugate separated in G. If H and H 0 are quasiconvex in G and G0 , respectively, then the amalgamated free product G ∗α G0 is a hyperbolic group. As a final example of quasiconvexity, consider the group G = π1 M in Thurston’s construction (2.4). The cyclic subgroup H = hti ⊂ G is quasiconvex by Lemma 3.8, but there is also a direct  ±1 ±1 for G. Let f denote the quotient proof in this case. Take the generating set Σ = x±1 i , yi , t map G → Z in (2.3). Then for any word w = z1 tn1 1 z2 tn2 2 · · · zk tnk k representing tn , we have |w| ≥ |n1 | + · · · + |nk | ≥ |n1 + · · · + nk | = |f (w)| = |n| . Thus |tn | = n for all n. The group H = hti is hence actually convex in this case, not just quasiconvex: every geodesic with endpoints in H lies entirely within H. More generally, suppose that G = N o α H for some N C G and α : H → Aut(N ). Assume H is finitely generated. Choose a generating set Σ0 for H, and extend it to a generating set Σ of G. Let i : H → G denote the inclusion map, and let π : G → G/N = H denote the quotient map. Then (πi)h = h for all h ∈ H. Thus |h|Σ0 = |πih|Σ0 ≤ C |ih|Σ , where C = max {|πσ|Σ0 : σ ∈ Σ}. By the definition of Σ, we have |h|Σ0 ≥ |ih|Σ . Thus the inclusion i : H → G is a C-quasi-isometric embedding. By Lemma 3.2, H is quasiconvex in G. Even in the hyperbolic case, arbitrary subgroups are not necessarily quasiconvex. Consider instead the subgroup H = π1 N of G = π1 M for N, M as in Example (ix) of Section 2. Then 21 G = H o Z, where a generator of Z acts on H by ϕ∗ for some pseudo-Anosov map ϕ : N → N . Although both H and G are hyperbolic, H is not a quasiconvex subgroup of G [8, IV.49]. 22 Chapter 4 Finite Automata By Lemma 3.8, geodesic segments in the Cayley graph of a hyperbolic group remain close for all time. As a result, these groups are particularly amenable to analysis by combinatorial group theory. In this section, we recall some of the basic definitions and lemmas concerning finite automata, which are used both in deriving an important result of Cannon in this section and in proving the main result of this paper. Most of the definitions and results below are taken from [5], which also covers the material outlined here in more detail. Let Σ be a finite set. Define Σ∗ to be the set of sequences (x1 , . . . , xn ) with all xi ∈ Σ; we include the sequence () of length 0 in Σ∗ , called the null string . A language over Σ is a subset of 0 0 Σ∗ . For any w = (w1 , . . . , wn ) and w0 = (w10 , . . . , wm ) in Σ∗ , set ww0 = (w1 , . . . , wn , w10 , . . . , wm ). In particular, w = w = w for all words w. Definition. Let L, L0 be languages over a fixed alphabet Σ. (i) The concatenation LL0 is the language consisting of words ww 0 with w ∈ L and w0 ∈ L0 . (ii) The union L ∪ L0 is the union of the sets L, L0 ⊂ Σ∗ . (iii) The star closure L∗ consists of  and all words w1 w2 · · · wn for wi ∈ L. The language L is regular if it can be formed from the languages {σ} for σ ∈ Σ and {} by the operations (i), (ii), (iii) above. Definition. A deterministic finite automaton M is a quintuple (S, Σ, µ, Y, s0 ) satisfying the following properties: (i) The state set S is a finite set. (ii) The alphabet Σ is a finite set. (iii) The transition function µ is a map S × Σ → S. (iv) The set of accept states Y is a subset of S. 23 (v) The start state s0 is an element of S. Write sx for µ(s, x). Extend µ to Σ∗ inductively by setting s(x1 · · · xn ) = (s(x1 · · · xn−1 ))xn . For any automaton M = (S, Σ, µ, Y, s0 ), define the language recognized by M to be the subset L(M ) ⊂ Σ∗ of all words w with s0 w ∈ Y. We can represent a finite automaton (S, Σ, µ, Y, s0 ) visually as shown in the graph in Figure 4.1. Each circle in the graph corresponds to a state in S. For each state s ∈ S and each x ∈ Σ, we draw an arrow from s to the state µ(s, x) and label it with x. The accept states are drawn with a double border. The start state is the target of the bold arrow. In this representation, the state corresponding to s(w1 · · · wn ) is the endpoint of the path from s labelled w1 , . . . , wn . For simplicity, we often omit arrows that can never be used by words accepted by the automaton. In other words, the automaton fails to recognize a word if no appropriate arrow to follow exists at any point. Conceptually, a deterministic finite automaton represents a machine that inputs a word in Σ ∗ and outputs either yes (corresponding to an accept state) or no (corresponding to a reject state; that is, a state not in Y ), depending on whether the input has some desired property. The automaton in Figure 4.1, for example, accepts exactly those inputs that end in either 01 or 10. The set of all words w ∈ Σ∗ with s0 w ∈ Y is the language L(M ) accepted by M . It is often advantageous to relax the definition above slightly as follows. Definition. A non-deterministic finite automaton M is a quintuple (S, Σ, µ, Y, s0 ) satisfying the following properties: (i) The state set S is a finite set. (ii) The alphabet Σ is a finite set. (iii0 ) The transition function µ is a map S × (Σ ∪ {}) → 2S . (iv) The set of accept states Y is a subset of S. (v0 ) The set of start state S0 is a subset of S. As in the deterministic case, extend the map µ to Σ∗ inductively by setting s(x1 · · · xn ) = (s(x1 · · · xn−1 ))xn = [ s 0 xn , s0 ∈s(x1 ···xn−1 ) where sx = µ(s, x) for s ∈ S and x ∈ Σ. Figure 4.2 shows an example of a non-deterministic finite automaton, using the same conventions as in the deterministic case. This automaton recognizes the same language as the deterministic one in Figure 4.1. The states corresponding to s(w 1 , . . . , wn ) in this representation are all possible endpoints of paths labelled w1 , . . . , wn . For a non-deterministic finite automaton M = (S, Σ, µ, Y, s0 ), we also define the language L(M ) recognized by M to be the 24 0 1 0 0 0 0 1 0 0 1 1 1 1 1 Figure 4.1: A deterministic finite automaton. set of words w ∈ Σ∗ with Y ∩ s0 w non-empty for some s0 ∈ S0 . We can relax the definition of a finite automaton even further, as follows. Definition. A generalized finite automaton is a quintuple (S, Σ, µ, Y, s0 ) satisfying the following properties: (i) The state set S is a finite set. (ii) The alphabet Σ is a finite set. (iii00 ) The transition function µ is a map S × Σ∗ → 2S such that M (s, s0 ) = {w ∈ Σ∗ : s0 ∈ µ(s, w)} is a regular language over Σ for each fixed s, s0 ∈ S. (iv) The set of accept states Y is a subset of S. (v00 ) The set of start states S0 is a subset of S. We can represent a generalized finite automaton by a directed graph in the same manner as for deterministic and non-deterministic automata; the only difference is that edges are labelled with regular languages instead of elements of Σ ∪ {}. An example of such a graph is shown in Figure 4.3; it recognizes the same language as the automata in Figures 4.1 and 4.2. Define sw ∈ 2 S for all words w ∈ Σ∗ and s ∈ S as in the non-deterministic case. Under this representation, sw corresponds to all possible states that can be taken by following paths labelled with regular languages containing u1 , . . . , un for any words ui with w = u1 · · · un . Define the language L(M ) recognized by M to be the set of words w ∈ Σ∗ with Y ∩ s0 w non-empty for some s0 ∈ S0 . Theorem 4.1 (Kleene, Rabin, and Scott, [5, 1.2.7]). Let L be a language over an alphabet Σ. The following conditions on L are equivalent: (i) L is regular. 25 1 0  1  0,1 0 Figure 4.2: A non-deterministic finite automaton. (ii) There exists a deterministic finite automaton M recognizing L. (iii) There exists a non-deterministic finite automaton M recognizing L. (iv) There exists a generalized finite automaton M recognizing L. Not every language is regular. For example, suppose the language L = {x n1 xn2 : n ≥ 0} over Σ = {x1 , x2 } is recognized by a deterministic finite automaton M . For each n 6= m, the word xn1 xn2 n m n is an accept state and xm 1 x2 a reject state. It follows that s0 x1 and s0 x1 are distinct states of M for distinct n and m, where s0 denotes the start state of M. But M has only finitely many states, so L cannot be regular. Definition. Let Σ1 , . . . , Σn be alphabets. Choose a padding character $ 6∈ S Σi . Let wi ∈ Σ∗i for i = 1, . . . , n, and set N = max |wi |. Define the padded extension (w1 , . . . , wn )$ to be the pair (w̃1 , . . . , w̃n ), where w̃i is formed by appending N − |wi | copies of $ to wi . A padded string over Σ = Σ1 × · · · × Σn is a string of the form (w1 , . . . , wn )$ for some wi ∈ Σi , and a language over Σ is a set of padded strings over Σ. For example, over the alphabet {0, 1} × {0, 1}, we have (10, 1000) $ = (10$$, 1000). To simplify notation, we write the latter string as simply (10, 1000). For any languages L over Σ and L 0 over  Σ0 , define L × L0 to be the language (u, v)$ : u ∈ L, v ∈ L0 over Σ × Σ0 . All of the operations defined above extend to languages over product alphabets in the obvious way; for example, the union  $ of two languages L, L0 over such an alphabet is w : w$ ∈ L ∪ L0 . The important lemma below guarantees that many such operations preserve regularity. Lemma 4.2. Let L, L0 be regular languages over an arbitrary alphabet Σ, and let L 00 be a regular alphabet over Σ2 . Then the following languages are also regular: (i) L∗ . (ii) LL0 . (iii) L ∪ L0 26 01,10 0,1 Figure 4.3: A generalized finite automaton. (iv) ¬L = {u ∈ Σ∗ : u 6∈ L} (v) L ∩ L0 (vi) {u ∈ Σ∗ | ∃v ∈ L : uv ∈ L0 } (vii) L = {u ∈ Σ∗ | ∃v ∈ Σ∗ : uv ∈ L0 }. (viii) L × L0 . (ix) {x ∈ L | ∃x0 ∈ Σ∗ : (x, x0 ) ∈ L00 }. (x) {x ∈ L | ∃x0 ∈ L0 : (x, x0 ) ∈ L00 }. (xi) {x ∈ L | ∀x0 ∈ Σ∗ : (x, x0 ) ∈ L00 }. (xii) {x ∈ L | ∀x0 ∈ L0 : (x, x0 ) ∈ L00 }. Proof ([5, 1.2–1.4]). Choose finite automata M = (S, Σ, µ, Y, s0 ) M 0 = (S 0 , Σ, µ0 , Y 0 , s00 ) M 00 = (S 00 , Σ2 , µ00 , Y 00 , s000 ) recognizing L, L0 , and L00 , respectively. We construct finite automata recognizing each of the twelve languages in the lemma below. Although the regularity of the first three languages follows immediately from the definition of a regular language, showing that the set of languages recognized by finite automata is closed under star closure, concatenation, and union is an important step in the proof of Theorem 4.1. (i) The required automaton recognizing L∗ is formed by adding an -move from each accept state of M to the initial state s0 . (ii) Construct an automaton N by attaching an -move from each state of M to the start state s 00 ` of M 0 . More explicitly, set N = (M M 0 , Σ, ν 0 , Y 0 , s0 ), where ν(s, x) =   µ(s, x) ∪ {s0 } if s ∈ S; 0  µ0 (s, x) if s ∈ S 0 . 27 It is clear that L(N ) = L(M )L(M 0 ). (iii) Construct a non-deterministic automaton N by adding a state t0 to M ∪ M 0 and attaching arrows labelled with  from t0 to s0 and to s00 . Designate t0 as the initial state of N . More precisely, ` ` set N = (S S 0 {t0 } , Σ, ν, Y ∪ Y 0 , t0 ), where    µ(s, x) if x ∈ S;    ν(s, x) = µ0 (s, x) if x ∈ S 0 ;     {s , s0 } if x = t . 0 0 0 Then tw = s0 w ∪ s00 w for all w ∈ Σ∗ , so L(N ) = L(M ) ∪ L(M 0 ). (iv) The automaton (S, Σ, µ, S − Y, s0 ) recognizes exactly those words w with s0 w 6∈ Y ; that is, the language ¬L. (v) The regularity of L ∩ L0 = ¬(¬L ∪ ¬L0 ) follows immediately from parts (iii) and (iv). (vi) Let Z denote the set of states s ∈ S 0 such that sw ∈ Y for some w ∈ L. Then N = (M, Σ, µ, Z, s0 ) is the required automaton. (vii) Take L = Σ∗ in part (vi). (viii) Set N = (S × S 0 , Σ2 , ν, Y × Y 0 , (s0 , s00 )), where    (µ(s, x), µ(s0 , x0 )) if x, x0 6= $;    ν((s, s0 ), (x, x0 )) = (s, µ(s0 , x0 )) if x = $;     (µ(s, x), s0 ) if x0 = $. Then (s, s0 )(w, w0 ) = (sw, s0 w), so N recognizes the language L × L0 . (ix) Let N denote the automaton formed by replacing every arrow label (x, x0 ) in M 00 with x, producing a non-deterministic finite automaton over Σ. Explicitly, N = (S 00 , Σ, Y 00 , ν, s000 ), where ν(s, x) = [ ν(s, (x, x0 )). x0 ∈Σ Clearly N recognizes the given language. (x) The language Σ∗ × L0 is regular by part (viii), so {x ∈ L | ∃x0 ∈ L0 : (x, x0 ) ∈ L00 } = {x ∈ L | ∃x0 ∈ Σ∗ : (x, x0 ) ∈ L00 } ∩ (Σ∗ × L0 ) is regular by part (ix). 28 (xi) The regularity of {x ∈ L | ∀x0 ∈ Σ∗ : (x, x0 ) ∈ L00 } = ¬ {x ∈ L | ∃x0 ∈ Σ∗ : (x, x0 ) ∈ ¬L00 } follows from parts (iv) and (ix). (xii) The language {x ∈ L | ∀x0 ∈ L0 : (x, x0 ) ∈ L00 } = {x ∈ L | ∀x0 ∈ Σ∗ : (x, x0 ) ∈ L00 } ∩ (Σ∗ × L0 ) is regular by the same argument as in part (x). Note that for any group X with (finite) generating set Σ, the evaluation map w → w from F (Σ) to G extends to a map Σ∗ → G by considering each word in Σ as an element of F (Σ). This identification is not unique because of inverses, but the resulting map is still well-defined. We also denote the evaluation map on Σ∗ by either w → π(w) or w → w. The connection between hyperbolic groups and finite automata is the property of automation. In an automatic group X, there exists a finite automaton determining whether two words w, w 0 in a certain set of representatives of elements of X satisfy π(w 0 ) = π(w)g0 for any fixed g0 ∈ G. In particular, the word problem for G is solvable. That is, there exists an algorithm determining whether a given word w (restricted to a certain subset of Σ∗ ) represents the identity in X. As a result, many problems concerning hyperbolic groups are amenable to the techniques of geometric group theory. Definition. Let X be an arbitrary finitely generated group with generating set Σ. Call X automatic if there exist finite automata W over Σ and Mx over Σ2 for each x ∈ Σ∪{} that satisfy the following two properties: (i) For each g ∈ X, there exists some w ∈ L(W ) with w = g. (ii) The language recognized by Mx is L(Mx ) = {(u, v) ∈ L(W ) × L(W ) : ux = v}. The automaton W is called a word acceptor, and Mx is called a multiplier automaton for x 6=  and an equality recognizer for x = . The condition of having an automatic structure is called automation. Lemma 4.3 ([5, 2.4.1]). Automation is independent of the choice of generating set Σ. To prove that hyperbolic groups are automatic, we first introduce Cannon’s idea of cone types [3]. Definition. For any x, y ∈ G, write x ≤ y if there exists a geodesic segment [1y] passing through x. Define an equivalence relation on G by setting x ∼ x0 if the inequality x ≤ y holds exactly when x0 ≤ (x0 x−1 )y. The quotient C(G) = G/∼ is the set of cone types of G, and the image of x ∈ G in C(G) is the cone type of x, denoted by C(x). 29 To simplify notation, write u ≤ v for words u, v ∈ Σ∗ if u ≤ v. For any C ∈ C(G), write C ≤ x if g ≤ gx for some (and hence every) g ∈ G with C(G) = C. For any fixed x ∈ G, the relation g ≤ gx clearly depends only on the cone type of g. Thus write C(g)x for C(gx) if C(g) ≤ x. Theorem 4.4 (Cannon). For any hyperbolic group G, the set of cone types C(G) is finite. Proof. See [3] for a geometric proof or [5, 3.2] for a more combinatorial one. Definition. Define the language of geodesics Λ(G) to be the set of all words w ∈ Σ ∗ with |w| = |w|Σ . (Note that Λ also depends on the choice of Σ.) Thus elements of Λ(G) correspond to geodesics in Γ from 1 to any other point. These geodesics will form the language L(W ) in the automatic structure for G. It is not true in general, even for hyperbolic groups, that any language can be chosen for L(W ). There exists no finite automaton recognizing the language {xn1 xn2 : n ≥ 0}, for example, so Z has no automatic structure with L(W ) = ∗ 0 ∪ {−1, 1} . The automation of any hperbolic group G will follow from the three corollaries of Theorem 4.4 below. Corollary 4.5. The language Λ(G) over Σ is regular. Proof ([5, 3.2]). Define an automaton M as follows. For the set of states S of M , take C(G) with one additional state r. The transition function of M is given by µ(C, x) =   Cx  r if C ≤ x; otherwise on states C ∈ C(G), and µ(r, x) = r for all x. The automaton M = (S, Σ, µ, C(G), C(1)) then accepts exactly those words w ∈ Σ∗ with 1 ≤ π(w1 ) ≤ π(w1 w2 ) ≤ · · · ≤ π(w). These words are precisely the elements of Λ(G). Corollary 4.6. For any fixed g ∈ G, the language L = {w ∈ Λ(G) : w ≤ wg} is regular. Proof. Choose a word u ∈ Λ(G) with u = g. For any w ∈ Λ(G), we have w ∈ L iff wu ∈ Λ(G). Hence L = Λ(G) ∩ {w ∈ Σ∗ : wu ∈ Λ(G)} . The language Λ(G) is regular by Corollary 4.5. By parts (v) and (vi) (with L 0 = {w}) of Lemma 4.2, L is therefore also regular. Corollary 4.7. For any fixed cone type C ∈ C(G), the language L = {w ∈ Λ(G) : C(w) = C} is regular over Σ. 30 Proof. Since C(G) is finite, there exist s1 , . . . , sn and s01 , . . . , s0m in Σ∗ such that C is the only cone type for which the inequality C ≤ s holds for s = s1 , . . . , sn but fails for s = s01 , . . . , s0m . Thus L= n \ {w ∈ Λ(G) : w ≤ si } ∩ m \ ¬ {w ∈ Λ(G) : w ≤ s0i } . i=1 i=1 By Lemma 4.2 and Corollary 4.6, L is therefore regular. Proposition 4.8. Every δ-hyperbolic group G is automatic. Proof ([5, 2.3.4]). By Corollary (4.5), Λ(G) is regular. Choose a deterministic finite automaton M representing Λ(G). Let S denote the set of states of M , let Y ⊂ S denote the subset of accept states, and let s0 denote the initial state. For any x ∈ Σ∗ , define a deterministic finite automaton Mx as follows. For the set of states of Mx , add a special state r to the product S × S × X, where X = N4δ+4|x| (1). Define Σ2 to be the alphabet of Mx . The transition function µ of Mx is given by µ(r, (y1 , y2 )) = r for any y1 , y2 and µ((s1 , s2 , g), (y1 , y2 )) =   (s1 y1 , s2 y2 , y −1 gy2 ) if y −1 gy2 ∈ X; 1 1  r otherwise for any other state. The accept states of Mx are all states of the form (s1 , s2 , x) with s1 , s2 ∈ Y , and 0 the initial state of Mx is (s0 , s0 , 1). For any (padded) (y, y 0 ) = (y1 · · · yn , y10 · · · ym ) in Λ(G) × Λ(G), 0 we have (s0 , s0 )(y, y 0 ) = r if the geodesic chains π(y1 · · · yt ) and π(y10 · · · ym ) remain a distance at most 4δ + 4 |x| apart for all time t. Otherwise, the state (s0 , s0 )(y, y 0 ) is (s0 y, s00 y 0 , y −1 y 0 ). Hence the language L0x = (Λ(G) × Λ(G)) ∩ L(Mx ) consists of all pairs (y, y 0 ) of geodesics in Λ(G) such that y −1 y 0 = x and y, y 0 stay a distance of at most 4δ + 4 |x| apart for all time. By Lemma 2.3, any two geodesics y, y 0 with y −1 y 0 = x stay a distance at most 4δ apart until time y.y 0 = 1 1 (|y| + |y 0 | − d(y, y 0 )) = (|y| + |yx| − |x|) ≥ |y| − |x| . 2 2 It follows that y, y 0 stay at most 4δ + 4 |x| apart for all time. Hence L0x = {(y, y 0 ) ∈ Λ(G) × Λ(G) : π(y 0 ) = π(yx)} . Thus G is automatic with word acceptor Λ(G), equality recognizer M , and multiplier automata Mx for each x ∈ Σ. 31 The converse of Proposition 4.8 is false. For example, any finitely generated abelian group is automatic [5, 4.2.4]. The group Zn , however, does not satisfy Proposition 2.9 for n > 1, and is therefore not hyperbolic. The automation of G also has the following more geometric consequence. Proposition 4.9. If G is infinite, then there exists a constant C > 0 such that for every g ∈ G, some geodesic ray r ∈ Ω0 (G) passes through NC (g). Proof. We first claim that Ω0 (G) is non-empty. By Corollary 4.5, there exists a deterministic finite automaton M with L(M ) = Λ(G). Suppose that no word w ∈ Λ(G) revisits the same state twice. Then for each word w = w1 · · · w|w| ∈ Λ(G), the states s0 (w1 · · · wk ) are distinct for k = 0, . . . , |w|, where s0 is the initial state of M . It follows that |w| is bounded by the number of states C of M . Since the evaluation map Λ(G) → G is surjective, G must be finite, contradicting the hypothesis of the lemma. Thus there exists a geodesic word w ∈ Λ(G) such that s0 (w1 · · · wn ) = s0 (w1 · · · wm ) for some n < m. By definition, the prefix-closure Λ(G) = {x ∈ Σ∗ | ∃y ∈ Σ∗ : xy ∈ Λ(G)} is Λ(G) itself. Hence the state s = s0 (w1 · · · wn ) is an accept state. Hence s0 w1 · · · wn (wn+1 · · · wm )k = s for all k. The word w1 · · · wn (wn+1 · · · wm )k thus lies in Λ(G) for all k, and so gives the geodesic ray required by the claim. Choose a geodesic w ∈ Λ(G) with w = g, and write w = w1 · · · wn with each wi ∈ Σ. If the states s0 (w1 · · · wk ) are all distinct for k = 0, . . . , n, then k ≤ C. Hence |g| ≤ C. In this case, every geodesic in Ω0 (G) intersects NC (g). Otherwise, there exists some n < m such that s0 (w1 · · · wn ) = s0 (w1 · · · wm ) (4.1) As in the proof of the preceding claim, the words w1 · · · wn (wn+1 · · · wm )k for k ≥ 0 define a geodesic ray r ∈ Ω0 (G). Assuming without loss of generality that n is the smallest index satisfying (4.1), |n| < C. Thus d(g, r) ≤ n < C, as required. 32 Chapter 5 Nets in Groups Let M be a metric space (not necessarily hyperbolic). For any C > 0, a subspace M 0 ⊂ M is a C-net if M ⊂ NC (M 0 ). Call M 0 a net in M if M 0 is a C-net for some C; or, equivalently, if d(p, M 0 ) is bounded for all p ∈ M . Similarly, for a finitely generated group X, a subgroup X 0 ⊂ X is a net if it is a net in the metric space C(X, Σ) for some finite generating set of Σ. Note that we do not require that X be hyperbolic or that X 0 be finitely generated. Since the Cayley graph C(X, Σ) is independent of Σ up to quasi-isometry, the condition of being a net in X is independent of the particular choice of generating set Σ for X. Consider the problem of finding pairs (X, X 0 ) with X 0 ⊂ X that satisfy the following property: There exists a section s : X/X 0 → X such that s(X/X 0 ) is a net in G. (∗) In (∗), X/X 0 denotes the space of right cosets of X 0 in X; we do not require X 0 C X. In particular, the desired map s : X/X 0 → X is only a map of sets, not a group homomorphism or a continuous map. The goal of this paper is to prove that the pair (G, H) satisfies (∗) if G is hyperbolic and H ⊂ G is a quasiconvex subgroup of infinite index. In order to motivate this result, we provide a few examples and counterexamples of pairs satisfying (∗) in this section. π Lemma 5.1. Let 1 → N → E − → Q → 1 be an exact sequence of groups. Suppose E is finitely generated. Then the pair (E, N ) satisfies (∗) iff N is finite. Proof. It is clear that (E, N ) satisfies (∗) if N is finite. Thus assume N is infinite. Fix generating sets Σ and Σ0 = π(Σ) for E and Q, respectively. Suppose instead that there exists a section s : Q → E of π such that s(Q) is a C-net (with respect to Σ) in C(E, Σ) for some constant C. Clearly |πg| Σ0 ≤ |g|Σ for all g. Thus for any g, g 0 ∈ E, we have d(g, g 0 ) = g −1 g 0 Σ ≥ (πg)−1 (πg 0 ) Σ0 = d(πg, πg 0 ). (5.1) Fix q0 ∈ Q. Since N is infinite, there exists some g ∈ E with g ∈ s(q0 )N and d(g, s(q)) > C for 33 all q ∈ Q with d(q, q0 ) ≤ C. By (5.1), d(g, s(q)) > C for all q ∈ Q. The lemma follows from this contradiction. Thus pairs (E, N ) with N C E cannot satisfy (∗) because the preimages π −1 (q) remain uniformly separated: d(π −1 q, π −1 q 0 ) ≥ d(q, q 0 ) for all q, q 0 ∈ Q. Hence to construct a section s : X/X 0 → X of the required type, we need to consider subgroups X 0 for which the cosets gX 0 exhibit more complicated behavior. It was proved in Lemma 5.1 that for any exact sequence 1 → N → E → Q → 1, the pair (E, N ) does not satisfy (∗). If this sequence splits, then we can embed Q in E and consider the pair (E, Q); that is, we consider (E, Q) for E a semidirect product N o Q. In order to analyze this problem, it is useful to consider the projection f : E → s(Q) instead of s itself. Note that f moves points a bounded distance iff s(Q) is a net in E. The following lemma makes this observation more precise. Lemma 5.2. Let X = N o X 0 for some action of X 0 on N , and let π : X → X/N = X 0 denote the quotient map. Suppose X is finitely generated. Let d and d0 denote the metrices on C(X, Σ) and C(X 0 , Σ0 ), respectively, for some fixed generating sets Σ of X and Σ = π(Σ) of X 0 . Then (X, X 0 ) satisfies (∗) iff there exists a function ϕ : X → N and a constant C that satisfy the following two properties: (i) If ϕ(α) = ϕ(α0 ) for α 6= α0 in X, then d0 (πα, πα0 ) ≤ C. (ii) The distance d(α, (ϕα, πα)) ≤ C for all α ∈ X. Proof. Suppose first that (X, X 0 ) satisfies (∗). Then there exists a section s : N → X such that S = s(N ) is a 21 C-net in the Cayley graph C(G) for some C. For each α ∈ X, choose some f (α) ∈ S with d(α, f (α)) ≤ C/2. Write f (α) = (ϕ(α), ψ(α)) for some functions ϕ : X → X 0 and ψ : X → N . Since s is a section, we have ψ(α) = ψ(α0 ) for some α, α0 ∈ X iff ϕ(α) = ϕ(α0 ). But d0 (ψα, πα) = d(πf α, πα) ≤ d(f α, α) ≤ C/2, so ϕ satisfies property (i). Since Σ0 = π(Σ), we have |πα|Σ0 ≤ |α|Σ for all Σ. Assume without loss of generality that (1, σ 0 ) ∈ Σ for all σ 0 ∈ Σ0 . Then |(1, x)|Σ ≤ |x|Σ0 for all x ∈ X. It follows that |(1, x)|Σ = |x|Σ0 for all x ∈ X. We therefore have d((n, x), (n, x0 )) = (x−1 .n−1 , x−1 )(n, x0 ) Σ = (1, x−1 x0 ) Σ = x−1 x0 Σ0 = d0 (x, x0 ) (5.2) 34 for all n ∈ N and x ∈ X 0 . Hence for all α ∈ X, d(α, (ϕα, πα)) ≤ d(α, (ϕα, ψα)) + dΣ ((ϕα, ψα), (ϕα, πα)) = d0 (ψα, πα) + C/2 = d0 (πf α, πα) + C/2 ≤ d(f α, α) + C/2 ≤ C. The conclusion of the lemma therefore holds. Conversely, suppose that such a function ϕ exists. Consider the set S = {(ϕ(n, x), x) : (n, x) ∈ X} . By property (ii), S is a C-net in Γ = C(G, Σ). For any points (n, x), (n, x0 ) ∈ X for fixed n ∈ N , we have d0 (x, x0 ) ≤ C by (i). Hence d((n, x), (n, x0 )) ≤ C by (5.2). Let S 0 be a subset of S such that S 0 ∩ (n × X) contains at most one point for each n ∈ N . Then S 0 is a 2C-net in Γ. Choose an arbitrary (set-theoretic) section s : N → X such that S 0 ∩ (n × X) = {s(n)} whenever this intersection is nonempty. Then s(N ) ⊃ S 0 is also a 2C-net in Γ, so (X, X 0 ) satisfies (∗). Using Lemma 5.2, we now describe a method for using sections to satisfying (∗) to construct such sections over larger groups. Lemma 5.3. Let Q be a finitely generated group, and let Q act on groups N and N 0 . Suppose E = N o Q and E 0 = N 0 o Q are finitely generated. Set X = (N × N 0 ) o Q, where Q acts on N × N 0 via the diagonal map. If (E, Q) and (E 0 , Q0 ) satisfy (∗), then (X, Q) also satisfies it. Proof. Choose finite generating sets Σ and Σ0 for E and E 0 , respectively. Assume without loss of generality that Σ contains (1, q) for any (n, q) ∈ Σ, and similarly for Σ0 . Let (n × n0 , q) ∈ X, and let (n, q) = (n1 , q1 ) · · · (nr , qr ) and (n0 , q) = (n01 , q10 ), . . . , (n0s , qs0 ) with all (ni , qi ) ∈ E and (n0i , qi0 ) ∈ E 0 . Then (n × n0 , q) = (1 × n1 , q1 ) · · · (nr , qr )(1, qr−1 ) · · · (1, q1−1 )(n01 × 1, q10 ) · · · (n0s × 1, qs0 ). Hence X is generated by S = {(n × 1, q) : (n, q) ∈ Σ} ∪ {(1 × n, q) : (n, q) ∈ Σ0 } ; furthermore, we have |(n × n0 , q)|Σ×Σ0 ≤ 2(n, q)Σ + |(n0 , q)|Σ0 . 35 Equivalently, |α|Σ×Σ0 ≤ 2 |ρα|Σ + |ρ0 α|Σ0 (5.3) for all α ∈ X, where ρ and ρ0 denote the quotient maps ρ : X → X/N 0 = E and ρ0 : X → X/N = E 0 . Suppose (E, Q) and (E 0 , Q) satisfy (∗). Then there exist functions ϕ : E → N and ϕ0 : E 0 → N 0 satisfying properties (i) and (ii) in Lemma 5.2 for some constant C. Consider the function ψ : X → N × N 0 defined by ψ = ϕρ × ϕ0 ρ0 . To simplify notation, denote the three quotient maps E → E/N = Q, E 0 → E 0 /N 0 = Q, and X → X/(N × N 0 ) = Q by π. If ψ(α) = ψ(β), then property (i) forces dπ(S) (πα, πβ) ≤ dπ(Σ) (πρα, πρβ) ≤ C. (5.4) By property (ii), any α ∈ X satisfies dS (α, (ψα, πα)) ≤ 2dΣ (ρα, (ρψα, πα)) + dΣ0 (ρ0 α, (ρ0 ψα, πα)) ≤ 2dΣ (ρα, (ϕρα, πρα)) + dΣ0 (ρ0 α, (ϕρ0 α, πρ0 α)) ≤ 3C by (5.3). Combining (5.4) and (5.5) shows that (X, Q) satisfies (∗) by Lemma 5.2. (5.5) 36 Chapter 6 Nets in Hyperbolic Groups In this section, we prove that for any hyperbolic group G and any quasiconvex subgroup H ⊂ G with [G : H] infinite, the pair (G, H) satisfies (∗); that is, there exists a section s : G/H → G of the quotient map (of sets) G → G/H such that s(G/H) forms a net in the Cayley graph of G. Fix a δ-hyperbolic group G, a generating set Σ of G, and a K-quasiconvex subgroup H. Let Γ = C(G, Σ), and let d(x, y) = |x−1 y|Σ denote the metric on Γ. Set Λ = Λ(G) and C = C(G). To simplify notation, abbreviate |·|Σ as |·|. For each g ∈ G, set σ(g) = min {|gh| : h ∈ H} and S = {g ∈ G : |g| = σ(g)} . We form the desired section simply by choosing one point in each coset S ∩ gH. The diameter of the set S ∩ gH is uniformly bounded for all g ∈ G, so it suffices to prove that S itself is a net. The crucial step is doing so is showing that the set of geodesics to points in S is a regular language. The prefix closure S of S is then a finite distance in Γ away from S itself. Thus if S is a net in Γ, then so is S. As a subset of Γ, the set S consists of all points that lie on geodesic rays from 1 that intersect S. We use the quasiconvexity of H to prove that any point in Γ is a bounded distance from such a geodesic if [G : H] = ∞, completing the proof. The first step in this argument is the following lemma, which provides a convenient bound or estimate for the distance between points on the same coset gH. Lemma 6.1. Let H ⊂ G be a quasiconvex subgroup, and fix some g ∈ G. For all x 1 , x2 ∈ gH, we have d(x1 , x2 ) ≤ C1 + |x1 | + |x2 | − 2σ(g), where C1 > 0 is a constant depending only on G and H. Proof. Choose geodesics [1x1 ], [1x2 ], and [x1 x2 ]. Set f (p) = d(p, [1x1 ]) − d(p, [1x2 ]) for all p ∈ [x1 x2 ]. For any two adjacent vertices p and p0 , we have |f (p) − f (p0 )| ≤ 2. Since f (x1 ) ≤ 0 and f (x2 ) ≥ 0, it follows that there exists some p0 ∈ [x1 x2 ] with |d(p0 , [1x1 ]) − d(p0 , [1x2 ])| ≤ 2. By the δ-hyperbolicity of Γ, we have min {d(p, [1x1 ]), d(p, [1x2 ])} ≤ δ for each p ∈ [x1 x2 ]. Thus d(p0 , [1x1 ]), d(p0 , [1x2 ]) ≤ δ + 2; choose x01 ∈ [1x1 ] and x02 ∈ [1x2 ] realizing these inequalities. The quasiconvexity of H implies that there exists a point p00 ∈ gH with d(p0 , p00 ) < K. See Figure 6.1 for an illustration of this 37 x1 x01 p0 p00 1 x02 x2 Figure 6.1: The construction in Lemma 6.1. The dotted lines each have length at most δ + 2, and the quasigeodesic containing p00 stays in the K-neighborhood of the geodesic containing p0 . construction. We have σ(g) ≤ |p00 | ≤ |x0i | + d(x0i , p0 ) + d(p0 , p00 ) ≤ |x0i | + δ + K + 2 = |xi | − d(xi , x0i ) + δ + K + 2. Thus d(xi , x0i ) ≤ |xi | − σ(g) + δ + K + 2. We therefore have d(x1 , x2 ) ≤ d(x1 , x01 ) + d(x01 , p0 ) + d(p0 , x02 ) + d(x02 , x2 ) ≤ 2δ + 4 + d(x1 , x01 ) + d(x2 , x02 ) ≤ 4δ + 2K + 8 + |x1 | + |x2 | − 2σ(g), as required. For x1 , x2 ∈ S, Lemma 6.1 forces d(x1 , x2 ) ≤ C1 . The intersections S ∩ gH for g ∈ G thus have bounded diameter. In defining the section s by choosing one point in S ∩ gH for each coset gH, the particular choice of points is therefore irrelevant in the large-scale geometry of Γ. In particular, the condition that s be a net is independent of this choice. Set hg, g 0 i = 2(g −1 .g 0 ) = |g| + |g 0 | − |gg 0 | for g, g 0 ∈ G. Following the conventions in previous 38 sections, we also write hx, yi for hx, yi with x, y ∈ Σ∗ to simplify notation. The set S consists precisely of those points g ∈ G with |g| ≤ |gh| for all h. Thus S = {g ∈ G : hg, ghi ≤ |h| for all h ∈ H} . In order to prove that S is regular, we first prove that the condition hx, yi = n defines a regular language Ln ⊂ Λ2 for each n. The idea of the proof is to split each y with (x, y) ∈ Ln into subwords w, c, w0 ∈ Σ∗ such that hx, yi = hx, wcw 0 i = hxy, ci + hxwc, w 0 i with hx, wcw0 i , hxy, ci < n. By showing that the set of such words (y, w, c, w 0 ) is regular, we therefore conclude that Ln is regular by induction on n.  Lemma 6.2. For any fixed n ≥ 0, the language Ln = (x, y) ∈ Λ2 : hx, yi = n over Σ2 is regular. Proof. By Corollary 4.5, there exists a determinstic finite automaton M over Σ with L(M ) = Λ. Let M 0 denote the obtained by replacing each arrow labelled c ∈ Σ by arrows labelled (c, ) and ($, c) (with the same source and target). The language recognized by M 0 consists of all x, y ∈ Σ∗ such that xy ∈ Λ. Thus L0 = L(M 0 ) ∩ Λ2 , and so is regular. Fix some positive integer n, and suppose that Lm is regular for all m < n. For any x ∈ Λ and c ∈ Σ,    0 if x ≤ xc;    hx, ci = |x| + 1 − |xc| = 2 if x ≥ xc;     1 otherwise. Set Pi (c) = {x ∈ Λ | hx, ci = i} for i = 0, 1, 2 and c ∈ Σ. Let Cc denote the set of cones C such that x ≤ xc if C(x) = C. Then P0 (c) = {x ∈ Λ | C(x) ∈ Cc } P2 (c) = {x ∈ Λ | ∃y ∈ Λ : xc = y, C(y) ∈ Cc−1 } P1 (c) = Λ ∩ ¬(L0 ∪ L2 ) Since Cc is finite, all three languages Pi are regular by Lemma 4.2. Let R ⊂ Λ4 consist of all quadruples (x, y, z, w) with y = y1 · · · yn , z = xy1 · · · yi , and w = yi+1 · · · yn , where i is the largest index such that xy1 · · · yi ∈ Λ. We claim that the language R is regular. Construct a finite automaton M over Σ4 as follows. Let M have one state sC for each cone type C ∈ C, and add two states sr and sa . Designate sa as the only accept state. For each state sC , add arrows labelled (u, , u, ) and ($, u, u, ) from sC to the state sCu for each u ∈ Σ with x ≤ xu for C(x) = C. For any other u ∈ Σ, attach an arrow from sC to sr labelled ($, u, , u). Add an arrow from sr to itself labelled ($, u, $, u) for each u ∈ Σ. Attach an arrow labelled ($, $, $, $) from every 39 state in M to sa . It is clear that for any geodesics x, y, z, w ∈ Λ, the resulting automaton accepts the quadruple (x, y, z, w) iff it lies in R. Thus R = L(M 0 ) ∩ Λ4 . The claim follows. Let Rc denote the set of quadruples (x, y, z, w) ∈ R with w1 = c, and let Rc0 denote the set of sextuples (x, y, z, w, z 0 , w0 ) ∈ Λ6 such that (x, y, z, w) ∈ Rc , z 0 = zc, and w0 = w2 · · · w|w| . Since R is regular, it is clear that Rc and Rc0 are also regular for each c ∈ Σ. For any x, y, z ∈ G, we have hx, yi + hxy, zi − hy, zi = (|x| + |y| − |xy|) + (|xy| + |z| − |xyz|) − (|y| + |z| − |yz|) = |x| + |yz| − |xyz| = hx, yzi . (6.1) Fix x, y ∈ Λ, and write y = y1 · · · yn with each yi ∈ Σ. Let k ≥ 0 denote the largest index such that xy1 · · · yk ∈ Λ. By (6.1), hx, yi = hxy1 · · · yk+1 , yk+2 · · · yn i + k X hxy1 · · · yi , yi+1 i i=0 = hxy1 · · · yk , yk+1 i + hxy1 · · · yk+1 , yk+2 · · · yn i . Since xy1 · · · yk+1 6∈ Λ, we have hxy1 · · · yk , yk+1 i > 0. Thus hx, yi = n iff hxy1 · · · yk , yk+1 i = i and hxy1 · · · yk+1 , yk+2 · · · yn i = n − i for i = 1 or 2. Hence Ln satisfies Ln = [  (x, y) ∈ Λ2 | ∃(z, w, z 0 , w0 ) ∈ Λ4 : (x, y, z, w, z 0 , w0 ) ∈ Rc0 , hz, ci = i, hz 0 , w0 i = n − i [  (x, y) ∈ Λ2 | ∃(z, w, z 0 , w0 ) ∈ Λ4 : (x, y, z, w, z 0 , w0 ) ∈ Rc0 , z ∈ Pi (c), (z 0 , w0 ) ∈ Ln−i , c∈Σ i=1,2 = c∈Σ i=1,2 and so is regular. The lemma follows by induction on n. Lemma 6.3. The language L = {x ∈ Λ : x ∈ S} is regular. Proof. Assume without loss of generality that the generating set Σ of G contains a generating set Σ 0 for the hyperbolic group H. By Corollary 4.5, the language Λ0 ⊂ Σ0∗ ⊂ Σ∗ of geodesics in C(H, Σ0 ) is regular. For any g ∈ S and h ∈ H, we have hg, ghi = |g| + d(g, gh) − |gh| ≤ |g| + (C1 + |gh| − |g|) − |gh| = C1 for some constant C1 by Lemma 6.1. Hence S = {x ∈ Λ | ∀y ∈ Λ0 : hx, yi ≤ |y|} = {x ∈ Λ | ∀y ∈ Λ0 : hx, yi ≤ min(|y| , C1 )} . 40 Thus S = {x ∈ Λ | ∀y ∈ Λ0 : hx, yi ≤ C1 } ∩ C1 [ r=0    \ y∈Λ0 ∩N r (1) {x ∈ Λ : hx, yi ≤ r} . (6.2) By Lemma 6.2, the language {(x, y) ∈ Λ × Λ0 : hx, yi ≤ n} = (Λ × Λ0 ) ∩ n [  (x, y) ∈ Λ2 : hx, yi = i i=0 is regular for all n. Thus S is regular by (6.2) and Lemma 4.2. We now prove the main theorem. Theorem 6.4. Let G be a hyperbolic group, and let H ⊂ G be a quasiconvex subgroup. If [G : H] = ∞, then there exists a (set-theoretic) section s : G/H → H of the quotient map G → G/H such that s(G/H) is a net in G. Proof. We first claim that there exists a constant C2 such that for any g ∈ G, there exists a point g 0 ∈ G and a geodesic ray r through g 0 such that d(g, g 0 ) < C2 and d(r(t), H) is unbounded as t → ∞. By Proposition 4.9, there exists a point g 0 with d(g, g 0 ) < C for some constant C (independent of g) and a geodesic ray r ∈ Ω0 (G) through g 0 . Suppose r ⊂ Nl (H) for some l > 0. Set x = r(|g| + l), and choose some h ∈ H such that d(x, h) ≤ l. Then x.h = 1 (|x| + |h| − d(x, h)) ≥ |x| − d(x, h) ≥ |g| . 2 Since H is K-quasiconvex, there exists a geodesic [1h] in G lying in NK (H). By Lemma 2.3, any two geodesics [1g 0 ], [1h] stay a distance at most 4δ apart until time g 0 .h. Hence d(g, H) ≤ d(g, [1h]) + K ≤ d(g, g 0 ) + d(g 0 , [1h]) + K+ ≤ K + C + 4δ. (6.3) Set C 0 = K + C + 4δ. If d(g, H) > C 0 , contradicting (6.3), then the distance d(r(t), H) must be unbounded; the claim then holds with C2 = C. Suppose instead that d(g, H) ≤ C 0 . Choose some p ∈ NC 0 (1) such that g ∈ Hp. Since [G : H] is infinite, there exists some t ∈ G with d(t, H) > C 0 . Fix some such t minimizing |t|. The point gp−1 t then satisfies d(gp−1 t, H) ≥ d(Ht, H) ≥ d(t, H) > C 0 and d(gp−1 t, g) ≤ C2 , where o n C2 = C 0 + min |t0 | : t0 ∈ G, t0 6∈ NC 0 (H) . The claim therefore holds for all g ∈ G. 41 Fix g ∈ G. By the claim above, there exist g 0 , x ∈ G such that d(g, g 0 ) < C2 , g 0 ≤ x, and d(x, H) ≥ |g| + 12 C1 . Choose a point x0 ∈ S ∩ xH. The Gromov product x.x0 satisfies x.x0 = 1 1 (|x| + |x0 | − d(x, x0 )) ≥ |x0 | − C1 ≥ |g| 2 2 by Lemma 6.1. Any two geodesics [1x] and [1x0 ] remain a distance no greater than 4δ apart until time x.x0 , so d(g, [1x0 ]) ≤ d(g, g 0 ) + d(g 0 , [1x0 ]) < C2 + 4δ. Set L = {x ∈ Λ : x ∈ S}. Then any g ∈ G satisfies d(g, π(L)) < C2 + 4δ, where L = {x ∈ Σ∗ | ∃y ∈ Σ∗ : xy ∈ L} denotes the prefix closure of L. By Lemmas 4.2 and 6.3, L is regular. Let M be a deterministic finite automaton with L(M ) = L. Since M has only finitely many states, any word in L is within a bounded distance of a word in L; explicitly, any x ∈ L satisfies d(x, L) < C3 , where C3 is the number of states of M. Hence d(g, L) ≤ d(g, g 0 ) + d(g 0 , L) < C2 + C3 + 4δ By Lemma 6.1, each coset g0 H contains at most #NC1 (1) elements of S. Choosing exactly one point in each intersection S ∩ g0 H produces a section s : G/H → G such that d(p, s(G/H)) < #NC1 (1) + C2 + C3 + 4δ for all vertices p ∈ Γ. Since the image S = s(G/H) of the section s : G/H → G in Theorem 6.4 is a net, it is also a hyperbolic metric space. The left action of G on the right coset space G/H induces an action on S, given by g.s(g 0 ) = s(gg 0 ). By considering the corresponding homeomorphisms of the boundary induced by this action, we prove two results about the intersection of conjugate subgroups of H below. Set H g = g −1 Hg for any g ∈ G. This conjugate depends only on the image of g in the left coset space H\G. As such, we write H γ = γ −1 Hγ = H g for a coset γ = Hg ∈ H\G. In [6], it is proved that any quasiconvex subgroup H of a hyperbolic group G has finite width; that is, H γ ∩ H is finite for all but finitely many cosets γ ∈ G/H. Using a completely different method, the section s : G/H → G of Theorem 6.4, we prove a weaker version of this result. Specifically, we show in Proposition 6.7 below that quasiconvex subgroups of infinite index in G contain no infinite groups normal in G. We require the following elementary lemma: Lemma 6.5. If G is a finite extension of an infinite cyclic group, then any infinite cyclic subgroup H ⊂ G has finite index. π Proof. Choose an exact sequence 1 → N → G − → Q → 1 with N cyclic and Q finite. Then Q contains π(H) = H/(H ∩ N ), so [H : H ∩ N ] is finite. In particular, H ∩ N is non-trivial. Thus 42 [N : H ∩ N ] is finite. The index [G : H] ≤ [G : H ∩ N ] = [G : N ][N : H ∩ N ] = #Q[N : H ∩ N ] is therefore also finite. We also need the following result, which is interesting independently of its use in proving Proposition 6.7. Proposition 6.6. For any g ∈ G, let Lg denote the isometry Lg (g 0 ) = gg 0 on the vertices of Γ. Extend Lg to a graph automorphism of Γ. Suppose G is not elementary. Then the homomorphism g → (Lg )∞ has finite kernel. Proof. Let K denote the group of g ∈ G with (Lg )∞ = id, and fix g ∈ K. We first claim that there exists some constant N = N (g) such that [xN , g] = 1 for all x ∈ G. By Proposition 2.11, the supremum N0 of the order of all torsion elements of G is finite. The claim therefore holds immediately for all torsion x ∈ G with N = N0 !. Thus let x ∈ G be an arbitrary element of infinite order. By Proposition 4.9, there exists a constant C, independent of g and x, such that d(r, x) ≤ C for some geodesic r. Since (Lg )∞ acts trivially on (rt ) ∈ ∂G, the distance d(grt , rt ) is bounded. Both [1g] and gr are geodesics, so the union [1g] ∪ gr is a (1, 2 |g|)-quasi-geodesic. Thus there exists some geodesic ray r 0 such that d(grt , rt0 ) ≤ C 0 for some constant C 0 = C 0 (g) by Lemma 2.6. The distance d(rt , rt0 ) ≤ d(rt , grt ) + d(grt , rt0 ) is then bounded. But rt .rt0 = 1 (|rt | + |rt0 | − d(rt , rt0 )) = t − d(rt , rt0 ), 2 so d(rt , rt0 ) ≤ 4δ for all time t by Lemma 2.3. Choosing some t with d(rt , x) ≤ C, we therefore have d(gx, x) ≤ d(gx, grt ) + d(grt , rt ) + d(rt , x) = 2d(x, rt ) + d(grt , rt ) ≤ 2d(x, rt ) + d(grt , rt0 ) + d(rt , rt0 ) ≤ 2C + C 0 + 4δ. Thus x−1 gx ≤ 2C+C 0 +4δ for all x ∈ G of infinite order. Fix such an x ∈ G. Then |x−n gxn | ≤ 2C+ C 0 + 4δ for all n > 0, so there exist distinct n, m such that x−n gxn = x−m gxm and 0 < n < m < K, where K = #N2C+C 0 +4δ (1). Hence any x ∈ G of infinite order satisfies [xK! , g] = 1. The claim therefore holds for arbitrary x ∈ G with N = N0 !K!. By Proposition 2.10, there exist x1 , x2 ∈ G such that hx1 , x2 i is a free group of rank 2. The N N N commutators [xN 1 , g] and [x2 , g] vanish by the claim above. The centralizers CG (x1 ) and CG (x2 ) N are finite extensions of hxN 1 i and hx2 i, respectively, by Proposition 2.9 and Lemma 6.5. Suppose N hgi is infinite. By Lemma 6.5, both hgi and hxN i i have finite index in CG (xi ) for each i = 1, 2. It N N N N N follows that hgi ∩ hxN 1 i ∩ hx2 i has finite index in hgi. But hx1 , x2 i ⊂ hx1 , x2 i is free, so hx1 i ∩ hx2 i 43 is trivial. It follows that g must have finite order. Thus K consists entirely of torsion. Let g1 , . . . , gr ∈ K be distinct representatives of the conjugacy classes of torsion in G that intersect K. By the claim above, there exist constants N (g i ) for each σ ∈ Σ and i = 1, . . . , r such that [xN (gi ) , gi ] = 1 for all x ∈ G. Set N = N (g1 ) · · · N (gr ), and let H = xN : x ∈ G . Then H C G and [H, gi ] = 1 for all gi . Write xy for the conjugate y −1 xy. Then for all x ∈ G and h ∈ H, x  −1 −1 (gix )h = h−1 gix h = (hx )−1 gi (hx ) = gix for each gi . Thus [h, gix ] = 1 for all h ∈ H and x ∈ G. The commutator [h, k] therefore vanishes for all k ∈ K. By Proposition 2.10, G contains an element x ∈ G of infinite order. Then the centralizer CG (xN ) is a finite extension of Z by Proposition 2.9. Hence hxN i has finite index in CG (xN ) by Lemma 6.5. But CG (xN ) contains hxN i × K, so #K =  xN × K : xN    ≤ CG (xN ) : xN < ∞, as required. Proposition 6.7. Let G be a hyperbolic group, and let H ⊂ G be a quasiconvex subgroup with [G : H] = ∞. Let K ⊂ H with normal closure K G in G. If K is infinite, then [K G : K] = ∞. In particular, any subgroup of H normal in G is finite. Proof. The corollary is trivial if G is finite or a finite extension of Z, so assume without loss of generality that G is non-elementary. Suppose instead that K G /K is a finite set of order n. Each element of G acts on the coset space K G /K by conjugation, giving a homomorphism ρ : G → Sn . The kernel G0 = ker ρ has finite index in G, so ∂G0 = ∂G. Replacing G by the quasi-isometric group G0 , we can therefore assume that n = 1; that is, K C G. Let s : G/H → G denote the section given by Theorem 6.4. Then G acts on S = s(G/H) ⊂ G by g.s(x) = s(gx). Since s is an injective function from the right coset space G/H to G, this action is well-defined. The stabilizer of any s(x) ∈ S is H x ⊃ K, so K acts trivially on S. Since S is a net in G, the inclusion i : S → G is a (1, )-quasi-isometry for some . Hence i induces a bijection (in fact, a homeomorphism) i∞ : ∂S → ∂G. Since s(x) minimizes |·| in xH, we have |s(x)| ≤ |g −1 s(gx)| ≤ |g −1 | + |s(gx)| = |g| + |s(gx)|. Thus |s(gx)| ≥ |s(x)| − |g|. By Lemma 6.1, d(g.s(x), gs(x)) = d(s(gx), gs(x)) ≤ C1 + |sg(x)| + |gs(x)| − 2 |s(gx)| ≤ C1 + 2 |g| (6.4) 44 for all x. Thus the diagram g→(L0g )∞ // Homeo(∂S) G KK OO KK KK KK K g→(Lg )∞ KK (i∞ )∗ KK KK %% Homeo(∂G) (6.5) commutes, where Lg (g 0 ) = gg 0 and L0g s(x) = g.s(x). We hence have (Lg )∞ = 1 for all g ∈ K. By Proposition 6.6, K is finite. 45 Bibliography [1] K. Brown, Cohomology of Groups, Springer-Verlag, New York, 1982. [2] D. Burago, Y. Burago, and S. Ivanov, A Course in Metric Geometry, American Mathematical Society, Graduate Studies in Mathematics Vol. 33, Providence, Rhode Island, 2000. [3] J. W. Cannon, The Combinatorial Structure of Cocompact Discrete Hyperbolic Groups, Geom. Dedicata 16 (1984), 123-148. [4] A. Casson and S. Bleiler, Automorphisms of Surfaces after Nielsen and Thurston, Cambridge University Press, Cambridge, 1988. [5] D. B. A. Epstein et al., Word Processing in Groups, Jones and Bartlett Publishers, Boston, 1992. [6] R. Gitik et al., Widths of Subgroups, Trans. Amer. Math. Soc. 350 (1998), pp. 321–329. [7] M. Gromov, Hyperbolic Groups, published in “Essays in Group Theory,” ed. S. Gersten, Springer-Verlag, New York, 1987. [8] P. de la Harpe, Topics in Geometric Group Theory, University of Chicago Press, Chicago, 2000. [9] O. Kharlampovich and A. Myasnikov, Hyperbolic Groups and Free Constructions, Trans. Amer. Math. Soc. 350 (1998), pp. 573–613. [10] R. Lyndon and P. Schupp, Combinatorial Group Theory, Springer-Verlag, Berlin, 1977. [11] C. MacLachlan and A. Reid, The Arithmetic of Hyperbolic 3-Manifolds, Springer-Verlag, New York, 2003. [12] J. G. Ratcliffe, Foundations of Hyperbolic Manifolds, Springer-Verlag, New York, 1994. [13] W. Thurston, Hyperbolic Structures on 3-Manifolds, II: Surface Groups and 3-Manifolds which Fiber over the Circle, preprint. [14] ———, On the Geometry and Dynamics of Diffeomorphisms of Surfaces, Bull. Amer. Math. Soc. (N.S.) 19 (1988), pp. 417–431.