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

Hi everyone, I got a problem when proving lemmas for some combinatorial problems, and it is a question about integers.

Let

$\sum_{k=1}^m a_k^t = \sum_{k=1}^n b_k^t$

be an equation, where $m, n, t, a_i, b_i$ are positive integers, and $a_i \neq a_j$ for all $i, j$, $b_i \neq b_j$ for all $i, j$, $a_i \neq b_j$ for all $i, j$.

Does the equality have no solutions?

For $n \neq m$, it is easy to find solutions for $t=2$ by Pythagorean theorem, and even for $n = m$, we have solutions like

$1^2 + 4^2 + 6^2 + 7^2 = 2^2 + 3^2 + 5^2 + 8^2$.

For $t > 2$, similar equalities hold:

$1^2 + 4^2 + 6^2 + 7^2 + 10^2 + 11^2 + 13^2 + 16^2 = 2^2 + 3^2 + 5^2 + 8^2 + 9^2 + 12^2 + 14^2 + 15^2$ and $1^3 + 4^3 + 6^3 + 7^3 + 10^3 + 11^3 + 13^3 + 16^3 = 2^3 + 3^3 + 5^3 + 8^3 + 9^3 + 12^3 + 14^3 + 15^3$,

and we can extend this trick to all $t > 2$.

The question is, if we introduce one more restriction, that is, $|a_i - a_j| \geq 2$ and $|b_i - b_j| \geq 2$ for all $i, j$, is it still possible to find solutions for the equation?

For $t = 2$ we can combine two Pythagorean triples, say,

$5^2 + 12^2 + 25^2 = 7^2 + 13^2 + 24^2$,

but how about the cases for $t > 2$ and $n = m$?

share|improve this question
1  
Can't you just multiply all the $a_i$ and $b_i$ by 2 to get around your added restriction? Am I severely misreading something? –  Reid Barton Mar 1 '10 at 17:56
1  
Perhaps it's intended that the $a_i$ and $b_i$ don't all have a common multiple. –  Michael Lugo Mar 1 '10 at 19:02
    
Reid - No, you are absolutely right. The restriction I've been made is just a trial to make the equations harder, which may eventually leads to a strong enough one without any solutions. Michael - Now by the answer of Bjorn's, unless we can make the m small, we can not expect a restriction which makes the equality unsolvable. –  Hsien-Chih Chang 張顯之 Mar 2 '10 at 4:06
add comment

3 Answers 3

up vote 9 down vote accepted

An even harder problem than $t>2$ and $n=m$ is the Prouhet–Tarry–Escott problem. Now I leave it to you and google to find lots of examples ;-)

http://en.wikipedia.org/wiki/Prouhet-Tarry-Escott_problem

share|improve this answer
    
Thank you for the reference, I'm not familiar to this area, so the link you give is pretty useful!! Thanks a lot!! –  Hsien-Chih Chang 張顯之 Mar 1 '10 at 17:18
1  
Am I confused about something, or is the "[citation needed]" claim on that page definitely false? Doesn't the "odd/even number of bits equal to 1" thing generate solutions to that problem for every k? –  Reid Barton Mar 1 '10 at 17:57
1  
Right, there are many solutions. The Tarry-Escott problem is the problem of finding solutions where SUM_{i=0}^n a_i^t = \sum_{i=0}^mb_i^t for t=1,2,...,n. Such examples are apparently known only for n<=11. In the Morse sequence example n=2^m and t=0,1,...,m. Another nice question is if when you want the a_i and b_i to form a partition of the first s integers, is there a smaller example than the one from the Morse sequence. –  Gil Kalai Mar 1 '10 at 18:31
add comment

One set of solutions for t = 3 is the class of numbers known as Taxicab Numbers, named after the number of a taxicab G. H. Hardy took, 1729, that Ramanujan mentioned was equal to 13 + 123 = 93 + 103. This particular example fails, as |10 - 9| = 1 < 2, but there are other Taxicab numbers, such as:
1673 + 4363 = 2283 + 4233 = 2553 + 4143.

This might be a helpful site for your question.

-Gabriel Benamy

share|improve this answer
    
Thank you very much! Now there are LOTS of examples :] –  Hsien-Chih Chang 張顯之 Mar 1 '10 at 18:17
add comment

For any $t$, if $m$ is sufficiently large relative to $t$, and $n$ is any positive integer (possibly equal to $m$), then the circle method proves that there exists an infinite sequence of increasingly large solutions such that the ratios between the $a_1,\ldots,b_n$ approach any real positive ratios you want (assuming that a real solution with those ratios exists for that $m,n,t$). This answers your question with much stronger inequalities than the ones you imposed. If you want, you can simultaneously specify the residues of the $a_i$ and $b_j$ modulo some fixed number $N$, provided that those residues are compatible with the equation. In fact, again when $m \gg t$, you can even fix the $b_j$ in advance: the solution to Waring's problem guarantees the existence of $a_1,\ldots,a_m$, and a slight strengthening lets you impose your inequalities too, if the $b_j$ are large enough. (Proof: the circle method again.)

share|improve this answer
    
Thanks for the method!! –  Hsien-Chih Chang 張顯之 Mar 2 '10 at 4:10
add comment

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.