SOL GEOMETRY GROUPS ARE NOT

ASYNCHRONOUSLY AUTOMATIC

Noel Brady

Abstract. Lattices in the 3-dimensional Lie group Sol are shown to be not asynchronously automatic. The proof consists of an interaction of geometry and logical complexity arguments.

In 1910 Max Dehn formulated the word problem for finitely presented groups, and gave a beautiful algorithm to solve the word problem in the case of closed hyperbolic surface groups. Since then, group theorists have been developing many strategies for solving the word problem for various classes of groups.

More recently, Cannon [C] and Gromov [Gr] have offered substantial generalizations of the class of groups to which Dehn’s algorithm applies. Motivated in part by this work,

[ECHLPT] introduced the class of automatic groups. A group is called automatic if it can be described in the following sense by primitive computing machines called finite state automata. First, the group has a finite generating set, and there is a finite state automaton which recognizes a set of representative words in the generators for all the group elements. Secondly, there are finite state automata which can tell when two words, which are recognized by the first automaton above, represent elements of the group which are equal or just differ by a generator.

Automatic groups have an efficient algorithm for solving word problem. Certain large classes of groups, such as the hyperbolic groups introduced by Gromov in [Gr], are automatic. However, an automatic structure imposes certain restrictions on the geometry of a group. For instance, an automatic group must have a quadratic isoperimetric inequality. This is how one sees that the Baumslag-Solitar groups are not automatic.

The concept of an asynchronously automatic group [ECHLPT] is an attempt to broaden the class of groups which can be computed by finite state machines. The Baumslag-Solitar groups are asynchronously automatic. One may ask which 3-manifold groups are (asynchronously) automatic. In [ECHLPT] it is shown that the fundamental group of a closed 3-manifold which satisfies Thurston’s geometrization conjecture is automatic if and only if none of the prime components of the manifold are modeled on either Nil or Sol. It

Typeset by AMS-TEX

The author received partial support from from the NSF grant DMS-9704417.

is also shown that Sol manifold groups are not automatic, and that closed Nil manifold groups are not even asynchronously automatic.

If a group is asynchronously automatic, then it satisfies a purely geometric condition: it is asynchronously combable with a departure function. See section 1 for precise definitions. Indeed, one often shows that a group is not (asynchronously) automatic by showing that it fails to be (asynchronously) combable. In [Bri] it is shown that Sol lattices are asynchronously combable with departure. Nevertheless, we can prove the following.

Theorem 1. Lattices in the 3-dimensional Lie group Sol are not asynchronously automatic.

By the remarks preceeding the statement of Theorem 1, we see that the proof of Theorem 1 will have to use something more than just the geometry of an asynchronous combing. The extra ingredient used is the fact that the combing associated to an asynchronously automatic structure has to be a regular language. We feel that this interaction of logical complexity and geometry is at the heart of the subject of automatic groups, and should be kept in mind if, for instance, one has a CAT(0) group which one believes to be not automatic. In [Bra] this interaction between geometry and logical complexity is used to prove that there is essentially only one type of asynchronously automatic structure on closed hyperbolic surface groups. In [BBr] this interaction is used to prove that certain HNN’s of ℤ + ℤ which have quadratic isoperimetric inequality are not biautomatic.

Now, we explain the layout of the rest of the paper. Section 1 contains the background on asynchronously automatic structures and asynchronous combings with departure. Section 2 gives a brief introduction to the Lie group Sol, and provides some basic results which are needed in the proof of Theorem 1. We give a presentation of a typical lattice G in Sol, and give an explicit embedding of G in Sol. The remaining sections are devoted to the proof of Theorem 1.

In section 3 we give the basic reduction of the proof. By examining the logical complexity of the asynchronous combings associated to an asynchronously automatic structure, we see that the proof reduces to two very different cases. These are treated in sections 4 and 5, thus completing the proof. We conclude with some remarks and questions in section 6.

§1. Asynchronously automatic groups

This section provides the fundamental concepts of asynchronous automatic structures. These definitions can be found in the literature; for example [ECHLPT] chapters 1 and 2,

[BGSS] and [NS].

Let G be a finitely generated group and A ⊂ G be a finite set of monoid generators. Typically, one takes A to be the union of a finite set of group generators for G and the set of their inverses. Let A^{∗} denote the free monoid on A and w ↦ \overline{w} denote the natural map A^{∗} → G. Call elements of A^{∗}, words over the finite alphabet A. We are interested in subsets L ⊂ A^{∗} which map onto G.

We can place restrictions on the logical structure of L as follows. A finite state automaton with alphabet A, is a finite, directed graph, whose edges are labeled by elements of A such that no two edges with the same label can have the same initial vertex. We call the vertices of the graph states. One state is called the start state, and a subset of the states are called accept states. Reading the labels along a directed edgepath, with initial vertex the start state and terminal vertex an accept state, gives us an element of A^{∗} called an accepted word. A subset L ⊂ A^{∗} is called a regular language if it is the set of accepted words of some finite state automaton with alphabet A. If L ⊂ A^{∗} → G is a regular language and maps onto G we say it is a rational structure for G.

We can also view L as a set of edgepaths in a metric space, and place geometric restrictions on it. Given a finite monoid generating set A ⊂ G, one can construct the Cayley graph Γ_{A}(G) of G with respect to A. The set of vertices of Γ_{A}(G) is just G itself. There is a directed edge from g to ga for each g ∈ G and a ∈ A. Since A is finite, Γ_{A}(G) is a locally finite graph. Let each edge of Γ_{A}(G) be isometric to the interval [0, 1], and define the distance between two points to be the infimum of the lengths of all paths in Γ_{A}(G) joining them. This path metric makes Γ_{A}(G) into a geodesic metric space (i.e. for all x, y ∈ Γ_{A}(G) there is a path joining x to y of length equal to d(x, y), the distance between x and y). A word w ∈ A^{∗} gives an edgepath in Γ_{A}(G) (also denoted by w) which starts at the identity and ends at the vertex \overline{w}. We parameterize these paths by arc length up to their endpoints, where they remain constant. Thus w(t) = \overline{w} for all t ≥ length(w). Here length(w) denotes the length of the path w, which equals the length of w as an element of A^{∗}.

We say L ⊂ A^{∗} has the K-fellow traveler property if there exists K ≥ 0 such that for all u, v ∈ L with \overline{u^{−1}v} ∈ \overline{A} ∪ \{id\} then d(u(t), v(t)) ≤ K, for all t ≥ 0. This says that if two L-paths end distance ≤ 1 apart in Γ_{A}(G) then points traveling at unit speed along them (starting at the same time at the identity) stay within K of each other. Say that L ⊂ A^{∗} has the asynchronous K-fellow traveler property if there exists K ≥ 0 such that for all u, v ∈ L with \overline{u^{−1}v} ∈ \overline{A} ∪ \{id\} there are monotonic reparameterizations ϕ and ψ (depending on u and v) such that d(u(ϕ(t)), v(ψ(t))) ≤ K for all t ≥ 0. This is similar to the previous definition, except that we now allow points to speed up or slow down (but not backtrack) along the L-paths in order to stay within K of each other. We say that L ⊂ A^{∗} has a departure function D : ℝ_{+} → ℝ_{+} if for all r > 0, for all w ∈ L and for all 0 ≤ s, t ≤ length(w) we have

|s − t| > D(r) ⟹ d(v(s), v(t)) > r .

An automatic structure on G is a rational structure L → G which satisfies the K-fellow traveler property. We say that G is an automatic group. An asynchronous automatic structure on G is a rational structure L → G which satisfies the asynchronous K-fellow traveler property, and has a departure function.

Although we have not mentioned a departure function in defining an automatic structure L → G, the language L actually has a linear departure function. This is proven in theorem 3.3.4 of [ECHLPT]. Thus an automatic structure is a special case of an asynchronous automatic structure, where the reparameterization maps are the identity and the departure function is linear. However, in section 7.4 of [ECHLPT] the Baumslag-Solitar groups are shown to be asynchronously automatic but not automatic. Even automatic groups can admit other asynchronous automatic structures which are not automatic structures. The fundamental groups of closed hyperbolic 3-manifolds which fiber over the circle give examples of such groups. See [NS] for details.

In theorem 2.5.1 (resp. theorem 7.3.2) of [ECHLPT] it is shown that every automatic structure (resp. asynchronous automatic structure) L → G has a substructure L′ ⊂ L with uniqueness; that is, L′ → G is an automatic structure (resp. asynchronous automatic structure), and the projection map restricted to L′ is bijective.

The geometric content of the definitions of (asynchronous) automatic structure with uniqueness gives rise to the following concepts. By a synchronous combing (resp. asynchronous combing) on a finitely generated group G we mean a section σ for the projection map A^{∗} → G, such that σ(G) ⊂ A^{∗} satisfies the K-fellow traveler property (resp. asynchronous K-fellow traveler property). We say that σ is a combing with departure if σ(G) has a departure function. Clearly an asynchronous automatic structure on G gives rise to an asynchronous combing with departure.

Let L → G be an (asynchronous) automatic structure with uniqueness, such that the empty word in L maps to id ∈ G. The words of L (viewed as paths in the Cayley graph of G) have an obvious geometric constraint; namely, they satisfy the (asynchronous) Kfellow traveler property. Given u, v ∈ L with d(\overline{u}, \overline{v}) = R, we can apply the definition of asynchronous K-fellow traveler property to the (R + 1) L-paths whose endpoints are the vertices on a geodesic segment from \overline{u} to \overline{v}, to conclude that u and v must lie in KR-Hausdorff neighborhoods of each other. Case I of Theorem 1 is proven by exhibiting L-paths which do not satisfy this Hausdorff neighborhood condition. We will say that such paths contradict the asynchronous K-fellow traveler property of L.

In the two lemmas below we list some other geometric properties of words in L, which are derived from the regularity of L. Let q be the number of states in the automaton accepting L. We will denote by d( , ) the metric in the Cayley graph Γ_{A}(G). Lemma 1.1 says that every subsegment of a word in L will look something like a word in L.

Lemma 1.1. If u ∈ L and v is any subsegment of u, then there are words v_{1}, v_{2} ∈ A^{∗} of length ≤ q such that v_{1}vv_{2} ∈ L.

Proof. The endpoints of v break u into three segments. Consider u as a directed path in the finite state automaton graph. Let s_{1}, s_{2} be the states at the beginning and end of v respectively. The first segment of u is a path from the start state to s_{1}; choose a shortest such path. This gives a word in A^{∗} which we call v_{1}. Similarly, the last segment of u is a path from s_{2} to an accept state. Take a shortest such path to get a word v_{2}. Clearly v_{1}, v_{2} are both of length ≤ q. By construction, v_{1}vv_{2} is accepted by the automaton, and so is a word in L. □

We will refer to v_{1} as a head and to v_{2} as a tail, which we attach to v. Combining this with the (asynchronous) K-fellow traveler property gives a bound on how much L words can back track.

Lemma 1.2. If u ∈ L and v a subsegment of u with endpoints a, b then

v ⊂ B_{K(2q+d(a,b))+q}(a)

where B_{r}(a) denotes the ball of radius r about a in Γ_{A}(G).

Proof. Lemma 1.1 ensures that we can find short words v_{1}, v_{2} ∈ A^{∗} so that w = v_{1}vv_{2} ∈ L. Then d(id, \overline{w}) ≤ 2q + d(a, b). Now the empty word in L maps to id so that the (asynchronous) K-fellow traveler property gives

w ⊂ B_{K(2q+d(a,b))}(id)

Thus

w ⊂ B_{K(2q+d(a,b))+q}(\overline{v_{1}})

and so

v ⊂ B_{K(2q+d(a,b))+q}(a)

as required. □

§2. Sol geometry groups

The Lie group Sol is one of the eight basic geometries that one considers in the study of 3-manifolds. There is a good collection of background literature on Sol: for example [G] chapter 3, and [Sc]. We give the definition and describe basic properties of Sol here, mainly as a means of establishing notation for the remainder of the paper.

One can describe Sol as a semi direct product ℝ^{2} ⋊ ℝ where t ∈ ℝ acts on ℝ^{2} via the map

(x, y) ↦ (e^{t}x, e^{−t}y) .

We can identify Sol with ℝ^{3} so that the normal subgroup ℝ^{2} maps to the xy-plane. Multiplication is defined by

(x, y, z)(x′, y′, z′) = (x + e^{−z}x′, y + e^{z}y′, z + z′) .

Note that conjugation by (0, 0, t)

(0, 0, −t)(x, y, 0)(0, 0, t) = (e^{t}x, e^{−t}y, 0)

acts on the xy-plane in exactly the same way as conjugation by t acts on ℝ^{2}. Thus, t ↦ (0, 0, t) preserves the correct action of ℝ on ℝ^{2}. Using the group multiplication we obtain a left invariant metric of the form

ds^{2} = e^{2z}dx^{2} + e^{−2z}dy^{2} + dz^{2} .

Let d_{S}( , ) denote the distance function on Sol. The distance between two points is given by inf{length(γ)} where γ ranges over all rectifiable paths between the points. Since Sol is a complete Riemannian manifold, this inf is realized by a geodesic path in Sol.

Consider two points in the xz-plane. The infimum above is achieved for a path γ which lies entirely in this plane (since the e^{−2z}dy^{2} term in ds^{2} will contribute a positive amount to an arclength integral for paths with nonzero y component). Thus the metric on the xz-plane induced by ds^{2} = e^{2z}dx^{2} + dz^{2} agrees with the Sol metric. On mapping this plane to the upper half plane

{(x_{1}, x_{2}) ∈ ℝ^{2} : x_{2} > 0}

by

(x, z) ↦ (x_{1}, x_{2}) = (x, e^{−z})

the metric becomes the standard hyperbolic metric

ds^{2} = \frac{dx_{1}^{2} + dx_{2}^{2}}{x_{2}^{2}} .

Thus the xz-plane is a convexly embedded copy of ℍ^{2} in Sol. Similarly, the yz-plane is another convex ℍ^{2} in Sol. A standard computation in ℍ^{2} yields

d_{S}((x, 0, 0), (x′, 0, 0)) = d_{ℍ^{2}}((x, 1), (x′, 1))
= 2 log [\sqrt{1 + ((x − x′)/2)^{2}} + |x − x′|/2] .

Thus, for |x − x′| ≥ 2 we have

(2.1)  2 log |x − x′| ≤ d_{S}((x, 0, 0), (x′, 0, 0)) ≤ 2 log [\frac{3|x − x′|}{2}]

Note that |x − x′| is the Euclidean distance in the xy-plane from (x, 0, 0) to (x′, 0, 0). Similarly, for |y − y′| ≥ 2 we have

(2.2)  2 log |y − y′| ≤ d_{S}((0, y, 0), (0, y′, 0)) ≤ 2 log [\frac{3|y − y′|}{2}]

We will need to compare Euclidean distances between points in the xy-plane with Sol distances.

Definition 2.1. The two points (p_{1}, q_{1}, 0) and (p_{2}, q_{2}, 0) are said to have difference vector ⟨d_{1}, d_{2}⟩ = ⟨p_{2} − p_{1}, q_{2} − q_{1}⟩.

Lemma 2.2. If points (p_{1}, q_{1}, 0) and (p_{2}, q_{2}, 0) in Sol have difference vector ⟨d_{1}, d_{2}⟩ with |d_{i}| ≥ 2 then

max {2 log |d_{1}| , 2 log |d_{2}|} ≤ d_{S}((p_{1}, q_{1}, 0), (p_{2}, q_{2}, 0))

≤ 2 log [\frac{3|d_{1}|}{2}] + 2 log [\frac{3|d_{2}|}{2}]

Proof. Since left multiplication by (−p_{2}, q_{1}, 0) is an isometry of Sol, we have

d_{S}((p_{1}, q_{1}, 0), (p_{2}, q_{2}, 0)) = d_{S}((−d_{1}, 0, 0), (0, d_{2}, 0))
≥ max {d_{S}((0, 0, 0), (0, d_{2}, 0)) , d_{S}((−d_{1}, 0, 0), (0, 0, 0))}
≥ max {2 log |d_{2}| , 2 log |d_{1}|}

The first inequality is a consequence of the fact that the minimum Sol distance from (−d_{1}, 0, 0) to the line x = z = 0 is precisely d_{S}((0, 0, 0), (−d_{1}, 0, 0)) (and similarly for (0, d_{2}, 0) and the line y = z = 0). The second inequality follows from the estimates (2.1) and (2.2).

By the triangle inequality we also have an upper bound

d_{S}((p_{1}, q_{1}, 0), (p_{2}, q_{2}, 0)) = d_{S}((−d_{1}, 0, 0), (0, d_{2}, 0))

≤ d_{S}((−d_{1}, 0, 0), (0, 0, 0)) + d_{S}((0, 0, 0), (0, d_{2}, 0))

≤ 2 log [\frac{3|d_{1}|}{2}] + 2 log [\frac{3|d_{2}|}{2}]

and so the lemma follows. □

The next lemma gives a computation for the distance from a point in Sol to the xzplane. This will be useful in section 4. A similar result holds for distances from points to the yz-plane, only z must be replaced by −z in the right hand side of the equation in Lemma 2.3. Let dist_{S}( , ) denote the Sol distance from a point to a closed subset.

Lemma 2.3. For each point (x, y, z) in Sol we have

dist_{S}((x, y, z) , xz-plane) = log [\sqrt{1 + (\frac{ye^{−z}}{2} )^{2}} + \frac{|y|e^{−z}}{2} ]

Proof. Since left multiplication by (−xe^{z}, 0, −z) is an isometry of Sol which preserves the xz-plane we have

dist_{S}((x, y, z) , xz-plane) = dist_{S}((0, ye^{−z}, 0) , xz-plane)

= dist_{S}((0, ye^{−z}, 0) , z-axis)

= dist_{ℍ^{2}}((ye^{−z}, 1) , x_{2}-axis)

= log [\sqrt{1 + (\frac{ye^{−z}}{2} )^{2}} + \frac{|y|e^{−z}}{2} ]

The second equality is just the observation that any point which minimizes the distance from (0, ye^{−z}, 0) to the xz-plane must have zero x-component (any path γ realizing this distance cannot have a non zero x-component, since this would contribute a positive amount to the arc length integral). The other two equalities follow exactly as in the derivation of estimate (2.1). □

In [Sc], it is shown that any lattice G < Sol (i.e. discrete, cofinite volume subgroup) is actually uniform (i.e. cocompact) and that the 3-dimensional manifold Sol/G is a torus bundle over S^{1} with Anosov monodromy. Thus G has a presentation

(2.3)  G = G_{ϕ} = ⟨ a, b, t : [a, b] = 1, t^{−1}at = ϕ(a), t^{−1}bt = ϕ(b) ⟩

