Graphics Reference
In-Depth Information
we may also assume that c = 0. Define an ordering < of
N
n-1
by:
(
)
<
(
)
ff
,
,...,
f
gg
,
,...,
g
if and only if
il
i
2
in
-
1
il
i
2
in
-
1
(
)
<
(
)
ff
,
,...,
f
,
0
gg
,
,...,
g
,
0
.
(10.63)
il
i
2
in
-
1
il
i
2
in
-
1
It is easy to check that this defines a monomial ordering on
N
n-1
. Our inductive
hypothesis applied to the sequence
e
i
¢=(e
i1
,e
i2
,...,e
in-1
) in now proves Claim 1.
If
x
= (x
1
,x
2
,..., x
n
),
y
= (y
1
,y
2
,..., y
n
) Œ
N
n-1
Claim 2.
satisfies x
j
< y
j
for all j,
then
x
<
y
.
Let d
j
= y
j
- x
j
and
d
= (d
1
,d
2
,...,d
n
). Then
0
<
d
implies that
x
=
0
+
x
<
d
+
x
=
y
and Claim 2 is proved.
Now consider the sequence in (10.62) again and assume that it is an infinite
sequence. If any of the sequences of nonnegative integers e
ij
, j = 1,2,..., is bounded
for some fixed i, then we can choose a subsequence of the
e
i
so that the jth entries in
that subsequence are constant. By Claim 1 we would be done. Assume therefore that
the sequences e
ij
, j = 1,2,..., are unbounded for all i. Choose a subsequence of the
e
i
so that for that subsequence the first components form a strictly increasing sequence
of integers going to infinity. Let
f
i
be this new decreasing sequence of elements of
N
n
.
Now look at the second components of all the
f
i
and choose a subsequence so that
the second components form a strictly increasing sequence of integers going to infin-
ity. Continue in this way until we finally end up with a subsequence
g
i
= (g
i1
,g
i2
,
...,g
in
) of the original sequence
e
i
with the property that g
i+1,j
> g
ij
for all i and j. By
Claim 2 we would have
g
i+1
>
g
i
, which is impossible since the sequence
e
i
was decreas-
ing. This contradiction proves the theorem.
Theorem 10.10.3 is important because we need monomial orderings to have the
well-ordering property in addition to the total order to ensure that various algorithms
we shall define will terminate.
10.10.4. Proposition.
The lex, deglex, and degrevlex orders of k[X
1
,X
2
,...,X
n
] are
monomial orderings.
Proof.
Obvious.
We need some more terminology before we can state the multivariable long divi-
sion theorem.
Definition.
Fix a monomial order < on k[X
1
,X
2
,...,X
n
] and let f Πk[X
1
,X
2
,...,X
n
].
The largest monomial in f with respect to this order is called the
leading term
of f and
is denoted by lt(f). Its coefficient is called the
leading coefficient
and is denoted by lc(f).
The
leading power product
, denoted by lpp(f), is defined by the equation lt(f) =
lc(f)lpp(f) and is the largest power product appearing in f.
For example, assuming deglex order and Y < X, if
(
)
=
2
fXY
,
7
XY XY Y
+
-
,
