kth Elimination Order of Bayer and Stillman

 

Definition 1. Fix an integer 1<= k<= n. We say that a monomial order > on K[x1, x2,..., xn] is of k-elimination type provided that any monomial involving one of x1, x2,..., xk is greater than all monomials in K[xk+1, xk+2,..., xn].
Orders of k-elimination type are used to eliminate the first k variables of a system of equations on K[x1, x2,..., xn]. As an example of monomial order of k-elimination type (other than lex order), we will consider the following one:
Definition 2. Fix an integer 1<= k<= n and let a and b be in Nn. Then we define the order >k as follows: a >k b if

Ski=1 ai > Ski=1 bi, or Ski=1 ai = Ski=1 bi and a >grevlex b.
This is the kth elimination order of Bayer and Stillman and it is now supported by the Groebner applet.
It is preferred to lex order when eliminating only certain variables from a system of equations since it leads to simpler bases.

Examples.

  1. (2,0,1) >1 (1,2,0) since the first entry in (2,0,1) is greater than the first entry in (1,2,0). Hence x2z >1 xy2.
    (1,2,0) >2 (2,0,1) since the sum of the first two entries in (1,2,0) is greater than the sum of the first two entries in (2,0,1). Hence xy2 >2 x2z.
    (1,2,0) >3 (2,0,1) since the sum of the first three entries in (1,2,0) equals the sum of the first three entries in (2,0,1) and (1,2,0) >grevlex (2,0,1). Hence xy2 >3 x2z.
  2. Consider the equations

f1 = t2 + x2 + y2 + z2 = 0
f2 = t2 + 2x2 - xy - z2 = 0
f3 = t + y3 - z3 = 0.

We want to eliminate t from these equations.

  • The reduced Groebner basis for I = <f1, f2, f3> w.r.t. lex order with t>x>y>z is given by

    g1 = y12 - 4z3y9 + 5y8 + 6z6y6 + 6z2y6 - 10z3y5
    + 5y    4 - 4z9y3 - 12z5y3 + 5z6y2 + 13z2y2 + z12 + 6z8 + 9z4
    g2 = xz6 + 3xz2 - y11 + 4y8z3 - 5y7 - 5y5z6 - 3y5z2
    + 10y    4z3 - 5y3 + 2z9y2 + 6y2z5 - 3yz6 - 7yz2
    g3 = xy + y6 - 2y3z3 + 2y2 + z6 + 3z2
    g    4 = x2 + y6 - 2y3z3 + y2 + z6 + z2
    g    5 = t + y3 - z3.

    Hence a (Groebner) basis for the 1st elimination ideal I I K[x, y, z] is <g1, g2, g3, g4>: we have four generators, one with total degree 12.

  • The reduced Groebner basis for I w.r.t. the 1st elimination order with t>x>y>z is

    h1 = x2 - xy - y2 - 2z2
    h2 = y6 - 2y3z3 + z6 + xy + 2y2 + 3z2
    h    3 = t + y3 - z3.

    We have got a much simpler basis for I I K[x, y, z]: <h1, h2>. This is the reduced Groebner basis of the 1st elimination ideal I I K[x, y, z] w.r.t. grevlex order.

 

Last updated
Hosted by www.Geocities.ws

1