5. Reduction in Nilpotent Group Rings

Let ${\cal G}$ be a nilpotent group given by a convergent PCNI-presentation as described in section 2. The next example illustrates that no total, well-founded admissible ordering can exist for a non-trivial group due to the existence of inverses.

Example 5    
Let $\Sigma = \{ a, a^{-1} \}$ and $T = \{ aa^{-1} \longrightarrow\lambda, a^{-1}a \longrightarrow\lambda \}$ be a presentation of a group ${\cal G}$. Let ${\bf Q}$ denote the rational numbers. Suppose we simply require divisibility of the head term to allow reduction. Then we could reduce the polynomial $a^2 + 1 \in {\bf Q}[{\cal G}]$ at the monomial a² by the polynomial a^-1 + a as $a^2 = a^{-1} \circ a^3$. This would give

$$a^{2} + 1 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{... ...{-1} + a}\,$} a^{2} + 1 - (a^{-1} + a) \ast a^{3} = -a^{4} + 1$$

and the polynomial -a⁴ + 1 likewise would be reducible by a^-1 + a at the monomial -a⁴ causing an infinite reduction sequence. $\diamond$

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 ${\cal G}$ 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 ${\cal G}$ is given as a convergent PCP-presentation.

Definition 9    
Let p, f be two non-zero polynomials in ${\bf K}[{\cal G}]$. We say that f quasi-commutatively (qc-) reduces p to q at a monomial $\alpha \cdot t$ of p in one step, denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } q$, if

(a)

$t \geq_{\rm tup}{\sf HT}(f)$, and

(b)

$q = p - \alpha \cdot{\sf HC}(f)^{-1} \cdot f \ast ({\sf inv}\/({\sf HT}(f)) \circ t)$.

Quasi-commutative reduction by a set $F \subseteq {\bf K}[{\cal G}]$ is denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } q$ and abbreviates $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } q$ for some $f \in F$. $\diamond$

Notice that if f qc-reduces p at $\alpha \cdot t$ 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 $t \geq_{\rm tup}{\sf HT}(f)$. Further it is Noetherian and the translation lemma holds.

Lemma 9    
Let F be a set of polynomials in ${\bf K}[{\cal G}]$ and $p,q,h \in{\bf K}[{\cal G}]$ some polynomials.

1.

Let $p-q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } h$. Then there are $p',q' \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } q'$ and h=p'-q'.

2.

Let 0 be a normal form of p-q with respect to $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ }$. Then there exists a polynomial $g \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } g$ and $q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } g$.

Proof : 1.11.1 

1.

Let $p-q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } h = p-q-\alpha \cdot f \ast w$, where $\alpha \in {\bf K}^*, f \in F, w \in {\cal G}$ and ${\sf HT}(f) \circ w = t \geq_{\rm tup}{\sf HT}(f)$, i.e. $\alpha \cdot{\sf HC}(f)$ is the coefficient of t in p-q. We have to distinguish three cases:

(a)

$t \in {\sf T}(p)$ and $t \in {\sf T}(q)$: Then we can eliminate the term t in the polynomials p respectively q by qc-reduction. We then get $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } p - \alpha_1 \cdot f \ast w= p'$ and $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } q - \alpha_2 \cdot f \ast w= q'$, with $\alpha_1 - \alpha_2 =\alpha$, where $\alpha_1 \cdot{\sf HC}(f)$ and $\alpha_2 \cdot{\sf HC}(f)$ are the coefficients of t in p respectively q.

(b)

$t \in {\sf T}(p)$ and $t \not\in {\sf T}(q)$: Then we can eliminate the term t in the polynomial p by qc-reduction and get $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } p - \alpha \cdot f \ast w= p'$ and q = q'.

(c)

$t \in {\sf T}(q)$ and $t \not\in {\sf T}(p)$: Then we can eliminate the term t in the polynomial q by qc-reduction and get $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f}\,$ } q + \alpha \cdot f \ast w= q'$ and p = p'.

In all cases we have $p' -q' = p - q - \alpha \cdot f \ast w = h$.

2.

We show our claim by induction on k, where $p-q \mbox{$\,\stackrel{k}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } 0$. In the base case k=0 there is nothing to show. Hence, let $p-q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } h \mbox{$\,\stackrel{k}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } 0$. Then by (1) there are polynomials $p',q' \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } q'$ and h=p'-q'. Now the induction hypothesis for $p'-q' \mbox{$\,\stackrel{k}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } 0$ yields the existence of a polynomial $g \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } p' \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } g$ and $q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } q' \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } g$.
q.e.d.

1.11

In case ${\cal G}$ is a free Abelian group, qc-reduction coincides with Sims' reduction for Laurent polynomials, as the condition $t \geq_{\rm tup}{\sf HT}(f)$ implies that $u = {\sf inv}\/({\sf HT}(f)) \circ t$ is aligned with ${\sf HT}(f)$. Notice that in the general nilpotent case u and ${\sf HT}(f)$ 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 $\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 \}\}$ be a convergent PCNI-presentation of the free nilpotent group on two generators. Then for a₁a₂ and a₁a₃ due to Sims' ordering we get $a_1a_3 \succ a_1a_2$, but for the aligned elements a₁ and a₁a₃ we find $a_1a_3 \circ a_1 = a_1^2 a_3$, while $a_1a_2 \circ a_1 = a_1^2a_2a_3$, and hence $a_1a_3 \circ a_3 = a_1^2a_3 \prec a_1^2a_2a_3 = a_1a_2 \circ a_1$. $\diamond$

Gröbner bases as defined by Buchberger can now be specified for right ideals in this setting as follows.

Definition 10    
A set $G \subseteq {\bf K}[{\cal G}]$ is said to be a right Gröbner basis, if $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(G)}$, and $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$ is confluent. $\diamond$

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 qc-reduction $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(G)}$ in general will not hold. One reason for this phenomenon is that a reduction step is not preserved under right multiplication with elements of ${\cal G}$.

Example 7    
Let ${\bf Q}[{\cal G}]$ be the group ring given in example 5. Then for the polynomials p = a² + a and $f = a + \lambda$ we find that p is qc-reducible by f. This is no longer true for the multiple $p \ast a^{-2} = (a^2 + a) \ast a^{-2} = \lambda + a^{-1}$. Notice that, since $a^{-1} + \lambda \in {\sf ideal}_{r}^{}(p)$, we have $a^{-1} + \lambda \equiv_{{\sf ideal}_{r}^{}(p)} 0$, but $a^{-1} + \lambda \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm }}_{p}\,$ } 0$ does not hold. $\diamond$

We will now introduce how we can extend the expressiveness of qc-reduction. 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 qc-reduction. 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 non-zero polynomial in ${\bf K}[{\cal G}]$. In case there exists an element $w \in {\cal G}$ such that ${\sf HT}(p \ast w) = t \circ w$ for some $t \in {\sf T}(p)$, let a_d be the distinguishing letter between t and ${\sf HT}(p)$. Then one can construct an element $v \in {\sf ORD}\/(\Sigma_d)$ such that ${\sf HT}(p\ast v) = t \circ v$.
In particular, given p and $t \in {\sf T}(p)$ it is decidable whether there exists an element $w \in {\cal G}$ such that ${\sf HT}(p \ast w) = t$.

Proof : 1.11.1 
We show that for all polynomials $q \in \{ p \ast u \mid u \in {\cal G}\}$ the following holds: In case ${\sf HT}(q \ast w) = t_i \circ w$ for some $w \in {\cal G}$, $t_i \in {\sf T}(q)$ then one can construct an element $v \in {\sf ORD}\/(\Sigma_d)$ where a_d is the distinguishing letter between t_i and ${\sf HT}(q)$, and ${\sf HT}(q \ast v) = t_i \circ v$.
This will be done by induction on k where d = n-k.
In the base case let k=0, i.e., a_n is the distinguishing letter between ${\sf HT}(q) = t_1 \equiv a_1^{1_1} \ldots a_{n\phantom{1}}^{1_n}$ and $t_i \equiv a_1^{i_1} \ldots a_{n\phantom{1}}^{i_n}$. Hence 1_j = i_j for all $1 \leq j \leq n-1$ and $1_n >_{{\bf Z}} i_n$.
By our assumption there exists $w \in {\cal G}$ such that ${\sf HT}(q \ast w) = t_i \circ w$, with $w \equiv w'a_{n\phantom{1}}^{w_n}$, $w' \in {\sf ORD}\/(\Sigma \backslash \Sigma_n)$, and there exist $k_1, \ldots , k_{n-1}, x \in {\bf Z}$ such that $t_1 \circ w = a_1^{1_1} \ldots a_{n\phantom{1}}^{1_n} \circ w = a_1^{1_1} \ldot... ...a_1^{k_1} \ldots a_{n-1\phantom{1}}^{k_{n-1}} \circ a_{n\phantom{1}}^{1_n + x}$ and $t_i \circ w =a_1^{1_1} \ldots a_{n-1\phantom{1}}^{1_{n-1}}a_{n\phantom{1}}^{i_n... ...a_1^{k_1} \ldots a_{n-1\phantom{1}}^{k_{n-1}} \circ a_{n\phantom{1}}^{i_n + x}$. Thus $1_n + x <_{{\bf Z}} i_n + x$ or, in case a_n is bounded by $m_n \in {\bf N}$, $(1_n + x) {\sf\phantom{1}mod\phantom{1}}m_n <_{{\bf Z}} (i_n + x) {\sf\phantom{1}mod\phantom{1}}m_n$ must hold. First let us assume that the letter a_n is not bounded. Then let us set $v \equiv a_{n}^{-1_n}$. We show that for all $t_j \in T(q) \backslash \{t_i \}$ we have $t_i \circ v \succ t_j \circ v$. Note that for all t_j with prefix $a_1^{j_1} \ldots a_{n-1\phantom{1}}^{j_{n-1}} \prec a_1^{1_1} \ldots a_{n-1\phantom{1}}^{1_{n-1}}$ we have $t_j \circ v \prec t_i \circ v$, as right multiplication with $v \equiv a_{n}^{-1_n}$ only changes the exponent of a_n in the respective term. It remains to look at those terms t_j with $a_1^{j_1} \ldots a_{n-1\phantom{1}}^{j_{n-1}} \equiv a_1^{1_1} \ldots a_{n-1\phantom{1}}^{1_{n-1}}$. Then we can apply lemma 3 as we have $1_n >_{{\bf Z}} i_n$, $1_n >_{{\bf Z}} j_n$ and as seen above there exists an element x such that $1_n + x <_{{\bf Z}} i_n + x$ and $j_n + x <_{{\bf Z}} i_n + x$. Therefore $i_n - 1_n >_{{\bf Z}} j_n - 1_n$ and our claim must hold. In case the letter a_n is bounded by m_n, we set $v \equiv a_n^{m_n - i_n - 1}$. As before, for all t_j which have a prefix $a_1^{j_1} \ldots a_{n-1\phantom{1}}^{j_{n-1}} \prec a_1^{1_1} \ldots a_{n-1\phantom{1}}^{1_{n-1}}$ we have $t_j \circ v \prec t_i \circ v$. Tor those t_j with prefix $a_1^{1_1} \ldots a_{n-1\phantom{1}}^{1_{n-1}}$ we know that the exponent of a_n in $t_j \circ v$ cannot be m_n -1 unless t_j = t_i, and hence $t_j \circ v \prec t_i \circ v$ must hold.
In the induction step let us assume that for all polynomials $q \in \{ p \ast u \vert u \in {\cal G}\}$ and $w \in {\cal G}$ with ${\sf HT}(q \ast w) = t_i \circ w$, if the distinguishing letter a_d between ${\sf HT}(q)$ and t_i has index $d \geq n - (k-1)$ there exists an element $v' \in {\sf ORD}\/(\Sigma_d)$ such that ${\sf HT}(q \ast v') = t_i \circ v'$. Now for $q \in \{ p \ast u \vert u \in {\cal G}\}$, $w \in {\cal G}$ with ${\sf HT}(q \ast w) = t_i \circ w$ let us assume that the distinguishing letter between ${\sf HT}(q)$ and t_i has index d = n-k.
Since ${\sf HT}(q \ast w) = t_i \circ w$, for $w \equiv w'a_{d\phantom{1}}^{w_d}w''$ with $w' \in {\sf ORD}\/(\Sigma \backslash \Sigma_d)$, $w'' \in {\sf ORD}\/(\Sigma_{d+1})$, we know that there exist $k_1, \ldots, k_{d-1}, x \in {\bf Z}$ and $z_1, z_i, \tilde{z}_1 \in {\sf ORD}\/(\Sigma_{d+1})$ such that $t_1 \circ w = a_1^{1_1} \ldots a_{n\phantom{1}}^{1_n} \circ w = a_1^{1_1} \ld... ...ldots a_{d-1\phantom{1}}^{k_{d-1}} \circ a_{n\phantom{1}}^{1_d + x} \circ z_1$ and similarly $t_i \circ w = a_1^{k_1} \ldots a_{d-1\phantom{1}}^{k_{d-1}} \circ a_{n\phantom{1}}^{i_d + x} \circ z_i$. As $1_d \neq i_d$ then $1_d + x <_{{\bf Z}} i_d + x$ or, in case a_n is bounded by $m_n \in {\bf N}$, $(1_n + x) {\sf\phantom{1}mod\phantom{1}}m_n <_{{\bf Z}} (i_n + x) {\sf\phantom{1}mod\phantom{1}}m_n$ must hold. In case a_d is not bounded we can then set $v_d \equiv a_{n\phantom{1}}^{-1_d}$. We have to show that for all $t_j \in T(q) \backslash \{t_i \}$ there exists $v \in {\sf ORD}\/(\Sigma_d)$ such that we have $t_i \circ v \succ t_j \circ v$. Note that for all t_j with prefix $a_1^{j_1} \ldots a_{d-1\phantom{1}}^{j_{d-1}} \prec a_1^{1_1} \ldots a_{d-1\phantom{1}}^{1_{d-1}}$ we have $t_j \circ v_d \prec t_i \circ v_d$, as right multiplication with $v_d \equiv a_{n\phantom{1}}^{-1_d}$ has no influence on the prefix in ${\sf ORD}\/(\Sigma \backslash \Sigma_d)$.
Therefore, it remains to look at those terms t_j with $a_1^{j_1} \ldots a_{d-1\phantom{1}}^{j_{d-1}} \equiv a_1^{1_1} \ldots a_{d-1\phantom{1}}^{1_{d-1}}$ and $1_d \geq_{{\bf Z}} j_d$. Since there further exists $x \in {\bf Z}$ such that $1_d + x <_{{\bf Z}} i_d + x$ and $j_d +x \leq_{{\bf Z}} i_d + x$ we can again apply lemma 3 to show our claim. In case $i_d - 1_d >_{{\bf Z}} j_d - 1_d$ we are done. Else we get i_d = j_d and can apply the induction hypothesis since the distinguishing letter between $t_i \circ v_d$ and $t_j \circ$ will be of index greater than d, yielding an element $v' \in {\sf ORD}\/(\Sigma_{d+1})$ and we can set $v \equiv v_dv'$.
Now it remains to look at the case that a_d is bounded by m_d. Then we can set $v_d \equiv a_d^{m_d - i_d - 1}$ 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 $v \in {\sf ORD}\/(\Sigma_d)$ 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 qc-reducible 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²+a in our example. Then the head term of the multiple $p \ast a^{-1} = a+ \lambda$ results from the head term a² of p, but still $a + \lambda$ is not qc-reducible by p, since a² is no commutative prefix of a. Therefore, let us consider some further special multiples. For a polynomial p and a term $t \in {\sf T}(p)$ we call a term s in a multiple $p \ast w$ a t-term if $s = t \circ w$. 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 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 7 for $p \ast\lambda = a^2 + a$ and $p \ast a^{-1} = a+ \lambda$, both head terms result from the same term a² and the head term a of $p \ast a^{-1}$ is a commutative prefix of the head term a² of $p \ast\lambda$.

Lemma 11    
For $u,v \in {\cal G}$, let $p \ast u$ and $p \ast v$ be two right multiples of a non-zero polynomial $p \in {\bf K}[{\cal G}]$ such that for some term $t \in {\sf T}(p)$ the head terms are t-terms, i.e., ${\sf HT}(p \ast u) = t \circ u \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(p \ast v) = t \circ v \equiv a_1^{j_1} \ldots a_n^{j_n}$. Then there exists a term $\tilde{t} \leq_{\rm tup}a_1^{\rho_1} \ldots a_n^{\rho_n}$ where

$$\rho_l = \left\{ \begin{array}{l@{\quad\quad}l} {\sf sgn}(i_... ... {\sf sgn}(j_l) \\ 0 & \mbox{otherwise} \end{array} \right.$$

and an element $\tilde{z} \in {\cal G}$ such that ${\sf HT}(p \ast\tilde{z}) = t \circ\tilde{z} = \tilde{t}$. In particular, we have $p \ast u \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{p \ast\tilde{z}}\,$ } 0$ and $p \ast v \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{p \ast\tilde{z}}\,$ } 0$.

Proof : 1.11.1 
Let p, $p \ast u$ and $p \ast v$ be as described in the lemma and let the letters corresponding to our presentation be $\Sigma = \{a_1, \ldots, a_n,a_1^{-1}, \ldots, a_n^{-1}\}$.
We show the existence of $\tilde{z}$ by constructing a sequence $z_1, \ldots , z_n \in {\cal G}$, such that for $1 \leq l \leq n$ we have ${\sf HT}(p \ast z_l) = t \circ z_l \equiv a_1^{s_1} \ldots a_l^{s_l}r_l$ with $r_l \in {\sf ORD}\/(\Sigma_{l+1})$ and $a_1^{s_1} \ldots a_l^{s_l} \leq_{\rm tup}a_1^{\rho_1} \ldots a_l^{\rho_l}$. Then for $\tilde{z} = z_n$ our claim holds.
Let us start by constructing an element $z_1 \in {\cal G}$ such that ${\sf HT}(p \ast z_1) = t \circ z_1 \equiv a_1^{s_1}r_1$, $r_1 \in {\sf ORD}\/(\Sigma_{2})$ and $a_1^{s_1} \leq_{\rm tup}a_1^{\rho_1}$.
In case i₁ = j₁ or j₁ =0 we can set z₁ = v and $s_1 = j_1 = \rho_1$ since ${\sf HT}(p \ast v) = t \circ v \equiv a_1^{j_1} \ldots a_n^{j_n}$. Similarly in case i₁ = 0 we can set z₁ = u and $s_1 = i_1 = 0 = \rho_1$ since ${\sf HT}(p \ast u) = t \circ u \equiv a_2^{i_2}\ldots a_n^{i_n}\in{\sf ORD}\/(\Sigma_2)$. Hence let us assume $i_1 \neq j_1$ and both are non-zero.
First suppose that ${\sf sgn}(i_1) = {\sf sgn}(j_1)$. Notice that the construction in this case does not depend on whether a₁ is bounded or not. Then if $\vert i_1\vert \geq \vert j_1\vert$ we again set z₁ = v since for $s_1 = j_1 = \rho_1$ our claim holds. In case |j₁| > |i₁| we set z₁ = u because for $s_1 = i_1 = \rho_1$ our claim holds.
Now let us proceed with the case ${\sf sgn}(i_1) \neq {\sf sgn}(j_1)$, i.e., a₁ cannot be bounded. We construct $z_1 \in {\cal G}$ such that ${\sf HT}(p \ast z_1) = t \circ z_1 \in {\sf ORD}\/(\Sigma_2)$ as $\rho_1 = 0$. We claim that the letter a₁ has the same exponent for all terms in ${\sf T}(p)$, say b. In case this holds, no term in the polynomial $p \ast a_1^{-b}$ will contain the letter a₁ and the distinguishing letter between ${\sf HT}(p \ast a_1^{-b})$ and the term $t \circ a_1^{-b}$ is at least of index 2. Furthermore we know ${\sf HT}((p \ast a_1^{-b}) \ast(a_1^{b} \circ v)) = {\sf HT}(p \ast v) = t \circ v$. Thus by lemma 14 there exists an element $r \in {\sf ORD}\/(\Sigma_2)$ such that ${\sf HT}((p \ast a_1^{-b}) \ast r) = t \circ a_1^{-b} \circ r \in {\sf ORD}\/(\Sigma_2)$ and thus we can set z₁ = a₁^-br and $s_1 = 0 = \rho_1$.
Hence it remains to prove our initial claim. Suppose we have the representatives $s' \equiv a_1^{b_{s'}}x_{s'}$, $b_{s'} \in {\bf Z}$, $x_{s'} \in {\sf ORD}\/(\Sigma_2)$ for the terms $s' \in {\sf T}(p)$ and ${\sf HT}(p)=s \equiv a_1^{b_s}x_s$. Then we know $b_s \geq_{{\bf Z}} b_t$ since $t \in {\sf T}(p)$.
Hence in showing that the case $b_s >_{{\bf Z}} b_t$ is not possible we find that the exponents of a₁ in s and t are equal. To see this, let us study the possible cases. If b_s > 0 we have $b_s > b_t \geq 0$ and hence there exists no $x \in {\bf Z}$ such that $b_t + x > b_s + x \geq 0$. On the other hand b_s < 0 either implies b_t > 0 or $(b_t \leq 0$ and |b_s| > |b_t|). In both cases there exists no $x \in {\bf Z}$ 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₁ in ${\sf HT}(p \ast u)$ respectively ${\sf HT}(p \ast v)$ have different sign.
It remains to show that there cannot exist a term $s' \in {\sf T}(p)$ with $b_{s'} <_{{\bf Z}} b_s = b_t$. Let us assume such an s' exists. Since ${\sf HT}(p \ast u) = t \circ u \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(p \ast v) = t \circ v \equiv a_1^{j_1} \ldots a_n^{j_n}$ there then must exist $x_1, x_2 \in {\bf Z}$ such that $b_{s'} + x_1 <_{{\bf Z}} b_t + x_1 = i_1$ and $b_{s'} + x_2 <_{{\bf Z}} b_t + x_2 = j_1$. Without loss of generality let us assume i₁ > 0 and j₁ < 0 (the other case is symmetric). In case b_t < 0 we get that b_t + x₁ = i₁ > 0 implies x₁ > |b_t| > 0. Now, as $b_{s'} <_{{\bf Z}} b_t$ either implies b_s' > 0 or $(b_{s'} \leq 0$ and |b_s'| < |b_t|), we find b_s' + x₁ > b_t + x₁ contradicting $b_{s'} + x_1 <_{{\bf Z}} b_t + x_1$. On the other hand, in case b_t > 0 we know $b_t > b_{s'} \geq 0$. Furthermore, b_t + x₂ = j₁ < 0 implies x₂ <0 and |x₂| > b_t. Hence we get b_s' + x₂ < 0 and |b_s' + x₂| > |b_t + x₂| contradicting $b_{s'} + x_2 <_{{\bf Z}} b_t + x_2$.
Thus let us assume that for the letter a_k-1 we have constructed $z_{k-1} \in {\cal G}$ such that ${\sf HT}(p \ast z_{k-1}) = t \circ z_{k-1} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}r_{k-1} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{l_k}r'$ with $r_{k-1} \in {\sf ORD}\/(\Sigma_{k})$, $r' \in{\sf ORD}\/(\Sigma_{k+1})$ and $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} \leq_{\rm tup}a_1^{\rho_1} \ldots a_{k-1}^{\rho_{k-1}}$. We now show that we can find $z_k = z_{k-1} \circ\tilde{w} \in {\cal G}$ such that ${\sf HT}(p \ast z_{k}) = t \circ z_{k} \equiv a_1^{s_1} \ldots a_{k}^{s_{k}}r_{k}$ with $r_{k} \in {\sf ORD}\/(\Sigma_{k+1})$ and $a_1^{s_1} \ldots a_{k}^{s_{k}} \leq_{\rm tup}a_1^{\rho_1} \ldots a_{k}^{\rho_{k}}$.
This will be done in two steps. First we show that for the polynomials $p \ast u$ and $p \ast z_{k-1}$ with head terms $a_1^{i_1} \ldots a_n^{i_n}$ respectively $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{l_k}r'$ we can find an element $w_1 \in {\cal G}$ such that ${\sf HT}(p \ast z_{k-1} \ast w_1) = t \circ z_{k-1} \circ w_1 \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{\tilde{s}_{k}}\tilde{r}$, $\tilde{r} \in {\sf ORD}\/(\Sigma_{k+1})$ and $a_k^{\tilde{s}_{k}} \leq_{\rm tup}a_k^{\tilde{\rho}_{k}}$ with

$$\tilde{\rho}_k = \left\{ \begin{array}{l@{\quad\quad}l} {\sf... ...{\sf sgn}(l_k) \\ 0 & \mbox{otherwise}. \end{array} \right.$$

Then in case $a_k^{\tilde{\rho}_{k}} \leq_{\rm tup}a_k^{\rho_{k}}$ we are done and set $z_k = z_{k-1} \circ w_1$ and $s_k = \tilde{s}_{k}$. Else we can similarly proceed for the polynomials $p \ast v$ and $p \ast z_{k-1} \ast w_1$ with head terms $a_1^{j_1} \ldots a_n^{j_n}$ respectively $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{\tilde{s}_{k}}\tilde{r}$ and find an element $w_2 \in {\cal G}$ such that for $z_k = z_{k-1} \circ w_1 \circ w_2$ we have ${\sf HT}(p \ast z_{k}) = t \circ z_{k} \equiv a_1^{s_1} \ldots a_{k}^{s_{k}}r_{k}$, $r_{k} \in {\sf ORD}\/(\Sigma_{k+1})$ and $a_k^{s_{k}} \leq_{\rm tup}a_k^{\tilde{\rho}'_{k}}$ with

$$\tilde{\rho}'_k = \left\{ \begin{array}{l@{\quad\quad}l} {\s... ...}(\tilde{s}_k) \\ 0 & \mbox{otherwise}. \end{array} \right.$$

Then we can conclude $a_k^{s_{k}} \leq_{\rm tup}a_k^{\rho_{k}}$ as in case s_k = 0 we are immediately done and otherwise we get ${\sf sgn}(j_k) = {\sf sgn}(\tilde{s}_k) = {\sf sgn}(\tilde{\rho}_k) = {\sf sgn}(i_k)$ and $\min \{ \vert i_k\vert, \vert\tilde{s}_k\vert, \vert j_k\vert \} \leq \min \{ \vert i_k\vert, \vert j_k\vert \}$.
Let us hence show how to construct w₁. Remember that ${\sf HT}(p \ast u) = t \circ u \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(p \ast z_{k-1}) = t \circ z_{k-1} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{l_k}r'$ for some $r' \in{\sf ORD}\/(\Sigma_{k+1})$. In case i_k = l_k or l_k = 0 we can set $w_1 = \lambda$ and $\tilde{s}_k = l_k = \tilde{\rho}_k$ as ${\sf HT}(p \ast z_{k-1}) = t \circ z_{k-1} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{l_k}r'$. Hence let $i_k \neq l_k$ and $l_k \neq 0$.
First let us assume that ${\sf sgn}(i_k) = {\sf sgn}(l_k)$. Then in case $\vert i_k\vert \geq \vert l_k\vert$ we are done by setting $w_1 = \lambda$ as again ${\sf HT}(p \ast z_{k-1}) = t \circ z_{k-1} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{l_k}r'$ will do with $\tilde{s}_k = l_k = \tilde{\rho}_k$. Therefore, let us assume that |l_k| > |i_k|. Without loss of generality let us assume that a_k is not bounded¹². Then we consider the multiple $p \ast z_{k-1} \ast a_k^{-l_k+i_k}$, i.e., the exponent of the letter a_k in the term $t \circ z_{k-1} \circ a_k^{-l_k+i_k}$ will be i_k. If ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k+i_k}) = t \circ z_{k-1} \circ a_k^{-l_k+i_k}$ we are done because then $t \circ z_{k-1} \circ a_k^{-l_k+i_k} \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{i_{k}}\tilde{r}_k$ for some $\tilde{r}_k \in {\sf ORD}\/(\Sigma_{k+1})$ and we can set w₁ = a_k^-l_k+i_k and $\tilde{s}_k = i_k = \tilde{\rho}_k$. Otherwise we show that the t-term $t \circ z_{k-1} \circ a_k^{-l_k+i_k}$ in this multiple can be brought to head position using an element $r \in {\sf ORD}\/(\Sigma_{k+1})$ thus allowing to set $\tilde{s}_k = i_k = \tilde{\rho}_k$ and w₁ = a_k^-l_k+i_kr as then we have ${\sf HT}(p \ast z_{k-1} \ast w_1) = t \circ z_{k-1} \circ w_1 = a_1^{s_1} \ldo... ...rc a_k^{-l_k+i_k}r \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{i_k}\tilde{r}$ where $a_k^{l_k}r' \circ a_k^{-l_k+i_k}r \equiv a_k^{i_k}\tilde{r}$. (Note that the product of two elements in ${\sf ORD}\/(\Sigma_{i})$ is again an element in ${\sf ORD}\/(\Sigma_{i})$) This follows immediately if we can prove that the exponent of a_k in the term ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k + i_k})$ is also i_k. Then we can apply lemma 14 to the polynomial $p \ast z_{k-1} \ast a_k^{-l_k+i_k}$ and the term $t \circ z_{k-1} \circ a_k^{-l_k+i_k}$. Note that ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k + i_k})$ and $t \circ z_{k-1} \circ a_k^{-l_k+i_k}$ have then distinguishing letter of at least index k+1 and further ${\sf HT}((p \ast z_{k-1} \ast a_k^{-l_k+i_k}) \ast a_k^{-l_k+i_k}) = {\sf HT}(p \ast z_{k-1})= t \circ z_{k-1}$. Therefore, we show that the exponent of a_k in the term ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k + i_k})$ is also i_k. Let $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{b_k}r''$ with $r'' \in {\sf ORD}\/(\Sigma_{k+1})$ be the term in $p \ast z_{k-1}$ that became head term (note that a candidate in ${\sf T}(p \ast z_{k-1})$ for the head term in $p \ast z_{k-1} \ast a_k^{-l_k+i_k}$ must have prefix $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}$ since ${\sf HT}(p \ast z_{k-1}) \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}r_{k-1}$ and multiplication with a_k^{-l_k + i_k} only involves r_k-1), i.e., $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{b_k}r'' \circ a_k^{-l_k+i_k} \equiv a_... ...dots a_{k-1}^{s_{k-1}} a_k^{i_k} y \equiv t \circ z_{k-1} \circ a_k^{-l_k+i_k}$ for some $x,y \in {\sf ORD}\/(\Sigma_{k+1})$ and therefore $c_k \geq_{{\bf Z}} i_k$. Then by lemma 4 there exist $z_1 \in {\sf ORD}\/(\Sigma \backslash \Sigma_{k-1})$ and $z_2 \in {\sf ORD}\/(\Sigma_k)$ such that $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{i_k} y \circ z_1 = a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} \circ a_k^{i_k + f_k} \circ z$ for some $z \in {\sf ORD}\/(\Sigma_{k+1})$ and $a_k^{i_k + f_k} \circ z \circ z_2 \equiv a_k^{i_k}a_{k+1}^{i_{k+1}} \ldots a_n^{i_n}$, i.e., $z_2 = a_k^{-f_k} \circ z_2'$ for some $z_2' \in {\sf ORD}\/(\Sigma_{k+1})$. Note that the t-term is brought to head position by this multiplication. Now multiplying ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k + i_k})$ by z₁z₂ we find $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{c_k} x \circ z_1z_2 \equiv a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} a_k^{c_k + f_k - f_k}\tilde{x}$ for some $\tilde{x} \in {\sf ORD}\/(\Sigma_{k+1})$. This gives us $c_k \leq_{{\bf Z}} i_k$ and thus $i_k \leq_{{\bf Z}} c_k$ yields c_k = i_k.
Finally, we have to check the case that ${\sf sgn}(i_k) \neq {\sf sgn}(l_k)$, i.e., a_k is not bounded in this case, and $l_k \neq 0$. Let us take a look at the polynomial $p \ast z_{k-1} \ast a_k^{-l_k}$, i.e., the exponent of the letter a_k in the term $t \circ z_{k-1} \circ a_k^{-l_k}$ will be 0. Suppose ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k}) \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{c_k}x$, for some term $s \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{b_s}x_s \in {\sf T}(p \ast z_{k-1})$, $x, x_s \in {\sf ORD}\/(\Sigma_{k+1})$, i.e., c_k = b_s - l_k. In case this head term is already the corresponding t-term $t \circ z_{k-1} \circ a_k^{-l_k}$, we are done and we set w₁ = a_k^-l_k and $\tilde{s}_k = 0 = \tilde{\rho}_k$. Now if we can show c_k = 0, by lemma 14 the t-term $t \circ z_{k-1} \circ a_k^{-l_k}$ can be brought to head position using an element in ${\sf ORD}\/(\Sigma_{k+1})$ since the distinguishing letter between ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k})$ and the term $t \circ z_{k-1} \circ a_k^{-l_k}$ then has at least index k+1 and we know ${\sf HT}((p \ast z_{k-1} \ast a_k^{-l_k}) \ast a_k^{l_k}) = {\sf HT}(p \ast z_{k-1}) =t \circ z_{k-1}$. Hence, in showing that c_k=0 we are done. As before there exist $z_1 \in {\sf ORD}\/(\Sigma \backslash \Sigma_{k-1})$ and $z_2 \in {\sf ORD}\/(\Sigma_k)$ such that $t \circ z_{k-1} \circ a_k^{-l_k} \circ z_1 \equiv a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} a_k^{f_k}z$ for some $z \in {\sf ORD}\/(\Sigma_{k+1})$ and $a_k^{f_k}z \circ z_2 \equiv a_{k}^{i_{k}} \ldots a_n^{i_n}$, i.e., $z_2 \equiv a_k^{-f_k + i_k}z_2'$ for some $z_2' \in {\sf ORD}\/(\Sigma_{k+1})$. Remember that this multiplication brings the t-term to head position. Hence multiplying ${\sf HT}(p \ast z_{k-1} \ast a_k^{-l_k})$ by z₁z₂ we find $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{c_{k}}x \circ z_1z_2 \equiv a_1^{i_1} \ldots a_{k-1}^{i_{k-1}}a_{k}^{c_k + i_{k}}\tilde{x}$ for some $\tilde{x} \in {\sf ORD}\/(\Sigma_{k+1})$. Thus we know $c_k + i_k \leq_{{\bf Z}} i_k$. 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 s-term $s \circ a_k^{-l_k}$ for some $s \in {\sf T}(p\ast z_{k-1})$ we know $b_s \leq_{{\bf Z}} l_k$. In case i_k = 0, we have $c_k \leq_{{\bf Z}} 0$ implying c_k = 0. In case i_k > 0 then $c_k + i_k = b_s - l_k + i_k \leq_{{\bf Z}} i_k$ implies $0 \leq b_s - l_k + i_k \leq i_k$. Furthermore, as l_k < 0 we have -l_k + i_k > i_k implying b_s < 0 and hence $\vert b_s\vert \leq \vert l_k\vert$. But then $b_s - l_k \geq 0$ and $0 \leq b_s - l_k + i_k \leq i_k$ yields c_k = b_s - l_k = 0. On the other hand, i_k < 0 and l_k > 0 imply $0 \leq b_s \leq l_k$ and hence b_s - l_k + i_k <0 yielding $\vert b_s - l_k + i_k\vert \leq \vert i_k\vert$. Since $b_s - l_k \leq 0$ 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 qc-reducible to zero in one step by one of them. Such a property of a set of polynomials is called qc-saturation. In example 7 the multiples $p \ast a^{-1} = a+ \lambda$ and $p \ast a^{-2} = a^{-1} + \lambda$ give us a qc-saturating set for p = a²+a.

