SOLUBLE GROUPS WITH A FINITE REWRITING SYSTEM

J.R.J. Groves & G.C. Smith

Abstract. We describe a class of soluble groups with a finite complete rewriting system which includes all the soluble groups known to have such a system.It is an open question, related to deep questions in the theory of groups, whether it includes all soluble groups with such a system.

The aim of this note is to observe that, using a short argument coupled with some recent results and some known facts from the homology theory of soluble groups, it is possible to “almost” characterise the soluble groups with a finite complete rewriting system. We also take the opportunity to list some problems which we believe to be of importance to a systematic development of the theory of rewriting systems of groups and its applications to group homology but which have not yet, to our knowledge, appeared in print

Let Σ be a finite set (an alphabet) and let Σ^{∗} denote

the free monoid (semigroup with identity) on Σ. A rewriting system (Σ, R) consists of Σ together with a subset R of Σ^{∗} × Σ^{∗}. Define the relation → on Σ^{∗} as follows. Given u, v ∈ Σ^{∗} we say that u → v if and only if there is a sequence

w_{1}, …, w_{n} with w_{i} ∈ Σ^{∗}, w_{0} = u and w_{n} = v

and so that each pair (w_{i}, w_{i+1}) can be expressed in the form

w_{i} = alb, w_{i+1} = arb

with (l, r) ∈ R. (We assume that this vacuously renders valid u → u.) A rewriting system is said to be complete if

(1) there is no infinite sequence

u_{1} → u_{2} → … u_{n} → …

with u_{i} ≠ u_{i+1};

(2) given u, v, w ∈ Σ^{∗} with u → v and u → w, there exists z ∈ Σ^{∗} with v → z

and w → z. Thus the complete rewriting systems are precisely those in which each word in Σ^{∗} will, by random application of the ‘rules’, be rewritten to a unique ‘irreducible’ in a finite number of steps. Finally we say that the rewriting system R is finite if R itself is finite. We shall also say that R is regular if the set of left-hand-sides of pairs in R forms a regular language as a subset of Σ^{∗}. We refer to the books of Le Chenadec[9] or Jantzen[7] for further information on (string) rewriting systems.

We next require some group-theoretical notation. Following Bieri and Baumslag[3], we define a group to be constructible if, roughly speaking, it can be obtained from the trivial group in a finite number of steps by forming finite extensions, finite amalgamated free products and finite rank HNN-extensions where both the free factors (the base group) and the amalgamated (associated) subgroups are groups already obtained. More precisely, we say that finite groups are 0-constructible and that a group is n-constructible if it is a finite extension of a fundamental group of a graph of groups whose edge-groups and vertex-groups are (n − 1)-constructible. So G is constructible if it is n-constructible for some n. In the case of soluble groups, this simplifies considerably. It follows from the work in

[3] that a soluble group is constructible precisely when it is a finite extension of a torsion-free group which can be obtained by a finite series of HNN-extensions in each of which one of the associated subgroups equals the base group and the other has finite index in the base group.

Finally, we introduce some homological notation. Let G be a group and let ℤ denote the ring of integers; then ℤG denotes the integral group ring of G. We say that a group G has type (F P)_{n} if there is an exact sequence of ℤG-modules P_{i} of the form

⋯ → P_{n} → ⋯ → P_{1} → P_{0} → ℤ

with the modules P_{0}, …, P_{n} finitely generated and projective. (Here ℤ also denotes the trivial ℤG-module). If all the modules P_{i} are finitely generated and projective then we say that G has type (F P)_{∞}; if, further, the sequence is finite, we say that G has type (F P). The property (F P)_{1} is equivalent to the property of being finitely generated and the property (F P)_{2} is implied by finite presentation but it is currently unkown whether the reverse implication is true.

We can now state the result.

Theorem. Let G be a soluble group.

(1) If G is constructible then it has a finite rewriting system.

(2) If G has a finite rewriting system then it is of type (F P)_{∞}. In particular, if G is soluble of derived length at most two or if it has finite rank, then G is constructible if and only if it has a finite rewriting system.

We delay the proof of (1). The result (2) is an immediate consequence of the results in Anick[2] or Groves[5]. (See also Squier[11] and Brown[4].) There a resolution by free modules is constructed from a rewriting system in such a way that the modules in this resolution are finitely generated when the rewriting system is finite. The claim of the final sentence can be deduced form the results described in the last section of [1].

We discuss briefly the significance of this. It is relatively straightforward to show that constructible groups have type (F P)_{∞}; see, for example, [3]. It appears to be still an open question whether soluble groups of type (F P)_{∞} are constructible. Certainly, under the assumptions on G stated above, the two properties are known to be equivalent. Also, if we replace the property of being of type (F P)_{∞} by the stronger but related property of being of type (F P) then Kropholler[8] has shown this implies constructibility. Thus it is possible that the soluble groups with a finite rewriting system are precisely the soluble constructible groups.

Proof of part (1) of the Theorem. By the observations made earlier, we can divide the proof into two parts. We must show

(1) that a finite extension of a group with a finite complete rewriting system again has a finite complete rewriting system; and that

(2) if G has a finite complete rewriting system, then an HNN-extension H =< G, t : ϕ(G) = t^{−1}Gt >, where ϕ is a monomorphism of G with finite cokernel, also has a finite complete rewriting system.

We begin with (1). Suppose that G has a finite complete rewriting system (Σ, R) and that G is a subgroup of finite index in a group H. Let Ω be a right transversal for G in H and let Σ′ = Σ ∪ Ω; then Σ′ is finite. If w ∈ (Σ′)^{∗} let w̄ denote the image of w in H.

Let

R_{1} = {(z_{1}z_{2}, uz_{3}); z_{1}, z_{2} ∈ Ω}

where z̄_{1}z̄_{2} = ūz̄_{3} in H and u is R-irreducible. Also let

R_{2} = {(z_{1}s, uz_{2}); z_{1} ∈ Ω, s ∈ Σ}

where z̄_{1}s̄ = ūz̄_{2} in H and u is R-irreducible. Then put

R′ = R ∪ R_{1} ∪ R_{2}.

We claim that (Σ′, R′) is a finite complete rewriting system for H. To begin with, it is easily seen that the R′-irreducibles are in one-to-one correspondence with the irreducibles of H. Thus we only need to describe a well-founded partial order on (Σ′)^{∗} which is compatible with concatenation and so that for each rule in R′, the left-hand side is greater than the right-hand side. Consider a typical word of (Σ′)^{∗} in the form

u_{n+1}z_{n}u_{n} … u_{2}z_{1}u_{1}z_{0}u_{0}

where z_{i} ∈ Ω and u_{i} ∈ Σ^{∗}. Then we order two such words as follows:

(1) by the number n of occurrences of elements of Ω if these are different; or, if these two values are the same,

(2) by taking the lowest value of i for which the syllables u_{i} differ and, if one rewrites under (Σ, R) to the other, taking the former as the larger; or, if neither syllable rewrites to the other,

(3) by taking as larger an element with the syllable of greater length. We leave to the reader the routine check that this is a well-founded partial order which is compatible with concatenation. (cf. the ‘collected’ ordering used in [10]).

We now turn to the second problem. Suppose that G is a group with a finite complete rewriting system and that ϕ is a monomorphism of G so that the image of ϕ is a subgroup of finite index in G. We wish to show that the HNN-extension H =< G, t : ϕ(g) = t^{−1}gt for all g ∈ G > also has a finite complete rewriting system. Firstly, note that because ϕ is an isomorphism from G onto ϕ(G), the latter also has a finite complete rewriting system. Since ϕ(G) has finite index in G, we can extend this finite rewriting system of ϕ(G) to one for G, as above, and so obtain a second finite complete rewriting system (Σ′, R′) for G. Then Σ′ is the union of a subset Σ which generates ϕ(G) and a subset Ω which is a transversal for ϕ(G) in G. Again, if w ∈ (Σ′)^{∗} let w̄ denote the image of w in G.

We now describe the rewriting system for the HNN-extension H. Let

Σ′′ = Σ′ ∪ {t, t^{−1}}.

Let

R_{1} = {(tt^{−1}, 1), (t^{−1}t, 1)}

and

R_{2} = {(t^{−1}u, ϕ̃(u)t^{−1}) : u ∈ Σ′}

where ϕ̃(u) is the irreducible element of (Σ′)^{∗} of which the image in G is the same as that of ϕ(ū). Similarly, let

R_{3} = \{(tv, { \atop ϕ^{−1}(v)}t) : v ∈ Σ\}

where { \atop ϕ^{−1}(v)} is the irreducible element of Σ^{∗} of which the image in G is the same as that of ϕ^{−1}(v̄). Note that, as v̄ ∈ Σ ⊆ ϕ(G), the notation ϕ^{−1}(v̄) is well-defined.

