Title: On Gröbner Bases in Monoid and Group Rings

Language of presentation: English

Promotor: Prof. Dr. Klaus E. Madlener

Date of defense: June 14, 1995

Institution granting degree: Universität Kaiserslautern, Germany

Abstract:

One of the amazing features of computers is the ability to discover new mathematical results due to extensive computations impossible to be done by hand. Besides incredible numerical calculations, symbolical mathematical manipulations are substantial to many fields in mathematics and physics. Hence the idea of using a computer to do such manipulations led to open up whole new areas of mathematics and computer science. In the wake of these developments has come a new access to abstract algebra in a computational fashion - computer algebra. One important contribution is Buchberger's algorithm for manipulating systems of polynomial equations. In 1965 Buchberger introduced the theory of Gröbner bases for polynomial ideals in commutative polynomial rings over fields. It established a rewriting approach to the theory of polynomial ideals. Polynomials can be used as rules by giving an admissible ordering on the terms and using the largest monomial according to this ordering as a left hand side of a rule. ``Reduction'' as defined by Buchberger then can be compared to division of one polynomial by a set of finitely many polynomials. A Gröbner basis G is a set of polynomials 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). 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, several generalizations of Buchberger's ideas to other structures followed, e.g. to free algebras (Mora), Weyl algebras (Lassner), enveloping fields of Lie algebras (Apel, Lassner), solvable rings (Kapur, Weispfenning, Kredel), and skew polynomial rings (Weispfenning).

Most of these approaches fulfill the following requirements:

1. The rings allow admissible well-founded orderings.
2. If a polynomial can be reduced to zero by a set of polynomials, so can a multiple of this polynomial by a monomial.
3. The translation lemma holds, i.e., if the difference of two polynomials can be reduced to zero using a set of polynomials, then the two polynomials are joinable using the same set of polynomials for reduction.
4. Two polynomials give rise to finitely many s-polynomials only, in general at most one.

These statements then can be used to characterize Gröbner bases in the respective ring with respect to the corresponding reduction in a finitary manner and assuming that the reduction is effective it is decidable whether a finite set is a Gröbner basis by checking whether the s-polynomials are reducible to zero.

Starting point of this thesis was the idea to study arbitrary finitely generated monoid rings similar to Mora's approach to free monoid rings. In order to do this we combine string rewriting (to represent the monoid or group elements and their multiplication) and polynomial rewriting (in the monoid or group ring). Since we want to treat rings with well-founded but no longer admissible orderings, we mainly have to deal with the fact that many of the properties used to give a characterization of a Gröbner basis in the classical case no longer hold. We have proven that there are weaker requirements still enabling characterizations of Gröbner bases in terms of s-polynomials in case we use appropriate reductions combined with appropriate concepts of saturation. For special reductions we can even give a characterization where localization of critical situations to one s-polynomial for each pair of polynomials is possible. The existence of finite Gröbner bases for finitely generated right ideals has been ensured and procedures for finding them have been given for the following classes: the class of finite monoids, the class of free monoids, the class of Abelian monoids, the class of finite groups, the class of free groups, the class of plain groups, the class of context-free groups, and the class of nilpotent groups. For the class of nilpotent groups we could extend these results to two-sided ideals.

The thesis organizes as follows:

Chapter 1 gives a short introdution to the thesis.

Chapter 2 introduces some of the basic themes of this work. We need some definitions and notions from algebra and the theory of rewriting systems. Furthermore, as this work is based on Buchberger's ideas, a short summary of the theory of Gröbner bases and Buchberger's algorithm are given.

Chapter 3 gives a short outline on introducing Gröbner bases to non-commutative structures by sketching Mora's approach to free monoid rings and Weispfenning's approach to skew polynomial rings. We prove that the word problem for semi-Thue systems is equivalent to a restricted version of the membership problem for free monoid rings and similarly that the word problem for group presentations is equivalent to a restricted version of the membership problem for free group rings. Hence for free monoids respectively free groups with more than one generator the ideal membership problem is undecidable. (It is decidable for one generator.) Further we show that it is undecidable whether a finite Gröbner basis in a free monoid ring generated by more than one generator exists.