Definition 11    
A set $S \subseteq \{ p \ast w \mid w \in {\cal G}\}$ is called a qc-saturating set for a non-zero polynomial p in ${\bf K}[{\cal G}]$, if for all $w \in {\cal G}$, $p \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{S}\,$ } 0$. A set of polynomials $F \subseteq {\bf K}[{\cal G}]$ is called qc-saturated, if for all $f \in F$ and for all $w \in {\cal G}$, $f \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } 0$. $\diamond$

A further consequence of the previous lemmata is that finite qc-saturating sets exist and that they can be computed.

llProcedureQUASI-COMMUTATIVE SATURATION
 
Given: 		 A non-zero polynomial 

$p \in {\bf K}[{\cal G}]$.
Find: 		 

$\mbox{\sc Sat}_{qc}(p)$,
a qc-saturating set for p.
 
for all 

$t \in {\sf T}(p)$
do
		 St := $\emptyset$;
		 if 		 t can be brought to head position
		 		then 		 compute 

$q = p \ast w$
with 

${\sf HT}(p
\ast w) = t \circ w$
		 		 		  Ht := 

$\{ s \in {\cal G}\mid {\sf HT}(q) \geq_{\rm tup}s\}$;
		 		 		 % These are candidates for ``smaller''  polynomials with t-head terms
		 		 		 q := 

