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 12, February 26 Scribe: Fred Block

Let I be an ideal in ${\mathbb F}[x_1, \dots, x_n]$ and ${\mathbf R}={\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$. Fix a monomial order on ${\mathbb F}[x_1, \dots, x_n]$. Let G be a Gröbner basis for I and B=B(I) as defined in the previous lecture. By Lemma 11.5, we know that

• For each class $[f] \in {\mathbf R}$, [f]=[r] for some unique $r \in Span(B)$. So sometimes we simply write ${\mathbf R}= \mbox{Span}(B)$.

• The monomials $x^{\alpha}$, $\alpha \in B$, form a basis for R as a vector space over ${\mathbb F}$, that is,
  
  $$\vert B({\mathbf I})\vert=\dim_{{\mathbb F}}({\mathbb F}[x_1,\dots,x_n]/{\mathbf I}).$$
  
  
  These monomials are called basis monomials. They are also referred to as standard monomials sometimes.

Suppose that R is represented as $\mbox{Span}(B)$. Addition in R is easy. For multiplication in R, one needs to perform long division by G.

Example 12.1   Consider Example 11.3. For the first monomial order (x>y), the basis monomials are

1, x, x², x³, y, xy, x²y, x³y, y², xy², x² y², y³.

A Gröbner basis for I was found to be

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

so we have (modulo I)

$$x^3y^2\equiv y,\ \ x^4 \equiv y^2,\ \ xy^3 \equiv x^2,\ \ y^4 \equiv xy.$$

Now we can compute some products:

$$x^3 \cdot x^3y \equiv x^6y \equiv x^4 \cdot x^2y \equiv y^2 \cdot x^2y \equiv x^2y^3 \equiv x \cdot x^2 \equiv x^3,$$

$$x^{11} \equiv x^3 \left(x^4\right)^2 \equiv x^3 \left(y^2\right)^2 \equiv x^3 \cdot xy \equiv x^4y \equiv y^3.$$

The product should be reduced until it becomes a polynomial in $\mbox{Span}(B)$.

Example 12.2   Consider Example 11.3 again. For the second monomial order (y>x), the basis monomials are

$$1, x, x^2, \dots, x^{11}.$$

A Gröbner for I was found to be $G=\left\{y-x^7,\ x^{12}-x^2 \right\}$. Now

$$\mbox{Span}(B) = \{a_0 + a_1 x + \cdots + a_{11} x^{11}: a_i \in {\mathbb Q}\},$$

Addition and multiplication of polynomials in $\mbox{Span}(B)$ modulo Gare simply modulo x¹²-x², as y is not involved at all. So,

$${\mathbf R}={\mathbb Q}[x,y]/\left<xy^{3} - x^{2}, x^{3}y^{2} - y\right> \ \cong \ {\mathbb Q}[x]/(x^{12}-x^2).$$

Notice that with this particular monomial ordering, the ring structure of R seems simpler than its representation in Example 12.1.

Our next goal is to determine the ring structure of ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$. We shall study eigenvalues and Fourier transform in ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$. Here we consider only the case where B(I) is finite, that is, the ring ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ has finite dimension as a vector space over ${\mathbb F}$. In this case, the ring ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ is called a 0-dimensional algebra over ${\mathbb F}$.

Let

$$V({\mathbf I})= \left\{ P \in {\mathbb F}^n:\,\,f(P)=0,\,\, \forall\,\,f\in{\mathbf I}\right\},$$

i.e. the set of common zeros of I in ${\mathbb F}^n$. V(I) is called an algebraic set. It is also called a variety in the literature.

Lemma 12.3   If B(I) is finite, then V(I) is also finite. In fact, $\left\vert V({\mathbf I}) \right\vert \leq \left\vert B({\mathbf I})\right\vert$.

 

Exercise 12.4   Show how to find the required polynomials $f_1,\dots,f_m$ used in the proof.

Research Problem. Given some points $P_1, \dots, P_m \in {\mathbb F}^n$, compute a Gröbner basis for the ideal ${\mathbf I}=\{f\in {\mathbb F}[x_1, \dots, x_n]:\,\,f(P_i)=0,\,1\leq i \leq m\}$and B(I) under any given monomial order. Is it possible to compute them using ${\mathcal O}(m^2n)$ operations in ${\mathbb F}$?

In general, if V(I) is finite, then B(I) may not be finite. For example, if ${\mathbb F}= {\mathbb R}$ and ${\mathbf I}=\left< x^2+y^2 +1\right>$ then V(I) is empty as the polynomial f=x²+y² +1 has no solution in ${\mathbb R}^2$, but B(I) is infinite. Here the problem is that ${\mathbb R}$ is not algebraically closed.

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

Question. When does |V(I)|=|B(I)| if ${\mathbb F}$ is algebraically closed? Need I to be a radical ideal. Think over the ideal I=<f(x)> where f is not squarefree.