Monthly Archives: January 2011

Every monomial generating set is a Gröbner basis

Let I \subseteq F[x_1,\ldots,x_n] be a monomial ideal with monomial generating set G = \{g_1,\ldots,g_m\}. Use Buchberger’s Criterion to show that G is a Gröbner basis for I.


Let i < j. Recall that S(g_i,g_j) = \frac{M}{LT(g_i)} g_i - \frac{M}{LT(g_j)} g_j, where M is a least common multiple of g_i and g_j. Since the g_i are monomials, we have LT(g_i) = g_i. So in fact S(g_i,g_j) = \frac{M}{g_i}g_i - \frac{M}{g_j} g_j = M - M = 0.

Certainly I \neq 0; since S(g_i,g_j) = 0 for all i < j, by Buchberger’s criterion we have that G is a Gröbner basis for I.

Every monomial generating set is a Gröbner basis

Let F be a field. Suppose I \subseteq F[g_1,\ldots,g_n] is a monomial ideal with monomial generating set G = \{g_1,\ldots,g_m\}. Prove that G is a Gröbner basis for I.


Recall that LT(I) = (LT(p) \ |\ p \in I). Let p \in LT(I), with p = \sum a_i LT(p_i). In particular, each LT(p_i) is in (g_j) for some j, so that p \in I. Hence LT(I) \subseteq I. Conversely, we have g_i = LT(g_i) \in LT(I) for each i. Thus I = LT(I). Since LT(I) = (g_1, \ldots, g_m) = (LT(g_1), \ldots, LT(g_m)), G is a Gröbner basis of I.

A criterion for inclusion in LT(I)

Fix a monomial order on R = F[x_1, \ldots, x_n] and suppose G = \{g_1, \ldots,g_m\} is a Gröbner basis for the ideal I in R. Prove that h \in LT(I) if and only if h is a sum of monomials each divisible by some LT(g_i).


Since G is a Gröbner basis, we have LT(I) = (LT(g_1), \ldots, LT(g_m)). Thus LT(I) is a monomial ideal with monomial generators LT(g_i). By this previous exercise, h \in LT(I) if and only if each term in h is divisible by some LT(g_i).

A criterion for inclusion in a monomial ideal

Let I = (m_i \ | i \in I) be a monomial ideal in F[x_1,\ldots,x_n]. Prove that p \in I if and only if each term in p is divisible by some m_i. Use this criterion to show that p = x^2yz + 3xy^2 is in (xyz, y^2) but not in (xz^2, y^2).


Certainly, if each term in p is divisible by some m_i then p \in I. Suppose now that p \in I. We have p = \sum a_im_i, where a_i = \sum n_{i,j}. (each n_{i,j} is a monomial.) Then p = \sum_i \sum_j n_{i,j}m_i. Thus each term in p is divisible by some m_i.

Now let p = x^2yz + 3xy^2. Since x^2yz = x(xyz) and 3xy^2 = 3x(y^2), p \in (xyz, y^2). However, since xz^2 does not divide either x^2yz or 3xy^2, p \notin (xz^2, y^2).

Alternate characterizations of the lex and grlex orders

It can be shown that every m-order on \mathbb{N}^k may be obtained as follows.

Let m \leq k, and let \mathcal{B} = \{v_i\}_{i=1}^m be a set of pairwise orthogonal elements of \mathbb{R}^k such that the coordinates of v_1 are all nonnegative. (Recall that (a_i) and (b_i) are called orthogonal if (a_i) \cdot (b_i) = \sum a_ib_i = 0.) Now define a relation \sigma = \sigma_\mathcal{B} as follows: let (a_i), (b_i) \in \mathbb{N}^k and let S = \{i \ |\ v_i \cdot a \neq v_i \cdot b \}. We say that (a_i) \sigma (b_i) if S is empty or if S is nonempty with minimal element t and v_t \cdot a > v_t \cdot b. It turns out that \sigma_\mathcal{B} is an m-order, and that every m-order is equal to \sigma_\mathcal{B} for some \mathcal{B}.

  1. Let \mathcal{B} = \{e_i\}_{i=1}^k, where e_{i,j} = 1 if i = j and 0 otherwise. Prove that \sigma_\mathcal{B} is the lex order with respect to x_1 < x_2 < \ldots < x_k.
  2. Let \mathcal{B} = \{v_i\}_{i=1}^k, where v_{1,j} = 1 for all j and if i > 1, v_{i,j} = 1 if j \leq k-i+1, i-1-k if j = k-i+2, and 0 otherwise for i \geq 2. Prove that \sigma_\mathcal{B} is the grevlex order with respect to \{x_1, x_2, \ldots , x_k \}.

  1. First we will show that the elements of \mathcal{B} are pairwise orthogonal. To that end, suppose s \neq t, and consider e_s \cdot e_t = \sum e_{s,i}e_{t,i}. If i \neq s,t, then e_{s,i} = e_{t,i} = 0. If i = s, then e_{t,i} = 0, and if i = t, then e_{s,i} = 0. Thus e_s \cdot e_t = 0 as desired.

    Now suppose (a_i) \sigma (b_i). If S = \{t \ |\ e_t \cdot a \neq e_t \cdot b \} is empty, then in fact e_t \cdot a = e_t \cdot b for all t. Now e_t \cdot a = \sum e_{t,i}a_i = a_t, and likewise e_t \cdot b = b_t. So a = b. Suppose instead that S is nonempty with minimal element m. Then for all t < m, we have a_t = b_t, and a_m > b_m. Thus (a_i) \geq (b_i) with respect to the lex order.

    Now suppose (a_i) \geq (b_i) with respect to the lex order. If a_t = b_t for all t, we have e_t \cdot a = e_t \cdot b for all t, so that a_t = b_t for all t. Thus a \sigma b. Otherwise, if m is minimal such that a_m \neq b_m, we have a_m > b_m. In fact, e_m \cdot a > e_m \cdot b, and thus a \sigma b.

  2. First we will show that the elements of \mathcal{B} are pairwise orthoigonal. To that end, suppose s \neq t and consider v_s \cdot v_t = \sum v_{s,i} v_{t,i}. Without loss of generality, there are two cases. If s = 1, then we have v_s \cdot v_t = \sum v_{s,i} v_{t,i} = \sum v_{t,i} = \sum_{i=1}^{k-t+1} + (t-1-k) = 0. If 1 < s < t, then v_s \cdot v_t = \sum v_{s,i}v_{t,i} = \sum_{i=1}^{k-t+1} + (t-1-k) = 0.

    Now we show that this \sigma_\mathcal{B} is equivalent to the natural grlex order.

    Suppose (a_i) \sigma (b_i). If S = \{t \ |\ v_t \cdot a \neq v_t \cdot b \} is empty, then we have v_t \cdot a = v_t \cdot b for all t. We claim that a = b. To see this, we proceed by induction on the entries a_t, b_t in reverse order. For the base case, since v_1 \cdot a = v_1 \cdot b, we have \sum_{i=1}^k a_i = \sum_{i=1}^k b_i. Since v_2 \cdot a = v_2 \cdot b, we have \sum_{i=1}^{k-1} a_i - (k-1)a_k = \sum_{i=1}^{k-1} b_i - (k-1)b_k. Subtracting one equation from the other, we see that ka_k = kb_k, and thus a_k = b_k. Suppose now that a_t = b_t for all 2 \leq m < t \leq k. Since v_{k-m+2} \cdot a = v_{k-m+2} \cdot b, we have \sum_{i=1}^{m-1} a_i - (1-m)a_m = \sum_{i=1}^{m-1} b_i - (1-m)b_m. Again subtracting from v_1 \cdot a = v_1 \cdot b, we see that (1-m)a_m = (1-m)b_m, so that a_m = b_m. So a_t = b_t for all 2 \leq t \leq k, we easily see that a_1 = b_1 from v_1 \cdot a = v_2 \cdot b. Thus a = b, and so a \geq b with respect to the grlex order. Supppose instead that S is nonempty with minimal element m. Then v_t \cdot a = v_t \cdot b for all t < m, and v_m \cdot a > v_m \cdot b. If m = 1, then we see that \sum a_i > \sum b_i, so that a has greater total degree than b$. If m > 1, then a and b have the same total degree. By an adaptation of the induction proof we used above, we see that a_t = b_t for all m < t \leq k. Moreover, we have \sum_{i=1}^{m-1} a_i - (1-m)a_m > \sum_{i=1}^{m-1} b_i - (1-m)b_m; subtracting from v_1 \cdot a = v_1 \cdot b, we see that (1-m)a_m > (1-m)b_m, and since m > 1, a_m < b_m. Thus a \geq b with respect to the natural grevlex order.

    Conversely, suppose a \geq b with respect to the natural grevlex order. If \sum a_i > \sum b_i, then v_1 \cdot a > v_1 \cdot b, and so a \sigma b. Suppose instead that \sum a_i = \sum b_i and that m is maximal such that a_m < b_m (and a_t = b_t for all m < t \leq k). Certainly we have v_1 \cdot a = v_1 \cdot b. Again by a straightforward induction argument, we have v_t \cdot a = v_t \cdot b for all m < t \leq k. Finally, since a_m < b_m, we have (1-m)a_m > (1-m)b_m, so that (v_m \cdot a) - (v_1 \cdot a) > (v_m \cdot b) - (v_1 \cdot b), and thus v_m \cdot a > v_m \cdot b. Hence a \sigma b.

