Monomial Orderings

 

As you will discover using the Groebner applet, different monomial orderings not only lead to different Groebner bases for the same ideal, but they also affect substantially the computation. So let's have a deeper look at what a monomial ordering is.
Definition 1. Let N denote the non-negative integers. Let a = (a1,a2,...,an) be a vector in Nn and let x1,x2,...,xn be any n variables. Then a monomial xa in x1,x2,...,xn is defined as the product xa = x1a1x2a2...xnan. Moreover the total degree of xa is defined as |a| = a1 + a2 + ... + an.
This definition establishes a one-to-one correspondence between Nn and the monomials xa = x1a1x2a2...xnan in K[x1,x2,...,xn].
Definition 2. An ordering, >, on Nn is called admissible when it satisfies the following conditions:
  1. > is a total ordering on Nn;
  2. if a,b,g are vector in Nn and a > b, then a + g > b + g;
  3. > is a well-ordering on Nn, i.e. every nonempty subset of Nn has a smallest element under >.
Thanks to the one-to-one correspondence between Nn and the monomials xa = x1a1x2a2...xnan, it is clear that if > is an admissible ordering on Nn then > is an ordering on the monomials, i.e. if a > b then xa > xb.

Since a polynomial is a linear combination of monomials, we would like to rearrange unambiguously the terms in a polynomial in descending (or ascending) order. So we must be able to compare each monomials to establish their proper relative positions. This means that, given any two monomials xa and xb, exactly one of the three statements xa > xb , xa = xb, xa < xb must be true. This is what is required by the first condition in the definition above.
The second condition makes sure that the relative ordering of terms in a polynomial will remain unchanged after it has been multiplied by a monomial.
The third condition is very important for a monomial ordering. It states that every strictly decreasing sequence in Nn a(1)>a(2)>a(3)>... eventually terminates. This is used to show that various algorithms must terminate because some term strictly decreases at each step of the algorithm (as in the Division Algorithm in K[x1,x2,...,xn]).

Given parts (1.) and (2.), one can show that part (3.) is equivalent to a >= 0 for all a in Nn. This makes it easier to test if a given ordering is admissible. So we can reformulate the previous definition as follows:
Definition 2 (reformulation). An ordering, >, on Nn is called admissible (or a monomial order) when it satisfies the following conditions:
  1. > is a total ordering on Nn;
  2. if a,b,g are vector in Nn and a > b, then a + g > b + g;
  3. a >= 0 for all a in Nn.
There are several monomial orderings. We will define the most important three, leaving the proof of the fact that they are monomial orderings to the reader.
Definition 3. Let a and b be in Nn.
  1. Lexicographic Order (lex): a >lex b iff the left-most nonzero entry in a-b is positive.
  2. Graded Order (grlex): a >grlex b iff |a| > |b| or (|a| = |b| and a >lex b).
  3. Graded Reverse Order (grevlex): a >grevlex b iff |a| > |b| or (|a| = |b| and the right-most nonzero entry in a-b is negative).
Note that for each ordering there are n! different orders, corresponding to how the variables are ordered. For instance, if the variables are x and y, then we have one lex (or grlex or grevlex) order with x > y and a second with y > x. To avoid this, we will assume the following ordering on x1,x2,...,xn: x1 > x2 > ... > xn, unless otherwise stated. When we work with polynomials in two or three variables, we will call the variables x, y, z instead of x1,x2,x3.

Examples.

  1. (2,1,3) >lex (1,4,2) since the left-most nonzero entry in (1,-3,1) is positive. Hence x2yz3 >lex xy4z2.
  2. (3,2,3) >grlex (2,4,2) since |(3,2,3)| = 8 = |(2,4,2)| and (3,2,3) >lex (2,4,2). Hence x3y2z3 >grlex x2y4z2.
  3. (2,4,2) >grevlex (2,3,3) since |(2,4,2)| = 8 = |(2,3,3)| and the right-most nonzero entry in (0,1,-1) is negative. Hence x2y4z2 >grevlex x2y3z3.
  4. Let f(x,y,z) = xy5z2 + x2y3z3 + x3.
    Then w.r.t. lex f is reordered in decreasing order as:
    f(x,y,z) = x3 + x2y3z3 + xy5z2;
    w.r.t. grlex as:
    f(x,y,z) = x2y3z3 + xy5z2 + x3;
    and w.r.t. grevlex as:
    f(x,y,z) = xy5z2 + x2y3z3 + x3.

The lex order is useful when we need to eliminate the variables in solving systems of equations, but when we only want to eliminate certain variables and we do not care about the others, we can use the more efficient k-th elimination order.
Definition 4. Fixed a monomial order > and given a nonzero polynomial f = Sa aaxa in K[x1,x2,...,xn], we define:
  • The multidegree of f as:
    multideg(f) = max>(a in Nn: aa<>0).
  • The leading coefficient of f as:
    LC(f) = amultideg(f).
  • The leading monomial of f as:
    LM(f) = xmultideg(f).
  • The leading term of f as:
    LT(f) = LC(f)LM(f).
Example.

Let f(x,y,z) = 2xy5z2 + 3x2y3z3 + 4x3. Then,

w.r.t. lex: w.r.t. grlex: w.r.t. grevlex:
multideg(f) = (3,0,0)
LC(f) = 4
LM(f) = x3
LT(f) = 4x3		 multideg(f) = (2,3,3)
LC(f) = 3
LM(f) = x2y3z3
LT(f) = 3x2y3z3		 multideg(f) = (1,5,2)
LC(f) = 2
LM(f) = xy5z2
LT(f) = 2xy5z2

It's easy to see that the multidegree has the following properties [3]:
Lemma 1. Let f and g be two nonzero polynomials in K[x1,x2,...,xn]. Then:
  1. multideg(fg) = multideg(f) + multideg(g).
  2. multideg(f+g) <= max(multideg(f), multideg(g)) and if multideg(f) <> multideg(g) the equality holds.

 

Last updated
Hosted by www.Geocities.ws

1