§1. Admissible Orderings  Lecture XII  Page 1

Lecture XII Gröbner Bases

The subject of Gröbner bases or standard bases has generated considerable recent interest. Hironaka (Thesis, Harvard 1963) introduced the concept of standard bases for ideals in the ring of power series; independently, Buchberger (Thesis, Innsbruck 1965) gave an algorithm to construct a rather similar notion in polynomial rings. Buchberger coined the name Gröbner bases and popularized it [5]. Ideas germane to Gröbner bases appeared independently in the work of numerous authors including Richmond, Sims, Spear, Trinks and Zacharias. Gröbner bases are special generators for ideals with amiable computational properties. Many problems in polynomial algebra can be solved using such bases. The basic algorithm to construct such bases (in polynomial rings over a field) can be viewed as a simultaneous generalization of the Euclidean algorithm (for two univariate polynomials) and Gaussian elimination (for a system of linear multivariate polynomials). In the term rewriting literature, the algorithm is a special case of the Knuth-Bendix procedure. It is related to the “straightening law” of invariant theory and to the Wu-Ritt procedure (see [16]). These connections give a hint of the richness of these ideas. Generalizations and extensions of Gröbner bases to more general rings have been studied. This is only a brief introduction, as there are many extensions of these ideas (Gröbner bases for integer polynomials, universal Gröbner basis, special classes of ideals such as binomial ideals, etc). Our exposition is essentially an expansion of [10]. Some recent books on the subject include Becker and Weispfenning [4], Mishra [11], Cox, Little and O’Shea [6], Sturmfels [15], Adams and Loustaunau [1] and also a collection of research papers [14].

In this lecture, we fix an arbitrary field K and let R = K[X_{1}, …, X_{n}] = K[X].

§1. Admissible Orderings

Let PP = PP(X_{1}, …, X_{n}) be the set of power products (§0.10) of X. A partial ordering ≤_{A} on PP is

compatible if for all p, q, r ∈ PP, p ≤_{A} q implies rp ≤_{A} rq. It is semi-admissible if it is a compatible total

ordering. It is admissible if it is semi-admissible and 1 ≤_{A} p for all p ∈ PP. If p ≤_{A} q but p ≠ q then

we write p <_{A} q or q >_{A} p. Sometimes, a power product is called a term and an admissible orderings is also called a term ordering.

Example: Three important admissible orderings are the (pure) lexicographic ordering ≤_{LEX}, (total)

degree ordering ≤_{TOT}, and reverse lexicographic ordering ≤_{REV}. These orderings are completely

specified once we choose a total ordering on the variables X_{1}, …, X_{n}. Typically, we pick

X_{1} >_{A} X_{2} >_{A} ⋯ >_{A} X_{n}  (1)

where >_{A} is >_{LEX}, >_{TOT} or >_{REV}. Let

p = X_{1}^{d_{1}}X_{2}^{d_{2}} ⋯ X_{n}^{d_{n}}, q = X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}}.

(a) Define p ≥_{LEX} q if p = q or else, the first non-zero element in the sequence

(d_{1} − e_{1}, d_{2} − e_{2}, …, d_{n} − e_{n})  (2)

is positive. Thus, writing (X, Y, Z) for (X_{1}, X_{2}, X_{3}), we have

1 <_{LEX} Z <_{LEX} Z^{2} <_{LEX} ⋯ <_{LEX} Y <_{LEX} Y Z <_{LEX} Y^{2} ⋯ <_{LEX} <_{LEX} X <_{LEX} XZ <_{LEX} XY <_{LEX} X^{2} <_{LEX} · · · .

Note that there are an infinity of terms to be inserted at the three ellipses (describe them).

(b) Define p ≥_{TOT} q if deg(p) > deg(q) or else, p ≥_{LEX} q.

                   1 <_{TOT} Z <_{TOT} Y <_{TOT} X <_{TOT} Z^{2} <_{TOT} Y Z <_{TOT} Y^{2} <_{TOT} XZ <_{TOT} XY <_{TOT} X^{2} <_{TOT} · · · .

(c) Define p ≥_{REV} q iff either deg(p) > deg(q) or else, the last non-zero element in the sequence

(2) is negative.

                   1 <_{REV} Z <_{REV} Y <_{REV} X <_{REV} Z^{2} <_{REV} Y Z <_{REV} XZ <_{REV} Y^{2} <_{REV} XY <_{REV} X^{2} <_{REV} · · · .

This ordering is less familiar but has important computational properties (Bayer and Stillman). Suppose deg(p) = deg(q) and we wish to decide if p >_{REV} q. If deg_{X_{n}}(p) <

deg_{X_{n}}(q) then declare p >_{REV} q; otherwise deg_{X_{n}}(p) = deg_{X_{n}}(q) and we apply this rule recursively.

We need an oft-rediscovered little lemma of Dixon [7] (also attributed to Gordan).

Theorem 1 (Dixon’s Lemma) Given any subset T ⊆ PP(X_{1}, …, X_{n}), there is a finite subset F ⊆ T such that every power product in T is a multiple of some element of F.

Proof. We use induction on the number n of variables. If n = 1 then we let F consist of the unique term in T of minimum degree. Next assume n > 1. Pick any p_{0} ∈ T and say

p_{0} = X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}}.

Then every m ∈ T that is not divisible by p_{0} belongs to one of ∑_{i=1}^{n} e_{i} different sets: let i = 1, …, n and v = 0, 1, …, e_{i}−1. Then the set T_{i,v} consists of those monomials m ∈ T such that deg_{X_{i}}(m) = v. Let T′_{i,v} denote the set of monomials obtained by omitting the factor X_{i}^{v} from monomials in T_{i,v}. By inductive hypothesis, there exists finite subsets F′_{i,v} ⊆ T′_{i,v} such that each monomial in T′_{i,v} is a multiple of some monomial in F′_{i,v}. Let F_{i,v} be the set {m · X_{i}^{v} : m ∈ F′_{i,v}}. It is then clear that every monomial in T is a multiple of some monomial in the finite set

{p_{0}} ∪ ⋃_{i,v} F_{i,v}.

Q.E.D.

The set F in the lemma is known as a Dixon basis of T. Recall that a total ordering is well-founded if there is no infinite sequence of strictly decreasing elements. We show that any admissible ordering ≤_{A} is well-founded. For, if p_{1} >_{A} p_{2} >_{A} p_{3} >_{A} ⋯ then by Dixon’s lemma, the set T = {p_{1}, p_{2}, …, } has a

Dixon basis F. Without loss of generality, let F = {p_{1}, …, p_{k}} for some k. If T has more than k elements, then p_{k+1} is divisible by some p_{i} ∈ F. This contradicts p_{i} >_{A} p_{k+1}.

Corollary 2 An admissible ordering is well-founded.

Linear quasi-ordering on polynomials. We need to extend the admissible ordering ≤_{A} to poly-

nomials. First we extend it to mononomials: if c · p and d · q (c, d ∈ K; p, q ∈ PP) are two monomials, then we declare c · p ≤_{A} d · q if p ≤_{A} q. Note that this is^{1} a linear quasi-ordering. For any polynomial

p = c_{1}p_{1} + c_{2}p_{2} + ⋯ + c_{m}p_{m}, written as a sum of monomials with distinct p_{i}’s, introduce the term sequence of p

\overline{p} = (p_{1}, …, p_{m}),  (3)

where p_{1} >_{A} p_{2} >_{A} ⋯ >_{A} p_{m}. We compare two polynomials as follows: p ≤_{A} q iff in their term sequences

(p_{1}, …, p_{m}) and (q_{1}, …, q_{k}), either (1) m ≤ k and p_{i} = q_{i} for each i = 1, …, m, or (2) for some

i ≤ min{m, k}, p_{i} <_{A} q_{i} and p_{j} = q_{j} for j = 1, …, i − 1.

It is easy to check that this defines a linear quasi-ordering for polynomials. From a linear quasiordering ≤_{A}, we obtain a strict partial order <_{A} where x <_{A} y holds provided x ≤_{A} y holds but not y ≤_{A} x.

We leave it as an exercise to show:

Lemma 3 There is no strictly descending infinite sequence of polynomials under the ordering ≤_{A}.

Weight Schemes. For a quantitative approach to admissible ordering, we introduce another view of such orderings. Define a weight function w : PP → ℝ to be a real-valued function with the properties w(1) = 0 and w(pq) = w(p)+w(q). To avoid triviality, we assume that w(p) ≠ 0 for some p ∈ PP. It is easy to see w is completely characterized by the n-vector

\overline{w}:=(w(X_{1}), w(X_{2}), …, w(X_{n})).  (4)

Let us extend PP to the set \overline{PP} defined to consist of all rational power products of X_{1}, …, X_{n}. Thus a typical element of \overline{PP} is ∏_{i=1}^{n} X_{i}^{e_{i}} where e_{i} ∈ ℚ. For instance, X_{1}^{−3}X_{2}X_{4}^{1/5}. The definition of “weight function” extends to \overline{PP}, mutatis mutandis.

Lemma 4 For any weight function w : PP → ℝ, there is a unique extension of w to a weight function w′ : \overline{PP} → ℝ.

Proof. Let p = X^{e} where X ∈ {X_{1}, …, X_{n}} and e ∈ ℚ. It suffices to show that w′(p) is uniquely determined by w, since every element in \overline{PP} is a product of such p’s. If e ∈ ℕ then w′(p) = w(p). If e ∈ ℤ \ ℕ then w′(p) + w′(p^{−1}) = w′(1) = 0 implies w′(p) = −w(X^{−e}). If e = c/d (where c ∈ ℤ, d ∈ ℕ) then d · w′(p) = w′(p^{d}) = w′(X^{c}). Hence w′(p) = w′(X^{c})/d. We have completely determined w′. Q.E.D.

In some sense, extending the concept of weight functions from PP to \overline{PP} does not add anything essential. We wish to identify PP with ℕ^{n}, and \overline{PP} with ℚ^{n}. To freely switch between these two views as convenient, it is useful to introduce the analogue of the logarithm function (but still calling it “log”):

log :  \overline{PP} → ℚ^{n},
X^{e} ↦ e.

So a weight function w : ℚ^{n} → ℝ can be expressed as w(p) = ⟨\overline{w}, log(p)⟩ where \overline{w} is given in (4) and ⟨·, ·⟩ indicates inner product. A sequence

W = (w_{1}, …, w_{n})  (5)

1A binary relation ≤ on a set S is a quasi-order if for all x, y, z ∈ S, we have x ≤ x and if x ≤ y and y ≤ z then x ≤ z. This is like a partial-order except that the symmetry law is omitted: so x ≤ y and y ≤ x need not imply x = y. A quasi-ordering in which every two elements are comparable is called a linear quasi-ordering. Thus linear quasi-orderings satisfy the usual laws of linear orderings, save the symmetry law.

of n weight functions is called a weight scheme. W can be viewed as a function W : ℚ^{n} → ℝ^{n} where

W (p) = (w_{1}(p), …, w_{n}(p)), p ∈ ℚ^{n}.

The weight matrix \overline{W} associated with W is the n × n real matrix whose ith row is \overline{w_{i}} = (w_{i}(X_{1}), …, w_{i}(X_{n})), then we may write W (p) as a matrix-vector product

W (p) = \overline{W} · log(u).

Every weight scheme W (or its associated matrix \overline{W}) induces a partial order ≤′ on \overline{PP} which is defined as follows:

p ≤_{W} q iff W (p) ≤_{LEX} W (q).

This is easily seen to be a partial ordering (e.g., transitivity of ≤_{W} follows from the transitivity of

≤_{LEX}). Let us see some examples.

Example: (i) Let \overline{W} be the n × n identity matrix I_{n}. Then W induces the pure lexicographic ordering ≤_{LEX}

(ii) A weight matrix inducing the total degree ordering ≤_{TOT} is given by

[ \begin{matrix}1 & 1 & 1 & ⋯ & 1 & 1 \\ 1 & 0 & 0 & ⋯ & 0 & 0 \\ 0 & 1 & 0 & ⋯ & 0 & 0 \\ ⋮ & & & ... & & ⋮ \\ 0 & 0 & 0 & ⋯ & 1 & 0 \end{matrix} ] .

(iii) A weight matrix inducing the reverse lexicographic ordering ≤_{REV} is given by

[ \begin{matrix}1 & 1 & 1 & ⋯ & 1 & 1 \\ 1 & 1 & 1 & ⋯ & 1 & 0 \\ 1 & 1 & 1 & ⋯ & 0 & 0 \\ ⋮ & & & ... & & ⋮ \\ 1 & 1 & 0 & ⋯ & 0 & 0 \\ 1 & 0 & 0 & ⋯ & 0 & 0 \end{matrix} ] .

It should be noted that the ordering induced by W may only depend on a prefix of (w_{1}, …, w_{n}). For instance, if the entries of \overline{w_{1}} are n transcendental elements linearly independent over ℚ then W does not depend on the w_{2}, …, w_{n}. On the other hand, we are usually interested in \overline{W} with integer entries in which case the function will necessarily depend on all w_{i}’s.

A row operation on \overline{W} is admissible if it is one of the following two types:

(1) Multiplying a row by a positive constant.

(2) Adding an arbitrary constant multiple of row i to row j for some j > i.

It is not hard to see that admissible row operations does not change the partial ordering induced by \overline{W}. Moreover, such operations are invertible. Say two weight matrices are equivalent if they are equal after a sequence of admissible row operations. We say W (or \overline{W}) is non-negative if all the entries of \overline{W} are non-negative. We say W semi-admissible provided W is non-singular, i.e.,

W (p) = 0 iff p = 0 = (0, 0, …, 0).  (6)

Lemma 5 Let ≤_{W} be the partial ordering on \overline{PP} induced by a weight scheme W.

(i) The partial ordering ≤_{W} is a compatible ordering.

(ii) If W is semi-admissible, then ≤_{W} is a semi-admissible ordering.

(iii) If W is non-negative and semi-admissible then ≤_{W} is an admissible ordering.

(iv) If ≤_{W} is admissible then the first non-zero entry of each column of \overline{W} is positive. Moreover, \overline{W}

is equivalent a non-negative semi-admissible weight matrix.

Proof. (i) We have already noted that ≤_{W} is a partial ordering. Compatibility follows from the linearity

of weight functions: W (p) ≤_{LEX} W (q) implies W (rp) = W (r) + W (p) ≤_{LEX} W (r) + W (q) = W (rq).

(ii) ≤_{W} is a total ordering because p ≠ q implies W (p) ≠ W (q) (otherwise, by linearity, W (p/q) = 0

which contradicts u/v ≠ 1). (iii) If W is non-negative, ≤_{W} is admissible because W (1) = 0 ≤_{LEX} W (p) for all p ∈ \overline{PP}.

(iv) If ≤_{W} is admissible, it is easy to see that the first non-zero entry of each column is non-negative.

(Trivially, no columns can be entirely zero.) Let us say that a column “belongs to i” if the first non-zero entry of the column is in the ith row. Clearly the first row must be non-negative. So by adding a suitable multiple of the first row to the other rows, we can make all the columns belonging to 1 non-negative. At this point, row 2 becomes non-negative. We repeat this process with row 2, turning all the columns belonging to 2 non-negative. Notice that this does not affect the nonnegativity of any column. Clearly we can finally turn the entire matrix non-negative. Q.E.D.

Robbiano has shown that (Exercise) every admissible ordering is induced by some weight scheme (see also [8]).

Normal Form. There are obvious parallels between admissible row operations (§X.4) and elementary row operations. Let us say that a weight matrix is in normal form if (1) the rows are mutually orthogonal, and (2) in each non-zero row, the first non-zero entry is ±1.

Theorem 6 (i) Every weight matrix is equivalent to a normal form weight matrix. If the original matrix is rational, so is the normal form.

(ii) Two semi-admissible weight matrices with rational entries induce the same semi-admissible ordering on \overline{PP} iff they have the same normal form.

Proof. (i) We can make the rows mutually orthogonal using the Gram-Schmidt procedure (§IX.1). It is trivial to divide each row by the absolute value of its first non-zero entry to ensure that the first non-zero entry is ±1. This procedure preserves rationality of the matrix. (ii) If two weight matrices have the same normal form, then clearly they induce the same partial ordering on \overline{PP}. Conversely, suppose \overline{W} , \overline{W′} are semi-admissible and rational, and the the orderings ≤_{W}, ≤_{W′} that they induce on \overline{PP} are identical. By part (i), we may assume that they are both already in

normal form. Suppose the first i − 1 rows of \overline{W} and \overline{W′} are identical, and the ith rows are not. Let e, e′ ∈ ℚ^{n} be the ith rows of \overline{W} and \overline{W′}, respectively. By semi-admissibility, the matrices \overline{W} , \overline{W′} must have full-rank. Hence e, e′ are both non-zero. First suppose ⟨e, e′⟩ ≤ 0. Then observe that

⟨e − e′, e⟩ = e^{2} − ⟨e, e′⟩ > 0 while ⟨e − e′, e′⟩ = ⟨e, e′⟩ − e^{′2} < 0. This shows that X^{e−e′} >_{W} 1 and and

X^{e−e′} <_{W′} 1, contradiction. (Note that the rationality e, e′ depends on the rationality of the original

matrices.) Now suppose ⟨e, e′⟩ > 0. We choose α ∈ ℚ so that

⟨e − αe′, e⟩ = e^{2} − α⟨e, e′⟩ = 0.  (7)

That is, α = e^{2}/⟨e, e′⟩. Consider E = ⟨e − αe′, e′⟩ = ⟨e, e′⟩ − αe^{′2}. If E ≠ 0, then by perturbing α slightly, we can make ⟨e − αe′, e⟩ have a different sign than E. This again gives a contradiction. Hence we must have

E = ⟨e − αe′, e′⟩ = ⟨e, e′⟩ − αe^{′2} = 0.  (8)

Combining equations (7) and (8), we obtain ⟨e, e′⟩^{2} = e^{2}e^{′2}. Hence e, e′ are parallel. Since the first non-zero entries of both e and e′ are ±1, and ⟨e, e′⟩ > 0, this implies e = e′, contradiction. Q.E.D.

The following justifies the “normal form” terminology:

Corollary 7

(i) The normal forms of semi-admissible rational weight matrices are unique.

(ii) Two semi-admissible rational weight matrices are equivalent iff they have the same normal form.

Proof. (i) This is immediate from the preceding theorem. (ii) If two such matrices are equivalent, then they induce the same semi-admissible ordering. So they must have the same normal form. Conversely, since they both are equivalent to a unique normal form, they are equivalent to each other. Q.E.D.

Final Remarks.

1. This corollary is useful for constructing new semi-admissible orderings with rational matrices – we just have to make sure that their normal forms are distinct.

2. Our normal form can be defined for any real matrix. In case of rational matrices, a variant normal form may be preferable: still keeping the rows mutually orthogonal, we now insist that all entries are integer and the GCD of each row is 1. The preceding results hold for this variant.

3. Further treatment of the subject may be found in Robbiano [12, 13]. In particular, we can generalize weight functions to be w : R \ {0} → Γ where Γ is an ordered Abelian group playing the role of ℝ. All of Gröbner basis theory can be carried out in this general setting.

Exercises

Exercise 1.1: (i) Order the monomials of degree 3 in PP(X, Y) using the three types of admissible

ordering (assuming (1)). (ii) Similar, order the monomials of degree 3 in PP(X, Y, Z) for the three admissible orderings. (iii) Suppose we declare p ≥_{A} q if p = q or else, in (2), last nonzero component is negative.

(This is rather like reverse lexicographic ordering). Is this admissible? Semi-admissible? (iv) Show by admissible row operations that the weight matrix

[ \begin{matrix}1 & 1 & 1 \\ −2 & 1 & 1 \\ 0 & −1 & 1 \end{matrix} ] .

§2. Normal Form Algorithm  Lecture XII  Page 7

induces an admissible ordering that is one of the three standard examples ( ≤_{LEX}, ≤_{TOT}, ≤_{REV}). □

Exercise 1.2: Show the normal form matrices for total degree and reverse lexicographicl ordering on n variables. □

Exercise 1.3: (Robbiano) Show that every admissible ordering ≤_{A} on PP arises from some weight

scheme W. □

Exercise 1.4: Derive the Hilbert basis theorem (§XI.1) from Dixon’s lemma. □

Exercise 1.5: The following implies lemma 3. If U is any set totally ordered by ≤′, let S(U) denote the set of finite ordered sequences over U. That is, the elements of S(U) have the form (u_{1}, …, u_{k}) where u_{1} >′ u_{2} >′ ⋯ >′ u_{k} and k ≥ 0. We extend the ordering ≤′ to S(U) where

u = (u_{1}, …, u_{k}) ≤′ (v_{1}, …, v_{ℓ}) = v

if either u is a prefix of v (possibly u = v) or else there is some 1 ≤ i ≤ min{k, ℓ} such that u_{i} <′ v_{i} and for j = 1, …, i − 1, u_{j} = v_{j}. Show: If U is well-ordered by ≤′ then S(U) is well-ordered under the induced ordering. □

Exercise 1.6: We want to construct weight matrices with integer entries that induces an admissible ordering different from our standard examples:

(i) If we permute the rows of the normal forms for reverse lexicographic ordering, do we get new admissible orders? (ii) What about total degree ordering? (iii) Construct examples different from (i) and (ii). □

Exercise 1.7: In analogy to Hermite Normal form, let us define an alternative normal form for a weight matrix \overline{W} as follows: Let us call the first non-zero entry of each row a critical entry of the matrix. Say a weight matrix is in normal form if (1) the critical entries are ±1, and (2) there are only zero entries below each critical entry.

(i) Show that every weight matrix is equivalent to one of this form. (ii) Show the analogues of the above normal form results for this new definition. □

§2. Normal Form Algorithm

We fix some admissible ordering ≤_{A} in this section.

The heart of the Gröbner bases algorithm is the normal form algorithm which is described here. We also provide an explicit bound on the number of reduction steps in the normal form algorithm.

Concept of Reduction. The head term hterm(f) of a polynomial f ∈ R refers to the ≤_{A}-largest

power product (=term) in f. The head coefficient hcoef(f) and head monomial hmono(f) of f refers to the coefficient and monomial associated to the head term of f. Thus

                       hterm(f) · hcoef(f) = hmono(f).

For example, if f = −2X^{2}Y +X+1 then hterm(f) = X^{2}Y, hmono(f) = −2X^{2}Y and hcoef(f) = −2. These assertions did not depend on the choice of admissible ordering; we often choose examples with this property. On the other hand, the head term of g = X + Y^{3} depends on the admissible ordering.

