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