next up previous contents
Next: S-polynomials and Buchberger's Up: Recipe 5---Linear Algebra Previous: Some more definitions

Multivariate division by an ideal

We now discuss multivariate division and remainders. For a more complete discussion see Cox, Little, and O'Shea. We consider only the case when we are dividing by an ideal for which we have a Gröbner basis (otherwise the remainder is not unique).

Theorem 3: Division Algorithm in . (Cox, Little, O'Shea p. 63). Fix a monomial order > on , and let be an ordered s-tuple of polynomials in K. Then every f in K can be written as

where , and either r = 0 or r is a k-linear combination of monomials, none of which is divisible by any of LT, , LT. We will call r a remainder of f on division by F. Furthermore, if , then we have

For the algorithm which constructs the and r, and proof of its correctness, see Cox, Little, and O'Shea. Note that unless F is a Gröbner basis, the remainder r and quotients will not be unique. If, on the other hand, F is a Gröbner basis, then the remainder (but not the quotients) will be unique, and not depend on the order of polynomials in the basis. (This is proposition 1 in Cox, Little, O'Shea, p. 81.)

Remark. The fact that if r is not zero then it is a k-linear combination of `small' monomials is crucial to the linear algebraic aspect of Gröbner bases. We give an example here.

Example Suppose and . This is not a Gröbner basis, but we can find using Maple that is a (grevlex or `tdeg') Gröbner basis for F, where , , and . Using Maple again, with the normalf routine, we find that the remainder of dividing (say) by this ideal is

normalf(2*x1**4*x2 - x2**2 + x1**3 + x1 + 1, GB, [x1,x2], tdeg);
which gives . One important point is that none of the terms in this remainder are divisible by the leading terms of the Gröbner basis (namely , , or ). Another is that the algorithm produces a unique remainder, no matter what ordering is chosen for the basis.

Finally, notice that using this remainder we can define an equivalence class in K, namely if the remainder on dividing f by G is the same as the remainder on dividing g by G. This gives us the quotient ring (see Cox, Little, and O'Shea for the details verifying that this all makes sense). We observe, then, that the set of monomials which are not divisible by the leading terms of the Gröbner basis form a basis for this quotient ring. This is what we explore, in section (6.4). But first, we take advantage of all this notation to give a real definition of a Gröbner basis, and describe Buchberger's algorithm for computing one.



next up previous contents
Next: S-polynomials and Buchberger's Up: Recipe 5---Linear Algebra Previous: Some more definitions



Robert Corless
Tue Mar 12 21:09:19 EST 1996