Chapter 4 gives different approaches to define reduction in monoid rings. Since monoid rings in general are not commutative, we are mainly interested in right ideals. A well-founded ordering on terms is used to split a polynomial into a head monomial (the largest monomial) and a reduct. A natural way to define reduction is to use a multiple of a polynomial to replace a monomial in another polynomial in case the result is smaller. This is the case if the head term of the multiple equals the term of the removed monomial. This reduction is called strong reduction and can be used to express the congruence of a right ideal. Although a characterization of Gröbner bases with respect to this reduction in terms of strong s-polynomials is possible, this characterization is not finitary and it cannot be used to decide whether a finite set of polynomials is a strong Gröbner basis. One idea to localize a confluence test, i.e., reduce the number of s-polynomials to be considered, is to weaken reduction. The first weakening studied is restricting the multiples of polynomials used to stable ones, i.e., multiples where the new head term results from the original head term of the polynomial. The first problem is that the expressiveness of a right ideal congruence by reduction using an arbitrary set of generators of the right ideal is lost. This can be regained using a concept called saturation, which enlarges the set of polynomials used for reduction. But such saturating sets need not be finite. For saturated sets a characterization of Gröbner bases with respect to right reduction in terms of right s-polynomials is provided which is still not finitary. Therefore, two weakenings involving syntactical information on the representatives of the monoid elements (the terms) are given -- prefix reduction for arbitrary monoid rings and commutative reduction for Abelian monoid rings. Saturation concepts with respect to these reductions are provided and for saturated sets now a finitary characterization of the respective Gröbner bases in terms of special s-polynomials is possible. The characterization of prefix Gröbner bases can be used to give an enumerating procedure for such a basis which terminates in case a finite prefix Gröbner basis exists. For Abelian monoid rings a terminating procedure to complete a finite set of polynomials is provided. Furthermore, we introduce interreduction to both approaches and the existence of unique monic reduced Gröbner bases with respect to the respective ordering on the monoid is shown.

In chapter 5 we show that the subgroup problem for a group is equivalent to a restricted version of the right ideal membership problem in the corresponding group ring. Hence, only groups with solvable subgroup problem can be expected to allow the construction of finite Gröbner bases. We apply the concept of prefix reduction to the classes of free, plain respectively context-free groups and give algorithms to compute finite reduced prefix Gröbner bases for finitely generated right ideals. Furthermore, a generalization of commutative reduction to nilpotent groups, namely quasi-commutative reduction, is given and a finitary characterization of Gröbner bases in this setting is provided. A procedure to compute finite Gröbner bases with respect to this reduction for finitely generated right ideals is given. These results are extended to two-sided ideals.

Chapter 6 gives a sketch how the ideas of chapter 4 can be carried over to monoid rings over reduction rings.

Table of Contents:

1. Introduction
2. Basic Definitions
   1. Algebra
   2. The Notion of Reduction
   3. Gröbner Bases in Polynomial Rings
   4. Semi-Thue Systems
3. Non-Commutative Gröbner Bases
   1. The Free Monoid Ring
   2. Undecidability Results
   3. Skew Polynomial Rings
4. Reduction in Monoid and Group Rings
   1. Using Polynomials as Rules
   2. The Concept of Strong Reduction
   3. The Concept of Right Reduction
   4. The Concept of Prefix Reduction
   5. The Concept of Commutative Reduction
5. Group Rings
   1. The Subgroup Problem
   2. Free Groups
   3. Plain Groups
   4. Context-free Groups
   5. Nilpotent Groups
6. Monoid Rings over Reduction Rings
7. Concluding Remarks
8. Bibliography