Gröbner Bases (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 10, February 19 Scribe: Jennifer van der Horst

Recall Buchberger's Criterion. Let ${\mathbf I}\subset {\mathbb F}[x_1, \dots, x_n]$ be any ideal. Then a basis $G=\{g_1,\hdots,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 the remainder 0 under division by G. Proof. Suppose first that G is a Gröbner basis for I. For each pair $1\leq i<j\leq t$, since $S(g_i,g_j) \in {\mathbf I}$, we know from Lemma 8.1 that S(g_i,g_j) always has the remainder zero under division by G.

Conversely, suppose that every S-polynomial S(g_i,g_j), $1\leq i<j\leq t$, has the remainder zero under division by G, that is, there are polynomials $h_k^{ij} \in {\mathbb F}[x_1, \dots, x_n]$ such that

$$S(g_i,g_j) = \sum_{k=1}^{t} h_k^{ij} g_k, \mbox{ with } \mb... ...) \cdot \mbox{lt}(g_j)}{\gcd(\mbox{lt}(g_i), \mbox{lt}(g_j))}.$$ (14)

Suppose on the contrary that G is not a Gröbner basis for I. Then we may choose a polynomial $f \in {\mathbf I}$ such that $\mbox{lt}(f)$ is not divisible by any $\mbox{lt}(g_i)$, $1\leq{i}\leq{t}$. Since $f \in {\mathbf I}$, we can write f as

$$f=h_1g_1+h_2g_2+\cdots+h_tg_t$$ (15)

where $h_i \in {\mathbb F}[x_1, \dots, x_n]$. Let $x^{\alpha}$ be the maximal monomial among $\mbox{lm}(h_ig_i)=\mbox{lm}(h_i)\cdot\mbox{lm}(g_i)$, $1\leq{i}\leq{t}$. We may assume that the expression for f is chosen so that $x^{\alpha}$ is minimal among all the expressions (15) and so that the number of times $x^{\alpha}$ occurs among $\mbox{lm}(h_ig_i)$, $1\leq{i}\leq{t}$, is also minimal. We want to find another expression for f that violates these minimality conditions, so a contradicton.

Since $\mbox{lt}(f)$ is not divisible by any $\mbox{lt}(g_i)$, $1\leq{i}\leq{t}$, the terms of the h_ig_i that involve $x^{\alpha}$ must cancel. In particular, there must be at least two i's such that $\mbox{lm}(h_ig_i)=x^\alpha$. We may assume for simplicity that

$$\mbox{lt}(h_1g_1)=\mbox{lt}(h_1)\cdot \mbox{lt}(g_1) =ax^\alp... ...ox{lt}(h_2g_2) = \mbox{lt}(h_2) \cdot \mbox{lt}(g_2) =bx^\alpha$$

where $a,b \in {\mathbb F}_{q}\setminus \{0\}.$ Hence $x^{\alpha}$ is divisible by $\mbox{lt}(g_1)$ and $\mbox{lt}(g_2)$, so $\mbox{lt}(h_1)$ is divisible by

$$\frac{\mbox{lt}(g_2)}{x^\gamma} \ \ \mbox{where } x^\gamma = \gcd(\mbox{lt}(g_1),\mbox{lt}(g_2)).$$

It follows that there is a monomial $c x^{\beta}$ such that

$$\mbox{lt}(h_1) = c x^{\beta} \cdot \frac{\mbox{lt}(g_2)}{x^\gamma}.$$

Now, using (14) for i=1 and j=2, we can rewrite fas

$$f = f- c x^{\beta} \left(S(g_1,g_2)-\sum_{k=1}^{t} h_k^{12} g_k \right)$$

as the second term is zero. Collecting the coefficients of g_k, we have

$$f = u_1 g_1 + u_2 g_2 + \cdots + u_t g_t$$

where

$$\begin{eqnarray*}u_1 & = & h_1 - c x^{\beta}\left(\frac{\mbox{lt}(g_2)}{x^\gamma... ... u_k & = & h_k - c x^{\beta} \left( h_k^{12}\right), \ \ k > 2. \end{eqnarray*}$$

Note that in u₁ the leading term of h₁ cancels with the leading term of the second term, so $\mbox{lt}(u_1g_1) < x^{\alpha}$. For other terms u_kg_k with k > 1, since h_k¹²g_k have lower leading terms (than $\mbox{lt}(g_1)\cdot \mbox{lt}(g_2)/x^{\gamma}$), $x^{\alpha}$ can occur in $\mbox{lt}(u_kg_k)$only if $x^{\alpha}$ occurs in $\mbox{lt}(h_kg_k)$. Hence the number of times $x^{\alpha}$ occurs among $\mbox{lt}(u_kg_k)$, $1 \leq k \leq t$, decreases by at least one. This contradicts with the minimality conditions for f. Hence G must be a Gröbner basis. $\Box$

Buchberger's criterion gives immediately an algorithm for finding Gröbner bases. Let ${\mathbf I}= \left<f_1, \cdots, f_t\right>$ be an ideal in ${\mathbb F}[x_1, \dots, x_n]$. Fix a monomial order. To get a Gröbner basis for I, put $G= \{f_1, \cdots, f_t\}$initially. Compute the S-polynomials of all pairs of polynomials in G and do long division by G. If all the remainders are zero then G is already a Gröbner basis for I, so stop. If there are nonzero remainders, add them to G. Then repeat this process for the new G. Note that at each iteration of the algorithm, the initial ideal $\left<\mbox{lt}(G)\right>$increases due to the addition of nonzero remainder which give new leading terms. Since there is no infinite increasing sequence of ideals in ${\mathbb F}[x_1, \dots, x_n]$, the process must terminate after finite many steps! This method is called Buchberger's algorithm.

In practice, the number of steps in Buchberger's algorithm can be large and double exponential in the worst case. There are several improvements to Buchberger's algorithm due to the module structure of syzygies for which S-polynomials are special cases (so the name S-polynomials). Syzygies will play a critical role in decoding of linear codes and we shall study them in more details later.

Applications. Maple examples will be added later.