Basic properties of monomial orders

Let \leq be a monomial order. Let LT(f) denote the leading term of f with respect to \leq and let \delta(F) denote the multidegree of LT(f).

  1. Prove that LT(fg) = LT(f) LT(g) and \delta(fg) = \delta(f) + \delta(g) for any nonzero f,g \in F[x_1,\ldots,x_k].
  2. Prove that \delta(f+g) \leq \max(\delta(f), \delta(g)) with equality if \delta(f) \neq \delta(g).
  3. Prove that m \geq 1 for any monomial m.
  4. Prove that if m_1 divides m_2, then m_2 \geq m_1. Deduce that the leading term of a polynomial does not divide any of its lower terms.

We will begin with a more concrete definition of monomial order.

Let F be a field and let R = F[x_1,\ldots,x_k]. We define the monomials in R to be the set M(F,k) = \{ a \prod_{i=1}^k x_i^{t_i} \ |\ t_i \in \mathbb{N}, a \in F \}. Note that M(F,k) is closed under multiplication in R, so that (M(F,k), \cdot) is a subsemigroup (in facr a submonoid) of (R,\cdot). Now \mathbb{N}^k is also a semigroup under pointwise addition. Define \delta : M(F,k) \rightarrow \mathbb{N}^k by a \prod_{i=1}^k x_i^{t_i} \mapsto (t_i); certainly \delta is surjective, and moreover is a semigroup homomorphism. Also, we have \delta(m_1) = \delta(m_2) if and only if m_1 and m_2 are associates in M(F,k) (and thus associates in R). (In the language of semigroups, the kernel of \delta is the associate congruence.)

Note that every relation \sigma on \mathbb{N}^k induces a relation \tau on M(F,k) as follows: m_1 \tau m_2 if and only if \delta(m_1) \sigma \delta(m_2).

Definition: We will say that a relation \sigma on \mathbb{N}^k is an m-order if the following hold.

  1. \sigma is a linear order; that is, reflexive, antisymmetic, transitive, and total.
  2. Every nonempty subset of \mathbb{N}^k contains a \sigma-minimal element. That is, for every nonempty S, there exists x \in S such that for all y \in S, x \sigma y.
  3. If a \sigma b, then a+c \sigma b+c.

A relation \tau on M(F,k) is called a monomial order if it is induced by some m-order on \mathbb{N}^k.

Lemma: Let \tau be a monomial order on M(F,k). Then the following hold for all m,m_1,m_2 \in M(F,k).

  1. \tau is reflexive, transitive, and total.
  2. m_1 \tau m_2 and m_2 \tau m_1 if and only if m_1 and m_2 are associates in F[x_1,\ldots,x_k].
  3. Every nonempty subset of M(F,k) contains a \tau-minimal element. That is, for every nonempty subset S, there exists m \in S such that for all n \in S, m \tau n.
  4. If m_1 \tau m_2, then mm_1 \tau mm_2.

These follow directly from the definitions of m-order and \delta.

Lemma: Let \leq be an m-order on \mathbb{N}^k. Then 0 is minimal with respect to \sigma. Proof: Suppose we have 0 \geq x. Note that nx \geq (n+1)x for all n, where we interpret nx as the n-fold sum of x. Now the multiples of x form a nonempty ssubset of \mathbb{N}^k, which must contain a minimal element nx. That is, nx = (n+1)x = nx + x. Because \mathbb{N}^k is cancellative, we have x = 0. Thus 0 \in \mathbb{N}^k is minimal with respect to \leq. \square

Corollary: If \leq is a monomial order on M(F,k), then a is minimal with respect to \leq for all a \in F. In particular, 1 \leq m for all m \in M(F,k). \square

Definition: Let F be a field, k a positive natural number, R = F[x_1,\ldots,x_k], and let \leq be a monomial order on M(F,k). Let p = \sum a_i m_i \in R. Note that \{m_i\} contains a unique maximal element with respect to \leq; this is called the leading term of p and denoted LT(p). The multidegree of p, denoted \delta(p), is \delta(p) = \delta(LT(p)) where the right hand delta is the semigroup homomorphism M(F,k) \rightarrow \mathbb{N}^k defined above.

Let p = \sum_i a_im_i and q = \sum_j b_jn_j be in F[x_1,\ldots,x_k], with F a field, and let \leq be a monomial order on M(F,k). Note that pq = \sum_{i,j} a_ib_j m_in_j. Say LT(p) = m_0 and LT(q) = n_0. Then m_0 \geq m_i for all i and n_0 \geq n_j for all j. So for all i,j, we have m_0n_0 \geq m_0n_j \geq m_in_j; even after pq is simplified, m_0n_0 is maximal among the terms. Thus LT(pq) = LT(p)LT(q). By definition, then, \delta(pq) = \delta(p) + \delta(q).

Now suppose m_1|m_2; say mm_1 = m_2. Since 1 \leq m, we have m_1 \leq mm_1 = m_2; thus if m_1|m_2 then m_1 \leq m_2. If m_0 is greatest among a set of terms, then, it cannot divide any of them.

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: