- (1) lies in the ideal generated by
*F*(so that*p*and determine the same cosets of ) - (2) the leading monomial of is less than the
leading monomial of
*p*.

We now give details involving reducing a polynomial by a set of polynomials.

Given a monomial order, let be a
set of polynomials.
Now let *f* be
any
polynomial. We say that *f* is reducible to *g* with respect to *F* if
there exists such that
where *c* is a constant and *u*, *v*
are monomials chosen so that the
leading term of coincides with one
of the terms of *f*. The effect
is to
replace a term of *f* with terms of lower order.
The polynomial *p* is *irreducible* with respect to *F* if
the leading term of does not divide the leading
term of *f* for any .

A reduction step can be conceived of as a replacement
LHS RHS of
a term in *f*, which contains LHS as a factor,
by a term or sum of terms of lower
order. If, for example,
is a replacement
rule
and a term of *f* contains
*x* , then
can be replaced by 1.
The description of the reduction procedure in terms of
replacement rules
corresponds to the way it is commonly implemented. The ``handedness''
of replacement rules is determined by the term ordering.
The LHS is always
taken to
be the leading term of the polynomial, while RHS is the negative of
the
sum of the remaining terms (which are lower in the monomial order).

When one applies a list of rules *F* repeatedly
until no further reduction can occur
to any polynomial *p* one obtains a *normal form* of *p*
with respect to *F*. A normal form of *p*
with respect to *F* is irreducible
with respect to *F*.

Wed Jul 3 10:27:42 PDT 1996