Көпмүшелердің реттелу тәртібі

Order for the terms of a polynomial

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 and is any other monomial, then
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.

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

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.

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 1=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.

Graded reverse lexicographic order (grevlex, or degrevlex for degree reverse lexicographic order) compares the total degree first, then uses a 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 1=x1 > x2 > > xn 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 (so the monomial with smaller exponent is larger in the ordering), followed (as always only in case of a tie) 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.

Block order or elimination order (lexdeg) may be defined for any number of blocks but, for sake of simplicity, we consider only the case of two blocks (however, if the number of blocks equals the number of variables, this order is simply the lexicographic order). 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.

An elimination order guarantees that a monomial involving any of a set of indeterminates will always be greater than a monomial not involving any of them. A product order is the easier example of an elimination order. It consists in combining monomial orders on disjoint sets of indeterminates into a monomial order on their union. It simply compares the exponents of the indeterminates in the first set using the first monomial order, then breaks ties using the other monomial ordering on the indeterminates of the second set. This method obviously generalizes to any disjoint union of sets of indeterminates; the lexicographic order can be so obtained from the singleton sets {x1}, {x2}, {x3}, (with the unique monomial ordering for each singleton). 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 (this is enforced by the fact that, under rather common conditions on the ideal, the polynomials in the Gröbner basis have a degree that is at most exponential in the number of variables; no such complexity result exists for any other ordering). On the other hand, elimination orders are required for elimination and relative problems.