Revista Colombiana de Matemáticas Volumen 33 (1999), páginas 27–49

Non-commutative reduction rings

Klaus Madlener Birgit Reinert^{1} Universität Kaiserslautern, Germany

Abstract. Reduction relations are means to express congruences on rings. In the special case of congruences induced by ideals in commutative polynomial rings, the powerful tool of Gröbner bases can be characterized by properties of reduction relations associated with ideal bases. Hence, reduction rings can be seen as rings with reduction relations associated to subsets of the ring such that every finitely generated ideal has a finite Gröbner basis. This paper gives an axiomatic framework for studying reduction rings including non-commutative rings and explores when and how the property of being a reduction ring is preserved by standard ring constructions such as quotients and sums of reduction rings, as well as extensions to polynomial and monoid rings over reduction rings. Moreover, it is outlined when such reduction rings are effective.

Keywords and phrases. Reduction rings, Gröbner bases, non-commutative rings, standard ring constructions.

1991 Mathematics Subject Classification. Primary 68Q40. Secondary 12Y05,

68Q42, 13P10.

1. Introduction

Reasoning and computing in finitely presented algebraic structures is widespread in many fields of mathematics, physics and computer science. Many of the resulting problems can be formulated in terms of congruences on the respective structures. Reduction in the sense of simplification combined with appropriate completion methods is one general technique which is often successfully applied in this context, e.g. to solve the word problem and hence to compute effectively in the structure.

1This author was supported by the Deutsche Forschungsgemeinschaft (DFG).

One fundamental application of this technique to polynomial rings was provided by B. Buchberger [2] in his uniform effective solution of the ideal membership problem establishing the theory of Gröbner bases. Polynomials can be used as rules by giving an admissible^{2} ordering on the terms and using the largest monomial according to this ordering as a left hand side of a rule. “Reduction” as defined by Buchberger then can be compared to division of one polynomial by a set of finitely many polynomials. A Gröbner basis G is a set of polynomials such that every polynomial in the polynomial ring has a unique normal form with respect to reduction using the polynomials in G as rules (the polynomials in the ideal generated by G reduce to zero using G). Buchberger developed a terminating procedure to transform a finite generating set of a polynomial ideal into a finite Gröbner basis of the same ideal. Gröbner bases can be characterized in various other manners, e.g. by properties of their head monomials or by special representations for the ideal elements with respect to a Gröbner basis (called standard representations). Since Gröbner bases can be applied to solve many problems related to ideals and varieties in polynomial rings, generalizations to other structures followed (for an overview see e.g. Becker and Weispfenning [1] or Madlener and Reinert [10]). In this context, it is interesting to find sufficient conditions allowing 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 as to 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 ℤ form a reduction ring and that the property lifts to polynomials in one variable, we find that ℤ[X] is again a reduction ring and we can immediately conclude that also ℤ[X_{1}, …, X_{n}] is a reduction ring. Similarly, as sums of reduction rings are again reduction rings, we can directly conclude that ℤ^{k}[X_{1}, …, X_{n}] or even (ℤ[Y_{1}, …, Y_{m}])^{k}[X_{1}, …, X_{n}] are reduction rings. Moreover, since ℤ 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 [3], Madlener [8] and Stifter [19]).

2A term ordering ⪰ is called admissible if for every term s, t, u, s ⪰ 1 holds, and s ⪰ t implies s ∘ u ⪰ t ∘ u. An ordering fulfilling the latter condition is also said to be compatible with the respective multiplication ∘.

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 [17].

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 Madlener and Reinert [13]. Here we want to give an extended version of this paper including more details and proofs. Since, in a first step, we are not interested in effectivity, in Section 2 reduction rings are characterized by specifying three simple and natural axioms for the reduction relation and requiring the existence of finite Gröbner bases. In the remaining sections for different ring constructions we define natural reduction relations fulfilling the axioms and we additionally determine when the property of being a reduction ring is preserved. Moreover, in case the reduction ring is effective the resulting constructions as quotients and sums again are effective reduction rings. For the special case of monoid rings (including polynomial rings) we provide characterizations which enable to test the property of being a Gröbner basis by checking certain test sets which are finite provided the effective reduction ring fulfills additional properties. Such test sets are essential and have been used in critical-pair completion procedures as introduced by D. Knuth and P. Bendix or B. Buchberger for computing equivalent confluent reduction relations. However, while we determine when Gröbner bases exist and outline when they are additionally computable, we do not give procedures to compute them since this would go beyond the scope of this paper.

Let us close this section by summarizing some important notations and definitions of reduction relations which will be used throughout the paper (more details can be found in the book of Book and Otto [4]). Let E be a set of elements and ⟶ a binary relation on E called reduction. For a, b ∈ E we will write a ⟶ b in case (a, b) ∈ ⟶. A pair (E, ⟶) will be called a reduction system. Obviously the reflexive symmetric transitive closure ⟷^{∗} is an equivalence relation on E. The word problem for (E, ⟶) is to decide for a, b ∈ E, whether a ⟷^{∗} b holds. An element a ∈ E is said to be reducible (with respect to ⟶, also denoted by a ⟶) if there exists an element b ∈ E such that a ⟶ b. If there is no such b, a is called irreducible denoted by a −̸→ . In case a ⟶^{∗} b and b is irreducible, b is called a normal form of a. (E, ⟶) is said to be Noetherian (or terminating) in case there are no infinitely descending reduction chains a_{0} ⟶ a_{1} ⟶ …, with a_{i} ∈ E, i ∈ ℕ. It is called confluent, if for all a, a_{1}, a_{2} ∈ E, a ⟶^{∗} a_{1} and a ⟶^{∗} a_{2} implies the existence of a_{3} ∈ E such that a_{1} ⟶^{∗} a_{3} and a_{2} ⟶^{∗} a_{3}. We can combine these two properties to give sufficient conditions for the existence of unique normal forms: (E, ⟶) is said to be complete or convergent in case it is both, Noetherian and confluent. In case (E, ⟶) is Noetherian, confluence is equivalent to local confluence, i.e. for all a, a_{1}, a_{2} ∈ E, a ⟶ a_{1} and a ⟶ a_{2} implies the existence of a_{3} ∈ E such that a_{1} ⟶^{∗} a_{3} and a_{2} ⟶^{∗} a_{3}. The latter property called Newman’s Lemma is often the basis of completion methods for specialized reduction systems as e.g. string rewriting systems or polynomials as rules.

2. Reduction rings

Let R be a ring with unit 1 and a (not necessarily effective) reduction relation ⟹_{B} associated with subsets B ⊆ R, satisfying the following axioms:

(A1) ⟹_{B} = ⋃_{β∈B} ⟹_{β},

⟹_{B} is terminating for all finite subsets B ⊆ R.

(A2) α ⟹_{β} γ implies α − γ ∈ ideal^{R}(β).
(A3) α ⟹_{α} 0 for all α ∈ R ∖ {0}.

Part one of Axiom (A1) states how reduction using sets is defined and is hence applicable to arbitrary sets B. However, Axiom (A1) does not imply termination of reduction with respect to arbitrary sets. Consider for example the ring R = ℚ[{X_{i} | i ∈ ℕ}], 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} ≻ X_{2} ≻ . . .. Then although reduction using a finite set of polynomials is terminating, this is no longer true for infinite sets, as e.g. the set {X_{i} − X_{i+1} | i ∈ ℕ} gives rise to an infinite reduction sequence X_{1} ⟹_{X_{1}−X_{2}} X_{2} ⟹_{X_{2}−X_{3}} X_{3} . . ..

It is possible to give a more restricted form of Axiom (A1):

(A1’) ⟹_{B} = ⋃_{β∈B} ⟹_{β},

⟹_{B} is terminating for all subsets B ⊆ R.

Then, of course, reduction is always terminating, and many additional restrictions which we must add in later parts of the paper are no longer necessary. In this paper we prefer the more general formulation of the axiom.

Axiom (A2) states how reduction steps are related to the ideal congruence, namely, one reduction step using an element β ∈ R is captured by the congruence generated by ideal^{R}(β). We will later on see that this extends to the reflexive transitive symmetric closure ⟺^{∗}_{B} of any reduction relation ⟹_{B} for arbitrary sets B ⊆ R.

Notice that in case R is commutative, (A2) implies γ = α − β · ρ for some ρ ∈ R. In the non-commutative case, using a single element β for reduction α − γ ∈ ideal^{R}(β) only implies γ = α − ∑_{i=1}^{k} ρ_{i1} · β · ρ_{i2} for some ρ_{i1}, ρ_{i2} ∈ R, 1 ≤ i ≤ k, involving β 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 β from α. Notice further that Axiom (A2) does not provide any information on how α, γ ∈ R with α − γ ∈ ideal^{R}(β) are related with respect to the reduction relation ⟹_{{β}}.

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

(A2r) α ⟹_{β} γ implies α − γ ∈ ideal_{r}^{R}(β).
(A2l) α ⟹_{β} γ implies α − γ ∈ ideal_{l}^{R}(β).

In these special cases again we always get γ = α−β·ρ, respectively γ = α−ρ·β, for some ρ ∈ 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 arbitrary sets B ⊆ R and let ≡_{𝔦} denote the congruence generated by the ideal 𝔦 = ideal(B). Then (A1)^{3} and (A2) immediately imply ⟺^{∗}_{B} ⊆ ≡_{𝔦}. Hence, in case the reduction relation is effective one method for deciding the membership problem for a finitely generated ideal 𝔦 is to transform a finite generating set B into a finite set B′ such that B′ still generates 𝔦 and ⟹_{B′} is confluent on 𝔦. Notice that 0 has to be irreducible for all ⟹_{α}, α ∈ R^{4}. Therefore, 0 can be chosen as the normal form of the ideal elements. Hence the goal is to achieve α ∈ 𝔦 if and only if α ⟹^{∗}_{B′} 0. In particular, 𝔦 is one equivalence class of ⟺^{∗}_{B′} . The different definitions of reduction relations for rings existing in literature show that for deciding the membership problem of an ideal 𝔦 it is not necessary to enforce ⟺^{∗}_{B′} = ≡_{𝔦}. For example the D-reduction notion given by Pan [16] does not have this property but still is sufficient to decide ≡_{𝔦}-equivalence of two elements because α ≡_{𝔦} β if and only if α − β ∈ 𝔦. It may even happen that D-reduction is not only confluent on 𝔦 but confluent everywhere and still α ≡_{𝔦} β does not imply that the normal forms with respect to D-reduction are the same.

3We only need the first part of Axiom (A1), namely how ⟹_{B} is defined, and hence we do not have to restrict ourselves to finite sets.

40 cannot be reducible by itself since this would contradict the termination property in (A1). Similarly, 0 ⟹_{β} 0 and 0 ⟹_{β} γ, both β and γ not equal 0, give rise to infinite reduction sequences again contradicting (A1).

Example 2.1. Let us illustrate different ways of introducing reduction for the ring of integers ℤ. For α, β, γ ∈ ℤ we define:

• α ⟹_{β}^{1} γ if and only if α = κ · |β| + γ where 0 ≤ γ < |β| and κ ∈ ℤ,

• α ⟹_{β}^{2} 0 if and only if α = κ · β, i.e. β is a proper divisor of α.

Then for example we have 5 ⟹_{4}^{1} 1 but 5 ≠⇒ _{4}^{2} .

It is easy to show that both reductions satisfy (A1)–(A3). Moreover, the elements in ℤ have unique normal forms. An element belongs to ideal(4) if and only if it is reducible to zero using 4. For ⟹^{1}-reduction the normal forms are unique representatives of the quotient ℤ/ideal(4). This is no longer true for ⟹^{2}-reduction, e.g. 3 ≡_{ideal(4)} 7 since 7 = 3 + 4, but both are ⟹^{2}-irreducible.

However, if we want unique normal forms for all elements in R so that each congruence has one representative, we need special ideal bases.

Definition 2.2. A subset B of R is called a Gröbner basis of the ideal 𝔦 = ideal^{R}(B), if ⟺^{∗}_{B} = ≡_{𝔦} and ⟹_{B} is convergent^{5}.

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

Definition 2.3. A ring (R, ⟹) satisfying (A1)–(A3) is called a reduction ring if every finitely generated ideal in R has a finite Gröbner basis.

To simplify the notation, sometimes we will identify (R, ⟹) with R in case ⟹ is known or irrelevant. The notion of one-sided reduction rings is straightforward.

Effective or computable reduction rings can be defined similarly to Buchberger’s commutative reduction rings (see Buchberger [3] or Stifter [19]), in our case by demanding that the ring operations are computable, reduction is effective, and Gröbner bases can be computed. Procedures to compute Gröbner bases are normally completion procedures, based on effective tests (e.g. testing special polynomials for reducibility to zero) to decide whether a finite set is a Gröbner basis and to alter that set if not. Of course, other procedures are also possible, e.g. using the Euclidean algorithm for computing Gröbner bases in ℤ.

5Notice that in the literature the definition of Gröbner bases normally require that “ ⟹_{B} is confluent”. This is due to the fact that in these cases ⟹_{B} is terminating. In our context, however, for arbitrary sets B ⊆ R we have seen that ⟹_{B} need not be Noetherian. Hence we have to incorporate this additional requirement into our definition, which is done by demanding convergence. In rings where reduction using an arbitrary set of elements is always Noetherian, the weaker demand for (local) confluence is of course sufficient.

Notice that Definition 2.3 does not imply that Noetherian rings satisfying Axioms (A1), (A2) and (A3) are reduction rings. This is due to the fact that the property of being a reduction ring is, of course, strongly dependent on the reduction relation chosen for the ring. For example given a Noetherian ring R we can associate a (very simple) reduction relation to elements of R by defining α ⟹_{β} if and only if α = β. Additionally we define α ⟹_{α} 0. Then the Axioms (A1), (A2) and (A3) are fulfilled but, although every ideal in the Noetherian ring R has a finite basis (in the sense of a generating set), infinite ideals will not have finite Gröbner bases^{6}.

Another interesting question concerns changes to ideal bases which preserve the property of being a Gröbner basis. Extensions of Gröbner bases by ideal elements are not critical.

Remark 2.4. If B is a finite Gröbner basis of 𝔦 and α ∈ 𝔦, then B′ = B ∪{α} is again a Gröbner basis of 𝔦. First of all we find ⟺^{∗}_{B} ⊆ ⟺^{∗}_{B′} ⊆ ≡_{𝔦} = ⟺^{∗}_{B} . Moreover, since B′ is again a finite set ⟹_{B′} is terminating. Finally, ⟹_{B′} inherits its confluence from ⟹_{B} since β ⟹_{α} γ implies β ≡_{𝔦} γ and so β and γ have the same normal form with respect to ⟹_{B}.

Hence, if B is a Gröbner basis of an ideal 𝔦 and β ∈ B is reducible by B ∖{β} to α, then B ∪ {α} is again a Gröbner basis of 𝔦. In order to remove β from B ∪ {α} without losing the Gröbner basis property it is important for ⟹ to satisfy an additional axiom:

(A4) α ⟹_{β} and β ⟹_{γ} δ imply α ⟹_{γ} or α ⟹_{δ}.

Lemma 2.5. Let (R, ⟹) be a reduction ring satisfying (A4). Further let B ⊆ R be a Gröbner basis and B′ ⊆ B such that for all β ∈ B, β ⟹^{∗}_{B′} 0 holds. Then B′ is a Gröbner basis of ideal^{R}(B). In particular, for all α ∈ R, α ⟹^{∗}_{B} 0

implies α ⟹^{∗}_{B′} 0.

Proof. In this proof let α⇓_{B} denote a normal form of α with respect to ⟹_{B} and let IRR(⟹_{B}) denote the ⟹_{B}-irreducible elements in R. Notice that by the Axioms (A1) and (A4) and our assumptions on B′, all elements reducible by B are also reducible by B′: We show a more general claim by induction on n: If α, β ∈ R such that α ⟹_{β} and β ⟹^{n}_{B′} 0, then α ⟹_{B′}. The base case n = 1 is a direct consequence of (A4), as α ⟹_{β} and β ⟹_{β′∈B′} 0 immediately

