Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure

Randy Davila

REVIEW

Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure

Randy Davila

Combinatorics · Submitted 3 Aug 2026

Pith's verdict: Davila proves the Erdős–Staton residue conjecture for common-divisor graphs with a novel degree-preserving realization; the proof is sound and deserves a serious referee.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 15, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv ID2608.04040 (version 2)

Pith ID3SRZ2QJ3, Pith's permanent record of this paper and its review

CitationRandy Davila. "Havel--Hakimi Residues of Common-Divisor Graphs: Complete Asymptotics and Prime-Counting Structure." arXiv:2608.04040 (2026). https://pith.science/paper/3SRZ2QJ3

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Davila has settled the asymptotic residue problem for the common-divisor graphs G_n: R(G_n) = (ζ(2)-1)n/log n + (ζ(2)-1-A)n/log^2 n + O(n/log^3 n). That is Staton's conjecture plus the second-order term, so the main result is exactly what the title promises.

The lower bound is the Caro–Wei sum over prime vertices, made exact via summation by parts (Proposition 2.1). This is clean and I verified the expansion term by term. The upper bound is the real work: Lemma 3.1 constructs a second realization of the same degree sequence by packing almost all bounded-degree primes into cliques and restoring the lost composite incidences with degree-preserving switches. The composite least-prime-factor classes act as reservoirs, and the auxiliary edges come from integers with least prime factor ℓ(k). The needed estimates (ℓ(k)≪log k, φ(k)/k ≫ 1/loglog k) are standard and cited to Montgomery–Vaughan; they give reservoir sizes vastly larger than the number of excluded vertices. The text compresses the simultaneous choice of auxiliary edges, but the margin is so large that a greedy selection works. This is a minor exposition gap, not a flaw.

Soft spots are minor. The code and exact data are not shipped, only 'available upon request'; the computations are explicitly not used to certify the theorem, so this is a small reproducibility issue. The unavailable Fan Chung-listed preprint [2] means novelty can't be checked against that source, but the authors disclose it and make no claim over it. The Theo-Conjecture narrative runs long for a math paper, but it is honest and does not interfere with the proof. The even-k switch in Lemma 3.1 is the densest argument; I'd ask the authors to expand the counting there during revision. The defect identity (Lemma 4.1) is exact, and Conjecture 4.2 is clearly labeled open and unused.

The citation pattern is honest: Graffiti, Erdős–Staton, and the residue–Caro–Wei inequality from Favaron et al. are all properly credited. No circularity or post-hoc fitting. I see no load-bearing weakness. This is for graph theorists working on residue and independence, and for combinatorial number theorists interested in arithmetic graphs. I would send this to a serious referee, and I expect it to be accepted after modest revisions. I'd also bring it to a reading group—the wiring of prime number estimates to a degree-sequence construction is a nice lesson.

Referee report

Significance

Staton's conjecture is a long-standing problem in the Graffiti/Erdos lineage, and the theorem is a strong resolution: it not only confirms the conjectured first-order constant but also gives a provable second-order term. The proof is parameter-free in the relevant sense: the constants zeta(2)-1 and A arise from the Prime Number Theorem and from convergent series, and the computational Conjecture 4.2 is not used in the proof of Theorem 1.1, so there is no circularity. The degree-preserving compression construction in Lemma 3.1 is a genuine novelty, and the exact arithmetic reduction in Proposition 2.1 is clean and independently checkable. The paper also provides exact finite verification of the construction and makes falsifiable predictions (Conjecture 4.2) that are clearly separated from the theorem. I rechecked the main arithmetic expansions and the switch accounting; the central claim is sound.

Minor objections (3)

[Section 3, paragraph after Eq. (12)] The comparison showing that the excluded vertices and the per-class auxiliary requirements are both negligible relative to each reservoir is correct, but it is very compressed. Stating explicitly the uniform lower bound |R_k| >> n/(log log n)^2, the bound O(n log log n / log n) for the excluded set, and the O(n/log n) bound for the total auxiliary requirement would make the greedy simultaneous choice of the auxiliary vertices substantially easier to verify.
[Section 6] The sentence that source code and data are 'available from the author upon request' is not a durable reproducibility artifact; a permanent repository DOI or similar stable link would be preferable.
[Proposition 2.1 proof] The two series identities sum_{k>=2} 1/(k^2(k-1)) = 2 - zeta(2) and sum_{k>=2} log k/(k^2(k-1)) = A are used without derivation; a one-line verification for the first would help the reader, and a reference or short indication for the second would also be convenient.

How Pith checks papers → · Full audit of this paper →

The paper

The paper claims

This paper proves that the Havel–Hakimi residue of the common-divisor graph on $\{2,\ldots,n\}$ is asymptotic to $(\zeta(2)-1)n/\log n$, with an explicit second-order term, settling the conjectured limiting constant.

The reading

The paper resolves the asymptotic problem for the Havel–Hakimi residue of the graph whose vertices are the integers $2$ through $n$, with an edge between two numbers exactly when they share a nontrivial divisor. It proves that the residue grows as $(\zeta(2)-1)n/\log n$, with an explicit second-order correction $(\zeta(2)-1-A)n/\log^2 n$, where $A=\sum_{k=2}^{\infty}\log k/(k^2(k-1))$. The lower bound comes from the Caro–Wei sum restricted to prime vertices; the matching upper bound comes from constructing a different graph with the same degree sequence whose independence number is no larger than the predicted value. The result matters because it ties the distribution of primes to a purely combinatorial degree-sequence algorithm, and because it turns a computer-generated conjecture into a rigorous theorem.

What carries the argument

Two mechanisms carry the proof. The lower bound uses the prime degree classes $P_k(n)=\{p\le n \text{ prime}:\lfloor n/p\rfloor=k\}$: each such prime has degree $k-1$, so its Caro–Wei contribution is $1/k$, and summation by parts gives the exact identity $P(n)=\pi(n)-\sum_{k=2}^{\lfloor n/2\rfloor}\pi(n/k)/(k(k-1))$, whose first two terms are the theorem's constants. The upper bound is carried by a degree-preserving realization lemma: for $K=\lfloor(\log n)^2\rfloor$, one can rewire $G_n$ without changing any degree so that each full block of $k$ primes of class $k$ becomes a $K_k$ clique, while the lost prime-to-composite incidences are restored by switches inside least-prime-factor classes of composites, which remain cliques with a matching removed. The reservoir of available composites is supplied by the integers $\ell(k)t\le n$ with $\gcd(t,k)=1$, where $\ell(k)$ is the least prime not dividing $k$; standard estimates show this reservoir is much larger than the number of switches needed.

Extended reading notes

Core claim

The central claim is a two-term asymptotic formula for the Havel–Hakimi residue of the graph $G_n$ on $\{2,\ldots,n\}$ with adjacency $\gcd(x,y)>1$. The paper proves that $$R(G_n)=\bigl(\zeta(2)-1\bigr)\frac{n}{\log n}+\bigl(\zeta(2)-1-A\bigr)\frac{n}{\$log^{2}$ n}+O\!\left(\frac{n}{\$log^{3}$ n}\right),$$ with $A=\sum_{k=2}^{\infty}\log k/(k^2(k-1))=0.3201986326\ldots$. Consequently $R(G_n)\log n/n\to\zeta(2)-1\approx 0.6449$, confirming the constant that had been proposed on numerical and heuristic grounds. The lower bound sums $1/(d(p)+1)$ over prime vertices and applies the theorem that the residue dominates the Caro–Wei sum. The upper bound builds a second graph with the same degree sequence in which almost all low-degree primes are compressed into cliques of the size forced by their degree, with the removed edges restored by switches inside composite classes; since the residue depends only on the degree sequence, the independence number of that auxiliary realization bounds the residue from above.

Load-bearing premise

The upper-bound construction depends on the number-theoretic guarantee that, for each even $k\le(\log n)^2$, enough unused composite vertices with least prime factor $\ell(k)$ remain to absorb all degree-preserving switches; if the reservoir estimates failed, the matching upper bound would not follow.

Editorial extensions

If this is right

The residue-to-prime-count ratio satisfies $R(G_n)/\pi(n)=\zeta(2)-1-A/\log n+O(1/\log^2 n)$, so the residue is asymptotically a fixed fraction, about $0.6449$, of the number of primes up to $n$.
Composite vertices contribute only $O(\sqrt{n})$ to the Caro–Wei sum, so the leading behavior of the residue is governed entirely by prime vertices and their multiplicative level sets $\lfloor n/p\rfloor$.
The Havel–Hakimi defect $R(G_n)-\mathrm{CW}(G_n)$ admits an exact telescoping decomposition into nonnegative local defects; exact computation suggests this total defect stays at most $2$, a far stronger statement than the main theorem.
If the bounded-defect conjecture holds, exact values of $R(G_n)$ can be obtained within a constant from the easily computed Caro–Wei sum, bypassing the full reduction process.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The clique-compression technique should transfer to other arithmetic graph families whose low-degree vertices are organized by short multiplicative intervals, such as divisor graphs or coprime complements; one would expect similar zeta-type constants to govern their leading terms.
The exact defect identity suggests a route to proving bounded total defect by showing that local defects decay after the first few reductions, and a direct analysis of the Havel–Hakimi trajectory for arithmetic degree sequences might close the gap observed computationally.
The reconstruction result implies that the unlabeled isomorphism type of the common-divisor graph encodes $\pi(n)$, while the degree sequence alone encodes only the coarser constant $\zeta(2)-1$; a natural test would be to see which other arithmetic functions survive in unlabeled form.

Original abstract

Let $G_n$ be the graph on $\{2,\ldots,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=\sum_{k=2}^{\infty}(\log k)/(k^2(k-1))$, then the first two terms are $\R(G_n)=(\zeta(2)-1)n/\log n+(\zeta(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_\beta(n\exp\{-(\log n)^\beta\})$ for every fixed $0<\beta<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 $\pi(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.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 6,544 input tokens.

What the abstract itself states, as probabilities: claims first 0.07 · states limitation 0.16 · human participants 0.01 · controlled comparison 0.06 · randomized assignment 0.01 · states quantitative result 0.98 · compares with prior results 0.89 · mentions code or data availability 0.02.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

Let $G_n$ be the graph on $\{2,\ldots,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=\sum_{k=2}^{\infty}(\log k)/(k^2(k-1))$, then the first two terms are $\R(G_n)=(\zeta(2)-1)n/\log n+(\zeta(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_\beta(n\exp\{-(\log n)^\beta\})$ for every fixed $0<\beta<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 $\pi(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.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Let $G_n$ be the graph on $\{2,\ldots,n\}$ in which two integers are adjacent when they have a common divisor greater than one.	background 0.99	0.08	0.02	asserted 0.90
s1	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}.	result 0.59	0.93	0.54	asserted 1.00
s2	If $A=\sum_{k=2}^{\infty}(\log k)/(k^2(k-1))$, then the first two terms are $\R(G_n)=(\zeta(2)-1)n/\log n+(\zeta(2)-1-A)n/\log^2n +O(n/\log^3n)$.	result 1.00	0.90	0.57	asserted 1.00
s3	More precisely, the difference between $\R(G_n)$ and the prime-vertex contribution to the Caro--Wei sum is $O_\beta(n\exp\{-(\log n)^\beta\})$ for every fixed $0<\beta<1/2$; this estimate yields every coefficient in the expansion.	result 0.91	0.89	0.22	asserted 1.00
s4	The upper bound follows from a degree-preserving realization in which almost all relevant prime vertices are partitioned into cliques.	method 0.99	0.86	0.04	asserted 1.00
s5	We also prove that the unlabeled graph determines $\pi(n)$ through its simplicial true-twin classes.	result 0.90	0.89	0.11	asserted 1.00
s6	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.	result 0.85	0.88	0.11	asserted 1.00
s7	An exact local-defect identity additionally reduces the conjectured sharp $+2$ residue bound to explicit prefix estimates.	result 0.59	0.84	0.07	asserted 0.89

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

Figures

**Figure 1.** Historical and methodological structure of the paper. a

**Figure 2.** Arithmetic structure behind the proof. a

**Figure 3.** Convergence to the zeta constant and its second-order correction. a

**Figure 4.** The bounded-defect problem suggested by the loop. a

Figures reproduced from arXiv:2608.04040 by the authors.

References

How the literature uses it

What this paper does with the arXiv papers it cites

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

What it cites

Cites as background 1 paper

They are closely related to divisor graphs and to the complementary coprime graphs; see, for example, [ref] .

Bipartite divisor graphs for integer subsets · Introduction · 1.00

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.