$\min\{ p \ast({\sf inv}\/(t) \circ s) \mid s \inH_t, {\sf HT}(p \ast({\sf inv}\/(t) \circ s)) = s\}$;
		 		 		  St := $\{ q \}$;
		 endif 
endfor 


$\mbox{\sc Sat}_{qc}(p)$
:= 

$\bigcup_{t \in {\sf T}(p)} S_t\;\;\;$
% S contains at most 

$\vert{\sf T}(p)\vert$ 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 qc-saturation 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 qc-saturating set for the polynomial $g = 2 \cdot a_1^{-2}a_2^3 - 4 \cdot a_1^2a_2^3 - a_1a_2^2 + a_1a_2$ on page is $\mbox{\sc Sat}_{qc}(g) = \{ g \ast a_1a_2^{-1} = 2 \cdot a_1^{-1}a_2^2 - 4 \cdo... ...ast a_1^2a_2^{-1} = - 4 \cdot a_1^4a_2^2 - a_1^3a_2 + a_1^3 + 2 \cdot a_2^2 \}$ while the symmetrized set consisted of the polynomials ${\cal S}(g) = \{ g \ast a_2^{-1}, -g \ast a_1a_2^{-1}, g \ast a_1^{-1}a_2^{-2} \}$.

Lemma 12    
For a saturated set F of polynomials in ${\bf K}[{\cal G}]$, $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(F)}$ holds.

