Problem Statement
Let $\ell(N)$ be maximal such that in any finite set $A\subset \mathbb{R}$ of size $N$ there exists a Sidon subset $S$ of size $\ell(N)$ (i.e. the only solutions to $a+b=c+d$ in $S$ are the trivial ones). Determine the order of $\ell(N)$.
In particular, is it true that $\ell(N)\sim N^{1/2}$?
In particular, is it true that $\ell(N)\sim N^{1/2}$?
Categories:
Number Theory Sidon Sets
Progress
Originally asked by Riddell [Ri69]. Erdős noted the bounds\[N^{1/3} \ll \ell(N) \leq (1+o(1))N^{1/2}\](the upper bound following from the case $A=\{1,\ldots,N\}$). The lower bound was improved to $N^{1/2}\ll \ell(N)$ by Komlós, Sulyok, and Szemerédi [KSS75]. The correct constant is unknown, but it is likely that the upper bound is true, so that $\ell(N)\sim N^{1/2}$.In [AlEr85] Alon and Erdős make the stronger conjecture that perhaps $A$ can always be written as the union of at most $(1+o(1))N^{1/2}$ many Sidon sets. (This is easily verified for $A=\{1,\ldots,N\}$ using standard constructions of Sidon sets.)
This is discussed in problem C9 of Guy's collection [Gu04].
See also [1088] for a higher-dimensional generalisation.
Source: erdosproblems.com/530 | Last verified: January 15, 2026