Pith. sign in

REVIEW 6 major objections 6 minor 14 references

Sharp Square Root Bounds for Edge Eigenvector Universality in Sparse Random Regular Graphs

T0 review · 6 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random regular graph eigenvector projections are Gaussian to error O(sqrt(d) N^{-1/6+eps}), and this rate is optimal.

desk verdict The new sqrt(d) theorem statements are plausible but the proof's local law is circular and arithmetically wrong; desk reject. read the letter →

arxiv 2507.14259 v1 pith:CQWGNN5C submitted 2025-07-18 math.PR cs.DMmath-phmath.COmath.MPmath.SP

Leonhard Nagel This is my paper · ORCID
classification math.PRcs.DMmath-phmath.COmath.MPmath.SP MSC 05C8060B2060F05
keywords randomregulargraphseigenvectoruniversalityBerry-Esseenboundedgelocallawresolventconcentrationsparsematricesdegreedependencefourthcumulant
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper studies the second eigenvector $u_2$ of the normalized adjacency matrix of a uniformly random $d(N)$-regular graph on $N$ vertices, with degree growing no faster than $N^\kappa$, $\kappa<1/4$. It claims that for every deterministic unit vector $q$ orthogonal to the all-ones vector, the projection $\sqrt{N}\langle q,u_2\rangle$ is approximately Gaussian, with a Berry-Esseen error at most $C_\kappa \sqrt{d}\,N^{-1/6+\varepsilon}$. Previous bounds carried a factor $d^3$, so this would place the sparse-to-moderately-dense regime in the same $N^{-1/6}$ universality class as fixed degree, with only a square-root dependence on the degree. The paper also states a matching lower bound, asserting that no smaller degree-dependent prefactor is possible.

What carries the argument

The argument rests on a sharp edge local law for the resolvent $G(z)=(\tilde H-z)^{-1}$: for $z$ in the edge window, $\langle q,G(z)q\rangle$ is within $O(\sqrt{d}\,N^{-5/6+\varepsilon})$ of the Stieltjes transform $m_{\rm sc}(z)=(-z+\sqrt{z^2-4})/2$ of the semicircle law. The mechanisms are refined martingale concentration for the configuration model, a vector-outlier resolvent equation $v=-q/(z+m(z))+R$ with a small remainder, and a variance-normalization step in the cumulant computation that cancels the apparent factor of $d$. The interpolation parameter $s(t)=\sqrt{dt/N}$ balances the graph-structure error against the error from a Gaussian (GOE) evolution, producing the claimed $O(\sqrt d\,N^{-5/6+\varepsilon})$ bound.

What would settle it

Simulate random $d$-regular graphs with $d=N^{0.2}$ and $N$ around $10^5$, choosing $q$ with $d$ equal nonzero coordinates, and measure the sup-norm distance between the empirical distribution of $\sqrt{N}\langle q,u_2\rangle$ and $\Phi$. If the distance grows faster than $\sqrt{d}\,N^{-1/6+\varepsilon}$, or if the fourth cumulant of the overlap does not stay bounded below by a constant times $\sqrt{d}\,N^{-1/6}$, the claimed sharp rate is wrong.

Watch

Extended reading notes

Core claim

The core claim is Theorem 1: for $3\le d(N)\le N^\kappa$ with $\kappa<1/4$, any deterministic unit $q\perp e$ satisfies $\sup_x |\mathbb{P}(\sqrt{N}\langle q,u_2\rangle \le x)-\Phi(x)|\le C_\kappa\sqrt{d}\,N^{-1/6+\varepsilon}$. Theorem 2 asserts the matching lower bound $\sup_{q\perp e,\|q\|=1}\sup_x |\cdots|\ge c\sqrt{d}\,N^{-1/6}$ once $d\ge C\log N$. Together the two theorems identify $\sqrt{d}\,N^{-1/6}$ as the sharp scaling of edge eigenvector universality, meaning the $N^{-1/6}$ fluctuation rate of the edge survives degree growth and the degree enters only through its square root.

