The sharp asymptotic for distinct multiples in an interval: a Lean formalization

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

Let f(n)f(n) be the least nonnegative integer hh for which the open interval (n,n+h)(n,n+h) contains distinct integers a1,…,ana_1,\ldots,a_n satisfying i∣aii\mid a_i. We give a complete Lean 4 formalization of f(n)∼(2/e)nlog⁡nf(n)\sim (\sqrt{2}/e)n\sqrt{\log n}. The formula was previously announced by David Turturean. The lower bound uses completely multiplicative weights, an exact convolution over powers of 22 and 33, and two inverse-exponential profiles. The upper bound constructs fractional matching weights from finite histograms of prime valuations. Explicit oscillation and stability estimates transfer the continuous transport identities to the integer divisibility graph.

Author comments: Manuscript accompanying Justin Sun Prize submission JSP-000579. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos710-lean/tree/ee0440a8f58b07bcdc89c8b12606052cb84aac91

Provenance statement

OpenAI AI assistance was used in mathematical development, formalization, checking and exposition, as disclosed in the manuscript. David Turturean retains credit for the prior mathematical result.

References

  1. T. F. Bloom, Erdős problem 710 , Erdős Problems, https://www.erdosproblems.com/710, accessed November 2, 2026.link
  2. P. Erdős, Some of my forgotten problems in number theory , Hardy--Ramanujan Journal 15 (1992), 34--50. https://doi.org/10.46298/hrj.1992.125.DOI
  3. P. Erdős and C. Pomerance, Matching the natural numbers up to nn with distinct multiples in another interval , Indagationes Mathematicae (Proceedings) 83 (1980), no. 2, 147--161. https://doi.org/10.1016/1385-7258(80)90018-9.DOI
  4. The Formal Conjectures Authors, Formal Conjectures , definitions of Erdős Problems 710 and 711. Source blobs: e65522825737943cf4de3b41fa00e101288af6f3 (710); d0170ecd49a0621d4f3e951de1d0ec9690dab6a5 (711). https://github.com/google-deepmind/formal-conjectures.link
  5. P. Hall, On representatives of subsets , Journal of the London Mathematical Society s1-10 (1935), no. 1, 26--30. https://doi.org/10.1112/jlms/s1-10.37.26.DOI
  6. The Mathlib Community, Mathlib , Lean mathematical library. The revision used is specified in Appendix app:reproducibility . https://github.com/leanprover-community/mathlib4.link
  7. A. Kontorovich and contributors, PrimeNumberTheoremAnd . The revision used is specified in Appendix app:reproducibility . https://github.com/AlexKontorovich/PrimeNumberTheoremAnd.link
  8. D. Turturean, An asymptotic formula for distinct multiples in an interval , manuscript, version compiled November 1, 2026 (25 pages). Public announcement, September 23, 2026 (https://www.erdosproblems.com/forum/thread/710/proof-claims#proof-claim-344); manuscript (https://www.overleaf.com/read/jvdyzbbmbvcf).link

Version history

  1. v1 · 11 pagesSubmitted by Liam KruerManuscript accompanying Justin Sun Prize submission JSP-000579. Pinned source and Lean proof materials: https://github.com/Ghuffy1/erdos710-lean/tree/ee0440a8f58b07bcdc89c8b12606052cb84aac91CurrentNov 20, 2026