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

-
+1 Great answer. (I'm not gonna lie though, this hypothesis turned out to be a lot more complicated than what I'd hoped for!) – anon Apr 29 '12 at 22:50

I think that if n is odd then $\sum (\sum_{i=1}^n\epsilon_i x_i)^n = 2^{n-1}x_1 \times ... \times x_n$ where the outside sum goes over all sequences $\epsilon_1,....,\epsilon_n$ of $\pm 1$'s whose product is 1. I have a probabalistic proof, and have checked n=3. It is convenient that if n is odd one the terms in the expansion can't all be even powers.

-
I checked the $n=3$ case and it's zero. Indeed the coefficient of $x_1\cdots x_n$ in the expansion of that sum will, for any $n$, be $$\sum_{k=0}^n\binom{n}{k}(-1)^k=0,$$ as there are precisely $\binom{n}{k}$ sequences of $\epsilon_i$ such that $k$ are $-1$ and $n-k$ are $+1$. – anon Apr 28 '12 at 21:21