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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

The longest path in the divisor graph: a lower bound above 7 for the constant

Sungsoo Na
1 links
Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
preprint

The longest path in the divisor graph: a lower bound above 7 for the constant

Sungsoo Na
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Analytic Number Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon