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

Let $\mathbb {F}$ be a field, and let $F\in \mathbb {F} [X_{1},\ldots ,X_{n}]$ be a symmetric polynomial.
Then $F$ can be expressed uniquely as a polynomial $G(E_{1},\ldots ,E_{n})\in \mathbb {F} [X_{1},\ldots ,X_{n}]$, such that:

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

Proof

First, we shall descibe an algorithm for finding the desired polynomial $G$.

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

1. Find ${\text{L}}(F_{m})=c_{m}\,X_{1}^{a_{1}}\!\cdots X_{n}^{a_{n}}$ such that $c_{m}\in \mathbb {F} ,c_{m}\neq 0$.
2. Define $G_{m}(Y_{1},\ldots ,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 $F_{m+1}(X_{1},\ldots ,X_{n})=F_{m}(X_{1},\ldots ,X_{n})-G_{m}(E_{1},\ldots ,E_{n})$.
4. If $F_{m+1}\neq 0$, return to step 1 and began the process over with the index $m+1$.
   If $F_{m+1}=0$, move on to step 5.
5. Write $G=G_{1}+\cdots +G_{m}$.

In order to prove the algorithm we need two lemmas.

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

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

$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 $\sigma (F)=F$ contains the monomial $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 $c\,X_{1}^{a_{1}}\cdots X_{k}^{a_{k}}X_{k+1}^{a_{k+1}}\cdots X_{n}^{a_{n}}$. A contradiction.

$\square$

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

Proof: We have

${\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

${\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}}$

$\square$

We shall now prove the theorem:

1. Let $F\neq 0$ be a symmetric polynomial in variables $X_{1},\ldots ,X_{n}$.
Let ${\text{D}}(F)\in \mathbb {N}$ be the total number of monomials which are of lower order than ${\text{L}}(F)$ (but not necessarily occurring in $F$).
The proof is by strong induction on ${\text{D}}(F)$.

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

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

${\begin{aligned}G_{1}(Y_{1},\ldots ,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}(X_{1},\ldots ,X_{n})&=F_{1}(X_{1},\ldots ,X_{n})-G_{1}(E_{1},\ldots ,E_{n})\end{aligned}}$

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

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

${\begin{aligned}F_{2}(X_{1},\ldots ,X_{n})&=G^{*}\!(E_{1},\ldots ,E_{n})\\[5pt]F_{1}(X_{1},\ldots ,X_{n})&=G_{1}(E_{1},\ldots ,E_{n})+G^{*}\!(E_{1},\ldots ,E_{n})\end{aligned}}$

2. The properties of the theorem hold:

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

$\blacksquare$

Important results

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

Proof. By the fundamental theorm above and by Vieta's formulae, we get

${\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]G(X_{1},\ldots ,X_{n})&=H(E_{1},\ldots ,E_{n})\in \mathbb {F} [X_{1},\ldots ,X_{n}]\\[5pt]G(\alpha _{1},\ldots ,\alpha _{n})&=H{\bigl (}E_{1}(\alpha _{1},\ldots ,\alpha _{n}),\ldots ,E_{n}(\alpha _{1},\ldots ,\alpha _{n}){\bigr )}\\[5pt]E_{k}(\alpha _{1},\ldots ,\alpha _{n})&=(-1)^{k}{\frac {a_{n-k}}{a_{n}}}\in \mathbb {F} ,\quad (1\leq k\leq n)\end{aligned}}$

Therefore $G(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {F}$.

$\square$

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

Proof. We will show that

$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 $\beta _{1},\ldots ,\beta _{m}$.

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

$G(Y_{1},\ldots ,Y_{m})=H(X_{1},\ldots ,X_{n})$

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

$G(\beta _{1},\ldots ,\beta _{m})=H(\alpha _{1},\ldots ,\alpha _{n})\in \mathbb {F}$

$\square$

←Elementary symmetric polynomials

Fundamental theorem of symmetric polynomials

Proof→