Next: The Basis Algorithm Up: Background on Ideals Previous: Background on Ideals

## The Reduction Process

A key operation in the theory of Gröbner Basis is the idea of reducing a polynomial p by a set of polynomials F. Once a term order is defined, reducing a polynomial p by a set of polynomials F involves constructing a polynomial such that
(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.

Next: The Basis Algorithm Up: Background on Ideals Previous: Background on Ideals

Helton
Wed Jul 3 10:27:42 PDT 1996