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.

Tue Mar 12 21:09:19 EST 1996