imply α ⟹_{β′∈B′}. In the induction step we find β ⟹_{β′∈B′} δ ⟹^{n−1}_{B′} 0 and either α ⟹_{β′∈B′} or α ⟹_{δ} and our induction hypothesis yields α ⟹_{B′}.

6For any ideal 𝔦 ⊆ R, in this setting, the set 𝔦 ∖ {0} is the only possible Gröbner basis.

Hence we can conclude IRR(⟹_{B′}) ⊆ IRR(⟹_{B}). We want to show that B′ is a Gröbner basis of ideal^{R}(B): assuming α ⟹^{∗}_{B} α⇓_{B} but α ⟹^{∗}_{B′} α⇓_{B′}≠ α⇓_{B}, we find α ⟹^{∗}_{B} α⇓_{B′} and α⇓_{B′}∈ IRR(⟹_{B′}) ⊆ IRR(⟹_{B}), contradicting the confluence of ⟹_{B}. Hence, α⇓_{B′}= α⇓_{B}, implying that ⟹_{B′} is also confluent, as α⇓_{B} is unique. Now it remains to show that ⟺^{∗}_{B} ⊆ ⟺^{∗}_{B′} holds. This follows immediately, as for α ⟺^{∗}_{B} β we have α⇓_{B′}= α⇓_{B}= β⇓_{B}= β⇓_{B′} which

implies α ⟺^{∗}_{B′} β. □ ✓

Remark 2.4 and Lemma 2.5 are closely related to interreduction and reduced Gröbner bases. We call a Gröbner basis B ⊆ R reduced if no element β ∈ B is reducible by ⟹_{B∖{β}}.

In the remaining sections of the paper we study the question of which ring constructions, as e.g. extensions, products, sums or quotients, preserve the property of being a reduction ring.

3. Quotients of reduction rings

Let (R, ⟹) be a reduction ring and 𝔦 a finitely generated ideal in R with a (finite) Gröbner basis B. Then every element α ∈ R has a unique normal form α⇓_{B} with respect to ⟹_{B}. We choose the set of ⟹_{B}-irreducible elements of R as representatives for the elements in the quotient R/𝔦. Addition is defined by α + β := (α + β)⇓_{B} and multiplication by α · β := (α · β)⇓_{B}. Then a natural reduction can be defined on the quotient R/𝔦 as follows:

Definition 3.1. Let α, β, γ ∈ R/𝔦. We say that β reduces α to γ in one step, denoted by α ⟶_{β} γ, if there exists γ′ ∈ R such that α ⟹_{β} γ′ and (γ′)⇓_{B}= γ.

First we ensure that the Axioms (A1)–(A3) hold for reduction in R/𝔦 as defined in Definition 3.1: ⟶_{S} = ⋃_{s∈S} ⟶_{s} is terminating for all finite S ⊆ R/𝔦 since otherwise ⟹_{B∪S} would not be terminating in R, although B ∪ S is finite. Hence, (A1) is satisfied. If α ⟶_{β} γ for some α, β, γ ∈ R/𝔦, we know α ⟹_{β} γ′ ⟹^{∗}_{B} γ, i.e. α − γ ∈ ideal^{R}({β} ∪ B), and hence α − γ ∈ ideal^{R/𝔦}(β). Therefore, (A2) is also fulfilled. Finally, Axiom (A3) holds since α ⟹_{α} 0 for all α ∈ R ∖ {0} implies α ⟶_{α} 0.

Moreover, in case (A4) holds in R this is also true for R/𝔦: for α, β, γ, δ ∈ R/𝔦 we have that α ⟶_{β} and β ⟶_{γ} δ imply α ⟹_{β} and β ⟹_{γ} δ′ ⟹^{∗}_{B} δ, and since α is ⟹_{B}-irreducible this implies α ⟹_{{γ,δ}}, so α ⟶_{{γ,δ}}.

Theorem 3.2. If (R, ⟹) is a reduction ring with (A4), then for every finitely generated ideal 𝔦 the quotient (R/𝔦, ⟶) again is a reduction ring with (A4).

Proof. Since reduction in R/𝔦 as defined above inherits (A1)–(A4) from R, it remains to show that every finitely generated ideal 𝔧 ⊆ R/𝔦 has a finite Gröbner basis. Let 𝔧_{R} = {α ∈ R | α⇓_{B}∈ 𝔧} be an ideal in R corresponding to 𝔧. Since 𝔧_{R} is a finitely generated ideal in R, it has a finite Gröbner basis, say G_{R}. Then G = {α⇓_{B}| α ∈ G_{R}} ∖ {0} is a finite Gröbner basis of 𝔧: If α ∈ 𝔧 we have α ⟶^{∗}_{G} 0 and ideal^{R/𝔦}(G) = 𝔧, as every element which is reducible with an element β ∈ G_{R} is also reducible with an element of G ∪ B because (A4) holds. Since G∪B is also a Gröbner basis of 𝔧_{R} and ⟶_{G} ⊆ ⟹^{∗}_{G∪B} , when restricted to elements in R/𝔦 we have IRR(⟶_{G}) = IRR(⟹_{G∪B}) and ⟶_{G} is confluent. Furthermore, because ≡_{𝔧} = ≡_{𝔧_{R}} when restricted to R/𝔦, we get ⟷^{∗}_{G} = ≡_{𝔧} on R/𝔦, implying that R/𝔦 is a reduction ring. □ ✓

In Example 2.1 we have seen how to associate the integers with a reduction relation ⟶^{1} and in fact (ℤ, ⟶^{1}) is a reduction ring. Theorem 3.2 then states that for every m ∈ ℤ the quotient ℤ/ideal(m) again is a reduction ring. In particular reduction rings with zero divisors can be constructed in this way.

Now if (R, ⟹) is an effective reduction ring, then B can be computed and addition and multiplication in R/𝔦, as well as the reduction of Definition 3.1 are computable operations. Moreover, Theorem 3.2 can be generalized:

Corollary 3.3. If (R, ⟹) is an effective reduction ring satisfying (A4), then for every finitely generated ideal 𝔦 the quotient (R/𝔦, ⟶) again is an effective reduction ring with (A4).

Proof. Given R, B and a finite generating set F for an ideal 𝔧 in R/𝔦 we can compute a Gröbner basis for 𝔧 using the method for computing Gröbner bases in R: compute a Gröbner basis G_{R} of the ideal generated by B ∪ F in R. Then the set G = {normal.form(g, ⟹_{B}) | g ∈ G_{R}}, where normal.form(g, ⟹_{B}) is the normal form of g with respect to B in R and so an element of R/𝔦, is a Gröbner basis of 𝔧 in R/𝔦. □ ✓

Theorem 3.2 and Corollary 3.3 extend to the case of one-sided reduction rings with (A4) provided that the two-sided ideal has a finite right respectively left Gröbner basis.

4. Sums of reduction rings

Let (R_{1}, ⟹^{1} ), (R_{2}, ⟹^{2} ) be reduction rings. Then R = R_{1} × R_{2} = {(α_{1}, α_{2}) | α_{1} ∈ R_{1}, α_{2} ∈ R_{2}} is called the direct sum of R_{1} and R_{2}. Addition and multiplication are defined componentwise, the unit is (1_{1}, 1_{2}) where 1_{i} is the respective unit in R_{i}. A natural reduction can be defined on R as follows:

Definition 4.1. Let α = (α_{1}, α_{2}), β = (β_{1}, β_{2}), γ = (γ_{1}, γ_{2}) ∈ R. We say that β reduces α to γ in one step, denoted by α ⟶_{β} γ, if either (α_{1} ⟹_{β_{1}}^{1} γ_{1} and α_{2} = γ_{2}) or (α_{1} = γ_{1} and α_{2} ⟹_{β_{2}}^{2} γ_{2}) or (α_{1} ⟹_{β_{1}}^{1} γ_{1} and α_{2} ⟹_{β_{2}}^{2} γ_{2}).

Again we have to prove that the Axioms (A1)–(A3) hold for reduction in R: ⟶_{B}= ⋃_{β∈B} ⟶_{β} is terminating for finite B ⊆ R since this property is inherited from the termination of the respective reductions in R_{i}. Hence, (A1) holds. (A2) is satisfied because α ⟶_{β} γ implies α − γ ∈ ideal^{R}(β). (A3) is true as α ⟶_{α} (0_{1}, 0_{2}) holds for all α ∈ R ∖ {(0_{1}, 0_{2})}. Moreover, it is easy to see that if condition (A4) holds for ⟹^{1} and ⟹^{2} then it is inherited by ⟶.

Theorem 4.2. If (R_{1}, ⟹^{1} ), (R_{2}, ⟹^{2} ) are reduction rings, then (R = R_{1} × R_{2}, ⟶) is again a reduction ring.

Proof. Since reduction in R as defined above inherits (A1)–(A3), respectively (A4), from the reductions in the R_{i}, it remains to show that every finitely generated ideal 𝔦 ⊆ R has a finite Gröbner basis. To see this notice that the restrictions 𝔦_{1} = {α_{1} | (α_{1}, α_{2}) ∈ 𝔦 for some α_{2} ∈ R_{2}} and 𝔦_{2} = {α_{2} | (α_{1}, α_{2}) ∈ 𝔦 for some α_{1} ∈ R_{1}} are finitely generated ideals in R_{1}, respectively R_{2}, and hence have finite Gröbner bases B_{1}, respectively B_{2}. We claim that B = {(β_{1}, 0_{2}), (0_{1}, β_{2}) | β_{1} ∈ B_{1}, β_{2} ∈ B_{2}} is a finite Gröbner basis of 𝔦. Notice that 𝔦 = 𝔦_{1} × 𝔦_{2} and the elements of 𝔦_{1}, 𝔦_{2} are “included” in 𝔦 via multiplication with (1_{1}, 0_{2}), respectively (0_{1}, 1_{2}). Then ideal(B) = 𝔦 and α ∈ 𝔦 implies α ⟶^{∗}_{B} (0_{1}, 0_{2}) due to the fact that for α = (α_{1}, α_{2}) we have

α_{1} ∈ 𝔦_{1} and α_{2} ∈ 𝔦_{2} implying α_{1} ⟹^{∗}_{B_{1}}^{1} 0_{1} and α_{2} ⟹^{∗}_{B_{2}}^{2} 0_{2}. Similarly ⟶_{B}

is confluent because ⟹_{B_{1}}^{1} and ⟹_{B_{2}}^{2} are confluent. Finally ⟷^{∗}_{B} = ≡_{𝔦} since (α_{1}, α_{2}) ≡_{𝔦} (β_{1}, β_{2}) implies α_{1} ≡_{𝔦_{1}} β_{1}, respectively α_{2} ≡_{𝔦_{2}} β_{2}, and hence

α_{1} ⟺^{∗}_{B_{1}}^{1} β_{1}, respectively α_{2} ⟺^{∗}_{B_{2}}^{2} β_{2}. □ ✓

Special regular rings as introduced by Weispfenning [20] provide examples of such sums of reduction rings.

Now if (R_{1}, ⟹^{1} ), (R_{2}, ⟹^{2} ) are effective reduction rings, then addition and multiplication in R, as well as the reduction in Definition 4.1, are computable operations. Moreover, Theorem 4.2 can be generalized:

Corollary 4.3. If (R_{1}, ⟹^{1} ), (R_{2}, ⟹^{2} ) are effective reduction rings, then (R = R_{1} × R_{2}, ⟶) is again an effective reduction ring.

Proof. Given a finite generating set F = {(f_{i}, g_{i}) | 1 ≤ i ≤ k, f_{i} ∈ R_{1}, g_{i} ∈ R_{2}} a Gröbner basis of the ideal generated by F can be computed using the respective methods for Gröbner basis computation in R_{1} and R_{2}. Compute a Gröbner basis B_{1} of the ideal generated by {f_{1}, …, f_{k}} in R_{1} and a Gröbner basis B_{2} of the ideal generated by {g_{1}, …, g_{k}} in R_{2}. Then B = {(β_{1}, 0_{2}), (0_{1}, β_{2}) | β_{1} ∈ B_{1}, β_{2} ∈ B_{2}} is a finite Gröbner basis of the ideal generated by F in R. □ ✓

Due to the “simple” multiplication used when defining the structure, Theorem 4.2 and Corollary 4.3 extend directly to one-sided reduction rings. More complicated multiplications are possible and have to be treated individually.

5. Polynomial rings over reduction rings

For a reduction ring (R, ⟹) we adopt the usual notations in R[X], the polynomial ring in one variable X, where multiplication is denoted by ∗. Notice that for scalar multiplication by α ∈ R we assume α · X = X · α (see Pesch [17] for other possibilities). We specify an ordering on the set of terms {X^{i} | i ∈ ℕ} in one variable by defining that if X^{i} divides X^{j}, i.e. 0 ≤ i ≤ j, then X^{i} ⪯ X^{j}. Using this ordering, the head term HT(p), the head monomial HM(p), and the head coefficient HC(p) of a polynomial p ∈ R[X] are defined as usual, and RED(p) = p − HM(p). We extend the function HT to sets of polynomials F ⊆ R[X] by HT(F) = {HT(f) | f ∈ F }.

Let 𝔦 ⊆ R[X] be a finitely generated ideal in R[X]. It is easy to see that given a term t the set C(t, 𝔦) = {HC(f) | f ∈ 𝔦, HT(f) = t} ∪ {0} is an ideal in R. In order to guarantee that these ideals are also finitely generated we will assume that R is a Noetherian ring. Note that for any two terms t and s such that t divides s we have C(t, 𝔦) ⊆ C(s, 𝔦).

We additionally define a (not necessarily Noetherian) partial ordering on R by setting for α, β ∈ R, α >_{R} β if and only if there exists a finite set B ⊆ R such that α ⟹^{+}_{B} β. Then we can define an ordering on R[X] as follows: For f, g ∈ R[X], f > g if and only if either HT(f) ≻ HT(g) or (HT(f) = HT(g) and HC(f) >_{R} HC(g)) or (HM(f) = HM(g) and RED(f) > RED(g)). Notice that, in general, this ordering is neither total nor Noetherian on R[X].

Definition 5.1. Let p, f be two non-zero polynomials in R[X]. We say f reduces p to q at a monomial α · X^{i} in p in one step, denoted by p ⟶_{f} q, if

(a) HT(f) divides X^{i}, i.e. HT(f)X^{j} = X^{i} for some term X^{j},

(b) α ⟹_{HC(f)} β, with α = β + ∑_{i=1}^{k} γ_{i} · HC(f) · δ_{i} for some β, γ_{i}, δ_{i} ∈ R, 1 ≤ i ≤ k, and

(c) q = p − ∑_{i=1}^{k}(γ_{i} · f · δ_{i}) ∗ X^{j}.

Notice that if f reduces p to q at a monomial α · t the term t can still occur in the resulting polynomial q. But when using a finite set of polynomials for the reduction we know by (A1) that reducing α in R with respect to the finite set of head coefficients of the applicable polynomials must terminate and then either the monomial containing the term t disappears or is irreducible. Hence, reduction as defined in Definition 5.1 is Noetherian when using finite sets of polynomials and Axiom (A1) holds. It is easy to see that (A2) and (A3) are also true, and if the reduction ring satisfies (A4) this is inherited by R[X].

Theorem 5.2. If (R, ⟹) is a Noetherian reduction ring, then (R[X], ⟶) is a Noetherian reduction ring.

Proof. By Hilbert’s basis theorem R[X] is Noetherian if R is Noetherian. We only have to prove that every (finitely generated) ideal 𝔦 ≠ {0} in R[X] has a finite Gröbner basis.

A finite basis G of 𝔦 will be defined in stages according to the degree of the terms occurring as head terms among the polynomials in 𝔦 and then we will show that G is in fact a Gröbner basis.

Let G_{0} be a finite Gröbner basis of the ideal C(λ, 𝔦) in R, which must exist since R is supposed to be Noetherian. Further, at stage i > 0, if for each X^{j} with j < i we have C(X^{j}, 𝔦) ⫋ C(X^{i}, 𝔦), include in G_{i} for each α in Gb(C(X^{i}, 𝔦)) (a finite Gröbner basis of C(X^{i}, 𝔦)) a polynomial p_{α} from 𝔦 such that HM(p) = α · X^{i}. Notice that in this construction we use the axiom of choice, when choosing p_{α} from the infinite set 𝔦, and so it is non-constructive. At each stage only a finite number of polynomials can be added since the respective Gröbner bases Gb(C(X^{i}, 𝔦)) are always finite, and at most one polynomial from 𝔦 is included for each element in Gb(C(X^{i}, 𝔦)).

If a polynomial with head term X^{i} is included, then C(X^{j}, 𝔦) ⫋ C(X^{i}, 𝔦) for every j < i. So, if X^{i} ∈ HT (𝔦) is not included as a head term of a polynomial in G_{i}, then there is a term X^{j} occurring as a head term in some set G_{j}, j < i, C(X^{i}, 𝔦) = C(X^{j}, 𝔦), and C(X^{j}, G_{j}) is a Gröbner basis for the ideal C(X^{j}, 𝔦) = C(X^{i}, 𝔦) in R.

We claim that the set G = ⋃_{i≥0} G_{i} is a finite Gröbner basis of 𝔦.

To show that G is finite it suffices to prove that the set HT(G) is finite, since in every stage only finitely many polynomials, all having new head terms, are added. Assuming that HT(G) is infinite, there is a sequence X^{n_{i}}, i ∈ ℕ of different terms such that n_{i} < n_{i+1}. But then by construction there is an ascending sequence of ideals in R, namely C(X^{n_{0}}, 𝔦) ⫋ C(X^{n_{1}}, 𝔦) ⫋ … which contradicts the fact that R is supposed to be Noetherian.

So after some step m no more polynomials p from 𝔦 can be found such that for HT(p) = X^{i} the set C(X^{i}, 𝔦) is different from all C(X^{j}, 𝔦), j < i.

Notice that for all p ∈ 𝔦 we have p ⟶^{∗}_{G} 0 and G generates 𝔦. This follows immediately from the construction of G.

To see that ⟶_{G} is confluent, let p be a polynomial which has two distinct normal forms with respect to G, say p_{1} and p_{2}. Let t be the largest term on which p_{1} and p_{2} differ and let α_{1} and α_{2} be the respective coefficients of t in p_{1} and p_{2}. Since p_{1} − p_{2} ∈ 𝔦, this polynomial reduces to 0 using G and without loss of generality we can assume that these reductions always take place at the respective head terms of the polynomials in the reduction sequence. Let s ∈ HT(G) be the head term of the polynomial in G which reduces HT(p_{1} −p_{2}), i.e. s divides t, α_{1} − α_{2} ∈ C(s, 𝔦), and hence α_{1} ≡_{𝔦} α_{2}. Therefore, not both α_{1} and α_{2} can be in normal form with respect to any Gröbner basis of C(s, 𝔦) and so with respect to the set of head coefficients of polynomials in G with head term s. So both, α_{1} · t and α_{2} · t cannot be in normal form with respect to G, which is a contradiction to the fact that p_{1} and p_{2} are supposed to be in normal form with respect to G.

Finally, we have to prove ≡_{𝔦} = ⟷^{∗}_{G}. Let p ≡_{𝔦} q both be in normal form with respect to G. Then, as before, p − q ⟶^{∗}_{G} 0 implies p = q. Hence, we have shown that G is in fact a finite Gröbner basis of 𝔦. □ ✓

Of course, this theorem can be applied to R[X] and a new variable X_{2} and by iteration we immediately get the following:

Corollary 5.3. If (R, ⟹) is a Noetherian reduction ring, then R[X_{1}, …, X_{n}] is a Noetherian reduction ring with the respective lifted reduction.

Notice that other definitions of reduction in R[X_{1}, …, X_{n}] are known in the literature. These are usually based on divisibility of terms and admissible term orderings on the set of terms to distinguish the head terms. The proof of Theorem 5.2 can be generalized to these cases.

Now, if (R, ⟹) is an effective reduction ring, then addition and multiplication in R[X] as well as reduction as defined in Definition 5.1 are computable operations. Unlike in the previous sections, the proof of Theorem 5.2 does not specify how Gröbner bases for finitely generated ideals in R[X] can be constructed using Gröbner basis methods for R. So we cannot conclude that for effective reduction rings the polynomial ring again will be effective. A more suitable characterization of Gröbner bases requiring R to fulfill additional conditions will be provided for the more general case of monoid rings in the next section. The basic idea of that characterization will be to define Gröbner bases in terms of completion and to localize the completion test to special sets of polynomials. In order to provide effective completion procedures for computing Gröbner bases, various characterizations of Gröbner bases by finite test sets of special polynomials in certain commutative reduction rings (e.g. the integers and Euclidean domains) can be found in the literature (see e.g. Kapur and Narendran [6], Kandri-Rody and Kapur [5] and Möller [14]). A general approach to the characterization commutative reduction rings, allowing the computation of Gröbner bases via Buchberger’s approach was presented by Stifter [19].

We close this section by providing similar characterizations for polynomial rings over non-commutative reduction rings and outlining the arising problems. For simplicity we restrict ourselves to the case of R[X], but this is no general restriction. Given a generating set F ⊆ R[X] the key idea is to distinguish special elements of ideal(F) which have representations ∑_{i=1}^{n} g_{i} ∗f_{i} ∗h_{i}, g_{i}, h_{i} ∈ R[X], f_{i} ∈ F, such that the head terms HT(g_{i} ∗ f_{i} ∗ h_{i}) are all the same within the representation. Then, on one hand the respective HC(g_{i} ∗ f_{i} ∗ h_{i}) can add up to zero, which means that the sum of the head coefficients is in an appropriate module generated by the HC(f_{i}); m-polynomials^{7} are related to these situations. If the result is not zero the sum of the HC(g_{i} ∗ f_{i} ∗ h_{i}) can be described in terms of a Gröbner basis of the HC(f_{i}); g-polynomials are related to these situations. Zero divisors in the reduction ring occur as a special instance of m-polynomials where F = {f} and α ∗ f ∗ β, α, β ∈ R are considered.

In case R is a commutative or one-sided reduction ring the first problem is related to solving linear homogeneous equations in R and to the existence of finite bases of the respective modules. In case we want effectiveness, we have to require that these bases are computable. This becomes more complicated for non-commutative two-sided reduction rings, as the equations are no longer linear and we have to distinguish right and left multipliers simultaneously. In some cases the problem for two-sided ideals can be translated into the onesided case and hence solved via one-sided reduction techniques (Kandri-Rody and Weispfenning [7]).

The g-polynomials can be finitely described whenever finite Gröbner bases exist. Here, if we want effectiveness, we have to require that a Gröbner basis as well as representations for its elements in terms of the generating set are computable.

Then using m- and g-polynomials, Gröbner bases can be characterized similarly to the characterizations in terms of syzygies (a direct generalization of the approaches by Kapur and Narendran [6] respectively Möller [14]). In case the respective terms HT(g_{i} ∗ f_{i} ∗ h_{i}) give rise only to finitely many m- and gpolynomials, these situations can be localized to finitely many terms —to the least common multiples of the HT(f_{i}), i.e. the maximal term when f_{i} ∈ R[X]— and we can provide a completion procedure based on this characterization which will indeed compute a finite Gröbner basis if R is Noetherian. In principal ideal rings, where the function gcd (greatest common divisor) is defined, it is sufficient to consider sets F of size 2.

7Explicit definitions of m- and g-polynomials will be provided in the next section.

