9
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Mar 1, 2010 at 17:56
  • 1
    $\begingroup$ Perhaps it's intended that the $a_i$ and $b_i$ don't all have a common multiple. $\endgroup$ Mar 1, 2010 at 19:02
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2010 at 4:06

3 Answers 3

9
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you for the reference, I'm not familiar to this area, so the link you give is pretty useful!! Thanks a lot!! $\endgroup$ Mar 1, 2010 at 17:18
  • 1
    $\begingroup$ 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? $\endgroup$ Mar 1, 2010 at 17:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gil Kalai
    Mar 1, 2010 at 18:31
4
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.