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

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

Recall

Lemma 12.5. Suppose ${\mathbb F}$ is an algebraically closed field. If V(I) is finite, then so is B(I).

Before we can prove this lemma, we need the following result.

Hilbert's Nullstellensatz (strong form). Suppose ${\mathbb F}$ is algebraically closed and I is an ideal in ${\mathbb F}[x_1, \dots, x_n]$. For any $f\in {\mathbb F}[x_1,\dots,x_n]$, if f(P)=0 for every $P \in V({\mathbf I})$, then some power of f must lie in I.

Example 13.1   Let ${\mathbf I}= \langle (x-1)^2 \rangle\subset {\mathbb F}[x]$, so $V({\mathbf I})=\{1\}$. Suppose $f \in {\mathbb F}[x]$ such that f(1)=0. Then (x-1) divides f, implying that $f^2 \in {\mathbf I}$. f itself, however, is not in I.

Note that if ${\mathbb F}$ is NOT algebraically closed, then Hilbert's Nullstellensatz might not hold. For example, let ${\mathbb F}= {\mathbb F}_{2}= \{ 0,1 \}$, ${\mathbf I}= \langle x^2+x+1 \rangle \subseteq {\mathbb F}_{2}[x]$. Then $V({\mathbf I})=\varnothing$. For f =1, we have f(P)=0 for every $P \in V({\mathbf I})$, but $1 \notin \langle x^2+x+1 \rangle$.

Proof (of Lemma 12.5). Since V(I) is finite, for each $1 \leq i \leq n$, the i^th coordinate of points in V(I) has only finitely many values. Let $f_i \in {\mathbb F}[x_i]$ be a nonzero polynomial that vanishes at these values. Viewing f_i as a polynomial in ${\mathbb F}[x_1, \dots, x_n]$ we have f_i(P)=0 for all $P \in V({\mathbf I})$. By Hilbert's Nullstellensatz, ${f_i}^{m_i} \in {\mathbf I}$ for some m_i. The leading term of f_i^m_i is of the form x_i^n_i for some n_i, thus ${x_i}^{n_i} \in \mbox{lt}({\mathbf I})$ for $1 \leq i \leq n$. By Lemma 11.4, B(I) is finite. $\Box$

Next we want to see when equality occurs. That is, when does $\vert V({\mathbf I})\vert=\vert B({\mathbf I})\vert=dim_{{\mathbb F}}({\mathbb F}[x_1, \dots, x_n]/{\mathbf I})$?

Definition 13.2   An ideal ${\mathbf I}\subseteq {\mathbb F}[x_1, \dots, x_n]$ is called radical if, for $g \in {\mathbb F}[x_1, \dots, x_n]$, $g^m \in {\mathbf I}$ implies that $g \in {\mathbf I}$.

In the above example, ${\mathbf I}=\langle (x-1)^2 \rangle$ is not a radical ideal. In case of one variable, an ideal ${\mathbf I}=\langle f(x) \rangle \subseteq {\mathbb F}[x]$ is radical if and only if f(x) is squarefree.

Theorem 13.3   Suppose that ${\mathbb F}$ is algebraically closed and ${\mathbf I}\subset {\mathbb F}[x_1, \dots, x_n]$ an ideal with $\vert V({\mathbf I})\vert < \infty$. Then |V(I)|=|B(I)| iff I is a radical ideal.

Proof. From Lemma 12.3, we know that $\vert V({\mathbf I})\vert \leq \vert B({\mathbf I})\vert$. Let $V({\mathbf I}) = \{ P_1, \dots, P_t \}$ where t=|V(I)|. There are polynomials $f_i \in {\mathbb F}[x_1, \dots, x_n]$ such that

