Polynomial Reduction

Polynomial reduction is the successive cancellation of polynomial terms by multiples of specified polynomials, using a fixed monomial order. Let be a field and let consist of nonzero polynomials in . If a polynomial term of has monomial divisible by the leading monomial of , whose leading coefficient is , the reduction step replaces by

(1)

This cancels and introduces only smaller monomials.

Repeatedly canceling the largest reducible polynomial term terminates because the monomials form a well ordered set. It yields a representation

(2)

where no monomial of the remainder is divisible by a leading monomial of any . The remainder can depend on the choices of divisors. For example, with in and lexicographic order , the two reductions

			(3)
			(4)

give distinct remainders, each of which admits no further reduction by .

If is a Gröbner basis, the remainder is unique for the fixed monomial order and depends only on the ideal generated by . In that case, belongs to the ideal iff its remainder is zero. The coefficients need not be unique. For an arbitrary generating set, a zero remainder still implies membership, but a nonzero remainder does not rule it out. For the preceding , the polynomial belongs to its ideal and admits no reduction by .

Polynomial reduction is implemented in the Wolfram Language as PolynomialReduce[f, {g1, g2, ...}, {x1, x2, ...}]. It returns the list together with the remainder . For a single divisor in one variable, this specializes to polynomial division.