6. Reduction in Polycyclic Group Rings

Let

- (a)
- , and
- (b)
- .

- 1.
- Let
.
Then there are polynomials
such that
and
*h*=*p*'-*q*'. - 2.
- Let 0 be a normal form of
*p*-*q*with respect to . Then there exists a polynomial such that and .

This can be shown as lemma 9.

q.e.d.

1.11
Gröbner bases as defined by Buchberger can now be specified for
left ideals in this setting as before.

A set is said to be a

Let be the group ring given in example 5. Then similar to example 7 for the polynomials

We show that for a finite set of terms , where without loss of generality

This will be done by induction on

In the base case

In the induction step let us assume

Now it remains to check the case where

q.e.d.

1.11
Notice that the proof of this lemma shows that there is an algorithm
which computes some
as desired in case it
exists and that the element *w* need not be known for this computation.
Hence we can enrich a polynomial by the set of those multiples which bring
other terms of the polynomial to head position.
But still there remain cases of multiples which are not lpc-reducible.
Just take a look at the polynomial *p* = *a*^{2}+*a* in our example.
Then the head term of the multiple
results from the head
term *a*^{2} of *p*, but still
is not lpc-reducible by *p*,
as *a*^{2} is no commutative prefix of *a*.
Therefore, let us consider some further special multiples.
For a polynomial *p* and a term
we call a term *s*
in a multiple
a *t***-term** if
.
The following lemma states that if in two left-multiples of a polynomial
the head terms result from the same term *t*, then there is also a
left multiple of the polynomial with a *t*-term as head term which is in
some sense a common commutative prefix of the head terms of the
original two multiples.
In example 9 for
and
,
both head terms result from the same term *a*^{2} and
the head term *a* of
is a commutative prefix of the
head term *a*^{2} of
.

Let

We show the existence of
by constructing a sequence
,
such that for
we have
with
and
.
Then for
our claim holds.

Let us start by constructing an element
such that
,
and
.

In case *i*_{1} = *j*_{1} or *j*_{1} =0 we can set *z*_{1} = *v* and
since
.
Similarly in case *i*_{1} = 0 we can set *z*_{1} = *u* and
since
.
Hence let us assume
and both are non-zero.

First suppose that
.
Notice that the proof does not depend on whether *a*_{1} is bounded or not.
Then if
we again set *z*_{1} = *v*
since for
our claim holds.
In case
|*j*_{1}| > |*i*_{1}| we set *z*_{1} = *u* because for
our claim holds.

Now let us proceed with the case
,
hence *a*_{1} cannot be bounded.
We construct
such that
as
.
We claim that the letter *a*_{1} has the same exponent for all
terms in
,
say *b*.
In case this holds, no term in the polynomial
will
contain the letter *a*_{1} and the distinguishing letter between
and the term
is at least of
index 2.
Furthermore we know
.
Thus by the construction given in the proof of
lemma 14 there exists an element
such that
and thus we can set
and
.

Hence it remains to prove that the exponents of *a*_{1} have the desired property.
Suppose we have the representatives
,
,
for the
terms
and
.
Then we know
since
.

Hence in showing that the case
is not possible we
find that the exponents of *a*_{1} in *s* and *t* are equal.
To see this, let us study the possible cases.
If *b*_{s} > 0 we have
and hence there exists no
such that
.
On the other hand *b*_{s} < 0 either implies *b*_{t} > 0 or
and
|*b*_{s}| > |*b*_{t}|).
In both cases there exists no
such that
*b*_{t} + *x* < 0 and
|*b*_{t} + *x*| > |*b*_{s} + *x*|.
Hence *b*_{t} = *b*_{s} must hold as we know that *t* can be brought to
head position by *u* respectively *v*
such that the exponents of *a*_{1} in
respectively
have different
sign.

