Gröbner Bases (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 8, February 12 Scribe: Jira Limbupasiriporn

Recall that for any ideal ${\mathbf I}\subseteq {\mathbb F}[x_1, \dots, x_n]$and any $g_1, \dots, g_s \in I$, $\{ g_1, \dots , g_s \}$ is called a Gröbner basis of I if $<\mbox{lt}({\mathbf I})> = <\mbox{lt}(g_1), \dots ,\mbox{lt}(g_s)>$, that is, the leading term of every nonzero $f \in {\mathbf I}$ is divisible by some $\mbox{lt}(g_i)$.

Lemma 8.1   A Gröbner basis for I is a basis for I, and every nonzero $f \in {\mathbf I}$ always has the remainder zero under division by a Gröbner basis.

Proof. Let $G=\{ g_1, \dots, g_s \}$ be a Gröbner basis for I. Then for any nonzero $r \in {\mathbf I}$, $\mbox{lt}(r)$ is divisible by $\mbox{lt}(g_i)$for some $1 \leq i \leq s$. Hence $\mbox{mdeg}(\mbox{lt}(g_i)) \leq \mbox{mdeg}(\mbox{lt}(r))$and $\mbox{lt}(r)/\mbox{lt}(g_i)$ is a polynomial (with only one term) in ${\mathbb F}[x_1, \dots, x_n]$. Let

$$r_1 = r - \frac{\mbox{lt}(r)}{\mbox{lt}(g_i)} \cdot g_i.$$

Then r₁ is still in I. Note that the leading term of r is cancelled out in r₁ so either r₁=0 or $r_1 \ne 0$ with $\mbox{mdeg}(r_1) < \mbox{mdeg}(r)$. This shows that under division of G every nonzero $r \in {\mathbf I}$ can always be reduced to a remainder $r_1 \in {\mathbf I}$ so that either r₁=0or r₁ has a smaller leading term.

Now for any nonzero $f \in {\mathbf I}$, we can apply the above process repeatedly to f and its remainders. Note that the multidegrees of the remainders decrease (strictly), but since there is no infinite decreasing sequence in ${\mathbb N}^n$, we see that the division process must terminate with the remainder 0 after a finite number of steps and at that time we have

$$0 = f-(h_1 g_1+ \dots + h_s g_s)$$

for some $h_1, \dots, h_s \in {\mathbb F}[x_1, \dots, x_n]$. This means that by division of a Gröbner basis $G=\{ g_1, \dots, g_s \}$every nonzero $f \in {\mathbf I}$ can be expressed as $f=h_1 g_1+ \dots + h_s g_s$for some $h_1, \dots, h_s \in {\mathbb F}[x_1, \dots, x_n]$. This proves the lemma. $\Box$

A direct consequence of this lemma is that every polynomial in ${\mathbb F}[x_1, \dots, x_n]$has a unique remainder under division by a Gröbner basis.

To prove the existence of Gröbner bases, we need the following result.

Hilbert basis theorem. Every ideal in ${\mathbb F}[x_1, \dots, x_n]$ has a finite basis.

We should mention that a ring R is called Noetherian if every ideal in R is finitely generated. Hilbert Basis theorem says that the polynomial ring ${\mathbb F}[x_1, \dots, x_n]$ is a Noetherian ring. One can easily show that a Noetherian ring has no infinite (strictly) increasing chains of ideals, that is, every ascending chain of ideals must terminate. The above proof of Hilbert basis theorem, the inductive part, also shows that if a ring R is Noetherian then so is R[x].

Another direct consequence of Hilbert Basis theorem is that for any monomial order on ${\mathbb F}[x_1, \dots, x_n]$ there is no infinite decreasing sequence of monomials (or equivalently no infinite decreasing sequence in ${\mathbb N}^n$). To see this, let $\alpha_1, \alpha_2, \cdots$ be any sequence in ${\mathbb N}^n$. Let I be the ideal in ${\mathbb F}[x_1, \dots, x_n]$ generated by $x^{\alpha_i}$, $i \geq 1$. By Hilbert Basis theorem, I has a finite basis. Since each element of such a basis is a combination of finitely many of $x^{\alpha_i}$, we see that I is actually generated by finitely many of $x^{\alpha_i}$, say ${\mathbf I}=<x^{\alpha_1}, \cdots, x^{\alpha_m}>$. For each $i \geq 1$, since $x^{\alpha_i} \in {\mathbf I}$, we have

$$x^{\alpha_i} = \sum_{j=1}^{m} h_j x^{\alpha_j}$$

for some $h_j \in {\mathbb F}[x_1, \dots, x_n]$. Hence $x^{\alpha_i}$ must appear in some $h_j x^{\alpha_j}$, so divisible by $x^{\alpha_j}$ where $1 \leq j \leq m$. This means that, for each $i \geq 0$, $x^{\alpha_i} \geq x^{\alpha_j}$ for some $1 \leq j \leq m$. Therefore it is impossible to have an infinite decreasing sequence $x^{\alpha_1} > \cdots > x^{\alpha_i} > \cdots$.