Let us start by giving an informal description of our procedure:
The input are encodings of the relators R and the subgroup generators U in
binomial sets
and
,
respectively.
All ring operations take place in
.
The following sets are used by the procedure:
On termination by construction N is either empty or a set of prefix closed coset representatives
with respect to the ordering >.
The latter is ensured as for each
added to N the set B contains all border elements
,
and removing the set of elements
from
N does not destroy the property of being prefix closed.
Moreover, we have the following important invariant for the case that R is not empty:
Let N_{o}, B_{o}, G_{o} denote the sets when starting the execution of the while loop and
N_{n}, B_{n}, G_{n} the ones at the end.
Then for the sets N_{n}, B_{n}, and G_{n} at the end of each loop
we have that for each w which is not prefix reducible by G_{n} one of the following three conditions holds:
 1.
 ,
or
 2.

,
and
,
,
or
 3.

,
,
and
,
.
This is true for the sets
and
before
entering the while loop.
Notice that due to the construction the elements prefix irreducible with respect to G_{n} are
a (not necessarily proper) subset of those prefix irreducible with respect to G_{o}.
In the loop first the smallest element
is removed from B_{o}.
If it is prefix reducible by G_{o} the new sets are N_{n} = N_{o},
and G_{n} = G_{o} and the property still holds, since then
cannot be a prefix of any element
not prefix reducible by G_{n}.
Now if
is not prefix reducible by G_{o} it is first added to N and its border elements are
added to B.
We get
,
and
.
Let w be prefix irreducible with respect to G_{n}.
Then w was also prefix irreducible with respect to G_{o} and we have to check the three possible cases:
 1.
 If ,
since w is still prefix irreducible by G_{n}
it cannot be in S, hence .
 2.
 If
,
and
,
,
as
we find
and either
or .
 3.
 If
,
,
and
,
,
again
as
we find
and
or
.
For nonempty R the procedure will only terminate when B becomes empty.
Then because of the invariant
the set N must contain all elements of
which are not prefix reducible by the final set G.
The next theorem now states that on termination the subgroup
generated by
in
is in fact finitely generated (by
).
G can be used to decide the subgroup problem for
by prefix reduction.
Moreover, if R is not empty,
G contains the respective (nontrivial) equations which are also generated by TC and
encode the multiplication table for the cosets with generators as follows: For each polynomial xa  y
where
,
we know that x and y are coset representatives
and the corresponding entry in the table for x and a is
.
Theorem 9
Let
R and
U be as specified above.
If procedure E
XTENDED T
C S
IMULATION terminates, then the subgroup
generated by
is finitely generated.
Proof:
If the set of relators is empty
is generated by U and we are done.
On the other hand, for nonempty R
on termination the set G contains a prefix Gröbner basis which
can be used to decide the subgroup membership problem for the subgroup
generated
by the set
in
(compare Theorem 6).
We have to show that
is in fact
,
the subgroup generated by
in
.
This is done by proving that for any
,
the element
is in
.
Let us assume
.
Then there is
minimal with respect to > such that for appropriate
we have
.
The case
immediately gives us a contradiction to our construction.
Therefore, by our invariant w cannot be irreducible by G as this would imply .
Hence let
such that w_{1} is the head term of some polynomial w_{1}  v in G.
Then we know
and
.
Now we get
and as w was a minimal counter example
.
But this implies
as
contradicting our assumption.
q.e.d.
1.11
Now, if
is finitely generated and contains a nontrivial normal subgroup then
has finite index in
(Proposition 3.11 in [14]).
Since TC terminates in case
has finite index in
it remains to show that this is also the
case for procedure EXTENDED TC SIMULATION.
Theorem 10
Let
R and
U be as specified above.
If the subgroup generated by
has finite index in
,
then procedure E
XTENDED T
C S
IMULATION terminates.
Proof:
Let the subgroup
generated by
in
have finite index.
If the set of relators is empty then there is nothing to show.
The set of coset representatives can for example be computed by enumerating the set of elements
which are not prefix reducible by the obtained prefix Gröbner basis G of the right ideal generated
by F_{U}.
Hence let us assume that R is not empty.
As
is finitely generated
is also finitely generated (Proposition 3.9 in [14])
and hence has a finite Schreier transversal S.
Then for ,
and every
there exists just one
such that
.
Since
for some
we have
.
The set
generates
(compare Chapter 1 in [10]).
But then
again
is a generating set for
as
.
Hence the procedure will terminate at least after checking the candidates
for .
q.e.d.
1.11
Reviewing Example 4 with
,
and
we get the output
and
which corresponds to the
nontrivial part of the multiplication table on page
when interpreting the polynomials as described above:
,
,
.
Notice that the set G does not give us the trivial relations as
or
for
.
They can be applied to make the multiplication table complete.
On the other hand G directly corresponds to the prefix string rewriting system in Example 4
by translating rules
into polynomials uv and vice versa.
Next: 5. Conclusions
Up: A Note on Nielsen
Previous: 3. Towards Gröbner Bases
 ZCA Home 
Reports 