## Question on Sums of Squares

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

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

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

-
A very cool result! – Igor Rivin Jul 24 at 20:33
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