Algebra/Chapter 10/Symmetric Polynomials/Monomial Ordering

Definition 1

Let $(A_1,\dots ,A_n)$ be an N-tuple. Let us define:

$\overrightarrow{A}{}^n=(A_1,\dots ,A_n)$

For functions $\overrightarrow{F}{}^m,\overrightarrow{G}{}^n$ let us define:

$\overrightarrow{F}{}^m(\overrightarrow{G}{}^n)=(F_1(G_1,\dots ,G_n),\dots ,F_m(G_1,\dots ,G_n))$

This abbreviated notation will be of great use to us in the following pages and in the proof.

Definition 2

Let $𝔽$ be a field. Then $𝔽[\overrightarrow{X}{}^n]$ is the polynomial space in variables $X_1,\dots ,X_n$ with coefficients in $𝔽$.

A monomial is a polynomial of the form $c{X}_1^{a_1}\cdots X_n^{a_n}$, such that $c\in 𝔽$ and $a_1,\dots ,a_n\in \mathbb{N}$.

Definition 3

Let $X=X_1\cdots X_n$, and let $a=(a_1,\dots ,a_n)\in {\mathbb{N}}^n$ be an exponent vector. Let us define:

• $X^a=X_1^{a_1}\cdots X_n^{a_n}$
• $\mathrm{deg}(X^a)=a_1+\cdots +a_n$
• The degree of a non-zero polynomial is equal to the maximum of the degrees of its compsing monomials.

Properties

Monomial multiplication maintains exponent vector addition:

$\begin{array}{cc}{X}^a\cdot X^b& =(X_1^{a_1}\cdots X_n^{a_n})\cdot (X_1^{b_1}\cdots X_n^{b_n})\\ & =(X_1^{a_1}\cdot X_1^{b_1})\cdots (X_n^{a_n}\cdot X_n^{b_n})\\ & =X_1^{a_1+b_1}\cdots X_n^{a_n+b_n}\\ & =X^{a+b}\end{array}$

Definition 4

Let $X^a,X^b$ be monomials.

We say that $X^a$ is of lower order than $X^b$ (and denote it by $X^a\prec X^b$) if there exists an index $1\le k\le n$ such that

$\{\begin{array}{cc}{a}_i=b_i& :1\le i\le k-1\\ a_i<b_i& :i=k\end{array}$

In other words, the vectors $(a_1,\dots ,a_n),(b_1,\dots ,b_n)$ have a lexicographic ordering.

In a polynomial $F$, the monomial of maximal order is called the leading monomial, and is denoted by $\text{L}(F)$.

Example

$x_1^7{x}_2^3{x}_3^{10}\prec x_1^7{x}_2^{31}{x}_3⟺(7,3,10)\prec (7,31,1)$

Lemma

Let $F,G\in 𝔽[\overrightarrow{X}{}^n]$ be polynomials. Then $\text{L}(F\cdot G)=\text{L}(F)\cdot \text{L}(G)$.

Proof

Let $X^a,X^b,X^f,X^g$ be monomials, with $X^f=\text{L}(F),X^g=\text{L}(G)$.

1. Let us assume that $X^a\prec X^f$. We will show that $X^{a+c}\prec X^{f+c}$ for all $X^c$.
By definition, there exists an index $1\le k\le n$ such that

$\{\begin{array}{cc}{a}_i(+c_i)=f_i(+c_i)& :1\le i\le k-1\\ a_i(+c_i)<f_i(+c_i)& :i=k\end{array}$

2. Let us assume also that $X^b\prec X^g$. We will show that $X^{a+b}\prec X^{f+g}$.
By definition, there exist indexes $k_1,k_2\in \{1,\dots ,n\}$ such that respectively

$\begin{array}{cc}& \{\begin{array}{cc}{a}_i=f_i& :1\le i\le k_1-1\\ a_i<f_i& :i=k_1\end{array},\{\begin{array}{cc}{b}_i=g_i& :1\le i\le k_2-1\\ b_i<g_i& :i=k_2\end{array}\\ & \{\begin{array}{cc}1\le k_1\le k_2\le n:& (a_{k_1}<f_{k_1})\wedge (b_{k_1}\le g_{k_1})⟹a_{k_1}+b_{k_1}<f_{k_1}+g_{k_1}\\ 1\le k_2<k_1\le n:& (a_{k_2}=f_{k_2})\wedge (b_{k_2}<g_{k_2})⟹a_{k_2}+b_{k_2}<f_{k_2}+g_{k_2}\end{array}\}⟹X^{a+b}\prec X^{f+g}\end{array}$

hence:

$\text{L}(F\cdot G)=X^{f+g}=X^f\cdot X^g=\text{L}(F)\cdot \text{L}(G)$

$◻$

Definition 5

Let $F\in 𝔽[\overrightarrow{X}{}^n]$ be a polynomial. Let us define:

$\text{D}(F)=\{X^a\in 𝔽[\overrightarrow{X}{}^n]:\mathrm{deg}(X^a)\le \mathrm{deg}(\text{L}(F)),X^a\prec \text{L}(F)\}$

Meaning, the set of all monic monomials of degree $\le \mathrm{deg}(\text{L}(F))$ which are of lower order than $\text{L}(F)$.

Example

$\begin{array}{cc}& F(x_1,x_2)=4+3x_1+2x_1^2{x}_2+x_2^4\\ & \text{L}(F)=2x_1^2{x}_2\\ & \text{D}(F)=\{x_1{x}_2^2,x_1^2,x_1{x}_2,x_2^2,x_1,x_2,1\}\end{array}$