OctoInformBeta

Critical SK autocorrelation processes and dynamics across the temperature transition

For n≥1n\ge1, let WW be a symmetric n×nn\times n matrix with zero diagonal and independent entries Wij∼N(0,1/n)W_{ij}\sim N(0,1/n) for i<ji<j. The zero-field Gaussian Sherrington-Kirkpatrick law at inverse temperature β\beta is μβ(x)∝exp⁡{βx𝖳Wx/2}\mu_\beta(x)\propto\exp\{\beta x^{\mathsf T}Wx/2\} on {−1,1}n\{-1,1\}^n. For each site ii and real observable ff, write Piβf=𝔼μβ[f∣xj,j≠i]P_i^\beta f=\mathbb E_{\mu_\beta}[f\mid x_j,\ j\ne i]. The unscaled Dirichlet form is 𝒟β(f)=∑i=1n𝔼μβ(f−Piβf)2\mathcal D_\beta(f)=\sum_{i=1}^n\mathbb E_{\mu_\beta}(f-P_i^\beta f)^2. Continuous-time heat-bath dynamics resamples each site at rate one. A discrete attempt resamples one uniformly chosen site. The question is whether local resampling has a dimension-independent spectral gap for fixed 0<β<10<\beta<1, and how mixing slows at the critical inverse temperature β=1\beta=1.

Eldan, Koehler and Zeitouni proved a constant heat-bath gap for β<1/4\beta<1/4, and Anari, Jain, Koehler, Pham and Vuong proved O(nlog⁡n)O(n\log n) mixing in discrete attempts in the same range, which Anari, Koehler and Vuong extended to β\beta up to about 0.2950.295. Wang proved worst-start mixing in Oβ(nlog⁡(n/ε))O_\beta(n\log(n/\varepsilon)) attempts for every fixed β<1/2\beta<1/2. Boban, Li and Oveis Gharan obtained a constant unscaled gap for β<1/2+ε0\beta<1/2+\varepsilon_0, with an absolute ε0≥5⋅10−5\varepsilon_0\ge5\cdot10^{-5}.

For every fixed 0<β<10<\beta<1, the preprint proves the existence of a finite CβC_\beta such that Var⁡μβ(f)≤Cβ𝒟β(f)\operatorname{Var}_{\mu_\beta}(f)\le C_\beta\mathcal D_\beta(f) for every real observable ff, on a disorder event whose probability tends to one as n→∞n\to\infty. The preprint derives a lower bound 1/(Cβn)1/(C_\beta n) for the spectral gap per discrete attempt on the same event.

The Lean library CriticalMixing formalizes the fixed-temperature Poincaré theorem with Cβ≥1C_\beta\ge1. At β=1\beta=1, the Lean library proves simultaneous mixing bounds at total-variation threshold 1/41/4: for every ε>0\varepsilon>0, the worst-start continuous mixing time and discrete update count lie in [n2/3−ε,eεn][n^{2/3-\varepsilon},e^{\varepsilon n}] and [n5/3−ε,eεn][n^{5/3-\varepsilon},e^{\varepsilon n}], respectively, with disorder probability tending to one. At deterministic nonnegative times o(n2/3)o(n^{2/3}), or deterministic update counts o(n5/3)o(n^{5/3}), the Lean library proves that the μ1\mu_1-mass of starts still at total-variation distance greater than 1/41/4 from equilibrium tends to one in disorder probability. The linear Rayleigh supremum is the supremum, over real coefficient vectors aa for which a𝖳xa^{\mathsf T}x is nonconstant, of Var⁡μ1(a𝖳x)/𝒟1(a𝖳x)\operatorname{Var}_{\mu_1}(a^{\mathsf T}x)/\mathcal D_1(a^{\mathsf T}x). For every deterministic positive sequence Mn→∞M_n\to\infty, the Lean library proves that the spin covariance operator norm and the linear Rayleigh supremum simultaneously lie in [n2/3/Mn,Mnn2/3][n^{2/3}/M_n,M_n n^{2/3}] with disorder probability tending to one. The Lean library bounds the linear Rayleigh supremum above by the full relaxation time for n>0n>0.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every one of them, so the Lean library is the reference: where the preprint states a result differently, the statement on the page is the Lean library’s, and the preprint’s is given beside it. The preprint gives the results their order and their names.