where ϕ ∈ Sl_{2}(ℤ) is a hyperbolic element (i.e. |tr(ϕ)| > 2). Note that ϕ will have two irrational eigenvalues λ and λ^{−1}, with irrational slope eigendirections. In [Bri] it is shown that the groups G_{ϕ} are asynchronously combable with departure. It is interesting to note that the combing lines of the asynchronous combing provided in [Bri] ‘intersect’ the base ⟨a, b⟩ coset in a pattern which has irrational slopes, and so cannot come from a regular language in the generating set {a^{±1}, b^{±1}, t^{±1}}.

We can realize G = ℤ^{2} ⋊_{ϕ} ℤ explicitly as a subgroup of Sol as follows. First embed the normal subgroup ℤ^{2} in ℝ^{2} as the standard integer lattice. Now ϕ ∈ Sl_{2}(ℤ) acts on ℝ^{2} (preserving ℤ^{2}) with unit λ-eigenvector (e_{1}, e_{2}) and unit λ^{−1}-eigenvector (f_{1}, f_{2}). Let U : ℝ^{2} → ℝ^{2} be the linear map which takes (e_{1}, e_{2}) to (1, 0) and (f_{1}, f_{2}) to (0, 1). Now define f : G → Sol by

(2.4)  (a^{m}, b^{n}, t^{p}) ↦ (U(m, n), p log(λ)) .

It is clear from the definition of multiplication in Sol given above that f is a monomorphism and that its image is a lattice in Sol. There is an obvious way to extend f to a Gequivariant map f′ : Γ_{A}(G) → Sol. For example, we may map the edge [id, t] to the interval [(0, 0, 0), (0, 0, log(λ))] on the z-axis. Map the edge [id, a] (resp. [id, b]) to the straight segment [(0, 0, 0), (U(1, 0), 0)] (resp. [(0, 0, 0), (U(0, 1), 0)]) in the xy-plane. Finally, we map the other edges of Γ_{A}(G) to the appropriate G translates of these three segments. Since both Γ_{A}(G)/G and Sol/G are compact, theorem 1 of [C] shows that there are constants ϵ_{1}, ϵ_{2} > 0 such that

(2.5)  ϵ_{1}d_{S}(f′(x), f′(y)) ≤ d_{A}(x, y) ≤ ϵ_{2}d_{S}(f′(x), f′(y))

for all x, y ∈ Γ_{A}(G). This estimate enables us to translate problems about the geometry of L-paths in Γ_{A}(G) into questions about paths in Sol.

§3. Proof of Theorem 1: Reduction

We prove Theorem 1 by contradiction. Suppose we are given that G is asynchronously automatic. From section 1 we know that there is an asynchronous automatic structure L ⊂ A^{∗} with uniqueness for G, where A = {a, b, t, a^{−1}, b^{−1}, t^{−1}} is the standard monoid generating set corresponding to the presentation (2.3). Throughout this proof Δ denotes the finite state automaton which accepts L. Recall that Δ is a finite directed graph, with edges labeled by the elements of A. Let q denote the number of states in Δ.

Definition 3.1. A loop in Δ is a closed directed edgepath (not necessarily a simple closed path) contained in Δ.

Given a loop with a base vertex one can read off a word in A^{∗}, which will have a positive, negative, or zero t-exponent sum. We say that the loop has (respectively) positive, negative, or zero type. Note that the type of a loop is independent of the base vertex chosen.

Definition 3.2. A state s of Δ is said to be (1) accessible if there is a directed edgepath from the start state to s, and

(2) live if there is a directed edgepath from s to an accept state.

The proof of Theorem 1 breaks into two cases, depending on the structure of the graph Δ.

Case I: There are at least two types of loops based at some live and accessible state s in Δ.

We may assume that on reading two of the loops at s one obtains the words

(3.1)  l_{1} = t^{l}w = t^{l}a^{m_{1}}b^{n_{1}}

and

(3.2)  l_{2} = v = a^{m_{2}}b^{n_{2}}

where 0 < l ∈ ℤ and m_{i}, n_{i} ∈ ℤ are such that v ≠ id ∈ ⟨a, b⟩ ≅ ℤ^{2}.

Why can we make this assumption? First, we can ensure that one loop is of zero type by taking appropriate combinations of positive and negative type loops if necessary. Secondly, we may assume that the loop corresponding to l_{1} is of positive type (i.e. l > 0), since the geometry of the negative-zero case is similar to this. This will become apparent on reading the arguments for the positive-zero case in section 4.

Finally, the two loops at s may give words l′_{1}, l′_{2} ∈ A^{∗} with \overline{l′_{i}} = \overline{l_{i}} but l′_{i} ≠ l_{i}. Let M denote the larger of the lengths of the l′_{i}. Then every L-path stays within an M/2neighborhood of the corresponding edgepath constructed using the l_{i} instead of the l′_{i}. In section 4 we shall consider the subset of L consisting of words of the form u_{1}wu_{2}, where w is a word in the free monoid on {l′_{1}, l′_{2}}. Here u_{1} (resp. u_{2}) is obtained by tracing a shortest directed edgepath from the start state to s (resp. from s to an accept state), so that u_{1}, u_{2} have length at most q. These L-words track the left translate by \overline{u_{1}} of the submonoid of G generated by \{\overline{l_{1}}, \overline{l_{2}}\}. In section 4 we study the geometry of such submonoids of G. Certain paths in these monoids diverge far apart in Γ_{A}(G) and then re-converge, so that the corresponding L-paths contradict the asynchronous K-fellow traveler property (for any K). Actually, we will work with the free monoid on {l_{1}, l_{2}}, but since L-paths stay within an M/2 neighborhood of these paths the contradiction still holds.

Remark 3.3. This is an example of how an asynchronous automatic structure L → G is more restrictive than an asynchronous combing with departure. Since L is regular, it must be accepted by some finite state automaton Δ. Reading off a set of n based loops at some live and accessible state of Δ gives words w_{1}, …, w_{n} ∈ A^{∗}. As above, certain L-words must track (a left translate of) the submonoid of G generated by \{\overline{w_{1}}, …, \overline{w_{n}}\}. This involves the group multiplication on G, unlike an asynchronous combing with departure which is a purely geometric notion. In order to study the shape of an asynchronous automatic structure on a group G, we need an understanding of the geometry of finitely generated submonoids of G. We examine very specific two generator submonoids of a Sol lattice in section 4, and consider Hausdorff neighborhoods of single generator submonoids in section 5.

Another example of this interaction of logical complexity and geometry is seen, for example, in the case of torsion free hyperbolic groups, where where single generator submonoids track geodesic paths in the Cayley graph. This fact was an essential ingredient in the proof of Theorem 1 of [Bra].

Case II: There is at most one type of loop at each live and accessible state s in Δ.

We use the asynchronous K-fellow traveler property to show that L cannot map onto G. In particular there is an R > 0 and w ∈ L such that \overline{L} does not contain all the points of G that are within R of \overline{w};

(3.3)  G ∩ B_{R}(\overline{w}) ⊄ \overline{L} .

This gives a contradiction in case II and proves Theorem 1. This case includes the case where L is a simply starred language. This means that there is at most one loop at each live and accessible state of the finite state automaton accepting L. We note that in the simply starred case the language L has only got polynomial growth, and so could not surject onto G. We say that in Case II L is geometrically simply starred: that is, it is simply starred with respect to the type of loops in Δ.

We shall see in section 5 that L-words have a particularly simple geometric shape in Sol: they ‘change direction’ only finitely many times. The argument in section 5 is similar in flavor to previous work on simply starred languages, in particular the work in [NS] on asynchronous automatic structures on virtually abelian groups, and the work of [BG] on nilpotent groups.

The L-word w with the property (3.3) has a special form. The following definition establishes the terminology and concepts which will be used in section 5 to construct w and prove the neighborhood property (3.3).

Definition 3.4. An L-track is a directed edgepath in Δ beginning at the start state and ending at an accept state. Every L-word, by definition, describes an L-track in Δ.

A stem is an L-track which has no repeated states. Thus the length (i.e. number of edges) of a stem is at most q − 1. Every L-track ‘contains’ (as a subset of Δ) at least one stem; obtained by just omitting any loops that may occur as we proceed along the L-track.

All states along an L-track are live and accessible. Define a live and accessible state s to be positive (resp. negative, zero) if there is a loop in Δ based at s which is of positive

Figure 1. A maximal stem and an associated standard L-track.

(resp. negative, zero) type. If there are no loops based at s we call it a null state. The hypothesis of Case II ensures that these notions are well defined.

Definition 3.5. A stem induces a linear order on its set of states. Label these states by s_{1}, …, s_{m} where the subscripts denote the ordering. We call (s_{i}, s_{j}) where i < j a change if it has the following properties:

(1) the set {s_{i+1}, …, s_{j−1}} is either empty or consists entirely of null states,

(2) neither of the states s_{i} or s_{j} are null, and

(3) the states s_{i} and s_{j} are not both positive, negative or zero.

For example, the stem in figure 1 has 4 changes: namely, (s_{4}, s_{5}), (s_{5}, s_{6}), (s_{6}, s_{8}) and (s_{9}, s_{11}).

Since Δ is a finite graph, it can contain only finitely many stems.

Definition 3.6. A stem is said to be maximal if it contains a maximal number of changes. We call w ∈ L a maximal L-word if its L-track contains a maximal stem.

For each change (s_{i}, s_{j}) along a maximal stem add a loop of the appropriate type to the vertex s_{i}. Also add a loop to the final non-null vertex of the stem. We call the resulting track a standard maximal L-track. See figure 1. If a word has a standard maximal L-track as its track we call it a standard maximal L-word.

In section 5 we will work with these standard maximal L-words to prove that there is a word w ∈ L which satisfies the neighborhood property (3.3), and hence that L does not map onto G.

