REVIEW 2 major objections 5 minor 18 references
On divisibility relation graphs
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Adding two fresh primes to n preserves every eigenvalue of its divisor graph, and doubles multiplicities when n has a squarefree prime factor.
desk verdict A solid, mostly elementary paper with a genuinely new spectral divisibility theorem; the main proofs hold up, but one determinant identity and two propositions need tightening before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the divisor graph D_n viewed as the compatibility graph of the divisor partially ordered set, so eigenvectors are functions f on divisors satisfying a divisor-sum eigenvalue equation. The engine of the proof is a tensor-product lifting: the two-by-two partially ordered set S_0 carries a special function h assigning 0 to (0,0) and (1,1) and ±1 to the two middle elements, and because all lower and upper sums of h vanish, tensoring any eigenvector of D_S with h produces an eigenvector of D_{S×S_0} with the same eigenvalue. For the two-prime family D_{p q^a}, the zero-eigenvalue criterion is carried by a block Schur complement calculation in which the crucial identity B $D^{{-1}}$ C = 0 for the off-diagonal blocks of M_{a+6} yields det(M_a) = det(M_{a+6}).
What would settle it
Compute the determinant of the adjacency matrix of D_{p $q^{6}$} for any distinct primes p and q; the theorem predicts it equals det(D_{p $q^{0}$}) = -1, and that D_{p $q^{7}$} has determinant 0. More directly, evaluate any unverified entry of the 12-by-12 product B $D^{{-1}}$ C in Proposition 3.16; a single nonzero entry would disprove the determinant periodicity, and with it the if-and-only-if statement about eigenvalue 0.
Extended reading notes
Core claim
The paper's central discovery is that the spectrum of D_n is inherited when n is multiplied by two new primes, and the mechanism is an eigenvector lifting for partially ordered sets. For any partially ordered set S and the four-element partially ordered set S_0 = {0,1}^2, every eigenvector of the compatibility graph of S lifts to an eigenvector of the compatibility graph of S × S_0 with the same eigenvalue; the lift uses a fixed vector h on S_0 that is zero on (0,0) and (1,1) and takes opposite signs on (0,1) and (1,0), so that all sums of h below or above any point vanish. Applied to divisors, this gives f_n | f_{npq}, and when n contains a prime to the first power, two independent lifts give $f_n^{2}$ | f_{npq}. The paper further shows that -1 is always an eigenvalue, that -2 and 1 occur when n has an odd number of distinct prime factors, that 0 occurs when the number is even, and that for n = p q^a the eigenvalue 0 appears exactly when a ≡ 1 (mod 6), established through the determinant periodicity det(M_a) = det(M_{a+6}).
Load-bearing premise
The proof of the period-6 zero-eigenvalue criterion for D_{p q^a} rests on the claim that the off-diagonal block product B $D^{{-1}}$ C is exactly the zero matrix in a 12-by-12 block calculation, and the text verifies only one entry of that identity.
Editorial extensions
If this is right
- Every eigenvalue of D_n appears as an eigenvalue of D_{npq}, and when n has a prime to the first power, each eigenvalue appears with at least twice its original multiplicity.
- All the special eigenvalues identified for smaller divisor graphs—including -1 always, -2 and 1 for odd numbers of distinct prime factors, and 0 for even numbers—automatically persist in every extension by two new primes.
- Because D_n is perfect, its chromatic number equals its clique number 1 + Ω(n), and the paper's explicit coloring by Ω(m) realizes this bound.
- For two-prime numbers of the form p q^a, the eigenvalue 0 is present exactly when the exponent a is congruent to 1 modulo 6, so a single spectral computation detects an arithmetic congruence.
- The planarity classification and the formulas for clique and independence numbers show that the isomorphism class and these invariants depend only on the factorization type of n, not on the sizes of the primes.
Reading between the lines
- The period-6 behavior found for the zero eigenvalue of D_{p q^a} may hold for other eigenvalues as well; a testable extension is to compute the full characteristic polynomial of D_{p q^a} for many a and check whether all coefficients or eigenvalues vary periodically with the same period.
- The numerical multiplicities of 0, 1, and -2 for squarefree n follow the sequences 2,5,14,42,132,429 and 2,10,42,170,682,2730; the paper's tensor-product subspace explains only part of that growth, so a closed-form multiplicity formula for squarefree n remains a natural conjecture.
- The determinant-periodicity proof hinges on one unverified 12-by-12 block identity; checking all entries of B D^{-1} C computationally would settle that gap, and similar block identities might prove an analogous periodicity for D_{p^a q^b}.
- The eigenvector-lifting theorem is stated for arbitrary partially ordered sets, not only divisor lattices, so the same spectral inheritance holds for any compatibility graph obtained as the product of a partially ordered set with the two-point chain.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the divisibility relation graph D_n whose vertices are the divisors of n and whose edges join comparable divisors. It develops elementary invariants: clique number 1+Ω(n), independence number via the de Bruijn–Tengbergen–Kruyswijk theorem, chromatic number, distance properties, and a complete planarity classification. The spectral part proves divisibility relations between characteristic polynomials when new primes are adjoined (Theorems 3.1 and 3.2), gives explicit eigenvectors for selected eigenvalues, and studies the eigenvalue 0 for numbers with two prime factors, including a determinant periodicity result for D_{p q^a} and a partial result for D_{p^a q^b}.
Significance. If the stated spectral results hold, this is a useful contribution to the spectral theory of divisor posets and compatibility graphs, with potential connections to supercharacters. The elementary section is clean and largely self-contained. The tensor-product lifting argument in Proposition 3.5 and the block-determinant proof of Theorem 3.1 are elegant and likely to be reusable. The paper also provides executable code and presents its numerical tables as observations rather than as premises. However, the significance is currently conditional: two propositions that feed directly into Theorem 1.2 are stated without proof, and the key periodicity computation in Proposition 3.16 is only partially verified.
major comments (2)
- [§3.2.3–3.2.4, Propositions 3.11 and 3.12] Propositions 3.11 and 3.12 are asserted without any proof. These two statements are exactly the eigenvalue-1 part of Theorem 1.2(4) and the whole of Theorem 1.2(5). No argument follows the proposition statements, and the surrounding material (Remark 3.13 and Corollary 3.15) does not establish them. The authors should either supply complete proofs or explicitly downgrade these assertions to numerical observations/conjectures; as written, the theorems depend on unproved claims.
- [§3.3, Proposition 3.16] The proof of det(M_a)=det(M_{a+6}) rests entirely on the claim that B D^{-1} C = 0_{2a+2,2a+2}. The parenthetical verification lists four scalar identities but does not state the reduction that these four sums exhaust all entries of B D^{-1} C, nor does it show the arithmetic that yields zero from the displayed M_5^{-1}. Since this identity is the load-bearing step for Proposition 3.17 and hence for Theorem 1.2(6), the computation should be carried out explicitly or at least the reduction to the four sums should be stated and each sum evaluated. Direct evaluation from the displayed inverse does give zero in each case, so the issue is a missing proof rather than a detected falsehood.
minor comments (5)
- [§2.1] There are minor typographical errors: 'ismorphic' should be 'isomorphic' and 'a canonical a map' should be 'a canonical map'.
- [§2.2.1, Proposition 2.11] The phrase 'is and only if' should read 'if and only if'.
- [§3.1, Remark 3.6] The notation S' and S'' in Remark 3.6 is used without definition; the intended meaning is inferable from context but should be made explicit.
- [§3.1, proof of Theorem 3.2] The block row operation labeled (7), R_7 ← R_6 − R_7, appears to be a typographical slip: a row operation should modify a single row. The subsequent block matrix is consistent with the intended computation, but the notation should be corrected.
- [§3.3, Proposition 3.18] In the proof of Proposition 3.18 the symbol s is used both for the number of U^T blocks and for the scalar sum s=Σ_{i≥2} b_i + Σ_{i≥1} b'_i. Renaming one of these quantities would improve readability.
Circularity Check
No significant circularity: theorems are proved from elementary block-matrix and eigenvector arguments; self-citations are accompanied by direct proofs.
full rationale
The paper's central divisibility claims (Theorems 3.1, 3.2, 3.3) are established by self-contained block-determinant and tensor-product arguments, not by importing the claims. The special-eigenvalue results (Propositions 3.7, 3.11, 3.12) construct explicit eigenvectors. Lemma 3.9 cites [14], which is authored in part by the present authors, but the lemma is followed by the relevant eigenvector proof in the text, so the citation is not load-bearing. The numerical tables are presented as observations and are not used as premises for the theorems. The only caveat is Proposition 3.16, where the assertion BD^{-1}C=0 is supported by a partial verification of one scalar aggregate rather than a full displayed computation; this is a completeness or rigor gap in a direct calculation, not a circular reduction of the theorem to its own input. No fitted parameter is renamed as a prediction, and no uniqueness claim is imported from the authors' prior work. The paper is self-contained against external benchmarks, so the circularity score is 0.
Assumptions & free parameters
assumptions (5)
- standard math Fundamental theorem of arithmetic: each divisor of n = prod p_i^{a_i} corresponds uniquely to a vector (alpha_i) with 0 <= alpha_i <= a_i.
- standard math Lucas' theorem modulo 2, which gives binomial(i,j) mod 2 = product over bits of binomial(bit_i, bit_j) mod 2.
- standard math Dilworth's theorem and the perfectness of comparability graphs.
- standard math Sperner property of the divisor lattice (de Bruijn, van Ebbenhorst Tengbergen, Kruyswijk [3]).
- standard math Standard determinant identities for block matrices (product rule, Schur complement) and invariance under row and column permutations.
Cite this review
Pith. "Pith review of On divisibility relation graphs." pith.science (2026). https://pith.science/paper/D2TIULOX
@misc{pith2026250706873,
author = {Pith},
title = {Pith review of: On divisibility relation graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/D2TIULOX}},
note = {Machine review of arXiv:2507.06873}
}
abstract
For each positive integer $n$, we define the divisibility relation graph $D_n$ whose vertex set is the set of divisors of $n$, and in which two vertices are adjacent if one is a divisor of the other. This type of graph is a special case of graphs associated with a partial order, which have been widely studied in the literature. In this work, we determine various graph-theoretic invariants of divisibility relation graphs, such as their clique and independence numbers, and their planarity. We also discuss various spectral properties that are discovered by our numerical experiments.
Reference graph
Works this paper leans on
-
[1]
Rodrigo Angelo,A Cameron and Erdos conjecture on counting primitive sets, Integers18(2018), Paper No. A25,
work page 2018
-
[2]
P . J. Cameron and P . Erdos,On the number of sets of integers with various properties, Number theory (Banff, AB, 1988), de Gruyter, Berlin, 1990, pp. 61–79. MR 1106651
work page 1988
-
[3]
N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk,On the set of divisors of a number, Nieuw Arch. Wiskunde (2)23(1951), 191–193. MR 43115
work page 1951
-
[4]
R. P . Dilworth,A decomposition theorem for partially ordered sets, Ann. of Math. (2)51(1950), 161–166. MR 32578
work page 1950
-
[5]
Paul Erd ˝os and Eric Saias,Sur le graphe divisoriel, Acta Arithmetica73(1995), no. 2, 189–198
work page 1995
-
[6]
Christopher F Fowler, Stephan Ramon Garcia, and Gizem Karaali,Ramanujan sums as supercharacters, The Ramanujan Journal35(2014), 205–241
work page 2014
-
[7]
D. R. Fulkerson,Note on Dilworth’s decomposition theorem for partially ordered sets, Proc. Amer. Math. Soc.7 (1956), 701–702. MR 78334
work page 1956
-
[8]
Mare (https://mathoverflow.net/users/61949/mare),Kernel of a matrix and the catalan numbers, MathOver- flow, URL:https://mathoverflow.net/q/400865 (version: 2021-08-02)
work page 2021
Show all 18 references
-
[9]
20, Cambridge university press, 1997
Rudolf Lidl and Harald Niederreiter,Finite fields, no. 20, Cambridge university press, 1997
1997
-
[10]
,n}, European J
Nathan McNew,Counting primitive subsets and other statistics of the divisor graph of{1, 2, . . . ,n}, European J. Combin.92(2021), Paper No. 103237, 20. MR 4149161
2021
-
[11]
4, 329–339
Paul Melotti and ´Eric Saias,On path partitions of the divisor graph, Acta Arith.192(2020), no. 4, 329–339. MR 4054577
2020
-
[12]
Merzel, J ´an Min´aˇc, Tung T
Jonathan L. Merzel, J ´an Min´aˇc, Tung T. Nguyen, and Nguyen Duy Tˆan,On divisibility relation graphs,https: //github.com/tungprime/Divisor-graphs, 2025
2025
-
[13]
J ´an Min´aˇc, Tung T Nguyen, and Nguyen Duy Tˆan,On the gcd graphs over the polynomial ring and related topics, preprint (2024)
2024
-
[14]
Nguyen, and Federico W
J ´an Min´aˇc, Lyle Muller, Tung T. Nguyen, and Federico W. Pasini,Joins of normal matrices, their spectrum, and applications, To appear in Mathematica Slovaca (2025), arXiv:2207.04181
2025 arXiv
-
[15]
Nguyen and Nguyen Duy T ˆan,On gcd-graphs over finite rings, arXiv preprint arXiv:2503.04086 (2025)
Tung T. Nguyen and Nguyen Duy T ˆan,On gcd-graphs over finite rings, arXiv preprint arXiv:2503.04086 (2025)
2025 arXiv
-
[16]
AD Pollington,There is a long path in the divisor graph, Ars Combin16(1983), 303–304
1983
-
[17]
Numer40(1983), 291–304
Carl Pomerance,On the longest simple path in the divisor graph, Congr. Numer40(1983), 291–304
1983
-
[18]
S. U. Rehman, A. Q. Baig, M. Imran, and Z. U. Khan,Order divisor graphs of finite groups, An. S ¸tiint ¸. Univ. “Ovidius” Constant ¸a Ser. Mat.26(2018), no. 3, 29–40. MR 3909258 23 SOKAUNIVERSITY OFAMERICA Email address:jmerzel@soka.edu UNIVERSITY OFWESTERNONTARIO Email addres...
2018
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.