y-x^{2}=0

z-x^{3}=0

that are satisfied by some points (x,y,z), one might ask what other equations are implied by these? For example, if we multiply these equations by some other arbitrary polynomials and add them together, such as

(ya new equation.^{2}+x^{2}y +x^{4}) (y-x^{2}= 0 )

+ (-z-x^{3}) (z-x^{3}= 0 )

gives

y^{3}-z^{2}= 0

One says in this situation that y^{3}-z^{2} lies in
the **ideal** generated by y-x^{2}, z-x^{3} in the
set R[x,y,z]. Here R[x,y,z] is just the set of all polynomials in
x,y,z with real coefficients. In other words,
y^{3}-x^{2} is a linear combination of y-x^{2}
and z-x^{3} using arbitrary polynomials as coefficients. If
(x,y,z) is a point satisfying y-x^{2}=0, z-x^{3}=0,
then any other element g(x,y,z) in the ideal generated by
y-x^{2}, z-x^{3} gives another valid equation
g(x,y,z)=0 satisfied by (x,y,z).

In various contexts, one might not like the generators for the ideal that were given to us by a system of polynomial equations, and would prefer to "trade them in" for generators of the same ideal that have some better form. For example, this is what one wants to do when one wishes to eliminate the variable x from the above equations, i.e. one is trying to find the elements of the ideal that do not involve x. This is something that Gröbner bases allow us to do.

A **Gröbner basis** for an ideal I is a set of generators for
I having a certain property with respect to an ordering < on the
monomials, but we first need to explain what a monomial ordering is.
A **monomial ordering** is a total ordering < of all the
monomials {1, x, y, z, x^{2}, y^{2}, z^{2},
xy, xz, yz, x^{3}, ...}, which means that it is a binary
relation that allows one to compare any two monomials m, m' and
decide whether either m < m' or m > m'. In order to be a
monomial ordering, the total ordering < is
also required to have two other properties:

- The monomial 1 is smaller than any other monomial m.
- Given any three monomials m, m', m'' with m' < m'' we can conclude that m m' < m m''.

An example of such an order is the "lexicographic order" based on x > y > z. This ordering says that to compare two monomials m, m' we first see if one of them has smaller power of x and say this monomial is smaller in < if so. If they have same power of x, see if one has smaller power of y, and then this one is smaller in <. If they have same power of x and y, the one with smaller power of z is smaller in <. Here is part of the lexicographic order on monomials in R[x,y,z] based on x > y > z:

1 < z < z^{2} < ... <
y < yz < yz^{2} < ... <
y^{2} < y^{2}z <
y^{2}z^{2} < ...
< x < xz <...

For a given monomial order <, any polynomial f will have a unique
term whose monomial is largest in the < order, called the <-leading term
of f (NB: we are ignoring the coefficient in front of each
term to obtain a monomial, e.g. a term like -5 x y ^{3}
has monomial x y^{3}). If I is the ideal generated by polynomials f_{1},
f_{2}, ..., f_{r} then we say
{f_{1}, f_{2}, ..., f_{r}}
forms a Gröbner
basis for I if any polynomial f in I has its <-leading term
divisible by the <-leading term of some f_{i}.

For example, if we use the lexicographic order based x > y > z,
then f_{1} = y-x^{2}, f_{2}= z - x^{3}
do NOT form a Gröbner basis for their ideal, since f=
y^{3}-z^{2} has <-leading term y^{3}, which is
not divisible by either the <-leading term of f_{1} (which is
x^{2}) or the <-leading term of f_{2} (which is
x^{3}). On the other hand, there is an algorithm due to
Buchberger for computing the Gröbner basis of the ideal generated
by polynomials {f_{1},f_{2},...,f_{r}} with
respect to any monomial orderings, and we can apply this for
lexicographic orderings in Maple by using the "gbasis" command and
specify the monomial ordering to be "plex":

> with(grobner); [finduni, finite, gbasis, gsolve, leadmon, normalf, solvable, spoly] > gbasis({y-x^2,z-x^3},[x,y,z],plex); 2 2 2 3 [- y + x , - z + x y, - y + x z, - z + y ]Notice that the output Gröbner basis contains the element f=y

FACT: Let {f_{1},...,f_{r}}
be polynomials in the variables x_{1},...,x_{n}
and compute a Gröbner basis for their ideal I with respect
to the lexicographic monomial order based on
x_{1} > x_{2} > ... > x_{n}.
Then any polynomial f in I that does not involve
x_{1},..., x_{k-1}
is in the ideal generated by those elements of the Gröbner basis
that do not involve x_{1},...,x_{k-1}.

In other words, the latter subset of the Gröbner basis generates
all the polynomials one can obtain from f_{1},...,f_{r}
by elimination of the variables
x_{1},...,x_{k-1}.

We should point out that there is a more classical alternative
to using Gröbner bases for eliminating variables in polynomial
equations. This technique uses **resultants**, which one can
read about in Cox, Little, and O'Shea Sections 3.5 and 3.6.

Elimination of variables also has a very simple geometric intepretation related to projections. For an explanation, see Projections, profiles, and envelopes

Vic Reiner <reiner@math.umn.edu> Frederick J. Wicklin <fjw@geom.umn.edu> Last modified: Thu May 2 10:43:36 1996