Mathematics 392 – Seminar in Computational Commutative Algebra Lab Day 2/Problem Set 5 – Gröbner Bases in Maple September 29, 2006

Background

We have now seen the definition of a Gröbner basis for an ideal, with respect to a monomial order >. Recall G = {g_{1}, …, g_{t}} is a Gröbner basis for I if

• All g_{i} ∈ I, and

• ⟨LT_{>}(g_{1}), …, LT_{>}(g_{t})⟩ = ⟨LT_{>}(I)⟩. (Equivalently, for every f ∈ I, LT_{>}(f) is divisible by LT_{>}(g_{i}) for some i.)

We will discuss an algorithm, called Buchberger’s algorithm for computing a Gröbner basis from any generating set of I next week. For now, let’s just learn how to use Maple’s implementation of that algorithm, treating it as a sort of “black box”.

Maple’s Groebner package

All the procedures dealing with monomial orders, the division algorithm, Gröbner bases, etc. are contained in a package that you’ll need to load first, with the command

                              with(Groebner);

(N.B. no umlauts in Maple, so the alternate English spelling is the name of the command!)

NormalForm – Remainder on Division

The command that performs the division algorithm is called NormalForm. It returns only the remainder on division, which can be thought of as a sort of normal, or reduced form for the input polynomial f with respect to the divisor polynomials f_{1}, …, f_{s}. The format for the command is

                       NormalForm(f,PList,monorder);

where f is the polynomial you are dividing, PList is the list of divisors, and monorder specifies the monomial order. Almost any monomial order can be defined in Maple. To get the two we will use today, use

• plex(x,y) for the lexicographic order with x > y, plex(y,x) for lexicographic order with y > x, and similarly if there are more than 2 variables.

• tdeg(x,y) is the graded reverse lex order with x > y, tdeg(y,z,x) would give graded reverse lex with y > z > x, and so forth.

For example, enter

                      PList:=[x^2*y+x^2+1,x^3+x*y+2];
             f:=expand((x^4*y+x^2*y^3)*PList[1]+y^2*PList[2]);

                  NormalForm(f,PList,plex(x,y));

to divide

f = (x^{4}y + x^{2}y^{3})(x^{2}y + x^{2} + 1) + (y^{2})(x^{3} + xy + 2)

by

[f_{1}, f_{2}] = [x^{2}y + x^{2} + 1, x^{3} + xy + 2],

using the lex order with x > y. Question: What does the result say about {f_{1}, f_{2}} as a set of generators for the ideal I = ⟨f_{1}, f_{2}⟩.

Basis – Gröbner Basis Computation

The command for computing a Gröbner basis of an ideal generated by a given list of polynomials is called Basis. The format is

                      Basis(Plist,monorder);

where Plist is the list of generators for your ideal, and monorder is the monomial order to be used. Enter

                   Blex:=Basis(Plist,plex(x,y));

to compute the lex Gröbner basis for I = ⟨f_{1}, f_{2}⟩ as above (lex order with x > y).

Questions

1. What is the monomial ideal ⟨LT_{>_{lex}}(I)⟩ here? (Think of the definition of a Gröbner basis from last time.) How does this relate to the ideal ⟨LT_{>_{lex}}(f_{1}), LT_{>_{lex}}(f_{2})⟩?

2. Find the remainder on division of the polynomial f from before with respect to Blex. Is this what you expect? Why?

3. Look carefully at the terms in the two polynomials in Blex. What do you notice? If you were trying to determine the points in the variety V = V(f_{1}, f_{2}), how would this Gröbner basis help? What would you do to find V?

4. To carry out the process you described in 2 in Maple, you can solve a one-variable polynomial by an approximate numerical method and find all its complex roots with a command like this:

                    fsolve(Blex[1],y,complex);

Then substitute each y-value into the other equation to find x. Do this, then find all the points in V = V (f_{1}, f_{2}). Maple notes: When you call the lex Gröbner basis Blex, then Blex[1] is the first polynomial in the basis, and Blex[2] is the second. Look up the subs command in the on-line help to see how to substitute a value into an expression like a polynomial, if you haven’t seen that before.

5. What happens if you compute a Gröbner basis for I, but with respect to a lex order with y > x? Describe the form of the polynomials you get.

6. Now compute the Gröbner basis for the same I, but with respect to the grevlex order with x > y. (Your results should be different!) Does this Gröbner basis have the same properties as the lex ones?

7. What is the monomial ideal ⟨LT_{>_{grevlex}}(I)⟩? (Try to determine the leading terms in the Gröbner basis elements “by hand” first; you can then check your work using the LeadingTerm command from the Groebner package. Note: If you call the grevlex Gröbner basis Bgrev, then Bgrev[1] is the first polynomial in the basis, Bgrev[2] is the second, and so forth.

Additional Problems

Do the following problems from section 2.8, using Maple to carry out the necessary calculations. Your worksheet(s) for these computations, together with explanations, hand calculations to set up the polynomials, etc. will be your problem set for the week.

• 2,

• 3 (“the method of Examples 2 and 3” is essentially what we did in parts 3 and 4 above; it would be good to look over the calculations in the text too!),

• 8,

• 9 (it would be nice to include graphics illustrating the varieties from 8 and 9 – see the help for plot3d to see how to plot parametric curves and surfaces in R^{3}),

• 10