If F ⊆ R is a set of polynomials, we define hterm(F) in the natural way, hterm(F) = {hterm(f) : f ∈ F }. We then define the head ideal Head(F) of any set F ⊆ R to be the ideal generated by

hterm(F):
                             Head(F) := Ideal(hterm(F)).

A basic concept in Gröbner bases is that of reduction. Given two polynomials f, g ∈ R, we say f is reducible by g if hmono(g) divides some monomial m in f. In that case m = c · hmono(g) for some monomial c. We then call h = f − c · g a reduct of f by g, and denote this 3-way relationship by

f ⟶^{g} h.

Necessarily, f ≠ h. If G is any set of polynomials and there exists a g in G such that f ⟶^{g} h, then we write

f ⟶^{G} h,

and call this a G-reduction step. The reflexive transitive closure of the binary relation ⟶^{G} is denoted ⟶_{∗}^{G} . If f is not reducible by G, we call f a G-normal form, and denote this in the suggestive manner: f ⟶^{G}. A normal form of f ∈ R is any G-normal form f̂ such that

f ⟶_{∗}^{G} f̂ ⟶^{G} .

Write NF_{G}(f) for the set of G-normal forms of f. The following is an (essentially trivial) algorithm for computing a member of NF_{G}(f).

Normal Form Algorithm Input: a polynomial f ∈ R, a finite set G ⊆ R. Output: a G-normal form h of f.

h ← f.

while h is reducible by G do 1. Pick g ∈ G such that g divides some monomial m of f.

2. h ← h − c · g where m = hmono(c · g).

We remark that this algorithm is non-deterministic because step 1 may have several choices of g and m. A variant of this algorithm is where G is fixed, so that the input is only f. In this case we call it the G-normal form algorithm. We shall write nf_{G}(f) for the (non-unique) output of this procedure.

There are two fundamental questions concerning this algorithm:

(A) Termination: does every reduction sequence eventually reach a normal form?

(B) Is the normal form always unique? Note that a positive answer to (A) implies that NF_{G}(f) is non-empty. A positive answer to (B) implies that |NF_{G}(f)| = 1. The answer to (A) is easily deduced from lemma 3, once we remark that

f ⟶^{G} h implies f >_{A} h.

We may now give our first definition of a Gröbner basis: A finite set G of polynomials is a Gröbner bases (for the ideal Ideal(G)) if for every polynomial f, the G-normal form of f is unique.

Length of Reduction Sequences. We provide explicit upper bounds on the length of such sequences (cf. [8]).

Let us fix a finite set F ⊆ R and g ∈ R. Our goal is to bound the worst case length

k = k(F, g)

of any sequence of F -reductions that begins with g:

g = h_{1} ⟶^{F} h_{2} ⟶^{F} h_{3} ⟶^{F} ⋯ ⟶^{F} h_{k}.  (9)

We assume that our admissible ordering ≤_{A} arise from the weight scheme W = (w_{1}, …, w_{n})

(cf. (5)). Moreover, we may assume that the W is non-negative: w_{i}(p) ≥ 0 for all p ∈ PP. Let \overline{f} = (f_{1}, f_{2}, …, , f_{m}) be the term sequence (see (3)) for a polynomial f. Then we define the extended term sequence of f as follows. It is equal to \overline{f} if f_{m} = 1; otherwise, the extended term sequence is (f_{1}, f_{2}, …, , f_{m}, 1). So extended term sequences always end with 1.

Let (f_{1}, f_{2}, …, , f_{m}) be the extended term sequence of f. If m ≥ 2 then define

M(f) := max{w_{i}(f_{j}) − w_{i}(f_{j+1}) : i = 1, …, n and j = 1, …, m − 1}
μ(f) := min{|w_{i}(f_{j}) − w_{i}(f_{j+1})| : i = 1, …, n and j = 1, …, m − 1}.

If m = 1 then f is a constant and we define M(f) = μ(f) = 0. Thus M(f) ≥ μ(f) ≥ 0.

Our bounds on k = k(F, g) will be in terms of the following parameters. Let the term sequence of g be \overline{g} = (g_{1}, g_{2}, …, g_{ℓ}).

ℓ  := the length of g
Δ := max{w_{i}(g_{j}) : i = 1, …, n, j = 1, …, ℓ}
M_{0} := max{M(f) : f ∈ F }
μ_{0} := min{μ(f) : f ∈ F }

We may assume that μ_{0} > 0. The main result of this section is:

Theorem 8 Any sequence of F -reduction steps on g has length at most

k(F, g) ≤ ℓ2^{\frac{Δρ^{n}}{M_{0}}} ,

where ρ:= \frac{M_{0}}{μ_{0}} + 1.

For the pure lexicographic ordering ≤_{LEX}, we have Δ = M_{0} = μ_{0} = Δ = 1, ρ = 2, so k(F, g) ≤ ℓ2^{2^{n}}.

First introduce a “cost function” C_{F} : PP → ℝ where

C_{F} (p) = \frac{1}{μ_{0}} ∑_{i=1}^{n} (\frac{M_{0}}{μ_{0}} + 1)^{n−i} w_{i}(p)

= \frac{1}{μ_{0}} ∑_{i=1}^{n} ρ^{n−i}w_{i}(p).

Also let C_{F} (cp) = C_{F} (p) for p ∈ PP and c ∈ K Note that C_{F} (pq) = C_{F} (p) + C_{F} (q). Moreover, C_{F} (p) ≥ 0 with equality iff p = 1.

§2. Normal Form Algorithm  Lecture XII  Page 10

Lemma 9 Let p >_{A} q be consecutive power products appearing in the extended term sequence of f ∈ F. Then C_{F} (p) ≥ 1 + C_{F} (q). Proof. Since p >_{A} q, there exists a k_{0} such that

w_{k_{0}}(p) > w_{k_{0}}(q) and w_{i}(p) = w_{i}(q) (for i = 1, …, k_{0} − 1).

Hence

C_{F} (p) − C_{F} (q) = \frac{1}{μ_{0}} ∑_{i=1}^{n} ρ^{n−i}(w_{i}(p) − w_{i}(q))
= \frac{1}{μ_{0}} ρ^{n−k_{0}}(w_{k_{0}}(p) − w_{k_{0}}(q)) + \frac{1}{μ_{0}} ∑_{i=k_{0}+1}^{n} ρ^{n−i}(w_{i}(p) − w_{i}(q))
≥ ρ^{n−k_{0}} − \frac{1}{μ_{0}} ∑_{i=k_{0}+1}^{n} ρ^{n−i}M_{0}
= 1

Q.E.D.

Inductively, we obtain: Corollary 10 If f ∈ F and \overline{f} = (f_{1}, f_{2}, …, f_{k}) then

C_{F} (f_{1}) − i + 1 ≥ C_{F} (f_{i}) ≥ 1, (i = 1, …, k).

Now define a cost function on polynomials. For any polynomial h, let

Ĉ_{F} (h) := ∑_{i=1}^{m} 2^{C_{F} (h_{i})}, where \overline{h} = (h_{1}, …, h_{m}).

Lemma 11 For any g, h ∈ R, if g ⟶^{F} h then Ĉ_{F} (g) ≥ 1 + Ĉ_{F} (h). Proof. Suppose h = g−u·f for some f ∈ F and monomial u. Let \overline{f} = (f_{1}, f_{2}, …, f_{k}). The reduction by f removes the monomial uf_{1} from g and ‘replaces’ it with uf_{2} + uf_{3} + … + uf_{k}. Note that uf_{i} (i = 2, …, k) may combine with monomials in g and even vanish. If k = 1 then we have simply removed uf_{1} and clearly Ĉ_{F} (g) − Ĉ_{F} (h) ≥ 1. Assuming k ≥ 2,

Ĉ_{F} (g) − Ĉ_{F} (h) ≥ 2^{C_{F} (uf_{1})} − ∑_{i=2}^{k} 2^{C_{F} (uf_{i})}
≥ Ĉ_{F} (u) [2^{C} − ∑_{i=2}^{k} 2^{C−i+1}] ,  (C:= C_{F} (f_{1}))
= Ĉ_{F} (u)2^{C−k+1}.

This last term is ≥ Ĉ_{F} (uf_{k}) ≥ 1 by previous corollary. Q.E.D. \begin{matrix}c \\ ◯ \end{matrix} Chee-Keng Yap September 22, 1995 Conclusion of proof. Since Ĉ_{F} (h) ≥ 1 for any non-zero polynomial h, the last lemma implies that the length of the F -reduction sequence (9) is at most Ĉ_{F} (g). With \overline{g} = (g_{1}, …, g_{ℓ}), we have

C_{F} (g_{j}) = \frac{1}{μ_{0}} ∑_{i=1}^{n} ρ^{n−i}w_{i}(g_{j})

≤ \frac{Δ}{μ_{0}} ∑_{i=0}^{n−1} ρ^{i}

= \frac{Δ}{M_{0}} (ρ^{n} − 1).

Hence Ĉ_{F} (g) = ∑_{i=1}^{ℓ} 2^{C_{F} (g_{i})} < ℓ2^{Δρ^{n}/M_{0}}, and main result follows.

We remark that the bound makes no assumptions about the order of reductions. With some simple restrictions, we may greatly improve the bound, from double exponential in n to single exponential (Exercise).

Exercises

Exercise 2.1:

(i) Let G = {X^{2}Y, Y^{2}} and f = 2Y^{4} + X^{3}Y − 3XY + 1. Show that NF_{G}(f) = {−3XY + 1}.

(ii) Show that any finite set G of monomials is a Gröbner bases. Further, the G-normal forms

are independent of the choice of admissible ordering.

□

Exercise 2.2: Let G = {g_{1}, g_{2}} where g_{1} = XY − 2 and g_{2} = 3X^{2} − 1. Show that G is not a Gröbner basis. HINT: consider NF_{G}(X^{2}Y^{2}). □

Exercise 2.3: We want efficient implementations of the normal form algorithm.

(i) Give an efficient data structure D_{1}(S) a finite subset S ∈ ℤ^{n} such that given any e ∈ ℤ^{n}, you can use D_{1}(S) quickly retrieve some d ∈ S such that X^{d}|X^{e}. (ii) Modify D_{1}(S) into a semi-dynamic data structure, i.e., where S can have elements inserted and D_{1}(S) is quickly updated. (ii) Use the above data structure to implement the normal form algorithm. Assume a sparse representation of polynomials. □

Exercise 2.4: Let n be the number of variables, d the maximum degree of any variable in F, Δ the maximum degree of any variable in g.

(a) For total degree ordering, k(F, g) ≤ 2^{(Δ+1)^{n}}.

(b) The bound in (a) is k(F, g) ≤ (Δ + 1)^{n} if we insist that the normal form algorithm always chooses to eliminate the ≤_{A}-largest monomial in g that can be eliminated. □

Exercise 2.5: We show that the above upper bound is, in some sense, the best possible ([8]). The admissible ordering is the usual ≤_{LEX} with

X_{1} >_{LEX} X_{2} >_{LEX} … >_{LEX} X_{n}.

§3. Gröbner Bases  Lecture XII  Page 12

Let d, Δ, ℓ, L be integers satisfying d ≥ ℓ − 2 > 0 and Δ > L. The polynomial g is

