3. Towards Gröbner Bases

However, MATPHI works in the setting of commutative polynomial rings using a Gröbner basis as input while TC belongs to the setting of groups using arbitrary relators and subgroup generators as input. In order to compare both methods, we have to use the generalized setting presented in Section 1 - binomial ideals in free group rings - and enable the new procedure to deal with possibly infinite generating sets in a finitary manner.

To encode the input of TC as binomials we associate the relators *R* and the subgroup
generators *U* with two sets of polynomials
and
.
Essentially we want to check whether the subgroup generated by
in
is finitely generated
and this will be done in an incremental fashion using the fact that for a given finitely generated subgroup
of a free group the membership problem can be solved using prefix Gröbner bases and the
generating subset of the subgroup is then enlarged by adding polynomials modified by left multiplication
with suitable group elements in order to ``approximate'' *N*(*R*).

To compute prefix Gröbner bases of subgroups in the free group ring
we need the concept
of weak prefix saturation:
A set
is called **weakly prefix saturated** if for every ,
we have
.
This becomes necessary as the ordering on
is no longer admissible (see [23] for the details).

The property of being weakly saturated can be ensured for a set of polynomials by using a procedure
to compute a saturating set for a polynomial, i.e. a set such that each right multiple of the polynomial
prefix reduces to 0 in *one* step by a polynomial in the saturating set.
For free groups there are saturating sets consisting of at most two polynomials called
and
.
In our setting of binomials *u* - *v*, informally
is gained from *u*-*v* by ``shortening'' the head term *u*
without losing its head
position while
is derived from
by forcing the shortened head term to lose its head position
by cutting off its last letter.
Then
and
where
,
and there exists
such that
,
,
and
.

**Procedure**: PREFIX GR¨OBNER BASES OF RIGHT IDEALS IN FREE GROUP RINGS

< tex2html_comment_mark>

Given:A finite set .Find:G, the monic reduced prefix Gröbner basis of the right ideal generated byF. [1ex]G:= ;whilethere is such that is prefixreducible bydoG:= ;f:= ; % Compute a normal form (if non-zero with head coefficient 1).ifthenG:= ;endifendwhile

Correctness and termination follow from the results presented in [23,16]. The procedure can be used to solve the subgroup problem for a subgroup in :

However, in general the subgroup
of
we are interested in is generated by the set
where the set of relators is *not* empty.
We have to find a way to treat this possibly infinitely generated subgroup of
in a finitary manner
in order to verify whether it is in fact finitely generated.
The normal closure of a set of relators *R* can be approached using a result similar to the one
presented in [11] to solve the ideal membership problem for two-sided ideals in solvable
polynomial rings using one-sided ideals (compare also Zharkov's idea to compute Janet bases in [27]).
For a set
let
denote the two-sided and
the right ideal generated by *F* in
.

- 1.
*F*is a prefix Gröbner basis of and .- 2.
*F*is a prefix Gröbner basis of and for all , we have .- 3.
*F*is a prefix Gröbner basis of and for all , we have .