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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: