Leading terms

To say what a ``leading term'' is, we need to be able to order the monomials in some way. The amounts to the same thing as ordering the set $\mathbb{N}^n$. What is an ``ordering''?

Definition 2.8.1   Let $S$ be a set and let $\leq :S\times S \rightarrow \{{\rm true},{\rm false}\}$ be a function ^2.9. We call $\leq$ a total ordering ^2.10if

• $s\leq s$, (``reflective'')
• if $s\leq t$ and $t\leq s$ then $s=t$, (``anti-symmetric'')
• if $s\leq t$ and $t\leq u$ then $s\leq u$, (``transitive'')
• for all $s,t\in S$, either $s\leq t$ or $t\leq s$.

A function satisfying only the first three conditions above is called a partial ordering.

We shall only be interested in orderings on the monomials. In this case, there are some other conditions we shall want to add.

Definition 2.8.2   Let $M$ be the set of monomials $\underline{x}^{\underline{i}}$ in the variables $x_1,...,x_n$. A relation $\leq$ on $M$ is called a monomial ordering if, as an ordering on $\mathbb{N}^n$ it satisfies

• $\leq$ is a total ordering on $\mathbb{N}^n$,
• if $\underline{a}\leq \underline{b}$ and $\underline{c}\in \mathbb{N}^n$ then $\underline{a}+\underline{c}\leq \underline{b}+\underline{c}$,
• $\leq$ is a well-ordering ^2.11on $\mathbb{N}^n$.

The following example is one of the most commonly used monomial orderings.

Example 2.8.3   Define $(1,0,...,0)\leq (0,1,0,...,0)\leq ...\leq (0,0,...,0,1)$. In general, we say $(i_1,i_2,...,i_n)\leq (j_1,j_2,...,j_n)$ if the first non-zero entry in $(j_1-i_1,j_2-i_2,...,j_n-i_n)$ is positive.

Another perspective: Think of $(1,0,...,0)\in \mathbb{N}^n$ as the letter ``a'', $(2,0,...,0)\in \mathbb{N}^n$ as the word ``aa'', ..., $(0,1,0,...,0)\in \mathbb{N}^n$ as the letter ``b'', $(1,1,0,...,0)\in \mathbb{N}^n$ as the word ``ab'', ... .In general, we think of $(i_1,i_2,...,i_n)$ as the word having $i_1$ ``a''s, followed by $i_2$ ``b''s, ... . We say $(i_1,i_2,...,i_n)\leq (j_1,j_2,...,j_n)$ if the word for $(i_1,i_2,...,i_n)$ occurs before the word for $(j_1,j_2,...,j_n)$ in the dictionary.

This ordering is called the lexicographical ordering, denoted $\leq_{lex}$ if there is an ambiguiuty.

Lemma 2.8.4   The lexicographical ordering is a monomial ordering.

The proof is omitted (see Cox, Little, O'Shea [CLO], Proposition 4, Chapter 2, §2, for example).

The following example is another one of the most commonly used monomial orderings.

Example 2.8.5   In general, we say $\underline{i}=(i_1,i_2,...,i_n)\leq \underline{j}=(j_1,j_2,...,j_n)$ if either

$$\vert\underline{i}\vert<\vert\underline{j}\vert,$$

where $\vert\underline{i}\vert=i_1+..+i_n$, or, if $\vert\underline{i}\vert=\vert\underline{j}\vert$ and $(i_1,i_2,...,i_n)\leq_{lex} (j_1,j_2,...,j_n)$. This ordering is called the graded lexicographical ordering or degree ordering, denoted $\leq_{grlex}$ if there is an ambiguiuty.

Lemma 2.8.6   The graded lexicographical ordering is a monomial ordering.

This proof is also omitted.

Let $<$ be a fixed monomial ordering on $F[x_1,...,x_n]$. We define leading term of $f$ (with respect to $<$) to be the largest of the monomial terms occurring in the expression for $f$ with respect to $<$. Since the leading term is used so often, we introduce a short-hand notation for it. For $f\in F[x_1,...,x_n]$, let $lt(f)=lt_<(f)$ denote the leading term of $f$ (with respect to $<$).