next up previous
Next: Bibliography Up: Introducing Reduction to Polycyclic Previous: 6. Reduction in Polycyclic

7. Concluding Remarks

In this paper we have shown how Gröbner basis methods can be successfully introduced to nilpotent respectively polycyclic group rings. We have illustrated how depending on the respective group presentations commutative divisors can be used to define Noetherian reductions. Left ideals can be handled by so called lpc-reduction using convergent PCNI- as well as PCP-systems for presenting the group. For right ideals we have to be more careful. While the collecting process induced by convergent PCNI-presentations allows to define a Noetherian reduction using right multiples, this cannot be generalized for convergent PCP-systems. Hence we have introduced reversed PCP-systems with status right and in this setting again reduction can be specified. The results can be summarized as follws:
Group presentation left GBs right GBs two-sided GBs
PCNI-system $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$ $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{}\,$ }$ $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm qc}}_{}\,$ }$
      $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$
PCP-system $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$ none16 $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm lpc}}_{}\,$ }$
reversed PCP-system none $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{}\,$ }$ $\mbox{$\,\stackrel{}{\longrightarrow}\!\!\mbox{}^{{\rm rpc}}_{}\,$ }$
In [Re95] we have shown how the theory of Gröbner bases in monoid and group rings over fields can be lifted to monoid and group rings over reduction rings fulfilling special axioms, e.g., allowing to compute finite Gröbner bases for ideals in the coefficient domain. Hence the results of this paper also hold for nilpotent respectively polycyclic group rings over reduction rings, e.g., the integers ${\bf Z}$.

Finally we want to sketch how the results of this report can be lifted to group rings over nilpotent-by-finite respectively polycyclic-by-finite groups. Essential in this approach is the use of semi-Thue systems related to extensions of groups as introduced for context-free groups by Cremanns and Otto in [CrOt94]. Details of the lifting process for respective group rings can be found in [Re95] and [MaRe96]. The key idea is to combine a convergent presentation $(\Sigma_{{\cal E}},T_{{\cal E}})$ of a finite group ${\cal E}$ with a convergent PCNI-presentation respecitively PCP-presentation of a nilpotent respectively polycyclic group ${\cal N}$ presented by $(\Sigma_{{\cal N}}, T_{{\cal N}})$. Assuming $\Sigma_{{\cal E}} \cap \Sigma_{{\cal N}} =
\emptyset$, let $\Sigma = \Sigma_{{\cal E}} \cup \Sigma_{{\cal N}}$ and let T consist of the set of rules $T_{{\cal N}}$, and the following additional rules:

l $\longrightarrow$ rwr for all $l \longrightarrow r \in T_{{\cal E}}$, where $w_r \in \Sigma_{{\cal N}}^* \cap {\rm IRR}\/(T_{{\cal N}})$, xa $\longrightarrow$ awx for all $a \in \Sigma_{{\cal E}}$, for all $x \in \Sigma_{{\cal N}}$, where $w_a \in \Sigma_{{\cal N}}^* \cap {\rm IRR}\/(T_{{\cal N}})$.

Then in case $(\Sigma, T)$ is convergent it is called the extension presentation of ${\cal G}$ as an extension of ${\cal N}$ by ${\cal E}$ (see e.g. [Cr95]). Every element in ${\cal G}$ has a representative of the form eu where $e \in {\cal E}$ and $u \in {\cal N}$. We can specify a total well-founded ordering $\succ$ on our group by combining a total well-founded ordering $\succeq_{\cal E}$ on ${\cal E}$ and the syllable ordering $\geq_{\rm syll}$ on ${\cal N}$: For $e_1u_1,e_2u_2 \in {\cal G}$ we define $e_1u_1 \succ e_2u_2$ if and only if $e_1 \succ_{\cal E} e_2$ or (e1 = e2 and $u_1 >_{\rm syll}u_2)$. Furthermore, we can lift the tuple ordering to ${\cal G}$ as follows: For two elements eu, ev, we define $eu \geq_{\rm tup}ev$ if $u >_{\rm tup}v$ and we define $eu >_{\rm tup}\lambda$. According to this ordering we call ev a (commutative) prefix of eu if $v \leq_{\rm tup}u$ and introducing the concept of ${\cal E}$-closure as in [Re95] or [MaRe96] we can proceed to prove lemmata and theorems similar to those in section 5 and 6.

next up previous
Next: Bibliography Up: Introducing Reduction to Polycyclic Previous: 6. Reduction in Polycyclic
| ZCA Home | Reports |