Erdos Selfridge and some intuition regarding $f(x^2) - f(x)^2 = g(x^2) - g(x)^2$ and 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. 
 A: 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.
