2. Basic Definitions

For a subset *F* of
we can specify special
subsets of
as follows:
We call the set
the **right ideal**^{3},
the **left ideal**, and
the **two-sided ideal** generated by *F*.

As we are interested in constructing Gröbner bases for ideals in
,
we need an appropriate
presentation of the group
in order to do computations.
Structures which can be used to present
groups are **semi-Thue systems** (also called
**string-rewriting systems**).
Let us start with some basic definitions.
For a finite alphabet ,
will denote the set of all **words** over the
alphabet
where
presents the
**empty word**, i.e.,
the word of length zero.
will denote the **identity** on .
A **semi-Thue system**
*T* over
is a subset of
.
The elements (*l*,*r*) of *T* are called
**rules** and will often be
written as
.
The **single-step reduction relation**
on
induced
by a semi-Thue system *T* is defined as follows:
For any *u*,*v* in ,
if and only if there exist
*x*,*y* in
and (*l*,*r*) in *T* such that
and
.
The **reduction relation**
on
induced by *T* is the
reflexive transitive closure of
and is denoted by
.
The reflexive transitive symmetric closure is
denoted by
.
If
holds then one says that *u* reduces to *v*.
In case *u* has no descendant except itself it is called **irreducible**.
The reduction is called **Noetherian** if and only if there is no
infinite chain
.
We speak of **confluence** if for all *u*,*v*,*w* in ,
and
imply the existence of *z* in
such that
and
.
A semi-Thue system is called **convergent** if it is both, Noetherian
and confluent, i.e., unique normal forms exist for the irreducible elements.

Let be an alphabet. A mapping is called an

An equivalence relation on
is said to be a congruence
relation in case it is admissible, i.e., compatible with
concatenation.
Since this is obviously true for the reduction relation induced by a
semi-Thue system *T*, the reflexive transitive symmetric closure
is a congruence relation on the set ,
the **Thue
congruence** .
The congruence classes are denoted by
and we can set
.
In fact
is the factor monoid of the free monoid
modulo the congruence induced by *T* as the following lemma
establishes.

Let be a finite alphabet and for we define the subsets , . We first distinguish several particular classes of rules over .

Let ,

For a subset

- 1.
*C*contains only CX-rules, and- 2.
- for all
and for all
there
is exactly one rule
in
*C*.

For a rule where , is called a

- 1.
*P*contains only positive and negative P-rules.- 2.
- For all
there is a negative P-rule
in
*P*if and only if there also is a positive P-rule of the form with in*P*. - 3.
- For all
there is at most one negative P-rule
and at most
one positive P-rule
in
*P*.

- 1.
- is Abelian if and only if there is a PCAB-system presenting .
- 2.
- is nilpotent if and only if there is a PCNI-system presenting .
- 3.
- is polycyclic if and only if there is a PCP-system presenting .

Using a **syllable ordering** Wißmann has shown that a PCX-system
is
a Noetherian string-rewriting system and he gave a completion procedure for such systems
which terminates with an output that is again a PCX-system of the same type.

Let be an alphabet and a partial ordering on . We define an ordering on tuples over as follows:

Let . Then every can be uniquely decomposed with respect to

where

One can show that using the syllable ordering for orienting *T* we get

For example the semi-Thue system where such that we have and is a presentation of the free commutative group generated by and we have .

In restricting the syllable ordering introduced in definition
5 to ordered group words this gives us
if and only if for some
we
have *i*_{l} = *j*_{l} for all
and
with
if and only if
or
and
or
and
.
where > is the usual ordering^{5}
on
and for
,
if
,
if
and
if
.
We then call *a*_{d} the **distinguishing
letter** between the two ordered group words.

The next two technical lemmata are related to some properties of the wellfounded ordering and will be useful in the proofs later on.

In case

On the other hand,

q.e.d.

1.11

First let us look at the case

Now it remains to prove that the case is not possible.

First suppose

Hence let us suppose

q.e.d.

1.11

The following lemma is an easy observation on the results of multiplying a letter by special ordered group words.

- 1.
- Let be a nilpotent group with a convergent PCNI-presentation . Further for some let , . Then we have and for some .
- 2.
- Let be a polycyclic group with a convergent PCP-presentation . Further for some let . Then we have for some .

This follows immediately from the rules given in the respective presentations.

q.e.d.

1.11

We now define a new ordering on
called a **tuple ordering**, which
will be crucial in our definitions of reduction.

For two elements , we define if for each we have either

The tuple ordering can be used to specify special representations of right and left ideal elements and special bases of them.

Let

- 1.
- A representation

is called a**right commutative prefix standard representation**in case for the respective head terms we have and for all . In our previous work this was also called a**quasi-commutative (qc-) standard representation**. - 2.
- A representation

is called a**left commutative prefix standard representation**in case for the respective head terms we have and for all . Again for historical reasons this is sometimes called a**left polycyclic (lpc-) standard representation**.

Let

To show that
we now have to distinguish two cases.
If the letter *a*_{d} has unbounded exponents, we can apply lemma 2 since
and
hold (the latter follows as
).
Hence let us assume the letter *a*_{d} is bounded, i.e.,
we know
,
and
since
must also hold we get
and
.
Now in case
*v*_{d} + *u*_{d} + *s*_{d} = *w*_{d} we are done, as then
implies
.
Else, as
,
for
*y* = *w*_{d} - *v*_{d} we know
with
and hence
and we are done.

q.e.d.

1.11
However, the next example shows that for PCP-presentations of groups this
in general no longer holds.

Let and be a polycyclic presentation of the free nilpotent group with two generators. Then for , and we have , . Now for we find , but and hence .

Still for groups with convergent PCP-presentations a similar stability property holds for left multiples.

Let

q.e.d.

1.11

Let us close this section by summarizing Sims' notions for presenting polycyclic
groups as given in chapter 9 of [Si94].
Let

be a polycyclic series for . For let

a_{j}a_{i} |
= | , | j>i, |

a_{j}^{-1}a_{i} |
= | , | j>i,
, |

a_{j}a_{i}^{-1} |
= | , | j>i,
, |

a_{j}a_{i}^{-1} |
= | , | j>i,
, |

a_{i}^{mi} |
= | , | |

a_{i}^{-1} |
= | , | |

a_{i}a_{i}^{-1} |
= | , | , |

a_{i}^{-1}a_{i} |
= | , | , |

where the right sides are collected words.
Every presentation which has this form defines a polycyclic group, but
there might be *a*_{i} such that
although there
is no relation of the form
or only a relation of
the form
with *n* > *m*.
If this is not true, the presentation is called **consistent**,
which then is a synonym for confluent.

The relations of such a presentation can be interpreted as rewriting rules over the alphabet with respect to the syllable ordering - here called wreath ordering - induced by the precedence . Then a consistent polycyclic presentation gives rise to a convergent PCP presentation.