Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 35 min ago
Peer-reviewedCC BY-NC-NDProceedings of the National Academy of Sciences

Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof

  • Boris Alexeev1
  • Dustin G. Mixon2,3
  1. 1Independent Researcher
  2. 2Department of Mathematics, The Ohio State University
  3. 3Translational Data Analytics Institute, The Ohio State University
Open at sourceDOICite

Abstract

We resolve a $1,000 Erdős prize problem, complete with formal verification generated by a large language model. In over a dozen papers, beginning in 1976 and spanning two decades, Paul Erdős repeatedly posed one of his "favorite" conjectures: every finite Sidon set can be extended to a finite perfect difference set. We establish that {1, 2, 4, 8, 13} is a counterexample to this conjecture. During the preparation of this paper, we found that although this problem was presumed to be open for half a century, Marshall Hall, Jr. published a different counterexample three decades before Erdős first posed the problem. With a healthy skepticism of this apparent oversight, and out of an abundance of caution, we used ChatGPT to vibe prove both Hall's and our counterexamples in Lean.

Related

  1. Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings
    Michelle Delcourt, Luke Postle
    Journal of the London Mathematical SocietyPeer-reviewedCC BY-NC-ND46 citedCombinatorics & discrete mathematicsOpenAlex
  2. A Uniform Product-Difference Theorem for Dense Subsets of ℤ2
    Sayan Goswami, Chunlin Liu
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  3. Optimal entanglement-assisted source coding under a balanced-difference promise
    Julius A. Zeiss
    arXivPreprintCC BY 4.0Full textMathematical physicsQuantum physics & quantum informationarXiv
  4. Càdlàg Solutions to Backward Stochastic Dynamics featuring Oblique Subgradients and driven by Martingale Noise
    Andreea Negruţ, Aurel Răşcanu, Eduard Rotenstein
    arXivPreprintCC BY-NC-ND 4.0Full textDynamical systemsProbabilityarXiv
  5. Inertial Primal-Dual Dynamics Methods Featuring Implicit Hessian-Driven Damping for Convex Optimization Problems in Continuous and Discrete Time
    Xiangkai Sun, Zeying Gao, Liang He +1
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@article{alexeev2026forbidden,
  title = {{Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof}},
  author = {Boris Alexeev and Dustin G. Mixon},
  journal = {Proceedings of the National Academy of Sciences},
  year = {2026},
  month = may,
  doi = {10.1073/pnas.2531760123},
  url = {https://doi.org/10.1073/pnas.2531760123},
  note = {CC BY-NC-ND},
}
RIS
TY  - JOUR
TI  - Forbidden Sidon subsets of perfect difference sets, featuring a human-assisted proof
AU  - Boris Alexeev
AU  - Dustin G. Mixon
PY  - 2026
DA  - 2026/05/22
JO  - Proceedings of the National Academy of Sciences
DO  - 10.1073/pnas.2531760123
UR  - https://doi.org/10.1073/pnas.2531760123
AB  - We resolve a $1,000 Erdős prize problem, complete with formal verification generated by a large language model. In over a dozen papers, beginning in 1976 and spanning two decades, Paul Erdős repeatedly posed one of his "favorite" conjectures: every finite Sidon set can be extended to a finite perfect difference set. We establish that {1, 2, 4, 8, 13} is a counterexample to this conjecture. During the preparation of this paper, we found that although this problem was presumed to be open for half a century, Marshall Hall, Jr. published a different counterexample three decades before Erdős first posed the problem. With a healthy skepticism of this apparent oversight, and out of an abundance of caution, we used ChatGPT to vibe prove both Hall's and our counterexamples in Lean.
SN  - 0027-8424
SN  - 1091-6490
ER  -