1. Introduction

By introducing the theory of Gröbner bases for polynomial ideals in commutative polynomial rings over fields, Buchberger established a rewriting approach to the theory of polynomial ideals (see [Bu65]). He used polynomials as rules by giving an admissible term ordering on the terms and using the largest monomial according to this ordering as a left hand side of a rule. ``Reduction'' defined in this way can be compared to division of one polynomial by a set of finitely many polynomials. A Gröbner basis now is a set of polynomials G such that every polynomial in the polynomial ring has a unique normal form with respect to reduction using the polynomials in G as rules (especially the polynomials in the ideal generated by G reduce to zero using G). Hence in case they can be computed such bases enable to solve many problems related to ideals. For the polynomial ring Buchberger developed a terminating procedure to transform a finite generating set of a polynomial ideal into a finite Gröbner basis of the same ideal.

Since the theory of Gröbner bases turned out to be of outstanding importance for polynomial rings, extensions of Buchberger's ideas to other algebras followed, for example to free algebras ([Mo85,Mo94]), Weyl algebras ([La85]), enveloping fields of Lie algebras ([ApLa88]), solvable rings ([KaWe90,Kr93]), skew polynomial rings ([We92]), free group rings ([Ro93]) and monoid and group rings ([MaRe93b]).

Especially group rings are subject of extensive studies in mathematics. In 1981 Baumslag, Cannonito and Miller showed that for the integral group ring of a polycyclic group several decision problems including the membership problem for submodules are computable [BaCaMi81]. In [Si94] Sims studies these ideas and shows connections between special submodule bases which allow to solve the membership problem and Gröbner bases.

In this paper we want to present our results on generalizing reduction and Gröbner bases to polycyclic group rings and especially to the subclasses of Abelian groups and nilpotent groups. We want to point out that instead of using the fact that every group ring over a polycyclic group is Noetherian, we give a rewriting oriented approach which leads to a syntactical characterization of Gröbner bases in terms of s-polynomials and a completion based algorithm to compute them. In order to do this we have to give conditions when a polynomial can be used to reduce another polynomial. Due to the presentation of the group elements by ordered group words we can define a concept of ``syntactical divisors'' or ``commutative prefixes'' on the group elements which captures the known fact that in the commutative polynomial ring a divisor of a term is also a commutative prefix of this term. But we will see that this property alone in general will not be sufficient to ensure that reduction based on commutative prefixes is Noetherian. Hence additional conditions concerning the presentation chosen for the group and whether left or right multiples are used for reduction will be important. This leads to different instances of reduction for groups depending on their presentation. Notice that, since for finitely generated groups we have that Abelian implies nilpotent which again implies polycyclic, reduction in polycyclic group rings will also work for nilpotent group rings and again reduction specialized for nilpotent group rings can be used for Abelian group rings. We will also see why the reverse does not hold.

In section 2 the basic notions of this paper are presented. It is well known that a polycyclic group ${\cal G}$ can be presented by a confluent semi-Thue system of a special form. Such presentations are given and both - the vocabulary of Wißmann in [Wi89] and of Sims in [Si94] - are presented. In order to keep the paper self-contained, section 3 cites the results on the Baumslag, Cannonito, Miller approach to solve the submodule problem in polycyclic group rings as given in chapter 10 of Sims' book [Si94]. It also includes a possible way of deducing reduction in this setting, and problems related to this reduction. Furthermore, we sketch Sims' generalization of Gröbner bases to finitely generated free Abelian group rings -- so called rings of Laurent polynomials. Section 4 relates special Gröbner bases to solutions of the subgroup problem by rewriting techniques. It is outlined how Wißmann's approach [Wi89] to the subgroup problem in nilpotent and polycyclic groups can be seen in our setting. Section 5 states how Gröbner bases can be generalized for right and two-sided ideals in finitely generated nilpotent group rings. A comparison with Sims' approach for Laurent polynomials is done for the special case of free Abelian groups. Finally section 6 outlines how a generalization for left and two-sided ideals works for arbitrary polycyclic groups (hence especially for finitely generated nilpotent groups) and which problems arise for right ideals.