## 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$.