MINIMAL SETS OF CRITICAL PAIRS

MASSIMO CABOARA Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, I-16146 Genova, Italy E-mail: caboara@dima.unige.it

MARTIN KREUZER Fakultät für Mathematik, Universität Regensburg, D-93040 Regensburg, Germany E-mail: martin.kreuzer@mathematik.uni-regensburg.de

LORENZO ROBBIANO Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, I-16146 Genova, Italy E-mail: robbiano@dima.unige.it

In the computation of a Gröbner basis using Buchberger’s algorithm, a key issue for improving the efficiency is to produce good techniques for avoiding as many unnecessary critical pairs as possible. A good solution would be to avoid all non-minimal critical pairs, and hence to process only a minimal set of generators of the module generated by the critical pairs. In this paper we show how to obtain that desired solution while retaining the same efficiency as with the classical implementation. As a consequence, we get a new Optimized Buchberger Algorithm.

1 Introduction

Ever since practical implementations of Buchberger’s famous algorithm for computing Gröbner bases ^{1} became feasible, it has been clear that, in order to improve the efficiency of this algorithm, one needs to avoid the treatment of as many critical pairs as possible. B. Buchberger ^{2} studied this problem for the first time, and later ^{3}^{,}^{5} his results were substantially improved and expanded. Nevertheless, Gebauer and Möller ^{5} showed that their method did not always produce a minimal set of generators of the module generated by the critical pairs. However, their method was very efficient and yielded an almost minimal set of critical pairs. Since then, many kinds of optimizations of Buchberger’s algorithm have been found, in particular by implementators of computer algebra systems. But the problem of efficiently minimalizing the critical pairs has gone largely unnoticed and seems to be overdue for a solution. Indeed, that is the main objective of this paper.

To achieve our goal, we proceed as follows. Foremost, we need a detailed understanding of the entire process of computing Gröbner bases, in particular in the homogeneous case. A fine-tuned algorithm for simultaneously computing a Gröbner basis and a minimal system of generators contained in it leads to a new result on the minimalization of a reduced Gröbner basis. Then this result is applied to critical pairs, using the fact that we show how the old criteria M(i, j) and F (i, j) of Gebauer and Möller ^{5} yield a reduced Gröbner basis of the module of syzygies of the leading term module. Besides, when applied to this special case, the algorithm admits many subtle optimizations. In the end, we really achieve the goal of minimalizing the critical pairs efficiently.

Now, why do we think that what we achieved is important?

The first reason is theoretical curiosity. It is common knowledge among the implementators of Buchberger’s algorithm that the criteria of Gebauer and Möller almost produce a minimal set of critical pairs. We wanted to see whether that “vox populi” is really true. Of course one could use a standard minimalization processes to produce minimal sets of critical pairs, but this method could only handle small examples. Instead, we observed that, after applying the criteria of Gebauer and Möller, a reduced Gröbner basis of the module of critical pairs is obtained. Then we were able to see the difference between the reduced Gröbner basis and a minimal set of generators of the critical pairs, and how this difference depends on the size of the example.

Another important reason is that we wanted to be able to compute a minimal set of generators of the module of critical pairs with the same efficiency as the usual application of the Gebauer-Möller criteria. And we wanted to do it while computing a Gröbner basis, so that we can replace the Gebauer-Möller criteria by our procedure. As we show in the last sections, we achieved this goal.

A third reason is that our results hold in full generality, namely for Gröbner bases of modules over positively (multi-) graded rings. Other optimizations of Buchberger’s algorithm, for instance ideas using trivial syzygies, do not hold in this generality. Moreover, we would like to point out that the pairs we discard are truly useless, wheras for instance pairs between elements in a reduced Gröbner bases which reduce to zero can still be useful for the computation of syzygies.

Finally, the readers should know that the basic terminology is taken from the book of the second and third authors^{6}.

2 Positive Gradings

Since we are interested in optimizing the Buchberger Algorithm in the homogeneous case, we start by saying which gradings we consider. From now on let K always be a field and P = K[x_{1}, …, x_{n}] a polynomial ring over K. Moreover, let W ∈ Mat_{m,n}(ℤ) be an m × n-matrix with integer entries.

Definition 2.1. There exists exactly one ℤ^{m}-grading on P such that every term t = x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} is homogeneous of degree deg_{W} (t) = W · (α_{1}, …, α_{n})^{tr}. We say that P is (multi-) graded by W. The matrix W is called the weight matrix and its rows are called the weight vectors.

For instance, the grading on P by W = (1, …, 1) is the standard grading. For every d ∈ ℤ^{m}, the homogeneous component of degree d of P is P_{W,d} = ⊕_{deg_{W} (t)=d} K · t. Given δ_{1}, …, δ_{r} ∈ ℤ^{m}, the graded free P -module ⊕_{i=1}^{r} P (−δ_{i}) inherits a ℤ^{m}-grading from P in the natural way. Again we say that ⊕_{i=1}^{r} P (−δ_{i}) is graded by W. In order to be able to use these gradings in our algorithms, we need a positivity assumption.

Definition 2.2. The grading on P by W is called positive if rk(W) = m, if no column of W is zero, and if the first non-zero entry in each column of W is positive.

If P is positively graded by W, we have P_{W,0} = K and dim_{K}(M_{W,d}) < ∞ for every finitely generated graded P -module M and every d ∈ ℤ^{m}. Moreover, the graded version of Nakayama’s Lemma holds and we have the following characterization (see Sect. 1.7, 4.1 and 4.2 of Kreuzer – Robbiano^{6}^{,}^{7}).

Proposition 2.3 Let P be graded by W, where W has ℤ-linearly independent rows and non-zero columns. Then the following conditions are equivalent.

a) The grading on P given by W is positive.

b) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a well-ordering, i.e. every non-empty subset of Γ has a minimal element with respect to Lex.

c) The restriction of Lex to the monoid Γ = {d ∈ ℤ^{m} | P_{W,d} ≠ 0} is a term ordering, i.e. every element d ∈ Γ satisfies d >_{Lex} 0.

d) There exists a term ordering τ on 𝕋^{n} which is compatible with deg_{W}.

e) There exists a module term ordering σ on 𝕋^{n}⟨e_{1}, …, e_{r}⟩ which is compatible with the grading given by W.

3 Truncated Gröbner Bases

From now on we shall always assume that P = K[x_{1}, …, x_{n}] is a polynomial ring over a field K which is positively graded by a matrix W ∈ Mat_{m,n}(ℤ). The following notation will prove to be convenient. Given a subset S of a graded P -module and a multidegree d ∈ ℤ^{m}, we let S_{≤d} = {v ∈ S | v homogeneous, deg_{W} (v) ≤_{Lex} d} and S_{d} = {v ∈ S | v homogeneous, deg_{W} (v) = d}.

Definition 3.1. Assume that G = {g_{1}, …, g_{s}} is a homogeneous σ-Gröbner basis of a graded P -module M, and let d ∈ ℤ^{m}. Then the set G_{≤d} is called a d-truncated Gröbner basis of M, or a Gröbner basis of M which has been truncated in degree d.

Truncated Gröbner bases have a characterization which is analogous to the Buchberger criterion in the usual case. To formulate this precisely, we need to explain what we mean by the degree of a critical pair.

Let M be a graded submodule of a graded free P -module ⊕_{i=1}^{r} P (−δ_{i}), and let g_{1}, …, g_{s} ∈ M\{0} be homogeneous elements of degree d_{i} = deg_{W} (g_{i}). Moreover, for i = 1, …, s, we write LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}}, where c_{i} ∈ K \ {0}, where t_{i} ∈ 𝕋^{n}, and where γ_{i} ∈ {1, …, r}. Then we let 𝔹 = {(i, j) | 1 ≤ i < j ≤ s and γ_{i} = γ_{j}} and choose (i, j) ∈ 𝔹. The element σ_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} ε_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} ε_{j} is a syzygy of the pair (LM_{σ}(g_{i}), LM_{σ}(g_{j})). Clearly, it is a homogeneous element of degree deg_{W} (σ_{ij}) = deg_{W} (lcm(t_{i}, t_{j})) + δ_{γ_{i}} of the graded free P -module ⊕_{k=1}^{s} P (−d_{k}) whose canonical basis {ε_{1}, …, ε_{s}} satisfies deg_{W} (ε_{k}) = d_{k} for k = 1, …, s. This degree equals the degree of the corresponding S-vector S_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} g_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} g_{j} in the graded P - module ⊕_{k=1}^{r} P (−δ_{k}). The elements of the set 𝔹 are called the critical pairs of (g_{1}, …, g_{s}). For every critical pair (i, j) ∈ 𝔹, we have deg_{W} (σ_{ij}) ≥_{Lex} max{d_{i}, d_{j}} for all (i, j) ∈ 𝔹.

The following characterization of truncated Gröbner bases can be shown using Props. 2.3.10 and 2.3.12 of Kreuzer – Robbiano^{6}. Proposition 3.2 (Characterization of Truncated Gröbner Bases) Let P be positively graded by W ∈ Mat_{m,n}(ℤ), let G = {g_{1}, …, g_{s}} be a set of non-zero homogeneous vectors which generates a graded submodule M of ⊕_{i=1}^{r} P (−δ_{i}), and let d ∈ ℤ^{m}. Then the following conditions are equivalent.

a) The set G_{≤d} is a d-truncated σ-Gröbner basis of M.

b) For every homogeneous element v ∈ M_{≤d} \ {0}, we have LT_{σ}(v) ∈ ⟨LT_{σ}(g) | g ∈ G_{≤d}⟩.

c) For all pairs (i, j) ∈ 𝔹_{≤d}, we have NR_{σ,G_{≤d}}(S_{ij}) = 0, where G_{≤d} is the tuple obtained from G = (g_{1}, …, g_{s}) by deleting the elements of degree greater than d. As a consequence, we obtain our first important technical tool.

Corollary 3.3 Let d ∈ ℤ^{m}, let the elements of G = (g_{1}, …, g_{s}) be a dtruncated σ-Gröbner basis of M, and let g_{s+1} ∈ ⊕_{i=1}^{r} P (−δ_{i}) be a homogeneous element of degree d such that LT_{σ}(g_{s+1}) ∉ ⟨LT_{σ}(g_{1}), …, LT_{σ}(g_{s})⟩. Then {g_{1}, …, g_{s+1}} is a d-truncated Gröbner basis of M + ⟨g_{s+1}⟩.

Recall that the Lemma of Nakayama guarantees that all minimal systems of generators have the same length in the positively graded situation. Using a clever induction argument based on this lemma, we can also show the following useful result. Corollary 3.4 Let {g_{1}, …, g_{s}} ⊆ M \ {0} be a minimal homogeneous system of generators of M, and let g_{s+1} ∈ ⊕_{i=1}^{r} P (−δ_{i}) \ M be a homogeneous vector such that deg_{W} (g_{s+1}) ≥_{σ} max{deg_{W} (g_{i}) | i = 1, …, s}. Then {g_{1}, …, g_{s+1}} is a minimal system of generators of the module M + ⟨g_{s+1}⟩. In particular, we have μ(M + ⟨g_{s+1}⟩) = μ(M) + 1.

4 The Homogeneous Buchberger Algorithm

Now we let δ_{1}, …, δ_{r} ∈ ℤ^{m}, and we let M be a graded submodule of ⊕_{i=1}^{r} P (−δ_{i}) which is generated by a tuple of non-zero homogeneous vectors V = (v_{1}, …, v_{s}). Furthermore, we choose a module term ordering σ on the monomodule of terms 𝕋^{n}⟨e_{1}, …, e_{r}⟩ in ⊕_{i=1}^{r} P (−δ_{i}).

The homogeneous version of Buchberger’s well-known algorithm computes a homogeneous σ-Gröbner basis of M degree-by-degree. To ease the notation, we shall use the following convention: whenever a vector g_{i} appears, we write LM_{σ}(g_{i}) = c_{i}t_{i}e_{γ_{i}}, where c_{i} ∈ K \ {0}, where t_{i} ∈ 𝕋^{n}, and where γ_{i} ∈ \{1, …, r\}. For two indices i, j such that γ_{i} = γ_{j}, we let σ_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} e_{i} −

\frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} e_{j} and S_{ij} = \frac{lcm(t_{i},t_{j})}{c_{i}t_{i}} g_{i} − \frac{lcm(t_{i},t_{j})}{c_{j}t_{j}} g_{j}.

Theorem 4.1 (The Homogeneous Buchberger Algorithm) Consider the following sequence of instructions.

1) Let B = ∅, W = V, G = ∅, and let s′ be the number of elements in G.

2) Let d be the smallest degree with respect to Lex of an element in W or in B. Form the subtuple W_{d} of elements of degree d in W and the subset B_{d} = {(i, j) ∈ B | deg_{W} (σ_{ij}) = d}, and delete their entries from W and B, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, choose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute the S-vector S_{ij} and its normal remainder S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to the tuple G, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose a vector v ∈ W_{d} and remove it from W_{d}.

7) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 6).

8) Increase s′ by one, append g_{s′} = v′ to the tuple G, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9) If W = ∅ and B = ∅, return the tuple G and stop. Otherwise, continue with step 2).

This is an algorithm which returns an ordered tuple G = (g_{1}, …, g_{s′}) whose elements are a homogeneous σ-Gröbner basis of M.

The proof of this theorem is standard Computer Algebra and will for instance be contained in Volume 2 of Kreuzer – Robbiano^{7}. The following corollary computes a minimal system of generators of M contained in the given one while computing a Gröbner basis. For the proof we again refer to Kreuzer – Robbiano^{7}, Sect. 4.3. Corollary 4.2 (Buchberger Algorithm with Minimalization) In the situation of the theorem, we replace steps 1), 8), and 9) by the following instructions. 1’) Let B = ∅, W = V, G = ∅, let s′ be the number of elements in G, and let

V_{min} = ∅. 8’) Increase s′ by one, append g_{s′} = v′ to the tuple G, append v to the tu-

ple V_{min}, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to the set B. Continue with step 6).

9’) If W = ∅ and B = ∅, return the pair (G, V_{min}) and stop. Otherwise,

continue with step 2). Then the resulting set of instructions defines an algorithm. It returns a pair (G, V_{min}) such that G is an ordered tuple of homogeneous vectors which are a σ-Gröbner basis of M, and V_{min} is a subtuple of V of homogeneous vectors which are a minimal system of generators of M.

In addition, the claim that V_{min} contains a minimal system of generators of M holds even if we stop the algorithm after steps 3) to 8) have finished treating elements of degree d_{max} = max_{Lex}{deg_{W} (v_{1}), …, deg_{W} (v_{s})}.

At this point we are ready to apply the Buchberger Algorithm with Minimalization 4.2 to a reduced Gröbner basis and improve it significantly in that case.

Theorem 4.3 (Minimalization of a Reduced Gröbner Basis) In the situation of Theorem 4.1, let V = (v_{1}, …, v_{s}) be the reduced σ-Gröbner basis of M. Consider the following instructions.

1) Let s′ = 0, B = ∅, W = (v_{1}, …, v_{s}), G = ∅, and V_{min} = ∅.

2) Let d be the smallest degree with respect to Lex of an element of W or an element of {σ_{ij} | (i, j) ∈ B}. Form W_{d} and B_{d} and delete their entries from W and B, respectively.

3) If B_{d} = ∅, continue with step 6). Otherwise, choose a pair (i, j) ∈ B_{d} and remove it from B_{d}.

4) Compute S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, continue with step 3).

5) Increase s′ by one, append g_{s′} = S′_{ij} to G, append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B, and continue with step 3).

6) If W_{d} = ∅, continue with step 9). Otherwise, choose v ∈ W_{d} and remove it from W_{d}.

7) If LT_{σ}(v) = LT_{σ}(g) for some g ∈ G, then replace the element g in G by v. Continue with step 6).

8) Increase s′ by one, append g_{s′} = v to G and V_{min}, and append {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}} to B. Continue with step 6).

9) If W = ∅ and B = ∅, return V_{min} and stop. Otherwise, continue with step 2).

This is an algorithm which computes a subtuple V_{min} of V such that V_{min} is a minimal system of generators of M.

5 Minimalizing the Critical Pairs

In this section we continue to use the assumptions and notation of the previous section. In the Homogeneous Buchberger Algorithm 4.1, instead of treating all critical pairs in Σ = {σ_{ij} | (i, j) ∈ ℤ}, it is enough to treat those pairs corresponding to a subset Θ ⊆ Σ which is a minimal system of generators of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}). In order to find Θ, we first show that two of the rules given by Gebauer and Möller ^{5} produce a minimal Gröbner basis of Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}) contained in Σ. From this we find Θ by applying Theorem 4.3. We start by modifying Definition 3.1.1. of Kreuzer – Robbiano^{6} slightly.

Definition 5.1. On the monomodule of terms 𝕋^{n}⟨e_{1}, …, e_{s}⟩ in ⊕_{i=1}^{s} P (−d_{i}) we define a relation τ by letting

t e_{i} ≥_{τ} t′ e_{j} ⟺ \{ \begin{matrix}LT_{σ}(t t_{i} e_{γ_{i}}) >_{σ} LT_{σ}(t′ t_{j} e_{γ_{j}}), or \\ LT_{σ}(t t_{i} e_{γ_{i}}) = LT_{σ}(t′ t_{j} e_{γ_{j}}) and i ≥ j \end{matrix}

for t, t′ ∈ 𝕋^{n} and i, j ∈ {1, …, s}. It is easy to check that τ is a module term ordering. It is called the term ordering induced by G = (t_{1}e_{γ_{1}}, …, t_{s}e_{γ_{s}}) and σ.

It is well-known that the set Σ is a τ-Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}). Using our notation, the main result of Gebauer and Möller^{5} reads as follows. Proposition 5.2 Consider the following instructions. Rule 1. Delete in Σ all elements σ_{jk} such that there exists an index i ∈

{1, …, j − 1} such that t_{ki} divides t_{kj}. Call the resulting set Σ′.

Rule 2. Delete in Σ′ all elements σ_{ik} such that there exists an index j ∈ {i + 1, …, k − 1} such that t_{kj} properly divides t_{ki}. Call the resulting

set Σ′′.

Rule 3. Delete in Σ′′ all elements σ_{ij} such that there exists an index k ∈ {j+1, …, s} such that t_{ik} properly divides t_{ij} and t_{jk} properly divides t_{ji}. Call the resulting set Σ′′′. Then the set Σ′′′ still generates Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

Remark 5.3. Let us interpret the previous proposition in another way. For 1 ≤ i < j ≤ s such that γ_{i} = γ_{j}, we have LT_{τ} (σ_{ij}) = t_{ji}e_{j}. Hence Rules 1 and 2 can be restated as follows. Rule 1’. Delete in Σ all elements σ_{ij} such that there exists an element σ_{i′j}

such that LT_{τ} (σ_{ij}) is a proper multiple of LT_{τ} (σ_{i′j}).

Rule 2’. If, among the remaining elements, there are elements σ_{ij}, σ_{i′j} such that LT_{τ} (σ_{ij}) = LT_{τ} (σ_{i′j}), then delete the one having the larger index max{i, i′}.

From Rules 1’ and 2’ it follows that the set Σ′′ is a minimal τ-Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

In general, Σ′′ is not a minimal system of generators of the P -module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}), as our next example shows. (For another example, see Gebauer and Möller^{5}.)

Example 5.4. Let P = ℚ[x, y, z] be standard graded (i.e. graded by W = (1, …, 1)), let r = 1, s = 4 and t_{1} = x^{3}z^{2}, t_{2} = x^{3}y^{4}, t_{3} = y^{5}z^{2}, t_{4} = x^{2}y^{5}z. Then we get σ_{12} = y^{4}e_{1} − z^{2}e_{2}, σ_{13} = y^{5}e_{1} − x^{3}e_{3}, σ_{14} = y^{5}e_{1} − xze_{4}, σ_{23} = yz^{2}e_{2} − x^{3}e_{3}, σ_{24} = yze_{2} − xe_{4}, and σ_{34} = x^{2}e_{3} − ze_{4}. By applying Rules 1 and 2, we get the minimal τ-Gröbner basis Σ′′ = {σ_{12}, σ_{24}, σ_{34}, σ_{13}} of Syz_{P} (t_{1}, t_{2}, t_{3}, t_{4}), since LT_{τ} (σ_{23}) = LT_{τ} (σ_{13}) and LT_{τ} (σ_{14}) = z ·LT_{τ} (σ_{24}). Now we use Rule 3 and find Σ′′′ = Σ′′, but Σ′′′ is not a minimal system of generators of Syz_{P} (t_{1}, t_{2}, t_{3}, t_{4}), since σ_{13} = yσ_{12} + zσ_{24} − xσ_{34}.

