3. Solving the Submodule Problem in Polycyclic Group Rings

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 *a*_{1}.
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 *a*_{1} 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
terminate^{6}.
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 *a*^{j}*h*, where
.
In this way,
can be expressed as *b*_{i}*a*^{j}*h*.
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 *la*^{j} where
.
When this is done, every element of
can be described as

where , and , . In case the element is called a

Let

Let

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 *a*_{1}, *a*_{2}, and *a*_{3}).
Then for the right ideal *M* of
generated by the set
,
the
membership problem can be solved using the
-basis
for *M*_{1}.
In the next section we will see that a Gröbner basis in our sense will contain one more
polynomial, namely
*a*_{1}^{-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 be a group ring with presented by and . Further let , then

Hence we have the situation that

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 thatThis 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.u,v, and such that . Ifxanduare aligned, then .

LetThen 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:fbe a nonzero element of . There is a unique subset of such that the following hold:The cardinality of is at most 2

- 1.
- Each element of has the form with .
- 2.
- If
xis inU, then for a unique pair (y,g) such thatgis in ,yis inU, andyis aligned with the leading monomial ofg.^{m}.

llFunctionSYMMGiven:A finite subsetTof .Find:, the symmetrized set forT. Begin ; Fori:=mdown to 1 do begin ; Forfin do begin Letube the leading monomial off; Let and be the algebraically largest and smallest exponents, respectively, ona_{i}occurring in any monomialvofffor which the exponents on invagree with the corresponding exponents inu_{i}; If then Else begin Let be the greatest integer in^{8}; End End; End; Forfin do Iffhas negative leading coefficient then replacefby -fin ; End

For example the symmetrized set^{9}
of the polynomial
is
.

Now reduction using *sets which are their own symmetrized sets* is
specified by the following procedure:

llFunctionREDUCEGiven:A finite subsetTof which is its own symmetrized set. A non-zero polynomialfin .Find:An elementgofI+fis returned, whereIis the ideal of generated byT. The elementgis irreducible with respect to the set of products , wherehis inT,yis inU, andyis aligned with the leading monomial ofh. Begini:= 1;g:=f; % At all times . Ifg=0 thens=0. While do If there is an elementhinTsuch that the leading term ofhsatisfies and , whereyis inUandyandvare aligned, then begin Let , whereqandrare integers and ; ; % Recomputesand the terms with . End Elsei:=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:

LetFor a critical pair (fandgbe elements of with leading termuandv, respectively, and assume thatuandvare aligned. Let , , and . The leading monomial of and isw. Suppose . Then is a critical pair.

Now Gröbner bases can be computed as follows:

llFunctionGR¨OBNERGiven:A finite subsetTof .Find:A Gröbner basis for the ideal of generated byT. BeginB:= SYMM(T); LetCbe the set of critical pairs obtained fromB; WhileCis not empty do begin Remove a critical pair (f,g) fromC;h:= REDUCE (B,t(f,g)); If then beginS:=SYMM; Form all critical pairs obtainable from an element ofSand an element ofBand add these pairs toC; End End End

The output of this function will be a set which is both - a symmetrized set and a Gröbner basis.