Gröbner Bases

3 Reduced Gröbner bases and Applications

Let’s work this out for \((x+y,x^2+xy+y^2)\), \(x>y\) as before. We saw \(S(x+y,x^2+xy+y^2) = -y^2\) so we can add \(y^2\) to our list of generators. \(S(x+y,y^2) = y^2(x+y)-xy^2 = y^3 \mapsto 0\) and \(S(x^2+xy+y^2,y^2)=y^2(x^2+xy+y^2)-x^2y^2=xy^3+y^4 \mapsto 0\), so we see \((x+y,x^2+xy+y^2,y^2)\) is a Gröbner basis. Note however that the leading term of \(x^2+xy+y^2\) has the leading term of \(x+y\) as a divisor. This means it can be removed by Proposition 2.2. We are left with \((x+y,y^2)\). This is a minimal Gröbner basis as no more terms can be removed.

Definition 3.1. A minimal Gröbner basis is one with a minimal number of elements.

Proposition 3.2. We can always get a minimal Gröbner basis from a Gröbner basis as above, by removing redundant terms. The leading coefficients and number of terms of a minimal Gröbner basis for a fixed ideal \(I\) is unique.

Proof. This follows from the observation that for an ideal generated by monomials, there is a unique minimal monic generating set of monomials. □

Note that minimal Gröbner bases are not unique even though their size and leading coefficients are. For example, \((x+y,y^2)\) and \((x+y+y^2,y^2)\) are both Gröbner bases of the same ideal. To get true uniqueness we need a slightly stronger condition.

Definition 3.3. A reduced Gröbner basis is one in which none of the leading terms of any element divide any of the terms of the others and the leading terms are monic.

A reduced Gröbner basis is in particular a minimal Gröbner basis. For example, \((x+y,y^2)\) is an example, and \((x+y+y^2,y^2)\) is a non-example. We can always make a Gröbner basis reduced by performing the division algorithm on a term with the rest of the terms until it is reduced. For example, performing it on \((x+y+y^2,y^2)\), we get \(x+y+y^2-1(y^2)=x+y\) as the result for \(x+y\), and \(y^2\) stays as it is. In particular we get back \((x+y,y^2)\). Here is the reason we introduced reduced Gröbner bases:

Proposition 3.4. Every ideal has a unique reduced Gröbner basis.

Proof. By Proposition 3 we know the leading coefficients and number of elements are unique. So given two reduced Gröbner bases \(\{f_1,\dots ,f_n\},\{g_1,\dots ,g_n\}\) we can subtract terms with the same leading coefficient and apply the division algorithm to see that we must get \(0\) or else one of the Gröbner bases isn’t reduced. □

This yields a way to check if two ideals are equal, namely computing their reduced Gröbner bases. For example, the ideals \((xy^2+y^3+x+y,y^2)\) and \((x+y,x^2+xy+y^2)\) have the same reduced Gröbner basis, \((x+y,y^2)\) so are the same.

We can also use Gröbner bases to try to solve systems of polynomial equations, similarly to the Gauss-Jordan elimination that is used to solve systems of linear equations. This is the beginning of elimination theory, something developed by Emmy Noether and her students. To do this, we must choose a lexicographical ordering, which will specify in which order we eliminate variables. Then we have:

Proposition 3.5 (Elimination). Suppose our ordering is (lex) \(x_1>\dots >x_n\). Then if \(G\) is a Gröbner basis for \(I\), then \(G \cap K[x_2,...,x_n]\) is a Gröbner basis of \(I \cap K[x_2,\dots ,x_n]\).

Proof. Consider using the division algorithm of \(G\) on \(f \in I \cap K[x_2,\dots ,x_n]\). As \(x_1 > x_2\) we will never use any elements of \(G\) with \(x_1\), but will still get to \(0\) as \(G\) is a Gröbner basis. Then in the division algorithm we must be using only elements of \(G \cap K[x_2,\dots ,x_n]\) so by Proposition 2.2 we are done. □

This allows us to solve systems of equations when there are finitely many solutions. For example, consider the ellipse \(2x^2 + 2xy + y^2 - 2x - 2y\) and the circle \(x^2 + y^2- 1\). We can find their points of intersection via elimination. In particular, we would like to find zeros of the ideal \(2x^2 + 2xy + y^2 - 2x - 2y,x^2 + y^2- 1\). To do this, we compute its Gröbner basis under the ordering \(x>y\), giving \((2x+y^2+5y^3 -2,5y^4 -4y^3)\). Then we eliminate \(x\) and solve \(5y^4-4y^3 = 0\), which gives \(y = 0,\frac {4}{5}\). We then substitute this in for \(y\) to find the corresponding solutions in x, giving us \((1,0),(-\frac {3}{5},\frac {4}{5})\) as our two points of intersection.

Elimination can also be used to compute intersections of ideals (sums and products are easy). In order to do so, we introduce an auxiliary variable \(t\) and eliminate it. In particular, \(I\cap J = K[x_1,\dots ,x_n]\cap (tI+(1-t)J)\), and we can compute the right hand side using elimination. To see the equality above, note that something of the form \(tf+(1-t)g\) doesn’t involve \(t\) iff \(f=g\).

Here is an example of computing \(I\cap J\) using elimination. Suppose we want to find \((y^2,xy,x^2) \cap (x)\). We consider \((ty^2,txy,+tx^2,-tx+x)\) and find a Gröbner basis with the ordering \(t>x>y\). We get \((tx-x,ty^2,x^2,xy)\) as our reduced Gröbner basis, so \((xy,y^2)\) is the intersection.

Elimination has other computational applications as well. For example, one may want to saturate an ideal \(I\) with respect to a polynomial \(f\). This can be done by considering the ideal \(I + (1-tf)\) and eliminating \(t\). The reason this works is because by adding in \(1-tf\) we are sending \(I\) to the ideal it corresponds to in the localization, and by eliminating \(t\) we are intersecting it with our original ring, and by the correspondence of ideals for localization, this yields the saturation.

We can use this idea of localization to also tell if \(f \in \sqrt {I}\). In particular, \(f \in \sqrt {I}\) iff \(I+(1-tf) = (1)\) and this condition can be computed by looking at the Gröbner basis of \(I+(1-tf)\).

Finally we can compute ideal quotients \((I:J)\) using elimination. First note that it suffices to consider \(J\) principle as \((I:(f_1,\dots ,f_n)) = \cap _1^n(I:(f_i))\). Then note that if \(G \subset I \cap (f_i)\) is a generating set of \(I\cap (f_i)\), then \(\frac {G}{f_i} :=\{\frac {g}{f_i}|g \in G\}\) generates \((I:(f_i))\). Thus we can compute this using Gröbner bases.

Some final remarks: This is just the beginning of what Gröbner bases are good for. For example, they can compute radicals of general ideals, although this is more complicated (first reduce to 0-dimensional case, then treat perfect and non-perfect fields separately). They can also compute the primary decomposition of an ideal. The theory of Gröbner bases also extends to rings other than finitely generated K-algebras, for example there is an analogous theory for polynomial rings over principle ideal rings.