# Singular

### 7.9.2 Monomial orderings on free algebras

Monomial orderings are of critical importance when dealing with Groebner bases. Especially in the non-commutative Groebner theory up to a degree (length) bound it might be vital to have many choices for orderings since it is not guaranteed that there exists a finite Groebner bases with respect to the given ordering.

Let = { ,..., } be a set of symbols. A total ordering < on the free monoid with 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 respects multiplication, that is implies for all , , and in .
Note that the latter implies for all in .

The left lexicographical ordering on with ... is defined as follows: For arbitrary , in we say that , if

• or

• and holds.

Note: left lex is not a monomial ordering, though it is a natural choice to break ties in further definitions.

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

On the monoid define the weight homomorphism , uniquely determined by in for . As a special case, define the length len: by for . For any ordering << on and any weight define an ordering <, the -weight extension of << as follows: For arbitrary , in we say that if

• or
• and << holds.
An ordering < on eliminates a certain subset if for all one has .

In a ring declaration, LETTERPLACE supports the following monomial orderings. We illustrate each of the available choices by an example on the free monoid , , , where we order the monomials

, , , , , , , , , and 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:

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:

Wp(w) for intvec w'
The weighted degree left lexicographical ordering is the -weight extension of the left lexicographical ordering with weight uniquely determined by strict positive .

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

lp'
Let be weights uniquely determined by for where denotes the Kronecker delta. Let be the -weight extension of the left lexicographical ordering on and inductively be the -weight extension of for all . The monomial ordering lp corresponds to and eliminates for all .

The monomial ordering lp' corresponds to and eliminates { ,..., } for all <= < .

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

rp'
Let be weights uniquely determined by for where denotes the Kronecker delta. Let be the -weight extension of the left lexicographical ordering on and inductively be the -weight extension of for all . The monomial ordering rp corresponds to and eliminates for all .

The monomial ordering rp' corresponds to and eliminates { ,..., } for all .

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

(a(v), ordering) for intvec v'
For weight determined by with and monomial ordering on , the -weight extension of corresponds to (a(v), o). As a choice for there are currently two options implemented, which are dp and Dp. Notice that this ordering eliminates .

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

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

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 def R = freeAlgebra(r, 4); setring R; 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; ==> x1*x1*x1+x1*x2*x3+x3*x2*x1+x3*x3*x3+x1*x3+x2*x2+x2*x3+x3*x1+x1+x2+x3