0.4pt0.2pt

A Systematic Study
of
Gröbner Basis Methods

Vom Fachbereich Informatik

der Technischen Universität Kaiserslautern

genehmigte Habilitationsschrift

von

Dr. Birgit Reinert

Datum der Einreichung: 6. Januar 2003
Datum des wissenschaftlichen Vortrags: 9. Februar 2004

Dekan: Prof. Dr. Hans Hagen Habilitationskommission: Vorsitzender: Prof. Dr.
Otto Mayer Berichterstatter: Prof. Dr. Klaus E. Madlener Prof. Dr. Teo Mora
Prof. Dr. Volker Weispfenning

## Vorwort

Die vorliegende Arbeit ist die Quintessenz meiner Ideen und Erfahrungen, die
ich in den letzten Jahren bei meiner Forschung auf dem Gebiet der Gröbnerbasen
gemacht habe. Meine geistige Heimat war dabei die Arbeitsgruppe von Professor
Klaus Madlener an der Technischen Universität Kaiserslautern. Hier habe ich
bereits im Studium Bekanntschaft mit der Theorie der Gröbnerbasen gemacht und
mich während meiner Promotion mit dem Spezialfall dieser Theorie für Monoid-
und Gruppenringe beschäftigt. Nach der Promotion konnte ich im Rahmen eines
DFG-Forschungsstipendiums zusätzlich Problemstellungen und Denkweisen anderer
Arbeitsgruppen kennenlernen - die Arbeitsgruppe von Professor Joachim Neubüser
in Aachen und die Arbeitsgruppe von Professor Theo Mora in Genua. Meine
Aufenthalte in diesen Arbeitsgruppen haben meinen Blickwinkel für
weitergehende Fragestellungen erweitert. An dieser Stelle möchte ich mich bei
allen jenen bedanken, die mich in dieser Zeit begleitet haben und so zum
Entstehen und Gelingen dieser Arbeit beigetragen haben.

Mein besonderer Dank gilt meinem akademischen Lehrer Professor Klaus Madlener,
der meine akademische Ausbildung schon seit dem Grundstudium begleitet und
meine Denk- und Arbeitsweise wesentlich geprägt hat. Durch ihn habe ich
gelernt, mich intensiv mit diesem Thema zu beschäftigen und mich dabei nie auf
nur einen Blickwinkel zu beschränken. Insbesondere sein weitreichenden
Literaturkenntnisse und die dadurch immer neu ausgelösten Fragen aus
verschiedenen Themengebieten bewahrten meine Untersuchungen vor einer gewissen
Einseitigkeit. Er hat mich gelehrt, selbständig zu arbeiten, Ideen und Papiere
zu hinterfragen, mir meine eigene Meinung zu bilden, diese zu verifizieren und
auch zu vertreten.

Professor Teo Mora und Professor Volker Weispfenning danke ich für die
Übernahme der weiteren Begutachtungen dieser Arbeit. Professor Teo Mora danke
ich insbesondere auch für die fruchtbare Zeit in seiner Arbeitsgruppe in
Genua. Seine Arbeiten und seine Fragen haben meine Untersuchungen zum
Zusammenhang zwischen Gröbnerbasen in Gruppenringen und dem Todd-Coxeter
Ansatz für Gruppen und die Fragestellungen dieser Arbeit wesentlich geprägt.

Meinen Kollegen aus unserer Arbeitsgruppe danke ich für ihre
Diskussionsbereitschaft und ihre geduldige Anteilnahme an meinen Gedanken.
Insbesondere Andrea Sattler-Klein, Thomas Deiß, Claus-Peter Wirth und Bernd
Löchner haben immer an mich geglaubt und mich ermutigt, meinen Weg weiter zu
gehen. Mit ihnen durfte ich nicht nur Fachliches sondern das Leben teilen.

Um eine solche Arbeit fertigzustellen braucht man jedoch nicht nur eine
fachliche Heimat. Mein Mann Joachim hat nie an mir gezweifelt und mich immer
unterstützt. Auch nach unserem Umzug nach Rechberghausen hat er mein Pendeln
nach Kaiserslautern und das Brachliegen unseres Haushalts mitgetragen. Ohne
meine Eltern Irma und Helmut Weber und meine Patentante Anita Schäfer wäre
insbesondere nach der Geburt unserer Tochter Hannah diese Arbeit nie
fertiggestellt worden. Sie haben Hannah liebevoll behütet, so dass ich lesen,
schreiben und arbeiten konnte, ohne ein schlechtes Gewissen zu haben. Hannah
hat von Anfang an gelernt, dass Forschung ein Leben bereichern kann und die
Zeit mit ihrer erweiterten Familie und die vielen Reisen nach Kaiserslautern
genossen.

Gewidmet ist diese Arbeit meiner Mutter, die leider die Fertigstellung nicht
mehr erleben durfte, und Hannah, die auch heute noch Geduld aufbringt, wenn
ihre Mutter am Computer für ihre “Schule” arbeitet.

Rechberghausen, im August 2004 Birgit Reinert

##

Für meine Mutter

und Hannah

###### Contents

  1. 1 Introduction
    1. 1.1 The History of Gröbner Bases
    2. 1.2 Two Definitions of Gröbner Bases
    3. 1.3 Applications of Gröbner Bases
    4. 1.4 Generalizations of Gröbner Bases
    5. 1.5 Gröbner Bases in Function Rings – A Guide for Introducing Reduction Relations to Algebraic Structures
    6. 1.6 Applications of Gröbner Bases Generalized to Function Rings
    7. 1.7 Organization of the Contents
  2. 2 Basic Definitions
    1. 2.1 Algebra
    2. 2.2 The Notion of Reduction
    3. 2.3 Gröbner Bases in Polynomial Rings
  3. 3 Reduction Rings
    1. 3.1 Reduction Rings
    2. 3.2 Quotients of Reduction Rings
    3. 3.3 Sums of Reduction Rings
    4. 3.4 Modules over Reduction Rings
    5. 3.5 Polynomial Rings over Reduction Rings
  4. 4 Function Rings
    1. 4.1 The General Setting
    2. 4.2 Right Ideals and Right Standard Representations
      1. 4.2.1 The Special Case of Function Rings over Fields
      2. 4.2.2 Function Rings over Reduction Rings
      3. 4.2.3 Function Rings over the Integers
    3. 4.3 Right ${\cal F}$-Modules
    4. 4.4 Ideals and Standard Representations
      1. 4.4.1 The Special Case of Function Rings over Fields
      2. 4.4.2 Function Rings over Reduction Rings
      3. 4.4.3 Function Rings over the Integers
    5. 4.5 Two-sided Modules
  5. 5 Applications of Gröbner Bases
    1. 5.1 Natural Applications
    2. 5.2 Quotient Rings
    3. 5.3 Elimination Theory
    4. 5.4 Polynomial Mappings
    5. 5.5 Systems of One-sided Linear Equations in Function Rings over the Integers
  6. 6 Conclusions

0.4pt0.2pt

##  Chapter 1 Introduction

One of the amazing features of computers is the ability to do extensive
computations impossible to be done by hand. This enables to overcome the
boundaries of constructive algebra as proposed by mathematicians as Kronecker.
He demanded that definitions of mathematical objects should be given in such a
way that it is possible to decide in a finite number of steps whether a
definition applies to an object. While in the beginning computers were used to
do incredible numerical calculations, a new dimension was added when they were
used to do symbolical mathematical manipulations substantial to many fields in
mathematics and physics. These new possibilities 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 to this field which is the
subject of this work is the theory of Gröbner bases – the result of
Buchberger’s algorithm for manipulating systems of polynomials.

###  1.1 The History of Gröbner Bases

In 1965 Buchberger introduced the theory of Gröbner bases111Note that similar
concepts appear in a paper of Hironaka where the notion of a complete set of
polynomials is called a standard basis [Hir64]. for polynomial ideals in
commutative polynomial rings over fields [Buc65, Buc70]. Let
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ be a polynomial ring over a computable
field ${\mathbb{K}}$ and ${\mathfrak{i}}$ an ideal in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$. Then the quotient
${\mathbb{K}}[X_{1},\ldots,X_{n}]/{\mathfrak{i}}$ is a ${\mathbb{K}}$-algebra.
If this quotient is zero-dimensional the algebra has a finite basis consisting
of power products $X_{1}^{i_{1}}\ldots X_{n}^{i_{n}}$. This was the starting
point for Buchberger’s PhD thesis. His advisor Wolfgang Gröbner wanted to
compute the multiplication table and had suggested a procedure for zero-
dimensional ideals, for which termination conditions were lacking. The result
of Buchberger’s studies then was a terminating algorithm which turned a basis
of an ideal into a special basis which allowed to solve Gröbner’s question of
writing down an explicit multiplication for the multiplication table of the
quotient in the zero-dimensional case and was even applicable to arbitrary
polynomial ideals. Buchberger called these special bases of ideals Gröbner
bases.

###  1.2 Two Definitions of Gröbner Bases

In literature there are two main ways to define Gröbner bases in polynomial
rings over fields. They both require an admissible222An ordering $\succeq$ on
the set of terms is called an admissible term ordering if for every term
$s,t,u$, $s\succeq 1$ holds, and $s\succeq t$ implies $s\circ u\succeq t\circ
u$. An ordering fulfilling the latter condition is also said to be compatible
with the respective multiplication $\circ$. ordering on the set of terms. With
respect to such an ordering, given a polynomial $f$ the maximal term occurring
in $f$ is called the head term denoted by ${\sf HT}(f)$.

One way to characterize Gröbner bases in an algebraic fashion is to use the
concept of term division: A term $X_{1}^{i_{1}}\ldots X_{n}^{i_{n}}$ is said
to divide another term $X_{1}^{j_{1}}\ldots X_{n}^{j_{n}}$ if and only if
$i_{l}\leq j_{l}$ for all $1\leq l\leq n$. Then a set $G$ of polynomials is
called a Gröbner basis of the ideal $\mathfrak{i}$ it generates if and only if
for every $f$ in $\mathfrak{i}$ there exists a polynomial $g\in G$ such that
${\sf HT}(g)$ divides ${\sf HT}(f)$.

Another way to define Gröbner bases in polynomial rings is to establish a
rewriting approach to the theory of polynomial ideals. Polynomials can be used
as rules by using the largest monomial according to the admissible ordering as
a left hand side of a rule. Then a term is reducible by a polynomial as a rule
if the head term of the polynomial divides the term. A Gröbner basis $G$ then
is a set of polynomials such that every polynomial in the polynomial ring has
a unique normal form with respect to this reduction relation using the
polynomials in $G$ as rules (especially the polynomials in the ideal generated
by $G$ reduce to zero using $G$).

Of course both definitions coincide for polynomial rings since the reduction
relation defined by Buchberger can be compared to division of one polynomial
by a set of finitely many polynomials.

###  1.3 Applications of Gröbner Bases

The method of Gröbner bases allows to solve many problems related to
polynomial ideals in a computational fashion. It was shown by Hilbert (compare
Hilbert’s basis theorem) that every ideal in a polynomial ring has a finite
generating set. However, an arbitrary finite generating set need not provide
much insight into the nature of the ideal. Let $f_{1}=X_{1}^{2}+X_{2}$ and
$f_{2}=X_{1}^{2}+X_{3}$ be two polynomials in the polynomial
ring333${\mathbb{Q}}$ denotes the rational numbers.
${\mathbb{Q}}[X_{1},X_{2},X_{3}]$. Then ${\mathfrak{i}}=\\{f_{1}\ast
g_{1}+f_{2}\ast g_{2}\mid g_{1},g_{2}\in{\mathbb{Q}}[X_{1},X_{2},X_{3}]\\}$ is
the ideal they generate and it is not hard to see that the polynomial
$X_{2}-X_{3}$ belongs to ${\mathfrak{i}}$ since $X_{2}-X_{3}=f_{1}-f_{2}$. But
what can be said about the polynomial $f=X_{3}^{3}+X_{1}+X_{3}$? Does it
belong to ${\mathfrak{i}}$ or not?

The problem to decide whether a given polynomial lies in a given ideal is
called the membership problem for ideals. In case the generating set is a
Gröbner basis this problem becomes immediately decidable, as the membership
problem then reduces to checking whether the polynomial reduces to zero using
the elements of the Gröbner basis for reduction.

In our example the set $\\{X_{1}^{2}+X_{3},X_{2}-X_{3}\\}$ is a generating set
of ${\mathfrak{i}}$ which is in fact a Gröbner basis. Now returning to the
polynomial $f=X_{3}^{3}+X_{1}+X_{3}$ we find that it cannot belong to
${\mathfrak{i}}$ since neither $X_{1}^{2}$ nor $X_{2}$ is a divisor of a term
in $f$ and hence $f$ cannot be reduced to zero using the polynomials in the
Gröbner basis as rules.

The terms $X_{1}^{i_{1}}X_{2}^{i_{2}}X_{3}^{i_{3}}$ which are not reducible by
the set $\\{X_{1}^{2}+X_{3},X_{2}-X_{3}\\}$ form a basis of the
${\mathbb{Q}}$-algebra ${\mathbb{Q}}[X_{1},X_{2},X_{3}]/{\mathfrak{i}}$. By
inspecting the head terms $X_{1}^{2}$ and $X_{2}$ of the Gröbner basis we find
that the (infinite) set $\\{X_{3}^{i},X_{1}X_{3}^{i}\mid i\in{\mathbb{N}}\\}$
is such a basis. Moreover, an ideal is zero-dimensional, i.e. this set is
finite, if and only if for each variable $X_{i}$ the Gröbner basis contains a
polynomial with head term $X_{i}^{k_{i}}$ for some $k_{i}\in{\mathbb{N}}^{+}$.
Similarly the form of the Gröbner basis reveals whether the ideal is trivial:
${\mathfrak{i}}={\mathbb{K}}[X_{1},\ldots,X_{n}]$ if and only if
every444Notice that if one Gröbner basis contains an element from
${\mathbb{K}}$ so will all the others. Gröbner basis contains an element from
${\mathbb{K}}$.

Further applications of Gröbner bases come from areas as widespread as
robotics, computer vision, computer-aided design, geometric theorem proving,
Petrie nets and many more. More details can be found e.g. in Buchberger
[Buc87], or the books of Becker and Weispfenning [BW92], Cox, Little and
O’Shea [CLO92], and Adams and Loustaunau [AL94].

###  1.4 Generalizations of Gröbner Bases

In the last years, the method of Gröbner bases and its applications have been
extended from commutative polynomial rings over fields to various types of
algebras over fields and other rings. In general for such rings arbitrary
finitely generated ideals will not have finite Gröbner bases. Nevertheless,
there are interesting classes for which every finitely generated (left, right
or even two-sided) ideal has a finite Gröbner basis which can be computed by
appropriate variants of completion based algorithms.

First successful generalizations were extensions to commutative polynomial
rings over coefficient domains other than fields. It was shown by several
authors including Buchberger, Kandri-Rody, Kapur, Narendran, Lauer, Stifter,
and Weispfenning that Buchberger’s approach remains valid for polynomial rings
over the integers, or even Euclidean rings, and over regular rings (see e.g.
[Buc83, Buc85, KRK84, KRK88, KN85, Lau76, Sti87, Wei87b]). For regular rings
Weispfenning has to deal with the situation that zero-divisors in the
coefficient domain have to be considered. He uses a technique he calls Boolean
closure to repair this problem and this technique can be regarded as a special
saturating process555Saturation techniques are used in various fields to
enrich a generating set of a structure in such a way, that the new set still
describes the same structure but allows more insight. For example
symmetrization in groups can be regarded as such a saturating process.. We
will later on see how such saturating techniques become important ingredients
of Gröbner basis methods in many algebraic structures.

Since the development of computer algebra systems for commutative algebras
made it possible to perform tedious calculations using computers, attempts to
generalize such systems and especially Buchberger’s ideas to non-commutative
algebras followed. Originating from special problems in physics, Lassner in
[Las85] suggested how to extend existing computer algebra systems in order to
additionally handle special classes of non-commutative algebras, e.g. Weyl
algebras. He studied structures where the elements could be represented using
the usual representations of polynomials in commutative variables and the non-
commutative multiplication could be performed by a so-called “twisted product”
which required only procedures involving commutative algebra operations and
differentiation. Later on together with Apel he extended Buchberger’s
algorithm to enveloping fields of Lie algebras [AL88]. Because these ideas use
representations of the elements by commutative polynomials, Dickson’s
Lemma666Dickson’s Lemma in the context of commutative terms is as follows: For
every infinite sequence of terms $t_{s}$, $s\in{\mathbb{N}}$, there exists an
index $k\in{\mathbb{N}}$ such that for every index $i>k$ there exists an index
$j\leq k$ and a term $w$ such that $t_{i}=t_{j}w$. can be carried over. By
this the existence and construction of finite Gröbner bases for finitely
generated left ideals can be ensured using the same arguments as in the
original approach.

