Gröbner Bases Tutorial Part I Gröbner Bases and the Geometry of Elimination

Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases Gröbner Bases Tutorial Part I: Gröbner Bases and the Geometry of Elimination The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Department of Mathematics and Computer Science 2007 Outline Gröbner Bases Tutorial 1 Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems 2 Elimination Theory The Elimination Theorem The Extension and Closure Theorems 3 Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets 4 References Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Begin Gröbner Basics Gröbner Bases Tutorial k – field (often algebraically closed) Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References xα = x1α1 · · · xnαn – monomial in x1 , . . . , xn c xα , c ∈ k – term in x1 , . . . , xn k[x] = k[x1 , . . . , xn ] – polynomial ring in n variables An = An (k) – n-dimensional affine space over k V(I) = V(f1 , . . . , fs ) ⊆ An – variety of I = hf1 , . . . , fs i I(V ) ⊆ k[x] – ideal of the variety V ⊆ An √ I = {f ∈ k[x] | ∃m f m ∈ I} – the radical of I √ Recall that I is a radical ideal if I = I. Monomial Orders Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Definition A monomial order is a total order > on the set of monomials xα satisfying: xα > xβ implies xα xγ > xβ xγ for all xγ xα > 1 for all xα 6= 1 We often think of a monomial order as a total order on the set of exponent vectors α ∈ Nn . Lemma A monomial order is a well-ordering on the set of all monomials. Examples of Monomial Orders Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem Examples Lex order with x1 > · · · > xn : xα >lex xβ iff α1 > β1 , or α1 = β1 and α2 > β2 , or . . . Weighted order using w ∈ Rn+ and lex to break ties: xα >w ,lex xβ iff w ·α > w ·β , or w ·α = w ·β and xα >lex xβ Graded lex order with x1 > · · · > xn : This is >w ,lex for w = (1, . . . , 1) The Closure Theorem An Example Constructible Sets References Weighted orders will appear in Part II when we discuss the Gröbner walk. Leading Terms Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems Definition Fix a monomial order > and let f ∈ k[x] be nonzero. Write f = c xα + terms with exponent vectors β 6= α such that c 6= 0 and xα > xβ wherever β 6= α and xβ appears in a nonzero term of f . Then: LT(f ) = c xα is the leading term of f LM(f ) = xα is the leading monomial of f LC(f ) = c is the leading coefficient of f The Extension Theorem The Closure Theorem An Example Constructible Sets References The leading term LT(f ) is sometimes called the initial term, denoted in(f ). The Division Algorithm Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems Division Algorithm Given nonzero polynomials f , f1 , . . . , fs ∈ k[x] and a monomial order >, there exist r , q1 , . . . , qs ∈ k[x] with the following properties: f = q1 f1 + · · · + qs fs + r . No term of r is divisible by any of LT(f1 ), . . . , LT(fs ). LT(f ) = max> {LT(qi ) LT(fi ) | qi 6= 0}. Definition Any representation The Extension Theorem The Closure Theorem An Example f = q1 f1 + · · · + qs fs Constructible Sets References satisfying the third bullet is a standard representation of f . The Ideal of Leading Terms Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Definition Given an ideal I ⊆ k[x] and a monomial order >, the ideal of leading terms is the monomial ideal Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References hLT(I)i := hLT(f ) | f ∈ Ii. If I = hf1 , . . . , fs i, then hLT(f1 ), . . . , LT(fs )i ⊆ hLT(I)i, though equality need not occur. This is where Gröbner bases enter the picture! Gröbner Bases Gröbner Bases Tutorial Fix a monomial order > on k[x]. Gröbner Basics Definition Given an ideal I ⊆ k[x] a finite set G ⊆ I \ {0} is a Gröbner basis for I under > if Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems hLT(g) | g ∈ Gi = hLT(I)i. Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem Definition A Gröbner basis G is reduced if for every g ∈ G, LT(g) LC(g) divides no term of any element of G \ {g}. = 1. The Closure Theorem An Example Constructible Sets References Theorem Every ideal has a unique reduced Gröbner basis under >. Criteria to be a Gröbner Basis Gröbner Bases Tutorial Gröbner Basics Given > and g, h ∈ k[x] \ {0}, we get the S-polynomial xγ xγ S(g, h) := g− h, LT(g) LT(h) xγ = lcm(LM(g), LM(h)). Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Three Criteria (SR) G ⊆ I is a Gröbner basis of I ⇐⇒ every f ∈ I has a standard representation using G. (Buchberger) G is a Gröbner basis of hGi ⇐⇒ for every g, h ∈ G, S(g, h) has a standard representation using G. (LCM) G is a Gröbner basis of hGi ⇐⇒ for every g, h ∈ G, S(g, h) = ∑`∈G A` `, where A` 6= 0 implies LT(A` `) < lcm(LM(g), LM(h)) (a lcm representation). The Consistency Theorem Gröbner Bases Tutorial Fix an ideal I ⊆ k[x], where k is algebraically closed. Nullstellensatz Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References √ (Strong) I(V(I)) = I. (Weak) V(I) = 0/ ⇐⇒ 1 ∈ I ⇐⇒ I = k[x]. The Consistency Theorem The following are equivalent: I 6= k[x]. 1∈ / I. V(I) 6= 0. / I has a Gröbner basis consisting of nonconstant polynomials. I has a reduced Gröbner basis 6= {1}. The Finiteness Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Fix an ideal I ⊆ k[x], where k is algebraically closed. Also fix a monomial order >. The Finiteness Theorem The following are equivalent: V(I) ⊆ An is finite. k[x]/I is a finite-dimensional vector space over k. I has a Gröbner basis G where ∀i, G has a element whose leading monomial is a power of xi . Only finitely many monomials are not in hLT(I)i. When these conditions are satisfied: # solutions ≤ dimk k[x]/I. Equality holds ⇐⇒ I is radical. dimk k[x]/I = # solutions counted with multiplicity. Begin Elimination Theory Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory Given k[x, y] = k[x1 , . . . , xs , ys+1 , . . . , yn ], we write monomials as xα yβ . Definition A monomial order > on k[x, y] eliminates x whenever The Elimination Theorem xα > xβ ⇒ xα yγ > xβ yδ The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References for all yγ , yδ . Example Lex with x1 > · · · > xn eliminates x = {x1 , . . . , xs } ∀s. The Elimination Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Fix an ideal I ⊆ k[x, y]. Definition I ∩ k[y] is the elimination ideal of I that eliminates x. Theorem Let G be a Gröbner basis of I for a monomial order > that eliminates x. Then G ∩ k[y] is a Gröbner basis of the elimination ideal I ∩ k[y] for the monomial order on k[y] induced by >. Proof f ∈ I ∩ k[y] has standard representation f = ∑g∈G Ag g. If Ag 6= 0, then LT(g) ≤ LT(Ag g) ≤ LT(f ) ∈ k[y], so g ∈ G ∩ k[y]. SR Criterion ⇒ G ∩ k[y] is a Gröbner basis of I ∩ k[y]. Partial Solutions Gröbner Bases Tutorial Gröbner Basics Given I ⊆ k[x, y] = k[x1 , . . . , xs , ys+1 , . . . , yn ], the elimination ideal I ∩ k[y] will be denoted Is := I ∩ k[y] ⊆ k[y]. Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem Definition The variety of partial solutions is The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References V(Is ) ⊆ An−s . Question How do the partial solutions V(Is ) ⊆ An−s relate to the original variety V := V(I) ⊆ An ? Partial Solutions Gröbner Bases Tutorial Given coordinates x1 , . . . , xs , ys+1 , . . . , yn , let Gröbner Basics πs : An −→ An−s Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References denote projection onto the last n − s coordinates. An ideal I ⊆ k[x, y] gives: V = V(I) ⊆ An and πs (V ) ⊆ An−s . Is = I ∩ k[y] ⊆ k[y] and V(Is ) ⊆ An−s . Lemma πs (V ) ⊆ V(Is ). Partial Solutions Don’t Always Extend Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References In A3 , consider V = V(xy − 1, y − z). Using lex order with x > y > z, I = hxy − 1, y − zi has Gröbner basis xy − 1, y − z. Thus I1 = hy − zi, so the partial solutions are the line y = z. The The partial solution (0, 0) does not extend. x y ← the plane y = z ↑ ↑ ↓ z ↓ ← the solutions ← the partial solutions the arrows ↑,↓ indicate the projection π1 The Extension Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory Let I ⊆ k[x, y2 , . . . , yn ] = k[x, y] with variety V = V(I) ⊆ An , and let I1 := I ∩ k[y] be the first elimination ideal. We assume that k is algebraically closed. Theorem Let b = (a2 , . . . , an ) ∈ V(I1 ) be a partial solution. If the ideal I contains a polynomial f such that The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References f = c(y)x N + terms of degree < N in x with c(b) 6= 0, then there is a ∈ k such that (a, b) = (a, a2 , . . . , an ) is a solution, i.e., (a, a2 , . . . , an ) ∈ V . Zariski Closure Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases Definition Given a subset S ⊆ An , the Zariski closure of S is the smallest variety S ⊆ An containing S. The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Lemma The Zariski closure of S ⊆ An is S = V(I(S)). Example Over C, the set Zn ⊆ Cn has Zariski closure Zn = Cn . The Closure Theorem Gröbner Bases Tutorial Let V = V(I) ⊆ An and let k be algebraically closed. Theorem Gröbner Basics V(Is ) = πs (V ). Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Thus V(Is ) is the smallest variety in An−s containing πs (V ). Furthermore, there is an affine variety W ⊆ V(Is ) ⊆ An−s with the following properties: V(Is ) \ W = V(Is ). V(Is ) \ W ⊆ πs (V ). Thus “most” partial solutions in V(Is ) come from actual solutions, i.e, the projection of V fills up “most” of V(Is ). Prove Extension and Closure Theorems Gröbner Bases Tutorial Gröbner Basics Traditional proofs of the Extension and Closure Theorems use resultants or more abstract methods from algebraic geometry. Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems Recently, Peter Schauenberg wrote “A Gröbner-based treatment of elimination theory for affine varieties” (Journal of Symbolic Computation, to appear). This paper uses Gröbner bases to give new proofs of the Extension and Closure Theorems. The Extension Theorem The Closure Theorem An Example Constructible Sets References Part I of the tutorial will conclude with these proofs. We begin with the Extension Theorem. Prove the Extension Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Fix a partial solution b = (a2 , . . . , an ) ∈ V(I1 ) ⊂ An−1 . Notation for the Proof Let f ∈ k[x, y2 , . . . , yn ] = k[x, y]. We write Elimination Theory f = c(y) x M + terms of degree < M in x |{z} The Elimination Theorem LCx (f ) The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem We set f̄ := f (x, b) ∈ k[x]. The Closure Theorem An Example Constructible Sets References By hypothesis, there is f ∈ I with LCx (f ) 6= 0. Lemma Gröbner Bases Tutorial Let G be a Gröbner basis of I using > that eliminates x. Lemma Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem There is g ∈ G with LCx (g) 6= 0. Proof Let f = ∑g∈G Ag g be a standard representation of f ∈ I with LCx (f ) 6= 0. Thus The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References LT(f ) = max{LT(Ag g) | Ag 6= 0}. Since > eliminates x, it follows that degx (f ) = max{degx (Ag g) | Ag 6= 0} LCx (f ) = ∑ degx (Ag g)=degx (f ) LCx (Ag ) LCx (g) Main Claim Gröbner Bases Tutorial Gröbner Basics Notation and Definitions By the lemma, we can pick g ∈ G with LCx (g) 6= 0 and M := degx (g) minimal. Note that M = degx (ḡ) > 0. Main Claim Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem {f̄ | f ∈ I} = hḡi ⊆ k[x]. Consequence: If ḡ(a) = 0 for some a ∈ k, then f (a, b) = f̄ (a) = 0 for all f ∈ I, so (a, b) = (a, a2 , . . . , an ) ∈ V = V(I). This proves the Extension Theorem! The Closure Theorem An Example Constructible Sets References Strategy to prove Main Claim: Show h̄ ∈ hḡi for all h ∈ G. Claim Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Consider h ∈ G with degx (h) < M = degx (g). M minimal implies LCx (h) = 0, so degx (h̄) < degx (h). Claim Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References h̄ = 0. Proof. Let m := degx (h) < M and set S := LCx (g)x M−m h − LCx (h)g ∈ I, with standard representation S = ∑`∈G A` `. Observe: LCx (g) x M−m h̄ = S = ∑`∈G A` `¯ max{degx (A` ) + degx (`) | A` 6= 0} = degx (S) < M Prove the Claim Gröbner Bases Tutorial LCx (g) x M−m h̄ = S = ∑`∈G A` `¯ max{degx (A` ) + degx (`)} = degx (S) < M Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory First bullet implies: Since LCx (g) 6= 0 and m = degx (h), ¯ M − degx (h) + degx (h̄) ≤ max{degx (A` ) + degx (`)} so that The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References ¯ degx (h) − degx (h̄) ≥ min{M − (degx (A` ) + degx (`))}. Second bullet implies: All ` ∈ G in S have degx (`) < M, so ¯ < degx (`). Hence degx (`) ¯ < deg (A` ) + deg (`) < M. degx (A` ) + degx (`) x x The two strict inequalities give degx (h) − degx (h̄) ≥ 2. Finish the Claim Gröbner Bases Tutorial The inequality degx (h) − degx (h̄) ≥ 2 applies to all h ∈ G with degx (h) < M and hence to all ` ∈ G in S = ∑` A` `. Gröbner Basics Arguing as before gives Notation and Definitions degx (A` ) + degx (`) < degx (A` ) + degx (`) < M, Gröbner Bases The Consistency and Finiteness Theorems ↑ Elimination Theory drops by at least 2 The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References and ¯ } ≥ 3. degx (h) − degx (h̄) ≥ min{M − (degx (A` ) + degx (`)) | {z } ≥3 Continuing this way, we see that h̄ = 0 for all h ∈ G with degx (h) < M, as claimed. Prove the Main Claim Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Proof. For h ∈ G, we show h̄ ∈ hḡi by induction on degx (h). Base Case: degx (h) < M implies h̄ = 0 ∈ hḡi by Claim. Inductive Step: Assume h̄ ∈ hḡi for all h ∈ G with degx (h) < m ≥ M. Take h ∈ G with degx (h) = m. Then S := LCx (g) h − LCx (h) x m−M g ∈ I has standard representation S = ∑`∈G A` `, so degx (S) < m ⇒ degx (`) < m ∀` in S. By inductive hypothesis, `¯ ∈ hḡi. Hence LCx (g) h̄ − LCx (h) x m−M ¯ ḡ = S = ∑`∈G A` `. Then LCx (g) 6= 0 implies h̄ ∈ hḡi. The Closure Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem We next give Schauenberg’s proof of the Closure Theorem. Fix a partial solution b = (as+1 , . . . , an ) ∈ V(Is ) ⊂ An−s and a Gröbner basis G of I for > that eliminates x = (x1 , . . . , xs ). Notation for the Proof Let f ∈ k[x1 , . . . , xs , ys+1 , . . . , yn ] = k[x, y]. We write The Extension and Closure Theorems f = c(y) xα (f ) + terms < xα (f ) . | {z } Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References LCs (f ) We set f̄ := f (x, b) ∈ k[x]. A Special Case Gröbner Bases Tutorial Special Case Gröbner Basics Notation and Definitions If b ∈ V(Is ) satisfies Gröbner Bases LCs (g) The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems then b ∈ πs (V ). Proof. If we can find a = (a1 , . . . , as ) such that ḡ(a) = 0 for all g ∈ G, then g(a, b) = 0 for all g ∈ G. This implies (a, b) ∈ V , The Extension Theorem The Closure Theorem An Example Constructible Sets References 6= 0 for all g ∈ G \ k[y], and b ∈ πs (V ) follows. Prove the Special Case Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Let G = {`¯ | ` ∈ G \ k[y]}. Take g, h ∈ G \ k[y] and set S := LCs (g) xγ xα (h) h − LCs (h) xγ xα (g) g Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory where xγ = lcm(xα (g), xα (h) ). A standard representation S = ∑`∈G A` ` gives The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References LCs (g) xγ x h̄ − LCs (h) α (h) xγ x ¯ ḡ = S = A `. ∑ ` ¯ `∈G α (g) Then LCs (g) 6= 0 and LCs (h) 6= 0 imply: S = ∑ ¯ A` `¯ is a lcm representation. `∈G S is the S-polynomial of ḡ, h̄ up to a constant. Finish the Special Case Gröbner Bases Tutorial S = ∑`∈G A` `¯ is a lcm representation. ¯ Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References S is the S-polynomial of ḡ, h̄ up to a nonzero constant. These tell us that for every ḡ, h̄ ∈ G = {`¯ | ` ∈ G \ k[y]}, the S-polynomial of ḡ, h̄ has a lcm representation with respect to G. LCM Criterion ⇒ G is a Gröbner basis of hGi. Since LTx (g) 6= 0 for g ∈ G \ k[y], ḡ is nonconstant for every / ḡ ∈ G. Consistency Theorem ⇒ V(G) 6= 0. Hence there exits a such that ḡ(a) = 0 for all g ∈ G. Saturation Gröbner Bases Tutorial Gröbner Basics Fix ideals I, J ⊆ k[x]. Definition The saturation of I with respect to J is Notation and Definitions I : J ∞ := {f ∈ k[x] | J M f ⊆ I for M  0}. Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory To see what this means geometrically, let The Elimination Theorem V := V(I) The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem W := V(J). Then: Lemma An Example Constructible Sets References V \ W = V(I : J ∞ ). Proof of the Closure Theorem Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Proof. The goal is to find a variety W ⊆ V(Is ) such that V(Is ) \ W ⊆ πs (V ) Let G be a reduced Gröbner basis of I that eliminates x. Set J := Is + ∏g∈G\k [y] LCs (g) . Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory Then V(J) = The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References and V(Is ) \ W = V(Is ). [ g∈G\k [y] V(Is ) ∩ V(LCs (g)). Notice that b ∈ V(Is ) \ V(J) ⇒ LCs (g) 6= 0 ∀g ∈ G \ k[y]. By Special Case, b ∈ πs (V ). Hence V(Is ) \ V(J) ⊆ πs (V ). Two Cases Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Case 1. V(Is ) \ V(LCs (g)) = V(Is ) for all g ∈ G \ k[y]. Intersecting finitely many open dense sets is dense, so V(Is ) \ V(J) = T g∈G\k [y] V(Is ) \ V(LCs (g)) = V(Is ). Thus the theorem holds with W = V(J). Case 2. V(Is ) \ V(LCs (g)) ( V(Is ) for some g ∈ G \ k[y]. The strategy will be to enlarge I. First suppose that V(Is ) ⊆ V(LCs (g)). Then: LCs (g) vanishes on V(Is ) and √ hence on V . Hence Nullstellensatz ⇒ LCs (g) ∈ I. G reduced ⇒ LCs (g) ∈ / I (since LT(LCs (g)) divides LT(g)). Finish the Proof Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Together, these bullets imply that I ( I + hLCs (g)i ⊂ √ I, so in particular, V(I) = V(I + hLCs (g)i). So it suffices to prove the theorem for I + hLCs (g)i when V(Is ) ⊆ V(LCs (g)). On the other hand, when V(Is ) * V(LCs (g)), we have a union of proper subsets V(Is ) = V(Is ) \ V(LCs (g)) ∪ (V(Is ) ∩ V(hLCs (g)i)) = V(Is : LCs (g)∞ ) ∪ V(Is + hLCs (g)i) Hence it suffices to prove the theorem for I ( I + hIs : LCs (g)∞ i and I ( I + hLCs (g)i. ACC ⇒ these enlargements occur only finitely often. Example Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Consider A4 with variables w , x, y, z. Let π1 : A4 → A3 be projection onto the last three coordinates. Set f = x 5 + x 4 + 2 − yz and I = h(y − z)(fw − 1), (yw − 1)(fw − 1)i. This defines V := V(I) = V(y − z, yw − 1)∪ V((x 5 + x 4 + 2 − yz)w − 1) ⊆ A4 . Then: {g1 , g2 } = {(y − z)(fw − 1), (yw − 1)(fw − 1)} is a Gröbner basis of I for lex with w > x > y > z. I1 = 0. Furthermore,
5 4 g1 = (y − z)(x + x + 2 − yz) w + · · ·
2 5 4 g2 = y(x + x + 2 − yz) w + · · · Continue Example Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory As in the proof of the Closure Theorem, let J = I1 + ∏g∈G\k [x,y ,z] LC1 (g) = h(y − z)(x 5 + x 4 + 2 − yz) · y(x 5 + x 4 + 2 − yz)i = hy(y − z)(x 5 + x 4 + 2 − yz)2 i. This satisfies Case 1 of the proof, so that The Elimination Theorem V(I1 ) \ V(J) = A3 \ V(J) ⊆ π1 (V ). The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References However,
π1 (V ) = A \ V(x + x + 2 − yz) ∪ 3 5 4
V(y − z, x + x + 2 − yz) \ V(x + x + 2, y, z) . 5 4 5 4 Constructible Sets Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Definition A set S ⊆ An is constructible if there are affine varieties Wi ⊆ Vi ⊆ An , i = 1, . . . , N, such that Gröbner Bases The Consistency and Finiteness Theorems S= Elimination Theory N [ i=1 Vi \ Wi ). The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References Theorem Let k be algebraically closed and πs : An → An−s be projection onto the last n − s coordinates. If V ⊆ An is an affine variety, then πs (V ) ⊆ An−s is constructible. The proof of the Closure Theorem can be adapted to give an algorithm for writing πs (V ) as a constructible set. References Gröbner Bases Tutorial Gröbner Basics Notation and Definitions Gröbner Bases The Consistency and Finiteness Theorems Elimination Theory The Elimination Theorem The Extension and Closure Theorems Prove Extension and Closure Theorems The Extension Theorem The Closure Theorem An Example Constructible Sets References T. Becker, V. Weispfenning, Gröbner Bases, Graduate Texts in Mathematics 141, Springer, New York, 1993. D. Cox, J. Little, D. O’Shea, Ideals, Varieties and Algorithms, Third Edition, Undergraduate Texts in Mathematics, Springer, New York, 2007. P. Schauenberg, A Gröbner-based treatment of elimination theory for affine varieties, Journal of Symbolic Computation, to appear.