% low_temp_sk_glauber_typical_v2.txt
% A typical-start upper bound for low-temperature SK Glauber dynamics.
% Single-file clean rewrite. Read top to bottom.
usetikzlibrary{arrows.meta,calc,positioning}
allowdisplaybreaks
# A typical-start upper bound for low-temperatureSherrington--Kirkpatrick Glauber dynamics
maketitle
Abstract:
We study single-site heat-bath (Glauber) dynamics for the zero-field
Sherrington--Kirkpatrick spin glass at a fixed inverse temperature
beta>1. We prove that a configuration sampled from equilibrium mixes
to equilibrium in subexponential time: for every fixed beta>1 there
is a constant c_beta>0 such that, with probability tending to one
over the disorder and the starting configuration, the total-variation
distance from equilibrium is below 1/4 by time
exp(n^{1-c_beta}). The proof admits the explicit value
c_beta=1/40000000 for all fixed beta>1. The starting
configuration is held fixed before the distance to equilibrium is
measured; this is the essential subtlety, since averaging the start into
the law would make the distance zero at every time.
tableofcontents
%======================================================================
# Introduction
%======================================================================
## The question in plain terms
The SK model is a mean-field spin glass: n spins
sigma_iin{-1,1} interact through random pairwise couplings.
The heat-bath (Glauber) dynamics is the natural local sampler. Each site
has an independent rate-one clock; when the clock at site i rings,
the spin sigma_i is replaced by a fresh value drawn from its
conditional law given all the other spins. The chain has 2^n states
and is reversible with respect to the Gibbs measure pi^J_{n,beta}.
At high temperature the chain mixes quickly, in polynomial time
from every start. At low temperature (beta>1 in the
zero-field SK model) the landscape is glassy: there are deep valleys
separated by high barriers, and a configuration placed in the wrong
valley can take a very long time to escape. Sellke [cite]
shows the worst starting configuration can force an exponential
lower bound on the mixing time.
That leaves a sharper question. An adversarial start is unrealistic for
a sampler run on a freshly drawn instance. What happens if we start the
chain from a typical equilibrium configuration, i.e. from one
sample sigma_0simpi^J_{n,beta}? This paper answers the question
for every fixed beta>1: the chain is fast, at most subexponential in
n, from such a start.
Two conventions are essential and we fix them now.
[label=(roman*)]
The start is random and then held fixed. We first draw the
disorder J, then one configuration sigma_0simpi^J_{n,beta},
and only then look at the law P_t^{J,beta}(sigma_0,·) of the chain
started at that single sigma_0. The total-variation distance in the
mixing time is between this fixed-start law and pi^J_{n,beta}. If one
instead averaged sigma_0 into the starting distribution, stationarity
would force the distance to be zero at every time and the question would
vanish.
Time is continuous, one clock per site. Each site rings at
rate one, so the total jump rate of the chain is exactly n.
## The model
Let nge2 and let (J_{ij})_{1le i<jle n} be independent standard
Gaussian variables. Put J_{ji}=J_{ij} and J_{ii}=0. For a spin
configuration sigmain{-1,1}^n set
H^J_n(sigma)=frac1{sqrt n}sum_{i<j}J_{ij}sigma_isigma_j,
pi^J_{n,beta}(sigma)
=frac{exp(beta H^J_n(sigma))}{Z^J_{n,beta}},
where Z^J_{n,beta} is the normalizing constant. There is no external
field. The local field at site i is
[
h_i(sigma)=frac1{sqrt n}sum_{jne i}J_{ij}sigma_j .
]
When the clock at site i rings, the new value equals sin{-1,1}
with probability
P{new spin=smidsigma}
=frac{exp(beta s,h_i(sigma))}
{2cosh(beta h_i(sigma))} .
The update may leave sigma_i unchanged. Let
P_t^{J,beta}(sigma,·) denote the law at time t of this
continuous-time chain started from the fixed configuration sigma, and
let
T^J_{n,beta}(sigma)
=infBigl{tge0:
bigl|P_t^{J,beta}(sigma,·)-pi^J_{n,beta}bigr|_{TV}
letfrac14Bigr}
be the mixing time from that start. The joint law of interest samples
the disorder and one Gibbs configuration,
P_{J,,sigma_0simpi^J_{n,beta}}
=E_J,pi^J_{n,beta}.
## Main results
[Mixing from a typical Gibbs start]
For every fixed beta>1 there is a constant c_betain(0,1) such
that
[
P_{J,,sigma_0simpi^J_{n,beta}}Bigl{
T^J_{n,beta}(sigma_0)leexp(n^{1-c_beta})Bigr}
→ 1
(nto∞).
]
The constant may be taken as c_beta=1/40000000 uniformly over every
fixed beta>1, and it does not depend on the realized disorder.
Equivalently, in probability over the disorder J, the Gibbs mass of
the set of configurations whose mixing time is at most
exp(n^{1-c_beta}) tends to one. The exponent is not optimized, and
the dimension from which the estimates hold may depend on the fixed
beta; all such thresholds are absorbed into ``tending to one''.
The companion lower bound in [cite] gives a matching
stretched-exponential barrier. Combined with Theorem~thm:main it
produces a two-sided statement.
[Two-sided typical-start bound]
For every fixed beta>1, in the model and continuous-time convention
above,
[
P_{J,,sigma_0simpi^J_{n,beta}}Bigl{
exp(n^{1/10000})<T^J_{n,beta}(sigma_0)
leexp(n^{1-1/40000000})Bigr}
→ 1 .
]
Proof.
The continuous-time form of cite[Theorem~1.1]{OpenAISKBarriers2026}
states that, with joint probability tending to one,
|P^{J,beta}_{exp(n^{1/10000})}(sigma_0,·)-pi^J_{n,beta}|_{TV}>1/4
for sigma_0simpi^J_{n,beta}. By (eq:T) and continuity of the
finite-state semigroup this forces the strict lower bound
T^J_{n,beta}(sigma_0)>exp(n^{1/10000}). The upper bound is
Theorem~thm:main. Both events use the same joint law of
(J,sigma_0) and the same rate-one clocks, so their intersection has
probability tending to one.
## How the proof works
The proof has five logical stages. We describe each in words, then point
to its section.
[label=Stage arabic*.]
Equilibrium scalar inputs. The Parisi theory of the SK
model provides a scalar potential Phi and a magnetization martingale
whose variance in overlap space is dictated by the minimizing Parisi
measure. We state exactly which equilibrium inputs we use, in the
normalization of this paper. See Section~sec:scalar.
The long diffusion and its entropy--energy identity. We
continue the scalar diffusion past the endpoint of the Parisi support,
where the magnetizations pin down (level sets shrink exponentially). An
exact It^o calculation produces a scalar identity,
equation~(eq:scalar-balance), that balances the information
acquired by matrix queries against the energy gained. This is the engine
of the entropy bound. See Section~sec:scalar.
The Gaussian-query proposal. We build a random spin by
querying the matrix W=W(G) along orthogonalized directions. Each query
is conditionally Gaussian given the past and constructs a fresh
coordinate of a driving Brownian motion. The proposal Q_l has two
controlled features: sublinear relative entropy {rm KL}(Q_lVert P),
and a likelihood bound outside an exponentially unlikely event. See
Section~sec:proposal.
Reversing the entropy: coverage. Forward entropy alone says
nothing about reaching a prescribed set. Conditioning the Gibbs joint law
on the spin makes the remaining disorder law strongly log-concave; a
small Gaussian smoothing plus the quadratic transport inequality then
reverses the entropy comparison. The outcome is a coverage statement:
any Gibbs set of mass at least n^{-d} receives at least
exp(-n^{1-2d}) proposal mass for the realized target disorder and
smoothing base. See Section~sec:reverse.
Balancing flows and mixing. Two independent proposals joined
across a cut contradict the avoidance of a small boundary unless
every cut of appreciable Gibbs mass carries stationary flow at least
B_{min}=exp(-n^{1-b/20}). The geometry is elementary: a short
sequence of spins crossing a cut must contain a spin close to the
boundary. Fine-horizon spins supply endpoint coverage; coarse-horizon
spins have rare enough failures along the connecting sequence, and
rotating the Gaussian inputs makes consecutive coarse spins close in
Hamming distance. Then a finite-state pruning lemma and entropy
dissipation turn the flow bound into a statement about typical fixed
starting states. See Sections~sec:connections and~sec:mixing.
Theorems~thm:main and cor:two-sided are assembled from these
stages at the end of Section~sec:mixing.
## Relation to prior work
High-temperature, worst-start. Eldan, Koehler and Zeitouni
cite[Section~6]{EKZ2022} proved polynomial worst-start mixing for
beta<1/4. Wang cite[Theorem~1.1]{Wang2026} established optimal-order
Glauber mixing for every fixed beta<1/2, and Boban, Li and Oveis
Gharan cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
mixing in zero field to beta<1/2+ε_0 for some absolute
ε_0>0.
Low-temperature, worst-start. Sellke
cite[Theorem~1.1]{Sellke2025} proved exponential worst-start lower
bounds and distinguished the worst-start obstruction from fast mixing
after Gibbs-distributed start. Theorem~thm:main resolves the latter
throughout the fixed low-temperature phase.
Equilibrium Parisi theory. The stationarity conditions that drive
the argument come from the variational theory of the Parisi functional:
Chen cite[Theorem~2, Proposition~1]{Chen2017}, Jagannath and Tobasco
cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}, and Zhou
cite[Theorem~1]{Zhou2026}. For the whole low-temperature phase we use
full interval support from Lopatto cite[Theorem~1.1]{Lopatto2026}
(version~3). Guerra cite[Theorem~3]{Guerra2003} supplies the pressure
upper bound, and Auffinger--Chen cite[Propositions~1--2]{AC2015}
supplies spatial regularity and step-approximation stability of the
Parisi equation.
Techniques. The Gaussian-query construction is the exact
finite-dimensional analogue of Bolthausen's iterative TAP construction
cite[Sections~2--3]{Bolthausen2014} and of Montanari's incremental
approximate message passing cite[Sections~2--3]{Montanari2021}: query,
orthogonalize, reveal. The reverse-entropy step uses triangular transport
under strong convexity cite[Corollary~3.10]{BKM2005} together with the
convolution comparison recorded in cite[Lemma~11]{LugosiNeu2022}. The
mixing step combines the coarea proof of the reversible Cheeger
inequality cite[Theorem~3.5]{LawlerSokal1988} with entropy dissipation
for finite Markov chains cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}.
%======================================================================
# Notation and Gaussian completion
%======================================================================
Fix a finite beta>1. Constants may depend on this fixed parameter;
when that dependence matters we write C_beta or O_beta(·). All
logarithms are natural.
Distances and inner products.: For probability measures
mullnu on a common space, set
{rm KL}(muVertnu)=intlog(dmu/dnu),dmu. On the spin cube,
total variation is one half of the ell^1 distance. For vectors
v,winR^n write
[
< v,w>_n=frac1nsum_i v_i w_i,
|v|_n^2=< v,v>_n .
]
The symbols |v| and |A| denote the Euclidean norm of a vector and
the operator norm of a matrix.
The GOE completion.: A heat-bath update at site i never sees
J_{ii}. We complete the interaction matrix by adding independent
diagonal entries of law N(0,2/n): define a symmetric matrix W=W(G)
whose entries above the diagonal are W_{ij}=J_{ij}/sqrt n and whose
diagonal entries are independent N(0,2/n). Write G for the vector of
independent standard Gaussian drivers of all these entries and
gamma for its law. Since x_i^2=1 for every spin,
[
tfrac12,x^{T},x
=tfrac12sum_i W_{ii}
]
is the same random constant for every configuration. Hence the diagonal
contributes the same additive constant to every Gibbs weight; it changes
neither pi^J_{n,beta} nor any heat-bath rate nor the transition
kernel. Its effect on E F(G) is a deterministic constant that
we absorb into the pressure functional P below.
Gibbs weights on the completed matrix.: Define, with W=W(G),
[
widehatwidehat H_G(x)=H_G(x)=tfrac12 x^{T},x,
F(G)=logsum_{xin{-1,1}^n}e^{betawidehatwidehat H_G(x)}H_G(x),
pi_G(x)=e^{betawidehatwidehat H_G(x)-F(G)}H_G(x)-F(G).
]
Because the diagonal is a configuration-independent constant,
pi_G=pi^J_{n,beta} as probability measures. We work with
widehatwidehat H_GH_G everywhere. The Gibbs joint law of disorder and spin is
[
P(dG,x)=gamma(dG),pi_G(dx).
]
This is exactly the joint law of the starting configuration in
Theorem~thm:main. It is crucial that P is a joint law:
downstream we compare a proposal law Q_l to P on the joint
(G,x)-space. The transition kernel for a fixed disorder and a
fixed initial configuration is a different object, and the final
mixing argument must separate the two carefully.
%======================================================================
# Scalar inputs and the entropy--energy identity
%======================================================================
This section extracts the one-dimensional input that drives the whole
proof. The endpoint is Proposition~lem:scalar-balance
(equation~(eq:scalar-balance)): an exact scalar balance between the
energy a matrix-query proposal gains and the information it pays for.
Everything here is about a single diffusion and a few deterministic
functions of a scalar time; no high-dimensional geometry enters yet.
## Equilibrium inputs, stated once
Let mu_beta be a minimizing Parisi probability measure for the
zero-field Gaussian SK model at the fixed finite beta>1. We use the
following external inputs.
[leftmargin=*]
Pressure. Guerra's finite-volume interpolation bound
cite[Theorem~3]{Guerra2003}: E F(G)le nP, where
P is the Parisi pressure functional, whose exact
normalization we give below.
Regularity and stability. Auffinger--Chen
cite[Propositions~1--2]{AC2015}: the scalar Parisi equation has
continuous spatial derivatives, and its solution is stable under step
approximation of the CDF of mu_beta.
Full support and stationarity. Lopatto
cite[Theorem~1.1, Lemma~2.2, Proposition~2.4, Lemma~2.5]{Lopatto2026}:
the minimizing measure has full interval support,
[
supp(mu_beta)=[0,q_*], 0<q_*<1,
]
and the associated scalar solution obeys the stationarity identity used
in (eq:martingale) below.
The stationarity identity is also given, in the form we quote, in
Jagannath--Tobasco cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}.
What full support buys is precisely the ability to apply the identity at
every overlap in [0,q_*]; mere infinite support would not suffice.
## Normalization and the scalar Parisi equation
Use the scalar variance time v=beta^2 s with s the Parisi time
variable, and put alpha_v=mu_beta([0,v/beta^2]) for
0le vlebeta^2. Let Phi solve the backward Parisi equation
Phi_v=-tfrac12(Phi_{yy}+alpha_vPhi_y^2),
Phi(beta^2,y)=log(2cosh y),
with subscripts denoting derivatives. Equivalently, if u is the scalar
solution in [cite], then
Phi(v,y)=u(v/beta^2,y)+log2. Combining the independent ordered pair
couplings of the source gives the unordered pair coefficient
beta/sqrt n used in (eq:H), plus a centered diagonal term. Thus
this scalar normalization agrees with our completed Hamiltonian.
Set v_*=beta^2 q_*. The pressure functional and the finite-volume
upper bound read
P=,0)-frac1{2beta^2}int_0^{beta^2}valpha_v,dv,
E F(G)le nP .
The centered diagonal shifts neither P nor E F(G)
in any way that matters below. Since alpha_v=1 above v_*, the
Gaussian recursion gives, at v_*,
Phi(v_*,y)=log(2cosh y)+(beta^2-v_*)/(2) .
## Continuation past the support endpoint
For all v>v_* we continue the potential by the explicit formula
Phi(v,y)=log(2cosh y)+(beta^2-v)/(2),
alpha_v=1 .
This agrees with the original solution up to beta^2 and satisfies the
same PDE for every vge v_*. It describes the regime in which the
magnetizations pin down: the level sets of the magnetization
shrink and the spin becomes deterministic. Continue for every vge0
the two scalar functions
[
m(v,y)=Phi_y(v,y), a(v,y)=Phi_{yy}(v,y),
]
so that on the extension m(v,y)=tanh y and
a(v,y)=1-tanh^2 y.
Let Z be a standard Brownian motion and let Y solve
dY_v=alpha_v,m(v,Y_v),dv+dZ_v, Y_0=0 .
The drift is bounded and spatially Lipschitz, so the scalar SDE has a
unique strong solution. Abbreviate m_v=m(v,Y_v) and
a_v=a(v,Y_v). The stationarity identity, the differentiated PDE, and
It^o's formula give the key scalar facts
m_0=0, dm_v=a_v,dZ_v,
E m_v^2=(v)/(beta^2)(0le vle v_*),
and this martingale equation continues past v_* by direct It^o
calculus with the explicit functions (eq:phi-extension). We use,
repeatedly, the deterministic bounds
0<a(v,y)le1-m(v,y)^2le1, |m(v,y)|<1 .
Why (eq:a-m-bound) holds. We derive it in the form that
behaves well under step approximation. One Parisi step of CDF height
lambdain[0,1] and variance delta>0 maps a profile f to
[
(Tf)(y)=frac1lambdalogE,
e^{lambda f(y+sqrtdelta U)}, Usim N(0,1),
]
with Tf(y)=E f(y+sqrtdelta U) when lambda=0. Write
E_ for the Gaussian expectation tilted by
e^{lambda f(y+sqrtdelta U)} and renormalized. Differentiating gives
the exact formulas
[
(Tf)'=E_ f',
(Tf)''=E_ f''+lambdaVar_lambda(f') .
]
Suppose 0<f''le1-(f')^2. Then
[
0<(Tf)''le1-((Tf)')^2-(1-lambda)Var_lambda(f')
le1-((Tf)')^2 .
]
Inducting from f(y)=log(2cosh y) proves the bound for step CDFs;
stability cite[Propositions~1--2]{AC2015} passes the non-strict bound to
the minimizing CDF, and the strict lower bound on Phi_{yy} in
cite[Proposition~2.4]{Lopatto2026} gives strict positivity in the limit.
Hence m is strictly increasing and |m|<1, giving
(eq:a-m-bound). On the extension these assertions follow from
tanh directly.
## Tail estimates for the extended diffusion
Define the three deterministic functions
p(v)=E a_v, r(v)=E a_v^2,
rho(v)=beta√(r(v)) .
The martingale second-moment identity (eq:martingale) and
continuity give r(v)=1/beta^2 on [0,v_*], endpoints included. The
next lemma controls the continuation and confirms that rho is an
admissible noise-mixing coefficient in [0,1].
[Scalar tail bounds]
For vge v_* the extended diffusion obeys
rho(v)le1, -2le(log r)'(v)le0,
p'(v)=-r(v),
p(v)le C_beta e^{-v/2} .
At v=v_* the derivatives are from the right.
Proof.
We use the transformed-density method of
cite[Proposition~7.1]{Lopatto2026} and the moment comparison of
cite[Proposition~9.3]{Lopatto2026}, which together give the required
estimates for the arbitrary-time continuation.
Two moment ratios. For v>v_*, the density of Y_v divided by
cosh y is symmetric and nonincreasing in |y|. It suffices to check
this for step CDFs and pass to the limit; stability
cite[Propositions~1--2]{AC2015} justifies the passage. For a step CDF
with masses alpha^{(j)} on intervals [v_j,v_{j+1}], and
phi_t the centered Gaussian density of variance t, the transition
density on one interval is
[
K_j(z,y)=phi_{v_{j+1}-v_j}(y-z)
expbigl{alpha^{(j)}[Phi(v_{j+1},y)-Phi(v_j,z)]bigr} .
]
The Gaussian recursion normalizes K_j; its Doob transform has drift
alpha^{(j)}Phi_y. In a product of kernels the intermediate factors at
y_j reduce to
[
expbigl{-(alpha^{(j)}-alpha^{(j-1)})Phi(v_j,y_j)bigr},
]
which is even and nonincreasing in |y_j| because the masses are
nondecreasing and Phi is even and convex. The first positive-time
Gaussian convolution turns the initial point mass at zero into a
symmetric decreasing density, and multiplication by these factors plus
further Gaussian convolutions preserve that property (using the
centered-interval level-set representation of a symmetric decreasing
profile). Extending the final mass to one leaves an endpoint factor
proportional to cosh y; dividing by it leaves the asserted symmetric
decreasing profile.
Weighting either sechy or sech^3y by a
decreasing profile can only increase the expectation of
sech^2y, since two nonincreasing functions of |y| have
nonnegative covariance. Integration by parts gives
[
frac{int_{R}{k+2}y,dy}
{int_{R}{k}y,dy}
=(k)/(k+1)(k>0).
]
Consequently r/pge1/2 and E a_v^3/r(v)ge3/4.
Differential identities. On the extension a_v=1-m_v^2, and
direct It^o calculations yield
[
p'=-r, r'=4r-6,E a_v^3 .
]
The two moment ratios imply p'le-p/2 and r'le0. Since
0<a_vle1, the second identity also gives r'ge-2r. Integrating
p'le-p/2 gives p(v)le C_beta e^{-v/2}. Finally
r(v_*)=1/beta^2 and monotonicity of r imply rhole1.
## The entropy--energy identity
Let H(z) be the entropy of a sign with mean zin(-1,1):
[
H(z)=-(1+z)/(2)calH(z)=-(1+z)/(2)log(1+z)/(2)
-(1-z)/(2)log(1-z)/(2),
]
with continuous values at z=pm1. For V>v_* define the two scalars
that will be the energy per spin and the information cost per spin of the
matrix proposal:
e(V)=int_0^V√(r(v)),p(v),rho(v),dv,
j(V)=frac12int_0^Vrho(v)^2,
E(a_v^2)/(1-m_v^2)bbE(a_v^2)/(1-m_v^2),dv .
The factor rho(v)^2 inside j accounts for the independent noise we
introduce in the proposal. Below the support endpoint, It^o's formula
together with the PDE and stationarity gives
[
E[Y_bbE[Y_{v_*}m_{v_*}]=int_0^{v_*}(p(v)+alpha_v v/beta^2),dv,
E*,Y_{v_*})=Phi(0,0)
+frac12int_0^{v_*}alpha_v v/beta^2,dv .
]
These also follow by step approximation with bounded first and second
spatial derivatives. Substituting the endpoint value (eq:phi-at-vstar)
and using H(tanh y)=log(2cosh y)-ytanh y gives
int_0^{v_*}p(v),dv+E,H(m_{v_*})
=P-(calP-(beta^2)/(4)(1-q_*)^2 .
[Entropy--energy identity]
For every V>v_*,
log2-j(V)+beta e(V)=P-(calP-(beta^2)/(4),p(V)^2 .
Proof.
The same martingale calculation applied to binary entropy yields
[
frac12int_0^{v_*}E(a_v^2)/(1-m_v^2)bbE(a_v^2)/(1-m_v^2),dv
=log2-E,H(m_{v_*}).
]
Localization justifies It^o's formula near z=pm1; the integrand is
bounded because ale1-m^2. Since rho=1 and betasqrt r=1 on
[0,v_*], the two identities above prove (eq:scalar-balance) at
V=v_*. Above v_* the derivative of the left side of
(eq:scalar-balance) is (beta^2/2),r(v),p(v): indeed
a_v=1-m_v^2 there, and rho^2=beta^2 r. The derivative of
-beta^2p(v)^2/4 is the same, by p'=-r. Integrating from v_*
therefore proves the claim for every V>v_*.
The terminal error (beta^2)/(4)p(V)^2 on the right of
(eq:scalar-balance) is at most C_beta e^{-V} by
(eq:1). We take V proportional to log n, so this error is a
negative power of n while the spin is nearly pinned.
%======================================================================
# The Gaussian-query proposal
%======================================================================
We now build a random spin using the matrix W=W(G) together with
auxiliary randomness. The construction has a single design principle:
each query of the matrix is orthogonal to the earlier queries and
is independent given the past. This exposes fresh Gaussian information
while leaving a compressed GOE block unrevealed, so that a clean
conditional-Gaussian argument applies at every step. The scalar identity
(eq:scalar-balance) will then control both the relative entropy of
the resulting law Q_l and its likelihood outside a small exceptional
event.
The spirit is the same as Bolthausen's iterative TAP construction
cite[Sections~2--3]{Bolthausen2014} and Montanari's incremental
approximate message passing cite[Sections~2--3]{Montanari2021}, both of
which reveal Gaussian information along orthogonalized directions. What
is new here is the exact conditional-law bookkeeping for a finite
mesh, including the independent auxiliary noises that complete each
increment.
## Construction and conditional Gaussian laws
Mesh.: Fix a horizon parameterfootnote{We use the letter
l both for the horizon parameter and, later, for the horizon value.
Context disambiguates. The final paper uses l=f for fine coverage and
l=b for the coarse connecting sequence; see Section~sec:reverse.}
0<lle1/100 and set
h=n^{-1/16}, K=lceil llog n/hrceil,
t_k=kh, V=t_K .
For all sufficiently large n, K<n, and V>v_* with v_* the support
endpoint of Section~sec:scalar.
The two driving streams.: The disorder G retains its ordinary
Gaussian law gamma. We build a vector-valued process whose coordinates
follow the scalar SDE (eq:Y), driven by two independent streams,
dZ=rho(v),dB+√(1-rho(v)^2),dD .
Here D is an auxiliary standard Brownian motion, independent of
everything; B is to be constructed from matrix queries together with
auxiliary completions so that, after averaging over the disorder, (B,D)
is a standard Brownian pair. By (eq:1) the weight rhole1 equals
one up to v_* and is nonincreasing afterwards; this is exactly what
keeps the level sets pinning while retaining unit variance in Z. Write
M(v)_i=m(v,Y_{v,i}).
Building B.: On the first interval [0,h] we generate B
entirely from independent auxiliary Brownian noise. For each subsequent
interval [t_k,t_{k+1}], 1le k<K, the previous scalar increment
determines
s_k^2=int_{t_{k-1}}^{t_k}r(v),dv,
T_k=frac{M(t_k)-M(t_{k-1})}{s_k} .
Project T_k off the preceding query directions u_1,...,u_{k-1} and
normalize the residual to obtain |u_k|_n=1. If the residual is exactly
zero, choose a new direction measurably from the past: project the
coordinate basis vectors in their fixed order, take the first nonzero
projection, and normalize it. Since k<n, such a direction always
exists. Let Pi_{le k} be the orthogonal projection onto the span
through u_k, and Pi_{>k}=I-Pi_{le k}.
Query the column Wu_k. For an independent standard Gaussian vector
z_k, set the endpoint of the next Brownian increment to be
g_k=h^{-1/2}(B(t_{k+1})-B(t_k))
=Pi_{>k}Wu_k+Pi_{le k}z_k .
Fill the interval by linear interpolation between its endpoints plus an
independent centered Brownian bridge. Every new bridge and completion
noise is fresh. A deterministic-coefficient integral against this filled
path may equivalently be obtained by conditioning Brownian motion on its
endpoint.
The spin.: At time V, given the path, draw the coordinates
x_iin{-1,1} independently with means M_i(V). Let Q_l be the
marginal law of (G,x) produced this way.
Why (B,D) is a standard Brownian pair.: Condition on the
columns already revealed and on the auxiliary inputs already used.
Gaussian orthogonal invariance leaves the unqueried block a GOE matrix on
the orthogonal complement, with the original variance scale. The next
direction u_k is measurable with respect to this past. In an
orthonormal basis beginning with u_k/sqrt n, the new diagonal entry,
the remaining entries of that column, and the next compressed block are
independent. Hence Pi_{>k}Wu_k is a fresh Gaussian with covariance
Pi_{>k}, and
[
d_k=< u_k,Wu_k>_nsim N(0,2/n)
]
conditionally, before the column is revealed. The independent completion
has covariance Pi_{le k}, so g_k in (eq:gk) is a fresh
standard Gaussian vector. Induction, followed by the independent bridge
filling, proves that (B,D) in (eq:4) is a standard Brownian pair.
Coordinate symmetry.: After forgetting the matrix, the
coordinate paths and their final spins are i.i.d. The conditional mean of
x given the streams through time v is M(v), and its unconditional
law is uniform on the cube by the symmetry of the scalar process. The
spin marginal of P is also uniform, by coordinate-sign symmetry of the
disorder. Both are facts about marginals; the proposal spin remains
correlated with its own matrix.
## Entropy and likelihood estimates
The next proposition supplies two distinct comparisons. Entropy will
yield coverage after smoothing; the likelihood estimate will keep
intermediate proposals out of the small boundary of a putative low-flow
cut. Both are stated for the joint law Q_l on (G,x)-space.
[Proposal comparison]
For every fixed 0<lle1/100 and all sufficiently large n,
{rm KL}(Q_lVert P)le2n^{1-l/2} .
Moreover, there is an event in the proposal experiment of probability at
least 1-exp(-n^{1-10l}) such that the output subprobability
restricted to this event is dominated on (G,x)-space by
exp(n^{1-l/2}),P .
The good event is determined entirely by the inputs of this one proposal
run. Finally, the empirical Gram matrix of the T_k is within n^{-l} of
the identity in operator norm, except with probability at most
exp(-n^{1-10l}). The dimension from which all this holds may depend on
the fixed l.
Proof.
Put eta=n^{-l}. We evaluate the proposal energy from empirical inner
products, then compute the information cost of its matrix channel, and
combine with the pressure bound and the scalar identity
(eq:scalar-balance).
Empirical inner products.: Form the empirical matrix of all
normalized inner products among T_k,g_k (1le k<K) and x. It is an
average of n i.i.d. row outer products, by the coordinate law above.
Every unit linear form of a row is sub-Gaussian with norm at most
C_beta e^V. For the T_k part, use their disjoint martingale
increments, |a|le1, and
s_k^2ge c_beta h,e^{-2V},
which follows from (eq:1). An exponential martingale estimate
bounds the linear form by its deterministic quadratic-variation bound.
The g_k part is Gaussian and the spin term is bounded; the correlations
with the first part do not affect the resulting sub-Gaussian bound: for
squared linear forms the moments are bounded by
k!,(C_beta e^{2V})^k, and expanding the centered exponential moment
followed by exponential Markov gives, at deviation scale eta/2, a
quadratic-form tail
[
2exp(-c_beta neta^2e^{-4V}).
]
A 1/4-net of the unit sphere in dimension O(K) has exp(O(K))
points, by ball packing. The quadratic-form norm inequality and a union
bound therefore put the whole empirical matrix within eta of its
expectation, with exceptional probability at most exp(-n^{1-8l}).
The population identities are
E[T_jT_k]_bbE[T_jT_k]_{rm row}=mathbf1_bf1_{j=k},
E[T_jg_k]_bbE[T_jg_k]_{rm row}=0 (jle k),
E[T_kx]_bbE[T_kx]_{rm row}=s_k,
E[g_kx]_bbE[g_kx]_{rm row}=b_k,
where
b_k=h^{-1/2}int_{t_k}^{t_{k+1}}p(v)rho(v),dv. These follow from the
martingale bracket, the conditional mean of the final spin, and
(eq:4). The vectors s=(s_k) and b=(b_k) each have Euclidean
norm at most one, by projection of the unit-variance spin onto the
corresponding orthonormal scalar variables.
Triangular Cholesky and matrix norms.: We need a matrix-norm
estimate that does not lose a factor K under orthogonalization. Taking
the triangular part of an mtimes m matrix costs at most Clog(2m) in
operator norm: pad to a power of two and partition the strict triangle by
dyadic scales; at each scale the rectangles have disjoint row and column
sets, so retaining that scale is contractive; summing over scales proves
the bound.
Let A be a Gram matrix with |A-I|leeta<1/2, and let
R^{T} be its upper Cholesky factor. Along
A(t)=I+t(A-I), differentiation shows that dot RR^{-1} is the upper
triangular part, with half the diagonal, of
R^{-T} AR^{-1}. The norms of R and R^{-1} are uniformly
bounded; the preceding triangular estimate plus integration give
[
|R-I|le Cetalog(2m).
]
(Differentiability follows directly from the triangular Cholesky
recursion.)
Apply this with the Gram matrix of the T_k. The query matrix with
columns u_k is the matrix with columns T_k multiplied by R^{-1}. So,
writing c_k=< u_k,x>_n, the empirical event gives
[
|c-s|&le Cetalog(2K),
left|(mathbf1_bf1_{jle k}< u_j,g_k>_n)_{jk}right|
&le Cetalog(2K),
bigl|(< g_k,x>_n)_k-bbigr|&leeta .
]
The middle estimate uses that left multiplication of the population cross
matrix by the lower-triangular R^{-T} preserves its zero upper
triangle, including the diagonal. Also |c|le1, because the query
directions are orthonormal in |·|_n.
Energy of the final spin.: Let H_0=Pi_{>K-1}. Revealing the
columns in order decomposes the quadratic form exactly as
[
frac{widehatwidehat H_G(x)}H_G(x)n
=sum_kc_k< x,Pi_{>k}g_k>_n
+tfrac12sum_kc_k^2d_k
+tfrac12< x,H_0WH_0x>_n .
]
The last two terms are O(eta) outside an event of probability at most
CKexp(-cneta^2): the diagonal estimate follows from the conditional
Gaussian law and sum c_k^2le1, while the residual term uses that the
spin has not seen the unrevealed block. Removing the projections in the
first term costs at most Cetalog(2K) by the triangular bound. Its
remaining value is s· b up to the same error. The bound on
(log r)' in (eq:1) implies s_k/sqrt h differs from
√(r(v)) on [t_k,t_{k+1}] by a relative O(h). The missing initial
interval contributes O(h), and e(V) is bounded. Hence s· b=e(V)+O_beta(h),
and altogether
widehatwidehat H_G(x)/n=e(V)+O_H_G(x)/n=e(V)+O_beta(h+etalog(2K)).
This is the energy contribution to the comparison. We next isolate the
entropy paid for the matrix information alone.
The auxiliary reference law.: Start on an enlarged path space
with an independent uniform spin x, the ordinary Gaussian disorder, and
all unconditioned proposal inputs. Call this the unlinked
experiment. To obtain the actual proposal, multiply the density of the
unlinked experiment by
[
prod_i(1+x_i,m(V,Y_{V,i})).
]
For fixed x, the scalar martingale shows this is a stochastic
exponential with coordinate integrands
[
xi_i(v)=frac{x_i,a(v,Y_{v,i})}{1+x_i,m(v,Y_{v,i})},
|xi_i(v)|le2,
]
against the streams Z_i in (eq:4). Call the resulting law the
linked experiment. Summing the linking density over the uniform
spin shows the path and disorder marginal is unchanged.
For a continuous local martingale N starting at zero write
E(N)_V=-< N>_V/2). The linking density
factors as E_BE_D with
[
E_B&=E({·}xi_irho,dB_i)_V,
E_D&=E({·}xi_i√(1-rho^2),dD_i)_V,
]
using the zero quadratic covariation of B and D. Define the
auxiliary reference to have density E_D relative to the unlinked
law. Its (G,x)-marginal is again the independent product of Gaussian
disorder and uniform spin. The conditional mean-one assertion behind this
fact needs a filtration check, since the matrix-query endpoints depend on
the past of D.
Filtration check.: Let A contain all primitive
auxiliary inputs except D, and under the unlinked law set
[
F_v=,B_{[0,v]},D_{[0,v]}),
G_v=,G,A,D_calA,D_{[0,v]}).
]
Interval by interval, every query direction is determined by past D and
by information in G_0. Each new endpoint and its entire bridge
are known before using the current D-increment. Deterministic-coefficient
bridge integrals are linear Gaussian integrals with the endpoint term
fixed by that past. Thus F_v⊆calF_v⊆G_v. One can
also see this pathwise: rho=1 before v_*, and (eq:1) gives
-rholerho'le0 afterward, so rho has bounded variation and the
identity intrho,dB=rho B-int B,drho, applied on successive
intervals, uses no future D.
The pair (B,D) is Brownian in F, and D is Brownian in
G because its time-zero information is independent of D. The
bounded continuous D-integrand has the same stochastic integral in
these two filtrations: identical left-endpoint approximations converge in
L^2 by the It^o isometry. The bounded-integrand exponential-martingale
theorem in G now gives conditional mean one given
(x,G,A), proving the claimed marginal. All later Brownian
changes of measure use F; no Brownian property for B in the
enlarged filtration is required.
Information cost and likelihood.: The density of the linked
experiment relative to the auxiliary reference is E_B, whose logarithm
is
[
L=log E_B=sum_i(int_0^Vxi_irho,dB_i
-tfrac12int_0^Vxi_i^2rho^2,dv).
]
Under the linked law, compensating the B_i-drift by rhoxi_i leaves
a centered integral with bracket at most 4nV, so it has
exponential-martingale tails. The remaining half-bracket is a sum of
independent coordinate variables, each bounded by 2V. Coordinate
independence holds after linking because the linking density factors
across the i.i.d. coordinate streams and uniform spins; conditionally on
the streams through time v, the linked spin has probabilities
(1pm m(v,Y_{v,i}))/2. We obtain
E L=nj(V), L=nj(V)+O(neta),
outside an event of probability at most exp(-n^{1-4l}) for large n.
The centered integral is controlled by exponential Markov; the
half-bracket by bounded-variable concentration. The Brownian drift change
follows either from Girsanov's theorem for bounded integrands, or from
bounded predictable step approximation together with the mean-one
exponential identities.
Changing the reference to P.: Change the auxiliary reference a
second time, multiplying only by the density of P relative to
independent disorder and uniform spin. The new reference has
(G,x)-marginal P, and the log density of the linked experiment
relative to it is
[
L-nlog2+F(G)-betawidehatwidehat H_G(x).H_G(x).
]
Differentiating the log partition function gives a Gaussian Lipschitz
constant at most C_betasqrt n. The Gaussian concentration inequality
cite[Section~5.4, Theorem~5.6]{BLM2013} together with the pressure bound
(eq:pressure) therefore implies
[
F(G)le nP+ncalP+neta
]
outside an event of probability at most 2exp(-c_beta neta^2). This
uses the ordinary Gaussian marginal of G, which is unchanged after
linking.
Substituting the scalars.: Insert (eq:scalar-balance),
(eq:7), p(V)^2le C_beta e^{-V} and (eq:L-conc) into the log
density. On the events just proved it is at most
[
C_beta n(h+etalog(2K)+e^{-V})=o(n^{1-l/2}).
]
Indeed V=llog n+O(h), log(2K)=O(log n), and
0<lle1/100<1/16. The union of the exceptional events has probability
at most exp(-n^{1-10l}) for sufficiently large n. Taking the
restricted output marginal gives (eq:6), and its good event is
defined entirely from the inputs of this one proposal run.
The entropy bound.: The same comparison in expectation proves
(eq:5) by contraction of relative entropy under marginalization. The
exceptional paths contribute negligibly: L has second moment
O(n^2(1+V)^2), and the supremum of the absolute spin energies has second
moment O(n^2) by Gaussian tails and a union bound. The log partition
function is bounded by nlog2 plus that energy supremum. Cauchy--Schwarz
controls all exceptional contributions. The Gram estimate was already
established.
%======================================================================
# Reversing the entropy: coverage
%======================================================================
Proposition~prop:proposal controls {rm KL}(Q_lVert P), the
entropy cost of producing a proposal spin. But entropy in the
forward direction is not enough: a set of large Gibbs mass might still
receive negligible proposal mass, and we will need in
Section~sec:connections that a proposed spin reaches such a set with
appreciable probability. We therefore need a reverse comparison.
The idea is to condition the Gibbs joint law on the spin. With the spin
fixed, the remaining law of the disorder is strongly log-concave. A small
Gaussian smoothing then turns the forward comparison into the reverse one
via the quadratic transport inequality.
## Horizons and the smoothing map
For the rest of the proof fix the four exponents
f=frac1{100}, d=frac f{100}=frac1{10000},
b=frac d{100}=frac1{1000000}, delta=n^{-f/4}.
The relation bll dll f is the whole hierarchy. The longer horizon
l=f is used for coverage: it is the one whose proposal mass on Gibbs
sets will be bounded below. The shorter horizon l=b is reserved for the
connecting sequence in Section~sec:connections: its exceptional-event
estimate exp(-n^{1-10b}) is far stronger, even though its entropy bound
(eq:5) is weaker.
[Smoothing map S]calS]
For any joint law of disorder and spin, let S retain the spin
and replace its disorder by
G^circ=√(1-delta),G+sqrtdelta,barbar G,G,
where barbar GGsimgamma is independent of everything.
Both SP and SQ_f have standard Gaussian disorder
marginal. To generate the conditional spin kernel nu(·mid G^circ)
of SQ_f given the smoothed disorder, use Gaussian regression:
given G^circ, run the l=f proposal on
[
√(1-delta),G^circ+sqrtdelta,G'
]
with fresh independent standard Gaussian G' and fresh independent
auxiliary inputs. This is the conditional law of the proposal given the
smoothed disorder, by the Bayes rule for Gaussian vectors.
## Why smoothing reverses the entropy comparison
The central reverse inequality is the following.
[Smoothing reverses KL]
{rm KL}(SP SQ_f)calSQ_f)
ledelta^{-1},{rm KL}(Q_fVert P) .
Proof.
The two unsmoothed laws have the same uniform spin marginal (see
Section~sec:proposal). Given x, the conditional disorder density
of P has negative logarithm, up to a normalizing constant,
[
U_x(G)=tfrac12|G|^2-betawidehatwidehat H_G(x)+F(G).H_G(x)+F(G).
]
Its Hessian is at least the identity: the Hamiltonian is linear in G
(hence contributes nothing to the Hessian), and F is a convex
log-sum-exp of linear functions.
We use the following consequence of strong convexity. Suppose mu has
density proportional to e^{-U} with nabla^2Uge I, and lambdallmu.
Then there are couplings of mu,lambda whose mean squared displacement
is at most 2{rm KL}(lambdaVertmu) (or tends to that bound). This is
the quadratic transport inequality; the triangular-transport form is
cite[Corollary~3.10]{BKM2005}. We recall the proof for the
finite-dimensional densities used here.
Transport bound on a box. Restrict to a box and suppose both
densities are smooth and strictly positive up to its boundary. Map mu
to lambda by successive increasing conditional quantile maps. The
resulting triangular map T has positive diagonal derivatives, whose
product is its Jacobian determinant. The entropy formula is
[
{rm KL}(lambdaVertmu)
=int(U(T(z))-U(z)-logdetnabla T(z)),dmu(z).
]
Strong convexity bounds the first difference below by
nabla U(z)·(T(z)-z)+tfrac12|T(z)-z|^2. Integration by parts
replaces the linear term by div(T-id). There is
no boundary term: on a face where the i-th coordinate is an endpoint of
the box, the conditional quantile map fixes that endpoint, so the normal
component T_i-z_i vanishes; tangential motion does not matter. The
Jacobian terms are nonnegative because z-1-log zge0 for every positive
diagonal derivative z. This proves the coupling bound on the box.
Approximation. For fixed n, the conditional proposal density is
bounded by a constant times a Gaussian density, since its spin probability
is at most one. Truncate both conditional laws to increasing boxes and
normalize them. On each box, approximate lambda by smoothing and mixing
with a small positive constant density; the smooth reference density is
bounded away from zero on the box, so the relative entropies with respect
to the reference converge. The original laws have Gaussian tails up to
constants for fixed n and finite relative entropy. Thus the truncated
entropies converge, and tightness plus lower semicontinuity pass the
coupling bound to the original laws.
Applying to P and Q_f. Apply the transport bound with
mu=P(·mid x) and lambda=Q_f(·mid x). For any coupling of
two disorder values g,widetilde g, the Gaussian smoothing kernels
satisfy
[
{rm KL}(N(√(1-delta),g,delta I)
Vert N(√(1-delta),widetilde g,delta I))
=(1-delta)/(2delta)|g-widetilde g|^2 .
]
The convolution comparison is also recorded in
cite[Lemma~11]{LugosiNeu2022}. Joint convexity of entropy bounds the
divergence between the mixtures by this averaged kernel quantity. Average
over the common spin marginal and use the entropy chain rule. The
transport bound then proves (eq:8).
## Coverage conditional on a target and its base
The smoothed entropy comparison (eq:8) is a joint-law statement. We
now extract a statement for the original Gibbs law at a realized target
disorder G, using only the base G^circ that we also sample. The
following proposition records both the expected entropy estimate and the
coverage consequence used in the next section.
[Coverage at a target disorder]
Let G,barbar GG be independent standard Gaussian disorder vectors, set
G^circ=√(1-delta),G+sqrtdelta,barbar G,G, and let
nu(·mid G^circ) be the conditional spin kernel of
SQ_f (eq:smoothing). Then
E,{rm KL}(pi_GVertnu(·mid G^circ))
le O_beta(nsqrtdelta)+2n^{1-f/2}/delta .
With probability tending to one over the target/base pair,
{rm KL}(pi_GVertnu(·mid G^circ))le n^{1-4d} .
On the same event, simultaneously for every set
A⊆{-1,1}^n with pi_G(A)ge n^{-d},
nu(Amid G^circ)geexp(-n^{1-2d}).
The set A may be chosen after the target and base are realized.
Proof.
Let overlinepi(·mid G^circ) be the conditional spin law of
SP, the conditional mixture of pi_G over the target that
produced the base G^circ. Inserting this law into the logarithmic ratio
gives the exact decomposition
[
E,{rm KL}(pi_GVertnu(·mid G^circ))
&=E,{rm KL}(pi_GVert
overlinepi(·mid G^circ))
&+{rm KL}(SP SQ_f).calSQ_f).
]
Both expectations are over the target/base pair (G,G^circ) of the
statement. The conditional mixture minimizes averaged divergence among
spin laws depending only on the base, so the first term on the right is
at most E,{rm KL}(pi_GVertpi_{G^circ}).
For any two Hamiltonians, the Gibbs divergence is bounded by twice beta
times the supremum of their absolute energy difference. Here those
differences, for each fixed spin, are centered Gaussians of variance
O(ndelta): the smoothed and unsmoothed disorders differ by coordinate
strength O(sqrtdelta) on sqrt n-scale couplings. A union bound over
the 2^n spins, or an exponential moment argument, bounds the expected
supremum by O(nsqrtdelta). Combining this estimate with (eq:8)
and (eq:5) proves (eq:9).
The power-of-n event. Since 4d<f/8 and 4d<f/4 (recall
d=f/100 and f=1/100), Markov's inequality applied to (eq:9) gives
(eq:10) with probability tending to one.
Coverage from the entropy. On the single event (eq:10),
let A be any set with pi_G(A)ge n^{-d}. For s=pi_G(A) and
t=nu(Amid G^circ), entropy contraction to the two-point partition
gives slog(1/t)le{rm KL}(pi_GVertnu)+log2. Hence
[
log(1/t)le n^d(n^{1-4d}+log2)le n^{1-2d}
]
for sufficiently large n. The implication is deterministic once the
target and base are fixed, which proves the simultaneous assertion
(eq:cov).
Note that the coverage bound (eq:cov) deteriorates with
d, but this cost is well within the slack that the mixing argument
needs. The choice bll d in (eq:exponents) is exactly what makes
the connecting-sequence exception
exp(-n^{1-10b}) in Section~sec:connections smaller than the
coverage probability exp(-n^{1-2d}).
%======================================================================
# Connecting proposals across a cut
%======================================================================
This is the combinatorial heart of the proof. Everything so far has been
about a single proposal. We now plant two proposals on either side
of a putative low-flow cut and force a contradiction with an elementary
geometric fact: a short sequence of spin flips that crosses a cut must
pass near the boundary.
## Setup and statement
For distinct spins x,y, write c_G(x,y) for the heat-bath jump rate and
[
Q_G^{rm edge}(S,S^{rm c})
=sum_{xin S,,ynotin S}pi_G(x),c_G(x,y)
]
for the stationary flow of the chain across the set S. Detailed balance
makes the edge weights symmetric, so this flow is the reversible measure
of the cut; it is also the quantity the mixing Lemma~lem:pruning
of the next section uses.
[Balanced-cut flow]
With probability tending to one in the target disorder,
Q_G^{rm edge}(S,S^{rm c})>B_{min}:=exp(-n^{1-b/20})
quadfor every S with
min(pi_G(S),pi_G(S^{rm c}))ge n^{-d}.
Proof.
We split the argument into (a) the geometry of a putative low-flow cut,
(b) the construction of a proposal sequence, and (c) two estimates that
make this sequence impossible.
## A low-flow cut has a small enlarged boundary
For a sufficiently large fixed C, Gaussian quadratic-form tails on a
1/4-net give |W(G)|le C except with probability O(e^{-cn}). On this
event every one-spin energy difference is O(sqrt n), because flipping a
single spin changes x^{T}/2 by an O(|W|sqrt n) amount. The
heat-bath rate across any one-spin edge is therefore at least
exp(-O_beta(sqrt n)).
If a cut has stationary flow at most B_{min}, then its two-sided vertex
boundary
[
∂ S={x:,d_H(x,S)=1 and d_H(x,S^{rm c})=1}
]
has Gibbs mass at most 2B_{min}exp(O_beta(sqrt n)), since each
boundary vertex controls at most 2n unit-rate crossings each carrying a
heat-bath acceptance probability at least exp(-O_beta(sqrt n)).
Set R_n=lceil n^{1-b/4}rceil and enlarge ∂ S by Hamming
distance R_n. For two spins at Hamming distance at most R_n and with
|W(G)|le C, the logarithmic Gibbs weight ratio is bounded by
O_beta(n^{1-b/8}): the change in widehatwidehat H_GH_G along any path of
R_n flips is at most Csqrt n· R_n/sqrt n· n^{1/2}=O_beta(n^{1-b/8}),
and a Hamming ball of radius R_n has logarithmic cardinality
O(n^{1-b/4}log n). The enlarged boundary
D_R(G) therefore has target Gibbs mass at most
exp(-tfrac12 n^{1-b/20})
for n large, since 1-b/20<1-b/8 and b/20<b/4.
Among cuts violating (eq:11), select the first one in a fixed ordering
of the subsets of the cube whenever such a cut exists and |W(G)|le C.
Let D(G) be its enlarged boundary, and set
D(G)=∅calD(G)=∅ if no such cut exists or the norm bound fails.
This is measurable because the cube has finitely many subsets. Let
E be the event that a witness cut exists, the target-norm bound
holds, and the coverage statement (eq:10) holds for the sampled
base G^circ. The norm and coverage estimates reduce
(eq:11) to showing Pr(E)=o(1).
## A sequence with independent fine endpoints
The fine horizon l=f and the coarse horizon l=b serve distinct
purposes.
[leftmargin=*]
Fine horizon supplies coverage. On E, the coverage
statement (eq:cov) gives each side of the cut fine-proposal
probability at least exp(-n^{1-2d}). Two conditionally independent
fine endpoints therefore cross the cut with probability at least
exp(-2n^{1-2d}).
Coarse horizon supplies rare failures. We need an unconditional
bound on the failure probability of the connecting sequence that is
smaller than the endpoint-coverage probability. The fine-horizon
exceptional-event bound of Proposition~prop:proposal is
exp(-n^{1-10f}), which is too weak: 10fgg d. The coarse bound
exp(-n^{1-10b}) is strong enough, since 10bll dll2d.
We therefore use fine spins at the two endpoints for coverage, and
coarse spins along a grid for the connecting sequence. The shared
path prefixes plus the magnetization martingale keep each fine endpoint
close to its coarse output.
Rotating the inputs.: Given the target G and the base
G^circ from Section~sec:reverse, introduce independent standard
Gaussian vectors G'_1,G'_2, independent of both, and set
G(theta)=√(1-delta),G^circ
+sqrtdelta(costheta,G'_1+sintheta,G'_2),
0lethetaletfracpi2 .
Use a deterministic equally spaced grid in [0,pi/2] that includes both
endpoints, with spacing O(exp(-n^{1/4})) and cardinality
O(exp(n^{1/4})). Rotate two independent collections of all
auxiliary Gaussian path inputs by the same cosine-sine rule, so that small
changes in theta produce small changes in the auxiliary inputs.
Running the proposals.: At each grid point, run the coarse
proposal to horizon
[
V_b=hlceil blog n/hrceil
]
and draw its coarse spin. At each endpoint, also continue the path to
[
V_f=hlceil flog n/hrceil
]
and draw a fine spin. Coarse spin draws are not used in any
continuation. All final spin draws may use fresh independent randomness.
Conditional structure.: The two fine endpoints are independent
conditional on (G,G^circ) and each has law nu(·mid G^circ).
For each individual grid point, averaging over the disorder and
auxiliary inputs on the right side of (eq:rotation) gives the
appropriate proposal law; its primitive auxiliary collection is
independent of all target, base, and proposal matrix drivers. The
one-point estimates and their union bound require no independence across
grid points. The shared rotation supplies the nearby inputs needed for
continuity along the grid.
We now prove that, outside an event of probability at most
exp(-n^{1-d/2}), the following two properties both hold:
[label=(alph*)]
every coarse spin avoids D(G);
the sequence consisting of the first fine spin, all coarse spins in
grid order, and the last fine spin has consecutive Hamming distances at
most R_n.
The probability here is unconditional. Figure~fig:connection shows
the deterministic obstruction that (a) and (b) together create, once we
sample two fine endpoints that provably lie on opposite sides of the cut.
## Avoiding a boundary selected from the target
At a fixed grid point, the driver difference G-G(theta) has coordinate
variance 2delta, by (eq:rotation). Gaussian tails and a union
bound over spins show that the supremum of absolute energy differences is
O(nsqrtdelta), except with probability O(e^{-cn}). On the complement,
Gibbs weight ratios between the two disorders are at most
exp(O_beta(nsqrtdelta)).
Apply the likelihood estimate (eq:6) with coarse horizon l=b. Its
good event depends only on this proposal run. If
q_{rm good}(dxmid g) is the corresponding output subprobability kernel,
disintegration against the Gaussian disorder marginal gives
q_{rm good}(dxmid g)leexp(n^{1-b/2}),pi_g(dx)
quadfor almost every g .
The primitive auxiliary inputs and the final spin draw for this run are
independent of all the matrix drivers. Thus, after fixing
G(theta)=g and adjoining (G,G^circ), this remains the conditional
good-output kernel given the past. In particular, the inequality applies
to the random set D(G) once those matrices have been fixed.
The separate energy-change event is used only to compare Gibbs weights;
it is not built into the proposal good event.
By (eq:12), the resulting boundary probability on the complement of
the energy-change event is at most
[
exp(n^{1-b/2}+O_beta(nsqrtdelta)-tfrac12 n^{1-b/20}).
]
Add the proposal exceptional probability exp(-n^{1-10b}) and the
energy-change exception. Since sqrtdelta=n^{-f/8} and f=1/100, the
exponent 1-b/20 dominates both 1-b/2 and O_beta(nsqrtdelta) for
large n, so this proves the required one-point avoidance bound.
Correlations with auxiliary inputs at other grid points do not change this
calculation, because the good event depends only on the inputs of the run
at that point.
## Continuity of coarse magnetizations
We now control the increments along the grid. At any grid point,
Proposition~prop:proposal puts the Gram matrix of the coarse T_k
within n^{-b} of the identity except with probability
exp(-n^{1-10b}). On this event all |T_k|_nle2, and each
Gram--Schmidt residual has norm at least 1/2, so we do not touch
the zero-residual fallback of Section~sec:proposal. The reciprocals
1/s_k are bounded by a fixed power of n on the deterministic coarse
horizon, by (eq:1).
For neighboring grid points satisfying these Gram conditions, we claim
|M_theta(V_b)-M_{theta'}(V_b)|_n
le(n^{C_1})^{K_b+1},|theta-theta'|,
K_b=V_b/h,
provided the primitive inputs have polynomially bounded norms. The
constant C_1 is independent of the grid and of n.
Input bounds.: Bound the operator norms of
W(G^circ),W(G'_1),W(G'_2) and the normalized norms of all completion
vectors z_k in the two input collections. For their Brownian and bridge
inputs, bound the supremum norms of cumulative integrals against the
deterministic coefficients rho and √(1-rho^2). On a filled
interval include only the centered bridge in this primitive bound; its
endpoint is handled separately. All these norms are at most n^3 outside
an event of probability O(e^{-cn}). Gaussian tails give the matrix and
vector estimates. For the path integrals, write a bridge as Brownian
motion minus its linearly interpolated endpoint and use the Gaussian
martingale maximal bound for a bounded deterministic integrand. Rotation
(eq:rotation) makes the differences of the primitive inputs at two
angles at most a polynomial factor times |theta-theta'|.
Interval induction.: At a Gram--Schmidt step, the difference of
the two projection operators is bounded by twice the sum of preceding
direction differences in |·|_n. Normalizing residuals of norm at
least 1/2 costs only a fixed factor. Using 1/s_k, the new direction
difference is controlled by earlier magnetization and direction
differences at polynomial cost. The same is true of the new g_k, by its
matrix-query and completion formula (eq:gk). The cumulative driving
signals from (eq:4) differ by the primitive integral differences plus
the endpoint difference multiplied by a deterministic factor at most
sqrt h. Finally, the scalar integral equation (eq:Y) and its
spatially Lipschitz drift control the differences in Y and M over this
interval at constant cost, by Gronwall's inequality. Starting with the
entirely auxiliary first interval and taking successive maxima of these
differences proves (eq:13) after increasing C_1 if necessary.
Only the Gram conditions at the two endpoints of each grid step were used.
Since K_b=O(n^{1/16}log n) and the mesh spacing O(exp(-n^{1/4})) is
exponentially smaller, (eq:13) makes every consecutive coarse
magnetization difference negligible relative to n^{-b/3}.
## From magnetizations to spins
For either a coarse spin or a fine endpoint spin compared with its own
coarse magnetization, the normalized squared distance has mean
[
1-E m_{V_b}^2=p(V_b)le C_beta n^{-b/2},
]
by p(V_b)le C_beta e^{-V_b} and V_b=blog n. For a fine spin this
follows from the martingale conditional mean through the continuation.
Under the unconditioned single-run law, each squared distance is an average
of bounded i.i.d. coordinate variables; consequently it is at most
n^{-b/3} except with probability O(exp(-n^{1-b})). The triangle
inequality in |·|_n, along with the negligible magnetization
increments above, then gives Hamming step sizes at most R_n for large n,
since n^{-b/3}ll R_n^2/n=n^{1-b/2}/n=n^{-b/2}.
Union bound.: We now union bound all one-point and
consecutive-point exceptions for the two desired properties, including the
primitive-input event. The grid costs only exp(O(n^{1/4})) points, and
10b<b/2<d/2: the boundary exponent 1-b/20 also exceeds 1-d/2, since
b<d. The total failure probability is at most exp(-n^{1-d/2}) for
sufficiently large n.
## The crossing contradiction
On E, the coverage statement (eq:cov) gives each side of
the chosen cut fine-endpoint probability at least exp(-n^{1-2d}).
Conditional independence therefore puts the two fine endpoints on opposite
sides of the cut with probability at least exp(-2n^{1-2d}).
But if both sequence properties (a) and (b) hold and the fine endpoints
lie on opposite sides, then some consecutive pair in the sequence must
cross the cut. Each such pair contains a coarse spin. A shortest one-spin
path between the pair meets ∂ S and has length at most R_n,
placing that coarse spin in D(G). This contradicts property (a).
Consequently
Pr(E),exp(-2n^{1-2d})leexp(-n^{1-d/2}) .
Since d/2<2d, this implies Pr(E)=o(1) and proves
(eq:11). The auxiliary diagonal and smoothing base are used
only in this proof; the resulting flow bound concerns the original heat
bath.
%----------------------------------------------------------------------
[!htbp]
centering
[x=1cm,y=1cm,font=small,
coarse/.style={circle,draw=blue!55!black,fill=white,line width=.8pt,
minimum size=5.5mm,inner sep=0pt},
fine/.style={rectangle,draw=black!80,fill=black!12,line width=.8pt,
minimum size=5.5mm,inner sep=0pt},
forced/.style={coarse,draw=red!65!black,fill=red!8,line width=1.2pt},
boundary/.style={circle,draw=red!65!black,fill=red!8,line width=.8pt,
minimum size=3mm,inner sep=0pt}]
fill[black!3] (-.05,-.75) rectangle (7.3,.9);
fill[blue!3] (7.3,-.75) rectangle (13.5,.9);
draw[densely dotted,black!55] (7.3,-.75) -- (7.3,.9);
node at (3.6,.63) {S};
node at (10.4,.63) {S^{mathrm c}rmc};
node[fine] (leftfine) at (.65,0) {};
node[coarse] (coarsezero) at (2.5,0) {};
node[coarse] (coarseone) at (4.4,0) {};
node[forced] (crossleft) at (6.3,0) {};
node[forced] (crossright) at (8.3,0) {};
node[coarse] (coarselast) at (10.3,0) {};
node[fine] (rightfine) at (12.8,0) {};
draw[black!65] (leftfine) -- (coarsezero) -- (coarseone) -- (crossleft);
draw[black!65] (crossright) -- (coarselast) -- (rightfine);
draw[red!65!black,line width=1.1pt] (crossleft) -- (crossright);
node[below=1mm] at (leftfine.south) {x_{rm f}^{(0)}};
node[below=1mm] at (rightfine.south) {x_{rm f}^{(1)}};
node[below=1mm] at (crossleft.south) {u};
node[below=1mm] at (crossright.south) {v};
node[fill=white,inner sep=1.5pt] at (7.3,.48) {d_H(u,v)le R_n};
node at (6.9,-1.15)
{Every step has a coarse endpoint; coarse outputs avoid D(G).};
node at (7.3,-1.9)
{Expand the crossing step into single-spin flips: length ellle R_n.};
draw[densely dotted,black!55] (7.3,-2.25) -- (7.3,-3.35);
node[forced] (pathleft) at (3.8,-2.85) {};
node[boundary] (boundaryleft) at (6.2,-2.85) {};
node[boundary] (boundaryright) at (8.4,-2.85) {};
node[forced] (pathright) at (10.8,-2.85) {};
draw[black!65] (pathleft) -- (boundaryleft);
draw[black!65] (boundaryright) -- (pathright);
draw[red!65!black,line width=1.1pt] (boundaryleft) -- (boundaryright);
node[above=2mm,red!65!black] at (7.3,-2.85) {boundary edge};
node[below=1mm] at (pathleft.south) {u=y_0};
node[below=1mm] at (boundaryleft.south) {y_t};
node[below=1mm] at (boundaryright.south) {y_{t+1}};
node[below=1mm] at (pathright.south) {v=y_ell};
node at (2.6,-2.85) {S};
node at (12,-2.85) {S^{mathrm c}rmc};
node[red!65!black,align=center] at (7.3,-3.8)
{d_H(u,∂ S),,d_H(v,∂ S)leellle R_n
;⇒; u,vinD(G).};
%----------------------------------------------------------------------
%======================================================================
# From balanced flows to typical-state mixing
%======================================================================
The flow estimate (eq:11) is available only when both sides
of a cut have appreciable Gibbs mass. We now convert exactly this
information into a mixing statement about typical fixed starting states.
The finite-state argument below has three steps:
[label=arabic*.,leftmargin=*]
Find a set C of large stationary mass with good internal expansion,
by repeatedly pruning away subsets that do not expand.
On C, obtain a Poincar'e inequality from the coarea proof of the
reversible Cheeger inequality.
Use entropy dissipation of the full chain plus stationarity to
bound the pi-average of the fixed-start total variation at time T,
and finish with Markov's inequality over the starting state.
Crucially, the argument never asks a trajectory to stay inside C; that
is exactly what lets rare slow starting states be excluded later rather
than obstructing the bound.
## The pruning lemma
[Pruning and averaged mixing]
Let Ω be a finite set, pi a strictly positive probability on
Ω, and P_t a continuous-time Markov semigroup reversible with
respect to pi with jump rates c(x,y). Assume that for some R>0
[
sum_{yne x}c(x,y)le R (xinΩ).
]
Let 0<ε<1/3 and B>0. Suppose that
[
Q(S,S^{rm c}):=sum_{xin S,,ynotin S}pi(x)c(x,y)>B
quadwhenever εlepi(S)le1-ε.
]
Then for every T>0,
sum_{xinΩ}pi(x)bigl|P_T(x,·)-pibigr|_{rm TV}
lefrac{√(2R,H(pi))}{Bsqrt T}+2ε,
H(pi)=-sum_xpi(x)logpi(x).
Proof.
Put q(x,y)=pi(x)c(x,y)=q(y,x), and use the unordered-edge Dirichlet form
[
mathfrak D(u)=frakD(u)=sum_{{x,y}}q(x,y)(u(x)-u(y))^2.
]
Only distinct vertices occur, and every unordered pair is counted once.
Step 1: removing sets that do not expand.: Start with
C=Ω. Whenever a nonempty Usubset C satisfies
[
pi(U)lepi(C)/2, Q(U,C∖ U)<Bpi(U),
]
remove U from C. This terminates because each removal eliminates at
least one vertex. If A denotes all vertices removed so far, then every
edge between A and its current complement was counted when its first
endpoint was removed, so whenever Ane∅,
[
Q(A,Ω∖ A)<Bpi(A).
]
Suppose the removed mass first reached ε. Its preceding mass
a was less than ε, and the newly removed set has mass at
most (1-a)/2. The new total is therefore at most
(1+a)/2<(1+ε)/2<1-ε. This contradicts the
balanced-cut hypothesis, since Bpi(A)le B. Consequently the terminal
set satisfies pi(C)>1-ε and
Q(U,C∖ U)ge Bpi(U)
quadfor every Usubset C with pi(U)lepi(C)/2 .
Step 2: a Poincar'e inequality on the retained set.: Use the
coarea proof of the reversible Cheeger inequality
cite[Theorem~3.5]{LawlerSokal1988}, keeping the original unnormalized
weights on C. The resulting estimate is
sum_{yin C}pi(y)(u(y)-barbar u_C)^2u_C)^2
le(2R)/(B^2),mathfrak D(u),frakD(u),
barbar u_C=u_C=frac1{pi(C)}sum_{yin C}pi(y)u(y).
To prove it, choose a weighted median m of u on C. Each of
w=(u-m)_+ and w=(m-u)_+ has support of mass at most pi(C)/2.
Integrating (eq:internal-expansion) over the level sets of w^2
gives
[
Bsum_Cpi w^2
lesum_{{x,y}subset C}q(x,y)|w(x)^2-w(y)^2|.
]
By Cauchy--Schwarz this is at most
[
(sum_{{x,y}subset C}q(x,y)(w(x)-w(y))^2)^{1/2}
(2Rsum_Cpi w^2)^{1/2},
]
since (w(x)+w(y))^2le2(w(x)^2+w(y)^2) and the total outgoing rate is at
most R. If sum_Cpi w^2 vanishes the estimate is immediate; otherwise
divide and square. The sum of the energies of the positive and negative
parts is at most mathfrak D(u).frakD(u). The weighted mean minimizes squared
error, proving (eq:14).
Step 3: entropy dissipation for the full chain.: For a fixed
starting state x, set f_t^x(y)=P_t(x,y)/pi(y). Reversibility together
with (a-b)(log a-log b)ge4(sqrt a-sqrt b)^2 for a,b>0 gives the
entropy-dissipation estimate
cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}
int_0^Tsum_xpi(x),mathfrak D(√(f_t^x))frakD(√(f_t^x)),dt
letfrac14 H(pi).
Indeed, the derivative of sum_ypi(y)f_t^x(y)log f_t^x(y) is
[
-sum_{{y,z}}q(y,z)
(f_t^x(y)-f_t^x(z))(log f_t^x(y)-log f_t^x(z)).
]
The initial entropy is log(1/pi(x)) and the final entropy is
nonnegative. Averaging in xsimpi and integrating proves (eq:15).
Vanishing densities and reducible chains cause no problem: start with
(1-eta)f_0^x+eta and pass to eta↓0, or calculate on
communicating classes.
Step 4: averaging fixed-state distances.: Combining (eq:14)
and (eq:15) supplies some tin(0,T] with
[
sum_xpi(x)r_x^2le(R,H(pi))/(2TB^2),
r_x^2=sum_Cpi(y)(√(f_t^x(y))-a_x)^2,
a_x=frac1{pi(C)}sum_Cpi(y)√(f_t^x(y)) .
]
Cauchy--Schwarz and a_x^2pi(C)lesum_Cpi f_t^xle1 imply
[
sum_Cpi|f_t^x-a_x^2|le2r_x .
]
Also, total normalization gives
|sum_Cpi(f_t^x-1)|lesum_{C^{rm c}}pi(f_t^x+1).
Comparing f_t^x first with a_x^2 and then with 1 on C, and adding
the complement, yields
[
sum_Ωpi|f_t^x-1|
le4r_x+2sum_{C^{rm c}}pi(f_t^x+1).
]
The last sum before its factor two has average 2pi(C^{rm c}) over
xsimpi, because stationarity gives sum_xpi(x)f_t^x(y)=1. Dividing
by two for total variation and applying Cauchy--Schwarz in x proves the
upper bound at time t. Contraction under P_{T-t} gives the same bound
at the prescribed time T, establishing (eq:averaged-mixing).
## Proof of the main theorem
Proof. [Proof of Theorem~thm:main]
On the disorder event of Proposition~prop:cuts, apply
Lemma~lem:pruning to the SK chain with
[
ε=n^{-d}, B=exp(-n^{1-b/20}), R=n .
]
The last choice is valid because there are exactly n rate-one update
clocks, so the total jump rate at any vertex is n. Also
H(pi_G)le nlog2, since the state space has 2^n elements. Hence
[
sum_xpi_G(x)bigl|P_T^G(x,·)-pi_Gbigr|_{rm TV}
lefrac{√(2log2);n}{Bsqrt T}+2n^{-d}.
]
Take
[
T=exp(n^{1-b/40}).
]
Then the first term tends to zero, because
[
log(n)/(Bsqrt T)
=log n+n^{1-b/20}-tfrac12 n^{1-b/40}→-∞ .
]
The flow event (eq:11) itself has disorder probability tending to
one. Markov's inequality therefore shows that the Gibbs mass of fixed
states whose distance at time T exceeds 1/4 tends to zero in disorder
probability. The added diagonal changes neither this Gibbs law nor the
transition rates, so the same statement holds for the model H^J_n in
(eq:H). This proves Theorem~thm:main with
[
c_beta=(b)/(40)=frac1{40000000}.
]
All threshold dimensions may depend on the fixed beta>1.
## Reading the final exponents
For orientation, here is the chain of inequalities that governs the
constants, all in the ``1-exponent'' scale:
[
10b ll b/4 ll b/2 ll b/20 ll d
=100b ll 2dll fll 1 .
]
The two competing probabilities in Section~sec:connections were the
coverage probability exp(-2n^{1-2d}) and the sequence failure
probability exp(-n^{1-d/2}): the ratio of their exponents is 2d versus
d/2, and d/2ll d<2d gives the gap. The mixing time T=exp(n^{1-b/40})
sits below both because b/40ll b/20, so the exponential
exp(-n^{1-b/20}) flow bound has enough time to accumulate. Nothing here
is optimized; the only requirement was a positive b, and the constants
were chosen in a strict hierarchy to keep every exponent well separated.
%======================================================================
% References
%======================================================================
{99}
A.~Auffinger and W.-K.~Chen,
newblock On properties of Parisi measures,
newblock Probab. Theory Related Fields 161 (2015),
817--850.
newblock doi:10.1007/s00440-014-0563-y;
arXiv:1303.3573v1.
M.~Boban, A.~Li and S.~Oveis Gharan,
newblock Rank-1-perturbed trickledown theorems: mixing time of Glauber
dynamics for the Sherrington--Kirkpatrick model up to
betaletfrac12+ε,
newblock preprint (2026),
arXiv:2609.13138v1.
V.~I. Bogachev, A.~V. Kolesnikov and K.~V. Medvedev,
newblock Triangular transformations of measures,
newblock Sbornik: Math. 196 (2005), no.~3, 309--335.
newblock doi:10.1070/SM2005v196n03ABEH000882.
E.~Bolthausen,
newblock An iterative construction of solutions of the TAP equations for
the Sherrington--Kirkpatrick model,
newblock Comm. Math. Phys. 325 (2014), 333--366.
newblock doi:10.1007/s00220-013-1862-3;
arXiv:1201.2891.
S.~Boucheron, G.~Lugosi and P.~Massart,
newblock Concentration Inequalities: A Nonasymptotic Theory of
Independence, Oxford University Press, 2013.
W.-K.~Chen,
newblock Variational representations for the Parisi functional and the
two-dimensional Guerra--Talagrand bound,
newblock Ann. Probab. 45 (2017), no.~6A, 3929--3966.
newblock doi:10.1214/16-AOP1154;
arXiv:1501.06635v2.
P.~Diaconis and L.~Saloff-Coste,
newblock Logarithmic Sobolev inequalities for finite Markov chains,
newblock Ann. Appl. Probab. 6 (1996), no.~3, 695--750.
newblock doi:10.1214/aoap/1034968224.
R.~Eldan, F.~Koehler and O.~Zeitouni,
newblock A spectral condition for spectral gap: fast mixing in
high-temperature Ising models,
newblock Probab. Theory Related Fields 182 (2022),
nos.~3--4, 1035--1051.
newblock doi:10.1007/s00440-021-01085-x;
arXiv:2007.08200v1.
F.~Guerra,
newblock Broken replica symmetry bounds in the mean field spin glass
model,
newblock Comm. Math. Phys. 233 (2003), 1--12.
newblock doi:10.1007/s00220-002-0773-5;
arXiv:cond-mat/0205123v1.
A.~Jagannath and I.~Tobasco,
newblock Some properties of the phase diagram for mixed p-spin glasses,
newblock Probab. Theory Related Fields 167 (2017),
615--672.
newblock doi:10.1007/s00440-015-0691-z;
arXiv:1504.02731v2.
G.~F. Lawler and A.~D. Sokal,
newblock Bounds on the L^2 spectrum for Markov chains and Markov
processes: a generalization of Cheeger's inequality,
newblock Trans. Amer. Math. Soc. 309 (1988), no.~2,
557--580.
newblock doi:10.1090/S0002-9947-1988-0930082-9.
P.~Lopatto,
newblock Full replica symmetry breaking in the Sherrington--Kirkpatrick
model,
newblock preprint (2026),
arXiv:2607.11756v3.
G.~Lugosi and G.~Neu,
newblock Generalization bounds via convex analysis,
newblock Proc. Mach. Learn. Res. 178 (2022), 3524--3546.
newblock Proceedings article.
A.~Montanari,
newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
newblock SIAM J. Comput. 54 (2025), no.~4,
FOCS19-1--FOCS19-38 (online 2021).
newblock doi:10.1137/20M132016X;
arXiv:1812.10897v2.
OpenAI,
newblock Stretched-exponential barriers for typical SK initial states,
newblock
OpenAI Math Release preprint, 2026.
M.~Sellke,
newblock Exponentially slow mixing of the low temperature SK model,
newblock preprint (2025),
arXiv:2511.22621v2.
D.~Sherrington and S.~Kirkpatrick,
newblock Solvable model of a spin-glass,
newblock Phys. Rev. Lett. 35 (1975), no.~26, 1792--1796.
newblock doi:10.1103/PhysRevLett.35.1792.
S.~Wang,
newblock Optimal mixing of Glauber dynamics for the
Sherrington--Kirkpatrick model at beta<1/2,
newblock preprint (2026),
arXiv:2608.22159v2.
Y.~Zhou,
newblock Existence of full replica symmetry breaking for the
Sherrington--Kirkpatrick model at low temperature,
newblock Comm. Pure Appl. Math. 79 (2026), 1746--1770.
newblock doi:10.1002/cpa.70038.