Graphics Reference
In-Depth Information
know something about the degrees of f and the g
i
. For example, if the g
i
all have degree
2 and f has degree 4, we cannot assume that the a
i
will have degree at most 2. Nev-
ertheless, the approach will be to try to reduce f to 0 by successively subtracting appro-
priate multiples of g
1
from f, then multiples of g
2
, etc. We will need some criteria that
will tell us that as we change f we are making progress. To do this we define a notion
for when a term of a polynomial is more complicated than another one. We need an
ordering of monomials. One such well-known ordering is the following:
Definition.
The
lexicographic order
or
lex order
< of the monomials in indeterminates
X
1
, X
2
,..., X
n
over a ring R is defined as follows: Given monomials
ee
e
f
f
f
,
u
=
cX
X
...
X
and
v
=
dX X
...
X
1
2
1
2
n
n
12
12
then u < v if the
left
-most nonzero entry in the vector
d
= (f
1
,f
2
,...,f
n
) - (e
1
,e
2
,...,e
n
)
in
Z
n
is positive. The
reverse lexicographic order
defines u < v if the
right
-most nonzero
entry in the vector
d
is negative.
For example, if X = X
1
and Y = X
2
, then
2
Y
k
2
2
2
1
<< < < <
<<
YY
...
...
XXYXY
<
< < <
...
X XY
<
...
with respect to the lexicographic order. Note that the lexicographic order is deter-
mined by the order in which the indeterminates X
i
are listed. In essence, one has
chosen a fixed ordering of the variables, namely, X
n
< X
n-1
< ...< X
1
.
The lexicographic order is only one of many orderings. Other orderings actually
work better with certain problems. Here are two other standard ones; however, the
reader should be aware of the fact that the terminology varies between authors.
Definition.
The
degree lexicographic order
or
deglex order
< of the monomials in inde-
terminates X
1
, X
2
,..., X
n
over a ring R is defined by saying that any monomial of
total degree d is less than any monomial of degree e if d < e and monomials of equal
total degree are ordered using the lexicographic order.
For example, if X = X
1
and Y = X
2
, then
2
2
1
<<< <
YXY
XY
<<
X
. . . .
Definition.
The
degree reverse lexicographic order
or
degrevlex order
< of the mono-
mials in indeterminates X
1
, X
2
,..., X
n
over a ring R is defined by saying that any
monomial of total degree d is less than any monomial of degree e if d < e and mono-
mials of equal total degree are ordered using the reverse lexicographic order.
In the case of two variables, the degrevlex and deglex order are the same
(Exercise 10.10.2). On the other hand, when X
3
< X
2
< X
1,
then
3
2
XX
<
XXX
1
23
2
1
for deglex order, but
