Home Online Manual
Top
Back: Free associative algebras
Forward: Groebner bases for two-sided ideals in free associative algebras
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.9.2 Monomial orderings on free algebras

We provide many types of orderings for non-commutative Groebner bases up to a degree (length) bound. In general it is not clear, whether a given generating set has a finite Groebner bases with respect to some ordering.

Let $X$ = { $x_1$,..., $x_n$} be a set of symbols. A total ordering < on the free monoid $< X >$ with $1$ as the neutral element is called a monomial ordering if

  • it is a well-ordering, i.e., every non empty subset has a least element with respect to <, and
  • it is compatible with multiplication, that is $u < v$ implies $aub < avb$ for all $u$, $v$, $a$ and $b$ in $< X >$.
Note that the latter implies $1 <= m$ for all $m$ in $< X >$.

The left lexicographical ordering on $< X >$ with $x_1> x_2 > $... $ > x_n$ is defined as follows: For arbitrary $a$, $b$ in $< X >$ we say that $a<b$, if

  • $\exists u\in \langle X\rangle\setminus\{1\}:\;au=b$ or

  • $\exists u,\,v,\,w\in \langle X\rangle\;\exists x_i,\,x_j\in X: a=ux_iv,\;b=ux_jw$ and $i<j$ holds.

Note: left lex is not a monomial ordering, though it is a natural choice to break ties after, say, comparing elements by the total degree.

In a similar manner one can define the right lexicographical ordering.

On the monoid $(N_0,+)$define the weight homomorphism $w: \langle X\rangle\rightarrow N_0$, uniquely determined by $w(x_i)=w_i$ in $N_0$for $1 <= i <= n$.

As a special case, define the length len: $ \langle X\rangle\rightarrow N_0$ by $len(x_i)=1$ for $1 <= i <= n$.

For any ordering << on $< X >$ and any weight $w: \langle X\rangle\rightarrow N_0$ define an ordering $<$, called the $w$-weight extension of $<<$ as follows: For arbitrary $a$, $b$ in $< X >$ we say that $a<b$ if

  • $w(a)<w(b)$ or
  • $w(a)=w(b)$ and $a<<b$ holds.
An ordering < on $< X >$ eliminates a certain subset $\emptyset\not=Y\subset X$ if for all $f\in K\langle X\rangle\setminus\{0\}$ one has $ lm(f)\in K\langle X\setminus Y\rangle\Rightarrow f\in K\langle X\setminus Y\rangle\subseteq K\langle X\rangle$.

In a ring declaration, LETTERPLACE supports the following monomial orderings.

We illustrate each of the available choices by an example on the free monoid $<x_1$, $x_2$, $x_3>$, where we order the monomials

$x_1 x_1 x_1$, $x_3 x_2 x_1$, $x_1 x_2 x_3$, $x_3 x_3 x_3$, $x_3 x_1$, $x_2 x_2$, $x_1 x_3$, $x_2 x_3$, $x_1$, $x_2$ and $x_3$ correspondingly.

`dp'
The degree right lexicographical ordering is the length-weight extension of the right lexicographical ordering.

With respect to the ordering `dp', the test monomials are ordered as follows:

$x_1 x_1 x_1 > x_3 x_2 x_1 > x_1 x_2 x_3 > x_3 x_3 x_3 > x_3 x_1 > x_2 x_2 > x_1 x_3 > x_2 x_3 > x_1 > x_2 > x_3$

`Dp'
The degree left lexicographical ordering is the length-weight extension of the left lexicographical ordering.

With respect to the ordering `Dp', the test monomials are ordered as follows:

$x_1 x_1 x_1 > x_1 x_2 x_3 > x_3 x_2 x_1 > x_3 x_3 x_3 > x_1 x_3 > x_2 x_2 > x_2 x_3 > x_3 x_1 > x_1 > x_2 > x_3$

`Wp(w) for intvec w'
The weighted degree left lexicographical ordering is the $w$-weight extension of the left lexicographical ordering with weight $w: \langle X\rangle\rightarrow N_0$ uniquely determined by strict positive $w(x_i)=w_i>0$.

With respect to the ordering `Wp(1, 2, 1)', the test monomials are ordered as follows:

$x_1 x_2 x_3 > x_2 x_2 > x_3 x_2 x_1 > x_1 x_1 x_1 > x_2 x_3 > x_3 x_3 x_3 > x_1 x_3 > x_2 > x_3 x_1 > x_1 > x_3$

`lp'
Let $w^{(i)}$ be weights uniquely determined by $w^{(i)}(x_j)=\delta_{i,j}$ for $1\leq i,j\leq n$ where $\delta$ denotes the Kronecker delta. Let $<_n$ be the $w^{(n)}$-weight extension of the left lexicographical ordering on $\langle X\rangle$ and inductively $<_i$ be the $w^{(i)}$-weight extension of $<_{i+1}$ for all $1\leq i<n$. The monomial ordering lp corresponds to $<_1$ and eliminates $x_1,...,x_j$ for all $1\leq j<n$. We refer to it as to left elimination ordering.

The monomial ordering `lp' corresponds to $<_1$ and eliminates { $x_1$,..., $x_j$} for all $1$<= $j$< $n$. We refer to it as to left elimination ordering.

With respect to the ordering `lp', the test monomials are ordered as follows:

$x_1 x_1 x_1 > x_1 x_2 x_3 > x_3 x_2 x_1 > x_1 x_3 > x_3 x_1 > x_1 > x_2 x_2 > x_2 x_3 > x_2 > x_3 x_3 x_3 > x_3$

`rp'
Let $w^{(i)}$ be weights uniquely determined by $w^{(i)}(x_j)=\delta_{i,j}$ for $1\leq i,j\leq n$ where $\delta$ denotes the Kronecker delta. Let $<_1$ be the $w^{(1)}$-weight extension of the left lexicographical ordering on $\langle X\rangle$ and inductively $<_i$ be the $w^{(i)}$-weight extension of $<_{i-1}$ for all $1<i\leq n$. The monomial ordering rp corresponds to $<_n$ and eliminates $\{x_j,\ldots,x_n\}$ for all $1<j\leq n$. We refer to it as to right elimination ordering.

The monomial ordering `rp' corresponds to $<_n$ and eliminates { $x_j$,..., $x_n$} for all $1 < j <= n$. We refer to it as to right elimination ordering.

With respect to the ordering `rp', the test monomials are ordered as follows:

$x_3 x_3 x_3 > x_1 x_2 x_3 > x_3 x_2 x_1 > x_2 x_3 > x_1 x_3 > x_3 x_1 > x_3 > x_2 x_2 > x_2 > x_1 x_1 x_1 > x_1$

`(a(v), ordering) for intvec v'
For weight $v:\langle X\rangle\rightarrow N_0$ determined by $v(x_i)=v_i\in N_0$ with $1\leq i\leq n$ and monomial ordering $\prec$ on $\langle X\rangle$, the $v$-weight extension of $\prec$ corresponds to (a(v), o). As a choice for $\prec$ there are currently two options implemented, which are dp and Dp. Notice that this ordering eliminates $\{x_i\in X\mid v(x_i)\not=0\}$.

With respect to the ordering `( a(1, 0, 0), Dp)', the test monomials are ordered as follows:

$x_1 x_1 x_1 > x_1 x_2 x_3 > x_3 x_2 x_1 > x_1 x_3 > x_3 x_1 > x_1 > x_3 x_3 x_3 > x_2 x_2 > x_2 x_3 > x_2 > x_3$

With ordering `( a(1, 1, 0), Dp)' one obtains:

$x_1 x_1 x_1 > x_1 x_2 x_3 > x_3 x_2 x_1 > x_2 x_2 > x_1 x_3 > x_2 x_3 > x_3 x_1 > x_1 > x_2 > x_3 x_3 x_3 > x_3$

The examples are generated by the following code but with customized orderings denoted above.

 
LIB "freegb.lib";
ring r = 0, (x1,x2,x3),Dp; // variate ordering here
ring R = freeAlgebra(r, 4);
poly wr = x1*x1*x1+x3*x3*x3+x1*x2*x3+x3*x2*x1+x2*x2+x2*x3+x1*x3+x3*x1+x1+x2+x3;
wr; // polynomial will be automatically ordered according to the ordering on R
==> x1*x1*x1+x1*x2*x3+x3*x2*x1+x3*x3*x3+x1*x3+x2*x2+x2*x3+x3*x1+x1+x2+x3