Before continuing, we mention one important property of the set Σ′′. Proposition 5.5 The set Σ̃ = {−c_{j} ·σ_{ij} | σ_{ij} ∈ Σ′′} is the reduced τ-Gröbner basis of the module Syz_{P} (c_{1}t_{1}e_{γ_{1}}, …, c_{s}t_{s}e_{γ_{s}}).

Remark 5.6. When we apply the algorithm of Theorem 4.3 to the set Σ̃, we make the following observations.

A pair of pairs, i.e. a critical pair between two elements σ_{ij}, σ_{i′j′} yields an S-vector S_{((i,j),(i′,j′))} = c t σ_{ij} − c′ t′ σ_{i′j′} such that c, c′ ∈ K and t, t′ ∈ 𝕋^{n} and j = j′, since the two leading terms have to cancel. Without loss of generality, let i < i′. The result is of the form c̃t̃σ_{ii′} for some c̃ ∈ K and t̃ ∈ 𝕋^{n}. The degree of such a pair of pairs is deg_{W} (S_{((i,j),(i′,j))}) = deg_{W} (t) + deg_{W} (σ_{ij}) = deg_{W} (\frac{lcm(t_{i},t_{i′} ,t_{j})}{t_{j}}) + deg_{W} (e_{j}) = deg_{W} (lcm(t_{i}, t_{i′}, t_{j})) + δ_{γ_{j}}.

During the course of the algorithm, a new Gröbner basis element can only be obtained if t̃= 1. This is equivalent to gcd(t_{ij}, t_{i′j}) = 1.

Based on these results, we are now ready to optimize the computation of a minimal set of generators of Syz_{P} (LM_{σ}(G)). To ease the notation, we shall minimalize the set Σ′′ instead of Σ̃. Proposition 5.7 (Minimalization of the Critical Pairs) Let Σ′′ be the τ-Gröbner basis of Syz_{P} (LM_{σ}(G)) introduced above. Consider the following instructions.

1) Let B^{∗} = ∅, W = Σ′′, A = ∅, and Θ = ∅.

2) For all σ_{ij}, σ_{i′j} ∈ Σ′′ such that 1 ≤ i < i′ < j ≤ s, form the pair of pairs S_{((i,j),(i′,j))} = t̃σ_{ii′}, where t̃∈ 𝕋^{n}. If t̃= 1, append σ_{ii′} to B^{∗}.

3) Let d be the smallest degree with respect to Lex of an element of W or B^{∗}. Form W_{d} and B_{d}^{∗}, and delete their entries from W and B^{∗}, respectively.

4) If B_{d}^{∗} = ∅, continue with step 11). Otherwise, choose an element σ_{ij} ∈ B_{d}^{∗} and remove it from B_{d}^{∗}.

5) If LT_{τ} (σ_{ij}) ∈ LT_{τ} (A_{d}), then continue with step 4).

6) If LT_{τ} (σ_{ij}) = LT_{τ} (σ_{i′j}) for some σ_{i′j} ∈ W_{d}, then remove the element σ_{i′j} from W_{d}, append it to A, and continue with step 4).

7) Find σ_{i′j} ∈ A_{<d} such that t_{ji} is a multiple of t_{ji′}. Then perform the head reduction step σ_{ij} ⟶^{σ_{i′j}} t̃σ_{kℓ}, where t̃ ∈ 𝕋^{n}, k = min{i, i′}, and ℓ = max{i, i′}. If t̃≠ 1, continue with step 4).

8) If LT_{τ} (σ_{kℓ}) ∈ LT_{τ} (A_{d}), then continue with step 4).

9) If LT_{τ} (σ_{kℓ}) = LT_{τ} (σ_{k′ℓ}) for some element σ_{k′ℓ} ∈ LT_{τ} (W_{d}), then remove the element σ_{k′ℓ} from W_{d}, append it to A, and continue with step 4).

10) If σ_{kℓ} ∈ B_{d}^{∗}, then delete σ_{kℓ} in B_{d}^{∗} and continue with step 7), applied to this element. Otherwise continue with step 4).

11) Append W_{d} to A and to Θ.

12) If W = ∅ and B^{∗} = ∅, return Θ and stop. Otherwise, continue with step 3).

This is an algorithm which computes a subset Θ ⊆ Σ′′ such that Θ is a minimal system of generators of Syz_{P} (LM_{σ}(G)).

Let us apply this algorithm in the situation of Example 5.4.

Example 5.8. Our task is to minimalize W = Σ′′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}}, where we have deg_{W} (σ_{12}) = 9, deg_{W} (σ_{13}) = 10, and deg_{W} (σ_{24}) = deg_{W} (σ_{34}) = 9.

In step 2), the algorithm constructs the set B^{∗}. The pair of pairs ((2, 4), (3, 4)) yields S_{((2,4),(3,4))} = zσ_{24} − xσ_{34} = −yz^{2}e_{2} + x^{3}e_{3} = σ_{23}, and this is the only element of B^{∗}. Notice that it has degree 10.

In step 3), the algorithm starts to operate in degree d = 9. Since B_{9}^{∗} = ∅, it appends σ_{12}, σ_{24}, and σ_{34} to A and Θ in step 11).

