The Erdos Selfridge problem asks that
For any (multi)set $A$ of $n$ real numbers $\{ a_1, \cdots, a_n \}$, define the (multi)set $S_A = \{ a_i+a_j | i < j \}$. Find all positive integers $n$ such that $S_A = S_B \Rightarrow A = B$.
I was trying the problem yesterday but couldn't solve that (morever I find the result very counterintuive and surprising). With Dirichlet approximation theorem, we can work with the $a_i$'s being positive integer, and then the problem reduces to (define $f(x) = \sum_{a \in A} x^a$ and $g(x) = \sum_{b \in B} x^b$)
Determine all positive integers $n$ such that there exists $f(x), g(x) \in \mathbb{Z}[x]$ with $f(x) \neq g(x)$, $f(1) = g(1) = n$ and $f(x)^2 - f(x^2) = g(x)^2 - g(x^2)$.
The sketch of the solution from the book is very simple, here's a sketch:
Let $h(x) \in \mathbb{Z}[x]$ such that $f(x) - g(x) = (x-1)^k h(x)$ with $k > 0$ (since $(x-1)$ divides $f(x) - g(x)$) and $h(1) \neq 0$. Then just substitute $f(x) = g(x) + (x-1)^k h(x)$ into the original equation and and factor $(x-1)^k$ and then plug in $g(1)$ and it magically works (Gives $2^{k} = g(1)$) !
But my questions are that:
How do you guess the answer of $2^k$ a priori ? One way to do it is to try small cases, such that try to construct $A \neq B$ for which $S_A \neq S_B$. For $n = 2$, it's trivial, let $A = \{1, 3 \}, B = \{2,2 \}$, for $n = 3$ it's easy to see you can get $A$ from $S_A$ uniquely, but I got stuck at the construction when $n = 4$.
Why the polynomial method is more suitable, than say linear algebra methods ? It's tempting to view the problem as the set of linear equations $a_i+a_j = b_k$ and trying to solve it using tools from linear algebra, but that way of approach fails pretty soon (though I don't have much intution why)
Suppose you're convinced that $n = 2^k$ is the answer, and considering the polynomials is the way to go. Even then, how do you expect the solution to be in the lines of the official solution ? For example, why would you expect to construct the polynomial $h(x)$ and think that it would be useful to solve the problem ? It might be the case that Taylor Expansion at $x = 1$ or differentiation or somethings would have worked, but calculus based lines of attack don't work ?
Partial answers to the questions are appreciated too.
This is only a partial answer and concerns the 1. question on how to construct such a set.
Suppose there exists sets $A \neq B$ of size $n$ such that $S(A) = S(B)$, then we can construct sets $A' \neq B'$ of size $2n$ with the property $S(A') = S(B')$. For simplicity I introduced $S(X) \equiv \{x_i + x_j | x_i,x_j \in X, i<j \}$ and $T(X,Y) \equiv \{x_i + y_j | x_i \in X, y_j \in Y \}$
Hereto we construct: $$ A' = A \cup (B+2n) $$ $$ B' = B \cup (A+2n) $$ We then find that: $$ S(A') = S(A) ~~\cup~~ T(A,B+2n) ~~\cup~~ S(B+2n) = S(A) ~~\cup~~ T(A,B)+2n ~~\cup~~ S(B)+4n $$ $$ S(B') = S(B) ~~\cup~~ T(B,A+2n) ~~\cup~~ S(A+2n) = S(B) ~~\cup~~ T(B,A)+2n ~~\cup~~ S(A)+4n $$ and it follows that they are identical.
Note that any shift other then $n$ could have been used as well, but with this particular choice and the set $A_2=\{1,4\}$ and $B_2=\{2,3\}$ for $n=2$, we obtain for $n=4$ $$ A_4=\{1,4,6,7\} $$ $$ B_4=\{2,3,5,8\} $$ and will result in general in two disjoint sets $A_{2^k}$ and $B_{2^k}$ containing only different elements.