Microscopic spectra of random regular graphs

Source and verification

This article explains family 219 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

A sparse regular graph has only a fixed number of neighbors per vertex, yet its microscopic bulk eigenvalue statistics are predicted to match a dense Gaussian matrix. Family 219 claims this for every fixed degree at least three, and then for sufficiently weak diagonal disorder that remains fixed as the graph grows.

🏷️ Preliminaries: global density versus local statistics

Let $G_{n,d}$ be a uniformly chosen simple labelled $d$-regular graph, for fixed $d\ge 3$, and let $A_{n,d}$ be its adjacency matrix. Sizes are admissible when such a graph exists. Its empirical eigenvalue measure is $n^{-1}{\sum }_i{\delta }_{{\lambda }_i}$.

The limiting bulk density is the Kesten–McKay density

$$\begin{array}{c}{\rho }_d(E)=\frac{d\sqrt{4(d-1)-E^2}}{2\pi (d^2-E^2)},\\ |E|<2\sqrt{d-1}.\end{array}$$

This measures eigenvalue counts in macroscopic intervals. It does not determine the spacings in an interval containing only order-one eigenvalues. At an interior energy $E$, the typical spacing is $1/(n{\rho }_d(E))$, motivating the unfolded point measure

$${\Xi }_{n,E}=\sum _i{\delta }_{n{\rho }_d(E)({\lambda }_i-E)}.$$

The Gaussian orthogonal ensemble (GOE) is a real symmetric matrix with independent centered upper-triangular entries, variance $1/n$ off the diagonal and $2/n$ on it. Its microscopic bulk limit is a point process with characteristic level repulsion.

🏷️ What the two papers claim

Fixed-energy bulk limits

For every fixed $d\ge 3$ and each fixed energy in the open Kesten–McKay bulk, the clean companion claims convergence of ${\Xi }_{n,E}$ to the GOE bulk process through all admissible sizes, without conditioning on connectedness or other graph properties. (OpenAI, 2026)

For the operator $A_{n,d}+w\mathrm{diag}({\omega }_v)$ with independent uniform potentials, the disorder companion claims the same limit on compact subintervals of the clean bulk when $w>0$ is sufficiently small and fixed. The unfolding uses the positive density ${\rho }_{d,w}(E)$ of the corresponding infinite-tree random operator. (OpenAI, 2026a)

The permitted disorder depends on the degree and the distance to the clean edges. This is a bulk statement, not an assertion at all energies or arbitrary disorder strengths. For the disordered model, retaining the clean density in the unfolding would generally give the wrong intensity.

🏷️ How to test an entire point process

For each nonnegative continuous compactly supported $h$, consider the Laplace functional

$$\mathbb{E}\exp \left(-\int hd{\Xi }_{n,E}\right).$$

The manuscripts identify its limit with the GOE value. Such tests jointly encode local counts and their dependence, going beyond the mean density or a single nearest-neighbor spacing statistic. Taking $h$ close to a constant times an interval indicator probes the distribution of the number of eigenvalues in that interval.

The word fixed-energy also matters. Averaging this functional over a macroscopic energy interval could conceal behavior at the particular energy one wanted to understand.

🏷️ Tree resolvents and why the disorder remains visible

A regular graph is locally tree-like. Removing an edge on the infinite tree separates branches, and the cavity Green function satisfies a recursion of the schematic form

$$\begin{array}{rl}{G}_{v\to u}(z{)}^{-1}& =w{\omega }_v-z\\ & -\sum _{x\sim v,x\ne u}{G}_{x\to v}(z).\end{array}$$

This follows by taking a Schur complement of the branch operator. The convention here is $(H-z{)}^{-1}$, with $\mathrm{Im}z>0$. In the disordered model the recursion has a random solution; replacing it by its average loses local information.

The manuscript first proves quantitative stability of this recursion in the weak-disorder bulk. Edge switches, spectral averaging, and resolvent identities transfer the tree description to finite graphs. The local law is distributional: the environment remains part of the limiting object.

🏷️ From eigenvector marks to GOE statistics

The clean proof samples eigenvector coordinates at endpoints of graph edges. With eigenvectors normalized to squared norm $n$, the proposed comparison coordinates are centered unit-variance Gaussian pairs with covariance $E/d$. An entropy inequality from local graph counting, followed by a rigidity estimate, supplies quantitative Gaussian moments.