Load-bearing premise

Near the spectral edge, the proof's self-consistency step assumes that the deterministic approximation to the resolvent is already accurate to the error $O(\sqrt{d}\,N^{-5/6+\varepsilon})$ that the local law is supposed to prove; if that accuracy is not established independently, the bound does not follow.

Editorial extensions

If this is right

  • The edge local law gives uniform resolvent concentration in the window $|E-2|\le N^{-2/3+\varepsilon}$, so other edge statistics of random regular graphs inherit the same $\sqrt{d}$ error.
  • The previous $d^3$ dependence for eigenvector projections is replaced by $\sqrt{d}$, extending quantitative eigenvector universality to degrees as large as $N^{1/4}$.
  • The matching lower bound implies the $\sqrt{d}$ prefactor is unavoidable for any Gaussian approximation at this scale, not an artifact of the proof.

Reading between the lines

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

  • Because the concentration lemma is stated for general resolvent entries, the same variance-sensitive argument would likely improve degree dependence for bulk eigenvector fluctuations, not just the edge second eigenvector.
  • The lower-bound construction singles out vectors $q$ supported on $d$ equal-size coordinates; a direct numerical check of the fourth cumulant for such $q$ should show the predicted $\approx c/(d N^{1/3})$ scaling and would test the mechanism independently of the full theorem.
  • The paper conjectures a new universality class near $d=N^{1/2+o(1)}$ with error $O(d N^{-2/3})$; if correct, simulations across that degree range should exhibit a crossover from $\sqrt{d}N^{-1/6}$ to $dN^{-2/3}$ scaling.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

6 major / 6 minor

Summary. The paper proposes to prove that for uniformly random d(N)-regular graphs with d(N) <= N^kappa and kappa < 1/4, the projection sqrt(N)<q,u_2> of the second eigenvector onto any deterministic unit vector q orthogonal to the all-ones vector has Berry-Esseen error O(sqrt(d) N^{-1/6+epsilon}) (Theorem 1), and that this rate is optimal (Theorem 2). The proof is organized around an edge local law for the resolvent (Theorem 3), a self-consistent comparison with a constrained, time-evolved GOE (Sections 3-4), a Stein-Malliavin cumulant analysis, and a fourth-cumulant lower bound. The declared aim is to improve on prior d^3 bounds and to give the sharp degree dependence across the sparse-to-moderately-dense transition.

Significance. If valid, the sqrt(d) Berry-Esseen bound would be a substantial quantitative advance: it would identify the correct degree dependence at the spectral edge and would combine a nontrivial local-law rate with a matching lower bound in the regime d <= N^{1/4-epsilon}. The proposed strategy of exploiting the variance structure via vector resolvent equations and Stein-Malliavin machinery is conceptually appealing, and the paper identifies a natural scaling heuristic. However, the written proof contains multiple load-bearing gaps: a circular local-law argument, arithmetic failures in the concentration and cumulant estimates, an invalid comparison step, and an incorrect lower-bound computation. The main theorems are therefore not established by this manuscript. I regard the central claim as plausible, but the current derivation is not sufficiently sound for publication.

