Groebner basis

also: buchberger, s-polynomial, ideal

A generating set for a polynomial ideal whose leading terms generate the leading-term ideal, which makes the remainder of multivariate division unique and zero exactly on the ideal. Buchberger's algorithm builds one by reducing S-polynomials until none leaves a nonzero remainder.

Dividing a polynomial by a set of others is ill defined: the answer depends on the order the divisors are tried, and a nonzero remainder proves nothing about ideal membership. A Groebner basis is a generating set chosen so that pathology disappears, and the condition that does it is about leading terms:

⟨ lt (g_{1}), \dots, lt (g_{s})⟩ = lt (I)

Buchberger's algorithm computes one. For each pair, form the S-polynomial, which is constructed precisely to cancel the two leading terms:

S (f, g) = \frac{L}{lt ( f )} f - \frac{L}{lt ( g )} g, L = lcm (lm (f), lm (g))

Reduce it against the current basis; if the remainder is nonzero, it is a new element, and the pairs involving it join the queue. Termination follows from Dickson's lemma, since the leading-term ideal strictly grows at every addition.

Buchberger in grevlex on the Cox, Little and O'Shea example, run against the Part 4 Poly module.

input  : x^3 - 2*x*y ,  x^2*y + x - 2*y^2
basis  : x^2 , x*y , -1/2*x + y^2
reduces to zero: true
reduces to zero: true

The cost is the reason monomial orders matter. Buchberger is doubly exponential in the worst case, and the practical difference between lex and grevlex is routinely orders of magnitude, which is why the usual strategy is to compute in grevlex and convert afterwards. Buchberger's criteria, which discard pairs whose leading monomials are coprime or that are covered by a third, are what make it run at all.