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$.

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}({\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 $F_{m+1}({\vec {X}}{}^{n})=F_{m}({\vec {X}}{}^{n})-G_{m}({\vec {E}}{}^{n}({\vec {X}}{}^{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}({\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