Cox-Little-O’Shea 2.2 - Ordering on the Monomials in $k[x_1, \ldots, x_n]$

Definition 1 (monomial ordering)

[definition] A monomial ordering $>$ on $k[x_1, \ldots, x_n]$ is a relation $>$ on $\ZZ_{\ge 0}^n$ (or equivalently, a relation on the set of monomials $x^\alpha$, $\alpha \in \ZZ_{\ge 0}^n$) satisfying:

$>$ is a total ordering on $\ZZ_{\ge 0}^n$.
If $\alpha > \beta$ and $\gamma \in \ZZ_{\ge 0}^n$, then $\alpha + \gamma > \beta + \gamma$.
$>$ is a well-ordering on $\ZZ_{\ge 0}^n$. [/definition]

Lemma 2

[lemma] An order relation $>$ on $\ZZ_{\ge 0}^n$ is a well-ordering if and only if every strictly decreasing sequence in $\ZZ_{\ge 0}^n$

\[\alpha(1) > \alpha(2) > \alpha(3) > \cdots\]

eventually terminates. [/lemma]

[proof] ($\implies$) If such a sequence doesn’t terminate, then the set of elements of the sequence fails to have a minimum under $>$.

($\impliedby$) If there is a subset that doesn’t have a minimum, then we can inductively construct a sequence from it that does not terminate. [/proof]

Definition 3 (lexicographic order)

[definition] Let $\alpha, \beta \in \ZZ_{\ge 0}^n$ with

\[\alpha = (\alpha_1, \ldots, \alpha_n) \quad\text{ and }\quad \beta = (\beta_1, \ldots, \beta_n)\]

We say $\alpha >_{lex} \beta$ if the leftmost nonzero entry of $\alpha - \beta \in \ZZ^n$ is positive. In this case, will also say $x^\alpha >_{lex} x^\beta$. [/definition]

Notice this is really just a secret way of saying “the way we order words in a dictionary”.

Proposition 4 (lex order is a monomial ordering)

[proposition] The lex ordering on $\ZZ_{\ge 0}^n$ is a monomial ordering. [/proposition]

[proof] In this proof, when we write $>$, we mean $>_{lex}$.

($>$ is a partial order) Reflexivity and antisymmetry are obvious. For transitivity, say $\alpha > \beta$ and $\beta > \gamma$. And note that

\[\alpha - \gamma = (\alpha - \beta) + (\beta - \gamma).\]

But since $\alpha$ and $\beta$ both have leftmost positive entries, this carries over to $\alpha - \gamma$.

($>$ is a total order) Obvious.

($\alpha + \gamma > \beta + \gamma$) Suppose $\alpha > \beta$. Then

\[\alpha - \beta = (\alpha + \gamma) - (\beta + \gamma)\]

is leftmost positive.

(Well-ordering) Let $S \subseteq \ZZ_{\ge 0}^n$ be nonempty. Then consider the subset of $S$ consisting of the maximum number of left-justified zeros. We then let $\alpha$ be the element from this subset that has the smallest leftmost nonzero entry. This element is clearly the minimum of $S$. [/proof]

Definition 5 (graded lex order)

[definition] Let $\alpha, \beta \in \ZZ_{\ge 0}^n$. We say $\alpha >_{grlex} \beta$ if

\[|\alpha| = \sum_{i=1}^n \alpha_i > |\beta| = \sum_{i=1}^n \beta_i \quad\text{ or }\quad |\alpha| = |\beta| \text{ and } \alpha >_{lex} \beta.\]

[/definition]

Definition 6 (graded reverse lex order)

[definition] Let $\alpha, \beta \in \ZZ_{\ge 0}^n$. We say $\alpha>_{grevlex} \beta$ if

\[|\alpha| = \sum_{i=1}^n \alpha_i > |\beta| = \sum_{i=1}^n \beta_i \text{ or } |\alpha| = |\beta| \text{ and the rightmost nonzero entry of } \alpha - \beta\in \ZZ^n \text{ is negative}.\]

[/definition]

Definition 7 (multidegree, leading coefficient/monomial/term)

[definition] Let $f = \sum_{\alpha} c_\alpha x^\alpha \in k[x_1, \ldots, x_n]$ be nonzero and $>$ a monomial order.

(i) The multidegree of $f$ is

\[\operatorname{multideg}(f) = \max\{\alpha \in \ZZ_{\ge 0}^n \mid c_\alpha \neq 0\}\]

where the maximum is with respect to $>$.

(ii) The leading coefficient of $f$ is

\[\operatorname{LC}(f) = c_{\operatorname{multideg}(f)} \in k.\]

(iii) The leading monomial of $f$ is

\[\operatorname{LM}(f) = x^{\operatorname{multideg}(f)}\]

(with coefficient $1$).

(iv) The leading term of $f$ is

\[\operatorname{LT}(f) = \operatorname{LC}(f)\cdot \operatorname{LT}(f).\]

[/definition]

Lemma 8

[lemma] Let $f, g \in k[x_1, \ldots, x_n]$ be nonzero polynomials. Then:

(i) $\operatorname{multideg}(fg) = \operatorname{multideg}(f) + \operatorname{multideg}(g)$.

(ii) If $f + g \neq 0$, then

\[\operatorname{multideg}(f + g) \le \max(\operatorname{multideg}(f), \operatorname{multideg}(g)).\]

If, in addition,

\[\operatorname{multideg}(f) \neq \operatorname{multideg}(g),\]

then equality occurs. [/lemma]

Property (i), of course, is true for degree in $k[x]$. Property $(ii)$ is also true in $k[x]$ (leading terms can cancel).