Gröbner basis

In computer algebra and computational algebraic geometry, a Gröbner basis is a particular kind of generating subset of an ideal in a polynomial ring. Given a Gröbner basis of an ideal I of the polynomial ring R in variables X, Y, ..., T, over a field K, it is computationally simple to decide whether a given polynomial P(X, Y, ..., T) belongs to I, or not. That means that calculations in the factor ring R/I are decidable, in the sense that P mod I and Q mod I can be compared to see if P-Q mod I is 0. That is a prerequisite for using such rings in practice. In the case of a single variable X, there is no need for the theory since polynomial long division suffices. In the case of several variables, however, we may need to compute with various monomials such as X²Y³ and XY⁷, without knowing which has priority (is the dominant term in a polynomial). The use of Gröbner basis algorithms removes the difficulty, in a definite way.

The fundamental fact about Gröbner bases is that they exist; and, as shown by basic work of Buchberger, they are effectively computable for fields K of practical importance, by a simple if possibly long-winded elimination method. The main theoretical burden of the work is the correctness of Buchberger's algorithm: that is, it is known to terminate in a Gröbner basis.

In detail, given initially a finite set of generators for the ideal I, we can take any two, P and Q, and add to our list MP - NQ where M and N are monomials chosen to make the top term in that combination cancel. We can decide what is the top term by some ordering of lexicographic type (X > Y > Z, say); choice of the ordering gives some computational flexibility. Once that is done, once and for all, the monomials M and N are determinate up to possible constants, by an obvious recipe: for example to make top terms X²Y³ and XY⁷ cancel we multiply the first by M = Y⁴ and the second by N = X, and subtract.

The algorithm is then simply to saturate the list: eventually 'nothing new' will result. This generalises the Euclidean algorithm, for polynomials in one variable, where one of M and N can always be taken as 1, and the degree always goes down (hence we shall reach an end point). In this case termination comes out of the so-called Dickson's lemma.

The Gröbner basis algorithm can certainly be slow to terminate in the worst case; but is of practical use.