Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

How about positive integer solutions?

Anyone sheds some lights on this would be highly appreciated!

share|improve this question
    
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

3 Answers 3

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)$.

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

share|improve this answer
    
@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
1  
@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$.

share|improve this answer

Your Answer

 
discard

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.