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