On the other hand, Mora gave a concept of Gröbner bases for a class of non-
commutative algebras by saving an other property of the commutative polynomial
ring – admissible orderings – while losing the validity of Dickson’s Lemma.
The usual polynomial ring can be viewed as a monoid ring where the monoid is a
finitely generated free commutative monoid. Mora studied the class where the
free commutative monoid is substituted by a free monoid – the class of
finitely generated free monoid rings (compare e.g. [Mor85, Mor94]). The ring
operations are mainly performed in the coefficient domain while the terms are
treated like words, i.e., the variables no longer commute with each other and
multiplication is concatenation. The definitions of (one- and two-sided)
ideals, reduction and Gröbner bases are carried over from the commutative case
to establish a similar theory of Gröbner bases in “free non-commutative
polynomial rings over fields”. But these rings are no longer Noetherian if
they are generated by more than one variable. Mora presented a terminating
completion procedure for finitely generated one-sided ideals and an
enumeration procedure for finitely generated two-sided ideals with respect to
some term ordering in free monoid rings. For the special instance of ideals
generated by bases of the restricted form
$\\{\ell_{i}-r_{i}\mid\ell_{i},r_{i}\mbox{ words},1\leq i\leq n\\}$, Mora’s
procedure coincides with Knuth-Bendix completion for string rewriting systems
and the one-sided cases can be related to prefix respectively suffix rewriting
[MR98d, MR98c]. Hence many results known for finite string rewriting systems
and their completion carry over to finitely generated ideals and the
computation of their Gröbner bases. Especially the undecidability of the word
problem yields non-termination for Mora’s general procedure (see also
[Mor87]).

Gröbner bases and Mora’s procedure have been generalized to path algebras (see
[FCF93, Kel98]); free non-commutative polynomial rings are in fact a
particular instance of path algebras.

Another class of non-commutative rings where the elements can be represented
by the usual polynomials and which allow the construction of finite Gröbner
bases for arbitrary ideals are the solvable polynomial rings, a class
intermediate between commutative and general non-commutative polynomial rings.
They were studied by Kandri-Rody, Weispfenning and Kredel [KRW90, Kre93].
Solvable polynomial rings can be described by ordinary polynomial rings
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ provided with a “new” definition of
multiplication which coincides with the ordinary multiplication except for the
case that a variable $X_{j}$ is multiplied with a variable $X_{i}$ with lower
index, i.e., $i<j$. In the latter case multiplication can be defined by
equations of the form $X_{j}\star X_{i}=c_{ij}X_{i}X_{j}+p_{ij}$ where
$c_{ij}$ lies in ${\mathbb{K}}^{*}={\mathbb{K}}\backslash\\{0\\}$ and $p_{ij}$
is a polynomial “smaller” than $X_{i}X_{j}$ with respect to a fixed admissible
term ordering on the polynomial ring.

The more special case of twisted semi-group rings, where $c_{ij}=0$ is
possible, has been studied in [Ape88, Mor89].

In [Wei87a] Weispfenning showed the existence of finite Gröbner bases for
arbitrary finitely generated ideals in non-Noetherian skew polynomial rings
over two variables $X,Y$ where a “new” multiplication $\star$ is introduced
such that $X\star Y=XY$ and $Y\star X=X^{e}Y$ for some fixed $e$ in
${\mathbb{N}}^{+}$.

Ore extensions have been successfully studied by Pesch in his PhD Thesis
[Pes97] and his results on two-sided Gröbner bases are also presented in
[Pes98].

Most of the results cited so far assume admissible well-founded orderings on
the set of terms so that in fact the reduction relations can be defined by
considering the head monomials mainly (compare the algebraic definition of
Gröbner bases in Section 1.2). This is essential to characterize Gröbner bases
in the respective ring with respect to the corresponding reduction
relation777These reduction relations are based on divisibility of terms,
namely the term to be reduced is divisible by the head term of the polynomial
used as rule for the reduction step. in a finitary manner and to enable to
decide whether a finite set is a Gröbner basis by checking whether the
s-polynomials are reducible to zero888Note that we always assume that the
reduction relation in the ring is effective..

There are rings combined with reduction relations where admissible well-
founded orderings cannot be accomplished and, therefore, other concepts to
characterize Gröbner bases have been developed. For example in case the ring
contains zero-divisors a well-founded ordering on the ring is no longer
compatible with the ring multiplication999When studying monoid rings over
reduction rings it is possible that the ordering on the ring is not compatible
with scalar multiplication as well as with multiplication with monomials or
polynomials.. This phenomenon has been studied for the case of zero-divisors
in the coefficient domain by Kapur and Madlener [KM89] and by Weispfenning for
the special case of regular rings [Wei87b]. In his PhD thesis [Kre93], Kredel
described problems occurring when dropping the axioms guaranteeing the
existence of admissible orderings in the theory of solvable polynomial rings
by allowing $c_{ij}=0$ in the defining equations above. He sketched the idea
of using saturation techniques to repair some of them. Saturation enlarges the
generating sets of ideals in order to ensure that enough head terms exist to
do all necessary reduction steps and this process can often be related to
additional special critical pairs. Similar ideas can be found in the PhD
thesis of Apel [Ape88]. For special cases, e.g. for the Grassmann (exterior)
algebras, positive results can be achieved (compare the paper of Stokes
[Sto90]).

Another important class of rings where reduction relations can be introduced
and completion techniques can be applied to enumerate and sometimes compute
Gröbner bases are monoid and group rings. They have been studied in detail by
various authors, e.g. free group rings ([Ros93]), monoid and group rings
([MR93a, MR97a, Rei95, Rei96, MR98a]) (including finite and free monoids and
finite, free, plain and polycyclic groups), and polycyclic group rings
([Lo98]). In this setting we again need saturation techniques to repair a
severe defect due to the fact that in general we cannot expect the ordering on
the set of terms (here of course now the monoid or group elements) to be both,
well-founded and admissible. Let ${\cal F}$ be the free group generated by one
element $a$. Then for the polynomial $a+1$ in ${\mathbb{Q}}[{\cal F}]$ we have
$(a+1)\ast a^{-1}=1+a^{-1}$, i.e., after multiplication with the inverse
element $a^{-1}$ the largest term of the new polynomial no longer results from
the largest one of the original polynomial. Moreover, assuming our ordering is
well-founded, it cannot be compatible with the group
multiplication101010Assuming $a\succ 1$ compatibility with multiplication
would imply $1\succ a^{-1}$ giving rise to an infinite descending chain
$a^{-1}\succ a^{-2}\succ\ldots$ contradicting the well-foundedness of the
ordering. On the other hand for $1\succ a$ compatibility with multiplication
immediately gives us an infinite descending chain $a\succ a^{2}\succ\ldots$..

All approaches cited in this section can be basically divided into two main
streams: One extension was to study structures which still allow to present
their elements by ordinary “commutative” polynomials. The advantage of this
generalization is that Dickson’s Lemma, which is essential in proving
termination for Buchberger’s algorithm, carries over. The other idea of
generalization was to view the polynomial ring as a special monoid ring and to
try to extend Buchberger’s approach to other monoid and group rings. Since
then in general Dickson’s Lemma no longer holds, other ways to prove
termination, if possible, have to be established. Notice that solvable rings,
skew-polynomial rings and arbitrary quotients of non-commutative polynomial
rings cannot be interpreted as monoid rings. Hence to find a generalization
which will subsume all results cited here, a more general setting is needed.
In his habilitation thesis [Ape98], Apel provides one generalization which
basically extends the first one of these two in such a way that Mora’s
approach can be incorporated. He uses an abstraction of graded structures
which needs admissible well-founded orderings. Hence he cannot deal with group
rings and many cases of monoid rings where such orderings cannot exists. On
the other hand he is much more interested in algebraic characterizations of
Gröbner bases and the division algorithms associated to them.

In order to characterize structures where the well-founded ordering is no
longer admissible, we extend Gröbner basis techniques to an abstract setting
called function rings.

###  1.5 Gröbner Bases in Function Rings – A Guide for Introducing Reduction
Relations to Algebraic Structures

The aim of this work is to give a general setting which comprises all
generalizations mentioned above and which is a basis for studying further
structures in the light of introducing reduction relations and Gröbner basis
techniques. All structures mentioned so far can be viewed as rings of
functions with finite support. For such rings we introduce the familiar
concepts of polynomials, (right) ideals, standard representations, standard
bases, reduction relations and Gröbner bases. A general characterization of
Gröbner bases in an “algorithmic fashion” is provided. It is shown that in
fact polynomial rings, solvable polynomial rings, free respectively finite
monoid rings, and free, finite, plain, respectively polycyclic group rings are
examples of our generalization where finite Gröbner bases can be computed.
While most of the examples cited above are presented in the literature as
rings over fields we will here also present the more general concept of
function rings over reduction rings (compare [Mad86, Rei95, MR98b]) and the
impotant special case of function rings over the integers.

###  1.6 Applications of Gröbner Bases Generalized to Function Rings

For polynomial rings over fields many algebraic questions related to ideals
can be solved using Gröbner bases and their associated reduction relations.
Hence the question arises which of these applications can be extended to more
general settings. While some questions e.g. concerning algebraic geometry are
strongly connected to polynomial rings over fields, many other applications
carry over. They include natural ones such as the membership problem for
ideals, as well as special techniques such as elimination theory or the
treatment of systems of linear equations.

###  1.7 Organization of the Contents

Chapter 2 introduces some of the basic themes of this book. We need some basic
notions from the theory of algebra as well as from the theory of rewriting
systems. Furthermore, as the aim of this book is to provide a systematic study
of Gröbner basis methods, a short introduction to the original case of Gröbner
bases in polynomial rings over fields is presented.

Chapter 3 concentrates on rings with reduction relations, which are studied
with regard to the existence of Gröbner bases. They are called reduction rings
in case they allow finite Gröbner bases for finitely generated ideals.
Moreover, special ring constructions are presented, which in many cases
preserve the existence of Gröbner bases. These constructions include quotients
and sums of reduction rings as well as modules and polynomial rings over
reduction rings. Many structures with reduction relations allowing Gröbner
bases can already be found in this setting. For example knowing that the
integers ${\mathbb{Z}}$ for certain reduction relations allow finite Gröbner
bases, using the results of this chapter, we can conclude that the module
${\mathbb{Z}}^{k}$ as well as the polynomial rings
${\mathbb{Z}}[X_{1},\ldots,X_{n}]$ and ${\mathbb{Z}}^{k}[X_{1},\ldots,X_{n}]$
allow the computation of finite Gröbner bases.

Chapter 4 is the heart of this book. It establishes a generalizing framework
for structures enriched with reduction relations and studied with respect to
the existence of Gröbner bases in the literature. Reduction relations are
defined for the setting of function rings over fields and later on generalized
to reduction rings. Definitions for terms such as variations of standard
representations, standard bases and Gröbner bases are given and compared to
the known terms from the theory of Gröbner bases over polynomial rings. It
turns out that while completion procedures will still involve equivalents to
s-polynomials or the more general concept of g- and m-polynomials for the ring
case, these situations are no longer sufficient to characterize Gröbner bases.
Saturation techniques, which enrich the bases by additional polynomials, are
needed. Moreover, for function rings over reduction rings the
characterizations no longer describe Gröbner bases but only weak111111Weak
Gröbner bases are bases such that any polynomial in the ideal they generate
can be reduced to zero. For fields this property already characterizes Gröbner
bases as the Translation Lemma holds. In general this is not true and while
weak Gröbner bases allows to solve the ideal membership problem they no longer
guarantee the existence of unique normal forms for elements of the quotient.
Gröbner bases, since the Translation Lemma121212The Translation Lemma
establishes that if for two polynomials $f,g$ we have that $f-g$ reduces to
zero, both polynomials reduce to the same normal form. no longer holds. Since
the ring of integers viewed as a reduction ring is of special interest in the
literature and allows more insight into the respective chosen reduction
relations, this special case is studied.

Chapter 5 outlines how some applications known for Gröbner bases in the
literature carry over to function rings. These applications include natural
ones such as the ideal membership problem, representation problems, the ideal
inclusion problem, the ideal triviality problem, and many more. Another focus
is on doing computations in quotient rings using Gröbner bases. The powerful
elimination methods are also generalized. One of their applications to study
polynomial mappings is outlined. Finally solutions for linear equations over
function rings in terms of Gröbner bases are provided.

##  Chapter 2 Basic Definitions

After introducing the necessary definitions required from algebra we focus on
the subject of this book — Gröbner bases. One way of characterizing Gröbner
bases is in terms of algebraic simplification or reduction. The aim of this
chapter is to introduce an abstract concept for the notion of reduction which
is the basis of many syntactical methods for studying structures in
mathematics or theoretical computer science in Section 2.2. It is the
foundation for e.g. term rewriting and string rewriting and we introduce a
reduction relation for polynomials in the commutative polynomial ring over a
field in a similar fashion. Gröbner bases then arise naturally when doing
completion in this setting in Section 2.3.

###  2.1 Algebra

Mathematical theories are closely related with the study of two objects,
namely sets and functions. Algebra can be regarded as the study of algebraic
operations on sets, i.e., functions that take elements from a set to the set
itself. Certain algebraic operations on sets combined with certain axioms are
again the objects of independent theories. This chapter is a short
introduction to some of the algebraic systems used later on: monoids, groups,
rings, fields, ideals and modules.

###### Definition 2.1.1

A non-empty set of elements ${\cal M}$ together with a binary operation
$\circ_{{\cal M}}$ is said to form a monoid, if for all $\alpha,\beta,\gamma$
in ${\cal M}$

  1. 1.

${\cal M}$ is closed under $\circ_{{\cal M}}$, i.e., $\alpha\circ_{{\cal
M}}\beta\in{\cal M}$,

  2. 2.

the associative law holds for $\circ_{{\cal M}}$, i.e., $\alpha\circ_{{\cal
M}}(\beta\circ_{{\cal M}}\gamma)=_{{\cal M}}(\alpha\circ_{{\cal
M}}\beta)\circ_{{\cal M}}\gamma$, and

  3. 3.

there exists $1_{{\cal M}}\in{\cal M}$ such that $\alpha\circ_{{\cal
M}}1_{{\cal M}}=_{{\cal M}}1_{{\cal M}}\circ_{{\cal M}}\alpha=_{{\cal
M}}\alpha$. The element $1_{{\cal M}}$ is called identity. $\diamond$

For simplicity of notation we will henceforth drop the index ${\cal M}$ and
write $\circ$ respectively $=$ if no confusion is likely to arise.
Furthermore, we will often talk about a monoid without mentioning its binary
operation explicitly. The monoid operation will often be called multiplication
or addition. Since the algebraic operation is associative we can omit
brackets, hence the product $\alpha_{1}\circ\ldots\circ\alpha_{n}$ is uniquely
defined.

###### Example 2.1.2

Let $\Sigma=\\{a_{1},\ldots,a_{n}\\}$ be a set of letters. Then $\Sigma^{*}$
denotes the set of words over this alphabet. For two words $u,v\in\Sigma^{*}$
we define $u\circ v=uv$, i.e., the word which arises from concatenating the
two words $u$ and $v$. Then $\Sigma^{*}$ is a monoid with respect to this
binary operation and its identity element is the empty word, i.e., the word
containing no letters. This monoid is called the free monoid over the alphabet
$\Sigma$. $\diamond$

For some $n$ in ${\mathbb{N}}$111In the following ${\mathbb{N}}$ denotes the
set of natural numbers including zero and
${\mathbb{N}}^{+}={\mathbb{N}}\backslash\\{0\\}$. the product of $n$ times the
same element $\alpha$ is called the n-th power of $\alpha$ and will be denoted
by $\alpha^{n}$, where $\alpha^{0}=1$.

###### Definition 2.1.3

An element $\alpha$ of a monoid ${\cal M}$ is said to have infinite order in
case for all $n,m\in{\mathbb{N}}$, $\alpha^{n}=\alpha^{m}$ implies $n=m$. We
say that $\alpha$ has finite order in case the set $\\{\alpha^{n}\mid
n\in{\mathbb{N}}^{+}\\}$ is finite and the cardinality of this set is then
called the order of $\alpha$. $\diamond$

A subset of a monoid ${\cal M}$ which is again a monoid is called a submonoid
of ${\cal M}$. Other special subsets of monoids are (one-sided) ideals.

###### Definition 2.1.4

For a subset $S$ of a monoid ${\cal M}$ we call

  1. 1.

