Gröbner basis
Definition of monomial orderings and support:
Let be a field, and let be the set of monomials in , the polynomial ring in indeterminates.A monomial ordering is a total ordering on which satisfies
- 1.
implies that for all .
- 2.
for all .
In practice, for any , we associate to the string and compare monomials by looking at orderings
on these -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 , denoted , to be the set of terms with . Then define .
A partial order on :
We can extend our monomial ordering to a partial ordering on as follows:Let . If , we say that if .
It can be shown that:
- 1.
The relation defined above is indeed a partial order on
- 2.
Every descending chain with is finite.
A division algorithm for :
We can then formulate a division algorithm for :
Let be an ordered -tuple of polynomials, with . Then for each , there exist with unique, such that
- 1.
- 2.
For each , does not divide any monomial in .
Furthermore, if for some , then .
Definition of Gröbner basis:
Let be a nonzero ideal of . A finite set of polynomials is a Gröbner basis for if for all with there exists such that .
Existence of Gröbner bases:
Every ideal other than the zero ideal has a Gröbner basis. Additionally, any Gröbner basis for is also a basis of .