on random matrices and complexity of spin glasses

Overview

Auffinger, Ben Arous, and Cerny compute the exponential growth rate of the expected number of critical points of the spherical $p$-spin Hamiltonian below a fixed energy level (Auffinger, Ben Arous & Černý, 2013). The main mechanism is a precise Kac-Rice identity: after conditioning on the value of the Hamiltonian at a critical point, the Hessian is a shifted Gaussian Orthogonal Ensemble matrix.

The result explains the bottom of the energy landscape. There is a critical energy $-N{E}_0(p)$ where the annealed number of minima first becomes non-negligible, a threshold $-N{E}_{\infty }(p)$ above which fixed-index critical points disappear, and a sequence of levels

$$-N{E}_0(p)<-N{E}_1(p)<-N{E}_2(p)<\cdots <-N{E}_{\infty }(p)$$

giving a layered absence picture: below successive levels, only fixed indices up to a corresponding value can occur with non-negligible probability.

🏷️ The Spherical $p$-Spin Model

The state space is the sphere of radius $\sqrt{N}$,

$$S^{N-1}(\sqrt{N})=\{\sigma \in {\mathbb{R}}^N:\Vert \sigma {\Vert }^2=N\}.$$

For an integer $p\ge 2$, the spherical $p$-spin Hamiltonian is

$$H_{N,p}(\sigma )=\frac{1}{N^{(p-1)/2}}\sum _{i_1,\dots ,i_p=1}^N{J}_{i_1,\dots ,i_p}{\sigma }_{i_1}\cdots {\sigma }_{i_p},$$

where the coefficients $J_{i_1,\dots ,i_p}$ are independent standard Gaussians.

Equivalently, $H_{N,p}$ is a centered Gaussian process with covariance

$$\mathbb{E}{H}_{N,p}(\sigma )H_{N,p}({\sigma }^{\prime })=NR(\sigma ,{\sigma }^{\prime }{)}^p,R(\sigma ,{\sigma }^{\prime })=\frac{1}{N}⟨\sigma ,{\sigma }^{\prime }⟩.$$

The overlap $R(\sigma ,{\sigma }^{\prime })$ is the normalized correlation between two spin configurations. The covariance depends only on the overlap, so the model is rotationally invariant. This symmetry is what makes the later Kac-Rice integral collapse to a single-point calculation.

Why the energy scale is $N$

At a fixed configuration, $H_{N,p}(\sigma )$ has variance $N$, so a typical value is of order $\sqrt{N}$. The entropy of available configurations is exponential in $N$, and the global minimum is much lower, of order $N$. Thus the interesting low-energy levels are written as $Nu$, with $u<0$ fixed.

The case $p=2$ is essentially random-matrix theory from the start. The Hamiltonian is a quadratic form on the sphere, and the critical points are eigenvectors of a GOE matrix. The paper’s main content begins at $p\ge 3$, where the Hamiltonian is nonlinear but its Hessian at a critical point still has a GOE structure.

🏷️ Critical Points and Complexity

For a smooth function on a manifold, the Morse index of a nondegenerate critical point is the number of negative eigenvalues of the Hessian restricted to the tangent space. Index $0$ means a local minimum; index $1$ means a saddle with one unstable direction.

For a Borel set $B\subset \mathbb{R}$, define

$${\mathrm{Crt}}_{N,k}(B)=\#\{\sigma :\nabla H_{N,p}(\sigma )=0,H_{N,p}(\sigma )\in NB,i({\nabla }^2{H}_{N,p}(\sigma ))=k\}.$$

The total count is

$${\mathrm{Crt}}_N(B)=\sum _{k=0}^{N-1}{\mathrm{Crt}}_{N,k}(B).$$

The paper studies the annealed complexity

$$\underset{N\to \infty }{\lim }\frac{1}{N}\log \mathbb{E}{\mathrm{Crt}}_{N,k}((-\infty ,u))$$

and its total-index analogue. “Annealed” means the logarithm is taken after expectation. This is easier than the typical or quenched count

$$\frac{1}{N}\mathbb{E}\log {\mathrm{Crt}}_{N,k}((-\infty ,u)),$$

and the distinction matters: a first moment can be dominated by rare landscapes.

First moment, not concentration

The paper gives exact first-moment identities and their exponential asymptotics. It does not prove concentration of the number of critical points at each level. The ground-state result for even $p$ uses external input from the Parisi formula, not a second-moment theorem for the minima count.

🏷️ Preliminaries: Kac-Rice

The Kac-Rice formula counts critical points by integrating over the event that the gradient vanishes. In the present setting it says, schematically,

$$\mathbb{E}{\mathrm{Crt}}_{N,k}(B)={\int }_{S^{N-1}(\sqrt{N})}\mathbb{E}\left[|\det {\nabla }^{2}H(\sigma )|1_{\{H(\sigma )\in NB,i({\nabla }^{2}H(\sigma ))=k\}}\mid \nabla H(\sigma )=0\right]{\varphi }_{\nabla H(\sigma )}(0)d\sigma .$$

There are three pieces in this formula.

• The density ${\varphi }_{\nabla H(\sigma )}(0)$ measures how likely the gradient is to be near zero.
• The determinant $|\det {\nabla }^{2}H(\sigma )|$ is the local Jacobian converting zeros of the gradient into volume.
• The indicator restricts to critical values in the desired energy band and to the desired Morse index.

Because the spherical $p$-spin field is rotationally invariant, the integrand does not depend on $\sigma$. One can evaluate it at the north pole and multiply by the surface area of the sphere.

The key Gaussian computation

Let

$$f_{N,p}(\sigma )=N^{-1/2}{H}_{N,p}(\sqrt{N}\sigma ),\sigma \in S^{N-1}.$$

At a fixed point $\sigma$, the random variables

$$f(\sigma ),\nabla f(\sigma ),{\nabla }^{2}f(\sigma )$$

are jointly Gaussian. The gradient is independent of $(f,{\nabla }^{2}f)$, and conditional on $f(\sigma )=x$,

$${\nabla }^{2}f(\sigma )\stackrel{d}{=}\sqrt{2(N-1)p(p-1)}{M}_{N-1}-pxI,$$

where $M_{N-1}$ is a GOE matrix.

This is the bridge from spin glasses to random matrices. Conditioning on a low value $x<0$ shifts the Hessian upward by $-pxI$, making minima more likely. Conditioning on a higher value shifts the Hessian less, so negative eigenvalues appear.

🏷️ Preliminaries: The GOE Edge

The paper uses the GOE normalization in which a real symmetric $N\times N$ matrix $M_N$ has independent entries up to symmetry and

$$\mathbb{E}{M}_{ij}^2=\frac{1+{\delta }_{ij}}{2N}.$$

With this normalization, the empirical eigenvalue distribution converges to the semicircle law on

$$[-\sqrt{2},\sqrt{2}].$$

The low-energy spin-glass problem is controlled by the left edge $-\sqrt{2}$. A critical point at energy density $u$ corresponds, after the scaling in the Kac-Rice identity, to a GOE eigenvalue near

$$u\sqrt{\frac{p}{2(p-1)}}.$$

The value

$$E_{\infty }(p)=2\sqrt{\frac{p-1}{p}}$$

is exactly the energy density for which this GOE location is $-\sqrt{2}$.

Thus $-E_{\infty }(p)$ is the edge threshold. Below it, fixed-index critical points require an eigenvalue large-deviation event outside the semicircle edge. Above it, the relevant eigenvalues live inside the bulk, so critical points with index proportional to $N$ dominate rather than any fixed index.

🏷️ The Exact GOE Identity

Let

$${\lambda }_0^N\le {\lambda }_1^N\le \cdots \le {\lambda }_{N-1}^N$$

be the ordered eigenvalues of an $N\times N$ GOE matrix with the normalization above. The paper proves the finite-$N$ identity

