MATH 441/741/819 Assignment 2.  
Spring 2014.

Due Thursday February 6th at 2:30pm.
Late policy: -20% for up to 24 hours late.  Zero for more than 24 hours late.
Problems marked * are for MATH 819 students only.
Michael Monagan

Problems from the book.
Section 2.2  #1,2,4,10
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]
   and notice where they differ.  What do you observe for k[x,y]?

   An easy way to do this is to use the sort command in Maple.
   Let f := 1+x+y+z+...+x^3+y^3+z^3 be the polynomial with all the terms.
   To sort the terms in grlex order with x>y>z use
       sort( f, order=grlex(x,y,z) );
   To sort in the grevlex order with x>y>z, use
       sort( f, order=tdeg(x,y,z) );

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.