There are k! distinct lex, grlex, and grevlex orders on a polynomial ring in k indeterminates

Prove that there are k! distinct lex orders on F[x_1,\ldots,x_k]. Show similarly that there are k! distinct grlex and grevlex orders.


Each lex (and grlex and grevlex) order on F[x_1,\ldots,x_k] is (by definition) induced by a linear order of the indeterminates x_1, \ldots, x_k. Each linear order of [1,k] certainly corresponds to a permutation, so that there are at most |S_k| = k! distinct lex (and grlex and grevlex) orders. It remains to be shown that distinct permutations \tau \in S_k induce distinct monomial orders.

Suppose >_1 and >_2 are distinct linear orders of [1,k]. That is, there exist a,b \in [1,k] such that x_a >_1 x_b and x_b >_2 x_a. We immediately see that the lex, grlex, and grevlex orders induced by >_1 and >_2 are distinct, as those orders coincide with >_1 and >_2 on the set \{x_1, \ldots, x_k\}.

Sort a list of monomials by the lex, grlex, and grevlex orders

Sort the monomials x^2z, x^2y^2z, xy^2z, x^3y, x^3z^2, x^2, x^2yz^2, and x^2z^2 by the lex, grlex, and grevlex monomial orders with respect to the order x > y > z.


By the lex order:

  • x^3y > x^3z since these monomials have the same x degree, but the left monomial has larger y degree
  • x^3z^2 > x^2y^2z since the left monomial has larger x degree
  • x^2y^2z > x^2yz^2 since these monomials have the same x degree, but the left monomial has larger y degree
  • x^2yz^2 > x^2z^2 since these monomials have the same x degree, but the left monomial has larger y degree
  • x^2z^2 > x^2z since these monomials have the same x and y degrees, but the left monomial has larger z degree
  • x^2z > x^2 since these monomials have the same x and y degrees, but the left monomial has larger z degree
  • x^2 > xy^2z since the left monomial has larger x degree

By the grlex order:

  • x^2z^2 > x^2y^2z since these monomials have the same total degree, but the left monomial has larger x degree
  • x^2y^2z > x^2yz^2 since these monomials have the same total degree and the same x degree, but the left monomial has larger y degree
  • x^2yz^2 > x^3y since the left monomial has larger total degree
  • x^3y > x^2z^2 since these monomials have the same total degree, but the left monomial has larger x degree
  • x^2z^2 > xy^2z since these monomials have the same total degree, but the left monomial has larger x degree
  • xy^2z > x^2z since the left monomial has larger total degree
  • x^2z > x^2 since the left monomial has larger total degree

By the grevlex order:

  • x^2y^2 > x^3z^2 since these monomials have the same total degree, but the left monomial has smaller z degree
  • x^3z^2 > x^2yz^2 since these monomials have the same total degree and the same z degree, but the left monomial has smaller y degree
  • x^2yz^2 > x^3y since the left monomial has larger total degree
  • x^3y > xy^2z since these monomials have the same total degree, but the left monomial has smaller z degree
  • xy^2z > x^2z^2 since these monomials have the same total degree, but the left monomial has smaller z degree
  • x^2z^2 > x^2z since the left monomial has larger total degree
  • x^2z > x^2 since the left monomial has larger total degree

Sort a given list of monomials by the lex, grlex, and grevlex monomial orders

Sort the monomials x^3y, x^3z^2, x^3z, x^2y^2z, x^2y, xz^2, y^2z^2, and y^2z with respect to the lex, grlex, and grevlex orders induced by x > y > z.


Using the lexicographic order:

  1. x^3y > x^3z^2 since these monomials have the same x-degree, but the left monomial has larger y-degree.
  2. x^3z^2 > x^3z since these monomials have the same x– and y-degrees, but the left monomial has larger z-degree.
  3. x^3z > x^2y^2z since the left monomial has larger x-degree.
  4. x^2y^2z > x^2y since these monomials have the same x-degree, but the left monomial has larger y-degree.
  5. x^2y > xz^2 since the left monomial has larger x-degree.
  6. xz^2 > y^2z^2 since the left monomial has larger x-degree.
  7. y^2z^2 > y^2z since these monomials have the same x– and y-degrees, but the left monomial has larger z-degree.

Using the grlex order:

  1. x^3z^2 > x^2y^2z since these monomials have the same total degree, but the left monomial has larger x-degree.
  2. x^2y^2z > x^3y since the left monomial has larger total degree.
  3. x^3y > x^3z since these monomials have the same total degree and the same x-degree, but the left monomial has larger y-degree.
  4. x^3z > y^2z^2 since these monomials have the same total degree, but the left monomial has larger x-degree.
  5. y^2z^2 > x^2y since the left monomial has larger total degree.
  6. x^2y > xz^2 since these monomials have the same total degree, but the left monomial has larger x-degree.
  7. xz^2 > y^2z since these monomials have the same total degree, but the left monomial has larger x-degree.

Using the grevlex order:

  1. x^2y^2z > x^3z^2 since these monomials have the same total degree, but the left monomial has smaller z-degree.
  2. x^3z^2 > x^3y since the left monomial has larger total degree.
  3. x^3y > x^3z since these monomials have the same total degree, but the left monomial has smaller z-degree.
  4. x^3z > y^2z^2 since these monomials have the same total degree, but the left monomial has smaller z-degree.
  5. y^2z^2 > x^2y since the left monomial has larger total degree.
  6. x^2y > y^2z since these monomials have the same total degree, but the left monomial has smaller z-degree.
  7. y^2z > xz^2 since these monomials have the same total degree, but the left monomial has smaller z-degree.

Reversed lexicographical monomial orders

