Biology Reference
In-Depth Information
For example, with
x
y
, weight vector
ω
=
(
3
,
1
)
orders the monomials of poly-
x
2
xy
2
in the same way as the lexicographic order, while
ω
=
(
nomial
g
=
+
1
,
1
)
performs the same monomial ordering as the graded lexicographic ordering.
However, even after fixing the monomial ordering, there is still a problem with
multivariate polynomial division: when dividing a given polynomial by more than one
polynomial, the outcome may depend on the order in which the division is carried
out. Let
. The famous
ideal membership problem
is
to determine whether there are polynomials
h
1
,...,
f
,
h
1
,...,
h
m
∈
k
[
x
1
,...,
x
n
]
h
m
∈
k
[
x
1
,...,
x
n
]
such that
=
i
=
1
h
i
f
i
.The following definition will help us state this in the language of
abstract algebra and explains the name of the problem.
Definition 3.5.
Let
k
be a field. Then
f
h
i
f
i
|
I
=
f
1
,...,
f
m
=
h
1
,...,
h
m
∈
k
[
x
1
,...,
x
n
]
,
is called an
ideal
in
k
.
We know from abstract algebra that
I
is closed under addition and multiplication
by any polynomial in
k
[
x
1
,...,
x
n
]
. This is analogous to a subspace of a vector space,
where the “vectors” are polynomials.
We ask whether
f
is an element of
I
. In general, even under a fixed monomial
ordering, the order in which
f
is divided by the generating polynomials
f
i
affects the
remainder; perhaps even more surprisingly, a nonzero remainder of division does not
imply
f
[
x
1
,...,
x
n
]
∈
I
. Moreover, the generating set
{
f
1
,...,
f
m
}
of the ideal
I
is not unique
G
=
{
g
t
}
but a special generating set
can be selected so that the remainder
of polynomial division of
f
by the polynomials in
g
1
,...,
performed in any order is zero if
and only if
f
lies in
I
. A generating set with this property is called a
Gröbner basis
.A
Gröbner basis exists for very ideal other than
G
{
}
and for a fixed monomial ordering.
Before we give a precise definition, we need to look at a special kind of ideal.
Definition 3.6.
The
initial ideal
of an ideal
I
0
={
0
}
for a fixed monomial ordering
and is the ideal generated by the set of leading monomials (under
the specified ordering) of the polynomials of
I
. That is,
in
is denoted
in
(
I
)
(
I
)
=
in
(
f
)
|
f
∈
I
,
where
in
is the monomial of
f
that is ordered first under the specified monomial
ordering, called a
leading
or
initial
monomial. The monomials which do not lie in
in
(
f
)
are called
standard monomials
.
Definition 3.7.
(
I
)
Fix a monomial ordering
. A finite subset
of an ideal
I
is a
G
Gröbner basis
if
in
.
A Gröbner basis for an ideal is necessarily a generating set for the ideal but may
not be unique even under a fixed monomial ordering. However, if we also require that
for any two distinct elements
g
(
I
)
=
in
(
g
)
|
g
∈
G
g
∈
G
,notermof
g
is divisible by
in
,
(
g
)
, such a
Gröbner basis
is called
reduced
and is unique for an ideal and a monomial ordering
G
, provided the coefficient of
in
(
g
)
in
g
is 1 for each
g
∈
G
.
x
3
x
2
y
2
y
2
Example 3.4.
Let
x
y
and
f
1
=
−
2
xy
,
f
2
=
−
+
x
, and
I
=
f
1
,
f
2
in
k
[
x
,
y
]
under
grlex
order. Notice that
{
f
1
,
f
2
}
is not a Gröbner basis
Search WWH ::
Custom Search