Algebra/Chapter 10/Symmetric Polynomials/Fundamental Theorem of Symmetric Polynomials

Proof

First, we shall describe 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 𝔽,c_m\ne 0$.
2. Define $G_m(\overrightarrow{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}(\overrightarrow{X}{}^n)=F_m(\overrightarrow{X}{}^n)-G_m(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))$.
4. If $F_{m+1}\ne 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\ge a_2\ge \cdots \ge 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{array}{cc}{X}_m& :m\ne k,k+1\\ X_{k+1}& :m=k\\ X_k& :m=k+1\end{array}$

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.

$◻$

Lemma 2: The leading monomial in the expansion of $G_m(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))$ is $c_m{X}_1^{a_1}\cdots X_n^{a_n}$.

Proof: We have

$\begin{array}{cc}\text{L}(E_k)=X_1\cdots X_k,& :1\le k\le n\\ \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})\\ & =c_m\text{L}(E_1{)}^{b_1}\text{L}(E_2{)}^{b_2}\cdots \text{L}(E_n{)}^{b_n}\\ & =c_m{X}_1^{b_1}(X_1{X}_2{)}^{b_2}\cdots (X_1{X}_2\cdots X_n{)}^{b_n}\\ & =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}\\ & =c_m{X}_1^{a_1}{X}_2^{a_2}\cdots X_n^{a_n}\end{array}$

The last equality holds if and only if

$\begin{array}{cc}{a}_k& =\sum _{i=k}^n{b}_i,:1\le k\le n\\ b_k& =\{\begin{array}{cc}{a}_k-a_{k+1}& :1\le k\le n-1\\ a_k& :k=n\end{array}\end{array}$

$◻$

We shall now prove the theorem:

1. Let $F\ne 0$ be a symmetric polynomial in variables $X_1,\dots ,X_n$.
The proof is by strong induction on $|\text{D}(F)|$ (see definition).

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\le |\text{D}(F)|\le 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}$.

By lemma 2, we get:

$\begin{array}{cc}{G}_1(\overrightarrow{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}\\ F_2(\overrightarrow{X}{}^n)& =F_1(\overrightarrow{X}{}^n)-G_1(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))\end{array}$

The function $G_1$ is a polynomial, since $a_1\ge a_2\ge \cdots \ge a_n$.
In addition, by the properties of symmetric polynomials $G_1(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))$ is a symmetric polynomial in variables $X_1,\dots ,X_n$, therefore so is $F_2$.
The polynomials $F_1(\overrightarrow{X}{}^n),G_1(\overrightarrow{E}{}^n(\overrightarrow{X}{}^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\ne 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{array}{cc}{F}_2(\overrightarrow{X}{}^n)& =G^{*}(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))\\ F_1(\overrightarrow{X}{}^n)& =G_1(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))+G^{*}(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))\end{array}$

2. The properties of the theorem hold:

• By definition, the degree of $G_1(\overrightarrow{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\ne 0$ is an integer. Therefore $G_1$ too has integer coefficients.

$◼$

Important results

Proof. By Vieta's formulae, we get:

$\begin{array}{cc}P(z)& =\sum _{k=0}^n{a}_k{z}^k\in 𝔽[z]\\ E_k(\overrightarrow{\alpha }{}^n)& =(-1{)}^k\frac{a_{n-k}}{a_n}\in 𝔽,(1\le k\le n)\end{array}$

By the fundamental theorem above, $G$ can be expressed as a polynomial

$\begin{array}{cc}G(\overrightarrow{X}{}^n)& =H(\overrightarrow{E}{}^n(\overrightarrow{X}{}^n))\in 𝔽[\overrightarrow{X}{}^n]\\ G(\overrightarrow{\alpha }{}^n)& =H(\overrightarrow{E}{}^n(\overrightarrow{\alpha }{}^n))\in 𝔽\end{array}$

$◻$

Proof. We will show that

$P_k(z)=\prod _{i=1}^m(z-{\beta }_i)\in 𝔽[z]$

By Vieta's formulae, its coefficients are all symmetric polynomials in ${\beta }_1,\dots ,{\beta }_m$.

Let $G\in 𝔽[\overrightarrow{Y}{}^m]$ be a symmetric polynomial, and let $Y_1,\dots ,Y_m$ be the sums/products of every $k$ of the variables $X_1,\dots ,X_n$.
Then $G$ can be expressed as a polynomial

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

It is easy to see that by applying a permutation on $X_1,\dots ,X_n$, we also apply a permutation on $Y_1,\dots ,Y_m$.
Hence $H\in 𝔽[\overrightarrow{X}{}^n]$ is a symmetric polynomial, and by the previous theorem we get

$G(\overrightarrow{\beta }{}^m)=H(\overrightarrow{\alpha }{}^n)\in 𝔽$

$◻$