Let k be a positive natural number and let \tau \in S_n. Define a relation \leq_\tau on \mathbb{N}^k by (a_i) \leq (b_i) if the set \{ i \in [1,k] \ |\ a_{\tau(i)} \neq b_{\tau(i)} \} is empty or, if nonempty with maximal element k, we have a_{\tau(k)} < b_{\tau(k)}.

  1. Prove that the grading of \leq_\tau is an m-order. (See this previous exercise. Note that \leq_\tau itself is not an m-order since, for example, (1) > (2) > (3) > \ldots is a chain with no lower bound.) Let e_i = (e_{i,j}) where e_{i,j} = 1 if i = j and 0 otherwise. Prove that if i < j, then e_i > e_j.

A monomial ordering induced by the grading of some \leq_\tau is called a grevlex monomial order. (See this previous exercise.)

  1. Show that the grevlex ordering and the grlex ordering on F[x,y] with respect to x > y are the same. Prove that the grevlex ordering on F[x,y,z] is not the grading of any lexicographic ordering.
  2. Sort xy^2z, x^2z^2, y^2z^2, yz^2, xy, y^2, xz, z^2, x, and y under the grevlex ordering with respect to x > y > z.

We begin with a lemma.

Lemma: Let \leq be a linear order on \mathbb{N}^k which respects addition. Then the grading of \leq, denoted \leq_g, is an m-order. Proof: Certainly \leq_g is linear and respects addition; it remains to be seen that \leq_g is well-founded. To that end, let S \subseteq \mathbb{N}^k be a nonempty subset. Let A \subseteq S consist of those elements (a_i) such that \sum a_i is minimal. Certainly then every element of A is less than every element of S that is not in A with respect to \leq_g. Moreover, A is necessarily finite and thus contains a minimal element, which is minimal in S. \square

With this lemma in mind, we need to show that \leq_\tau is a linear order which respects addition.

  1. (Reflexive) Certainly the set \{ i \ |\ a_{\tau(i)} \neq a_{\tau(i)} \} is empty. Thus (a_i) \leq_\tau (a_i).
  2. (Antisymmetric) Suppose (a_i) \leq_\tau (b_i) and (b_i) \leq_\tau (a_i). If \{ i \ |\ a_{\tau(i)} \neq b_{\tau(i)} \} is empty, then we have (a_i) = (b_i). Suppose now that this set is nonempty with maximal element k; then we must have a_k > b_k > a_k, a contradiction.
  3. (Transitive) Suppose (a_i) \leq_\tau (b_i) and (b_i) \leq_\tau (c_i). If either of \{ i \ |\ a_{\tau(i)} \neq b_{\tau(i)} \} and \{ i \ |\ b_{\tau(i)} \neq c_{\tau(i)} \} is empty, then either (a_i) = (b_i) or (b_i) = (c_i) and certainly (a_i) \leq_\tau (c_i). Suppose both are nonempty with maximal elements k and \ell, respectively. Now a_{\tau(k)} < b_{\tau(k)} and b_{\tau(\ell)} < c_{\tau(\ell)}, and certainly a_{\tau(i)} = b_{\tau(i)} and b_{\tau(j)} = c_{\tau(j)} for i > k and j > \ell. If k \geq \ell, then k is maximal in the nonempty set \{ i \ |\ a_{\tau(i)} \neq c_{\tau(i)} \}, and we have a_{\tau(k)} < b_{\tau(k)} = c_{\tau(k)}. Similarly if \ell \geq k.
  4. (Total) Let (a_i) and (b_i) \in \mathbb{N}^k. If \{ i \ |\ a_{\tau(i)} \neq b_{\tau(i)} \} is empty, then (a_i) = (b_i). If this set is nonempty, then it has a maximal element k. Either a_{\tau(k)} > b_{\tau(k)} or a_{\tau(k)} < b_{\tau(k)}.
  5. (Respects addition) Let (a_i) \leq_\tau (b_i). If a_i = b_i for all i, then certainly (a_i) + (c_i) \leq_\tau (b_i) + (c_i). If there exists a maximal k such that a_{\tau(k)} > b_{\tau(k)}, then we also have k maximal such that a_{\tau(k)} + c_{\tau(k)} > b_{\tau(k)} + c_{\tau(k)}. Thus (a_i) + (c_i) \leq_\tau (b_i) + (c_i).

