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