${\sf ideal}_{r}^{{\cal M}}(S)=\\{\sigma\circ\alpha\mid\sigma\in
S,\alpha\in{\cal M}\\}$ the right ideal,

  2. 2.

${\sf ideal}_{l}^{{\cal M}}(S)=\\{\alpha\circ\sigma\mid\sigma\in
S,\alpha\in{\cal M}\\}$ the left ideal, and

  3. 3.

${\sf ideal}^{{\cal
M}}(S)=\\{\alpha\circ\sigma\circ\alpha^{\prime}\mid\sigma\in
S,\alpha,\alpha^{\prime}\in{\cal M}\\}$ the ideal

generated by $S$ in ${\cal M}$. $\diamond$

A monoid ${\cal M}$ is called commutative (Abelian) if we have
$\alpha\circ\beta=\beta\circ\alpha$ for all elements $\alpha,\beta$ in ${\cal
M}$. A natural example for a commutative monoid are the integers together with
multiplication or addition. Another example which will be of interest later on
is the set of terms.

###### Example 2.1.5

Let $X_{1},\ldots,X_{n}$ be a set of (ordered) variables. Then ${\cal
T}=\\{X_{1}^{i_{1}}\ldots X_{n\phantom{1}}^{i_{n}}\mid i_{1},\ldots
i_{n}\in{\mathbb{N}}\\}$ is called the set of terms over these variables. The
multiplication $\circ$ is defined as $X_{1}^{i_{1}}\ldots
X_{n\phantom{1}}^{i_{n}}\circ X_{1}^{j_{1}}\ldots
X_{n\phantom{1}}^{j_{n}}=X_{1}^{i_{1}+j_{1}}\ldots
X_{n\phantom{1}}^{i_{n}+j_{n}}$. The identity is the empty term $1_{\cal
T}=X_{1}^{0}\ldots X_{n\phantom{1}}^{0}$. $\diamond$

A mapping $\phi$ from one monoid ${\cal M}_{1}$ to another monoid ${\cal
M}_{2}$ is called a homomorphism, if $\phi(1_{{\cal M}_{1}})=1_{{\cal M}_{2}}$
and for all $\alpha,\beta$ in ${\cal M}_{1}$, $\phi(\alpha\circ_{{\cal
M}_{1}}\beta)=\phi(\alpha)\circ_{{\cal M}_{2}}\phi(\beta)$. In case $\phi$ is
surjective we call it an epimorphism, in case $\phi$ is injective a
monomorphism and in case it is both an isomorphism. The fact that two
structures $S_{1}$, $S_{2}$ are isomorphic will be denoted by $S_{1}\cong
S_{2}$.

A monoid is called left-cancellative (respectively right-cancellative) if for
all $\alpha,\beta,\gamma$ in ${\cal M}$, $\gamma\circ\alpha=\gamma\circ\beta$
(respectively $\alpha\circ\gamma=\beta\circ\gamma$) implies $\alpha=\beta$. In
case a monoid is both, left- and right-cancellative, it is called
cancellative. In case $\alpha\circ\gamma=\beta$ we say that $\alpha$ is a left
divisor of $\beta$ and $\gamma$ is called a right divisor of $b$. If
$\gamma\circ\alpha\circ\delta=\beta$ then $\alpha$ is called a divisor of
$\beta$. A special class of monoids fulfill that for all $\alpha,\beta$ in
${\cal M}$ there exist $\gamma,\delta$ in ${\cal M}$ such that
$\alpha\circ\gamma=\beta$ and $\delta\circ\alpha=\beta$, i.e., right and left
divisors always exist. These structures are called groups and they can be
specified by extending the definition of monoids and we do so by adding one
further axiom.

###### Definition 2.1.6

A monoid ${\cal M}$ together with its binary operation $\circ$ is said to form
a group if additionally

  1. 4.

for every $\alpha\in{\cal M}$ there exists an element ${\sf
inv}\/(\alpha)\in{\cal M}$ (called inverse of $\alpha$) such that
$\alpha\circ{\sf inv}\/(\alpha)={\sf inv}\/(\alpha)\circ\alpha=1$. $\diamond$

Obviously, the integers form a group with respect to addition, but this is no
longer true for multiplication.

A subset of a group ${\cal G}$ which is again a group is called a subgroup of
${\cal M}$. A subgroup ${\cal H}$ of a group ${\cal G}$ is called normal if
for each $\alpha$ in ${\cal G}$ we have $\alpha{\cal H}={\cal H}\alpha$ where
$\alpha{\cal H}=\\{\alpha\circ\beta\mid\beta\in{\cal H}\\}$ and ${\cal
H}\alpha=\\{\beta\circ\alpha\mid\beta\in{\cal H}\\}$.

We end this section by briefly introducing some more algebraic structures that
will be used throughout.

###### Definition 2.1.7

A nonempty set ${\sf R}$ is called an (associative) ring (with unit element)
if there are two binary operations $+$ (addition) and $\star$ (multiplication)
such that for all $\alpha,\beta,\gamma$ in ${\sf R}$

  1. 1.

${\sf R}$ together with $+$ is an Abelian group with zero element $0$ and
inverse $-\alpha$,

  2. 2.

${\sf R}$ is closed under $\star$, i.e., $\alpha\star\beta\in{\sf R}$,

  3. 3.

$\star$ is associative, i.e.,
$\alpha\star(\beta\star\gamma)=(\alpha\star\beta)\star\gamma$,

  4. 4.

the distributive laws hold, i.e.,
$\alpha\star(\beta+\gamma)=\alpha\star\beta+\alpha\star\gamma$ and
$(\beta+\gamma)\star\alpha=\beta\star\alpha+\gamma\star\alpha$,

  5. 5.

there is an element $1\in{\sf R}$ (called unit) such that
$1\star\alpha=\alpha\star 1=\alpha$. $\diamond$

A ring is called commutative (Abelian) if $\alpha\star\beta=\beta\star\alpha$
for all $\alpha,\beta$ in ${\sf R}$. The integers together with addition and
multiplication are a well-known example of a ring. Other rings which will be
of interest later on are monoid rings.

###### Example 2.1.8

Let ${\mathbb{Z}}$ be the ring of integers and ${\cal M}$ a monoid. Further
let ${\mathbb{Z}}[{\cal M}]$ denote the set of all mappings $f:{\cal
M}\longrightarrow{\mathbb{Z}}$ where the sets ${\sf supp}(f)=\\{\alpha\in{\cal
M}\mid f(\alpha)\neq 0\\}$ are finite. We call ${\mathbb{Z}}[{\cal M}]$ the
monoid ring of ${\cal M}$ over ${\mathbb{Z}}$. The sum of two elements $f$ and
$g$ is denoted by $f+g$ where $(f+g)(\alpha)=f(\alpha)+g(\alpha)$. The product
is denoted by $f\star g$ where $(f\star
g)(\alpha)=\sum_{\beta\circ\gamma=\alpha}f(\beta)\star g(\gamma)$.

Polynomial rings are a special case of monoid rings namely over the set of
terms as defined in Example 2.1.5.

A ring ${\sf R}$ is said to contain zero-divisors, if there exist not
necessarily different elements $\alpha,\beta$ in ${\sf R}$ such that
$\alpha\neq 0$ and $\beta\neq 0$, but $\alpha\star\beta=0$. Then $\alpha$ is
called a left zero-divisor and $\beta$ is called a right zero-divisor.

###### Definition 2.1.9

A commutative ring is called a field if its non-zero elements form a group
under multiplication. $\diamond$

Similar to our proceeding in group theory we will now look at subsets of a
ring ${\sf R}$. For a subset $U\subseteq{\sf R}$ to be a subring of $R$ with
the operations $+$ and $\star$ it is necessary and sufficient that

  1. 1.

$U$ is a subgroup of $({\sf R},+)$, i.e., for $a,b\in U$ we have $a-b\in U$,
and

  2. 2.

for all $\alpha,\beta\in U$ we have $\alpha\star\beta\in U$.

We will now take a closer look at special subrings that play a role similar to
normal subgroups in group theory.

###### Definition 2.1.10

A nonempty subset $\mathfrak{i}$ of a ring ${\sf R}$ is called a right (left)
ideal of ${\sf R}$, if

  1. 1.

for all $\alpha,\beta\in\mathfrak{i}$ we have $\alpha-\beta\in\mathfrak{i}$,
and

  2. 2.

for every $\alpha\in\mathfrak{i}$ and $\rho\in{\sf R}$, the element
$\alpha\star\rho$ (respectively $\rho\star\alpha$) lies in $\mathfrak{i}$.

A subset that is both, a right and a left ideal, is called a (two-sided) ideal
of ${\sf R}$. $\diamond$

For each ring the sets $\\{0\\}$ and ${\sf R}$ are trivial ideals. Similar to
subgroups, ideals can be described in terms of generating sets.

###### Lemma 2.1.11

Let $F$ be a non-empty subset of ${\sf R}$. Then

  1. 1.

${\sf ideal}^{{\sf
R}}(F)=\\{\sum_{i=1}^{n}\rho_{i}\star\alpha_{i}\star\sigma_{i}\mid\alpha_{i}\in
F,\rho_{i},\sigma_{i}\in{\sf R},n\in{\mathbb{N}}\\}$ is an ideal of ${\sf R}$,

  2. 2.

${\sf ideal}_{r}^{{\sf
R}}(F)=\\{\sum_{i=1}^{n}\alpha_{i}\star\rho_{i}\mid\alpha_{i}\in
F,\rho_{i}\in{\sf R},n\in{\mathbb{N}}\\}$ is a right ideal of ${\sf R}$, and

  3. 3.

${\sf ideal}_{l}^{{\sf
R}}(F)=\\{\sum_{i=1}^{n}\rho_{i}\star\alpha_{i}\mid\alpha_{i}\in
F,\rho_{i}\in{\sf R},n\in{\mathbb{N}}\\}$ is a left ideal of ${\sf R}$.
$\diamond$

Notice that the empty sum $\sum_{i=1}^{0}\alpha_{i}$ is zero.

We will simply write ${\sf ideal}(F)$, ${\sf ideal}_{r}(F)$ and ${\sf
ideal}_{l}(F)$ if the context is clear. Many algebraic problems for rings are
related to ideals and we will close this section by stating two of them222For
more information on such problems in the special case of commutative
polynomial rings see e.g. [Buc87]..

The Ideal Membership Problem
---
Given: | An element $\alpha\in{\sf R}$ and a set of elements $F\subseteq{\sf R}$.
Question: | Is $\alpha$ in the ideal generated by $F$?

###### Definition 2.1.12

Two elements $\alpha,\beta\in{\sf R}$ are said to be congruent modulo ${\sf
ideal}(F)$, denoted by $\alpha\equiv_{{\sf ideal}(F)}\beta$, if
$\alpha=\beta+\rho$ for some $\rho\in{\sf ideal}(F)$, i.e.,
$\alpha-\beta\in{\sf ideal}(F)$. $\diamond$

The Congruence Problem
---
Given: | Two elements $\alpha,\beta\in{\sf R}$ and a set of elements $F\subseteq{\sf R}$.
Question: | Are $\alpha$ and $\beta$ congruent modulo the ideal generated by $F$?

Note that both problems can similarly be specified for left and right ideals.

We have seen that a non-empty subset of ${\sf R}$ is an ideal if it is closed
under addition and closed under multiplication with arbitrary elements of
${\sf R}$. Modules now can be viewed as a natural generalization of the
concept of ideals to arbitrary commutative groups.

###### Definition 2.1.13

Let ${\sf R}$ be a ring. A left ${\sf R}$-module $M$ is an additive
commutative group with an additional operation $\cdot:{\sf R}\times
M\longrightarrow M$, called scalar multiplication, such that for all
$\alpha,\beta\in{\sf R}$ and $a,b\in M$, the following hold:

  1. 1.

$\alpha\cdot(a+b)=\alpha\cdot a+\alpha\cdot b$,

  2. 2.

$(\alpha+\beta)\cdot a=\alpha\cdot a+\beta\cdot a$,

  3. 3.

$(\alpha\star\beta)\cdot a=\alpha\cdot(\beta\cdot a)$, and

  4. 4.

$1\cdot a=a$. $\diamond$

We can define right ${\sf R}$-modules and (two-sided) ${\sf R}$-modules (also
called ${\sf R}$-bimodules) in a similar fashion.

Notice that a (left, right) ideal $\mathfrak{i}\subseteq{\sf R}$ forms a
(left, right) ${\sf R}$-module with respect to the addition and multiplication
in ${\sf R}$. This obviously holds for the trivial (left, right) ideals
$\\{0\\}$ and ${\sf R}$ of ${\sf R}$.

Another example of (left, right) ${\sf R}$-modules we will study are the
finite direct products of the ring called free (left, right) ${\sf R}$-modules
${\sf R}^{k}$, $k\in{\sf R}$.

An additive subset of a (left, right) ${\sf R}$-module is called a (left,
right) submodule if it is closed under scalar multiplication with elements of
${\sf R}$. For a subset $F\subseteq M$ let $\langle F\rangle$ denote the
submodule generated by $F$ in $M$.

The Submodule Membership Problem
---
Given: | An element $a\in M$ and a set of elements $F\subseteq M$.
Question: |  $a\in\langle F\rangle$?

Similar to the congruence problem for ideals we can specify the congruence
problem for submodules as follws:

###### Definition 2.1.14

Two elements $a,b\in{\sf R}$ are said to be congruent modulo the submodule
$\langle F\rangle$ for some $F\subseteq M$, denoted by $a\equiv_{\langle
F\rangle}b$, if $a-b\in\langle F\rangle$. $\diamond$

The Congruence Problem for submodules
---
Given: | Two elements $a,b\in{\sf R}$ and a set of elements $F\subseteq M$.
Question: |  $a\equiv_{\langle F\rangle}b$?

###  2.2 The Notion of Reduction

This section summarizes some important notations and definitions of reduction
relations and basic properties related to them, as can be found more
explicitly for example in the work of Huet or Book and Otto ([Hue80, Hue81,
BO93]).

Let ${\cal E}$ be a set of elements and $\longrightarrow$ a binary relation on
${\cal E}$ called reduction. For $a,b\in{\cal E}$ we will write
$a\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}\,$}b$ in
case $(a,b)\in\;\;\longrightarrow$. A pair $({\cal E},\longrightarrow)$ will
be called a reduction system. Then we can expand the binary relation as
follows:

$\,\stackrel{{\scriptstyle 0}}{{\longrightarrow}}\\!\\!\mbox{}\,$ |  |  | denotes the identity on ${\cal E}$,
---|---|---|---
$\,\stackrel{{\scriptstyle}}{{\longleftarrow}}\\!\\!\mbox{}\,$$\,\stackrel{{\scriptstyle+}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$ |  |  | denotes the inverse relation for $\longrightarrow$,
$\,\stackrel{{\scriptstyle n+1}}{{\longrightarrow}}\\!\\!\mbox{}\,$ |  $:=$ |  $\mbox{$\,\stackrel{{\scriptstyle n}}{{\longrightarrow}}\\!\\!\mbox{}\,$}\circ\longrightarrow$ | where $\circ$ denotes composition of relations and $n\in{\mathbb{N}}$,
$\,\stackrel{{\scriptstyle\leq n}}{{\longrightarrow}}\\!\\!\mbox{}\,$ |  $:=$ |  $\;\\!\bigcup_{0\leq i\leq n}\\!\\!\mbox{$\,\stackrel{{\scriptstyle i}}{{\longrightarrow}}\\!\\!\mbox{}\,$}$,
$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}\,$ |  $:=$ |  $\;\\!\bigcup_{n>0}\\!\mbox{$\,\stackrel{{\scriptstyle n}}{{\longrightarrow}}\\!\\!\mbox{}\,$}$ | denotes the transitive closure of $\longrightarrow$,
$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$ |  $:=$ |  $\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}\,$}\cup\mbox{$\,\stackrel{{\scriptstyle 0}}{{\longrightarrow}}\\!\\!\mbox{}\,$}$ | denotes the reflexive transitive closure of $\longrightarrow$,
$\,\stackrel{{\scriptstyle}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$ |  $:=$ |  $\;\\!\longleftarrow\cup\longrightarrow$$\,\stackrel{{\scriptstyle+}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$ | denotes the symmetric closure of $\longrightarrow$,
$\,\stackrel{{\scriptstyle+}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$ |  |  | denotes the symmetric transitive closure of $\longrightarrow$,
$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$$\,\stackrel{{\scriptstyle+}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$ |  |  | denotes the reflexive symmetric transitive closure of $\longrightarrow$.

A well-known decision problem related to a reduction system is the word
problem.

###### Definition 2.2.1

The word problem for a reduction system $({\cal E},\longrightarrow)$ is to
decide for $a,b$ in ${\cal E}$, whether
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}\,$}b$
holds. $\diamond$

Instances of this problem are well-known in the literature and undecidable in
general. In the following we will outline sufficient conditions such that a
reduction system $({\cal E},\longrightarrow)$ has solvable word problem.

An element $a\in{\cal E}$ is said to be reducible (with respect to
$\longrightarrow$) if there exists an element $b\in{\cal E}$ such that
$a\longrightarrow b$. All elements $b\in{\cal E}$ such that
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}b$
are called successors of $a$ and in case
$a\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}\,$}b$
they are called proper successors. An element which has no proper successors
is called irreducible. In case
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}b$
and $b$ is irreducible, $b$ is called a normal form of $a$. Notice that for an
element $a$ in ${\cal E}$ there can be no, one or many normal forms.

