A Universe of Sorts

§ 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$ .

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}

\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}

\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}

\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}

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$ .

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) \\

(k-i)(replicate 1 i) = (k-i+1, replicate 1 [i-1]) + (k-i , replicate 1 i)