#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 Round 3, same day: we asked whether every finite Sidon set embeds in SOME classical
near-optimal family — and the answer is no, with an explicit, machine-verified counterexample.
Round 2 raised an obvious question: Singer failed for two size-4 patterns but Bose–Chowla rescued
both — is there a short list of classical families (Singer, Bose, Erdős–Turán, Spence–Ruzsa,
Hughes–Cilleruelo — Eberhard–Manners' full catalog of Desarguesian projective-plane templates)
that together cover every finite Sidon set? We fired this as a real brief. The answer: the
exact union-of-families conjecture is false, and it's false already at 5–6 points. Three explicit obstruction sets, found by an algebraic sieve and checked against every
characteristic at once, not case by case. A₀={0,1,4,6,20} has no degree-2 Bose–Chowla
embedding in any finite field, proved by an explicit Bézout identity over the integers —
an identity like that holds after reduction mod every prime simultaneously, so this isn't a
per-characteristic case analysis, it's a single certificate closing all of them at once.
A*={0,1,3,11,15} simultaneously defeats Singer (via Mueller's known {0,1,3,11} obstruction), Bose,
and the Spence–Ruzsa construction. A**={0,1,3,11,15,20} adds Hughes–Cilleruelo and Erdős–Turán to
that list — a single 6-point Sidon set that embeds in none of the five standard
Desarguesian families. We independently re-derived the actual polynomial algebra, not just read it.
Rebuilt the recurrence F_n(T,D) from the stated definition and confirmed it matches their closed
forms through F₆. For A₀: substituted D=T²+T+1, confirmed f₆(T)=−T⁴−2T³−2T²+1 factors as
−(T+1)(T³+T²+T−1) exactly, confirmed f₂₀ mod f₆ = 8T³+21T²+28T+16 exactly, and confirmed the
Bézout identity (−24T−31)f₆+(−3T²−2T+2)(f₂₀ mod f₆) = 1 exactly — the actual proof. For A*: verified
F₁₁(−1,D) and F₁₅(−1,D) factor exactly as claimed, verified the characteristic-17 gcd computation
digit for digit. For A**'s Hughes–Cilleruelo exclusion: verified H₃'s factorization, verified q₁₁
and q₁₅ are exactly the non-degenerate factors of H₁₁ and H₁₅, confirmed their resultant is exactly
17⁶, and confirmed the final mod-17 Bézout certificate closes the argument. Every one of these
exact. One real arithmetic slip, found and correctly triaged, not load-bearing. The
Spence–Ruzsa exclusion for A* states "(−2)¹⁵−1−15(−3) = −32724 ≡ 0 (mod 7)" and calls this a
contradiction. We recomputed independently: −32724 ≡ 1 (mod 7), not 0. The stated congruence is
simply wrong — but the actual value being nonzero is exactly what the argument needs (a genuine
mismatch at n=15 in the one surviving characteristic from n=11, which is the real contradiction);
if the value really were 0 as written, that would undermine the exclusion, not support it. So the
final claim (A* excludes Spence–Ruzsa) still holds — the source just mis-stated its own
intermediate number. Flagging this plainly rather than silently fixing it. What this doesn't prove — named honestly in the source: A** could still avoid
the five templates yet embed in a non-Desarguesian projective plane, a planar-function family, or
(most importantly for #44 itself) a large classical host after deleting a bounded number of
points — the deletion-barrier question from round 1 is untouched by this. A literature sweep
(Cilleruelo–Nathanson, Forey–Fresán–Kowalski real per Kowalski et al., Hulak–Ramos–de Queiroz,
Bailleul–Riblet, all verified real) found no prior paper claiming universal family coverage either
— so this closes a real gap, not a strawman. The proposed next target: Roth–Raviv–Tamo's
Sidon spaces (arXiv:1705.04560, real, verified) — higher-dimensional subspaces with
unique factorization rather than one-dimensional Bose lines, which get the parameter count right
where higher-degree Bose provably doesn't (h>2 kills density outright: q^(1−h/2)→0). Round 4, same day: the proposed next target lands a real answer, plus a genuinely
sharper open problem. Do A₀ and A** — the two round-3 obstruction sets that beat all five
Desarguesian families — embed in Sidon spaces instead? Yes, both, explicitly. But Sidon spaces
can't yet deliver the density-one completion #44 actually wants, and the reason why is now precise
rather than vague. We independently rebuilt both explicit constructions from scratch, in a genuine field
implementation, not just checked the arithmetic on paper. For A₀={0,1,4,6,20}: built
F₂¹² via the exact stated polynomial (confirmed irreducible and primitive ourselves), took
U₀ = span{1, α¹⁰¹, α⁴⁰⁴, α⁶⁰⁶, α²⁰²⁰}, confirmed it's genuinely 5-dimensional, and ran an exhaustive
pairwise-product check over all 31 nonzero elements to confirm the Sidon property directly — not
assumed. The resulting 31-element cyclic Sidon set in Z/4095Z matched the source's list exactly,
element for element, and 101·A₀ = {0,101,404,606,2020} landed inside it exactly as claimed. Same
full rebuild for A**={0,1,3,11,15,20} in F₂¹³ (H=663): confirmed the claimed relation
1+α⁶⁶³+α¹⁷⁵⁴+α⁵⁰⁶⁹=0 exactly, confirmed the 5-dimensional Sidon property exhaustively, and matched
their 31-element exponent set exactly, including 663·A** landing inside it. A real error, caught by re-deriving the actual arithmetic instead of trusting the
summary line. The source reports the resulting densities as K/m ≈ 0.4844 (for A₀) and
≈ 0.3425 (for A**). Both are wrong. With K=31 and m=4095, K/m = 0.00757 — not 0.4844. With K=31 and
m=8191, K/m = 0.00378 — not 0.3425 (off by a factor of ~64 and ~90 respectively; we couldn't
reconstruct where either number actually came from). This doesn't touch the underlying point — if
anything it's stronger evidence for it, since the true densities are even smaller than claimed, and
"enormous embedding flexibility, awful asymptotic density" was already the conclusion being drawn.
Flagging it the same way as the round-3 arithmetic slip: found, checked, doesn't change the
verdict, still worth naming plainly. Why Sidon spaces don't (yet) close #44 for these seeds. Density-one completions
are proven to require an exact "binary critical" regime (field size q=2, ambient dimension exactly
twice the Sidon-space dimension) — every other regime provably loses a constant factor, an
elementary reduction we didn't re-derive in full but is straightforward algebra. The problem: a
cited theorem (Castello et al.) gives an exact norm criterion showing the standard explicit
construction family (Roth–Raviv–Tamo's monomial graphs) is completely empty in that exact
regime, for every dimension — not a weak construction, a real nonexistence result for the whole
family. So the two explicit 5-dimensional cores found here are real, but nothing in the known
toolkit can grow them into the unbounded critical spaces a density-one answer needs. Exhaustive
finite searches (not independently reproduced by us) found zero completions of either core at the
next critical dimension, and zero binary critical Sidon spaces at all for dimension 5 — extending a
previously published dimension-4 nonexistence result. The honest state of play, in the source's own labeling (which we're not overriding):
the explicit constructions and the checked citations are solid; whether unbounded binary critical
Sidon spaces containing these specific cores exist at all is explicitly marked open, not conjectured
either way with confidence — a real, sharper reformulation of where #44's next real test sits, not a
new dead end. Round 5, same day: a parallel question — does going to a cubic extension field restore
the near-universal coverage rate quadratic Bose–Chowla lost at size five? No, cleanly. Round
2 found quadratic (Fq²) Bose–Chowla hits 1,030/1,035 size-4 patterns. Round 3 found it
drops hard at size 5. The natural next question: does moving to a cubic extension (Fq³)
recover a high hit rate for size-5 patterns, the way going up a degree seemed like it might help? An
agentic run (Codex, GPT-5.6 Sol, max reasoning effort) tested this directly on a fixed sample of 20
size-5 Sidon sets, and the answer is a clean, structural no. Why, exactly. The obvious generalization — take one level of a linear functional
on Fq³ — isn't even Sidon (a level has q² elements, provably too many for the group of
order q³−1). The one construction that IS genuinely Sidon and near-optimal at cubic degree turns out
to just be the classical Singer difference set in disguise, with only two essential parameters after
accounting for scalar redundancy — not three, so a 5-point pattern (3 real conditions) is still
generically overdetermined, same problem as before. A third variant (a "norm-one functional level")
does get the hoped-for three-parameter recurrence, but Sidonicity stops being automatic — an
exhaustive search over every parameter at every prime q≤199 found zero certificates from it. We independently rebuilt both positive certificates from scratch — exact match.
The quadratic search hit 6/20 of the sample; the cubic projective (Singer) search recovered only 1
more, with two explicit certificates: {0,1,10,15,18} at q=37 with cubic recurrence
z³=z²+20z+2, and {0,1,12,16,22} at q=127 with z³=3z²+99z+106. We reimplemented the finite-field
arithmetic ourselves (not the source's code): confirmed both cubics are irreducible mod q, confirmed
the root has the full multiplicative order q³−1 in each case (genuine primitivity, not just
irreducibility), and confirmed the resulting difference set's prefix matches exactly —
{0,1,10,15,18} at modulus 1407, {0,1,12,16,22} at modulus 16257, both exact. Verdict, in the source's own words: "strong negative structural partial." Cubic
extension doesn't create a new usable family — it either fails to be Sidon, collapses back to
Singer, or requires an extra global Sidonicity filter that empirically finds nothing. The rule "size
m becomes tractable around degree m−2" doesn't hold. Scope caveats named honestly in the source:
prime base fields only, q≤199 only, one fixed 20-set sample, not a claim about every size-5 pattern
— a real, clean negative result, not a proof of general nonexistence. Round 6, next day: two reasoners, same question, working independently — and a fact
Round 4 explicitly left unverified now genuinely is. Round 4 asked whether U₀ and U** (the
two 5-dimensional "native core" binary critical Sidon spaces) extend to dimension 6, and reported
"zero binary critical Sidon spaces at all for dimension 5" — but flagged plainly that this exhaustive
claim was not independently reproduced by us. We fired the same follow-up brief through two
separate channels at once — Codex (agentic, GPT-5.6 Sol) and a fresh ChatGPT Pro chat — without
either seeing the other's work. They agree on everything checkable, and one of them actually closed the gap Round 4 left
open. Both independently reconstructed the identical field definitions for U₀ and U**,
cited the same literature (Roth–Raviv–Tamo's Sidon-space/orbit-code equivalence; Gluesing-Luerssen–
Morrison–Troha's real, published k=4 exhaustive nonexistence result, arXiv:1403.1218 — we pulled the
actual PDF and confirmed the exact passage; Castello et al.'s norm criterion, JAC 2023, confirmed
Theorem 4.5 verbatim), and reached the same overall verdict: genuinely open, no construction, no
general nonexistence proof. The Pro return went further on one specific point: it actually re-ran
the k=3/4/5 exhaustive search itself rather than inheriting Round 4's number. We independently
reproduced all three from scratch, in a fresh implementation, in seconds — k=5 alone is 33,554,432
graph-normalized candidates, of which 32,841,152 have full product span and exactly zero are Sidon,
confirmed exactly. Also hand-verified a real "full span but not Sidon" collision at k=5 (pairs
{1,21} and {2,6} both landing on the same product in the field) to make sure "zero" wasn't a search
bug. What's now a genuinely new, triple-verified fact. No binary critical Sidon space
exists at dimension 5 — extending the only previously published nonexistence point (k=4,
2014) by one dimension. This wasn't in print anywhere we could find, and it's now survived two
independent reasoners plus our own from-scratch computation. We also directly brute-forced the
narrower question Round 4 left as a proof sketch — does either specific core (U₀, U**) extend to
dimension 6 in its own native field — and confirmed zero extensions across every one of the 127 and
255 cosets respectively. Still open, precisely. Neither reasoner found a construction or an unbounded
nonexistence proof. Both suggest the same kind of next move (a structural classification of the
"residual injections" / field-realizable alternating-code family a completion would have to belong
to) rather than another brute-force round at a bigger bound — we're taking that steer.