Proof : 1.11.1 
$\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } \subseteq\;\; \equiv_{{\sf ideal}_{r}^{}(F)}$ is an immediate consequence of the definition of qc-reduction. To show that the converse also holds, let $p - q \in {\sf ideal}_{r}^{}(F)$. Then $p = q + \sum_{i=1}^m \alpha_i \cdot f_i \ast u_i, \in {\bf K}, f_i \in G, u_i \in {\cal G}$ and we show that $p \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$ by induction on m. Without loss of generality we can assume that for every multiple $f_i \ast u_i$, ${\sf HT}(f_i \ast u_i) = {\sf HT}(f_i) \circ u_i \geq_{\rm tup}{\sf HT}(f_i)$ holds. In case m=0 we are done as then p=q. Hence let $p = q + \sum_{i=1}^m \alpha_i \cdot f_i \ast u_i + \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$. Then the induction hypothesis yields $p \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } q + \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$. Now let $t = {\sf HT}(f_{m+1} \ast u_{m+1})$ and $t\geq_{\rm tup}{\sf HT}(f_{m+1})$. Furthermore, let $\beta_1$ respectively $\beta_2$ be the coefficient of t in q respectively $q+ \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$. Then in case $t \not\in {\sf T}(q)$ we get $q+ \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1} \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f_{m+1}}\,$ } p$. In case $t \not\in {\sf T}(p)$ we similarly get $p - \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f_{m+1}}\,$ } q$. As $p - \alpha_{m+1} \cdot f_{m+1} \ast u_{m+1} = q + \sum_{j=1}^{m} \alpha_{j} \cdot f_j \ast u_{j}$ the induction hypothesis yields $p - \alpha_{m+1} \cdot f_{m+1} \ast u_{m+1} \mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm qc}}_{F}\,$ } q$ and hence we are done. Otherwise let $\beta_1 \neq 0$ be the coefficient of t in $q+ \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$ and $\beta_2 \neq 0$ the coefficient of t in q.
This gives us a qc-reduction step
$q + \alpha_{m+1} \cdot f_{m+1} \ast u_{m+1} \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f_{m+1}}\,$ }$
$q + \alpha_{m+1} \cdot f_{m+1} \ast u_{m+1} - \beta_1 \cdot{\sf HC}(f_{m+1})^{-1} \cdot f_{m+1} \ast u_{m+1} =$
$q - (\beta_1 \cdot{\sf HC}(f_{m+1})^{-1} -\alpha_{m+1}) \cdot f_{m+1} \ast u_{m+1}$
eliminating the occurrence of t in $q+ \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$.
Then obviously $\beta_2 = (\beta_1 \cdot{\sf HC}(f_{m+1})^{-1} -\alpha_{m+1}) \cdot{\sf HC}(f_{m+1})$ and, therefore, we have $q \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{f_{m+1}}\,$ } q - (\beta_1 \cdot{\sf HC}(f_{m+1})^{-1} -\alpha_{m+1}) \cdot f_{m+1} \ast u_{m+1}$, i.e., q and $q+ \alpha_{m+1}\cdot f_{m+1} \ast u_{m+1}$ are joinable.
q.e.d.

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

