# Famous Theorems of Mathematics/π is transcendental/Monomial ordering

## Definition 1

Let ${\displaystyle (A_{1},\ldots ,A_{n})}$ be an N-tuple. Let us define:

${\displaystyle {\vec {A}}{}^{n}=(A_{1},\ldots ,A_{n})}$

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

${\displaystyle {\vec {F}}{}^{m}({\vec {G}}{}^{n})={\bigl (}F_{1}(G_{1},\ldots ,G_{n}),\ldots ,F_{m}(G_{1},\ldots ,G_{n}){\bigr )}}$

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

## Definition 2

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

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

## Definition 3

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

• ${\displaystyle X^{a}=X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}$
• ${\displaystyle \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:

{\displaystyle {\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 4

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

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

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

In other words, the vectors ${\displaystyle (a_{1},\ldots ,a_{n}),(b_{1},\ldots ,b_{n})}$ have a lexicographic ordering.

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

### Example

${\displaystyle 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 ${\displaystyle F,G\in \mathbb {F} [{\vec {X}}{}^{n}]}$ be polynomials. Then ${\displaystyle {\text{L}}(F\cdot G)={\text{L}}(F)\cdot {\text{L}}(G)}$.

### Proof

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

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

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

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

{\displaystyle {\begin{aligned}&{\begin{cases}a_{i}=f_{i}&:\!1\leq i\leq k_{1}-1\\[3pt]a_{i}

hence:

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

${\displaystyle \square }$

## Definition 5

Let ${\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}$ be a polynomial. Let us define:

${\displaystyle {\text{D}}(F)={\Big \{}X^{a}\!\in \mathbb {F} [{\vec {X}}{}^{n}]:\deg(X^{a})\leq \deg({\text{L}}(F)),X^{a}\!\prec {\text{L}}(F){\Big \}}}$

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

### Example

{\displaystyle {\begin{aligned}&F(x_{1},x_{2})=4+3x_{1}+2x_{1}^{2}x_{2}+x_{2}^{4}\\[3pt]&{\text{L}}(F)=2x_{1}^{2}x_{2}\\[3pt]&{\text{D}}(F)={\Big \{}x_{1}x_{2}^{2},x_{1}^{2},x_{1}x_{2},x_{2}^{2},x_{1},x_{2},1{\Big \}}\end{aligned}}}

 Monomial ordering