Thus the grading of \leq_\tau is an m-order on \mathbb{N}^k. With e_i defined as above, if i < j, \sum e_{i,k} = \sum e_{j,k} and j is maximal in \{ t \ |\ e_{i,t} \neq e_{j,t} \}. Since e_{i,j} = 0 and e_{j,j} = 1, we have e_i > e_j.

Let \leq_1 and \leq_2 denote the grevlex and grlex orders on \mathbb{N}^2, respectively. Suppose (a_1,b_1) >_1 (a_2,b_2). If a_1+b_1 > a_2 + b_2, then (a_1,b_1) \geq_2 (a_2,b_2). If a_1 + b_1 = a_2 + b_2, then we have b_1 < b_2$, as otherwise b_1 = b_2 and a_1 = a_2. Then a_1 > a_2, and thus (a_1,b_1) \geq_2 (a_2,b_2). Thus \leq_1 \subseteq \leq_2. Now suppose (a_1,b_1) >_2 (a_2,b_2). Again, if a_1 + b_1 > a_2 + b_2 then (a_1,b_1) >_1 (a_2,b_2). If a_1 + b_1 = a_2 + b_2, then we have a_1 > a_2. Thus b_2 = (a_1 - a_2) + b_1 > b_1, and we have (a_1,b_1) >_1 (a_2,b_2). Thus \leq_2 \subseteq \leq_1. Hence the grevlex and grlex orders on \mathbb{N}^2 are the same.

There are six distinct lexicographic orders on \mathbb{N}^3; one for each permutation of \{1,2,3\}. We will let \leq_{(a,b,c)} denote the lexicographic order which looks at the a coordinate first, then b, then c. Let \leq denote the grevlex order (with respect to the identity permutation of the indices). Note that (1,1,0) > (0,1,1). However, (0,1,1) >_{3,1,2}, >_{3,2,1} (1,1,0). Similarly, (2,0,0) > (0,1,1) but (0,1,1) >_{2,1,3}, >_{2,3,1} (2,0,0), and (0,2,0) > (1,0,1) while (1,0,1) >_{1,2,3}, >_{1,3,2} (0,2,0). So the grevlex order on \mathbb{N}^3 is not the grading of any lexicographic order.

Finally, let \leq denote the grevlex order on F[x,y,z] with respect to x > y > z and note the following.

  • xy^2z > x^2z^2 since the total degrees are the same and \mathsf{deg}(z) = 1 < 2 = \mathsf{deg}(z^2).
  • x^2z^2 > y^2z^2 since the total degrees are the same, the z-degrees agree, and the y-degree on the left is zero and on the right is 2.
  • y^2z^2 > yz^2 since the total degree on the left is 4 while on the right is 3.
  • yz^2 > xy since the total degree on the left is 3 while on the right is 2.
  • xy > y^2 since the total degrees are the same, the z-degrees are the same, and the y degree is smaller on the left.
  • y^2 > xz since the total degrees are the same and the z-degree is smaller on the left.
  • xz > z^2 since the total degrees are the same and the z-degree is smaller on the left.
  • z^2 > x since the total degree is larger on the left.
  • x > y since the total degrees are the same, the z-degrees are the same, and the y degree is smaller on the left.

The grading of a monomial order

Let F be a field, k a positive natural number, and let \leq be an m-order on \mathbb{N}^k with induced monomial order \leq on M(F,k). Define the relation \leq_g on \mathbb{N}^k by (a_i) \geq_g (b_i) if and only if either \sum a_i > \sum b_i or \sum a_i = \sum b_i and (a_i) \geq (b_i).

  1. Prove that \leq_g is an m-order. (See this previous exercise.)
  2. A grading of a lexicographic monomial ordering is called a grlex monomial order. Sort the monomials y^4, x^2y, xy^2, y^2, and x with respect to the lexicographic ordering and the grevlex ordering (both with x > y).

