Decision problems in finitely presented groups

Derek F. Holt

1 Introduction

Let G = ⟨X |R ⟩ be a group defined by a finite presentation, let A = X ∪ X^{−1} and let A^{∗} denote the set of words in A, including the empty word ε. For v, w ∈ A^{∗}, v = w will mean that they are equal as words, and v =_{G} w will mean that they map onto the same element of G. We shall also use \overline{w} to denote the image of the word w in G.

In this article, we shall be concerned with the following three decision problems.

The word problem: for w ∈ A^{∗} is \overline{w} = 1?

The conjugacy problem: for v, w ∈ A^{∗} does there exist g ∈ A^{∗} with vg =_{G} gw?

The generalized word problem: given w ∈ A^{∗} and a finite set of words in A^{∗} generating a subgroup H of G, is \overline{w} ∈ H?

As with almost all such decision problems, they are theoretically undecidable in general; in particular, the celebrated Novikov-Boone theorem asserts that the word problem is undecidable. (For an accessible proof of this result, see Chapter 13 of [Rotman, 1984].) However, we shall be concerned here with examples and situations in which one or more of these problems is decidable, and more importantly in efficient computational solutions.

Notice that we have phrased the problems in such a way that they make sense in the more general context of monoids, although we do not know whether the conjugacy problem is of any interest in this more general setting.

2 The word problem

Probably the first efficient method devised for solving the word problem was Dehn’s algorithm for small cancellation groups, which is described in Section 4, Chapter V of [Lyndon and Shupp, 77]. After enlarging the set R of defining relators, any element equal to the identity in such a group can be reduced in length by a single substitution, using a defining relator.

More generally, a rewriting system for a group (or monoid) G is a set S of rewrite-rules v → w with v, w ∈ A^{∗}, such that v =_{G} w for all rewrite-rules, and the set of all such equations forms a set of defining relations for G as a monoid. (So, in particular, it contains rules of the form xx^{−1} → ε for generators x ∈ A.) There is a fairly extensive literature on rewriting systems, so we shall give only brief details here. For example, there is a detailed theoretical and practical treatment of their applications to group theory in [Sims, 94].

The idea is that for any word w ∈ A^{∗}, we attempt to reduce the word by substituting the right hand sides of the rules in S for the left hand sides. Usually we ensure that this is a genuine reduction by imposing a suitable wellordering ≺ of A^{∗}, which must be preserved under left and right multiplication by words in A^{∗}, and arrange the rewrite rules such that w ≺ v. (For example, in a shortlex ordering, shorter words precede longer ones, and a lexicographical ordering is used to distinguish between words of equal length.)

Words that contain no occurrences of left-hand-sides of rules in S are called S-irreducible. S is called complete if every word w ∈ A^{∗} can be reduced, by a finite number of reductions, to an S-irreducible word that is uniquely determined by w. This turns out to be equivalent to the property that v =_{G} w if and only if v and w reduce to the same irreducible word, and so we can use a complete rewriting system to solve the word problem in G. Example: A complete rewriting system S for the free abelian group ⟨a, b | ab = ba⟩ of rank 2 (using a shortlex ordering on A^{∗}) consists of the 8 reduction rules

aa^{−1} → 1, a^{−1}a → 1, bb^{−1} → 1, b^{−1}b → 1,
ba → ab, ba^{−1} → a^{−1}b, b^{−1}a → ab^{−1}, b^{−1}a^{−1} → a^{−1}b^{−1}.

In general, we can try to find a complete presentation for G by starting with rules corresponding to the defining relators of G, and applying the Knuth-Bendix completion procedure which adjoins new rules to S, and halts when S is complete. However, in most cases when G is infinite, there is no finite complete system, and so the procedure will never halt.

Finite complete systems have been found for various particular types of groups, including polycyclic-by-finite groups, two-dimensional surface groups, and many Coxeter groups. However, there is no really satisfactory underlying theory, and the existence of such systems often depends on judicious or fortuitous choice of generators X for G and the ordering ≺ on A^{∗}.

Although a finite complete rewriting system usually seems to lead to a reasonably efficient computational solution of the word problem, this is not always the case, as the following monoid example illustrates. Example: A = {e, c, o, z}, S consists of the three rules

ze → ce, zc → oz, oc → cz.

Then S is complete (using a shortlex ordering on A^{∗}), and the word z^{n}e reduces to c^{n}e for all n > 0, but it requires 3.2^{n} − 2n − 3 reduction steps.

An alternative method of solving the word problem efficiently in a group G is to try to find an automatic structure for G. These are defined in terms of finite state automata, which we shall abbreviate to fsa in both singular and plural. See for example [Hopcroft and Ullman, 1979] for the general theory of fsa.

Definition 2.1 The group G = ⟨ A | R ⟩ is said to be automatic (with respect to A), if there exist finite state automata W, and M_{a} for each a ∈ A, such that:

(i) W has input alphabet A, and accepts a unique word mapping onto each element of G. (ii) Each M_{a} has input alphabet A′×A′, and it accepts the padded pair (v^{+}, w^{+}) for v, w ∈ A^{∗} if and only if v, w ∈ L(W) and va =_{G} w.

Here A′ = A ∪ {$}, where $ is used as a padding-symbol. For w, x ∈ A^{∗}, the associated padded pair (w^{+}, x^{+}) ∈ (A′ × A′)^{∗} is obtained by adjoining symbols $ to the shorter of w and x to make them have equal length. The language of the fsa W is denoted by L(W).

The fsa W is called the word-acceptor and the M_{a} the multiplier automata. The complete collection {W, M_{a}} is known as an automatic structure for G.

The definition of the class of automatic groups evolved in the mid-1980’s following the appearance of a paper by Jim Cannon on hyperbolic groups [Cannon, 84]. Bill Thurston noticed that some of the properties that were proved about these groups could be reformulated in terms of finite state automata. The class of word-hyperbolic groups, which is a generalization due to Gromov of the class considered by Cannon, is one of the most important family of examples. A finitely generated group G is called word-hyperbolic if, for any geodesic triangle in the Cayley graph of G, any point on any side of the triangle lies within a bounded distance of the union of the other two sides. This property turns out to be independent of the choice of finite generating set for G.

The best general reference for the theory of automatic groups is the book [Epstein et. al., 1992]. In particular, it turns out that the automaticity of G is independent of the choice of generating set X. All finite groups are easily seen to be automatic; in fact the class of automatic groups is invariant under finite variations, such as sub- and super-groups of finite index. It is also closed under direct and free products, and includes, for example, all word-hyperbolic groups, braid groups, Coxeter groups and Artin groups of finite type. All automatic groups have finite presentations.

Given an automatic structure, the word problem can be solved in time O(n^{2}), where n is the length of the input word u, by using the multiplier automata to reduce u to a G-equivalent word in L(W) (which can be thought of as the normal form for u).

A collection of programs has been written at Warwick for computing automatic structures. Currently, they only work for shortlex structures, in which L(W) consists of the least words under the shortlex ordering that map onto each group element. Many, but not all, of the known classes of automatic groups are known to possess shortlex structures. In particular, word-hyperbolic groups are shortlex automatic with respect to any set of group generators and any ordering of the generators and their inverses.

The programs are described in some detail in [Epstein, Holt, Rees, 1991] and [Holt, 1995], and more generally in [Epstein et. al., 1992]. The latest version is part of a package called kbmag and is available by anonymous ftp from

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

3 The conjugacy problem

One method of solving the conjugacy problem in a group G is to try to find a bi-automatic structure for G.

Definition 3.1 The group G = ⟨ A | R ⟩ is said to be bi-automatic, if there exist finite state automata W, M_{a} and _{a}M for each a ∈ A, such that:

(i) W has input alphabet A, and accepts a unique word mapping onto each element of G. (ii) Each M_{a} has input alphabet A′×A′, and it accepts the padded pair (v^{+}, w^{+}) for v, w ∈ A^{∗} if and only if v, w ∈ L(W) and va =_{G} w. (iii) Each_{a}M has input alphabet A′×A′, and it accepts the padded pair (v^{+}, w^{+}) for v, w ∈ A^{∗} if and only if v, w ∈ L(W) and av =_{G} w.

The bi-automatic structure for G consists of the collection {W, M_{a}, _{a}M} of fsa in the definition. Not every automatic structure is part of a bi-automatic structure, but no examples are known of groups that are automatic but not biautomatic. In particular, any shortlex automatic structure of a word-hyperbolic group is part of a bi-automatic structure.

Given a bi-automatic structure and words v, w ∈ A^{∗}, we can construct the composite multipliers M_{v} and _{w}M, which recognize multiplication on the right by v and on the left by w, respectively.

Then

L(M_{v}) ∩ L(_{w}M) = { (g^{+}, h^{+}) ∈ (A′ × A′)^{∗} |
g, h ∈ L(W), gv =_{G} h, wg =_{G} h }

so v and w are conjugate in G if and only if L(M_{v}) ∩ L(_{w}M) is nonempty. Unfortunately, the algorithm for constructing M_{v} has complexity exponential in the length of v, so this method is only practical for short words v, w.

An O(n^{2}) algorithm for the conjugacy problem for word-hyperbolic groups has been devised by Epstein, and we expect it to be efficient, but it requires a prior knowledge of the constant of hyperbolicity of G. Currently no practical general method is known for computing this constant, so it is difficult at this time to assess Epstein’s conjugacy algorithm properly.

4 The Generalized Word Problem

A method of solving the generalized word problem efficiently for a subgroup H of a group G is to try to find an automatic coset system for G with respect to H.

Definition 4.1 The group G = ⟨ A | R ⟩ is said to be coset automatic with respect to the finitely generated subgroup H, if there exist finite state automata W, and M_{a} for each a ∈ A, such that:

(i) W has input alphabet A, and accepts a unique word in each coset Hg of H in G. (ii) Each M_{a} has input alphabet A′×A′, and it accepts the padded pair (v^{+}, w^{+}) for v, w ∈ A^{∗} if and only if v, w ∈ L(W) and Hva = Hw.

The automata W, M_{a}(a ∈ A) constitute an automatic coset system for G with respect to H. Given an automatic coset system, the generalized word problem can be solved in time O(n^{2}), where n is the length of the input word u, by using the multiplier automata to reduce u to a word in L(W) ∩ Hu. (In practice, the representative of H in L(W) is virtually always the empty word ε, although the definition does not require this.)

The kbmag package mentioned above is capable of computing shortlex automatic coset systems under certain additional technical conditions which we shall not explain in detail here, but which do appear to hold in many examples, including all quasiconvex subgroups of word-hyperbolic groups.

Suppose that we have an automatic coset system {W, M_{a}} for G with respect to a subgroup H, and let

Y = \{ \overline{va} \overline{x}^{−1}) | a ∈ A, (v^{+}, x^{+}) ∈ L(M_{a}) \}.

So Y is a set of Schreier generators of H with respect to G.

We now make the additional assumption that Y is finite. (In fact, this is one of the assumptions required for the implementation in kbmag to succeed.) Then H can be shown to be finitely presented, and there is a straightforward algorithm, which is implemented in kbmag, for computing a presentation of H with Y as generating set.

The idea is to regard the elements of Y as initial states of the coset multiplier automata M_{a}. Then we build the composites M_{r} for the defining relators r of G, and the defining relators for H are the initial states of the M_{r}. See [Hurt, 1997] or [Holt and Hurt, 1997] for further details. Example: Let G be the Heineken group

⟨ x, y, z | [x, [x, y]] = z, [y, [y, z]] = x, [z, [z, x]] = y ⟩

and

H = ⟨ [x, y], [y, z], [z, x] ⟩.

Then kbmag calculated that H is free of rank 3 (and hence free on the given generating set). In fact some related calculations enabled us to prove that G itself is word-hyperbolic.

There is an alternative approach to solving the generalized word problem, which starts with an automatic structure {W, M_{a}} for the full group G. Let L = L(W). The subgroup H is called L-rational if L∩H is a regular language (i.e. the language of an fsa). Such subgroups were studied in [Gersten and Short, 1994], where it is proved that L-rational is equivalent to L-quasiconvex. This means that any prefix of a word in L ∩ H lies within a bounded distance of H in the Cayley graph of G. Such subgroups are always finitely generated.

An algorithm for constructing an fsa W_{H} with language L ∩ H, which takes as input an automatic structure for G and a set of generators for an Lrational subgroup H of G, is described in [Kapovich, 1995]. A practical version is described in [Hurt, 1997], and an implementation is available in kbmag.

The fsa W_{H} can be used together with the automatic structure of G to determine whether a given word in A^{∗} lies in H. First use the the multiplier automata to reduce the word to one in L, and then use W_{H} to test whether it lies in H.

As a further application, if we can find W_{H_{1}} and W_{H_{2}} for two subgroups H_{1} and H_{2}, then we can compute the intersection of their languages, and hence derive a (finite) generating set for H_{1} ∩ H_{2}.

References

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

[Epstein et. al., 1992] David B. A. Epstein J.W. Cannon, D. F. Holt, S. Levy, M. S. Patterson and W. Thurston, Word Processing in Groups, Jones and Bartlett, 1992.

[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.

[Gersten and Short, 1994] S. M. Gersten, H. B. Short, “Rational Subgroups Of Biautomatic Groups”, Ann. Math. 134 (1991), 125–158.

[Holt, 1995] Derek 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. Gilbert Baumslag et. al., 1995, 69–82.

[Holt and Hurt, 1997] Derek F. Holt and Darren F. Hurt, “Computing automatic coset systems and subgroup presentations”, submitted to J. Symbolic Computation.

[Hopcroft and Ullman, 1979] John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, 1979.

[Hurt, 1997] Darren F. Hurt, The Use of Knuth-Bendix Methods and Automatic Coset Systems for Solving the Generalized Word Problem and Finding Subgroup Presentations, PhD Thesis, University of Warwick, 1997.

[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 25, ed. Gilbert Baumslag et. al., 1995, 91–99.

[Lyndon and Shupp, 77] R.C. Lyndon and P.E. Shupp, Combinatorial Group Theory, Springer-Verlag, Berlin-Heidelberg-New York, 1977.

[Rotman, 1984] , Joseph J. Rotman, An Introduction to the Theory of Groups, Third Edition, Allyn and Bacon, Inc., 1984.

[Redfern, 1993] I. D. Redfern, Automatic Coset Systems, PhD Thesis, University of Warwick, 1993.

[Sims, 94] C.C. Sims, Computation with Finitely Presented Groups, Cambridge University Press, 1994.