All three statements are exactly the properties guaranteed by the Division Algorithm; we merely fix a choice of quotients and remainder for each \(f\).

1. The leading monomials \(\text{LM}(g)\) of elements \(g \in I \setminus \{ 0\} \) generate the monomial ideal \(\langle \text{LM}(g) \mid g \in I \setminus \{ 0\} \rangle \). Since \(\text{LM}(g)\) and \(\text{LT}(g)\) differ by a nonzero constant, this ideal equals \(\langle \text{LT}(g) \mid g \in I \setminus \{ 0\} \rangle = \langle \text{LT}(I) \rangle \). Thus, \(\langle \text{LT}(I) \rangle \) is a monomial ideal.

2. Since \(\langle \text{LT}(I) \rangle \) is generated by the monomials \(\text{LM}(g)\) for \(g \in I \setminus \{ 0\} \), Dickson’s Lemma tells us that \(\langle \text{LT}(I) \rangle = \langle \text{LM}(g_1), \dots , \text{LM}(g_t) \rangle \) for finitely many \(g_1, \dots , g_t \in I\). Since \(\text{LM}(g_i)\) differs from \(\text{LT}(g_i)\) by a nonzero constant, it follows that \(\langle \text{LT}(I) \rangle = \langle \text{LT}(g_1), \dots , \text{LT}(g_t) \rangle \). This completes the proof.

(1) The span condition. We claim that

Indeed, since \(G\setminus \{ 0\} \subseteq G\), we have \(\langle \operatorname {LT}(G\setminus \{ 0\} )\rangle \subseteq \langle \operatorname {LT}(G)\rangle \). For the reverse inclusion, let \(\operatorname {LT}(g)\) be a generator with \(g\in G\). If \(g\neq 0\), then \(g\in G\setminus \{ 0\} \) and hence \(\operatorname {LT}(g)\in \langle \operatorname {LT}(G\setminus \{ 0\} )\rangle \). If \(g=0\), then \(\operatorname {LT}(g)=\operatorname {LT}(0)=0\), and \(0\) belongs to every ideal, so again \(\operatorname {LT}(g)\in \langle \operatorname {LT}(G\setminus \{ 0\} )\rangle \). Thus the two generated ideals coincide.

(2) The membership condition. Assume first that \(G\subseteq I\). Then clearly \(G\setminus \{ 0\} \subseteq I\). Conversely, assume \(G\setminus \{ 0\} \subseteq I\). Let \(g\in G\). If \(g=0\) then \(g\in I\) since \(0\in I\). If \(g\neq 0\) then \(g\in G\setminus \{ 0\} \), hence \(g\in I\). Therefore \(G\subseteq I\).

Combining (1) and (2), we see that

as claimed.

