Efficient computation in word-hyperbolic groups

David B. A. Epstein and Derek F. Holt

Abstract

We describe briefly some practical procedures for computing the various constants associated with a word-hyperbolic group, and report on the performance of their implementations in the KBMAG package on a number of examples. More complete technical details will be published elsewhere.

1 Introduction

During the mid 1980’s, there was a growing demand for efficient computational methods for solving some of the classical decision problems, such as the word, conjugacy and isomorphism problems, in infinite finitely presented groups. These are of course theoretically undecidable in general, but some of them have been proved to be solvable in various special classes of groups, such as braid groups, Coxeter groups and knot groups. At that time, the only existing general technique for attempting to solve the word problem on a computer was the Knuth-Bendix algorithm (see, for example [Gilman, 1979]). However, this was not really satisfactory, because most of the time it did not work, and making it work at all for infinite groups usually depended on an appropriate and often non-obvious choice of an ordered generating set for the group.

In 1985, the concept of an automatic group was introduced by W. Thurston, as a formulation in terms of finite state automata of various geometrical properties of discrete cocompact groups of isometries of hyperbolic space that had been proved by Jim Cannon in [Cannon, 84]. Many familiar classes of groups, including word-hyperbolic groups, virtually abelian groups, Coxeter groups, braid groups and most knot groups have been shown to be automatic. The word problem is solvable (by reduction of words to a normal form) in quadratic time in these groups. The conjugacy problem is solvable (but only in exponential time) in the more restricted class of biautomatic groups.

Algorithms for performing these computations were implemented in Warwick during the following few years by the authors of this paper and Sarah Rees. See the multi-author book [Epstein et al., 1992] for the general theory of automatic books, and [Epstein, Holt, Rees, 1991] and [Holt, 1996] for a detailed description of the algorithms. The latest implementation is part of the second author’s package KBMAG [Holt, 1995]. These methods make use of the Knuth-Bendix process, and KBMAG includes a standalone implementation of this. It also includes an extensive library of routines for performing operations on finite state automata.

This article is concerned with the more restricted class of word-hyperbolic groups, which were first defined by Gromov; see [Gromov, 1987]. They represent an algebraic or geometrical formulation of the idea of a negatively curved group, and they include small-cancellation groups and the discrete cocompact isometries of hyperbolic space studied by Jim Cannon. For a detailed exposition of the definitions and properties of these groups, the reader is referred to [Alonso et al, 1991]. In particular, it is shown in Theorem 2.18 of that article that the word problem is solvable by a Dehn algorithm in linear time.

A number of potentially efficient and useful algorithms have been proposed recently for word-hyperbolic groups. The first author has devised an n log(n) solution of the conjugacy problem, which represents a substantial improvement over the exponential time method for biautomatic groups. Mike Shapiro has proposed (in outline) a procedure for reducing words to short-lex normal form in linear time, improving on the general quadratic time method for automatic groups. Eric Swenson has proposed a method for testing a quasiconvex subgroup of a word-hyperbolic group for abnormality. (None of these are published yet.)

However, it is not yet clear whether it will be possible to implement these methods efficiently, because they all depend on the knowledge of various constants that are associated with the Cayley graph of a word-hyperbolic group. In this article, we shall describe in outline some algorithms for computing these constants. More complete details have been or will be published elsewhere. Most of them are either already fully available in KBMAG (which is freely available by ftp), or have experimental implementations in that system.

A group G is word-hyperbolic if geodesic triangles in the Cayley graph Γ of the group are δ′-slim, in the sense that there is a global constant δ′ such that any point on a side of the triangle lies within a distance δ′ in Γ of the union of the other two sides. (This definition turns out to be independent of the choice of generating set of G.) There is an equivalent definition, which we shall state precisely in Section 2, in terms of a usually slightly larger constant δ, known as the thinness constant of Γ, which specifies that all geodesic triangles are δ-thin. The most difficult algorithm that we shall describe is a method of estimating δ for a given group G. Our current experimental implementation works on easy examples, such as the Von Dyck triangle groups and twodimensional space groups.

It was proved by Papasoglu in [Papasoglu, 1994], that G is hyperbolic if and only if all geodesic bigons in Γ are γ-thin for some global constant γ. It is much easier to compute γ than δ, so this provides us with a practical method of verifying that a group really is word-hyperbolic. Our method for finding γ is very similar to an algorithm described in [Wakefield, 1997], but it contains a simplification which appears to improve the performance substantially.

One can also consider geodesic bigons in which one or both of the vertices lies on the boundary of Γ (see Chapter 4 of [Alonso et al, 1991]). These correspond to pairs of infinite geodesic paths in Γ such that all points on the first path lie within a uniformly bounded distance γ̂ of the other path. If one of the vertices of the bigon is a vertex of Γ, then the paths both start at that vertex, and if both vertices lie on the boundary of Γ then the paths are infinite in both directions. There is a fixed constant γ̂ such that all such bigons satisfy this criterion, and we shall describe a method for estimating it. (In all of the examples that we have investigated, γ̂ is no larger than γ.)

Each of these procedures follows a general philosophy of group-theoretical algorithms that construct finite state automata. This approach was originally proposed in the algorithms described in Chapter 5 of [Epstein et al., 1992] for computing automatic structures, and employed in their implementations for short-lex structures described in [Holt, 1996]. The idea is first to find a method of constructing likely candidates for the required automata, which we shall call the working automata, The second step is to construct other (usually larger) test automata of which the sole purpose is to verify the correctness of the working automata. If this verification fails, then it should be possible to use words in the language of the test automata to construct improved versions of the working automata. One practical difficulty with this approach is that experience shows that incorrect working automata and the resulting test automata are much larger than the correct ones, so it can be extremely important to find good candidates on the first pass.

The remainder of this article is organised as follows, In Section 2 we summarise the required definitions and notation. In Section 3 we describe our method of verifying hyperbolicity by computing γ, and of finding the related constant γ̂. In Section 4 we describe briefly our proposal for estimating δ. Finally, we discuss the performance of our implementations on some examples in Section 5.

2 Notation

G will denote a group with a given finite generating set X. Let A = X ∪X^{−1}, and let A∗ be the set of all words in A. For u, v ∈ A^{∗}, we denote the image of u in G by \overline{u}, and u =_{G} v will mean the same as \overline{u} = \overline{v}. For a word u ∈ A^{∗}, l(u) will denote the length of u and u(i) will denote the prefix of u of length i, with u(i) = u for i ≥ l(u).

Let Γ = Γ_{X}(G) be the Cayley graph of G with respect to X. We make Γ into a metric space in the standard manner, by letting all edges have unit length, and defining the distance ∂(x, y) between any two points of Γ to be the minimum length of paths connecting them. (The points of Γ include both the vertices, and points on the edges of Γ.) This makes Γ into a geodesic space, which means that for any x, y ∈ Γ there exist geodesics (i.e. shortest paths) between x and y. For g ∈ G, l(g) will denote the length of a geodesic path from the base vertex 1_{G} of Γ to g.

A geodesic triangle Δ in Γ consists of three not necessarily distinct points a, b, c together with three directed geodesic paths u, v, w joining bc, ca and ab, respectively. (So l(u) = ∂(b, c), etc.) The vertices a, b, c of Δ are not necessarily vertices of Γ; they might lie in the interior of an edge of Γ.

The most convenient definition of word-hyperbolic groups is in terms of thin triangles. Let Δ be a geodesic triangle as above. Let ρ(a) = (l(v)+l(w)− l(u))/2 and define ρ(b), ρ(c) correspondingly. Then ρ(b) + ρ(c) = l(u), so any point d on u satisfies either ∂(d, b) ≤ ρ(b) or ∂(d, c) ≤ ρ(c), and similarly for v and w. The points d, e, f on u, v, w with ∂(d, b) = ρ(b) and ∂(d, c) = ρ(c), etc., are known as the meeting points of the triangle (see Fig. 1).

In a constant curvature geometry (the euclidean plane, the hyperbolic plane or the sphere), the meeting points of a triangle are the points where the inscribed circle meets the edges. In more general spaces, such as Cayley graphs, the term inscribed circle has no meaning, but the meeting points can still be defined.

Suppose a, b and c are vertices in the Cayley graph. Then the meeting points are also vertices if and only if the perimeter l(u) + l(v) + l(w) is even. In our algorithm for estimating δ we will avoid the resulting unpleasantness in the case of triangles of odd perimeter by shifting the meeting points by a distance of 1/2 to a neighbouring vertex.

Let δ ∈ ℝ_{+}. Then we say that Δ is δ-thin if, for any r ∈ ℝ with 0 ≤ r ≤ ρ(x), the points p and q on v and w with ∂(p, a) = ∂(q, a) = r satisfy ∂(p, q) ≤ δ, and similarly for the points within distance ρ(b) of b and ρ(c) of c. We call such points p and q companions. Normally companions are distinct, but there can be many situations where they coincide—for example two geodesics sides of a triangle could have an intersection consisting of a disjoint union of three intervals. Mostly points on the triangle have exactly one companion, but the meeting points normally have two companions— once again, in degenerate situations two or all three of the meeting points may coincide.

The group G is called word-hyperbolic if there exists a δ such that all geodesic triangles in Γ are δ-thin. (It turns out that this definition is independent of the generating set X of G, although the minimal value of δ does depend on X.)

If u, v ∈ A^{∗}, then we call the set D = \{\overline{u(i)}^{−1}\overline{v(i)} | i ∈ ℤ, i ≥ 0\} the set of word-differences arising from (u, v). We say that u and v fellow-travel with respect to D and, if β ≥ max{l(g) | g ∈ D}, then we say that u and v fellow-travel with the bound β.

Notice that in a geodesic triangle in a word-hyperbolic group, with the above notation, the words along the edges of the triangle from a to e and a to f fellow-travel with bound δ, and similarly for the pairs of words from the other two vertices to the meeting points. This fact forms the basis of our method for estimating δ to be described in Section 4. The crucial point is that word pairs (u, v) which fellow-travel with respect to a set D of worddifferences can be recognised by a 2-variable finite state automaton having state set D. (See one of the references on automatic groups for technical details.)

The group G is said to be automatic, if there is a finite state automaton W (the word-acceptor) with alphabet A that accepts at least one word mapping onto each element of G, and a bound β such that all pairs of words u and v in the languageL(W) of W such that l(\overline{u}^{−1}\overline{v}) ≤ 1 fellow-travel with the bound β. See [Epstein et al., 1992] for the basic properties of automatic groups.

Now we fix a total order on the alphabet A. The automatic structure is

Figure 1. This picture shows the meeting points as the intersection of the inscribed circle with the edges of the triangle in the case of constant curvature geometry. called short-lex if L(W) consists of the short-lex least representatives of each element g ∈ G; that is the lexicographically least among the shortest words in A∗ that map onto g. The existence of such a structure for a given group G depends in general on the generating set X of G, but word-hyperbolic groups are known to be short-lex automatic for any choice of generators. (This is Theorem 3.4.5 of [Epstein et al., 1992].)

The group G is called strongly geodesically automatic with respect to X if there is an automatic structure in which L(W) is the set of all geodesic words u ∈ A^{∗}; that is, those u for which l(u) = l(\overline{u}). It is shown in Theorem 3.2.1 of [Epstein et al., 1992] that this property is equivalent to the existence of a constant γ such that all geodesic words u, v ∈ A^{∗} with l(\overline{u}^{−1}\overline{v}) ≤ 1 fellowtravel with bound γ. In this case, γ is also a bound on the width of geodesic bigons in Γ, and we shall describe how to compute such a γ, together with the set of associated word-differences of length at most γ, in Section 3. It is proved in Corollary 2.3 of [Papasoglu, 1994] that G is strongly geodesically automatic if and only if G is word-hyperbolic, and so this calculation also provides us with an efficient verification procedure for the word-hyperbolicity of G.

