A Gröbner basis always pertains to a particular order on monomials.
Definition n8. Let \(S\)S be a non-empty set. A binary relation on \(S\)S is a subset \(r\)r of \(S \times S\)S S. The relation \(\Delta(S) = \{(a, a) \mid a \in S\}\)(S) = \(a, a) \mid a \in S\ is the diagonal of \(S\)S. The inverse of \(r\)r is \(r^{-1} = \{(a, b) \mid (b, a) \in r\}\)r -1 = \(a, b) \mid (b, a) \in r\. The strict part of \(r\)r is \(r_s = r \setminus r^{-1}\)r s = r r -1, and the product of \(r\)r and \(u\)u is \[u \circ r = \{(a, c) \mid \text{there is } b \in S \text{ such that } (a, b) \in r \text{ and } (b, c) \in u\}.\]
We use infix notation so that \(a \; r \; b\)a \; r \; b means \((a, b) \in r\)(a, b) r.
Definition ne. Let \(r\)r be a binary relation on \(S\)S. Then \(r\)r is
- transitive if \(r \circ r \subseteq r\)r r r,
- antisymmetric if \(r \cap r^{-1} \subseteq \Delta(S)\)r r -1 (S),
- connex if \(r \cup r^{-1} = S \times S\)r r -1 = S S,
- a linear order on \(S\)S if it is transitive, antisymmetric, and connex.
An element \(a \in R\)a R of a non-empty subset \(R \subseteq S\)R S is minimal if there is no \(b \in R\)b R with \(b \; r_s \; a\)b \; r s \; a. A strictly descending sequence in \(S\)S is an infinite sequence \(a_n \in S\)a n S such that \(a_{n+1} \; r_s \; a_n\)a n+1 \; r s \; a_n for all \(n \in \mathbb{N}_0\)n N 0. The relation \(r\)r is noetherian if every non-empty subset of \(S\)S has a minimal element. A well-order on \(S\)S is a noetherian linear order on \(S\)S.
Proposition dt. A linear order \(\ge\) on \(S\)S is a well-order if and only if there is no strictly descending sequence in \(S\)S.
Proof. We prove the contrapositive: \(\ge\) is not a well-order if and only if there is a strictly descending sequence in \(S\)S. (\(\implies\)) Suppose \(\ge\) is not a well-order. Then there is a non-empty subset \(R \subseteq S\)R S that has no minimal element. We can choose \(a \in R\)a R and since \(a\)a is not the minimal element, we can choose again \(b \in R\)b R such that \(a > b\)a > b, which leads to a strictly descending sequence. (\(\impliedby\)) Suppose there is a strictly descending sequence in \(S\)S. The elements of such a sequence form a non-empty subset \(R\)R of \(S\)S that has no minimal element. Hence, \(\ge\) is not a well-order.
We denote monomial orders by \(\succeq\), their inverses by \(\preceq\), and their strict parts by \(\succ\) and \(\prec\).
We denote by \(\mathcal{M}(x_1, \ldots, x_n)\)M(x 1, , x n) or simply \(\mathcal{M}\)M the set of all monomials in \(x_1, \ldots, x_n\)x 1, , x n. The set \(\mathcal{M}\)M forms an Abelian monoid under multiplication. We can associate any monomial \(x^\alpha \in \mathcal{M}\)x M with its \(n\)n-tuple of exponents \(\alpha \in \mathbb{N}_0^n\) N 0 n in a one-to-one fashion, so we use \(\mathcal{M}\)M and \(\mathbb{N}_0^n\)N 0 n interchangeably.
Definition nj. A monomial order \(\succeq\) is a well-order on \(\mathcal{M}\)M that satisfies the property of respecting multiplication: if \(m_1 \succeq m_2\)m 1 m 2, then \(n \cdot m_1 \succeq n \cdot m_2\)n m 1 n m 2 for all \(m_1, m_2, n \in \mathcal{M}\)m 1, m 2, n M.
The property of respecting multiplication ensures that the relative ordering of monomials in a polynomial does not change when we multiply the polynomial by a monomial. This is necessary for the division algorithm.
Definition nk. Let \(x^\alpha, x^\beta \in \mathcal{M}(x_1, \ldots, x_n)\)x , x \mathcalM(x_1, \ldots, x_n) be monomials. We say \(x^\alpha \succeq_{\mathrm{lex}} x^\beta\)x lex x^\beta if \(\alpha = \beta\) = or if there is \(1 \le i \le n\)1 i n such that \(\alpha_j = \beta_j\) j = j for \(1 \le j < i\)1 j < i and \(\alpha_i > \beta_i\) i > i. This is the lexicographic order.
Remark nm. The strict part \(\succ_{\mathrm{lex}}\) lex compares the exponent \(n\)n-tuples so that \(x^\alpha \succ_{\mathrm{lex}} x^\beta\)x lex x^\beta if the left-most non-zero component of \(\alpha - \beta\) - is positive. The lexicographic order depends on how the variables \(x_1, x_2, \ldots, x_n\)x 1, x 2, , x_n are ordered. In general, there are \(n!\)n! ways to order \(n\)n variables and each has its respective lexicographic order. We assume the standard order \(x_1 > x_2 > \cdots > x_n\)x 1 > x 2 > > x_n, or the alphabetical order \(x > y > z\)x > y > z.
- Let \(xy^2z^3\)xy 2z 3 and \(xy^3\)xy 3 be monomials in \(\mathcal{M}(x, y, z)\)M(x, y, z). Then \(xy^3 \succ_{\mathrm{lex}} xy^2z^3\)xy 3 lex xy^2z^3 since for \(i = 2\)i = 2 we have \(\alpha_1 = \beta_1\) 1 = 1 and \(\alpha_2 > \beta_2\) 2 > 2, where \(\alpha = (1, 3, 0)\) = (1, 3, 0) and \(\beta = (1, 2, 3)\) = (1, 2, 3).
- With variables ordered \(x > y > z\)x > y > z, we get \(x \succ_{\mathrm{lex}} y \succ_{\mathrm{lex}} z\)x lex y {\mathrm{lex}} z.
- A monomial containing the most significant variable is greater than any monomial that does not. For instance, \(x \succ_{\mathrm{lex}} y^3 z^2\)x lex y 3 z^2 in \(\mathcal{M}(x, y, z)\)M(x, y, z).
The intuition behind the lexicographic order is that it looks for the most significant variable that appears in one of the monomials and gives preference to the monomial in which this variable has greater power.
Proposition np. The lexicographic order \(\succeq_{\mathrm{lex}}\) lex on \(\mathcal{M}\)M is a monomial order.
Proof. Following the definition of the lexicographic order and the fact that the regular numerical order on \(\mathbb{N}_0\)N 0 is a linear order, it is straightforward to show that for any monomials \(x^\alpha, x^\beta, x^\gamma \in \mathcal{M}(x_1, \ldots, x_n)\)x , x , x^ \in \mathcalM(x_1, \ldots, x_n), transitivity, antisymmetry, and connexity hold. These properties show that \(\succeq_{\mathrm{lex}}\) lex is a linear order on \(\mathcal{M}\)M.
Let us prove the property of respecting multiplication. If \(x^\alpha \succeq_{\mathrm{lex}} x^\beta\)x lex x^\beta, then either \(\alpha = \beta\) = , or there is \(1 \le i \le n\)1 i n such that \(\alpha_i - \beta_i > 0\) i - i > 0 with \(\alpha_j = \beta_j\) j = j for \(1 \le j < i\)1 j < i. Also, \(x^\alpha \cdot x^\gamma = x^{\alpha + \gamma}\)x x = x^\alpha + \gamma and \(x^\beta \cdot x^\gamma = x^{\beta + \gamma}\)x x = x^\beta + \gamma. Comparing the results gives \((\alpha + \gamma) - (\beta + \gamma) = \alpha - \beta\)( + ) - ( + \gamma) = \alpha - \beta and we see that \(\alpha_i - \beta_i > 0\) i - i > 0 with \(\alpha_j = \beta_j\) j = j for \(1 \le j < i\)1 j < i again; or if \(\alpha = \beta\) = , then \(\alpha + \gamma = \beta + \gamma\) + = + \gamma. This shows that \(x^{\alpha + \gamma} \succeq_{\mathrm{lex}} x^{\beta + \gamma}\)x + \mathrmlex}} x^{\beta + \gamma}.
The last part is to show that \(\succeq_{\mathrm{lex}}\) lex is noetherian. By Proposition dt, if \(\succeq_{\mathrm{lex}}\) lex is not a well-order, then there is a strictly decreasing sequence \(x^{\alpha_{(1)}} \succ_{\mathrm{lex}} x^{\alpha_{(2)}} \succ_{\mathrm{lex}} \cdots\)x (1) _{{lex}} x^{\alpha_{(2)}} \succ_{\mathrm{lex}} \cdots of elements in \(\mathcal{M}(x_1, \ldots, x_n)\)M(x 1, , x n). By the definition of \(\succeq_{\mathrm{lex}}\) lex, there exists a \(j\)j such that all the first components of the \(n\)n-tuples \(\alpha_{(k)}\) (k) with \(k \ge j\)k j are equal. Continuing further, there is an \(l \ge j\)l j such that all the second components of the \(n\)n-tuples \(\alpha_{(m)}\) (m) with \(m \ge l\)m l are all equal. We see that there must be a \(p \ge l\)p l for which the whole \(n\)n-tuples \(\alpha_{(p)} = \alpha_{(p+1)} = \cdots\) (p) = (p+1) = are all equal. This means that the sequence is not strictly decreasing, a contradiction.
Definition nq. Let \(x^\alpha, x^\beta \in \mathcal{M}(x_1, \ldots, x_n)\)x , x \mathcalM(x_1, \ldots, x_n) be monomials. We say \(x^\alpha \succeq_{\mathrm{rclex}} x^\beta\)x rclex x^\beta if \(\alpha = \beta\) = or if there is \(1 \le i \le n\)1 i n such that \(\alpha_j = \beta_j\) j = j for \(i < j \le n\)i < j n and \(\alpha_i < \beta_i\) i < i. This is the reverse colexicographic order.
The strict part \(\succ_{\mathrm{rclex}}\) rclex compares the exponent \(n\)n-tuples so that \(x^\alpha \succ_{\mathrm{rclex}} x^\beta\)x rclex x^\beta if the right-most non-zero component of \(\alpha - \beta\) - is negative. Remark nm about variable ordering applies here as well.
- Let \(xy^2z^3\)xy 2z 3 and \(xy^3\)xy 3 be monomials in \(\mathcal{M}(x, y, z)\)M(x, y, z). Then \(xy^3 \succ_{\mathrm{rclex}} xy^2z^3\)xy 3 rclex xy^2z^3 as well, but for a different reason: for \(i = 3\)i = 3 we have \(\alpha_3 < \beta_3\) 3 < 3, where \(\alpha = (1, 3, 0)\) = (1, 3, 0) and \(\beta = (1, 2, 3)\) = (1, 2, 3).
- The lexicographic and reverse colexicographic orders coincide for monomials in one and two variables. They may differ for three or more variables: \(xz \succ_{\mathrm{lex}} y^2\)xz lex y 2 but \(y^2 \succ_{\mathrm{rclex}} xz\)y 2 rclex xz in \(\mathcal{M}(x, y, z)\)M(x, y, z).
The intuition behind the reverse colexicographic order is that it looks for the least significant variable that appears in one of the monomials and gives preference to the monomial in which this variable has lesser power. It can be thought of as a double reversal of the lexicographic order. The reverse colexicographic order is a linear order but not a well-order, as witnessed by the strictly descending sequence \[x_1 x_2 \succ_{\mathrm{rclex}} x_1 x_2^2 \succ_{\mathrm{rclex}} x_1 x_2^3 \succ_{\mathrm{rclex}} \cdots\] and therefore it is not a monomial order.
Examples nc and nx show that the lexicographic and reverse colexicographic orders do not take the total degree of monomials into account. In certain cases, it is desirable to order monomials by total degree.
Definition no. Let \(x^\alpha, x^\beta \in \mathcal{M}(x_1, \ldots, x_n)\)x , x \mathcalM(x_1, \ldots, x_n) be monomials. We say \(x^\alpha \succeq_{\mathrm{grlex}} x^\beta\)x grlex x^\beta if \(\lvert x^\alpha \rvert > \lvert x^\beta \rvert\) x > \lvert x \beta \rvert, or \(\lvert x^\alpha \rvert = \lvert x^\beta \rvert\) x = \lvert x \beta \rvert and \(x^\alpha \succeq_{\mathrm{rclex}} x^\beta\)x rclex x^\beta. This is the graded reverse lexicographic order.
Despite its name, the graded reverse lexicographic order makes use of the reverse colexicographic order.
- \(y^2 \succeq_{\mathrm{grlex}} x\)y 2 grlex x since \(\lvert y^2 \rvert = 2 > \lvert x \rvert = 1\) y 2 = 2 > x \rvert = 1. Also, \(y^2 \succeq_{\mathrm{grlex}} xz\)y 2 grlex xz since \(\lvert xz \rvert = \lvert y^2 \rvert\) xz = y 2 \rvert and \(y^2 \succeq_{\mathrm{rclex}} xz\)y 2 rclex xz.
- \(x \succeq_{\mathrm{grlex}} y \succeq_{\mathrm{grlex}} z\)x grlex y {\mathrm{grlex}} z since all have the same total degree and \(x \succeq_{\mathrm{rclex}} y \succeq_{\mathrm{rclex}} z\)x rclex y {\mathrm{rclex}} z.
Proposition n1. The graded reverse lexicographic order \(\succeq_{\mathrm{grlex}}\) grlex on \(\mathcal{M}\)M is a monomial order.
Proof. Since \(\succeq_{\mathrm{grlex}}\) grlex first uses the usual well-order on the total degree \(\lvert x^\alpha \rvert \in \mathbb{N}_0\) x \in \mathbbN 0 and, when \(\lvert x^\alpha \rvert = \lvert x^\beta \rvert\) x = \lvert x \beta \rvert, decides ties using the reverse colexicographic order (which is a linear order), \(\succeq_{\mathrm{grlex}}\) grlex is also linear. It is also a well-order since the strict part \(\succ_{\mathrm{grlex}}\) grlex is solely the well-order on \(\lvert x^\alpha \rvert \in \mathbb{N}_0\) x \in \mathbbN 0.
To show the property of respecting multiplication, consider monomials \(x^\alpha, x^\beta, x^\gamma \in \mathcal{M}(x_1, \ldots, x_n)\)x , x , x^ \in \mathcalM(x_1, \ldots, x_n). We have \(x^\alpha \cdot x^\gamma = x^{\alpha + \gamma}\)x x = x^\alpha + \gamma and \(x^\beta \cdot x^\gamma = x^{\beta + \gamma}\)x x = x^\beta + \gamma. Assume \(x^\alpha \succeq_{\mathrm{grlex}} x^\beta\)x grlex x^\beta. If \(\lvert x^\alpha \rvert > \lvert x^\beta \rvert\) x > \lvert x \beta \rvert, then \(x^{\alpha + \gamma} \succ_{\mathrm{grlex}} x^{\beta + \gamma}\)x + \mathrmgrlex}} x^{\beta + \gamma} since \(\lvert x^{\alpha + \gamma} \rvert = \lvert x^\alpha \rvert + \lvert x^\gamma \rvert > \lvert x^\beta \rvert + \lvert x^\gamma \rvert = \lvert x^{\beta + \gamma} \rvert\) x + \rvert = \lvert x \alpha \rvert + \lvert x^\gamma \rvert > \lvert x^\beta \rvert + \lvert x^\gamma \rvert = \lvert x^\beta + \gamma \rvert. If \(\lvert x^\alpha \rvert = \lvert x^\beta \rvert\) x = \lvert x \beta \rvert, we get \(\lvert x^{\alpha + \gamma} \rvert = \lvert x^{\beta + \gamma} \rvert\) x + \rvert = \lvert x \beta + \gamma \rvert and use the reverse colexicographic order. Since \(x^\alpha \succeq_{\mathrm{rclex}} x^\beta\)x rclex x^\beta, either \(\alpha = \beta\) = , or there is \(1 \le i \le n\)1 i n such that \(\alpha_i - \beta_i < 0\) i - i < 0 with \(\alpha_j = \beta_j\) j = j for \(i < j \le n\)i < j n. As in the proof of Proposition np, \((\alpha + \gamma) - (\beta + \gamma) = \alpha - \beta\)( + ) - ( + \gamma) = \alpha - \beta, so \(x^{\alpha + \gamma} \succeq_{\mathrm{grlex}} x^{\beta + \gamma}\)x + \mathrmgrlex}} x^{\beta + \gamma}.
Definition nu. Let \(x^\alpha, x^\mathrm{A} \in \mathcal{M}(x_1, \ldots, x_n)\)x , x A \mathcalM(x_1, \ldots, x_n) and \(y^\beta, y^\mathrm{B} \in \mathcal{M}(y_1, \ldots, y_m)\)y , y B \mathcalM(y_1, \ldots, y_m) be monomials, \(\succeq_1\) 1 a monomial order on \(\mathcal{M}(x_1, \ldots, x_n)\)M(x 1, , x n), and \(\succeq_2\) 2 a monomial order on \(\mathcal{M}(y_1, \ldots, y_m)\)M(y 1, , y m). We say \(x^\alpha y^\beta \succeq_{1,2} x^\mathrm{A} y^\mathrm{B}\)x y _1,2 x^\mathrmA y^\mathrm{B} on \(\mathcal{M}(x_1, \ldots, x_n, y_1, \ldots, y_m)\)M(x 1, , x n, y_1, , y_m) if \(x^\alpha \succ_1 x^\mathrm{A}\)x 1 x^A, or \(x^\alpha = x^\mathrm{A}\)x = x A and \(y^\beta \succeq_2 y^\mathrm{B}\)y 2 y^B. This is the block order.
Note that \(x^\alpha \succ_1 x^\mathrm{A}\)x 1 x^A implies \(x^\alpha y^\beta \succeq_{1,2} x^\mathrm{A} y^\mathrm{B}\)x y _1,2 x^\mathrmA y^\mathrm{B}. In combination with Gröbner bases, this allows the elimination of variables \(x_1, \ldots, x_n\)x 1, , x n from a system of polynomials.