representing multi variable monomials using powers of linear functions

Question

Prove that there exists $2^n$ linear functions $f_i(x_1,\dots,x_n)$ such that

$$x_1\cdots x_n=\sum_{i=1}^{2^n}f_i^n(x_1,\dots,x_n)$$

Hint

Consider the formula for the permanent.

It seems that induction doesn't help here.

Answer 1

Let $N=\{1, 2, \dots, n\}$. The answer relies on the following

Theorem. $$\sum_{I \subseteq N} (-1)^{n-|I|} \left(\sum_{i\,\in\,I} x_i\right)^n = n! \prod_{i \in N} x_i.$$ Proof. Let $P(x_1, x_2, \dots, x_n)$ be the polynomial from the left side. Its value is zero if any of $x_i$ equals zero. Indeed, we can split the summands in the definition of $P$ into pairs such that elements in every pair differ only in sign and presence of $x_i$. Thus, the sum in each pair equals $0$ if $x_i=0$ and so does the whole sum. Representing $P$ as $P \equiv x_iQ+R$, where $Q$ and $R$ are some polynomials and $R$ doesn't depend on $x_i$, and substituting $x_i=0$ we see that $R \equiv 0$. Thus, $P \equiv x_iQ$ and each monomial in expanded and reduced form of $P$ must contain $x_i$. As this is true for any $i \in N$, each monomial must contain all of $x_i$, i.e. at least the product $x_1 x_2 \dots x_n$. But as the degree of $P$ is $n$, $P$ is nothing else than $k\prod_{i \in N} x_i$ for some constant $k$. To finish the proof, we must prove that $k=n!$. The substitution $x_1=x_2=\dots=x_n=1$ leads this to the identity $\sum_{i=0}^n (-1)^{n-i} \binom n i i^n=n!$ or, equivalently, $$\sum_{j=0}^n (-1)^j \binom n j (n-j)^n=n!.$$ It has simple combinatorial proof using the inclusion-exclusion principle. Just note that the right side is the number of permutations of $N$ while the left side counts them in the set of $n^n$ tuples of kind $(t_1, t_2, \dots, t_n)$, where $t_i \in N$, using the list of properties $A_t=\text{"$t$ is missing in a tuple"}$. A combination of $j$ such properties, that can be chosen $\binom n j$ ways, implies counting $n$-tuples consisting only of elements not excluded by the chosen properties, and there are $n-j$ such elements. $\blacksquare$

The rest is easy. There are $2^n$ subsets of indices and we only need to adjust the coefficients bringing them into braces. Thereby, the sum transforms into $$\sum_{I \subseteq N} \left((n!)^{-1/n} k(n-|I|,n) \sum_{i\,\in\,I} x_i\right)^n,$$ where $$k(m,n) = \left\{\begin{array}{cl} 1, & \text{if $m$ is even} \\ -1, & \text{if $m$ is odd, n is odd} \\ \cos {\frac {\pi} n} + i \sin {\frac {\pi} n}, & \text{if $m$ is odd, n is even} \end{array}\right.$$ (the last case is a primitive $2n$th root of unity).