We shall assume throughout that our group G = ⟨X⟩ is short-lex automatic with respect to X, and that we have already computed the corresponding short-lex word-acceptor W and the set of word-differences D arising from the pairs of words u, v ∈ L(W) such that l(\overline{u}^{−1}\overline{v}) ≤ 1. This data, which is known as the short-lex automatic structure of G with respect to X, can be used to reduce arbitrary words in A^{∗} to their short-lex least equivalent word in G in quadratic time. The above computations can all be carried out using KBMAG.

3 Verifying hyperbolicity

As explained above, to verify hyperbolicity, we need to find a constant γ such that all geodesic word pairs (u, v) with l(\overline{u}^{−1}\overline{v}) ≤ 1 fellow-travel with bound γ. Since we have already proved short-lex automaticity, it follows easily from the definition of automaticity that it is sufficient to find such a constant γ′ for those pairs in which u =_{G} v and v is short-lex minimal. The calculation of γ and the associated word-difference set from γ′ is then a straightforward composite operation on finite state automata (see [Holt, 1996]). We can also construct an automaton GW that accepts all geodesic words in Γ; that is, the word-acceptor in the geodesic automatic structure.

Assuming that such a γ′ exists, there is a finite set WD of word-differences of length at most γ′ associated with all such geodesic word pairs for which u =_{G} v and v is short-lex minimal. The idea is to construct candidates WD_{n} for WD, where WD_{0} = D, as defined above. We form WD_{n+1} from WD_{n} by adjoining any extra word-differences that we find. If G is word-hyperbolic and WD is finite, then this process will halt when WD_{n} contains WD, but if G is not word-hyperbolic, then it will not halt, and WD_{n} will grow indefinitely large. We also maintain a candidate GW_{n} for the geodesic word-acceptor GW. This is constructed from WD_{n} as the set of all geodesic words u which fellow-travel with their short-lex equivalent v with respect to WD_{n}.

The principal step in the process is to construct a test automaton T that accepts all geodesic words that fellow travel with some word in GW_{n} with respect WD_{n}. If all such words already lie in L(GW_{n}) then the procedure halts and we define GW and WD to be the current candidates. On the other hand, if we find one or more words u in L(T)\L(GW_{n}), then we reduce them to their short-lex equivalent words v, and adjoin the word-differences associated with (u, v) which are not already in WD_{n} to WD_{n}. (By construction of GW_{n}, they cannot all lie in WD_{n}.) The resulting extended set then becomes WD_{n+1} amd the process is repeated with this in place of WD_{n}.

It is not difficult to prove by induction on l(u) that any geodesic word u ∈ A^{∗} must eventually be accepted by some GW_{n}, and so the process will halt if WD is finite. From GW and WD, it is straightforward, using the composite operation on automata, to construct an automaton GP such that L(GP) is equal to all pairs of geodesic words (u, v) for which l(\overline{u}^{−1}\overline{v}) ≤ 1. For full technical details, see [Epstein & Holt 1998] or the similar procedure described in [Wakefield, 1997]

Now consider two infinite geodesic paths u, v in Γ, which either have a vertex of Γ as common starting point and are infinite in one direction only, or are infinite in both directions. We say that u and v are neighbouring paths with respect to the constant γ̂, if every point on one of the paths lies at distance at most γ̂ from the other path. Such pairs of paths correspond to geodesic bigons in Γ in which one or both vertices lie on the boundary of the group, and it can be shown that there is in fact a single constant γ̂ such that all pairs of neighbouring paths in Γ are neighbours with respect to γ̂. As mentioned in the introduction, for several future potential applications, it is important to be able to estimate γ̂ as well as γ.

In the case of one-way infinite paths, where u and v have a common starting vertex, which might as well be the base point of Γ, the set of worddifferences N GD = \{\overline{u(t)}^{−1}\overline{v(t)} | t ∈ ℤ, t ≥ 0\} is finite, and we would like to calculate this set. Then we can take γ̂ to be the maximum length of an element of N GD. For two-way infinite paths u, v, it is can be shown that there are vertices u(0) and v(0) of Γ on u and v such that the elements \overline{u(t)}^{−1}\overline{v(t)} lie in the same set N GD for all t ∈ ℤ. (Here u(t) represents the element of G corresponding to the point on the path u at distance t from u(0), and similarly for v(t).) Hence the same constant γ̂ will serve also for two-way infinite neighbouring paths.