g:= X_{1}^{Δ}X_{n}^{L} + X_{1}^{Δ}X_{n}^{L−1} + ⋯ + X_{1}^{Δ}X_{n}

and the reducing set F comprises the following polynomials:

f_{1} = X_{1} − (X_{2}^{d}X_{3}^{d} ⋯ X_{n−1}^{d})(X_{n}^{d} + X_{n}^{d−1} + ⋯ + X_{n}^{d−ℓ+2})
f_{2} = X_{2} − (X_{3}^{d}X_{4}^{d} ⋯ X_{n−1}^{d})(X_{n}^{d} + X_{n}^{d−1} + ⋯ + X_{n}^{d−ℓ+2})
⋮
f_{n−1} = X_{n−1} − (X_{n}^{d} + X_{n}^{d−1} + ⋯ + X_{n}^{d−ℓ+2})
f_{n} = X_{n}^{ℓ} − X_{n}^{ℓ−1} − ⋯ − X_{n}
f_{n+1} = X_{n}^{ℓ−1} − X_{n}^{ℓ−2} − ⋯ − X_{n}
⋮
f_{n+ℓ−2} = X_{n}^{2} − X_{n}
f_{n+ℓ−1} = X_{n} − 1

i) Consider the reduction sequence that always choose the ≤_{LEX}-least monomial to reduce. Let

s(f) be the length of the entire F -reduction sequence starting from f. Show that if \overline{f} = (f_{1}, …, f_{m}) then s(f) = ∑_{i=1}^{m} s(f_{i}). ii) Show that s(X_{1}^{e_{1}} ⋯ X_{n}^{e_{n}}) is at least

2^{\frac{ℓ−2}{ℓ−1} ((e_{1}(d+1)^{n−1}+e_{2}(d+1)^{n−2}+···+e_{n}−1)}.

iii) Conclude that s(g) ≥ 2^{\frac{ℓ−2}{ℓ−1} (d+1)^{n−1}Δ}L. □

§3. Characterizations of Gröbner Bases

We now give several characterizations of Gröbner bases. Note that the following discussion is entirely relative to some fixed admissible ordering ≥_{A}.

The Normal Form Characterization. Our original definition (§2) of Gröbner basis was based on the concept of reduction and the normal form algorithm: a finite set G ⊆ R is Gröbner iff every f ∈ R has a unique G-normal form. We also say G is a Gröbner basis for the Ideal(G) that it generates.

The Standard Characterization. Perhaps the simplest characterization is this: a finite set G ⊆ R is Gröbner iff

Head(G) = Head(Ideal(G)).  (10)

This definition is elegant but highly non-constructive as it does not suggest any procedure to verify if a given set is Gröbner. We call this the standard characterization of Gröbner bases because some literature defines “standard bases” precisely this way, being the closest to Hironaka’s notion of standard bases.

Buchberger’s Characterization. Computationally, this is the most important characterization. The least common multiple (LCM) of two power products p = X_{1}^{e_{1}}X_{2}^{e_{2}} ⋯ X_{n}^{e_{n}} and q = X_{1}^{d_{1}}X_{2}^{d_{2}} ⋯ X_{n}^{d_{n}} is given by

LCM(p, q) := X_{1}^{max(d_{1},e_{1})}X_{2}^{max(d_{2},e_{2})} ⋯ X_{n}^{max(d_{n},e_{n})}.

The LCM of two monomials ap and bq (a, b ∈ K; p, q ∈ PP) is^{2} ab · LCM(p, q). For example, the LCM of 6X^{3}Y and 4X^{2}Y^{2} is 24X^{3}Y^{2}.

A critical notion in the constructive approach to Gröbner basis due to Buchberger is the following: for f, g ∈ R where m = LCM(hterm(f), hterm(g)), we define the S-polynomial of f and g to be

S(f, g) := \frac{m}{hmono(f)} · f − \frac{m}{hmono(g)} · g.

It is easy to understand S(f, g) once we note that the head terms in \frac{m}{hmono(f)} · f and \frac{m}{hmono(g)} · g both equals m, and hence they cancel each other in the defining expression for S(f, g). For example, with g_{1} = XY − 2, g_{2} = 3X^{2} − 1, we get

m = LCM(XY, 3X^{2}) = 3X^{2}Y, S(g_{1}, g_{2}) = 3X · g_{1} − Y · g_{2} = −6X + Y.

Buchberger’s characterization is this: G is Gröbner iff S(f, g) ⟶_{∗}^{G} 0 for all f, g ∈ G.

Term Rewriting Connection. The theory of Gröbner bases is intimately related to the termrewriting literature. For any fixed set F ⊆ R, we can view the binary relation ⟶_{∗}^{F} on R as a partial order. In general, consider a partial order ⟶_{∗} on an arbitrary set U. Let us write f ⟶ g, if f ⟶_{∗} g and f ≠ g. The partial order is Noetherian if it has no infinite descending sequence in the sense of

f_{1} ⟶ f_{2} ⟶ f_{3} ⟶ · · · .

The partial order is said to be Church-Rosser if for all f, g, g′ ∈ U, if f ⟶_{∗} g and f ⟶_{∗} g′ then there exists h ∈ U such that g ⟶_{∗} h and g′ ⟶_{∗} h. (Such an h is called a common successor of g, g′.) A minimal element f in this partial order is called an normal form, or a normal form of g if, in addition, g ⟶_{∗} f. A powerful induction principle for Noetherian structures is the following:

Proposition 12 (Principle of Noetherian Induction) For a Noetherian relation ⟶_{∗} , to establish the validity of a predicate P (x) for all x ∈ U, it is sufficient that:

(1) P (x) holds for all normal form elements x ∈ U.

(2) For x ∈ U: if P (y) holds whenever x ⟶ y, then we can conclude that P (x) holds.

In proof, suppose that (1) and (2) hold. For the sake of contradiction, suppose P (x_{0}) fails. Then x_{0} is not a normal form. So there exists some x_{1} such that x_{0} ⟶ x_{1} and P (x_{1}) fails. Continuing in this fashion, we obtain an infinite descending sequence x_{0}, x_{1}, x_{2}, …, which contradicts the Noetherian property. The following is a basic result in the theory of term-rewriting:

Theorem 13 If ⟶_{∗} is a Noetherian partial order on U then ⟶_{∗} is Church-Rosser iff every g ∈ U has a unique normal form.

Exercise 3.1: Prove theorem 13 using Noetherian induction. □

2If K is the quotient field of a UFD, then we could replace ab by LCM(a, b) (§III.1).

The Church-Rosser Property Characterization. We now apply this terminology to the partial order ⟶_{∗}^{F} induced by F -reductions. From §2, we know that this partial order is Noetherian. Combined with theorem 13, we conclude that the Church-Rosser property for ⟶_{∗}^{F} is equivalent to F being Gröbner: a set G ⊆ R to be Gröbner iff the relation ⟶_{∗}^{G} is Church-Rosser.

Extended Standard Characterization. The following is a useful variant of the standard characterization:

Lemma 14 (Extended standard characterization) G is Gröbner in the standard sense of (10) iff for all f ∈ Ideal(G), there are elements α_{i} ∈ R, g_{i} ∈ G, (i = 1, …, r) such that

f = ∑_{i=1}^{r} α_{i}g_{i}  (11)

and hterm(f) ≥_{A}hterm(α_{i}g_{i}) for all i.

Proof. (⇒) Let f ∈ Ideal(G). If f = 0 then f has the desired form (11). Otherwise, since hmono(f) ∈ Head(Ideal(G)) = Head(G) there is some g_{1} ∈ G and monomial p_{1} such that hmono(p_{1}g_{1}) = hmono(f). By the principle of Noetherian induction on Ideal(G), we may assume that f − p_{1}g_{1} can be represented in a form of equation (11). Then clearly f can be so represented. [The Noetherian induction refers to the partial order ⟶_{∗}^{G} on Ideal(G) with 0 as the only normal form.]

(⇐) Conversely, assume every f ∈ Ideal(G) can be expressed as in Equation (11). We want to show Head(G) = Head(Ideal(G)). It is clear that Head(G) ⊆ Head(Ideal(G)). For the opposite inclusion, suppose p ∈ Head(Ideal(G)) and p ≠ 0. Then p = ∑_{i} β_{i}hterm(f_{i}) where β_{i} ∈ R and f_{i} ∈ Ideal(G). From (11), we see that each f_{i} can be written as ∑_{j} α_{ij}g_{ij} where g_{ij} ∈ G. We may assume that α_{ij} are monomials. Therefore

p = ∑_{i} β_{i} (∑_{j} hterm(α_{ij}g_{ij})) = ∑_{i} ∑_{j}(β_{i}α_{ij})hterm(g_{ij}),

implying p ∈ Head(G). Q.E.D.

Ideal Membership Characterization. It is clear that if g is the F -normal form of h then g ≡ h(mod Ideal(F)). If F is Church-Rosser, then we have a unique representative for each equivalence class of polynomials modulo Ideal(F). Since 0 is clearly a normal form, it must be the unique representative for each element in Ideal(F). In particular, for all h ∈ Ideal(F), h ⟶_{∗}^{F} 0. The ideal membership characterization of Gröbner bases says that the converse also holds: F is Gröbner iff

∀h ∈ Ideal(F), h ⟶_{∗}^{F} 0.  (12)

Note that the condition (12) is equivalent to 0 ∈ NF_{F} (h) for all h ∈ Ideal(F). But in fact (12) is equivalent to the stronger assertion

∀h ∈ Ideal(F), NF_{F} (h) = {0}.  (13)

To see this, it suffices to show that g ∈ NF_{F} (h) implies g = 0. If g ≠ 0 then, since g ∈ Ideal(F), we have g ⟶_{∗}^{F} 0. So g is F -reducible, contradiction.

We summarize the above discussions in the following:

Theorem 15 (Characterization of Gröbner bases) Let G ⊆ I ⊆ R where I is an ideal and G is finite. The following are equivalent:

1. (Normal Form) Every f ∈ R has a unique G-normal form.

2. (Standard bases) Head(G) = Head(I).

3. (Buchberger’s Criterion) For all f, g ∈ G, we have S(f, g) ⟶_{∗}^{G} 0.

4. (Church-Rosser) The relation ⟶_{∗}^{G} is Church-Rosser.

5. (Extended Standard) Every f ∈ Ideal(G) has the expression

f = ∑_{i=1}^{r} α_{i}g_{i}, (where hterm(f) ≥_{A}hterm(α_{i}g_{i}), α_{i} ∈ R, g_{i} ∈ G).

6. (Ideal Membership) For all f ∈ I, we have f ⟶_{∗}^{G} 0.

Exercises

Exercise 3.2:

(i) Is the following set

F_{1} = {X^{3} − X^{2} + X − 1, XY − Y − X^{2} + X, Y^{2} − X^{2}}

a Gröbner bases under the lexicographic ordering where X <_{LEX} Y?

(ii) Show that the following is a Gröbner basis under the total degree ordering (does not matter whether X <_{TOT} Y or X >_{TOT} Y):

F_{2} = {XY^{4} − 1, X^{3} − Y, Y^{5} − X^{2}}.

(iii) Give a finite procedure to check if any set F is Gröbner. HINT: use Buchberger’s char-

acterization.

□