It remains to show that there cannot exist a term
with
.
Let us assume such an *s*' exists.
Since
and
there
then must exist
such that
and
.
Without loss of generality let us assume *i*_{1} > 0 and *j*_{1} < 0 (the
other case is symmetric).
In case *b*_{t} < 0 we get that
*b*_{t} + *x*_{1} = *i*_{1} > 0 implies
*x*_{1} > |*b*_{t}| > 0.
Now, as
either implies
*b*_{s'} > 0 or
and
|*b*_{s'}| < |*b*_{t}|), we find
*b*_{s'} + *x*_{1} > *b*_{t} + *x*_{1} contradicting
.
On the other hand, in case *b*_{t} > 0 we know
.
Furthermore,
*b*_{t} + *x*_{2} = *j*_{1} < 0 implies *x*_{2} <0 and
|*x*_{2}| >
*b*_{t}.
Hence we get
*b*_{s'} + *x*_{2} < 0 and
|*b*_{s'} + *x*_{2}| > |*b*_{t} + *x*_{2}|
contradicting
.

Thus let us assume that for the letter *a*_{k-1} we have
constructed
such that
with
,
and
.
We now show that we can find
such that
with
and
.

This will be done in two steps.
First we show that for the polynomials
and
with head terms
respectively
we can find an element
such that
,
and
with

Then in case we are done and set and . Else we can similarly proceed for the polynomials and with head terms respectively and find an element such that for we have , and with

Then we can conclude as in case

Let us hence show how to construct

First let us assume that . Without loss of generality we can assume that

Finally, we have to check the case that and . Notice that in this case the letter

q.e.d.

1.11
These two lemmata now state that given a polynomial, we can construct
additional polynomials, which are in fact left multiples of the
original polynomial, such that every left multiple of the
polynomial is lpc-reducible to zero in one step by one of them.
Such a property of a set of polynomials is called (lpc-) saturation.
In example 9 the multiples
and
give us a lpc-saturating
set for *p* = *a*^{2}+*a*.

A set is called a

llProcedureLEFT-POLYCYCLIC SATURATIONGiven:A non-zero polynomial .Find:, a lpc-saturating set forp.for alldoS_{t}:= ;iftcan be brought to head positionthencompute withH_{t}:= ; % These are candidates for ``smaller'' polynomials witht-head termsq:= ;S_{t}:= ;endifendfor:= %Scontains at most polynomials

Notice that this is only a naive procedure and more structural information should
be used, e.g. to rule out unnecessary candidates from the sets *H*_{t}.

This can be shown as in the proof of lemma 12.

q.e.d.

1.11
Let us now proceed to characterize left Gröbner bases by so-called s-polynomials corresponding to lpc-reduction.

For such that and with either or for we can define an

the situation for some

We now can give a characterization of a left Gröbner basis in a familiar way using the concept of lpc-saturation.

- 1.
- For all polynomials we have .
- 2.
- For all polynomials we have .

Again we can follow the lines of the proof given for the similar theorem 3 for nilpotent groups and qc-reduction.

q.e.d.

1.11
It is also possible to give a characterization of left Gröbner bases in terms of standard representations.

- 1.
- For all polynomials we have .
- 2.
- Every has a left commutative prefix standard representation.
- 3.
*G*is a left commutative prefix standard basis.- 4.
*G*is a left Gröbner basis.

ProcedureLEFT GR¨OBNER BASES IN POLYCYCLIC GROUP RINGSGiven:A finite set of polynomials .Find:, a left Gröbner basis of .G:= ;%Gis lpc-saturated andB:= ;whiledo% Test if statement 2 of theorem 7 is valid (q_{1},q_{2}) := ;% Remove an element using a fair strategyifh:= existsthenh' := ; % Compute a normal formif% The s-polynomial does not reduce to zerothenG:= ;%Gis lpc-saturated andB:= ;endifendifendwhile

The set *G* enumerated by this naive procedure fulfills the requirements of
theorem 7, i.e., the set *G* at each stage generates
and is lpc-saturated.
Using a fair strategy to remove elements from the test set *B* ensures
that for all polynomials entered into *G* the s-polynomials are considered
in case they exist.
Hence, in case the procedure terminates, it computes a left Gröbner basis.
The next theorem states that every left Gröbner basis contains a finite one and hence this procedure must terminate.

Since lpc-reduction is based on commutative prefixes this can be shown using Dickson's lemma as in the proof of theorem 5.

q.e.d.

1.11
Let us now continue to show how again Gröbner bases of two-sided
ideals can be characterized by left Gröbner bases which have
additional properties.
We will call a set of polynomials a **Gröbner basis** of the
two-sided ideal it generates, if it fulfills one of the equivalent
statements in the next theorem.

- 1.
*G*is a left Gröbner basis and .- 2.
- For all we have .
- 3.
*G*is a left Gröbner basis and for all , we have .- 4.
*G*is a left Gröbner basis and for all , we have .

This can be shown as in the proof of theorem 4.

q.e.d.

1.11
Statement 4 enables a constructive approach to use procedure LEFT GR¨OBNER BASES IN POLYCYCLIC GROUP RINGS in order to compute
Gröbner bases of two-sided ideals and item 2 states that such bases
can be used to decide the membership problem for the two-sided ideal
by using lpc-reduction.
The following corollary similar to theorem 7
can be used as the foundation
of a procedure to compute two-sided Gröbner bases.

- 1.
- For all polynomials we have .
- 2.
- (a)
- For all polynomials we have .
- (b)
- For all , we have .

Notice that so far we only have characterized lpc-saturated Gröbner bases. Of course there also exist Gröbner bases which are not lpc-saturated. It is even possible to introduce interreduction for lpc-reduction and to compute reduced Gröbner bases which are unique in case we demand that the polynomials are monic, i.e., they have head coeffient 1.

We call a set of polynomials

The proof again can be done using standard techniques as in the case of ordinary polynomial rings.

q.e.d.

1.11
Such reduced Gröbner bases can be computed by incorporating interreduction
into the respective procedures.

Let us close this section by sketching a possible approach to
treat right ideals in polycyclic group rings.
As seen in section 2 a stability property for right
multiples need not hold when using the idea of commutative prefixes for
reduction if
is given by a convergent PCP-presentation.
Furthermore, Wißmann's result given in section 4
for the existence of only -confluent bases in case
the group is given by a convergent PCP-system, states that in general
no finite Gröbner bases will exist when using weakenings of strong
reduction and every reduction based on commutative prefixes and using
right multiples is such a weakening.
Anyhow, a similar approach is possible in case we change the presentation of
our polycyclic group.
Let
be a convergent PCP-presentation of a polycyclic
group.
Then the presentation
,
where
and
,
,
is again a polycyclic power presentation which is convergent^{15}
with respect to the syllable ordering now with status right, i.e.,
the syllables are compared from the right to the left.
Such a presentation will be called a **reversed polycyclic power
commutation presentation** (with status right).
The irreducible elements now are reversed ordered words of the form
,
i.e.,
,
where we define
recursively by
,
and
.
We can show similar
properties as in the case of Wißmann's PCP-presentations.

Let

- (a)
- , and
- (b)
- .

- 1.
- Let
.
Then there are
such that
and
*h*=*p*'-*q*'. - 2.
- Let 0 be a normal form of
*p*-*q*with respect to . Then there exists a polynomial such that and .

A set is said to be a

A set is called an

For such that and with either or for , we can define an

the situation for some gives us

- 1.
- For all polynomials we have .
- 2.
- For all polynomials we have .

Let us close this section by showing how in fact reversed polycyclic power commutation presentations and rpc-reduction yield a solution to the subgroup problem in polycylic groups giving rise to confluent bases of the subgroup.

Let be the group specified on page now presented by a convergent