Gröbner Bases

1 Hilbert Basis Theorem & Monomial Orderings

Gröbner bases are a great way to do computations in polynomial rings \(R[x_1,\dots ,x_n]\) which is quite useful in algebraic geometry, where such rings are viewed as the ring of functions on an affine space. They allow you to answer questions like:

• Given two ideals \(I,J\), how can you compute \(I \cap J\)?
• Given an ideal \(I\), how can you make computations in the quotient \(K[x_1,\dots ,x_n]/I\)?
• Given two ideals \(I,J\), how can you tell if they are the same?
• How can you tell if an element is in the radical of an ideal?
• How can you compute the saturation of an ideal with respect to a polynomial?
• How can we find solutions to systems of polynomial equations (when there are finitely many)?
• How can we compute the ideal quotient \((I:J)=\{r | rJ \subset I\}\)

These will all be answered here.

The fundamental idea of the Gröbner basis is seen in the proof of the Hilbert Basis Theorem:

Theorem 1.1 (Hilbert Basis Theorem). If \(R\) is Noetherian, then \(R[x]\) is too.

Proof. Fix an ideal of \(R[x]\), \(I\). Let \(L_n\) be the ideal in \(R\) of leading coefficients of terms with \(x^n\) as the leading term in \(I\). \(L_n\) stabilizes as \(n \to \infty \) as \(R\) is Noetherian. Thus by choosing polynomials whose leading terms generate \(L_n\) up till the point of stabilization we get a finite set of generators for \(I\). □

As a corollary, \(R[x_1,\dots ,x_n]\) is Noetherian (induction), but note that this inductive argument implicitly orders \(x_1\) to \(x_n\). The ideas of ordering and looking at leading terms generating an ideal give rise to Gröbner bases.

Definition 1.2. A monomial ordering is a well ordering on monomials satisfying \(a \leq b \implies ac \leq bc\) (a,b,c are monomials in \(R[x_1,...,x_n]\)).

Here are three important examples:

• (lex) We can lexicographically order monomials with \(x_1 > \dots > x_n\).
• (grlex) We can "grade" the lexicographical ordering by ordering monomials by total degree, and if they are the same degree, then by lex.
• (grevlex) We can first grade monomials by degree, and if they are the same degree, we can start from \(x_n\) going to \(x_1\), saying that \(m>n\) if \(m\) has a lower exponent on \(x_n\).

Note in all of these orderings we have \(x_1 > \dots > x_n\).

As an example consider these three orderings of the same set of monomials:

• (lex) \(x^3y,x^3y^2,x^2y^2z,x^2yz^2,x^2z^2,x^2z,x^2,xy^2z\)
• (grlex) \(x^3z^2,x^2y^2z,x^2yz^2,x^3y,x^2z^2,xy^2z,x^2z,x^2\)
• (grevlex) \(x^2y^2z,x^3z^2,x^2yz^2,x^3y,xy^2z,x^2z^2,x^2z,x^2\)