Four-point near-Sidon sets: the best constant $c$ forcing a Sidon subset of size $cn$ (Erdős #757)
Statement
A Sidon set is a set whose pairwise differences are all distinct; for a $4$-element Sidon set $B$ the difference set $B-B=\{b-b' : b,b'\in B\}$ has exactly $13$ elements. Let $A\subset\mathbb{R}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert = 4$ has $\lvert B-B\rvert\geq 11$ — i.e. at most one difference is 'missing' from each four-point pattern. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$. Equivalently (in distance language): if every four points of $A$ determine at least five distinct distances, how large a subset with all pairwise distances distinct is guaranteed?
Acceptance. FULLY RESOLVES: determine the optimal constant $c$ exactly — a proof of $c\geq c_0$ (every size-$n$ set satisfying the 4-subset condition contains a Sidon subset of size $\geq (c_0-o(1))n$) together with a matching construction family showing $c\leq c_0$; machine-checkable (Lean/Coq) preferred, else a complete written proof. ADVANCES: (a) a lower bound on $c$ strictly greater than the best lower bound stated in the background, with full proof; (b) an upper bound strictly smaller than the best upper bound stated in the background, via an explicit infinite family of sets satisfying the hypothesis whose largest Sidon subsets are asymptotically small — with proof, plus verification code for finite members; (c) certified exact values of the finite extremal ratio $\min_A \max\{|S| : S\subseteq A \text{ Sidon}\}/n$ for small $n$ via exhaustive or SAT search with an exhaustiveness certificate; (d) a Lean formalization of the current record bounds. Deliver the proof file, or the construction family + verification code, or the search code + certified table.
Background
Posed by Erdős [Er97b]; listed as open on erdosproblems.com/757 (fetched 2026-07-21, status 'open', tagged 'geometry | distances | sidon sets'). Without loss of generality one may take $A\subset\mathbb{N}$. Known frontier: Erdős and Sós proved $c\geq 1/2$. Gyárfás and Lehel [GyLe95] proved $\tfrac{1}{2}+\tfrac{1}{141\cdot 76}\leq c\leq \tfrac{3}{5}$, the upper bound witnessed by the set of the first $n$ Fibonacci numbers. The current record is due to Ma and Tang [MaTa26]: $$\frac{9}{17}\leq c\leq \frac{4}{7},$$ so the answer lies in $[9/17, 4/7]\approx[0.5294, 0.5714]$ and either side can move. A formalized statement of the problem exists in the DeepMind formal-conjectures repository (FormalConjectures/ErdosProblems/757.lean). The venue hosts several Sidon-set problems (maximum Sidon sets in $[N]$, minimal maximal Sidon sets) but none on this hypothesis-forcing constant. The attacker's tools: SAT/ILP search over integer sets satisfying the every-4-subset condition to find small-$n$ extremal configurations minimizing the largest Sidon subset (candidate periodic/recursive structures generalizing the Fibonacci example) to push the upper bound below $4/7$, plus structural/discharging arguments — possibly computer-assisted case analysis — for the lower bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #757 (T. F. Bloom) | website |
| REF-02 | Formalized statement of Erdős #757 (DeepMind formal-conjectures, Lean) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.