SOLVED
This has been resolved in some other way than a proof or disproof.
Let $f(N)$ be the size of the largest Sidon subset of $\{1,\ldots,N\}$ and $A(N)$ be the number of Sidon subsets of $\{1,\ldots,N\}$. Is it true that\[A(N)/2^{f(N)}\to \infty?\]Is it true that\[A(N) = 2^{(1+o(1))f(N)}?\]
A problem of Cameron and Erdős. It is known that $f(N)\sim N^{1/2}$ and conjectured (see
[30]) that $f(N)=N^{1/2}+O(N^{\epsilon})$.
While $A(N)$ has not been completely determined, both of these questions are now settled, the first positively and the second negatively. The current best bounds are (for large $N$)\[2^{1.16f(N)}\leq A(N) \leq 2^{6.442f(N)}.\]The lower bound is due to Saxton and Thomason
[SaTh15], the upper bound is due to Kohayakawa, Lee, Rödl, and Samotij
[KLRS15].
See also
[862].
This is discussed in problem C9 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 15 October 2025. View history
Additional thanks to: Wouter van Doorn
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 #861, https://www.erdosproblems.com/861, accessed 2026-05-21
