Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases

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

The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
TheoremDavid A. Cox

The Extension and
Closure Theorems

Constructible Sets

References



An Example



The Closure
TheoremThe Extension
Theorem

Department of Mathematics and Computer Science
Amherst College






Prove
Extension and
ClosureTheorems

ISSAC 2007 Tutorial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

David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

ReferencesBegin Gröbner Basics
Gröbner
Bases Tutorial
David A. Cox

k – field (often algebraically closed)
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

Referencesxα = 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 theset 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem

ExamplesLex 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems

Definition
Fix a monomial order > and let f ∈ k[x] be nonzero. Writef = 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems

Division Algorithm
Given nonzero polynomials f , f1 , . . . , fs ∈ k[x] and amonomial order >, there exist r , q1 , . . . , qs ∈ k[x] with thefollowing 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
David A. Cox
Gröbner
Basics
Notation andDefinitions

Definition
Given an ideal I ⊆ k[x] and a monomial order >, the ideal ofleading terms is the monomial ideal

Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

hLT(I)i := hLT(f ) | f ∈ Ii.
If I = hf1 , . . . , fs i, thenhLT(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].

David A. Cox

Definition
Given an ideal I ⊆ k[x] a finite set G ⊆ I \ {0} is a Gröbner
basis for I under > if

Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

hLT(g) | g ∈ Gi = hLT(I)i.

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
TheoremDefinition
A Gröbner basis G is reduced if for every g ∈ G,

LT(g) divides no term of any element of G \ {g}.
LC(g) = 1.

The Closure
Theorem
An Example
Constructible Sets

References

TheoremEvery ideal has a unique reduced Gröbner basis under >.

Criteria to be a Gröbner Basis
Gröbner
Bases Tutorial
David A. Cox
Gröbner
BasicsGiven > and g, h ∈ k[x] \ {0}, we get the S-polynomialxγ
xγ
S(g, h) :=
g−
h,
LT(g)
LT(h)

xγ = lcm(LM(g), LM(h)).

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 ⇐⇒ forevery g, h ∈ G, S(g, h) has a standard representation
using G.
(LCM) G is a Gröbner basis of hGi ⇐⇒ for everyg, 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.

David A. Cox

Nullstellensatz

Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 nonconstantpolynomials.
I has a reduced Gröbner basis 6= {1}.

The Finiteness Theorem
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryGivenk[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
Theoremxα > xβ ⇒ xα yγ > xβ yδ

The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems

for all yγ , yδ .

The Extension
Theorem

ExampleThe Closure
Theorem
An Example
Constructible Sets

References

Lex with x1 > · · · > xn eliminates x = {x1 , . . . , xs } ∀s.

The Elimination Theorem
Gröbner
Bases Tutorial

Fix an ideal I ⊆ k[x, y].

David A. Cox

Definition
I ∩ k[y] is the elimination ideal of I that eliminates x.

Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

Theorem
Let G be a Gröbner basis of I for a monomial order > thateliminates x. Then G ∩ k[y] is a Gröbner basis of theelimination ideal I ∩ k[y] for the monomial order on k[y]induced by >.
Prooff ∈ 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
David A. Cox
Gröbner
BasicsGiven 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 andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
TheoremDefinition
The variety of partial solutions is

The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 theoriginal variety V := V(I) ⊆ An ?

Partial Solutions
Gröbner
Bases Tutorial
David A. Cox

Given coordinates x1 , . . . , xs , ys+1 , . . . , yn , let

Gröbner
Basicsπs : An −→ An−s

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

In A3 , consider
V = V(xy − 1, y − z).
Using lex orderwith x > y > z,
I = hxy − 1, y − zi
has Gröbner basis
xy − 1, y − z. Thus
I1 = hy − zi, so thepartial solutions are
the line y = z. The
The partial solution(0, 0) does not extend.

xy← the plane y = z

↑
↑

↓

z
↓

← the solutions← the partial
solutionsthe arrows ↑,↓indicate theprojection π1

The Extension Theorem
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryLet 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 thatThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

Referencesf = 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases

Definition
Given a subset S ⊆ An , the Zariski closure of S is thesmallest variety S ⊆ An containing S.

The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

Lemma
The Zariski closure of S ⊆ An is S = V(I(S)).
ExampleOver C, the set Zn ⊆ Cn has Zariski closure Zn = Cn .

The Closure Theorem
Gröbner
Bases Tutorial
David A. Cox

Let V = V(I) ⊆ An and let k be algebraically closed.
TheoremGröbner
BasicsV(Is ) = πs (V ).

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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−swith 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
David A. Cox
Gröbner
BasicsTraditional proofs of the Extension and Closure Theorems
use resultants or more abstract methods from algebraic
geometry.

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems

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
David A. Cox
Gröbner
Basics
Notation andDefinitions
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
Theoryf = c(y) x M + terms of degree < M in x|{z}

The Elimination
TheoremLCx (f )The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem

We setf̄ := f (x, b) ∈ k[x].

The Closure
Theorem
An Example
Constructible Sets

References

By hypothesis, there is f ∈ I with LCx (f ) 6= 0.

LemmaGröbner
Bases Tutorial

Let G be a Gröbner basis of I using > that eliminates x.

David A. Cox

Lemma

Gröbner
BasicsThere is g ∈ G with LCx (g) 6= 0.

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

Proof
Let f = ∑g∈G Ag g be a standard representation of f ∈ I with
LCx (f ) 6= 0. ThusLT(f ) = max{LT(Ag g) | Ag 6= 0}.

Since > eliminates x, it follows thatdegx (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
David A. Cox
Gröbner
Basics
Notation andDefinitions

By the lemma, we can pick g ∈ G with LCx (g) 6= 0 and
M := degx (g) minimal. Note that M = degx (ḡ) > 0.
Main Claim

Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem{f̄ | f ∈ I} = hḡi ⊆ k[x].
Consequence: If ḡ(a) = 0 for some a ∈ k, thenf (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̄ ∈ hḡi for all h ∈ G.

ClaimGröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions

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
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

Referencesh̄ = 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryLCx (g) x M−m h̄ = S = ∑`∈G A` `¯

max{degx (A` ) + degx (`)} = degx (S) < M
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
ClosureTheorems
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 (`). Hencedegx (`)¯ < deg (A` ) + deg (`) < M.
degx (A` ) + degx (`)
xx
The two strict inequalities give degx (h) − degx (h̄) ≥ 2.

Finish the Claim
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics

The inequality degx (h) − degx (h̄) ≥ 2 applies to all h ∈ Gwith degx (h) < M and hence to all ` ∈ G in S = ∑` A` `.
Arguing as before gives

Notation andDefinitions

degx (A` ) + degx (`) < degx (A` ) + degx (`) < M,

Gröbner Bases
The Consistency and
Finiteness Theorems↑

Elimination
Theorydrops by at least 2

The Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

Referencesand¯ } ≥ 3.
degx (h) − degx (h̄) ≥ min{M − (degx (A` ) + degx (`))
|
{z
}
≥3
Continuing this way, we see that h̄ = 0 for all h ∈ G withdegx (h) < M, as claimed.

Prove the Main Claim
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

Proof. For h ∈ G, we show h̄ ∈ hḡi by induction on degx (h).
Base Case: degx (h) < M implies h̄ = 0 ∈ hḡi by Claim.
Inductive Step: Assume h̄ ∈ hḡi for all h ∈ G withdegx (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` `, sodegx (S) < m ⇒ degx (`) < m ∀` in S.
By inductive hypothesis, `¯ ∈ hḡi. Hence
LCx (g) h̄ − LCx (h) xm−M¯ḡ = S = ∑`∈G A` `.

Then LCx (g) 6= 0 implies h̄ ∈ hḡi.

The Closure Theorem
Gröbner
Bases Tutorial

We next give Schauenberg’s proof of the Closure Theorem.

David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
TheoremFix 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
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

LCs (f )We setf̄ := f (x, b) ∈ k[x].

A Special Case
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions

Special Case
If b ∈ V(Is ) satisfies

Gröbner Bases

LCs (g) 6= 0 for all g ∈ G \ k[y],The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems

then b ∈ πs (V ).
Proof. If we can find a = (a1 , . . . , as ) such that ḡ(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

and b ∈ πs (V ) follows.

Prove the Special Case
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions

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
Theorywhere xγ = lcm(xα (g), xα (h) ). A standard representation
S = ∑`∈G A` ` gives

The Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

LCs (g)xγxh̄ − LCs (h)
α (h)

xγ

x

¯
S
=
A
`.
ḡ
=
∑
`
¯
`∈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 ḡ, h̄ up to a constant.

Finish the Special Case
Gröbner
Bases Tutorial
David A. Cox

S = ∑`∈GA` `¯ is a lcm representation.
¯

Gröbner
Basics

S is the S-polynomial of ḡ, h̄ up to a nonzero constant.

Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

These tell us that for everyḡ, h̄ ∈ G = {`¯ | ` ∈ G \ k[y]},the S-polynomial of ḡ, h̄ has a lcm representation withrespect to G. LCM Criterion ⇒ G is a Gröbner basis of hGi.
Since LTx (g) 6= 0 for g ∈ G \ k[y], ḡ is nonconstant for every/ḡ ∈ G. Consistency Theorem ⇒ V(G) 6= 0.
Hence there exits a such that ḡ(a) = 0 for all g ∈ G.

Saturation
Gröbner
Bases Tutorial
David A. Cox
Gröbner
BasicsFix ideals I, J ⊆ k[x].
Definition
The saturation of I with respect to J is

Notation andDefinitions

I : J ∞ := {f ∈ k[x] | J M f ⊆ I for M  0}.

Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryTo see what this means geometrically, let

The Elimination
Theorem

V := V(I)The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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

Proof. The goal is to find a variety W ⊆ V(Is ) such that
V(Is ) \ W ⊆ πs (V )David A. Cox
Gröbner
Basics
Notation andDefinitions

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
TheoryThen
V(J) =The Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 thatb ∈ 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 unionof 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
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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,54
g1 = (y − z)(x + x + 2 − yz) w + · · · 254
g2 = y(x + x + 2 − yz) w + · · ·Continue Example
Gröbner
Bases Tutorial

As in the proof of the Closure Theorem, letDavid A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryJ = 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 thatThe Elimination
TheoremV(I1 ) \ V(J) = A3 \ V(J) ⊆ π1 (V ).

The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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
David A. Cox
Gröbner
Basics
Notation andDefinitions

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
TheoryN[
i=1

Vi \ Wi ).

The Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
The Extension
Theorem
The Closure
Theorem
An Example
Constructible Sets

References

Theorem
Let k be algebraically closed and πs : An → An−s beprojection onto the last n − s coordinates. If V ⊆ An is anaffine variety, then πs (V ) ⊆ An−s is constructible.
The proof of the Closure Theorem can be adapted to givean algorithm for writing πs (V ) as a constructible set.

References
Gröbner
Bases Tutorial
David A. Cox
Gröbner
Basics
Notation andDefinitions
Gröbner Bases
The Consistency and
Finiteness Theorems

Elimination
TheoryThe Elimination
Theorem
The Extension and
Closure Theorems

Prove
Extension and
ClosureTheorems
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 andAlgorithms, Third Edition, Undergraduate Texts in
Mathematics, Springer, New York, 2007.
P. Schauenberg, A Gröbner-based treatment ofelimination theory for affine varieties, Journal of
Symbolic Computation, to appear.