Next we process degree 10. In step 4), we choose σ_{23} ∈ B_{10}^{∗} and set B_{10}^{∗} = ∅. Then, in step 6), we find LT_{τ} (σ_{23}) = x^{3}e_{3} = LT_{τ} (σ_{13}), where σ_{13} ∈ W_{10}. Hence σ_{13} is removed from W_{10} and appended to A in step 6).

Thus we have B^{∗} = ∅ and W = ∅ now, and step 12) returns Θ = {σ_{12}, σ_{24}, σ_{34}}. We note that this is the correct answer, and there is an improvement over the application of Proposition 5.2 coming from the fact that in step 6) we merely check LT_{τ} (σ_{ij}) ∈ LT_{τ} (W_{d}) rather than σ_{ij} ∈ W_{d}.

The following example provides a case where it is actually necessary to do one head reduction step in 7) in order to find a previously undiscovered non-minimal critical pair.

Example 5.9. Let P = ℚ[x_{1}, …, x_{5}] be standard graded, let r = 1 and s = 4. The terms t_{1} = x_{2}^{2}x_{3}^{6}x_{4}x_{5}^{2}, t_{2} = x_{1}^{8}x_{2}x_{4}x_{5}^{4}, t_{3} = x_{1}^{8}x_{2}^{2}x_{3}^{6}, and t_{4} = x_{1}^{8}x_{3}^{6}x_{5}^{4} yield the critical pairs σ_{12} = x_{1}^{8}x_{5}^{2}e_{1}−x_{2}x_{3}^{6}e_{2}, σ_{13} = x_{1}^{8}e_{1}−x_{4}x_{5}^{2}e_{3}, σ_{14} = x_{1}^{8}x_{5}^{2}e_{1} − x_{2}^{2}x_{4}e_{4}, σ_{23} = x_{2}x_{3}^{6}e_{2} − x_{4}x_{5}^{4}e_{3}, σ_{24} = x_{3}^{6}e_{2} − x_{2}x_{4}e_{4}, and σ_{34} = x_{5}^{4}e_{3} − x_{2}^{2}e_{4}. Here steps 1) and 2) of Proposition 5.2 discard σ_{23} and σ_{14}, because LT_{τ} (σ_{23}) = x_{4}x_{5}^{4}e_{3} = x_{5}^{2} LT_{τ} (σ_{13}) and LT_{τ} (σ_{14}) = x_{2}^{2}x_{4}e_{4} = x_{2} LT_{τ} (σ_{24}). Thus we have Σ′′ = {σ_{12}, σ_{13}, σ_{24}, σ_{34}}. We note that deg_{W} (σ_{12}) = 21, deg_{W} (σ_{13}) = 19, and deg_{W} (σ_{24}) = deg_{W} (σ_{34}) = 20. But Σ′′ is not minimal, because we have σ_{12} = x_{5}^{2}σ_{13} − x_{2}σ_{24} + x_{4}σ_{34}.

Now we apply our algorithm. In step 2), we compute S_{((2,4),(3,4))} = x_{2}σ_{24} − x_{4}σ_{34} = x_{2}x_{3}^{6}e_{2} − x_{4}x_{5}^{4}e_{3} = σ_{23}. Thus σ_{23} is appended to B^{∗}. It has degree deg_{W} (σ_{23}) = 21. No further pairs of pairs are found.

In step 3), the algorihtm starts to operate in degree d = 19. We have B_{19}^{∗} = ∅ and W_{19} = (σ_{13}). Thus we append σ_{13} to A and Θ in step 11).

Next we pass to degree d = 20. We still have B_{20}^{∗} = ∅, but now we get W_{20} = (σ_{24}, σ_{34}). In step 11), σ_{24} and σ_{34} are put into A and Θ.

When we start processing degree d = 21, we have to choose σ_{23} ∈ B_{21}^{∗} and set B_{21}^{∗} = ∅ in step 4). The leading term LT_{τ} (σ_{23}) = x_{4}x_{5}^{4}e_{3} is not equal to one of the leading terms of the elements of A_{21} or W_{21}. But we can perform a head reduction step in 7), namely σ_{23} ⟶^{σ_{13}} −σ_{12}.

Here step 8) does not apply, but in step 9) we have LT_{τ} (σ_{12}) ∈ LT_{τ} (W_{21}). Thus we continue by removing σ_{12} from W_{21} and appending it to A.

Finally, we get B^{∗} = ∅ and W = ∅. The algorithm returns Θ = {σ_{13}, σ_{24}, σ_{34}}. As mentioned above, the non-minimal critical pair σ_{12} was discovered after one head reduction step in 7).

6 The Optimized Buchberger Algorithm

In this section we combine the results obtained so far. We continue to use the notation and conventions of the previous sections. In particular, we let P = K[x_{1}, …, x_{n}] be a polynomial ring over a field K which is positively graded by W ∈ Mat_{m,n}(ℤ), we let M be a graded submodule of a graded free P -module ⊕_{i=1}^{r}P (−δ_{i}) which is generated by a tuple of homogeneous vectors V = (v_{1}, …, v_{s}), and we let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩. Theorem 6.1 (The Optimized Buchberger Algorithm) Let P = K[x_{1}, …, x_{n}] be positively graded by W ∈ Mat_{m,n}(ℤ), let M be a graded submodule of a graded free P -module ⊕_{i=1}^{r} P (−δ_{i}), let V = (v_{1}, …, v_{s}) be a tuple of non-zero homogeneous vectors which generate M, and let σ be a module term ordering on 𝕋^{n}⟨e_{1}, …, e_{r}⟩. Consider the following sequence of instructions.

