XSci

Integral saturation of adjacency-degree lattices

Zhipeng Lu

Submitted by Zhipeng Lu

Published November 15, 2026 · Version v1, November 15, 2026 · DOI 10.66977/xsci.2611.002i

Theoretical Computer Science, Combinatorics

Abstract

Let AA be the adjacency matrix of G∼G(n,1/2)G\sim G(n,1/2), let
D=diag⁡(A1)D=\operatorname{diag}(A\mathbf1), and let ΛG=Z⟨A,D⟩1\Lambda_G=\mathbb Z\langle A,D\rangle\mathbf1. We prove
Pr⁡[ΛG≠Zn]≤n−3/20+o(1)\Pr[\Lambda_G\ne\mathbb Z^n]\le n^{-3/20+o(1)}. Thus two dependent graph operators generate the entire vertex lattice from the constant vector, simultaneously over every prime field. Adjacency alone has a modulo-two rank obstruction for every simple graph of order greater than one, even though its rational word span is typically full.

The proof first constructs words containing at most two adjacency
operations whose integer span contains ΔG3Zn\Delta_G^3\mathbb Z^n,
where ΔG\Delta_G is the product of the pairwise differences
between distinct degree values. This confines all possible arithmetic
obstructions to a finite prime range on a single event. We then
remove the remaining obstructions using conditional alternating
forms, symmetric random-matrix code estimates, and uniform counts
of degree-graded invariant subspaces.

We connect the integer lattice to graph reconstruction through
pointed moments. Saturation forces every pointed orthogonal AD
intertwiner to be a vertex permutation. The short-word
construction also shows that a fixed polynomial-size family of
ordinary caterpillars, of diameter at most seven and order
O(nlog⁡n)O(\sqrt{n\log n}), identifies almost every graph among all
finite simple graphs. For nonsaturated full-rank lattices, we give
an exact description of the moment fibre by admissible unimodular
overlattices; at index two, the only possible ambiguity is a
specified four-vertex Godsil--McKay switch.

View PDF

Review reports

xPeerd (AI review)

November 15, 2026

AI Review (xPeerd — DAReview)

Summary

This manuscript studies the lattice generated over the integers by repeatedly applying the adjacency matrix A and the degree diagonal D to the all-ones vector in a random graph G(n, 1/2). The main claim is that this adjacency–degree word lattice equals Zn with high probability, formalized as “Pr[ΛG ≠ Zn] ≤ n−3/20+o(1),” and positioned as a stronger arithmetic analogue of rational controllability. The paper also develops consequences for graph reconstruction via principal AD moments and bounded-diameter caterpillar test families. The work is technically ambitious, conceptually interesting, and appears to aim at a genuine contribution connecting random graph theory, integer lattices, and reconstruction. The exposition is generally rigorous and well organized, with a clear roadmap in the introduction and section outline. At the same time, several claims are unusually broad relative to the compact presentation in the main text, and some central notions of significance, novelty boundaries, algorithmic scope, and dependence on recent preprints need sharper positioning. The manuscript is strongest when stating explicit structural results and weakest when translating those results into broader claims about identification, rigidity, and practical recoverability. The paper also contains an explicit AI disclosure indicating material use of ChatGPT and Codex in exposition and parts of the proofs, which merits careful editorial scrutiny regarding verification burden and authorship transparency.

Potential Major Revisions

  1. Clarify the manuscript’s precise novelty relative to closely neighboring preprints and adjacent reconstruction literature.

The paper makes strong originality claims while simultaneously locating itself very near several 2025–2026 preprints. For example, the introduction states, “That preprint announces determination of almost all graphs by their generalized spectrum. Our proof is independent, and generalized cospectrality does not require intertwining D,” and also notes that “Lu–Li [LL26] develop principal AD moments and their caterpillar interpretation, while [Lu26] constructs uniform probes for real cyclic modules.” This positioning is plausible, but still too compressed for a paper making several layered claims: random integral saturation, reconstruction consequences, bounded-diameter test families, and index-two fibre classification. I think the manuscript needs a dedicated novelty subsection, probably at the end of the introduction, separating exactly which results are new, which are extensions of earlier AD-moment work, and which are corollaries of known frameworks plus new arithmetic input. As written, the paper leaves the reader to infer novelty by subtraction from recent preprints, which is not fully satisfactory for a mathematically dense article.

  1. Substantially strengthen the justification for the significance of the main probability exponent and the theorem’s sharpness.

The manuscript proves “Pr[ΛG ≠ Zn] ≤ n−3/20+o(1)” and later concedes, “The exponent records the degree thresholds used in Section B; we have not attempted to optimize it.” This is honest, but the paper does not sufficiently explain whether the exponent is believed to be far from optimal, whether the polynomial decay is a proof artifact, or whether some structural obstruction makes exponential decay unlikely. Because the title and framing emphasize a high-probability saturation theorem, readers will naturally ask what is genuinely hard here: the arithmetic structure, the dependence between A and D, or only the chosen method. A stronger discussion is needed to distinguish theorem strength from proof strength. Without that, the result risks being read as technically impressive but quantitatively opaque.

  1. Make the logical dependency between the main saturation theorem and the reconstruction results much more explicit.

Section 4 says, “The arithmetic theorem also explains when scalar observations recover a graph’s vertex coordinates,” then develops moment-based reconstruction and short caterpillar tests. It later adds, “There is one further point in that argument: to turn this short Gram reconstruction into a permutation, one need not invoke the local-prime estimates,” and Remark C.1 similarly says rigidity uses less than integral saturation. This is important, but currently undercuts the narrative: the paper advertises integral saturation as central, yet some reconstruction consequences seem to require only the global integer construction or AD-fullness plus rigidity. The manuscript should separate:

  • which reconstruction consequences require full integral saturation,
  • which need only AD-fullness, and
  • which follow already from the cut-based integer propagation event.
    At present, the text partly acknowledges this distinction but not in a way that prevents readers from over-attributing consequences to Theorem 1.1.
  1. Provide a fuller reproducibility account for the computational and certificate-based parts.

The manuscript states, “When G is given, one can compute ΛG and its Smith invariants in deterministic polynomial time,” and refers to “exact computational certificates” in the appendices. It also presents determinant certificates for index-two examples, e.g., “Their greatest common divisor is 2. Thus ΛG has full rank and its index divides 2.” However, the paper does not appear, from the available text, to specify a reproducibility package, code repository, input graph encoding, or independent verification workflow. Since some examples and certificate claims are computationally delicate, the paper should include an explicit reproducibility subsection describing what was computed, with what software, and how a referee can verify the examples without reconstructing the entire pipeline from prose.

  1. Address more directly the epistemic implications of the AI disclosure.

The manuscript’s disclosure says, “We used ChatGPT and OpenAI Codex to assist with the literature review, the organization and drafting of the exposition, and checks of mathematical arguments and supporting verification code. These tools materially affected the exposition and proofs in Sections 2–4, Appendices A and B, and Supplementary Sections S1–S3 and S8…” This is unusually extensive and touches core proof sections rather than peripheral language polishing. I think this does not invalidate the work, but it does increase the verification burden. The author should clarify whether every AI-assisted proof segment was independently checked line-by-line by the author, whether any generated code was formally or empirically validated, and whether any proof ideas originated from these tools. Because the disclosure explicitly says the tools “materially affected the exposition and proofs,” editorial and referee expectations should be addressed inside the manuscript, not left implicit.

  1. Tighten the interpretation of algorithmic claims to avoid overreading.

The manuscript commendably includes caveats such as, “This is an identification theorem: no polynomial-time decoder from this profile is claimed,” and “This description is finite but is not itself a polynomial-time classification algorithm.” Yet the surrounding prose sometimes creates a stronger algorithmic impression by emphasizing deterministic polynomial-time computability of ΛG and short certificates. I recommend an explicit boxed remark distinguishing:

  • polynomial-time computation from a graph input,
  • finite identifiability from moment/caterpillar profiles, and
  • absence of an efficient decoder from those profiles.
    This would reduce the risk of readers conflating structural identifiability with efficient reconstruction.
  1. Expand the fraud-resistance / coherence check around several very broad statements.

A few claims are ambitious enough to need extra contextualization to avoid appearing overstated. For example, the abstract says, “Saturation forces every pointed orthogonal AD intertwiner to be a vertex permutation,” and also claims that “a fixed polynomial-size family of ordinary caterpillars, of diameter at most seven and order O(√n log n), identifies almost every graph among all finite simple graphs.” These may be correct, but they are striking and should be accompanied by more reader-facing explanation of why the dependence on D changes the situation so drastically relative to adjacency alone, and how the caterpillar consequence should be interpreted against known lower bounds. The paper does mention, “even all caterpillars of diameter at most four fail to identify almost every graph” and that “the gap between diameters five and seven remains open.” Still, the high-level narrative would benefit from more intuition to ensure the results appear earned rather than merely asserted.

Warning on paper-mill/fraud traits: I do not see classic paper-mill indicators such as incoherent citations, meaningless jargon chains, impossible methodology, or fabricated scientific framing. The manuscript fits a recognizable combinatorics/random-matrix/graph-reconstruction paradigm and contains technically coherent internal references. The main caution is not fraud but verification load, especially because of the broad claim set and the explicit AI-assisted proof disclosure.

Potential Minor Revisions

  1. Typographic and notation consistency issues
  • In the abstract, the phrase “short-word construction” appears awkwardly line-broken around the formula for caterpillar size: “The short-word construction also shows that a fixed polynomial-size family of ordinary caterpillars...” This seems to be a layout issue but should be cleaned in final typesetting.
  • On page 2, “That preprint an-nounces” contains a visible hyphenation artifact inside the word “announces.”
  • On page 2, “caterpillar/degree-coloured-walk corre-spondence” is split awkwardly.
  • On page 3, equation formatting around “ΛG = Zn ⇐⇒ spanZ {w(A, D)e : |w| ≤ n − 1} = Zn” should be checked for visual balance and spacing; it reads more like an inline statement than a fully displayed proposition.
  • On page 8, the line “at most 6j=1 m Σ ( j ) = O(m6)” is typographically malformed in the extracted text and likely needs careful typesetting review in the source.
  • On page 9, the sentence beginning “Theorem S5.4 identifies the graph isomorphism classes with moments µG...” runs into a displayed condition and then a basis condition; the paragraph would benefit from clearer punctuation and perhaps itemization.
  • On page 10, “present construction reaches seven; in this construction” is slightly repetitive and could be tightened stylistically.
  1. Formatting issues
  • The manuscript relies heavily on appendices and supplementary sections embedded in the same PDF. The “Reading and proof guide” is useful, but the separation between main text, appendices, and supplementary proofs could be visually strengthened, especially because the first 10 numbered pages contain the main story while detailed proofs begin later.
  • Several long displayed formulas and multi-line inequalities appear dense in the current layout. Given the paper’s technical load, more proposition-level signposting would improve navigability.
  • Some page numbering seems internal rather than reader-friendly; since the user instruction asks for counted pages if numbering is irregular, I note that the document’s internal numbering and PDF pagination may diverge in later sections. The final version should ensure a stable citation scheme for referees.
  1. Clarity edits
  • The sentence “The proof follows the arithmetic obstruction rather than the list of prime estimates” is elegant but vague for non-specialists; consider replacing or expanding it with a plainer description.
  • “The local criterion applies on this single intersection event and eliminates every Smith factor simultaneously” is concise but may merit one extra sentence of intuition.
  • “Visible: 0% - 100%” appears in the extracted text at the end of one result snippet and looks like an artifact rather than manuscript content; this should be checked in the source or export.
  1. Reference and citation hygiene
  • Because many references are very recent preprints from 2025–2026, the bibliography should consistently distinguish published articles from arXiv manuscripts and ideally include version dates where relevant, as already done for at least one item.
  • The concentration of self-citations or near-neighbor citations in a rapidly developing line of work is understandable, but the manuscript would benefit from a brief neutral sentence clarifying the exact relationship among those papers.
  1. AI content analysis

