MATHEMATICAL SCIENCES VIGRE SEMINAR
MATHEMATICAL SCIENCES VIGRE SEMINAR MATH 499
Popular in Course
Popular in Mathematics (M)
This 20 page Class Notes was uploaded by Jayde Lang on Monday October 19, 2015. The Class Notes belongs to MATH 499 at Rice University taught by Brendan Hassett in Fall. Since its upload, it has received 8 views. For similar materials see /class/224940/math-499-rice-university in Mathematics (M) at Rice University.
Reviews for MATHEMATICAL SCIENCES VIGRE SEMINAR
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/19/15
Math 499699 VIGRE Senior Seminar Let f1 fn1 be n 1 polynomials in n variables The resultant is a polynomial in the coefficients of the which vanishes whenever the have a common zero The problem of nding explicit formulas for resultants is classicall Sylvester and B zout developed determinantal formulas ilel formulas that express the resultant as the determinant of some matrix for n 1 2 3 when the n 1 polynomials all have the same degree For example let n 1 and consider 101 0012 alz a2 0 and 41 12013 12112 1221 123 0 1n matrix form we have 13 0 0 a0 a1 a2 12 7 0 ltb0 b1 b2 b3 1 7 0 1 0 Since square matrices have some very nice properties we translate this into an equivalent system involving a square matrix With respect to common zeroes it will not matter if equations like 0 and 11111 0 are added to the systeml So in this particular case we can add zp z 0 12101 0 and 141 0 which gives the following matrix equation 0 0 a0 a1 a I4 0 0 a0 a1 a2 0 13 0 a0 a1 a2 0 0 12 0 0 b0 b1 b2 123 z 0 b0 b1 b2 b3 0 1 0 Such a square matrix equation has nontrivial solutions only when the determinant of the matrix is zero This system has a solution if 101 and 971 have a common solution Consequently the determinant will vanish whenever 101 and 41 have a common solution When the n 1 polynomials do not have the same degree the situation was less understood classicallyl Note that the procedure given above for n 1 doesn7t care about the degrees of the two polynomials however the results of Sylvester and B zout do not extend to n 2 3 Just recently Amit Khetan has given formulas for the n 2 3 cases For n 2 Khetanls theorem is that the resultant of a system f1f2f3 E CIl12131111 with common Newton polygon Q is the determinant of the block matrix B L L 0 where L and L are linear terms and the entries of B are cubic forms in the coef cients of the polynomials In this seminar we will develop the mathematics behind Khetanls result In particular we will cover spectral sequences the Koszul complex the Tate resolution Beilinson resolution and spectral sequence etcl Lecture Notes Math 499699 October 207 2004 Continuing our journey through the eld of Invariant Theory7 today our goal is to nd an algorithm for determining the ring of invariants hx17 7xn of a nite matrix group G C GLn7 h Where h is eld of characteristic 0 De nition Given f17 7 fm E hx17 7xnl7 we let H1617 7 denote the subset of hx17 7 xn consisting of all polynomial expressions in f17 7 fm with coe cients in h hf17 E hx177xn l f gf17 7 fm7gis a polynomial with coe cients in 16 Note that hf17 7 is closed under multiplication7 addition7 and contains h Hence7 it is a subring of hx17 H We say that this subring is generated by f17 7 WARNING Both H1017 7 and ltf1 7 are generated by f17 7 fm7 but in each case we mean something slightly different Let7s recall the de nition of ltf17 7 De nition Let f17 7 f5 be polynomials in hx17 7xn Then we can set ltf1mfgt th h1mhe Hickman i1 De nition Given a nite matrix group G C GLn7 k the Reynolds opera tor of G is the map Ra hx17 7 x77 A hx17 7xn de ned by the formula 1 RafX i Z fA39X lGl AeG for E hx17 7xn This can be thought of as averaging the e ect ofG on f Proposition Let Ra be the Reynolds operator of the nite matrix group G 1 RG is hlinear in 2 ff 6 hx177xn7 then Rgf E hx17 7xnlc 5 ff 6 hx177xnG7 then RgF Example 1 Consider the cyclic matrix group we discussed last time C4 6 GL27 h generated by 0 71 A lt 1 o l and containing the elements A4lt1 112 Because the action of A is de ned 1 gt gt 7y7y gt gt r we can easily see that Haylc E kzy l Then we nd that the Reynolds d operator is de ne R04f17yif7yyr fez 7y y ix m y We can use the above proposition to compute some invariants as follows R04I2 iy2 JFI2 y2 12 ltx2 y2 BMW iPIy Iy 7 W aty 0 304 No ikryg 13y 7 mos 0639 wy 7 Iys R0412y2 ilt12y2 JrI2y2 JrI2y2 Jr12f 12y Thus 12 y27 13y 7 zyg ff 6 Hz ylc li We Will see that these three polyno mials actually generate the ring of invariants Notice that for any monomial 1 RG 10 is a homogeneous invariant poly nomial of degree lal or the zero monomiali We actually only need a nite number of such invariants to generate the ring H11 i i 7 In Theorem Emmy Noether Given a nite matrix group G C CLnk we ave k117A71nG klRGI 1 l l S lGll In particular H11 i i i Inlc is generated by nitely many homogeneous invari ants Example 2 Return to the example C4 6 GLn7 k We need to compute R04ziyj such that ij S 4 Iiyj RC4 Iiyj Iiyj RC4 WW I 0 If 0 y 0 us 0 I I2 y 14 I4 y4 W No I3y 7 Iys y 12 y 12f 12f 13 0 Iys 713y7 193 12y 0 y4 z4 y4 Then by the theorem7 we know that the four invariants 12 y27 z4y47 zgyi zy37 and 12y Noticing that I4 y4 12 y22 2er2 we nd that we only need the three generators from before And we have proved that Mr ylc H12 zgy 7 Iy37r2y2l We have seen that by hand we can nd the generators of the ring of invari ants for lGl 4 But as the order of the nite matrix group and or the number of variables increases7 so does the number of monomials that we have to nd Thus7 we need to nd a more ef cient method for nding the generators The main tool for doing this is called Molien s Theoremi This theorem allows us to predict the number of linearly independent homogeneous invariants of a given degreei Once we have found that H11 i i 7 Inlc hf17 i i i 7 fm7 then we can ask if there is an algorithm for writing a given invariant f 6 H117 i i i 7177 in terms Offlvwwfrm Proposition Suppose that f17 i i i 7fm 6 H11 i i 7177 are given Fix a mono mial order in h 117 i i i 7 1777 M7 i i i 7 gm where any monomial involving one of 17 i i 7 n is greater than all monomials in hy17i i i 7ym Let G be a Groeb ner basis of the ideal fl Gylp i i 7 fm 7 ymgt C H117 i i i 7zn7y17i i i 7 Given f 6 H117 i i i 7177 let 9 f be the remainder of f on division by G Then 1 f 6 klflvwwfml 239f and only ifg 6 klylpuyyml 2 ff 6 hf17iu7fm7 then f gf17ui7fm is an expression of f as a polynomial in f17i i i 7 m Lecture Notes Math 499699 September 22 2004 Last week we talked about monomial orders7 and this week we will consider monomial ide si De nition An ideal I C Hal l l l In is a monomial ideal if there is a subset A C Z20 can be in nite such that I consists of all polynomials which are nite sums of the form EaeA ham where ha 6 hlzl l l l 717 We write I ltzu la E A Some properties of monomial ideals 0 Let I ltzu la E Agti Then the monomial mg 6 I if and only if some a 6 A7 I divides 13 Note In this case we can write z I IV for some 7 E Z7210 This equivalent to B a 7 0 Let I be a monomial and f a polynomial in Hzl l l l znli Then f E I ltgt every term of f lies in I 42gt f is a h linear combination of monomials in I 0 Two monomial ideals are the same if and only if they contain the same monomi si 0 Dickson s Lemma A monomial ideal I C h11iurn has a nite basis In Macaulay 2 we have a command monomialIdeali You type something like monomialIdea1a 2abb 3aci If an entry in your de nition of the ideal is not a monomial7 then the program will take the leading monomial in your polynomial Remember that the default order is grevlexi Now suppose that we start with a regular polynomial ideal and want a monomial ideal The most obvious ones to consider is de ned below De nition Let I C hlzl l l l 717 be a nonzero ideal i The ideal of leading terms of elements ofI is de ned LTI oral there exists f E I with LTf 010 ii We denote the ideal generated by the elements of LTI ltLTIgt Note If we let I ltf17i l l fngt then the ideals ltLTf1Hi 7LTfngt and ltLTIgt may be different By de nition LTfZ CLTI C ltLTIgt for each i7 and thus ltLTf1iHLTfngt Q ltLTIgti But7 we can see that equality is not guaranteed with the following example Let I ltfl7 f2gt lt13 7 21y 12y7 2y2 1 Let our monomial order be graded lexicographical orderi Then ltLTf1LTf2gt 1312y Because we have the identity My 7 2 z e m3 e 21y we know that 12 E ltLTIgti But7 12 1312y Proposition For a nonzero ideal I C hzlzn ltLTIgt is a monomial ideal Dicksonls Lemma then tells us that for any nonzero ideal I C H11 zn there are polynomials g1 gs E I such that ltLTIgt ltLT91 LTg5gtl This fact and the division algorithm discussed last week prove the existence of a nite generating set for every polynomial ideall Theorem Hilbert Basis Theorem Every ideal I E k11 zn has a nite generating set That is I ltg1 g5gt for some g1 gs E I We can choose the gi E I such that they are exactly the polynomials with the property ltLTIgt ltLTg1 LTg5gtl We give such ideals a special name De nition Fix a monomial order A nite subset G g1ld0tsg5 of an ideal I is said to be a Groebne39r basis if ltLTgl LTgsgt ltLTIgt From what we have seen above we nd that every nonzero ideal has a Groebner basis In fact any Groebner basis for an ideal I is actually a basis for It In Macaulay 2 the command for nding the Groebner basis of an ideal is simply gb Before we can use the computers to compute Groebner bases we should rst learn how to compute them by hand De nition Let fg 6 H11 zn be nonzero polynomials i If multidegf a and multidegg B then let 7 ylpumyn where 71 max ai i for each i We call 1 the least common multiple LMf and LMg and write 1 7 LCMLMfLMg ii The Spolynomial off andg is the combination Wak w g The S polynomial is designed to cancel leading terms Theorem Let I be a polynomial ideal Then a basis G g1 gs for I is a Groebner basis of I and only for all i f j the remainder on division of 5gigj by G some xed order is 0 Suppose we are given an ideal I and a basis G 91 gs First compute Sglg2 and if Sglg2 is not an element of g1 g5gt then add it to the ideal ltg1 g5gt Now you have the ideal ltg1 gs Sglg2 g51gt Next take the Spolynomial of g1 and ggl Check to see if it is our ideal and if not add the remainder terml Keep going until you have found a Groebner basis This process will terminate and is formally know as Buchbergerls Algorithml In computer language it goes something like this Theorem Let I ltf17iii7fngt 0 Then a Groebner basis for I can be constructed in a nite number of steps by the following algoiithm Input F lt13 of Output a Groebner basis G 91 i i i 79 for I With F C G G I F REPEAT G I G FOR each pair pqp q in G DO 5 I 51074 IF 5 THEN G GUS UNTIL G G c Here we are letting 517 4 denote the remainder on division of 517 4 by GA Lecture Notes Math 499699 September 29 2004 We can nally consider our rst use of Algebraic Geometry in a 77 real world77 problem integer programming Letls begin with a simple problemi Suppose that a local air freight company has only two customers UPS and FedEx who pay it to y packages from Houston to Dallas Each plane used can only carry loads up to 3700 kilos and up to 20 cubic meters UPS places its packages into groupings weighing exactly 400 kilos and taking up 2 cubic meters of volume The groupings from FedEx come weighing 3700 kilos and taking up 3 cubic meters FedEx is willing to pay 15 per package for ontime delivery while UPS will only pay 11 per grouping As the manager of the shipping company your problem is to decide how many shipments from each of the companies should be included in each ight to maximize your revenuesi Mathematically we are saying we want to maximize 11U15F subject to the following constraints 4U 5F S 37 weight limit in hundreds of kilos 2U 3F S 20 volume limit in cubic meters U F E Z20 Notice that we need U F to both be integersi This is an important restriction and the characteristic feature of integer programming problems lnteger programming problems are generalizations ofthe mathematical trans lation of the above example Namely in an integer programming problem we are looking for the largest or smallest value of some linear function clAl i i i ann on the set of all A1 i i i An 6 Z7210 satisfying some set of linear inequalities f1 a11141 a12142 ainAn S 0T 2 171 f2 a21141 a22142 a2nAn S 0T 2 112 f5 a51141 as2A2 asnAn S 0T 2 bs In addition we assume that the Aij b are integers not necessarily positivei We can go back to our example and think of it in geometric terms We are really looking for the element U F E Z2 lying in the convex polygon in R2 bounded above by the lines U 5F 372U 3F 20 and below by the axes U 0 F 0 The polygon described is known as the feasible regioni De nition The feasible region of an integer programming problem is the set P of all A1HiAn E R satisfying the inequalities in the statement of the problem It is possible for the feasible region to contain no integer points and thus the problem have no solutionsi Example In R2 consider the region AB 1 3A7B21 2A7B 1 A320 One way of solving our original problem is to just plug the values of all of the integer valued points in our feasible region into the equation llU 15F and nd the maximum value It turns out to be the point 44 We can do this quite quickly for our problem but what about problems in more equations or just larger feasible regions The general integer programming problem is known to be NP completei In order to discuss general integer programming problems we can make life easier by standardizing the problems using the following observations 1 Given a linear functional Al i i An we need only consider minimizing it since maximizing Z is just minimizing iii 2 We need only consider inequalities of the form S because a11141 i i i ainAn 2 bi ltgt ailAl Hf ainAn S 4 3 By introducing new 77slack variables we can change our inequalities to equalitiesi These slack variables will have coef cient zero in the linear function to be minimized Here is an example of introducing a slack variablei Suppose you are given 3A1 7 A2 2A3 S 9 Then you can introduce an A4 2 0 such that 3A1 7 A2 2A3 A4 9 Applying 12 and 3 above any integer programming problem can be written in standard form Minimize clAl i i i ann subject to a11141 M2142 v v v alnAn b1 a21141 2142 v v v aZnAn b2 asiAi as2A2 i i i asnAn 11 Aj 6Z20Iluini We can now turn our attention to solving such problems by turning them into questions about polynomialsi First suppose that all of the coef cients aij bj are nonnegativei We introduce an indeterminant z for each of the equations in the standard form and exponentiate to obtain the equality zgz1A1012A2amAn 232 for eachi l i i i s We can multiply these s equations together to get 5 5 H ZgzlAl022A2alnAn H i1 i1 We can rearrange the exponents to nd that n 5 A7 5 a 7 b 2 7 2 i F1 i1 i1 This equation gives us an algebraic characterization of the integer n tuples in the feasible region of the given prob emi Proposition 1 Let k be a eld and de ne g0 kw1i i i wn 7 H21 i i i 25 by setting 5 wj H 2 i1 for each j 1Hin and letting gw1 i i i wn gg0w1 i i i g0wn for each polynomial g E h w1i i i wn Then 1i i i An is an integer paint in the feasible region if and only g0 maps the manamial w1 1102 2 f to t e manamial 211 wnquot Example Consider the standard form of our shipping problem With slack variables X Yr Minimize 711U 715F 7 0X 7 OY subject to 4U 5F X 37 2U 3F Y 20 UFXY E ZZO Then we de ne our map 1klw17w27w37w4l A H21722l wl gt gt zfzg 112 gt gt W3 gt gt 2 1 104 gt gt 22 The proposition tells us that the integer points in the feasible region of the restated problem are the U F X Y such that U F X Y 7 37 20 80001102103 w421 22A Proposition 2 Suppose that F17 7 fn 6 H217 725 are given Fix a mono mial order in H217 7 257 1017 7 ion with the elimination property any mono mial containing one of the 2139 is greater than any monomial containing only the wj Then Q be the Groebner basis for the ideal Iltf1 w17wfn wngt and for each f 6 H217 727 let g 79 be the remainder on division of f by Then a A polynomial f satis es f E hf17l 7 if and only ifg E hw17u7wn b ff 6 hf17ul7fn andg E hw17l7wn7 then f gf17ul7fn C If each and f are monomials and f E hf17u7fn7 then g is also a monomial If you combine Proposition 1 and part c of Proposition 27 you nd that if 211 257quot is in the image of go7 then it is automatically the image of some monomial wA1 wf7 quotl Back to our example of shipping packages7 we would consider the ideal 4 2 5 3 I 122 70172122 702721 703722 w4gt C kl217227w17w27w37w4l Using lex order with the variables ordered 21 gt 22 gt wl gt 112 gt 103 gt 1047 we obtain a Groebner basis for this ideal7 3 2 4 3 2 4 2 2 3 g 21710372271047w4w37w17w4w3w27w17w4w3w17w27w4w17w3w271031027101 Then using the rst polynomials we nd that f 7230 reduces to 103710420 Hence f is in the image go7 and the remainder on division is g wgw llwgl This monomial corresponds to the solution U 47F 47 X 1 Lecture Notes Math 499699 September 8 2004 For our rst treatment of polynomials over elds7 we will consider the case of polynomials in one variable For the remainder of the semester7 we will assume that h is a eld not necessarily algebraically closed De nition 1 Given a nonzero polynomial f 6 Hz let f amIeru Jraildrao where ai E h and am y 0 Then m is the degree off and amrm is the leading term of f and we write degf m and LTf amzm Example If f 615 413 1312 9 then degf 5 and LTf 615 Because we are in a eld7 every element in It has a multiplicative inverse and thus for any two nonzero polynomials f7 9 6 Hz d59ltfgt S degg 42gt LTf divides LTg This leads us into our next proposition which is very similar to something you have seen in high school algebra Proposition 1 Division Algorithm Let g be a nonzero polynomial in Hz Then every f 6 Hz can be written uniquely as fqgr7 where qr 6 Hz and either r 0 or degr S degg Furthermore q and r can he found using an algorithm Idea of Proof The algorithm proceeds as follows Output 417 r q 0 r f WHILE r y 0 AND LTg divides LTr DO 4 1 4 LTTLT9 r z r e momom One way to see that this algorithm works is to notice that when we de ne q 0r we get the trivial equality f r Then we can see that 4 LTltrgtLTltggtgtg r e LTltTgtLTltggtgtggt qg momom r 7 LTrLTgg 49 r The process eventually terminates because r 7 LTrLTgg is zero or has degree smaller than the degree of r which is nite Example Let fr3212r1 g2117 907 rf Then 3 z 12 r1 zg212z171221l 212zli Notice that degr1 gtdegg7 so we have to repeat the process We now have 12 Eg x 4223 21 2 4 73 2 3 71 Tgiil zlilz21lilzli Now degr2 degg7 so we must repeat the process one more time This time l2 722 1 43723 4x 2r721 4x 8 l l 7 r3lz17 21l i Finally the degree of r3 is zero7 so we can set L 12 31 and r 7 8i Corollary 1 If f 6 Hz is a nonzero polynomial then f has at most degf roots in Proof lnduct on the degree of Corollary 2 Every ideal of Hz can be written in the form for some nonzero polynomia In general ideals of this sort are called principal and the polynomial ring Hz is called a principal ideal domain because all of its ideals are principal Now we come to our next question When given a set of polynomials generating an ideal in Hz how do we nd the one polynomial which generates the whole ideal The answer ends up being another word from high school7 the greatest common divisor De nition 2 Let g 6 Then GCDfg exists and is unique up to a nonzero constant in h GCDfgis a generator of the ideal ltfggt There is an algorithm for nding GCDfg The algorithm referred to in the de nition is the classic Euclidian Algorithmi For two polynomials g 6 Hz where g f 07 write f qg r with qr as in Proposition 1 Then we see that r remainderf g7 and we can nd GCDfg through the following algorithm lnput f7 g Output h h 2 f sg WHILEsy oDO rem I remainderh7 s hs s rem We can see this algorithm in action with the following example Example If f hl I4 71 and g sl 15 717 then rem I4 71 because I4 71 0z6 7 1 14 71 Thus7 h2157l7 32147li Now we repeat the process to nd that rem 12 71 because 15 7 l 1214 7 l 12 71 Thus7 h3z47l7 33127li One more repetition gives us rem 07 so h4 12717 340 Now we have found that GCDf7g12 7 1 Now suppose that you are given an ideal generated by more than two poly nomials in one variable f17iu7fni How then do we nd the generator of ltf17fngt7 De nition 3 A greatest common divisor of polynomials f17ui7fn 6 Mr is a polynomial h such that h divides f17 i i i 7fn fp is another polynomial which divides f17i i i 7 fn7 then p divides h We write h GCDf17H Proposition 2 Let f17i i i 7 fn 6 Hz where s 2 2 Then GCDf17 i i i 7 exists and is unique up to multiplication by a nonzero con stant in h GCDf17 i i i 7 is a generator of the ideal ltf17 i i i 7 Ifs 2 37 then GCDf17Hi7fnGCDf17GCDf27Hi7fn iv There is an algorithm for nding GCDf17 i i i 7 Lecture Notes Math 499699 October 6 2004 Letls begin this lecture With a motivetional problem Suppose you are given a cubic polynomial ion one variable With roots a1 a2 13 Then we can Write 13 1212 cz d I 7 a1z 7 a2z 7 a3 13 7 a1 a2 7 1912 a1a2 alas 012013 011012013 Thus we nd 5 011 012 013 C 011012 alas 042013 d 7a1a2a3 One may notice that the polynomails in terms of the alphals are unchanged under permutations of 11 a2 13 Such polynomials are said to be symmetric De nition A polynomial f 6 Hal rn is symmertic if f117 i i 7 f171 7170 where 739 6 Sn ie 739 permutes the n variables De nition Given variables 11 In we de ne the elementary symmetric functions 01 on 6 Hal rn by the formulas 0111I2In Ur E Eula i1lti2ltltiT on plaguan Notice that or is the sum of all monomials in 11 7 In Which are products of r distinct variables Proposition For any polynomial in h11zn with leading coe cient 1 the other coe cients are just the elementary symmetric functions of the roots up to afactor of i1 Theorem The Fundamental Theorem of Symmetric Polynomials Ev ery symmetric polynomial in H117 7 In can be written uniquely as a polyno mial in the elementary symmetric functions Now we will move on to our rst peek at Invariant Theoryl Let GLnh be the set of all invertible n X n matrices with entries in the eld h This is a group under multiplication where we will denote the identity matrix by W De nition A nite subset G C GLn k is a nite matrix group if it is nonempty and closed under matiix multiplication The number of elements in G is called the order of G and denoted Example 1 Let G be the set generated by A lt 0 fl 1 0 We nd that So we nd that G A 142143 A4 12 is a nite matrix group of order 4 Example 2 Let 739 be a permutation of 1 2 l l l So we permute 11 l l In by 739 to get 171 l l l zTnl We can determine a matrix from 739 M7 as follows 11 171 M7 z In awn M7 is called a permutation matrix and is obtained by permuting the columns of In according to 7quot In general there are it ways to permute n elements Noting that M71 M72 M7271 we nd that the permutation matrices are closed under multiplication so form a nite matrix group of order nll Example 2a Letls consider the permutation 739 de ned by z y 2 gt gt y z 0 l 0 0 0 Here 13 0 l 0 and M7 0 0 1 because 739 is de ned by send 0 0 l l 0 ing the rst column to the second spot the second column to the third spot and the third column to the rst spotl Example 3 Symmetries of regular polyhedral For example the set of rotations of the cube in R3 taking the cube to itself form a nite set which is closed under multiplications hence a nite matrix groupl Proposition Let G C GLn k be a nite matrix group Then i In 6 G ii A E G Am In for some integer m gt 0 iii AEG A IEG De nition Let G C GLnk be a nite matrix group A polynomial f E zlplqzn is invariant under G iffor X zlv wzn fX fA X VA 6 Cl C We denote the set of inveriant polynomials by H11 l l l 7 In Example 4 Consider the group Sn C GLn7 k of permutation matricesl Then H11 l l l Inlsquot symmetric polynomials Lecture Notes Math 499699 September 15 2004 We learned last time that every ideal in Hz is generated by a single element Today we want to consider ideals in the polynomial ring 11 zn ecall that on Mr we used the division algorithm to nd the generator of the ideal ltfi7 i 7 C This algorithm involved knowing what the leading term of our polynomials was Likewise we rst need to de ne some type of ordering on the monomials in n variables so that each polynomial can have a well de ned leading term De nition 1 A monomial ordering on H11 rn is any relation gt on Z20 satisfying i gt is a total or linear ordering on Z20 ii Ifagt andyEZgo thenaygt y iii gt is a wellordering on Z20 e every nonempty subset of Z20 has a smallest element under gt7 7 De nition 2 Lemicographic Order Leta 11 an 51 5 E Z20 We say that 1 gt1 6 if in the vector di erence a 76 E Z the leftmost nonzero entry is positive We write I gtle z if a gtle Examples a 523 gt1 155 because 523155 43 2 thus z 1213 gt1 b 123 gtlw 111 because 123111 012 thus 111313 gt1 111213 In practice if we are give two or three variables we will call them zy or z y 2 respectively and use alphabetical order I gt y gt 2 in order to de ne the lexiographic order Note that Lex order is the same as alphabetical order hence the name Example Amanda gt1 Bill gt1 Carl gt1 Edgar There are two other ordering which will come into play this semester so we will de ne them now De nition 3 Graded Lem Order Let 15 6 Z20 We say a gtgrlw B if eit er 7 lal Zai gt 0r lal anda gt1 6 i1 i1 Simply stated grlex orders by total degree rst and the uses lex order to break ties in total degree Examples a zy223 gtgrlw 14y because ll23l 6 gt K4 10l 5 b zy223 gtgrle zy24 because ll23l 6 Kl 14l and zy223 gt1 zyz De nition 4 Graded Reverse Lem Order Let 15 6 Z20 We say a gtgrevlw B if either 7 139 W gt W 2 or lal and in a 7 B the rightmost nonzero entry is negative As with grlex grevlex orders by total degree by now to break ties we look at the rightmost nonzero entry instead of the leftmosti A good way to think about this ordering is that sometimes you would like you would like y5 to be greater than 124 More generally you want any monomial with a positive power of the last variable In to be considered very small in the order Examples a zyz gtgrevlex my b any gtgrevlex zyz These monomials are not the only ordering known A fun project would be to explore more of these orderings Now let s see how to put the terms of a polynomial in H11 i i i In in decreasing order with respect to these orderingsi For an example let s set f 4y224 7 612 312y2 7 12 i 0 With respect to lex order we would write f 312y2 7 125 7 612 4y224i 0 With respect to grleX order we would write f 125 4y224 312 7 612 0 With respect to grevlex order we would write f 4y224 7 125 312y2 7 612 In order to generalize this example to all polynomials in n variables we develop the following terminologyi De nition 5 Let f Ea our be a nonzero polynomial in H11 i i i zn and let gt be a monomial order The multideg39ree of f is de ned multidegf maxa E Z20 a0 0i The leading monomial off is LOU amultidegf 6 76A The leading monomial of f is LM f zmumdewt iv The leading term of f is LTltfgt Loo LMU So in our example from before where f 4y224 7 612 312y2 7 125 we have 0 With respect to lex order multidegf 211LCf 3LMf z2yzLTf 312y2 0 With respect to grlex order multidegf 10 5LCf 71 125LTf 7125 0 With respect to greVleX order multidegf 0 2 4 LCf 4 y224 LTf 4y224 Lemma 1 Let fg 6 H11 i i i zn he nonzero polynomials Then multidegfg multidegf multide g If f g f 0 then multidegf g max multide f multidegg Equality holds multidegf7 multide g Now that we have established what we mean by a leading term with respect to a given monomial ordering we can speak of a division algorithm in the ring H11 i i i zn Proposition 1 Fix a monomial order gt on Z20 and let F f1i i i he an ordered ztuple of polynomials in hzlinznr Then every f 6 H11 i i i zn can be written as fa1flAuasfsT7 where air E hzlinzn and either r 0 or r is a linear combination with coe cients in h of monomials none of which is divisible by any LTfl Furthermore if ai 7 0 then multidegf2 multidegai