advanced34 min studyLesson 559 in Mathematics

Gröbner bases and elimination

Choose an elimination order, compute polynomial consequences, and distinguish the closed elimination variety from the actual constructible projection.

Before you begin

On this page

The question for today

What you’ll understand

Explain how a Gröbner basis turns ideal membership into a remainder test.
Apply the elimination theorem with an explicit variable order.
Compute a projection closure and identify points not reached by the original system.

Eliminating variables should preserve every polynomial consequence involving the variables that remain. A Gröbner basis makes that goal algorithmic once a monomial order is fixed. The resulting equations describe a closed algebraic set, but projection of an affine set need not be closed. A reliable elimination calculation therefore has two separate outputs: the equations of the projection's closure and the additional information needed to decide which points actually lift.

Leading monomials depend on the chosen order

A monomial order is a multiplicative well-order with one as the smallest monomial. It selects a leading monomial for each nonzero polynomial and makes multivariable division terminate. A Gröbner basis G of an ideal I is a finite subset whose leading monomials generate the ideal of all leading monomials from I. Division by an arbitrary generating list can leave a nonzero remainder even for an ideal member. Division by a Gröbner basis has zero remainder exactly for membership, with a unique normal form when the basis is reduced.

Buchberger's criterion tests the overlaps between leading terms through S-polynomials. If every such polynomial reduces to zero, the basis is Gröbner for the specified order. Appending nonzero remainders enlarges the leading-monomial ideal until Noetherianity forces termination. This is a symbolic exact-arithmetic statement, not a promise that the computation will be small. Degrees and coefficient sizes can grow sharply, and rounding coefficients can change cancellations. An answer labelled simply Gröbner basis without its coefficient field and monomial order omits essential information.

G\text{ Gröbner for }I\quad\Longleftrightarrow\quad\langle\operatorname{LM}(g):g\in G\rangle=\langle\operatorname{LM}(f):f\in I\rangle

Leading monomials are taken in one fixed monomial order. The equality is of monomial ideals.↔ Scroll wide equations horizontally.

Put the variables to be removed first

For lexicographic order x₁ greater than x₂ and so on, a Gröbner basis G has the elimination property: its members involving only the last variables form a Gröbner basis for the corresponding intersection of I with their polynomial ring. To eliminate x from k[x,y], therefore choose lex order x greater than y, not the reverse. Other block elimination orders work too, but a generic graded order does not automatically provide this particular intersection by merely discarding polynomials containing x.

The mechanism is visible in leading terms. If a polynomial in the elimination ideal involves only retained variables, its leading monomial must be divisible by a leading monomial from G. Under the elimination order that basis polynomial cannot hide a removed variable in a lower term. It therefore belongs to the retained-variable subring and can reduce the polynomial there. The theorem is valid over any field; identifying the variety of the elimination ideal with a point-projection closure uses the algebraically closed setting of this module.

I_1=I\cap k[x_2,\ldots,x_n],\qquad G_1=G\cap k[x_2,\ldots,x_n],\qquad \overline{\pi(V(I))}=V(I_1)

G uses lex x₁>⋯>xₙ, π forgets x₁, and the closure identity concerns k-valued points over an algebraically closed field.↔ Scroll wide equations horizontally.

Closure can add nonlifting points

An elimination polynomial is a necessary equation for a projected point, but its solutions need not all extend to solutions of the full system. The hyperbola xy=1 projects to every nonzero x and omits zero. Yet no nonzero polynomial in x vanishes on all nonzero scalars over an infinite field, so its elimination ideal is zero and its closed projection variety is the entire affine line. The added point is not a symbolic-computation error; closed equations cannot describe a puncture by themselves.

Chevalley's theorem gives the correct general type of image: a finite-type morphism has constructible image, a finite union of locally closed sets. Constructible does not mean closed, and dominant does not mean surjective. A dense constructible subset of an irreducible variety contains a nonempty open subset, but can still omit a closed locus. To determine exact images one can split into denominator or leading-coefficient cases, retaining nonvanishing conditions alongside equations. Finite morphisms provide an important special case where images of closed sets are closed.

Work it through

Lexicographic elimination with two solutions

Over characteristic zero, solve $I=(x+y-1,xy+2)\subset k[x,y]$ using lex order x>y. Give a Gröbner basis and verify that every eliminated solution lifts.

Use x+y−1 to write x=1−y. Substitution in xy+2 gives y−y²+2, so the same ideal is generated by g₁=x+y−1 and g₂=y²−y−2.
Their leading monomials are x and y², which are relatively prime. Buchberger's product criterion, or direct reduction of their S-polynomial, shows these two monic polynomials form a Gröbner basis for lex x>y. The elimination ideal in k[y] is generated by g₂.
Factor g₂=(y−2)(y+1). For y=2 the first equation gives x=−1; for y=−1 it gives x=2. Both points satisfy xy+2=0, so no extra closure points occur in this example. The inverse substitution uniquely lifts each retained value.

The result

The reduced lex basis is {x+y−1, y²−y−2}, and the solution set is {(-1,2),(2,−1)}. The chosen order eliminates x.

The living notebook

Explore the model

Interactive lab

Interactive lab · root-finding

A numerical branch after symbolic elimination

Pause and Reset, then set target c = 2.25 and upper bound U = 3. One Step tests z=1.5 and collapses the bracket. Completing the square in y²−y−2 gives z²=2.25 with z=y−0.5, so predict the displayed positive branch yields y=2 and x=−1. The second algebraic solution uses z=−1.5, outside this positive-root instrument. Reset and set both c = 2.25 and U = 4 for a fresh bracket comparison. This is a quadratic bisection model, not a Gröbner-basis or complex-root solver.

Quadratic / midpointCurrent bracketPositive root

Midpoint after 0 refinements: 1.5
Bracket error bound: 1.5
Computed residual · x² − c: 0.25

Target c2Initial upper bound U3

t = 0 s

Bisection of x² − c on [0,U], capped at 50 iterations for floating-point resolution. The error bound is the maximum distance from the displayed midpoint to either bracket endpoint (half the width in exact arithmetic). Compensated square evaluation preserves the bracket when ordinary multiplication rounds a residual to zero. A truly exact endpoint or midpoint collapses the bracket. This is one monotone quadratic, not a general root solver. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA numerical root branch can inspect an eliminated equation while missing other algebraic solutions.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

The image is k without zero, a dense constructible set. Its closure is all of the affine line, defined by the zero ideal; elimination alone does not certify that zero lifts.

Your turn

Try it yourself

Use lex order y>x for H=(xy−1). Identify a Gröbner basis, H∩k[x], the exact x-projection, and its closure. Explain how a nonvanishing condition recovers the exact image.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

A single nonzero polynomial is a Gröbner basis for its principal ideal. Can any nonzero polynomial in x vanish at every nonzero scalar?

Compare with the solution

The singleton {xy−1} is a Gröbner basis, with leading monomial xy under lex y>x. It has no member in k[x], so the elimination basis is empty and H∩k[x]=(0). Directly, x can be any nonzero scalar, with unique y=1/x, while x=0 makes the equation impossible. The image is therefore D(x), and its closure is all of A¹. The equation-free condition together with x≠0 describes the exact constructible image. The nonvanishing information cannot be recovered from the zero elimination ideal alone, although it is immediate from the original relation.

Keep the idea

Take it with you

A Gröbner basis and its normal forms depend on a specified monomial order and field.
An elimination order makes a retained-variable subset a basis for the elimination ideal.
Elimination equations describe the closed projection closure; actual images can require inequalities.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.