The longest path in the divisor graph: a lower bound above 7 for the constant
We prove that lim infx→∞ f(x) log x/x ≥ 7.4374, where f(x) is the largest number of vertices of a simple path in the divisor graph of {1, …, x}, in which two integers are joined when one divides the other. The best earlier lower bound was 0.76898, due to Weingartner. It is known that f(x) is of exact order x/log x, and Saias conjectured that f(x) ∼ cx/log x with 7 < c < 13; by our bound the limit, if it exists, is larger than 7. The path is given by an explicit recursive construction, and the proof is computer-assisted: the construction uses finitely many stored paths, which satisfy conditions that programs check, and the constant is a lower bound, computed in interval arithmetic, of a finite expression. MSC 2020: 11N25 (primary), 05C38, 11B75, 11Y60. Files: the paper (PDF), its LaTeX source, the programs with their inputs and expected outputs (reproduction ZIP), three data archives (the stored paths, the exact data that the evaluation reads, the numbers saved by its four runs) with their checksum file, the formal proofs (Lean ZIP), and a file that describes them.
Authors
- Sungsoo Na (ORCID: https://orcid.org/0009-0005-5257-3374)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-18
- DOI
- https://doi.org/10.5281/zenodo.24323272
- Primary Topic
- Analytic Number Theory Research
- Type
- preprint