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

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

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 polynomialMis less thanN(with respect to graded lex) if either the total degree ofMis less than the total degree ofNorMcomes beforeNin the dictionary.

**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

**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:
*

- If M and M are monic monmials in a and b, then they are ordered by the graded lex order a < b.
- If M and M are monic monomials in c and d, then they are ordered by the graded lex order c < d.
*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

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.

Wed Jul 3 10:27:42 PDT 1996