#44: can any finite Sidon set be completed to near-optimal density? A real deletion barrier, not just a stalled attempt
The target (erdosproblems.com/44, OPEN, 0 claimed proofs — someone's actively working on formalizing it right now). Given any finite Sidon set A ⊂ {1,...,N}, does every ε>0 admit an M and a completion B ⊂ {N+1,...,M} with A∪B Sidon and size at least (1−ε)√M? Related to problems #329 and #707 — a positive answer to #707 would imply this, which would imply #329.
What's new here isn't a solve — it's a real obstruction, proven, not just observed. The natural attack is: take a huge Singer perfect difference set (the classical near-optimal Sidon construction, density ~1/√M), delete whatever collides with your fixed seed A, keep the rest. The chat proves this can't work for certain seeds: an external point not already inside the difference set forces Θ(q) genuine integer collisions, and deleting one point can repair at most 4 of them — so at least (1/16−o(1))q points have to go. For Alexeev–Mixon's {1,2,4,8,13}, which provably embeds in no perfect difference set at all, that's fatal to the whole sparse-repair template. A different, linearly-far construction would be needed.
We rebuilt the actual mechanism from scratch — not just the citations. Implemented a genuine Singer perfect difference set via GF(q³) arithmetic (trace-zero coset construction), verified it's really λ=1 (every nonzero residue represented as a difference exactly once) for q=2,3,5,7. Tested the |A|≤2 embedding claim directly: zero failures across all 56 possible target differences at q=7. Tested the deletion-barrier mechanics (Steps 1–4 of the proof): x↦f_x really is a permutation, multiplicity per point really caps at 2, total appearances per point really caps at 4 — all confirmed exactly, not approximately. And we reproduced their actual headline number independently: scanning all 2,052 affine copies of the q=7 Singer set (matches their count exactly — φ(57)=36 units × 57 shifts) against the normalized Alexeev–Mixon seed, minimum additional deletions needed = 1, found via our own from-scratch search (u=2, t=22), not copied from their result.
Citations, checked directly, not trusted: Alexeev–Mixon (arXiv:2510.19804, the non-embedding result), Tong Niu's withdrawn size-4 follow-up (arXiv:2604.25214), O'Bryant's July 2026 thickness paper confirming Ruzsa's 1/√2 is still the infinite-Sidon record (arXiv:2606.28651), Eberhard–Manners' dense-Sidon structure conjecture (arXiv:2107.05744) — all real. Will Sawin's unpublished |A|=3 proof, pulled directly from the MathOverflow API rather than trusted secondhand: accepted answer, real, uses Singer's construction + Weil's Riemann Hypothesis for curves + a primitive-root sieve, exactly as described — including Peter Mueller's follow-up answer, also real.
What's still open. No proof and no counterexample. The |A|=3 case leans on Sawin's algebraic-geometric estimates, which weren't independently re-derived here (flagged honestly in the source). The deletion barrier only rules out sparse edits of a single perfect difference set — it says nothing about a genuinely different, dense construction built around the seed from the start. Alexeev–Mixon-style forbidden seeds are the most plausible counterexample candidates but calling them actual counterexamples to #44 would be an overclaim right now.
Round 2, same day: the two size-4 "forbidden" patterns embed after all — just not via Singer. Peter Mueller's MathOverflow answer named two specific |A|=4 sets, {0,1,3,11} and {0,1,4,11}, that provably embed in no Singer/Desarguesian perfect difference set for any q. That sounded like a real wall. It wasn't — it was specific to Singer. Both patterns embed cleanly and elementarily into a completely different classical near-optimal Sidon family, Bose–Chowla rulers (built from a primitive root of a quadratic extension field rather than a projective plane). {0,1,3,11} embeds via F₅ (T=−1, D=2); {0,1,4,11} via F₂₃ (T=7, D=11), giving a 23-element modular Sidon set with the target sitting exactly as its own prefix.
We rebuilt every one of these constructions from scratch, independent of the transcript — every single number matched. Implemented the Bose–Chowla recurrence directly (u_{k+2}=Tu_{k+1}−Du_k over F_q), verified z has order exactly q²−1 (genuine primitivity, not just "discriminant is a non-residue") for both worked cases, and reproduced the full 23-element F₂₃ ruler digit-for-digit — including the specific primitivity certificates z¹⁷⁶=4+2z, z⁴⁸=6, z²⁶⁴=−1. Verified both independent Ruzsa–Lindström witnesses (6-mark and 16-mark rulers) and every resultant/factorization in the paper's negative result about why the Ruzsa family specifically can't be scaled up (2016=2⁵·3²·7, 197676=2²·3²·17²·19) — exact matches throughout.
The big claim — checked, with a real self-caught mistake
along the way. The source exhaustively checked all 1,035 Sidon
quadruples {0,1,a,b} for 2≤a