be a polycyclic generating sequence for
together with a consistent polycyclic presentation for .
In case n=1, is cyclic and this case is well known.
Hence let us assume that n>1 and set . Then is normal in and is a cyclic group generated by the image of a1. By induction on n we may assume that we know how to describe submodules in the modules , . In order to show how this information can be lifted to we have to distinguish whether or not. In the following we abbreviate a1 by a.
First suppose , i.e., is finite and w.l.o.g. let . Then is isomorphic (as a -module) to , as if is a -basis for , then the set is a -basis of . Now, a -submodule M of is a -submodule if and only if M is closed under multiplication by a from the right. If is a generating set for M as a -module, then M is closed under multiplication by a if and only if is in M for all . Suppose the products do belong to M. A typical element g of M has the form , ,, . Then , and since and each , we get . If some is not in M, then we can add it to T and recompute the -submodule generated by T. Because the ascending chain condition holds, this process will terminate6. Since we can describe submodules of effectively, we can describe submodules of .
Now let us suppose that is infinite. Then is still a free -module, but with an infinite basis . Any element can be written uniquely in the form ajh, where . In this way, can be expressed as biajh. Thus elements of can easily be described as -linear combinations of the elements of U. However, it is also useful to write g in the form laj where . When this is done, every element of can be described as
Sims outlines how these membership problems can be treated using matrix methods. In example 8.3. he states how to compute such a basis in the group ring of the free nilpotent group (see example 1 for a presentation of this group on the letters a1, a2, and a3). Then for the right ideal M of generated by the set , the membership problem can be solved using the -basis for M1. In the next section we will see that a Gröbner basis in our sense will contain one more polynomial, namely a1-1 + 1.
Notice that the constructive discussion cited above states how a solution for the membership problem for modules in can be given using a solution for the membership problem for . Assuming that the solution is given by reduction methods - say given M, a -module, we can compute a basis B of the module such that g in M iff - we can the lift reduction similar to the case of polynomial rings over reduction rings. However, since elements of in order to decide membership have to be turned into polynomials, i.e., occurrences of a with negative exponents have to be made positive by multiplication with an appropriate power of a, for such a lifted reduction the translation lemma no longer holds.
Let us close this section by sketching how Sims introduces Gröbner bases for the special case of finitely generated free Abelian groups in section 10.7 of [Si94]. The group ring then is also called the ring of Laurent polynomials.
Let the free Abelian group be generated by and let the Laurent monomials , be ordered by a reverse lexicographic ordering (i.e. a lexicographic ordering comparing from the right to the left) in which the exponents are compared with respect to the ordering 7. The elements in U represent the group elements. Two elements and are called aligned, if for all . Then, although the ordering on the monomials is not consistent with multiplication, one can specify certain multiples for which multiplication is stable which is done in corollary 7.6.
Suppose that u,v, and such that . If x and u are aligned, then .This corollary is in fact comparable to the lemmata 5 and 6 specialized for free Abelian groups. The property ensures that multiplying a polynomial with a monomial whose term is aligned to the head term leaves the head term in head position. Hence defining reduction based on this property remains stable, but in general will not capture the ideal congruence. This can be repaired because of theorem 7.9.
Let f be a nonzero element of . There is a unique subset of such that the following hold:Then for a finite set one can define the symmetrized set as the union of the sets , , additionally assuming that all polynomials have positive leading coefficient. This in some sense corresponds to the fact that in the above proof of the Baumslag, Cannonito, Miller approach additionally to the condition one also has to ensure . Symmetrized sets can be computed as follows:
The cardinality of is at most 2m.
- Each element of has the form with .
- If x is in U, then for a unique pair (y,g) such that g is in , y is in U, and y is aligned with the leading monomial of g.
llFunctionSYMM Given: A finite subset T of . Find: , the symmetrized set for T. Begin ; For i := m down to 1 do begin ; For f in do begin Let u be the leading monomial of f; Let and be the algebraically largest and smallest exponents, respectively, on ai occurring in any monomial v of f for which the exponents on in v agree with the corresponding exponents in ui; If then Else begin Let be the greatest integer in8 ; End End; End; For f in do If f has negative leading coefficient then replace f by -f in ; End
For example the symmetrized set9 of the polynomial is .
Now reduction using sets which are their own symmetrized sets is specified by the following procedure:
llFunctionREDUCE Given: A finite subset T of which is its own symmetrized set. A non-zero polynomial f in . Find: An element g of I + f is returned, where I is the ideal of generated by T. The element g is irreducible with respect to the set of products , where h is in T, y is in U, and y is aligned with the leading monomial of h. Begin i := 1; g := f; % At all times . If g=0 then s=0. While do If there is an element h in T such that the leading term of h satisfies and , where y is in U and y and v are aligned, then begin Let , where q and r are integers and ; ; % Recompute s and the terms with . End Else i := i+1; End
Hence reduction of a polynomial p at a monomial by a polynomial f can be defined in case there exists u in U such that and u are aligned, , and . Then for , where q and r are integers and we get . Now critical pairs can be specified with respect to this reduction:
Let f and g be elements of with leading term u and v, respectively, and assume that u and v are aligned. Let , , and . The leading monomial of and is w. Suppose . Then is a critical pair.For a critical pair (f,g) let and where q and r are integers and . Then we set .
Now Gröbner bases can be computed as follows:
llFunctionGR¨OBNER Given: A finite subset T of . Find: A Gröbner basis for the ideal of generated by T. Begin B := SYMM(T); Let C be the set of critical pairs obtained from B; While C is not empty do begin Remove a critical pair (f,g) from C; h := REDUCE (B,t(f,g)); If then begin S:=SYMM; Form all critical pairs obtainable from an element of S and an element of B and add these pairs to C; End End End
The output of this function will be a set which is both - a symmetrized set and a Gröbner basis.