Back to the index. Or to the chambers

This article has 19 links. View as Cloud or List.

Partial Order Fix Ideal Polynomial Ring Finite Language Relation Theory Implication Field Basic Polynomial Total Order Indeterminate Basis Topological Space Archimedean Semigroup Prismatoid Associates Product Of Posets Support Division Algorithm For Integers

Loading ...

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

Grobner Basis

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

$a \leq b$ implies that $ac \leq bc$ for all $a,b,c \in S$ .
$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 the string $(a_1,a_2,\ldots,a_n)$ 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 $\operatorname{supp}(a)$ , to be the set of terms 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 if $\max(\operatorname{supp}(a)-\operatorname{supp}(b)) < \max(\operatorname{supp}(b)-\operatorname{supp}(a))$ .

It can be shown that:

The relation defined above is indeed a partial order on $F[x_1,\ldots,x_n]$
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 -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 unique, such that

$f=a_1f_1+\cdots+a_sf_s+r$
For each $i=1,\ldots,s$ , does not divide any monomial in $\operatorname{supp}(r)$ .

Furthermore, if $a_if_i \neq 0$ for some

, then $M(a_if_i) \leq M(f)$ .

Definition of Gröbner basis:
Let 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 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 is also a basis of .

1	Partial Order
1	Total Order
1	Polynomial Ring
1	Basic Polynomial
1	Field
1	Finite
1	Fix
1	Relation Theory
1	Language
1	Implication
1	Ideal
2	Prismatoid
2	Basis Topological Space
2	Indeterminate
2	Archimedean Semigroup
3	Associates
9	Product Of Posets
10	Division Algorithm For Integers
15	Support