Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?
share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
+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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.