$$f_i(P_j)=\left\{ \begin{array}{ll} 0 & \mbox{ if } i \neq j \\ 1 & \mbox{ if } i=j. \end{array} \right.$$

We know that $f_1, \dots, f_t$ are linearly independent over ${\mathbb F}$modulo I. We claim that they actually form a basis for ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ if and only if I is radical.

Suppose first that I is radical. For any $g \in {\mathbb F}[x_1, \dots, x_n]$, define a new function

$$g_1= \sum_{i=1}^t g(P_i)\cdot f_i.$$

Note that $g_1 \in {\mathbb F}[x_1, \dots, x_n]$. Let $h=g-g_1 \in {\mathbb F}[x_1, \dots, x_n]$. Then for every $1 \leq j \leq t$,

$$h(P_j)=g(P_j)-\sum_{i=1}^t g(P_i) \cdot f_i(P_j) = g(P_j)-g(P_j) =0.$$

By Hilbert's Nullstellensatz, some power of h lies in I. Since I is radical, it follows that $h \in {\mathbf I}$. Therefore, $h \equiv 0 \pmod{{\mathbf I}}$, i.e. $g \equiv g_1 \pmod{{\mathbf I}}$. This means that every element in ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ is a linear combination of $f_1, \dots, f_t$ over ${\mathbb F}$ modulo I. Hence $\vert B({\mathbf I})\vert=dim_{{\mathbb F}}({\mathbb F}[x_1, \dots, x_n]/{\mathbf I}) \leq t$. This proves that t=|V(I)|=|B(I)| and $f_1, \dots, f_t$ form a basis for ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ over ${\mathbb F}$.

Conversely, suppose that t=|B(I)|. Let $g \in {\mathbb F}[x_1, \dots, x_n]$ be such that $g^m \in {\mathbf I}$ for some m. Then (g(P)^m = g^m(P)=0 for every $P \in V({\mathbf I})$. Hence g(P) = 0 for every $P \in V({\mathbf I})$. Since $\dim_{{\mathbb F}}({\mathbb F}[x_1, \dots, x_n]/{\mathbf I}) = \vert B({\mathbf I})\vert$, the linear independence of $f_1, \dots, f_t$ implies that they form a basis for ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ over ${\mathbb F}$. We can express g as

$$g \equiv \sum_{i=1}^t a_i f_i \pmod{{\mathbf I}}$$

for some $a_i \in {\mathbb F}$. Plugging in P_j, we see that a_j=0 for $1 \leq j \leq t$. Therefore $g \equiv 0 \pmod{{\mathbf I}}$, that is, $g \in {\mathbf I}$. This shows that I is radical. $\Box$

The functions $f_1, \dots, f_t$ constructed in the proof are very important. They are called orthogonal idempotents. That is, they satisfy

$$\begin{eqnarray*}f_i^2 &\equiv & f_i \pmod{{\mathbf I}} \mbox{ for $1 \leq i \le... ...cdot f_j &\equiv & 0 \pmod{{\mathbf I}} \mbox{ for $i \neq j$ }. \end{eqnarray*}$$

Note that ${\mathbb F}^t$ is a ring under componentwise addition and multiplication. Such a ring seems trivial, but the next theorem says that the ring ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ is nothing more!

Theorem 13.4   Suppose that ${\mathbb F}$ is algebraically closed and ${\mathbf I}\subset {\mathbb F}[x_1, \dots, x_n]$ a radical ideal with V(I) finite. Then we have the ring isomorphism

$${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}\cong {\mathbb F}^t, \mbox{ where } t=\vert V({\mathbf I})\vert.$$

Proof. Let $V({\mathbf I}) = \{ P_1, \dots, P_t \}$, and let f_i, $1\leq{i}\leq{t}$, be defined as above. We know from the proof of previous theorem that $f_1, \dots, f_t$ form a basis for ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ over ${\mathbb F}$, that is,

$${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}= {\mathbb F}f_1 + \d... ...bb F}f_t = \{ a_1f_1 + \dots + a_tf_t : a_i \in {\mathbb F}\}.$$

For any element $f\in {\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$, one has $f=a_1f_1 + \dots a_tf_t$ where a_i= f(P_i). Suppose $g=b_1f_1 + \dots b_tf_t \in {\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ is another element. Observe that

$$f+g=(a_1+b_1)f_1 + \dots + (a_t+b_t)f_t,$$

and

$$f \cdot g = \left( \sum_{i=1}^t a_if_i \right) \cdot \left( \... ...) = \sum_{i,j} a_ib_jf_if_j = (a_1b_1)f_1+ \dots + (a_tb_t)f_t.$$

Hence the following map is a ring isomorphism:

$$\phi: {\mathbb F}[x_1, \dots, x_n]/{\mathbf I}\longrightarrow... ...thbb F}^t \mbox{, with } f \mapsto (f(P_1), \dots , f(P_t) ).$$

$\Box$

This map is a Fourier Transform!!!

Remark. When I is not a radical ideal, the ring structure of ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ can also be determined quite easily. Suppose one is familiar with the concept of multiplicity of a point as a common zero of polynomials in an ideal. Also, for an integer m, denote by ${\mathbb F}_m$ the ring ${\mathbb F}[x]/(x^m)$.

Theorem. Suppose that ${\mathbb F}$ is algebraically closed and ${\mathbf I}\subset {\mathbb F}[x_1, \dots, x_n]$an ideal. Suppose further that $V({\mathbf I}) = \{P_1, \cdots, P_t\}$ (so is finite) and P_i has multiplicity m_i for $1\leq{i}\leq{t}$. Then we have the ring isomorphism

$${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}\cong {\mathbb F}_{m_1} \otimes \cdots \otimes {\mathbb F}_{m_t}.$$

The theorem implies that $\dim_{{\mathbb F}}({\mathbb F}[x_1, \dots, x_n]/{\mathbf I}) = \sum_{i=1}^{t} m_i$. Hence $\dim_{{\mathbb F}}({\mathbb F}[x_1, \dots, x_n]/{\mathbf I})$ is equal to the number of points in V(I)counted with multiplicities. To understand this theorem, one should think about the case of one variable: Let ${\mathbf I}= \langle f(x) \rangle \subset {\mathbb F}[x]$ where

$$f(x) = \prod_{i=1}^{t} (x-a_i)^{m_i}$$

with $a_1, \ldots, a_t \in {\mathbb F}$ being distinct. By the Chinese Remainder Theorem,

$${\mathbb F}[x]/(f(x)) \cong \prod_{i=1}^{t} {\mathbb F}[x]/((... ...ong {\mathbb F}_{m_1} \otimes \cdots \otimes {\mathbb F}_{m_t},$$

as ${\mathbb F}[x]/((x-a_i)^{m_i}) \cong {\mathbb F}[x]/(x^{m_i})$. So the isomorphism in the above theorem is a generalization of the Chinese Remainder Theorem!