§4 Proof of Theorem 1: Case I

Recall from section 3 that, in this case, there is a positive type loop l_{1} and a type zero loop l_{2}, based at a live and accessible state s in the finite state automaton graph Δ for L.

We assume that l_{1} and l_{2} are of the forms described in (3.1) and (3.2) respectively.

In order to obtain a contradiction in this case we need to find two words γ_{1} and γ_{2} in the free monoid on \{l_{1}, l_{2}\} and a constant B > 0 such that d(\overline{γ_{1}}, \overline{γ_{2}}) ≤ \frac{B}{K} − 2q yet the path γ_{1} is not contained in a (B + q)-Hausdorff neighborhood of γ_{2}. We know from Lemma 1.2 that there are L-words v_{i} = u_{1}γ_{i}u_{2} where the lengths of the u_{i} are bounded by q, the number of states in Δ. Thus d(\overline{v_{1}}, \overline{v_{2}}) < \frac{B}{K} but v_{1} does not lie inside a B-Hausdorff neighborhood of v_{2}. This contradicts the asynchronous K-fellow traveler property of L.

We may suppose that the γ_{i} are paths in Sol, provided we use the estimate (2.5) to translate the bounds. There is a constant C > 0 such that γ_{1} is not contained in a C Hausdorff neighborhood of γ_{2} in Sol, and yet

(4.1)  d_{S}(\overline{γ_{1}}, \overline{γ_{2}}) ≤ α_{1}C − α_{2}

where C + \frac{B+q}{ϵ_{1}} , α_{1} = \frac{ϵ_{1}}{ϵ_{2}K} and α_{2} = \frac{(2K+1)q}{ϵ_{2}K}.

It is instructive to begin by considering the special case where l_{1} = t^{l} and l_{2} = v = a^{m_{2}}b^{n_{2}} (i.e. w = id ∈ ⟨a, b⟩). We shall consider the general case of l_{i} given by (3.1) and (3.2) in the Remarks 4.4 at the end of this section. Recall that the embedding f defined by (2.4) takes the eigendirections of ϕ to the x- and y-axes in Sol. Since these eigendirections have irrational slopes, the element v corresponds to a point (x, y, 0) in Sol where y/x is irrational. Thus, the vector v is not parallel to either axis. For the sake of concreteness, we assume that both x and y are positive.

Definition/Remark 4.1. For k ∈ ℤ call the left translate of the xy-plane by t^{k} = (0, 0, k log(λ)) the k-level. The coset t^{k}⟨a, b⟩ lies in the k-level. If P is a point in a k-level and Q is a point in a (k + n)-level, then an easy arc length computation gives d_{S}(P, Q) ≥ n log(λ). This fact will be used later to show that the paths γ_{i} diverge.

We construct the paths γ_{1} and γ_{2} in a piecewise fashion. There are two main steps; a divergence estimate, and a convergence construction. Here is an outline of the procedure.

(1) The divergence step: The initial segments [γ_{1}]_{1} and [γ_{2}]_{1} are defined so that the paths diverge. The definitions involve Nth powers of the l_{i} where N ∈ ℕ is large and even. The path γ_{2} is of the form [γ_{2}]_{1}l1^{\frac{N}{2}} u where u is some word in the monoid ⟨l_{1}, l_{2}⟩. We prove that the endpoint E_{1} of [γ_{1}]_{1} lies outside of a C(N)-neighborhood of all of γ_{2}, for large N. The bound C(N) is a linear function of N.

(2) The convergence construction: We iterate a construction which forces the γ_{i} to converge. Suppose that the endpoints E_{j} and F_{j} of [γ_{1}]_{j} and [γ_{2}]_{j} lie on some k_{j}-level. We add segments to the [γ_{i}]_{j} to obtain paths [γ_{1}]_{j+1} and [γ_{2}]_{j+1} with endpoints E_{j+1} and F_{j+1} on some k_{j+1}-level. Under suitable conditions distances decrease according to

d_{S}(E_{j+1}, F_{j+1}) ≤ \frac{2}{3}d_{S}(E_{j}, F_{j}) .

SOL GEOMETRY GROUPS ARE NOT ASYNCHRONOUSLY AUTOMATIC 13

We find lower bounds for N which ensure that this process continues until setting

γ_{i} = [γ_{i}]_{r}

for some r, we have

d_{S}(\overline{γ_{1}}, \overline{γ_{2}}) ≤ α_{1}C(N) − α_{2}

which is the required contradiction.

Figure 2. The segments [γ_{1}]_{1} and [γ_{2}]_{1}l_{1}^{\frac{N}{2}} in Sol.

Step 1.(Divergence) For N ∈ ℕ large and even define

[γ_{1}]_{1} = l_{1}^{N}l_{2}^{λ^{lN} +β_{1}}

and

[γ_{2}]_{1} = l_{2}l_{1}^{N}

where λ^{2l} + 1 ≤ β_{1} < λ^{2l} + 2 is chosen such that λ^{lN} + β_{1} ∈ ℕ. Figure 2 is a picture of the paths [γ_{1}]_{1} and [γ_{2}]_{1}l_{1}^{\frac{N}{2}} . Let E_{1} be the endpoint \overline{[γ_{1}]}_{1} and F_{1} be the endpoint \overline{[γ_{2}]}_{1}. Thus

E_{1} = \overline{[γ_{1}]}_{1}
= (0, 0, lN log(λ)) ((λ^{lN} + β_{1})x, (λ^{lN} + β_{1})y, 0)
= ([1 + β_{1}λ^{−lN}]x, [λ^{lN} + β_{1}]λ^{lN}y, lN log(λ))

and

F_{1} = (x, y, lN log(λ)) .

The points

A_{1} = (x, y, \frac{lN}{2} log(λ))
A_{2} = (x, y, \frac{3lN}{2} log(λ))

both lie on [γ_{2}]_{1}l_{1}^{\frac{N}{2}} . The next lemma tells us that E_{1} lies outside a large neighborhood of γ_{2}.

Lemma 4.2. Let E_{1}, [γ_{1}]_{1} and [γ_{2}]_{1} be as above. Suppose that γ_{2} is formed by adjoining l_{1}^{\frac{N}{2}} u to the endpoint of [γ_{2}]_{1}, where u is any word in the monoid ⟨l_{1}, l_{2}⟩. Then, if

N ≥ max \{\frac{2 log_{λ}(2)}{l} , \frac{2 log_{λ}(y)}{l}\}

E_{1} lies outside a C(N)-neighborhood of γ_{2} where

C(N) = \frac{Nl}{2} log(λ)

Proof. The subsegment of [γ_{2}]_{1} from (0, 0, 0) to A_{1} lies below the \frac{lN}{2} -level and so E_{1} is at least \frac{lN}{2} log(λ) from it. Similarly, the last segment of γ_{2} (from A_{2} to the endpoint \overline{γ_{2}}) lies on or above the \frac{3lN}{2} -level, and so E_{1} is at least \frac{lN}{2} log(λ) from it too.

So we only need to estimate the distance from E_{1} to [A_{1}, A_{2}], the middle segment of γ_{2}. For P = (x, y, z_{p}) ∈ [A_{1}, A_{2}] we have

\frac{lN}{2} log(λ) ≤ z_{p} ≤ \frac{3lN}{2} log(λ) .

Thus, Lemma 2.3 gives the upper bound

dist_{S}(P, xz-plane) = log [\sqrt{1 + (\frac{ye^{−z_{p}}}{2} )^{2}} + \frac{ye^{−z_{p}}}{2} ]

≤ log [\sqrt{1 + (\frac{y}{2λ^{\frac{lN}{2}}} )^{2}} + \frac{y}{2λ^{\frac{lN}{2}}} ]

≤ log(2)

for N ≥ N_{1} = \frac{2}{l}log_{λ}(y). Lemma 2.3 also gives a lower bound for the distance from E_{1} to the xz-plane.

dist_{S}(E_{1} , xz-plane)

= dist_{S} (([1 + β_{1}λ^{−lN}]x, [λ^{lN} + β_{1}]λ^{lN}y, lN log(λ)) , xz-plane)

= log [\sqrt{1 + (\frac{(λ^{lN} + β_{1})y}{2} )^{2}} + \frac{(λ^{lN} + β_{1})y}{2} ]

≥ log [(λ^{lN} + β_{1})y]

= log(y) + log(1 + β_{1}λ^{−lN}) + lN log(λ)

> lN log(λ)

Here we are assuming that log(y) > 0 or y > 1. We can ensure that both x, y > 2 (needed for a later application of Lemma 2.2) by replacing the loop at s corresponding to l_{2} by a positive multiple of itself if necessary.

There is some point P_{0} on [A_{1}, A_{2}] which realizes dist_{S}(E_{1}, [A_{1}, A_{2}]). From the first inequality we know that there is a point P′_{0} on the xz-plane such that d_{S}(P_{0}, P′_{0}) ≤ log(2). Then the triangle inequality gives

dist_{S}(E_{1}, [A_{1}, A_{2}]) = d_{S}(E_{1}, P_{0})
≥ d_{S}(E_{1}, P′_{0}) − d_{S}(P′_{0}, P_{0})
≥ lN log(λ) − log(2) .

Thus dist_{S}(E_{1}, [A_{1}, A_{2}]) ≥ \frac{lN}{2} log(λ) provided N ≥ N_{2} = \frac{2 log_{λ}(2)}{l}.

Combining these estimates gives

dist_{S}(E_{1}, γ_{2}) ≥ C(N)

where C(N) = \frac{lN}{2} log(λ) provided N ≥ max \{N_{1}, N_{2}\} as required. □

