Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure
Abstract
Let Gn be the graph on {2,…,n} in which two integers are adjacent when they have a common divisor greater than one. We determine the complete asymptotic expansion of its Havel--Hakimi residue R(Gn), confirming a leading-constant prediction of Staton recorded in Fajtlowicz's \emph{Written on the Wall}. If A=∑k=2∞(log k)/(k2(k−1)), then the first two terms are R(Gn)=(ζ(2)−1)n/log n+(ζ(2)−1−A)n/log2n +O(n/log3n). More precisely, the difference between R(Gn) and the prime-vertex contribution to the Caro--Wei sum is Oβ(nexp{−(log n)β}) for every fixed 0<β<1/2; this estimate yields every coefficient in the expansion. The upper bound follows from a degree-preserving realization in which almost all relevant prime vertices are partitioned into cliques. We also prove that the unlabeled graph determines π(n) through its simplicial true-twin classes. Stable inverses for weighted sums of the resulting degree-class counts give criteria equivalent to the Riemann hypothesis, including one involving only the Caro--Wei sum. An exact local-defect identity additionally reduces the conjectured sharp +2 residue bound to explicit prefix estimates.
Related
- Complete Factorial Asymptotics and Integrable Structure of Generalized Charlier Recurrence Coefficients
- A Joint Local Limit Theorem for Prime Divisor Counting Functions
- A Divisor-Weighted Golomb Sequence: Zeta Asymptotics and Arithmetic Fluctuations
- Multiplicity-One Structure in Graded Zero-Divisor Graphs
- Counting linear extensions of incidence posets of bipartite graphs is #P-complete
BibTeX
@misc{davila2026havelhakimi,
title = {{Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure}},
author = {Randy Davila},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.04040},
eprint = {2608.04040},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.04040},
}
RIS
TY - UNPB
TI - Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure
AU - Randy Davila
PY - 2026
DA - 2026/08/31
PB - arXiv
DO - 10.48550/arxiv.2608.04040
UR - https://arxiv.org/abs/2608.04040
AB - Let G_n be the graph on {2,…,n} in which two integers are adjacent when they have a common divisor greater than one. We determine the complete asymptotic expansion of its Havel--Hakimi residue R(G_n), confirming a leading-constant prediction of Staton recorded in Fajtlowicz's \emph{Written on the Wall}. If A=∑_k=2^∞(log k)/(k^2(k−1)), then the first two terms are R(G_n)=(ζ(2)−1)n/log n+(ζ(2)−1−A)n/log^2n +O(n/log^3n). More precisely, the difference between R(G_n) and the prime-vertex contribution to the Caro--Wei sum is O_β(nexp{−(log n)^β}) for every fixed 0<β<1/2; this estimate yields every coefficient in the expansion. The upper bound follows from a degree-preserving realization in which almost all relevant prime vertices are partitioned into cliques. We also prove that the unlabeled graph determines π(n) through its simplicial true-twin classes. Stable inverses for weighted sums of the resulting degree-class counts give criteria equivalent to the Riemann hypothesis, including one involving only the Caro--Wei sum. An exact local-defect identity additionally reduces the conjectured sharp +2 residue bound to explicit prefix estimates.
ER -