2. Basic Definitions

Let ${\cal G}$ be a group with binary operation $\circ$ and identity $\lambda$. The elements of a group ring ${\bf K}[{\cal G}]$ over a field ${\bf K}$ can be presented as polynomials $f = \sum_{g \in {\cal G}} \alpha_{g} \cdot g$ where only finitely many coefficients are non-zero. Addition and multiplication for two polynomials $f = \sum_{g \in {\cal G}} \alpha_{g} \cdot g$ and $h = \sum_{g \in {\cal G}} \beta_{g} \cdot g$ are defined as $f + h = \sum_{g \in {\cal G}} (\alpha_{g} + \beta_{g}) \cdot g$ and $f \ast h = \sum_{g \in {\cal G}} \gamma_{g} \cdot g$ with $\gamma_{g} = \sum_{x \circ y = g \in {\cal G}} \alpha_{x} \cdot\beta_{y}$. Polynomials will be written as finite sums $\sum_{i=1}^k \alpha_i \cdot t_i$ with $\alpha_i \in {\bf K}$ and $t_i \in {\cal G}$.

For a subset F of ${\bf K}[{\cal G}]$ we can specify special subsets of ${\bf K}[{\cal G}]$ as follows: We call the set ${\sf ideal}_{r}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, w_i \in {\cal G}\}$ the right ideal³, ${\sf ideal}_{l}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot w_i \ast f_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, w_i \in {\cal G}\}$ the left ideal, and ${\sf ideal}_{}^{}(F) = \{ \sum_{i=1}^n \alpha_i \cdot u_i \ast f_i \ast w_i \mid n \in {\bf N}, \alpha_i \in {\bf K}, f_i \in F, u_i, w_i \in {\cal G}\}$ the two-sided ideal generated by F.

As we are interested in constructing Gröbner bases for ideals in ${\bf K}[{\cal G}]$, we need an appropriate presentation of the group ${\cal G}$ 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 $\Sigma$, $\Sigma^*$ will denote the set of all  words over the alphabet $\Sigma$ where $\lambda$ presents the   empty word, i.e., the word of length zero. $\equiv$ will denote the  identity on $\Sigma^*$. A  semi-Thue system T over $\Sigma$ is a subset of $\Sigma^* \times \Sigma^*$. The elements (l,r) of T are called  rules and will often be written as $l \longrightarrow r$. The   single-step reduction relation on $\Sigma^*$ induced by a semi-Thue system T is defined as follows: For any u,v in $\Sigma^*$, $u \longrightarrow_T v$ if and only if there exist x,y in $\Sigma^*$ and (l,r) in T such that $u \equiv xly$ and $v \equiv xry$. The  reduction relation on $\Sigma^*$ induced by T is the reflexive transitive closure of $\longrightarrow_T$ and is denoted by $\mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$. The reflexive transitive symmetric closure is denoted by $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$. If $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v$ 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 $u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } v_1 \mbox{... ...} v_2 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } \ldots$. We speak of confluence if for all u,v,w in $\Sigma^*$, $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$ and $u \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } w$ imply the existence of z in $\Sigma^*$ such that $v \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$ and $w \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } z$. A semi-Thue system is called convergent if it is both, Noetherian and confluent, i.e., unique normal forms exist for the irreducible elements.

Definition 1    
Let $\Sigma$ be an alphabet. A mapping $\imath: \Sigma \longrightarrow\Sigma$ is called an  involution if $\imath(\imath(a)) = a$ for all $a \in \Sigma$. A semi-Thue system is called a  group system if there exists an involution $\imath$ such that for all $a \in \Sigma$ the rules $(\imath(a)a, \lambda)$ and $(a\imath(a), \lambda)$ are included in T. $\diamond$

Note that sometimes we will assume that $\Sigma = \Gamma \cup \Gamma^{-1}$ where $\Gamma^{-1} = \{ a^{-1} \mid a \in \Gamma \}$ contains the formal inverses of $\Gamma$ and T contains the rules corresponding to the trivial relations in a group, namely $\{ (aa^{-1}, \lambda) , (a^{-1}a, \lambda) \mid a \in \Gamma \}$.

An equivalence relation on $\Sigma^*$ 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 $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$ is a congruence relation on the set $\Sigma^*$, the Thue congruence . The congruence classes are denoted by $[w]_T = \{ v \in \Sigma^* \mid v \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ } w \}$ and we can set ${\bf M}_T = \{ [w]_T \mid w \in \Sigma^* \}$. In fact ${\bf M}_T$ is the factor monoid of the free monoid $\Sigma^*$ modulo the congruence induced by T as the following lemma establishes.

Lemma 1    
Let $(\Sigma, T)$ be a semi-Thue system.

1.

The set ${\bf M}_T$ together with the binary operation $\circ : {\bf M}_T \times {\bf M}_T \longrightarrow{\bf M}_T$ defined by $[u]_T \circ [v]_T = [uv]_T$ and the identity $[\lambda]_T$ is a monoid, called the   factor monoid of $\Sigma^*$ and $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{T}\,$ }$.

2.

In case T is a group system, the set ${\bf M}_T$ together with $\circ$, $[\lambda]_T$ and ${\sf inv}$ is a group, where ${\sf inv}\/([w]_T) = [{\rm inv}(w)]_T$, and ${\rm inv}(\lambda) = \lambda$, ${\rm inv}(wa) = \imath(a){\rm inv}(w)$ for all $w \in \Sigma^*$, $a \in \Sigma$.

Hence, semi-Thue systems are means for presenting monoids and groups. The following definitions are closely related to describing monoids and groups in terms of generators and defining relations. We call a pair $(\Sigma, T)$ a    presentation of a monoid (group) ${\cal M}$ if ${\cal M}\cong {\bf M}_T$. Note that every monoid can be presented by a (even convergent) semi-Thue system. Just let $\Sigma$ be the (possibly infinite) set of all elements and T the multiplication table. The problem is that this presentation in general is neither finite nor recursive. We call a monoid (group) ${\cal M}$  finitely generated, if ${\cal M}$ has a presentation $(\Sigma, T)$ such that $\Sigma$ is finite. ${\cal M}$ is said to be  finitely presented, if additionally T is finite. In order to do effective computations in our monoid or group we have to be able to compute representatives for the congruence classes of the elements. A very nice solution occurs in case we are able to give convergent finite semi-Thue systems as presentations, since then every congruence class has a unique representative and many problems, e.g. the word problem, are algorithmically solvable. The class of polycyclic groups, which include the Abelian and nilpotent groups, allow convergent presentations⁴. The following notations are taken from [Wi89].

Let $\Sigma = \{a_1,a_1^{-1}, \ldots, a_n, a_n^{-1} \}$ be a finite alphabet and for $1 \leq k \leq n$ we define the subsets $\Sigma_{k} = \{ a_i, a_i^{-1} \mid k \leq i \leq n \}$, $\Sigma_{n+1} = \emptyset$. We first distinguish several particular classes of rules over $\Sigma$.

Definition 2    
Let $i,j \in \{ 1, \ldots, n \}$, j>i and $\delta, \delta' \in \{ 1, -1 \}$.

1.

A rule $a_j^\delta a_i^{\delta'} \longrightarrow a_i^{\delta'} a_j^\delta$ is called a   CAB-rule (Abelian).

2.

A rule $a_j^\delta a_i^{\delta'} \longrightarrow a_i^{\delta'} a_j^\delta z$, $z \in \Sigma_{j+1}^*$ is called a   CNI-rule (nilpotent).

3.

A rule $a_j^\delta a_i^{\delta'} \longrightarrow a_i^{\delta'}z$, $z \in \Sigma_{i+1}^*$ is called a   CP-rule (polycyclic). $\diamond$

Definition 3    
For ${\rm X} \in \{ \mbox{AB, NI, P} \}$ a subset C of $\Sigma^* \times \Sigma^*$ is called a commutation system if

1.

C contains only CX-rules, and

2.

for all $1 \leq i < j \leq n$ and for all $\delta, \delta' \in \{ 1, -1 \}$ there is exactly one rule $a_j^\delta a_i^{\delta'} \longrightarrow r$ in C. $\diamond$

Definition 4    
For $1 \leq i \leq n$ a rule $a_i^m \longrightarrow r$ where $m \geq 1$, $r \in \Sigma_{i+1}^*$ is called a   positive P-rule and a rule $a_i^{-1} \longrightarrow uv$ where $u \in \{ a_i \} ^*$ and $v \in \Sigma_{i+1}^*$ is called a   negative P-rule. Then a subset P of $\Sigma^* \times \Sigma^*$ is called a  power system if

1.

P contains only positive and negative P-rules.

2.

For all $1 \leq i \leq n$ there is a negative P-rule $a_i^{-1} \longrightarrow uv$ in P if and only if there also is a positive P-rule of the form $a_i^m \longrightarrow r$ with $m \geq 1$ in P.

3.