Definition 12    
For $p_{1}, p_{2} \!\in \!{\bf K}[{\cal G}]$ such that ${\sf HT}(p_1) \!\equiv\! a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(p_2) \!\equiv\! a_1^{j_1} \ldots a_n^{j_n}$ with either $i_l \cdot j_l = 0$ or ${\sf sgn}(i_l)={\sf sgn}(j_l)$ for $1 \leq l \leq n$ we can define an s-polynomial, and setting

$$\rho_l = \left\{ \begin{array}{l@{\quad\quad}l} {\sf sgn}(j_... ... 0 \\ {\sf sgn}(i_l) & \mbox{otherwise} \end{array} \right.$$

the situation $a_1^{\rho_1 \cdot\max \{ \vert i_1\vert,\vert j_1\vert \}}\ldots a_{n\phantom{... ... i_n\vert,\vert j_n\vert \}}= {\sf HT}(p_1) \circ w_1 = {\sf HT}(p_2) \circ w_2$ for some $w_1,w_2 \in {\cal G}$ gives us

$${\sf spol}_{}(p_{1}, p_{2}) = {\sf HC}(p_1)^{-1} \cdot p_1 \ast w_1 - {\sf HC}(p_2)^{-1} \cdot p_2 \ast w_2.$$

$\diamond$

Notice that ${\sf HT}(p_i) \leq_{\rm tup}a_1^{\rho_1 \cdot\max \{ \vert i_1\vert,\vert j_1\v... ...ldots a_{n\phantom{1}}^{\rho_n \cdot\max \{ \vert i_n\vert,\vert j_n\vert \}}$ for $i \in \{ 1,2 \}$ holds in case such an s-polynomial exists. Furthermore, if there exists a term t such that $t \geq_{\rm tup}{\sf HT}(p_1)\equiv a_1^{i_1} \ldots a_n^{i_n}$ and $t \geq_{\rm tup}{\sf HT}(p_2) \equiv a_1^{j_1} \ldots a_n^{j_n}$, an s-polynomial always exists since then the condition for the existence of an s-polynomial is fulfilled as the tuple-ordering requires that the exponent of a letter a_i in the tuple-smaller term is either zero or has the same sign as the exponent of a_i in the tuple-larger term. We even have $t \geq_{\rm tup}a_1^{\rho_1 \cdot\max \{ \vert i_1\vert,\vert j_1\vert \}}\ldots a_{n\phantom{1}}^{\rho_n \cdot\max \{ \vert i_n\vert,\vert j_n\vert \}}$.

Again for the case of free Abelian groups this definition corresponds to the definition of critical pairs for Laurent polynomials and the resulting t-polynomials are a specialization of these s-polynomials for the integer group ring¹³.

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

Theorem 3    
For a qc-saturated set $G \subseteq {\bf K}[{\cal G}]$ the following statements are equivalent:

1.

For all polynomials $g \in {\sf ideal}_{r}^{}(G)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } 0$.

2.

For all polynomials $f_{k}, f_{l} \in G$ we have ${\sf spol}_{}(f_{k}, f_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } 0$.

Proof : 1.11.1 
$1 \Longrightarrow2:$ By definition 12 in case for $f_{k}, f_{l} \in G$ the s-polynomial exists we get

$${\sf spol}_{}(f_{k}, f_{l}) = {\sf HC}(f_k)^{-1} \cdot f_{k} ... ...-{\sf HC}(f_l)^{-1} f_{l} \ast w_2 \:\in {\sf ideal}_{r}^{}(G),$$

and then ${\sf spol}_{}(f_{k}, f_{l}) \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } 0$.

$2 \Longrightarrow1:$ We have to show that every non-zero element $g \in {\sf ideal}_{r}^{}(G)$ is $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$-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 $h \in {\sf ideal}_{r}^{}(G)$, $h \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ } h'$ implies $h' \in {\sf ideal}_{r}^{}(G)$. Thus as $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$ is Noetherian it suffices to show that every $g \in {\sf ideal}_{r}^{}(G) \backslash \{ 0 \}$ is $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$-reducible. Let $g = \sum_{j=1}^m \alpha_{j} \cdot f_{j} \ast w_{j}$ be a representation of a non-zero polynomial g such that $\alpha_{j} \in {\bf K}^*, f_j \in F, w_{j} \in {\cal G}$. Since G is qc-saturated we can assume $g= \sum_{j=1}^m \alpha_j \cdot g_j \ast v_j$, where $\alpha_j \in {\bf K}^*, g_j \in G, v_j \in {\cal G}$ and ${\sf HT}(g_{j} \ast v_{j}) = {\sf HT}(g_{j}) \circ v_{j} \geq_{\rm tup}{\sf HT}(g_j)$. Depending on this representation of g and our well-founded total ordering on ${\cal G}$ we define $t = \max \{ {\sf HT}(g_{j})\circ v_{j} \mid j \in \{ 1, \ldots m \} \}$ and K is the number of polynomials $g_j \ast v_j$ containing t as a term. Then $t \succeq {\sf HT}(g)$ and in case ${\sf HT}(g) = t$ this immediately implies that g is $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{G}\,$ }$-reducible. Otherwise we show that g has a special representation (a standard representation corresponding to qc-reduction which is a right commutative prefix standard representation) where all terms are bounded by ${\sf HT}(g)$, as this implies that g is top-reducible using G. This will be done by induction on (t,K), where (t',K')<(t,K) if and only if $t' \prec t$ or (t'=t and K'<K). Note that this ordering is well-founded since $\geq_{\rm syll}$ is and $K \in{\bf N}$. In case $t \succ {\sf HT}(g)$ there are two (not necessarily different) polynomials g_k,g_l in the corresponding representation such that $t = {\sf HT}(g_k) \circ v_k = {\sf HT}(g_l) \circ v_l$ and we have $t \geq_{\rm tup}{\sf HT}(g_k)$, $t \geq_{\rm tup}{\sf HT}(g_l)$. Hence by definition 12 there exists an s-polynomial ${\sf spol}_{}(g_k,g_l) = {\sf HC}(g_k)^{-1} \cdot g_k \ast z_1- {\sf HC}(g_l)^{-1} \cdot g_l \ast z_2$