MATH 439/739/819 Assignment 4. Spring 2012. Due Tuesday March 13th 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. MATH 441 students may do additional problem 3 for a 3% bonus on the assignments. Enjoy, Michael Monagan 3.5 # 5, 10, 15 3.6 # 1, 3, 4*, 6*, 7, 8a 4.1 # 1, 2, 5*, 10 4.2 # 2, 5, 7, 12, 14 Notes: o For #5 of 3.5 compute the resultant using Maple's resultant command. o For #10 of 3.5, compute the resultant by hand and also using Maple's resultant command as a check. Note, for the second part of the question, assume a in a*x^2+b*x+c is not zero. o For #1 of 3.6, use Maple to compute the resultant. o For #6 of 3.6 note that the Maple command roots(f,x); computes the "rational roots" of a polynomial. Hence the Maple command select(type,roots(f,x),integer); gives us the integer roots. o For #7 on 3.6 just use Maple to eliminate t from u (1+t^2) - t^2 = 0, and v (1+t^2) - t^3 = 0 using (i) resultants and (ii) Groebner bases (the elimination theorem). o For #8a of 3.6, which values for c satisfy h(c) <> Res(f(x,c),g(x,c),x)? The question shows c=0 is one. Are there any others? See Proposition 3. o Study the proofs of the weak Nullstellensatz and Hilbert's Nullstellensatz o For problem #12 of section 4.2 use Maple's gcd command to compute the GCDs. o Do problem 14 of section 4.2 by hand -- first compute a Groebner basis for the ideal by hand. Additional exercises. 1: Show that x^2+y^2+1 is irreducible over C by constructing a system of polynomial equations and solving it using Groebner bases in Maple. 2: Consider the polynomials f := x^2+2*y^2-3; and g := x^2+x*y+y^2; from exercise #2 of section 3.1. Let I = (a) Compute R = Res(f,g,x) first using Maple, then by constructing Sylvester's matrix and calculating its determinant by hand. (b) Is = I intersect Q[y] ? (c) Using any method, find A, B in Q[x,y] s.t. A f + B g = R. Suggest use Maple's gcdex command to solve s f + t g = 1. 3* Part (a) (20 marks) On assignment 2 you implemented the division algorithm for the lex and grlex monomial orderings. For this assignment we will implement Buchberger's algorithm to compute a Groebner basis. You can use my division algorithm code in DivAlg.mws on the course webpage. Write a Maple procedure SPOLY(f,g,LT) that computes the S-polynomial of two polynomials f and g in Q[x1,...,xn] where LT is a Maple procedure which computes the leading term of a polynomial wrt a monomial ordering. You may use Maple's gcd and/or lcm commands to compute the GCD (LCM) of two monomials. Now write a Maple procedure Buchberger(F,LT) that takes as input a set (or list) of polynomials F = {f1,f2,...,fs} and LT. First compute the a Groebner basis for the ideal generated by F using Buchberger's algorithm with monomial ordering implied by LT. You may apply proposition 4 of section 2.9 to speed up Buchberger's algorithm if you wish. Part (b) (10 marks) Make your Buchberger procedure output a reduced Groebner basis. Test your algorithm on the following five problems. Problem 1 in Q[x,y,z] using lex AND grlex with x>y>z f1 := x*y-1; f2 := x*z-1; On this problem, only the first S-polynomial, y*f1-x*f2=y-z, does not reduce to 0 so this is a good first test problem. Problem 2 in Q[w,x,y,z] using lex AND grlex with w>x>y>z f1 := 3*x-6*y-2*z; f2 := 2*x-4*y+4*w; f3 := x-2*y-z-w; Note: you should get the same Groebner basis using lex and grlex because the polynomials are linear. Problem 3 in Q[x,y,z] using lex AND grlex with x>y>z. f1 := x^2+y+z-1; f2 := x+y^2+z-1; f3 := x+y+z^2-1; This is the first example in section 3.1. Problem 4 in Q[u0,u1,u2,u3] using lex AND grlex with x>y>z f1 := x-z^4; f2 := y-z^5; This is exercise 2(c) of section 2.7. Problem 5 in Q[t,x,y,z] using lex AND grlex with t>x>y>z. f1 := t^2+x^2+y^2+z^2; f2 := t^2+2*x^2-x*y-z^2; f3 := t+y^3-z^3; This is exercise 7 of section 3.1. For each problem where G = {g1,g2,...,gt} is the Groebner basis that you obtain, print G and print also the set of leading terms of G, i.e., {LT(g1),LT(g2),...,LT(gt)} so that you and I can check that your Groebner bases are right. To do this use the command printf( "LT(G) = %a\n", map(LT,G) );