A linear form in $k$ variables is an expression of the form $P(x_1,...,x_k)=a_1x_1+...+a_kx_k$ with real constants $a_1,...,a_k$. Prove that there exist a positive integer $n$ and linear forms $P_1,...,P_n$ in $2017$ variables such that the equation $$x_1\cdot x_2\cdot ... \cdot x_{2017}=P_1(x_1,...,x_{2017})^{2017}+...+P_n(x_1,...,x_{2017})^{2017}$$holds for all real numbers $x_1,...,x_{2017}$.
Problem
Source: Baltic Way 2017 Problem 4
Tags: algebra, equation, polynomial
ThE-dArK-lOrD
14.11.2017 21:00
Choose $n=2^{2017}$ and $$\{ P_1,P_2,\dotsc ,P_n\} =\left\{ \sum_{i =1}^{2017}{\frac{\prod_{j =1}^{2017}{\epsilon_j}}{\epsilon_i}x_i} \mid \epsilon_1,\epsilon_2,\dotsc ,\epsilon_{2017}\in \{ -1,1\} \right\}.$$
Tintarn
14.11.2017 21:54
This problem was proposed by me. I know of three essentially different solutions, two of them using a modest amount of linear algebra and the third one being the one in #2 (the existence of that latter one really was the reason to propose this for such a competition).
By induction. In the induction step, we need to prove that we can "diagonalise" $X^nY$ as a linear combination of $k+1$-st powers of linear forms.
So write $X^nY=\sum_{i=0}^m \alpha_i(x+\beta_i)^{n+1}$. After expanding and comparing coefficients, we see that we need to solve for $\alpha_i,\beta_i$ when $\sum_i \alpha_i\beta_i^k$ is known for all $k$. So we can simply choose the $\beta_i$ distinct (but arbitrarily otherwise) and from the Vandermonde determinant or by polynomial interpolation or otherwise, the resulting linear system of equations for the $\alpha_i$ has a (unique) solution. Done.
Note that this solution uses essentially $n!$ summands for diagonalising $X_1X_2\dots X_n$ which seems to be way too much. If we think about it for some time, why would be even expect the claimed result to be true? Well, essentially by some "degrees of freedom" heuristic. If we expand everything, we get for each monomial a equation on the coefficients. We would expect that by increasing the number of variables/summands (whereas the number of equations remains constant) we would eventually find a solution. How far do we have to go? The expected size is roughly the number of monomials in the expansion which is well-known to be $\binom{2n-1}{n}$.
Let us define map $\mathbb{R}^n \to \mathbb{R}^{N}$ where $N=\binom{2n-1}{n}$ sending a $n$-tuple $(x_1,x_2,\dotsc,x_n)$ to the $N$-tuple of numbers $x_1^{i_1}x_2^{i_2}\dots x_n^{i_n}$ for all the possible tuples with $i_j \ge 0$ and $\sum_j i_j=n$.
For instance, when $n=1$, this is just $x \mapsto x$ and for $n=2$, we have $(x,y) \mapsto (x^2,xy,y^2)$.
Now, it is not hard to see that the claim is equivalent to a certain element being in the linear span of the image of that map. But wait, if this is true, can't we just prove that the span of the image is everything? (In fact, it is not hard to see that the truth of the problem statement implies that this must be true). So suppose this was not the case. Then the span must be a proper linear subspace and hence the image must lie completely in one such subspace. So we have one non-trivial linear equation connecting all the monomials in the definition.
For the sake of illustration, when $n=2$, we get constants $a,b,c$ not all vanishing such that $ax^2+bxy+cy^2=0$ for all $x,y$.
But this is obviously impossible: The LHS is a polynomial which does not vanish for all real values unless it it the zero polynomial. Done.
More precisely, from this solution we can extract the fact that a construction works with at most $\binom{2n-1}{n-1}$ numbers which is known to be roughly of size $4^n$. Now, can we do better? Well, we can, as the solution in #2 really shows that we can get off with $2^n$ summands. Now, is that optimal? Not quite but, as I believe, essentially: There is one easy thing to do, namely to take the two linear forms with opposite sign choices and merge them together, leaving us with $2^{n-1}$ summands. For $n=2$, this is essentially the well-known identity $xy=\frac{(x+y)^2-(x-y)^2}{4}$. And this I finally believe to be optimal, but I can only prove it for $n=2$ (where it's trivial) and for $n=3$ (where it is a bit of work). I would be grateful to anyone pointing out a proof (or a counterexample) of this claim.
It is immediate that the sum of the $2017$-th powers of the linear forms constructed must be a scalar multiple of $x_1x_2\dots x_{2017}$.
As we can divide out constants, we are done. Well, are we? We still need to rule out that this constant (and therefore the whole polynomial) vanishes.
It is actually not so hard to explicitly compute that constant, it is just $2^{2017} \cdot 2017! \ne 0$, but unfortunately I don't have an easy proof to see that the constant does not vanish without actually computing it...
ThE-dArK-lOrD
14.11.2017 21:55
Nice problem, congratulations
Tintarn
19.01.2018 09:54
I just found out that there actually is some literature on this subject: For any homogeneous polynomial $P$ of degree $d$, one can define the Waring rank $W(P)$ as the minimal number of linear forms whose $d$-th powers sum up to $P$. So the proofs above show that $P(X_1\dotsc X_n) \le 2^{n-1}$ and my conjecture was that this is sharp. And in fact is as this paper shows (unfortunately, not in a very elementary way). In fact, this subsequent paper determines the Waring rank for any monomial, namely $P(X_1^{e_1}\dotsc X_n^{e_n})=(e_2+1)(e_3+1)\dotsc (e_n+1)$ where $e_1 \le e_2 \le \dotsc \le e_n$.
Tintarn
20.09.2019 14:34
I just found that this problem essentially already appeared as A4 in the Putnam Competition 2004. See here.
Tintarn
20.09.2019 14:44
In particular one can find there a very interesting new solution which appears to be due to harazi: Consider the function \[f(t)=(e^{tx_1}-1)(e^{tx_2}-1)(e^{tx_3}-1)\dots (e^{tx_n}-1).\]Using the power series expansion $e^x=\sum_{n=0}^{\infty} \frac{x^n}{n!}$ one finds that this equals \[f(t)=x_1x_2\dots x_nt^n+\mathcal{O}(t^{n+1})\]considered as a power series in $t$. On the other hand we can first expand the product in $2^n$ summands, each of them of the form $(-1)^{n-\vert I\vert} e^{t (\sum_{i \in I} x_i)}$ for a subset $I \subset \{1,2,3,\dots,n\}$. Now expanding this as a power series in $t$, one finds that the coefficient of $t^n$ equals $\frac{1}{n!} \left(\sum_{i \in I} x_i\right)^n$ so that we have shown the identity \[x_1\dots x_n=\frac{1}{n!} \sum_{I \subset \{1,2,\dots,n\}} (-1)^{n-\vert I\vert} \left(\sum_{i \in I} x_i\right)^n.\]