Next: 4. Enumerating Cosets Using Up: A Note on Nielsen Previous: 2.2 The Todd-Coxeter Coset

# 3. Towards Gröbner Bases

In commutative polynomial rings there is a strong relation between Gröbner bases of an ideal and its quotient ring. In fact Gröbner bases enable computations in the quotient ring by normal form computations. The quotient is determined as a -vector space by the natural basis associated to the reduced Gröbner basis of the ideal. This natural basis consists of those commutative terms which are irreducible with respect to the Gröbner basis, i.e. it is a regular subset of the commutative terms (when viewed as a formal language). Of course such a vector space basis is strongly dependent on the ordering chosen for computing the Gröbner basis. In [8] the procedure MATPHI is presented which, given a reduced Gröbner basis, enumerates the natural basis: This is done systematically by initializing the natural basis to and the set of border elements to . While there are elements in B the minimal one is removed and it is checked whether it is irreducible with respect to the Gröbner basis. If this is the case for each new element added to N the border elements are added to B. On termination N contains the natural basis. Additionally MATPHI computes a multiplication table which for each and each variable Xi contains the result of the normal form computation . While in general the entries of this multiplication table are vectors, when restricted to binomial polynomials they can be interpreted as terms. Notice that then the output is similar to the one produced by TC where on termination we get a set of coset representatives and a multiplication table for all coset representatives g and .

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

Theorem 5 ([23])   A set is a prefix Gröbner basis of the right ideal it generates if it is prefix reduced and weakly prefix saturated.

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 by F.
[1ex]G :=

;
while there is
such that

is prefixreducible by

do
G :=

;
f :=

;
% Compute a normal form (if non-zero with head coefficient 1).
if
then 		G :=

;
endif
endwhile


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 :

Theorem 6 ([15])   Let U be the generating subset of a subgroup in . Then is an element of if and only if w prefix reduces to 1 using a prefix Gröbner basis of the right ideal generated by in .

In [23] it was shown how the computation of the monic prefix Gröbner basis as well as the resulting solution for the subgroup problem are related to Nielsen reduction:

Theorem 7   Let U be a finite subset of and G the monic reduced prefix Gröbner of the right ideal generated by in . Then the set is Nielsen reduced for U.

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 .

Theorem 8 ([16])   For the following properties are equivalent:
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 .

This theorem is the basis of a procedure which computes prefix Gröbner bases of two-sided ideals by iterating the computation of prefix Gröbner bases and extending them by multiplication with elements in until a prefix Gröbner basis of the two-sided ideal is computed. For a set of relators R, on input this is equivalent to computing a prefix Gröbner basis of an encoding of the the normal closure of R and it halts if and only if the subgroup generated by N(R) in is finitely generated. This will be a special case of the procedure presented in the next section.

Next: 4. Enumerating Cosets Using Up: A Note on Nielsen Previous: 2.2 The Todd-Coxeter Coset
| ZCA Home | Reports |