For disorder, the Gaussian covariance is instead determined conditionally by the tree Green function. Even its variance at a root is random, proportional to $\mathrm{Im}{G}_o(E+i0)/{\rho }_{d,w}(E)$. Conditioning correctly is necessary before any averaging.

The remaining argument converts discrete edge-switch symmetries into continuous identities for subsequential microscopic limits. Many small switches implement an effective Gaussian insertion. Fixed-energy Dyson Brownian motion comparison then identifies the eigenvalue law. Local resolvent control, Gaussian eigenvector marks, and microscopic point-process identification are three separate stages; local tree convergence alone proves none of the last stage.

🏷️ Key steps and proof outlines

The proof must connect three scales: local tree geometry, sampled eigenvector coordinates, and eigenvalue spacings of order $1/n$. The following gives the main interfaces and the arguments that make those interfaces useful.

Graph counting creates an entropy inequality

Quantize a vertex labeling into $M$ colors. Let $T$ be the distribution of a uniformly sampled ordered star (a vertex and its neighbors), and $Q$ the distribution of an oriented edge. In the configuration model, fix the colors and the desired neighbor colors at every vertex. If $m_{jk}=nd{Q}_{jk}$ is the number of half-edges requesting the ordered color pair $(j,k)$, a compatible pairing requires $m_{jk}=m_{kj}$ and even $m_{jj}$. Its probability is

$$\frac{{\prod }_{j<k}{m}_{jk}!{\prod }_j(m_{jj}-1)!!}{(nd-1)!!}.$$

Stirling’s formula gives logarithm $-ndH(Q)/2+O(M^2\log n)$. The number of prescribed star arrays is at most $e^{nH(T)}$. If $M^{d+1}\log n$ is sublinear by a fixed power, the number of histograms can be absorbed in the error. Markov’s inequality and a union bound therefore control every labeling simultaneously. Conditioning on simplicity preserves the high-probability conclusion because its probability stays bounded below for fixed degree.

Apply this count to quantized eigenvector labels plus a Gaussian field with covariance proportional to

$$\frac{\eta }{(A-E{)}^2+{\eta }^2}.$$

After dequantization, the count becomes a star–edge differential-entropy inequality. The eigenvalue equation removes one nearly deterministic star coordinate. The source then expands the entropy deficit in Hermite tensors, the Gaussian-orthogonal polynomial coefficients of the whitened labels. A coercive quadratic inequality, subject to the edge-swap symmetries, makes each fixed-order non-Gaussian tensor polynomially small by induction. This yields Gaussian moments at sampled endpoints uniformly over graph-measurable choices of eigenindices in the allowed window. The uniformity comes from counting all labelings first, not from a union bound over an uncontrolled list of eigenvectors (OpenAI, 2026b).

Disorder changes the Gaussian reference covariance

For a disordered tree, write the incoming cavity values as $g_i=c_i+i{b}_i$ with $b_i>0$, and let $V_o$ be the root potential. The Gaussian reference on a star satisfies the constraint

$$(V_o-E)Z+\sum _{i=1}^d{X}_i=0.$$

Its precision quadratic form on that constraint space is

$$\sum _{i=1}^d\frac{|X_i+g_{i}Z{|}^2}{b_i}.$$

To verify it, begin with independent real Gaussians of variances $b_i$ and a root Gaussian of variance $({\sum }_i{b}_i{)}^{-1}$, condition on the linear constraint in shifted coordinates, and apply the Gaussian conditioning formula. The resulting covariance is the imaginary part of the compressed tree Green function. On an edge the precision splits into two positive contributions, one from each endpoint.

After whitening, these contributions satisfy exact identities: their pullbacks sum to the identity on the star, and the two shares on an edge sum to the identity on the edge. The entropy/Fisher-information argument uses these identities and re-rooting to cancel terms in expectation. Averaging the environment covariance before whitening would destroy these identities. The conclusion is conditional Gaussianity with the random tree covariance, including root variance $\Im G_o(E+i0)/(\pi {\rho }_{d,w}(E))$ in the source’s eigenvector normalization (OpenAI, 2026a).

Reversible changes yield exact resolvent identities

In the clean graph, sample finitely many oriented edges and permute the matching between their two endpoint lists. Except on an event of probability $O(1/n)$ for a fixed list, the endpoints are distinct and there are no unwanted edges. The switch is a bijection of equally weighted marked regular graphs, hence preserves their law.

