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

The division algorithm is useful, but it doesn't give us everything that we want by itself. For example, the polynomial $y^2-y^3$ is in the ideal $⟨x-y^2,x-y^3⟩$ , but if we try to divide $y^2-y^3$ by $x-y^2$ and $x-y^3$ in lex order, nothing happens: we get $q_1=q_2=0$ and $r=y^2-y^3$ , so the division algorithm is not telling us that it is in the ideal.

For now, we'll solve this problem by defining it away. For an ideal $I\subseteq \mathbf{R}[x_1,...,x_n]$ , we say that $f_1,...,f_k\in I$ are a Gröbner basis for $I$ if

where $⟨LT\left(I\right)⟩=⟨LT\left(f\right):f\in I⟩$ is the monomial ideal generated by the leading terms of all the polynomials in $I$ .

In our example above, $\{x-y^2,x-y^3\}$ is not a Gröbner basis for $I=⟨x-y^2,x-y^3⟩$ since $y^2=LT(y^2-y^3)$ is in $⟨LT\left(I\right)⟩$ but not in $⟨LT(x-y^2),LT(x-y^3)⟩$ . For a Gröbner basis though, the division algorithm does what we want it to.

Proposition Fix a monomial order. Suppose $f_1,...,f_k\in \mathbf{R}[x_1,...,x_n]$ are a Gröbner basis for the ideal $I=⟨f_1,...,f_n⟩$ that they generate and suppose $g\in \mathbf{R}[x_1,...,x_n]$ . Let $r$ be the remainder upon division of $g$ by $(f_1,...,f_k)$ . Then

1. $g=q_1{f}_1+\cdots +q_k{f}_k$ has a solution $(q_1,\cdots ,q_k)\in \mathbf{R}{[x_1,...,x_n]}^k$ if and only if $r=0$ , and
2. $r$ is unique in the sense that if $g=f+\tilde{r}$ with $f\in I$ and no term of $\tilde{r}$ is divisible by any $LT\left(f_i\right)$ , then $r=\tilde{r}$ .

In particular, changing the order of the $f_i$ does not change $r$ .

The first statement is the special case of the second when $r=0$ . To prove the second, we just note that $r-\tilde{r}\in I$ , so that if $r\ne \tilde{r}$ , then $LT(r-\tilde{r})\in ⟨LT\left(I\right)⟩$ . But every term of $r-\tilde{r}$ , and in particular the leading term, is not divisible by any of the $LT\left(f_i\right)$ , so that

which contradicts our assumption that $f_1,...,f_k$ is a Gröbner basis.

Thus we now “know” how to determine whether a given polynomial $g$ is in the ideal $I$ : we find a Gröbner basis for $I$ and then just use the division algorithm. At this point though, we've never even shown that any particular set of polynomials is a Gröbner basis (you're asked to show this in a very simple example on the homework). What we really want to be able to do is start with an arbitrary (finite) set of generators for an ideal and find a Gröbner basis for it. A Gröbner basis will always exist because the Hilbert basis theorem tells us that $⟨LT\left(I\right)⟩$ is generated by finitely many elements $LT\left(f_i\right)$ . This doesn't tell us anything about how to find one though.

Exercises

1. Determine whether $x^2-4\in 〈x^3,+,x^2,-,4,x,-,4,,,x^3,-,x^2,-,4,x,+,4,,,x^3,-,2,x^2,-,x,+,2〉$ .
2. 1. Compute the remainder on division of the polynomial $f=x^7{y}^2+x^3{y}^2-y+1$ by the set $\{x{y}^2-x,x-y^3\}$ with respect to the grlex order on $\mathbf{R}[x,y]$ with $x>y$ .
   2. Repeat, using the lex order.
3. If $I=⟨x^{\alpha \left(1\right)},...,x^{\alpha \left(s\right)}⟩$ is a monomial ideal, prove that a polynomial $f$ is in $I$ if and only if the remainder of $f$ on division by $x^{\alpha \left(1\right)},...,x^{\alpha \left(s\right)}$ is zero.
4. For the ideal $I=⟨2x{y}^2-x,3x^{2}y-y-1⟩$ with grlex order, show that $⟨2x{y}^2,3x^{2}y⟩⊊⟨LT\left(I\right)⟩$ .
5. 1. Show that $\{x+z,y-z\}$ is a Gröbner basis for lex order.
   2. Divide $xy$ by the ordered set $(y-z,x+z)$ .
   3. Now divide $xy$ by $(x+z,y-z)$ . How can your reconcile the different quotients?
6. Show that $\{x-y^{37},x-y^{38}\}$ is not a Gröbner basis with respect to lex order.

Buchberger's algorithm for computing gröbner bases

Given an ideal $I=⟨f_1,...,f_k⟩$ , we've seen several examples now of how it is possible that $f_1,...,f_k$ may not be a Gröbner basis for $I$ , i.e. we may have