The board / number theory / #862
Erdős Problem #862
SOLVED LEANdatabase updated 2026-01-21
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways. A solution has also been checked by machine, in Lean.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
\(A_1(N)\), the number of maximal Sidon subsets of \(\{1, \dots, N\}\).
Let \(A_1(N)\) be the number of maximal Sidon subsets of \(\{1,\ldots,N\}\). Is it true that \[A_1(N) < 2^{o(N^{1/2})}?\] A problem of Cameron and Erdős. This is resolved as a consequence of results of Saxton and Thomason [SaTh15] - they prove that the number of Sidon sets in \(\{1,\ldots,N\}\) is at least \(2^{(1.16+o(1))N^{1/2}}\). Since each Sidon set is contained in a maximal Sidon set, and each maximal Sidon set contains at most \(2^{(1+o(1))N^{1/2}}\) Sidon sets, it follows that \[A_1(N) \geq 2^{(0.16+o(1))N^{1/2}}.\]
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/862.Prizenone
Topicsnumber theory, sidon sets
Statement in LeanFormal Conjectures
Solution in Leanyes
OEISA382395
Original pageerdosproblems.com/862
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.