Putnam 2004, Problem A-4

Show that for any positive integer $n$ there is an integer $N$ such that the product $x_1 x_2 \cdots x_n$ can be expressed identically in the form
\[
x_1 x_2 \cdots x_n = \sum_{i=1}^N c_i (a_{i1} x_1 + a_{i2} x_2 + \cdots + a_{in} x_n)^n
\]
where the $c_i$ are rational numbers and each $a_{ij}$ is one of the numbers $-1, 0, 1$.

Solution:
It suffices to verify that
$$x_1\cdots x_n = \frac{1}{2^n n!} \sum_{e_i \in \{-1,1\}} (e_1\cdots e_n)(e_1x_1 + \cdots + e_nx_n)^n.$$

To check this, first note that the right side vanishes identically for $x_1 = 0$, because each term cancels the corresponding term with $e_1$ flipped. Hence the right side, as a polynomial, is divisible by $x_1$; similarly it is divisible by $x_2, \ldots, x_n$. Thus the right side is equal to $x_1\cdots x_n$ times a scalar. (Another way to see this: the right side is clearly odd as a polynomial in each individual variable, but the only degree $n$ monomial in $x_1, \ldots, x_n$ with that property is $x_1\cdots x_n$.) Since each summand contributes $\frac{1}{2^n}x_1\cdots x_n$ to the sum, the scalar factor is 1 and we are done.

**Remark:** Several variants on the above construction are possible; for instance,
$$x_1\cdots x_n = \frac{1}{n!} \sum_{e_i \in \{0,1\}} (-1)^{n-e_1-\cdots-e_n}(e_1x_1 + \cdots + e_nx_n)^n$$
by the same argument as above.

**Remark:** These construction work over any field of characteristic greater than $n$ (at least for $n > 1$). On the other hand, no construction is possible over a field of characteristic $p \leq n$, since the coefficient of $x_1\cdots x_n$ in the expansion of $(e_1x_1 + \cdots + e_nx_n)^n$ is zero for any $e_i$.

**Remark:** Richard Stanley asks whether one can use fewer than $2^n$ terms, and what the smallest possible number is. Eliyahu Yablon notes that one can reduce the count to $2^{n-1}$ by combining opposite terms:
$$x_1\cdots x_n = \frac{1}{2^{n-1}n!} \sum_{e_2,\ldots,e_n \in \{-1,1\}} (e_2\cdots e_n)(x_1 + e_2x_2 + \cdots + e_nx_n)^n.$$