# Can $e_n$ always be written as a linear combination of $n$-th powers of linear polynomials?

User Eric Gregor and I were talking in chat and he mentioned this question and postulated the possibility of an approach through symmetric polynomials. After some thinking, I came to this:

Hypothesis. For any $n$, the elementary symmetric polynomial $e_n\in k[x_1,\cdots,x_n]$ can be expressed as a $k$-linear combination of $n$th powers of degree one homogeneous polynomials.$^\dagger$

$^\dagger$We assume the characteristic does not divide $n!$. We could assume it's zero for more simplicity.

Let us denote $s(a,b,\cdots,c)=(a+b+\cdots+c)^n-(a^n+b^n+\cdots+c^n).$ I have two examples:

$$xy=\frac{s(x,y)}{2} \tag{n=2}$$

$$xyz=\frac{s(x,y,z)-\big(s(x,y)+s(y,z)+s(z,x)\big)}{6} \tag{n=3}$$

My scratchwork was getting tedious so I didn't finish the $n=4$ case. Besides this I haven't really made any substantive headway, but I did derive the following equality. We denote $\mathrm{pt}\,\lambda$ the number of parts of an integer partition $\lambda\vdash n$, and $m_\lambda$ the sum of all monomials of shape $\lambda$ in $x_j,j\in J$.

$$T_{J,\ell}:=\sum_{\large I\subseteq J \atop \large |I|=\ell}\left(\sum_{i\in I}x_i\right)^n=\sum_{\large \lambda\vdash n \atop \large \mathrm{pt}\lambda\le\ell}\binom{n}{\lambda}\binom{|J|-|I|}{\ell-\mathrm{pt}\,\lambda}m_\lambda.$$

This can be justified as follows: expanding the inner summands of the LHS with the multinomial theorem will result in the terms $m_\lambda$ (with the appropriate multinomial coefficents), times the count of supersets $I$ ($\subseteq J$) of cardinality $\ell$ containing a particular subset $K$ of cardinality $\mathrm{pt}\,\lambda$; construct such $I$ by choosing $|K/I|$ elements out of $|J/I|$ available. In our context $J=[n]$ of course.

The reason I mention this is that the $T_{[n],\ell}$'s appear to be relevant in the computations I was going through for $n=2,3,4$ (as if inverting a linear system in the $m_\lambda$'s...). It may or may not be the correct way of thinking about the problem. I guess my question is then:

• Is the hypothesis correct?
• If so, how would we prove it?
• (Optional) If this isn't already inherently answered in the hypothetical proof, how would we explicitly compute what the combinations of powers are?

Yes, the hypothesis is correct. There is an explicit construction. Let $$t(i,n) := \sum_{1 \le k_1 < k_2 < \ldots < k_i \le n} s(x_{k_1},\ldots,x_{k_i}).$$ Then $$x_1 \cdots x_n = \frac{1}{n!} \sum_{i=0}^{n-2} (-1)^{i} t(n-i,n).$$
Proof. Use the definition of $t$ and the multinomial theorem to obtain the equivalent statement $$n! \cdot x_1 \cdots x_n = \sum_{i=0}^{n-2} (-1)^i \sum_{1 \le k_1 < \ldots < k_{n-i} \le n} ~~ \sum_{a_1+\ldots+a_{n-i}=n,~a_j \neq n} \binom{n}{a_1,\ldots,a_{n-i}} \prod_{j=1}^{n-i} x_{k_j}^{a_j}.$$ Consider fixed sequences $0< b_1,\ldots,b_m < n$ with $\sum_j b_j = n$ and $1 \le r_1,\ldots,r_m \le n$. The monomial $f := \prod_j x_{r_j}^{b_j}$ appears in all summands of the outer sum with $0 \le i \le n-m$ by choosing $k_j := r_j$ and $a_j := b_j$ for $j \le m$ and $k_j \in (\{1,\ldots,n\} - \{r_j : 1 \le j\le n-i\})$, $b_j := 0$ for $j>m$ (permute indices to meet the "<" requirement). Obviously there are $\binom{n-m}{n-i-m}$ ways to choose the $k_j$s for fixed $i$. Also observe that the multinomial coefficient is the same for every summand (since joining zeroes doesn't change it).
So the total coefficient of the monomial $f$ on the RHS equals $\sum_{i=0}^{n-m} (-1)^i \binom{n-m}{n-m-i} \binom{n}{b_1,\ldots,b_m}$. For $m<n$, this sum equals $0$. For $n=m$, it equals $n!$, which concludes the proof.