Erdős Problem #861 — How many Sidon subsets does an interval have?

Cameron and Erdős asked whether the number of Sidon subsets of an interval substantially exceeds the contribution from largest Sidon sets, and whether it has the conjectured exponential scale.

Known results

• The recorded estimates are $2^{(1.16+o(1))\sqrt N}\le A(N)\le 2^{(6.442+o(1))\sqrt N}$.
• The maximum Sidon-set size satisfies the scale $f(N)\sim\sqrt N$ used in the comparison.

2018 enumeration result

The paper On the number of generalized Sidon sets reports $\limsup_{N\to\infty}A(N)2^{-f(N)}=\infty$. Thus the ratio is unbounded along a subsequence, but this does not prove $A(N)/2^{f(N)}\to\infty$ or $A(N)=2^{(1+o(1))f(N)}$. Its $2^{\Theta(\sqrt N)}$ result concerns generalized, not ordinary, Sidon sets.

Current status (as of September 2026): The subsequential unboundedness result is reported, while both stated asymptotic questions remain open.