1.1 A brief introduction to computational algebraic geometry  (Page 9/20)

More formally, we say that $x^{\alpha }{>}_{\text{grlex}}{x}^{\beta }$ if $deg{x}^{\alpha }>deg{x}^{\beta }$ or if $deg{x}^{\alpha }=deg{x}^{\beta }$ and $x^{\alpha }{>}_{\text{lex}}{x}^{\beta }$ . Since the partial ordering by degree and the lexicographic ordering both have the property that

the graded lexicographic order has this property as well. Since any graded order (an order in which degree is used first and then something else is used as a tie-breaker) satisfies well-ordering automatically (because there are only finitely many monomials of each degree), we see that grlex is a term order.

Example: Graded reverse lexicographic order

Perhaps one of the most frequently used term orders in practice (because it tends to result in faster computations) is graded reverse lexicographic or grevlex order. This one is perhaps a little more confusing. As the name suggests, graded reverse lexicographic order uses degree first, and uses “reverse lexicographic order” to break ties.

If we reverse the lexicographic order however, so that $x^{\alpha }{>}_{\text{revlex}}{x}^{\beta }$ if $x^{\alpha }{<}_{\text{lex}}{x}^{\beta }$ , the result isn't a monomial ordering. It fails well-ordering, because there are infinite descending sequences, e.g. in revlex order we have

However, the reverse of an order preserved under multiplication by $x^{\gamma }$ is at least still preserved under multiplication by $x^{\gamma }$ , so while reverse lexicographic order isn't a monomial order by itself, we can still use it to break ties in a graded order (for which well-ordering is automatic).

There's one final issue to defining grevlex: when we reverse the lex order, it reverses the order of the variables, but we still want to get an order with $x_1>x_2>\cdots >x_n$ in the end. Thus we start with a lex order with $x_n>\cdots >x_1$ , so that when we reverse it we get a reverse lexicographic order with $x_1{>}_{\text{revlex}}{x}_2{>}_{\text{revlex}}\cdots {>}_{\text{revlex}}{x}_n$ . We then say that $x^{\alpha }{>}_{\text{grevlex}}{x}^{\beta }$ if $deg{x}^{\alpha }>deg{x}^{\beta }$ or if $deg{x}^{\alpha }=deg{x}^{\beta }$ and $x^{\alpha }{>}_{\text{revlex}}{x}^{\beta }$ .

For example, in the graded reverse lexicographic order on $\mathbf{R}[x,y,z]$ with $x>y>z$ , we have

Basically, we order by degree first, and break ties by saying a monomial is bigger if it has a smaller power of the least significant variable. More formally, we say that $x^{\alpha }>x^{\beta }$ if $deg{x}^{\alpha }>deg{x}^{\beta }$ or if $deg{x}^{\alpha }=deg{x}^{\beta }$ and in the vector difference $\alpha -\beta$ , the rightmost non-zero entry is negative.

Exercises

1. In each part, determine whether the polynomial $f\in \mathbf{R}\left[x\right]$ is in the given ideal $I\subseteq R\left[x\right]$ . Notice that determining if $f$ lies in the ideal $⟨g⟩$ is equivalent to determining if $g$ divides $f$ . How do we use the same idea in (c) and (d), where $I=⟨g_1,g_2⟩$ ?
   1. $f\left(x\right)=x^2-3x+2$ ,         $I=⟨x-2⟩$
   2. $f\left(x\right)=x^5-4x+1$ ,         $I=⟨x^3-x^2+x⟩$
   3. $f\left(x\right)=x^2-4x+4$ ,         $I=⟨x^4-6x^2+12x-8,2x^3-10x^2+16x-8⟩$
   4. $f\left(x\right)=x^3-1$ ,                $I=⟨x^9-1,x^5+x^3-x^2-1⟩$
2. Find an ideal $I\subset \mathbf{R}\left[x\right]$ in which every element $f\in I$ is divisible by $x$ , but such that $x\notin I$ .
3. 1. Show that $⟨x-y^2,xy,y^2⟩=⟨x,y^2⟩$ .
   2. Is $⟨x-y^2,xy⟩=⟨x^2,xy⟩$ ?
4. Rewrite each of the following polynomials, ordering the terms first with the lex order, then the graded lex order, and finally the graded reverse lex order, provided that $x>y>z$ .
   1. $f(x,y,z)=2x+3y+z+x^2-z^2+x^3$
   2. $2x^2{y}^8-3x^{5}y{z}^4+xy{z}^3-x{y}^4$
   3. $7x^2{y}^{4}z-2x{y}^6+x^2{y}^2$
5. Ideals make sense in the ring of integers $\mathbf{Z}$ just as they do in polynomial rings like $\mathbf{R}\left[x\right]$ . For example, in $\mathbf{Z}$ the ideal $I=⟨a,b⟩$ consists of all integers $xa+yb$ for $x,y\in \mathbf{Z}$ .
   1. Is 10 in the ideal $I=⟨3⟩$ ?
   2. Is 2 in the ideal $I=⟨5,8⟩$ ?
   3. Is $-6$ in the ideal $I=⟨12,22⟩$ ?
   4. Is 3 in the ideal $I=⟨68,173⟩$ ?