The division algorithm gives \(f = q_1 g_1 + \cdots + q_t g_t + r\), where \(r\) satisfies (i). We can also satisfy (ii) by setting \(g = q_1 g_1 + \cdots + q_t g_t \in I\). This proves the existence of \(r\). To prove uniqueness, suppose \(f = g+r = g'+r'\) satisfy (i) and (ii). Then \(r-r' = g' - g \in I\), so that if \(r \ne r'\), then \(\text{LT}(r-r') \in \langle \text{LT}(I) \rangle = \langle \text{LT}(g_1), \dots , \text{LT}(g_t) \rangle \). By Lemma 16, it follows that \(\text{LT}(r-r')\) is divisible by some \(\text{LT}(g_i)\). This is impossible since no term of \(r, r'\) is divisible by one of \(\text{LT}(g_1), \dots , \text{LT}(g_t)\). Thus \(r-r'\) must be zero, and uniqueness is proved. The final part of the proposition follows from the uniqueness of \(r\).

If the remainder is zero, then we have already observed that \(f \in I\). Conversely, given \(f \in I\), then \(f = f + 0\) satisfies the two conditions of Proposition 27. It follows that \(0\) is the remainder of \(f\) on division by \(G\).

Let \(d_i = \text{LC}(p_i)\), so that \(d_i x^\delta \) is the leading term of \(p_i\). Since the sum \(\sum _{i=1}^s p_i\) has strictly smaller multidegree, it follows easily that \(\sum _{i=1}^s d_i = 0\).

Next observe that since \(p_i\) and \(p_j\) have the same leading monomial, their S-polynomial reduces to

It follows that

However, \(\sum _{i=1}^s d_i = 0\) implies \(d_1 + \cdots + d_{s-1} = -d_s\), so that (2) reduces to

Thus, \(\sum _{i=1}^s p_i\) is a sum of S-polynomials of the desired form, and equation (1) makes it easy to see that \(S(p_i, p_j)\) has multidegree \({\lt}\delta \). The lemma is proved.

By hypothesis, \(\operatorname {multideg}(p_i) = \operatorname {multideg}(p_j) = \delta \), which implies \(\delta = \alpha ^{(i)} + \operatorname {multideg}(g_i)\) and \(\delta = \alpha ^{(j)} + \operatorname {multideg}(g_j)\). The leading terms are \(\operatorname {LT}(p_i) = c_i \operatorname {LC}(g_i) x^\delta \) and \(\operatorname {LT}(p_j) = c_j \operatorname {LC}(g_j) x^\delta \). Let \(\gamma _{ij}\) be the exponent of \(\operatorname {lcm}(\operatorname {LM}(g_i), \operatorname {LM}(g_j))\).

On the one hand, the left-hand side simplifies to:

On the other hand, the right-hand side expands to:

The two sides are equal, which completes the proof.

\(\Rightarrow \): If \(G\) is a Gröbner basis, then since \(S(g_i, g_j) \in I\), the remainder on division by \(G\) is zero by Corollary 28.

\(\Leftarrow \): Let \(f \in I\) be nonzero. We will show that \(\text{LT}(f) \in \langle \text{LT}(g_1), \dots , \text{LT}(g_t)\rangle \) as follows. Write

From Lemma 14, it follows that

The strategy of the proof is to pick the most efficient representation of \(f\), meaning that among all expressions \(f = \sum _{i=1}^t h_i g_i\), we pick one for which

is minimal. The minimal \(\delta \) exists by the well-ordering property of our monomial ordering. By (3), it follows that \(\text{multideg}(f) \le \delta \).

If equality occurs, then \(\text{multideg}(f) = \text{multideg}(h_i g_i)\) for some \(i\). This easily implies that \(\text{LT}(f)\) is divisible by \(\text{LT}(g_i)\). Then \(\text{LT}(f) \in \langle \text{LT}(g_1), \dots , \text{LT}(g_t)\rangle \), which is what we want to prove.

It remains to consider the case when the minimal \(\delta \) satisfies \(\text{multideg}(f) {\lt} \delta \). We will use \(S(g_i, g_j) \overline{\hspace{1.5em}}^G 0\) for \(i \ne j\) to find a new expression for \(f\) that decreases \(\delta \). This will contradict the minimality of \(\delta \) and complete the proof.

Given an expression \(f = \sum _{i=1}^t h_i g_i\) with minimal \(\delta \), we begin by isolating the part of the sum where multidegree \(\delta \) occurs:

The monomials appearing in the second and third sums on the second line all have multidegree \({\lt}\delta \). Then \(\text{multideg}(f) {\lt} \delta \) means that the first sum on the second line also has multidegree \({\lt}\delta \).

The key to decreasing \(\delta \) is to rewrite the first sum in two stages: use Lemma 30 to rewrite the first sum in terms of S-polynomials, and then use \(S(g_i, g_j) \overline{\hspace{1.5em}}^G 0\) to rewrite the S-polynomials without cancellation.

To express the first sum on the second line of (4) using S-polynomials, note that

satisfies the hypothesis of Lemma 30 since each \(p_i = \text{LT}(h_i) g_i\) has multidegree \(\delta \) and the sum has multidegree \({\lt}\delta \). Hence, the first sum is a linear combination with coefficients in \(k\) of the S-polynomials \(S(p_i, p_j)\). In Exercise 31, you will verify that

where \(x^{\gamma _{ij}} = \text{lcm}(\text{LM}(g_i), \text{LM}(g_j))\). It follows that the first sum (5) is a linear combination of \(S(g_i, g_j)\) for certain pairs \((i, j)\).

Consider one of these S-polynomials \(S(g_i, g_j)\). Since \(S(g_i, g_j) \overline{\hspace{1.5em}}^G 0\), the division algorithm (Theorem 3 of §3) gives an expression

where \(A_l \in k[x_1, \dots , x_n]\) and

when \(A_l g_l \ne 0\). Now multiply each side of (6) by \(x^{\delta - \gamma _{ij}}\) to obtain

where \(B_l = x^{\delta - \gamma _{ij}} A_l\). Then (7) implies that when \(B_l g_l \ne 0\), we have

since \(\text{LT}(S(g_i, g_j)) {\lt} \text{lcm}(\text{LM}(g_i), \text{LM}(g_j)) = x^{\gamma _{ij}}\) by Exercise 7.

It follows that the first sum (5) is a linear combination of certain \(x^{\delta - \gamma _{ij}} S(g_i, g_j)\), each of which satisfies (8) and (9). Hence we can write the first sum as

with the property that when \(\tilde{B}_l g_l \ne 0\), we have

Substituting (10) into the second line of (4) gives an expression for \(f\) as a polynomial combination of the \(g_i\)’s where all terms have multidegree \({\lt}\delta \). This contradicts the minimality of \(\delta \) and completes the proof.

We begin with some frequently used notation. If \(G = \{ g_1, \ldots , g_t \} \), then \(\langle G \rangle \) and \(\langle \operatorname {LT}(G) \rangle \) will denote the following ideals:

Turning to the proof of the theorem, we first show that \(G \subseteq I\) holds at every stage of the algorithm. This is true initially, and whenever we enlarge \(G\), we do so by adding the remainder \(r = \overline{S(p,q)}^{G'}\) for \(p,q \in G' \subseteq G\). Thus, if \(G \subseteq I\), then \(p,q \in I\) and, hence, \(S(p,q) \in I\), and since we are dividing by \(G' \subseteq I\), we get \(G \cup \{ r\} \subseteq I\). We also note that \(G\) contains the given basis \(F\) of \(I\), so that \(G\) is actually a basis of \(I\).

The algorithm terminates when \(G = G'\), which means that \(r = \overline{S(p,q)}^{G'} = 0\) for all \(p,q \in G\). Hence \(G\) is a Gröbner basis of \(\langle G \rangle = I\) by Theorem 6 of §6.

It remains to prove that the algorithm terminates. We need to consider what happens after each pass through the main loop. The set \(G\) consists of \(G'\) (the old \(G\)) together with the nonzero remainders of \(S\)-polynomials of elements of \(G'\). Then

Since \(G' \subseteq G\). Furthermore, if \(G' \ne G\), we claim that \(\langle \operatorname {LT}(G') \rangle \) is strictly smaller than \(\langle \operatorname {LT}(G) \rangle \). To see this, suppose that a nonzero remainder \(r\) of an \(S\)-polynomial has been adjoined to \(G\). Since \(r\) is a remainder on division by \(G'\), \(\operatorname {LT}(r)\) is not divisible by the leading terms of elements of \(G'\), and thus \(\operatorname {LT}(r) \notin \langle \operatorname {LT}(G') \rangle \) by Lemma 2 of §4. Yet \(\operatorname {LT}(r) \in \langle \operatorname {LT}(G) \rangle \), which proves our claim.

By (1), the ideals \(\langle \operatorname {LT}(G') \rangle \) from successive iterations of the loop form an ascending chain of ideals in \(k[x_1, \ldots , x_n]\). Thus, the ACC (Theorem 7 of §5) implies that after a finite number of iterations the chain will stabilize, so that \(\langle \operatorname {LT}(G') \rangle = \langle \operatorname {LT}(G) \rangle \) must happen eventually. By the previous paragraph, this implies that \(G' = G\), so that the algorithm must terminate after a finite number of steps.

We know that \(\langle \operatorname {LT}(G)\rangle = \langle \operatorname {LT}(I)\rangle \). If \(\operatorname {LT}(p) \in \langle \operatorname {LT}(G \setminus \{ p\} )\rangle \), then we have \(\langle \operatorname {LT}(G \setminus \{ p\} )\rangle = \langle \operatorname {LT}(G)\rangle \). By definition, it follows that \(G \setminus \{ p\} \) is also a Gröbner basis for \(I\).