The resolvent response to a finite-rank change is explicit. If $R=(H-z{)}^{-1}$, $U$ selects the changed coordinates, $B$ is an invertible perturbation matrix, and $M=U^{\mathsf{T}}RU$, then

$$(H+UB{U}^{\mathsf{T}}-z{)}^{-1}=R-RU(B^{-1}+M{)}^{-1}{U}^{\mathsf{T}}R.$$

The determinant lemma gives the corresponding logarithmic-derivative formula for the trace. Versions using $I+MB$ handle singular $B$. Passing these identities to microscopic subsequential limits is justified by the local-law and resolvent-tail estimates.

The Gaussian endpoint marks are invariant under simultaneous orthogonal changes of coordinates. Conjugating the permutation identities by those changes gives all reflection switches; finite products of reflections give the full orthogonal family. Many small rotations can then be analyzed using their first two moments.

Many small changes simulate Gaussian matrix noise

The disordered proof uses a different reversible operation: on a positive-probability event measurable without the root potential, interchange the two halves of small equal intervals of its uniform distribution. This preserves the conditional potential law and changes it by $D_{\alpha }=\pm \ell$, with $\ell \asymp \theta$. Resolvent reduction gives rank-one coefficients

$${\beta }_{\alpha }=\frac{c_{\alpha }{D}_{\alpha }}{1+a_{\alpha }{D}_{\alpha }},$$

where $a_{\alpha }=\Re G_o$ and $c_{\alpha }=\Im G_o/(\pi {\rho }_{d,w}(E))$. Pairing the two interval halves cancels the first-order mean; Lipschitz control leaves $\mathbb{E}{\beta }_{\alpha }=O({\theta }^2)$. Choose a small fixed $\tau >0$, set $T=r^{\tau }\to \infty$ and $\theta =(T/r{)}^{1/2}$, and make $r$ changes. Then

$$\underset{\alpha }{\max }|{\beta }_{\alpha }|=O(\theta ),s_2:=\sum _{\alpha }{\beta }_{\alpha }^2\asymp T,|s_1|:=\left|\sum _{\alpha }{\beta }_{\alpha }\right|=O(T)$$

with probability tending to one. The scalar mean $s_1$ need not vanish.

Conditionally on the microscopic positions and environments, the standardized marks are independent Gaussian vectors. A Lindeberg replacement of their centered rank-one contributions matches the GOE covariance. Two spectral cutoffs first control the far resolvent tail and then isolate a much smaller finite block. The resulting comparison matrix is

$$H_r=\mathrm{diag}(x_j:|x_j|\le K)+s_{1}I+\sqrt{s_2}{\mathcal{W}}_r,$$

with raw GOE ${\mathcal{W}}_r$. The limiting-space construction takes graph size to infinity for each fixed list first; only then does $r$ grow. It does not demand a finite-graph Gaussian-mark theorem for an increasing number of sampled roots.

Density normalization closes the fixed-energy argument

The final input is fixed-energy Dyson Brownian motion universality for a diagonal matrix plus Gaussian noise. Spectral discrepancy bounds verify its regularity and time-window hypotheses after rescaling the finite block. A further dilation tending to one makes the comparison density exactly $1/\pi$, as required by the chosen theorem. Correlation-function convergence is converted to Laplace-functional convergence with local counting bounds; the ordered-tuple multiplicity and the spatial Jacobian must both be included.

Switching invariance is used after averaging out the conditional environment data. Thus each original microscopic subsequential law is identified with the same GOE law after unfolding by the correct density. Subsequence compactness then gives convergence through all admissible graph sizes.

See Also

• Family 214 also uses operator estimates on expanding graphs, for connection kernels rather than adjacency eigenvalues.
• Random-matrix preliminaries in spin-glass complexity explains another role of Gaussian matrix spectra.

🏷️ Manuscripts and verification scope

• Fixed-energy universality for weak Anderson disorder on random regular graphs — pinned manuscript and companion source.
• GOE bulk universality for fixed-degree random regular graphs — pinned manuscript and companion source.

No family scope page was present at lean/docs/219.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Fixed-energy universality for weak Anderson disorder on random regular graphs.

🐻  OpenAI 2026b. GOE bulk universality for fixed-degree random regular graphs.