For all $1 \leq i \leq n$ there is at most one negative P-rule $a_i^{-1} \longrightarrow uv$ and at most one positive P-rule $a_i^m \longrightarrow r$ in P. $\diamond$

In combining these rule systems we can characterize special group presentations. For ${\rm X}$ in $\{ \mbox{AB, NI, P} \}$, a presentation $(\Sigma, T)$ is called a   CX-string-rewriting system (CX-system) if $T= C \cup I$ where C is a commutation system and I contains the trivial rules, i.e., $I = \{ a_ia_i^{-1} \longrightarrow\lambda, a_i^{-1}a_i \longrightarrow\lambda \vert 1 \leq i \leq n \}$. It is called a   PCX-string-rewriting system (PCX-system) if $T = C \cup P \cup I$ where T additionally includes a power system P. The motivation for such presentations stems from the fact that they can be used to characterize special classes of groups.

Theorem 1 (Theorem 2.5.1. in [Wi89])    
For a finitely presented group ${\cal G}$ the following statements hold:

1.

${\cal G}$ is Abelian if and only if there is a PCAB-system presenting ${\cal G}$.

2.

${\cal G}$ is nilpotent if and only if there is a PCNI-system presenting ${\cal G}$.

3.

${\cal G}$ is polycyclic if and only if there is a PCP-system presenting ${\cal G}$.

Notice that this theorem is a syntactical illustration of the fact that for finitely generated groups Abelian implies nilpotent which again implies polycyclic.

Using a syllable ordering Wißmann has shown that a PCX-system $(\Sigma, T)$ 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.

Definition 5    
Let $\Sigma$ be an alphabet and $\succ$ a partial ordering on $\Sigma^*$. We define an ordering $\succ^{\rm lex}$ on tuples over $\Sigma^*$ as follows:

$$(u_0, \ldots, u_m) \succ^{\rm lex} (v_0, \ldots, v_m)$$

$$\mbox{if and only if}$$

$$\mbox{there exists } 0 \leq k \leq m \mbox{ such that } u_i = v_i \mbox{ for all } 0 \leq i < k \mbox{ and } u_k \succ v_k.$$

Let $a \in \Sigma$. Then every $w \in \Sigma^*$ can be uniquely decomposed with respect to a as $w \equiv w_0aw_1 \ldots aw_k$, where $\vert w\vert _a = k \geq 0$ and $w_i \in (\Sigma \backslash \{ a \})^*$. Given a total precedence² $\triangleright$ on $\Sigma$ we can define a syllable ordering with status left by

$$u >_{{\rm syll}(\Sigma)} v$$

$$\mbox{if and only if}$$

$$\vert u\vert _a > \vert v\vert _a \mbox{ or}$$

$$\vert u\vert _a = \vert v\vert _a \mbox{ and } (u_0, \ldots, ... ...yll}(\Sigma \backslash \{ a \})}^{\rm lex} (v_0, \ldots, v_m)$$

where a is the largest letter in $\Sigma$ according to $\triangleright$ and $(u_0, \ldots, u_m)$, $(v_0, \ldots, v_m)$ are the decompositions of u and v with respect to a in case |u|_a = |v|_a = m. $\diamond$

The total precedence used on an alphabet $\Sigma = \{ a_i, a_i^{-1} \mid 1 \leq i \leq n \}$ in our setting is $a_1^{-1} \succ a_1 \succ \ldots a_i^{-1} \succ a_i \succ \ldots \succ a_n^{-1} \succ a_n$. Using the syllable ordering induced by this precedence we can give a characterization of the elements of our group as a subset of the set of     ordered group words ${\sf ORD}\/(\Sigma) = {\sf ORD}\/(\Sigma_1)$, where we define ${\sf ORD}\/(\Sigma_{i})$ recursively by ${\sf ORD}\/(\Sigma_{n+1}) = \{ \lambda \}$, and ${\sf ORD}\/(\Sigma_i) = \{ w \in \Sigma_i^* \mid w \equiv uv \mbox{ for some } u \in \{ a_i \}^* \cup \{ a_i^{-1} \}^* , v \in {\sf ORD}\/(\Sigma_{i+1}) \}$. Further with respect to T we define the constants $\epsilon_T(i)$ for $1 \leq i \leq n$ by setting

$$\epsilon_T(i) = \left\{ \begin{array}{r@{\quad\quad}l} \inft... ...longrightarrow r$ for some unique $m>0$.} \end{array} \right.$$

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

