Graphics Reference
In-Depth Information
ing polynomials to get to a reduced one. For example, there are two choices when
reducing the polynomial
22
gXY X
=
-
with respect to the set of polynomials P in Example 10.10.11, that is, g has the two
P-normal forms
g
=-
g
yp
=-
XY
-
X
and
g
=-
g
xp
=- .
2
X
1
1
2
2
That one gets different sequences of polynomials on the way to a reduced form might
not be bad by itself, but what turns out to be bad is that differences such as
g
2
-= -
g
XY
X
(10.64)
are irreducible. Trying to fix this problem is what leads to an algorithm for finding
Gröbner bases.
Definition.
Let f and g be nonzero polynomials in k[X
1
,X
2
,...,X
n
]. Let L =
lcm(lpp(f),lpp(g)). The
S-polynomial
of f and g, denoted by S(f,g), is defined by
L
lt f
L
lt g
()
=
Sf g
,
f
-
g
.
()
()
For example, if p
1
and p
2
are the polynomials in Example 10.10.11, then
(
)
=- =-
Sp p
,
Yp
Xp
XY
X
.
12
1
2
This is in fact the same polynomial as the one in equation (10.64) that measured
differences in outcomes of reductions.
10.10.12. Theorem.
(Buchberger) Let P be a finite set of polynomials in k[X
1
,X
2
,
...,X
n
]. Then the following are equivalent:
(1) P is a Gröbner basis for <P>.
(2) For all f and g in P we have NF(S(f,g),P) = 0.
Proof.
See [CoLO97] or [AdaL94].
10.10.13. Theorem.
(Buchberger Gröbner Basis Algorithm) Fix a monomial order
and let I be a nonzero ideal in k[X
1
,X
2
,...,X
n
]. If P = {p
1
,p
2
,...,p
m
} is any basis for I,
that is, I =<p
1
,p
2
,...,p
m
>, then Algorithm 10.10.3 computes a Gröbner basis G for I.
Proof.
See [CoLO97] or [AdaL94]. Algorithm 10.10.3 does not produce a unique
Gröbner basis because different choices could be made as it proceeds.
10.10.14. Example.
To use Algorithm 10.10.3 to find a Gröbner basis for the ideal
I =<p
1
= X
2
Y + X,p
2
= XY
2
+ 1> using the deglex order on k[X,Y] with X > Y.
