Gröbner Bases (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 9, February 14 Scribe: Virgínia Rodrigues

Theorem 9.1   Every ideal in ${\mathbb F}[x_1, \dots, x_n]$ has a Gröbner basis.

Proof. Let I be a nonzero ideal in ${\mathbb F}[x_1, \dots, x_n]$ and consider the ideal $\left<\mbox{lt}({\mathbf I})\right>$. By Hilbert Basis Theorem, there exist $h_1,\dots,h_s$ $\in {\mathbb F}[x_1, \dots, x_n]$ such that $\left<\mbox{lt}({\mathbf I})\right>=\left<h_1,\dots,h_s\right>.$Since $\left<\mbox{lt}({\mathbf I})\right>$ is generated by the leading terms of elements of I, each h_i is a linear combination of finitely many leading terms of polynomials in I. This means that there are finitely many polynomials $g_1,\dots,g_t \in {\mathbf I}$ such that $h_i \in \left<\mbox{lt}(g_1),\dots,\mbox{lt}(g_t)\right>$, for all $1 \leq i \leq s$. Hence

$$\left<\mbox{lt}({\mathbf I})\right>=\left<h_1,\dots,h_s\right... ...ox{lt}(g_t)\right>\subseteq\left<\mbox{lt}({\mathbf I})\right>,$$

as $g_1,\dots,g_t \in {\mathbf I}$. Therefore, $\left<\mbox{lt}({\mathbf I})\right>=\left<\mbox{lt}(g_1),\dots,\mbox{lt}(g_t)\right>$ and so $\{g_1,\dots,g_t\}$ is a Gröbner basis. $\Box$

Finding Gröbner Bases. Let us illustrate by an example. Let f₁=xy²+y⁴+y-1, f₂=xy+y³-y+1 and ${\mathbf I}=\left<f_1,f_2\right>\subseteq{\mathbb Q}[x,y]$. Use lex order with x>y. Like in Euclidean Algorithm we do long division:

$$\begin{array}{lclll} r_{-1} &=& xy^2+y^4+y-1 && =f_1,\\ r_0 ... ..._2,\\ r_2 &=& xy+1 &= r_0-yr_1 &=-yf_1+(y^2+1)f_2. \end{array}$$

The algorithm gets stuck, since none of the leading terms of r₁ and r₂is divisible by the other. But note that ${\mathbf I}=\left<r_1,r_2\right>$ and

$$\left<\mbox{lt}(f_1),\mbox{lt}(f_2)\right>=\left<xy^2,xy\righ... ...\left<y^2,xy\right>=\left<\mbox{lt}(r_1),\mbox{lt}(r_2)\right>.$$

So $\{r_1,r_2\}$ is a ``better'' basis for I than $\{f_1, f_2\}$.

Is $\{r_1,r_2\}$ a Gröbner basis of I? Let us examine the elements in ${\mathbf I}=\left<r_1,r_2\right>$. A nonzero $f \in {\mathbf I}$ is of the form

$$f=h_1r_1+h_2r_2=h_1\cdot (y^2-1)+h_2 \cdot (xy+1),$$

for some $h_1,\ h_2 \in {\mathbb Q}[x,y]$. What is $\mbox{lt}(f)$? Certainly,

$$\mbox{lt}(h_1\cdot (y^2-1)) = \mbox{lt}(h_1) \cdot y^2$$

and

$$\mbox{lt}(h_2\cdot (xy+1)) = \mbox{lt}(h_2)\cdot xy.$$

If they don't cancel then $\mbox{lt}(f)$ is one of them and it is possible to divide f by $\{r_1,r_2\}$. Suppose they cancel. Then

$$\mbox{lt}(h_1)\cdot y^2=-\mbox{lt}(h_2) \cdot xy.$$

So $y\mid\mbox{lt}(h_2)$ and $x\mid\mbox{lt}(h_1)$. Let h₁=-x, h₂=y and

r₃ = h₁r₁+h₂ r₂= -x(y²-1)+y(xy+1) = x+y.

Then $r_3 \in {\mathbf I}$. But $\mbox{lt}(r_3)=x \not\in \left<\mbox{lt}(r_1),\mbox{lt}(r_2)\right>$, so $\{r_1,r_2\}$ is not a Gröbner basis of I. Then we add r₃ to $\{r_1,r_2\}$ and consider the new basis $\{r_1,r_2,r_3\}$. Is it a Gröbner basis of I?

Apply long division to r₁, r₂ and r₃:

$$\begin{array}{lclll} r_1 &=& y^2-1 & & = f_1-yf_2,\\ r_2 &=&... ... r_1+r_4 & = (xy+y^3-y+1) f_1 + (-xy-y^4-y +1) f_2. \end{array}$$

Thus,

$$\left<r_1,r_2,r_3\right>=\left<r_3,r_4\right>$$

and

$$\left<\mbox{lt}(r_3),\mbox{lt}(r_4)\right>=\left<x,y^2\right>... ...\left<y^2,xy\right>=\left<\mbox{lt}(r_1),\mbox{lt}(r_2)\right>.$$

Is $\{r_3,r_4\}$ a Gröbner basis of I? Each nonzero $f \in {\mathbf I}$ is of the form

$$f=h_1r_3+h_2r_4=h_1\cdot (x+y)+h_2\cdot(-y^2+1),$$

for some $h_1,\ h_2 \in {\mathbb Q}[x,y]$. If the leading terms cancel then $\mbox{lt}(h_1)\cdot x=\mbox{lt}(h_2) \cdot y^2.$ So, $x\mid\mbox{lt}(h_2)$ and $y^2\mid\mbox{lt}(h_1)$. Consider

r₆=y²r₃+xr₄=y²(x+y)+x(-y²+1)=x+y³.

Divide r₆ by r₃ and r₄:

r₆=r₃-yr₄ +0.

The remainder is zero.

Claim: $\{r_3,r_4\}$ is a Gröbner basis for Iwhere

$$\begin{array}{lclcl} r_3 &= & x+y &=& (-x-y^2) f_1 + (xy+y^3+... ...&= & -y^2+1 &=& (xy+y^3-y) f_1 + (-xy^2-y^3+1) f_2. \end{array}$$

This is due to Buchberger's Criterion described below.

The construction of r₃ from r₁ and r₂ or of r₆ from r₃ and r₄ is a so-called S-polynomial. In general we have

Definition 9.2   Let $f,g \in {\mathbb F}[x_1, \dots, x_n]$, nonzero. The S-polynomial of f and g is defined as follows. Suppose

$$\mbox{mdeg}(f) = \alpha = (\alpha_1,\dots,\alpha_n) \in {\mathbb N}^{n}$$

and

$$\mbox{mdeg}(g) = \beta = (\beta_1,\dots,\beta_n) \in {\mathbb N}^{n}.$$

Let $\gamma=(\gamma_1,\dots,\gamma_n)$ where $\gamma_i=\min\{\alpha_i,\beta_i\}, \ 1\leq i\leq n$, so $\gcd(\mbox{lt}(f),\mbox{lt}(g))=\gcd(x^\alpha,x^\beta)=x^\gamma$. Then the S-polynomial of f and gis defined as

$$S(f,g)=\mbox{lc}(g)x^{\beta-\gamma}f-\mbox{lc}(f)x^{\alpha-\g... ... \frac{\mbox{lt}(g)}{x^\gamma}f-\frac{\mbox{lt}(f)}{x^\gamma}g.$$

Here the leading terms in the two expressions on the right hand side cancel. Hence

 

$$\mbox{lt}(S(f,g)) < \frac{\mbox{lt}(f) \mbox{lt}(g)}{\gcd(\mbox{lt}(f), \mbox{lt}(g))}.$$ (13)

For example, let f=3 xy²z+1 and g=2xz³+ z³. Use lex order with x>y>z. Then

$$\alpha=(1,2,1), \ \ \beta = (1,0,3), \ \ \mbox{and } \gamma=(1,0,1).$$

Hence $\alpha-\gamma=(0,2,0)$, $\alpha-\beta=(0,0,2)$ and

S(f,g)= 2 x⁰ y⁰ z³ f - 3 x⁰ y² z⁰ g = -3 y²z² + 2 z².

Buchberger's Criterion. Let ${\mathbf I}\subseteq {\mathbb F}[x_1, \dots, x_n]$ be any ideal. Then a basis $G=\{g_1,\dots,g_t\}$ for I is a Gröbner basis if and only if for all pairs i,j, with $1\leq i<j\leq t$, S(g_i,g_j) has remainder 0 under the division by G.