Computation in ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 11, February 21 Scribe: Todd Mateer

Let I be any ideal in ${\mathbb F}[x_1, \dots, x_n]$. For $f,g \in {\mathbb F}[x_1, \dots, x_n]$, we say that $f \equiv g \pmod{{\mathbf I}}$ (i.e. f is congruent to g modulo I) if $f - g \in {\mathbf I}$. For example, if $f \in {\mathbf I}$, then $f \equiv 0 \pmod{{\mathbf I}}$. The following properties on congruence are easy to verify.

If $f_{1} \equiv g_{1} \pmod{{\mathbf I}}$ and $f_{2} \equiv g_{2}\pmod{{\mathbf I}}$, then
(1) $f_{1} + f_{2} \equiv g_{1} + g_{2}\pmod{{\mathbf I}}$
(2) $f_{1} \cdot f_{2} \equiv g_{1} \cdot g_2 \pmod{{\mathbf I}}$
(3) $h \cdot f_{1} \equiv h \cdot g_{1}\pmod{{\mathbf I}}$ for any $h \in {\mathbb F}[x_1, \dots, x_n]$.

Note that the converse of property (3) is not true, that is, if $h \cdot f \equiv h \cdot g\pmod{{\mathbf I}}$, one may not have $f \equiv g \pmod{{\mathbf I}}$.

The congruence relation above is an equivalence relation, so ${\mathbb F}[x_1, \dots, x_n]$ is partitioned into equivalence classes, called congruence classes modulo I. Each $f\in {\mathbb F}[x_1,\dots,x_n]$ is in a unique congruence class, namely $f + {\mathbf I}= \{f + h : h \in {\mathbf I}\}$, often denoted by $\bar{f}$ or [f]. For $f,g \in {\mathbb F}[x_1, \dots, x_n]$, we have f + I= g + I (as sets) iff $f \equiv g \pmod{{\mathbf I}}$. The collection of all congruence classes is denoted by ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$. The elements in ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ can also be viewed as polynomials in ${\mathbb F}[x_1, \dots, x_n]$with two polynomials f and g identified whenever $f \equiv g \pmod{{\mathbf I}}$.

Now one can define addition and multiplication in ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ as

$$[f]+ [g] = [f+g], \ \ [f]\cdot [g] = [fg],$$

which are simply polynomial addition and multiplication modulo I. The properties (1) and (2) above imply that the two operations are well-defined and make ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ into a ring. This ring is commutative and contains the field ${\mathbb F}$. It is also called an ${\mathbb F}$-algebra.

Fix any monomial order on ${\mathbb F}[x_1, \dots, x_n]$. For any ideal I in ${\mathbb F}[x_1, \dots, x_n]$, define

$$B({\mathbf I}) = \{\alpha \in {\mathbb N}^{n} : x^{\alpha} \notin \mbox{lt}({\mathbf I})\} \subseteq {\mathbb N}^{n}$$

the set of exponent vectors $\alpha \in {\mathbb N}^n$ such that $x^{\alpha}$ is not the leading term of any polynomial in I. We will often write B for B(I). Let $G=\{g_1, \cdots, g_t\}$ be a Gröbner basis for I (under the same monomial order). We know that $x^{\alpha} \in \mbox{lt}({\mathbf I})$ iff $x^{\alpha}$ is divisible by some $\mbox{lt}(g_i)$, $1\leq{i}\leq{t}$. Hence B consists of all the monomials not divisible by $\mbox{lt}(g_i)$, $1\leq{i}\leq{t}$.

Example 11.1   Let ${\mathbf I}= \left<f(x)\right> \subseteq {\mathbb F}[x]$ (univariate) where f has degree m. Then

$$\mbox{lt}({\mathbf I}) = \{x^{m}, x^{m+1}, ...... \}$$

$$B = \{0,1, ... , m-1\}.$$

Then

$$\mbox{Span}(B) = \{g \in {\mathbb F}[x] : \deg g < m\},$$

and the elements 1, x, x², ... , x^m-1 form a basis for ${\mathbb F}[x]/(f(x))$ as a vector space over ${\mathbb F}$.

Example 11.2   Let ${\mathbf I}= \left<y^{2} - x^{3}\right> \subseteq {\mathbb F}[x,y]$. First, let us use lexicographic order with y > x. Then

$$\mbox{lt}({\mathbf I}) = \{x^{i}y^{j}\cdot y^{2} : (i,j) \in {\mathbb N}^{2} \}$$

and

$$B = \{(i,j): j=0,1, \mbox{ and } i \in {\mathbb N}\}$$

as illustrated in Figure 11.1, where $\mbox{lt}({\mathbf I})$ lies in the shaded region and B in unshaded.

Figure 11.1: Illustration of Example 11.2 (y > x case)

Now, let us use lexicographic order with x > y. Then

$$\mbox{lt}({\mathbf I}) = \{x^{i}y^{j}\cdot x^{3} : (i,j) \in {\mathbb N}^{2}\}$$

and

$$B = \{(i,j) : i=0,1,2 \mbox{ and }, j \in {\mathbb N}\}$$

as illustrated in Figure 11.2.

Figure 11.2: Illustration of Example 11.2 (x > y case)

Example 11.3   Let ${\mathbf I}= \left<xy^{3} - x^{2}, x^{3}y^{2} - y\right> \subseteq {\mathbb Q}[x,y]$First, let us use graded lexicographic order with x > y. Then a Gröbner basis G is given by

