next up previous contents
Next: The vector space Up: S-polynomials and Buchberger's Previous: S-polynomials and Buchberger's

Buchberger's Algorithm

The closure of Gröbner bases with respect to S-polynomials suggests the simple algorithm of computing , taking its remainder, and if it is not zero, add it to the basis (as it is a combination of ideal elements, it is certainly in the ideal). Amazingly, this works---since we might be adding a polynomial every time, we have to check that eventually the process terminates, and indeed it does. This is Buchberger's algorithm, in its simplest and most expensive form.

Remark. When I attended ISSAC '89 in Portland, Oregon, which was my first ISSAC, I spent some time socializing. (This is only to be expected by those who know me). Several notables, including David Stoutemyer (the principal author of Derive), Fritz Schwarz, and James Davenport (who is the author of a fundamental monograph on the Risch integration algorithm), and I went to sample the fine products of the local microbreweries. We found one quite close to the hotel that had a very nice selection of inexpensive but tasty beverages, and had a genteel discussion. Several jugs later, Fritz Schwarz somehow had asked James Davenport about the proof of finiteness of Buchberger's algorithm. Davenport claimed that he could prove it in two lines, given the statement of the theorem. General disbelief followed---but he did it, then and there, on a napkin. General hilarity on noticing not two, but three lines. Chagrin, on Davenport's side---until he noticed and pointed out to all of us that the first line merely stated what was to be proved! I still have the napkin, by the way.

Example. We prove nothing here (the proof in Cox, Little and O'Shea is essentially the same as the one on my napkin), but give instead a simple example. We use the grevlex order (tdeg) for the ideal .

, and the remainder on division by I is again just . So we add this to the list, and call it .

Now , and so the remainder on division by I is 0. But , which on division by I gives -2xy, not zero. So we add -2xy to the basis, and call it . Now . We find as before that and reduce to zero. Also, so on division by F we get 0.

Now , which has remainder , not zero. So we add this to the basis, and call it . Now when we compute all S-polynomials and reduce them modulo F we get zero in all cases. Thus we have found that

is a Gröbner basis for I.

We now continue with the final recipe.



next up previous contents
Next: The vector space Up: S-polynomials and Buchberger's Previous: S-polynomials and Buchberger's



Robert Corless
Tue Mar 12 21:09:19 EST 1996