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.
Advertisements
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: