Next: 6. Reduction in Polycyclic
Up: Introducing Reduction to Polycyclic
Previous: 4. On the Relations
5. Reduction in Nilpotent Group Rings
Let
be a nilpotent group given by a convergent PCNIpresentation as
described in section 2.
The next example illustrates that no total, wellfounded admissible
ordering can exist for a nontrivial group due to the
existence of inverses.
Example 5
Let
and
be a presentation of a group
.
Let
denote the rational numbers.
Suppose we simply require divisibility of the head term to allow reduction.
Then we could reduce the
polynomial
at the monomial
a^{2} by the polynomial
a^{1} +
a as
.
This would give
and the polynomial

a^{4} + 1 likewise would be reducible by
a^{1} +
a at the monomial 
a^{4} causing an
infinite reduction sequence.
Hence we will give additional restrictions on the divisibility
property required to allow reduction in order to prevent that a monomial
is replaced by something larger.
Since
in general is not commutative, we will at first restrict ourselves
to right multiples to define reduction.
How reduction using left multiples can be done is outlined in section
6 for the more general case that
is given as a
convergent PCPpresentation.
Definition 9
Let
p,
f be two nonzero polynomials in
.
We say that
f quasicommutatively (qc) reduces p to
q at
a monomial
of
p in one step, denoted by
,
if
 (a)

,
and
 (b)

.
Quasicommutative reduction by a set
is denoted by
and abbreviates
for some
.
Notice that if f qcreduces p at
to q,
then t no longer is a term in q and by lemma 5, p > q holds.
This reduction is effective, as it is possible to decide, whether we have
.
Further it is Noetherian and the translation lemma holds.
Lemma 9
Let F be a set of polynomials in
and
some
polynomials.
 1.
 Let
.
Then there are
such that
and h=p'q'.
 2.
 Let 0 be a normal form of pq with respect to
.
Then there exists a polynomial
such that
and
.
Proof :
1.11.1
 1.
 Let
,
where
and
,
i.e.
is the
coefficient of t in pq.
We have to distinguish three cases:
 (a)

and
:
Then we can eliminate the term t in the polynomials
p respectively q by qcreduction. We then
get
and
,
with
,
where
and
are
the coefficients of t in p respectively q.
 (b)

and
:
Then we can eliminate the term t in the polynomial
p by qcreduction and get
and q = q'.
 (c)

and
:
Then we can eliminate the term t in the polynomial
q by qcreduction and get
and p = p'.
In all cases we have
.
 2.
 We show our claim by induction on k, where
.
In the base case k=0 there is nothing to show.
Hence, let
.
Then by (1) there are polynomials
such that
and h=p'q'.
Now the induction hypothesis for
yields
the existence of a polynomial
such that
and
.
q.e.d.
1.11
In case
is a free Abelian group, qcreduction coincides with Sims'
reduction for Laurent polynomials, as the condition
implies
that
is aligned with
.
Notice that in the general nilpotent case u and
no longer need
to be aligned.
Furthermore the following example shows that even if they are aligned,
Sims' definition of reduction
cannot be carried over to nilpotent groups.
Example 6
Let
and
be
a convergent PCNIpresentation of the free nilpotent group on two
generators.
Then for
a_{1}a_{2} and
a_{1}a_{3} due to Sims' ordering we get
,
but for the aligned
elements
a_{1} and
a_{1}a_{3} we find
,
while
,
and hence
.
Gröbner bases as defined by Buchberger can now be specified for
right ideals in this setting as follows.
Definition 10
A set
is said to be a
right Gröbner basis, if
,
and
is confluent.
Since Buchberger's reduction always captures the ideal congruence, in order to
characterize Gröbner bases he only has to give a confluence criteria.
Now we find that in our setting we have to be more careful, as for
qcreduction
in general will
not hold.
One reason for this phenomenon is that a reduction step is not preserved under
right multiplication with elements of .
Example 7
Let
be the group ring given in example
5.
Then for the polynomials
p =
a^{2} +
a and
we find that
p is qcreducible by
f.
This is no longer true for the multiple
.
Notice that, since
,
we have
,
but
does not hold.
We will now introduce how we can extend the expressiveness of
qcreduction.
We start by enabling the reducibility of special monomial multiples
of a polynomial by allowing to use not only the
polynomial itself but a special set of polynomial multiples for qcreduction.
First let us take a look at what multiples are appropriate to later
on enable an effective characterization of a right Gröbner basis.
As our example shows, we have to pay attention to the problem that
different terms of a polynomial can
come to head position by right multiplication with group elements.
The next lemma states how right multiples which bring other terms to head position can be constructed in case they exist.
Lemma 10
Let p be a nonzero polynomial in
.
In case there exists an element
such that
for some
, let a_{d} be the distinguishing
letter between t and
.
Then one can construct an
element
such that
.
In particular, given p and
it is decidable whether there
exists an element
such that
.
Proof :
1.11.1
We show that for all polynomials
the
following holds:
In case
for some
,
then one can construct an element
where a_{d}
is the distinguishing letter between t_{i} and
,
and
.
This will be done by induction on k where d = nk.
In the base case let k=0, i.e., a_{n} is the
distinguishing letter between
and
.
Hence 1_{j} = i_{j} for all
and
.
By our assumption there exists
such that
,
with
,
,
and there exist
such that
and
.
Thus
or, in case a_{n} is bounded by
,
must hold.
First let us assume that the letter a_{n} is not bounded.
Then let us set
.
We show that for all
we
have
.
Note that for all t_{j} with prefix
we have
,
as
right multiplication with
only changes the exponent of a_{n} in
the respective term.
It remains to look at those terms t_{j} with
.
Then we can apply lemma 3 as we have
,
and as seen above there exists an element x such that
and
.
Therefore
and our claim must hold.
In case the letter a_{n} is bounded by m_{n}, we set
.
As before, for all t_{j} which have a prefix
we have
.
Tor those t_{j} with prefix
we know that the exponent of a_{n} in
cannot be m_{n} 1 unless
t_{j} = t_{i}, and hence
must hold.
In the induction step let us assume that for all polynomials
and
with
,
if the distinguishing letter a_{d}
between
and t_{i} has index
there exists
an element
such that
.
Now for
,
with
let us assume that the distinguishing letter
between
and t_{i} has index d = nk.
Since
,
for
with
,
,
we know that there exist
and
such that
and similarly
.
As
then
or,
in case a_{n} is bounded by
,
must hold.
In case a_{d} is not bounded we can then set
.
We have to show that for all
there exists
such that we
have
.
Note that for all t_{j} with prefix
we have
,
as
right multiplication with
has no influence on the prefix
in
.
Therefore, it remains to look at those terms t_{j} with
and
.
Since there further exists
such that
and
we can again apply lemma 3
to show our claim.
In case
we are done.
Else we get i_{d} = j_{d} and can apply the induction hypothesis since
the distinguishing letter between
and
will be of
index greater than d, yielding an element
and we can set
.
Now it remains to look at the case that a_{d} is bounded by m_{d}.
Then we can set
and proceed to construct
v as above.
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 qcreducible
by this set of polynomials due to the fact that the ``divisibility''
criteria for the head term does not hold.
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 qcreducible by p, since
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 tterm if
.
The following lemma states that if in two right multiples of a polynomial
the head terms result from the same term t, then there is also a
right multiple of the polynomial with a tterm as head term which is in
some sense a common commutative prefix of the head terms of the
original two multiples.
In example 7 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
.
Proof :
1.11.1
Let p,
and
be as described in the lemma and
let the letters corresponding to our presentation be
.
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 nonzero.
First suppose that
.
Notice that the construction in this case 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
,
i.e., 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 lemma 14 there exists an element
such that
and thus we can set
z_{1} = a_{1}^{b}r and
.
Hence it remains to prove our initial claim.
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_{k1} 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 s_{k} = 0 we are immediately done and otherwise we get
and
.
Let us hence show how to construct w_{1}.
Remember that
and
for some
.
In case i_{k} = l_{k} or l_{k} = 0 we can set
and
as
.
Hence let
and
.
First let us assume that
.
Then in case
we are done by setting
as again
will do with
.
Therefore, let us assume that
l_{k} > i_{k}.
Without loss of generality let us assume that a_{k} is not bounded^{12}.
Then we consider the multiple
,
i.e., the exponent of the letter a_{k} in the term
will be i_{k}.
If
we are done because then
for some
and we can set
w_{1} = a_{k}^{lk+ik} and
.
Otherwise we show that the tterm
in this multiple can be brought
to head position using an element
thus allowing
to set
and
w_{1} = a_{k}^{lk+ik}r as then we have
where
.
(Note that the product of two elements in
is again an element in
)
This follows immediately if we can prove that the exponent of a_{k} in
the term
is also i_{k}.
Then we can apply lemma 14 to the polynomial
and the term
.
Note that
and
have then distinguishing letter of at least index k+1 and
further
.
Therefore, we show that the exponent of a_{k} in
the term
is also i_{k}.
Let
with
be the term in
that became head
term (note that a candidate in
for the head term in
must have prefix
since
and multiplication with
a_{k}^{lk +
ik} only involves r_{k1}),
i.e.,
for some
and therefore
.
Then by lemma 4
there exist
and
such that
for some
and
,
i.e.,
for some
.
Note that the tterm is brought to head position by this
multiplication.
Now multiplying
by
z_{1}z_{2} we find
for some
.
This gives us
and thus
yields
c_{k} = i_{k}.
Finally, we have to check the case that
,
i.e., a_{k} is
not bounded in this case, and
.
Let us take a look at the polynomial
,
i.e., the exponent of the letter a_{k} in the term
will be 0.
Suppose
,
for some term
,
,
i.e.,
c_{k} = b_{s}  l_{k}.
In case this head term is already the corresponding tterm
,
we are
done and we set
w_{1} = a_{k}^{lk} and
.
Now if we can show c_{k} = 0,
by lemma 14 the tterm
can be
brought to head position using an element in
since
the distinguishing letter between
and the term
then has at least index k+1 and we know
.
Hence, in showing that c_{k}=0 we are done.
As before there exist
and
such that
for some
and
,
i.e.,
for some
.
Remember that this multiplication brings the tterm to head
position.
Hence multiplying
by z_{1}z_{2}
we find
for
some
.
Thus we know
.
To see that this implies c_{k} = 0 we have to distinguish three cases.
Remember that
c_{k} = b_{s}  l_{k} and since our head term is an sterm
for some
we know
.
In case i_{k} = 0, we have
implying c_{k} = 0.
In case i_{k} > 0 then
implies
.
Furthermore, as l_{k} < 0 we have
l_{k} + i_{k} > i_{k} implying b_{s} < 0 and hence
.
But then
and
yields
c_{k} = b_{s}  l_{k} = 0.
On the other hand, i_{k} < 0 and l_{k} > 0 imply
and hence
b_{s}  l_{k} + i_{k} <0 yielding
.
Since
this inequation can only hold in case
c_{k} = b_{s}  l_{k} = 0.
q.e.d.
1.11
These two lemmata now state that given a polynomial, we can construct
additional polynomials, which are in fact right multiples of the
original polynomial, such that every right multiple of the
polynomial is qcreducible to zero in one step by one of them.
Such a property of a set of polynomials is called qcsaturation.
In example 7 the multiples
and
give us a qcsaturating set for p = a^{2}+a.
Definition 11
A set
is called a
qcsaturating set for a nonzero polynomial
p in
,
if for all
,
.
A set of polynomials
is called
qcsaturated, if for all
and
for all
,
.
A further consequence of the previous lemmata is that finite
qcsaturating sets exist and that they can be computed.
llProcedureQUASICOMMUTATIVE SATURATION
Given: A nonzero polynomial
.
Find:
,
a qcsaturating set for p.
for all
do
S_{t} := ;
if t can be brought to head position
then compute
with
H_{t} :=
;
% These are candidates for ``smaller'' polynomials with thead terms
q :=
;
S_{t} := ;
endif
endfor
:=
% S contains at most
polynomials
Notice that more structural information can be used to rule out unnecessary
candidates from the set H_{t} to make this procedure more efficient.
While in the free Abelian group case symmetrized sets and qcsaturation
are successfully used to repair the same deficiency such sets in general
will not coincide.
One reason is that Sims uses a different ordering on his elements.
For example a qcsaturating set for the polynomial
on page is
while the symmetrized set consisted of the polynomials
.
Lemma 12
For a saturated set F of polynomials in
,
holds.
Proof :
1.11.1
is an
immediate consequence of the definition of qcreduction.
To show that the converse also holds, let
.
Then
and we show that
by induction on m.
Without loss of generality we can assume that for every
multiple
,
holds.
In case m=0 we are done as then p=q.
Hence let
.
Then the induction hypothesis yields
.
Now let
and
.
Furthermore, let
respectively
be the coefficient of t
in q respectively
.
Then in case
we get
.
In case
we similarly get
.
As
the
induction hypothesis yields
and hence we are done.
Otherwise
let
be the coefficient of t in
and
the coefficient of t in q.
This gives us a qcreduction step
eliminating the occurrence of t in
.
Then obviously
and, therefore, we have
,
i.e.,
q and
are joinable.
q.e.d.
1.11
Let us now proceed to characterize right Gröbner bases by socalled spolynomials corresponding to qcreduction.
Definition 12
For
such that
and
with either
or
for
we can define an
spolynomial, and setting
the situation
for some
gives us
Notice that
for
holds in case such an spolynomial exists.
Furthermore, if there exists a term t such that
and
,
an spolynomial always exists since then the condition for the existence of an spolynomial is fulfilled as the tupleordering requires that the exponent of a letter a_{i} in the tuplesmaller term is either zero or has the same sign as the exponent of a_{i} in the tuplelarger term.
We even have
.
Again for the case of free Abelian groups this definition corresponds to the definition of
critical pairs for Laurent polynomials and the resulting tpolynomials are
a specialization of these spolynomials for the integer group ring^{13}.
We now can give a characterization of a right Gröbner basis in a familiar way using the concept of qcsaturation.
Theorem 3
For a qcsaturated set
the following statements are equivalent:
 1.
 For all polynomials
we have
.
 2.
 For all polynomials
we have
.
Proof :
1.11.1
By definition 12 in case for
the spolynomial exists we get
and then
.
We have to show that every nonzero element
is
reducible to zero.
Without loss of generality we assume that G contains no constant polynomials, as then we are done at once.
Remember that for
,
implies
.
Thus as
is Noetherian
it suffices to show that every
is
reducible.
Let
be a
representation of a nonzero polynomial g such that
.
Since G is qcsaturated we can assume
,
where
and
.
Depending on this representation of g and our wellfounded
total ordering on
we define
and
K is the number of polynomials
containing t as a term.
Then
and
in case
this immediately implies that g is
reducible.
Otherwise we show that
g has a special representation (a standard representation
corresponding to qcreduction which is a right commutative prefix standard representation) where all terms are
bounded by
,
as this implies that g is
topreducible using G.
This will be done by induction on (t,K), where
(t',K')<(t,K) if and only if
or
(t'=t and K'<K).
Note that this ordering is wellfounded
since
is and
.
In case
there are two (not necessarily different) polynomials g_{k},g_{l} in the corresponding
representation
such that
and we have
,
.
Hence by definition 12 there exists an spolynomial
Next: 6. Reduction in Polycyclic
Up: Introducing Reduction to Polycyclic
Previous: 4. On the Relations
 ZCA Home 
Reports 