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.

Post a comment or leave a trackback: Trackback URL.

Leave a Reply

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

You are commenting using your 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: