# existence of equal sum, equal sum of square, equal sum of cube, etc

Is there a way to determine whether there exists a positive solution ($x_i > 0$ and $y_i > 0$) for all of the following equations to hold when $k > 2$?

$x_1 + x_2 + \cdots + x_{2n} = y_1 + y_2 + \cdots + y_n$.

$x^2_1 + x^2_2 + \cdots + x^2_{2n} = y^2_1 + y^2_2 + \cdots + y^2_n$.

$x^3_1 + x^3_2 + \cdots + x^3_{2n} = y^3_1 + y^3_2 + \cdots + y^3_n$.

$\cdots$

$x^k_1 + x^k_2 + \cdots + x^k_{2n} = y^k_1 + y^k_2 + \cdots + y^k_n$.

Anyone sheds some lights on this would be highly appreciated!

-
For positive integer solutions it is no for $n=1$ by Fermat's Last Theorem. – Tony Huynh Feb 1 '11 at 1:13
@Tony: it depends on $k$ . If $k=1, n=1$, the answer is yes. – Mark Sapir Feb 1 '11 at 3:38
@Mark, the problem says $k>2$. – Gerry Myerson Feb 1 '11 at 6:12
If Prouhet's solution says anything about this problem, then $k$ should be $\ll n$. – Mark Sapir Feb 1 '11 at 10:28

One can't have $k \ge 2n$ (proof in a moment). An integer solution at the end.

If $k \le n$ then one can choose $y_1,y_2,\cdots,y_n$ and $x_{n+1},x_{n+2},\cdots,x_{2n}$ and solve for $x_1,x_2,\cdots,x_n$. I arbitrarily decided to try this with $x_3=3,x_4=4$ Varying $y_1,y_2$ I find

$y_1,y_2;x_1,x_2,x_3,x_4=8,20;\frac{21-\sqrt{437}}{2},\frac{21+\sqrt{437}}{2},3,4$ Many other choices work as well (for example $11 \le x_1 \le x_2$).

later It should be easy to find solutions with $k=n$ although I have no idea about the integer case: Pick $y_1,\cdots,y_n$ not too small and no two too close together (say $y_i=i$) Then the values $y^j_1 + y^j_2 + \cdots + y^j_n$ determine the coefficients of the monic polynomial $f(t)=\prod_1^n(t-y_i)$ and vice versa. The $y_i$ are the $n$ roots of $f$. Now pick $x_{n+1},\cdots,x_{2n}$ positive but "small enough".Then the desired equations $x^j_1 + x^j_2 + \cdots + x^j_n=y^j_1 + y^j_2 + \cdots + y^j_n-\sum_1^nx_{n+k}^j$ determine the coefficents of some monic polynomial $g(t)$ whose roots are $x_1,\cdots,x_n$. If the prechosen values are small enough (maybe $x_{n+k}=\frac{k}{100^n}$) then the coeffcients of $g$ should be only slightly preturbed from those of $f$ so the roots $x_1,\cdots,x_n$ should be only slightly preturbed from $y_1,\cdots,y_n$

Here is my argument for why we can't expect $k=2n$: In this case the equations and values for $y_1,...,y_n$ will determine $x_1,x_2,\cdots ,x_{2n}$ up to order. But we know a solution with $n$ zeros so the other solutions must be the same rearranged.

The (multi)sets $A=[0,4,5]$ and $B=[1,2,6]$ have equal sums of $j$th powers $j=0,1,2$. Thus the same is true for $A\cup 4A \cup 5A \cup 6A$ and $B\cup 4B \cup 5B \cup 6B$. This remains true for $j=1,2$ if we drop the common terms and the 4 $0$s leaving $$[16,20,20,25] \text{ and }[1, 2, 6, 6, 8, 10, 12, 36]$$

I haven't managed a similar trick for $[0,2,9,11]$ and $[1,4,7,10]$ (equal sum of powers for $j=0,1,2,3$) or other similar examples.

A potentially useful technique for the integer case: One way to verify the claim about $[6,2,1]$ and $[5,4,0]$ is to observe that the polynomial $p(t)=t^6-t^5-t^4+t^2+t-1=(t-1)(t^2-1)(t^3-1)$ has a triple root at $t=1$. In our case, consider the polynomial $\sum_1^{2n}t^{x_i}-\sum_1^n t^{y_i}-n$. It has a $k+1$-fold root at $t=1$ precisely if the desired equations hold. Hence $f(t)=t^{36}-t^{25}-2t^{20}-t^{16}+t^{12}+t^{10}+t^8+2t^6+t^2+t-4$ has a triple root at $t=1$. In fact $f=(t-1)(t^2-1)(t^3-1)(t^2-t-1)g(t)$ where $g(t)=t^{28}+2t^{27}+\cdots+13t^4+11t^3+9t^2+7t+4$ has (weakly) unimodal non-negative coefficients and the triple root at $t=1$ comes from the same $(t-1)(t^2-1)(t^3-1)=p(t)$.

-
You've switched notation - the original has $x_{2n}$ and $y_n$, you have it the other way around. – Gerry Myerson Feb 1 '11 at 6:18
But y>x????? Ok I'll swap it. – Aaron Meyerowitz Feb 1 '11 at 6:50
Use $A=[0,3,3]$, $B=[1,1,4]$, and $C\cup3C\cup4C$ for $C=A$, $C=B$ to get $9^j+9^j+12^j=1^j+1^j+4^j+4^j+4^j+16^j$ for $j=1,2$. – Gerry Myerson Feb 2 '11 at 22:28

For integers, this is referred to as the Tarry-Escott problem, also as multigrade equations, a search for either term should bring you much joy. I just noticed you have $n$ terms on one side, $2n$ on the other, whereas people are usually more interested in equal numbers of terms on each side.

-
@Gerry: The Prouhet-Tarry-Escott problem is different as you yourself mention, it has the same number of terms on each side. – Mark Sapir Jan 31 '11 at 22:24
Not only that, the OP explicitly wants to know about not-necessarily-integer (but positive) solutions as well. Even if positivity were not required, and there were the same number of terms on each side, the question becomes: can you have $M^{-1} N \mathbf{1} = \mathbf{1},$ where $M, N$ are Vandermonde matrices, and does not seem to be entirely trivial. – Igor Rivin Feb 1 '11 at 1:15
The problem with equal number of terms in each side has a nice solution found by Prouhet in around 1860. Consider the word $w_n$ in $a,b$ defined as $\phi^n(a)$ where $\phi$ is the substitution $a\to ab, b\to ba$. It has exactly $2^n$ $a$'s and $2^n$ $b$'s. Let $x_1,\ldots,x_{2^n}$ be the numbers of places in $w_n$ where letter $a$ occurs, and $y_1,\ldots, y_{2^n}$ the places where $b$ occurs. Then these $x$'s and $y$'s satisfy the first $n$ Prouhet's conditions. Note that later the words $w_n$ were rediscovered by Thue, Morse, Arshon and many others. These are called Thue words now. – Mark Sapir Feb 1 '11 at 3:16
Also I think Prouhet in his paper mentioned that the problem goes back to Euler. – Mark Sapir Feb 1 '11 at 3:22
@Igor, if positivity (and integrality) is (are) not required, then my guess is it's a simple matter of counting up conditions and variables; if there are more of the latter than of the former, I would expect there to be solutions. @Mark, of course in Prouhet's solution the number of variables is exponential in the number of conditions. The big question (I'm sure you know this) is whether, for all $n$, there is a (non-trivial, integral) solution up to $n$th powers with just $n+1$ terms on each side. I concede that this may be of limited interest to WAB but still recommend searching multigrade. – Gerry Myerson Feb 1 '11 at 3:25

The polynomial

$c_0 + c_1x + \cdots + c_{n-2}x^{n-2} + x^n(x-y_1)(x-y_2)\cdots(x-y_n)$

with all $y_i > 0$ can only have $2n$ positive real zeros if its $n-2$th derivative has $n+2$ positive real zeros. The $n-2$th derivative is

$(n-2)!c_{n-2} + \frac{(2n)!}{(n+2)!}x^2(x-y_1')\cdots(x-y_n')$,

where the $y_i'$s are all positive. This will have $n+2$ real zeros iff $(-1)^n c_{n-2} \le 0$, but if $(-1)^n c_{n-2} \lt 0$ then one of the roots will be negative. If $c_{n-2} = 0$ and $c_j \ne 0$ for some $j \lt n-2$, then by looking at the $j$th derivative (and assuming $j$ is maximal such that $c_j \ne 0$) we see that we don't even get $2n$ real roots of the original polynomial.

Thus, you can't find any solutions in the positive reals with $k \ge n+1$. Aaron gave a sketch of a reason that you can expect to find solutions with $k = n$.

-