Monomial order

Last updated January 26, 2024

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.,

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\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=\textstyle \sum _{u\in S}c_{u}u$ as a linear combination of monomials, where $S$ is a finite subset of $M$ and the $c u$ 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 $c u$ , and the leading term is the corresponding $c u u$ . 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 $\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 < x² < x³ < ... 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 x₁, x₂, x₃, ... in decreasing order for the monomial order considered, so that always x₁ > x₂ > x₃ > .... (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 x₁, x₂ and x₃. With this convention there are still many examples of different monomial orders.

Lexicographic order

Lexicographic order (lex) first compares exponents of x₁ in the monomials, and in case of equality compares exponents of x₂, 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 (see Lexicographic order § Ordering of sequences of various lengths).

For monomials of degree at most two in two indeterminates $x_{1},x_{2}$ , the lexicographic order (with $x_{1}>x_{2}$ ) is

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.

Graded lexicographic order

Graded lexicographic order (grlex, or deglex for degree lexicographic order) first compares the total degree (sum of all exponents), 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 (infinitely many) powers of y are less than x (that lexicographic order is nevertheless a well ordering is related to the impossibility of constructing an infinite decreasing chain of monomials).

For monomials of degree at most two in two indeterminates $x_{1},x_{2}$ , the graded lexicographic order (with $x_{1}>x_{2}$ ) is

x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}>x_{2}>1.

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 (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 x₁ > x₂ > ... > x_n of the indeterminates, it is furthermore necessary that the tie-breaker lexicographic order before reversal considers the last indeterminate x_n 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 x_n 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 x_n−1, and so forth ending with x₁.

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 $x_{1}^{2}>x_{1}x_{2}>x_{1}x_{3}>x_{2}^{2}>x_{2}x_{3}>x_{3}^{2}$ but graded reverse lexicographic ordered as $x_{1}^{2}>x_{1}x_{2}>x_{2}^{2}>x_{1}x_{3}>x_{2}x_{3}>x_{3}^{2}$ . 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 (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 x₁,..., x_h and y₁,...,y_k 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 $(a_{1},\ldots ,a_{n})\in \mathbb {R} _{\geq 0}^{n}$ 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 (1,1,...,1). If the a_i are rationally independent numbers (so in particular none of them are zero and all fractions ${\tfrac {a_{i}}{a_{j}}}$ are irrational) 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 (Cox et al. pp. 72–73), for instance (1,0,0,...,0), (0,1,0,...,0), ... (0,0,...,1) for lex, or (1,1,1,...,1), (1,1,..., 1,0), ... (1,0,...,0) for grevlex.

For example, consider the monomials $xy^{2}z$ , $z^{2}$ , $x^{3}$ , and $x^{2}z^{2}$ ; the monomial orders above would order these four monomials as follows:

Lex: $x^{3}>x^{2}z^{2}>xy^{2}z>z^{2}$ (power of $x$ dominates).
Grlex: $x^{2}z^{2}>xy^{2}z>x^{3}>z^{2}$ (total degree dominates; higher power of $x$ broke tie among the first two).
Grevlex: $xy^{2}z>x^{2}z^{2}>x^{3}>z^{2}$ (total degree dominates; lower power of $z$ broke tie among the first two).
A weight order with weight vector (1,2,4): $x^{2}z^{2}>xy^{2}z>z^{2}>x^{3}$ (the dot products 10>9>8>3 do not leave any ties to be broken here).

Related notions

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 {x₁}, {x₂}, {x₃}, ... (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.

Related Research Articles

In mathematics, a polynomial is a mathematical expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example of a polynomial of a single indeterminate $x$ is $x 2 - 4 x + 7$ . An example with three indeterminates is $x 3 + 2 xyz 2 - yz + 1$ .

In mathematics, Hilbert's Nullstellensatz is a theorem that establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic geometry. It relates algebraic sets to ideals in polynomial rings over algebraically closed fields. This relationship was discovered by David Hilbert, who proved the Nullstellensatz in his second major paper on invariant theory in 1893.

In mathematics and specifically in algebraic geometry, the dimension of an algebraic variety may be defined in various equivalent ways.

In mathematics, an affine algebraic plane curve is the zero set of a polynomial in two variables. A projective algebraic plane curve is the zero set in a projective plane of a homogeneous polynomial in three variables. An affine algebraic plane curve can be completed in a projective algebraic plane curve by homogenizing its defining polynomial. Conversely, a projective algebraic plane curve of homogeneous equation $h (x, y, t) = 0$ can be restricted to the affine algebraic plane curve of equation $h (x, y, 1) = 0$ . These two operations are each inverse to the other; therefore, the phrase algebraic plane curve is often used without specifying explicitly whether it is the affine or the projective case that is considered.

In mathematics, and more specifically in computer algebra, computational algebraic geometry, and computational commutative algebra, a Gröbner basis is a particular kind of generating set of an ideal in a polynomial ring $K [x 1, ..., x n]$ over a field $K$ . A Gröbner basis allows many important properties of the ideal and the associated algebraic variety to be deduced easily, such as the dimension and the number of zeros when it is finite. Gröbner basis computation is one of the main practical tools for solving systems of polynomial equations and computing the images of algebraic varieties under projections or rational maps.

In mathematics, a monomial is, roughly speaking, a polynomial which has only one term. Two definitions of a monomial may be encountered:

A monomial, also called power product, is a product of powers of variables with nonnegative integer exponents, or, in other words, a product of variables, possibly with repetitions. For example, $is a monomial. The constant is a monomial, being equal to the empty product and to for any variable . If only a single variable is considered, this means that a monomial is either or a power of, with a positive integer. If several variables are considered, say, then each can be given an exponent, so that any monomial is of the form with non-negative integers.$
A monomial is a monomial in the first sense multiplied by a nonzero constant, called the coefficient of the monomial. A monomial in the first sense is a special case of a monomial in the second sense, where the coefficient is $. For example, in this interpretation and are monomials.$

In algebra and in particular in algebraic combinatorics, the ring of symmetric functions is a specific limit of the rings of symmetric polynomials in n indeterminates, as n goes to infinity. This ring serves as universal structure in which relations between symmetric polynomials can be expressed in a way independent of the number n of indeterminates. Among other things, this ring plays an important role in the representation theory of the symmetric group.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative analogue of a polynomial ring since its elements may be described as "polynomials" with non-commuting variables. Likewise, the polynomial ring may be regarded as a free commutative algebra.

In mathematics, the lexicographic or lexicographical order is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a totally ordered set.

In mathematics the monomial basis of a polynomial ring is its basis that consists of all monomials. The monomials form a basis because every polynomial may be uniquely written as a finite linear combination of monomials.

In mathematics, a symmetric polynomial is a polynomial $P (X 1, X 2, ..., X n)$ in $n$ variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, $P$ is a symmetric polynomial if for any permutation $σ$ of the subscripts $1, 2, ..., n$ one has $P (X σ(1), X σ(2), ..., X σ(n)) = P (X 1, X 2, ..., X n)$ .

In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial can be expressed as a polynomial in elementary symmetric polynomials. That is, any symmetric polynomial $P$ is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials. There is one elementary symmetric polynomial of degree $d$ in $n$ variables for each positive integer $d \leq n$ , and it is formed by adding together all distinct products of $d$ distinct variables.

In mathematics, a homogeneous polynomial, sometimes called quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, $is a homogeneous polynomial of degree 5, in two variables; the sum of the exponents in each term is always 5. The polynomial is not homogeneous, because the sum of exponents does not match from term to term. The function defined by a homogeneous polynomial is always a homogeneous function.$

In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients that is equal to zero if and only if the polynomials have a common root, or, equivalently, a common factor. In some older texts, the resultant is also called the eliminant.

In mathematics, and more specifically in computer algebra and elimination theory, a regular chain is a particular kind of triangular set of multivariate polynomials over a field, where a triangular set is a finite sequence of polynomials such that each one contains at least one more indeterminate than the preceding one. The condition that a triangular set must satisfy to be a regular chain is that, for every $k$ , every common zero (in an algebraically closed field) of the $k$ first polynomials may be prolongated to a common zero of the $(k + 1)$ th polynomial. In other words, regular chains allow solving systems of polynomial equations by solving successive univariate equations without considering different cases.

In ring theory, a branch of mathematics, a ring R is a polynomial identity ring if there is, for some N > 0, an element P ≠ 0 of the free algebra, Z⟨X₁, X₂, ..., X_N⟩, over the ring of integers in N variables X₁, X₂, ..., X_N such that

A system of polynomial equations is a set of simultaneous equations $f 1 = 0, ..., f h = 0$ where the $f i$ are polynomials in several variables, say $x 1, ..., x n$ , over some field $k$ .

In abstract algebra, a monomial ideal is an ideal generated by monomials in a multivariate polynomial ring over a field.

References

David Cox; John Little; Donal O'Shea (2007). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer. ISBN 978-0-387-35650-1.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.