Near-optimal shattering in the Ising pure p-spin and rarity of solutions returned by stable algorithms

Abstract

We show that in the Ising pure $p$-spin model of spin glasses, shattering takes place at all inverse temperatures $\beta \in (\sqrt{(2\log p)/p},\sqrt{2\log 2})$ when $p$ is sufficiently large as a function of $\beta$. Of special interest is the lower boundary of this interval which matches the large $p$ asymptotics of the inverse temperature marking the hypothetical dynamical transition predicted in statistical physics. We show this as a consequence of a `soft' version of the overlap gap property which asserts the existence of a distance gap of points of typical energy from a typical sample from the Gibbs measure. We further show that this latter property implies that stable algorithms seeking to return a point of at least typical energy are confined to an exponentially rare subset of that super-level set, provided that their success probability is not vanishingly small.

Typos corrected and a few precisions added. Theorem 1.2 slightly revised