What was the motive for inventing Gröbner bases?

Question

How did professor Buchberger discover Gröbner (Groebner) bases for polynomial ideals? What was the problem(s) that lead to such a discovery?

Answer 1

Fortunately, Buchberger himself described the context of his discovery, see Historical background to Gröbner's paper by Abramson. The method, in general outline, was known to Gröbner long before the Buchberger's thesis (1965). In the 1950 paper Über die Eliminationstheorie (Abramson's English translation) it is applied to finding bases of integrals of differential equations, but he alludes to many other applications:

"For about 17 years, I have applied and tested these methods in the most varied and complicated cases, and I believe I can say, on the basis of my experiences, that they in fact represent a useful and valuable tool for the solution of these and similar ideal theoretic tasks in every case. Because I have often been asked how one can most easily find the reduced representation of a polynomial ideal, I have now decided to publish the essential features of these methods, omitting the details."

In 1964 Gröbner explained the method in examples at a seminar, but it was not clear when the algorithm would terminate. Buchberger took up the problem, already in a general and abstract form, in 1965. In brief, it was to determine effectively whether a generated polynomial ideal is zero dimensional or not, or, when it was, whether only finitely many residue classes remained and whether they were linearly independent. What he later called Gröbner bases were designed to resolve these questions. Here is Buchberger's own account of the details:

"The method mentioned here is the method Gröbner presented in his seminar 1964, in which I took part as a student and after which I asked Gröbner whether I could take the study of his method as my PhD thesis subject. In fact, Gröbner described the method only in examples, the method was not really described as a general algorithm. More importantly, it was not at all clear when exactly, for a given input polynomial set, the method could be terminated. This point is subtle for the following reasons:

• Even if one knew (in a specific) example that the polynomial ideal is zero dimensional (i.e. the residue class ring has a finite vector space basis) it was by no means clear whether or not by Gröbner’s method a situation will always be reached, in which only finitely many linearly independent residue classes remained (which is the case if each indeterminate appears purely in one of the basis polyomials).

• Even if a situation was reached in which, by the above criterion, it was clear that only finitely many residue classes remained, it was not at all clear whether they are linearly independent: By considering higher degrees, it might well happen that dependencies could appear that were not known at the moment when the method was stopped. Hence, the question was: How high do we have to go with the degrees of the polynomials in order to be sure that no more linear dependencies will appear?

• In general, if an arbitrary polynomial set is given, we do not know whether or not the polynomial ideal generated is zero dimensional or not. This question just needs the computation of a Gröbner basis for deciding it!

These were basically the questions Gröbner gave to me for my PhD thesis. In fact, they were not clearly separated but, in his wording, the question was: When can one terminate computation by this method?

On the way towards answering these questions, I then invented the notion of S-polynomials and showed its relevance for answering all three questions. Based on S-polynomials, I then gave a new algorithm that computes polynomials sets (which I later called Gröbner bases) from which as a by-product also a linearly independent vector space basis of the residue class ring of the input polynomial set could be read off. For this algorithm I also gave a complete correctness and termination proof (which guarantees termination also for the non-zero dimensional case).