An exact formula for fork-free sets of integers and the irrationality of their density
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
Let be the largest size of a subset of in which no element divides two distinct other elements. We prove the exact formula , where is the two-prime grid rank and is an explicit union of intervals. A matching construction follows from a cutoff recursion whose finite certificates are checked in Lean. The limit is irrational. The proof uses rotation returns, a two-cutoff -adic nonvanishing argument, and a three-place Subspace Theorem. The linked Lean development verifies the exact formula, convergence, and irrationality.
Provenance statement
References
- G. Audemard and L. Simon, Predicting learnt clauses quality in modern SAT solvers, in: Proc. 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), 399--404.
- H. Barbosa et al., cvc5: a versatile and industrial-strength SMT solver, in: Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2022), Lecture Notes in Comput. Sci. 13243, Springer, 2022, 415--442.
- T. F. Bloom, Erdős Problem #1062 , https://www.erdosproblems.com/1062. Accessed 21 September 2026.link
- E. Bombieri and W. Gubler, Heights in Diophantine Geometry , New Mathematical Monographs 4, Cambridge University Press, Cambridge, 2006.
- Conjectures.io, Erdős 1062 (parts ii) , formalized task fc-8432eac9-parts-ii-71df995464-formalized-v1 , https://conjectures.io/problems/erdos1062-erdos-1062-parts-ii. Accessed 21 September 2026.link
- D. Davis, Forbidden subgraphs in divisor graphs and an Erdős divisibility problem, preprint, arXiv:2604.17613 (https://arxiv.org/abs/2604.17613) (2026).arXiv
- L. de Moura and N. Bjørner, Z3: an efficient SMT solver, in: Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), Lecture Notes in Comput. Sci. 4963, Springer, 2008, 337--340.
- L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language, in: Automated Deduction -- CADE 28 , Lecture Notes in Comput. Sci. 12699, Springer, 2021, 625--635.
- J.-H. Evertse and R. G. Ferretti, A further improvement of the quantitative Subspace Theorem, Ann. of Math. (2) 177 (2013), 513--590.
- J.-H. Evertse and H. P. Schlickewei, A quantitative version of the absolute subspace theorem, J. Reine Angew. Math. 548 (2002), 21--127.
Show all 26 referencesShow fewer references
- Google DeepMind, Formal Conjectures , file FormalConjectures/ErdosProblems/1062.lean , https://github.com/google-deepmind/formal-conjectures. Accessed 21 September 2026.link
- S. Goel, R. Lunia and A. Ray, Diophantine approximation and the subspace theorem, preprint, arXiv:2502.00731 (https://arxiv.org/abs/2502.00731) (2025).arXiv
- E. Goldberg and Y. Novikov, Verification of proofs of unsatisfiability for CNF formulas, in: Design, Automation and Test in Europe Conference and Exhibition (DATE 2003), IEEE, 2003, 886--891.
- R. K. Guy, Unsolved Problems in Number Theory , 3rd ed., Problem Books in Mathematics, Springer, New York, 2004.
- K. Lebensold, A divisibility problem, Stud. Appl. Math. 56 (1977), no. 3, 291--294.
- A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515--534.
- Lean FRO, comparator , https://github.com/leanprover/comparator.link
- Lean FRO, lean4export , https://github.com/leanprover/lean4export.link
- The mathlib Community, The Lean mathematical library, in: Proc. 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), 2020, 367--381.
- K. F. Roth, Rational approximations to algebraic numbers, Mathematika 2 (1955), 1--20, corrigendum 168.
- H. P. Schlickewei, The -adic Thue--Siegel--Roth--Schmidt theorem, Arch. Math. (Basel) 29 (1977), 267--270.
- W. M. Schmidt, Norm form equations, Ann. of Math. (2) 96 (1972), 526--551.
- W. M. Schmidt, Diophantine Approximation , Lecture Notes in Math. 785, Springer, Berlin, 1980.
- W. M. Schmidt, Diophantine Approximations and Diophantine Equations , Lecture Notes in Math. 1467, Springer, Berlin, 1991.
- V. T. Sós, On the distribution mod 1 of the sequence , Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 1 (1958), 127--134.
- N. Wetzler, M. J. H. Heule and W. A. Hunt, Jr., DRAT-trim: efficient checking and trimming using expressive clausal proofs, in: Theory and Applications of Satisfiability Testing (SAT 2014), Lecture Notes in Comput. Sci. 8561, Springer, 2014, 422--429.
Version history
- v1 · 17 pagesSubmitted by Liam KruerTeX edition of the manuscript accompanying Justin Sun Prize submission JSP-000882. Pinned manuscript, Lean proof and exact full-statement audit: https://github.com/TheJustinSunPrize/awards/pull/4905CurrentNov 21, 2026