6.859/15.083 Integer Programming and Combinatorial Optimization Fall 2009 Lecture 15: Algebraic Geometry II Today... • Ideals in k[x] • Properties of Gr¨obner bases • Buchberger’s algorithm • Elimination theory The Weak Nullstellensatz • • 0/1-Integer Programming The Structure of Ideals in k[x] Theorem 1. If k is a field, then every ideal of k[x] is of the form �f � for some f ∈ k[x]. Moreover, f is unique up to multiplication by a nonzero constant in k. Proof: • If I = {0}, then I So assume I �= �0�. = {0}. • Let f be a nonzero polynomial of minimum degree in I. Claim: �f� = I. • Clearly, �f� ⊆ I. Let g ∈ I be arbitrary. • The division algorithm yields g = q f + r, where either r = 0 or deg(r) < deg(f ). • I is an ideal, so q f ∈ I, and, thus, r = g − q f ∈ I. • By the choice of f, r = 0. • But then g = q f ∈ �f �. Reminder: Gr¨obner Bases • Fix a monomial order. A subset {g1, . . . , gs} of an ideal I is a Gr¨obner basis of I if �LT(g1), . . . , LT(gs)� = �LT(I)�. • Equivalently, {g1, . . . , gs} ⊆ I is a Gr¨obner basis of I iff the leading term of any element in I is divisible by one of the LT(gi). 1Properties of Gr¨obner Bases I Theorem 2. Let G = {g1, . . . , gs} be a Gr¨obner basis for an ideal I, and let f ∈ k[x1, . . . , xn]. Then the remainder r on division of f by G is unique, no matter how the elements of G are listed when using the division algorithm. Proof: • First, recall the following result: Let I = �xα : α ∈ A� be a monomial ideal. Then a monomial xβ lies in I iff xβ is divisible by xα for some α ∈ A. Suppose f = a1g1 + + a�+ r� with r = r�.• · · · + asgs + r = a�1g1 + · · · sgs �• Then r − r� ∈ I and, thus, LT(r − r�) ∈ �LT(I)� = �LT(g1), . . . , LT(gs)�. • The lemma implies that LT(r − r�) is divisible by one of LT(g1), . . . , LT(gs). • This is impossible since no term of r, r� is divisible by one of LT(g1), . . . , LT(gs). S-Polynomials • Let I = �f1, . . . , ft�. • We show that, in general, �LT(I)� can be strictly larger than �LT(f1), . . . , LT(ft)�. • Consider I = �f1, f2�, where f1 = x3 − 2xy and f2 = x2y − 2y2 + x with grlex order. Note that • x (x 2 y − 2y 2 + x) − y (x 3 − 2xy) = x 2 ,· · so x2 ∈ I. Thus x2 = LT(x2) ∈ �LT(I)�. • However, x2 is not divisible by LT(f1) = x3 or LT(f2) = x2y, so that x2 �∈ �LT(f1), LT(f2)�. • What happened? • The leading terms in a suitable combination ax αfi − bxβ fj may cancel, leaving only smaller terms. • On the other hand, axαfi − bxβ fj ∈ I, so its leading term is in �LT(I)�. • This is an “obstruction” to {f1, . . . , ft} being a Gr¨obner basis. • Let f, g ∈ k[x1, . . . , xn] be nonzero polynomials with multideg(f) = α and multideg(g) = β. • Let γi = max(αi, βi). We call xγ the least common multiple of LM(f) and LM(g). • The S-polynomial of f and g is defined as γ γx xS(f, g) = LT(f) · f − LT(g) · g. 2�� �� � � • An S-polynomial is designed to produce cancellation of leading terms. Example: • Let f = x3y2 − x2y3 + x and g = 3x4y + y2 with the grlex order. • Then γ = (4, 2). • Moreover, 4 2 4 2 S(f, g) = xx3yy2 · f − 3xxy4y · g 1 = x y g· f − 3· 1 = −x 3 y 3 + x 2 − 3y 3 • Consider it =1 cifi, where ci ∈ k and multideg(fi) = δ ∈ Z+ n for all i. • If multideg( it =1 cifi) < δ, then it =1 cifi is a linear combination, with coefficients in k, of the S-polynomials S(fj , fk) for 1 ≤ j, k ≤ t. • Moreover, each S(fj , fk) has multidegree < δ. tcifi = cjkS(fj , fk) i=1 j,k Properties of Gr¨obner Bases II Theorem 3. A basis G = {g1, . . . , gs} for an ideal I is a Gr¨obner basis iff for all pairs i =� j, the remainder on division of S(gi, gj ) by G is zero. Sketch of proof: • Let f ∈ I be a nonzero polynomial. There are polynomials hi such that f = s higi.i=1 • It follows that multideg(f) ≤ max(multideg(higi)). • If “<”, then some cancellation of leading terms must occur. • These can be rewritten as S-polynomials. • The assumption allows us to replace S-polynomials by expressions that involve less cancella-tion. • We eventually find an expression for f such that multideg(f) = multideg(higi) for some i. • It follows that LT(f) is divisible by LT(gi). • This shows that LT(f) ∈ �LT(g1), . . . , LT(gs)�. 3Buchberger’s Algorithm • Consider I = �f1, f2�, where f1 = x3 − 2xy and f2 = x2y − 2y2 + x with grlex order. Let F = (f1, f2). • S(f1, f2) = −x2; its remainder on division by F is −x2 . • Add f3 = −x2 to the generating set F . • S(f1, f3) = −2xy; its remainder on division by F is −2xy. • Add f4 = −2xy to the generating set F . • S(f1, f4) = −2xy2; its remainder on division by F is 0. • S(f2, f3) = −2y2 + x; its remainder is −2y2 + x. • Add f5 = −2y2 + x to the generating set F . • The resulting set F satisfies the “S-pair criterion,” so it is a Gr¨obner basis. Buchberger’s Algorithm The algorithm: In: F = (f1, . . . , ft) {defining I = �f1, . . . , ft�} Out: Gr¨obner basis G = (g1, . . . , gs) for I, with F ⊆ G 1. G := F 2. REPEAT 3. G� := G 4. FOR each pair p =� q in G� DO 5. S := remainder of S(p, q) on division by G� 6. IF S = 0 THEN � G := G ∪ {S} 7. UNTIL G = G� Buchberger’s Algorithm Proof of correctness: • The algorithm terminates when G = G�, which means that G satisfies the S-pair criterion. Proof of finiteness: • The ideals �LT(G�)� from successive iterations form an ascending chain. 4• Let us call …