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

Let be a field and fix a monomial order on . Let be an ideal and suppose is a generating set for . Prove that if mod , then the ideal is strictly larger than the ideal . Conclude that Buchberger’s algorithm for computing Gröbner bases terminates in finitely many steps.

Suppose is a generating set for the ideal , and suppose that mod for some and . Choose such that mod and such that no nonzero term in is divisible by any . (That is, let be the remainder of when divided by using general polynomial division.) Let and let . We certainly have . Suppose now that . In particular, . Since is a monomial ideal, by this previous exercise, every nonzero term in is divisible by some . Thus , a contradiction. Hence the inclusion is strict.

Now recall Buchberger’s algorithm:

We are given an ideal with .

- If mod for all , then halt and return .
- If mod for some , then append to and start over.

Suppose that this algorithm does not terminate. Then we may construct a function as follows: for , let . For , let be the leading term of the remainder obtained at the th step in Buchberger’s algorithm. Now is an infinite set; by this previous exercise, there is a finite subset such that . Let be the largest index such that . In particular, the leading term of the th remainder is in , a contradiction. Thus in fact Buchberger’s algorithm terminates in a finite number of steps.

### Like this:

Like Loading...

*Related*

or leave a trackback:

Trackback URL.