MATH 495/800 Assignment 2.  Summer 2006.
Due Wednesday June 7th at 9:30am.  Late policy: -10% for each day late.
Problems marked * are for MATH 800 students only.
Enjoy, 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,14,13*
Section 2.6  #2,3,9,12*


For question 2.3 #1 execute the division algorithm by hand.
For question 2.3 #3, the command in Maple 10 is

    > Groebner[NormalForm]( f, [f1,f2], MO );
  and in older versions of Maple it is
    > Groebner[normalf]( f, [f1,f2], MO );

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

  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.

For question 2.6 #9 use the lex monomial ordering in part (b) not invlex.

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 items 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 give it, for example
      > 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
        i := 1; while i<=s and LT(f[i]) does not divide LT(p) do i := i+1
        if i>s then (p,r) := (p-LT(p),r+LT(p))
        else t := LT(p)/LT(f[i]); (p,a[i]) := (p-t*f[i],a[i]+t)
    return (a[1],...,a[s],r)

   Prove that if the algorithm terminates then
        f = a[1] f[1] + ... + a[s] f[s] + r
   for some r satisfying no term of r is divisible by any LT(f[i]), 1<=i<=s.
   To prove this use
        f - a[1] f[1] - ... - a[s] f[s] - (p + r) = 0
   for the loop invariant.  The purpose of this exercise is to get to you
   practice writing down a proof using a loop invariant.