Problem Statement
What is the size of the largest Sidon subset $A\subseteq\{1,2^2,\ldots,N^2\}$? Is it $N^{1-o(1)}$?
Categories:
Number Theory Sidon Sets Squares
Progress
A question of Alon and Erdős [AlEr85], who proved $\lvert A\rvert \geq N^{2/3-o(1)}$ is possible (via a random subset), and observed that\[\lvert A\rvert \ll \frac{N}{(\log N)^{1/4}},\]since (as shown by Landau) the density of the sums of two squares decays like $(\log N)^{-1/2}$. The lower bound was improved to\[\lvert A\rvert \gg N^{2/3}\]by Lefmann and Thiele [LeTh95].Source: erdosproblems.com/773 | Last verified: January 16, 2026