MrMineev

Symmetric Polynomials

1 Elementary Symmetric Polynomials

When dealing with polynomials, it is sometimes useful to introduce the idea of Symmetric Polynomials. A Symmetric Polynomial is simply a polynomial that has the same result no matter the order in which the input variables are given. The simplest example would be the product of three variables $a,b$ and $c$ .

This polynomial is indeed symmetric as $f(a,b,c) = f(b,c,a) = f(c,a,b) = ...$ . Swapping the values of some of the variables with each other does not change the outcome. If one tries to generate all symmetric polynomials with three variables, which sort of satisfy a ”simplicity” rule (which for now is not well defined), then they might end with such a result.

e1(a,b,c) = a+ b + c

e2(a,b,c) = ab+ bc+ ac
e3(a,b,c) = abc

Looking at these polynomials, one can start developing the idea of an Elementary Symmetric Polynomial. The sum of all possible subsets of the input variables of the size $n$ , is often denoted as $en$ or sometimes $σn$ . From this definition, you can try to complete the listed elementary symmetric polynomials with a new one.

However, throughout this chapter, the knowledge about Elementary Symmetric Polynomials with more than three variables will be unnecessary, it is still useful to keep in mind the definition of everything we describe for a greater number of variables. For now, consider what we have and try to prove some properties about $e1,e2$ and $e3$ . It is often useful to represent symmetric equations using elementary symmetric polynomials (more about this later).

2 Newton-Girard Formula for Symmetric Polynomials in three variables

Something that holds a specific point of interest is the expressions of the form $ak + bk + ck$ . For this specific problem there exists the Newton-Girard Formula for Symmetric Polynomials. Define a function $Sk(x1,...,xn)$ in the following way.

Then, the theorem claims that there exists a recursive formula for calculating $Sk$ .

S1 = e1
S2 = S1e1 - 2e2
S3 = S2e1 - s1e2 + 3e3
...
( )
k∑-1 j k
Sk = - (- 1) Sk-jej - (- 1)kek
i=1

The proof of the statement will not be provided here. Here, I will not be considering the formula for more than three variables, as mentioned earlier. The Newton-Girard Formula for three variables looks way simpler.

Proving this statement is way much simpler than the general form of the Newton-Girard Formula.

e1Sk- 1 - e2Sk-2 + e3Sk-3 = (a+ b +c)(ak-1 + bk-1 + ck-1)-
k-2 k-2 k-2 k- 3 k- 3 k- 3
(ab+ bc+ ac)(a + b +c )+ abc(a + b + c ) =
ak + bk + ck + abk-1 + ack-1 + bak-1 + bck-1 + cak-1 + cbk-1
- bcak-2 - bak-1 - cak-1 - acbk-2 - abk-1 - abck-2 - ack-1 - cbk- 1 - bck- 1

+ bcak-2 + acbk-2 + abck-2 = ak + bk + ck

3 Symmetric Inequality

Consider a simple inequality.

Notice, that this is a simple consequence of the Rearrangement Inequality. However, there exists another elegant solution that requires no knowledge of any inequalities.

2 2 2 1 2 2 2 2 2 2
a + b + c - ab- bc- ca = 2(a - 2ab+ b + a - 2ac +c + b - 2bc+ c )
1 2 2 2
= 2(a- b)(a- c) (b- c) ≥ 0

Now that we have proven this inequality, let us transform it into an elementary symmetric polynomial form.

Another simple equation that we can prove is that $e22 ≥ 3e1e3$ . We can prove this by just substituting the definitions of $e1,e2$ and $e3$ .

(ab+ bc+ ac)2 ≥ 3abc(a + b+ c)
a2b2 + 2a2bc+ a2c2 + 2ab2c+ 2abc2 + b2c2 ≥ 3a2bc+ 3ab2c+ 3abc2
2 2 2 2 22 2 2 2
a b + a c + b c ≥ a bc+ abc + abc

The last inequality is simply proven using the Rearrangement inequality by taking $x = [ab,bc,ac]$ and the same $y = [ab,bc,ac]$ , we assume $ab ≤ bc ≤ ac$ and get the following.

a2b2 + b2c2 + a2c2 = x1y1 + x2y2 +x3y3
2 2 2
≥ x1y3 + x2y1 + x1y2 = a bc+ ab c+ abc

These two inequalities ( $2 e1 ≥ 3e2$ and $2 e2 ≥ 3e1e3$ ) are the most useful ones. Using these inequalities along with basic usage of other common inequalities can help solve a variety of different problems. One might notice that most of the techniques somehow transform an equation or inequality into a form involving purely elementary symmetric polynomials and can ask the question: what if such a form does not exist? Happily, for us, there is a theorem called the Fundamental Theorem of Symmetric Polynomials, which claims that any symmetric polynomial can, in fact, be expressed as an expression using elementary symmetric polynomials (the theorem applies to any number of variables). The proof of this statement will also not be provided here due to its complexity.

4 Systems of Symmetric Equations

Say we have three systems of symmetric equations as the following.

(
|| x+ y+ z = 1
|{ x2 + y2 + z2 = 2
| x3 + y3 + z3 = 3
||(

We want to find the value of $4 4 4 x + y + z$ , for example. First of all, transform the equations using elementary symmetric polynomials.

(|e = 1
{ 12
|(e1 - 2e2 = 2
S3 = e1S2 - e2S1 + e3S0 = e31 - 2e1e2 - e2e1 + 3e3 = e31 - 3e1e2 + 3e3 = 5

Now from this we get that $e1 = 1$ , $1 e2 = - 2$ and from the third equation we can find $e3$ .

3e3 = 3- e31 + 3e1e2 = 3 - 1 - 3⋅1⋅ 1= 1
2 2
e3 = 1
6

From here, it is simple to extend our knowledge to calculate $x4 + y4 + z4$ using the Newton-Girard Formula.

S = e S - e S + e S = 3 + 1⋅2 + 1 = 25
4 1 3 2 2 3 1 2 6 6

However, this wasn’t really solving a system of symmetric equations; all that happened really was just applying the Newton-Girard Formula multiple times. Now, let us consider something harder.

(
|{ xy+ yz + xz + xyz = 17
x2yz + xy2z + xyz2 = 36
|( 2 2 2 2 2 2
xy + x z + xy + 3xyz + xz + y z + yz = 66

And again find $4 4 4 x +y + z$ . Do the same as last time: express the system using elementary symmetric polynomials.

(|e + e = 17
||{ 2 3
e1e3 = 36
|||(e1e2 = 66

The problem of expressing symmetric polynomials through elementary symmetric polynomials has a solution; however, almost always, it is just simpler to notice patterns and try to factor and transform the equation on your own. Now all that is left is to solve for $e1,e2$ and $e3$ .

e1e3 + e1e2 = e1(e2 + e3) = 17e1 = 102 ⇐ ⇒ e1 = 6
e = 66= 11
2 6
e = 36 = 6
3 6

Now, a cool trick to keep in mind is that sometimes we are interested in finding such a cubic polynomial $P(t)$ such that $x,y,z$ are all roots of that polynomial. This would be useful as from there we can immediately find the solution in the following way.

(
|{ ax3 + bx2 + cx +d = 0
ay3 + by2 + cy+ d = 0
|( az3 + bz2 + bz + d = 0
(
|{ ax4 + bx3 + cx2 + dx = 0
ay4 + by3 + cy2 + dy = 0
|( az4 + bz3 + bz2 + dz = 0
4 4 4 3 3 3 2 2 2
a(x + y + z) +b(x + y +z )+ c(x + y + z )+ d(x+ y + z) = 0
aS4 + bS3 + cS2 + dS1 = 0
- dS1 - cS2 - bS3
S4 =-------a-------

Making such a polynomial is surprisingly simple. If you want $x,y,z$ to be roots of a polynomial $P (t)$ , simply let $P(t) = (t- x)(t- y)(t- z)$ . Expanding out the expression, we get the following.

P(t) = t3 - t2x - t2y - t2z +txy + txz + tyz - xyz
= t3 - t2(x + y+ z)+ t(xy+ xz +yz) - xyz

As you can see, all the coefficients are known; they are just the elementary symmetric polynomials! This trick applies to an even greater number of variables.

n
∏ (t- ai) = tn - e1tn-1 +e2tn-2 - ...
i=1

However, again, here, we will not be looking at more than three variables. Going back to our result, we can now provide such $P (t)$ .

Now, everything left to apply our solution to find $S4$ is to calculate $S1,S2$ and $S3$ .

S = e = 6
2 1 1
S2 = e1 - 2e2 = 36- 2 ⋅11 = 14
S3 = e31 - 3e1e2 + 3e3 = 216- 3 ⋅6⋅11+ 3 ⋅6 = 36

Substitution all the gathered information we can find $S4$ .

This concludes the solution. What I want you to notice is that the whole idea of finding a polynomial with roots $x,y,z$ is unnecessary; one could replace all the calculations by simply calculating $S4$ through $S1,S2,S3$ and $e1,e2,e3$ . In fact, what was just described is yet another proof or perspective on the Newton-Girard Formula. Obviously, in such cases, using the Newton-Girard Formula directly is best. However, if you forgot, you could always remember it using this trick.

1 Elementary Symmetric Polynomials
2 Newton-Girard Formula for Symmetric Polynomials in three variables
3 Symmetric Inequality
4 Systems of Symmetric Equations