Erdős Problems

Tags Prizes

SOLVED

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)}?\]

#861: [Er92c]

number theory, sidon sets

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 [KLRS].