###### Definition 2.2.2

A reduction system $({\cal E},\longrightarrow)$ is said to be Noetherian (or
terminating) in case there are no infinitely descending reduction chains
$a_{0}\longrightarrow a_{1}\longrightarrow\ldots\;$, with $a_{i}\in{\cal E}$,
$i\in{\mathbb{N}}$. $\diamond$

In case a reduction system $({\cal E},\longrightarrow)$ is Noetherian every
element in ${\cal E}$ has at least one normal form.

###### Definition 2.2.3

A reduction system $({\cal E},\longrightarrow)$ is called confluent, if for
all $a,a_{1},a_{2}\in{\cal E}$,
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{1}$
and
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{2}$
implies the existence of $a_{3}\in{\cal E}$ such that
$a_{1}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{3}$
and
$a_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{3}$,
and $a_{1}$, $a_{2}$ are called joinable. $\diamond$

In case a reduction system $({\cal E},\longrightarrow)$ is confluent every
element has at most one normal form. We can combine these two properties to
give sufficient conditions for the solvability of the word problem.

###### Definition 2.2.4

A reduction system $({\cal E},\longrightarrow)$ is said to be complete (or
convergent) in case it is both, Noetherian and confluent. $\diamond$

Complete reduction systems with effective or computable333By effective or
computable we mean that given an element we can always construct a successor
in case one exists. reduction relations have solvable word problem, as every
element has a unique normal form and two elements are equal if and only if
their normal forms are equal. Of course we cannot always expect $({\cal
E},\longrightarrow)$ to be complete. Even worse, both properties – termination
and confluence – are undecidable in general. Nevertheless, there are weaker
conditions which guarantee completeness.

###### Definition 2.2.5

A reduction system $({\cal E},\longrightarrow)$ is said to be locally
confluent, if for all $a,a_{1},a_{2}\in{\cal E}$,
$a\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{1}$
and
$a\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{2}$
implies the existence of an element $a_{3}\in{\cal E}$ such that
$a_{1}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{3}$
and
$a_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{3}$.
$\diamond$

I.e. local confluence is a special instance of confluence, namely a
localization of confluence to one-reduction-step successors of elements only.
The next lemma gives an important connection between local confluence and
confluence.

######  Lemma 2.2.6 (Newman)

Let $({\cal E},\longrightarrow)$ be a Noetherian reduction system. Then
$({\cal E},\longrightarrow)$ is confluent if and only if $({\cal
E},\longrightarrow)$ is locally confluent.

To prove Newman’s lemma we need the concept of Noetherian induction which is
based on the following definition.

###### Definition 2.2.7

Let $({\cal E},\longrightarrow)$ be a reduction system. A predicate ${\cal P}$
on ${\cal E}$ is called $\longrightarrow$-complete, in case for every
$a\in{\cal E}$ the following implication holds: if ${\cal P}(b)$ is true for
all proper successors of $a$, then ${\cal P}(a)$ is true. $\diamond$

The Principle of Noetherian Induction:
In case $({\cal E},\longrightarrow)$ is a Noetherian reduction system and
${\cal P}$ is a predicate that is $\longrightarrow$-complete, then for all
$a\in{\cal E}$, ${\cal P}(a)$ is true.

Proof of Newman’s lemma:
Suppose, first, that the reduction system $({\cal E},\longrightarrow)$ is
confluent. This immediately implies the local confluence of $({\cal
E},\longrightarrow)$ as a special case. To show the converse, since $({\cal
E},\longrightarrow)$ is Noetherian we can apply the principle of Noetherian
induction to the following predicate:

${\cal P}(a)$

if and only if

for all $a_{1},a_{2}\in{\cal E}$,
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{1}$
and
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{2}$
implies that $a_{1}$ and $a_{2}$ are joinable.

All we have to do now is to show that ${\cal P}$ is
$\longrightarrow$-complete. Let $a\in{\cal E}$ and let ${\cal P}(b)$ be true
for all proper successors $b$ of $a$. We have to prove that ${\cal P}(a)$ is
true. Suppose
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{1}$
and
$a\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{2}$.
In case $a=a_{1}$ or $a=a_{2}$ there is nothing to show. Therefore, let us
assume $a\neq a_{1}$ and $a\neq a_{2}$, i.e.,
$a\longrightarrow\tilde{a}_{1}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{1}$
and
$a\longrightarrow\tilde{a}_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}\,$}a_{2}$.
Then we can deduce the following figure where $b_{0}$ exists, as $({\cal
E},\longrightarrow)$ is locally confluent and $b_{1}$ and $b$ exist by our
induction hypothesis since $a_{1}$, $b_{0}$ as well as $a_{2}$, $b_{1}$ are
proper successors of $a$. Hence $a_{1}$ and $a_{2}$ must be joinable, i.e.,
the reduction system $({\cal E},\longrightarrow)$ is confluent.
q.e.d.

Therefore, if the reduction system is terminating, a check for confluence can
be reduced to a check for local confluence. The concept of completion then is
based on two steps:

  1. 1.

Check the system for local confluence.
If it is locally confluent, then it is also complete.

  2. 2.

Add new relations arising from situations where the system is not locally
confluent.

For many reduction systems, e.g. string rewriting systems or term rewriting
systems, the check for local confluence again can be localized, often to
finite test sets of so-called critical pairs. The relations arising from such
critical situations are either confluent or give rise to new relations which
stay within the congruence described by the reduction system. Hence adding
them in order to increase the descriptive power of the reduction system is
correct. This can be done until a complete set is reached. If fair strategies
are used in the test for local confluence, the limit system will be complete.

We close this section by providing sufficient conditions to ensure a reduction
system $({\cal E},\longrightarrow)$ to be Noetherian.

###### Definition 2.2.8

A binary relation $\succeq$ on a set $M$ is said to be a partial ordering, if
for all $a,b,c$ in $M$:

  1. 1.

$\succeq$ is reflexive, i.e., $a\succeq a$,

  2. 2.

$\succeq$ is transitive, i.e., $a\succeq b$ and $b\succeq c$ imply $a\succeq
c$, and

  3. 3.

$\succeq$ is anti-symmetrical, i.e., $a\succeq b$ and $b\succeq a$ imply
$a=b$. $\diamond$

A partial ordering is called total, if for all $a,b\in M$ either $a\succeq b$
or $b\succeq a$ holds. Further a partial ordering $\succeq$ defines a
transitive irreflexive ordering $\succ$, where $a\succ b$ if and only if
$a\succeq b$ and $a\neq b$, which is often called a proper or strict ordering.
We call a partial ordering $\succeq$ well-founded, if the corresponding strict
ordering $\succ$ allows no infinite descending chains $a_{0}\succ
a_{1}\succ\ldots\;$, with $a_{i}\in M$, $i\in{\mathbb{N}}$. Now we can give a
sufficient condition for a reduction system to be terminating.

###### Lemma 2.2.9

Let $({\cal E},\longrightarrow)$ be a reduction system and suppose there
exists a partial ordering $\succeq$ on ${\cal E}$ which is well-founded such
that $\longrightarrow\;\;\subseteq\;\;\succ$. Then $({\cal
E},\longrightarrow)$ is Noetherian.

Proof :
Suppose the reduction system $({\cal E},\longrightarrow)$ is not Noetherian.
Then there is an infinite sequence $a_{0}\longrightarrow
a_{1}\longrightarrow\ldots\;$, $a_{i}\in{\cal E}$, $i\in{\mathbb{N}}$. As
$\longrightarrow\;\subseteq\;\succ$ this sequence gives us an infinite
sequence $a_{0}\succ a_{1}\succ\ldots\;$, with $a_{i}\in{\cal E}$,
$i\in{\mathbb{N}}$ contradicting our assumption that $\succeq$ is well-founded
on ${\cal E}$.
q.e.d.

###  2.3 Gröbner Bases in Polynomial Rings

The main interest in this section is the study of ideals in polynomial rings
over fields. Let ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ denote a polynomial ring
over the (ordered) variables $X_{1},\ldots,X_{n}$ and the computable field
${\mathbb{K}}$. By ${\cal T}=\\{X_{1}^{i_{1}}\ldots
X_{n\phantom{1}}^{i_{n}}\mid i_{1},\ldots i_{n}\in{\mathbb{N}}\\}$ we define
the set of terms in this structure. A polynomial then is a formal sum
$\sum_{i=1}^{n}\alpha_{i}\cdot t_{i}$ with non-zero coefficients
$\alpha_{i}\in{\mathbb{K}}\backslash\\{0\\}$ and terms $t_{i}\in{\cal T}$. The
products $\alpha\cdot t$ for $\alpha\in{\mathbb{K}}$, $t\in{\cal T}$ are
called monomials and will often be denoted as $m=\alpha\cdot t$. We recall
that a subset $F$ of ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ generates an ideal
${\sf ideal}(F)=\\{\sum_{i=1}^{k}f_{i}\ast g_{i}\mid k\in{\mathbb{N}},f_{i}\in
F,g_{i}\in{\mathbb{K}}[X_{1},\ldots,X_{n}]\\}$ and $F$ is called a basis of
this ideal. It was shown by Hilbert using non-constructive arguments that
every ideal in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ in fact has a finite basis,
but such a generating set need not allow algorithmic solutions for the
membership or congruence problem related to the ideal as we have seen in the
introduction. It was Buchberger who developed a special type of basis, namely
the Gröbner basis, which allows algorithmic solutions for several algebraic
problems concerning ideals. He introduced a reduction relation to
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ by transforming polynomials into “rules”
and gave a terminating procedure to “complete” an ideal basis interpreted as a
reduction system. This procedure is called Buchberger’s algorithm in the
literature. We will give a sketch of his approach below.

Let $\succeq$ be a total well-founded ordering on the set of terms ${\cal T}$,
which is admissible, i.e., $t\succeq 1$, and $s\succ t$ implies $s\circ u\succ
t\circ u$ for all $s,t,u$ in ${\cal T}$. The latter property is called
compatibility with the multiplication $\circ$. In this context $\circ$ denotes
the multiplication in ${\cal T}$, i.e., $X_{1}^{i_{1}}\ldots
X_{n\phantom{1}}^{i_{n}}\circ X_{1}^{j_{1}}\ldots
X_{n\phantom{1}}^{j_{n}}=X_{1}^{i_{1}+j_{1}}\ldots
X_{n\phantom{1}}^{i_{n}+j_{n}}$. With respect to this multiplication we say
that a term $s=X_{1}^{i_{1}}\ldots X_{n\phantom{1}}^{i_{n}}$ divides a term
$t=X_{1}^{j_{1}}\ldots X_{n\phantom{1}}^{j_{n}}$, if for all $1\leq l\leq n$
we have $i_{l}\leq j_{l}$. The least common multiple ${\sf LCM}(s,t)$ of the
terms $s$ and $t$ is the term $X_{1}^{\max\\{i_{1},j_{1}\\}}\ldots
X_{n\phantom{1}}^{\max\\{i_{n},j_{n}\\}}$. Note that ${\cal T}$ can be
interpreted as the free commutative monoid generated by $X_{1},\ldots,X_{n}$
with the same multiplication $\circ$ as defined above and identity
$1=X_{1}^{0}\ldots X_{n\phantom{1}}^{0}$ (recall Example 2.1.5). We proceed to
give an example for a total well-founded admissible ordering on the set of
terms ${\cal T}$.

###### Example 2.3.1

A total degree ordering $\succ$ on ${\cal T}$ is specified as follows:
$X_{1}^{i_{1}}\ldots X_{n\phantom{1}}^{i_{n}}\succ X_{1}^{j_{1}}\ldots
X_{n\phantom{1}}^{j_{n}}$ if and only if
$\sum_{s=1}^{n}i_{s}>\sum_{s=1}^{n}j_{s}$ or
$\sum_{s=1}^{n}i_{s}=\sum_{s=1}^{n}j_{s}$ and there exists $k$ such that
$i_{k}>j_{k}$ and $i_{s}=j_{s},1\leq s<k$. $\diamond$

Henceforth, let $\succeq$ denote a total admissible ordering on ${\cal T}$
which is of course well-founded.

###### Definition 2.3.2

Let $p=\sum_{i=1}^{k}\alpha_{i}\cdot t_{i}$ be a non-zero polynomial in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ such that
$\alpha_{i}\in{\mathbb{K}}^{*}={\mathbb{K}}\backslash\\{0\\}$, $t_{i}\in{\cal
T}$ and $t_{1}\succ\ldots\succ t_{n}$. Then we let ${\sf
HM}(p)=\alpha_{1}\cdot t_{1}$ denote the head monomial, ${\sf HT}(p)=t_{1}$
the head term and ${\sf HC}(p)=\alpha_{1}$ the head coefficient of $p$. ${\sf
RED}(p)=p-{\sf HM}(p)$ stands for the reductum of $p$. We call $p$ monic in
case ${\sf HC}(p)=1$. These definitions can be extended to sets $F$ of
polynomials by setting ${\sf HT}(F)=\\{{\sf HT}(f)\mid f\in F\\}$, ${\sf
HC}(F)=\\{{\sf HC}(f)\mid f\in F\\}$, respectively ${\sf HM}(F)=\\{{\sf
HM}(f)\mid f\in F\\}$.  $\diamond$

Using the notions of this definition we can recursively extend $\succeq$ from
${\cal T}$ to a partial well-founded admissible ordering $\geq$ on
${\mathbb{K}}[X_{1},\ldots,X_{n}]$.

###### Definition 2.3.3

Let $p,q$ be two polynomials in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$. Then we
say $p$ is greater than $q$ with respect to a total well-founded admissible
ordering $\succeq$ on ${\cal T}$, i.e., $p>q$, if

  1. 1.

${\sf HT}(p)\succ{\sf HT}(q)$ or

  2. 2.

${\sf HM}(p)={\sf HM}(q)$ and ${\sf RED}(p)>{\sf RED}(q)$. $\diamond$

Now one first specialization of right ideal bases in terms of the
representations they allow can be given according to standard representations
as introduced e.g. in [BW92] for polynomial rings over fields.

###### Definition 2.3.4

Let $F$ be a set of polynomials in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ and $g$
a non-zero polynomial in ${\sf
ideal}(F)\subseteq{\mathbb{K}}[X_{1},\ldots,X_{n}]$. A representations of the
form

$\displaystyle g$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}f_{i}\star
m_{i},f_{i}\in F,m_{i}=\alpha_{i}\cdot
t_{i},\alpha_{i}\in{\mathbb{K}},t_{i}\in{\cal T},n\in{\mathbb{N}}$ (2.1)

where additionally ${\sf HT}(g)\succeq{\sf HT}(f_{i}\star m_{i})$ holds for
$1\leq i\leq n$ is called a standard representation of $g$ in terms of $F$. If
every $g\in{\sf ideal}(F)\backslash\\{0\\}$ has such a representation in terms
of $F$, then $F$ is called a standard basis of ${\sf ideal}(F)$. $\diamond$

What distinguishes an arbitrary representation from a standard representation
is the fact that the former may contain polynomial multiples with head terms
larger than the head term of the represented polynomial. For example let
$f_{1}=X_{1}+X_{2}$, $f_{2}=X_{1}+X_{3}$ and $F=\\{f_{1},f_{2}\\}$ in
${\mathbb{Q}}[X_{1},X_{2}]$ with $X_{1}\succ X_{2}\succ X_{3}$. Then for the
polynomial $g=X_{2}-X_{3}$ we have the representation $g=f_{1}+(-1)\cdot
f_{2}$ which is no standard one as ${\sf HT}(g)=X_{2}\prec{\sf HT}(f_{1})={\sf
HT}(f_{2})=X_{1}$. Obviously the larger head terms have to vanish in the sum.
Therefore, in order to change an arbitrary representation into one fulfilling
our additional condition (2.1) we have to deal with special sums of
polynomials related to such situations.

###### Definition 2.3.5

Let $F$ be a set of polynomials in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ and $t$
an element in ${\cal T}$. Then we define the set of critical situations ${\cal
C}(t,F)$ related to $t$ and $F$ to contain all tuples of the form
$(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k})$, $k\in{\mathbb{N}}$,
$f_{1},\ldots,f_{k}\in F$444Notice that $f_{1},\ldots,f_{k}$ are not
necessarily different polynomials from $F$., $m_{i}=\alpha_{i}\cdot t_{i}$,
such that

  1. 1.

${\sf HT}(f_{i}\star m_{i})=t$, $1\leq i\leq k$, and

  2. 2.

$\sum_{i=1}^{k}{\sf HM}(f_{i}\star m_{i})=0$.

We set ${\cal C}(F)=\bigcup_{t\in{\cal T}}{\cal C}(t,F)$. $\diamond$

In our example the tuple $(X_{1},f_{1},f_{2},1,-1)$ is an elements of the
critical set ${\cal C}(X_{1},F)$. We can characterize standard bases using
these special sets.

###### Theorem 2.3.6

Let $F$ be a set of polynomials in
${\mathbb{K}}[X_{1},\ldots,X_{n}]\backslash\\{0\\}$. Then $F$ is a standard
basis of ${\sf ideal}(F)$ if and only if for every tuple
$(t,f_{1},\ldots,f_{k},m_{1},\ldots,m_{k})$ in ${\cal C}(F)$ as specified in
Definition 2.3.5 the polynomial $\sum_{i=1}^{k}f_{i}\star m_{i}$ has a
standard representation with respect to $F$.

Proof :
In case $F$ is a standard basis since these polynomials are all elements of
${\sf ideal}(F)$ they must have standard representations with respect to $F$.
To prove the converse, it remains to show that every element in ${\sf
ideal}(F)$ has a standard representation with respect to $F$. Hence, let
$g=\sum_{j=1}^{m}f_{j}\star m_{j}$ be an arbitrary representation of a non-
zero polynomial $g\in{\sf ideal}(F)$ such that $f_{j}\in F$, and
$m_{j}=\alpha_{j}\cdot t_{j}$ with $\alpha_{j}\in{\mathbb{K}}$, $t_{j}\in{\cal
T}$. Depending on this representation of $g$ and the well-founded total
ordering $\succeq$ on ${\cal T}$ we define $t=\max_{\succeq}\\{{\sf
HT}(f_{j}\star t_{j})\mid 1\leq j\leq m\\}$ and $K$ as the number of
polynomials $f_{j}\star t_{j}$ with head term $t$. Then $t\succeq{\sf HT}(g)$
and in case ${\sf HT}(g)=t$ this immediately implies that this representation
is already a standard representation. Else we proceed by induction on the term
$t$. Without loss of generality let $f_{1},\ldots,f_{K}$ be the polynomials in
the corresponding representation such that $t={\sf HT}(f_{i}\star t_{i})$,
$1\leq i\leq K$. Then the tuple $(t,f_{1},\ldots,f_{K},m_{1},\ldots,m_{K})$ is
in ${\cal C}(F)$ and let $h=\sum_{i=1}^{K}f_{i}\star m_{i}$. We will now
change our representation of $g$ in such a way that for the new representation
of $g$ we have a smaller maximal term. Let us assume $h$ is not $0$555In case
$h=0$, just substitute the empty sum for the representation of $h$ in the
equations below.. By our assumption, $h$ has a standard representation with
respect to $F$, say $\sum_{j=1}^{n}h_{j}\star n_{j}$, where $h_{j}\in F$, and
$n_{j}=\beta_{j}\cdot s_{j}$ with $\beta_{j}\in{\mathbb{K}}$, $s_{j}\in{\cal
T}$ and all terms occurring in the sum are bounded by $t\succ{\sf HT}(h)$ as
$\sum_{i=1}^{K}{\sf HM}(f_{i}\star m_{i})=0$. This gives us:

$\displaystyle g$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{K}f_{i}\star
m_{i}+\sum_{i=K+1}^{m}f_{i}\star m_{i}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}h_{j}\star n_{j}+\sum_{i=K+1}^{m}f_{i}\star m_{i}$

which is a representation of $g$ where the maximal term is smaller than $t$.
q.e.d.

In fact for the case of polynomial rings over fields one can show that it is
sufficient to consider critical sets for subsets of $F$ of size 2 and we can
restrict the terms to the least common multiples of the head terms of the
respective two polynomials. These sets then correspond to the concept of
s-polynomials used to characterize Gröbner bases which will be introduced
later on.

Reviewing our example on page 2.3.4 we find that the set
$F=\\{X_{1}+X_{2},X_{1}+X_{3}\\}$ is no standard basis as the polynomial
$g=X_{2}-X_{3}$ has no standard representation although it is an elements of
${\sf ideal}(F)$. However the set $F\cup\\{g\\}$ then is a standard basis of
${\sf ideal}(F)$.

In the literature standard representations in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ are closely related to reduction relations
based on the divisibility of terms and standard bases are in fact Gröbner
bases. Here we want to introduce Gröbner bases in terms of rewriting. Hence we
continue by introducing the concept of reduction to
${\mathbb{K}}[X_{1},\ldots,X_{n}]$.

We can split a non-zero polynomial $p$ into a rule ${\sf
HM}(p)\longrightarrow-{\sf RED}(p)$ and we have ${\sf HM}(p)>-{\sf RED}(p)$.
Therefore, a set of polynomials gives us a binary relation $\longrightarrow$
on ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ which induces a one-step reduction
relation as follows.

###### Definition 2.3.7

Let $p,f$ be two polynomials in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$. We say $f$
reduces $p$ to $q$ at a monomial $m=\alpha\cdot t$ of $p$ in one step, denoted
by $p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{f}\,$}q$, if

  1. (a)

${\sf HT}(f)\circ u=t$ for some $u\in{\cal T}$, i.e., ${\sf HT}(f)$ divides
$t$, and

  2. (b)

$q=p-\alpha\cdot{\sf HC}(f)^{-1}\cdot f\ast u$.

We write
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{f}\,$}$ if there is a polynomial $q$ as defined above and $p$ is then
called reducible by $f$. Further, we can define
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}\,$},\mbox{$\,\stackrel{{\scriptstyle+}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}\,$}$, and $\,\stackrel{{\scriptstyle
n}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm b}}\,$ as usual. Reduction by a set
$F\subseteq{\mathbb{K}}[X_{1},\ldots,X_{n}]$ is denoted by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}q$ and abbreviates
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{f}\,$}q$ for some $f\in F$, which is also written as
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{f\in F}\,$}q$. $\diamond$

Note that if $f$ reduces $p$ to $q$ at a monomial $m=\alpha\cdot t$ then $t$
is no longer among the terms of $q$. We call a set of polynomials
$F\subseteq{\mathbb{K}}[X_{1},\ldots,X_{n}]$ interreduced, if no $f\in F$ is
reducible by a polynomial in $F\backslash\\{f\\}$.

In the classical case of polynomial rings over fields the existence of a
standard representation for a polynomial immediately implies reducibility of
the head monomial of the polynomial by any reduction relation based on
divisibility of terms, hence by the reduction relation defined here. This is
due to the fact that if a polynomial $g$ has a standard representation in
terms of a set of polynomials $F$ for at least one polynomial $f$ in $F$ and
some term $t$ in ${\cal T}$ we have ${\sf HT}(g)={\sf HT}(f\star t)={\sf
HT}(f)\circ t$ and hence $g$ is reducible at the monomial ${\sf HM}(g)$ by
$f$. Notice that this is no longer true for polynomial rings over the
integers. Let $F=\\{3\cdot X^{2}+X,2\cdot X^{2}+X\\}$ be a subset of
${\mathbb{Z}}[X]$. Then the polynomial $g=(3\cdot X^{2}+X)-(2\cdot
X^{2}+X)=X^{2}$ has a standard representation in terms of $F$ but neither
$3\cdot X^{2}$ nor $2\cdot X^{2}$ are divisors of the monomial $X^{2}$ as
neither $3$ nor $2$ devide $1$ in ${\mathbb{Z}}$.

Notice that we have $\longrightarrow\;\subseteq\;\;>$ and indeed one can show
that our reduction relation on ${\mathbb{K}}[X_{1},\ldots,X_{n}]$ is
Noetherian. Therefore, we can restrict ourselves to ensuring local confluence
when describing a completion procedure to compute Gröbner bases later on. But
first we have to provide a definition of Gröbner bases in the context of
rewriting.

###### Definition 2.3.8

A set $G\subseteq{\mathbb{K}}[X_{1},\ldots,X_{n}]$ is said to be a Gröbner
basis of the ideal it generates, if

  1. 1.

$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{G}\,$}=\;\;\equiv_{{\sf ideal}(G)}$, and

  2. 2.

$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm b}}_{G}\,$
is confluent. $\diamond$

The first statement expresses that the reduction relation describes the ideal
congruence. It holds for any basis of an ideal in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ and is hence normally omitted in the
definitions provided in the literature. However, when generalizing the concept
of Gröbner bases to other structures it is no longer guaranteed and hence we
have included it in our definition. The second statement ensures the existence
of unique normal forms. If we additionally require a Gröbner basis to be
interreduced, such a basis is unique in case we assume that the polynomials
are monic, i.e., their head coefficients are $1$. The following lemma gives
some properties of the reduction relation, which are essential in giving a
constructive description of a Gröbner basis not only in the setting of
commutative polynomial rings over fields.

###### Lemma 2.3.9

Let $F$ be a set of polynomials and $p,q,h$ some polynomials in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$. Then the following statements hold:

  1. 1.

Let
$p-q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h$. Then there are polynomials
$p^{\prime},q^{\prime}\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}p^{\prime}$,
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}q^{\prime}$ and $h=p^{\prime}-q^{\prime}$.

  2. 2.

Let $0$ be a normal form of $p-q$ with respect to $F$. Then there exists a
polynomial $g\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ such that
$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}g$ and
$q\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}g$.

  3. 3.

$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}q\mbox{ if and only if }p-q\in{\sf ideal}(F)$.

  4. 4.

$p\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ implies $\alpha\cdot p\ast
u\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ for all $\alpha\in{\mathbb{K}}$ and $u\in{\cal T}$.

  5. 5.

$\alpha\cdot p\ast
u\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{p}\,$}0$ for all $\alpha\in{\mathbb{K}}^{*}$ and $u\in{\cal T}$.

The second statement of this lemma is often called the Translation Lemma in
the literature. Statement 3 shows that Buchberger’s reduction relation always
captures the ideal congruence. Statement 4 is connected to the important fact
that reduction steps are preserved under multiplication with monomials.

The set $F=\\{X_{1}+X_{2},X_{1}+X_{3}\\}$ of polynomials in
${\mathbb{Q}}[X_{1},X_{2},X_{3}]$ from page 2.3.4 is an example of an ideal
basis which is not complete, i.e. the reduction relation is not
complete666Note that we call a set of polynomials complete (confluent, etc.)
if the reduction relation induced by these polynomials used as rules is
complete (confluent, etc.).. This follows as the polynomial $X_{1}$ can be
reduced by $\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$ to $-X_{2}$ as well as to $-X_{3}$ and the latter two polynomials
cannot be joined using
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm b}}_{F}\,$.

Of course we cannot expect an arbitrary ideal basis to be complete. But
Buchberger was able to show that in order to “complete” a given basis one only
has to add finitely many special polynomials which arise from critical
situations as described in the context of reduction systems in the previous
section and Definition 2.3.5.

The term $X_{1}$ in our example describes such a critical situation which is
in fact the only one relevant for completing the set $F$.

###### Definition 2.3.10

The s-polynomial for two non-zero polynomials
$p,q\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ is defined as

${\sf spol}(p,q)={\sf HC}(p)^{-1}\cdot p\ast u-{\sf HC}(q)^{-1}\cdot q\ast v,$

where ${\sf LCM}({\sf HT}(p),{\sf HT}(q))={\sf HT}(p)\circ u={\sf HT}(q)\circ
v$ for some $u,v\in{\cal T}$. $\diamond$

An s-polynomial will be called non-trivial in case it is not zero and notice
that for non-trivial s-polynomials we always have ${\sf HT}({\sf
spol}(p,q))\prec{\sf LCM}({\sf HT}(p),{\sf HT}(q))$. The s-polynomial for $p$
and $q$ belongs to the set of critical situations ${\cal C}({\sf LCM}({\sf
HT}(p),{\sf HT}(q)),\\{p,q\\})$.

In our example we find ${\sf
spol}(X_{1}+X_{2},X_{1}+X_{3})=X_{1}+X_{2}-(X_{1}+X_{3})=X_{2}-X_{3}$.

Why are s-polynomials related to testing for local confluence? To answer this
question we have to look at critical situations related to the reduction
relation as defined in Definition 2.3.7. Given two polynomials
$p,q\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ the smallest situation where both of
them can be applied as rules is the least common multiple of their head terms.
Let ${\sf LCM}({\sf HT}(p),{\sf HT}(q))={\sf HT}(p)\circ u={\sf HT}(q)\circ
v=t$ for some $u,v\in{\cal T}$. This gives us the following situation:

Then we get $p^{\prime}-q^{\prime}=t-{\sf HC}(q)^{-1}\cdot q\ast v-(t-{\sf
HC}(p)^{-1}\cdot p\ast u)={\sf HC}(p)^{-1}\cdot p\ast u-{\sf HC}(q)^{-1}\cdot
q\ast v={\sf spol}(p,q)$, i.e., the s-polynomial is derived from the two one-
step successors by subtraction. Now by Lemma 2.3.9 we know that ${\sf
spol}(p,q)\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ implies the existence of a common normal form for the
polynomials $p^{\prime}$ and $q^{\prime}$. Since the reduction relation based
on Definition 2.3.7 is terminating, the confluence test can hence be reduced
to checking whether all s-polynomials reduce to zero. The following theorem
now gives a constructive characterization of Gröbner bases based on these
ideas.

###### Theorem 2.3.11

For a set of polynomials $F$ in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$, the
following statements are equivalent:

  1. 1.

$F$ is a Gröbner basis.

  2. 2.

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

  3. 3.

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

Proof :
$1\Longrightarrow 2:$ Let $F$ be a Gröbner basis and $g\in{\sf ideal}(F)$.
Then $g$ is congruent to $0$ modulo the ideal generated by $F$, i.e.,
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$. Thus, as $0$ is irreducible and $G$ is confluent, we get
$g\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$.
$2\Longrightarrow 1:$ By Lemma 2.3.9 3 we know
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\longleftrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{G}\,$}=\;\;\equiv_{{\sf ideal}(G)}$. Hence it remains to show that
reduction with respect to $F$ is confluent. Since our reduction is terminating
it is sufficient to show local confluence. Thus, suppose there are three
different polynomials $g,h_{1},h_{2}$ such that
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h_{1}$ and
$g\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h_{2}$. Then we know $h_{1}\equiv_{{\sf ideal}(F)}g\equiv_{{\sf
ideal}(F)}h_{2}$ and hence $h_{1}-h_{2}\in{\sf ideal}(F)$. Now by lemma 2.3.9
(the translation lemma),
$h_{1}-h_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ implies the existence of a polynomial
$h\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ such that
$h_{1}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h$ and
$h_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h$. Hence, $h_{1}$ and $h_{2}$ are joinable.
$2\Longrightarrow 3:$ By definition 2.3.10 the s-polynomial for two non-zero
polynomials $f_{k},f_{l}\in{\mathbb{K}}[X_{1},\ldots,X_{n}]$ is defined as

${\sf spol}(f_{k},f_{l})={\sf HC}(f_{k})^{-1}\cdot f_{k}\ast u-{\sf
HC}(f_{l})^{-1}\cdot f_{l}\ast v,$

where ${\sf LCM}({\sf HT}(p),{\sf HT}(q))={\sf HT}(p)\circ u={\sf HT}(q)\circ
v$ and, hence, ${\sf spol}(f_{k},f_{l})\in{\sf ideal}(F)$. Therefore, ${\sf
spol}(f_{k},f_{l})\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ follows immediately.
$3\Longrightarrow 2:$ We have to show that every $g\in{\sf
ideal}(F)\backslash\\{0\\}$ is
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$-reducible to zero. Remember that for $h\in{\sf ideal}(F)$,
$h\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}h^{\prime}$ implies $h^{\prime}\in{\sf ideal}(F)$. As
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm b}}_{F}\,$
is Noetherian, thus it suffices to show that every $g\in{\sf
ideal}(F)\backslash\\{0\\}$ is
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$-reducible. Let $g=\sum_{j=1}^{m}\alpha_{j}\cdot f_{j}\ast w_{j}$ be
an arbitrary representation of $g$ with $\alpha_{j}\in{\mathbb{K}}^{*}$,
$f_{j}\in F$, and $w_{j}\in{\cal T}$. Depending on this representation of $g$
and a total well-founded admissible ordering $\succeq$ on ${\cal T}$ we define
$t=\max\\{{\sf HT}(f_{j})\circ w_{j}\mid j\in\\{1,\ldots,m\\}\\}$ and $K$ is
the number of polynomials $f_{j}\ast w_{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 $\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$-reducible. Thus we will prove that $g$ has a representation where
every occurring term is less or equal to ${\sf HT}(g)$, i.e., there exists a
representation such that $t={\sf HT}(g)$777Such representations are often
called standard representations in the literature (compare [BW92]).. This will
be done by induction on $(t,K)$, where $(t^{\prime},K^{\prime})<(t,K)$ if and
only if $t^{\prime}\prec t$ or $(t^{\prime}=t$ and $K^{\prime}<K)$888Note that
this ordering is well-founded since $\succ$ is well-founded on ${\cal T}$ and
$K\in{\mathbb{N}}$.. In case $t\succ{\sf HT}(g)$ there are two polynomials
$f_{k},f_{l}$ in the corresponding representation999Not necessarily $f_{l}\neq
f_{k}$. such that ${\sf HT}(f_{k})\circ w_{k}={\sf HT}(f_{l})\circ w_{l}=t$.
By definition 2.3.10 we have an s-polynomial ${\sf spol}(f_{k},f_{l})={\sf
HC}(f_{k})^{-1}\cdot f_{k}\ast z_{k}-{\sf HC}(f_{l})^{-1}\cdot f_{l}\ast
z_{l}$ such that ${\sf HT}(f_{k})\circ z_{k}={\sf HT}(f_{l})\circ z_{l}={\sf
LCM}({\sf HT}(f_{k}),{\sf HT}(f_{l}))$. Since ${\sf HT}(f_{k})\circ w_{k}={\sf
HT}(f_{l})\circ w_{l}$ there exists an element $z\in{\cal T}$ such that
$w_{k}=z_{k}\circ z$ and $w_{l}=z_{l}\circ z$. We will now change our
representation of $g$ by using the additional information on this s-polynomial
in such a way that for the new representation of $g$ we either have a smaller
maximal term or the occurrences of the term $t$ are decreased by at least 1.
Let us assume that ${\sf spol}(f_{k},f_{l})$ is not trivial101010In case ${\sf
spol}(f_{k},f_{l})=0$, just substitute $0$ for the sum
$\sum_{i=1}^{n}\delta_{i}\cdot h_{i}\ast v_{i}$ in the equations below.. Then
the reduction sequence ${\sf
spol}(f_{k},f_{l})\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ results in a representation of the form ${\sf
spol}(f_{k},f_{l})=\sum_{i=1}^{n}\delta_{i}\cdot h_{i}\ast v_{i}$, where
$\delta_{i}\in{\mathbb{K}}^{*},h_{i}\in F,v_{i}\in{\cal T}$. As the $h_{i}$
are due to the reduction of the s-polynomial, all terms occurring in the sum
are bounded by the term ${\sf HT}({\sf spol}(f_{k},f_{l}))$. Moreover, since
$\succeq$ is admissible on ${\cal T}$ this implies that all terms of the sum
$\sum_{i=1}^{n}\delta_{i}\cdot h_{i}\ast v_{i}\ast z$ are bounded by ${\sf
HT}({\sf spol}(f_{k},f_{l}))\circ z\prec t$, i.e., they are strictly bounded
by $t$111111This can also be concluded by statement four of lemma 2.3.9 since
${\sf
spol}(f_{k},f_{l})\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ implies ${\sf spol}(f_{k},f_{l})\ast
z\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{F}\,$}0$ and ${\sf HT}({\sf spol}(f_{k},f_{l})\ast z)\prec t$.. We can
now do the following transformations:

$\displaystyle\alpha_{k}\cdot f_{k}\ast w_{k}+\alpha_{l}\cdot f_{l}\ast w_{l}$
(2.2) $\displaystyle=$ $\displaystyle\alpha_{k}\cdot f_{k}\ast
w_{k}+\underbrace{\alpha^{\prime}_{l}\cdot\beta_{k}\cdot f_{k}\ast
w_{k}-\alpha^{\prime}_{l}\cdot\beta_{k}\cdot f_{k}\ast
w_{k}}_{=\,0}+\alpha^{\prime}_{l}\cdot\beta_{l}\cdot f_{l}\ast w_{l}$
$\displaystyle=$
$\displaystyle(\alpha_{k}+\alpha^{\prime}_{l}\cdot\beta_{k})\cdot f_{k}\ast
w_{k}-\alpha^{\prime}_{l}\cdot\underbrace{(\beta_{k}\cdot f_{k}\ast
w_{k}-\beta_{l}\cdot f_{l}\ast w_{l})}_{=\,{\sf spol}(f_{k},f_{l})\ast z}$
$\displaystyle=$
$\displaystyle(\alpha_{k}+\alpha^{\prime}_{l}\cdot\beta_{k})\cdot f_{k}\ast
w_{k}-\alpha^{\prime}_{l}\cdot(\sum_{i=1}^{n}\delta_{i}\cdot
h_{i}\ast(v_{i}\circ z))$

where, $\beta_{k}={\sf HC}(f_{k})^{-1}$, $\beta_{l}={\sf HC}(f_{l})^{-1}$, and
$\alpha^{\prime}_{l}\cdot\beta_{l}=\alpha_{l}$. By substituting (2.2) in our
representation of $g$ either $t$ disappears or $K$ is decreased.
q.e.d.

The second item of this theorem immediately implies the correctness of the
algebraic definition of Gröbner bases, which is equivalent to Definition
2.3.8.

###### Definition 2.3.12

A set $G$ of polynomials in
${\mathbb{K}}[X_{1},\ldots,X_{n}]\backslash\\{0\\}$ is said to be a Gröbner
basis, if ${\sf HT}({\sf ideal}(G))=\\{{\sf HT}(g)\ast t\mid g\in G,t\in{\cal
T}\\}$. $\diamond$

###### Remark 2.3.13

A closer inspection of the proof of $3\Longrightarrow 2$ given above reveals a
concept which is essential in the proofs of similar theorems for specific
function rings in the following chapters. The heart of this proof consists in
transforming an arbitrary representation of an element $g$ belonging to the
ideal generated by the set $F$ in such a way that we can deduce a top
reduction sequence for $g$ to zero, i.e., a reduction sequence where the
reductions only take place at the respective head term. Such a representation
of $g$ then is a standard representation and Gröbner bases are standard bases.
$\diamond$

As a consequence of Theorem 2.3.11 it is decidable whether a finite set of
polynomials is a Gröbner basis. Moreover, this theorem gives rise to the
following completion procedure for sets of polynomials.

Procedure: Buchberger’s Algorithm

Given: | A finite set of polynomials $F\subseteq{\mathbb{K}}[X_{1},\ldots,X_{n}]$.
---|---
Find: |  $\mbox{\sc Gb}(F)$, a Gröbner basis of $F$.

$G$ := $F$;
---
$B$ := $\\{(q_{1},q_{2})\mid q_{1},q_{2}\in G,q_{1}\neq q_{2}\\}$;
while $B\neq\emptyset$ do
|  $(q_{1},q_{2}):={\rm remove}(B)$;
| % Remove an element from the set $B$
|  $h:={\rm normalform}({\sf
spol}(q_{1},q_{2}),\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
b}}_{G}\,$})$
|  % Compute a normal form of ${\sf spol}(q_{1},q_{2})$ with respect to
$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm b}}_{G}\,$
|  if | $h\neq 0$
|  |  then |  $B:=B\cup\\{(f,h)\mid f\in G\\}$;
|  |  |  $G:=G\cup\\{h\\}$;
| endif
endwhile
$\mbox{\sc Gb}(F):=G$

Applying this procedure to our example $F=\\{X_{1}+X_{2},X_{1}+X_{3}\\}$ from
page 2.3.4 gives us $h=X_{2}-X_{3}$ and $G=F\cup\\{h\\}$ is a Gröbner basis as
all other critical situations are resolvable.

Termination of the procedure can be shown by using a slightly different
characterization of Gröbner bases (see Section 1.2): A subset $G$ of ${\sf
ideal}^{{\mathbb{K}}[X_{1},\ldots,X_{n}]}(F)$ is a Gröbner basis of ${\sf
ideal}^{{\mathbb{K}}[X_{1},\ldots,X_{n}]}(F)$ if and only if ${\sf HT}({\sf
ideal}^{{\mathbb{K}}[X_{1},\ldots,X_{n}]}(F)\backslash\\{0\\})={\sf
ideal}^{\cal T}({\sf HT}(G))$, i.e., the set of the head terms of the
polynomials in the ideal generated by $F$ in
${\mathbb{K}}[X_{1},\ldots,X_{n}]$ coincides with the ideal (in ${\cal T}$)
generated by the head terms of the polynomials in $G$. Reviewing the
procedure, we find that every polynomial added in the while loop has the
property that its head term cannot be divided by the head terms of the
polynomials already in $G$. By Dickson’s Lemma or Hilbert’s Basis Theorem, the
head terms of the polynomials in $G$ will at some step form a basis for the
set of head terms of the polynomials of the ideal generated by $F$ which
itself is the ideal in ${\cal T}$ generated by the head terms of the
polynomials in $G$. From this time on for every new polynomial $h$ computed by
the algorithm the head term ${\sf HT}(h)$ must lie in this ideal. Therefore,
its head term must be divisible by at least one of the head terms of the
polynomials in $G$, i.e., ${\sf HT}(h)$ and hence $h$ cannot be in normal form
with respect to $G$ unless it is zero.

##  Chapter 3 Reduction Rings

In this chapter we proceed to distinguish sufficient conditions, which allow
to define a reduction relation for a ring in such a way that every finitely
generated ideal in the ring has a finite Gröbner basis with respect to that
reduction relation. Such rings will be called reduction rings. Often
additional conditions can be given to ensure effectivity for the ring
operations, the reduction relation and the computation of the Gröbner bases –
the ring is then called an effective reduction ring. Naturally the question
arises, when and how the property of being a reduction ring is preserved under
various ring constructions. This can be studied from an existential as well as
from a constructive point of view. One main goal of studying abstract
reduction rings is to provide universal methods for constructing new reduction
rings without having to generalize the whole setting individually for each new
structure: e.g. knowing that the integers ${\mathbb{Z}}$ are a reduction ring
and that the property lifts to polynomials in one variable, we find that
${\mathbb{Z}}[X]$ is again a reduction ring and we can immediately conclude
that also ${\mathbb{Z}}[X_{1},\ldots,X_{n}]$ is a reduction ring. Similarly,
as sums of reduction rings are again reduction rings, we can directly conclude
that ${\mathbb{Z}}^{k}[X_{1},\ldots,X_{n}]$ or even
$({\mathbb{Z}}[Y_{1},\ldots,Y_{m}])^{k}[X_{1},\ldots,X_{n}]$ are reduction
rings. Moreover, since ${\mathbb{Z}}$ is an effective reduction ring it can be
shown that these new reduction rings again are effective. Commutative
effective reduction rings have been studied by Buchberger, Madlener, and
Stifter in [Buc83, Mad86, Sti87].

On the other hand, many rings of interest are non-commutative, e.g. rings of
matrices, the ring of quaternions, Bezout rings and various monoid rings, and
since in many cases they can be regarded as reduction rings, they are again
candidates for applying ring constructions. More interesting examples of non-
commutative reduction rings have been studied by Pesch in [Pes97].

A general framework for reduction rings and ring constructions including the
non-commutative case was presented at the Linz conference “33 years of Gröbner
Bases” in [MR98b]. Here we extend this framework by giving more details and
insight. Additionally, we add a section on modules over reduction rings, as
this concept arises naturally as a generalization of ideals in rings.

Of course there are also rings of interest, which can be enriched by a
reduction relation, but will not allow finite Gröbner bases for all ideals.
Monoid and group rings provide such a setting. For such structures still many
of the properties studied here are of interest and can be shown in weaker
forms, e.g. provided a monoid ring with a reduction relation we can define a
reduction relation for the polynomial ring with one variable over the monoid
ring.

The chapter is organized as follows: In Section 3.1 we introduce axioms for
specifying reduction relations in rings and give two concepts involving
special forms of ideal bases – weak reduction rings and reduction rings. In
Section 3.2 – 3.5 we study quotients, sums, modules, and polynomial rings of
these structures.

###  3.1 Reduction Rings

Let ${\sf R}$ be a ring with unit $1$ and a (not necessarily effective)
reduction relation $\Longrightarrow_{B}\subseteq{\sf R}\times{\sf R}$
associated with subsets $B\subseteq{\sf R}$ satisfying the following axioms:

  1. (A1)

$\Longrightarrow_{B}\;=\;\bigcup_{\beta\in B}\Longrightarrow_{\beta}$,
$\Longrightarrow_{B}$ is terminating for all finite subsets $B\subseteq{\sf
R}$.

  2. (A2)

$\alpha\Longrightarrow_{\beta}\gamma$ implies $\alpha-\gamma\in{\sf
ideal}^{{\sf R}}(\beta)$.

  3. (A3)

$\alpha\Longrightarrow_{\alpha}0$ for all $\alpha\in{\sf R}\backslash\\{0\\}$.

Part one of Axiom (A1) states how a reduction relation using sets is defined
in terms of a reduction relation using elements of ${\sf R}$ and is hence
applicable to arbitrary sets $B\subseteq{\sf R}$. However, Axiom (A1) does not
imply termination of reduction with respect to arbitrary sets: Just assume for
example the ring ${\sf R}={\mathbb{Q}}[\\{X_{i}\mid i\in{\mathbb{N}}\\}]$,
i.e., the polynomial ring with infinitely many indeterminates, and the
reduction relation based on divisibility of head terms with respect to the
length-lexicographical ordering induced by $X_{1}\succ X_{2}\succ\ldots$. Then
although reduction when using a finite set of polynomials is terminating, this
is no longer true for infinite sets. For example the infinite set
$\\{X_{i}-X_{i+1}\mid i\in{\mathbb{N}}\\}$ gives rise to an infinite reduction
sequence
$X_{1}\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{X_{1}-X_{2}}\,$}X_{2}\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{X_{2}-X_{3}}\,$}X_{3}\ldots$.
This phenomenon of course has many consequences. Readers familiar with Gröbner
bases in polynomial rings know that when proving that a set of polynomials is
a Gröbner basis if and only if all ideal elements reduce to zero using the
set, this is shown by proving that every ideal element is reducible by some
element in the set (compare Theorem 2.3.11). Unfortunately, this only implies
reducibility to zero in case the reduction relation is terminating. Without
this property other methods have to be applied.

In order to ensure termination for arbitrary subsets of ${\sf R}$ it is
possible to give a more restricted form of Axiom (A1):

  1. (A1’)

$\Longrightarrow_{B}\;=\;\bigcup_{\beta\in B}\Longrightarrow_{\beta}$,
$\Longrightarrow_{B}$ is terminating for all subsets $B\subseteq{\sf R}$.

Then of course reduction sequences are always terminating and many additional
restrictions, which we have to add later, are no longer necessary. Still we
prefer the more general formulation of the axiom since it allows to state more
clearly why and where termination is needed and how it can be achieved.

Axiom (A2) states how reduction steps are related to the ideal congruence,
namely that one reduction step using an element $\beta\in{\sf R}$ is captured
by the congruence generated by ${\sf ideal}^{{\sf R}}(\beta)$. We will later
on see that this extends to the reflexive transitive symmetric closure
$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$ of
any reduction relation $\Longrightarrow_{B}$ for arbitrary sets
$B\subseteq{\sf R}$.

Notice that in case ${\sf R}$ is commutative (A2) implies
$\gamma=\alpha-\beta\cdot\rho$ for some $\rho$ in ${\sf R}$. In the non-
commutative case using a single element $\beta$ for reduction
$\alpha-\gamma\in{\sf ideal}^{{\sf R}}(\beta)$ only implies
$\gamma=\alpha-\sum_{i=1}^{k}\rho_{i1}\cdot\beta\cdot\rho_{i2}$ for some
$\rho_{i1},\rho_{i2}\in{\sf R}$, $1\leq i\leq k$, hence possibly involving
$\beta$ more than once with different multipliers. This provides a large range
of possibilities for defining reduction steps, e.g. by subtracting one or more
appropriate multiples of $\beta$ from $\alpha$. Notice further that on the
converse Axiom (A2) does not provide any information on how $\alpha$,
$\gamma\in{\sf R}$ with $\alpha-\gamma\in{\sf ideal}^{{\sf R}}(\beta)$ are
related with respect to the reduction relation
$\Longrightarrow_{\\{\beta\\}}$. As a consequence many properties of
specialized reduction relations as known from the literature, e.g. the useful
Translation Lemma, cannot be shown to hold in this general setting.

We can define one-sided (right or left) reduction relations in rings by
refining Axiom (A2) as follows:

  1. (A2r)

$\alpha\Longrightarrow_{\beta}\gamma$ implies $\alpha-\gamma\in{\sf
ideal}_{r}^{{\sf R}}(\beta)$, respectively

  2. (A2l)

$\alpha\Longrightarrow_{\beta}\gamma$ implies $\alpha-\gamma\in{\sf
ideal}_{l}^{{\sf R}}(\beta)$.

In these special cases again we always get $\gamma=\alpha-\beta\cdot\rho$
respectively $\gamma=\alpha-\rho\cdot\beta$ for some $\rho\in{\sf R}$.

Remember that Axiom (A2) while not specific on the exact form of the reduction
step ensures that reduction steps “stay” within the ideal congruence. Let us
now study the situation for a set $B\subseteq{\sf R}$ and let
$\equiv_{{\mathfrak{i}}}$ denote the congruence generated by the ideal
${\mathfrak{i}}={\sf ideal}(B)$, i.e., $\alpha\equiv_{{\mathfrak{i}}}\beta$ if
and only if $\alpha-\beta\in{\mathfrak{i}}$. Then (A1)111We only need the
first part of Axiom (A1), namely how $\Longrightarrow_{B}$ is defined, and
hence we do not have to restrict ourselves to finite sets. and (A2)
immediately imply
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\subseteq\;\;\equiv_{{\mathfrak{i}}}$.
Hence, in case the reduction relation is effective one method for deciding the
membership problem for a finitely generated ideal ${{\mathfrak{i}}}$ is to
transform a finite generating set $B$ into a finite set $B^{\prime}$ such that
$B^{\prime}$ still generates ${\mathfrak{i}}$ and
$\Longrightarrow_{B^{\prime}}$ is confluent on ${\mathfrak{i}}$. Notice that
$0$ has to be irreducible222$0$ cannot be reducible by itself since this would
contradict the termination property in (A1). Similarly,
$0\Longrightarrow_{\beta}0$ and $0\Longrightarrow_{\beta}\gamma$, both $\beta$
and $\gamma$ not equal $0$, give rise to infinite reduction sequences again
contradicting (A1). for all $\Longrightarrow_{\alpha}$, $\alpha\in{\sf R}$.
Therefore, $0$ has to be the normal form of the ideal elements. Hence the goal
is to achieve $\alpha\in{{\mathfrak{i}}}$ if and only if
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$.
In particular ${\mathfrak{i}}$ is one equivalence class of
$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$.
The different definitions of reduction relations for rings existing in
literature show that for deciding the membership problem of an ideal
${\mathfrak{i}}$ it is not necessary to enforce
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}=\;\equiv_{{\mathfrak{i}}}$.
For example the D-reduction notion given by Pan in [Pan85] does not have this
property but is still sufficient to decide
$\equiv_{{\mathfrak{i}}}$-equivalence of two elements because
$\alpha\equiv_{{\mathfrak{i}}}\beta$ if and only if
$\alpha-\beta\in{{\mathfrak{i}}}$. It may even happen that D-reduction is not
only confluent on ${{\mathfrak{i}}}$ but confluent everywhere and still
$\alpha\equiv_{{\mathfrak{i}}}\beta$ does not imply that the normal forms with
respect to D-reduction are the same. This phenomenon is illustrated in the
next example.

###### Example 3.1.1

Let us look at different ways of introducing reduction relations for the ring
of integers ${\mathbb{Z}}$. For $\alpha,\beta,\gamma\in{\mathbb{Z}}$ we
define:

  * •

$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{\beta}\,$}\gamma$
if and only if $\alpha=\kappa\cdot|\beta|+\gamma$ where $0\leq\gamma<|\beta|$
and $\kappa\in{\mathbb{Z}}$ (division with remainder),

  * •

$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}^{{\rm
D}}_{\beta}\,$}0$ if and only if $\alpha=\kappa\cdot\beta$, i.e. $\beta$ is a
proper divisor of $\alpha$ (D-reduction).

Then for example we have
$5\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{4}\,$}1$
but
$5\mbox{$\,\,\,\,{\not\\!\\!\\!\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}^{{\rm
D}}_{4}}\,$}$.
It is easy to show that both reduction relations satisfy (A1) – (A3).
Moreover, all elements in ${\mathbb{Z}}$ have unique normal forms. An element
belongs to ${\sf ideal}(4)$ if and only if it is reducible to zero using $4$.
For $\Longrightarrow$-reduction the normal forms are unique representatives of
the quotient ${\mathbb{Z}}/{\sf ideal}(4)$. This is no longer true for
$\Longrightarrow^{D}$-reduction, since e.g. $3\equiv_{{\sf ideal}(4)}7$ since
$7=3+4$, but both are $\Longrightarrow^{D}$-irreducible. On the other hand, as
$\Longrightarrow_{\alpha}^{D}$ is only applicable to multiples
$\kappa\cdot\alpha$ and then reduces them to zero, $\Longrightarrow_{4}^{D}$
is confluent everywhere on ${\mathbb{Z}}$. $\diamond$

Since confluence of a reduction relation on the ideal is already sufficient to
solve its membership problem, bases with this property called weak Gröbner
bases have been studied in the literature. We proceed here by defining such
weak Gröbner bases in our context.

###### Definition 3.1.2

A subset $B$ of ${\sf R}$ is called a weak Gröbner basis of the ideal
${\mathfrak{i}}={\sf ideal}(B)$ it generates, if
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
terminating and
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
for all $\alpha\in{\mathfrak{i}}$. $\diamond$

Notice that in Theorem 2.3.11 this property was one way of characterizing
Gröbner bases in ${\mathbb{K}}[X_{1},\ldots,X_{n}]$. We will later on see why
in polynomial rings the terms weak Gröbner basis and Gröbner basis coincide.

###### Definition 3.1.3

A ring $({\sf R},\Longrightarrow)$ satisfying (A1) – (A3) is called a weak
reduction ring if every finitely generated ideal in ${\sf R}$ has a finite
weak Gröbner basis. $\diamond$

As stated before such a weak Gröbner basis is sufficient to decide the ideal
membership problem in case the reduction relation is effective. However, if we
want unique normal forms for all elements in ${\sf R}$ such that each
congruence has one unique representative we need a stronger kind of ideal
basis.

###### Definition 3.1.4

A subset $B$ of ${\sf R}$ is called a Gröbner basis of the ideal
${\mathfrak{i}}={\sf ideal}(B)$ it generates, if
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}=\;\;\equiv_{{\mathfrak{i}}}$
and $\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
complete333Notice that in the literature definitions of Gröbner bases normally
only require that
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
“confluent”. This is due to the fact that in these cases
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
terminating. In our context, however for arbitrary sets $B\subseteq{\sf R}$ we
have seen that
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ need not
be Noetherian. Hence we have to incorporate this additional requirement into
our definition, which is done by demanding completeness. Hence here we have a
point where the weaker form (A1) demands more care in defining the term
“Gröbner basis”. In rings where the reduction relation using an arbitrary set
of elements is always Noetherian, the weaker demand for (local) confluence is
of course sufficient.. $\diamond$

Of course Gröbner bases are also weak Gröbner bases. This can be shown by
induction on $k$, where for $\alpha\in{\sf ideal}(B)$ we have
$\alpha\mbox{$\,\stackrel{{\scriptstyle
k}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}0$. In case $k=1$ we
immediately get that
$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
must hold as $0$ is irreducible. In case $k>1$ we find
$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta\mbox{$\,\stackrel{{\scriptstyle
k-1}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}0$ and by our induction
hypothesis
$\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
must hold. Now either
$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta$
and we are done or
$\beta\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\alpha$.
In the latter case the completeness of our reduction relation combined with
the irreducibility of zero then must yield
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
and we are done.

The converse is not true. To see this let us review the definition of
$\Longrightarrow^{D}$-reduction for ${\mathbb{Z}}$ as presented in Example
3.1.1. Then the set $\\{2\\}$ is a weak Gröbner basis of the ideal
$2\cdot{\mathbb{Z}}=\\{2\cdot\alpha\mid\alpha\in{\mathbb{Z}}\\}$ as for every
$\alpha\in(2\cdot{\mathbb{Z}})\backslash\\{0\\}$ we have
$\alpha\Longrightarrow_{\\{2\\}}^{D}0$. On the other hand elements in
${\mathbb{Z}}\backslash(2\cdot{\mathbb{Z}})$ are irreducible and hence $3$ and
$5$ are in normal form with respect to $\Longrightarrow_{\\{2\\}}^{D}$.
Therefore,
$3\mbox{$\,\,\,\,{\not\\!\\!\\!\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}^{{\rm
D}}_{\\{2\\}}}\,$}5$ although $5\equiv_{2\cdot{\mathbb{Z}}}3$ as $5=3+1\cdot
2$.

However, for many rings as e.g. polynomial rings over fields, weak Gröbner
bases are also Gröbner bases. This is due to the fact that many rings with
reduction relations studied in the literature fulfill a certain property for
the reduction relation called the Translation Lemma (compare Lemma 2.3.9 (2)).
Rephrased in our context the Translation Lemma states that for a set
$F\subseteq{\sf R}$ and for all $\alpha,\beta\in{\sf R}$,
$\alpha-\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{F}\,$}0$
implies the existence of $\gamma\in{\sf R}$ such that
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{F}\,$}\gamma$
and
$\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{F}\,$}\gamma$.
As mentioned before, the validity of this lemma for a reduction relation in a
ring has consequences on the relation between weak Gröbner bases and Gröbner
bases.

###### Theorem 3.1.5

Let ${\sf R}$ be a ring with a reduction relation $\Longrightarrow$ fulfilling
(A1) – (A3). If additionally the Translation Lemma holds for the reduction
relation $\Longrightarrow$ in ${\sf R}$, then weak Gröbner bases are also
Gröbner bases.

Proof :
Let ${\sf R}$ be a ring where the Translation Lemma holds for the reduction
relation $\Longrightarrow$. Further let $B$ be a weak Gröbner basis of the
ideal ${\mathfrak{i}}={\sf ideal}(B)$. In order to prove that $B$ is in fact a
Gröbner basis we have to show two properties:

  1. 1.

$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}=\;\;\equiv_{{\mathfrak{i}}}$:
The inclusion
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\subseteq\;\;\equiv_{{\mathfrak{i}}}$
follows by (A1) and (A2). To see the converse let
$\alpha\equiv_{{\mathfrak{i}}}\beta$. Then $\alpha-\beta\in{\mathfrak{i}}$,
and
$\alpha-\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$,
as $B$ is a weak Gröbner basis. But then the Translation Lemma yields that
$\alpha$ and $\beta$ are joinable by
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ and hence
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta$.

  2. 2.

$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
complete:
Since $\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ is
terminating it suffices to show local confluence. Let
$\alpha,\beta_{1},\beta_{2}\in{\sf R}$ such that
$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta_{1}$
and
$\alpha\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta_{2}$.
Then again $\beta_{1}-\beta_{2}\in{\mathfrak{i}}$, and
$\beta_{1}-\beta_{2}\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$,
since $B$ is a weak Gröbner basis. As before the Translation Lemma yields that
$\beta_{1}$ and $\beta_{2}$ are joinable by
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$ and we are
done.

q.e.d.

On the other hand, looking at proofs of variations of the Translation Lemma in
the literature we find that in order to show this property for a ring with a
reduction relation we need more information on the reduction step as is
provided by the very general form of Axiom (A2). Hence in this general setting
weak Gröbner bases and Gröbner bases have to be distinguished.

Rings where finitely generated ideals have finite Gröbner bases are of
particular interest.

###### Definition 3.1.6

A ring $({\sf R},\Longrightarrow)$ satisfying (A1) – (A3) is called a
reduction ring if every finitely generated ideal in ${\sf R}$ has a finite
Gröbner basis. $\diamond$

The connection between weak reduction rings and reduction rings follows from
Theorem 3.1.5.

###### Corollary 3.1.7

Let $({\sf R},\Longrightarrow)$ be a weak reduction ring. If additionally the
Translation Lemma holds, then $({\sf R},\Longrightarrow)$ is a reduction ring.

To simplify notations sometimes we will identify $({\sf R},\Longrightarrow)$
with ${\sf R}$ in case $\Longrightarrow$ is known or irrelevant. The notion of
one-sided weak reduction rings and one-sided reduction rings is
straightforward444An example for a one-sided weak reduction ring which is not
a one-sided reduction ring can be given using the two different reduction
relations $\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}\,$ and
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}^{{\rm D}}\,$ for
the integers provided in Example 3.1.1. Then the free monoid ring
${\mathbb{Z}}[\\{a,b\\}]$ with prefix reduction induced by
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}\,$ is a one-sided
reduction ring while for prefix reduction induced by
$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}^{{\rm D}}\,$ we
get a one-sided weak reduction ring..

Effective or computable weak reduction rings and effective or computable
reduction rings can be defined similar to Buchberger’s commutative reduction
rings (see [Buc83, Sti87]), in our case by demanding that the ring operations
are computable, the reduction relation is effective, and, additionally,
Gröbner bases can be computed. Procedures which compute Gröbner bases are
normally completion procedures based on effective tests for local confluence
to decide whether a finite set is a Gröbner basis and to enrich that set if
not. But of course other procedures are also possible, e.g. when using
division with remainders as reduction relation in ${\mathbb{Z}}$ the Euclidean
algorithm can be used for computing Gröbner bases of ideals.

Notice that Definition 3.1.6 does not imply that Noetherian rings satisfying
the Axioms (A1), (A2) and (A3) are indeed reduction rings. This is due to the
fact that while of course all ideals then have finite bases, the property of
being a Gröbner basis strongly depends on the reduction ring which is of
course itself strongly dependent on the reduction relation chosen for the
ring. Hence the existence of finite ideal bases does not imply the existence
of finite Gröbner bases as the following example shows: Given an arbitrary
Noetherian ring ${\sf R}$ we can associate a (very simple) reduction relation
to elements of ${\sf R}$ by defining for any $\alpha\in{\sf
R}\backslash\\{0\\}$, $\alpha\Longrightarrow_{\beta}$ if and only if
$\alpha=\beta$. Additionally we define $\alpha\Longrightarrow_{\alpha}0$. Then
the Axioms (A1), (A2) and (A3) are fulfilled but although every ideal in the
Noetherian ring ${\sf R}$ has a finite basis (in the sense of a generating
set), infinite ideals will not have finite Gröbner bases, as for any ideal
${\mathfrak{i}}\subseteq{\sf R}$ in this setting the set
${\mathfrak{i}}\backslash\\{0\\}$ is the only possible Gröbner basis.

Another interesting question concerns which changes to ideal bases preserve
the property of being a Gröbner basis. Extensions of (weak) Gröbner bases by
ideal elements are not critical555Extensions of (weak) Gröbner bases by
elements not belonging to the ideal make no sense in our context as then the
reduction relation no longer is a proper means for describing the original
ideal congruence..

###### Remark 3.1.8

If $B$ is a finite (weak) Gröbner basis of ${\mathfrak{i}}$ and
$\alpha\in{\mathfrak{i}}$, then $B^{\prime}=B\cup\\{\alpha\\}$ is again a
(weak) Gröbner basis of ${\mathfrak{i}}$: First of all we find
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\subseteq\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}\subseteq\;\;\equiv_{{\mathfrak{i}}}\;\;=\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}$.
Moreover, since $B^{\prime}$ is again a finite set,
$\Longrightarrow_{B^{\prime}}$ is terminating. Finally
$\Longrightarrow_{B^{\prime}}$ inherits its confluence from
$\Longrightarrow_{B}$ since $\beta\Longrightarrow_{\alpha}\gamma$ implies
$\beta\equiv_{{\mathfrak{i}}}\gamma$, and hence $\beta$ and $\gamma$ have the
same normal form with respect to $\Longrightarrow_{B}$. $\diamond$

Hence, if $B$ is a finite Gröbner basis of an ideal ${\mathfrak{i}}$ and
$\beta\in B$ is reducible by $B\backslash\\{\beta\\}$ to $\alpha$, then
$B\cup\\{\alpha\\}$ is again a Gröbner basis of ${\mathfrak{i}}$. The same is
true for weak Gröbner bases.

