§ Fundamental theorem of symmetric polynomials

• Every symmetric polynomial of variables $x, y, z$ can be written in terms of the elementary symmetric polynomials $\sigma_0 \equiv 1$, $\sigma_1 = x + y + z$, $\sigma_2 = xy + yz + xz$. Generalize appropriately.

§ Two variable case

• For even further simplicity, consider the two variable case: every symmetric polynomial of variables $x, y$ can be written in terms of the elementary symmetric polynomials $\sigma_0 = 1$, $\sigma_1 = x + y$, $\sigma_2 = xy$.
• Consider some symmetric polynomial $p(x)$. Define an ordering on its monomials $x^ay^b > x^c y^d$ iff either $a + b > c + d$, or $a > c$, or $a = c \land b > d$. So we compare first by degree, then by $(a, b) > (c, d)$ lexicographically. Thus, call this order the lex order.
• Define bigmon(p) to be the largest monomial in $p(x)$. Define bigcoeff(p) to be the coefficient of bigmon(p). Finally, define bigterm(p) = bigmon(p) . bigcoeff(p) as the leading term of the polynomial $p(x, y)$.
• Prove an easy theorem that bigterm(pq) = bigterm(p)bigterm(q).
• Now, suppose we have a leading monomial $x^5y^9$. Actually, this is incorrect! If we have a monomial $x^5y^9$, then we will also have a monomial $x^9y^5$, which is lex larger than $x^5y^9$. Thus, in any leading monomial, we will have the powers be in non-increasing (decreasing order).
• OK, we have leading monomial $x^9 y ^5$. We wish to write this in terms of elementary symmetric polynomials. We could try and write this by using the leading term $x$ in $s_1$ and leading term $xy$ in $s_2$.
• This means we need to solve $x^9y^5 = x^k (xy)^l$, or $9 = k + l$ and $5 = l$. This tells us that we should choose $l = 5$ and $k = 9 - 5 = 4$. If we do this, then our combination of symmetric polynomials will kill the leading term of $p(x)$. Any new terms we introduce will be smaller than the leading term, which we can write as elementary symmetric polynomials by induction!

§ Three variable case

• Now consider three variables. Once again, suppose $p(x)$ has leading monomial $x^ay^bz^c$. We saw earlier that we must have $a \geq b \geq c$ for it to be a leading monomial.
• Let's write it in terms of $s_1, s_2, s_3$. So we want to write it as product of $(x)^p$, $(xy)^q$, and $(xyz)^r$. Their product is $x^{p+q+r}y^{q+r}z^r$.
• This gives us the system of equations $x^{p+q+r}y^{q+r}z^r = x^ay^bz^c$. This means (1) $r = c$, (2) $q+r = b$ or $q = b - c$, and (3) $p + q + r = a$or $p = a - q - r = a - (b - c) - c = a - b$.

§ General situation

• think of the monomial $x^ay^bz^c$ as a vector $[a, b, c]$. Then the leading terms of the symmetric polynomials correspond to $[1, 0, 0]$, $[1, 1, 0]$, and $[1, 1, 1$].
• When we take powers of symmetric polynomials, we scale their exponent vector by that power. So for example, the leading term of $s_2^9$ is $x^9y^9$ which is $[9, 9] = 9[1, 1]$.
• When we multiply symmetric polynomials, we add their exponent vectors. For example, the leading term of $s_1 s_2$ is $x(x+y) = x^2 y = [2, 1]$. This is equal to $[1, 0] + [1, 1]$
• Thus, we wish to write the vector $[a, b, c]$ as a linear combination of vectors $[1, 0, 0]$, $[1, 1, 0]$, and $[1, 1, 1]$. This is solving the equation:

[a]   [1 1 1][p]
[b] = [0 1 1][q]
[c]   [0 0 1][r]

• subject to the conditions that the unknowns $p, q, r, \geq 0$, given knowns $a, b, c$such that $a \geq b \geq c$.
• Let's check that the equation makes sense: $a = p + q + r$ as all of $[1, 0, 0]$, $[1, 1, 0]$ and $[1, 1, 1]$have a $1$ at the $a$ position. Similarly for $b, c$.
• Solve by the usual back-substitution.