Exercise 3.3: Define H(f) to mean the highest degree homogeneous component of a polynomial f ∈ R. If F ⊆ R, let H(F) = {H(f) : f ∈ H}. The H-base or Macaulay base of an ideal I is a finite set F such that Ideal(H(I)) = Ideal(H(F)). Let f^{∧} denote the homogenization of f with respect to a new variable X_{0}, and for a set S ⊆ R, S^{∧} = {f^{∧} : f ∈ S}. Prove: {f_{1}, …, f_{m}} is a H-base of I iff I^{∧} = Ideal(f_{1}^{∧}, …, f_{m}^{∧}). □

Exercise 3.4: (Sturmfels) Let Λ ⊆ ℤ^{n} is a lattice (§VIII.1). The lattice ideal I =⊆ K[X_{1}, …, X_{n}] = K[X] of Λ is the ideal with the generator set of elements of the form

X^{e^{+}} − X^{e^{−}}, e ∈ Λ.

Here e^{+} is obtained from e by replacing any negative component by 0, and e^{−} is obtained from −e by a similar process. E.g., e = (−2, 2, 0, 3, −1), e^{+} = (0, 2, 0, 3, 0), e^{−} = (2, 0, 0, 0, 1).

§4. Buchberger’s Algorithm  Lecture XII  Page 16

(i) Show that the ideal generated by F_{2} (previous exercise) is a lattice ideal, where the lattice is generated by the vectors (1, 4) and (4, 3).

(ii) If A = {a_{1}, …, a_{m}} ⊆ ℤ^{n} is a generating set of Λ and all the components of a_{i} are positive, then I is generated by the set {X^{a^{+}} − X^{a^{−}} : a ∈ A}.

(iii) Show that ℤ^{n}/Λ is a direct sum G_{0} ⊕ G_{1} where G_{0} is a free Abelian group and G_{1} is the direct sum of a finite number of cyclic groups. HINT: use relevant theorems in §XI.1 and §X.9.

(iv) Show that if G_{1} is trivial then I is a prime ideal (called a toric ideal), (Sturmfels and Eisenbud).

(v) Show that if G_{0} is trivial, the order of the group G_{1} is equal to the determinant of Λ, and I is zero-dimensional. In fact, K[X]/I has dimension det(Λ).

(vi) Relative to an admissible ordering ≤_{A}, Head(I) is generated by the monomials {X^{e^{+}} : e ∈

Λ, e^{+} >_{A} e^{−}}.

(vii) A binomial X^{e} − X^{d} belongs to I iff e − d ∈ Λ.
□

Exercise 3.5: Complete the proof of theorem 15. □

§4. Buchberger’s Algorithm

Despite Buchberger’s criterion, it is not immediately obvious how to construct a Gröbner basis for any ideal (given by a set of generators, as always). We now present Buchberger’s algorithm to construct Gröbner bases. There are various heuristics to improve the algorithm but the basic version of the algorithm given below is easy to describe.

Buchberger’s Algorithm Input: F ⊆ R a finite set of polynomials Output: G a Gröbner basis for Ideal(F). G ← F; B ← {S(f, g) : f, g ∈ F, f ≠ g}; while B ≠ ∅ do begin

Remove f from B; h ← nf_{G}(f); if h′ ≠ 0 then begin

B ← B ∪ {S(f, h′) : f ∈ G};

G ← G ∪ {h′}

end {if} end {while}

Correctness: If this algorithm terminates, it is easy to see from Buchberger’s criterion that G is a Gröbner basis for Ideal(F). To see that this algorithm terminates, let

h_{1}, h_{2}, …

§5. Uniqueness  Lecture XII  Page 17

be the sequence of non-zero polynomials produced by the normal form algorithm in the while-loop. Since each h_{i} is not reducible by any of the previous polynomials (since h_{i} is not reducible by G which contains {h_{1}, …, h_{i−1}}) we see that hterm(h_{i}) is not divisible by hterm(h_{j}) for all j = 1, …, i − 1. By Dickson’s lemma, the set {hterm(h_{i}) : i ≥ 1} must be finite, i.e., the loop terminates.

Exercises

Exercise 4.1: (i) Compute the Gröbner basis of {XY^{4} − 1, X^{3} − Y, Y^{5} − X^{2}} under the pure lexicographic ordering assuming X >_{LEX} Y.

(ii) Now assume X <_{LEX} Y.

(iii) Now use the reverse lexicographic ordering with X >_{REV} Y.

□

Exercise 4.2: Compute the Gröbner basis of {X^{3}−Y, XY −Z} relative to the reverse lexicographic order (assuming Z >_{REV} Y >_{REV} X). □

Exercise 4.3: (Trinks) Compute the Gröbner basis for the following polynomials in ℚ[w, p, z, t, s, b] using the pure lexicographic order determined by w >_{LEX} p >_{LEX} z >_{LEX} t >_{LEX} s >_{LEX} b:

A_{1} = 45p + 35s − 165b − 36,
A_{2} = 35p + 40z + 25t − 27s,
A_{3} = 15w + 25ps + 30z − 18t − 165b^{2},
A_{4} = −9w + 15pt + 20zs,
A_{5} = wp + 2zt − 11b^{3},
A_{6} = 99w − 11sb + 3b^{2}.

NOTE: computer algebra systems should solve this in the order of minutes. The Gröbner basis has a univariate polynomial in b of degree 10, coefficients up to 60 digits. □

§5. Uniqueness

Now that we have established the existence of Gröbner bases, we turn to the question of their uniqueness. It is clear that we need to impose some additional conditions to get any kind of uniqueness.

We define a non-empty set F ⊆ K[X_{1}, …, X_{n}] to be self-reduced if each f ∈ F is not reducible by F − {f}. Of course, this definition is relative to some admissible ordering.

To treat some extreme cases of this definition, let us define the zero polynomial 0 to be reducible by F, for all F. Hence, no self-reduced set contains 0. By definition, if f ≠ 0 then f is not reducible by the empty set. Hence if F is a singleton set and F ≠ {0}, then it is self-reduced. Also, if c ∈ K and c ∈ F then F is self-reduced implies F = {c}.

Definition: A finite non-empty set G ⊆ R is a reduced (Gröbner) basis if (1) it is a Gröbner basis,

(2) it is self-reduced and (3) each f ∈ G is monic (i.e., hcoef(f) = 1).

Lemma 16 Every ideal has a reduced basis (relative to any choice of admissible ordering).

Proof. Begin with any Gröbner basis G. For each g ∈ G, reduce it with respect to the remaining polynomials of G. If the result g′ is 0, then discard g from G; other replace g by g′. After such a step, it is easy to see that G remains a Gröbner basis for the original ideal (use the standard characterization). We systematically cycle through all choices of g, and we continue this as long as G continues to change. More precisely, we stop if no g ∈ G can be reduced by the remaining polynomials. Clearly this process must terminate because each replacement polynomial g′ is <_{A} the

original g. Finally, we replace each polynomial g by g/hcoef(g). Q.E.D.

Monomial Ideals. A monomial ideal is one generated by a set of monomials. It is easy to show:

An ideal I is monomial iff for all f ∈ I, each monomial of f also belongs to I.  (14)

We prove a strong uniqueness property for reduced bases of monomial ideals:

Theorem 17 Reduced basis for monomial ideals are comprised of power products; moreover, they are unique and this is independent of the admissible ordering.

We shall omit the proof because it is similar to, but simpler than, the proof for the homogeneous case (Theorem 20 below).

Lemma 18 If G is a reduced basis then

hterm(G) = {hterm(f) : f ∈ G}

is a reduced basis for Head(G).

Proof. By the standard characterization of Gröbner bases, hterm(G) is a basis for Head(G). Clearly hterm(G) is self-reduced because this amounts to saying that no term in hterm(G) divides another term in hterm(G). Q.E.D.

Theorem 19 (Buchberger) Reduced basis are unique, up to choice of admissible orderings.

Proof. By way of contradiction, suppose G, G′ are distinct reduced bases for the same ideal. By the previous two lemmas, we conclude that hterm(G) = hterm(G′); this equality holds only because we assume the admissible ordering in G and G′ are the same. In particular, |G| = |G′|. Since G, G′ are distinct, without loss of generality, let f ∈ G \ G′. Then there is f′ ∈ G′ such that hterm(f) = hterm(f′). Then f − f′ is a non-zero polynomial. Suppose that hterm(f − f′) occur in f (the argument if it occurs in f′ is similar). Since f − f′ ⟶_{∗}^{G} 0, there is some g ∈ G such that hterm(g) divides hterm(f − f′). Clearly g ≠ f. Then f is reducible by G \ {f}, contradicting the self-reduced property. Q.E.D.

Homogeneous Ideals. A homogeneous ideal is one generated by a set of homogeneous elements. As for monomial ideals, it is easy to show:

I is homogeneous iff for all f ∈ I, each homogeneous component of f belongs to I. (15)

We have a strong uniqueness result similar to the case of monomial ideals:

§6. Elimination Properties  Lecture XII  Page 19

Theorem 20 Reduced basis for homogeneous ideals are comprised of homogeneous polynomials; moreover, such bases are unique and independent of the admissible ordering.

Proof. Let G be a reduced basis for a homogeneous ideal I. If f ∈ G is not homogeneous, let h be any homogeneous component of f of degree less than deg(f). Since h ∈ I, there is some g ∈ G such that h is reducible by g. Hence f is reducible by g and g ≠ f. This contradicts the self-reduced property.

To show uniqueness, suppose G′ is another reduced basis, G′ ≠ G. We do not assume that the admissible orderings implicit in the definitions of G and G′ are the same. Hence, for any polynomial f, we shall write hterm(f) and hterm′(f) to denote the head terms of f relative to the two admissible orderings. We may now assume that G, G′ have only homogeneous polynomials. Without loss of generality, let f ∈ G \ G′. Then hterm′(f′) divides hterm(f) for some f′ ∈ G′. Similarly, hterm(g) divides hterm′(f′) for some g ∈ G. Hence f is reducible by g. This is a contradiction unless g = f. So assume g = f. Then hterm(f) = hterm′(f′). Consider the non-zero polynomial f − f′. Consider hterm(f − f′) and we may suppose it belongs to f. Since f − f′ ⟶_{∗}^{G} 0, we conclude that hterm(f − f′) is reducibile by some h ∈ G. This means f is reducible by h, contradicting the self-reduced property. Thus f does not exist and G = G′. Q.E.D.

Exercises

Exercise 5.1: Show the characterizations of monomial and homogeneous ideals in (14) and (15). □

Exercise 5.2: Modify Buchberger’s algorithm (§4) to output a reduced basis. □

§6. Elimination Properties

In this and the following sections, we discuss of applications of Gröbner bases. The number of applications are numerous. But two basic applications are: computing in residue class rings (the original motivation of Buchberger) and elimination. This section considers the elimination applications.

Let X, Y be disjoint sets of variables and suppose ≤_{X} and ≤_{Y} are admissable orderings on PP(X) and

PP(Y), respectively. Then we define the lexicographic product of ≤_{X} and ≤_{Y},

(≤_{X}, ≤_{Y})

which is an admissible ordering on PP(X ∪ Y): If p, p′ ∈ PP(X), q, q′ ∈ PP(Y) then

pq (≤_{X}, ≤_{Y}) p′q′

iff p ≤_{Y} p′ or else, p = p′ and q ≤_{X} q′.

Clearly a pure lexicographic ordering ≤_{LEX} on n variables in which X_{i} <_{LEX} X_{i+1} is obtained as a lexico-

graphic product of the unique admissible ordering on each of the variables, (≤_{X_{1}}, …, ≤_{X_{n}}).

Theorem 21 Let ≤_{X,Y} denote the lexicographic product of admissible orderings ≤_{X} and ≤_{Y} on PP(X)

and PP(Y), respectively. If G ⊆ K[X, Y] is a Gröbner basis with respect to ≤_{X,Y} then

(a) Ideal_{K[X,Y]}(G) ∩ K[Y] = Ideal_{K[Y]}(G ∩ K[Y])

(b) G ∩ K[Y] is a Gröbner basis for Ideal_{K[Y]}(G ∩ K[Y]).

Proof. For part (a), note that the inclusion

Ideal_{K[Y]}(G ∩ K[Y]) ⊆ Ideal_{K[X,Y]}(G) ∩ K[Y]

is immediate. The converse inclusion uses a simple observation:

hterm(f) ∈ PP(Y) ⟺ f ∈ K[Y].

If f ∈ Ideal_{K[X,Y]}(G) ∩ K[Y], then by applying a sequence of G-reductions to reduct f to 0, we see that

f = ∑_{i=1}^{m} f_{i}g_{i}

where f_{i} ∈ K[X, Y], g_{i} ∈ G, hterm(f) ≥_{X,Y} hterm(f_{i}g_{i}). But this implies that hterm(f_{i}g_{i}) ∈ PP(Y)

which means f_{i}, g_{i} ∈ K[Y]. This proves part (a). But the proof also shows that G ∩ K[Y] is a Gröbner basis for the ideal Ideal_{K[Y]}(G ∩ K[Y]) (use the extended standard characterization).

Q.E.D.

If I ⊆ K[X] and Y is any subset of X then we call I ∩ K[Y] an elimination ideal of I. Note that I ∩K[Y] is clearly an ideal in K[Y]. The theorem just proved shows how to obtain elimination ideals — by constructing a Gröbner basis with respect to any admissible ordering which is a lexicographic product of two admissible orderings over PP(X\Y) and PP(Y), respectively. Note that the variables in X \ Y are to be “eliminated” in order to get I ∩ K[Y], and these variables are given “greater priority” in the admissible ordering. In particular, with the pure lexicographic ordering <_{A} in which

X_{1} <_{A} ⋯ <_{A} X_{n},

we get a Gröbner basis G ⊆ K[X_{1}, …, X_{n}] such that, for each i = 1, …, n, G ∩ K[X_{1}, …, X_{i}] generates an elimination ideal of (G). Of course, G ∩ K[X_{1}, …, X_{i}] may be trivial, i.e., {0}.

A set S ⊆ R is zero-dimensional iff its zero set Zero(S) ⊆ \overline{K}^{n} is finite. For example, if S = {X_{1}^{2} − 1, X_{2}^{2}, …, X_{n}^{2}} then Zero(S) has two zeros (±1, 0, …, 0).

Theorem 22 Let X_{i} (i = 1, …, n) be disjoint groups of variables, and I ⊆ K[X_{1}, …, X_{n}]. Then I is zero-dimensional iff for each i = 1, …, n, I ∩ K[X_{i}] ≠ ∅.

Proof. (⇐) If f_{i} ∈ I ∩ K[X_{i}] for each i = 1, …, n then for any zero ξ = (ξ_{1}, …, ξ_{n}) ∈ Zero(I), ξ (and hence ξ_{i}) must be a root of f_{i}. So Zero(I) is clearly finite.

(⇒) Suppose Zero(I) = {ξ^{(1)}, …, ξ^{(m)}} where ξ^{(j)} = (ξ_{1}^{(j)}, …, ξ_{n}^{(j)}). Then for each i = 1, …, n, there is a polynomial f_{i} ∈ K[X_{i}] such that f_{i}(ξ_{i}^{(j)}) = 0 for each j = 1, …, m. Hence f_{i} vanishes on Zero(I). By Hilbert’s Nullstellensatz, some power m_{i} of f_{i} belongs to I: f_{i}^{m_{i}} ∈ I. This proves I ∩ K[X_{i}] ≠ ∅.

Q.E.D.

Corollary 23 Let G be a Gröbner basis. Then G is zero-dimensional, iff for each i = 1, …, n, there is a g_{i} ∈ G with hterm(g_{i}) ∈ PP(X_{i}).

Proof. This is because hterm(G) = {hterm(g) : g ∈ G} generates Head(Ideal(G)) and Ideal(G) ∩ K[X_{i}] is non-empty implies there exists g_{i} ∈ Head(Ideal(G)) ∩ K[X_{i}]. Q.E.D.

Theorem 24 Let G be a Gröbner basis with respect to the pure lexicographic order ≤_{LEX} where

X_{1} <_{LEX} X_{2} <_{LEX} ⋯ <_{LEX} X_{n}. Then G is zero-dimensional if and only if for each i = 1, …, n, there is

a p_{i} ∈ G such that p_{i} ∈ K[X_{1}, …, X_{i}] − K[X_{1}, …, X_{i−1}].

Proof. If G is zero dimensional, the existence of p_{i} follows from the above corollary (if hterm(g_{i}) ∈ PP(X_{i}) then g_{i} ∈ K[X_{1}, …, X_{i}] \ K[X_{1}, …, X_{i−1}]). Conversely, suppose for each i, we have some p_{i} ∈ G where p_{i} ∈ K[X_{1}, …, X_{i}] − K[X_{1}, …, X_{i−1}]. Then we see that every ξ = (ξ_{1}, …, ξ_{n}) in Zero(G) must satisfy p_{i}(ξ_{1}, …, ξ_{i}) = 0. If i = 1, this shows there are finitely many ξ_{1} in Zero(G). Inductively, if there are only finitely many values for the first i − 1 components of ξ ∈ Zero(G), we see from p_{i}(ξ_{1}, …, ξ_{i−1}, ξ_{i}) = 0 that there are only finitely many possible values for ξ_{i}.

Q.E.D.

Application to Solving Polynomial Equations. Suppose we want to solve the system f_{1} = f_{2} = ⋯ = f_{m} = 0 of polynomial equations:

• The question whether the system is inconsistent (has no solutions) amounts to whether 1 ∈ Ideal(f_{1}, …, f_{m}). We can determine the membership of any element g in Ideal(f_{1}, …, f_{m}) by first computing a Gröbner basis G of Ideal(f_{1}, …, f_{m}) and then checking if nf_{G}(g) = 0. But for g = 1, it is sufficient to see if G contains a non-zero constant.

• If the system is consistent, we can check whether it has finitely many solutions. Compute a Gröbner basis G relative to any ≤_{A}. Check for each i whether there is a polynomial p_{i} ∈ G

with hterm(p_{i}) ∈ PP(X_{i}).

• Finally, suppose the system has finitely many solutions. Suppose we answered the previous question of zero-dimensionality by choosing ≤_{A} according to theorem 24. Then we can continue

from the Gröbner basis G computed there: we solve for all possible values for X_{1} (considering the polynomials in G ∩ K[X_{1}]). Then we back back-solve in the natural way: for each possible value of X_{1}, we solve the polynomials in G ∩ K[X_{1}, X_{2}] for the associated values of X_{2}. This can be continued in the obvious way.

Application in Geometric Projections. Geometrically, the elimination of variables amounts to projection. Let

X = {X_{1}, …, X_{m}},  Y = {Y_{1}, …, Y_{n}}  (16)

and for I ⊆ K[X, Y], let V be the algebraic set Zero(I) ⊆ \overline{K}^{m+n}. We are interested in the projection map

π : \overline{K}^{m+n} → \overline{K}^{m}

given by π(x, y) = x. Intuitively, I ∩ K[X] is the zero set of the projection π(V). There is a subtlety: the projection may not be an algebraic set. A simple example is V = Zero(XY − 1) where π(V) = \overline{K} − 1, which is not an algebraic set. Thus we define the Zariski closure of a subset S ⊆ \overline{K}^{m} to be the smallest algebraic set that contains S. Then we have the theorem, whose proof we leave to an exercise.

Theorem 25 . Let I ⊆ K[X, Y] be an ideal. The Zariski closure of π(Zero(I)) is equal to Zero(I ∩ K[X]).

An instance of projection is the problem of “implicitization”. In computer-aided design, a surface S ⊆ ℝ^{3} is often represented parametrically in the form:

X = \frac{f(s, t)}{d(s, t)}, Y = \frac{g(s, t)}{d(s, t)}, Z = \frac{h(s, t)}{d(s, t)},  (17)

where f, g, h, d ∈ ℚ[s, t]. That is, S = {(X(s, t), Y (s, t), Z(s, t)) : (s, t) ∈ ℝ^{2}}. Implicitization of these parametric equations is the problem of computing a polynomial A(X, Y, Z) such that S = Zero(A). This polynomial can be obtained by computing

Ideal(d(s, t)X − f(s, t), d(s, t)Y − g(s, t), d(s, t)Z − h(s, t)} ∩ ℚ[X, Y, Z],

i.e., eliminating s, t. In fact, by homogenizing the equations using another indeterminate u and treating X, Y, Z as the indeterminates, A(X, Y, Z) can be computed as a Macaulay resultant, (see [3, 2] for this and other applications). Note that the parametric form (17) is useful when we have to render the surface, as in computer graphics. But the implicit form A(X, Y, Z) is more useful when we need to know if a given point (a, b, c) is one the surface, or on one side of the surface).

Exercises

Exercise 6.1: For the following systems, indicate whether it is solvable, and if so, whether it is zero-dimensional, and if so, compute the finitely many solutions:

(i) {X^{2} + Y^{2} − 1, XY − 1, Y^{2} − X}

(ii) {X^{2}Y − Y + X^{2} − 1, XY + X − 1, XY^{3} + Y^{3} + Y + 2}.

(iii) {XY^{2} − Y^{2} + X − 1, X^{3} + X^{2}, Y^{2} − Y }.

(iv) {XY^{2} − Y^{2} − X + 1, XY^{2} − Y, X^{3} − X^{2} − X + 1}. □

Exercise 6.2: (Macaulay’s quartic curve) Consider the curve X = t, Y = t^{3}, Z = t^{4}. (i) Use the Gröbner basis algorithm to that its ideal is Ideal(X^{3} − Y, XY − Z) or Ideal(Y − X^{3}, Z − X^{4}) (by eliminating t). (ii) Re-do (i) but by using Macaulay’s resultant (as suggested in the text). (iii) Show by computing the appropriate Gröbner basis that its projective closure on the XY plane, the Y Z plane and the XZ-plane are (respectively) Y − X^{3}, Z^{3} − Y^{4} and Z − X^{4}. □

Exercise 6.3: Show how Gröbner basis algorithms can be used to compute the resultant (with respect to X_{1}) of two polynomials in K[X_{1}, …, X_{n}]. □

Exercise 6.4: Prove theorem 25. □

§7. Quotient Rings  Lecture XII  Page 23

Exercise 6.5: With X, Y as in (16), let f_{1}, …, f_{m} ∈ K[Y].

(i) Show that the kernel of the map ϕ : K[X] → K[Y] where ϕ(X_{i}) = f_{i} (i = 1, …, m) is given by

Ideal(X_{1} − f_{1}, …, X_{m} − f_{m})_{K[X,Y]} ∩ K[X].

(ii) With I ⊆ K[Y] an ideal, give an interpretation of

Ideal(I, X_{1} − f_{1}, …, X_{n} − f_{n})_{K[X,Y]} ∩ K[X].
□

Exercise 6.6: (Bayer)

Let G = (V, E) be an undirected graph on the vertex set V = {1, …, n}. We want to test if G is 3-colorable, i.e., there is a 3-coloring of G such that adjacent vertices have distinct colors. Associate vertex i with the variable X_{i} and consider the system of polynomials

{X_{i}^{3} − 1, X_{i}^{2} + X_{i}X_{j} + X_{j}^{2} : i, j = 1, …, n, (i, j) ∈ E}.

Show that G is 3-colorable iff this system is consistent. □

Exercise 6.7:

(i) Compute the minimal polynomial (§VI.3) of \sqrt{3} − ^{2} \sqrt{3} + 1.

(ii) Let P (X) be the minimal polynomial the algebraic number α, and β ∈ ℚ(α). Say, β = A(α)/B(α) where A, B ∈ ℤ(X). Show that the minimal polynomial of β appears in a suitable reduced Gröbner basis of an ideal intersection. □

§7. Computing in Quotient Rings

Gröbner bases provide a simple tool for computing in residue class rings (equivalently, quotient rings). For an ideal I ⊆ R, let S = R/I be the quotient ring and the canonical homomorphism from R to S be denoted

a ∈ R ⟼ \overline{a} = a + I ∈ S.

The element \overline{a} is called the “residue class” of a. Let G ⊆ I be a reduced Gröbner basis for I, relative to some admissible ordering. First let us address the question of representing elements of S. For a ∈ R, we let nf_{G}(a) represent \overline{a}. We write nf_{G}(a) ≅ \overline{a} to indicate this relation between a particular polynomial nf_{G}(a) and an element \overline{a} of R/I. Note that \overline{a} = \overline{b} iff a − b ∈ I iff nf_{G}(a − b) = 0 iff nf_{G}(a) = nf_{G}(b). So there is a bijection between the elements of S and the set

{nf_{G}(a) : a ∈ R}.

Ring operations in S are easily simulated:

\overline{a} ± \overline{b} ≅ nf_{G}(a) ± nf_{G}(b)
\overline{a} · \overline{b} ≅ nf_{G}(nf_{G}(a) · nf_{G}(b))

where the ± and · on the right hand side are ordinary polynomial operations.

Lemma 26 Let I ⊆ R = K[X_{1}, …, X_{n}] be an ideal with G as Gröbner basis.

(i) S = R/I is a K-vector space.

(ii) Let B = \{p ∈ PP : p = nf_{G}(p)\}. Then \overline{B} = \{\overline{p} : p ∈ B\} forms a basis for this vector space.

(iii) S is a finite dimensional K-vector space iff I is zero-dimensional.

Proof. (i) is routine. (ii) follows from the above representation of S by the G-normal forms, since each normal form is of the form ∑_{i=1}^{k} α_{i}p_{i} with α_{i} ∈ K, p_{i} ∈ PP(X_{1}, …, X_{n}) and p = nf_{G}(p). To see (iii), recall that I is zero-dimensional iff for each i, there is a f_{i} ∈ G with hterm(f_{i}) ∈ PP(X_{i}). So if I is zero-dimensional, we easily see that the X_{i}-degree of each p ∈ B is less than deg(hterm(f_{i})). This implies B is a finite set and S is finite dimensional. Conversely, if I is not zero-dimensional, there exists a variable X_{i} such that X_{i}^{ℓ} ∈ B for all ℓ ≥ 0. Then B is infinite and S is infinite dimensional.

Q.E.D.

Therefore, if I is zero-dimensional then we can construct the basis \overline{B} (as represented by B) for the K-vector space S. Furthermore, we can construct the so-called multiplication table for this basis: for each p, q ∈ B, we only need to compute the G-normal form of pq. We are thus set up for computation in S = R/I.

Dimension of an Ideal. In general, for a prime ideal P ⊆ K[X] = R, its dimension dim(P) is the transcendence degree^{3} of R/I over K. If I is a general ideal, its dimension dim(I) is defined to be the maximum dimension of a prime ideal P that contains I. Let us relate dimension to another quantity: define (following Gröbner)

δ(I) := max{|Y| : Y ⊆ X, I ∩ K[Y] = (0)}.

It is immediate that δ(P) ≤ dim(P) since P ∩ K[Y] = (0) implies that Y is a transcendental set over R/P. The following theorem (from Gröbner[9]) shows that they are in fact equal for all I.

Theorem 27 The dimension of I is the largest cardinality of a set Y ⊆ X such that I ∩K[Y] = (0). That is, dim(I) = δ(I).

This leads to a method to compute a subset of X that is a transcendental base for R/I: for each subset Y ⊆ X, compute a Gröbner basis G for I relative to an admissible ordering which is the lexicographic product ( ≤_{X−Y}, ≤_{Y}). Then Y is a transcendental set iff G ∩ K[Y] is empty. We may systematically

do this computation for Y’s of larger cardinality before those of smaller cardinality, stopping at the first transcendent set Y we find. Note that the alternative “bottom-up” approach is to find a set transcendental Y and then try to extend it to Y ∪ {X_{i}} for some X_{i} ∈ X \ Y. Unfortunately, this fails for non-prime ideals I. The following is an example from Cavaliere (unpublished lecture notes):

I = Ideal(X_{1}^{2}, X_{1}X_{3}, X_{1}X_{4}, X_{2}X_{3}, X_{2}X_{4}) ⊆ K[X_{1}, …, X_{4}]  (18)

Then I ∩ K[X_{2}] = (0) and I ∩ [X_{2}, X_{j}] ≠ (0) for j ≠ 2. However, I ∩ K[X_{3}, X_{4}] = (0), and in fact dim(I) = 2. See the chapter by Weispfenning and ? [14] for further aspects of this problem.

§8. Syzygy  Lecture XII  Page 25

Exercises Exercise 7.1: Construct the multiplication table for R/Ideal(G) where G = {X^{2} − X + 1, Y^{2} −

3A subset T ⊆ R/I is said to be algebraically independent over K if there is no polynomial relation A(t_{1}, …, t_{m}) ∈ K[t_{1}, …, t_{m}] and elements a_{1}, …, a_{m} ∈ T such that A(a_{1}, …, a_{m}) = 0. We say T is a transcendental set over K if every finite subset of T is algebraically independent over K. If T is a maximal cardinality transcental set, we call it a transcendental base of R/I over K. Although a transcendental base is non-unique, its cardinality is unique. This cardinality is called the transcendence degree of R/I over K.

Y + 2X, XY − 2}. □

Exercise 7.2: Given g a polynomial and a set F of polynomials generating an ideal I ⊆ R, show how to decide if \overline{g} is an invertible element in S = R/I. Note: g is invertible if there is some h such that gh + I = R = Ideal(1). □

Exercise 7.3: Verify the assertions on the example (18) of Cavaliere. □

§8. Syzygy

In this section, let g = [g_{1}, …, g_{m}] ∈ R^{m} be a fixed but arbitrary sequence of polynomials in R = K[X_{1}, …, X_{n}]. We regard g as an ordered basis for Ideal(g_{1}, …, g_{m}).

Definition: Let a = [a_{1}, …, a_{m}] ∈ R^{m}. The g-grade of a is given by

max{hterm(a_{i}g_{i}) : i = 1, …, m}

where the maximum is with respect to the implicit admissible ordering <_{A}. We call a a syzygy of g

if ∑_{i=0}^{m} a_{i}g_{i} = 0.

Let us motivate some syzygy computations that might be desired.

Let Syz(g) ⊆ R^{m} denote the set of syzygies of g. Observe that Syz(g) is a R-submodule of R^{m}. By Hilbert’s basis theorem for Noetherian modules (§XI.1), Syz(g) is finitely generated. So the question to construct a finite basis of Syz(g) naturally arises. Why would we be interested in syzygies in the first place? Well, it would tell us about any non-trivial relations among g_{1}, …, g_{m}. If particular, if g_{1} can be expressed as a combination of g_{2}, …, g_{m}, then clearly any basis for Syz(g) must contain an syzygy whose first component is a non-zero constant! Let us say that a finite set F ⊆ R is a minimal basis (for the ideal it generates) if no proper subset of F generates Ideal(F). Thus computing a syzygy basis yields a method (possibly overkill) to decide if F is a minimal basis.

Next, let the map φ : R^{m} → R given by φ(a) = ∑_{i=1}^{m} a_{i}g_{i} be called the canonical map determined by g : it is clearly an R-module homomorphism (§XI.1). So Syz(g) is simply the kernel of φ. Then the following sequence^{4} is exact:

R^{m} ⟶^{φ} R ⟶^{ψ} R/I ⟶ 0

where I is the ideal generated by g_{1}, …, g_{m} and ψ is the canonical map from R to R/I. Again, Syz(g) has a finite basis, say h = [h_{1}, …, h_{t}] (h_{i} ∈ R^{m}). We can thus look at the set Syz(h) of syzygies of h, where Syz(h) is called the second syzygy module of I. Again, why would we be interested in the second syzygy module? As before, it would tell us of any non-trivial relations among the generators of the first syzygy module (and similar to the minimal basis application, might be used for a similar purpose).

⋯ ⟶^{φ_{i−1}} ⋯ M_{i−1} ⟶^{φ_{i}} M_{i} ⟶^{φ_{i+1}} ⋯

4A (finite or infinite) sequence of R-module homomorphisms is exact if the image of φ_{i} equals the kernel of φ_{i+1} for all i. (The kernel of a homomorphism is the set elements that maps to 0.)

Again, we introduce may another canonical map φ′ : R^{t} ⟶ R^{m} such that the following extended sequence is exact:

R^{t} ⟶^{φ′} R^{m} ⟶^{φ} R ⟶^{ψ} R/I ⟶ 0.

But the Syz(h) also has a finite basis (say with s generators) with canonical map φ′′, and we can extend this exact sequence again. The Hilbert syzygy theorem says that such extensions of the exact sequence terminate in that we eventually reach a final canonical map φ′′ with the trivial kernel (0) (hence only trivial syzygies). So we have a finite exact sequence,

0 ⟶ R^{s} ⟶^{φ′′} ⋯ ⟶ R^{t} ⟶^{φ′} R^{m} ⟶^{φ} R ⟶^{ψ} R/I ⟶ 0,

called a free resolution of I. There are clearly arbitrary choices in the definition of this sequence (the ordering in g = [g_{1}, …, g_{m}], the choice of syzygy bases, etc). Nevertheless, it contains certain invariants that depends only on I (e.g., [17, ch.VII] and also lecture XIII). It is therefore important to develop computational tools for computing with syzygies.

Syzygy basis for a Gröbner basis. We will initially assume that g is a Gröbner basis.

For 1 ≤ i < j ≤ m, the S-polynomial of g_{i} and g_{j} can be written in the form

S(g_{i}, g_{j}) = α_{i,j}g_{i} + β_{i,j}g_{j}

where α_{i,j}, β_{i,j} are monomials. Then by the extended standard characterization of Gröbner bases,

S(g_{i}, g_{j}) = ∑_{μ=1}^{m} h_{μ}^{i,j}g_{μ}

where hterm(S(g_{i}, g_{j})) ≥_{A}hterm(h_{μ}^{i,j}g_{μ}) for each μ.

Define

T (i, j) :=[h_{1}^{i,j}, h_{2}^{i,j}, …, h_{i}^{i,j} − α_{i,j}, …, h_{j}^{i,j} − β_{i,j}, …, h_{m}^{i,j}].

In other words, the μ-th entry of T (i, j) is h_{μ}^{i,j} except when μ = i or μ = j, in which case the entries are h_{j}^{i,j} − α_{i,j} and h_{j}^{i,j} − β_{i,j}, respectively. Clearly, T (i, j) is a syzygy of g. The grade of T (i, j) is equal to

hterm(α_{ij}g_{i}) = hterm(β_{ij}g_{j})

which is equal to LCM(hterm(g_{i}), hterm(g_{j})). It is also important for the following proof to notice that the grade of T (i, j) is attained at the ith and jth components and no where else.

Theorem 28 (Spear, Schreyer) If g is an ordered Gröbner basis then

{T (i, j) : 1 ≤ i < j ≤ m}

forms a basis for the module Syz(g).

Proof. We have noted that the T (i, j) belongs of Syz(g). To show that they generate Syz(g), let a = [a_{1}, …, a_{m}] ∈ Syz(g). Let p be the grade of a. Without loss of generality, suppose that k of the components of a achieves this grade so that, for some 1 ≤ j_{1} < j_{2} < ⋯ < j_{k} ≤ m, we have

p = hterm(g_{j_{1}}a_{j_{1}}) = hterm(g_{j_{2}}a_{j_{2}}) = ⋯ = hterm(g_{j_{k}}a_{j_{k}}).

Clearly k ≥ 2 since hterm(g_{j_{1}}a_{j_{1}}) must be cancelled in the expression ∑_{i=1}^{m} a_{i}g_{j_{i}} = 0. We will show that for some monomial γ,

b = a − γ · T (j_{1}, j_{2})

such that either b has grade <_{A} p or else less than k components of b attain the grade p. Repeating

this, we must eventually achieve the trivial syzygy [0, 0, …, 0] since <_{A} is well-founded. This would

prove that the set of T (i, j) generates Syz(g).

In fact, since p = hterm(a_{j_{1}}g_{j_{1}}) = hterm(a_{j_{2}}g_{j_{2}}), we see that

LCM(hterm(g_{j_{1}}), hterm(g_{j_{2}}))

must divide p. Hence γ · T (j_{1}, j_{2}) has grade p, for some monomial γ. Moreover, we may choose γ so that the j_{1}th component of

b = a − γ · T (j_{1}, j_{2})

is <_{A} p. Since the grade p is attained only at the j_{1}th and j_{2}th components of T (j_{1}, j_{2}), this means that the number of components of b that attains grade p is strictly reduced. Further, since the grade of b is ≤_{A} p, our inductive step is complete. This completes our proof.

Q.E.D.

With s = \binom{m}{2}, let

U ∈ R^{s×m}  (19)

denote matrix whose rows are the syzygies T (i, j). Note that T (i, j) can be computed by running any normal form algorithm on the S-polynomial S(g_{i}, g_{j}), and doing some straightforward bookkeeping.

Syzygy basis for an arbitrary ordered basis. Suppose now f = [f_{1}, …, f_{r}] ∈ R^{r} is an arbitrary ordered ideal basis. We again want to construct a module basis for Syz(f).

Let g = [g_{1}, …, g_{m}] be a Gröbner basis for the ideal generated by {f_{1}, …, f_{r}}. We may assume m ≥ r and g_{i} = f_{i} for i = 1, …, r. Let

G = [I_{r}|O]

be an r × m matrix consisting of an r × r identity matrix I_{r} and O is a r × (m − r) matrix of zeroes. Then

f^{T} = Gg^{T}

where (·)^{T} denotes matrix transpose. Since each g_{i} is a linear combination of f_{1}, …, f_{r}, there is an m × r matrix F with entries in R such that

g^{T} = F f^{T} .

We may further assume the first r rows of F form the identity matrix I_{r}. Hence

GF = I_{r}.

With U as in (19), we obtain

U · g^{T} = 0.

Theorem 29 The matrix B:= U · F is an s × r matrix whose rows form a basis for Syz(f).

Proof. Suppose a ∈ Syz(f). Then aG is a syzgy of g (by our assumption on G, aG is just the padding out of a with 0’s). Since the rows of U form a basis for these syzgies, there exists an s-tuple b such that aG = bU. Hence:

a = aGF = b · UF = bB.

This proves the rows of B is indeed a basis for Syz(f). Q.E.D.

Note that the matrix F, and hence B, can be constructed from f: the entries of F can be built up during the construction of the Gröbner basis g from f.

Application to Ideal Intersection. Let f_{1}, …, f_{r}, g_{1}, …, g_{s} be given. We want the ideal intersection

I = Ideal(f_{1}, …, f_{r}) ∩ Ideal(g_{1}, …, g_{s}).

Write h :=[f_{1}, …, f_{r}, g_{1}, …, g_{s}]. We construct B, the matrix whose rows form a basis for Syz(h). If C is the matrix consisting of the first r columns of B, and for each row a of C, we form the dot product a · f^{T} (where f = [f_{1}, …, f_{r}]), then we claim that the set S of these dot products a · f^{T} generates I. To see that each a · f^{T} ∈ S is in I, note that for some b, the concatenation a; b is a row of B. Hence a · f^{T} + b · g^{T} = 0 where g = [g_{1}, …, g_{s}]. Hence a · f^{T} ∈ Ideal(g_{1}, …, g_{s}) ∩ Ideal(f_{1}, …, f_{r}). Conversely, any element of I has the form a′ · f^{T} and also the form b′ · f^{T}. Hence [a′; −b′] is a syzygy of h. Thus a′ is a linear combination of the rows of C, and so a′ · f^{T} is a linear combination of elements of the form a · f^{T} ∈ S.

Final Remarks. This section touches on an important direction in the development of Gröbner basis: the whole subject is capable of generalization to R-submodules of R^{m}, for some m ≥ 1. (It is a generalization because an ideal of R is just a submodule of R^{m} with m = 1.) Let us briefly indicate how it goes. We may define a “generalized power product” to be an element of the form p · e_{i} where p ∈ PP(X) and e_{i} = (0, …, 0, 1, 0, …, 0) is the ith elementary m-vector with a 1 in the ith position. Write PP_{m}(X) for these generalized power products. (So the original notation PP is just PP_{1}) We say a total ordering ≤_{A} on PP_{m}(X) is admissible if for all g, h ∈ PP_{m}(X) and all p ∈ PP(X), we have

(1) g ≤_{A} pg and (2) g ≤_{A} h implies pg ≤_{A} ph. One then shows that this is a well-ordering, and extend

this total ordering to a linear quasi-ordering on R^{m}. We may define the notion of the headterm of g and reduction f ⟶^{g} h, and hence a notion of normal forms and Gröbner basis. Alternatively, the standard characterization can be used to define Gröbner basis. Finally, an analogue of Buchberger’s algorithm can be shown.

Exercises

Exercise 8.1: Describe the necessary modifications to the normal form algorithm and Buchberger’s algorithm in order to carry out the computation of a general syzygy basis above. □

Exercise 8.2: Compute a syzygy basis for the following ordered basis

[g_{1}, g_{2}, g_{3}] = [X_{1}^{2} − X_{2}X_{4}, X_{1}X_{2} − X_{3}X_{4}, X_{1}X_{3} − X_{2}^{2}],

say, assuming a pure lexicographic ordering. □

Exercise 8.3: Describe some efficient method to solve the following: given F, compute a subset H ⊆ F that is a minimal basis for Ideal(F). □

Exercise 8.4: (Gianni-Trager-Zacharias)

(i) If I, J ⊆ R are ideals and t is a new indeterminate, show that

(I ∩ J) = (Ideal(tI, (t − 1)J) · R[t]) ∩ R.

(ii) Use this to give an alternative algorithm for computing ideal intersection.

□

Exercise 8.5: If ≤_{A} is an admissible ordering on PP, show that the following (still denoted ≤_{A}) are

admissible orderings on PP_{m}. Let p, q ∈ PP.

(i) Define p · e_{i} ≤_{A} q · e_{j} iff i < j or else, p ≤_{A} q.

(ii) Define p · e_{i} ≤_{A} q · e_{j} iff p <_{A} q or else, i ≤ j. □

Exercise 8.6: Carry out the above outline of a generalization of Gröbner basis theory to submodules of R^{m}. □

Exercise 8.7: Generalize the above syzygy algorithm. If G = [g_{1}, …, g_{k}] where g_{i} ∈ RR^{m}, we may define a = [a_{1}, …, a_{k}] ∈ ℝ^{k} to be a syzygy of G if ∑_{i=1}^{k} a_{i}g_{i} = 0 (as in the second syzygy module). Then the set Syz(G) of syzygies of G is a submodule of R^{k}. Develop an algorithm to compute a basis for Syz(G). □

References

[1] William W. Adams and Philippe Loustaunau. An introduction to Gröbner Bases. Graduate Studies in Mathematics, Vol.3. American Mathematical Society, 1994.

[2] C. Bajaj, T. Garrity, and J. Warren. On the applications of the multi-equational resultants. Technical Report CSD-TR-826, Computer Science Department, Purdue University, November, 1988.

[3] Chanderjit Bajaj. Algorithmic implicitization of algebraic curves and surfaces. Technical Report CSD-TR-681, Computer Science Department, Purdue University, November, 1988.

[4] Thomas Becker and Volker Weispfenning. Grobner bases : a computational approach to commutative algebra. Springer-Verlag, New York, 1993. (written in cooperation with Heinz Kredel).

[5] Bruno Buchberger. Gröbner basis: An algorithmic method in polynomial ideal theory. In N. K. Bose, editor, Multidimensional Systems Theory, Mathematics and its Applications, chapter 6, pages 184–229. D.Reidel Publishing Company, 1985.

[6] David Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms : an introduction to computational algebraic geometry and commutative algebra. Springer-Verlag, New York, 1992.

[7] Leonard E. Dixon. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Amer. J. of Math., 35:413–426, 1913.

[8] T. Dubé, B. Mishra, and C. K. Yap. Admissible orderings and bounds for Gröbner bases normal form algorithm. Report 88, NYU-Courant Institute, Robotics Laboratory, 1986.

[9] Wolfgang Gröbner. Moderne Algebraische Geometrie. Springer-Verlag, Vienna, 1949.

[10] B. Mishra and C. K. Yap. Notes on Gröbner bases. Information Sciences, 48:219–252, 1989.

[11] Bhubaneswar Mishra. Algorithmic Algebra. Springer-Verlag, 1993. Texts and Monographs in Computer Science Series.

[12] L. Robbiano. Term orderings on the polynomial ring. EUROCAL ’85, pages 513–517, 1985. Lecture Notes in Computer Science No. 204.

[13] L. Robbiano. On the theory of graded structures. Journal of Symbolic Computation, 2:139–170, 1986.

[14] Lorenzo Robbiano, editor. Computational Aspects of Commutative Algebra. Academic Press, London, 1989.

[15] Bernd Sturmfels. Algorithms in Invariant Theory. Springer-Verlag, Vienna, 1993.

[16] Wen tsün Wu. Mechanical Theorem Proving in Geometries: Basic Principles. Springer-Verlag, 1994. (Tr. from Chinese by X. Jin and D. Wang).

[17] Oscar Zariski and Pierre Samuel. Commutative Algebra, volume 2. Springer-Verlag, New York, 1975.