major comments (6)
  1. [§2.3, proof of Theorem 3] The proof states 'Near the edge, m(z) approximately equals msc(z) + O(sqrt(d) N^{-5/6+epsilon}) by self-consistency' and then uses this to conclude |<q,G(z)q> - msc(z)| <= C sqrt(d)/N^{5/6-epsilon}. This is circular: the preceding propositions establish at most a vector equation with an uncontrolled remainder, not the target m(z)-to-msc(z) bound. Since Theorem 3 is the only local-law input used in Sections 3-5, the main results rest on an unproved assumption.
  2. [§2.3, Proposition 1 and remainder estimate] Even if Proposition 1's remainder bound ||R||_2 <= C sqrt(d)/(N eta) is granted, the displayed conclusion of Theorem 3 fails at the allowed endpoint. For eta = N^{-2/3}, C sqrt(d)/(N eta) = C sqrt(d)/N^{1/3}, whereas the claimed error is C sqrt(d)/N^{5/6-epsilon}. The two differ by a factor N^{1/2}, and no additional power of eta appears in the text to repair this. Thus the edge local law is not established even conditionally on Proposition 1.
  3. [Lemma 1] The variance proxy and Lipschitz bound in Lemma 1 are arithmetically inconsistent. The proof obtains V <= C N/eta^4 and L = O(1/(sqrt(d) eta^2)); at the edge value eta = N^{-2/3} these are C N^{11/3} and N^{4/3}/sqrt(d), not the claimed O(d/N) and O(sqrt(d/N)). The sentence 'this gives V = O(d/N)' is false. Since Lemma 1 is the concentration input for the subsequent remainder estimates, the variance-sensitive concentration part of the argument is unsupported.
  4. [§3.1-3.2, Lemma 3 and Theorem 4] Lemma 3(iii) contains a missing sqrt(N) factor, and the chosen time scale does not close the comparison. From part (ii), Cauchy-Schwarz gives E||partial_s G_{t,s}||_HS <= eta^{-2} sqrt(N E||Delta_t||_op^2) = eta^{-2} sqrt(N d t + d^2), not eta^{-2} sqrt(d t + d^2/N). With t* = N^{-1/3+epsilon}, the term N d t equals d N^{2/3}, which is not bounded by d^2/N for the stated degree range (for example, d=N^{1/4} gives d N^{2/3}=N^{11/12}, while d^2/N=N^{-1/2}). Additionally, the evaluation of the minimum in Theorem 4 is incorrect: substituting s(t)=sqrt(d t/N) into (4) gives approximately C d/N + C sqrt(d) N^{-4/3+2 epsilon}, not C sqrt(d)/N^{5/6-epsilon}.
  5. [Propositions 4 and 6] The second cumulant bound is arithmetically invalid. The proof obtains ||D X||^2 = O(d^2/N) and multiplies by ||L^{-1}|| = O(N^{2/3-epsilon}), yielding O(d^2 N^{-1/3-epsilon}); this can equal O(d N^{-1/3+epsilon}) only if d = O(N^epsilon), not if d <= N^{1/4}. Moreover, the 'cancellation' in Proposition 6 is a non sequitur: dividing by sigma^2 = 1 + O(d^{-1}) multiplies by a factor of the form 1 + O(d^{-1}), which cannot remove a factor of d from the numerator. The stated conclusion of Proposition 6 should remain O(d N^{-1/3+epsilon}).
  6. [Lemma 5 and §5.2] The lower-bound computation does not produce the claimed scaling. The displayed expansion leads to |kappa_4| approximately 4|c_2|/(d N^{1/3}), which is smaller than c sqrt(d) N^{-1/6} by a factor (sqrt(d) N^{1/6})^{-1}. The subsequent sentence '1/(sqrt(d) N^{1/6}) ... which is bounded below' reverses the direction of the inequality, since sqrt(C log N) N^{1/6} tends to infinity. In addition, the claim that c_2 = E[g_1^3 eta_1] != 0 is asserted without computation. Theorem 2 is therefore not established by the written proof.
minor comments (6)
  1. [Title] The title contains a typo: 'SP ARSE' should read 'SPARSE'.
  2. [§2.2] The subsection titled 'Proof of Theorem 1' actually gives a heuristic derivation of Proposition 1; Proposition 1 itself is not formally proved, and the local GOE coupling used there is not rigorously specified.
  3. [§5.1, Step 2] The stochastic differential equation for X_i^{(q)} is introduced without derivation, without a precise definition of the Brownian motions B_{ij}, and without a justification of the error term E_i(t); these objects need to be defined for the argument to be checkable.
  4. [§5.2 and references [2], [5]] The 'quantitative Berry-Esseen lower bound' cited to [2] and [5] is not a standard result in those references and is not stated or proved in the paper; if it is a new lemma, it must be proved.
  5. [References [4], [6]] The bound ||L^{-1}|| = O(N^{2/3-epsilon}) on the complement of constants is cited to [4] and [6], but those references concern different operators and settings; the paper should state precisely which theorem applies to the switching operator on regular graphs and why.
  6. [§3.2, Theorem 4] The arithmetic in equations (4)-(5) is incorrect, although the resulting bound C d/N is actually at least as strong as C sqrt(d)/N^{5/6-epsilon} for d <= N^{1/3}; this should be corrected locally.

Circularity Check

2 steps flagged · score 8.0 of 10

The edge local law is assumed, not proved: Theorem 3's self-consistency step asserts the target error, and the lower bound proof injects the same non-Gaussian correction it is supposed to establish.

  1. self definitional [Section 2.3, Bootstrap-Free Analysis, proof of Theorem 3]
    "Near the edge, m(z) approximately equals msc(z) + O(sqrt(d) N^{-5/6+epsilon}) by self-consistency. The error term satisfies: |<q,R>| <= ||R||_2 <= C sqrt(d)/(N eta) <= C sqrt(d)/N^{5/6-epsilon}. This directly gives the claimed bound without iteration."

    Theorem 3 claims exactly |<q,G(z)q> - msc(z)| <= C0 sqrt(d)/N^{5/6-epsilon}. The proof reduces the resolvent to -1/(z+m(z)) plus a remainder R and then asserts m(z) is already within the target distance of msc(z) by self-consistency. No prior proposition establishes this closeness; Proposition 1 gives only a vector resolvent representation with a remainder bound. The asserted error is the theorem's conclusion, used as a premise. Moreover, the displayed remainder inequality is arithmetically false at the allowed endpoint eta=N^{-2/3}: C sqrt(d)/(N eta) = C sqrt(d) N^{-1/3}, not C sqrt(d)/N^{5/6-epsilon}. Thus the central local law is assumed in the form needed.

  2. other [Section 5.2, proof of Lemma 5 and Theorem 2]
    "By the optimal eigenvector local law established in Section 2, each eigenvector component admits the decomposition: u_{2k} = g_k/sqrt(N) + eta_k/N^{5/6} where g_k ~ N(0, 1) are independent Gaussian variables and eta_k are correction terms with |eta_k| <= C."

    The lower bound proof needs a nonzero non-Gaussian fourth cumulant. It obtains this from c_2 * sum q_k^4, with c_2 = E[g_1^3 eta_1], and the paper asserts this expectation is nonzero because the correction terms eta_k are correlated with the Gaussian components g_k through the eigenvector equation. That is exactly the non-Gaussian correction the theorem is meant to establish, asserted rather than computed. The invoked optimal eigenvector local law is Theorem 3, whose proof already assumed its target error. So the matching lower bound inherits the circularity: the non-Gaussian fluctuation being proved is inserted at the start.

full rationale

The load-bearing point is Section 2.3. Theorem 3 is the only edge local law used as input by the self-consistent comparison (Section 3), the Stein-Malliavin cumulant argument (Section 4), and the final proofs (Section 5). Its proof explicitly asserts the target error by self-consistency without deriving it, so the central claim reduces to itself by definition. Even if that circular assertion were granted, the subsequent remainder estimate does not close: at eta = N^{-2/3}, C sqrt(d)/(N eta) = C sqrt(d) N^{-1/3}, larger than the claimed C sqrt(d)/N^{5/6-epsilon} by a factor of N^{1/2}. The lower bound proof repeats the pattern by assuming a Gaussian-plus-correction decomposition with an asserted nonzero correlation c_2, feeding the non-Gaussianity it is supposed to prove. The self-citation [12] is not load-bearing: it is background, not a substitute for the missing local-law proof. The circularity is therefore central, not a citation-practice issue.

Assumptions & free parameters 3 free parameters · 5 assumptions · 3 invented entities