$$G = \{x^{3}y^{2} - y, x^{4} - y^{2}, xy^{3} - x^{2}, y^{4} - xy\}$$

with

$$\left<\mbox{lt}({\mathbf I})\right> = \left<\mbox{lt}(G)\right> = \left<x^{3}y^{2}, x^{4}, xy^{3}, y^{4}\right>$$

and

$$B = \{(0,0), (1,0), (2,0), (3,0), (0,1), (1,1), (2,1), (3,1),(0,2), (1,2), (2,2), (0,3)\}$$

as shown in Figure 11.3.

Figure 11.3: Illustration of Example 11.3 (x > y case)

Now use graded lexicographic order with y > x. Then

$$G = \{y - x^{7}, x^{12} - x^{2}\}$$

is a Gröbner basis for I and

$$B = \{(i,0) : 0 \leq i \leq 11\}$$

as shown in Figure 11.4.

Figure 11.4: Illustration of Example 11.3 (y > x case)

The above examples show that the ``shape'' of B relies heavily on the monomial order used.

Lemma 11.4   Let I be an ideal in ${\mathbb F}[x_1, \dots, x_n]$. Fix any monomial order and a Gröbner basis G for I. Then B(I) is finite iff $\mbox{lt}(G)$ contains some power of each variable x_i, $1 \leq i \leq n$.

Proof. Certainly, if B(I) is finite then for each variable x_i, only finitely many powers of x_i can lie in B(I) and the rest must be in $\mbox{lt}({\mathbf I})$. In particular $x_{i}^{m_{i}} \in \mbox{lt}({\mathbf I})$ for some integer m_i. Since G is a Gröbner basis for I, x_i^m_i is divisible by the leading term of some $g\in G$, which then implies that $\mbox{lt}(g)$ is a power of x_i.

Conversely, suppose that $x_{i}^{m_{i}} \in \mbox{lt}(G)$ for some integers m_i, $1 \leq i \leq n$. For any monomial $x^{\alpha}=x_i^{\alpha_1} \cdots x_n^{\alpha_n}$, if $\alpha_i > m_i$for some i then $x^{\alpha}$ is divisible by x_i^m_i, so $x^{\alpha} \in \mbox{lt}({\mathbf I})$. Hence $x^{\alpha}$ can lie in B(I) only if $\alpha_i < m_i$ for all $1 \leq i \leq n$, and there are only finitely many choices for such $\alpha$. $\Box$

For a nonzero polynomial $f = \sum a_{\alpha} x^{\alpha} \in {\mathbb F}[x_1, \dots, x_n]$, its support is defined to be

$$\mbox{Supp}(f) = \{\alpha: a_{\alpha} \ne 0\},$$

the set of exponent vectors of monomials in f with nonzero coefficients. If f=0, we make the convention that $\mbox{Supp}(f) = \emptyset$. Now for any subset $B \subseteq {\mathbb N}^n$, define

$$\mbox{Span}(B) = \{ f \in {\mathbb F}[x_1, \dots, x_n]: \mbox{Supp}(f) \subseteq B\},$$

that is, $\mbox{Span}(B)$ is the set of polynomials whose nonzero terms have exponent vectors lying in B.

Lemma 11.5   Let I be an ideal in ${\mathbb F}[x_1, \dots, x_n]$. Fix a monomial order. Then

(a)

The monomials $x^{\alpha}, \alpha \in B({\mathbf I})$ are linearly independent modulo I. That is, if

$$a_{1} x^{\alpha_1} + \cdots + a_{k} x^{\alpha_k} \equiv 0 \pmod{{\mathbf I}}$$

for some $k \geq 1$, $\alpha_1, \ldots, \alpha_k \in B({\mathbf I})$, and $a_1, \ldots, a_{k} \in {\mathbb F}$, then $a_{1} = \ldots = a_{k} =0$.

(b)

For every $f\in {\mathbb F}[x_1,\dots,x_n]$, there is a unique $r \in \mbox{Span}(B({\mathbf I}))$such that $f \equiv r \pmod{{\mathbf I}}$.

Proof. (a) Suppose $a_1 x^{\alpha_1} + \cdots + a_k x^{\alpha_k} \equiv 0 \pmod{{\mathbf I}}$. Then $a_1 x^{\alpha_1} + \cdots + a_k x^{\alpha_k} \in {\mathbf I}$, hence it must have remainder zero on division by G, as G is a Gröbner basis for I. If not all a_i are zero then the leading term, say $x^{\alpha_i}$, of $a_1 x^{\alpha_1} + \cdots + a_k x^{\alpha_k}$must be divisible by $\mbox{lt}(g)$ for some $g\in G$, which means that $x^{\alpha_i} \in \mbox{lt}({\mathbf I})$, contradicting to the assumption that $x^{\alpha_i} \in B({\mathbf I})$. Hence all a_i must be zero, so follows the linear independence.

(b) Let $G=\{g_1, \ldots, g_t\}$ be a Gröbner basis for the monomial order that defines B(I). For each $f\in {\mathbb F}[x_1,\dots,x_n]$, on division by G, f can be written as

$$f = h_1 g_1 + \cdots + h_tg_t + r$$

where $h_1, \ldots, h_t \in {\mathbb F}[x_1, \dots, x_n]$ and r either is 0 or has no terms divisible by any leading terms of G. Hence $r \in \mbox{Span}(B({\mathbf I}))$ and $f \equiv r \pmod{{\mathbf I}}$ (as $h_1 g_1 + \cdots + h_tg_t \in {\mathbf I}$). The uniqueness follows from part (a). $\Box$