Unformatted text preview:

6 859 15 083 Integer Programming and Combinatorial Optimization Lecture 14 Algebraic Geometry I Today 0 1 integer programming and systems of polynomial equations The division algorithm for polynomials of one variable Multivariate polynomials Ideals and a ne varieties A division algorithm for multivariate polynomials Dickson s Lemma for monomial ideals Hilbert Basis Theorem Gro bner bases 0 1 Integer Programming Feasibility Normally n aij xj bi i 1 m j 1 xj 0 1 j 1 n aij xj bi 0 i 1 m x2j xj 0 j 1 n Equivalently n j 1 Motivates study of systems of polynomial equations Refresher Polynomials of One Variable Some basics Let f a0 xm a1 xm 1 am where a0 0 We call m the degree of f written m deg f We say a0 xm is the leading term of f written LT f a0 xm For example if f 2x3 4x 3 then deg f 3 and LT f 2x3 1 Fall 2009 If f and g are nonzero polynomials then deg f deg g LT f divides LT g The Division Algorithm In g f Out q r such that f q g r and r 0 or deg r deg g 1 q 0 r f 2 WHILE r 0 AND LT g divides LT r DO 3 q q LT r LT g 4 r r LT r LT g g Polynomials of More than One Variable Fields A eld consists of a set k and two binary operations and which satisfy the following conditions a b c a b c and a b c a b c a b b a and a b b a a b c a b a c there are 0 1 k such that a 0 a 1 a given a k there is b k such that a b 0 given a k a 0 there is c k such that a c 1 Examples include Q R and C Monomials A monomial in x1 xn is a product of the form x 1 1 x 2 2 x nn with 1 n Z We also let 1 n and set x x 1 1 x 2 2 x nn The total degree of x is 1 n Polynomials 2 A polynomial in x1 xn is a nite linear combination of monomials f a x S where a k for all S and S Zn is nite The set of all polynomials in x1 xn with coe cients in k is denoted by k x1 xn We call a the coe cient of the monomial x If a 0 then a x is a term of f The total degree of f deg f is the maximum such that a 0 Example f 2x3 y 2 z 32 y 3 z 3 3xyz y 2 Four terms total degree six Two terms of max total degree which cannot happen in one variable What is the leading term Orderings on the Monomials in k x1 xn For the division algorithm on polynomials in one variable xm 1 xm x2 x 1 In Gaussian elimination for systems of linear equations x1 x2 xn Note that there is a one to one correspondence between the monomials in k x1 xn and Zn A monomial ordering on k x1 xn is any relation on Zn that satis es 1 is a total ordering 2 if and Zn then 3 every nonempty subset of Zn has a smallest element under Examples of Monomial Orderings Lex Order For Zn lex if the left most nonzero entry of is positive We write x lex x if lex For example 1 2 0 lex 0 3 4 and 3 2 4 lex 3 2 1 Also x1 lex x52 x33 Graded Lex Order For Zn grlex if or and lex For example 1 2 3 grlex 3 2 0 and 1 2 4 grlex 1 1 5 3 Further De nitions Let f a x be a nonzero polynomial in k x1 xn and let be a monomial order The multidegree of f is 0 multideg f max Zn a The leading coe cient of f is LC f amultideg f The leading monomial of f is LM f xmultideg f The leading term of f is LT f LC f LM f Example Let f 4xy 2 z 4z 2 5x3 7x2 z 2 and let denote the lex order Then multideg f 3 0 0 LC f 5 LM f x3 LT f 5x3 The Basic Algebraic Object of this Lecture A subset I k x1 xn is an ideal if it satis es 1 0 I 2 if f g I then f g I 3 if f I and h k x1 xn then h f I Let f1 fs k x1 xn Then f1 fs s hi fi h1 hs k x1 xn i 1 is an ideal of k x1 xn We call it the ideal generated by f1 fs An ideal I is nitely generated if I f1 fs and we say that f1 fs are a basis of I 4 Polynomial Equations Given f1 fs k x1 xn we get the system of equations f1 0 fs 0 If we multiply the rst equation by h1 the second one by h2 and so on we obtain h1 f1 h2 f2 hs fs 0 which is a consequence of the original system Thus we can think of f1 fs as consisting of all polynomial consequences of f1 f2 fs 0 Let f1 fs k x1 xn Then we set V f1 fs a1 an k n fi a1 an 0 i 1 s and call V f1 fs an a ne variety If f1 fs g1 gt then V f1 fs V g1 gt Let V kn be an a ne variety Then we set I V f k x1 xn f a1 an 0 for all a1 an V If V is an a ne variety then I V is an ideal Driving Questions Does every ideal have a nite generating set Given f k x1 xn and I f1 fs is f I Find all solutions in k n of a system of polynomial equations f1 x1 xn fs x1 xn 0 Find a nice basis for f1 fs A Division Algorithm in k x1 xn Goal Divide f by f1 fs Example 1 Divide f xy 2 1 by f1 xy 1 and f2 y 1 using lex order with x y This leads to xy 2 1 y xy 1 1 y 1 2 Example 2a Divide f x2 y xy 2 y 2 by f1 xy 1 and f2 y 2 1 using lex order with x y This eventually leads to x2 y xy 2 y 2 x y xy 1 1 y 2 1 x y 1 5 Theorem 1 Fix a monomial order on Zn and let f1 fs be an ordered tuple of polynomials in k x1 xn Then every f k x1 xn can be written as f a1 as fs r where ai r k x1 xn and …


View Full Document

MIT 15 083J - Lec

Download Lec
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lec and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lec 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?