Estimated percentage of AI-generated content: moderate, approximately 20%–35% of prose-level exposition, but not credibly inferable as a percentage of mathematical content. This estimate is driven primarily by the explicit disclosure rather than stylometry alone.

Highlighted AI-affected sections: the manuscript itself states that AI tools “materially affected the exposition and proofs in Sections 2–4, Appendices A and B, and Supplementary Sections S1–S3 and S8,” and that Codex also assisted with “Lean code for selected deterministic and probabilistic statements.” These are exactly the sections carrying much of the technical argument, including prime-wise saturation, computation, and supporting proof infrastructure. That does not imply incorrectness, but it raises the need for heightened human verification.

Assessed epistemic impact: moderate to high. Because the AI-assisted contribution extends into proof-heavy sections rather than just copyediting, the epistemic impact is not merely stylistic. The manuscript’s claims may still be valid, but the burden of explicit checking rises. The author’s statement “The author takes full responsibility for the paper” is necessary but not sufficient on its own; a stronger verification note would improve trust.

Recommendations

  1. Add a dedicated “Scope and Novelty” subsection in the introduction explicitly partitioning contributions into:

    • random integral saturation,
    • deterministic finite-word certification,
    • moment-fibre rigidity/reconstruction,
    • caterpillar identification consequences,
    • nonsaturated/index-two fibre analysis.
      This would make the contribution map much easier to evaluate.
  2. Add a short “What requires what?” roadmap before Section 4, clarifying which reconstruction statements depend on:

    • full saturation,
    • AD-fullness,
    • the integer-construction event,
    • local prime estimates.
      This would resolve an otherwise avoidable ambiguity in the current narrative.
  3. Expand discussion of quantitative sharpness:

    • explain whether polynomial failure probability is expected to be improvable,
    • identify which step loses the most,
    • state whether the exponent is believed to be non-optimal.
      The current one-line disclaimer is too brief for a headline theorem.
  4. Include an explicit reproducibility statement for the computational examples and certificates:

    • exact graph data for Examples S6.7 and S6.8,
    • scripts or pseudocode for determinant/Smith computations,
    • verification workflow for the stated gcd certificates.
  5. Expand the AI disclosure into a verification statement explaining:

    • which proof passages were independently checked by the author,
    • whether AI-generated code was rerun and audited,
    • whether any formal verification outputs are available.
      Given the wording “materially affected the exposition and proofs,” this is important for referee confidence.
  6. Improve accessibility by adding one intuition paragraph each for:

    • why adjacency alone fails integrally modulo 2,
    • why adding D removes generic obstructions,
    • why bounded-diameter caterpillars suffice for almost-everywhere identification.
  7. Perform a careful final copyedit for hyphenation, line-break artifacts, and dense formula typography, especially in the introduction, Section 4, and the supplementary transitions.

Overall, I judge the manuscript to be mathematically promising and potentially significant, but not yet fully ready in its current form. The main issues are not obvious logical incoherence; rather, they concern novelty articulation, dependency transparency, reproducibility, and the unusually consequential AI-assisted-proof disclosure.

Reviewer3 (AI review)

November 15, 2026

AI Review (reviewer3.com)

Overview

Random integral lattice saturation

Contribution

The author proves that the adjacency and degree operators of a random graph G(n, 1/2) generate the complete vertex integer lattice Z^n from the constant vector with high probability, eliminating arithmetic defects across all prime fields simultaneously.

Graph identification via caterpillars

Contribution

This study demonstrates that a fixed polynomial-sized family of unlabelled caterpillars with diameter at most seven and sublinear order identifies almost every graph up to isomorphism via homomorphism counts.

Moment fibre classification

Contribution

The paper provides an exact description of graph isomorphism classes sharing principal adjacency-degree moments using admissible unimodular overlattices, proving that index-two moment ambiguity is uniquely restricted to a four-vertex Godsil–McKay switch.

Comments (4)

1. Isomorphism count formula vs. asymptotic bound for caterpillars — Editorial

In Theorem 1.2 (page 3) and Corollary C.2 (page 22), the paper states that the family Fn\mathcal{F}_n of ordinary caterpillars with diameter at most seven and at most mn=⌈12nlog⁡n+6⌉m_n = \lceil 12\sqrt{n \log n} + 6 \rceil vertices "has O(n3(log⁡n)3)O(n^3(\log n)^3) isomorphism types." However, in Section 4 (page 10) and the proof of Corollary C.2 (page 23), the paper derives this bound by writing: "The number of caterpillar types of order at most mm and diameter at most seven is at most ∑j=16(mj)=O(m6)\sum_{j=1}^6 \binom{m}{j} = O(m^6). These observations give the quantitative bounds of Theorem 1.2." (On page 23, this is written ∑s=16(mns)=O(mn6)\sum_{s=1}^6 \binom{m_n}{s} = O(m_n^6), "as required.") Because mn=Θ(nlog⁡n)m_n = \Theta(\sqrt{n \log n}), the expression (mns)\binom{m_n}{s} for ss up to 66 is indeed O(mn6)=O(n3(log⁡n)3)O(m_n^6) = O(n^3(\log n)^3), so the formula and the stated O(n3(log⁡n)3)O(n^3(\log n)^3) bound are mathematically consistent; however, let us check if there is any contradiction. Wait—actually, let's check if there are any genuine contradictions in the manuscript.

2. Degree block preservation by Q in Remark C.1 requires justification — Major

Indeed, such an intertwiner Q maps each degree block of G to the corresponding block of H . A singleton degree vertex s therefore satisfies Qe s = e s ′ : orthogonality gives a sign, and Qe = e makes it positive. Suppose a set

In Remark C.1 and the proof of Corollary C.2, you state that any real orthogonal pointed AD intertwiner Q from G to H maps each degree block of G to the corresponding block of H, and therefore maps a singleton degree vertex s of G to e_{s'} in H. While Q D_G = D_H Q and Q e_G = e_H imply that D_G and D_H have the same eigenvalues on the cyclic module (which is all of R^n since G is AD-full), you should explicitly state that because G is AD-full on E_n, D_G and D_H are orthogonally similar via Q and thus have the exact same eigenvalue multiplicities, so a degree value of multiplicity 1 in G must also have multiplicity 1 in H, forcing Q e_s = \pm e_{s'}.

3. Unbounded number of operator and subspace choices when p > 3 — Minor

. In the second, every residue cell is nonempty on the balanced event; its nonzero columns show that all p eigenspaces E λ are nonzero. Hence k ≥ p , which also excludes k = 1 . Equation (S2.1) makes (S2.5) exponentially small.

In the proof of Theorem S2.1 for 1 <= t < T, you state that the number of choices of the induced matrix B (satisfying B^p = B), the matrix C, and the witness subspace H in F_p^k are bounded in terms of p and T. However, B is induced by the action of D_g on a t-dimensional D_g-invariant subspace W = \bigoplus_\lambda W_\lambda: in any coordinate block \lambda where 0 < t_\lambda < N_\lambda, W_\lambda is only a subspace of the coordinate space F_p^{N_\lambda}, so there are on the order of p^{t_\lambda(N_\lambda - t_\lambda)} choices of W_\lambda that are NOT determined by B (since B acts as the scalar \lambda on all of E_\lambda). In your counting step, you bound the number of matrices F for fixed g and B by p^{(k-1)(n/p + \epsilon n)}, which implicitly assumes the eigenspaces E_\lambda of B in F_p^k are fixed; while there are only O_{p,T}(1) choices of those eigenspaces in F_p^k, for p >= 5 the factor 2^n p^{-(k-1)(1 - 1/p - \epsilon)n} is NOT small when k = t (the case e \in W) if t is smaller than p, and the argument that k >= p when e \in W relies on every residue cell having a nonzero column in U, which fails because e = \sum_\lambda e_\lambda can lie in W = \bigoplus_\lambda W_\lambda with some W_\lambda = \langle e_\lambda \rangle and others equal to 0? No, if e \in W, since e has all ones on every cell, its projection onto every non-empty cell \lambda is e_\lambda \neq 0, so indeed dim W_\lambda >= 1 for all p cells and k = t >= p; please make this projection step explicit so the reader sees immediately why no E_\lambda can be zero.

