Graphics Reference
In-Depth Information
The term “P-normal form” for a polynomial is
not quite
just another name for a
remainder in Algorithm 10.10.2. The reason is that an elementary reduction of f does not
require that the term u in f is a leading term. In practical algorithms, however, u always
will
be chosen to be a leading term because of Algorithm 10.10.2.
10.10.6. Example.
Choose the lexicographic order for k[X,Y] with X > Y and let
{
}
2
22
2
P
=
p
=
3
XY X p
+
,
=
XY
-
X p
,
=
Y p
,
=
4
X
+
X
1
2
3
4
and
3
2
2
2
.
f
=
12
XYXY
-
+
9
Y
The first term of each of the polynomials p
i
is the leading term. Define polynomials
g
i
and h
i
by
22
2
2
3
22
2
g
=-
f
4
Xp
=-
X Y
-
4
X
+
9
XY
,
h
=-
f
12
Xp
=-
XY
+
9
XY
1
1
1
3
2
2
2
g
=+ =-
g
p
49
X
+
XY
-
X
,
hhp
=+=
9
YX
-
,
2
1
2
2
1
2
2
hh
=-
9
Yp X
=-
,
g
=-
g
9
XY p
=- -
4
X
X
,
3
2
3
3
2
3
ggp
=+ =
0
.
4
3
4
This shows that
f
fifififi
g
g
g
g
and
f
fififi
h
h
h
3
.
1
2
3
4
1
2
Thus, f P-reduces to g
4
and h
3
. Since both g
4
and h
3
are P-irreducible, they are both
P-normal forms for f.
Note that Example 10.10.6 shows that P-normal forms (or remainders in
Algorithm 10.10.2) are
not
unique in general. Now, an elementary P-reduction intro-
duces potentially new terms to the original polynomial. It might seem initially that
we could have an infinite chain of elementary P-reductions. This is not possible
however. See [AdaL94]. (The termination part of the proof for Algorithm 10.10.2 does
not apply directly because elementary P-reductions of f do not necessarily pick a
leading term of f. One needs a simple modification of that proof.)
10.10.7. Proposition.
Let P be a finite set of polynomials and f an arbitrary poly-
nomial. If the P-normal form g for f is unique, then g = 0 if and only if f belongs to
the ideal <P>.
ææ
Proof.
Let P = {p
1
,p
2
,...,p
m
}. Now, if
f
g
, then
fap ap
=
+
2 2
...
+
+
ap g
+
11
mm
for some polynomials a
i
. Therefore, if g = 0 then f Œ<P>. Conversely, let f Œ<P>. It is
not true in general that every P-normal form of f is 0. See Exercise 10.10.6. On the
other hand, at least one will be because if
