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 ith 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+1th 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.

Advertisements
Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: