Problem #707: Let $A\subset \mathbb{N}$ be a finite Sidon set

---

Progress

See also [44] and [329] (indeed a positive solution to this problem implies a positive solution to [44], and thence also to [329]).

This is discussed in problems C9 and C10 of Guy's collection [Gu04], and was also asked by Erdős in the 1991 problem session of Great Western Number Theory. The prize of \$1000 was offered in [Er80] for a proof or disproof of this conjecture. In some sources (such as [Er77c]) Erdős weakens this to whether any finite Sidon set can be contained in the perfect difference set modulo $m^2+m+1$ for some (not necessarily prime) $m$. In [Er97c] he admits this conjecture is 'perhaps too optimistic'.

Alexeev and Mixon [AlMi25] have disproved this conjecture, proving that $\{1,2,4,8\}$ cannot be extended to a perfect difference set modulo $p^2+p+1$ for any prime $p$, and also that $\{1,2,4,8,13\}$ cannot be extended to any perfect difference set. Their proof has been formalised in Lean with the assistance of ChatGPT.

Surprisingly, they discovered that this conjecture was actually first disproved by Hall in 1947 [Ha47], long before Erdős asked this question. Hall proved that $\{1,3,9,10,13\}$ cannot be extended to any perfect difference set.

It is trivial that any Sidon set of size $2$ can be extended to a perfect difference set. In a discussion on MathOverflow, Sawin has proved that any Sidon set of size $3$ can also be extended. It remains open whether any Sidon set of size $4$ can be extended to a perfect difference set, but in the same MathOverflow discussion Mueller has shown that $\{0,1,3,11\}$ is a candidate counterexample, in that all the known ways to construct perfect difference sets cannot succeed.