Let R′′ = R′∪R_{1}∪R_{2}∪R_{3}. We claim that (Σ′′, R′′) is a finite complete rewriting system for H. Firstly, note that the R′′-irreducibles are of the form

u_{0}t^{i_{1}}u_{1}t … u_{n}t^{i_{n}}u_{n+1}s

where i_{j} > 0 and s is a power of either t or t^{−1}. It then follows from the standard normal form theorem for HNN-extensions that these are in bijective correspondence with the elements of H. It remains, as in the first part of the proof, to find a suitable order. The ordering is very similar to that used before and we will be brief. We write any word of (Σ′′)^{∗} in the form

u_{n+1}s_{n}u_{n} … u_{2}s_{1}u_{1}s_{0}u_{0}

where s_{i} ∈ {t, t^{−1}} and u_{i} ∈ (Σ′)^{∗}. We then order as above, firstly by the number n and then on the u_{i}. The latter is again done firstly via the natural order arising from the rewriting system on G and secondly by length. It follows that H does indeed have a finite complete rewriting system.

(A more general and considerably more technical version of these results is available in [6].)

Some Questions. We now turn to the questions mentioned above. We believe that a considerably greater understanding of rewriting systems is necessary if the homological theorems mentioned above are to be applied. The three questions below are formulated with this in mind.

Firstly, it has been shown by Jantzen (see Section 4.2 of [7]) that a group with a finite rewriting system may have a generating set on which there is no finite rewriting system. Thus the property of having a finite rewriting system is dependent on the choice of generating set. If, however, we replace ‘finite’ by ‘regular’, we know of no such example.

Question 1. Suppose that G is a group with a regular complete rewriting system. Is it true that, on any finite alphabet which generates G, there is a regular complete rewriting system ?

The second problem is the reverse of the first part of the proof above. It is known that a subgroup of finite index in a finitely presented group is again finitely presented. The proof does not, however, seem to adapt easily to finite rewriting systems.

Question 2. Is it true that a subgroup of finite index in a group with a finite (regular) complete rewriting system must again have a finite (regular) complete rewriting system.

The Theorem above shows that the class of soluble groups with a finite complete rewriting system is very restricted. Finitely generated soluble groups of length two, however, have strong finiteness properties and so we pose the following.

Question 3. Does every finitely generated metabelian group have a regular complete rewriting system?

It is shown in [6] that the wreath product of a group with a regular complete rewriting system with an orderable group with a regular complete rewriting system again has a regular complete rewriting system. It is thus possible to deal with a sizeable class of ‘typical’ metabelian groups. It is also shown in [6] how to reduce the problem for metabelian groups of finite abelian section rank down to a particular and smaller class of groups. We isolate a typical group of this class giving a special ‘test-case’ of Question 3.

Question 3′. Does the group generated by the matrices

[ \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ] , [ \begin{matrix}2/3 & 0 \\ 0 & 1 \end{matrix} ]

have a regular complete rewriting system?

References

1. Åberg, Hans, Bieri-Strebel valuations (of finite rank), Proc. London Math. Soc. (3) 52 (1986), 269–304.

2. Anick, D.J., On the homology of associative algebras, Trans. Amer. Math. Soc. 296 (1986), 641-659.

3. Baumslag, G. and Bieri, R., Constructable solvable groups, Math. Z. 151 (1976), 249–257.

4. Brown, K. S., Proceedings of the Workshop on Algorithms, Word Problems and Classification in Combinatorial Group Theory, MSRI, Berkeley, 1989 (to appear).

5. Groves, J. R. J., Proceedings of the Third International Conference on the Theory of Groups, Canberra, 1989 (to appear).

6. Groves, J. R. J. & Smith, G. C., Rewriting systems and soluble groups, preprint (1989).

7. Jantzen, M., Confluent String Rewriting, EACTS monographs on Theoretical Computer Science, vol. 14, Springer-Verlag, Berlin, 1988.

8. Kropholler, P. H., Cohomological dimension of soluble groups, J. Pure Appl. Algebra 43 (1986), 281–287.

9. Le Chenadec, Ph., Canonical forms in finitely presented algebras, Pitman, London; John Wiley & Sons, New York, 1986.

10. Sims, C. C., Verifying Nilpotence, J. Symbolic Computation 3 (1987), 231-248.

11. Squier, Craig C., Word problems and a homological finiteness condition for modules, J. Pure Appl. Algebra 49 (1987), 201-217.

University of Melbourne, Parkville, Australia 3052 and School of Mathematical Sciences, University of Bath, England.