Step 2. (Convergence) The endpoints E_{1} and F_{1} of [γ_{1}]_{1} and [γ_{2}]_{1} lie on the Nl-level. Projecting them to the xy-plane via left multiplication by t^{−lN} gives points

t^{−lN}E_{1} = \overline{l_{2}}^{λ^{lN} +β_{1}} = ([λ^{lN} + β_{1}]x, [λ^{lN} + β_{1}]y, 0)

and

t^{−lN}F_{1} = t^{−lN} \overline{l_{2}}\overline{l_{1}^{N}}
= t^{−lN}(x, y, 0)t^{lN}
= (λ^{lN}x, λ^{−lN}y, 0) .

These have difference vector

⟨β_{1}x, D_{1}y⟩

where

(4.2)  D_{1} = λ^{lN} + β_{1} − λ^{−lN} .

Since left multiplication by t^{−lN} is an isometry we can estimate d_{S}(E_{1}, F_{1}) in the xy-plane. Applying Lemma 2.2 (since x, y > 2) we obtain

d_{S}(E_{1}, F_{1}) = d_{S} ((0, 0, 0) , (β_{1}x, D_{1}y, 0))

≤ 2 log [\frac{3β_{1}x}{2}] + 2 log [\frac{3D_{1}y}{2} ] .

Before giving a description of the convergence iteration, first look at the effect of right multiplication on difference vectors. Suppose g_{1}, g_{2} ∈ G lie on some k-level, and map isometrically (via left multiplication by t^{−k}) to points (p_{1}, q_{1}, 0) and (p_{2}, q_{2}, 0) in the xyplane. They have difference vector

⟨d_{1}, d_{2}⟩ = ⟨p_{2} − p_{1}, q_{2} − q_{1}⟩ .

Right multiplication by l_{1}^{m} (where m > 0) gives points g_{1}t^{lm} on the (k + lm)-level, which project to points

t^{−lm}t^{−k}g_{i}t^{lm} = t^{−lm}(p_{i}, q_{i}, 0)t^{lm}
= (λ^{lm}p_{i}, λ^{−lm}q_{i}, 0) .

The new difference vector is

⟨λ^{lm}d_{1}, λ^{−lm}d_{2}⟩

which has slope λ^{−2lm} \frac{y}{x}.

If we only right multiply g_{2} by \overline{l_{2}}^{n} (for some n > 0) then the points g_{1} and g_{2}\overline{l_{2}}^{n} still lie on the k-level. They project to the points

t^{−k}g_{1} = (p_{1}, q_{1}, 0)

and

t^{−k}g_{2}\overline{l_{2}}^{n} = (p_{2}, q_{2}, 0)(nx, ny, 0)
= (p_{2} + nx, q_{2} + ny, 0)

in the xy-plane. These have difference vector

⟨d_{1} + nx, d_{2} + ny⟩ .

The convergence construction exploits these effects of right multiplication on difference vectors. Here is the precise description.

Convergence construction: Hypothesis. Assume that for some j ≥ 1 the paths [γ_{1}]_{j} and [γ_{2}]_{j} have endpoints E_{j} and F_{j} which lie on the k_{j}-level. Suppose that these points project (via left multiplication) to the xy-plane with difference vector

⟨β_{j}x, D_{j}y⟩

where β_{j} satisfies λ^{2l} + 1 ≤ β_{j} < λ^{2l} + 2 and where D_{j} ≥ λ^{2l} + 2. Recall that x and y are the coordinates of \overline{l_{2}} = v. Note that the slope of this vector is greater than \frac{y}{x}. In figure 3 (a) t^{−k_{j}}E_{j} has smaller x- and y-coordinates than t^{−k_{j}}F_{j}.

Figure 3. Difference vectors in the convergence construction.

Convergence construction: Inductive step. Let n_{j} be the greatest integer less than or equal to \frac{1}{2} log_{λ^{l}}(D_{j}) so that

(4.3)  D_{j} = λ^{l(2n_{j}+2θ_{j})} for some 0 ≤ θ_{j} < 1.

Since D_{j} ≥ λ^{2l} + 2 we see that n_{j} will be at least 1. Now define

[γ_{1}]_{j+1} = [γ_{1}]_{j}l_{1}^{n_{j}}l_{2}^{λ^{ln_{j}} β_{j}+β_{j+1}}

and

[γ_{2}]_{j+1} = [γ_{2}]_{j}l_{1}^{n_{j}}

where λ^{2l} + 1 ≤ β_{j+1} < λ^{2l} + 2 is chosen such that β_{j+1} + λ^{ln_{j}}β_{j} ∈ ℕ.

Let E_{j+1} and F_{j+1} be the endpoints of [γ_{1}]_{j+1} and [γ_{2}]_{j+1} respectively. Then they project (via left multiplication) to points in the xy-plane with difference vector

⟨β_{j+1}x, D_{j+1}y⟩

where

D_{j+1} = λ^{ln_{j}}β_{j} + β_{j+1} − λ^{−ln_{j}}D_{j}

= λ^{ln_{j}}(β_{j} − λ^{2lθ_{j}}) + β_{j+1} (4.4)

The second equality uses equation (4.3). Now the hypothesis on β_{j} implies that

D_{j+1} ≥ λ^{ln_{j}}(1) + β_{j+1}
≥ λ^{ln_{j}} .

For n_{j} ≥ N_{3} = \frac{log_{λ}(λ^{2l}+2)}{l} this becomes

D_{j+1} ≥ λ^{2l} + 2

and so we can iterate the procedure. The difference vector ⟨β_{j+1}x, D_{j+1}y⟩ is shown in figure 3 (b).

Note that the x- and y-coordinates of t^{−(ln_{j}+k_{j})}E_{j+1} will be larger than those of t^{−(ln_{j}+k_{j})}F_{j+1} this time, so the roles of the [γ_{i}]_{j+1} will be reversed. After a few iterates the paths [γ_{i}]_{j} will spiral around each other in Sol as shown in figure 4. Convergence construction: Case j = 1. We start the iteration at j = 1. From equation (4.2) we know that the difference vector for the points t^{−lN}F_{1} and t^{−lN}E_{1} is ⟨β_{1}x, D_{1}y⟩ where

D_{1} = λ^{lN} + β_{1} − λ^{−lN}
= λ^{lN}(1 + β_{1}λ^{−lN} − λ^{−2lN}) .

Figure 4. The paths γ_{i} in Sol

Now n_{1} is the greatest integer less than or equal to \frac{1}{2} log_{λ^{l}}(D_{1}). Thus

n_{1} = \frac{N}{2}

provided N is large enough so that log_{λ^{l}}(1 + β_{1}λ^{−lN} − λ^{−2lN}) < 2. This is true if

N ≥ N_{4} = \frac{1}{l} log_{λ} [\frac{λ^{2l} + 2}{λ^{2l} − 1}] .

Thus the path γ_{2} will be of the form [γ_{2}]_{1}l1^{\frac{N}{2}} u as described in Lemma 4.2, and so the divergence estimate holds.

We have defined the convergence construction inductively. The next lemma gives conditions on the n_{j} which ensure that the paths being constructed are actually converging.

Lemma 4.3. If n_{j} is large enough in the convergence construction above, then

d_{S}(E_{j+1}, F_{j+1}) ≤ \frac{2}{3}d_{S}(E_{j}, F_{j}) .

Exact lower bounds N_{5} and N_{6} for n_{j} are given in the proof.

Proof. We will work in the case where t^{−k_{j}}E_{j} has smaller x- and y-coordinates than t^{−k_{j}}F_{j}. The same argument works in the other case.

Since left multiplication is an isometry we have

d_{S}(E_{j+1}, F_{j+1}) = d_{S}( (0, 0, 0) , (β_{j+1}x, D_{j+1}y, 0) ) .

Thus Lemma 2.2 and equation (4.4) give

d_{S}(E_{j+1}, F_{j+1}) ≤ 2 log [\frac{3β_{j+1}x}{2}] + 2 log [\frac{3y}{2} D_{j+1}]

= 2 log [\frac{3β_{j+1}x}{2}] + 2 log [\frac{3y}{2} λ^{ln_{j}}(β_{j} − λ^{2lθ_{j}} + λ^{−ln_{j}}β_{j+1})]

< 2 log [\frac{3}{2}(λ^{2l} + 2)] + log [\frac{3y}{2} ] + 2 log(λ)ln_{j}

+ 2 log [β_{j} − λ^{2lθ_{j}} + λ^{−ln_{j}}β_{j+1}] < C_{1} + 2 log(λ)ln_{j}

where

C_{1} = 2 log [\frac{3}{2}(λ^{2l} + 2)] + 2 log [\frac{3y}{2} ] + 2 log [2(λ^{2l} + 2)] .

Note that C_{1} is a positive constant since x, y > 1.

On the other hand, Lemma 2.2 and equation (4.3) give

d_{S} ( (0, 0, 0) , (β_{j}x, D_{j}y, 0) ) ≥ max {2 log [β_{j}x] , 2 log [D_{j}y]}
≥ max {2 log [(λ^{2l} + 1)x] , 2 log [λ^{l(2n_{j}+2θ_{j})}y]}
≥ max {2 log [(λ^{2l} + 1)x] , 2(2ln_{j}) log(λ)}
= 4ln_{j} log(λ)

provided

n_{j} ≥ N_{5} = \frac{log [(λ^{2l} + 1)x]}{2l log(λ)} .

Combining these estimates, we see that

d_{S}(E_{j+1}, F_{j+1}) ≤ \frac{2}{3}d_{S}(E_{j}, F_{j})

if

C_{1} + 2ln_{j} log(λ) ≤ \frac{8ln_{j} log(λ)}{3} .

This is true if

n_{j} ≥ N_{6} = \frac{3C_{1}}{2l log(λ)} .

The lemma follows, with N_{5} and N_{6} as the lower bounds for n_{j}. □

Here is a summary of what we have shown. We constructed [γ_{1}]_{1} and [γ_{2}]_{1}, and found that the point E_{1} on [γ_{1}]_{1} lies outside a C(N)-neighborhood of all of γ_{2}, provided that

N ≥ max {N_{1}, N_{2}, N_{4}}

from Lemma 4.2.

We construct the paths [γ_{1}]_{j} and [γ_{2}]_{j} (with endpoints E_{j} and F_{j} respectively) by iteration on j, adjoining words from the monoid ⟨l_{1}, l_{2}⟩ to the endpoints of [γ_{i}]_{j} to obtain [γ_{i}]_{j+1}. These paths have the property that

d_{S}(E_{j+1}, F_{j+1}) ≤ \frac{2}{3}d_{S}(E_{j}, F_{j})

provided

n_{j} ≥ N_{7} = max {N_{3}, N_{5}, N_{6}}

from the construction in step 2.

Now, n_{1} = \frac{N}{2} (provided N ≥ N_{4}) and so we must have

N ≥ 2N_{7}

to start the convergence iteration. We continue the iteration until, for some 2 < r ∈ ℕ, we have n_{r} < N_{7}. But then

d_{S}(E_{r}, F_{r}) ≤ 2 log [\frac{3x}{2}β_{r}] + 2 log [\frac{3y}{2} D_{r}]

< 2 log [\frac{3x}{2}(λ^{2l} + 2)] + 2 log [\frac{3y}{2} λ^{l(2n_{r}+2θ_{r})}]

< 2 log [\frac{3x}{2}(λ^{2l} + 2)] + 2 log [\frac{3y}{2} λ^{2l(N_{7}+1)}]

= H

and we just choose N large enough such that

H < α_{1}C(N) − α_{2}.

Since C(N) = \frac{Nl}{2} log(λ) we see that

N ≥ \frac{2(H + α_{2})}{α_{1}l log(λ)}

works. Let γ_{i} = [γ_{i}]_{r} and C = C(N) where

N ≫ max \{N_{1}, N_{2}, N_{4}, 2N_{7}, \frac{2(H + α_{2})}{α_{1}l log(λ)}\} .

Then γ_{1} is not contained in a C-Hausdorff neighborhood of γ_{2} in Sol, yet

d_{S}(\overline{γ_{1}}, \overline{γ_{2}}) ≤ α_{1}C − α_{2}

as in equation (4.1). This gives the required contradiction in the case where l_{1} = t^{l}.

Remarks 4.4. In the general case l_{1} = t^{l}w where w ∈ ⟨a, b⟩ is not the identity. Suppose that w maps to the point (x_{1}, y_{1}, 0) in Sol. Then \frac{y_{1}}{x_{1}} will be irrational, so that x_{1} and y_{1} are nonzero. Now, for n ∈ ℕ we have

(4.5)  (t^{l}w)^{n} = t^{ln} (t^{−l(n−1)}wt^{l(n−1)}) … (t^{−l}wt^{l}) w

= t^{ln} ([\frac{λ^{ln} − 1}{λ^{l} − 1}] x_{1} , [\frac{λ^{−ln} − 1}{λ^{−l} − 1}] y_{1} , 0)

Suppose that g_{1}, g_{2} ∈ G lie on some k-level, and that the points g_{i}t^{ln} project (via left multiplication by t^{−(k+ln)}) to points P_{i} in the xy-plane. Right multiplying g_{i} by (t^{l}w)^{n} and projecting to the xy-plane has the effect of adding the vector

([\frac{λ^{ln} − 1}{λ^{l} − 1}] x_{1} , [\frac{λ^{−ln} − 1}{λ^{−l} − 1}] , 0)

to P_{i}. In particular, the difference vector will be unchanged. Thus, replacing t^{l} by t^{l}w has no effect on the estimates in the convergence construction above.

Equation (4.5) also shows that w has only a bounded effect on the divergence estimates in Lemma 4.2. Since λ^{−l} < 1 the terms

[\frac{λ^{−ln} − 1}{λ^{−l} − 1}]

are just the partial sums of a convergent geometric series, and so are bounded by

\frac{λ^{l}}{λ^{l} − 1} .

For example, suppose we want to estimate the distance from the point v(t^{l}w)^{n} to the xzplane, where \frac{N}{2} ≤ n ≤ \frac{3N}{2} . Since left multiplication by t^{−ln} is an isometry which preserves the xz-plane we have

dist_{S}(v(t^{l}w)^{n} , xz-plane)

= dist_{S} ( (λ^{ln}x + [\frac{λ^{ln} − 1}{λ^{l} − 1}] x_{1} , λ^{−ln}y + [\frac{λ^{−ln} − 1}{λ^{−l} − 1}] y_{1} , 0) , xz-plane)

= log [\sqrt{1 + (\frac{Y}{2} )^{2}} + \frac{Y}{2} ]

where Y = yλ^{−ln} + [\frac{λ^{−ln}−1}{λ^{−l}−1}] |y_{1}|. As n ≥ \frac{N}{2} this will be bounded for large N. This bound will replace the log(2) bound of Lemma 4.2. We can make similar modifications to the lower bound for the distance from the endpoint of [γ_{1}]_{1} to the xz-plane. This gives the final contradiction in case I.

§5. Proof of Theorem 1: Case II

Let us recall the working assumption in case II: there is at most one type of loop at each live and accessible state of Δ. As in section 3, we view G as a subgroup of Sol and L-words as paths in Sol. We shall obtain a contradiction by exhibiting a word w ∈ L and R > 0 such that the neighborhood property (3.3) holds

B_{R}(\overline{w}) ∩ G ⊄ \overline{L} .

Here B_{R}(\overline{w}) is the radius R ball about \overline{w} in Sol. The following properties of L-words will be important.

(1) If w, w_{1} ∈ L are such that

d_{S}(\overline{w}, \overline{w_{1}}) ≤ R

then w_{1} and w lie in K_{1}R-Hausdorff neighborhoods of each other, where

K_{1} = \frac{ϵ_{2}K}{ϵ_{1}} .

(2) If a and b are points on the L-word w, then the subsegment [a, b] of w with endpoints

a and b satisfies

[a, b] ⊂ B_{δ_{1}+K_{1}d_{S}(a,b)}(a)

where

δ_{1} = \frac{(2K + 1)q}{ϵ_{1}} .

Note that property 1 is just the standard consequence of the asynchronous K-fellow traveler property of L, which has been translated into Sol using estimate (2.1). Similarly, property 2 is the Sol version of Lemma 1.2 on bounded backtracking of L-words.

Given a maximal stem in Δ one can add r loops to this stem, obtaining a standard maximal track T as in definition 3.6. Then every L-word that has T as its track will be of the form

(5.1)  w = u_{1}l_{1}^{n_{1}} … u_{r}l_{r}^{n_{r}}u_{r+1}

where n_{i} ≥ 1 for all 1 ≤ i ≤ r, and the sum of the lengths of the u_{i} is less than q. We say that w is obtained from T by pumping each loop at least M times if n_{i} ≥ M for all 1 ≤ i ≤ r. The next lemma gives conditions which ensure that only maximal L-words can track standard maximal words.

Lemma 5.1. Let T be a standard maximal L-track. Then, given any R > 0, there exists an integer M ≥ 1 such that if we pump each loop of T at least M times we obtain L-words w with the following property. If w_{1} ∈ L is such that

d_{S}(\overline{w}, \overline{w_{1}}) ≤ R

then w_{1} is a maximal L-word.

Proof. The word w is of the form described in equation (5.1) where n_{i} ≥ M for all 1 ≤ i ≤ r. Thus, for M ≫ q, the path w in Sol looks like the concatenation of r directed segments (the l_{i}^{n_{i}}), each of which either lies in some k-level or is ‘transverse’ to the k-levels, pointing ‘upwards’ or ‘downwards’ in Sol. These segments are connected together by ‘hinges’ (the u_{i}) of length strictly less than q, as shown in figure 5. Strictly speaking the segments l_{i} with zero t-exponent sum do not have to lie in a k-level. However, we are only looking at r words l_{i}, and each of these lies within \frac{length(l_{i})}{2} of their endpoints. Thus, the segments l_{i}^{n_{i}} lie within a bounded neighborhood of the corresponding segments where we write the l_{i} in standard form

t^{∗}a^{∗}b^{∗}.

So me may assume that the l_{i} are in standard form. For each ≤ i ≤ r, the path w can be viewed as consisting of three subsegments:

w_{i,0} = u_{1}l_{1}^{n_{1}} … u_{i}

and

l_{i}^{n_{i}}

and

w_{i,1} = u_{i+1}l_{i+1}^{n_{i+1}} … u_{r+1} .

Denote the endpoints of l_{i}^{n_{i}} by

P_{i} = \overline{w_{i,0}}

and

Q_{i} = \overline{w_{i,0}}\overline{l_{i}}^{n_{i}} .

Now, if w_{1} ∈ L is such that d_{s}(\overline{w}, \overline{w_{1}}) ≤ R, property 1 implies that w_{1} lies in a K_{1}R-Hausdorff neighborhood of w. The first claim shows that w_{1} cannot take any shortcuts in the K_{1}R-neighborhood of w.

Claim 1: Let w, w_{i,0}, and w_{i,1} be as described above. If M is large (precise lower bounds M_{1} and M_{2} given in the proof) then for each 1 ≤ i ≤ r the K_{1}R-neighborhoods of w_{i,0} and w_{i,1} are disjoint.

Proof of claim 1. Suppose the neighborhoods have nonempty intersection. Then there are points x in Sol, a on w_{i,0} and b on w_{i,1} such that

d_{S}(a, x) ≤ K_{1}R and d_{S}(b, x) ≤ K_{1}R.

Figure 5. The Hausdorff neighborhood of w.

Then d_{S}(a, b) ≤ 2K_{1}R and property 2 implies that

[a, b] ⊂ B_{2K_{1}^{2}R+δ_{1}}(a)

where [a, b] denotes the subsegment of w with endpoints a and b. Now l_{i}^{n_{i}} is a subsegment of [a, b] so the distance between its endpoints is bounded by

2δ_{1} + 4K_{1}^{2}R .

This gives a contradiction for large values of M. Here are the precise bounds. If l_{i} has nonzero t-exponent sum then

d_{S}(P_{i}, Q_{i}) ≥ n_{i} log(λ) ≥ M log(λ)

giving a contradiction if

M > M_{1} = \frac{2δ_{1} + 4K_{1}^{2}R}{log(λ)} .

If l_{i} has zero t-exponent sum then

\overline{l_{i}} = (x_{i}, y_{i}.0) .

Let

d = min_{j}{|x_{j}| , |y_{j}|}

where j runs over the elements of \{i, …, r\} for which \overline{l_{j}} = (x_{j}, y_{j}, 0). Then

d_{S}(P_{i}, Q_{i}) = d_{S}( (0, 0, 0) , (n_{i}x_{i}, n_{i}y_{i}, 0) )
≥ d_{S}( (0, 0, 0) , (Md, Md, 0) )
≥ 2 log |Md|

by Lemma 2.2. This gives a contradiction if

M > M_{2} = \frac{1}{d}e^{2δ_{1}+4K_{1}^{2}R}

thus establishing claim 1. □

Now w_{1} is a connected subset of the K_{1}R-neighborhood of w, with endpoints in the K_{1}R-neighborhoods of w_{i,0} and w_{i,1}. Thus for each 1 ≤ i ≤ r there is at least one point c_{i} which lies in the K_{1}R-neighborhood of l_{i}^{n_{i}}, but not in the K_{1}R-neighborhoods of w_{i,0} and w_{i,1}. The next claim states that w_{1} tracks the segments l_{i}^{n_{i}} almost up to their endpoints.

Claim 2: Let M be as in claim 1. Then for 1 ≤ i ≤ r there exist points a_{i}, b_{i} ∈ w_{1} such that the subsegments [a_{i}, b_{i}] of w_{1} satisfy the following properties.

(1) [a_{i}, b_{i}] is contained in the K_{1}R-Hausdorff neighborhood of l_{i}^{n_{i}}.

(2) d_{S}(a_{i}, P_{i}) ≤ N(R).

(3) d_{S}(b_{i}, Q_{i}) ≤ N(R). where N(R) = 2K_{1}^{2}R + K_{1}R + δ_{1}.

Proof of claim 2. For each 1 ≤ i ≤ r there exists c_{i} ∈ w_{1} which lies in the K_{1}Rneighborhood of l_{i}^{n_{i}} but not in the K_{1}R-neighborhoods of w_{i,0} and w_{i,1}. Starting at c_{i} proceed along w_{1} towards \overline{w_{1}} until we reach a point b_{i} which also lies in the K_{1}Rneighborhood of w_{i,1}. Since b_{i} lies within K_{1}R of a point on l_{i}^{n_{i}} and a point on w_{i,1} these points are within 2K_{1}R of each other. Property 2 implies that the subsegment of w they define is contained in a 2K_{1}^{2}R + δ_{1} radius ball about one of the points, and therefore is contained in a 2K_{1}^{2}R + K_{1}R + δ_{1} ball about b_{i}. Thus

d_{S}(b_{i}, Q_{i}) ≤ N(R) = 2K_{1}^{2}R + K_{1}R + δ_{1} .

Similarly, we can proceed back along w_{1} towards the identity until we reach a point a_{i} which also lies in the K_{1}R-neighborhood of w_{i,0}. As above we have

d_{S}(a_{i}, P_{i}) ≤ N(R) .

One may assume that a_{i} and b_{i} are vertices of the edgepath w_{1} replacing N(R) by N(R)+ \frac{1}{ϵ_{1}} if necessary. We will also extend the last segment so that b_{r} = \overline{w_{1}}. This completes the proof of claim 2. □

We continue with the proof of Lemma 5.1. There are two cases to consider. The first is when l_{i} has nonzero t-exponent sum. Then one endpoint of l_{i}^{n_{i}} is at least M levels above the other. Thus a_{i} is at least M − \frac{2N(R)}{log(λ)} levels above or below b_{i}. For

M ≫ \frac{2N(R)}{log(λ)} + q

these points are separated by more than q levels. Therefore the subsegment [a_{i}, b_{i}] will traverse a nonzero type loop in the L-track corresponding to w_{1} in Δ. Denote this track by T_{1}.

In the second case l_{i} has zero t-exponent sum. Now l_{i} must stay in some level, and the subsegment [a_{i}, b_{i}] of w_{1} cannot move more than K_{1}R above or below this level. It is possible for [a_{i}, b_{i}] to remain inside the K_{1}R neighborhood of l_{i}^{n_{i}} using alternating sequences of positive and negative t-exponent sum words. However, if M is large enough, this will contradict the fact that w is a maximal word. Here are the details.

A simple loop in Δ is a loop (as defined in section 2) which does not cross itself. Since Δ is finite, there are only finitely many simple loops. Thus there exists an integer N_{0} > 0 such that the length of each simple loop of nonzero type is bounded by N_{0} times the absolute value of the t-exponent sum of the loop. Now Case II hypothesis implies that any loop in Δ will be a combination of simple loops of the same type. Thus for every nonzero type loop l we have

length(l) ≤ N_{0}|t-exponent sum of l| .

Suppose that [a_{i}, b_{i}] does not traverse a zero type loop in T_{1}. If a subsegment of [a_{i}, b_{i}] traverses a positive loop its endpoints will be at least one level apart. Thus [a_{i}, b_{i}] can traverse at most \frac{2K_{1}R}{log(λ)} + q positive loops before it has to ‘change’ to a negative loop. See figure 6. Therefore the lengths (in Γ_{A}(G)) of the subsegments of [a_{i}, b_{i}] between loop changes are bounded by

N_{0} (\frac{2K_{1}R}{log(λ)} + q) + q

and estimate (2.3) implies that the Sol lengths are bounded by

B = \frac{N_{0}}{ϵ_{1}} (\frac{2K_{1}R}{log(λ)} + q) + \frac{q}{ϵ_{1}} .

Now we can choose M large enough such that

d_{S}(a_{i}, b_{i}) ≥ 2 log(Md) − 2N(R)
≫ 3B .

Figure 6. The K_{1}R-neighborhood of l_{i}^{n_{i}}.

and so T_{1} will have more changes than T, contradicting the fact that T is a maximal track. Thus, [a_{i}, b_{i}] must traverse zero type loops in T_{1}. We have seen that w_{1} traverses positive, negative and zero type loops in Δ whenever w does, and so is a maximal L-word. This completes the proof of Lemma 5.1. □

Finally, Lemma 5.2 below shows that L does not map onto G. This gives a contradiction in Case II and finally proves Theorem 1.

Lemma 5.2. Given a standard maximal L-track T, there exists R > 0 and w ∈ L whose L-track is T such that

G ∩ B_{R}(\overline{w}) ⊄ \overline{L} .

Proof. The proof breaks into two cases, depending on the type of the last loop along T. In the first case this loop is of zero type, and reading it gives a word l_{r} where

\overline{l_{r}} = (x_{r}, y_{r}, 0) .

There are only finitely many simple loops of zero type in Δ. Each of these gives a word which maps to the xy-plane in Sol as a vector with irrational slope. Choose constants 0 < A < B such that the absolute values of these slopes are bounded between A and B. Note that there is at most one type of loop at each live and accessible state of Δ, and thus each such loop is simple. This is because two or more such loops would give rise to a sublanguage of L with exponential growth which maps into some coset of ⟨a, b⟩ in G. But ⟨a, b⟩ ≅ ℤ^{2} has polynomial growth, and so two or more words in this language would have to map to the same point in the coset, contradicting the fact that L is a language with uniqueness.

Choose R_{0} ∈ ℕ such that

R_{0} ≫ 2q + \frac{log_{λ} [\frac{B}{A} ]}{2}

and set

R = R_{0} log(λ) .

Given R as above we pump each loop of T at least M times (where M is given in Lemma 5.1) to obtain the word w. The last loop of T is pumped sufficiently large so that we get a contradiction as follows.

The point \overline{w}\overline{t}^{R_{0}} lies in the R ball about \overline{w}. By Lemma 5.1 if w_{1} ∈ L is such that

\overline{w_{1}} = \overline{w}\overline{t}^{R_{0}}

then w_{1} is also a maximal L-word. Furthermore, the subsegment [a_{r}, b_{r}] of w_{1} is of the form

… v_{s−1}^{m_{s−1}}v′_{s}v_{s}^{m_{s}}v′_{s+1}

where m_{i} ∈ ℕ, the v_{i} all have zero t-exponent sum, and the sum of the lengths of the v′_{i} is less than q. Actually, the beginning of [a_{r}, b_{r}] may be a path which traverses a nonzero loop in Δ, but it can only do this for a bounded amount.

Translate w and w_{1} by an isometry (left multiplication) so that the initial point P_{r} of the subsegment l_{r}^{n_{r}} becomes the origin. Then l_{r}^{n_{r}} is the vector (n_{r}x_{r}, n_{r}y_{r}, 0) in the xy-plane, which has slope less than or equal to B. The v_{i}^{m_{i}} lie somewhere between the (R_{0} −2q) and (R_{0} + 2q) levels. Right multiplication by appropriate powers of t gives points X_{i_{j}} on the xy-plane which are within (R_{0} + 2q) log(λ) of the vertex points of the subsegment v_{i}^{m_{i}} of w_{1}. Thus these points lie in a [K_{1}R + (R_{0} + 2q) log(λ)]-neighborhood of l_{r}^{n_{r}}. Lemma 2.2 implies that they lie in a bounded Euclidean neighborhood of l_{r}^{n_{r}}. We know from section 4 the effect of right multiplication on difference vectors. The points X_{i_{j}} will have difference vectors with slope greater than

λ^{2(R_{0}−2q)}A ≫ λ^{log}^{λ}^{(^{\frac{B}{A}})}A = B .

But l_{r}^{n_{r}} = (n_{r}x_{r}, n_{r}y_{r}, 0) has slope bounded above by B, and so we get a contradiction for n_{r} sufficiently large.

In the second case the last loop along T is of nonzero type. We suppose that it is a positive loop, and that its corresponding word l_{r} has t-exponent sum equal to m > 0. There are only finitely many simple positive loops in Δ. They are of the form t^{p_{j}}u′_{j} where p_{j} > 0 and

u′_{j} = (x_{j}, y_{j}, 0)

with j in some finite indexing set J. Let

Y = max_{j∈J} |y_{j}| .

The hypothesis of Case II implies that each positive loop at a live and accessible state of Δ must be a combination of the simple loops above.

We choose R = R(Y) sufficiently large (lower bound estimated below), and use Lemma 2.2 to obtain a corresponding M > 0. As in the first case, w ∈ L is chosen by pumping each loop of T at least M times, and pumping the last loop enough to obtain the contradiction below.

Figure 7. The image of L-paths in the yz-plane.

Pick a point on the line containing \overline{w} and parallel to the y-axis, which is a Sol distance approximately R from \overline{w}. Now choose g ∈ G ⊂ Sol which is nearest this point, so that

g ∈ G ∩ B_{R}(\overline{w}) .

Figure 7 shows the points \overline{w} and g projected onto the yz-plane by the map (x, y, z) ↦ (y, z). Translate the path w isometrically (by left multiplication) so that the initial point P_{r} of l_{r}^{n_{r}} is the origin. If w_{1} ∈ L is such that \overline{w_{1}} = g then Lemma 5.1 implies that w_{1} is a maximal L-word. Furthermore, its final section (all but a bounded amount of [a_{r}, b_{r}]) is of the form

… v_{s−1}^{m_{s−1}}v′_{s}v_{s}^{m_{s}}v′_{s+1}

where the v_{i} are now positive t-exponent sum words, and the sum of the lengths of the v′_{i} is less than q. Pick a point on the segment [a_{r}, b_{r}]; for example the initial point of the first of the v_{i}. It maps to a point (y_{0}, z_{0}) in the yz -plane.

Recall that l_{r} is a word with m > 0 t-exponent sum, and is a product of words of the form

t^{p_{j}}u′_{j}

described above. Therefore, the distance from the endpoint of \overline{l_{r}}^{n_{r}} to the xz-plane is bounded above by

dist_{S} ( [t(0, Y, 0)]^{mn_{r}} , xz-plane ) = dist_{S} ( (0 , \frac{λ^{−mn_{r}} − 1}{λ^{−1} − 1}Y , 0) , xz-plane )

≤ dist_{S} ( (0 , \frac{λY}{2(λ − 1)} , 0) , xz-plane )

for n_{r} large enough. By Lemma 2.3 the distance from \overline{w} to the xz-plane is bounded by

(5.2)  log [\sqrt{1 + (\frac{λY}{2(λ − 1)})^{2}} + \frac{λY}{2(λ − 1)}] + \frac{q}{ϵ_{1}} .

Now the point (y_{0}, z_{0}) lies on some k-level (where z_{0} = k log(λ)) and so

(0, y_{0}, z_{0}) = (0, y_{0}, 0)t^{k} .

Since the v_{j} are products of words of the form t^{p_{j}}u′_{j} as well, the distance from the endpoint of

… v_{s−1}^{m_{s−1}}v′_{s}v_{s}^{m_{s}}v′_{s+1}

to the xz-plane is bounded above by

dist_{S} ( (0, y_{0}, z_{0})[t(0, Y, 0)]^{mn_{r}−k} , xz-plane ) + \frac{q}{ϵ_{1}}

= dist_{S} ( (0 , λ^{−mn_{r}}y_{0} + \frac{λ^{−(mn_{r}−k)} − 1}{λ^{−1} − 1}Y , 0) , xz-plane ) + \frac{q}{ϵ_{1}}

≤ dist_{S} ( (0 , 1 + \frac{λY}{2(λ − 1)} , 0) , xz-plane ) + \frac{q}{ϵ_{1}}

for n_{r} large enough. Lemma 2.3 implies that the distance from this endpoint (which is \overline{w_{1}}) to the xz-plane is bounded by

(5.3)  log [\frac{3}{2} (1 + \frac{λY}{2(λ − 1)})] + \frac{q}{ϵ_{1}} .

Thus the distance between \overline{w} and \overline{w_{1}} is less than the sum of the bounds in thetag5.2 and thetag5.3. If R = R(Y) is chosen much larger than this sum to begin with (note that R(Y) is independent of M and n_{r}), then we would have d_{S}(\overline{w}, \overline{w_{1}}) = d_{S}(\overline{w}, g) is approximately R, a contradiction. This establishes Lemma 5.2 and so completes the proof of Theorem 1. □

§6. Remarks and questions

Since Sol is a subgroup of index eight in its full isometry group, a result of [NS] shows that Theorem 1 extends to include lattices in Isom(Sol).

Sol geometry groups also appear as subgroups of the Hilbert Modular groups, so the following is a natural question to ask.

Question 6.1. Are the Hilbert Modular groups asynchronously automatic?

Consider, for example, the group G = Sl_{2}(ℤ(\sqrt{2})). The Borel subgroup B < G (consisting of all upper triangular matrices) is a Sol group. We can see this as follows. The units in the ring ℤ(\sqrt{2}) form an infinite cyclic group generated by the element ϵ = \sqrt{2}+1. There is a corresponding infinite cyclic subgroup ℤ < B generated by the diagonal matrix with entries ϵ and ϵ^{−1} = \sqrt{2} − 1. The subgroup N < B, consisting of matrices with 1 along the diagonal and entries a + b\sqrt{2} (a, b ∈ ℤ) above the diagonal, is a normal subgroup which is isomorphic to ℤ^{2}. The group B is a semi direct product N ⋊ ℤ where ℤ acts on N by conjugation. Thus B is isomorphic to the Sol group ℤ^{2} ⋊_{ϕ} ℤ, where

ϕ = ( \begin{matrix}3 & 4 \\ 2 & 3 \end{matrix})

Unfortunately, knowing that a subgroup of a group G is not asynchronously automatic, does not necessarily tell us about the group itself. Perhaps some of the techniques used in the Sol case can be applied here too. The group G is an irreducible, (non-cocompact) lattice in Isom(ℍ^{2} × ℍ^{2}).

Thurston has asked if the cocompact irreducible lattices in Isom(ℍ^{2}×ℍ^{2}) are automatic. Ones attempts at Question 6.1 might yield insights into this intriguing question.

References

[AB] J. Alonso and M. Bridson, Semihyperbolic groups, Proc. London Math. Soc. 70 1 (1995), 56–114.

[BGSS] G. Baumslag, S.M. Gersten, M. Shapiro, and H. Short, Automatic groups and amalgams, Jour of Pure and Applied Algebra 76 (1991), 229–316.

[Bra] N. Brady, Asynchronous automatic structures on closed hyperbolic surface groups, Geometric Group Theory (R. Charney, M. Davis, M. Shapiro, eds.), de Gruyter, Berlin, New York, 1995, pp. 49–65.

[BBr] N. Brady and M. Bridson, On graphs of abelian groups and the absence of biautomaticity, Preprint (1999).

[Bri] M. Bridson, Combings of semidirect products and 3-manifold groups, Geom. Funct. Anal. 3 (1993), 263–278.

[BG] M. Bridson and R. Gilman, On bounded languages and the geometry of nilpotent groups, Combinatorial and geometric group theory – Edinburgh, London Math. Soc. Lecture Note Ser., vol. 204, Cambridge Univ. Press, 1995, pp. 1–15.

[C] J.W. Cannon, The combinatorial structure of cocompact discrete hyperbolic groups, geometricae Dedicata 16 (1984), 123–148.

[ECHLPT] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Patterson, W.P. Thurston, Word Processing in Groups, Jones and Bartlett Publ. (1992).

[G] M. Grayson, Geometry and growth in 3-dimensions, PhD Thesis. Princeton University (1983).

[NS] W. Neumann and M. Shapiro, Equivalent automatic structures and their boundaries, International Journal of Algebra and Computation 2 (1992), 443–469.

[Sc] P. Scott, The geometries of 3-manifolds, Bull. London Math. Soc. 15 (1983), 401–487.

Department of Mathematics, University of Oklahoma, Norman, OK 73019