To find N GD, we construct automata NG_{n} (n > 0) which accept all pairs of (finite) geodesic words u, v of equal length l with the following two properties:

(i) There exist one-way infinite neighbouring paths û, v̂ such that u = û(l) and v = v̂(l) are prefixes of û and v̂, respectively;

(ii) There exist finite geodesic words u′, v′ such that u = u′(l), v = v′(l) and

l(\overline{u′}^{−1}\overline{v′}) ≤ n. It is straightforward to construct NG_{1} from GP. We just make all states accepting (which has the effect that all prefixes of accepted words become accepted words), and then (repeatedly) remove any states which are not the source of any transition. This ensures that Condition (i) is satisfied. In general, we construct NG_{n} by taking a composite of NG_{1} and NG_{n−1}, and then removing all states which are not the source of any transition. Since all pairs of words accepted by some NG_{n} are prefixes of pairs of neighbouring geodesics, all such pairs must fellow travel with respect to γ̂, and so eventually we will get NG_{n+1} = NG_{n} and the process will terminate. Then N GD is simply the set of all word-differences arising from pairs of words accepted by NG_{n}.

In principle, this procedure might be expected to get more and more difficult as n grows larger, but in fact in all of the examples that we have tried so far, the process has terminated on the first pass with NG_{2} = NG_{1} and so γ̂ = γ. We are not aware of any theoretical reason why this should be the case in general, however.

4 Finding the thinness constant

Throughout this section, we assume that G = ⟨X⟩ is a word-hyperbolic group and that δ > 0 is a constant such that all geodesic triangles in Γ_{X}(G) are δ-thin. The aim is to devise a practical algorithm to find such a δ, preferably as small as possible. As before, we assume that we have already calculated the short-lex automatic structure for G with respect to X; that is the word-acceptor W and word-differences D. We also need to construct the automaton W^{R} which accepts a word w if and only if the reversed word w^{R} ∈ L(W). Full technical details of the material in this section can be found in [Epstein & Holt 1998].

Let us recall the notation for δ-thin geodesic triangles with vertices a, b, c and edges u, v, w in the Cayley graph Γ = Γ_{X}(G) that was introduced in Section 2. The meeting points on the sides u, v and w are denoted by d, e and f, respectively. We shall call such a geodesic triangle short-lex geodesic, if its vertices are vertices of Γ and if the words A^{∗} corresponding to the edges of the triangle (which we shall also denote by u, v, w) all lie in L(W). We prefer to work with short-lex geodesic triangles, because in general there are far more geodesic triangles and consideration of all of these is likely to make an already difficult computational problem impossible.

Our algorithms are designed to compute the minimal δ ∈ ℕ such that all short-lex geodesic triangles are δ-thin. Let β be the maximum length of an element in D, and let γ and γ′ be as defined in Section 3. Then if δ is the thinness constant for short-lex geodesic triangles, it can be shown by an elementary geometrical argument that the thinness constant for arbitrary geodesic triangles in Γ is at most δ + 2(β + γ′) + 3 or, alternatively, at most δ + 2γ + 3.

Let GT be the set of word-differences arising from those pairs of words (u_{a}, v_{a}), where u_{a} and v_{a} are the words labelling those parts of the two edges of a short-lex geodesic triangle that go from a to the meeting points on the two edges. In other words u_{a} is the prefix of w labelling the word from a to f, and v_{a} is the prefix of v^{R} labelling the word from a to f. The value of δ is then the maximum length of an element of GT . (As we mentioned before, in the case of triangles with odd perimeter, where the meeting points lie in the middle of edges of Γ, we shift each meeting point by a distance half clockwise around the triangle, to bring it to a neighbouring vertex.)

The general philosophy of our tactics is the same as for the algorithm for finding γ′ in Section 3. At any stage, we have a candidate GT_{n} for GT , and we then attempt to decide whether GT_{n} contains GT and, if not, to adjoin some missing elements. Unfortunately, this testing process is much more difficult and heavy on computing resources (particularly memory) than it is for the computations described earlier.

