Take the 2-minute tour ×

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


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

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 ;-)


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

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

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

Your Answer