$$\mathbb{E}{\mathrm{Crt}}_{N,k}(B)=2\sqrt{\frac{2}{p}}(p-1{)}^{N/2}{\mathbb{E}}_{\mathrm{GOE}}^N\left[\exp \left\{-\frac{N(p-2)}{2p}({\lambda }_k^N{)}^2\right\}{1}_{\left\{{\lambda }_k^N\in \sqrt{\frac{p}{2(p-1)}}B\right\}}\right].$$

Summing over $k$ gives the total complexity identity

$$\mathbb{E}{\mathrm{Crt}}_N(B)=2N\sqrt{\frac{2}{p}}(p-1{)}^{N/2}{\int }_{\sqrt{\frac{p}{2(p-1)}}B}\exp \left\{-\frac{N(p-2)}{2p}{x}^2\right\}{\rho }_N(x)dx,$$

where ${\rho }_N$ is the normalized one-point eigenvalue density.

🏷️ Proof Ideas Behind the Finite-$N$ Identity

The finite-$N$ formula is not only an asymptotic estimate. It is an exact identity, and its proof has three clean inputs.

Step 1: Normalize and apply Kac-Rice

Work on the unit sphere with

$$f_{N,p}(\sigma )=N^{-1/2}{H}_{N,p}(\sqrt{N}\sigma ),\sigma \in S^{N-1}.$$

Then

$$\mathbb{E}{f}_{N,p}(\sigma )f_{N,p}({\sigma }^{\prime })=⟨\sigma ,{\sigma }^{\prime }{⟩}^p.$$

The event $H_{N,p}\in NB$ becomes $f_{N,p}\in \sqrt{N}B$. Kac-Rice gives

$$\mathbb{E}{\mathrm{Crt}}_{N,k}(B)={\omega }_N{\varphi }_{\nabla f(n)}(0)\mathbb{E}\left[|\det {\nabla }^{2}f(n)|1_{\{f(n)\in \sqrt{N}B,i({\nabla }^{2}f(n))=k\}}\mid \nabla f(n)=0\right],$$

where $n$ is the north pole and ${\omega }_N$ is the surface area of $S^{N-1}$. Rotational invariance is what turns the integral over the sphere into this single expectation.

The density term is explicit because the tangent gradient is Gaussian with covariance $p{I}_{N-1}$:

$${\varphi }_{\nabla f(n)}(0)=(2\pi p{)}^{-(N-1)/2}.$$

Step 2: Differentiate the covariance kernel

Use local coordinates near the north pole,

$${\Psi }^{-1}(x)=(x_1,\dots ,x_{N-1},\sqrt{1-|x{|}^2}),$$

so the covariance kernel is

$$C(x,y)={\left(x\cdot y+\sqrt{1-|x{|}^2}\sqrt{1-|y{|}^2}\right)}^p.$$

Differentiating $C$ at $x=y=0$ gives

$$\mathbb{E}[f^2]=1,\mathbb{E}[f_i{f}_j]=p{\delta }_{ij},\mathbb{E}[f{f}_i]=0,\mathbb{E}[f_i{f}_{\ell m}]=0,\mathbb{E}[f{f}_{ij}]=-p{\delta }_{ij},$$

and

$$\mathbb{E}[f_{ij}{f}_{\ell m}]=p(p-1)({\delta }_{i\ell }{\delta }_{jm}+{\delta }_{im}{\delta }_{j\ell })+p^2{\delta }_{ij}{\delta }_{\ell m}.$$

These covariance identities imply two structural facts. First, the gradient is independent of $(f,{\nabla }^{2}f)$, so conditioning on $\nabla f=0$ does not change the joint law of the value and Hessian. Second, conditioning on $f(n)=x$ shifts the Hessian by a scalar matrix:

$${\nabla }^{2}f(n)\stackrel{d}{=}\sqrt{2(N-1)p(p-1)}{M}_{N-1}-pxI,$$

where $M_{N-1}$ is a GOE matrix with the paper’s normalization.

Step 3: Turn a determinant into one extra GOE eigenvalue

After Step 2, the remaining expectation has the form

