Lower and Upper Bounds for Glauber Dynamics from Typical States of the Low-Temperature Sherrington–Kirkpatrick Model

Authors’ Note

With the exception of this note, the entire document is machine-written. We have carefully supervised its preparation to ensure that the proofs are readable and that previous literature is appropriately cited. We are releasing this manuscript on Hexagon to disseminate the result as quickly as possible because it may be of interest to the mathematical community. We welcome suggestions concerning mathematical corrections, omitted citations, and attribution of ideas.

P. L. was partially supported by NSF grant DMS-2450004.

Introduction

The Sherrington–Kirkpatrick (SK) model is the mean-field Ising spin glass, in which every pair of spins interacts through an independent Gaussian coupling [100]. Its equilibrium theory is well developed. Parisi’s hierarchical ansatz [91] predicted the limiting free energy, and this prediction was proved through Guerra’s interpolation bound [59] and Talagrand’s matching lower bound [103]. At every fixed inverse temperature $\beta> 1$ and zero external field, the minimizing Parisi measure is supported on an interval $[0,q_\beta]$; this was proved by Zhou for $\beta$ close to one [116, Theorem 1] and in [69, Theorem 1.1] for every $\beta> 1$. Much less is known about the dynamics of the model at low temperature, and about the finite-size corrections to its equilibrium quantities. This paper addresses both.

Our main results concern the heat-bath dynamics, also called Glauber dynamics [58], in which one spin at a time is resampled from its conditional law. For fixed $\beta> 1$, we sample the couplings and then one configuration from the Gibbs measure, and run the dynamics from this configuration. We prove that, with probability tending to one, the law of the configuration at time $\exp(A_\beta n^{7/30})$ is still at total-variation distance greater than $\tau$ from the Gibbs measure, for every fixed $\tau< 1/2$ and a coefficient $A_\beta> 0$ that does not depend on $\tau$ (Theorem 1.1). In the other direction, for every fixed $\omega\in(0,1/4)$, the distance is at most $1/4$ at time $\exp(n^{1-\omega})$, again with probability tending to one (Theorem 1.3). OpenAI proved bounds of both kinds in the same setting, with the same joint law of the couplings and the initial configuration, the same clocks of rate one per site, and the threshold $1/4$: a lower bound at time $\exp(n^{1/10000})$ [77, Theorem 1.1] and an upper bound at time $\exp(n^{1-1/40000000})$ [85, Theorem 1]. We follow the overall strategy of both proofs. Let $T^J(X_0)$ be the first time at which the distance from the Gibbs measure is at most $1/4$. Combining our two bounds, we find that if $\log T^J(X_0) = n^{\zeta+o(1)}$, then $7/30 \le\zeta\le3/4$ (Corollary 1.5). The proof of the lower bound uses the upper bound $n^{-7/10}$ of Aronow and Lopatto on the mean bias of the pressure [6, Theorem 1.1].

Our second contribution is a complete formal proof of Theorem 1.1 in the Lean 4 proof assistant [48, 108], together with formal proofs of two results that are not new. The first is the fluctuation theorem $\operatorname{Var}(F_n) = n^{1/3+o(1)}$ for the logarithm $F_n$ of the partition function (Theorem 1.6), which was stated and proved by OpenAI in [81, Theorem 1.1]. OpenAI’s public formalization of this theorem assumes a two-sided bound on positive logarithmic moments of the centered completed log partition function, which is proved on paper in [81, Proposition 7.5]; our formal proof establishes this bound. We restate the theorem with attribution, describe the structure of its proof, and reproduce the short final step of that proof; we do not claim a new mathematical proof of Theorem 1.6. We have formalized Theorem 1.3; see Section 22.5.

The second known result is a lower bound with exponent $5/6$ on the mean bias $P_\beta-n^{-1}\mathbb{E}F_n$, where $P_\beta=\lim_{n\to\infty}n^{-1}\mathbb{E}F_n$ is the limiting pressure. It follows from Theorem 1.6 and a variance–bias inequality of Aronow and Lopatto [8, Lemma 7.4 and Remark 7.14] that the mean bias is at least of order $n^{-5/6-\varepsilon}$ for every fixed $\varepsilon>0$ (Corollary 1.7). This deduction was already recorded in [6, Section 1.6]; what is new here is its formal proof. Together with the upper bound of [6], it shows that if the mean bias is $n^{-a+o(1)}$, then $7/10\le a\le5/6$.

Main results

For an integer $n\ge2$, let $\Sigma_n=\{-1,1\}^n$, and let $J=(J_{ij})_{1\le i<j\le n}$ be independent standard Gaussian variables. We set $J_{ji}=J_{ij}$ and $J_{ii}=0$. The Hamiltonian, the partition function, and the Gibbs measure at inverse temperature $\beta$ are

We write $R(x,y)=n^{-1}\sum_{i=1}^n x_i y_i$ for the overlap of $x,y\in\Sigma_n$, and $F_n=\log Z_n$.

In the heat-bath dynamics, each site carries an independent exponential clock of rate one. When the clock of site $i$ rings at a configuration $x$, the spin $x_i$ is replaced by $\sigma\in\{-1,1\}$ with probability

which is the conditional law of the $i$th spin under $\pi^J$ given the other spins. An update may leave the configuration unchanged. We write $P_t^J(x,\cdot)$ for the law at time $t$ of this process started at $x$, and $K^J$ for the transition matrix of the discrete chain that chooses a site uniformly at random and performs one such update. One unit of continuous time contains $n$ update attempts on average. Both chains are reversible with respect to $\pi^J$. For $x\in\Sigma_n$, $t\ge0$, and integers $k\ge0$, we set

where $\lVert\nu-\zeta\rVert_{\mathrm{TV}}=\frac{1}{2}\sum_x\lvert\nu(x)-\zeta(x)\rvert$. We also write

for the mixing times of the two chains started at $x$. Since $t \mapsto d^{J}(x,t)$ is continuous and nonincreasing (Lemma 3.2), we have $T^{J}(x) \le t$ if and only if $d^{J}(x,t) \le1/4$, and similarly in discrete time. Finally, $\mathbb{P}_{J,X_0\sim\pi^J}$ denotes the joint law of the couplings $J$ and of a configuration $X_0$ whose conditional law given $J$ is $\pi^J$; see (38). These definitions are given in detail in Section 3.

The configuration $X_0$ is sampled once and then held fixed, so that $d^J(X_0,t)$ measures the distance from equilibrium of the chain started at this particular configuration. If the initial configuration were instead averaged over $\pi^J$ before the distance is taken, the law at time $t$ would be $\pi^J$ by stationarity, and the distance would vanish. Since the Gibbs mass of the set of initial configurations in the event of (1.2) takes values in $[0,1]$ and has expectation equal to the displayed probability, (1.2) is equivalent to the convergence of this Gibbs mass to one in probability over the disorder; this observation is made after [77, Theorem 1.1] and is recalled in Section 3. The coefficient $A_\beta$ depends only on $\beta$: the same coefficient serves for every fixed threshold $\tau< 1/2$ and for both clocks, while the rate of convergence in (1.2) and (1.3) may depend on $\tau$. The restriction $\tau< 1/2$ comes from spin-flip symmetry: for every configuration $v$, the half-space $\{y : R(v,y) \le0\}$ has Gibbs mass at least $1/2$, and the proof shows that, for a suitable configuration $v$ with $R(v,X_0)$ bounded away from zero, the chain started at $X_0$ is unlikely to enter this half-space before the stated time.