## Buchberger’s algorithm for computing Gröbner bases terminates in finitely many steps

Let $F$ be a field and fix a monomial order on $R = F[x_1, \ldots, x_n]$. Let $I \subseteq R$ be an ideal and suppose $G = \{g_1, \ldots, g_m\}$ is a generating set for $I$. Prove that if $S(g_i,g_j) \equiv r \not\equiv 0$ mod $G$, then the ideal $(LT(g_1), \ldots, LT(g_m), LT(r))$ is strictly larger than the ideal $(LT(g_1), \ldots, LT(g_m))$. Conclude that Buchberger’s algorithm for computing Gröbner bases terminates in finitely many steps.

Suppose $G = \{g_1, \ldots, g_m\}$ is a generating set for the ideal $I \subseteq R$, and suppose that $S(g_i,g_j) \not\equiv 0$ mod $G$ for some $i$ and $j$. Choose $r \in R$ such that $S(g_i,g_j) \equiv r$ mod $G$ and such that no nonzero term in $r$ is divisible by any $LT(g_k)$. (That is, let $r$ be the remainder of $S(g_i,g_j)$ when divided by $G$ using general polynomial division.) Let $A = (LT(g_1), \ldots, LT(g_m), LT(r))$ and let $B = (LT(g_1), \ldots, LT(g_m))$. We certainly have $B \subseteq A$. Suppose now that $A \subseteq B$. In particular, $LT(r) \in B$. Since $B$ is a monomial ideal, by this previous exercise, every nonzero term in $r$ is divisible by some $LT(g_k)$. Thus $r = 0$, a contradiction. Hence the inclusion $B \subseteq A$ is strict.

Now recall Buchberger’s algorithm:

We are given an ideal $I = (G)$ with $G = \{g_1,\ldots,g_m\}$.

1. If $S(g_i,g_j) \equiv 0$ mod $G$ for all $i < j$, then halt and return $G$.
2. If $S(g_i,g_j) \equiv r \not\equiv 0$ mod $G$ for some $i < j$, then append $r$ to $G$ and start over.

Suppose that this algorithm does not terminate. Then we may construct a function $a : \mathbb{N}^+ \rightarrow R$ as follows: for $1 \leq i \leq m$, let $a_i = LT(g_i)$. For $i \geq 1$, let $a_{m+i}$ be the leading term of the remainder $r$ obtained at the $i$th step in Buchberger’s algorithm. Now $A = \{a_i\}_{i \in \mathbb{N}^+}$ is an infinite set; by this previous exercise, there is a finite subset $B \subseteq A$ such that $(A) = (B)$. Let $k$ be the largest index such that $a_k \in B$. In particular, the leading term of the $k+1$th remainder $r$ is in $B \subseteq (LT(g_1), \ldots, LT(g_m), LT(r_1), \ldots, LT(r_k))$, a contradiction. Thus in fact Buchberger’s algorithm terminates in a finite number of steps.