Monomial order

A monomial order is a way of comparing monomials, such as $x^{2} y$ and $x y^{3}$ , that makes multivariate polynomials behave enough like univariate ones for division to work^[1]. In one variable, monomials are ordered by degree and every polynomial has a leading term. In several variables there is no single natural choice, and one must be made: a monomial order is a total order on monomials that respects multiplication, so that $u > v$ implies $u w > v w$ , and in which every monomial is at least 1. It fixes the leading term of every polynomial, and with it the steps of multivariate division and the Gröbner basis of an ideal. The most common orders are lexicographic (lex), graded lexicographic (grlex) and graded reverse lexicographic (grevlex). The choice changes results and cost dramatically: lex bases eliminate variables and solve systems but are often huge, while grevlex bases are usually the cheapest to compute.

§ 01

Definition

Identify a monomial $x_{1}^{α_{1}} \dots x_{n}^{α_{n}}$ with its exponent vector $α \in N^{n}$ . A monomial order is a total order $>$ on $N^{n}$ such that

α > β ⟹ α + γ > β + γ for all γ, α \geq 0 for all α

The second condition makes the order a well-order: by Dickson's lemma, every set of monomials has finitely many minimal elements under divisibility^[6], from which it follows that every strictly decreasing sequence of monomials is finite. This is what guarantees that division, which replaces a leading term by smaller ones, terminates^[1].

§ 02

Common orders

With variables ordered $x_{1} > x_{2} > \dots > x_{n}$ , the standard orders are^[1]^[8]:

Lexicographic order compares the exponents of $x_{1}$ first, then of $x_{2}$ , and so on, like words in a dictionary: $x_{1} > x_{2}^{100}$ . Graded lexicographic order compares total degree first and breaks ties lexicographically. Graded reverse lexicographic order compares total degree first; among monomials of equal degree, the one with the smaller exponent in the last variable where they differ is larger. The two graded orders agree for two variables but differ from three on: $x y z^{2}$ is larger than $y^{3} z$ in grlex, since $x$ appears in it, but smaller in grevlex, since it has more $z$ .

The monomials of degree at most 3 in x and y, numbered from smallest to largest. Lexicographic order exhausts all powers of y before reaching x, and in the full ring infinitely many monomials lie below x. The graded orders proceed degree by degree.

Three orders as comparison functions on exponent arrays.

(* Lexicographic: compare the first variable, then the next ... *)
let lex (a : mono) (b : mono) =
  let rec go i = if i = Array.length a then 0 else if a.(i) <> b.(i) then compare a.(i) b.(i) else go (i + 1) in
  go 0
(* Graded lexicographic: total degree first, ties broken by lex. *)
let grlex a b = let c = compare (degree a) (degree b) in if c <> 0 then c else lex a b
(* Graded reverse lexicographic: total degree first; on a tie, the
   monomial with the smaller exponent in the last variable that differs
   is larger. *)
let grevlex a b =
  let c = compare (degree a) (degree b) in
  if c <> 0 then c
  else
    let rec go i = if i < 0 then 0 else if a.(i) <> b.(i) then compare b.(i) a.(i) else go (i - 1) in
    go (Array.length a - 1)

One polynomial, written with its terms in decreasing order under each.

open Mpoly

Running it.

lex      -5x^3 + 7x^2z^2 + 4xy^2z + 4z^2
grlex    7x^2z^2 + 4xy^2z - 5x^3 + 4z^2
grevlex  4xy^2z + 7x^2z^2 - 5x^3 + 4z^2
grlex:   xyz^2 > y^3z: true
grevlex: xyz^2 > y^3z: false

More generally, any order can be described by a matrix: compare the vectors $W α$ and $W β$ lexicographically, for a suitable real matrix $W$ . Robbiano showed that every monomial order arises this way^[2]. Weight orders compare a weighted degree first; elimination orders, which make every monomial containing certain variables larger than every monomial without them, are what lex provides for all variables at once.

§ 03

Division depends on the order

Dividing a polynomial by several others means repeatedly cancelling its leading term with a divisor whose leading term divides it. The leading terms, and therefore the quotients and the remainder, depend on the order, and with an arbitrary set of divisors the remainder depends even on the order in which the divisors are tried^[1].

Dividing x²y + xy² + y² by xy − 1 and y² − 1, in both orders, then by a Gröbner basis of the same ideal.

open Mpoly

Running it.

dividing by (xy - 1, y^2 - 1): quotients x + y, 1, remainder x + y + 1
dividing by (y^2 - 1, xy - 1): quotients x + 1, x, remainder 2x + 1
Gröbner basis: x - y, y^2 - 1
remainder by it, in either order: 2y + 1, 2y + 1

The two remainders differ, even though both divisions are correct. With a Gröbner basis as divisor set, the remainder is unique, whatever the order in which the divisors are tried.

§ 04

Which order to use

Reduced Gröbner bases of three ideals under each order, with the number of reduction steps in Buchberger's algorithm.

open Mpoly
 
(* The same ideals under three orders: size of the reduced Gröbner basis
   and the work Buchberger's algorithm does. *)
let largest_digits g = List.fold_left (fun m p -> List.fold_left (fun m (_, c) ->
    max m (String.length (Z.to_string (Z.abs (Q.num c))) + String.length (Z.to_string (Q.den c)) - 1)) m p) 0 g

Running it.

system                  order     basis size  max degree  largest coefficient digits  reductions
circle, parabola, plane lex                3           4                           1           6
circle, parabola, plane grlex              3           2                           1           4
circle, parabola, plane grevlex            3           2                           1           4
three quadrics          lex                3           8                           6         241
three quadrics          grlex              7           4                           2          41
three quadrics          grevlex            6           4                           2          23
a cubic system          lex                3          18                           4        1182
a cubic system          grlex              3           3                           1           0
a cubic system          grevlex            3           3                           1           0

Lex bases have the triangular shape that solves systems, with the last polynomial in a single variable, but their degrees and coefficients are much larger, and computing them costs far more. Grevlex usually gives the smallest bases; Bayer and Stillman explained its advantages through the regularity of ideals^[5]. In the cubic system, the leading terms under the graded orders are pairwise coprime, so the input is already a Gröbner basis and no reduction is needed, while lex requires over a thousand steps. The common strategy is therefore to compute a grevlex basis and convert it: the FGLM algorithm does this by linear algebra for ideals with finitely many solutions^[3], and the Gröbner walk moves through intermediate orders in general^[4].

§ 05

History

Orders on monomials were used implicitly by Macaulay and in the elimination theory of the early twentieth century. Buchberger's thesis of 1965, which introduced Gröbner bases, required a fixed order on terms^[7], and Dickson's lemma of 1913 provided the finiteness argument^[6]. Robbiano classified all monomial orders in 1985^[2], Bayer and Stillman gave the theoretical case for grevlex in 1987^[5], and methods for changing orders, FGLM in 1993 and the Gröbner walk in 1997, made the choice of order a matter of efficiency rather than of the answer needed^[3]^[4].