Removing elements from a set is critical as we might decrease the set of
elements which are reducible with respect to the set. Hence if the set is a
Gröbner basis, after removing elements the ideal elements might no longer
reduce to zero using the remaining set. Reviewing the example presented in
Section 1.3 we find that while the set
$\\{X_{,}^{2}+X_{2},X_{1}^{2}+X_{3},X_{2}-X_{3}\\}$ is a Gröbner basis in
${\mathbb{Q}}[X_{1},X_{2},X_{3}]$ the subset
$\\{X_{,}^{2}+X_{2},X_{1}^{2}+X_{3}\\}$, although it generates the same ideal,
is none. In order to remove $\beta$ from a Gröbner basis $B$ without losing
the Gröbner basis property it is important for the reduction relation
$\Longrightarrow$ to satisfy an additional axiom:

  1. (A4)

$\alpha\Longrightarrow_{\beta}$ and $\beta\Longrightarrow_{\gamma}\delta$
imply $\alpha\Longrightarrow_{\gamma}$ or $\alpha\Longrightarrow_{\delta}$.

It is not easy to give a simple example for a ring with a reduction relation
fulfilling (A1) – (A3) but not (A4) as the reduction rings we have introduced
so far all satisfy (A4)666An example using a right reduction relation in a
monoid ring can be found in Example 3.6 in [MR98d]: Let $\Sigma=\\{a,b,c\\}$
and $T=\\{a^{2}\longrightarrow 1,b^{2}\longrightarrow 1,c^{2}\longrightarrow
1\\}$ be a monoid presentation of ${\cal M}$ with a length-lexicographical
ordering induced by $a\succ b\succ c$. For $p,f\in{\mathbb{K}}[{\cal M}]$ a
(right) reduction relation is defined by
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
s}}_{f}\,$}q$ at a monomial $\alpha\cdot t$, if  (a) ${\sf HT}(f\ast w)=t$ for
some $w\in{\cal M}$, and (b) $q=p-\alpha\cdot{\sf HC}(f\ast w)^{-1}\cdot f\ast
w$. Looking at $p=ba+b,q=bc+1$ and $r=ac+b\in{\mathbb{Q}}[{\cal G}]$ we get
$p\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
s}}_{q}\,$}p-q\ast ca=-ca+b$ and
$q\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
s}}_{r}\,$}q-r\ast c=-a+1=q_{1}$, but
$p\mbox{$\,\,\,\,{\not\\!\\!\\!\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}^{{\rm
s}}_{\\{r,q_{1}\\}}}\,$}$. Trying to reduce $ba$ by $r$ or $q_{1}$ we get
$r\ast a=\underline{aca}+ba,r\ast caba=ba+\underline{bcaba}$ and $q_{1}\ast
aba=-ba+\underline{aba},q_{1}\ast ba=-\underline{aba}+ba$ all violating
condition (a). Trying to reduce $b$ we get the same problem as $r\ast
cab=b+\underline{bcab},q_{1}\ast ab=-b+\underline{a}$ and $q_{1}\ast
b=-\underline{ab}+b$..

###### Lemma 3.1.9

Let $({\sf R},\Longrightarrow)$ be a reduction ring satisfying (A4). Further
let $B\subseteq{\sf R}$ be a (finite) Gröbner basis of a finitely generated
ideal in ${\sf R}$ and $B^{\prime}\subseteq B$ such that for all $\beta\in B$,
$\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$
holds. Then $B^{\prime}$ is a Gröbner basis of ${\sf ideal}^{{\sf R}}(B)$. In
particular, for all $\alpha\in{\sf R}$,
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
implies
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$.

Proof :
In this proof let $\alpha\\!\\!\Downarrow_{B}$ denote a normal form of
$\alpha$ with respect to $\Longrightarrow_{B}$ and let ${\rm
IRR}\/(\Longrightarrow_{B})$ denote the $\Longrightarrow_{B}$-irreducible
elements in ${\sf R}$. Notice that by the Axioms (A1) and (A4) and our
assumptions on $B^{\prime}$, all elements reducible by $B$ are also reducible
by $B^{\prime}$: We show a more general claim by induction on $n$: If
$\alpha,\beta\in{\sf R}$ such that $\alpha\Longrightarrow_{\beta}$ and
$\beta\mbox{$\,\stackrel{{\scriptstyle
n}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$, then
$\alpha\Longrightarrow_{B^{\prime}}$. The base case $n=1$ is a direct
consequence of (A4), as $\alpha\Longrightarrow_{\beta}$ and
$\beta\mbox{$\,\stackrel{{\scriptstyle}}{{\Longrightarrow}}\\!\\!\mbox{}_{\beta^{\prime}\in
B^{\prime}}\,$}0$ immediately imply $\alpha\Longrightarrow_{\beta^{\prime}\in
B^{\prime}}$. In the induction step we find
$\beta\Longrightarrow_{\beta^{\prime}\in
B^{\prime}}\delta\mbox{$\,\stackrel{{\scriptstyle
n-1}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$ and either
$\alpha\Longrightarrow_{\beta^{\prime}\in B^{\prime}}$ or
$\alpha\Longrightarrow_{\delta}$ and our induction hypothesis yields
$\alpha\Longrightarrow_{B^{\prime}}$.
Hence we can conclude ${\rm IRR}\/(\Longrightarrow_{B^{\prime}})\subseteq{\rm
IRR}\/(\Longrightarrow_{B})$. We want to show that $B^{\prime}$ is a Gröbner
basis of ${\sf ideal}^{{\sf R}}(B)$: Assuming
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\alpha\\!\\!\Downarrow_{B}$
but
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}\alpha\\!\\!\Downarrow_{B^{\prime}}\neq\alpha\\!\\!\Downarrow_{B}$,
we find $\alpha\\!\\!\Downarrow_{B^{\prime}}\in{\sf ideal}^{{\sf R}}(B)$ and
$\alpha\\!\\!\Downarrow_{B^{\prime}}\in{\rm
IRR}\/(\Longrightarrow_{B^{\prime}})\subseteq{\rm
IRR}\/(\Longrightarrow_{B})$, contradicting the confluence of
$\Longrightarrow_{B}$. Hence,
$\alpha\\!\\!\Downarrow_{B^{\prime}}=\alpha\\!\\!\Downarrow_{B}$, implying
that $\Longrightarrow_{B^{\prime}}$ is also confluent, as
$\alpha\\!\\!\Downarrow_{B}$ is unique. Now it remains to show that
$\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\subseteq\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}$
holds. This follows immediately, as for
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B}\,$}\beta$
we have
$\alpha\\!\\!\Downarrow_{B^{\prime}}=\alpha\\!\\!\Downarrow_{B}=\beta\\!\\!\Downarrow_{B}=\beta\\!\\!\Downarrow_{B^{\prime}}$
which implies
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longleftrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}\beta$.
q.e.d.

This result carries over for weak Gröbner bases.

###### Corollary 3.1.10

Let $({\sf R},\Longrightarrow)$ be a weak reduction ring satisfying (A4).
Further let $B\subseteq{\sf R}$ be a (finite) weak Gröbner basis of a finitely
generated ideal in ${\sf R}$ and $B^{\prime}\subseteq B$ such that for all
$\beta\in B$,
$\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$
holds. Then $B^{\prime}$ is a weak Gröbner basis of ${\sf ideal}^{{\sf
R}}(B)$. In particular, for all $\alpha\in{\sf R}$,
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
implies
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$.

Proof :
As in the proof of Lemma 3.1.9 we can conclude ${\rm
IRR}\/(\Longrightarrow_{B^{\prime}})\subseteq{\rm
IRR}\/(\Longrightarrow_{B})$. Hence assuming that
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}0$
while
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}\alpha\\!\\!\Downarrow_{B^{\prime}}\neq
0$ would imply $\alpha\\!\\!\Downarrow_{B^{\prime}}\in{\rm
IRR}\/(\Longrightarrow_{B})$. As $B^{\prime}\subseteq B$ this would give us a
contradiction since then $\alpha\in{\sf ideal}^{{\sf R}}(B)$ would have two
different normal forms at least one of them not equal to zero with respect to
$B$ contradicting the fact that $B$ is supposed to be a weak Gröbner basis.
q.e.d.

Remark 3.1.8 and Lemma 3.1.9 are closely related to interreduction and reduced
(weak) Gröbner bases. We call a (weak) Gröbner basis $B\subseteq{\sf R}$
reduced if no element $\beta\in B$ is reducible by
$\Longrightarrow_{B\backslash\\{\beta\\}}$.

The results of this section carry over to rings with appropriate one-sided
reduction relations.

In the remaining sections of this chapter we study the question which ring
constructions preserve the property of being a (weak) reduction ring.

###  3.2 Quotients of Reduction Rings

Let ${\sf R}$ be a ring with a reduction relation $\Longrightarrow$ fulfilling
(A1) – (A3) and ${\mathfrak{i}}$ a finitely generated ideal in ${\sf R}$ with
a finite Gröbner basis $B$. Then every element $\alpha\in{\sf R}$ has a unique
normal form $\alpha\\!\\!\Downarrow_{B}$ with respect to
$\Longrightarrow_{B}$. We choose the set of $\Longrightarrow_{B}$-irreducible
elements of ${\sf R}$ as representatives for the elements in the quotient
${\sf R}/{\mathfrak{i}}$. Addition is defined by
$\alpha+\beta:=(\alpha+\beta)\\!\\!\Downarrow_{B}$ and multiplication by
$\alpha\cdot\beta:=(\alpha\cdot\beta)\\!\\!\Downarrow_{B}$. Then a natural
reduction relation can be defined on the quotient ${\sf R}/{\mathfrak{i}}$ as
follows:

###### Definition 3.2.1

Let $\alpha,\beta,\gamma\in{\sf R}/{\mathfrak{i}}$. We say $\beta$ reduces
$\alpha$ to $\gamma$ in one step, denoted by
$\alpha\longrightarrow_{\beta}\gamma$, if there exists $\gamma^{\prime}\in{\sf
R}$ such that $\alpha\Longrightarrow_{\beta}\gamma^{\prime}$ and
$(\gamma^{\prime})\\!\\!\Downarrow_{B}=\gamma$. $\diamond$

First we ensure that the Axioms (A1) – (A3) hold for the reduction relation in
${\sf R}/{\mathfrak{i}}$ based on Definition 3.2.1:
$\longrightarrow_{S}\;=\bigcup_{s\in S}\longrightarrow_{s}$ is terminating for
all finite $S\subseteq{\sf R}/{\mathfrak{i}}$ since otherwise
$\Longrightarrow_{B\cup S}$ would not be terminating in ${\sf R}$ although
$B\cup S$ is finite. Hence (A1) is satisfied. If
$\alpha\longrightarrow_{\beta}\gamma$ for some $\alpha,\beta,\gamma\in{\sf
R}/{\mathfrak{i}}$ we know
$\alpha\Longrightarrow_{\beta}\gamma^{\prime}\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\gamma$,
i.e., $\alpha-\gamma\in{\sf ideal}^{{\sf R}}(\\{\beta\\}\cup B)$, and hence
$\alpha-\gamma\in{\sf ideal}^{{\sf R}/{\mathfrak{i}}}(\beta)$. Therefore, (A2)
is also fulfilled. Finally Axiom (A3) holds since
$\alpha\Longrightarrow_{\alpha}0$ for all $\alpha\in{\sf R}\backslash\\{0\\}$
implies $\alpha\longrightarrow_{\alpha}0$.

Moreover, in case (A4) holds in ${\sf R}$ this is also true for ${\sf
R}/{\mathfrak{i}}$: For $\alpha,\beta,\gamma,\delta\in{\sf R}/{\mathfrak{i}}$
we have that $\alpha\longrightarrow_{\beta}$ and
$\beta\longrightarrow_{\gamma}\delta$ imply $\alpha\Longrightarrow_{\beta}$
and
$\beta\Longrightarrow_{\gamma}\delta^{\prime}\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\delta$
and since $\alpha$ is $\Longrightarrow_{B}$-irreducible777Remember that in the
proof of Lemma 3.1.9 we have shown that $\alpha\Longrightarrow_{\beta}$ and
$\beta\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B^{\prime}}\,$}0$
imply $\alpha\Longrightarrow_{B^{\prime}}$. This carries over to our situation
in the form that $\alpha\Longrightarrow_{\beta}$ and
$\beta\Longrightarrow_{\gamma}\delta^{\prime}\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{B}\,$}\delta$
implies $\alpha\Longrightarrow_{\\{\gamma,\delta^{\prime},\delta\\}\cup B}$
and using induction to $\alpha\Longrightarrow_{\\{\gamma,\delta\\}\cup B}$.
this implies $\alpha\Longrightarrow_{\\{\gamma,\delta\\}}$ and hence
$\alpha\longrightarrow_{\\{\gamma,\delta\\}}$.

###### Theorem 3.2.2

If $({\sf R},\Longrightarrow)$ is a reduction ring with (A4), then for every
finitely generated ideal ${\mathfrak{i}}$ the quotient $({\sf
R}/{\mathfrak{i}},\longrightarrow)$ again is a reduction ring with (A4).

Proof :
Since reduction in ${\sf R}/{\mathfrak{i}}$ as defined above inherits (A1) –
(A4) from ${\sf R}$, it remains to show that every finitely generated ideal
${\mathfrak{j}}\subseteq{\sf R}/{\mathfrak{i}}$ has a finite Gröbner basis.
Let ${\mathfrak{j}}_{{\sf R}}=\\{\alpha\in{\sf
R}\mid\alpha\\!\\!\Downarrow_{B}\in{\mathfrak{j}}\\}$ be an
ideal888${\mathfrak{j}}_{{\sf R}}$ is an ideal in ${\sf R}$ since  1.
$0\in{\mathfrak{j}}_{{\sf R}}$ as $0\in{\mathfrak{j}}$. 2.
$\alpha,\beta\in{\mathfrak{j}}_{{\sf R}}$ implies
$\alpha\\!\\!\Downarrow_{B},\beta\\!\\!\Downarrow_{B}\in{\mathfrak{j}}$, hence
$\alpha\\!\\!\Downarrow_{B}+\beta\\!\\!\Downarrow_{B}=(\alpha+\beta)\\!\\!\Downarrow_{B}\in{\mathfrak{j}}$
and $\alpha+\beta\in{\mathfrak{j}}_{{\sf R}}$. 3.
$\alpha\in{\mathfrak{j}}_{{\sf R}}$ and $\gamma\in{\sf R}$ implies
$\alpha\\!\\!\Downarrow_{B}\in{\mathfrak{j}}$ and
$\gamma\cdot\alpha\\!\\!\Downarrow_{B}=(\gamma\cdot\alpha)\\!\\!\Downarrow_{B}\in{\mathfrak{j}}$,
$\alpha\\!\\!\Downarrow_{B}\cdot\gamma=(\alpha\cdot\gamma)\\!\\!\Downarrow_{B}\in{\mathfrak{j}}$,
hence $\gamma\cdot\alpha,\alpha\cdot\gamma\in{\mathfrak{j}}_{{\sf R}}$. in
${\sf R}$ corresponding to ${\mathfrak{j}}$. Then ${\mathfrak{j}}_{{\sf R}}$
is finitely generated as an ideal in ${\sf R}$ by its finite basis in ${\sf
R}/{\mathfrak{i}}$ viewed as elements of ${\sf R}$ and the finite basis of
${\mathfrak{i}}$. Hence ${\mathfrak{j}}_{{\sf R}}$ has a finite Gröbner basis
in ${\sf R}$, say $G_{{\sf R}}$. Then
$G=\\{\alpha\\!\\!\Downarrow_{B}\mid\alpha\in G_{{\sf R}}\\}\backslash\\{0\\}$
is a finite Gröbner basis of ${\mathfrak{j}}$: If $\alpha\in{\mathfrak{j}}$ we
have
$\alpha\mbox{$\,\stackrel{{\scriptstyle*}}{{\longrightarrow}}\\!\\!\mbox{}_{G}\,$}0$
and ${\sf ideal}^{{\sf R}/{\mathfrak{i}}}(G)={\mathfrak{j}}$, as every element
which is reducible with an element $\beta\in G_{{\sf R}}$ is also reducible
with an element of $G\cup B$ because (A4) holds. Since $G\cup B$ is also a
Gröbner basis of ${\mathfrak{j}}_{{\sf R}}$ and
$\mbox{$\,\stackrel{{\scriptstyle}}{{\longrightarrow}}\\!\\!\mbox{}_{G}\,$}\subseteq\mbox{$\,\stackrel{{\scriptstyle*}}{{\Longrightarrow}}\\!\\!\mbox{}_{G\cup
B}\,$}$, when restricted to elements in ${\sf R}/{\mathfrak{i}}$ we have ${\rm