We will give the details of this approach for right reduction rings and the more general case of monoid rings in the next section.

6. Monoid rings over reduction rings

While polynomial rings over Noetherian reduction rings are again reduction rings, this cannot be achieved for the more general case of monoid rings. Already “non-commutative polynomial rings” over fields as presented by Mora [15], which are in fact free monoid rings, give us negative results concerning the existence of finite Gröbner bases for finitely generated two-sided ideals due to the fact that they are closely related to the word problem for monoids (Kandri-Rody and Weispfenning [7], Reinert [18] and Madlener and Reinert [11]). However, when restricting the focus to one-sided ideals in this special setting, the existence of finite one-sided Gröbner bases can be shown (Mora [15]).

Hence, we will restrict our attention to monoid rings over a right reduction ring (R, ⟹) satisfying (A4) and provide a characterization of right Gröbner bases for finitely generated right ideals in this setting —the case of left ideals in monoid rings over left reduction rings with (A4) being similar.

Given a cancellative^{8} monoid M with multiplication ∘, we call R[M] the monoid ring over R with elements presented as “polynomials” f = ∑_{t∈M} α_{t} · t where only finitely many coefficients are non-zero. The elements α_{t} ·t are called monomials, consisting of a coefficient α_{t} ∈ R and a term t ∈ M. Addition and multiplication for two polynomials f = ∑_{t∈M} α_{t} · t and h = ∑_{t∈M} β_{t} · t is defined as f + h = ∑_{t∈M}(α_{t} + β_{t}) · t and f ∗ h = ∑_{t∈M} γ_{t} · t with γ_{t} = ∑_{x∘y=t} α_{x} · β_{y}. Assuming a total well-founded ordering ≻ on M, the usual notions as HT(p), HC(p), and HM(p) are defined for p ∈ R[M] ∖ {0}. For a subset F of R[M] we call the set ideal_{r}(F) = {∑_{i=1}^{n} f_{i} ∗ (α_{i} · w_{i}) | n ∈ ℕ, α_{i} ∈ R, f_{i} ∈ F, w_{i} ∈ M} the right ideal generated by F in R[M].

As before, we define a partial ordering on R by setting for α, β ∈ R, α >_{R} β if and only if there exists a finite set B ⊆ R such that α ⟹^{+}_{B} β. This ordering can be extended to an ordering on R[M] as follows. For f, g ∈ R[M], f > g if and only if either HT(f) ≻ HT(g) or (HT(f) = HT(g) and HC(f) >_{R} HC(g)) or (HM(f) = HM(g) and RED(f) > RED(g)). Notice that the ordering in general is neither total nor Noetherian on R[M].

8In case we allow arbitrary monoids we have to be more careful in defining right reduction and critical situations corresponding to it.

Definition 6.1. Let p, f be two non-zero polynomials in R[M]. We say that f right reduces p to q at a monomial α · t in p in one step, denoted by p ⟶_{f}^{r} q, if

(a) HT(f ∗ w) = HT(f) ∘ w = t for some w ∈ M,

(b) α ⟹_{HC(f)} β, i.e. α = β + HC(f) · γ, γ ∈ R and

(c) q = p − f ∗ (γ · w).

While reduction needs no longer eliminate the occurrence of a term, it is Noetherian when using a fixed finite set of polynomials due to Axiom (A1) for ⟹ (compare Section 5). It is easy to see that (A2)–(A4) also hold and we can define Gröbner bases as before:

Definition 6.2. A set G ⊆ R[M] is called a right Gröbner basis of 𝔦 = ideal_{r}(G), if ⟷^{∗}_{G}^{r} = ≡_{𝔦}, and ⟶_{G}^{r} is convergent.

Notice that, contrary to the polynomial ring cases, p ∗ (α · w) ⟶_{p}^{r} 0 will not hold in general since the ordering on M will not be necessarily compatible with the multiplication in M, i.e., in general HT(p ∗ w) ≠ HT(p) ∘ w. In fact, for groups it cannot be admissible and well-founded at the same time unless the group is trivial. To repair this phenomenon which leads to ⟷^{∗}_{G}^{r} ≠ ≡_{ideal_{r}(G)} in general we introduce the concept of saturation.

Definition 6.3. A set of polynomials F ⊆ {p ∗ (α · w) | α ∈ R^{∗}, w ∈ M} is called a (right) saturating set for a polynomial p ∈ R[M], if for all α ∈ R, w ∈ M, p∗(α·w) ⟶_{F}^{r} 0 holds in case p∗(α·w) ≠ 0. A set F of polynomials in R[M] is called (right) saturated, if f ∗ (α · w) ⟶_{F}^{r} 0 holds for all f ∈ F, α ∈ R, w ∈ M in case f ∗ (α · w) ≠ 0.

We do not go into the details of when finite saturated sets exist and how they can be computed (see e.g. in Reinert [18] or Madlener and Reinert [10]). In order to characterize right Gröbner bases we now introduce special polynomials.

Definition 6.4. Let P = {p_{1}, …, p_{k}} be a set of polynomials in R[M] and t an element in M such that there are w_{1}, …, w_{k} ∈ M with HT(p_{i} ∗ w_{i}) = HT(p_{i}) ∘ w_{i} = t, for all 1 ≤ i ≤ k. Further, let γ_{i} = HC(p_{i}) for 1 ≤ i ≤ k^{9}. Let {α_{1}, …, α_{n}} be a right Gröbner basis of {γ_{1}, …, γ_{k}} and

α_{i} = γ_{1} · β_{i,1} + … + γ_{k} · β_{i,k}

for β_{i,j} ∈ R, 1 ≤ i ≤ n, and 1 ≤ j ≤ k. Notice that the α_{i} respectively the β_{i,j} do not depend on t. Then we define the g-polynomials (Gröbner polynomials) corresponding to P and t by setting

9Note that this definition has to be modified for non-cancellative monoids, as then HT(p∗ w) = HT(p) ∘ w no longer implies HC(p ∗ w) = HC(p).

g_{i} = ∑_{j=1}^{k} p_{j} ∗ (β_{i,j} · w_{j}) for each 1 ≤ i ≤ k.

Notice that HM(g_{i}) = α_{i} · t.

For the right module M = {(δ_{1}, …, δ_{k}) | ∑_{i=1}^{k} γ_{i} · δ_{i} = 0}, let the set {A_{i} | i ∈ I ⊆ ℕ} be a basis with A_{i} = (α_{i,1}, …, α_{i,k}) for α_{i,j} ∈ R, i ∈ I, and 1 ≤ j ≤ k. Notice that the A_{i} do not depend on t. Then we define the m-polynomials (module polynomials) corresponding to P and t by setting

m_{i} = ∑_{j=1}^{k} p_{j} ∗ (α_{i,j} · w_{j}) for each i ∈ I.

Notice that HT(m_{i}) ≺ t.

Since R is a right reduction ring the number of g-polynomials related to P and t is finite. If in R every right module of solutions to linear homogeneous equations is finitely generated, the number of m-polynomials related to P and t is finite.

Definition 6.5. Given F ⊆ R[M], the set of g- and m-polynomials corresponding to F contains for each finite subset P ⊆ F and each term t ∈ M the g- and m-polynomials as specified in Definition 6.4.

For a set consisting of one polynomial the corresponding m-polynomials reflect the multiplication of the polynomial with zero-divisors of the head coefficient, i.e., by a basis of the annihilator of the head coefficient.

We can use g- and m-polynomials to characterize special bases in monoid rings over a reduction ring in case they are additionally saturated.

Theorem 6.6. For a finite saturated subset F of R[M] the following statements are equivalent:

1. For all polynomials g ∈ ideal_{r}(F) we have g ⟶^{∗}_{F}^{r} 0.

2. F is a right Gröbner basis of ideal_{r}(F).

3. All g-polynomials and all m-polynomials corresponding to F right reduce to zero using F.

Proof.

1 ⟹ 2 : The inclusion ⟷^{∗}_{F}^{r} ⊆ ≡_{ideal_{r}(F)} is obvious. Hence, let us assume f ≡_{ideal_{r}(F)} g, i.e., f − g ∈ ideal_{r}(F) and, therefore, f − g ⟶^{∗}_{F}^{r} 0. We show that this implies f ⟷^{∗}_{F}^{r} g. In case f −g = 0 we are immediately done. Hence, let us assume f − g ≠ 0 and, as any polynomial in ideal_{r}(F) is right reducible to zero using F, without loss of generality we can assume that the reduction sequence f − g ⟶^{∗}_{F}^{r} 0 uses top-reduction, i.e., all reductions take place at the respective head monomial. Further, let t = HT(f − g) and let γ_{1}, respectively γ_{2}, be the coefficients of t in f, respectively g. We will now show that f ⟷^{∗}_{F}^{r} g holds by induction on the term t = HT(f −g). In case t = λ we find f −g = γ_{1}−γ_{2} ⟶^{∗}_{F}^{r} 0 and by lemma 2.5 the finite set C_{F} (λ) = {HC(f) | f ∈ F, λ = HT(f ∗ z) = HT(f) ∘ z for some z ∈ M} ⊆ R is a Gröbner basis of ideal_{r}^{R}(C_{F} (λ)). Hence, as

γ_{1} − γ_{2} ∈ ideal_{r}^{R}(C_{F} (λ)), γ_{1} ≡_{ideal_{r}^{R}(C_{F} (λ))} γ_{2} implies γ_{1} ⟺^{∗}_{C_{F} (λ)} γ_{2}. Using the

respective polynomials belonging to the elements in C_{F} (λ), we get f ⟷^{∗}_{F}^{r} g. Now let us assume t ≻ λ and f − g ⟶^{k}_{F}^{r} h where k ∈ ℕ^{+} is minimal such that HT(h) ≠ t. Further, let f_{1}, …, f_{k} be the polynomials used in the respective reduction steps, i.e., γ_{1} − γ_{2} ⟹^{∗}_{{HC(f_{i})|1≤i≤k}} 0. Again, since

C_{F} (t) =

{HC(f) | f ∈ F, t = HT(f) ∘ z for some z ∈ M, HT(f ∗ z) = HT(f) ∘ z}

is a finite right Gröbner basis of ideal_{r}^{R}(C_{F} (t)) and {HC(f_{i}) | 1 ≤ i ≤ k} ⊆ C_{F} (t), we find γ_{1} ⟺^{∗}_{C_{F} (t)} γ_{2}. Now applying the polynomial multiples belonging to the elements of C_{F} (t) used in this last sequence to the monomial with term t in f, we find an element f̃ ∈ R[M] such that f ⟷^{∗}_{F}^{r} f̃, HM(f̃) = γ_{2} · t, f̃− g ∈ ideal_{r}(F), and t ≻ HT(f̃− g). Hence, our induction hypothesis yields g ⟷^{∗}_{F}^{r} f̃⟷^{∗}_{F}^{r} f and we are done.

It remains to show that right reduction using F is confluent. Suppose there is a polynomial g having two distinct normal forms with respect to F, say p_{1} and p_{2}. Let t be the largest term on which p_{1} and p_{2} differ and let α_{1} respectively α_{2} be the coefficients of t in p_{1} respectively p_{2}. Since p_{1} − p_{2} ∈ ideal_{r}(F) we know p_{1} − p_{2} ⟶^{∗}_{F}^{r} 0 and α_{1} − α_{2} ∈ ideal_{r}^{R}(C_{F} (t)), and C_{F} (t) is a right Gröbner basis. Hence, α_{1} ⟺^{∗}_{C_{F} (t)} α_{2}, and either α_{1} or α_{2} must be reducible using C_{F} (t), i.e., not both p_{1} and p_{2} can be in normal form with respect to F, contradicting our assumption.

2 ⟹ 3 : This follows from the fact that all g- and m-polynomials belong to the right ideal generated by F.

3 ⟹ 1 : We have to show that every element g ∈ ideal_{r}(F) ∖ {0} is right reducible to zero using F. Remember that for h ∈ ideal_{r}(F), h ⟶_{F}^{r} h′ implies h′ ∈ ideal_{r}(F). Thus, as ⟶_{F}^{r} is Noetherian since F is finite, it suffices to show that every g ∈ ideal_{r}(F) ∖ {0} is right reducible using F. This will be done by assuming the contrary. Let g = ∑_{j=1}^{m} f_{j} ∗(γ_{j} ·w_{j}) with γ_{j} ∈ R^{∗}, f_{j} ∈ F, w_{j} ∈ M be a representation of a polynomial g ∈ ideal_{r}(F) ∖ {0}. As F is saturated, we can always assume HT(f_{i} ∗ (γ_{i} · w_{i})) = HT(f_{i}) ∘ w_{i}. Depending on this representation of g and the well-founded total ordering ⪰ on M we define the critical term of g to be t = max{HT(f_{j}) ∘ w_{j} | j ∈ {1, … m}}. We call another representation of g “smaller” if for the corresponding critical term t̃ we have t̃ ≺ t. Let us assume that our polynomial g is not right reducible by F and that our representation of g is a minimal one with respect to t. We have to distinguish two cases. In case t ≠ HT(g), without loss of generality assume that t occurs in the first k products of our representation. Hence, we have HT(f_{i}) ∘ w_{i} = t for each 1 ≤ i ≤ k and ∑_{i=1}^{k} HC(f_{i}) · γ_{i} = 0, i.e., the vector (γ_{1}, …, γ_{k}) is in the right module M = {(α_{1}, …, α_{k}) | ∑_{i=1}^{k} HC(f_{i}) · α_{i} = 0}. By our assumption this module has been considered when generating the mpolynomials for {f_{1}, …, f_{k}} and t. Let the set B = {A_{i} = (α_{i,1}, …, α_{i,k}) | i ∈ I} be a basis of M. Without loss of generality, we assume that there are A_{1}, …, A_{n} ∈ B such that for 1 ≤ i ≤ k we have γ_{i} = ∑_{j=1}^{n} α_{j,i} · δ_{j} for some δ_{j} ∈ R. Thus, we get

\begin{aligned}∑_{i=1}^{k} f_{i} ∗ (γ_{i} · w_{i}) & = ∑_{i=1}^{k} f_{i} ∗ ((∑_{j=1}^{n} α_{j,i} · δ_{j}) · w_{i}) \\ & = ∑_{j=1}^{n}(∑_{i=1}^{k} f_{i} ∗ (α_{j,i} · w_{i})) · δ_{j} \end{aligned}  (1)

Taking a closer look at the last sum of these transformations in (1), we see that we can express the sum of the first k elements of our representation of g by a sum of m-polynomials. Since these m-polynomials belonging to {f_{1}, …, f_{k}} and t all have head terms smaller than t and are right reducible to zero using F, we get a new representation of g with a critical term smaller than t, contradicting our assumption that our chosen representation was minimal.

In case t = HT(g), we know that there exists a finite subset P ⊆ F such that HC(g) ∈ ideal^{R}({HC(p) | p ∈ P }), and as this ideal is finitely generated it has a right Gröbner basis, say G_{P}. Then HC(g) is reducible by an element α ∈ G_{P}. By our assumption, now α · t is head monomial of a g-polynomial corresponding to P and t and since this g-polynomial is right reducible to zero using F, in particular there exist polynomials f_{1}, …, f_{k} ∈ F involved in the reduction of α · t such that α ⟹_{HC(f_{1})} α_{1} ⟹_{HC(f_{2})} … ⟹_{HC(f_{k})} 0. We will now show that this implies that HM(g) is right reducible using F, by induction on k. For k = 1 we find HC(g) ⟹_{α} and α ⟹_{HC(f_{1})} 0, and hence Axiom (A4) implies HC(g) ⟹_{HC(f_{1})}, i.e., g is right reducible at HM(g) using f_{1} ∈ F. Now let k > 1. Then by Axiom (A4), HC(g) is either reducible by HC(f_{1}) or by α_{1}. This again gives us a contradiction, as either g is right reducible at HM(g) using f_{1} ∈ F or the induction hypothesis can be applied to α_{1} and f_{2}, …, f_{k}.

