Welcome to MathOverflow

Question

2

Is it possible for two different $n$-element sets, each of which consists of $n$ unique positive integers (they can appear in both sets, though) to have the same sum when the squares of their elements are added?

Edit: For obvious reasons, I'm not considering the case $n=1$.

flag	asked Jul 24 at 20:03 rebeccakuang 23●3

4

$8,1$ and $7,4$ – Will Jagy Jul 24 at 20:07

This is not really an appropriate question for the site (see the FAQ). Try math.stackexchange.com instead. – Qiaochu Yuan Jul 24 at 20:12

Anthony Quas · Accepted Answer · 2012-07-24 20:09:12Z UTC

13

Yes. One way to see this is that there are more $n$-element subsets with terms up to $N$ than there are possible sums of squares, giving an answer by the pigeonhole principle.

A more beautiful answer was given by Prouhet in the 1850's, who exhibited for each $n$ an explicitly-defined pair of sets $A$ and $B$ of size $2^n$ such that $$\sum_{a\in A}a^k=\sum_{b\in B}b^k\text{ for each $1\le k\le n$}. $$

answered Jul 24 at 20:09

Anthony Quas
6,260●1●12●28

A very cool result! – Igor Rivin Jul 24 at 20:33

1

Apparently it's well known to the French as the subsets come from the Morse sequence, so that Prouhet discovered the Morse sequence 50 years before Thue did, which in turn was 15 years before Morse did! I think the proof of this is actually a nice non-trivial, but non-impossible exercise in induction. – Anthony Quas Jul 24 at 21:48

@Anthony, thanks for the serious treatment of the question and the very lucid answer! – rebeccakuang Jul 24 at 22:44

If you include 0, there are other interesting families of solutions: $3^2+4^2=0^2+5^2$, $10^2+11^2+12^2=0^2+13^2+14^2$, $21^2+22^2+23^2+24^2 = 0^2 + 25^2+26^2+27^2$, and so on. The pattern is left to the reader. – Kevin O'Bryant Jul 25 at 1:07

Question on Sums of Squares

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.