Sidon sets: does $F(N+k)\le F(N)+1$ hold for every fixed $k$ and all large $N$? (Erdős #155)
Statement
Let $F(N)$ be the size of the largest Sidon subset of $\{1,\ldots,N\}$ (a set $A$ is Sidon, or $B_2$, if all pairwise sums $a+b$ with $a\le b$, $a,b\in A$, are distinct — equivalently all nonzero differences are distinct). Is it true that for every fixed $k\geq 1$ we have $$F(N+k)\leq F(N)+1$$ for all sufficiently large $N$? Erdős remarked this may even hold with $k$ as large as $\epsilon N^{1/2}$.
Acceptance. FULLY RESOLVES: a proof that for every fixed $k\ge 1$, $F(N+k)\le F(N)+1$ holds for all sufficiently large $N$ (machine-checkable proof preferred, matching the formal-conjectures Lean statement, else a complete written proof); OR a proof that for some fixed $k\ge 2$ there are infinitely many $N$ with $F(N+k)\ge F(N)+2$. Note the quantifier 'for all sufficiently large $N$' means no finite computation alone can settle either direction. ADVANCES: (a) a proof for the single case $k=2$ (the first open case); (b) a conditional proof under a clearly stated hypothesis such as $F(N)=\sqrt{N}+O(N^{\epsilon})$; (c) an extension of the exact values of $F(N)$ strictly beyond the range stated in the background, with reproducible search code and exhaustiveness certificates, together with the complete list of double-jump windows ($F(N+k)\ge F(N)+2$ with small $k$) in the verified range; (d) a proof of the statement for $k$ growing with $N$ under any regime, or any nontrivial upper bound on the number of $N\le x$ where a double jump within distance $k$ occurs. Deliver the proof file, or the search code plus tables and certificates.
Background
Posed by Erdős [Er92c][ESS94][Er94b]; listed as open on erdosproblems.com/155 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics | sidon sets'). The case $k=1$ is trivial: deleting the element $N+1$ from a Sidon subset of $[N+1]$ leaves a Sidon subset of $[N]$, so $F(N)\le F(N+1)\le F(N)+1$ always. The question is open for every fixed $k\ge 2$: can extending the interval by a bounded amount infinitely often gain two or more new elements? Context: by Erdős–Turán ($F(N)\le N^{1/2}+O(N^{1/4})$) and the Singer/Bose–Chowla constructions, $F(N)=(1+o(1))\sqrt{N}$, so on average $F$ increments once per $\sim 2\sqrt{N}$ steps — the conjecture says the increments are eventually spread out at least $k$ apart for every fixed $k$, consistent with the stronger belief (Erdős #30) that $F(N)=\sqrt{N}+O(N^{\epsilon})$. Exact values of $F(N)$ are equivalent to optimal Golomb ruler data (OEIS A143824 gives the largest such subset sizes; A003022 the length of the shortest Golomb ruler with $n$ marks; A227590 is also linked from the problem page) and are known exactly for $N$ into the several hundreds via distributed optimal-ruler searches. The statement is formalized in Lean in google-deepmind/formal-conjectures. Closely related venue problems: the maximum-Sidon-set problem (Erdős #30, exact values and the $N^{1/4}$ second-order term) and the minimal maximal Sidon set problem (Erdős #156) — this problem asks a distinct question about the increment regularity of the same function $F$. The attacker's tools: extend the exact table of $F(N)$ by SAT/branch-and-bound Golomb-ruler search and catalogue every window where $F$ jumps twice within a bounded gap (data that shapes or refutes the $\epsilon N^{1/2}$ strengthening), plus proof attempts for the first open case $k=2$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #155 (T. F. Bloom) | website |
| REF-02 | OEIS A143824 — size of the largest Sidon subset of {1,...,n} (all differences distinct) | website |
| REF-03 | OEIS A003022 — length of the shortest (optimal) Golomb ruler with n marks | website |
| REF-04 | OEIS A227590 — related Sidon-set/Golomb-ruler sequence (linked from the problem page) | website |
| REF-05 | Formalized statement (Lean, google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.