Famous Theorems of Mathematics/π is transcendental/Fundamental theorem of symmetric polynomials

Let ${\displaystyle \mathbb {F} }$ be a field, and let ${\displaystyle F\in \mathbb {F} [{\vec {X}}{}^{n}]}$ be a symmetric polynomial.
Then ${\displaystyle F}$ can be expressed uniquely as a polynomial ${\displaystyle G({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]}$, such that:

• ${\displaystyle G}$'s degree does not exceed ${\displaystyle F}$'s degree.
• If ${\displaystyle F}$ has integer coefficients, then so does ${\displaystyle G}$.

Proof

First, we shall descibe an algorithm for finding the desired polynomial ${\displaystyle G}$.

Let us define initial conditions ${\displaystyle m=1}$ and ${\displaystyle F_{1}=F}$.

1. Find ${\displaystyle {\text{L}}(F_{m})=c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}$ such that ${\displaystyle c_{m}\in \mathbb {F} ,c_{m}\neq 0}$.
2. Define ${\displaystyle G_{m}({\vec {Y}}{}^{n})=c_{m}\,Y_{1}^{a_{1}-a_{2}}Y_{2}^{a_{2}-a_{3}}\!\cdots Y_{n-1}^{a_{n-1}-a_{n}}Y_{n}^{a_{n}}}$.
3. Write ${\displaystyle F_{m+1}({\vec {X}}{}^{n})=F_{m}({\vec {X}}{}^{n})-G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}$.
4. If ${\displaystyle F_{m+1}\neq 0}$, return to step 1 and began the process over with the index ${\displaystyle m+1}$.
If ${\displaystyle F_{m+1}=0}$, move on to step 5.
5. Write ${\displaystyle G=G_{1}\!+\cdots +G_{m}}$.

In order to prove the algorithm we need two lemmas.

Lemma 1: The leading monomial in ${\displaystyle F}$ satisfies ${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$.

Proof: Let us assume there exists an index ${\displaystyle k}$ such that ${\displaystyle a_{k}. Then there exists a permutation ${\displaystyle \sigma \in S_{X}}$ such that

${\displaystyle X_{\sigma (m)}={\begin{cases}X_{m}&:m\neq k,k+1\\X_{k+1}&:m=k\\X_{k}&:m=k+1\end{cases}}}$

But the polynomial ${\displaystyle \sigma (F)=F}$ contains the monomial ${\displaystyle c\,X_{1}^{a_{1}}\!\cdots X_{k}^{a_{k+1}}X_{k+1}^{a_{k}}\!\cdots X_{n}^{a_{n}}}$, which is of higher order than ${\displaystyle c\,X_{1}^{a_{1}}\!\cdots X_{k}^{a_{k}}X_{k+1}^{a_{k+1}}\cdots X_{n}^{a_{n}}}$. A contradiction.

${\displaystyle \square }$

Lemma 2: The leading monomial in the expansion of ${\displaystyle G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}$ is ${\displaystyle c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}$.

Proof: We have

{\displaystyle {\begin{aligned}{\text{L}}(E_{k})=X_{1}\!\cdots X_{k},&\quad :\!1\leq k\leq n\\[5pt]{\text{L}}(c_{m}\,E_{1}^{b_{1}}E_{2}^{b_{2}}\!\cdots E_{n}^{b_{n}})&=c_{m}\,{\text{L}}(E_{1}^{b_{1}})\,{\text{L}}(E_{2}^{b_{2}})\cdots {\text{L}}(E_{n}^{b_{n}})\\[5pt]&=c_{m}\,{\text{L}}(E_{1})^{b_{1}}{\text{L}}(E_{2})^{b_{2}}\!\cdots {\text{L}}(E_{n})^{b_{n}}\\[5pt]&=c_{m}\,X_{1}^{b_{1}}(X_{1}X_{2})^{b_{2}}\!\cdots (X_{1}X_{2}\cdots X_{n})^{b_{n}}\\[5pt]&=c_{m}(X_{1})^{b_{1}\,+\,\cdots \,+\,b_{n}}(X_{2})^{b_{2}\,+\,\cdots \,+\,b_{n}}\!\cdots (X_{n-1})^{b_{n-1}+\,b_{n}}(X_{n})^{b_{n}}\\[5pt]&=c_{m}\,X_{1}^{a_{1}}X_{2}^{a_{2}}\!\cdots X_{n}^{a_{n}}\end{aligned}}}

The last equality holds if and only if

{\displaystyle {\begin{aligned}a_{k}&=\sum _{i\,=\,k}^{n}b_{i},\quad :\!1\leq k\leq n\\[5pt]b_{k}&={\begin{cases}a_{k}\!-a_{k+1}&:\!1\leq k\leq n-1\\[5pt]a_{k}&:\!k=n\end{cases}}\end{aligned}}}

${\displaystyle \square }$

We shall now prove the theorem:

1. Let ${\displaystyle F\neq 0}$ be a symmetric polynomial in variables ${\displaystyle X_{1},\ldots ,X_{n}}$.
The proof is by strong induction on ${\displaystyle |{\text{D}}(F)|}$ (see definition).

If ${\displaystyle |{\text{D}}(F)|=0}$ then ${\displaystyle F}$ is a constant polynomial, and it is easy to show the algorithm holds.

Let us assume the algorithm holds for all symmetric polynomials ${\displaystyle F}$ with ${\displaystyle 0\leq |{\text{D}}(F)|\leq k}$, for some ${\displaystyle k\in \mathbb {N} }$.
We will show that the algorithm holds also for a symmetric polynomial ${\displaystyle F_{1}}$ with ${\displaystyle |{\text{D}}(F_{1})|=k+1}$, such that ${\displaystyle {\text{L}}(F_{1})=c_{1}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}}$.

By lemma 2, we get:

{\displaystyle {\begin{aligned}G_{1}({\vec {Y}}{}^{n})&=c_{1}\,Y_{1}^{a_{1}-a_{2}}Y_{2}^{a_{2}-a_{3}}\!\cdots Y_{n-1}^{a_{n-1}-a_{n}}Y_{n}^{a_{n}}\\[5pt]F_{2}({\vec {X}}{}^{n})&=F_{1}({\vec {X}}{}^{n})-G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\end{aligned}}}

The function ${\displaystyle G_{1}}$ is a polynomial, since ${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$.
In addition, by the properties of symmetric polynomials ${\displaystyle G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}$ is a symmetric polynomial in variables ${\displaystyle X_{1},\ldots ,X_{n}}$, therefore so is ${\displaystyle F_{2}}$.
The polynomials ${\displaystyle F_{1}({\vec {X}}{}^{n}),G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))}$ both contain ${\displaystyle {\text{L}}(F_{1})}$, hence it is cancelled in their subtraction.

If ${\displaystyle F_{2}=0}$ then ${\displaystyle G=G_{1}}$.
If ${\displaystyle F_{2}\neq 0}$ then ${\displaystyle {\text{L}}(F_{2})\prec {\text{L}}(F_{1})}$, meaning ${\displaystyle |{\text{D}}(F_{2})|<|{\text{D}}(F_{1})|=k+1}$.
Thus, the inductive assumption holds for ${\displaystyle F_{2}}$, and therefore the algorithm yields a polynomial ${\displaystyle G^{*}}$ such that

{\displaystyle {\begin{aligned}F_{2}({\vec {X}}{}^{n})&=G^{*}\!({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\\[5pt]F_{1}({\vec {X}}{}^{n})&=G_{1}({\vec {E}}{}^{n}({\vec {X}}{}^{n}))+G^{*}\!({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\end{aligned}}}

2. The properties of the theorem hold:

• By definition, the degree of ${\displaystyle G_{1}({\vec {Y}}{}^{n})}$ is ${\displaystyle a_{1}}$ and the degree of ${\displaystyle F_{1}}$ is at least ${\displaystyle a_{1}\!+\cdots +a_{n}}$.
• If ${\displaystyle F_{1}}$ has integer coefficients then ${\displaystyle c_{1}\neq 0}$ is an integer. Therefore ${\displaystyle G_{1}}$ too has integer coefficients.

${\displaystyle \blacksquare }$

Important results

Theorem. Let ${\displaystyle \mathbb {F} \subseteq \mathbb {E} }$ be a field, and let ${\displaystyle F\in \mathbb {F} [z]}$ be a polynomial of degree ${\displaystyle n}$ with roots ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E} }$.
Let ${\displaystyle G\in \mathbb {F} [{\vec {X}}{}^{n}]}$ be a symmetric polynomial. Then ${\displaystyle G({\vec {\alpha }}{}^{n})\in \mathbb {F} }$.

Proof. By Vieta's formulae, we get

{\displaystyle {\begin{aligned}F(z)&=a_{0}+a_{1}z+\cdots +a_{n-1}z^{n-1}+a_{n}z^{n}\in \mathbb {F} [z]\\[5pt]E_{k}({\vec {\alpha }}{}^{n})&=(-1)^{k}{\frac {a_{n-k}}{a_{n}}}\in \mathbb {F} ,\quad (1\leq k\leq n)\end{aligned}}}

By the fundamental theorm above, ${\displaystyle G}$ can be expressed as a polynomial

{\displaystyle {\begin{aligned}G({\vec {X}}{}^{n})&=H({\vec {E}}{}^{n}({\vec {X}}{}^{n}))\in \mathbb {F} [{\vec {X}}{}^{n}]\\[5pt]G({\vec {\alpha }}{}^{n})&=H({\vec {E}}{}^{n}({\vec {\alpha }}{}^{n}))\in \mathbb {F} \end{aligned}}}

${\displaystyle \square }$

Theorem. Let ${\displaystyle \mathbb {F} \subseteq \mathbb {E} }$ be a field, and let ${\displaystyle F\in \mathbb {F} [z]}$ be a polynomial of degree ${\displaystyle n}$ with roots ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}\in \mathbb {E} }$.
Let ${\displaystyle 1\leq k\leq n}$, and let ${\displaystyle \beta _{1},\ldots ,\beta _{m}}$ be the sums of every ${\displaystyle k}$ of the roots ${\displaystyle \alpha _{1},\ldots ,\alpha _{n}}$ (namely ${\displaystyle m={\tbinom {n}{k}}}$).
Then there exists a monic polynomial ${\displaystyle F_{k}\in \mathbb {F} [z]}$ of degree ${\displaystyle m}$ with roots ${\displaystyle \beta _{1},\ldots ,\beta _{m}}$.

Proof. We will show that

${\displaystyle F_{k}(z)=(z-\beta _{1})(z-\beta _{2})\cdots (z-\beta _{m})\in \mathbb {F} [z]}$

By Vieta's formulae, its coefficients are all symmetric polynomials in ${\displaystyle \beta _{1},\ldots ,\beta _{m}}$.

Let ${\displaystyle G\in \mathbb {F} [{\vec {Y}}{}^{m}]}$ be a symmetric polynomial, and let ${\displaystyle Y_{1},\ldots ,Y_{m}}$ be the sums of every ${\displaystyle k}$ of the variables ${\displaystyle X_{1},\ldots ,X_{n}}$.
Then ${\displaystyle G}$ can be expressed as a polynomial

${\displaystyle G({\vec {Y}}{}^{m})=H({\vec {X}}{}^{n})}$

It is easy to see that by applying a permutation on ${\displaystyle X_{1},\ldots ,X_{n}}$, we also apply a permutation on ${\displaystyle Y_{1},\ldots ,Y_{m}}$.
Hence ${\displaystyle H\in \mathbb {F} [{\vec {X}}{}^{n}]}$ is a symmetric polynomial, and by the previous theorem we get

${\displaystyle G({\vec {\beta }}{}^{m})=H({\vec {\alpha }}{}^{n})\in \mathbb {F} }$

${\displaystyle \square }$

 Fundamental theorem of symmetric polynomials