□ ✓

We have already determined when for a finite set of polynomials P and a term t the respective sets of g- and m-polynomials described in Definition 6.4 are finite. However, these conditions do not imply that the set of polynomials to be tested in Theorem 6.6 (3) will be finite due to the fact that in general infinitely many terms t have to be considered (compare Definition 6.5). Hence it is important to find a localization to crucial term overlaps, similar to the case of s-polynomials in commutative polynomial rings where only the least common multiple of the head terms has to be considered. In our setting, the key idea are suitable weakenings of the reduction relation: recall that for two reductions ⟶^{1}⊆⟶^{2} with ⟷^{∗}^{1} = ⟷^{∗}^{2} the confluence of ⟶^{1} will imply the confluence of ⟶^{2}. To identify such weaker reduction relations we have to take a closer look at the representations of the monoid elements. Remember that monoids can be presented by string rewriting systems (see the book of Book and Otto [4] for more details on string rewriting systems). Henceforth, we will assume that M is presented by a finite convergent string rewriting system such that the ordering on M is compatible with the completion ordering of the string rewriting system. This implies that the monoid elements are the irreducible words, the ordering on M is compatible with concatenation, and multiplication can be done by normal form computation. We can give the following syntactical weakening of right reduction.

Definition 6.7. Let p, f be two non-zero polynomials in R[M]. We say f prefix reduces p to q at a monomial α · t of p in one step, denoted by p ⟶_{f}^{p} q, if

(a) HT(f)w ≡ t for some w ∈ M, i.e., HT(f) is a prefix of t as a word in the generators,

(b) α ⟹_{HC(f)} β, i.e. α = β + HC(f) · γ, γ ∈ R, and

(c) q = p − f ∗ (γ · w).

Then term overlaps correspond to common prefixes of words and in defining g- and m-polynomials we can restrict the attention to minimal such situations giving rise only to finitely many such candidates for a set F. This localization is possible because for prefixes and concatenation our ordering on M behaves admissible, i.e. t ≻ u and t∘w ≡ tw implies tw ≻ u∘w for t, u, w ∈ M. For more details see Reinert [18] and Madlener and Reinert [9, 12]. In substituting prefix saturation for saturation and prefix reduction for right reduction, Theorem 6.6 can be specialized to characterize prefix Gröbner bases, which are of course right Gröbner bases of the same right ideal.

Now, if (R, ⟹) is an effective reduction ring then addition and multiplication in R[M] as well as reduction as defined in Definition 6.7 are computable operations.

The existence of finite prefix Gröbner bases can be shown for the classes of finite, respectively free, monoids and the classes of finite, free, plain, respectively context-free, groups. Using different syntactical weakenings of right reduction also finitary results are gained for the class of polycyclic groups (which includes the Abelian and nilpotent groups). The details on these approaches are presented in Reinert [18] and Madlener and Reinert [9, 12]. Hence, all these monoid rings are indeed reduction rings.

It remains to determine when in fact these monoid and group rings are effective right reduction rings: We need that right Gröbner bases and representations of their elements in terms of the elements of the generating set are computable, and that it is possible to compute finite bases for right modules of solutions to linear homogeneous equations over R. With these assumptions the bases are computable in the special cases of monoids and groups mentioned above. In fact they can be computed using completion procedures based on resolving non-trivial g- and m-polynomials.

7. Conclusions

The aim of this paper was to show how, starting with a reduction ring, new reduction rings can be constructed using standard ring constructions such as quotients and sums and extensions to polynomial and monoid rings. This enables us to present many results known from the literature in a uniform setting. Other ring constructions such as skew-polynomial rings, solvable polynomial rings or Ore extensions could be studied in a similar fashion.

On the other hand, reduction relations in arbitrary rings fulfilling the Axioms (A1)–(A3) and (A4) will inherit similar properties resulting directly from the axioms. E.g., when applying the ring constructions of this paper they will yield similar natural reduction relations for the resulting rings. A well-known example is the free monoid ring (also called the non-commutative polynomial ring) where many properties of the reduction relation for commutative polynomial rings carry over, although of course finite Gröbner bases in general will no longer exist.

References

[1] T. Becker & V. Weispfenning, Gröbner Bases —A Computational Approach to Commutative Algebra, Springer Verlag, 1992.

[2] B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal, Doctoral Dissertation, Universität Innsbruck, 1965.

[3] B. Buchberger, A Critical-Pair/Completion Algorithm for Finitely Generated Ideals in Rings, in: Symposium “Rekursive Kombinatorik”, Münster (FRG), May 1983. Springer LNCS 171 (1984), 137–161.

[4] R. Book, and F. Otto, String-Rewriting Systems, Springer Verlag, 1993.

[5] A. Kandri-Rody and D. Kapur, Computing a Gröbner Basis of a Polynomial Ideal over a Euclidean Domain, Journal of Symbolic Computation 6 (1988), 37–57.

[6] D. Kapur and P. Narendran, Constructing a Gröbner Basis for a Polynomial Ring, in: J. Avenhaus, K. Madlener (eds): Summary in Proceedings of Combinatorial Algorithms in Algebraic Structures, Otzenhausen. Universität Kaiserslautern, 1985.

[7] A. Kandri-Rody and V. Weispfenning, Non-Commutative Gröbner Bases in Algebras of Solvable Type, Journal of Symbolic Computation 9 (1990), 1–26.

[8] K. Madlener, Existence and Construction of Gröbner Bases for Ideals in Reduction Rings, Working paper, Universität Kaiserslautern, 1986.

[9] K. Madlener and B. Reinert, Computing Gröbner Bases in Monoid and Group Rings, in: Proc. ISSAC’93, 1993, 254–263.

[10] K. Madlener and B. Reinert, String Rewriting and Gröbner Bases —A General Approach to Monoid and Group Rings, in: Proceedings of the Workshop on Symbolic Rewriting Techniques, Monte Verita, 1995, 127–180.

[11] K. Madlener and B. Reinert. Relating rewriting techniques on monoids and rings: Congruences on monoids and ideals in monoid rings, Theoretical Computer Science, 208 (1998), 3–31.

[12] K. Madlener and B. Reinert. A generalization of Gröbner basis algorithms to polycyclic group rings, Journal of Symbolic Computation, 25 (1998) 23–43.

[13] K. Madlener and B. Reinert. Gröbner bases in non-commutative reduction rings, in B. Buchberger and F. Winkler, editors, Gröbner Bases and Applications (Proc. of the Conference 33 Years of Gröbner Bases), volume 251 of London Mathematical Society Lecture Notes Series, 408–420, Cambridge University Press, 1998.

[14] H. M. Möller, H. M., On the Construction of Gröbner Bases Using Syzygies, Journal of Symbolic Computation 6 (1998), 345–359.

[15] F. Mora, Gröbner Bases for Non-Commutative Polynomial Rings, in: Proc. AAECC-3, Springer LNCS 229 (1985), 353–362.

[16] L. Pan, On the Gröbner Bases of Ideals in Polynomial Rings over a Principal Ideal Domain, University of California, Santa Barbara, Department of Mathematics, Internal Manuscript, 1985.

[17] M. Pesch, Gröbner Bases in Skew Polynomial Rings, Doctoral Dissertation, Universität Passau, 1997.

[18] B. Reinert, On Gröbner Bases in Monoid and Group Rings, Doctoral Dissertation, Universität Kaiserslautern, 1995.

[19] S. Stifter, A Generalization of Reduction Rings, Journal of Symbolic Computation 4 (1987), 351–364.

[20] V. Weispfenning, Gröbner Basis for Polynomial Ideals over Commutative Regular Rings, in: Proc. EUROCAL’87, Springer LNCS 378 (1987), 336–347.

(Recibido en octubre de 1998)

Fachbereich Informatik Universität Kaiserslautern

67663 Kaiserslautern, Germany

madlener@informatik.uni-kl.de reinert@informatik.uni-kl.de