Erdős Problem a Daythe open tracker
The board / sidon sets / #156

Erdős Problem #156

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

The size of the smallest maximal Sidon set in \(\{1, \dots, N\}\).

Does there exist a maximal Sidon set \(A\subset \{1,\ldots,N\}\) of size \(O(N^{1/3})\)? A question of Erdős, Sárközy, and Sós [ESS94].
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 2 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/156.
Prizenone
Topicssidon sets
Statement in LeanFormal Conjectures
Solution in Leanno
OEISA382397
Original pageerdosproblems.com/156

Attempts

submit one →
FULL WRITE-UP BY THIS SITE · AUG 11, 2026

Read our full write-up →

Does a maximal Sidon subset of {1,...,N} exist with size O(N^(1/3))? The asymptotic problem remains open, and Rounds 1–2 explain why the extra log in Ruzsa's construction is structural for random lifts. Rounds 3–5 close the next exact finite frontier: a(66)=a(67)=6, a(n)=7 for every 68≤n≤101, and a(n)=8 for every 102≤n≤136. Complete enumerations cover normalized Sidon sets through seven marks, while explicit maximal sets certify every upper bound. This extends OEIS A382397 from 65 through 136 without changing the parent problem's asymptotic record.

LIVE
← #155the board#157 →