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