# Prove that every symmetric polynomial can be written in terms of the elementary symmetric polynomials

How do I prove that

any symmetric polynomial P is given by an expression involving only additions and multiplication of constants and elementary symmetric polynomials.

I have no clue of where to start, I just know the basic definition:

The polynomial $P(x_1,x_2,...,x_n)$ is symmetric if for any permutation $\sigma$ of $\{x_1,x_2,...,x_n\}$, $$P(x_1,x_2,...,x_n)=P(x_{\sigma_1},x_{\sigma_2},...,x_{\sigma_n})$$ The elementary symmetric polynomials for a polynomial consists of $n$ variables, $\{x_1,x_2,...,x_n\}$, and are defined as $\{e_1,e_2,...,e_n\}$: $$e_0=1\\ e_1=\sum_{i}x_i\\ e_2=\sum_{i,j}x_ix_j\\ e_3=\sum_{i,j,k}x_ix_jx_k\\ ....................\\ e_n=x_1x_2...x_n$$

Can I use induction, if possible where do I start ?

Proof for symmetric polynomials with two variables X, Y:

Let $$f(X,Y)$$ be a symmetric polynomial with degree n. By definition, $$f(X,Y)=f(Y,X)$$. Now, $$f(X,Y)= \sum_{0 \le i\le n,0\le j \le n,i+j\le n} a_{ij}X^iY^j$$ for some $$a_{ij}$$, and $$a_{ij}=a_{ji} \;\forall{0\le i \le n,0\le j\le n}.\;\;\;\;(*)$$

If $$\alpha,\beta \in{\mathbb R}, c$$ are some arbitrary constants, and $$f(X,Y), g(X,Y)$$ are two symmetric polynomials, then $$\alpha f(X,Y)+\beta g(X,Y)+c$$ is also a symmetric polynomial. This obviously extends to cases with multiple symmetric functions, i.e.

$$\sum_{j=1}^{p} \alpha_j f_j(X,Y)+c \; \text{is symmetric} \;\forall{\alpha_j \in{\mathbb R}, f_j \;\text{are all symmetric}} \;\;\;\;(**)$$

If n is even, then let $$n=2m$$ $$(X+Y)^n=X^n+\binom n 1 X^{n-1}Y+ \;...\;+\binom n mX^mY^m+ \;...\;+\binom n {n-1} XY^{n-1}+Y^n$$

If n is odd, then let $$n=2m+1$$ $$(X+Y)^n=X^n+\binom n 1 X^{n-1}Y+ \;...\;+\binom n mX^{m+1}Y^m+\binom n {m+1}X^mY^{m+1}+ \;...\;+\binom n {n-1} XY^{n-1}+Y^n$$

It is clear that $$(X+Y)^n$$ is symmetric $$\forall{n\in {\mathbb N}}$$. Moreover, $$\forall 0\le k\le n,$$ the $$k^{th}$$ term is the same as the $$(n+2-k)^{th}$$ term.

By $$(*)$$ and $$(**)$$ , it suffices to prove that every symmetric polynomial $$f_0(X,Y)$$ with at most 2 non-constant terms can be generated by $$X+Y$$ and $$XY$$, and that all polynomials with at most 2 non-constant terms generated by $$X+Y$$ and $$XY$$ are symmetric.

Suppose $$\mu X^iY^j$$ is symmetric, where $$i\ge 0, j\ge 0$$ are not both $$0$$. Then $$X^iY^j=X^jY^i,$$ which implies $$i=j$$.

Now, let us consider the polynomial $$\;\eta_1 X^iY^j + \eta_2 X^rY^s$$, where $$i+j \ne r+s, i+j \ne 0, r+s \ne 0$$. If it is symmetric, then $$\;\eta_1 X^iY^j + \eta_2 X^rY^s=\;\eta_1 X^jY^i + \eta_2 X^sY^r$$

This means either $$X^iY^j=X^jY^i,X^rY^s=X^sY^r$$ or $$\eta_1=\eta_2, X^iY^j=X^sY^r, X^jY^i=X^rY^s$$. Therefore, in the first case, $$i=j, r=s$$, and in the second case, $$i=s,j=r$$. Hence, all symmetric polynomials with two non-constant terms are of the form $$\eta X^iY^i+\omega X^jY^j+c \;\text{or}\; \gamma (X^iY^j+X^jY^i)+c$$.

Now, $$\mu X^iY^i$$ and $$\eta X^iY^i+\omega X^jY^j$$ can clearly be generated by $$XY$$, so we only have to check $$\gamma (X^iY^j+X^jY^i)\;,$$ where $$i\ne j$$.

Without loss of generality, suppose that $$i\gt j$$, so we have $$\gamma (X^iY^j+X^jY^i)=\gamma X^jY^j(X^{i-j}+Y^{i-j})$$. Now we only have to check if $$X^{i-j}+Y^{i-j}$$ can be generated by $$X+Y$$ and $$XY$$.

Let $$i-j=q$$. When $$q=1$$, $$X^q+Y^q$$ can trivially be generated by $$X+Y$$, since it's itself $$X+Y$$. When $$q=2, X^q+Y^q=X^2+Y^2=(X+Y)^2-2XY,$$ so $$X^q+Y^q$$ can be generated by $$X+Y$$ and $$XY$$ as well. Notice that

$$X^{q+1}+Y^{q+1}=(X^q+Y^q)(X+Y)-(XY^q+YX^q)=(X^q+Y^q)(X+Y)-XY(X^{q-1}+Y^{q-1})$$

Therefore, $$X^{q+1}+Y^{q+1}$$ can be generated by $$X+Y,XY,X^{q-1}+Y^{q-1},$$ and $$X^q+Y^q$$. Hence, by induction,$$\forall{q\in {\mathbb N}}, X^q+Y^q$$ can be generated by $$X+Y$$ and $$XY$$. This means

$$\gamma(X^iY^j+X^jY^i)$$ can be generated by $$X+Y$$ and $$XY$$, hence all symmetric polynomials $$f(X,Y)$$ can be generated by $$X+Y$$ and $$XY$$.

All polynomials of degree n generated by $$X+Y$$ and $$XY$$ are of the form $$\sum_{0 \le i'\le n,0\le j' \le n,i'+j'\le n} \kappa_{i'j'}(X+Y)^{i'}(XY)^{j'}$$

Each term of this sum is symmetric, so the sum is symmetric as well. Hence, every polynomial generated by $$X+Y$$ and $$XY$$ is symmetric, and every symmetric polynomial can be generated by $$X+Y$$ and $$XY$$.