Regularity of quasigeodesics in a hyperbolic group

Derek F. Holt and Sarah Rees Mathematics Institute, University of Warwick, Coventry CV4 7AL, UK. dfh@maths.warwick.ac.uk Department of Mathematics, University of Newcastle, Newcastle NE1 7RU, UK. Sarah.Rees@ncl.ac.uk

18th September 2000

Abstract

We prove that for λ ≥ 1 and all sufficiently large ϵ, the set of (λ, ϵ)-quasigeodesics in an infinite word-hyperbolic group G is regular if and only if λ is rational. In fact, this set of quasigeodesics defines an asynchronous automatic structure for G. We also introduce the idea of an exact (λ, ϵ)-quasigeodesic and show that for rational λ and appropriate ϵ the sets of exact (λ, ϵ)-quasigeodesics define synchronous automatic structures.

1 Introduction

It is proved in [3] that all synchronous automatic structures on a wordhyperbolic group are equivalent. This means roughly that, given two such structures, accepted words from each which represent the same group element asynchronously fellow travel with each other. The equivalence follows from the fact that, for any such structure, the accepted words consist of (λ, ϵ)-quasigeodesics for some fixed λ ≥ 1 and ϵ ≥ 0. In this paper, we show that there is a wealth of such structures.

Our main result is that for any infinite word-hyperbolic group G with finite generating set X, and any rational λ ≥ 1 and ϵ ≥ 0, the set of all (λ, ϵ)- quasigeodesics in the Cayley graph Γ_{X}(G) forms a regular set, but for irrational λ and ϵ > 2λ the set is never regular. (We impose this restriction on ϵ since for smaller values of ϵ it is possible that the set of (λ, ϵ)-quasigeodesics might consist only of geodesics and (λ′, ϵ′)-quasigeodesics for some fixed λ′ < λ.) We show also that if λ and λ′ are distinct and rational, then the sets of (λ, ϵ)-quasigeodesics and (λ′, ϵ′)-quasigeodesics are distinct, at least for all sufficiently large ϵ and ϵ′. It follows that, for all distinct rational λ, we get distinct families of automatic structures for G. These are asynchronous if we accept all (λ, ϵ)-quasigeodesics, but by a further suitable restriction of the set of accepted words, we get distinct families of synchronous automatic structures.

2 Definitions and notation

Let G be a group with specified finite generating set X, which we shall assume to be closed under the taking of inverses. We define the Cayley graph Γ = Γ_{X}(G) of G with respect to X to be the directed graph with vertices corresponding to the elements of G and with |X| directed edges with source the vertex g, for each g ∈ G, of which an edge labelled x joins g to the vertex gx (while its reverse, joining gx to g, is labelled x^{−1}). We denote by d_{Γ} the graph metric on Γ, and use the same notation to denote a continuous extension of that metric to the 1-skeleton of Γ (which we shall also denote by Γ).

We define a geodesic in Γ to be a path of minimal length between its two ends. For λ ≥ 1 and ϵ > 0, we define a (λ, ϵ)-quasigeodesic to be a path γ with the property that for any two points x, y on γ, the distance between x and y along γ, which we denote by d_{γ}(x, y), satisfies the inequality

d_{γ}(x, y) ≤ λd_{Γ}(x, y) + ϵ.

We say that γ is an exact (λ, ϵ)-quasigeodesic if, in addition to this property, we have

d_{γ}(x, y) ≥ λd_{Γ}(x, y) − ϵ

for all points x, y on γ. (The definition of (λ, ϵ)-quasigeodesic is standard, but that of exact (λ, ϵ)-quasigeodesic is our own.)

Any word w over X corresponds naturally to a path in Γ, which it labels, and which starts at the vertex corresponding to the identity element of G. We say that a word w over X is a geodesic in G if it labels a geodesic path in Γ and a (λ, ϵ)-quasigeodesic in G if it labels a (λ, ϵ)-quasigeodesic path in Γ.

Let γ be a path labelled by a word in X. Then γ consists of a sequence of unit-length subpaths joining the adjacent vertices on γ. Since these subpaths are themselves necessarily geodesic, it is not hard to see that to test whether γ is a (λ, ϵ)-quasigeodesic it is sufficent to check that d_{γ}(x, y) ≤ λd_{Γ}(x, y)+ϵ for all graph vertices x, y on γ. However, if, in addition, we check that d_{γ}(x, y) ≥ λd_{Γ}(x, y)−ϵ only for vertices x, y on γ, then we can only conclude, for arbitrary points x, y on γ, that d_{γ}(x, y) ≥ λd_{Γ}(x, y) − ϵ − 2. We shall avoid this technicality by calling a word w an exact (λ, ϵ)-quasigeodesic if the condition d_{γ}(x, y) ≥ λd_{Γ}(x, y) − ϵ holds just for graph vertices x, y on γ.

Let γ, δ be two paths in Γ, each parameterised by arc-length, and of lengths L_{γ} and L_{δ}. For convenience, define γ(s) to be γ(L_{γ}) when s > L_{γ} and δ(s) to be δ(L_{δ}) when s > L_{δ}. We say that γ and δ synchronously K-fellow travel if for all s ≥ 0, d_{Γ}(γ(s), δ(s)) ≤ K. We say that γ and δ asynchronously K-fellow travel if we can define increasing (but not necessarily strictly increasing) surjective functions f_{1} : [0, 1] → [0, L_{γ}] and f_{2} : [0, 1] → [0, L_{δ}] such that d_{Γ}(γ(f_{1}(s)), δ(f_{2}(s)) ≤ K for all s ∈ [0, 1]. We say that γ,δ boundedly asynchronously K-fellow travel with bound M if we can find functions f_{1}, f_{2} as above with the additional property that |f_{2}(s) − f_{2}(s′)| ≤ M whenever |f_{1}(s) − f_{1}(s′)| ≤ 1, and |f_{1}(s) − f_{1}(s′)| ≤ M whenever |f_{2}(s) − f_{2}(s′)| ≤ 1. For words w, v over X, we say that w, v fellow travel (in one of the ways defined above) if the same is true of the corresponding paths in the Cayley graph. Some authors use slightly different (but equivalent) discrete definitions of asynchronous fellow travelling.

Let x_{0} be a symbol not in X, and let X̂ = X ∪ {x_{0}}. Define x_{0} to represent the identity element of G, and let Γ̂ be the Cayley graph of G over the generating set X̂; this is formed from Γ by adding a loop labelled x_{0} at each vertex of Γ. For any word v over X we say that a word v′ over X̂ is a padded version of v if it is formed from v by adding some symbols x_{0} between symbols of v or at either end of v. It is clear that if two words v and w asynchronously K-fellow travel over X then padded versions v′ and w′ of the two words, of equal length, can be constructed which synchronously (K + 1/2)-fellow travel over X̂, that is, as paths in Γ̂. Conversely if some such padded versions of two words v, w synchronously k-fellow travel, then certainly v and w asynchronously k-fellow travel.

It is straightforward to construct a deterministic finite state automaton D with alphabet X̂^{2} which recognises pairs of words v′, w′ over X̂ of equal length which synchronously k-fellow travel in Γ̂. A pair of words (v′, w′) for which v′ = y_{1}y_{2} … y_{m} and w′ = z_{1}z_{2} … z_{m} is read into D as a sequence (y_{1}, z_{1})(y_{2}, z_{2}) … (y_{m}, z_{m}) over X̂^{2}. Where d is an accept state of D, we denote by d^{(y,z)} the target of d under (y, z), for any y, z ∈ X̂, and similarly by d^{(v′,w′)} the target of a pair of words (v′, w′). The set S of accept states of D is the set of elements of G at distance at most k from the origin, and the start state is the identity of G. There is also a unique failure state, from which there are no transitions. Suppose that d is an accept state of D, and that y, z are elements of X̂^{2}. Then we define the target d^{(y,z)} of d under (y, z) to be the element y^{−1}dz of G if this element is in S, and to be the failure state of D otherwise. This procedure is well known, and is described, for example, in Definition 2.3.3 of [2]. The accept states of D are known as word-differences, because they keep track of the difference v′(t)^{−1}w′(t) between the prefixes of the two words that have been read so far.

Using D, and given M, we can easily construct a deterministic finite state automaton D_{M} which recognises pairs of synchronously k-fellow travelling words of equal length over X̂ which contain at most M consecutive symbols x_{0}. A word-difference is associated with each state of D_{M} (but different states might be associated with the same word-difference). We denote by f(d) the word-difference associated with the state d of D_{M}.

We can also use D_{M} to decide whether or not two words v, w over X boundedly asynchronously K-fellow travel in Γ with bound M. We simply construct all appropriate pairs of padded words v′, w′ of equal length and feed them as input to D_{M}. Where d is a state of D_{M}, and v, w are words over X, we denote by d^{∗(v,w)} the set of all states of D_{M} of the form d^{(v′,w′)}, where v′ and w′ are padded versions of v and w. Of course there are normally many padded pairs (v′, w′) associated with an unpadded pair of words (v, w). Used in this way, D_{M} recognises that a pair of words (v, w) boundedly asynchronously fellow travels (with parameters K, M) if the image d_{0}^{∗(v,w)} of the start state of D_{M} contains an accept state of D_{M}.

For a word w over X, l_{G}(w) will denote the length of the shortest word over X that represents the same element of G as w. The group G is called automatic if there is a finite state automaton W with alphabet X such that the language L(W) of W maps surjectively onto G, and such that any two words v, w over X with l_{G}(v^{−1}w) ≤ 1 synchronously K-fellow travel for some constant K. Similarly, G is called asynchronously automatic if the above conditions hold but with the words v, w asynchronously K-fellow travelling. L(W) is called a (synchronous or asynchronous) automatic structure for G. It is proved in Theorem 3.4.5 of [2] that if G is word-hyperbolic, then there is a synchronous automatic structure with L(W) equal to the set of all geodesic words. There is also such a structure in which L(W) contains just the shortlex least among the geodesic words representing each group element.

3 The main results

We shall assume throughout this section that G is an infinite word-hyperbolic group with a fixed inverse-closed generating set X, and that Γ = Γ_{X}(G) is its Cayley graph.

The following result is well-known, but we could not find a proof of it in the literature, so we include one here.

Proposition 3.1 Let λ ≥ 1 and ϵ ≥ 0. Then there exist constants K, M with the following property. Let u and v be words over X that represent the same group element, where u is a geodesic and v is a (λ, ϵ)-quasigeodesic. Then u and v boundedly asynchronously K-fellow travel with asynchronicity bound M.

Proof: Let d_{Γ} denote the metric of the Cayley graph Γ, extended continuously to its 1-skeleton. Words u and v may be viewed either as discrete paths in the Cayley graph itself, parameterised according to arc length by integers, or as continuous paths, again parameterised by arc length. Let d_{u} and d_{v} measure distance along the (continuous) paths u and v. Let L_{u}, L_{v} be the lengths of u and v.

By Proposition 3.3 of [1], there exists a constant k such that the discrete path v is in a k-Hausdorff neighbourhood of the discrete path u. Hence we can define a function g, mapping [0, L_{v}] ∩ ℤ to [0, L_{u}] ∩ ℤ, with g(0) = 0, g(L_{v}) = L_{u}, and with the property that

d_{Γ}(v(i), u(g(i)) ≤ k

for all i in [0, L_{v}] ∩ ℤ. To prove that v and u asynchronously fellow travel we shall construct an increasing function g_{2} : [0, L_{v}] → [0, L_{u}] satisfying an analogous condition. Having done that, we define f_{1} : [0, 1] → [0, L_{v}] by the rule f_{1}(x) = L_{v}x and then f_{2} : [0, 1] → [0, L_{u}] as the composite function g_{2} ∘ f_{1}.

Now, for some integer i, let v(i), v(i + 1) be adjacent vertices of v. Then the vertices u(g(i)) and u(g(i + 1)) are joined by a segment of length |g(i + 1) − g(i)| of the geodesic u, and are joined by a path of length at most 2k + 1 through v(i) and v(i + 1). Hence

|g(i + 1) − g(i)| ≤ 2k + 1.

Hence the continuous function g_{1} : [0, L_{v}] → [0, L_{u}], which is defined to take the same value as g at integer points and by the rule

g_{1}(s) = g(i) + (s − i)(g(i + 1) − g(i))

for s in (i, i + 1) (and i ∈ ℤ), satisfies

d_{Γ}(v(s), u(g_{1}(s)) ≤ 2k + 1 = k_{1}

for all s ∈ [0, L_{v}].

Now suppose that s, s′ ∈ [0, L_{v}] satisfy g_{1}(s) = g_{1}(s′). Then v(s) and v(s′) are joined by a path via u(g_{1}(s)) of length at most 2k_{1}, and along v by a path of length |s′ − s|. Hence, since v is a (λ, ϵ)-quasigeodesic,

|s′ − s| ≤ 2k_{1}λ + ϵ

Now we define an increasing function g_{2} : [0, L_{v}] → [0, L_{u}] by the rule

g_{2}(s) = max_{s′≤s}g_{1}(s′)

Then whenever g_{1}(s) ≠ g_{2}(s) we can find s_{1} < s with g_{2}(s) = g_{1}(s_{1}) > g_{1}(s), and (since g_{1} is continuous and takes its maximum value at L_{v}) we can find s_{2} > s with g_{1}(s_{2}) = g_{1}(s_{1}). By the above, |s_{2} − s_{1}| ≤ 2k_{1}λ + ϵ. Now

d_{Γ}(v(s), u(g_{2}(s)) ≤ d_{Γ}(v(s), v(s_{i})) + d_{Γ}(v(s_{i}), u(g_{1}(s_{i}))

for each of i = 1, 2. Hence

d_{Γ}(v(s), u(g_{2}(s))) ≤ \frac{1}{2}(2k_{1}λ + ϵ) + k_{1} = k_{1}(λ + 1) + \frac{ϵ}{2}.

The existence of the increasing function g_{2} proves that the continuous paths v and u asynchronously fellow travel, at distance K = k_{1}(λ + 1) + ϵ/2.

We verify bounded asynchronicity by noting the following:-

(a) If g_{2}(s′) = g_{2}(s) + 1, then since there is a path from v(s) to v(s′) via u(g_{2}(s′)) and u(g_{2}(s)) of length at most 2K + 1 it follows that s′ − s, the distance between the points along v, is at most (2K + 1)λ + ϵ.

(b) If s′ = s + 1, then since there is a path from u(s) to u(s′) via v(s) and v(s′) of length at most 2K + 1 it follows that g_{2}(s′) − g_{2}(s), the geodesic distance between the two points, is at most 2K + 1.

□

Proposition 3.2 Let λ ≥ 1 and ϵ ≥ 0. Then there exists a constant K with the following property. Let v and v′ be words over X with l_{G}(v^{−1}v′) ≤ 1, where v and v′ are both exact (λ, ϵ)-quasigeodesics. Then v and v′ synchronously K-fellow travel.

Proof: Let u and u′ be geodesic words equal in G to v and v′, respectively. From the fact that the geodesic words define an automatic structure for G, we know that u and u′ synchronously K′-fellow travel for some constant K′. We shall prove that for some constant K′′ the words u and v asynchronously K′′-fellow travel, using the functions f_{1} : [0, 1] → [0, L_{u}] and f_{2} : [0, 1] → [0, L_{v}], defined by f_{1}(x) = L_{u}x and f_{2}(x) = L_{v}x, and similarly for u′ and v′. Since v and v′ are exact (λ, ϵ)-quasigeodesics with l_{G}(v^{−1}v′) ≤ 1, their lengths differ by at most 2ϵ + λ, and it will then follow that v and v′ synchronously K-fellow travel with K = K′ + 2K′′ + 2ϵ + λ.

Let x be a point on the path v and let d_{v}(1, x) = λt. (This is the distance along the path v from the beginning of the path to x.) Let y be the point on the path u at distance t from the identity (or, if l(u) < t, let y be the end point of u.) We need to bound the distance d_{Γ}(x, y). By Proposition 3.3 of [1] we know that, for some constant k, the path u lies within a k-Hausdorff neighbourhood of v, and so there is a point y′ on u with d_{Γ}(x, y′) ≤ k. Also, since v is an exact (λ, ϵ)-quasigeodesic, we have |d_{Γ}(1, x) − t| ≤ ϵ/λ ≤ ϵ. Then using the triangle inequality twice and the fact that u is a geodesic, we have

t − ϵ − k ≤ d_{u}(1, y′) ≤ t + ϵ + k

and hence d_{Γ}(x, y) ≤ 2k + ϵ, which proves the result. □

Lemma 3.3 Suppose that w is a word asynchronously K-fellow travelling with a geodesic word u between its end points a, b ∈ Γ, and suppose that every proper subword of w is a (λ, ϵ)-quasigeodesic but that w itself is not. Let c ≠ a, b be a vertex of Γ on w, at distance l along w from a, and let d be a point on u within distance K of c. Suppose that d is at geodesic distance r from a. Then

−3λK < l − λr ≤ ϵ + λK.

Proof: Suppose that u has length n and that w has length l + m. Let s be the geodesic distance of c from a, and let t be the geodesic distance of c from b. Note that d is at distance n − r from b along u.

We verify first that

−2λK < l − λs ≤ ϵ. (∗)

The inequalities we want follow immediately from this together with the two triangle inequalities

r ≤ s + K, s ≤ r + K.

The right hand inequality in (∗) follows immediately from the fact that the portion of w between a and c is a (λ, ϵ)-quasigeodesic.

To deduce the left hand inequality of (∗), we observe first that, since s, t are the lengths of geodesics, s ≤ r +K, t ≤ n−r +K, and hence s+t ≤ n+2K. From this it follows that

l − λs ≥ l + λt − λn − 2λK.

From the fact that w is not a (λ, ϵ)-quasigeodesic we deduce that λn + ϵ < l + m, while the fact that the portion of w between c and b is a (λ, ϵ)- quasigeodesic implies that m ≤ λt + ϵ. Combining these last three inequalities gives the required result. □

Theorem 3.4 If λ ≥ 1 is rational and ϵ ≥ 0, then the set of (λ, ϵ)- quasigeodesic words over X is regular and the set of exact (λ, ϵ)-quasigeodesic words over X is regular.

Proof: Let W be the finite state automaton which recognises the set of all shortlex minimal geodesic words, and let D_{M} be the finite state automaton described in Section 2, which we use to recognise pairs of words which K-asynchronously fellow travel with bound M (where K, M are given by Proposition 3.1). Let s_{0} be the start state of W, and d_{0} the start state of D_{M}. Let f be the map from the set of states of D_{M} to the corresponding set of word-differences.

Let v be a word of length l, and u a word of length r. Let s = s_{0}^{u} be the target state of u in W, and d one of the states in the finite set d_{0}^{∗(v,u)}, as defined in Section 2. Let e take the value l − λr if this is within the range (−3λK, ϵ + λK], and otherwise let e take the value E if l − λr > ϵ + λK or −E if l − λr ≤ −3λK, where E is a fixed positive number bigger than both ϵ + λK and 3λK. Then we say that the triple (s, d, e) is a triple based at v. Note that, since λ is rational, there are only finitely many possible such triples, and any one of these may be based at several words v. If T is a set of triples all of which are based at v, then we say that T is based at v.

We say that a triple (s, d, e) is live provided that s is an accept state of W and d an accept state of D_{M}; there exists a live triple based at v precisely when there exists a shortlex geodesic u which asynchronously fellow travels with v according to the bounds K, M. We say that (s, d, e) is bounded if e is in (−3λK, ϵ + λK], and otherwise that it is unbounded. Note that, by Proposition 3.1, if v is a (λ, ϵ)-quasigeodesic then there are live triples (s, d, e) based at v for which f(d) represents the identity.

We recognise the set of (λ, ϵ)-quasigeodesics with an automaton Q whose accept states are sets of sets of live triples, and with a single fail state from which there are no transitions. Note that there are only finitely many such sets altogether. The start state S_{0} of the automaton is equal to {T_{0}}, where T_{0} = {(s_{0}, d_{0}, 0)}. The accept state which is the target of a (λ, ϵ)- quasigeodesic w is a set of sets of triples, with one such set of triples based at each suffix v of w.

We need to define the target in Q of a state S under a generator g. We define this in terms of images of the sets T (of triples) which are elements of S. If t = (s, d, e) is a triple in T, then define the image of t under g to be the set of all live triples of the form (s^{u}, d′, e′), where d′ ∈ d^{∗(g,u)} for some word u (necessarily of length at most 2M + 1) and e′ is calculated as follows. If t is unbounded then e′ is set equal to e. Otherwise suppose that t is bounded. If e′′ = e + 1 − λ|u| is within the range (−3λK, ϵ + λK] then e′ is set equal to e′′, while if e′′ > ϵ + λK then e′ is set equal to E, and otherwise e′ is set equal to −E. Then we define T^{g} to be the union of all the targets under g of triples t in T. Now we define the target S^{g} of S under g either to be the accept state {T^{g} | T ∈ S} ∪ {T_{0}}, or to be the failure state. We define S^{g} to be the failure state precisely when either for some bounded triple t in some T in S one of the triples in t^{g} has the form (s′, d′, e′) where f(d′) represents the identity and e′ = E, or for some T in S there is no triple (s′, d′, e′) in T^{g} for which f(d′) represents the identity.

If, for some word w, S_{0}^{w} = S, then each set T in S is based at some suffix v of w. (Note that v is not necessarily unique. Indeed, since there are arbitrarily many suffices of w and only finitely many possible T, it will certainly not be unique in general.) In the first situation, where S^{g} is the failure state, vg fellow travels in the appropriate way with its shortlex geodesic representative, and every proper prefix of vg is a (λ, ϵ)-quasigeodesic, but vg itself is not a (λ, ϵ)-quasigeodesic. In the second situation, vg fails to fellow travel appropriately with its shortlex geodesic representative. In either case vg is recognised as not being a (λ, ϵ)-quasigeodesic, and it follows from Lemma 3.3 that any word that is not a (λ, ϵ)-quasigeodesic will fail in one or other of these two ways when input to Q. On the other hand, a word that is a (λ, ϵ)-quasigeodesic will not fail in either of these ways, and so the accepted language of Q is precisely the set of all (λ, ϵ)-quasigeodesics.

The proof of the regularity of the set of exact (λ, ϵ)-quasigeodesics is similar. We just have to check, in addition, that the difference between length and λ times geodesic length is bounded below by −ϵ for all subwords of the input word, and so our concept of bounded triple needs to be slightly more restrictive in this case. □

Since we know already that the set of geodesic words defines an automatic structure for G, it follows from Theorem 3.4 and Proposition 3.1 that for any rational λ ≥ 1 and any real ϵ ≥ 0 the set of (λ, ϵ)-quasigeodesics defines an automatic structure, but this structure will be synchronous only when λ = 1. We would like to use the exact (λ, ϵ)-quasigeodesics to get synchronous automatic structures, but first we need to show that there are enough of them to map onto G provided that ϵ is not too small.

Lemma 3.5 Let λ ≥ 1 be rational, and let g ∈ G. Then there exists an exact (λ, 2λ + 1)-quasigeodesic word v that maps onto g.

Proof: Let u be a geodesic word mapping onto g, and let s be the length of u. We can choose an integer t such that |2t − (λ − 1)s| ≤ 1. Then |λ − λ′| ≤ 1/s, where λ′ = 2t/s + 1.

Suppose that u = x_{i_{1}} … x_{i_{s}} when written as a word over X. We form an exact (λ, 2λ + 1)-quasigeodesic of length s + 2t and geodesic length s by inserting subwords which freely reduce to the trivial word between some of the symbols in u.

Define a sequence e_{0}, … e_{s} of integers as follows. Let e_{0} = 0, e_{s} = t, and for each i with 0 < i < s, define e_{i} to be the integer in the interval [ti/s − 1/2, ti/s + 1/2). Now define a sequence d_{1}, … d_{s} by the rule d_{i} = e_{i} − e_{i−1} for each i.

For each j we define v^{(j)} to be the word x_{i_{j}}(x_{i_{j}}^{−1}x_{i_{j}})^{d_{j}}; of course if d_{j} = 0 then v^{(j)} is simply x_{i_{j}}. Then we define v to be v^{(1)} … v^{(s)}; we call v^{(1)},…,v^{(s)} the pieces of v. The word v certainly has length s + 2t and geodesic length s (since it freely reduces to u). It remains to show that it is an exact (λ, 2λ + 1)-quasigeodesic.

A subword of v of the form v^{(j+1)} … v^{(k)} has geodesic length k−j and length (k − j) + 2(d_{j+1} + … + d_{k}). In general, a subword of v can be expressed as a product v′ = w_{1}v^{(j+1)} … v^{(k)}w_{2}, where w_{1} is a proper subword of v^{(j)} and w_{2} a proper subword of v^{(k+1)}. The word v′ has geodesic length either k − j, k − j + 1 or k − j + 2, the length of the subword of u to which v′ freely reduces. Since w_{1} has length at most 2d_{j}, and w_{2} length at most 2d_{k+1}, the length of v′ is at most

(k − j) + 2(d_{j} + … + d_{k+1}) = (k − j) + 2(e_{k+1} − e_{j−1})
< (k − j) + 2(\frac{t(k + 1)}{s} − \frac{t(j − 1)}{s} + 1)
= (k − j) + 2(\frac{t(k − j + 2)}{s} + 1)
= (k − j) + 2(\frac{(k − j + 2)(λ′ − 1)}{2} + 1)
= (k − j)(1 + λ′ − 1) + 2(λ′ − 1) + 2
= λ′(k − j) + 2λ′.

Since |λ − λ′| ≤ 1/s, it follows that l(v′) exceeds λ times its geodesic length by at most 2λ + (k − j + 2)/s, which is certainly normally less than 2λ + 1; careful separate consideration of the cases k = s and j = 0 confirms 2λ + 1 as an upper bound in those cases too.

Similarly, we see that the length of v′ is at least

(k − j) + 2(d_{j+1} + … + d_{k}) = (k − j) + 2(e_{k} − e_{j})

> (k − j) + 2(\frac{tk − tj}{s} − 1)
= k − j + 2(\frac{(k − j)(λ′ − 1)}{2} − 1)
= (k − j)λ′ − 2,

which is smaller than λ times its geodesic length by at most 2λ + 1, and so v is an exact (λ, 2λ + 1)-quasigeodesic, as required. □

From Lemma 3.5 and Proposition 3.2, we can now conclude:

Theorem 3.6 Let λ ≥ 1 be rational and ϵ ≥ 2λ + 1. Then the set of exact (λ, ϵ)-quasigeodesics forms the language of a synchronous automatic structure for G. Furthermore, distinct values of λ give rise to distinct automatic structures.

Since we are assuming that G is infinite, the final statement of the theorem is clear, because a sufficiently long word cannot be both an exact (λ, ϵ)- quasigeodesic and an exact (λ′, ϵ′)-quasigeodesic when λ ≠ λ′.

We certainly could not expect to get the same results for irrational λ, because there are only countably many possible automatic structures for G (since there are only countably many regular languages over any given alphabet)! Our final aim is to show that the statement of Theorem 3.4 is false whenever λ is irrational.

Lemma 3.7 Let λ ≥ 1 be rational. Then integers r, s with r/s = λ can be found such that there is a (λ, 2λ)-quasigeodesic word v with length r and geodesic length s for which each positive power v^{n} is a (λ, 2λ)-quasigeodesic word of geodesic length ns.

Proof: Let W be the (minimised) word acceptor in the automatic structure for G for which L(W) is the set of all geodesic words. Then all states of W are accept states, except for a unique failure state. Since we are assuming that G is infinite, L(W) is infinite, which means that there is a word u over X that maps some accept state of W to itself. Since L(W) is closed under subwords, it follows that u^{n} is accepted by W and is therefore a geodesic for all n ≥ 0.

Let s be the length of u. By replacing u by a power if necessary, we can assume that t = (λ − 1)s/2 is an integer. Now we construct a quasigeodesic word v of length r = s + 2t exactly as in the proof of Lemma 3.5. Since we now have t exactly equal to (λ − 1)s/2, v is a (λ, 2λ)-quasigeodesic.

The fact that the same is also true of any power v^{n} of v follows from the fact that the procedure described above to construct v from u also constructs v^{n} from u^{n}, since the sequence (d_{i}) is periodic with period dividing s. □

Lemma 3.8 Given any μ and any ϵ ≥ 0, if v is a word such that it and all of its powers are (μ, ϵ)-quasigeodesics, and v has length r and geodesic length s, then r/s ≤ μ.

Proof: Suppose that v has length r and geodesic length s. Then for any n, v^{n} has length nr and geodesic length at most ns. Hence for any n,

nr ≤ μns + ϵ

Dividing by n we see that r ≤ μs. □

Theorem 3.9 Suppose that μ is irrational and greater than 1, and that ϵ ≥ 2μ. Then the set of (μ, ϵ)-quasigeodesic words over X is not regular.

Proof: We prove the result by contradiction.

Suppose that the set is regular and is recognised by an automaton M_{μ}. Choose coprime integers a, b, both bigger than N such that a/b < μ, and such that, for any pair of positive integers a′, b′ with a/b ≤ a′/b′ < μ, both a′ and b′ are bigger than N. Lemma 3.7 guarantees that we can find integers r, s, such that r = ca and s = cb for some integer c, together with an (r/s, 2μ)-quasigeodesic v of length r and geodesic length s, for which each power v^{n} (for n > 0) is a (r/s, 2μ)-quasigeodesic. Recall from the proof of Lemma 3.5 that v is a concatenation of pieces of the form x_{i}(x_{i}^{−1}x_{i})^{d_{i}}, for some i, d, and that its free reduction is a geodesic.

Each power v^{n} must be accepted by the automaton M_{μ}. Therefore, since M_{μ} has N states, for some integers k_{0}, k, where 1 ≤ k ≤ N, the target in M_{μ} of every power v^{k_{0}+mk} is the same state σ_{0}. We define the word v_{0} to be v^{k}. This has length r_{0} = kr and geodesic length s_{0} = ks.

Our aim is to establish a contradiction by constructing infinite sequences of integers r_{0}, r_{1}, … and s_{0}, s_{1}, … with N < r_{i} < r_{0} and N < s_{i} < s_{0}, and such that for any i either

\frac{r_{i}}{s_{i}} < \frac{r_{i+1}}{s_{i+1}} < μ

or r_{i+1} < r_{i} and

\frac{r_{i+1}}{s_{i+1}} = \frac{r_{i}}{s_{i}} .

Clearly infinite sequences of this type cannot exist and so we have a contradiction. We find r_{i} and s_{i} as the length and geodesic length respectively of a (μ, ϵ)-quasigeodesic word v_{i} which is a concatenation of pieces. All of the powers of v_{i} are also (μ, ϵ)-quasigeodesic, its free reduction is geodesic, and it maps some state σ_{i} of M_{μ} to itself. Note that we have already ensured that the word v_{0} has these properties.

Suppose that we have found appropriate v_{i}, r_{i}, s_{i} and σ_{i} for some i. Then we shall describe how to find v_{i+1}, r_{i+1}, s_{i+1} and σ_{i+1}.

Since s_{i} > N, we can write v_{i} as a product uv′_{i}w, where each of u, v′_{i}, w is a proper subword of v_{i} and is a concatenation of pieces, and the target of σ_{i} under both u and uv′_{i} is the same state σ_{i+1}. Then, for any n, v_{i}^{′n} maps σ_{i+1} to σ_{i+1}. Hence v′_{i} and all its powers v_{i}^{′n} are (μ, ϵ)-quasigeodesics, and hence, by Lemma 3.8, where r′_{i} is the length of v′_{i} and s′_{i} its geodesic length, r′_{i}/s′_{i} ≤ μ.

Now since w maps the state σ_{i+1} to the state σ_{i} and u maps σ_{i} to σ_{i+1}, the word wu maps σ_{i+1} to σ_{i+1}, and so this too is a word all of whose powers are (μ, ϵ)-quasigeodesics. It has length r′′_{i} = r_{i} − r′_{i}, and geodesic length s′′_{i} = s_{i} − s′_{i} (since it is a concatenation of pieces), and hence r′′_{i}/s′′_{i} ≤ μ.

Now since r′_{i} + r′′_{i} = r_{i} and s′_{i} + s′′_{i} = s_{i}, if one of r′_{i}/s′_{i} and r′′_{i}/s′′_{i} is strictly less than r_{i}/s_{i}, then the other must be greater than r_{i}/s_{i}. Hence either

\frac{r′_{i}}{s′_{i}} = \frac{r_{i}}{s_{i}} = \frac{r′′_{i}}{s′′_{i}} ,

in which case we set r_{i+1} = r′_{i} < r_{i} and s_{i+1} = s′_{i} < s_{i}, or one of r′_{i}/s′_{i} and r′′_{i}/s′′_{i} is larger than r_{i}/s_{i}, in which case we select the values of r and s from the larger pair as r_{i+1} and s_{i+1}. If r_{i+1} = r′_{i} then v_{i+1} = v′_{i}, and if r_{i+1} = r′′_{i} then v_{i+1} = wu. Since r_{i+1}/s_{i+1} ≥ a/b, we know that r_{i+1}, s_{i+1} > N. □

References

[1] J. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro and H. Short, Notes on word-hyperbolic groups, Proc. Conf. Group Theory from a Geometrical Viewpoint, eds. E. Ghys, A. Haefliger and A. Verjovsky, held in I.C.T.P., Trieste, March 1990, World Scientific, Singapore, 1991.

[2] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson and W.P. Thurston, “Word Processing in Groups”, Jones and Bartlett, Boston, 1992.

[3] W. D. Neumann and M. Shapiro, Equivalent automatic structures and their boundaries, Int. J. Algebra Comput. 2 (1992), 443–469.