$${\rm IRR}\/(T) = \{ a_1^{i_1} \ldots a_{n\phantom{1}}^{i_n} \... ...j) \neq \infty \mbox{ then } 0 \leq i_j \leq \epsilon_T(j) \}.$$

For example the semi-Thue system $(\Sigma, T)$ where $T= C \cup I$ such that we have $C= \{ a_j^\delta a_i^{\delta'} \longrightarrow a_i^{\delta'} a_j^{\delta} \mid 1 \leq i < j \leq n, \delta, \delta' \in \{ 1, -1 \} \}$ and $I = \{ a_ia_i^{-1} \longrightarrow\lambda, a_i^{-1}a_i \longrightarrow\lambda \mid 1 \leq i \leq n \}$ is a presentation of the free commutative group generated by $\{ a_1, \ldots, a_n \}$ and we have ${\rm IRR}\/(T) = {\sf ORD}\/(\Sigma)$.

In restricting the syllable ordering introduced in definition 5 to ordered group words this gives us $a_1^{i_1} \ldots a_{n\phantom{1}}^{i_n} >_{\rm syll}a_1^{j_1} \ldots a_{n\phantom{1}}^{j_n}$ if and only if for some $1 \leq d \leq n$ we have i_l = j_l for all $1 \leq l \leq d-1$ and $i_d >_{{\bf Z}} j_d$ with $\alpha >_{{\bf Z}} \beta$ if and only if $\beta = 0$ or $({\sf sgn}(\alpha) = -1$ and ${\sf sgn}(\beta) = 1)$ or $({\sf sgn}(\alpha) = {\sf sgn}(\beta)$ and $\vert\alpha\vert > \vert\beta\vert)$. where > is the usual ordering⁵ on ${\bf Z}$ and for $\alpha \in {\bf Z}$, ${\sf sgn}(\alpha) = 0$ if $\alpha = 0$, ${\sf sgn}(\alpha) = 1$ if $\alpha > 0$ and ${\sf sgn}(\alpha) = -1$ if $\alpha < 0$. 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 $>_{{\bf Z}}$ and will be useful in the proofs later on.

Lemma 2    
Let $a,b,c \in {\bf Z}$. Then $a >_{\bf Z} b$ and $a \cdot c \geq 0$ imply $a + c >_{\bf Z} b + c$.

Proof : 1.11.1 
In case a > 0 we find $b \geq 0$ (since $a >_{\bf Z} b$) and $c \geq 0$ (as $a \cdot c \geq 0)$. This immediately implies $a + c > b + c \geq 0$ and hence $a + c >_{\bf Z} b + c$.
On the other hand, a < 0 gives us $c \leq 0$ (since $a \cdot c \geq 0$) and depending on b either a + c < b + c < 0 or $a + c < 0 \leq b + c$, again implying $a + c >_{\bf Z} b + c$.
q.e.d.

1.11

Lemma 3    
Let $a,b,c \in {\bf Z}$. Then $a >_{\bf Z} b$, $a \geq_{\bf Z} c$, and the existence of an element $x \in {\bf Z}$ such that $a + x <_{\bf Z} b + x$ and $c + x \leq_{\bf Z} b + x$ imply $b - a \geq_{\bf Z} c - a$. In case $c + x <_{\bf Z} b + x$ holds we get $b - a >_{\bf Z} c - a$.

Proof : 1.11.1 
First let us look at the case b-a = c-a. This implies b=c and hence b+y = c+ y for all $y \in {\bf Z}$. Therefore the existence of an $x \in {\bf Z}$ such that $c + x <_{\bf Z} b + x$ implies $b - a \neq_{\bf Z} c - a$.
Now it remains to prove that the case $b - a <_{\bf Z} c - a$ is not possible.
First suppose c-a < 0. Let us distinguish the two possible cases: If a>0 we get $a\geq c\geq 0$ (as $a \geq_{\bf Z} c$) and $a > b \geq 0$ (as $a >_{\bf Z} b$). Since then $b-a \geq 0$ is not possible, $b - a <_{\bf Z} c - a$ implies that we have c-a < b-a <0 and hence $a > b \geq c \geq 0$ must hold. We now show that in this case no x as described in the lemma can be found. For $a > b \geq 0$ we get that for all $y \geq -b$ we have $b+y <_{{\bf Z}} a+y$ and for all y < -b we have $b+y >_{{\bf Z}} a+y$. Similarly, for $b \geq c \geq 0$ we find that for all $z \geq -c$ we have $c+z \leq_{{\bf Z}} b+z$ and for all z<-c, $c+z \geq_{{\bf Z}} b+z$ holds. Hence for x such that $a + x <_{\bf Z} b + x$ and $c + x \leq_{\bf Z} b + x$ to hold, we must have x<-b and $x \geq -c$, contradicting $-b \leq -c$. On the other hand, a<0 leads to a contradiction $c-a \geq 0$ as $a \geq_{\bf Z} c$ either implies $c \geq 0$ or $a \leq c < 0$.
Hence let us suppose c-a > 0 and therefore $c-a > b-a \geq 0$ implying $c > b \geq a$ (and hence $a >_{{\bf Z}} c$ must hold as $a \neq c$). Furthermore, $a >_{\bf Z} b$ implies a < 0. Let us analyze the remaining cases. If $c \leq 0$ we find b < 0 as well (since $c > b \geq a$). Since the equation $a + x <_{\bf Z} b + x$ holds for $x \geq -a >0$ only and $c + x \leq_{\bf Z} b + x$ for $0 \leq x < -b < -a$ only, no x as required can exist. Hence suppose c>0. Then depending on b the equation $c + x \leq_{\bf Z} b + x$ holds either for $0 \leq x < -b < -a$ (in case b < 0) only or for $x < -b \leq 0$ (in case $b \geq 0$), and as further $x \geq -a >0$ must hold again no such x can exist.
q.e.d.

1.11

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

Lemma 4    

1.

Let ${\cal G}$ be a nilpotent group with a convergent PCNI-presentation $(\Sigma, T)$. Further for some $1 \leq j < i \leq n$ let $w_1 \in {\sf ORD}\/(\Sigma \backslash \Sigma_{j})$, $w_2 \in {\sf ORD}\/(\Sigma_{i+1})$. Then we have $a_i \circ w_1 \equiv w_1a_iz_1$ and $w_2 \circ a_i \equiv a_iz_2$ for some $z_1, z_2 \in {\sf ORD}\/(\Sigma_{i+1})$.

2.

Let ${\cal G}$ be a polycyclic group with a convergent PCP-presentation $(\Sigma, T)$. Further for some $1 \leq i < n$ let $w \in {\sf ORD}\/(\Sigma_{i+1})$. Then we have $w \circ a_i \equiv a_iz$ for some $z \in {\sf ORD}\/(\Sigma_{i+1})$.

Proof : 1.11.1 
This follows immediately from the rules given in the respective presentations.
q.e.d.

1.11

We now define a new ordering on ${\cal G}$ called a tuple ordering, which will be crucial in our definitions of reduction.

Definition 6    
For two elements $w \equiv a_1^{i_1} \ldots a_n^{i_n}, v \equiv a_1^{j_1} \ldots a_n^{j_n} \in {\sf ORD}\/(\Sigma)$, we define $w \geq_{\rm tup}v$ if for each $1 \leq l \leq n$ we have either j_l = 0 or ${\sf sgn}(i_l)={\sf sgn}(j_l)$ and $\vert i_l\vert \geq \vert j_l\vert$ where ${\sf sgn}(i)$ is the sign of the non-zero integer i. Further we define $w >_{\rm tup}v$ if $w \geq_{\rm tup}v$ and |i_l|>|j_l| for some $1 \leq l \leq n$ and $w \geq_{\rm tup} \lambda$ for all $w \in {\cal G}$. According to this ordering we call v a syntactic divisor or commutative prefix of w if $w >_{\rm tup}v$. $\diamond$

Notice that this ordering captures the fact that a divisor of a term in the ordinary polynomial ring is also a commutative prefix of the term. The tuple ordering is not total on ${\cal G}$ but we find that $w >_{\rm tup}v$ implies $w \succ v$, where $\succeq$ is the ordering on ${\cal G}$ induced by the syllable ordering used as completion ordering for the respective PCX-presentation of ${\cal G}$. Given a non-zero polynomial p in ${\bf K}[{\cal G}]$, the so called head term ${\sf HT}(p)$ is the largest term in p with respect to $\succ$, ${\sf HC}(p)$ is the coefficient of this term and the head monomial is ${\sf HM}(p) = {\sf HC}(p) \cdot{\sf HT}(p)$. ${\sf T}(p)$ is the set of terms occurring in p. The total ordering $\succeq$ on ${\cal G}$ can be extended to a partial ordering on ${\bf K}[{\cal G}]$ by setting p > q if and only if ${\sf HT}(p) \succ {\sf HT}(q)$ or $({\sf HM}(p) = {\sf HM}(q)$ and $p - {\sf HM}(p) > q - {\sf HM}(q))$.

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

Definition 7    
Let F be a set of polynomials and p a non-zero polynomial in ${\bf K}[{\cal G}]$.

1.

A representation

$$p = \sum_{i=1}^{n} \alpha_i \cdot f_{i} \ast w_i, \;\; \mbox{ with } \alpha_i \in {\bf K}^*, f_{i} \in F, w_i \in {\cal G}$$

is called a right commutative prefix standard representation in case for the respective head terms we have ${\sf HT}(p) \succeq {\sf HT}(f_{i}) \circ w_i = {\sf HT}(f_i \ast w_i)$ and ${\sf HT}(f_i \ast w_i) \geq_{\rm tup}{\sf HT}(f_i)$ for all $1 \leq i \leq n$. In our previous work this was also called a quasi-commutative (qc-) standard representation.

2.

A representation

$$p = \sum_{i=1}^{n} \alpha_i \cdot w_i \ast f_{i}, \;\; \mbox{ with } \alpha_i \in {\bf K}^*, f_{i} \in F, w_i \in {\cal G}$$

is called a left commutative prefix standard representation in case for the respective head terms we have ${\sf HT}(p) \succeq w_i \circ{\sf HT}(f_{i}) = {\sf HT}(w_i \ast f_i)$ and ${\sf HT}(w_i \ast f_i) \geq_{\rm tup}{\sf HT}(f_i)$ for all $1 \leq i \leq n$. Again for historical reasons this is sometimes called a left polycyclic (lpc-) standard representation.

A set $F \subseteq {\bf K}[{\cal G}]$ is called a right commutative prefix respectively left commutative prefix standard basis if every non-zero polynomial in ${\sf ideal}_{r}^{}(F)$ respectively ${\sf ideal}_{l}^{}(F)$ has a right commutative prefix respectively left commutative prefix standard representation with respect to F. $\diamond$

Notice that in case ${\cal G}$ is Abelian these representations coincide and are called commutative standard representations. We will later on see how such representations are related to different reductions, which will be Noetherian because of the following statements, which heavily depend on the presentation of the group.

Lemma 5    
Let ${\cal G}$ be a nilpotent group with a convergent PCNI-presentation, $w,v,\tilde{v} \in {\cal G}$ with $w \geq_{\rm tup}v$ and $v \succ \tilde{v}$. Then for $u \in {\cal G}$ such that $w = v \circ u$, we get $w \succ \tilde{v}\circ u$. Notice that since ${\cal G}$ is a group, u always exists and is unique, namely $u = {\sf inv}\/(v) \circ w$.

Proof : 1.11.1 
Let a_d be the distinguishing letter between v and ${\tilde{v}}$, i.e., $v \equiv x a_d^{v_d}y_v$, ${\tilde{v}} \equiv x a_d^{{\tilde{v}}_d}y_{\tilde{v}}$ with $x \in {\sf ORD}\/(\Sigma \backslash \Sigma_d)$, $y_v, y_{\tilde{v}} \in {\sf ORD}\/(\Sigma_{d+1})$ and $v_d >_{{\bf Z}} \tilde{v}_d$. Then for $u \equiv a_1^{u_1} \ldots a_n^{u_n}$ we get $v \circ a_1^{u_1} \ldots a_d^{u_d} = a_1^{w_1} \ldots a_{d-1}^{w_{d-1}} \circ a_d^{u_d+v_d+s_d} \circ (a_{d+1}^{s_{d+1}} \ldots a_n^{s_n} \circ y_v)$ and similarly $\tilde{v} \circ a_1^{u_1} \ldots a_d^{u_d} = a_1^{w_1} \ldots a_{d-1}^{w_{d-1... ...d^{u_d+v_d+s_d} \circ (a_{d+1}^{s_{d+1}} \ldots a_n^{s_n} \circ y_{\tilde{v}})$ and since $(a_{d+1}^{s_{d+1}} \ldots a_n^{s_n} \circ y_v)$, $(a_{d+1}^{s_{d+1}} \ldots a_n^{s_n} \circ y_{\tilde{v}})\in {\sf ORD}\/(\Sigma_{d+1})$ and the exponents of the letter a_d are different, in order to decide whether $w \succ \tilde{v}\circ u$ we only have to compare the exponents of a_d in the normal forms of the respective products. Now, $w \geq_{\rm tup}v$ gives us, for the exponent w_d of the letter a_d in w, $w_d \geq_{{\bf Z}} v_d$, ${\sf sgn}(w_d) = {\sf sgn}(v_d)$ and u_d + v_d + s_d = w_d or $(u_d + v_d + s_d) {\sf\phantom{1}mod\phantom{1}}{m_d} = w_d$ in case a_d is bounded by m_d.

To show that $w \succ \tilde{v}\circ u$ we now have to distinguish two cases. If the letter a_d has unbounded exponents, we can apply lemma 2 since $v_d >_{{\bf Z}} \tilde{v}_d$ and $v_d \cdot(u_d + s_d) \geq 0$ hold (the latter follows as $w \geq_{\rm tup}v$). Hence let us assume the letter a_d is bounded, i.e., we know $0 \leq \tilde{v}_d < v_d \leq w_d < m_d$, and since $0 \leq u_d < m_d$ must also hold we get $0 \leq \tilde{v}_d + u_d < v_d + u_d$ and $(v_d + u_d + s_d) {\sf\phantom{1}mod\phantom{1}}{m_d} = w_d$. Now in case v_d + u_d + s_d = w_d we are done, as then $u_d + s_d \geq 0$ implies $v_d + u_d + s_d > \tilde{v}_d + u_d + s_d$. Else, as $v_d \leq w_d$, for y = w_d - v_d we know $u_d + s_d = l \cdot m_d + y$ with $0 \leq y < m_d$ and hence $0 \leq ( \tilde{v}_d + u_d + s_d) {\sf\phantom{1}mod\phantom{1}}{m_d} = (\tilde... ...m_d + y) {\sf\phantom{1}mod\phantom{1}}{m_d} = \tilde{v}_d + y < v_d + y = w_d$ 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.

Example 1    
Let $\Sigma = \{ a_1, a_1^{-1}, a_2, a_2^{-1}, a_3, a_3^{-1} \}$ and $T = \{ a_3a_1 \longrightarrow a_1a_2a_3, a_3a_1^{-1} \longrightarrow a_1^{-1}a_... ...row a_1^{\delta'}a_2^{\delta} \mid \delta, \delta' \in \{ 1, -1 \} \} \cup T_I$ be a polycyclic presentation of the free nilpotent group with two generators. Then for $w \equiv a_1^2a_2$, $v \equiv a_1a_2$ and $\tilde{v} \equiv a_1a_3$ we have $w \geq_{\rm tup}v$, $v \succ \tilde{v}$. Now for $u \equiv a_1$ we find $v \circ u = a_1a_2 \circ a_1 \equiv a_1^2a_2$, but $\tilde{v} \circ u = a_1a_3 \circ a_1 = a_1^2a_2a_3$ and hence $\tilde{v} \circ u \succ w$. $\diamond$

This example stresses the importance of the presentation chosen for the group, as the group is nilpotent. Note that lemma 5 holds when using the presentation $\Sigma = \{ a_1, a_1^{-1}, a_2, a_2^{-1}, a_3, a_3^{-1} \}$ and $T = \{ a_2a_1 \longrightarrow a_1a_2a_3, a_2^{-1}a_1^{-1} \longrightarrow a_1^{... ...longrightarrow a_1^{\delta'}a_3^{\delta} \mid \delta, \delta' \in \{ 1, -1 \}\}$. Then for $w \equiv a_1^2a_2$, $v \equiv a_1a_2$ and $\tilde{v} \equiv a_1a_3$ we get $u \equiv a_1a_3^{-1}$ and $\tilde{v} \circ u = a_1a_3 \circ a_1a_3^{-1} \equiv a_1^2 \prec w$.

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

Lemma 6    
Let ${\cal G}$ be a polycyclic group with a convergent PCP-presentation, $w,v,\tilde{v} \in {\cal G}$ with $w \geq_{\rm tup}v$ and $v \succ \tilde{v}$. Then for $u \in {\cal G}$ such that $w = u \circ v$, we get $w \succ u \circ\tilde{v}$. Notice that since ${\cal G}$ is a group, u always exists and is unique, namely $u = w \circ{\sf inv}\/(v)$.

Proof : 1.11.1 
Let a_d be the distinguishing letter between v and ${\tilde{v}}$, i.e., $v \equiv x a_d^{v_d}y_v$, ${\tilde{v}} \equiv x a_d^{{\tilde{v}}_d}y_{\tilde{v}}$ with $x \in {\sf ORD}\/(\Sigma \backslash \Sigma_d)$, $y_v, y_{\tilde{v}} \in {\sf ORD}\/(\Sigma_{d+1})$ and $v_d >_{{\bf Z}} \tilde{v}_d$. Then for $u \equiv a_1^{u_1} \ldots a_n^{u_n}$ we get $u \circ v = a_1^{u_1} \ldots a_n^{u_n} \circ x a_d^{v_d}y_v = a_1^{u_1} \ldots... ...} \circ x' a_d^{u_d+v_d+z_1} {y_v}' = x'' \circ a_d^{u_d+v_d+z_2} \circ{y_v''}$ with $x',x'' \in {\sf ORD}\/(\Sigma \backslash \Sigma_d)$, ${y_v}', {y_v''} \in {\sf ORD}\/(\Sigma_{d+1})$ and similarly $u \circ\tilde{v} = x'' \circ a_d^{u_d+\tilde{v}_d+z_2} \circ{y_{\tilde{v}}''}$ with ${y_{\tilde{v}}''} \in {\sf ORD}\/(\Sigma_{d+1})$. Furthermore, $w \geq_{\rm tup}v$ gives us, for the exponent w_d of the letter a_d in w, $w_d \geq_{{\bf Z}} v_d$, ${\sf sgn}(w_d) = {\sf sgn}(v_d)$ and u_d + v_d + z₂ = w_d or $(u_d + v_d + z_2) {\sf\phantom{1}mod\phantom{1}}{m_d} = w_d$ in case a_d is bounded by m_d. To show that $w \succ u \circ\tilde{v}$ we can proceed as in lemma 5.
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

$${\cal G}= {\cal G}_1 \geq {\cal G}_2 \geq \ldots \geq {\cal G}_{n+1} = \{ \lambda\}$$

be a polycyclic series for ${\cal G}$. For $1 \leq i \leq n$ let a_i be an element of ${\cal G}_i$ whose image in ${\cal G}_i / {\cal G}_{i+1}$ generates that group. The letters $a_1, \ldots , a_n$ are called a polycyclic generating sequence and we have ${\cal G}_i = \langle a_i, \ldots , a_n \rangle$, i.e., ${\cal G}_i$ is the subgroup of ${\cal G}$ generated by $a_i, \ldots , a_n$. Further let $I = \{ i \mid {\cal G}_i / {\cal G}_{i+1} \mbox{ is finite} \}$ and for $i \in I$ set $m_i = \vert{\cal G}_i : {\cal G}_{i+1}\vert$. It is assumed that the generating sequence is not redundant in the sense that no a_i is in ${\cal G}_{i+1}$. Every element of ${\cal G}$ can be expressed in the form $a_1^{i_1} \ldots a_n^{i_n}$, where $i_1, \ldots, i_n \in {\bf Z}$, and such a presentation is called a collected word, if $0 \leq i_j < m_j$ for $j \in I$. Now ${\cal G}$ gives rise to a unique presentation called the standard polycyclic presentation with respect to the letters $a_1, \ldots , a_n$, namely

ajai	=	$a_ia_{i+1}^{\alpha_{ij(i+1)}} \ldots a_n^{\alpha_{ijn}}$,	j>i,
aj-1ai	=	$a_ia_{i+1}^{\beta_{ij(i+1)}} \ldots a_n^{\beta_{ijn}}$,	j>i, $j \not\in I$,
ajai-1	=	$a_i^{-1}a_{i+1}^{\gamma_{ij(i+1)}} \ldots a_n^{\gamma_{ijn}}$,	j>i, $i \not\in I$,
ajai-1	=	$a_i^{-1}a_{i+1}^{\delta_{ij(i+1)}} \ldots a_n^{\delta_{ijn}}$,	j>i, $i,j \not\in I$,
aimi	=	$a_{i+1}^{\mu_{i(i+1)}} \ldots a_n^{\mu_{in}}$	$i \in I$,
ai-1	=	$a_i^{m_i-1}a_{i+1}^{\nu_{i(i+1)}} \ldots a_n^{\nu_{in}}$	$i \in I$,
aiai-1	=	$\lambda$,	$i \not\in I$,
ai-1ai	=	$\lambda$,	$i \not\in 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 $\vert{\cal G}_i : {\cal G}_{i+1}\vert = m$ although there is no relation of the form $a_i^m = \ldots$ or only a relation of the form $a_i^n = \ldots$ 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 $\{ a_1, \ldots, a_n \}$ with respect to the syllable ordering - here called wreath ordering - induced by the precedence $a_1^{-1} \succ a_1 \succ \ldots \succ a_n^{-1} \succ a_n$. Then a consistent polycyclic presentation gives rise to a convergent PCP presentation.