Gröbner basis

Definition of monomial orderings and supportPlanetmathPlanetmath:
Let F be a field, and let S be the set of monomials in F[x1,,xn], the polynomial ring in n indeterminates. A monomial ordering is a total ordering on S which satisfies

  1. 1.

    ab implies that acbc for all a,b,cS.

  2. 2.

    1a for all aS.

In practice, for any a=x1a1x2a2xnanF[x1,,xn], we associateMathworldPlanetmath to a the string (a1,a2,,an) and compare monomials by looking at orderingsMathworldPlanetmath on these n-tuples.

Example. An extremely prevalent example of a monomial ordering is given by the standard lexicographical ordering of strings. Other examples include graded lexicographic ordering and graded reverse lexicographic ordering.

Henceforth, assume that we have fixed a monomial ordering. Define the support of a, denoted supp(a), to be the set of terms xi with ai0. Then define M(a)=max(supp(a)).

A partial order on F[x1,,xn]:
We can extend our monomial ordering to a partial ordering on F[x1,,xn] as follows: Let a,bF[x1,,xn]. If supp(a)supp(b), we say that a<b if max(supp(a)-supp(b))<max(supp(b)-supp(a)).

It can be shown that:

  1. 1.

    The relation defined above is indeed a partial order on F[x1,,xn]

  2. 2.

    Every descending chain p1(x1,,xn)>p2(x1,,xn)> with pi[x1,,xn] is finite.

A division algorithmPlanetmathPlanetmath for F[x1,,xn]:
We can then formulate a division algorithm for F[x1,,xn]:
Let (f1,,fs) be an ordered s-tuple of polynomials, with fiF[x1,,xn]. Then for each fF[x1,,xn], there exist a1,,as,rF[x1,,xn] with r unique, such that

  1. 1.


  2. 2.

    For each i=1,,s, M(ai) does not divide any monomial in supp(r).

Furthermore, if aifi0 for some i, then M(aifi)M(f).

Definition of Gröbner basis:
Let I be a nonzero ideal of F[x1,,xn]. A finite set TI of polynomials is a Gröbner basis for I if for all bI with b0 there exists pT such that M(p)M(b).

Existence of Gröbner bases:
Every ideal Ik[x1,,xn] other than the zero idealMathworldPlanetmathPlanetmath has a Gröbner basis. Additionally, any Gröbner basis for I is also a basis of I.

Title Gröbner basis
Canonical name GrobnerBasis
Date of creation 2013-03-22 13:03:47
Last modified on 2013-03-22 13:03:47
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 28
Author mathcam (2727)
Entry type Definition
Classification msc 13P10
Defines monomial ordering
Defines Gröbner basis