1.1 A brief introduction to computational algebraic geometry  (Page 12/20)

Essentially, the problem is that it may be possible to cancel out the leading terms of some of the $f_i$ to get new elements of $I$ with smaller leading terms.

Let's look at an example. Consider the ideal $I=⟨f_1,f_2⟩\subseteq \mathbf{R}[x,y,z]$ in graded lex order, with $f_1=x^{2}y+y^{2}z$ and $f_2=x{y}^2+z^2$ . We can try to cancel out the leading terms of $f_1$ and $f_2$ in hopes of getting a polynomial in $I$ with a new leading monomial:

To potentially find more new leading terms of $I$ that aren't in $⟨x^{2}y,x{y}^2,y^{3}z⟩$ , we might, for example try to attempt the same sort of cancellation on the leading terms of $f_1$ and $f_3$ , giving

whose leading term is already known to be in $⟨LT\left(I\right)⟩$ since it is divisible by $LT\left(f_3\right)$ . However, we can divide it by $f_3$ (along with $f_1$ and $f_2$ ) to possibly get a remainder in $I$ with a new leading term

and we see that $f_4=x^3{z}^2+xy{z}^3\in I$ so that $x^3{z}^2\in ⟨LT\left(I\right)⟩$ is a new leading term which is not divisible by any of $x^{2}y,x{y}^2,y^{3}z$ .

What we're doing is looking at pairs of polynomials in our current list of generators, $f_i$ and $f_j$ and cancelling out their leading terms, and then dividing the result by our current list of generators to potentially get an element of the ideal with a new leading term. It turns out that if we keep doing this until we no longer get anything new in this way out of any pair $(f_i,f_j)$ of our current generators, then we can stop this process and our current list of generators is a Gröbner basis.

More precisely, given monomials $x^{\alpha }$ and $x^{\beta }$ , with $\alpha =({\alpha }_1,...,{\alpha }_n)$ and $\beta =({\beta }_1,...,{\beta }_n)$ in $\mathbf{R}[x_1,...,x_n]$ , the least common multiple of $x^{\alpha }$ and $x^{\beta }$ is $x^{\gamma }$ where ${\gamma }_i=max\{{\alpha }_i,{\beta }_i\}$ . If $x^{\gamma }$ is the LCM of the leading monomials of $f$ and $g$ , then we say that the $S$ -polynomial of $f$ and $g$ is the polynomial

This is more precisely what we mean above by “cancelling the leading terms” of $f_i$ and $f_j$ .

Thus to find a Gröbner basis, we claim that all we need to do is start with some generating set of polynomials $G=\left\{f_i\right\}$ , and then keep computing $S(f_i,f_j)$ for pairs of polynomials in our set and dividing the $S$ -polynomial by the set $G$ , and adding the remainder to $G$ if it isn't zero (and hence its leading term isn't in $⟨LT\left(G\right)⟩$ yet). Eventually this process will stop This process must stop eventually, because each time a polynomial is added to $G$ , the ideal $⟨LT\left(G\right)⟩$ gets bigger, and it is impossible for there to be an infinite ascending chain $I_1⊊I_2⊊I_3⊊\cdots$ of ideals in $\mathbf{R}[x_1,...,x_n]$ . This fact is equivalent to the claim that any ideal of $\mathbf{R}[x_1,...,x_n]$ is finitely generated. (Hint: Consider $I=\bigcup I_n$ .) when division of $S(f_i,f_j)$ by the set $G$ yields a zero remainder for every pair $f_i,f_j\in G$ , and once that happens, $G$ is a Gröbner basis.

This algorithm for computing a Gröbner basis is called Buchberger's Algorithm , and it relies on the following theorem (for a proof, see Cox, Little, and O'Shea, 2.6):

Theorem (Buchberger's criterion) Let $G=\left\{⟨f_1,...f_k⟩\right\}\subset \mathbf{R}[x_1,...,x_n]$ be a set of polynomials and $I=⟨G⟩$ be the ideal they generate. Then $G$ is a Gröbner basis for $I$ if and only if for every pair $1\le i,j\le k$ , the remainder on division of $S(f_i,f_j)$ by $G$ is zero.