Let P be the polynomial ring R[x1, ..., xn] of rank n over a ring R. A monomial (or power product) of P is a product of powers of the variables (or indeterminates) of P, that is, an expression of the form x1e1 ... xnen with ei ≥0 for 1 ≤i ≤n. Multivariate polynomials in Magma are stored efficiently in distributive form, using arrays of coefficient-monomial pairs, where the coefficient is in the base ring R. The word `term' will always refer to a coefficient multiplied by a monomial.
Monomial orders are of critical importance when dealing with Gröbner bases. Let M be the set of all monomials of P. A monomial ordering on M is a total order < on M such that 1 ≤s for all s ∈M, s ≤t implies su ≤tu for all s, t, u ∈M, and M is a well-ordering (every non-empty subset of M possesses a minimal element w.r.t. <). Monomial orders can be naturally specified in terms of weight vectors: a vector W from Qn with non-negative entries is called a weight vector since it weights a monomial s by the product s.W (defined to be the dot product of the exponent vector of s with W); any sequence of n linearly-independent weight vectors determines a monomial order on M (see the weight order below [subsection Weight: weight]). All monomial orderings can in fact be represented in terms of weight vectors.
Multivariate polynomial rings are constructed in Magma such that the monomials of any polynomial are sorted with respect to a specified monomial order, with the greatest monomial first. Gröbner basis computations are dramatically affected by the choice of monomial order. Magma provides an extensive choice of monomial orders. Currently, the intrinsic functions PolynomialRing (or PolynomialAlgebra), ChangeOrder and VariableExtension expect a monomial order; it is specified by a string giving the name, optionally followed by extra arguments for that order.
We now describe each of the monomial orders available in Magma. We suppose that s and t are monomials from P which has rank n. Any order on the monomials is then fully defined by just specifying exactly when s < t with respect to that order. In the following, the argument(s) are described for an order as a list of expressions; that means that the expressions (without the parentheses) should be appended to any base arguments when any particular intrinsic function is called which expects a monomial order. See also [CLO96, Chap. 2, Para 2] for more details about the first three orders.
Definition: s < t iff there exists 1 ≤i ≤n such that the first i - 1 exponents of s and t are equal but the i-th exponent of s is less than the i-th exponent of t. The order is specified by the argument ("lex").
The order is called "lexicographical" since it orders the monomials as if they were words in a dictionary. The i-th variable is greater than the (i + 1)-th variable for 1 ≤i < n so the first variable is the greatest variable. A Gröbner basis of an ideal with respect to the lexicographical order usually represents the most information about the ideal but can be hard to compute.
Definition: s < t iff the total degree of s is less than the total degree of t or the total degree of s is equal to the total degree of t and s < t with respect to the lexicographical order. The order is specified by the argument ("glex").
The order is called "graded lexicographical" since it first grades the monomials by total degree, and then decides ties by the lexicographical order. The i-th variable is greater than the (i + 1)-th variable for 1 ≤i < n so the first variable is the greatest variable. This order is rarely used because the grevlex order below is usually a better degree order (i.e., yields smaller Gröbner bases).
Definition: s < t iff the total degree of s is less than the total degree of t or the total degree of s is equal to the total degree of t and s > t with respect to the lexicographical order applied to the exponents of s and t in reverse order. The order is specified by the argument ("grevlex").
The order is called "graded reverse lexicographical" since it first grades the monomials by total degree, and then decides ties by the negation of the lexicographical order applied to the variables in reverse order. Again, the i-th variable is greater than the (i + 1)-th variable for 1 ≤i < n so the first variable is the greatest variable. A Gröbner basis of an ideal with respect to the graded reverse lexicographical order is usually the easiest to compute so it is recommended that this order be used when just any Gröbner basis for an ideal is desired.
Definition (given a sequence W of n positive integer weights): s < t iff the total weighted degree ds of s w.r.t. W is less than the total degree dt of t w.r.t. W or ds=dt and s > t with respect to the lexicographical order applied to the exponents of s and t in reverse order. The order is specified by the arguments ("grevlexw", W).
The order is called "graded reverse lexicographical (weighted)" since it first grades the monomials by weighted degree w.r.t. W, and then decides ties by the negation of the lexicographical order applied to the variables in reverse order. If W = [1, 1, ..., 1], then this order is equal to the grevlex order. Again, the i-th variable is greater than the (i + 1)-th variable for 1 ≤i < n so the first variable is the greatest variable.
This order is similar to the grevlex order, but is useful if an ideal is homogeneous with respect to the grading given by W, since the Gröbner basis of the ideal will tend to be smaller with this order.
Definition (given k with 1 ≤k ≤n - 1): s < t iff sk < tk with respect to the grevlex order or sk = tk and sk' < tk' with respect to the grevlex order where mk denotes the monomial consisting of the first k exponents of m and mk' denotes the monomial consisting of the last n - k exponents of m (this order is thus the concatenation of two block grevlex orders). The order is specified by the arguments ("elim", k).
The order is called "elimination" since the first k variables are "eliminated": if G is a Gröbner basis of an ideal I of the polynomial ring K[x1, ..., xn] with respect to this order, then G ∩K[xk + 1, ..., xn] is a Gröbner basis of the k-th elimination ideal I ∩K[xk + 1, ..., xn]. (It is usually easier to compute a Gröbner basis with respect to this order for any k than with respect to the full lexicographical order.) Again, the i-th variable is greater than the (i + 1)-th variable for 1 ≤i < n so the first variable is the greatest variable.
Definition (given sequences U and V such that U and V contain distinct integers in the range 1 to n and the sum of the lengths of U and V is n and U and V are disjoint): s < t iff sU < tU with respect to the grevlex order or sU = tU and sV < tV with respect to the grevlex order where mL denotes the monomial consisting of the exponents of m corresponding to the entries of L in order. The order is specified by the arguments ("elim", U, V). V may be omitted if desired so the arguments are just ("elim", U); in this case V is chosen to be an appropriate sequence to complement U.
The order is called "elimination" since the variables in U are "eliminated". The order of the elements in U and V are significant since the ordering on the variables makes U[1] greatest, then U[2], etc., then V[1], V[2], etc.
Definition (given sequences U and V such that U and V contain distinct integers in the range 1 to n and the sum of the lengths of U and V is n and U and V are disjoint): s < t iff sV < tV with respect to the grevlex order or sV = tV and sU < tU with respect to the grevlex order. The order is specified by the arguments ("invblock", U, V). V may be omitted if desired so the arguments are just ("invblock", U); in this case V is chosen to be an appropriate sequence to complement U.
The order is called "inverse block" since it applies a block ordering on the exponents on V then U which inverts the lists supplied to the elimination list order. Thus this is the same as the elimination order except that the lists U and V are swapped. See [BW93, p. 390] for the motivation for this order.
Definition (given i with 1 ≤i ≤n): s < t iff sL < tL with respect to the grevlex order or sL = tL and the i-th exponent of s is less than the i-th exponent of t, where L is the sequence [1 .. n] with i deleted. The order is specified by the arguments ("univ", i).
The order is called "univariate" since when monomials are compared, any monomial not containing the i-th variable is greater than any monomial containing the i-th variable. Thus all variables but the i-th are "eliminated" so that a Gröbner basis of a zero-dimensional ideal I with this ordering will contain the unique monic generator of the elimination ideal consisting of all the polynomials in I containing the i-th variable alone. The j-th variable is greater than the (j + 1)-th variable for 1 ≤j < i and i < j ≤n and the j-th variable is greater than the i-th variable for any j not= i.
Definition (given n weight vectors W1, ... Wn from Qn): s < t iff there exists 1 ≤i ≤n such that s.Wj = t.Wj for 1 ≤j < i and s.Wi < t.Wi. The order is specified by the arguments ("weight", Q) where Q is a sequence of n2 non-negative integers or rationals describing the n weight vectors of length n (in row major order).
The n weight vectors must describe a vector space basis of Qn (i.e., be linearly-independent), since otherwise this would not yield a total ordering on the monomials. The weight order allows one to specify any possible monomial order; any of the monomial orders mentioned above can be specified by an appropriate choice of weight vectors. However, using the in-built versions of the specialized orders above is much faster than constructing versions of them based on weight vectors. The next section contains an example in which a polynomial ring is constructed with a weight order for the monomials.