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