Next: 4. On the Relations Up: Introducing Reduction to Polycyclic Previous: 2. Basic Definitions

# 3. Solving the Submodule Problem in Polycyclic Group Rings

In [Si94] Sims gives the following discussion for handling finitely generated right modules over the integral group ring of any polycyclic group , which is based on the work of Baumslag, Cannonito and Miller [BaCaMi81].

Let 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

where , and , . In case the element is called a polynomial and p is called the degree and c0 the constant term of the polynomial.
Let T be a finite subset of and let M be the -submodule generated by T. Since a is a unit in we can multiply each element in T by some power of a such that the resulting element is a polynomial, i.e., it has positive exponents in a only, and additionally we assume it has nonzero constant term c0. Given , let Mk be the set of polynomials in M with degree at most k, and let Ck be the set of coefficients of the term ak occurring in the polynomials in Mk. Let and . Then since also , we get with . Therefore, for , i.e., Ck is a -submodule of . Furthermore, holds.
Let d be the maximal degree of the polynomials in T (assuming that T has been modified to contain only polynomials as described above). Then one can show that Ck = Cd for . Moreover, knowing Md alone allows to solve the membership problem in M, as we can multiply every element by a power of a in order to turn it into a polynomial, say of degree k. Then in case k > d we check whether . If not we are done, since then . Else there exists an element with leading coefficient ck and we can reduce g by subtracting hak-d. Thus we may assume that which leaves us with the decision whether . How do we get to know Md? Let A be the -module generated by T, B respectively C the elements in A with degree at most d-1 respectively constant term 0. Then we have and, moreover, A=Md if and only if and .

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.

Example 2
Let be a group ring with presented by and . Further let , then p is a basis of the right -module as described by Sims. The polynomials and g = a + a-1 both do not belong to this right module. Now we have and we find that the polynomial'' is reducible'' to 0 using p, while neither of the polynomials'' f nor are reducible with respect to p.
Hence we have the situation that g and f are congruent with respect to the -module generated by p, but do not have the same normal form''.

Hence we cannot expect the resulting bases to be Gröbner bases in the strong sense that every element in has a unique normal form with respect to the module. In the following sections we show how for special cases Gröbner bases can be computed when using other definitions of reduction.

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:
1.
Each element of has the form with .
2.
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.
The cardinality of is at most 2m.
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:


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.

Next: 4. On the Relations Up: Introducing Reduction to Polycyclic Previous: 2. Basic Definitions
| ZCA Home | Reports |