In mathematics, a monomial order (sometimes called a term order or an admissible order) is a total order on the set of all (monic) monomials in a given polynomial ring, satisfying the property of respecting multiplication, i.e.,
If u ≤ v {\displaystyle u\leq v} and w {\displaystyle w} is any other monomial, then u w ≤ v w {\displaystyle uw\leq vw} . 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:
The order is a total order. If u is any monomial then 1 ≤ u {\displaystyle 1\leq u} . 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 (for the chosen monomial ordering). Concretely, let R be any ring of polynomials. Then the set M of the (monic) monomials in R is a basis of R, considered as a vector space over the field of the coefficients. Thus, any nonzero polynomial p in R has a unique expression
p = ∑ u ∈ S c u u {\displaystyle p=\textstyle \sum _{u\in S}c_{u}u} as a linear combination of monomials, where S is a finite subset of M and the cu are all nonzero. When a monomial order has been chosen, the leading monomial is the largest u in S, the leading coefficient is the corresponding cu, and the leading term is the corresponding cuu. 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 { x n ∣ n ∈ N } {\displaystyle \left\{x^{n}\mid n\in \mathbb {N} \right\}} 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 x1 > x2 > x3 > .... (If there should be infinitely many indeterminates, this convention is incompatible with the condition of being a well ordering, and one would be forced to use the opposite ordering; however the case of polynomials in infinitely many variables is rarely considered.) 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 (lex) 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 (as it is usually the case), the lexicographical order is a well-order, although this is not the case for the lexicographical order applied to sequences of various lengths. For monomials of degree at most two in two indeterminates x 1 , x 2 {\displaystyle x_{1},x_{2}} , the lexicographic order (with x 1 > x 2 {\displaystyle x_{1}>x_{2}} ) is
x 1 2 > x 1 x 2 > x 1 > x 2 2 > x 2 > 1. {\displaystyle x_{1}^{2}>x_{1}x_{2}>x_{1}>x_{2}^{2}>x_{2}>1.}
For Gröbner basis computations, the lexicographic ordering tends to be the most costly; thus it should be avoided, as far as possible, except for very simple computations.
… excerpt ends here. Continue reading the full article.