As a candidate for GT_{0} we could choose WD as defined in Section 3, which is essentially the corresponding set for geodesic bigons. However, we have found it more effective to produce GT_{0} by taking pairs u and v of random elements of L(W) (up to some prescribed length). These can be used to calculate the unique w ∈ L(W) which completes the shortlex geodesic hyperbolic triangle, and the elements of GT which arise from this triangle are then computed. We can do this for a large number (perhaps 100000) of random pairs u, v and take GT_{0} to be the set of all word-differences in GT obtained in this fashion.

One might hope to get all of GT fairly quickly by this method, but unfortunately this does not seem happen in practice, and there are typically some word-differences that are hard to find by random methods. It would make the process more efficient if we could find a more refined method for guessing GT , because the correctness testing process works more effectively on correct data.

To perform the correctness test, we use W and GT_{n} to construct an automaton called F RD_{n}, which stands for ‘forward, reverse, difference’. This accepts all pairs of words (u_{a}, v_{a}) as described above. Its name comes from the fact that its states have three components, the first a state of L(W) arising from reading w, the second a state of L(W^{R}) arising from v^{R}, and the third keeping track of the word-difference of the pair in GT_{n}.

From this, we form an associated automaton F RD_{n}^{3}, which consists of three copies of F RD_{n}. The three pairs of words read by F RD_{n}^{3} are accepted when they are the three pairs of edges emerging from the three vertices of some short-lex geodesic triangle, ending and meeting at the meeting points of the triangle. The states of F RD_{n}^{3} are just triples of states of F RD_{n}, but deciding which of them are accept states is quite complicated.

Roughly speaking, for this to be true, the first two components of the three states of F RD_{n} in the triple (that is, the ‘forward’ and ‘reverse’ components) have to match up in such a way that the words u, v and w corresponding to the edges of the triangle all lie in L(W) and, in addition, the product of the three third components, which are the word-differences in GT_{n} has to be equal to the identity in G. Again, we refer the reader to [Epstein & Holt 1998] for full technical details. This list of accept states is typically very large.

The idea then is to compute a two-variable finite state automaton GP (geodesic pairs) of which the language is the subset of A^{∗} × A^{∗} defined by the expression

{(w_{1}, w_{2}) ∈ A^{∗} × A^{∗} |
∃(u_{a}, v_{a}, u_{b}, v_{b}, u_{c}, v_{c}) ∈ L(F RD_{n}^{3}) : w_{1} = u_{a}v_{b}^{R}, w_{2} = v_{a}u_{c}^{R}}.

Then GP accepts the set of pairs of sides (w, v^{R}) emerging from the vertex a in the triangles that are accepted by F RD_{n}^{3}. Thus GT_{n} contains GT , and the process terminates if and only if L(GP) = L(W) × L(W^{R}). Since checking for equality of the languages of automata is easy, we can perform this check provided that we can construct GP.

If the check fails, then our definition of GP ensures that L(GP) ⊂ L(W)× L(W^{R}). So we can find one or more specific word pairs (w_{1}, w_{2}) ∈ L(W) × L(W^{R})\L(GP) and then compute the word-differences arising from the shortlex geodesic triangle having w_{1} and w_{2}^{R} as two of its sides. We can then adjoin these to GT_{n} to form GT_{n+1}.

The construction of GP can be carried out in theory, but because of the large number of quantified variables involved in the above expression, a naive implementation would be hopelessly expensive in memory usage. Our implementation uses a number of refinements, but it remains very heavy in memory usage. However, it does work for some straightforward examples.

5 Examples

The procedure for finding the geodesic fellow-traveller constant γ has been run successfully, using the implementation in KBMAG, on a variety of examples. These include the following.

(i) Two dimensional surface groups T_{m}(m > 1), P_{m}, K_{m}(m > 0) defined by the presentation

⟨ a_{1}, b_{1}, …, a_{m}, b_{m}, x_{1}, …, x_{k} | ∏_{i=1}^{m}(a_{i}^{−1}b_{i}^{−1}ab) ∏_{j=1}^{k} x_{j}^{2} ⟩,

