PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Gröbner basis (Definition)

Definition of monomial orderings and support:
Let $ F$ be a field, and let $ S$ be the set of monomials in $ F[x_1,\ldots,x_n]$, the polynomial ring in $ n$ indeterminates. A monomial ordering is a total ordering $ \leq$ on $ S$ which satisfies

  1. $ a \leq b$ implies that $ ac \leq bc$ for all $ a,b,c \in S$.
  2. $ 1 \leq a$ for all $ a \in S$.

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]$, we associate to $ a$ the string $ (a_1,a_2,\ldots,a_n)$ and compare monomials by looking at orderings 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 $ \operatorname{supp}(a)$, to be the set of terms $ x_i$ with $ a_i\neq 0$. Then define $ M(a)=\max(\operatorname{supp}(a))$.

A partial order on $ F[x_1,\ldots,x_n]$:
We can extend our monomial ordering to a partial ordering on $ F[x_1,\ldots,x_n]$ as follows: Let $ a,b \in F[x_1,\ldots,x_n]$. If $ \operatorname{supp}(a) \neq \operatorname{supp}(b)$, we say that $ a < b$ if $ \max(\operatorname{supp}(a)-\operatorname{supp}(b)) < \max(\operatorname{supp}(b)-\operatorname{supp}(a))$.

It can be shown that:

  1. The relation defined above is indeed a partial order on $ F[x_1,\ldots,x_n]$
  2. Every descending chain $ p_1(x_1,\ldots,x_n) > p_2(x_1,\ldots,x_n) > \ldots$ with $ p_i \in [x_1,\ldots,x_n]$ is finite.

A division algorithm for $ F[x_1,\ldots,x_n]$:
We can then formulate a division algorithm for $ F[x_1,\ldots,x_n]$:
Let $ (f_1,\ldots,f_s)$ be an ordered $ s$-tuple of polynomials, with $ f_i \in F[x_1,\ldots,x_n]$. Then for each $ f \in F[x_1,\ldots,x_n]$, there exist $ a_1,\ldots,a_s, r \in F[x_1,\ldots,x_n]$ with $ r$ unique, such that

  1. $ f=a_1f_1+\cdots+a_sf_s+r$
  2. For each $ i=1,\ldots,s$, $ M(a_i)$ does not divide any monomial in $ \operatorname{supp}(r)$.
Furthermore, if $ a_if_i \neq 0$ for some $ i$, then $ M(a_if_i) \leq M(f)$.

Definition of Gröbner basis:
Let $ I$ be a nonzero ideal of $ F[x_1,\ldots,x_n]$. A finite set $ T \subset I$ of polynomials is a Gröbner basis for $ I$ if for all $ b \in I$ with $ b \neq 0$ there exists $ p \in T$ such that $ M(p) \mid M(b)$.

Existence of Gröbner bases:
Every ideal $ I \subset k[x_1,\ldots,x_n]$ other than the zero ideal has a Gröbner basis. Additionally, any Gröbner basis for $ I$ is also a basis of $ I$.



"Gröbner basis" is owned by mathcam. [ full author list (2) ]
(view preamble)

View style:

Also defines:  monomial ordering, Gröbner basis

Cross-references: basis, zero ideal, bases, ideal, divide, polynomials, division algorithm, finite, chain, relation, terms, fixed, orderings, string, associate, implies, satisfies, 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 4526 times total.

Classification:
AMS MSC13P10 (Commutative rings and algebras :: Computational aspects of commutative algebra :: Polynomial ideals, Gröbner bases)

Pending Errata and Addenda
None.
[ View all 4 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)