Monomial order


In mathematics, a monomial order is a total order on the set of all monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e.,
Monomial orderings are most commonly used with Gröbner bases and multivariate division. In particular, the property of being a Gröbner basis is always relative to a specific monomial order.

Definition, details and variations

Besides respecting multiplication, monomial orders are often required to be well-orders, since this ensures the multivariate division procedure will terminate. There are however practical applications also for multiplication-respecting order relations on the set of monomials that are not well-orders.
In the case of finitely many variables, well-ordering of a monomial order is equivalent to the conjunction of the following two conditions:
  1. The order is a total order.
  2. If u is any monomial then.
Since these conditions may be easier to verify for a monomial order defined through an explicit rule, than to directly prove it is a well-ordering, they are sometimes preferred in definitions of monomial order.

Leading monomials, terms, and coefficients

The choice of a total order on the monomials allows sorting the terms of a polynomial. The leading term of a polynomial is thus the term of the largest monomial.
Concretely, let be any ring of polynomials. Then the set of the monomials in is a basis of, considered as a vector space over the field of the coefficients. Thus, any nonzero polynomial in has a unique expression
as a linear combination of monomials, where is a finite subset of and the are all nonzero. When a monomial order has been chosen, the leading monomial is the largest in, the leading coefficient is the corresponding, and the leading term is the corresponding. Head monomial/coefficient/term is sometimes used as a synonym of "leading". Some authors use "monomial" instead of "term" and "power product" instead of "monomial". In this article, a monomial is assumed to not include a coefficient.
The defining property of monomial orderings implies that the order of the terms is kept when multiplying a polynomial by a monomial. Also, the leading term of a product of polynomials is the product of the leading terms of the factors.

Examples

On the set of powers of any one variable x, the only monomial orders are the natural ordering 1 < x < x2 < x3 < ... and its converse, the latter of which is not a well-ordering. Therefore, the notion of monomial order becomes interesting only in the case of multiple variables.
The monomial order implies an order on the individual indeterminates. One can simplify the classification of monomial orders by assuming that the indeterminates are named x1, x2, x3,... in decreasing order for the monomial order considered, so that always. In the example below we use x, y and z instead of x1, x2 and x3. With this convention there are still many examples of different monomial orders.

Lexicographic order

Lexicographic order first compares exponents of x1 in the monomials, and in case of equality compares exponents of x2, and so forth. The name is derived from the similarity with the usual alphabetical order used in lexicography for dictionaries, if monomials are represented by the sequence of the exponents of the indeterminates. If the number of indeterminates is fixed, the lexicographical order is a well-order, although this is not the case for the lexicographical order applied to sequences of various lengths (see. For Gröbner basis computations this ordering tends to be the most costly; thus it should be avoided, as far as possible, except for very simple computations.

Graded lexicographic order

Graded lexicographic order first compares the total degree, and in case of a tie applies lexicographic order. This ordering is not only a well ordering, it also has the property that any monomial is preceded only by a finite number of other monomials; this is not the case for lexicographic order, where all powers of x are less than y. Although very natural, this ordering is rarely used: the Gröbner basis for the graded reverse lexicographic order, which follows, is easier to compute and provides the same information on the input set of polynomials.

Graded reverse lexicographic order

Graded reverse lexicographic order compares the total degree first, then uses a reverse lexicographic order as tie-breaker, but it reverses the outcome of the lexicographic comparison so that lexicographically larger monomials of the same degree are considered to be degrevlex smaller. For the final order to exhibit the conventional ordering of the indeterminates, it is furthermore necessary that the tie-breaker lexicographic order before reversal considers the last indeterminate xn to be the largest, which means it must start with that indeterminate. A concrete recipe for the graded reverse lexicographic order is thus to compare by the total degree first, then compare exponents of the last indeterminate xn but reversing the outcome, followed by a similar comparison of xn−1, and so forth ending with x1.
The differences between graded lexicographic and graded reverse lexicographic orders are subtle, since they in fact coincide for 1 and 2 indeterminates. The first difference comes for degree 2 monomials in 3 indeterminates, which are graded lexicographic ordered as but graded reverse lexicographic ordered as. The general trend is that the reverse order exhibits all variables among the small monomials of any given degree, whereas with the non-reverse order the intervals of smallest monomials of any given degree will only be formed from the smallest variables.

Elimination order

Block order or elimination order may be defined for any number of blocks but, for sake of simplicity, we consider only the case of two blocks. For this ordering, the variables are divided in two blocks x1,..., xh and y1,...,yk and a monomial ordering is chosen for each block, usually the graded reverse lexicographical order. Two monomials are compared by comparing their x part, and in case of a tie, by comparing their y part. This ordering is important as it allows elimination, an operation which corresponds to projection in algebraic geometry.

Weight order

Weight order depends on a vector called the weight vector. It first compares the dot product of the exponent sequences of the monomials with this weight vector, and in case of a tie uses some other fixed monomial order. For instance, the graded orders above are weight orders for the "total degree" weight vector. If the ai are rationally independent numbers then a tie can never occur, and the weight vector itself specifies a monomial ordering. In the contrary case, one could use another weight vector to break ties, and so on; after using n linearly independent weight vectors, there cannot be any remaining ties. One can in fact define any monomial ordering by a sequence of weight vectors, for instance,,... for lex, or ,,... for grevlex.
For example, consider the monomials,,, and ; the monomial orders above would order these four monomials as follows:
When using monomial orderings to compute Gröbner bases, different orders can lead to different results, and the difficulty of the computation may vary dramatically. For example, graded reverse lexicographic order has a reputation for producing, almost always, the Gröbner bases that are the easiest to compute. On the other hand, elimination orders are required for elimination and relative problems.