Gröbner Bases (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 7, February 7 Scribe: Jeff Farr

Recall the monomial orders:
(1) lex: lexicographical order (plex in Maple)
(2) grlex: graded lexicographical order
(3) grevlex: graded reverse lexicographical order (tdeg in Maple)

Fix any monomial order > on ${\mathbb F}[x_1, \dots, x_n]$. For any nonzero polynomial $f\in {\mathbb F}[x_1,\dots,x_n]$, its terms can be arranged in decreasing order:

$$f= a x^{\alpha} + \sum_{\beta < \alpha} a_{\beta} x^{\beta},$$

where $a, a_{\beta} \in {\mathbb F}$ are nonzero. The first term $a x^{\alpha}$ is called the leading term of f, denoted by $\mbox{lt}(f)$. $x^{\alpha}$ is called the leading monomial of f, denoted by $\mbox{lm}(f)$, and the coefficient a of the leading term is called the leading coefficient of f, denoted by $\mbox{lc}(f)$. Also, $\alpha$ is called the multidegree of f, denoted by $\mbox{mdeg}(f)$.

Example 7.1   Let $f=4xy^2z+4z^2-5x^3+7x^2z^2 \in {\mathbb Q}[x,y,z]$. We write f in decreasing order for various monomial orders; a list [x,y,z] below means x > y > z.

1.

lex, [x,y,z]:
f = -5x³+7x²z²+4xy²z+4z², $\mbox{lt}(f)=-5x^3$, $\mbox{lc}(f)= -5$, $\mbox{lm}(f)=x^3$,
$\mbox{mdeg}(f)=(3,0,0)$.

2.

lex, [y,z,x]:
f = 4xy²z+7x²z²+4z²-5x³, $\mbox{lt}(f)=4xy^2z$, $\mbox{lc}(f)=4$, $\mbox{lm}(f)=xy^2z$,
$\mbox{mdeg}(f)=(2,1,1)$.

3.

grlex, [x,y,z]:
f = 7x²z²+4xy²z-5x³+4z², $\mbox{lt}(f)=7x^2z^2$, $\mbox{lc}(f)=7$, $\mbox{lm}(f) =x^2z^2$,
$\mbox{mdeg}(f)=(2,0,2)$.

4.

grevlex, [y,x,z]:
f = 4xy²z+7x²z²-5x³+4z², $\mbox{lt}(f)=4xy^2z$, $\mbox{lc}(f)=4$, $\mbox{lm}(f)=xy^2z$,
$\mbox{mdeg}(f)=(2,1,1)$.

Weighted degree orders. Let $\lambda:{{\mathbb N}}^n \rightarrow {\mathbb R}$ be a linear map defined as

$$\lambda(\alpha)=a_1 \alpha_1 + a_2 \alpha_2 + \dots + a_n \alpha_n \mbox{, where } a_i \in {\mathbb R}.$$

Here $\lambda$ is specified by the n-tuple $[a_1, \dots, a_n]$. We say $\lambda(\alpha)$ is the weighted degree of $x^{\alpha}$ and $\alpha>\beta$ if $\lambda(\alpha) > \lambda(\beta)$. When $a_1= \cdots = a_n=1$, $\lambda$ agrees with the total degree. One can define monomial order by first using the weighted degree $\lambda$, then breaking ties by lex or rlex if necessary.

Example 7.2   Consider orders on monomials $x^{\alpha_1} y^{\alpha_2}$ in ${\mathbb F}[x,y]$.

1.

Fix any integer $k \geq 1$. Let $\lambda(\alpha) = \alpha_1 + k \alpha_2$ and break ties by lex or rlex. Such weighted degree orders will be used in decoding algorithms later.

2.

Let $\lambda(\alpha) = \sqrt{2} \cdot \alpha_1 + \alpha_2$. Then $\lambda$ defines a monomial order by itself, since it is impossible to have ties! (To see why, just note that $\sqrt{2}$ is irrational while $\alpha_1$ and $\alpha_2$ are integers. Here $\sqrt{2}$ can be replaced by any positive irrational real number.)

In general, one can use several linear functions on ${\mathbb N}^n$ to define a monomial order on ${\mathbb F}[x_1, \dots, x_n]$, as shown by the following exercise.

Exercise 7.3   Let $\lambda_1, \ldots, \lambda_{\ell}$ be linear functions on ${\mathbb Z}^n$satisfying the following conditions:

(a)

for every nonzero $\alpha \in {\mathbb Z}^n$, at least one of $\lambda_1(\alpha), \ldots, \lambda_{\ell}(\alpha)$ is nonzero, and

(b)

for every nonzero $\alpha \in {\mathbb N}^n$, the first nonzero value of $\lambda_1(\alpha), \ldots, \lambda_{\ell}(\alpha)$ is positive.

Then $\lambda_1, \ldots, \lambda_{\ell}$ define a monomial order on ${\mathbb N}^n$as follows:

$$\alpha > \beta \mbox{ if $\lambda_1(\alpha)= \lambda_1(\beta)... ...}(\alpha)> \lambda_{i}(\beta)$ for some $1 \leq i \leq \ell$.}$$

The monomial order defined in the above exercise is called the lexicographical product of the weighted degree orders $\lambda_1, \dots, \lambda_{\ell}$. All the monomials orders we have seen so far are special cases. The lex order is defined by $\lambda_i = \alpha_i$, $1 \leq i \leq n$. The graded lex order is defined by $\lambda_0 = \alpha_1 + \cdots + \alpha_n$and $\lambda_i = \alpha_i$, $1 \leq i \leq n-1$. The graded reverse lex order is defined by $\lambda_0 = \alpha_1 + \cdots + \alpha_n$ and $\lambda_i = -\alpha_{n+1-i}$, $1 \leq i \leq n-1$.

L. Robbiano (1985) proved that every monomial order on ${\mathbb N}^n$ can be defined by the lexicographical product of some weighted degree orders $\lambda_1, \dots, \lambda_{\ell}$ with $\ell \leq n$. Such a general order can be specified by an $\ell \times n$ matrix with each row corresponds to a weighted degree order $\lambda$. If all the entries in the matrix are integers (or rational numbers) then the condition (a) above implies that one must have $\ell=n$ and the matrix must be nonsingular.

Long Division. Fix any monomial order > on ${\mathbb F}[x_1, \dots, x_n]$. Given $f, f_1, \ldots, f_m \in {\mathbb F}[x_1, \dots, x_n]$, nonzero, we can use $f_1, \ldots, f_m$ to divide f. This is possible as long as f has terms that are divisible by one of the leading terms of $f_1, \ldots, f_m$. Hence f can be written as

$$f = h_1 f_1 + \cdots + h_m f_m + r$$ (12)

where $\mbox{mdeg}(h_if_i) \leq \mbox{mdeg}(f)$, $1\leq i \leq m$, and r=0 or none of the terms in r is divisible by any $\mbox{lm}(f_i)$, $1\leq i \leq m$. The remaider r in (12) is not unique in general and it may depend on which f_i were used first in the division. We illustrate by a simple example.

Example 7.4   Let f=xy²-x, f₁=xy+1, $f_2=y^2-1 \in {\mathbb F}[x,y]$. We use lex order with x>y.

1.

Using f₂ first, we find that $f=x\cdot f_2 \in <f_1,f_2>$.

2.

Using f₁ first, we find that $f=y\cdot f_1 -(x+y)$.

Note that $x+y = y\cdot f_1 - x\cdot f_2 \in <f_1,f_2>$, but none of the terms in x+y is divisible by any of the leading terms of f₁ and f₂. This indicates that $\{f_1, f_2\}$ is not a ``nice'' basis for the ideal <f<sub>1</sub>,f<sub>2</sub>>. For a ``nice'' basis of an ideal I, every nonzero $f \in {\mathbf I}$ should always have remainder 0 when divided by the elements in the basis. This asks in particular that the leading term of every nonzero $f \in {\mathbf I}$ should be divisible by one of the leading terms of the basis elements.

Now fix any monomial order > on $\mathbf{R} ={\mathbb F}[x_1,\dots,x_n]$. Let I be any ideal in R. Define

$$\mbox{lt}({\mathbf I})= \{ \mbox{lt}(f) \vert f \in {\mathbf I}, f\ne 0\}$$

i.e., $\mbox{lt}({\mathbf I})$ the set of leading terms of all nonzero polynomials in I. Let $<\mbox{lt}({\mathbf I})>$ be the ideal generated by the monomials in $\mbox{lt}({\mathbf I})$.

Example 7.5   Let f₁=(x²-1)(x+2)², $f_2=(x^2-1)(x+3)^3 \in {{\mathbb Q}}[x]$ and I= <f₁,f₂>. Then I=<g> where $g= \gcd (f_1,f_2)=x^2-1$. Hence $\mbox{lt}({\mathbf I}) = \{x^2,x^3, x^4, \dots \}$ and $<\mbox{lt}({\mathbf I})> = x^2 \cdot {{\mathbb Q}}[x]$.

Note that

$$<\mbox{lt}(f_1),\mbox{lt}(f_2)> = <x^4, x^5> = x^4 \cdot {{\m... ...b Q}}[x] \subsetneqq <\mbox{lt}({\mathbf I})> = <\mbox{lt}(g)>.$$

So, again, $\{f_1, f_2\}$ is not a ``nice'' basis but g is. We could also start with a linear system and use Gaussian elimination to obtain a Grö bner basis.

Definition. Fix any monomial order. Let I be any ideal in ${\mathbb F}[x_1, \dots, x_n]$. Let $g_1, \dots , g_s \in {\mathbf I}$. Then the set $\{ g_1, \dots , g_s \}$ is called a Gröbner basis if $<\mbox{lt}({\mathbf I})> = <\mbox{lt}(g_1), \dots ,\mbox{lt}(g_s)>$. That is, the leading term of every nonzero polynomial in I is divisible by some $\mbox{lt}(g_i)$, $1 \leq i \leq s$.

Lemma 7.6   A Gröbner basis for I is actually a basis for I and every nonzero polynomial in I always has remaider 0 under division by a Gröbner basis.