Small maximal integer Sidon sets by finite phase colorings

Primarily AI-generated textHuman understanding: no partsmath.NT — Number Theory

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

Every sufficiently large integer interval {1,…,N}\{1,\ldots,N\} contains an inclusion-maximal Sidon set of size O(N1/3)O(N^{1/3}). A quadratic seed supplies exact integer differences, and a periodically labeled family of anchors covers each relevant local window. Finite-dimensional bounds for affine sign patterns give a fixed alphabet of translates and a common periodic word. Two separated alphabets give Sidon, sum-free tags for all primes. The seed blocks every point outside two intervals of length O(p2)O(p^2) and the multiples of pp, with p≍N1/3p\asymp N^{1/3}. A maximal completion adds only O(p)O(p) elements. The linked Lean verification covers the original upper-bound target.

Author comments: TeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000154. Pinned paper, Lean bridge and audit are listed at https://github.com/TheJustinSunPrize/awards/pull/5531

Provenance statement

The manuscript acknowledges substantial Codex assistance. This TeX edition spells out the necessity direction of the exact window criterion and updates the appendix to the portable project's 178 audited public theorems.

References

  1. P. Erdős, A. Sárközy, and V. T. Sós, On sum sets of Sidon sets, I, J. Number Theory 47 (1994), no. 3, 329--347. DOI (https://doi.org/10.1006/jnth.1994.1040).DOI
  2. I. Z. Ruzsa, A small maximal Sidon set, Ramanujan J. 2 (1998), 55--58. DOI (https://doi.org/10.1023/A:1009757824153).DOI
  3. N. Sauer, On the density of families of sets, J. Combin. Theory Ser. A 13 (1972), no. 1, 145--147. DOI (https://doi.org/10.1016/0097-3165(72)90019-2).DOI
  4. S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), no. 1, 247--261. DOI (https://doi.org/10.2140/pjm.1972.41.247).DOI
  5. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in Automated Deduction---CADE 28 , LNCS 12699, Springer, 2021, 625--635. DOI (https://doi.org/10.1007/978-3-030-79876-5_37).DOI
  6. The mathlib Community, The Lean mathematical library, in Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP '20) , ACM, 2020, 367--381. DOI (https://doi.org/10.1145/3372885.3373824).DOI
  7. Formal Conjectures project and Conjectures.io, Erdős problem 156, formalized task bundle at revision bf40872f .
  8. Justin Sun Prize submission JSP-000154 (https://github.com/TheJustinSunPrize/awards/pull/5531) and pinned manuscript and verification notes (https://github.com/JENW1N/erdos-156-proof/blob/a9e52bd1d056f26888db473ab7320bd9768c2c6b/paper/README.md).link

Version history

  1. v1 · 10 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000154. Pinned paper, Lean bridge and audit are listed at https://github.com/TheJustinSunPrize/awards/pull/5531CurrentNov 21, 2026