|
|
|
|
Gröbner basis
|
(Definition)
|
|
|
Definition of monomial orderings and support:
Let  be a field, and let  be the set of monomials in
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img3.png "$ F[x_1,\ldots,x_n]$") , the polynomial ring in  indeterminates. A monomial ordering is a total ordering  on  which satisfies
 implies that
 for all
 . for all  .
In practice, for any
![$ a=x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n} \in F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img12.png "$ a=x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n} \in F[x_1,\ldots,x_n]$") , 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
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img21.png "$ F[x_1,\ldots,x_n]$") :
We can extend our monomial ordering to a partial ordering on
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img22.png "$ F[x_1,\ldots,x_n]$") as follows: Let
![$ a,b \in F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img23.png "$ a,b \in F[x_1,\ldots,x_n]$") . If
 , we say that  if
 .
It can be shown that:
- The relation defined above is indeed a partial order on
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img27.png "$ F[x_1,\ldots,x_n]$")
- Every descending chain
 with
![$ p_i \in [x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img29.png "$ p_i \in [x_1,\ldots,x_n]$") is finite.
A division algorithm for
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img30.png "$ F[x_1,\ldots,x_n]$") :
We can then formulate a division algorithm for
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img31.png "$ F[x_1,\ldots,x_n]$") :
Let
 be an ordered  -tuple of polynomials, with
![$ f_i \in F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img34.png "$ f_i \in F[x_1,\ldots,x_n]$") . Then for each
![$ f \in F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img35.png "$ f \in F[x_1,\ldots,x_n]$") , there exist
![$ a_1,\ldots,a_s, r \in F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img36.png "$ a_1,\ldots,a_s, r \in F[x_1,\ldots,x_n]$") with  unique, such that
-
- For each
 ,  does not divide any monomial in
 .
Furthermore, if
 for some  , then
 .
Definition of Gröbner basis:
Let  be a nonzero ideal of
![$ F[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img46.png "$ F[x_1,\ldots,x_n]$") . 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
![$ I \subset k[x_1,\ldots,x_n]$](http://images.planetmath.org:8080/cache/objects/3470/l2h/img53.png "$ I \subset k[x_1,\ldots,x_n]$") other than the zero ideal has a Gröbner basis. Additionally, any Gröbner basis for  is also a basis of  .
|
"Gröbner basis" is owned by mathcam. [ full author list (2) ]
|
|
(view preamble)
| Also defines: |
monomial ordering, Gröbner basis |
|
|
Cross-references: basis, zero ideal, bases, finite set, ideal, divide, polynomials, division algorithm, finite, chain, relation, terms, fixed, lexicographic ordering, orderings, string, associate, implies, total ordering, indeterminates, polynomial ring, monomials, field, support
There are 4 references to this entry.
This is version 25 of Gröbner basis, born on 2002-09-23, modified 2006-10-04.
Object id is 3470, canonical name is GrobnerBasis.
Accessed 6105 times total.
Classification:
| AMS MSC: | 13P10 (Commutative rings and algebras :: Computational aspects of commutative algebra :: Polynomial ideals, Gröbner bases) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