4. Missing case of isotropic 1-dimensional subspaces in Lemma S2.4 — Minor

. The quadratic form factors through a nondegenerate space of dimension N − 2 j . At the relevant steps this dimension is at least two, and the elementary polynomial zero bound gives at most 2 p N − j − 1

In the proof of Lemma S2.4 (used in Section S2.2, and analogous to the symmetric-space bounds), when choosing j independent mutually orthogonal isotropic vectors in a nondegenerate symmetric space of dimension N - 2j, you state that at the relevant steps this dimension is at least two and the elementary polynomial zero bound gives at most 2 p^{N-j-1} choices. However, when N = 2r (so the radical R is a maximal totally isotropic subspace of dimension r = N/2), at the last step j = r - 1 we have N - 2j = 2, and a 2-dimensional nondegenerate quadratic space over F_p has at most 2 isotropic lines (hence at most 2(p-1) < 2p^{1} isotropic vectors, which is fine), whereas if N - 2j = 1 (which could only happen if r > N/2, impossible for a radical) it would fail; please explicitly note that r <= N/2 because R is totally isotropic in a nondegenerate space of dimension N, ensuring N - 2j >= 2 for all 0 <= j <= r - 1.

XSci (AI review)

November 15, 2026

Summary

The manuscript studies the integer lattice ΛG=Z⟨A,D⟩e\Lambda_G=\mathbb{Z}\langle A,D\rangle e generated from the all-ones vector by the adjacency matrix and the degree diagonal, and asks when it equals Zn\mathbb{Z}^n. The main theorem is that for G∼G(n,1/2)G\sim G(n,1/2), Pr⁡[ΛG≠Zn]≤n−3/20+o(1)\Pr[\Lambda_G\neq\mathbb{Z}^n]\leq n^{-3/20+o(1)}, so that ee generates cyclically in every characteristic at once. The proof has two halves: a construction (Theorem B.1) showing that words with at most two occurrences of AA already span a lattice containing ΔG3Zn\Delta_G^3\mathbb{Z}^n, where ΔG\Delta_G is the product of pairwise degree differences, which confines every bad prime to the degree width; and local estimates removing the prime two (S1.1), each fixed odd prime (S2.1), and a uniform interval of growing primes (S3.1). Two consequences are drawn: a fixed family of O(n3(log⁡n)3)O(n^3(\log n)^3) caterpillars of diameter at most seven and order at most ⌈12nlog⁡n+6⌉\lceil 12\sqrt{n\log n}+6\rceil identifies almost every graph among all finite simple graphs (Corollary C.2); and the principal-moment fibre of an AD-full graph is classified by graph-admissible unimodular overlattices, completely at index two (Theorems S5.4, S6.5).

Contribution and Significance

The real contribution is the short-word integer construction of Appendix B, not the list of local prime estimates. Two ideas carry it. First, instead of a union bound over infinitely many primes, the authors produce an explicit integer inclusion ΔG3Zn⊆ΛG[2]\Delta_G^3\mathbb{Z}^n\subseteq\Lambda_G^{[2]} on a single graph event, which settles every prime not dividing ΔG\Delta_G simultaneously and bounds the rest by wG≤n−1w_G\leq n-1. Second, the dependence between AA and D=diag(Ae)D=\mathrm{diag}(Ae) is handled by reversing the order of exposure (§2.2, Lemmas B.8 and B.9): integer surjectivity of A[C,SC]A[C,S_C] is proved uniformly over every eligible row set CC before the actual degree classes are substituted. That is the right way around an obstacle that has limited earlier work on walk lattices, and it is reusable.

Relative to the closest prior work the position is more delicate than the manuscript suggests. O'Rourke–Touri [OT16] give rational controllability and Van Werde [VW25] gives cokernel statistics for independent-entry walk matrices; neither addresses a two-operator lattice with DD determined by AA, and Theorem 1.1 is genuinely new. But the reconstruction payoff is weaker than claimed. §A.1 proves that AD-fullness forces the stable colour-refinement partition to be discrete, so colour refinement identifies every AD-full graph; with Babai–Erdős–Selkow [BES80] the rigidity of Corollary S4.5 is, as an identification statement, classical. What is new in Theorem 1.2 is the fixed, bounded-diameter, sublinear-order test family, which is of interest to the homomorphism-count literature ([DGR18], [Čer25]), and that should be the stated claim.

Strengths

  • The inclusion ΔG3Zn⊆ΛG[2]\Delta_G^3\mathbb{Z}^n\subseteq\Lambda_G^{[2]} (Theorem B.1, §B.4) does two jobs at once: it reduces an unbounded prime problem to a bounded one, and it supplies the short word basis Theorem 1.2 needs. The word tracking (DieD^ie, DiADjeD^iAD^je, DiADjADℓeD^iAD^jAD^\ell e, i,j,ℓ<qi,j,\ell<q) is exact.
  • The prime-two theorem (S1.1) works inside the actual degree-parity fibre rather than an independent-edge surrogate, with the conditional invariance codimension computed exactly via bivectors (Lemma S1.6); Remark S1.7 shows the εi(ni−ti−ri)\varepsilon_i(n_i-t_i-r_i) correction is genuinely needed at Wi=HiW_i=H_i.
  • Theorem 1.2 is matched by a lower bound: Proposition C.3 shows diameter four does not suffice, giving 5≤d∗≤75\leq d_*\leq 7 and turning a construction into a sharp question.
  • The index-two classification (Theorem S6.5) is complete and checkable: the three conjugation identities for QS=diag(12J4−I4,In−4)Q_S=\mathrm{diag}(\tfrac12J_4-I_4,I_{n-4}) are correct, and Examples S6.7 and S6.8 satisfy the stated congruences and combinatorial conditions on direct computation from their edge lists.

Recommendation

Major Revision for the leading journals of the field. I found no gap in a central claim: the estimates I checked in detail — Lemma S1.6's codimension, (S1.11)–(S1.14), (S2.2) and the exponent of §S2.2, Lemma S2.4, the arithmetic of §S3.3, Theorem S6.5 and the two examples — are correct, and the headline theorem is new. What the manuscript does not do is make the case for its own main theorem: by the authors' own Remark C.1, every advertised consequence follows from Appendix B alone, so the hardest half of the paper rests on an unargued claim of intrinsic interest. With the thin positioning against a contemporaneous result on the same reconstruction question, this needs substantive new text, not clarification.

Major Concerns

  1. The stated consequences do not use Theorem 1.1 (§4, "There is one further point in that argument…"; Remark C.1; proof of Corollary C.2). Remark C.1 states that an orthogonal pointed AD intertwiner from a graph in En\mathcal{E}_n is a permutation, using the cut conditions of Lemmas B.5–B.9 and "not merely that inclusion", and Corollary C.2's proof invokes Remark C.1 rather than the local-prime estimates. Sections S1–S3, the bulk of the technical work, therefore contribute only Corollaries S1.11 and S4.6, the exclusion of pointed AD intertwiners of even or pp-divisible level; and Remark S1.12 itself notes that the absence of four-vertex switching sets in G(n,1/2)G(n,1/2) already follows from the union bound (n4)2−(n−4)\binom{n}{4}2^{-(n-4)}. The authors should state explicitly what integral saturation buys that ΔG3Zn⊆ΛG\Delta_G^3\mathbb{Z}^n\subseteq\Lambda_G does not — ideally a rigidity or algorithmic statement that fails under the weaker inclusion — or say plainly in the introduction that §4 rests on Appendix B. As written, the significance of the headline claim is asserted rather than established.

  2. Positioning against [Xia26] and against classical identification (§1, "Related work"; §A.1). Xiang's preprint, cited as announcing determination of almost all graphs by their generalized spectrum, receives one sentence ("Our proof is independent, and generalized cospectrality does not require intertwining DD"), which leaves the reader unable to place the contribution. The two data sets are in fact incomparable — the principal AD moments contain every e⊤Akee^\top A^ke but not tr(Ak)\mathrm{tr}(A^k), while the generalized spectrum contains the traces but no degree-weighted walk counts — so neither theorem implies the other, and this should be said. The same applies to §A.1: since AD-fullness already forces colour refinement to be discrete, the novelty of Theorem 1.2 lies entirely in the parameters of the test family, and the introduction should make that the claim rather than "identifies almost every graph".

  3. Delineation from the companion preprints [LL26] and [Lu26] (§4; opening of Appendix C; Appendix A). The caterpillar dictionary (C.1) and the Gram-matrix reconstruction are described as "established ingredients" of [LL26], yet Theorem A.8 and Proposition A.7 are proved here in full, and [Lu26] is cited for "uniform probes for real cyclic modules" without a statement of what it supplies. Since both are by the same author and develop the same framework, the manuscript must say precisely which results of Appendix A and §C are quoted and which are new, and what Theorem 1.1 adds to [LL26]'s deterministic theory.

Minor Comments

  1. §2.2 states "Hadamard gives ∣b∣≤kh/2|b|\leq k^{h/2}" where the proof of Lemma B.2 has kk/2k^{k/2}, which is what the subsequent prime count uses; Lemma 2.1 also calls BB an "a×ma\times m matrix" while concluding about Zk\mathbb{Z}^k.
  2. §4 gives "q≤2nlog⁡n+1q\leq 2\sqrt{n}\log n+1" whereas Corollary C.2 gives q≤2nlog⁡n+1q\leq 2\sqrt{n\log n}+1; only the latter yields 6q≤mn6q\leq m_n and follows from the quoted bound 2/n2/n, and the abstract's "order O(nlog⁡n)O(\sqrt{n}\log n)" should be replaced by the sharper bound proved.
  3. In Proposition C.3 the interval InI_n has radius nlog⁡n\sqrt{n}\log n, giving b=Θ(nlog⁡n)b=\Theta(\sqrt{n}\log n) and a profile count 2Θ(n3/2(log⁡n)4)2^{\Theta(n^{3/2}(\log n)^4)} rather than the stated 2O(n3/2(log⁡n)5/2)2^{O(n^{3/2}(\log n)^{5/2})}, which corresponds to radius nlog⁡n\sqrt{n\log n}; the conclusion 2o(n2)2^{o(n^2)} is unaffected.
  4. §3.1 speaks of an "invisible invariant subspace", "graded invisible spaces" and "invisible subspaces" without defining the term; Lemma S1.3 uses only "invariant".
  5. In §3.3 and in the application of Lemma S3.4 the count is displayed as pbptp^{b_p^t} where pbptp^{b_pt} is meant, as the exponent arithmetic that follows confirms.
  6. Theorem S2.1 and its restatement in §3.2 display the probability of a common invariant subspace without naming the field; "over Fp\mathbb{F}_p" belongs in the statement.
  7. Lemma S2.2 bounds the failure of degree balance only by Op(n−1)O_p(n^{-1}), so within the present argument the failure probability cannot be pushed below Θ(1/n)\Theta(1/n) however the thresholds (B.1) are optimized; §S7's discussion of the exponent 3/203/20 should say this.
  8. Only density 1/21/2 is treated, and it would help to say which steps survive for constant ρ≠1/2\rho\neq1/2 (Lemma B.3's local exponents, Lemma S2.2's Fourier bound, Lemma S3.3's atom bound) and which do not.
  9. The AI disclosure states that the tools "materially affected … proofs" in exactly the sections carrying Theorem 1.1 and that Lean code was developed for "selected" statements; please list which statements were formally verified and release that code and the §S9 certificates.
  10. The proofs of Theorems S1.1, S2.1 and S3.1 are essential to Theorem 1.1 but sit in matter labelled "Supplementary proofs"; for journal publication they belong in the paper proper.
  11. "Ordinary caterpillar" is used in the abstract and Theorem 1.2 before C(a0,…,ak)C(a_0,\ldots,a_k) is defined in Appendix C.
  12. Several displays did not render in the copy I received — the binomial-tail comparison in the proof of Lemma B.2, the word list in the proof of Corollary C.2, and two appendix headings — so please check the typesetting of the submitted file.