Famous Theorems of Mathematics/π is transcendental/Monomial ordering

Definition 1

Let $\mathbb {F}$ be a field. Then $\mathbb {F} [X_{1},\ldots ,X_{n}]$ is the polynomial space in variables $X_{1},\ldots ,X_{n}$ with coefficients in $\mathbb {F}$.

A Monomial is a polynomial of the form $c\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}$, such that $c\in \mathbb {F}$ and $a_{1},\ldots ,a_{n}\in \mathbb {N}$.

Definition 2

Let $X=X_{1}\cdots X_{n}$, and let $a=(a_{1},\ldots ,a_{n})\in \mathbb {N} ^{n}$ be an exponent vector. Let us define:

• $X^{a}=X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}$
• The degree of $X^{a}$ is equal to $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{aligned}X^{a}\cdot X^{b}&=(X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}})\cdot (X_{1}^{b_{1}}\!\cdots X_{n}^{b_{n}})\\[5pt]&=(X_{1}^{a_{1}}\!\cdot X_{1}^{b_{1}})\cdots (X_{n}^{a_{n}}\!\cdot X_{n}^{b_{n}})\\[5pt]&=X_{1}^{a_{1}+b_{1}}\!\cdots X_{n}^{a_{n}+b_{n}}\\[5pt]&=X^{a+b}\end{aligned}}$

Definition 3

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

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

${\begin{cases}a_{i}=b_{i}&:\!1\leq i\leq k-1\\[3pt]a_{i}<b_{i}&:i=k\end{cases}}$

In other words, the vectors $(a_{1},\ldots ,a_{n}),(b_{1},\ldots ,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}\iff (7,3,10)\prec (7,31,1)$

Lemma

Let $F,G\in \mathbb {F} [X_{1},\ldots ,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\leq k\leq n$ such that

${\begin{cases}a_{i}(+\,c_{i})=f_{i}(+\,c_{i})&:\!1\leq i\leq k-1\\[3pt]a_{i}(+\,c_{i})<f_{i}(+\,c_{i})&:i=k\end{cases}}$

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,\ldots ,n\}$ such that respectively

${\begin{aligned}&{\begin{cases}a_{i}=f_{i}&:\!1\leq i\leq k_{1}-1\\[3pt]a_{i}<f_{i}&:i=k_{1}\end{cases}},\quad {\begin{cases}b_{i}=g_{i}&:\!1\leq i\leq k_{2}-1\\[3pt]b_{i}<g_{i}&:i=k_{2}\end{cases}}\\[8pt]&{\begin{cases}1\leq k_{1}\leq k_{2}\leq n\!:&(a_{k_{1}}\!<f_{k_{1}}\!)\land (b_{k_{1}}\!\leq g_{k_{1}}\!)\,\implies \,a_{k_{1}}\!+b_{k_{1}}\!<f_{k_{1}}\!+g_{k_{1}}\\[5pt]1\leq k_{2}<k_{1}\leq n\!:&(a_{k_{2}}\!=f_{k_{2}}\!)\land (b_{k_{2}}\!<g_{k_{2}}\!)\,\implies \,a_{k_{2}}\!+b_{k_{2}}\!<f_{k_{2}}\!+g_{k_{2}}\end{cases}}\!{\Bigg \}}\,\implies \,X^{a+b}\prec X^{f+g}\end{aligned}}$

hence:

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

$\square$

←Introduction

Monomial ordering

Symmetric polynomials→