The central proof rests on several unsupported or circular premises: the local law error is assumed in its own proof, the admissible norm of L^{-1} is asserted without proof, and the GOE interpolation and eigenvector decomposition are domain assumptions that are not derived. The chosen scaling parameters t* and s(t) are tuned to produce the target error.

free parameters (3)
  • evolution time t* = N^{-1/3+epsilon}
    Chosen in Remark 2 to balance GOE evolution dt against constraint mismatch d^2/N so that the error becomes sqrt(d) N^{-5/6-epsilon}; this tuning drives the main bound.
  • interpolation slope s(t) = sqrt(dt/N)
    Chosen via minimization in Theorem 4 to make E1 and E2 balance; not derived from first principles.
  • regularization exponent epsilon = arbitrary positive
    Small positive number in the error N^{-1/6+epsilon}; standard for absorbing logarithmic factors, but the proof needs it to hide several unproved losses.
assumptions (5)
  • ad hoc to paper m(z) satisfies m(z) = msc(z) + O(sqrt(d) N^{-5/6+epsilon}) by self-consistency
    Invoked in proof of Theorem 3 (Section 2.3) to obtain the local law; this is the target error itself, making the step circular.
  • ad hoc to paper The switching-space OU operator L satisfies ||L^{-1}|| = O(N^{2/3-epsilon}) on the complement of constants
    Stated in Proposition 4 and attributed to [4] and [6]; neither source contains this bound, and no derivation is given.
  • domain assumption Under GOE interpolation at t = d^{-1/2}, edge spectral statistics are approximately preserved
    Used in Section 2.2 to justify isotropy via local GOE approximation; cited to [8] but not proved in this paper.
  • ad hoc to paper Quantitative Berry-Esseen lower bound sup|P(Y<=x)-Phi(x)| >= c |kappa4(Y)| / (1+E|Y|^3)^2
    Used in Section 5.2 to convert the fourth cumulant lower bound into a Kolmogorov distance lower bound; this inequality is not standard and is not established in the cited references.
  • domain assumption Eigenvector components decompose as u_{2k} = g_k/sqrt(N) + eta_k/N^{5/6} with independent N(0,1) g_k
    Assumed in Lemma 5 for the lower bound; the independence and size of eta_k are not proved.
invented entities (3)
  • Malliavin derivative on the switching graph
    purpose: Used to compute cumulants of eigenvector overlaps via integration by parts
    Definition 2 introduces a derivative on the space of switchings; no external verification, and the integration by parts Lemma 4 is asserted without proof.
  • Discrete Ornstein-Uhlenbeck operator L on switchings
    purpose: Defines the Malliavin representation and bounds cumulant norm
    The key norm bound on L^{-1} is unsupported.
  • Constrained GOE ensemble H_GOE_t
    purpose: Interpolation dynamics comparing regular graph to Gaussian ensemble
    Standard Dyson Brownian motion but the 'constraint mismatch' term and its d^2/N bound in Lemma 3(ii) are asserted without detailed proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sharp Square Root Bounds for Edge Eigenvector Universality in Sparse Random Regular Graphs." pith.science (2026). https://pith.science/paper/CQWGNN5C

@misc{pith2026250714259,
  author       = {Pith},
  title        = {Pith review of: Sharp Square Root Bounds for Edge Eigenvector Universality in Sparse Random Regular Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQWGNN5C}},
  note         = {Machine review of arXiv:2507.14259}
}
abstract

We study how eigenvectors of random regular graphs behave when projected onto fixed directions. For a random $d$-regular graph with $N$ vertices, where the degree $d$ grows slowly with $N$, we prove that these projections follow approximately normal distributions. Our main result establishes a Berry-Esseen bound showing convergence to the Gaussian with error $O(\sqrt{d} \cdot N^{-1/6+\varepsilon})$ for degrees $d \leq N^{1/4}$. This bound significantly improves upon previous results that had error terms scaling as $d^3$, and we prove our $\sqrt{d}$ scaling is optimal by establishing a matching lower bound. Our proof combines three techniques: (1) refined concentration inequalities that exploit the specific variance structure of regular graphs, (2) a vector-based analysis of the resolvent that avoids iterative procedures, and (3) a framework combining Stein's method with graph-theoretic tools to control higher-order fluctuations. These results provide sharp constants for eigenvector universality in the transition from sparse to moderately dense graphs.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 13 canonical work pages

  1. [1]

    Bourgade, P., Huang, J., Yau, H.-T.: Eigenvector statistics of sparse random matrices. Ann. Inst. H. Poincar´ e Probab. Statist.55, (2019), 1358–1440. MR 3690289

    work page 2019

  2. [2]

    Bentkus, V.: On the dependence of the Berry-Esseen bound on dimension. J. Statist. Plann. Inference 113, (2003), 385–402. MR 1965117

    work page 2003

  3. [3]

    European J

    Bollob´ as, B.: A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1, (1980), 311–316. MR 0595929

    work page 1980

  4. [4]

    M., and Richthammer, T.: Proof of Aldous’ spectral gap conjecture

    Caputo, P., Liggett, T. M., and Richthammer, T.: Proof of Aldous’ spectral gap conjecture. J. Amer. Math. Soc. 23, (2010), 831–851. MR 2629990

    work page 2010

  5. [5]

    Chen, L. H. Y., Goldstein, L., and Shao, Q.-M.: Normal approximation by Stein’s method. Probability and its Applications (New York) . Springer, Heidelberg, 2011. xii+405 pp. MR 2732624

    work page 2011

  6. [6]

    and Yau, H.-T.: A dynamical approach to random matrix theory

    Erd˝ os, L. and Yau, H.-T.: A dynamical approach to random matrix theory. Courant Lecture Notes in Mathematics , 28. Courant Institute of Mathematical Sciences, New York, 2017. ix+226 pp. MR 3699468

    work page 2017

  7. [7]

    A.: On tail probabilities for martingales

    Freedman, D. A.: On tail probabilities for martingales. Ann. Probability 3, (1975), 100–118. MR 0380971

    work page 1975

  8. [8]

    Friedman, J.: A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc. 195, no. 910, (2008), viii+100 pp. MR 2437174

    work page 2008

Show all 14 references
  1. [9]

    A., Bourgade, P.: Extreme gaps between eigenvalues of random matrices

    G´ erard, B. A., Bourgade, P.: Extreme gaps between eigenvalues of random matrices. Ann. Probab. 51, (2023), 1484–1533. MR 3112927 SHARP BOUNDS FOR EDGE EIGENVECTOR UNIVERSALITY 13

    2023

  2. [10]

    and Yau, H.-T.: Edge universality of sparse random matrices

    Huang, J. and Yau, H.-T.: Edge universality of sparse random matrices. Preprint, arXiv:2206.06580

    arXiv

  3. [11]

    In Probabilistic methods for algorithmic discrete mathemat- ics, 195–248, Algorithms Combin., 16, Springer, Berlin, 1998

    McDiarmid, C.: Concentration. In Probabilistic methods for algorithmic discrete mathemat- ics, 195–248, Algorithms Combin., 16, Springer, Berlin, 1998. MR 1678578

    1998

  4. [12]

    Preprint, arXiv:2507.12502

    Nagel, L.: Quantitative edge eigenvector universality for random regular graphs. Preprint, arXiv:2507.12502

    arXiv

  5. [13]

    In Proceedings of the Sixth Berkeley Symposium on Math- ematical Statistics and Probability , Vol

    Stein, C.: A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. In Proceedings of the Sixth Berkeley Symposium on Math- ematical Statistics and Probability , Vol. II, 583–602, Univ. California Press, Berkeley, 1972. MR 0402873

    1972

  6. [14]

    Tracy, C. A. and Widom, H.: On orthogonal and symplectic matrix ensembles. Comm. Math. Phys. 177, (1996), 727–754. MR 1385083 Department of Electrical Engineering and Computer Sciences, University of Cali- fornia, Berkeley, United States of America Email address : nagel@berkeley.edu

    1996

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.