Problem #39: Is there an infinite Sidon set $A\subset \mathbb{N}$ such...

---

Progress

The trivial greedy construction achieves $\gg N^{1/3}$. The first improvement on this was achieved by Ajtai, Komlós, and Szemerédi [AKS81b], who found an infinite Sidon set with growth rate $\gg (N\log N)^{1/3}$. The current best bound of $\gg N^{\sqrt{2}-1+o(1)}$ is due to Ruzsa [Ru98].

Erdős [Er73] had offered \$25 for any construction which achieves $N^{c}$ for some $c>1/3$. Later he [Er77c] offered \$100 for a construction which achieves $\omega(N)N^{1/3}$ for some $\omega(N)\to \infty$.

Erdős proved that for every infinite Sidon set $A$ we have\[\liminf \frac{\lvert A\cap \{1,\ldots,N\}\rvert}{N^{1/2}}=0.\]Erdős and Rényi have constructed, for any $\epsilon>0$, a set $A$ such that\[\lvert A\cap \{1\ldots,N\}\rvert \gg_\epsilon N^{1/2-\epsilon}\]for all large $N$ and $1_A\ast 1_A(n)\ll_\epsilon 1$ for all $n$.

This is discussed in problem C9 of Guy's collection [Gu04].