\input amstex
\textfont9=\tenbf
% Previous two lines added JHD 14.2.89
\magnification=1200
\def\comment #1{\sevenbf\par\noindent\hrule\smallskip #1
\smallskip\hrule\medskip}
\def\fcrs{finite complete rewriting system }
\def\rcrs{regular complete rewriting system }
\def\fpi{$FP_{\infty}$ }
\def\fgm{finitely generated metabelian }
\def\fg{finitely generated }
\def\xgen{\langle x \rangle}
\def\zx{{\Bbb Z}\langle x \rangle}
\documentstyle{amsppt}
\document
\medskip 
\nologo
\topmatter
\title Soluble Groups with a Finite Rewriting System
\endtitle
\author J.R.J. Groves \& G.C. Smith\endauthor
\address{University of Melbourne, Parkville, Australia 3052 and 
School of Mathematical Sciences, University of Bath, England.}\endaddress
\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.}\endabstract
\endtopmatter



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 $\Sigma$ be a finite set (an {\it alphabet}) and let $\Sigma^*$ denote

the free monoid (semigroup with identity) on $\Sigma$.  A {\it rewriting
system}
$(\Sigma,R)$  consists of $\Sigma$ together with a subset $R$ of $\Sigma^* 
\times \Sigma^*$. Define the relation $\rightarrow$  on $\Sigma^*$ as
follows.
Given $u,v \in \Sigma^*$
we say that $u \rightarrow v$ if and only if  there is a 
sequence 
$$w_1, \dots ,w_n \qquad \text{with } w_i \in \Sigma^*, w_0=u\text{ and
}w_n=v$$ 
and so that each pair $(w_i,w_{i+1})$ can be expressed in the form
$$w_i =alb,\qquad w_{i+1}=arb$$ with $(l,r)\in R$.
(We assume that this vacuously renders valid  $u \rightarrow u$.) A
rewriting
system is said to be {\it complete} if  \roster
\item there is no infinite sequence
$$u_1 \rightarrow u_2 \rightarrow \dots u_n \rightarrow\dots\quad$$
with $u_i \neq u_{i+1}$;
\item given $u,v,w \in \Sigma^*$ with $u \rightarrow v$ and $u \rightarrow
w$, there exists $z \in \Sigma^*$ with $v \rightarrow z$ and $w \rightarrow
z$.
\endroster
Thus the complete rewriting systems are precisely those in which each word
in
$\Sigma^*$ 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  {\it finite}
if $R$ itself is finite. We shall also say that $R$ is {\it regular} if the
set
of left-hand-sides of pairs in $R$ forms a regular language as a subset of
$\Sigma^*$. 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 {\it 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
{\it 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
$\Bbb Z$ denote the ring of integers; then $\Bbb Z G$ denotes the integral
group ring of $G$. We say that a group $G$ has type $(FP)_n$ if there is
an exact sequence of $\Bbb Z G$-modules $P_i$ of the form $$\dots
\rightarrow P_n \rightarrow \dots \rightarrow P_1 \rightarrow P_0
\rightarrow
\Bbb Z$$ with the modules $P_0,\dots,P_n$ finitely generated and
projective.
(Here $\Bbb Z$ also denotes the trivial $\Bbb ZG$-module). If all the
modules
$P_i$ are finitely generated and projective then we say that $G$ has type
$(FP)_{\infty}$; if, further, the sequence is finite, we say that $G$ has
type
$(FP)$. The property $(FP)_1$ is equivalent to the property of being
finitely generated and the property $(FP)_2$ is implied by finite
presentation
but it is currently unkown whether the reverse implication is true.

We can now state the result.

\proclaim{Theorem} Let $G$ be a soluble group.
\roster
\item If $G$ is constructible then it has a finite rewriting system.
\item If $G$ has a finite rewriting system then it is of type
$(FP)_{\infty}$.
\endroster
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. \endproclaim

We delay the proof of \therosteritem1. The result \therosteritem2 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 $(FP)_{\infty}$; see, for
example,
[3]. It appears to be still an open question whether soluble groups of type
$(FP)_{\infty}$ 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 $(FP)_{\infty}$ by the stronger
but related property of being of type $(FP)$ 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.

\demo{Proof of part \therosteritem1 of the Theorem} By the observations
made
earlier, we can divide the proof into two parts. We must show  \roster
\item
that a finite extension of a group with a finite complete rewriting system
again
has a finite complete rewriting system; and that  \item if $G$ has a finite
complete rewriting system, then an HNN-extension $H=<G,t:\phi(G) =
t^{-1}Gt>$,
where $\phi$ is a monomorphism of $G$ with finite cokernel, also has a
finite
complete rewriting system. \endroster

We begin with \therosteritem1. Suppose that $G$ has a finite complete
rewriting
system $(\Sigma,R)$ and that $G$ is a subgroup of finite index in a group
$H$.
Let $\Omega$ be a right transversal for $G$ in $H$ and let $\Sigma'=\Sigma
\cup
\Omega$; then $\Sigma'$ is finite. If $w \in (\Sigma')^*$ let $\bar w$
denote
the image of $w$ in $H$. 

Let $$R_1 = \{ (z_1z_2, uz_3);z_1, z_2 \in \Omega\}$$ where $\bar z_1\bar
z_2 =
\bar{u}\bar z_3$ in $H$ and $ u$ is $R$-irreducible. Also let 
$$R_2 = \{ (z_1s, uz_2);z_1\in \Omega, s \in \Sigma\}$$ 
where $\bar z_1\bar s =
\bar{u}\bar z_2$ in $H$ and $ u$ is $R$-irreducible. Then put $$R'=R\cup
R_1 \cup R_2.$$

We claim that $(\Sigma',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 $(\Sigma')^*$ 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 $(\Sigma')^*$ in the
form
$$u_{n+1}z_nu_n\dots u_2z_1u_1z_0u_0$$ where $z_i \in \Omega$ and $u_i \in
\Sigma^*$. Then we order two such words as follows: 
\roster 
\item by the number
$n$ of occurrences of elements of $\Omega$ if these are different; or, if
these
two values are the same, 
\item  by taking the lowest value of $i$ for which the
syllables $u_i$ differ and, if one rewrites under $(\Sigma,R)$ to the
other,
taking the former as the larger; or, if neither syllable rewrites to the
other,
\item by taking as larger an element with the syllable of greater length.
\endroster
 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 $\phi$ is a monomorphism of $G$
so that the image of $\phi$ is a subgroup of finite index in $G$. We wish
to show
that the HNN-extension $H = <G,t: \phi(g) = t^{-1}gt \text{ for all } g \in
G>$
also has a finite complete rewriting system. Firstly, note that because
$\phi$
is an isomorphism from $G$ onto $\phi(G)$, the latter also has a finite
complete
rewriting system. Since $\phi(G)$ has finite index in $G$, we can extend
this
finite rewriting system of $\phi(G)$ to one for $G$, as above, and so
obtain a
second finite complete rewriting system $(\Sigma',R')$ for $G$. Then
$\Sigma'$
is the union of a subset $\Sigma$ which generates $\phi(G)$ and a subset
$\Omega$
which is a transversal for $\phi(G)$ in $G$. Again, if $w \in  (\Sigma')^*$
let $\bar w$ denote the image of $w$ in $G$. 

We now describe the rewriting system for the HNN-extension $H$. Let 
$$\Sigma'' = \Sigma' \cup \{t,t^{-1}\}.$$
Let
$$R_1=\{(tt^{-1},1),(t^{-1}t,1)\}$$
and 
$$R_2= \{(t^{-1}u,\widetilde{\phi(u)}t^{-1}): u \in \Sigma'\}$$
where $\widetilde{\phi(u)}$ is the irreducible element of $(\Sigma')^*$ of
which the image in $G$ is the same as that of  $\phi(\bar u)$.
Similarly, let
$$R_3 = \{(tv,\widetilde{\phi^{-1}(v)}t): v \in \Sigma\}$$
where  $\widetilde{\phi^{-1}(v)}$ is the irreducible element of $\Sigma^*$
of
which the image in $G$ is the same as that of  $\phi^{-1}(\bar v)$. Note
that, as $\bar v \in \Sigma \subseteq \phi(G)$, the notation 
$\phi^{-1}(\bar v)$
is well-defined.

Let $R''=R' \cup R_1 \cup R_2 \cup R_3$. We claim that $(\Sigma'', R'')$ is
a
finite complete rewriting system for $H$. Firstly, note that the
$R''$-irreducibles are of the form
$$u_0t^{i_1}u_1t\dots u_nt^{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 $(\Sigma'')^*$ in the
form 
$$u_{n+1}s_nu_n\dots u_2s_1u_1s_0u_0$$ 
where $s_i \in \{t,t^{-1}\}$ and $u_i \in (\Sigma')^*$. 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.
\enddemo
(A more general and considerably more technical version of these results is
available in [6].)

\demo{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. 
\proclaim{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 ?  \endproclaim

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.
\proclaim{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. 
\endproclaim

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.
\proclaim{Question 3} Does every \fgm group have a regular complete
rewriting
system? \endproclaim
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.
\proclaim{Question 3$'$} Does the group generated by the matrices
$$\bmatrix 1&1\\0&1 \endbmatrix,\qquad \bmatrix 2/3&0\\0&1 \endbmatrix$$
have a regular complete rewriting system? \endproclaim
\enddemo
\Refs

\ref \no 1 \by \AA berg,  Hans 
\paper Bieri-Strebel valuations (of finite rank)
\jour Proc. London Math. Soc. (3)
\vol 52
\yr 1986
\pages 269--304
\endref

\ref \no 2 \by Anick, D.J.
\paper On the homology of associative algebras
\jour Trans. Amer. Math. Soc.
\vol 296
\yr 1986
\pages 641-659
\endref


\ref \no 3 \by Baumslag, G. and Bieri, R.
\paper Constructable solvable groups
\jour Math. Z.
\vol 151
\yr 1976
\pages 249--257
\endref


\ref \no 4 \by Brown, K. S.
\paper The geometry of rewriting systems:A proof of the Anick-Groves-Squier
Theorem 
\book Proceedings of the Workshop on Algorithms, Word Problems and
Classification in Combinatorial Group Theory, MSRI, Berkeley, 1989
\toappear
\endref

\ref \no 5 \by Groves, J. R. J.
\paper Rewriting systems and homology of groups
\book Proceedings of the Third International Conference on the Theory of
Groups, Canberra, 1989
\toappear
\endref

\ref \no 6 \by Groves, J. R. J. \& Smith, G. C.
\paper Rewriting systems and soluble groups
\paperinfo preprint
\yr 1989
\endref

\ref \no 7 \by Jantzen, M.
\book Confluent String Rewriting
\bookinfo EACTS monographs on Theoretical Computer Science
\vol 14
\publ Springer-Verlag
\yr 1988
\publaddr Berlin
\endref

\ref \no 8 \by Kropholler, P. H.
\paper Cohomological dimension of soluble groups
\jour 	J. Pure Appl. Algebra
\vol 43
\yr 1986
\pages 281--287
\endref

\ref \no 9 \by Le Chenadec, Ph.
\book Canonical forms in finitely presented algebras
\bookinfo Pitman, London; John Wiley \& Sons, New York
\yr1986
\endref


\ref \no 10 \by Sims, C. C.
\paper Verifying Nilpotence
\jour J. Symbolic Computation
\yr 1987
\vol 3
\pages  231-248
\endref


\ref \no 11 \by Squier, Craig C.
\paper Word problems and a homological finiteness condition for modules
\jour	J. Pure Appl. Algebra
\vol 49
\yr 1987
\pages 201-217
\endref
\endRefs


\enddocument \end

