Gröbner Bases

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 6, February 5 Scribe: Fred Block

Let ${\mathbb F}$ be any field, and let $\mathbf{R} ={\mathbb F}[x_1,\dots,x_n]$ denote the polynomial ring.

We consider the following problems:

Problem 6.1   Given $f_1,\dots,f_m \in \mathbf{R}$, decide if they have a common zero in ${\mathbb F}^n$.

Problem 6.2   Given $g,f_1,\dots,f_m \in \mathbf{R}$, decide if g can be written as

$$g=h_1 f_1+\dots+h_m f_m$$ (11)

for some $h_1,\dots,h_m \in \mathbf{R}$.

Let $<f_1,\dots,f_m>$ denote the set of all polynomials in (11) for all possible $h_1,\dots,h_m \in \mathbf{R}$, which is an ideal of R.

In general a nonempty subset ${\mathbf I}\subseteq {\mathbf R}$ is called an ideal if

1.

$a,b \in {\mathbf I}\Rightarrow a-b \in {\mathbf I}$, and

2.

$a\in {\mathbf I}, b \in {\mathbf R}\Rightarrow ab\in{\mathbf I}$

One can check that $<f_1,\dots,f_m>$ is an ideal of R. If ${\mathbf I}=<f_1,\dots,f_m>$, we say that I is generated by $f_1,\dots,f_m$, or $\{f_1,\dots,f_m\}$ is a basis for I. An ideal may have many bases and different bases may have different number of elements. Also, the elements of a basis for an ideal need not be linearly independent over ${\mathbb F}$ but can be easily reduced to one with linearly independent elements.

The ideal ${\mathbf I}=<f_1,\dots,f_m>$ captures the common zeros of $f_1,\dots,f_m$ nicely in that:

1.

Every common zero of $f_1,\dots,f_m$ is a zero of every $g \in {\mathbf I}$.

2.

If I has another basis, say ${\mathbf I}=<g_1,\dots,g_s>$, then a point in ${\mathbb F}^n$ is a common zero of $f_1,\dots,f_m$ iff it is a common zero of $g_1,\dots,g_s$.

A Gröbner basis for an ideal ${\mathbf I}=<f_1,\dots,f_m> \subseteq {\mathbf R}$is some ``nice'' basis for I such that we can ``see'' the common zeros of the ideal, hence Problem 6.1 can be easily solved (when ${\mathbb F}$ is algebraically closed). In terms of ideals, Problem 6.2 is the membership problem, that is, decide if g is a member of ${\mathbf I}=<f_1,\dots,f_m>$. A Gröbner basis will also allow this problem easily solved.

Examples:

1.

Suppose that $f_1,\dots,f_m \in \mathbf{R}$ are linear. Applying Gaussian elimination gives a ``triangular'' system $g_1,\dots,g_s$. Then $<f_1,\dots,f_m>=<g_1,\dots,g_s>$, and the zeros of $g_1,\dots,h_s$can be easily determined. Here, $<g_1,\dots,g_s>$ is a Gröbner basis.

2.

Let $f_1, f_2 \in {\mathbb F}[x]$ (univariable polynomials). Apply the EEA to get $d(x)=\gcd(f_1,f_2)$. Then <f₁,f₂>=<d(x)>. Here, d(x) is a Gröbner basis for <f₁,f₂>.

In some sense, a Gröbner basis is a common generalization of Gaussian elimination and the Euclidean algorithm.

Monomial Ordering. In Gaussian elimination, one needs to put the variables in some order, usually as $x_1>x_2>\dots>x_n$. For long division of univariate polynomials, one also needs to write the terms in decreasing order, namely $x^n>x^{n-1}>\dots>x>1$. When dealing with multivariate polynomials, ordering of terms is also needed, and there are many ways to order!

Notation: ${\mathbb N}=\{0,1,2,\dots\}$ and ${\mathbb N}^n$ the set of all n-tuples with entries in ${\mathbb N}$. For $\alpha=(\alpha_1,\dots,\alpha_n) \in {\mathbb N}^n$, write $x^{\alpha}=x_1^{\alpha_1} \dots x_n^{\alpha_n}$, called a monomial. Hence there is a one-to-one correspondence between monomials in ${\mathbb F}[x_1, \dots, x_n]$ and elements in ${\mathbb N}^n$.

A monomial order on ${\mathbb F}[x_1, \dots, x_n]$ is any relation > on ${\mathbb N}^n$ such that

1.

For any $\alpha, \beta \in {\mathbb N}^n$, either $\alpha=\beta$, $\alpha>\beta$, or $\alpha<\beta$ (so a total ordering).

2.

For every $\alpha \in {\mathbb N}^n$, if $\alpha \ne 0$ then $\alpha > 0$.

3.

If $\alpha>\beta$ and $\gamma \in {\mathbb N}^n$, then $\alpha+\gamma>\beta+\gamma$.

For any two monomials $x^{\alpha}$ and $x^{\beta}$, we say $x^{\alpha}> x^{\beta}$, $x^{\alpha}= x^{\beta}$ or $x^{\alpha}< x^{\beta}$, if $\alpha>\beta$, $\alpha=\beta$ or $\alpha<\beta$, respectively. The first two conditions mean that the terms in a polynomial can be arranged in decreasing order with the constant term last. The third condition means that if a polynomial is multiplied by a monomial, the ordering of its terms will not change, which is important for long division of polynomials. Also, the last two conditions imply that if $x^{\alpha}$ is divisible by $x^{\beta}$, but not equal, then $x^{\alpha}> x^{\beta}$.

Examples: Let $\alpha=(\alpha_1,\dots,\alpha_n), \beta=(\beta_1,\dots,\beta_n) \in {\mathbb N}^n$.

1.

Lexicographical order or lex order (lex): $\alpha>\beta$ if $\alpha_1=\beta_1,\dots, \alpha_{i-1}=\beta_{i-1}$ but $\alpha_i>\beta_i$ for some $1\le i\le n$.

2.

Graded lex order (grlex): $\alpha>\beta$ if $\vert\alpha\vert=\sum_{i=1}^{n}\alpha_i > \sum_{i=1}^{n}\beta_i=\vert\beta\vert$ or if $\vert\alpha\vert=\vert\beta\vert$ but $\alpha>\beta$ in lex order.

3.

Reverse lexicographical order (not a monomial order by itself): $\alpha>\beta$ if $\alpha_n=\beta_n,\dots, \alpha_{i+1}=\beta_{i+1}$but $\alpha_{i}<\beta_{i}$ for some $1\le i\le n$.

4.

Graded reverse lex order (grevlex): $\alpha>\beta$ if $\vert\alpha\vert>\vert\beta\vert$ or if $\vert\alpha\vert=\vert\beta\vert$but $\alpha>\beta$ in reverse lex order.

It should be mentioned that a monomial order is actually a well-ordering on ${\mathbb N}^n$, which means that every nonempty subset of ${\mathbb N}^n$ has a smallest element. This follows from the Hilbert basis theorem for ideals, which will be proved later. Consequently there is no infinite decreasing sequence $\alpha_1>\alpha_2>\dots$ in ${\mathbb N}^n$ for any monomial order >. This property will be important in showing that various algorithms must terminate because some term strictly decreases at certain steps of the algorithms.