## § Elementary and power sum symmetric polynomials

• Let us have $n$ variables $x[1], x[2], \dots, x[n]$.
• Let $e_k$ be the elementary symmetric polynomial that is all products of all $k$ subsets of $x[:]$.
• Let $p_k$ be the power sum symmetric polynomial that is of the form $p_k = \sum_i x[i]^k$.

#### § Speedy proof when $k = n$ / no. of vars equals largest $k$ (of $e[k]$) we are expanding:

• Let $P(x) = e[n] x^0 + e[n-1]x^1 + \dots + e[1]x^{n-1} + e[0]x^n$. That is, $P(x) = \sum_i e[n-i] x^{i}$
• Let $r[1], r[2], \dots, r[n]$ be the roots. Then we have $P(r[j]) = \sum_i e[n-i] r[j]^{i} = 0$.
• Adding over all $r[j]$, we find that:
\begin{aligned} &\sum_{j=1}^k P(r[j]) = \sum_j 0 = 0\\ &\sum_j \sum_i e[n-i] r[j]^{i} = 0 \\ &\sum_j \sum_i e[n-i] r[j]^{i} = 0 \\ &\sum_j e[n] \cdot 1 + \sum_j \sum_{i>0}^k e[n-1] r[j]^i = 0 \\ k e[n] + &\sum_{i=1}^k e[i] P[n-i] = 0 \end{aligned}

#### § Concretely worked out in the case where $n = k = 4$:

\begin{aligned} &P(x) = 1 \cdot x^4 + e_1 x^3 + e_2 x^2 + e_3 x + e_4 \\ &\texttt{roots: } r_1, r_2, r_3, r_4\\ &P(x) = (x - r_1)(x - r_2)(x - r_3)(x - r_4)\\ &e_0 = 1 \\ &e_1 = r_1 + r_2 + r_3 + r_4 \\ &e_2 = r_1r_2 + r_1r_3 + r_1r_4 + r_2r_3 + r_2r_4 + r_3r_4 \\ &e_3 = r_1r_2r_3 + r_1r_2r_4 + r_2r_3r_4 \\ &e_4 = r_1r_2r_3r_4\\ \end{aligned}
• Expanding $P(r_j)$:
\begin{aligned} P(r_1) &= r_1^4 + e_1r_1^3 + e_2r_1^2 + e_3 r_1 + e_4 = 0 \\ P(r_2) &= r_2^4 + e_1r_2^3 + e_2r_1^2 + e_3 r_1 + e_4 = 0 \\ P(r_3) &= r_3^4 + e_1r_3^3 + e_2r_1^2 + e_3 r_1 + e_4 = 0 \\ P(r_4) &= r_4^4 + e_1r_4^3 + e_2r_1^2 + e_3 r_1 + e_4 = 0 \\ \end{aligned}
• Adding all of these up:
\begin{aligned} &P(r_1) + P(r_2) + P(r_3) + P(r_4) \\ &=(r_1^4 + r_2^4 + r_3^4 + r_4^4) &+ e_1(r_1^3 + r_2^3 + r_3^3 + r_2^3) &+ e_2(r_1^2 + r_2^2 + r_3^2 + r_4^2) &+ e_3(r_1 + r_2 + r_3 + r_4) &+ 4 e_4 \\ &= 1 \cdot P_4 e_1 P_3 + e_2 P_2 + e_3 P_1 + 4 e_4 \\ &= e_0 P_4 + e_1 P_3 + e_2 P_2 + e_3 P_1 + 4 e_4 \\ &= 0 \\ \end{aligned}

#### § When $k > n$ (where $n$ is number of variables):

• We have the identity $k e_k + \sum_{i=0}^{k-1} e_i p_{k-i} = 0$. (when $i = k$, we get $p_{k-i} = p_0 = 1$, this gives us the $k e_i = k e_k$ term).
• When $k > n$, this means that $e_k = 0$.
• Further, when $k > n$, this means that $s_i$ when $i > n$ is zero.
• This collapses the identity to $\sum_{i=0}^{k-1} e_i p_{k-i} = 0$ (we lose $e_k)$, which further collapses to $\sum_{i=0}^n e_i p_{k-1} = 0$ (we lose terms where $k - 1 > n$)
• Proof idea: We add ( $k-n$) roots into $f$ to bring it to case where $k = n$. Then we set these new roots to $0$ to get the identity $\sum_{i=0}^n s_i p_{k-i} = 0$.

#### § Proof by cute notation

• Denote by the tuple $(a[1], a[2], \dots, a[n])$ with $a[i] \geq a[i+1]$ the sum $\sum x[i]^a[i]$.
• For example, with three variables $x, y, z$, we have:
• $(1) = x + y + z$
• $(1, 1) = xy + yz + xz$
• $(2) = x^2 + y^2 + z^2$
• $(2, 1) = x^2y + y^2z + z^2x$
• $(1, 1, 1) = xyz$.
• $(1, 1, 1, 1) = 0$, because we don't have four variables! We would need to write something like $xyzw$, but we don't have a $w$, so this is zero.
• In this notation, the elementary symmetric functions are $(1)$, $(1, 1)$, $(1, 1, 1)$ and so on.
• The power sums are $(1)$, $(2)$, $(3)$, and so on.
• See that $(2)(1) = (x^2 + y^2 + z^2)(x + y + z) = x^3 + y^3 + z^3 + x^2y + x^2z + y^2x + y^2z + z^2x + z^2y = (3) + (2, 1)$.
• That is, the product of powers gives us a larger power, plus some change (in elementary symmetric).
• How do we simplify $(2, 1)$? We want terms of the form only of $(k)$ [power sum ] or $(1, 1, \dots, 1)$ [elementary ].
• We need to simplify $(2, 1)$.
• Let's consider $(1)(1, 1)$. This is $(x + y + z)(xy + yz + xz)$. This will have terms of the form $xyz$ (ie, $(1, 1, 1)$). These occur with multiplicity $3$, since $xyz$ can occur as $(x)(yz)$, $(y)(xz)$, and $(z)(xy)$. This will also have terms of the form $x^2y$ (ie, $(2, 1)$).
• Put together, we get that $(1)(1, 1) = (2, 1) + 3 (1, 1, 1)$.
• This tells us that $(2, 1) = (1)(1, 1) - 3(1, 1, 1)$.
• Plugging back in, we find that $(2)(1) = (3) + (1)(1, 1) - 3 (1, 1, 1)$. That is, $p[3] - p[2]s[1] + p[1]s[2] - 3s[3] = 0$.
In general, we will find:
$(k-1)(1) = (k) + (k-1, 1) \\ (k-2)(1, 1) = (k-1, 1) + (k-2, 1, 1) \\ (k-3)(1, 1, 1) = (k-2, 1, 1) + (k-3, 1, 1, 1) \\ (k-4)(1, 1, 1, 1) = (k-3, 1, 1, 1) + (k-4, 1, 1, 1, 1) \\$
• In general, we have:
(k-i)(replicate 1 i) = (k-i+1, replicate 1 [i-1]) + (k-i , replicate 1 i)