# Gröbner basis

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. 1.

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

2. 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 if $\max(\operatorname{supp}(a)-\operatorname{supp}(b))<\max(\operatorname{supp}(b% )-\operatorname{supp}(a))$.

It can be shown that:

1. 1.

The relation defined above is indeed a partial order on $F[x_{1},\ldots,x_{n}]$

2. 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. 1.

$f=a_{1}f_{1}+\cdots+a_{s}f_{s}+r$

2. 2.

For each $i=1,\ldots,s$, $M(a_{i})$ does not divide any monomial in $\operatorname{supp}(r)$.

Furthermore, if $a_{i}f_{i}\neq 0$ for some $i$, then $M(a_{i}f_{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$.

Title Gröbner basis GrobnerBasis 2013-03-22 13:03:47 2013-03-22 13:03:47 mathcam (2727) mathcam (2727) 28 mathcam (2727) Definition msc 13P10 monomial ordering Gröbner basis