MATH 441/741/819 Assignment 2.  Spring 2012.
Due Tuesday February 7th at 2:30pm.
Late policy: -20% for up to 48 hours late.  Zero for more than 24 hours late.
Problems marked * are for MATH 819 students only.
MATH 441 students may do additional problem 3 for a 3% bonus on the assignments.
Michael Monagan

Problems from the book.
Section 2.2  #1,2,4
Section 2.3  #1,3,5
Section 2.4  #3,8,10
Section 2.5  #1,6,7,10,12,13*,14
Section 2.6  #2,3,9,12*

Notes on exercises.

For question 2.3 #1, use f = x^4 y^2 + x^3 y^2 - y + 1 instead.
For question 2.6 #9 use the lex monomial ordering in part (b) not invlex.
For question 2.3 #3, the command in Maple is

    > Groebner[NormalForm]( f, [f1,f2], MO );

  It computes the remainder of f divided by (f1,f2) wrt the monomial
  ordering MO.  The help page  ?MonomialOrders  describes the available
  monomial orderings.  The lex monomial ordering in k[x,y] with x>y is
  plex(x,y), the grlex ordering is grlex(x,y) and grevlex is tdeg(x,y).


Additional problems.

1: The monomial ordering grlex with x>y can be described by simply writing
   down the ordering thus
      1 < y < x < y^2 < x y < x^2 < y^3 < x y^2 < x^2 y < x^3 < ...
   To better understand the difference between the grlex and grevlex orderings
   write down the ordering explicitly up to and including all monomials of
   total degree 3 for both grlex and grevlex and for both k[x,y] and k[x,y,z].
   An easy way to do this is to use the sort command in Maple.
   The syntax is sort( L, F ) where L is a list of monomials being sorted and
   F is a boolean valued function where F(s,t) must output true if s<t and
   false otherwise.  So all you need to do is write a procedure F which 
   compares two monomials in a given ordering, then do
      > sort( [1,x,y,x^2,x*y,y^2,x^3,x^2*y,x*y^2,y^3], F );

2: Suppose we are dividing f by (f[1],...,f[s]) under some monomial ordering.
   The division algorithm I presented in class was 

    (a[1],...,a[s]) := (0,...,0)
    (p,r) := (f,0)
    while p <> 0 do
        Let i be the first index s.t. LT(f[i]) | LT(p).
        If no such i exists then set (p,r) := (p-LT(p),r+LT(p))
        else set t := LT(p)/LT(f[i]); (p,a[i]) := (p-t*f[i],a[i]+t).
    return (a[1],...,a[s],r)

   Prove that that the values of the variables satisfy the loop invariant 
        f = a[1] f[1] + ... + a[s] f[s] + p + r
   each time the while condition p <> 0 is executed.  Thus conclude that
   if the loop terminates, p = 0 and hence the output satisfies
        f = a[1] f[1] + .... + a[s] f[s] + 0 + r.

3*: PROGRAM THE DIVISION ALGORITHM in Maple and test your program on the
  same examples in exercises #1, 2 from section 2.3.  See my programming
  notes for how to program the LT command for the lex and grlex orderings.