To show that \geq_g is an m-order, we need to show that it is reflexive, antisymmetric, transitive, and total, that every nonempty subset of \mathbb{N}^k has a minimal element, and that \geq_g respects addition.

  1. (Reflexive) For all \alpha = (a_i) \in \mathbb{N}^k, certainly \sum a_i = \sum a_i. Thus \alpha \geq_g \alpha.
  2. (Antisymmetric) Suppose \alpha = (a_i) \geq_g (b_i) \beta and \beta \geq_g \alpha. Note that it must be the case that \sum a_i = \sum b_i, and so also \alpha \geq \beta \geq \alpha. Thus \alpha = \beta.
  3. (Transitive) Suppoe \alpha = (a_i) \geq (b_i) = \beta and \beta \geq (c_i) = \gamma. If the sums \sum a_i, \sum b_i, and \sum c_i are not all equal, then \alpha \geq_g \gamma. If all three sums are equal, then in fact \alpha \geq \beta and \beta \geq \gamma, so that \alpha \geq \gamma.
  4. (Total) Let \alpha = (a_i), \beta = (b_i) \in \mathbb{N}^k. If \sum a_i \neq \sum b_i, then ether \alpha \geq_g \beta or \beta \geq_g \alpha. If \sum a_i = \sum b_i, then (since \leq is total) either \alpha \geq \beta or \beta \geq \alpha.
  5. (Well-founded) Let S \subseteq \mathbb{N}^k be a nonempty subset. To each element (a_i) \in S we associate a natural number \sum a_i; let T \subseteq S be the subset of S consisting of precisely those elements whose sums are minimal. Now choose an element \mu of T which is minimal with respect to \leq. Certainly \mu is minimal (in T) with respect to \leq_g, and thus minimal in S.
  6. (Respects addition) Suppose (a_i) \geq_g (b_i). If \sum a_i > \sum b_i, then \sum (a_i + c_i) > \sum (b_i + c_i) and we have (a_i) + (c_i) \geq_g (b_i) + (c_i). If \sum a_i = \sum b_i, then we have (a_i) \geq (b_i), so that (a_i) + (c_i) \geq (b_i) + (c_i), and \sum (a_i + c_i) = \sum (b_i + c_i), and thus (a_i) + (c_i) \geq_g (b_i) + (c_i).

So \geq_g is an m-order. A monomial ordering is called a grading if it is induced by \leq_g for some m-order \leq.

For example, note the following. Let \leq denote the lexicographic monomial order induced by x > y and let \leq_g be the grading of \leq.

  1. y^4 \geq_g x^2y since \mathsf{deg}(y^4) = 4 > 3 = \mathsf{deg}(x^2y)
  2. x^2y \geq_g xy^2 since \mathsf{deg}(x^2y) = 3 = \mathsf{deg}(xy^2) and (2,1) \geq (1,2) lexicographically
  3. xy^2 \geq_g y^2 since \mathsf{deg}(xy^2) = 3 > 2 = \mathsf{deg}(y^2)
  4. y^2 \geq_g x since \mathsf{deg}(y^2) = 2 > 1 = \mathsf{deg}(x)

Thus y^4 \geq_g x^2y \geq_g xy^2 \geq_g y^2 \geq_g x. Similarly, we have the following.

  1. x^2y \geq xy^2 since (2,1) \geq (1,2) lexicographically
  2. xy^2 \geq x since (1,2) \geq (1,0) lexicographically
  3. x \geq y^4 since (1,0) \geq (0,4) lexicographically
  4. y^4 \geq y^2 since (0,4) \geq (0,2) lexicographically

Thus x^2y \geq xy^2 \geq x \geq y^4 \geq y^2.