where k = 0, 1 or 2 for the groups T_{m}, P_{m} and K_{m}, respectively. Here γ = 2m for T_{m}, P_{m} and 2m + 2 for K_{m}.

(ii) Hyperbolic von Dyck triangle groups, such as

⟨a, b | a^{3} = b^{n} = (ab)^{2} = 1⟩

for n ≥ 7. Here γ is about n/2. (iii) The symmetry group of a certain tessellation by dodecahedra of hyper-

bolic 3-space as featured in the video ‘Not Knot’ ([Not Knot]), with presentation

G_{4} = ⟨a, b, c, d, e, f | a^{4} = b^{4} = c^{4} = d^{4} = e^{4} = f^{4} = aba^{−1}e = bcb^{−1}f = cdc^{−1}a = ded^{−1}b = efe^{−1}c = faf^{−1}d = 1⟩.

Here γ = 4. (iv) Hyperbolic Fibonacci groups, such as

⟨a_{1}, … a_{m} | a_{i}a_{i+1} = a_{i+2} (1 ≤ i ≤ m)⟩,

where m is even, m ≥ 8, and the indices in the relations are taken modulo m. We have tried m = 8, 10 and 12, in which cases γ = 3.

Of these, the examples in (i) and (ii) were very quick and easy, while those of (iii) and (iv) were rather harder. As we mentioned above, in all of the examples that we have looked at to date we found quickly that γ̂ = γ.

We completed the calculation of δ without undue difficulty in each of the examples in (i) and (ii) that we tried. Generally δ was not much larger than γ, with δ−γ at most 3. To date we have not succeeded in computing δ for the examples (iii) and (iv). Of these, we have some hope of eventually succeeding with (iii), but we will either need to refine our implementations, or acquire the use of a computer with more memory.

References

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

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

[Epstein et al., 1992] D.B.A. Epstein, J.W. Cannon, D.F. Holt, S.V.F. Levy, M.S. Paterson, W. Thurston (1992). Word Processing in Groups, AKPeters, Natick, Mass.

[Epstein & Holt 1998] D. B. A. Epstein and D. F. Holt, Computation in wordhyperbolic groups, preprint.

[Epstein, Holt, Rees, 1991] D. B. A. Epstein, D. F. Holt and S. E. Rees, The use of Knuth-Bendix methods to solve the word problem in automatic groups, J. Symbolic Computation 12 (1991), 397–414.

[Holt, 1995] Derek F. Holt, KBMAG—Knuth-Bendix in Monoids and Automatic Groups, software package (1995), available by anonymous ftp from

ftp.maths.warwick.ac.uk in directory people/dfh/kbmag2.

[Holt, 1996] D.F. Holt, The Warwick automatic groups software, in Geometrical and Computational Perspectives on Infinite Groups DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 25, ed. G. Baumslag et. al., 1996, 69–82.

[Holt & Hurt, 1997] D.F. Holt and D.F. Hurt, Automatic coset systems and subgroup presentations, to appear in J. Symbolic Computation.

[Gilman, 1979] R.H. Gilman, Presentations of groups and monoids, J. Algebra 57 (1979), 544-554.

[Gromov, 1987] M. Gromov, Hyperbolic groups, in Essays in Group Theory, ed. S.M. Gersten, M.S.R.I. Publ. 8, Springer, 1987, 75–263.

[Kapovich, 1995] Ilya Kapovich, Detecting quasiconvexity: algorithmic aspects, in: Geometric and Computational Perspectives on Infinite Groups, DIMACS Series in Discrete Mathematics and Theoretical Computer Science vol. 25, ed. Gilbert Baumslag et. al., 1995, 91–99.

[Not Knot] Charlie Gunn and Delle Maxwell, Not Knot, video ISBN 0-86720-240-8, published by AKPeters, Natick, Mass., with a booklet by D.B.A. Epstein and C. Gunn.

[Papasoglu, 1994] , P. Papasoglu, Strongly geodesically automatic groups are hyperbolic, (Warwick preprint) (1994) (to appear).

[Wakefield, 1997] P. Wakefield, Procedures for Automatic groups, Ph.D. Thesis, University of Newcastle upon Tyne, 1997.