### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Topics in Mathematics MATH 676

CSU

GPA 3.78

### View Full Document

## 36

## 0

## Popular in Course

## Popular in Mathematics (M)

This 43 page Class Notes was uploaded by Melvina Keeling on Monday September 21, 2015. The Class Notes belongs to MATH 676 at Colorado State University taught by Staff in Fall. Since its upload, it has received 36 views. For similar materials see /class/210095/math-676-colorado-state-university in Mathematics (M) at Colorado State University.

## Reviews for Topics in Mathematics

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15

Course Notes for Math 676 Computational Algebraic Geometry Spring 2009 Prof Dan Bates Colorado State University February 23 2009 Chapter 1 Foreword These notes are being written on the y as I teach a graduate topics class in computational algebraic geometry We7ll be covering standard symbolic sorts of computation Grobner bases7 resultants7 etc and newer numerical methods homotopy methods7 numerical algebraic geometry After that7 we7ll have at least a few weeks left to really dig into some topics Please note that these notes are available to anybody but were originally intended as a reference for students in this topics course Since some of the details I will provide in lectures will come from various copyrighted sources7 some parts of these notes will be a bit sparse to be lled in later In general7 when possible7 I will point out good sources for details7 extensions7 or examples I am not intending to provide a thorough introduction to algebraic ge ometry lnstead7 my intention is to get to computation and applications as quickly as possible We7ll spend much more time on algorithms7 complex ity7 and adventures with software and applications than with theory The next time around7 things may change7 but that7s the plan for now Also7 I am pitching the course more towards math grad students since there are no engineersscientists in the course Please note that a there will be plenty of details missing from these notes and7 much more importantly7 b I make no claims that what I record here is entirely correct I am often rather informal with these notes7 so7 for example7 I am sometimes not so careful about including all necessary conditions when stating theorems So take everything with a grain of salt 7 the gist is there7 but dont take the details as hard fact That said7 if you spot any errors7 please let me know I would go broke if I offered even a penny for each such report7 but I will at least give you a smile and a hearty handshake Just two weeks into the course7 I already owe a signi cant debt to my students for their help both with these notes and with the lectures based upon them Thank you to all twelve of you in alphabetical order 0 Dan Brake 0 Shawn Farnell 0 Beth Malmskog Tim McCoy 0 Ken Monks Eric Nelson Matt Niemerg 0 Dusty Ross Eric Schmidt Elly Smith Jenna Tague Cassie Williams Contents 1 Foreword 2 Basics 21 Polynomials and their solutions 22 ldeals 23 Varieties 231 Dimension 24 ldeals and varieties 241 Combining ideals and varieties 242 Moving between ideals and varieties 243 Going a bit further 244 Did you say schemes 03 25 Big outstanding questions Development of Grobner Bases 31 32 33 34 35 Univariate division Univariate ideal membership Solving univariate polynomial systems77 Multivariate division7 round 1 Monomial orders 36 Multivariate division7 round 2 37 Monomial ideals 38 Leading term ideals and Gro39bner Bases 39 The ideal membership problem 4 Computation of Grobner bases 41 Recognizing Grobner bases 42 Computing a Gro39bner basis from scratch 43 Some computational concerns 44 Some responses 5 Solving polynomial systems exactly 6 Realworld polynomial systems 61 Kinematics 62 Game theory 63 Optimal control 64 Others 7 Basics of numerical methods 8 Homotopy continuation zerodimensional solving 9 Basic numerical algebraic geometry 10 Advanced topics in numerical algebraic geometry 11 Potential further topics 111 Hilbert polynomials and dimension 112 Fewnomials and bounds on the number of real solutions 30 30 32 33 33 34 35 35 35 35 35 36 37 38 39 40 40 40 113 Toric deformations 40 114 Tropical geometry 40 115 Basic convex geometry 7 Bernstein and such 40 A Advanced topics for talks 41 Chapter 2 Basics Much of this chapter was motivated by the two Cox7 Little7 and O7Shea books7 but especially the UTM book Ideals Varieties and Algoiithms which l7ll call CLOl Their GTM book Using Algebraic Geometry which l7ll call CLO2 is also canonical for this sort of course7 but the intro is a bit more terse and points to CLOl a lot Hal Schenck7s book Computational Algebraic Geometry and Bernd Sturmfels7 Solving Polynomial Systems are also close at hand while we go through some of these symbolic methods in the next few chapters 21 Polynomials and their solutions I assume that you know what polynomials are along with monomials7 co ef cients7 terms7 degree7 rings7 and elds If not7 check out CLOl for a nice introduction For now7 we only allow for nonnegative exponents in the monomials ie7 no Laurent polynomials7 but that restriction may be lifted later Polynomials live in polynomial rings l9x177xn commutative rings with 17 with l a eld or occasionally a ring7 typically Q R or C In fact7 for this course7 we7ll mostly think about l9 C A polynomial f 6 Elm will may obviously be thought of as a function f F a l De nition 21 A solution of a polynomial fz1 7x 6 l xl will is a point z 6 IF such that fz 0 ie st 2 E f 10 6 F is called ndimensional a ine space for eld E Think of R well get to projective space later If f is a set of m polynomials in n variables then we have a function f W a F De nition 22 Given a set ofpolynomials f f1 fm C Mal an a polynomial system a solution of the polynomial system f is a point z E P such that 0 fori 1m ie z is a solution for each polynomial in system f This brings us to the fundamental dichotomy in algebraic geometry 7 polynomials are algebraic objects which have as solution sets geometric ob jects The interplay between these two worlds is the focus of our course Sometimes we will use algebraic symbolic manipulations of polynomials to understand the corresponding geometric objects Sometimes though we will move to the geometric side to gather information about the algebraic side this is common in the numerical methods that well encounter later We will focus on the problem of nding solutions of polynomial systems This brings about a point that should be made clear fx 0 has two meanings for some polynomial f There is a polynomial meaning ie all coef cients appearing in f are zero and a functional meaning ie f evaluates to 0 for all input These need not be the same 7 Mail certainly evaluates to 0 for all elements of Z2 but is not itself the zero polynomial Luckily as proven nicely in CLOl the two meanings are the same for in nite elds 22 Ideals ln algebra we dont think about subsets of rings we think about ide als Given a set of polynomials f1fm C Fx1znl the ideal lt f1 fm gt generated by f1 fm is just the collection of all polyno mial combinations of the fi Think of linear combinations with polynomial coef cients rather than numerical coef cients If you havent seen ideals for a while this might be a good time to crack open your favorite algebra text To make a long story short a sums of elements of an ideal and b products of an element of an ideal with any ring element stay in the ideal Example 21 Let f x2yy2 C Rxy Obviously y and y2 are in lt f gt So is 3ny 7 yz as is z myl9 5z2y 3000y4 7 2 z 71y2 z isn t though neither is y or even 2 We want to study solution sets of polynomial systems f C Mal xn It would be handy as well see later if we could use ideals rather than sets of polynomials A solution77 of an ideal I is just a point that satis es all in nitely many polynomials in I Fortunately we can make this change of focus Proposition 21 The solutions off C F1xn are the same as those oflt f gt Proof Let f f1fm Suppose z is a solution of f ie 0 Vfl E f Then for any 9 lt f gt g is a polynomial combination of the fi But 0 for each i meaning that 92 0 Conversely the f are certainly elements of lt f gt so solutions of the ideal must satisfy each f D Given some description of an ideal I in a ring R without knowing any generators we have no guarantee that there is a nite set of generators for I The algorithms described later for solving77 polynomial systems computing solution sets typically put information about the generators of the ideal at hand into a matrix or cycle through them performing operations on each or each pair It would be utter disaster if some ideals in polynomial rings had to have in nitely many generators Fortunately we have the Hilbert Basis Theorem Theorem 21 Every ideal in a polynomial ring has a nite set of generators Good news huh Thank you Hilbert There are several ways of proving this For now though given the audience we7ll move on If you havent seen a proof before we7ll probably hit one later after talking about Grobner bases One quick note before we move to the geometric side In practice polyno mial systems coming from applications come as exactly that 7 a polynomial system rather than an ideal It is often adequate to use this polynomial system as it is handed to you just by plugging it into some numerical or symbolic software package but part of what makes us as mathematicians valuable to engineers and scientists is that we also know that there is an underlying ideal and that changing generators may be of use to us More on that later 23 Varieties Ideals are nice and all but we want to nd solutions of polynomial systems Here7s the fundamental de nition on this geometric side of the coin De nition 23 An a ine algebraic set is the solution set of a polyno mial systemideal in a polynomial ring Given a polynomial system f E Flz1zn we can move to the ideal I lt f gt We denote the solution set corresponding to I as VI A word about words Some authors would also call this a variety or more speci cally an af ne variety Hence the lI77 notation Other authors de ne varieties as irreducible af ne algebraic sets whatever irreducible might mean 7 well get to that soon I could be very careful and use the term af ne algebraic set77 but that7s a lot of keystrokes for not much bene t Just to set the record straight variety for me in these notes means an af ne or projective depending on the context algebraic set I make no assumptions about irreducibility So what can these varieties look like You have seen some before Example 22 Think about z E The solution set ofz 0 is well z 0 E R Shocking huh OK lets be a little more sophisticated Example 23 A system of linear equations 014 112 11min b1 0 124 122 12min b2 0 am i am z amy n bm 07 is also a system of degree I polynomials which generates an ideal The solution set of this system of linear equations is thus the variety for this ideal Thus linear spaces points lines planes etc are varieties z is a point in one variable a line in two a plane in three and so on As you proba bly know a linear space of dimension one less than the ambient dimension ie of codimension I is called a hyperplane and is given by a single linear equation Example 24 It tains out that we can provide a single degree 2 07quot higheiquot polynomial and still get something of eodimension 1 Think of y 7 d2 07quot y2 7 x2 in R2 The former is a parabola dimension 1 the latteiquot is a paiiquot of lines note that the latteiquot factors In R3 take x2 y2 22 7 1 yielding a two dimensional sphere A single noneonstant polynomial will always give you something of eodimension 1 231 Dimension OK7 so what is the dimension of a variety There is a lot to be said about this7 but lets keep it simple and mostly right for now Points are zero dimensional Lines and curves are one dimensional Surfaces are two dimensional This much is clear The codimension of a variety is just the ambient dimension minus the dimension What about7 for example7 a line and a point together7 such as you get with the system dz 7 17 zy 7 1 in R2 Obviously7 we think of the line as being dimension one and the point as being zero dimensional ie7 isolated By convention7 we declare that this variety the union of the line and the point has dimension one as this is the maximum dimension of the two bits Loosely speaking7 dimension is the number of degrees of freedom on a variety not including rotation A bit more technically and locally7 it is the dimension of the tangent space at a point on the variety For example7 for a nice7 smooth curve7 the tangent space at a point is a line7 making it one dimensional For a nice surface like a sphere7 the tangent space at any point is two dimensional7 so we say that the sphere is two dimensional OK7 so what does nice mean Think about a self intersecting curve7 e7 some curve that has a loop Other than at the point of self intersection7 the tangent space is one dimensional However7 for that one special7 nasty point7 there are two tangent directions What do we do about this De nition 24 NOT CORRECTX The dimension of a variety is the di mension of the tangent space at a nice point on the variety By nice I am talking about nonsingularregularsmoothmanifold points7 ie7 points at which the Jacobian matrix has full rank The nasty points are then singular where the Jacobian does not have full rank Unfortu nately7 this notion of dimension is still not entirely correct In the example 10 above a point and a line the entire line is singular 7 no nice77 nonsingu larregularsmoothmanifold points If we are looking for nice points we are left with only the isolated point which would lead us to call the variety zero dimensional which is incorrect In fact this will always happen when a component of a solution set is not of the correct77 dimension ie when the codimension of a component does not equal the number of polynomials in the system Such a component will always be singular Yikes So how can we talk about dimension Well there are at least two answers for now on which we may elaborate a bit later First a fairly standard de nition of dimension is that it is the degree of the Hilbert polynomial That will take some unwrapping which I hope to get to later on Second we can move to lV de ned below for each component 7 this is the ideal of all polynomials that vanish on our algebraic set In the example above we would then get lt z gt for the line so we get that all points are nonsingular on the line since the Jacobian would be 1 0 which is full rank At this point we could go on and carefully de ne dimension but we already have intuition about this For now we are better off using that intu ition and moving on Perhaps later we will come back to Hilbert polynomials and at that point cover dimension One last thing before we start getting to more sophisticated connections between varieties and ideals Given no polynomials our solution set is by default the entire ambient space eg F Adding one polynomial equation to our polynomial system chops the dimension by one yielding a hypersur face What if we add another lntuition says that the dimension should again drop by one right For example think about the linear picture Adding one nontrivial linear equation drops the dimension by one always Adding another nontrivial linear equation may decrease the dimension by one more but not necessarily For example suppose the two linear equations are linearly dependent Unfortunately the same holds true in the nonlinear setting The number of equations does not directly dictate the codimension of the corresponding variety though it does provide an upper bound on the codimensionl 24 Ideals and varieties 241 Combining ideals and varieties Given two varieties ie Vf1 f and Vgl 91 what can we say about the intersection and union of these two varieties In particular are they also varieties ie can we cook up polynomials that de ne them Before reading on try it Take the case of two hypersurfaces each given by one polynomial f and 9 say Then the intersection is given by the system f g 0 In general we just merge the two polynomial systems together to get the intersection of the two varieties As for the union we want one set of polynomials to hold or the other In the case of two polynomials as in the last paragraph fg 0 suf ces Check this What if we have the union of Vf1f2 and Vglgg Then take all four combinations Check this too This case is a little harder to prove than the intersection case above 242 Moving between ideals and varieties Now we can nally get to the main set of ideas 7 the dictionary77 as it is called in CLOl We already know that we have a map from ideals to varieties ie There is also a map in the other direction lndeed given some set of points V C F we de ne V f E Fz1 n fz 0 V2 6 V ie V is just the set of all polynomials that vanish at all points of V Using these two mappings we can now move back and forth between ideals and varieties What if we go over and back 7 will we come back to where we came from Lets start with a variety V V is all polynomials that vanish on V Now what is the common zero set locus of the polynomials of V Well its just V fairly obviously This isn7t a formal proof but one can prove that V VIV if V is a variety to begin with This seems nice What if V is not a variety to begin with How about the other direction Take an ideal I and move to the variety VI Now take all polynomials that vanish on VI to get IVI Does 12 I IVI necessarily Think about 2 in R It vanishes at z 07 so IVI includes xzng and x z is not in lt 2 gt7 so we have moved to something bigger ln fact7 with some work7 we could prove the Hilbert Nullstellensatz Theorem 22 IVI if we are working over an algebraically closed eld What is W It is the radical of the ideal I and is de ned by W f 6 Elm will f E I for some Clearly7 I C Recall that an ideal is said to be radical if I Suppose we take two ideals I1 C I2 Since I2 is larger7 it places more restrictions on the corresponding variety7 so we get that VI2 C VI1 The same actually holds true in the opposite direction7 too Check this So7 to sum up where we are so far7 we have inclusion reversing correspon dences between ideals and varieties that are not bijective 243 Going a bit further We can say more if we dont think about general ideals and varieties For ex arnple7 suppose we restrict to the case of radical ideals over an algebraically closed eld and their corresponding varieties Then I so we have I IVI and V VIV7 so we have a bijectionl More can be said along these lines When we look back to our example with a point and a line7 we want to say that there are two components 7 a line and a point How can we make that precise De nition 25 A variety is irreducible if it cannot be written as the nite union of strictly smaller varieties Great7 but how do we know that something is irreducible For exarnple7 what keeps us from writing the y aXis as the union of the positive7 zero7 and negative parts Couldn7t those be varieties We need to go back to algebra De nition 26 An idealI is prime if eitherf E I org 6 I anytime fg E I Proposition 22 An a ne variety V is irreducible if and only if IV is prime Proof sketch straight from CLOl Assume V is irreducible Let fg E IV7 and let V1 V Vf and V2 V Vg which are varieties since intersections of varieties are varieties Since fg E IV7 we have that fgz 0 for all z E V So7 for any point z 6 V7 we have that z 6 V1 U V2 since fgz 0 means that fz 0 or 92 0 Conversely7 V C V1 U V2 by de nition of those two varieties7 so that V V1 U V2 V is irreducible7 though7 so7 WLOG7 assume that V V1 Then f vanishes throughout V7 meaning that f E IV In the other direction7 assume IV is prime and let V V1 UV2 WLOG7 assume that V 31 V1 WWTS that V V27 so we7ll show that IV IV2 since7 then7 we can apply the V mapping V2 C V by de nition7 and V1 is a proper subset of V meaning that IV is a proper subset of IV1 Choose f E IV1 7IV and g E V V1UV2 tells us that fg vanishes on all of V But I prime forces f or g to be in IV By de nition7 f is not in IV7 so 9 E IV7 meaning that IV D Every prime ideal is also radical7 so this proposition gives us that there is a one to one correspondence between prime ideals and irreducible varieties But wait7 there7s more Every variety can be decomposed into a union of irreducible components Even better Proposition 23 Every variety has a minimal irreducible decomposition where no variety may be contained within another which is unique up to ordering of the union Because of our propositions above7 we also have the following Proposition 24 Over an algebraically closed eld every radical ideal of a polynomial ring has a unique decomposition as an intersection of prime ideals no one of which is contained in another All of these statements are proven in Chapter 4 of CLOZ in case you are curious The previous proposition holds only for radical ideals What about gen eral ideals Can we decompose them into an intersection of primes Unfortunately7 the intersection of primes is always radical7 so no such luck We need to go one step further and de ne primary ideals De nition 27 An ideal I is primary if fg E I implies that either f or 9 quot is in I for some in Primes are primary and if I is primary then P is prime and is the smallest prime containing I In that case we call I P primary Proposition 25 Every ideal can be written as a nite intersection of pri mary ideals The previous proposition holds for all Noetherian rings so it includes all polynomial rings over any eld including nite elds There is some sense of minimality too but this is enough for us If you toss in minimality you get the Lasker Noether Theorem To nish the algebraic picture an ideal is maximal if it is proper but not contained in any larger proper ideal These are nice Proposition 26 Over an algebraically closed eld mapimal ideals always have the form lt 1 7 a1 pn 7 an gt and vice versa ie maccimal ideals correspond to points Only the opposite direction holds if the eld is not algebraically closed To see that this doesnt hold over R for example consider the ideal generated by p2 1 Over R the variety is empty so it seems believable that this ideal could be maximal Moreover think of it over C it is contained in the maximals lt z i gt and lt z 7i gt which obviously don7t exist over R So the picture is that our ring sitting at the bottom of some tree which we will describe is contained in and is equal to the intersection of a set of primary ideals The radical of each of these primaries is a so called associated prime Some of these could be maximal though that isnt necessary Proposition 27 The set of primes associated to ideal I is uniquely deter mined ie it doesn t depend on a choice of primary decomposition There is nothing saying that associated primes cannot sit inside one an other ln fact we have the following de nition De nition 28 If associated prime P contains no other associated primes it is considered a minimal prime Otherwise it is an embedded prime Moreover we de ne the primary component associated to a minimalembedded prime to be minimalembedded itself There is a lot to keep straight here In our polynomial ring we have general ideals some of which are primary Among the primaries we have primes Among those primes some are maximal and if we are considering 15 the decomposition of a particular ideal some are minimal while others are embedded The terms minimal and mapimal both come from their role on the algebraic side obviously Since embedded primes contain other associ ated primes the variety of an embedded prime or primary is contained in the variety of some other component ie it is embedded Thus the term embedded re ects the geometric interpretation Example 25 Think about the ideal lt z gtC It is pretty clearly prime but not mapimal Each point 0a on the y accis has maccimal ideal lt my 7 a gt which clearly contains the ideal lt z gt However these are not embedded primes since they are not associated Alright so primes pick out our irreducible components for us What extra information do we get from looking at primaries rather than primes To answer this we need schemes 244 Did you say schemes Yep But dont worry we wont go too far down this path In fact lets just say that primary ideals contain derivative information77 that is missed by primes ideals Also lets take a look at an example or two straight out of Eisenbud7s nice book on Commutative Algebra Think about the variety I lt my gt in Rlpy B This is just the origin 7 not so exciting In fact I is prime since its maximal so we really do get just the origin What primary ideals are associated to I Here are a few along with a brief and incomplete geometric interpretation Example 26 J lt x2y gt For some reason we don t have time to get into it at least for now we look at RJ ie the quotient ring A general element f E R has all monomials in z andy with coe icients in R The class off in RI though is of the form a bx since all other monomials are killed by J check this Note that a f00 andb 00 Thus we are led to say that although the set theoretic geometric object for J is just the origin the scheme theoretic geometric object is the origin plus a smidge in the p direction corresopnding to the function value and the derivative with respect to p respectively The picture we would draw is the origin with a tiny arrow pointing in the positive z direction Example 27 J lt zzxyy2 gt Using the same kind of analysis as above we get the rst partial in both the z andy directions We could draw an arrow in each direction but in this case we usually just draw a fuzzy little dot around the origin This is referred to as the rst in nitessimal neighborhood at the origin Example 28 Let J be given by all 11th degree monomials in z andy Then we get all partials up to order 10 and draw a bigger dot at the origin this seems silly I know This is the 10th in nitessimal neighborhood Now lets move to I lt z gt in the same ring This is prime and gives us the y axis as the variety Example 29 J lt 2 gt This is just like the rst eccample aboue ecccept that we get the tangent in the z direction for all points on the line ie a fuzzy line Now what if we choose two different primary decompositions for the same ideal Example 210 I lt ay gtlt z gt lt zzzyy2 gtlt z gt W lt x2y gt Either way we get the y accis plus the rst in nitessimal neighbor hood at the origin Check this That7s all were going to say about this at least for now Would you like to know more If so Eisenbud7s Commutative Algebra with a View toward Algebraic Geometry is very easy to read and informative The two Cox Little ampO7Shea books are nice too though they do not delve quite as deep Decker Kc Schreyer also discuss these ideas at the beginning of their book If you really like commutative algebra AtiyahiMacDonald is canonical as is Matsumura 25 Big outstanding questions Gro39bner basis methods are going to let us answer some big questions that would otherwise be more dif cult if possible at all Here are a few 1 Given some ideal what is the corresponding variety This is a big one and it will be essential during much of the course 17 2 How can we tell whether some polynomial is in a given ideal 3 How can we tell whether two ideals are identical Chapter 3 Development of Grobner Bases As we will see shortly the ideal membership problem our focus for the next short while is solved via simple division in the univariate setting It would be great if that were the case in the multivariate setting too though there are a couple confounding factors We7ll hit those on our way to Gro39bner bases one of the main goals for this course In the next chapter well take a look at how to compute and recognize Gro39bner bases Cox Little and O7Shea give one of the best treatments of the development of Gro39bner bases that l have seen so I will just give the highlights here For a nice treatment related to this chapter and the next couple check out Chapter 2 of CLOl 31 Univariate division Welcome back to high school today Well be doing long division of univariate polynomials Formatting division is a headache so PM just talk you through an example Example 31 Let s divide 33278 by z5 First notice that we order the monomials by decreasing degree Now to start dividing we compare leading terms and gure out what the rst term of the quotient must be In this case it s 2 Notice that this depended only on the leading terms Now we multiply 2 by x5 and subtract this from x33z278 yielding 72x278 notice again that we have the monomials in a particular order Again we check leading terms In the end we have that x3 3x2 7 8 2 7 2x 10 x 5 7 58 19 ie the remairider is 58 The point of this example is to notice our assumptions 7 we have a term order7 we pay attention to leading terms only7 and we end up with a quotient and a remainder Moreover7 we can write f qg r for any polynomials f and 97 where r 0 or degr S degg Even better7 this division method is an algorithm It is correct gets the right answer and terminates in nite time since the degrees of the subresults keep dropping Also7 it is deterministic since multiple runs with the same input will certainly guarantee the same output there are no choices to be made anywhere Finally7 there is a certi cate that it is correct 7 we can just check the answer at the end by simple arithmetic What happens in the multivariate case well get to that soon7 though the basic requirements are similar with one extra wrinkle about remainders First7 though7 lets see what division does for us in terms of our big questions membership and solving 32 Univariate ideal membership First7 notice that univariate polynomial rings are principal ideal domains ie7 each ideal is principal7 ie7 each ideal can be generated by a single generator lndeed7 for any nonempty ideal I7 let 9 E I have minimal degree among polynomials in I Then7 for any f 6 I7 we can write f qg r with r f 7 qg E I of degree smaller than 9 But 9 was chosen with minimal degree7 so r 07 meaning that g qg lt g gt So7 to decide if a polynomial f is in some ideal I7 just nd a generator 9 st I lt 9 gt and see if glf evenly a remainder of zero lndeed7 f E I lt 9 gt iff f qg for some polynomial q Now all that remains is to cook up a generator for any given ideal I The GCD h of polynomials f and g is characterized by the facts that 1 h divides both f and g and 2 any other divisor of both must also divide h Proposition 31 GCDfg eccists is unique up to a coristarit cart be cal culated somehow arid gerierates lt g gt I Most of this should be fairly clear The Euclidean algorithm yields the 20 GCD As for generating I7 we know that there is a polynomial h more than one7 actually such that I lt h gt The claim is that h GCDf7g As proof7 notice that h divides both f and 97 so that condition 1 of the de nition of the de nition of the GOD is met Suppose p is some other common divisor7 so that f qlp and g 12p Since h E I lt f7g gt7 h clf egg clql c2qZp7 so p divides h D All of these concepts extend up to multiple univariate polynomials ln particular7 the GOD of a set of more than two polynomials can be found be nding the GOD of any 27 then the GOD of that GOD and another polynomial7 then the GOD of that GOD and another polynomial7 etc Example 32 Isp p478x322gtkz2724gtkp9 E I lt x375z27p7 37 p2 7 7x2 15z 7 97x3 7 6x2 11x 7 6 gt 9 To decide this we rst nd the GOD of the generators of the ideal In Maple just include the Algebraic package and use the command GCdGCdfg h where f g and h are the generators of I That command yields p2 7 4x 3 and division ofp by this GOD yields a remainder of 0 via Remainderfgcd1 Note that a nonzero remainder guarantees that the polynomial is not in the ideal 33 Solving univariate polynomial systems ldeal membership is interesting and has its uses7 but7 in the real world7 solving polynomial systems is arguably more important How do we solve univariate polynomial systems Obviously7 we can move from any given set of generators to a single generator via the GCD7 as described in the previous section So we need to solve single7 univariate polynomials You probably know some things about this 0 f 0 The solution set is z E F o degf 0 and f 31 0 No solution 0 degf 1 f z 7 a7 so z 7 a is the unique solution 0 degf 2 Quadratic formula 21 o degf 34 There are formulas The MacTutor History of Math page at St Andrews in Scotland has a great write up about the characters who rst discovered these formulas o degf 2 5 Out of luck symbolically Abel supposedly gave the rst proof of this though according to MacTutor Ruf ni certainly played a role So what do we do about solving general univariate polynomials Note rst of all that there are no more than d distinct complex or therefore real solutions Thus if we nd d we know that we are done Method 1 Newton7s method for real roots We7ve all seen this one before Just grab a host of starting points and plug them all into the Newton machine well talk more about Newton7s method when we get to numerical methods but there are a few things to notice First not all starting points converge In fact try to nd the roots of 2 71 starting from 05 3 and 12 You will see that the rst converges to 1 quickly quadraticallyl the second converges immediately exactly in one step to 1 and 12 diverges Well the last is at 1024 after 5 steps Also note that singular solutions kill the quadratic convergence of Newton7s method but well worry about that sort of statement later Unfortunately this doesnt cut it for us Without knowing a priori how many real solutions a polynomial has there is no guarantee that we can nd all of them Indeed if there are less than the degree we will not know that and will ad in nitum choose more and more starting points from which to try Newton7s method Method 2 Eigenvalues of companion matrices LSt f a d ad11sd 1 10 The following matrix is called the companion matmw of f denoted Cf 0 0 0 77 1 0 0 fail ad 0 1 0 7L2 ad 0 0 1 iad l 22 lt7s then fairly easy to prove that the solutions of f are precisely the eigenvalues of Of and vice versa Check out Sturrnfels7 CBMS book for more on this Method 3 Sturm sequences and bisection for real roots This one is also out of Sturrnfels7 book and is probably not as well known judging from my experience De ne p0 f7 p1 a and pl 7rernpl27pi1 for i 2 2 This is the Sturm sequence for polynornial f Theorem 31 Let a7b be an interval in R such that fa 31 0 and fb 31 0 Then the number of real roots in the interval is Na 7 Nb where Nz is the number of sign changes in the Sturm sequence when evaluated at x Thus7 given an interval7 we can count the number of real roots in the interval Bisecting the interval then tells us how many roots lie in each half interval P rorn there7 we can continue bisecting and dropping any intervals that contain no roots Eventually7 the diameter of the intervals will be less than 6 as long as E gt 0 Example 33 Consider 2 7 1 on 7272 At z 72 the Sturm sequence evaluates t0 3 42U N72 2 and t0 3420 at z 2 N2 0 so there are 2 7 0 2 roots in the interval Before moving on to rnultivariate considerations7 it is worth recalling Descartes7 Rule of Signs ln particular7 the number of positive real roots of polynomial f is bounded above by the number of sign changes among its coef cients Plugging in 7a for a we get the same result for negative real roots7 and zero can of course also be a root Putting those three facts together7 we have that a degree d univariate polynornial with m rnonornials will have no more than d distinct real roots thanks to the fundamental theorem of algebra and no more than 2m71 real roots thanks to Descartes7 Rule of Signs As we may see later7 these bounds in some way generalize up to rnultivariate polynomials in the form of the Bezout bound and fewnornial bounds On to rnultivariate stuff 34 Multivariate division round 1 ls f zzy zyz y2 E RlLy in the ideal generated by 91 y2 7 1 and 92 xy 7 1 thanks7 again7 CLO17 Using the univariate case as our 23 precedent let7s divide Wait How do you divide f by two polynomials I suppose you could divide by one and then the other but what if the result of this is then again divisible by 91 For that matter even if we do decide in what order to divide how do we choose leading terms since division involves comparing leading terms We need to choose a reasonable order for the monomials in our polynomial ring But what would make a term order reasonable Well here are a few things 1 Our order should compare any two monomials ie we should never be unsure which term of our polynomial is the leading term because two terms are incomparable D well be multiplying monomials together during division so we may want orders to be maintained by multiplication In other words if x lt x where 04 and B are n tuples of nonnegative integers then we want xu lt z for any n tuple of nonnegative integers 7 that we choose 3 For various algorithmic reasons ie proofs of termination we7ll want any set of monomials to have a minimal element Now we can de ne what is called a monomial or term order 35 Monomial orders De nition 31 A monomial order or term order for the monomials of Fx1xn must satisfy the three conditions given above ie it must be a total ordeiing it must respect multiplication by monomials and it must be a well ordering Actually the third requirement is a consequence of the other two though you dont necessarily see that a priori so it is enough for an order to satisfy the rst two conditions Also CLOl covers this much more nicely and in more detail Also please note that a monomial order requires a variable order too A monomial order using the variable order Xy could will be different than the same monomial order with the variable order reversed 24 Example 34 The led term order ledicographic is perhaps the easiest to understand To compare two monomials rst look at the edponents of the rst variable If they are di erent then the monomial with the larger rst edponent is larger If there is a tie move to the second variable and compare those edponents If all edponents are the same then the monomials are the same For edample we have dzy gt dyz assuming that we set d gt y because the edponents for d are 2 gt 1 If we flip the variable order then the conclu sion on this edample flips too As another edample dy lt dy2 because the edponents on d are the same but those fory are 1 lt 2 Example 35 grled graded led or degree led is probably the second easiest to understand To compare two monomials you rst compare their total degrees the sum of all edponents If they di er then you draw the obvious conclusion Otherwise you use led as a tiebreaker For grled with d gt y dzy gt dyz since the degrees are the same and led orders them this way However led would set dzy gt dy8 whereas grled goes the other way since 3 lt 9 Example 36 grevled graded reverse led is the nastiest of the standard three monomial orders Again the rst comparison is by degree just like with grled BUT the tiebreaker is reverse led 7 you look at the last variable instead of the rst and favor the smaller edponent rather than the larger So it s actually graded double reverse led sounds like gureskatingl For edample dzy gt dyz because they have the same total degree and the y variable has edponents 1 lt 2 and the monomial order flips this edponent order Keep in mind though that grading degree is always the rst thing to check 36 Multivariate division round 2 Now that we have monomial orders under our belts we can try dividing again First though let7s x some terminology De nition 32 Let f Zaad E Fd1 n with a ded monomial or der Then the multidegree of f multidegf is just the largest edponent appearing in f an n tuple The leading coef cient LCf leading mono mial LMf and leading term LTf off are the coe cient monomial and term coe cient times monomial that go with the term having the largest degree ie the multidegree respectively 25 OK let7s divide something Let7s divide zyz 1 by zy 1 and y 1 in that order using the leX order with z gt To write this down just stack the two divisors where you usually put the divisor Also there will be two quotients 7 one for each divisor 7 that sit atop the dividend where the quotient usually goes well proceed as usual checking whether the leading term of a divisor divides the leading term of the dividend beginning with the rst divisor and working our way down In this case xylxyz so we put y in the rst quotient multiply and subtract like usual This leaves us with 7y 1 xy LTxy 1 doesn7t divide 7y but y LTy 1 does so we put 71 in the second quotient multiply and subtract leaving us with 2 Obviously neither leading term divides 2 so we conclude that zy21yzy17y12 If we knew that multivariate division solved the ideal membership prob lem we7d be golden Unfortunately we dont yet Let7s try another one for a good reason 7 not just torture Let7s divide zzy zyz y2 by xy 7 1 and y2 7 1 This is one of many places where you are far better looking in 0101 After the rst two steps we are left with the partial dividend z y2 y Neither xy nor yz divide s so it is tempting to say that we are done HOWEVER y2 the leading term of the second polynomial divides y2 the second term of the partial dividend so we should take advantage of that Thus we set up somewhere a list of things in the remainder and add z to it leaving behind y2 y We can that add a 1 to the second quotient multiply and subtract leading us to the next partial dividend y 1 Now neither leading term of a divisor divides either of the terms of y 1 so we of cially say that we are done and end up with z2yzy2 112 zyw 7 1 112 71y1 All told in dividing f by some set of polynomials 9 we end up with f 2 19 r where the remainder r is 0 or is built from monomials none of which are divisible by a leading term of a 9 That7s the good news The bad news is that if you swap the order of the divisors in that last example you get a different remainder 7 2x 11 So as things stand the division algorithm doesn7t solve the ideal membership problem Bummer Wouldn7t it be nice if we could cook up a nice77 set of generators for an ideal so that division by these generators would yield unique remainders and thereby solve the ideal membership problem for multivariate polynomial rings 26 37 Monomial ideals De nition 33 An ideal is a monomial ideal if it has a generating set con sisting only of possibly in nitely many monomials Not a shocking de nition7 but it will be a useful concept Note that a monomial is in a monomial ideal iff some generator divides it evenly Note7 too7 that although the Hilbert Basis Theorem discussed in Chapter 2 guarantees the existence of some nite generating set7 there is no guarantee from that theorem that there is a nite generating set consisting only of monomialsl More on that in a moment ldeal membership in a monomial ideal is a piece of cake ln particular7 for a monomial ideal I7 f E I iff every term of f is in I iff f can be written as a linear combination ie7 the coef cients are numbers from the eld of ideal elements So7 to check whether f 6 I7 just look at each monomial But wait7 there is no guarantee that we have a nite generating set consisting only of monomials7 so this criterion is perhaps not so practical7 right Wrong Dickson7s Lemma says that monomial ideas are nitely generated by monomials ln fact7 in CLOl7 they rst prove Dickson7s Lemma and then prove the Hilbert Basis Theorem as a corollary So7 we now have an ideal membership algorithm for monomial ideals f E I iff Rem gi 0 for some generating set g of I Fine7 but not all ideals are monomial ln fact7 most interesting ones aren7t What do we do in general 38 Leading term ideals and Grobner Bases De nition 34 Let I be a nonzero ideal in a multivariate polynomial ring over a eld LTI is the set of all leading terms of polynomials in I and lt LTI gt is the ideal that they generate Notice that L lt LTI gt is a monomial ideal That means that it has a nite generating set of monomials HOWEVER7 be careful 7 the leading terms of a provided set of generators of I need not generate Ll lndeed7 let f x3 72y and g y 7 2y2z Then zgiyf 2 is in I7 meaning that 2 is in L7 but x2 is not divisible by either LTf or LTgl We7ll always 27 have that the ideal generated by the leading terms of the generators of I is contained in L but the reverse containment is not guaranteed OK so not every set of generators for I can lead to a generating set of L by taking leading terms But there must be at least one set of generators that can from the last section so lets give them a name De nition 35 Under a coed monomial order a set of generators of an ideal is a Grobner basis for the ideal if the leading terms of the generators generate L That7s it That7s all that a Grobner basis is 7just a nice set of generators for an ideal Granted we dont know how to cook one up for a given ideal We dont even know how to check that a set of generators is a Gro39bner basis well get to those points in the next section Before we go though note that every nonzero ideal in a multivariate polynomial ring has a Grobner basis 39 The ideal membership problem Grobner bases are the bases that we were talking about back in 36 They are the nice bases which give us unique remainders when dividing In a multivariate polynomial ring R Flzlznl given a Grobner basis G 91 91 of an ideal I C R and a polynomial f E R we know that there is a unique polynomial r E R having no term divisible by the leading terms of the g and there is some 9 E I such that f g r This is pretty straightforward to prove 7 g is what it needs to be and r is unique because otherwise the leading term of the difference of any two distinct remainders is divisible by some LTg since the difference is in I But we assumed that no term of any remainder is divisible by any of these LTg so the difference is 0 Since the remainder upon dividing a polynomial f by a Grobner basis is unique it is reasonable to name it 7 we call it the normal form for f Note however that the quotients when performing such a division need not be unique Of course this doesnt matter 7 we dont care which linear combination of the elements of a Gro39bner basis yield f 7 r In fact we will typically only care whether the remainder is zero Since this normal form will come up from time to time it makes sense to have some notation for it 28 De nition 36 Rf7G is the remainder off when divided by a Grabner basis G Note that this di ers from the notation in CLOZ Finally7 we can solve the ideal membership problem for multivariate polynomial rings f E I iff the remainder when dividing f by a Grobner basis for I is zero ie7 if Rf7 G 0 The proof is pretty obvious7 given the uniqueness of the remainder The problem is that we dont know how to compute a Grobner basis for a given ideal We don7t even know how to check whether a set of generators is a Grobner basisWe7ll cover those topics and some complexity concerns next 29 Chapter 4 Computation of Grobner bases As well see soon Gro39bner bases are handy computational tools In fact for a while and still in some settings they wereare the only option for computation As a result there has been a fair bit of thought put into their computation though like everything there are some limitations imposed on their effectiveness due to the complexity needed to compute them In this chapter we will talk about the standard way to compute a Gro39bner basis some of the related computational concerns and some of the responses that have been cooked up in response to these concerns As above we7ll follow CLOl as far as we can with this though we will start branching out at the end of this chapter 41 Recognizing Grobner bases Given some ideal I and a potential Gro39bner basis H how do we check whether H is indeed a Gro39bner basis for I Well what does it mean to be a Gro39bner basis It means that the leading terms of H generate the ideal generated by all leading terms of polynomials of I How can we miss things Well one obvious way as we saw in 38 is that the leading terms can be cancelled out in some two term polynomial combination In particular it should be easy to cook up a B a and b so that the leading terms of hl and hg cancel in the polynomial combination azahl 7 lug12 For example in 38 we had that 2 zhl 7 yhg where hl y 7 2y2 z and hg 30 3 7 2mg Note that this is emactly EX 2 of 25 in CLOl In this example a b Oz B 1 2 is clearly the leading term of 2 and it is certainly not in the ideal generated by the leading terms of hl and hg at least using lexl So hl and hg do not constitute a Gro39bner basis for the ideal that they generate In fact the ab 046 to get leading terms to cancel is so straightforward let7s write them down The following is known as the S polynomial for two other polynomials f and g 7 7 s S f g 7 if 7 79 lt LTf my where y E Zgo is given by y mazmultidegf multidegg and LT includes the leading coef cient as usual By the way the S stands for syzygy a fancy word for alignment particularly in astronomy and other algebraic geometry Again let7s check out an example from CLOl Consider the polynomials f xsyz 7 xzys z and g z4y y2 using the graded leX order 7 4 2 so we get 4y2 4y2 Sltf7 9 W i 7 1 3 3 2 3 7 s s 7 41 9 y 3y 7 meaning that we dont have a Gro39bner basis CLOl nicely proves that this is the only way to have leading terms cancel out Given some set of polynomials h1 hk all with the same multidegree they prove that any polynomial combination ofthe h with lesser multidegree must be a linear combination of polynomials of the form Sh hj Finally based on this we get the criterion originally provided by Buch berger for checking whether some basis is indeed a Grobner basis In partic ular a potential generating set H for an ideal I is indeed a Grobner basis for I iff RShhj H 0 for all 239 31 j The forward direction is obvious 7 S polynomials are in the ideal so division by a Grobner basis is automa tially zero as described above In the opposite direction we need to take f lt hlhk gt and show that LTf lt LTh1LThk gt f is a linear combination of the hi and in looking at the multidegree of f and the multidegrees of the summands of the linear combination there is either equality at which point division to a zero remainder is possible or there is 31 inequality In the latter case7 there is a lot of work to dothis might make a good extra topic77 by me or7 even better7 a talk by one of the students For kicks7 try out lt z 7 27y 7 z gt with leXX7y7Z ls it a Gro39bner basis for the ideal it generates What about lt y 7 272 7 x3 gt with lexyzx NOTE THE ORDEREW What about with lexxyz7 42 Computing 21 Grobner basis from scratch Given Buchberger7s S criterion above7 Buchberger7s algorithm for computing a Grobner basis is fairly straightforward ln particular7 given an ideal I lt f177fkgt3 H LetGf1fk D Set NUMNEW to 0 C40 Form all S polynomials Sgigj for all pairs of polynomials in G 4 Compute RSgigj7 G for each S polynomial Cf lncrement NUMNEW for each remainder that is nonzero and throw it into G CT lf NUMNEW is 07 then G is a Grobner basis for I Otherwise7 go to 2 Try this on x3 7 2mg and y 7 2y2 z with graded leX Remember that 7z2 was the rst remainder when dividing an S polynomial by the existing partial basis You should end up with ve generators So does this algorithm actually compute a Gro39bner basis for I77 There are really two main considerations here 7 whether it is correct and does produce a Grobner basis for I and whether is terminates on all input no in nite loops For the former7 it should be clear7 thanks to Buchberger7s S criterion above As for termination in nite time7 rst note that each trip through the loop is clearly nite 7 its the number of loops that is in question The key here is to notice that we add fewer new S polynomials each time this takes a little reasoning so that7 considering the ideal Jk of S polynomials added to G at stage k7 we end up with an ascending chain of ideals larger 32 and larger ideals Noetherian rings satisfy the ascending chain condition that all ascending chains of ideals are of nite length so we eventually stop adding more to G ie the algorithm terminates The connection between the ascending chain condition and the Hilbert Basis Theorem could also be the subject of a talk Though it rather belongs in the next section it should be noted that a Grobner basis as computed with the previous algorithm might be too big meaning that some of the generators are redundant In fact if g E G with LTG lt LTG 7 p gt then G 7 p is also a Grobner basis for I Dumping all extra generators and making all polynomials monic we are working over a eld herel we get a so called minimal Grb bner bases Unfor tunately this does not yield a unique Gro39bner basis for I Page 89 of CLOl has a nice example of this If we also require that for all polynomials g E G no monomial of g is in lt LTG 7 g gt then we get a reduced Grb bner basis These are unique up to term order 43 Some computational concerns Complexity still unknown though people have a good idea coef cient blowup nite eldsl 44 Some responses 33 Chapter 5 Solving polynomial systems exactly 34 Chapter 6 Realworld polynomial systems 61 Kinematics 62 Game theory 63 Optimal control 64 Others 35 Chapter 7 Basics of numerical methods 36 Chapter 8 Homotopy continuation zerodimensional solving 37 Chapter 9 Basic numerical algebraic geometry 38 Chapter 10 Advanced topics in numerical algebraic geometry 39 Chapter 11 Potential further topics 111 Hilbert polynomials and dimension 112 Fewnomials and bounds on the number of real solutions 113 Toric deformations 114 Tropical geometry 115 Basic convex geometry Bernstein and such 40 Appendix A Advanced topics for talks Here are a few ideas for the 20725 minute talks I am asking you to give at the end of the semester The list is not complete7 and I will generally be open to suggestions as long as they are at least tangentially connected to the material in the course Please let me know what topic you pick so that we can avoid redundancy Also7 feel free to swing by my of ce if you are having trouble deciding Solving a class of polynomial systems in various wayspackages Details about complexity of Gro39bner bases7 from MayrMeyer Faugere7s F4 and F5 algorithms rough idea Computation on elliptic curves basic or advanced Syzygies7 free resolutions7 Betti numbers de nitions and such Parallel computation of Gro39bner bases More advanced numerical methods Basic toric geometry Basic tropical geometry 0 0000A demo 41 0 Demo of that number theory package that Rachel Pries mentioned 7 one letter 0 Some other application of algebraic geometry 0 Proof of Buchberger7s criterion andor Buchberger7s algorithm as in 0101 0 Connect the ACC ascending chain condition to what we have dis cussed 42

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.