Symmetric Polynomials #week 6

Well...

I haven't seen much symmetric polynomials in Olympiads, but still I am learning, because I found them cute. And I am basically using this blog as my notes :P

What are symmetric polynomials? 

One can understand this with  examples. If we are considering over 3 variables, $x_1,x_2,x_3$ then 

$$\sum_{sym}x_1^2\cdot x_2^3\cdot x_3=x_1^2\cdot x_2^3\cdot x_3+x_1^2\cdot x_3^3\cdot x_2+x_2^2\cdot x_1^3\cdot x_3+x_2^2\cdot x_3^3\cdot x_1+x_3^2\cdot x_1^3\cdot x_2.$$

See? $3!$ terms! Let's take one more example with again over 3 variables, $x_1,x_2,x_3$ then

$$\sum_{sym}x_1^2\cdot x_2^2= x_1^2\cdot x_2^2+x_1^2\cdot x_3^2+x_2^2\cdot x_1^2+x_2^2\cdot x_3^2+x_3^2\cdot x_1^2+x_3^2\cdot x_2^2$$

Wait.. why 2 times ? So basically what happens in symmetrictric sums, is we go through all $n!$ possible permutations. So, here we have $a^2\cdot b^2\cdot c^0$ as like the "general" form type, right? Now, list down all the $3!=6$ permutations of $x_1,x_2,x_3$, and put them in the general form, and then we sum it up.

So all possible permutations and then putting in the general form we get ,

${x_1,x_2,x_3}\rightarrow  x_1^2\cdot x_2^2$

${x_1,x_3,x_2}\rightarrow  x_1^2\cdot x_3^2$

${x_2,x_1,x_3}\rightarrow x_2^2\cdot x_1^2$

${x_2,x_3,x_1}\rightarrow x_2^2\cdot x_3^2$

${x_3,x_1,x_2}\rightarrow x_3^2\cdot x_1^2$

${x_3,x_2,x_1}\rightarrow x_3^2\cdot x_3^2$

Okie! Summing them and we will get the symmetric sums. So this makes sense I hope?

One thing to be noted is to not get confused between cyclic sums and symmetric sums.

To make things clear, Cyclic sums have only $n$ terms whereas in symmetric sums, we have $n!$ terms.

Let's go through another example , which I hope will perhaps clear this thing.

So considering  over $4$ variables, we get $$\sum_{cyc}x_1^2\cdot x_2=x_1^2\cdot x_2+x_2^2\cdot x_3+x_3^2\cdot x_4+x_4^2\cdot x_1.$$  

See $4$ terms rights? and we are summing it in "cycle" types. 

Well, if you are still confused then go through OTIS excerpts, it's really nice!

Elementary Symmetric Polynomials:

Nothing fancy here, just viettas with no signs type. 

The elementary symmetric polynomials in $n$ variables $x_1,x_2,\dots x_n$ can be defined as 

$$\sigma_1= \sum x_i$$

$$\sigma_2= \sum_{i<j} x_i\cdot x_j$$

$$\sigma_3=\sum_{i<j<k} x_i\cdot x_j\cdot x_k$$  

and so on with $$\sigma_n= x_1\cdot x_2 \dots x_n$$

Fundamental theorem of symmetric polynomials:

The fundamental theorem of symmetric polynomials states that any symmetric polynomial in n variables can be expressed  by a polynomial expression in terms of these elementary symmetric polynomials (uniquely).

And now we are going to take a lot of examples to verify this theorem !!! Oh, and why am I doing that? Again, I like to understand what's happening :P.

$$a^2+b^2+c^2=(a+b+c)^2-2(ab+bc+ca)={\sigma_1}^2-2\cdot \sigma_2$$

$$a^3+b^3=(a+b)(a^2+b^2-ab)=(a+b)({a+b}^2-3ab)=\sigma_1\cdot (\sigma_1^2-3\sigma_2)=\sigma_1 ^3-3\cdot \sigma_1\cdot \sigma_2$$

$$a^3+b^3+c^3=(a+b+c)^3 -3(\sum_{sym}a^2b)-6(abc)$$ $$=(a+b+c)^3-3(a+b+c)(ab+bc+ca)+9abc-6abc=\sigma_1^3-3\cdot \sigma_1\cdot \sigma_2+3\sigma_3$$

Okie this much was fine.. let's try $a^4+b^4+c^4$. So,

  $$a^4+b^4+c^4=(a+b+c)^4- 4(a^2+b^2+c^2)(ab+ca+bc)- 8(abc)(a+b+c)$$ $$=\sigma_1^4 -4({\sigma_1}^2-2\cdot \sigma_2)\cdot \sigma_2-8\sigma_3\cdot \sigma_1$$

These were simple.. now what about $\sum_{sym}x_1^2x_2x_3$ ? Note that,

$$2 \sum_{sym}x_1^2x_2x_3=2(\sum_{cyc}x_1x_2)^2- 2(\sum_{cyc}x_1^2x_2^2)=2\sigma_2^2-(x_1^2+x_2^2+x_3^2)^2 + (x_1^4+x_2^4+x_3^4)$$ $$= 2\sigma_2^2- [{\sigma_1}^2-2\cdot \sigma_2]^2+[\sigma_1^4 -4({\sigma_1}^2-2\cdot \sigma_2)\cdot \sigma_2-8\sigma_3\cdot \sigma_1]$$

Okie.. this looks fine to me.. but too tiresome.. T_T. I might have made some mistake :(

Newton Sums:

It's given in AOPS wiki. 

So we can basically find out any $x_1^d+\dots+x_n^d$, recursively using this 

$$a^n+b^n+c^n=(a+b+c)(a^{n-1}+b^{n-1}+c^{n-1})-(ab+bc+ca)(a^{n-2}+b^{n-2}+c^{n-2})+abc(a^{n-3}+b^{n-3}+c^{n-3}).$$

So this guarantees that we can express in the elementary symmetric polynomials form, however I am not quite sure about the uniqueness.. 

Yeah so that's it for today! I will do some problem solving now!

Sunaina💜