Biology Reference
In-Depth Information
x
2
and
g
x
2
xy
2
. The remainder
Example 3.3.
Consider the polynomials
f
=
=
+
xy
2
or
x
2
, depending on whether we choose the initial monomial
of
g
to be
x
2
or
xy
2
, respectively.
As we will see below, multivariate polynomial division becomes well defined when
using Gröbner bases.
Let
k
be a field. Here, we focus on the finite fields
−
of dividing
f
by
g
is
Z
p
where
p
is prime; however,
much of the presented results are valid for other fields, such as
Q
. The linear com-
x
α
n
n
over
k
, where
x
α
1
1
bination of monomials of the form
x
α
=
···
α
is the
n
-tuple
n
exponent
α
=
(α
1
,...,α
n
)
∈ Z
0
with nonnegative entries, forms a ring, called
a
polynomial ring
, denoted
k
. For the purpose of polynomial division,
it is necessary to be able to arrange the terms of a polynomial unambiguously in
some order. This requires a
total
ordering on the monomials, i.e., for every pair of
monomials
x
α
and
x
β
, exactly one of the following must be true:
[
x
1
,...,
x
n
]
x
α
≺
x
β
,
x
α
=
x
β
,
x
α
x
β
.
Taking into account the properties of the polynomial sum and product operations,
the following definition emerges.
Definition 3.4.
A
monomial ordering
on
k
n
[
x
1
,...,
x
n
]
is any relation
on
Z
0
satisfying:
n
1.
is a total ordering on
Z
0
.
n
2.
If
α
β
and
γ
∈ Z
0
, then
α
+
γ
β
+
γ
.
n
n
3.
is a well ordering on
Z
0
, i.e., every nonempty subset of
Z
0
has a smallest
element under
.
To simplify the classification of monomial orderings, we will assume throughout
that
x
1
z
).
One of the most popular monomial orderings is the
lexicographic ordering
(
lex
)
which is analogous to the ordering of words in dictionaries and under which
x
2
x
2
···
x
n
(or
x
y
lex
xy
2
. Another one is the
graded lexicographic ordering
(
grlex
) which orders by total
degree first, then “breaks ties” using the lexicographic ordering. Under graded lexi-
cographic ordering,
xy
2
grlex
x
2
. Yet another very useful monomial ordering is the
graded reverse lexicographic ordering
(
grevlex
). Like
grlex
,itusesthetotaldegree
first but to break ties it looks at the rightmost variable and favors the smaller power. For
example,
y
2
z
≺
grlex
xz
2
but
y
2
z
gre
v
lex
xz
2
. Algorithmic definitions are available
at [
19
].
A monomial ordering can also be defined by a weight vector
ω
=
(ω
1
,...,ω
n
)
in
n
Z
have nonnegative coordinates in order for 1 to always be the
smallest monomial. Fix a monomial ordering
0
. We require that
ω
n
σ
, such as
lex
. Then, for
α, β
∈ Z
0
,
define
α
ω,σ
β
if and only if
ω
·
α
ω
·
β
or
(ω
·
α
=
ω
·
β
and
α
σ
β).
Search WWH ::
Custom Search