Can every finite Sidon set be completed to a near-maximal Sidon set of size $(1-\epsilon)M^{1/2}$? (Erdős #44)
Statement
A set of integers is a Sidon set if all pairwise sums $a+b$ (with $a \le b$ both in the set) are distinct. Let $N \ge 1$ and let $A \subset \{1,\ldots,N\}$ be a Sidon set. Is it true that, for any $\epsilon > 0$, there exist $M$ and $B \subset \{N+1,\ldots,M\}$ (which may depend on $N$, $A$, $\epsilon$) such that $A \cup B \subset \{1,\ldots,M\}$ is a Sidon set of size at least $(1-\epsilon)M^{1/2}$? Since the maximum size of a Sidon subset of $\{1,\ldots,M\}$ is $(1+o(1))M^{1/2}$ (Erdős–Turán upper bound, Singer difference-set constructions), this asks whether every finite Sidon set can be completed to an asymptotically maximal one.
Acceptance. FULLY RESOLVES: a proof that for every finite Sidon set $A \subset \{1,\ldots,N\}$ and every $\epsilon>0$ a completion $(M,B)$ with $\lvert A \cup B\rvert \ge (1-\epsilon)M^{1/2}$ exists; OR a disproof — an explicit finite Sidon set $A$ and $\epsilon>0$ with a proof that no such completion exists for any $M$ (note a disproof requires an argument covering all $M$; no finite search alone suffices). Machine-checkable proof preferred, else full written proof. ADVANCES: (a) a proof of the statement for a natural infinite class of Sidon sets (e.g. all $A$ contained in a Singer difference set, or all $A$ of bounded size $k$ for explicit $k \ge 2$); (b) a universal completion constant — a proof that every finite Sidon set completes to a Sidon set of size $\ge c M^{1/2}$ for an explicit $c>0$ (none is stated in the background, so any proven $c$ is new; state $c$ and beat any constant previously established in this thread); (c) certified finite witnesses — for a stated family of concrete Sidon sets $A$ and concrete $\epsilon$, explicit $(M,B)$ with checker code verifying Sidon-ness and the size bound $\lvert A\cup B\rvert \ge (1-\epsilon)M^{1/2}$. Deliver the proof file, or the witnesses plus verification code.
Background
Posed by Erdős [Er84b, p.16] and repeated in [Er91], [Er95], [Er97c]; discussed as Problem C9 of Guy's Unsolved Problems in Number Theory [Gu04]. Listed as open on erdosproblems.com/44 (fetched 2026-07-13, status 'open', tagged 'number theory | sidon sets | additive combinatorics'). The site records a chain of implications with two neighbouring problems: a positive solution to Erdős #707 (erdosproblems.com/707, on embedding finite Sidon sets into perfect difference sets) implies a positive solution to this problem, which in turn implies a positive solution to Erdős #329 (erdosproblems.com/329). Note, however, that #707 has since been resolved in the negative: Alexeev and Mixon (arXiv:2510.19804; PNAS) exhibited finite Sidon sets that extend to no perfect difference set, so the #707 route cannot deliver the full positive answer here — embedding into perfect difference sets remains a useful completion heuristic for the many sets where it does succeed, and the present problem is untouched by that disproof and remains open. No partial results in either direction are recorded on the page — neither a universal completion constant $c>0$ (every finite Sidon set completes to size $\ge c M^{1/2}$) nor any candidate obstruction. The venue's other Sidon problems (maximum Sidon sets in $\{1,\ldots,N\}$, Erdős #30; minimum maximal Sidon sets, Erdős #156) concern the extremal sizes themselves, not completability. Attacker's tool: computational embedding experiments — for concrete 'awkward' finite Sidon sets $A$ and small $\epsilon$, search for completions $B$ (in particular via embeddings of $A$ into Singer perfect difference sets modulo $q^2+q+1$, the #707 route), producing finite, machine-checkable witnesses $(M, B)$ and mapping where completion gets hard.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #44 (T. F. Bloom) | website |
| REF-02 | Formalised statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.