1) Let W = V, A = ∅, B = ∅, B^{∗} = ∅, G = ∅, and let s′ be the number of elements in G.

2) Let d be the smallest degree with respect to Lex of an element of W or {σ_{ij} | (i, j) ∈ B}. Form W_{d}, B_{d}, B_{d}^{∗} and delete their entries from W, B, and B^{∗}, respectively.

3) Apply MinPairs(A, B_{d}, B_{d}^{∗}).

4) If B_{d} = ∅, then continue with step 7). Otherwise, choose a pair (i, j) ∈ B_{d}, delete it from B_{d}, and append it to A.

5) Compute S_{ij} and S′_{ij} = NR_{σ,G}(S_{ij}). If S′_{ij} = 0, then continue with 4).

6) Increase s′ by one, append g_{s′} = S′_{ij} to G, perform Update(B, B^{∗}, g_{s′}), and continue with step 4).

7) If W_{d} = ∅ then continue with 10). Otherwise, choose v ∈ W_{d} and delete it in W_{d}.

8) Compute v′ = NR_{σ,G}(v). If v′ = 0, continue with step 7).

9) Increase s′ by one, append g_{s′} = v′ to G, perform Update(B, B^{∗}, g_{s′}), and then continue with step 7).

10) If W = ∅ and B = ∅, then return G and stop. Otherwise, continue with step 2).

Here the procedure Update(B, B^{∗}, g_{s′}) is defined as follows. U1) Form the set C = {(i, s′) | 1 ≤ i < s′, γ_{i} = γ_{s′}}.

U2) Delete from C all pairs (j, s′) for which there exists an index i ∈ {1, …, j − 1} such that t_{s′i} divides t_{s′j}.

U3) Delete from C all pairs (i, s′) for which there exists an index j ∈ {i + 1, …, s′ − 1} such that t_{s′j} properly divides t_{s′i}.

U4) Find in C all pairs (i, s′) and (j, s′) such that 1 ≤ i < j < s′ and such that gcd(t_{is′}, t_{js′}) = 1. For each of these, check if (i, j) is already contained in B^{∗} and append it if necessary.

U5) Append the elements of C to B and stop.

Furthermore, the procedure MinPairs(A, B_{d}, B_{d}^{∗}) is defined as follows. M1) If B_{d}^{∗} = ∅, then stop. Otherwise, choose a pair (i, j) in B_{d}^{∗} and remove

it from B_{d}^{∗}.

M2) If t_{ji} = t_{ji′} for some pair (i′, j) ∈ A, then continue with step M1).

M3) If t_{ji} = t_{ji′} for some pair (i′, j) ∈ B_{d}, then remove this pair from B_{d} and append it to A. Continue with step M1).

M4) Find (i′, j) ∈ A such that t_{ji} is a multiple of t_{ji′}. Let (k, ℓ) = (min{i, i′}, max{i, i′}). If gcd(t_{ij}, t_{i′j}) ≠ 1, then continue with M1).

M5) If t_{ℓk} = t_{ℓk′} for some pair (k′, ℓ) ∈ A, then continue with M1).

M6) If t_{ℓk} = t_{ℓk′} for some pair (k′, ℓ) ∈ B_{d}, then delete this pair in B_{d}, append it to A, and continue with M1).

M7) If (k, ℓ) ∈ B_{d}^{∗}, then delete (k, ℓ) in B_{d}^{∗} and continue with M4), applied to this pair.

M8) Continue with step M1).

Altogether, we obtain an algorithm which computes an ordered tuple G = {g_{1}, …, g_{s′}) whose elements form a homogeneous σ-Gröbner basis of M.

Moreover, the set of pairs which are treated at some time in steps 4) – 6) of the algorithm corresponds to a minimal system of generators of the module Syz_{P} (c_{1}t_{1}, …, c_{s′}t_{s′}).

Let us illustrate the performance of this algorithm by a simple example. It shows that cases like Example 5.4 occur naturally during actual Gröbner basis computations.

Example 6.2. Let P = ℚ[x, y, z] be standard graded, let r = 1, let σ = DegLex, and let M ⊆ P be the homogeneous ideal generated by v_{1} = x^{3}z^{2} + x^{2}y^{2}z, v_{2} = x^{3}y^{8}, and v_{3} = y^{10}z^{2}. Then the leading terms are t_{1} = x^{3}z^{2}, t_{2} = x^{3}y^{8}, and t_{3} = y^{10}z^{2}. Let us follow the steps of the Optimized Buchberger Algorithm.

The first degree is d = 5. Since B_{5} = ∅, the first actions are to choose v_{1} ∈ W_{5} in step 7) and append g_{1} = v_{1} to G in step 9). Then we continue with d = 11 and choose v_{2} ∈ W_{11} in step 7). Since v′ = NR_{σ,G}(v_{2}) = v_{2}, we appendg_{2} = v_{2} to G in step 9) and update the set of pairs. The result is B = {(1, 2)} and B^{∗} = ∅. Now we have to treat the degree d = 12. Notice that the degree of the pair (1, 2) is 13. Hence B_{12} = ∅ and we have to choose v_{3} ∈ W_{12} in step 7). Since v′ = NR_{σ,G}(v_{3}) = v_{3}, we appendg_{3} = v_{3} to G in step 9) and update the set of pairs. In step U1), we form C = {(1, 3), (2, 3)}. In step U2), we obtain t_{31} = x^{3} = t_{32}, and therefore (2, 3) is deleted in C. The result is B = {(1, 2), (1, 3)} and B^{∗} = ∅. This completes degree 12, and we continue with degree 13.

We choose the pair (1, 2) in step 4) and append it to A. Then we compute S_{12} = y^{8}g_{1} − z^{2}g_{2} = x^{2}y^{10}z and S′_{12} = NR_{σ,G}(S_{12}) = x^{2}y^{10}z. Thus we have a new Gröbner basis element g_{4} = x^{2}y^{10}z and need to update the pairs again. In step U1), we form C = {(1, 4), (2, 4), (3, 4)}. Step U2) does not apply, but in step U3) we remove the pair (1, 4) from C, since t_{42} = x properly divides t_{41} = xz. Now we check that t_{24} = y^{2}z properly divides t_{23} = y^{2}z^{2} and t_{34} = x^{2} properly divides t_{32} = x^{3}. Hence the pair (2, 3) is appended to B^{∗}.

At this point we have finished degree 13, and we have the situation A = {(1, 2)}, B = {(1, 3), (2, 4), (3, 4)}, B^{∗} = {(2, 3)}, G = {g_{1}, …, g_{4}}, and s′ = 4. The next degree is d = 14, where we have to deal with the pairs in B_{14} = {(2, 4), (3, 4)}. Since B_{14}^{∗} = ∅, we choose (2, 4) in step 4) and append it to A. Then we compute S_{24} = 0 and continue by choosing (3, 4) in B_{14} and adding it to A. Again S_{34} = 0, and degree 14 is finished.

Now we start degree 15 by performing MinPairs(A, B_{15}, B_{15}^{∗}), where A = {(1, 2), (2, 4), (3, 4)}, B_{15} = {(1, 3)} and B_{15}^{∗} = {(2, 3)}. In step M1), we choose (2, 3). In step M3), we discover t_{32} = x^{3} = t_{31}, where (3, 1) ∈ B_{15}. Hence (1, 3) is deleted in B_{15} and appended to A. Then the procedure is finished, and the facts that B_{15} = ∅ as well as W_{15} = ∅ allow us to return G and stop.

As in Example 5.4, we have found one useless pair, namely the pair (1, 3) in degree 15, which would not have been discovered by the Gebauer-Möller Installation, and which we were able to discard by a simple combinatorial check.

Remark 6.3. Let us discuss the efficiency of the algorithm of Theorem 6.1.

a) When we compare this algorithm with the Gebauer-Möller installation, we see that Rules 1) and 2) correspond exactly to steps U2) and U3). However, Rule 3) is not performed by Update(…), but by step M3) of MinPairs(…). In fact, step M3) gets rid of more pairs, because Rule 3) requires (i, j) ∈ B_{d}^{∗} ∩ B_{d}, whereas we only need a pair (i, j) ∈ B_{d}^{∗} such that LT_{τ} (σ_{ij}) = LT_{τ} (σ_{i′j}) for some (i′, j) ∈ B_{d}.

b) A potential drawback of our approach is that the number of pairs of pairs considered in step U4) is quadratic in the number of elements of C surviving steps U2) and U3). But that number is usually fairly small. Hence the cost of U4) and the cardinality of B^{∗} tend to be rather small. On the other hand, we do not need to check Rule 3 for all elements of the list B which is usually rather long. Our experiments suggest that, on average, the overhead of the two approaches is comparable.

c) Our procedure MinPairs(…) is very efficient in treating the elements of B_{d}^{∗}. Each time we loop through steps M2) – M8), we delete one pair in B_{d}^{∗}, and B_{d}^{∗} is never enlarged. In practice, we find that most superfluous pairs are cancelled by steps U2) and U3) and that the lists B_{d}^{∗} are generally small. Hence our algorithm harnesses the full power and efficiency of the Gebauer-Möller installation, while it simultaneously kills all unnecessary pairs at a comparatively small cost.

7 Experimental Data

Experimental data showing the efficiency of the Optimized Buchberger Algorithm will be presented in the full paper.

References

1. B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal (Ph.D. Thesis, Universität Innsbruck, 1965).

2. B. Buchberger, A criterion for detecting unnecessary reductions in the construction of Groebner bases, Proc. EUROSAM 79, Springer LNCS 72, 3–21 (1979).

3. B. Buchberger, Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory, in Multidimensional Systems Theory, ed. N.K. Bose (D. Reidel Publ. Comp., Dordrecht, 1985)

4. CoCoA, a system for Computing in Commutative Algebra, available via

anonymous ftp from cocoa.dima.unige.it

5. R. Gebauer and H.M. Möller, On an installation of Buchberger’s algorithm, J. Symb. Comput. 6, 257–286 (1987).

6. M. Kreuzer and L. Robbiano, Computational Commutative Algebra 1 (Springer, Heidelberg, 2000).

7. M. Kreuzer and L. Robbiano, Computational Commutative Algebra 2 (Springer, Heidelberg, in preparation).