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

Fundamental Theorem of Symmetric Polynomials: Let $\mathbb {F}$ be a field, and let $F\in \mathbb {F} [{\vec {X}}^{n}]$ be a symmetric polynomial. Then $F$ can be expressed uniquely as a polynomial $G({\vec {E}}^{n}({\vec {X}}^{n}))\in \mathbb {F} [{\vec {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 describe an algorithm for finding the desired polynomial $G$.
Let us define initial conditions $m=1$ and $F_{1}=F$.
* 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$.
* Define $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}}$.
* Write $F_{m+1}({\vec {X}}^{n})=F_{m}({\vec {X}}^{n})-G_{m}({\vec {E}}^{n}({\vec {X}}^{n}))$.
* 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.
* 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}({\vec {E}}^{n}({\vec {X}}^{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}$. 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\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}}$.
By lemma 2, we get:
    ${\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 $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}({\vec {E}}^{n}({\vec {X}}^{n}))$ is a symmetric polynomial in variables $X_{1},\ldots ,X_{n}$, therefore so is $F_{2}$. The polynomials $F_{1}({\vec {X}}^{n}),G_{1}({\vec {E}}^{n}({\vec {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}\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}({\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 $G_{1}({\vec {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 $P\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} [{\vec {X}}^{n}]$ be a symmetric polynomial. Then $G({\vec {\alpha }}^{n})\in \mathbb {F}$.
Proof. By Vieta's formulae, we get:
    ${\begin{aligned}P(z)&=\sum _{k\,=\,0}^{n}a_{k}z^{k}\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 theorem above, $G$ can be expressed as a polynomial
    ${\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}}$
$\square$
Theorem: Let $\mathbb {F} \subseteq \mathbb {E}$ be a field, and let $P\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/products of every $k$ of the roots (namely $m={\tbinom {n}{k}}$). Then there exists a monic polynomial $P_{k}\in \mathbb {F} [z]$ of degree $m$ with roots $\beta _{1},\ldots ,\beta _{m}$.
Proof. We will show that
    $P_{k}(z)=\prod _{i\,=\,1}^{m}(z-\beta _{i})\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} [{\vec {Y}}^{m}]$ be a symmetric polynomial, and let $Y_{1},\ldots ,Y_{m}$ be the sums/products of every $k$ of the variables $X_{1},\ldots ,X_{n}$. Then $G$ can be expressed as a polynomial
    $G({\vec {Y}}^{m})=H({\vec {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} [{\vec {X}}^{n}]$ is a symmetric polynomial, and by the previous theorem we get
    $G({\vec {\beta }}^{m})=H({\vec {\alpha }}^{n})\in \mathbb {F}$
$\square$
| ←Elementary Symmetric Polynomials | Fundamental Theorem of Symmetric Polynomials |