betaFeedback

WorksMathematics

Non-asymptotic First- and Second-Order Tail Brackets for the Kostlan-Shub-Smale Field and Spherical k-Spin Complexity

Abstract

For the Kostlan-Shub-Smale field XX of degree k≥3k\ge3 on the sphere Sd−1\mathbb{S}^{d-1}, we prove the two-sided bound (1−ε(u)) δ∗(u)≤P{sup⁡X>u}≤δ∗(u)(1-\varepsilon(u))\,δ_{*}(u)\le\mathbb{P}\{\sup X>u\}\leδ_{*}(u) at every finite (k,d)(k,d), where δ∗(u)δ_{*}(u) is the expected number of critical points above uu, halved when kk is even, and ε(u)\varepsilon(u) is explicit for ρu≥min⁡{d−1,322(d−1)}ρu\ge\min\{d-1,\frac32\sqrt{2(d-1)}\}. The gap is therefore at most of order e−(1+ρ2)u2/2e^{-(1+ρ^{2})u^{2}/2} with ρ2=k/(2(k−1))ρ^{2}=k/(2(k-1)). We also give δ∗δ_{*} itself in closed form, as a finite sum of Hermite polynomials, together with a two-term envelope that is asymptotically sharp and a single-monomial relaxation of the form Cud−2e−u2/2Cu^{d-2}e^{-u^{2}/2}. As an application we bracket the annealed complexity of the spherical kk-spin Hamiltonian at every finite (k,d)(k,d): the upper bound holds at every energy, a lower bound of the same form at every energy above 9/49/4 times the spectral edge 2(d−1)/ρ\sqrt{2(d-1)}/ρ, above twice the edge when d≥10d\ge10, and is consistent with the Auffinger-Ben Arous-Černý complexity function as d→∞d\to\infty.

Introduction

Let XX be the Kostlan–Shub–Smale (KSS) field of degree k≥3k \ge3 on the unit sphere Sd−1⊂Rd\mathbb{S}^{d-1} \subset\mathbb{R}^d, d≥3d \ge3: the centered Gaussian field with covariance E[X(s)X(t)]=⟨s,t⟩k\mathbb{E}[X(s)X(t)] = \langle s,t\rangle^k. It is the canonical isotropic Gaussian homogeneous polynomial of degree kk, the Hamiltonian of the spherical kk-spin model up to normalization, and the noise part of the spiked tensor model; its paths are polynomials. This paper is about one quantity, P{sup⁡Sd−1X>u}\mathbb{P}\{\sup_{\mathbb{S}^{d-1}} X > u\}, and about how well the Kac–Rice first moment describes it at finite (k,d)(k,d).

Two things are proved. The first is that the Kac–Rice bound is not only an upper bound but a two-sided one, with an explicit error: Theorem 1.1 brackets the supremum probability between (1−ε(u))δ∗(u)(1-\varepsilon(u))\delta_*(u) and δ∗(u)\delta_*(u), where δ∗(u)\delta_*(u) is the expected number of critical points above uu (halved for kk even) and ε(u)\varepsilon(u) is explicit at every finite (k,d)(k,d). The second is that δ∗\delta_* itself is computable: it has a closed form as a finite sum of Hermite polynomials (Theorem 2.4), together with two explicit relaxations (Theorems 2.7 and 2.10). that trade tightness for a form one can invert. § 5 applies both to the annealed complexity of the spherical kk-spin Hamiltonian.

The point of the bracket is that it turns a bound into an approximation. Without it, an explicit upper bound on a tail can always be suspected of being loose by an unknown factor, and there is no baseline against which to judge it. Here the baseline is δ∗\delta_* itself, and the bracket says the first moment is right to within ε(u)\varepsilon(u), which decays like e−ρ2u2/2e^{-\rho^2 u^2/2} with ρ2=k/(2(k−1))\rho^2 = k/(2(k-1)).

The Kac–Rice integral and the conditional Hessian

Throughout, ρ:=k/(2(k−1))\rho:= \sqrt{k/(2(k-1))} and ς2:=1/ρ2=2(k−1)/k\varsigma^2 := 1/\rho^2 = 2(k-1)/k; Φ\Phi and φ\varphi are the standard Gaussian distribution function and density, Φ‾:=1−Φ\overline{\Phi} := 1-\Phi, λmax⁡\lambda_{\max} is the largest eigenvalue of a symmetric matrix, ∥G∥\lVert G\rVert the operator norm of a matrix GG, and ∥Y∥p:=(E∣Y∣p)1/p\lVert Y\rVert_p := (\mathbb{E}|Y|^p)^{1/p} for a random variable YY; N[u,∞)cp(F)N^{\mathrm{cp}}_{[u,\infty)}(F) and N[u,∞)lm(F)N^{\mathrm{lm}}_{[u,\infty)}(F) count the critical points and the local maxima of a smooth function FF with value ≥u\ge u, the argument being omitted when F=XF=X. The Gaussian Orthogonal Ensemble of size nn, GOE⁡(n)\operatorname{GOE}(n), is the law of a real symmetric n×nn \times n random matrix G=(Gij)G=(G_{ij}) whose entries are jointly Gaussian, centered, independent up to symmetry, with the normalization Var⁡(Gii)=1\operatorname{Var}(G_{ii})=1 and Var⁡(Gij)=1/2\operatorname{Var}(G_{ij})=1/2 for i≠ji\ne j; equivalently, the density on the space of real symmetric matrices is proportional to exp⁡(−tr⁡(G2)/2)\exp(-\operatorname{tr}(G^2)/2) and the law is invariant under conjugation by any orthogonal matrix [14].

Fix t∈Sd−1t\in\mathbb{S}^{d-1} and an orthonormal basis (ea)a≤d−1(e_a)_{a\le d-1} of t⊥=TtSd−1t^\perp=T_t\mathbb{S}^{d-1}. Differentiating ⟨s,t⟩k\langle s,t\rangle^k, the covariant derivatives of XX at tt satisfy

Cov⁡(∂aX(t),∂bX(t))=kδab,Cov⁡(X(t),∇X(t))=0,Cov⁡(∇X(t),∇2X(t))=0,\operatorname{Cov}(\partial_a X(t),\partial_b X(t))=k\delta_{ab},\qquad\operatorname{Cov}(X(t),\nabla X(t))=0,\qquad\operatorname{Cov}(\nabla X(t),\nabla^2X(t))=0,
Cov⁡(X(t),∇ab2X(t))=−kδab,Cov⁡(∇ab2X(t),∇cd2X(t))=k(k−1)(δacδbd+δadδbc)+k2δabδcd.\operatorname{Cov}(X(t),\nabla^2_{ab}X(t))=-k\delta_{ab},\qquad\operatorname{Cov}(\nabla^2_{ab}X(t),\nabla^2_{cd}X(t))=k(k-1)(\delta_{ac}\delta_{bd}+\delta_{ad}\delta_{bc})+k^2\delta_{ab}\delta_{cd}.

Hence the matrix

G:=∇2X(t)+kX(t)Id−12k(k−1)∼GOE⁡(d−1)(1)G:=\frac{\nabla^2X(t)+kX(t)I_{d-1}}{\sqrt{2k(k-1)}}\sim\operatorname{GOE}(d-1) \tag*{(1)}

is independent of (X(t),∇X(t))(X(t),\nabla X(t)), the gradient ∇X(t)∼N(0,kId−1)\nabla X(t)\sim N(0,kI_{d-1}) is independent of (X(t),∇2X(t))(X(t),\nabla^2X(t)), and conditionally on {X(t)=x,∇X(t)=0}\{X(t)=x,\nabla X(t)=0\},

∇2X(t)=2k(k−1)(G−ρxId−1),(2)\nabla^2X(t)=\sqrt{2k(k-1)}(G-\rho xI_{d-1}), \tag*{(2)}

since 2k(k−1)ρ=k\sqrt{2k(k-1)}\rho=k; this is the conditional law of Auffinger et al. [2 Lemma 3.2(b)]. The critical point tt is a nondegenerate local maximum if and only if λmax⁡(G)<ρx\lambda_{\max}(G)<\rho x. The Kac–Rice formula for the critical points of XX [1 Theorem 6.1], with p∇X(t)(0)=(2πk)−(d−1)/2p_{\nabla X(t)}(0)=(2\pi k)^{-(d-1)/2} and (2), gives

δexact(u):=EN[u,∞)cp=Ck,d∫u∞A(ρx)φ(x) dx,(3)\delta_{\mathrm{exact}}(u):=\mathbb{E}N^{\mathrm{cp}}_{[u,\infty)}=C_{k,d}\int_u^\infty A(\rho x)\varphi(x)\,\mathrm{d}x, \tag*{(3)}
A(ν):=E∣det⁡(G−νId−1)∣,Ck,d:=Vol⁡(Sd−1)(k−1π)(d−1)/2=2πΓ(d/2)(k−1)(d−1)/2.A(\nu):=\mathbb{E}\left|\det(G-\nu I_{d-1})\right|,\qquad C_{k,d}:=\operatorname{Vol}(\mathbb{S}^{d-1})\left(\frac{k-1}{\pi}\right)^{(d-1)/2}=\frac{2\sqrt{\pi}}{\Gamma(d/2)}(k-1)^{(d-1)/2}.

an equality for the expected number of critical points above uu, which Theorem 2.4 computes in closed form. For kk even, X(−s)=X(s)X(-s)=X(s) and the critical points come in antipodal pairs. Since the maximum of XX over the compact Sd−1\mathbb{S}^{d-1} is attained at a critical point, 1{sup⁡Sd−1X>u}≤N[u,∞)cp\mathbf{1}\{\sup_{\mathbb{S}^{d-1}}X>u\}\le N^{\mathrm{cp}}_{[u,\infty)}, and taking expectations

P{sup⁡Sd−1X>u}≤δ∗(u):=23+(−1)kδexact(u).(4)\mathbb{P}\left\{\sup_{\mathbb{S}^{d-1}}X>u\right\}\le\delta_*(u):=\frac{2}{3+(-1)^k}\delta_{\mathrm{exact}}(u). \tag*{(4)}

The bound is loose by the critical points above uu that are not the global maximum, saddle points and beaten local maxima alike; Theorem 1.1 shows that this slack is a factor ε(u)=O(ud−2e−ρ2u2/2)\varepsilon(u)=O(u^{d-2}e^{-\rho^2u^2/2}). The bound (4) is sharp at second order. For a Gaussian field of constant variance on a parameter set with bounded curvature, Azaïs and Wschebor [5 Theorem 8.12] prove that the Rice bound on the density of the maximum exceeds that density by at most exp⁡(−(1+γ)u2/2+o(u2))\exp(-(1+\gamma)u^2/2+o(u^2)), with γ>0\gamma>0 given by the conditional variance of the field at two points (and a boundary term, absent here). The scale δexact\delta_{\mathrm{exact}} is therefore the right one for the supremum probability as u→∞u\to\infty; the constants of that theorem are asymptotic in the level, and Theorem 1.1 gives the matching lower bound at finite (k,d)(k,d) by another route. § 2 evaluates δexact\delta_{\mathrm{exact}} in closed form for every uu (Theorem 2.4) and gives δIMF≥δexact\delta_{\mathrm{IMF}}\ge\delta_{\mathrm{exact}} on [uIMF,∞)[u_{\mathrm{IMF}},\infty), with uIMF:=2d−1/ρu_{\mathrm{IMF}}:=\sqrt{2d-1}/\rho, and δSMF≥δIMF\delta_{\mathrm{SMF}}\ge\delta_{\mathrm{IMF}} on [uSMF,∞)[u_{\mathrm{SMF}},\infty) (Proposition 2.12).

Asymptotic baseline as u→∞u\to\infty, with dd fixed. Replacing A(ρx)A(\rho x) in (3) by its leading monomial (ρx)d−1(\rho x)^{d-1} gives, by Lemma B.2, the asymptotic equivalent

References

  1. [1]Diego Armentano, Jean-Marc Azaïs, and José R. León. On a general Kac–Rice formula for the measure of a level set. The Annals of Applied Probability, 35(3):1828–1851, 2025. https://doi.org/10.1214/25-AAP2158.
  2. [2]Antonio Auffinger, Gérard Ben Arous, and Jiří Černý. Random matrices and complexity of spin glasses. Communications on Pure and Applied Mathematics, 66(2):165–201, 2013. https://doi.org/10.1002/cpa.21422. arXiv:1003.1129v2.
  3. [3]Jean-Marc Azaïs and Mario Wschebor. On the distribution of the maximum of a Gaussian field with d parameters. The Annals of Applied Probability, 15(1A):254–278, 2005. https://doi.org/10.1214/105051604000000602.
  4. [4]Jean-Marc Azaïs and Mario Wschebor. A general expression for the distribution of the maximum of a Gaussian field and the approximation of the tail. Stochastic Processes and their Applications, 118(7):1190–1218, 2008. https://doi.org/10.1016/j.spa.2007.07.016.
  5. [5]Jean-Marc Azaïs and Mario Wschebor. Level sets and extrema of random processes and fields. John Wiley & Sons, 2009. https://doi.org/10.1002/9780470434642.
  6. [6]Gérard Ben Arous, Amir Dembo, and Alice Guionnet. Aging of spherical spin glasses. Probability Theory and Related Fields, 120:1–67, 2001. https://doi.org/10.1007/PL00008774.
  7. [7]Gérard Ben Arous, Song Mei, Andrea Montanari, and Mihai Nica. The landscape of the spiked tensor model. Communications on Pure and Applied Mathematics, 72(11):2282–2330, 2019. https://doi.org/10.1002/cpa.21861. arXiv:1711.05424v2.
  8. [8]Ronald A. DeVore and George G. Lorentz. Constructive Approximation. Springer, 1993. https://doi.org/10.1007/978-3-662-02888-9.
  9. [9]Yan V. Fyodorov. Complexity of random energy landscapes, glass transition, and absolute value of the spectral determinant of random matrices. Physical Review Letters, 92(24):240601, 2004. https://doi.org/10.1103/PhysRevLett.92.240601.
  10. [10]Eric Kostlan. On the distribution of roots of random polynomials. In From Topology to Computation: Proceedings of the Smalefest, pages 419–431. Springer, 1993. https://doi.org/10.1007/978-1-4612-2740-3_38.
  11. [11]Leiden Declaration. The Leiden Declaration on Artificial Intelligence and Mathematics. https://leide n declaration.ai/, 2026. DOI: 10.5281/zenodo.20302944. Endorsed by the International Mathematical Union.DOI
  12. [12]Thibault Lesieur, Léo Miolane, Marc Lelarge, Florent Krzakala, and Lenka Zdeborová. Statistical and computational phase transitions in spiked tensor estimation. Proceedings of the 2017 IEEE International Symposium on Information Theory (ISIT), pages 511–515, 2017. https://doi.org/10.1109/ISIT.2017.8006580.
  13. [13]M. A. Lifshits. On the absolute continuity of distributions of functionals of random processes. Theory of Probability & Its Applications, 27(3):600–607, 1983. https://doi.org/10.1137/1127066.
  14. [14]Madan Lal Mehta. Random matrices, volume 142 of Pure and Applied Mathematics. Elsevier/Academic Press, 3rd edition, 2004.
  15. [15]Amelia Perry, Alexander S. Wein, and Afonso S. Bandeira. Statistical limits of spiked tensor models. Annales de l’Institut Henri Poincaré. Probabilités et Statistiques, 56(1):230–264, 2020. https://doi.org/10.1214/19-AIHP960.
  16. [16]Michael Shub and Steve Smale. Complexity of Bézout’s theorem. II. Volumes and probabilities. In Computational Algebraic Geometry, pages 267–285. Birkhäuser Boston, 1993. https://doi.org/10.1007/978-1-4612-2752-6_19.
  17. [17]Eliran Subag. The complexity of spherical p-spin models—a second moment approach. The Annals of Probability, 45(5):3385–3450, 2017. https://doi.org/10.1214/16-AOP1139.
  18. [18]Eliran Subag and Ofer Zeitouni. The extremal process of critical points of the pure p-spin spherical spin glass model. Probability Theory and Related Fields, 168(3–4):773–820, 2017. https://doi.org/10.1007/s00440-016-0724-2.
  19. [19]Gábor Szegő. Orthogonal Polynomials, volume 23 of American Mathematical Society Colloquium Publications. American Mathematical Society, 4th edition, 1975. https://doi.org/10.1090/coll/023.
  20. [20]Jonathan Taylor, Akimichi Takemura, and Robert J. Adler. Validity of the expected Euler characteristic heuristic. The Annals of Probability, 33(4):1362–1396, 2005. https://doi.org/10.1214/009117905000000099.

Paper details

vlnc:W_48wu2c9g
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents