Monomial orders

At the heart of the NCProcess1 and NCProcess2 commands is a GBA and central to this is the notion of monomial order. The effect of the SetKnowns and SetUnknowns commands is to prescribe a monomial order. It is essential to set a monomial order before running NCProcess. Indeed this is all which is required; one need not set knowns and unknowns.

In this section we give more thorough descriptions of the types of monomial orders which are natural for these applications. They provided more flexibility in attacking problems.

Many possible choices of ordering are possible. We will briefly discuss three types of orderings: graded lex, pure lex and multigraded lex. The discussion here gives a straightforward generalization the discussion of graded lex and pure lex monomial orders from commutative polynomial rings to noncommutative polynomial rings. See [CLS]. See also Appendix §.

Graded Lex (notation: a < b < c < d)

A graded lexicographic order on monic monomials in variables, say a, b, c, ... compares two monic monomials by first comparing their total degrees. If their total degrees are not equal, then the monomial with the smaller total degree is considered smaller in the graded lex order. If their total degrees are equal, then the monomials are compared using a ``dictionary'' type order. To specify a graded lex order, one needs to specify an order on the variables, denoted a < b < c < ..., from which this ``dictionary'' order is derived. For example, if we use a graded lex order on monomials in the variables a and b such that a < b, then the monomials of total degree 2 are ordered by

a < b < a a < a b < b a < b b.

More generally, for a < b < c < ... and monic monomials M and N, we say that

M is less than N (with respect to graded lex) if either the total degree of M is less than the total degree of N or M comes before N in the dictionary.

This type of order often works well when the main objective is not to eliminate particular variables but primarily to reduce the degree of the polynomial p-q in the polynomial equations p=q.

Pure lex (notation: a « b « c « d)

Pure lex order is a type of order used to transform a collection of equations into a collection of polynomial equations in triangular form, as described in in §. The pure lex order induced by a, b, c, ... is denoted by a « b « c « ... (contrast this to the notation for graded lex and multigraded lex). This notation is consistent with [CLS].

For those unfamiliar with pure lex orders, it is instructive to note that, in a pure lex order on monic monomials in a and b such that a « b, any monomial M containing b is higher in the order than any monomial M which does not contain b, even if M has a much higher degree than M . Also two monic monomials containing b are ranked by first comparing the number of occurrences of the variable b in the monomial. If that is not enough to determine which is larger, a ``dictionary'' type order is used.

For example, if we use a pure lex graded lex order on monic monomials in a and b such that a « b, then the monic monomials of total degree 2 are ordered by

a < a a < a b < b a < b b.

Multigraded lex (notation: a < b « c < d)

Multigraded lex is a combination of pure lex and graded lex. We defer the explanation of this order until Appendix §. The notation for multigraded lex orders consists of a list of variables separated by either < or « (e.g., a < b « c < d, a « b « c or a < b < c). If all of the separators are <, then the multigraded lex order is a graded lex order. If all of the separators are «, then the multigraded lex order is a pure lex order. We give one example.

Example 7.1 We consider a mulrigraded lex order on monic monomials in the variables a, b, c and d which is denoted a < b « c < d.

This order on the monic monomials of total degree 2 is

a < b < aa < ab < ba < bb < c < d < ac < bc < ca < cb < ad < bd < da < db < cc < cd < dc < dd.

More generally the following statements hold:

1. If M and M are monic monmials in a and b, then they are ordered by the graded lex order a < b.
2. If M and M are monic monomials in c and d, then they are ordered by the graded lex order c < d.
3. If M and M are monic monomials in a and c (or in a and d or in b and c or in b and d), then they are ordered by the pure lex order a « c (or a « d or b « c or b « d).

Knowns and Unknowns

Much of this paper is phrased in terms of knowns and unknowns. We use orders to put this distinction into a Gröbner Basis Algorithm. Obviously, one wants to solve for (or eliminate) unknowns, not knowns. Thus we will always be using orders satisfying

knowns « unknowns

and such that monic monomials in the knowns are ordered using a graded lex order. Indeed, this property could be taken to be the formal definition of known. In the notation of multigraded lex, the knowns are listed with < between them and the unknowns are listed with a combination of < and « between them.

In the examples in this paper, the monic monomials in the unknowns are ordered using a pure lex order. In the notation of multigraded lex, this is expressed by listing the unknowns with « between them.

We have found that one could use either a pure lex or certain multigraded lex orders on the unknowns and obtain the same results. The examples in this paper were initially done with a multigraded lex order on the unknowns which was not a pure lex order.