6. Reduction in Polycyclic Group Rings

Let ${\cal G}$ be a polycyclic group given by a convergent PCP-presentation. As we have seen in section 2, due to the more general form of the commutation rules, lemma 5 no longer holds for right multiples. But using lemma 6 , we can define a reduction based on commutative prefixes now using left multiples which enables us to study left ideal congruences, and later on even ideal congruences.

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

(a)

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

(b)

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

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

Notice that if f lpc-reduces p at $\alpha \cdot t$ to q, then t no longer is a term in q and by lemma 6, 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 13    
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 lpc}}_{F}\,$ } h$. Then there are polynomials $p',q' \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{F}\,$ } q'$ and h=p'-q'.

2.

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

Proof : 1.11.1 
This can be shown as lemma 9.
q.e.d.

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

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

Again we find that in our setting we have to be more careful, as for lpc-reduction $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm lpc}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{l}^{}(G)}$ in general does not hold. One reason for this phenomenon is that a reduction step is not preserved under left multiplication with elements of ${\cal G}$.

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

We will now introduce how we can extend the expressiveness of lpc-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 lpc-reduction. First let us take a look at what multiples are appropriate to later on enable an effective characterization of a left Gröbner basis. We proceed similar to the case of qc-reduction for nilpotent groups rings.

Lemma 14    
Let p be a non-zero polynomial in ${\bf K}[{\cal G}]$. Then it is decidable for $t \in {\sf T}(p)$ whether there exists an element $w \in {\cal G}$ such that ${\sf HT}(w \ast p ) = w \circ t$.

Proof : 1.11.1 
We show that for a finite set of terms $T = \{ t_1, \ldots , t_s \}$, where without loss of generality t₁ is the greatest term, the following holds: In case there exists $w \in {\cal G}$ such that for some $t_i \in T \backslash \{ t_1 \}$ we have $w \circ t_i \succ w \circ t_j$ for all $t_j \in T \backslash \{ t_i \}$, then we can effectively construct $v \in {\cal G}$ such that $v \circ t_i \succ v \circ t_j$ for all $t_j \in T \backslash \{ t_i \}$ also holds without knowing w.
This will be done by induction on k where $T \subseteq{\sf ORD}\/(\Sigma_{n-k})$.
In the base case k=0 we get $T \subseteq{\sf ORD}\/(\Sigma_n)$, hence $t_1 \equiv a_n^{1_n}$, $t_i \equiv a_n^{i_n}$ and $1_n >_{{\bf Z}} i_n$. By our assumption there exists $w \in {\cal G}$ with $w \equiv w' a_n^{w_n}$, $w' \in {\sf ORD}\/(\Sigma \backslash \Sigma_n)$ such that $w \circ t_i \succ w \circ t_j$ must hold for all $t_j \in T \backslash \{ t_i \}$. We have to consider two cases. First let us assume that the letter a_n is not bounded. Then let us set $v \equiv a_{n}^{-1_n}$. We have to show that for all $t_j \in T \backslash \{ t_i \}$ we have $-1_n + i_n >_{{\bf Z}} - 1_n + j_n$. The case t_j = t₁ is trivial and for each $t_j \in T \backslash \{ t_1, t_i \}$ the equation is a consequence of 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, namely w_n, such that $1_n + x <_{{\bf Z}} i_n + x$ and $j_n + x <_{{\bf Z}} i_n + x$. Now in case a_n is bounded by $m_n \in {\bf N}$ we can set $v \equiv a_n^{m_n - i_n - 1}$. We find that since for all $t_j \in T \backslash \{ t_i \}$, we have $i_n \neq j_n$ and $v \circ t_i \equiv a_n^{m_n -1}$, for all other multiples $v \circ t_j \equiv a_n^{x_j}$, x_j < m_n -1 must hold.
In the induction step let us assume k>0 and again without loss of generality t₁ is the largest term in $T \subseteq{\sf ORD}\/(\Sigma_{n-k})$. By our assumption there exists $w \in {\cal G}$ such that $w \circ t_i \succ w \circ t_j$ for all $t_j \in T \backslash \{ t_i \}$. Let a_d be the distinguishing letter between $t_1 \equiv a_{n-k}^{1_{n-k}} \ldots a_n^{1_n}$ and $t_i \equiv a_{n-k}^{i_{n-k}} \ldots a_n^{i_n}$, and let $w \equiv w'w''a_{d}^{w_d}w'''$ with $w' \in {\sf ORD}\/(\Sigma \backslash \Sigma_{n-k})$, $w'' \in {\sf ORD}\/(\{a_{n-k+1}, \ldots , a_{d-1}\})$, $w''' \in {\sf ORD}\/(\Sigma_{d+1})$. As before let us first consider the case that the letter a_d is not bounded. Then there exist $l_{n-k}, \ldots , l_{d-1}, x \in {\bf Z}$, $z_1, z_i \in {\sf ORD}\/(\Sigma_{d+1})$ such that $w \circ t_1 = w'w''a_d^{w_d}w''' \circ a_{n-k}^{1_{n-k}} \ldots a_n^{1_n} \equiv w' a_{n-k}^{l_{n-k}} \ldots a_{d-1}^{l_{d-1}} a_d^{w_d + 1_d + x} z_1$, $w \circ t_i \equiv w' a_{n-k}^{l_{n-k}} \ldots a_{d-1}^{l_{d-1}} a_d^{w_d + i_d + x} z_i$. Now let us set $v_d = (a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}}) \circ a_d^{- 1_d} \circ{\sf inv}\/(a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}})$. Since $v_d \circ t_1 = (a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}}) \circ a_d^{- 1_d... ..._{n-k}} \ldots a_n^{1_n} \equiv a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}} y_1$ and $v_d \circ t_i = a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}} a_d^{-1_d + i_d} y_i$ with $y_1,y_i \in {\sf ORD}\/(\Sigma_{d+1})$, $v_d \circ t_i \succ v_d \circ t_1$ holds. It remains to study $v_d \circ t_j$ for all $t_j \in T \backslash \{ t_1, t_i \}$. In case the distinguishing letter between t_i and t_j has index $s \leq d$ we must have $t_j \prec t_i$, as $t_j \prec t_1$ and therefore $j_s <_{{\bf Z}} i_s = 1_s$ respectively $j_d <_{{\bf Z}} i_d <_{{\bf Z}} 1_d$ must hold. Then $t_i \equiv x_i a_s^{i_s} y_i$ and $t_j \equiv x_i a_s^{j_s} y_j$ with $x_i \in {\sf ORD}\/(\Sigma \backslash \Sigma_s)$, $y_i, y_j \in {\sf ORD}\/(\Sigma_{s+1})$ and $v_d \circ t_j = (a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}}) \circ a_d^{- 1_d} ... ...e{z}_j \equiv a_{n-k}^{1_{n-k}} \ldots a_{s-1}^{1_{s-1}} a_s^{j_s} \tilde{z}_j$ with $z_j, \tilde{z}_j \in {\sf ORD}\/(\Sigma_{s+1})$ and and similarly $v_d \circ t_i = a_{n-k}^{1_{n-k}} \ldots a_{s-1}^{1_{s-1}} a_s^{i_s - i_s + i_... ...e{z}_i \equiv a_{n-k}^{1_{n-k}} \ldots a_{s-1}^{1_{s-1}} a_s^{i_s} \tilde{z}_i$ with $\tilde{z}_i \in {\sf ORD}\/(\Sigma_{s+1})$ thus implying $v_d \circ t_i \succ v_d \circ t_j$. Otherwise let $T' = \{ y_j \mid t_j \in T, t_j \equiv a_{n-k}^{i_{n-k}} \ldots a_{d}^{i_{d}}y_j, y_j \in {\sf ORD}\/(\Sigma_{d+1}) \}$. Then $T' \subseteq{\sf ORD}\/(\Sigma_{d+1}) \subset {\sf ORD}\/(\Sigma_{n-k})$ and still for $w \in {\cal G}$ from above we can conclude $(w \circ a_{n-k}^{i_{n-k}} \ldots a_{d}^{i_{d}}) \circ y_i \succ (w \circ a_{n-k}^{i_{n-k}} \ldots a_{d}^{i_{d}}) \circ y_j$ for the terms $y_j \in T' \backslash \{ y_i \}$. Hence by our induction hypothesis $v_{d+1} \in {\cal G}$ can be constructed such that $v_{d+1} \circ y_i \succ v_{d+1} \circ y_j$. Now we can combine v_d and v_d+1 in order to construct v as follows: let us set $v = v_d \circ(a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}})\circ a_d^{i_d} \circ ... ...circ a_d^{- i_d} \circ {\sf inv}\/(a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}})$. Then we get $v \circ t_i \succ v \circ t_j$ for all $t_j \in T \backslash \{ t_i \}$ since $v \circ t_j = (a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}}) \circ a_d^{-1_d + i_... ...c y_j \equiv a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}} a_d^{- 1_d + i_d} z_j$ and similarly $v_d \circ t_i \equiv a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}} a_d^{- 1_d + i_d} z_i$ with $z_j, z_i \in {\sf ORD}\/(\Sigma_{d+1})$ and by the definition of v_d+1 we also know $v_{d+1} \circ y_j = z_j \prec z_i = v_{d+1} \circ y_i$ proving our claim.
Now it remains to check the case where a_d is bounded by m_d. We can set $v_d = (a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}}) \circ a_d^{m_d - i_d -1} \circ{\sf inv}\/(a_{n-k}^{1_{n-k}} \ldots a_{d-1}^{1_{d-1}})$, and as above an element v can be constucted such that $v \circ t_i \succ v \circ t_j$ for all $t_j \in T \backslash \{ t_i \}$.
q.e.d.

1.11 Notice that the proof of this lemma shows that there is an algorithm which computes some $v \in {\cal G}$ as desired in case it exists and that the element w need not be known for this computation. Hence we can enrich a polynomial by the set of those multiples which bring other terms of the polynomial to head position. But still there remain cases of multiples which are not lpc-reducible. Just take a look at the polynomial p = a²+a in our example. Then the head term of the multiple $a^{-1} \ast p = a+ \lambda$ results from the head term a² of p, but still $a + \lambda$ is not lpc-reducible by p, as 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 $w \ast p$ a t-term if $s = w \circ t$. The following lemma states that if in two left-multiples of a polynomial the head terms result from the same term t, then there is also a left multiple of the polynomial with a t-term as head term which is in some sense a common commutative prefix of the head terms of the original two multiples. In example 9 for $\lambda\ast p = a^2 + a$ and $a^{-1} \ast p = a+ \lambda$, both head terms result from the same term a² and the head term a of $a^{-1} \ast p$ is a commutative prefix of the head term a² of $\lambda\ast p$.

Lemma 15    
For $u,v \in {\cal G}$, let $u \ast p$ and $v \ast p$ be two left 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}(u \ast p) = u \circ t \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(v \ast p) = v \circ t \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}(\tilde{z} \ast p) = \tilde{z} \circ t = \tilde{t}$. In particular, we have $u \ast p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{\tilde{z} \ast p}\,$ } 0$ and $v \ast p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{\tilde{z} \ast p}\,$ } 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}(z_l \ast p) = z_l \circ t \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}(z_1 \ast p) = z_1 \circ t \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}(v \ast p) = v \circ t \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}(u \ast p) = u \circ t \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 proof 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)$, hence a₁ cannot be bounded. We construct $z_1 \in {\cal G}$ such that ${\sf HT}(z_1 \ast p) = z_1 \circ t \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 $a_1^{-b} \ast p$ will contain the letter a₁ and the distinguishing letter between ${\sf HT}(a_1^{-b} \ast p)$ and the term $a_1^{-b} \circ t$ is at least of index 2. Furthermore we know ${\sf HT}((v \circ a_1^{b}) \ast(a_1^{-b} \ast p)) = {\sf HT}(v \ast p) = v \circ t$. Thus by the construction given in the proof of lemma 14 there exists an element $r \in {\sf ORD}\/(\Sigma_2)$ such that ${\sf HT}(r \ast(a_1^{-b} \ast p)) = r \circ a_1^{-b} \circ t \in {\sf ORD}\/(\Sigma_2)$ and thus we can set $z_1 = r \circ a_1^{-b}$ and $s_1 = 0 = \rho_1$.
Hence it remains to prove that the exponents of a₁ have the desired property. 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}(u \ast p)$ respectively ${\sf HT}(v \ast p)$ 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}(u \ast p) = u \circ t \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(v \ast p) = v \circ t \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}(z_{k-1} \ast p) = z_{k-1} \circ t \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 = \tilde{w} \circ z_{k-1} \in {\cal G}$ such that ${\sf HT}(z_{k} \ast p) = z_{k} \circ t \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 $u \ast p$ and $z_{k-1} \ast p$ 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}(w_1 \ast z_{k-1} \ast p) = w_1 \circ z_{k-1} \circ t \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 = w_1 \circ z_{k-1}$ and $s_k = \tilde{s}_{k}$. Else we can similarly proceed for the polynomials $v \ast p$ and $w_1 \ast z_{k-1} \ast p$ 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 = w_2 \circ w_1 \circ z_{k-1}$ we have ${\sf HT}(z_{k} \ast p) = z_{k} \circ t \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}(u \ast p) = u \circ t \equiv a_1^{i_1} \ldots a_n^{i_n}$ and ${\sf HT}(z_{k-1} \ast p) = z_{k-1} \circ t \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}(z_{k-1} \ast p) = z_{k-1} \ast t \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)$. Without loss of generality we can assume that a_k is not bounded¹⁴. Then in case $\vert i_k\vert \geq \vert l_k\vert$ we are done by setting $w_1 = \lambda$ as again ${\sf HT}(z_{k-1} \ast p) = z_{k-1} \circ t \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|. Then we consider the multiple $y \ast z_{k-1} \ast p$, where $y = (a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}) \circ a_k^{-l_k+i_k} \circ{\sf inv}\/(a_1^{s_1} \ldots a_{k-1}^{s_{k-1}})$, i.e., the exponent of the letter a_k in the term $y \circ z_{k-1} \circ t$ will be i_k. If ${\sf HT}(y \ast z_{k-1} \ast p) = y \circ z_{k-1} \circ t$ we are done because then $y \circ z_{k-1} \circ t \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₁ = y and $\tilde{s}_k = i_k = \tilde{\rho}_k$. Otherwise we show that the t-term $y \circ z_{k-1} \circ t$ in this multiple can be brought to head position using an element $r \in {\cal G}$ such that we have ${\sf HT}((r \circ y) \ast z_{k-1} \ast p) = r \circ y \circ z_{k-1} \circ t = r... ..._{k-1}}a_k^{l_k}r' \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{i_k}\tilde{r}$, where $\tilde{r} \in {\sf ORD}\/(\Sigma_{k+1})$, thus allowing to set $\tilde{s}_k = i_k = \tilde{\rho}_k$ and $w_1 = r \circ y$. This follows immediately if we can prove that the exponent of a_k in the term ${\sf HT}(y \ast z_{k-1} \ast p)$ is also i_k. Then we can apply lemma 14 to the polynomial $y \ast z_{k-1} \ast p$ and the term $y \circ z_{k-1} \circ t$. Note that ${\sf HT}(y \ast z_{k-1} \ast p)$ and $y \circ z_{k-1} \circ t$ have then distinguishing letter of at least index k+1 and further ${\sf HT}({\sf inv}\/(y) \ast(y \ast z_{k-1} \ast p)) = {\sf HT}(z_{k-1} \ast p)= z_{k-1} \circ t$. Therefore, we show that the exponent of a_k in the term ${\sf HT}(y \ast z_{k-1} \ast p)$ 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 $z_{k-1} \ast p$ that became head term (note that a candidate in ${\sf T}(z_{k-1} \ast p)$ for the head term in $y \ast z_{k-1} \ast p$ must have prefix $a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}$ since ${\sf HT}(z_{k-1} \ast p) \equiv a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}r_{k-1}$) and multiplication with y gives us $y \circ a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{b_k}r'' \equiv a_1^{s_1} \ldot... ... a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{i_k} w \equiv y \circ z_{k-1} \circ t$ for some $x,w \in {\sf ORD}\/(\Sigma_{k+1})$ and we have $c_k \geq_{{\bf Z}} i_k$. Then there exist $z_1, z_2 \in {\cal G}$ such that $z_1 \circ a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_k^{i_k} y\equiv a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} a_k^{i_k + f_k}z$ for some $z \in {\sf ORD}\/(\Sigma_{k+1})$ and $z_2 \circ a_1^{i_1} \ldots a_{k-1}^{i_{k-1}}a_k^{i_k + f_k}z \equiv a_1^{i_1} \ldots a_n^{i_n}$ and $z_2 = (a_1^{i_1} \ldots a_{k-1}^{i_{k-1}}) \circ a_k^{-f_k} \circ z_2' \circ{\sf inv}\/(a_1^{i_1} \ldots a_{k-1}^{i_{k-1}})$ for some $z_2' \in {\sf ORD}\/(\Sigma_{k+1})$. Note that the t-term in $y \ast z_{k-1} \ast p$ is brought to head position by multiplication with $z_2 \circ z_1$. Now multiplying ${\sf HT}(y \ast z_{k-1} \ast p)$ by $z_2 \circ z_1$ we find $z_2 \circ z_1 \circ a_1^{s_1} \ldots a_{k-1}^{s_{k-1}} a_k^{c_k} x = a_1^{i_1}... ... - f_k}\tilde{x} \equiv a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} a_k^{c_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)$ and $l_k \neq 0$. Notice that in this case the letter a_k is not bounded. Let us take a look at the polynomial $y \ast z_{k-1} \ast p$ where $y = (a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}) \circ a_k^{-l_k} \circ{\sf inv}\/(a_1^{s_1} \ldots a_{k-1}^{s_{k-1}})$, i.e., the exponent of the letter a_k in the term $y \circ z_{k-1} \circ t$ will be 0. Suppose ${\sf HT}(y \ast z_{k-1} \ast p) \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}(z_{k-1} \ast p)$, $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 $y \circ z_{k-1} \circ t$, we are done and we set w₁ = y and $\tilde{s}_k = 0 = \tilde{\rho}_k$. Now if we can show c_k = 0, by lemma 14 the t-term $y \circ z_{k-1} \circ t$ can be brought to head position using an element as constructed in lemma 14 since the distinguishing letter between ${\sf HT}(y \ast z_{k-1} \ast p)$ and the term $y \circ z_{k-1} \circ t$ then has at least index k+1 and we know ${\sf HT}({\sf inv}\/(y) \ast(y \ast z_{k-1} \ast p)) = {\sf HT}(z_{k-1} \ast p)= z_{k-1} \circ t$. Hence, in showing that c_k=0 we are done. As before there exist $z_1, z_2 \in {\cal G}$ such that $z_1 \circ y \circ z_{k-1} \circ t \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 $z_2 \circ a_1^{i_1} \ldots a_{k-1}^{i_{k-1}} a_k^{f_k}z\equiv a_{1}^{i_{1}} \ldots a_n^{i_n}$, i.e., $z_2 = (a_1^{i_1} \ldots a_{k-1}^{i_{k-1}}) \circ a_k^{-f_k + i_k}z_2' \circ{\sf inv}\/(a_1^{i_1} \ldots a_{k-1}^{i_{k-1}})$ for some $z_2' \in {\sf ORD}\/(\Sigma_{k+1})$. Remember that this multiplication brings the t-term in $y \ast z_{k-1} \ast p$ to head position. Hence multiplying ${\sf HT}(y \ast z_{k-1} \ast p)$ by $z_2 \circ z_1$ we find $z_2 \circ z_1 \circ a_1^{s_1} \ldots a_{k-1}^{s_{k-1}}a_{k}^{c_{k}}x \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 $y \circ s$ for some $s \in {\sf T}(z_{k-1} \ast p)$ 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 left multiples of the original polynomial, such that every left multiple of the polynomial is lpc-reducible to zero in one step by one of them. Such a property of a set of polynomials is called (lpc-) saturation. In example 9 the multiples $a^{-1} \ast p = a+ \lambda$ and $a^{-2} \ast p = a^{-1} + \lambda$ give us a lpc-saturating set for p = a²+a.

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

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

llProcedureLEFT-POLYCYCLIC SATURATION
 
Given: 		 A non-zero polynomial 

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

$\mbox{\sc Sat}(p)$,
a lpc-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 = w \ast p$
with 

${\sf HT}(w \ast p
) = w \circ t$
		 		 		  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\{ ( s \circ{\sf inv}\/(t)) \ast p \mid s \inH_t, {\sf HT}(( s \circ{\sf inv}\/(t)) \ast p)) = s\}$;
		 		 		  St := $\{ q \}$;
		 endif 
endfor 


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

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

$\vert{\sf T}(p)\vert$ polynomials

Notice that this is only a naive procedure and more structural information should be used, e.g. to rule out unnecessary candidates from the sets H_t.

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

Proof : 1.11.1 
This can be shown as in the proof of lemma 12.
q.e.d.

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

Definition 17    
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{... ...t i_n\vert,\vert j_n\vert \}}= w_1 \circ{\sf HT}(p_1) = w_2 \circ{\sf HT}(p_2)$ for some w₁,w₂ in ${\cal G}$ gives us

$${\sf spol}_{}(p_{1}, p_{2}) = {\sf HC}(p_1)^{-1} \cdot w_1 \ast p_1 - {\sf HC}(p_2)^{-1} \cdot w_2 \ast p_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 its existence 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 \}}$.

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

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

1.

For all polynomials $g \in {\sf ideal}_{l}^{}(G)$ we have $g \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{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 lpc}}_{G}\,$ } 0$.

Proof : 1.11.1 
Again we can follow the lines of the proof given for the similar theorem 3 for nilpotent groups and qc-reduction.
q.e.d.

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

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

1.

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

2.

Every $g \in {\sf ideal}_{l}^{}(G)$ has a left commutative prefix standard representation.

3.

G is a left commutative prefix standard basis.

4.

G is a left Gröbner basis.

Now, using the characterization given in theorem 7 we can state a procedure which enumerates left Gröbner bases in polycyclic group rings.

ProcedureLEFT GR¨OBNER BASES IN POLYCYCLIC GROUP RINGS
 
Given: 		 A finite set of polynomials 

$F \subseteq {\bf K}[{\cal G}]$.
Find: 		 

$\mbox{\sc Gb}_{l}(F)$,
a  left Gröbner basis of 

${\sf ideal}_{l}^{}(F)$.
 
G := 

$\bigcup_{g \in G} \mbox{\sc Sat}_{}(g)$;% G is lpc-saturated and 

${\sf ideal}_{l}^{}(F) = {\sf ideal}_{l}^{}(G)$
B := 

$\{ (q_{1}, q_{2}) \mid q_{1}, q_{2} \in G, q_{1} \neq q_{2} \}$;
while 

$B \neq \emptyset$
do % Test if  statement 2 of theorem 7 is valid
		      

(q1, q2) := 

${\rm remove}(B)$;% Remove an element using a fair strategy
		      if 		 h := 

${\sf spol}_{}(q_{1}, q_{2})$
exists
		 		   then 		 h' := 

${\rm normalform}(h, \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{G}\,$ })$;
  % Compute a normal form
		 		 		 if 		 $h' \neq 0$
% The s-polynomial does not  reduce to zero
		 		 		 		then 		G := 

$G \cup \mbox{\sc Sat}_{}(h')$;% G is lpc-saturated and 

${\sf ideal}_{l}^{}(F) = {\sf ideal}_{l}^{}(G)$
		 		 		 		 		B := 

$B \cup \{ (f, g ) \mid f \in G, g \in \mbox{\sc Sat}_{}(h') \}$;
						 endif
		 endif 
endwhile


$\mbox{\sc Gb}_{l}(F):= G$

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

Theorem 8    
Every left Gröbner basis contains a finite one.

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

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

Theorem 9    
For a set of polynomials $G \subseteq {\bf K}[{\cal G}]$, assuming that ${\cal G}$ is presented by $(\Sigma, T)$ as described above, the following properties are equivalent:

1.

G is a left Gröbner basis and ${\sf ideal}_{l}^{}(G) = {\sf ideal}_{}^{}(G)$.

2.

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

3.

G is a left Gröbner basis and for all $w \in {\cal G}$, $g \in G$ we have $g \ast w \in {\sf ideal}_{l}^{}(G)$.

4.

G is a left Gröbner basis and for all $a \in \Sigma$, $g \in G$ we have $g \ast a \in {\sf ideal}_{l}^{}(G)$.

Proof : 1.11.1 
This can be shown as in the proof of theorem 4.
q.e.d.

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

Corollary 4    
For a lpc-saturated set $G \subseteq {\bf K}[{\cal G}]$ the following statements are equivalent:

1.

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

2.

(a)

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

(b)

For all $a \in \Sigma$, $g \in G$ we have $g \ast a \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{G}\,$ } 0$.

Again the existence of finite Gröbner bases is a consequence of Dickson's Lemma.

Corollary 5    
Every Gröbner basis contains a finite one.

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

Definition 18    
We call a set of polynomials $F \subseteq {\bf K}[{\cal G}]$ interreduced or reduced with respect to $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$, if no polynomial f in F is lpc-reducible by the other polynomials in $F \backslash \{ f \}$. $\diamond$

Theorem 10    
Every (left) ideal in ${\bf K}[{\cal G}]$ contains a unique monic finite reduced (left) Gröbner basis.

Proof : 1.11.1 
The proof again can be done using standard techniques as in the case of ordinary polynomial rings.
q.e.d.

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

Let us close this section by sketching a possible approach to treat right ideals in polycyclic group rings. As seen in section 2 a stability property for right multiples need not hold when using the idea of commutative prefixes for reduction if ${\cal G}$ is given by a convergent PCP-presentation. Furthermore, Wißmann's result given in section 4 for the existence of only $\lambda$-confluent bases in case the group is given by a convergent PCP-system, states that in general no finite Gröbner bases will exist when using weakenings of strong reduction and every reduction based on commutative prefixes and using right multiples is such a weakening. Anyhow, a similar approach is possible in case we change the presentation of our polycyclic group. Let $(\Sigma, T)$ be a convergent PCP-presentation of a polycyclic group. Then the presentation $(\Sigma,\rho(T))$, where $\rho(T) = \{ \rho(l) \longrightarrow\rho(r) \mid l \longrightarrow r \in T\}$ and $\rho(\lambda) = \lambda$, $\rho(wa) = a \rho(w)$, is again a polycyclic power presentation which is convergent¹⁵ with respect to the syllable ordering now with status right, i.e., the syllables are compared from the right to the left. Such a presentation will be called a reversed polycyclic power commutation presentation (with status right). The irreducible elements now are reversed ordered words of the form $a_n^{i_n} \ldots a_1^{i_1}$, i.e., ${\sf REVORD}\/(\Sigma) = {\sf REVORD}\/(\Sigma_1)$, where we define ${\sf REVORD}\/(\Sigma_{i})$ recursively by ${\sf REVORD}\/(\Sigma_{n+1}) = \{ \lambda \}$, and ${\sf REVORD}\/(\Sigma_i) = \{ w \in \Sigma_i^* \mid w \equiv vu \mbox{ for some... ...\in \{ a_i \}^* \cup \{ a_i^{-1} \}^* , v \in {\sf REVORD}\/(\Sigma_{i+1}) \}$. We can show similar properties as in the case of Wißmann's PCP-presentations.

Lemma 17    
Let ${\cal G}$ be a polycyclic group with $(\Sigma, T)$ a convergent reversed polycyclic power commutation presentation with status right. Further for some $1 \leq i < n$ let $w \in {\sf REVORD}\/(\Sigma_{i+1})$. Then we have $a_i \circ w \equiv za_i$ for some $z \in {\sf REVORD}\/(\Sigma_{i+1})$.

Based on the form of the rules occurring in the presentation of ${\cal G}$ we can again prove stability for certain right multiples. From now on we will always assume that ${\cal G}$ is presented by a convergent reversed polycyclic power commutation system with status right.

Lemma 18    
Let ${\cal G}$ be a group presented by a convergent reversed polycyclic power commutation system with status right and $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$.

The proof of this lemma and the ones follwing in the remaining part of this section follow the lines of the proofs given for the comparable facts for lpc-reduction due to the symmetrical situation provided by the form of the reversed presentation of ${\cal G}$. We now proceed to study an appropriate reduction based on commutative prefixes for this setting.

Definition 19    
Let p, f be two non-zero polynomials in ${\bf K}[{\cal G}]$. We say that f right polycyclic (rpc-) reduces p to q at a monomial $\alpha \cdot t$ of p in one step, denoted by $p \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{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)$.

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

Notice that if f rpc-reduces p at $\alpha \cdot t$ to q, then t no longer is a term in q and by lemma 18, 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 19    
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 rpc}}_{F}\,$ } h$. Then there are $p',q' \in {\bf K}[{\cal G}]$ such that $p \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{F}\,$ } p', q \mbox{$\,\stackrel{*}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{F}\,$ } q'$ and h=p'-q'.

2.

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

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

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

As before, in general we do not have the property $\mbox{$\,\stackrel{*}{\longleftrightarrow}\!\!\mbox{}^{{\rm rpc}}_{G}\,$ } = \;\;\equiv_{{\sf ideal}_{r}^{}(G)}$, but it can be restored by saturation due to the following lemmata:

Lemma 20    
Let p be a non-zero polynomial in ${\bf K}[{\cal G}]$. Then it is decidable whether for $t \in {\sf T}(p)$ there exists an element $w \in {\cal G}$ such that ${\sf HT}(p \ast w) = t \circ w$.

Lemma 21    
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_n^{i_n} \ldots a_1^{i_1}$ and ${\sf HT}(p \ast v) = t \circ v\equiv a_n^{j_n} \ldots a_1^{j_1}$. Then there exists a term $\tilde{t} \leq_{\rm tup}a_n^{\rho_n} \ldots a_1^{\rho_1}$ 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 rpc}}_{p\ast\tilde{z}}\,$ } 0$ and $p \ast v \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{ p\ast\tilde{z}}\,$ } 0$.

Definition 21    
A set $S \subseteq \{ p \ast w \mid w \in {\cal G}\}$ is called an (rpc-) 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 rpc}}_{S}\,$ } 0$. A set of polynomials $F \subseteq {\bf K}[{\cal G}]$ is called (rpc-) saturated, if for all $f \in F$ and for all $w \in {\cal G}$, $f \ast w \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{F}\,$ } 0$. $\diamond$

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

Now it remains to give a confluence criteria which can be done using s-polynomials a usual.

Definition 22    
For $p_{1}, p_{2} \!\in \!{\bf K}[{\cal G}]$ such that ${\sf HT}(p_1) \!\equiv\! a_n^{i_n} \ldots a_1^{i_1}$ and ${\sf HT}(p_2) \!\equiv\! a_n^{j_n} \ldots a_1^{j_1}$ 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_n^{\rho_n \cdot\max \{ \vert i_n\vert,\vert j_n\vert \}}\ldots a_{1}^{\rho_1... ...t i_1\vert,\vert j_1\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$

Theorem 11    
For a 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 rpc}}_{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 rpc}}_{G}\,$ } 0$.

Procedures to compute rpc-saturating sets and Gröbner bases with respect to rpc-reduction can be given as in the case of lpc-reduction before. Again the concept of interreduction can be supplied to yield unique monic reduced Gröbner bases, and it is possible to characterize two-sided ideals by right ideals using the same ideas as cited before.

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

Example 10    
Let ${\cal G}$ be the group specified on page now presented by a convergent reversed polycyclic power commutation presentation assuming a syllable ordering with precedence $a_1^{-1} \succ a_1 \succ a_2^{-1} \succ a_2 \succ a_3^{-1} \succ a_3$ and status right, $\Sigma = \{ a_1, a_1^{-1}, a_2, a_2^{-1}, a_3, a_3^{-1} \}$, $T = \{ a_1a_1^{-1} \longrightarrow\lambda, a_1^{-1}a_1 \longrightarrow\lambda, ... ...\longrightarrow a_3^{\delta'}a_2^{\delta} \mid \delta, \delta' \in \{1,-1\}\}$. Then for the right ideal generated by $P_U = \{ a_2 - 1, a_3 - 1 \}$ the set $G = \{ a_2 - 1, a_2^{-1} - 1, a_3 - 1, a_3^{-1} - 1 \}$ is a Gröbner basis corresponding to the subgroup generated by U. While in the setting of example 4 the elements $a_2^{-1} \circ a_3 \circ a_1$ and a₁ have no common descendant with respect to $\Longrightarrow_U$, now we find that the normal form a₃a₂^-1a₁ of the element $a_2^{-1} \circ a_3 \circ a_1$ is reducible by G as follows: $a_3a_2^{-1}a_1 \mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{a_... ...{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{a_2^{-1} - 1}\,$ } a_1$. Hence now a₃a₂^-1a₁ and a₁ are clearly joinable. $\diamond$