$$\mathbb{E}\left[|\det (M_{N-1}-sI)|1_{\{i(M_{N-1}-sI)=k\}}{1}_{\{s\in G\}}\right]$$

for a Gaussian shift $s$ proportional to $f(n)$. If the eigenvalues of $M_{N-1}$ are

$${\mu }_0\le \cdots \le {\mu }_{N-2},$$

then

$$|\det (M_{N-1}-sI)|=\prod _{j=0}^{N-2}|{\mu }_j-s|.$$

The index condition says exactly that $s$ is inserted as the $k$-th ordered eigenvalue, using the same zero-based indexing as ${\lambda }_0^N\le \cdots \le {\lambda }_{N-1}^N$.

This last observation is the algebraic heart of the proof. The GOE eigenvalue density contains the Vandermonde factor

$$\prod _{i<j}|{\mu }_i-{\mu }_j|.$$

Multiplying by

$$\prod _j|{\mu }_j-s|$$

produces the Vandermonde factor for the $N$ numbers obtained by inserting $s$ among the $N-1$ eigenvalues. After a harmless rescaling from the $(N-1)$-GOE normalization to the $N$-GOE normalization, the variable $s$ becomes ${\lambda }_k^N$. The Gaussian density of $s$ combines with the GOE Gaussian weight and leaves precisely the exponential factor

$$\exp \left\{-\frac{N(p-2)}{2p}({\lambda }_k^N{)}^2\right\}.$$

The constants from the sphere volume, gradient density, Hessian scaling, and GOE normalizing constants combine into

$$2\sqrt{\frac{2}{p}}(p-1{)}^{N/2}.$$

This identity is the main conceptual achievement of the paper. Once it is known, the complexity asymptotics become large-deviation estimates for GOE eigenvalues.

🏷️ The Complexity Functions

For $u\le -E_{\infty }(p)$, define the GOE edge rate

$$I_1(u)=\frac{2}{E_{\infty }(p{)}^2}{\int }_u^{-E_{\infty }(p)}\sqrt{z^2-E_{\infty }(p{)}^2}dz.$$

This is the cost for pushing the smallest GOE eigenvalue below the edge after translating variables to the energy scale.

The total complexity exponent is

$${\theta }_p(u)=\{\begin{array}{ll}\frac{1}{2}\log (p-1)-\frac{p-2}{4(p-1)}{u}^2-I_1(u),& u\le -E_{\infty }(p),\\ \frac{1}{2}\log (p-1)-\frac{p-2}{4(p-1)}{u}^2,& -E_{\infty }(p)\le u\le 0,\\ \frac{1}{2}\log (p-1),& u\ge 0.\end{array}$$

For fixed index $k$, the exponent is

$${\theta }_{k,p}(u)=\{\begin{array}{ll}\frac{1}{2}\log (p-1)-\frac{p-2}{4(p-1)}{u}^2-(k+1)I_1(u),& u\le -E_{\infty }(p),\\ \frac{1}{2}\log (p-1)-\frac{p-2}{p},& u\ge -E_{\infty }(p).\end{array}$$

The main exponential asymptotics are

$$\underset{N\to \infty }{\lim }\frac{1}{N}\log \mathbb{E}{\mathrm{Crt}}_{N,k}((-\infty ,u))={\theta }_{k,p}(u),$$

for each fixed $k$, and

$$\underset{N\to \infty }{\lim }\frac{1}{N}\log \mathbb{E}{\mathrm{Crt}}_N((-\infty ,u))={\theta }_p(u).$$

Two simple consequences are worth isolating:

$$\underset{N\to \infty }{\lim }\frac{1}{N}\log \mathbb{E}{\mathrm{Crt}}_N(\mathbb{R})=\frac{1}{2}\log (p-1),$$

and, for every fixed $k$,

$$\underset{N\to \infty }{\lim }\frac{1}{N}\log \mathbb{E}{\mathrm{Crt}}_{N,k}(\mathbb{R})=\frac{1}{2}\log (p-1)-\frac{p-2}{p}.$$

The surprising fixed-index feature

At the level of exponential rates, the total number of index-$k$ critical points does not depend on $k$, as long as $k$ is fixed while $N\to \infty$. The energy location does depend on $k$: the low-lying index-$k$ points sit in different layers.

🏷️ Ground State and Layering

For each fixed $k\ge 0$, define $E_k(p)>0$ by

$${\theta }_{k,p}(-E_k(p))=0.$$

The sequence satisfies

$$E_0(p)>E_1(p)>E_2(p)>\cdots >E_{\infty }(p),E_k(p)\downarrow E_{\infty }(p).$$

The root $E_0(p)$ is the annealed prediction for the ground-state energy. Indeed, below $-N(E_0(p)+\epsilon )$, the expected number of minima is exponentially small. Markov’s inequality then shows that with high probability there are no minima that low.

Ground-state scale

Let

$$G{S}_N=\frac{1}{N}\underset{\sigma \in S^{N-1}(\sqrt{N})}{\inf }{H}_{N,p}(\sigma ).$$

For every $p\ge 3$ and every $\epsilon >0$,

$$\mathbb{P}\{G{S}_N\ge -E_0(p)-\epsilon \}\to 1.$$

For even $p\ge 4$, the matching upper bound follows from the Parisi formula, and

$$G{S}_N\to -E_0(p)$$

in probability.

The finite-index layers come from the other roots $E_k(p)$.

Low-energy layering

Fix $k\ge 0$ and $\epsilon >0$. With exponentially high probability, there is no critical point of index at least $k$ below

$$-N(E_k(p)+\epsilon ).$$

Also, with exponentially high probability, there is no critical point of any fixed index $k$ above

$$-N(E_{\infty }(p)-\epsilon ).$$

Translated into geometry, this is an absence statement for fixed indices:

• Below $-N{E}_1(p)$, the only possible fixed index is $0$.
• Below $-N{E}_2(p)$, the only possible fixed indices are $0$ and $1$.
• Below $-N{E}_3(p)$, the only possible fixed indices are $0,1,2$.
• Above $-N{E}_{\infty }(p)$, critical points of any fixed index are exponentially unlikely; typical critical points have index growing with $N$.

This gives a quantitative Morse-theoretic picture of metastability. In the usual landscape heuristic, moving from one deep minimum to another requires crossing an index-one saddle. Since the first index-one layer is separated from the ground layer by

$$N(E_0(p)-E_1(p)),$$

the predicted barrier height is linear in $N$.

🏷️ Scope of the First-Moment Method

The computation is a first-moment computation. When the exponent is negative, it gives a strong absence result by Markov’s inequality: with high probability there are no critical points in that region. This is how the lower bound on the ground-state energy and the forbidden fixed-index regions are obtained.

When the exponent is positive, the interpretation is more delicate. A positive annealed exponent says that the expected number of critical points is exponentially large, but it does not by itself prove that a typical realization contains exponentially many such points. Proving typical abundance requires additional concentration or second-moment arguments, which are not part of the finite-$N$ GOE identity itself.

For this note, the main takeaway is therefore the mechanism: Kac-Rice reduces the landscape count to a shifted GOE determinant, and the determinant inserts one eigenvalue into the GOE joint density.

🔗 See Also

• on Ising models --- The Ising note gives the discrete-spin statistical-mechanics background; the spherical model replaces $\{\pm 1{\}}^N$ by a continuous sphere to make differential geometry and random matrices available.
• on Slepian’s lemma and Gaussian comparison --- The Hamiltonian is a Gaussian process indexed by the sphere, and comparison ideas are a natural companion to energy landscape estimates.
• on Dudley’s Theorem --- Metric entropy controls global behavior of Gaussian processes; here the focus is instead on critical points, but both viewpoints study the geometry induced by the covariance.
• on Gaussian Correlation Inequality --- Another example where Gaussian structure converts a geometric question into a precise probabilistic inequality.

📚 References

🐻  Auffinger, A., Ben Arous, G. & Černý, J. 2013. Random Matrices and Complexity of Spin Glasses. Communications on Pure and Applied Mathematics 66(2), 165–201.