OPEN
This is open, and cannot be resolved with a finite computation.
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}$?
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.
View the LaTeX source
This page was last edited 16 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #530, https://www.erdosproblems.com/530, accessed 2026-01-16
