================================================================
STRETCHED-EXPONENTIAL BARRIERS FOR TYPICAL SK INITIAL STATES
================================================================
A self-contained rewrite. Same theorem as the original; clearer
structure; every proof included.
----------------------------------------------------------------
0. WHAT THIS PAPER PROVES (plain summary)
----------------------------------------------------------------
The Sherrington-Kirkpatrick (SK) model is a mean-field model of a
spin glass. There are n spins x_i in {-1,+1}, random couplings
J_ij, energy H(x) = (1/sqrt n) sum_{i<j} J_ij x_i x_j, and a Gibbs
measure pi(x) proportional to exp(beta H(x)) at inverse temperature
beta.
Below a critical temperature (beta>1) this measure is glassy:
equilibrium is spread over many nearly disjoint regions with tiny
overlap between them. The dynamics tends to get trapped, and mixing
is slow.
We study the heat-bath dynamics: repeatedly pick a spin and resample
it from its conditional law given all the others. The Gibbs measure
is stationary, so the only question is how fast the chain forgets
where it started.
MAIN RESULT (informal). Pick the initial spin configuration x_0 at
random from equilibrium. Then with probability tending to 1, after
exp(n^(1/10000)) steps the chain is still far (total-variation
distance > 1/4) from equilibrium. So equilibrium initial states,
not just adversarial ones, are slow.
The exponent 1/10000 is not claimed to be optimal. The content is
that the mixing time is stretched-exponential: faster than any
polynomial in n but far slower than exp(c n).
----------------------------------------------------------------
0.1 HOW TO READ (reader's guide)
----------------------------------------------------------------
This proof uses graduate-level probability and analysis. The aim of
this rewrite is clarity of logic and intuition, not removal of the
advanced tools. A reader without the background can follow the
"story" from the plain-language paragraphs that open each section;
the formal statements and proofs follow.
The argument has two halves.
(STATIC) Facts about the Gibbs measure itself, proved once and for
all:
- a quantitative free-energy comparison (Section 2);
- the scalar Parisi functional and its minimizer (Section 3);
- a strict upper bound on the equilibrium energy (Section 3.5);
- "locking": three-replica comparison of overlaps (Sections 4 and 7);
- coverage: for any set S of moderate Gibbs mass, most points of S
have a fixed positive fraction of S within overlap q_* (Section 6).
(DYNAMIC) A path argument (Section 8). Follow the chain. To mix it
would have to cross from positive to nonpositive overlap with a fixed
reference. Along the way we build many nested crossings, each pinned
by an independent uniform threshold. The static lemmas force these
thresholds into ever-narrower windows; the probability is negligible.
The two appendices give independent polynomial-time corollaries and
the reusable coverage estimates.
----------------------------------------------------------------
1. THE MODEL, THE DYNAMICS, AND THE MAIN THEOREM
----------------------------------------------------------------
1.1 Setup.
For n>=2 let Sigma_n = {-1,+1}^n. Let (J_ij)_{1<=i<j<=n} be i.i.d.
standard Gaussians (the disorder). The Hamiltonian and Gibbs measure:
H(x) = H^J_n(x) = (1/sqrt n) sum_{i<j} J_ij x_i x_j,
pi(x) = pi^J_{n,beta}(x) = exp(beta H(x)) / Z,
Z = Z^J_{n,beta} = sum_{x in Sigma_n} exp(beta H(x)).
The overlap of two configurations is
R(x,y) = (1/n) sum_{i=1}^n x_i y_i in [-1,1].
pi is invariant under global spin flip x -> -x.
We fix beta>1 and let n -> infinity.
1.2 The dynamics.
Continuous time: each site i has an independent rate-1 Poisson clock.
When site i rings, resample x_i from its conditional law given the
other spins:
P(x_i <- s | x_{[n]\{i}}) = exp(beta s h_i(x)) / (2 cosh(beta h_i(x))),
h_i(x) = (1/sqrt n) sum_{j != i} J_ij x_j.
Write P^J_t for the transition kernel; the total ring rate is n.
Discrete time: the kernel K^J picks one of the n sites uniformly and
performs the same conditional resampling. One "attempt" = one K^J step.
Both chains are reversible with stationary measure pi.
1.3 Distance to equilibrium.
For measures nu, eta on Sigma_n, total variation is
||nu-eta||_TV = (1/2) sum_x |nu(x)-eta(x)|.
For a fixed starting state x,
d^J(x,t) = ||P^J_t(x,.) - pi||_TV,
T^J(x) = inf{t>=0 : d^J(x,t) <= 1/4},
d^J_disc(x,k) = ||(K^J)^k(x,.) - pi||_TV,
T^J_disc(x) = min{k integer >=0 : d^J_disc(x,k) <= 1/4}.
These are pointwise (starting-state) mixing times, not worst-case.
1.4 Main theorem.
THEOREM 1.1 (main). Let kappa = 1/10000. For every fixed beta>1,
sample J and then x_0 ~ pi^J. Then
P{ d^J(x_0, exp(n^kappa)) > 1/4 } -> 1,
P{ d^J_disc(x_0, floor(exp(n^kappa))) > 1/4 } -> 1.
1.5 Why the order of conditioning matters.
We draw x_0 from pi^J first, then freeze it as the starting point of
the kernel. If instead we integrated x_0 out, stationarity would
return pi at every time and we would learn nothing. The joint
statement is equivalent to: the pi-mass of slow starts tends to 1 in
probability over J. Reason: that mass F_n(J) lies in [0,1]; the
statement "P{F_n > eps} -> 0 for every eps" is exactly "E F_n -> 0"
by Markov plus boundedness.
1.6 Consequence at polynomial times.
COROLLARY 1.2. For every fixed a>0,
P{ T^J(x_0) > n^a } -> 1, P{ T^J_disc(x_0) > n^a } -> 1.
Proof. Total variation is nonincreasing under a Markov kernel
(contraction): d^J(x,t+s) <= d^J(x,t). Thus d^J(x, exp(n^kappa)) > 1/4
forces d^J(x, n^a) > 1/4 once n^a < exp(n^kappa), which holds for
large n. Same with floor for the discrete chain. QED
----------------------------------------------------------------
2. GAUSSIAN HIERARCHIES AND THE FREE-ENERGY COMPARISON
----------------------------------------------------------------
We need two pressure (free-energy) comparisons:
(upper) a bound on a pressure with prescribed replica overlaps;
(lower) an upper bound on P_beta - p_n(beta), the finite-size error.
Both come from finite Gaussian hierarchies. The upper bound lets the
hierarchy's covariance endpoint differ from the prescribed overlap
matrix, with an explicit cost. The lower bound chooses the hierarchy
along an overlap-dependent ODE.
The constrained comparison is in Guerra's Gaussian interpolation
framework, with Talagrand's coupled-replica bounds and Panchenko's
vector-spin formulation. We derive the finite-hierarchy matrix form
directly, allowing nonunit endpoint diagonals. Throughout beta>0 is
fixed; C_beta varies but never depends on n.
2.1 Removing the diagonal.
Add independent J_11,...,J_nn standard Gaussian and, only in
free-energy computations, use
widehat H_n(sigma) = H_n(sigma) + (1/sqrt(2n)) sum_{i=1}^n J_ii.
The extra term has mean zero and does not depend on sigma, so the Gibbs
measure and E log Z are unchanged. Since sum_i (sigma_i tau_i)^2 = n and
(sum_i sigma_i tau_i)^2 = n + 2 sum_{i<j} sigma_i tau_i sigma_j tau_j
= n^2 R(sigma,tau)^2,
the off-diagonal part contributes covariance (n R^2 - 1)/2, and the
diagonal adds exactly 1/2. Hence
E widehat H_n(sigma) widehat H_n(tau) = (n/2) R(sigma,tau)^2.
2.2 Two Gaussian tools.
LEMMA 2.1 (Gaussian tools). Let G be a standard Gaussian vector in
finite dimension.
(a) If f is L-Lipschitz, then for a>0 and every real theta,
P( |f(G)-E f(G)| >= a ) <= 2 exp(-a^2/(2L^2)),
log E exp( theta (f(G)-E f(G)) ) <= theta^2 L^2 / 2.
(b) If a density on R^m is proportional to exp(-V) with V twice
differentiable and grad^2 V >= I, then Var(f) <= E|grad f|^2 for smooth
f. In particular Var(a.G) <= |a|^2 for a linear functional.
PROOF. (a) Let H_s be convolution with N(0,sI) and B_t standard
Brownian motion. The heat equation and Ito give
f(B_1) - E f(B_1) = int_0^1 grad H_{1-t} f(B_t).dB_t, |grad H_s f| <= L.
The integrand is bounded, so the stochastic exponential has expectation
1; its quadratic variation is at most L^2, giving the MGF bound for every
theta. Exponential Markov plus optimizing theta gives the concentration.
Smoothing and localization extend this to Lipschitz f of at most linear
growth, which covers every use below.
(b) Only the linear case is used. The potentials below are smooth with
I <= grad^2 V <= CI for a finite C depending on the fixed finite system
(the nonquadratic parts are finite log-partition sums, whose Hessians
are bounded sums of covariances). Let Y_t solve dY_t = sqrt2 dB_t -
grad V(Y_t)dt with semigroup Q_t. The drift is globally Lipschitz, so
the solution is unique, and synchronous coupling plus strong convexity
contracts distances by e^{-t}: an L-Lipschitz f becomes e^{-t}L-Lipschitz
under Q_t. Integration by parts shows nu(dy) prop exp(-V)dy is invariant
and
d/dt Var_nu(Q_t f) = -2 int |grad Q_t f|^2 d nu.
For f(y)=a.y the strong-convexity tails justify integrating to infinity.
Coupling independent Y,Y'~nu gives Var_nu(Q_t f) <= (1/2)e^{-2t}|a|^2
E|Y-Y'|^2 -> 0, and |grad Q_t f| <= e^{-t}|a| gives
Var_nu(a.Y) <= 2|a|^2 int_0^infty e^{-2t}dt = |a|^2.
The finite upper Hessian bound justifies the diffusion; we check the
lower bound I <= grad^2 V at each use. QED
2.3 The hierarchy and its law.
Besides any quenched root randomness take independent Gaussian fields
g_0,...,g_k. Choose masses
0 = x_{-1} <= x_0 <= ... <= x_k = 1, w_l = x_l - x_{l-1},
and a terminal log partition function F_k on a finite configuration
space. Integrate fields backwards: for 1<=j<=k,
F_{j-1} = (1/x_{j-1}) log E_j exp(x_{j-1} F_j),
with E_j integrating g_j; at x_{j-1}=0 the right side is E_j F_j. The
hierarchy pressure is E F_0.
The recursion also fixes a law on fields and terminal configurations:
given the prefix through j-1, multiply the law of g_j by
W_j = exp( x_{j-1} (F_j - F_{j-1}) ),
which the recursion normalizes. After level k draw from the terminal
Gibbs law.
For a pair of paths at level l: sample the root and fields through l
once, then the two continuations independently given the prefix. Write
E^{(2)}_l for that pair law; at l=k only the terminal draws differ. A
finite tree is sampled by drawing each shared prefix once and making
descendants conditionally independent. Every branch has the single-path
marginal; this convention fixes the shared randomness used below.
LEMMA 2.2 (hierarchy differentiation). Suppose an independent standard
Gaussian g at level j enters the terminal exponent as sqrt(v) g.e(S),
with e a fixed vector-valued function of the terminal configuration.
With all other parameters fixed, for v>0,
d/dv E F_0 = (1/2)[ E|e(S)|^2
- sum_{l=j}^k w_l E^{(2)}_l e(S^1).e(S^2) ],
extending to the endpoints by integration and continuity. A quenched
Gaussian is level 0.
PROOF. Add a deterministic vector along sqrt(v) g. Differentiating the
terminal log partition function and then the recursion shows that, for
l>=j, the gradient of F_l is m_l^e, the conditional mean of e(S) given
the prefix through l. Differentiating again,
grad^2 F_l = E[ grad^2 F_{l+1} | l ] + x_l Cov(m_{l+1}^e | l),
and at the terminal level the Hessian is the thermal covariance of e(S).
For j>=1 differentiate the jth logarithmic expectation in its variance
and integrate by parts in its Gaussian field; the result is one half of
the tilted expectation of tr grad^2 F_j + x_{j-1}|m_j^e|^2. At j=0
ordinary Gaussian differentiation omits the second term, matching
x_{-1}=0. Earlier levels propagate the derivative by conditioning.
Iterating the Hessian recursion, twice the pressure derivative equals
E|e(S)|^2 - E|m_k^e|^2
+ sum_{l=j}^{k-1} x_l ( E|m_{l+1}^e|^2 - E|m_l^e|^2 )
+ x_{j-1} E|m_j^e|^2,
which telescopes to E|e(S)|^2 - sum_{l=j}^k w_l E|m_l^e|^2. Two
descendants are independent given their prefix, so E|m_l^e|^2 =
E^{(2)}_l e(S^1).e(S^2). This is the claim. Gaussian integrability
(finite cube, bounded coupled gradients, values growing at most linearly
in the Gaussians) justifies each step; a zero mass is a direct limit.
QED
2.4 Matrix interpolation bound.
For d configurations sigma^1,...,sigma^d let D_{ab} = R(sigma^a,sigma^b)
be the Gram matrix. If D is feasible, define the unnormalized pressure
F_{d,n}(D) = (1/n) E log sum_{ R(sigma^a,sigma^b)=D_ab }
exp( beta sum_{a=1}^d H_n(sigma^a) ).
Write U:V = sum_{a,b} U_ab V_ab and |U|^2 = U:U.
Choose a symmetric matrix path
Q_{-1}=0, Q_j - Q_{j-1} >= 0 (0<=j<=k), Q_k = Q_end.
The endpoint is free: it may differ from D and may have nonunit diagonal.
Zero increments are allowed; insert a quenched level Q_0=0 if the first
nonzero increment should carry positive mass. At one site take
independent d-dimensional Gaussian fields of covariance beta^2(Q_j -
Q_{j-1}). For a symmetric multiplier lambda define Psi(Q,x,lambda) as
the expected hierarchy value with terminal function
log sum_{s in {-1,1}^d} exp( (sum_{j=0}^k g_j).s + s^T lambda s ).
The deterministic correction is
int x d|Q|^2 = sum_{j=0}^k x_{j-1} ( |Q_j|^2 - |Q_{j-1}|^2 ),
so the quenched initial increment carries mass 0.
PROPOSITION 2.3 (matrix interpolation). For every feasible D and every
path and multiplier as above,
F_{d,n}(D) <= Psi(Q,x,lambda) - lambda:D
+ (beta^2/4)( |D - Q_end|^2 - int x d|Q|^2 ).
For fixed D, lambda the bound passes to any sequence of finite paths for
which Q_end, Psi(Q,x,lambda) and the path integral converge.
PROOF. Put independent copies of the single-site fields at all n sites.
Interpolate from those fields to the common Hamiltonian disorder,
keeping the overlap constraint. With s_i=(sigma^1_i,...,sigma^d_i),
the terminal exponent is
sqrt(t) beta sum_a widehat H_n(sigma^a)
+ sqrt(1-t) sum_{i=1}^n sum_{j=0}^k g_{j,i}.s_i
+ sum_{i=1}^n s_i^T lambda s_i.
Let phi(t) be the expected recursive value divided by n. For two
terminal draws let R_ab = R(sigma^a,tau^b) (generally not symmetric).
The Hamiltonian covariance is n beta^2 |R|^2/2, the jth site-field
increment has covariance n beta^2 (Q_j - Q_{j-1}):R, and the self
overlap is D. Summing Lemma 2.2 over the increments,
phi'(t) = (beta^2/4)[ |D|^2 - 2 Q_k:D
- sum_{l=0}^k w_l E^{(2)}_l ( |R|^2 - 2 Q_l:R ) ]
<= (beta^2/4)( |D|^2 - 2 Q_k:D + sum_{l=0}^k w_l |Q_l|^2 ),
dropping the nonnegative squares |R - Q_l|^2 (no symmetry of R needed).
Summation by parts gives |Q_k|^2 - sum_l w_l |Q_l|^2 = int x d|Q|^2.
At t=1 the fields vanish and phi(1)=F_{d,n}(D)+lambda:D. At t=0 the
overlap constraint is removed, which increases the terminal sum and hence
every recursive value (each integration is monotone); the recursion
factors over sites and phi(0) <= Psi(Q,x,lambda). Integrating the
derivative bound proves the proposition. Singular increments follow by
continuity or a square root of the covariance. QED
2.5 The scalar functional.
Let mu be a probability measure on [0,1] with alpha(s)=mu([0,s]).
Define Phi_alpha by the terminal value Phi_alpha(1,z)=log(2 cosh z) and
the backward equation
-d_s Phi_alpha = (beta^2/2)( d_{zz} Phi_alpha
+ alpha(s) (d_z Phi_alpha)^2 ).
For a step function alpha this is exactly the Gaussian recursion: over
an interval of length b-a with constant mass x, a terminal function f is
mapped to
z -> (1/x) log E exp( x f(z + beta sqrt(b-a) G) ),
with ordinary expectation at x=0. For general alpha take L^1 limits of
step functions (well-defined by the regularity in Section 3). Define
P_beta(mu) = Phi_alpha(0,0) - (beta^2/2) int_0^1 s alpha(s) ds,
P_beta = inf_mu P_beta(mu).
The infimum is attained (compactness plus continuity; Proposition 3.3).
UPPER COMPARISON. Apply Proposition 2.3 with d=1, D=Q_end=1, lambda=0,
first for step measures and then by approximation:
p_n(beta) := (1/n) E log Z_{n,beta} <= P_beta.
THEOREM 2.4 (quantitative comparison). For every fixed beta>0 there is
C_beta<infinity such that, for all sufficiently large n,
P_beta - C_beta n^{-1/24} <= p_n(beta) <= P_beta.
The upper bound is the display above. The lower bound is the rest of this
section.
2.6 Concentration along a hierarchy.
For the lower bound use equally spaced masses:
w_j = 1/(k+1), x_j = (j+1)/(k+1) (0<=j<=k).
Fix 0<=t<=1 and levels 0=q_{-1}<q_0<...<q_k, Delta_j=beta^2(q_j-q_{j-1}).
Use the terminal exponent
U(sigma) = sqrt(t) beta widehat H_n(sigma)
+ sum_{j=0}^k sqrt(Delta_j) z_j.sigma,
with z_0,...,z_k independent standard Gaussian vectors in R^n. Let A_j be
the prefix through level j (including the Hamiltonian disorder). Under
the path law set
m_j = E[sigma | A_j], M_j = |m_j|^2/n, r_j = E M_j.
m_j is a martingale, so 0 <= r_0 <= ... <= r_k <= 1.
LEMMA 2.5 (field-energy concentration). For every 0<=j<=k, under the
single-path law,
Var( z_j.sigma / n ) <= 1/n.
PROOF. Condition first on the terminal spin sigma. The product of the
tilts W_l and the terminal Gibbs density telescopes, so the conditional
joint density of all Gaussian variables and fields is proportional to the
original Gaussian density times
exp( U(sigma) - sum_{l=0}^k w_l F_l ).
Each F_l is jointly convex in its prefix Gaussian variables: at the
terminal level this is log-sum-exp of linear functions; backward, the
mass-zero expectation preserves convexity and Holder's inequality does so
for a positive-mass logarithmic expectation. Extending F_l to be constant
in its descendants keeps it convex. The weights w_l are nonnegative and
U(sigma) is linear for fixed sigma, so the negative log of the conditional
density has Hessian >= I. The linear specialization of Lemma 2.1 gives
Var( z_j.sigma/n | sigma ) <= 1/n.
To drop the conditioning, note the conditional mean is sigma-independent:
use the gauge transformation with eps_i = sigma_i,
J_ab -> eps_a eps_b J_ab (a<b), z_{l,i} -> eps_i z_{l,i} (0<=l<=k),
diagonal fixed. It preserves the Gaussian law, carries the conditional law
at sigma to the conditional law at the all-plus spin, and preserves
z_j.sigma. Hence the conditional means coincide, and the law of total
variance gives the claim. QED
LEMMA 2.6 (average overlap concentration). Let Delta_min = min_j Delta_j.
If k>=1 and k/sqrt(n Delta_min) <= 1, then
sum_{j=0}^k w_j E^{(2)}_j (R - r_j)^2
<= C ( k/sqrt(n Delta_min) + k^{-1/2} ),
with C an absolute constant.
PROOF. The law of total variance splits the error into the fluctuation of
the conditional mean M_j and the variance left after the prefix is fixed.
FLUCTUATION OF M_j. Fix j<k. Sample three paths a,b,c with a common
prefix through j+1 and conditionally independent continuations. For
B=B(sigma^a,sigma^b,sigma^c) with |B|<=1, integration by parts in the two
adjacent fields gives
E B ( z_j/sqrt(Delta_j) - z_{j+1}/sqrt(Delta_{j+1}) ).sigma^a/n
= -w_j E B m_j.sigma^a/n. (2.6a)
To see (2.6a): the density is the product of the tilts along the common
edges 1..j+1, along the three descendant branches, and the three terminal
Gibbs probabilities. Applying the derivative difference
(1/sqrt(Delta_j)) d_{z_{j,i}} - (1/sqrt(Delta_{j+1})) d_{z_{j+1,i}}
coordinate by coordinate, every term at level <= j+1 depends only on
sqrt(Delta_j) z_j + sqrt(Delta_{j+1}) z_{j+1} and cancels, terms above j
depend on neither field, and only F_j survives with coefficient
x_{j-1}-x_j = -w_j; its normalized derivative is m_{j,i}. Summing over i
gives (2.6a).
Let Y be the quantity multiplying B on the left of (2.6a). Every branch
has the single-path marginal, so Lemma 2.5 and the L^2 triangle inequality
give Var(Y)^{1/2} <= 2/sqrt(n Delta_min). With B=1, (2.6a) reads
E Y = -w_j r_j. Centering, using |B|<=1 and w_j=1/(k+1),
| E B ( m_j.sigma^a/n - r_j ) | <= 2(k+1)/sqrt(n Delta_min). (2.6b)
Take B = R(sigma^b,sigma^c). Given A_{j+1} the three descendants are
independent, so the left side of (2.6b) becomes
| E ( m_j.m_{j+1}/n - r_j ) M_{j+1} |. Replacing m_{j+1} by m_j in both
factors changes the expectation by at most 3 sqrt(gamma_j), where
gamma_j = (1/n) E|m_{j+1}-m_j|^2, using |m_l|<=sqrt(n) and |M_j-r_j|<=1.
After the replacement the expectation is E(M_j-r_j)M_j = Var(M_j).
Martingale orthogonality gives sum_{j<k} gamma_j <= 1, and Cauchy-Schwarz
yields
sum_{j<k} w_j Var(M_j) <= C ( k/sqrt(n Delta_min) + k^{-1/2} ). (2.6c)
CONDITIONAL VARIANCE. Define
C_j = Cov(sigma|A_j), D_j = grad^2 F_j, V_j = Cov(m_{j+1}|A_j).
The law of total covariance and the differentiated recursion give
C_j = E[C_{j+1}|A_j] + V_j, D_j = E[D_{j+1}|A_j] + x_j V_j.
Since D_k=C_k and the masses are nondecreasing, backward induction gives
D_j >= x_j C_j. (2.6d)
Write Delta=Delta_{j+1}, y=sqrt(Delta) z_{j+1}; its density given A_j is
proportional to exp(-|y|^2/(2Delta) + x_j F_{j+1}). Integration by parts
with grad_y F_{j+1}=m_{j+1} gives
Cov(m_{j+1},y|A_j) = Delta D_j,
Cov(y|A_j) = Delta I + Delta^2 x_j D_j.
The joint covariance of (m_{j+1},y) is positive semidefinite, so the
Schur complement gives
V_j >= Delta D_j (I + Delta x_j D_j)^{-1} D_j. (2.6e)
Order eigenvalues decreasingly as c_i,d_i,v_i. By (2.6d), d_i>=x_j c_i.
The map d -> Delta d^2/(1+Delta x_j d) is increasing on d>=0, so the
min-max principle applied to (2.6e) gives
v_i >= Delta d_i^2/(1+Delta x_j d_i) >= Delta x_j^2 c_i^2/(1+Delta x_j^2 c_i).
Above the threshold c_i >= (Delta x_j^2)^{-1} this is at least c_i/2;
since c_i <= tr C_j <= n, those eigenvalues contribute at most
2n tr V_j to sum_i c_i^2, while those below threshold contribute at most
n/(Delta x_j^2). Hence
tr C_j^2 / n^2 <= 2 tr V_j / n + 1/(n Delta_{j+1} x_j^2). (2.6f)
Martingale orthogonality gives sum_{j<k} E tr V_j <= n. Summing (2.6f)
over j with x_j=(j+1)/(k+1),
B_0 := sum_{j<k} w_j E tr C_j^2/n^2 <= C/k + C k/(n Delta_min). (2.6g)
For two independent descendants of the level-j prefix the conditional
overlap has mean M_j and variance
(1/n^2)(tr C_j^2 + 2 m_j^T C_j m_j). The second term is at most
2 sqrt(tr C_j^2/n^2) (use |m_j|^2<=n and |C_j|_op <= sqrt(tr C_j^2)), so
the averaged conditional variance is at most B_0 + 2 sqrt(B_0), which is
<= C/k under k/sqrt(n Delta_min)<=1. Combining with (2.6c) through the law
of total variance, and costing level k at most 4/(k+1) because |R-r_k|<=2,
gives the lemma. QED
2.7 Adaptive interpolation and the finite-size error.
PROOF OF THEOREM 2.4. The upper bound is done. For the lower bound choose
field levels so the pressure derivative separates into a quadratic in the
overlap means plus the controlled overlap error, then integrate and match
a scalar trial measure.
CHOOSING THE PATH. Take a differentiable q(t) with positive gaps and
f(t)=n^{-1} E F_0(t,q(t)). For a field gap a_j=q_j-q_{j-1} in overlap
units, the hierarchy identity gives
d/da_j (1/n) E F_0 = (beta^2/2)( 1 - sum_{l=j}^k w_l r_l ).
The Hamiltonian part is (beta^2/4)(1 - sum_l w_l E^{(2)}_l R^2). Summing
and using sum_{j<=l} a_j' = q_l',
f'(t) = (beta^2/4)(1 - sum_l w_l E^{(2)}_l R^2)
+ (beta^2/2)( q_k' - sum_l w_l r_l q_l' ).
This suggests the ODE q_j'(t) = -r_j(t,q(t)). Indeed, since
E^{(2)}_j R = r_j, every positive-gap solution has
f'(t) = (beta^2/4)[ 1 - 2 r_k + sum_j w_j r_j^2
- sum_j w_j E^{(2)}_j (R - r_j)^2 ]. (2.7a)
The last term is the overlap error; the rest is controlled after
integration using the ODE. Choose
k = floor(n^{1/12}), eta = n^{-1/6}, q_j(1) = (j+1) eta (0<=j<=k),
and solve (the ODE) backwards from t=1.
EXISTENCE AND BOUNDS. On the open region of positive gaps, the finite
Gaussian recursions make r_j continuous in t and locally Lipschitz in q.
Domination: uniformly in the prefix and t, |grad_{z_h} F_h| =
sqrt(Delta_h)|m_h| <= L. Subtracting F_h(z_h=0) from numerator and
denominator gives W_h(z_h) <= C exp(L|z_h|), so the conditional first
moments of later fields are uniformly bounded. d_{q_i}U is bounded by a
constant times |z_i|+|z_{i+1}| (second term omitted at i=k), hence
d_{q_i} F_l <= C(1 + sum_{h<=l}|z_h|). Representing r_j as an expectation
of R on a two-path tree, the terminal Gibbs probabilities are at most one,
so its density and q_i-derivative are dominated by C(1+S)e^{LS}, with S
the sum of norms of all fields in the tree. This is Gaussian integrable,
uniformly in t and q, giving the local Lipschitz property. At t=0
continuity follows from the same bound and from continuity in sqrt(t)
(no derivative of sqrt(t) is needed).
Along the local solution, r_j>=r_{j-1} implies each gap q_j-q_{j-1} is
nondecreasing as time runs backwards (with r_{-1}=0), so it stays at least
eta. The bound 0<=r_j<=1 prevents escape to infinity and gives
q_k(t) <= (k+1)eta + 1 - t, Delta_j(t) >= beta^2 eta.
These estimates continue the local solution across all of [0,1] and verify
the field-gap hypothesis of Lemma 2.6. Thus, for all large n, uniformly
along the path,
sum_j w_j E^{(2)}_j (R - r_j)^2 <= C_beta n^{-1/24}, (2.7b)
because the two terms of that lemma are O_beta(n^{-1/3}) and O(n^{-1/24})
(k/sqrt(n beta^2 eta) = O_beta(n^{-1/3}) and k^{-1/2}=O(n^{-1/24})).
INTEGRATING THE DERIVATIVE. Write delta=(k+1)eta=O(n^{-1/12}) and
Q_j=q_j(0). The derivative d/da_j lies in [0,beta^2/2], so removing the
fields present at t=1 costs at most beta^2 delta/2, and
f(1) <= p_n(beta) + (beta^2/2) delta.
The ODE and Jensen give
int_0^1 r_j = Q_j - q_j(1), int_0^1 r_j^2 >= (Q_j - q_j(1))^2,
with endpoint bounds 0<=Q_j<=1+delta and 0<=q_j(1)<=delta. Integrating
(2.7a), applying these and (2.7b),
p_n(beta) >= f(0) + (beta^2/4)( 1 - 2 Q_k + sum_j w_j Q_j^2 )
- C_beta n^{-1/24}. (2.7c)
IDENTIFYING A TRIAL MEASURE. At t=0 there is no Hamiltonian coupling, so
f(0) is the scalar single-site value at levels Q_0,...,Q_k. The only
obstruction to using these levels as a trial measure on [0,1] is that some
Q_j may exceed 1. Replace Q_j by min(Q_j,1). Each gap can only decrease,
total decrease Q_k - min(Q_k,1) <= delta; d/da_j in [0,beta^2/2] bounds
the change in scalar value by beta^2 delta/2, and the quadratic expression
in (2.7c) changes by at most C_beta delta. So we may take Q_k<=1 within
the stated error, interpreting zero gaps by continuity.
Now let mu = sum_j w_j delta_{Q_j}. Its distribution function is zero up
to Q_0, equals x_{j-1} on (Q_{j-1},Q_j), and equals one on (Q_k,1]. Over
that final interval the recursion adds beta^2(1-Q_k)/2 to log(2 cosh z),
so
Phi_alpha(0,0) = f(0) + (beta^2/2)(1 - Q_k).
The penalty is identified by summation by parts:
(beta^2/2) int_0^1 s alpha(s) ds
= (beta^2/4)( 1 - sum_j w_j Q_j^2 ).
The expression preceding the error in (2.7c) is therefore exactly
P_beta(mu), which is at least P_beta. This completes the lower comparison
and the proof of Theorem 2.4. QED
----------------------------------------------------------------
3. SCALAR REGULARITY, MINIMIZERS, AND THE ENERGY GAP
----------------------------------------------------------------
We establish the scalar identities behind the overlap comparisons and
the energy bound. Three parts: (1) justify the scalar equation and its
stochastic evolution for general distribution functions, atoms included;
(2) first variations and properties of an arbitrary minimizing measure;
(3) a strict energy bound when beta>1. No description of the support is
assumed beyond what we prove.
Earlier work: Auffinger-Chen for regularity and zero-field support;
Chen and Jagannath-Tobasco for first-variation characterization. We
prove what we use, with our normalization and atom conventions.
Throughout alpha(s)=mu([0,s]) is right-continuous. Recall the terminal
value equation
-d_s Phi_alpha = (beta^2/2)( d_{zz} Phi_alpha
+ alpha(s)(d_z Phi_alpha)^2 ),
Phi_alpha(1,z) = log(2 cosh z).
For step alpha this is the Gaussian recursion of Section 2. For general
alpha, defined by approximation. The time derivative is understood a.e.
(no differentiability at a jump of alpha is needed). Write u=d_z
Phi_alpha, chi=d_{zz} Phi_alpha.
3.1 Regularity and first variations.
LEMMA 3.1 (regularity, stability, scalar evolution). The step
approximation defining Phi_alpha is independent of the sequence. The
functions Phi_alpha,u,chi are continuous on [0,1]xR, and
|u| <= 1, 0 < chi <= 1, |chi(s,z)-chi(s,z')| <= C_beta|z-z'|.
Phi_alpha(s,.) is even, so u(s,0)=0. For two distribution functions
alpha, alpha~,
sup_{s,z}( |Phi_alpha-Phi_alpha~| + |u_alpha-u_alpha~|
+ |chi_alpha-chi_alpha~| )
<= C_beta int_0^1 |alpha(s)-alpha~(s)| ds. (3.1a)
The functions are also continuous in beta>0, uniformly in (s,z) for
their differences, locally in beta.
The SDE
dX_s = beta dB_s + beta^2 alpha(s) u(s,X_s) ds, X_0 = 0, (3.1b)
has a unique strong solution. For a step function its transitions across
constant-mass intervals are the normalized tilted Gaussian kernels of the
scalar recursion. The bounded martingale U_s=u(s,X_s) satisfies
U_t - U_s = beta int_s^t chi(v,X_v) dB_v, (3.1c)
E chi(t,X_t) - E chi(s,X_s)
= -beta^2 int_s^t alpha(v) E chi(v,X_v)^2 dv, (3.1d)
and conditionally, for 0<=s<t<=1,
E[chi(t,X_t)|X_s] = chi(s,X_s)
- beta^2 int_s^t alpha(v) E[chi(v,X_v)^2|X_s] dv. (3.1e)
Hence Gamma(s):=E u(s,X_s)^2 is C^1 (one-sided at the endpoints), with
Gamma(0)=0, Gamma'(s) = beta^2 E chi(s,X_s)^2. (3.1f)
Well-posedness and (3.1c)-(3.1d) also hold from any deterministic
start (s,z).
PROOF. Work first with step alpha and pass to limits.
DERIVATIVE BOUNDS ALONG A STEP PATH. On an interval of constant mass m
and length ell, the recursion is T_m f(z)=m^{-1} log E exp(m f(z + beta
sqrt(ell) Z)), with T_0 f = E f(z + beta sqrt(ell) Z). Fix (s,z), list
the remaining breakpoints s=t_0<...<t_r=1, masses m_j on [t_j,t_{j+1}),
f_j=Phi_alpha(t_j,.). Starting Z_0=z, sample Z_{j+1} from the tilted
kernel
K_j(v,dy) = exp(m_j[f_{j+1}(y)-f_j(v)]) N(v, beta^2(t_{j+1}-t_j))(dy),
equal to the Gaussian at m_j=0. Let F_j=sigma(Z_0,...,Z_j), M_j=f_j'(Z_j).
Differentiating the recursion once and twice,
E[M_{j+1}|F_j] = M_j,
f_j''(Z_j) = E[f_{j+1}''(Z_{j+1})|F_j]
+ m_j E[(M_{j+1}-M_j)^2|F_j].
So M is a martingale with terminal tanh Z_r, and iterating the second
identity,
chi(s,z) = E sech^2(Z_r) + sum_{j<r} m_j E(M_{j+1}-M_j)^2.
The increments are orthogonal, so the unweighted squared sum has
expectation Var(tanh Z_r). Since 0<=m_j<=1,
0 < E(1 - tanh^2 Z_r) <= chi(s,z)
<= E(1 - tanh^2 Z_r) + Var(tanh Z_r) = 1 - u(s,z)^2 <= 1.
Every recursion preserves evenness, and the gradient is a conditional
mean of the terminal gradient, so |u|<=1.
SMOOTHNESS. For a fixed finite path, the kth derivative of one
logarithmic Gaussian integral is a polynomial in tilted moments of
f',...,f^(k) with coefficients bounded for 0<=m<=1; at m=0 derivative
passes through the expectation. Since all positive-order derivatives of
log(2 cosh z) are bounded, induction gives bounded derivatives. Inside a
constant-mass interval the recursion solves the PDE. Its first two
spatial derivatives satisfy
-u_s = (beta^2/2) u_{zz} + beta^2 alpha u u_z,
-chi_s = (beta^2/2) chi_{zz} + beta^2 alpha u chi_z + beta^2 alpha chi^2.
With w=chi_z, one more differentiation gives the linear equation
-w_s = (beta^2/2) w_{zz} + beta^2 alpha u w_z + 3 beta^2 alpha chi w.
The bounds on u,chi control drift and potential uniformly over all step
paths; the terminal value of w has |w(.,1)|<=2. Concatenating diffusion
representations,
sup_{s,z} |w(s,z)| <= 2 e^{3 beta^2}.
SCALAR DIFFUSION. On a constant-mass interval [a,b], let Y_s = z +
beta(B_s-B_a). Ito identifies exp(m(Phi(b,Y_b)-Phi(a,z))) as an
exponential martingale with stochastic logarithm m beta int_a^b
u(v,Y_v) dB_v; the bounded integrand justifies the change of measure,
adding drift beta^2 m u. Under that drift, a further Ito gives
d u(s,X_s) = beta chi(s,X_s) dB_s,
d chi(s,X_s) = beta chi_z(s,X_s) dB_s - beta^2 alpha(s) chi(s,X_s)^2 ds.
This is (3.1c)-(3.1d) for step paths.
STABILITY AND PASSAGE TO GENERAL alpha. Subtract the equations for two
step paths with the same diffusion coefficient. The difference of the
scalar values has drift (beta^2/2) alpha(u+u~) and source
(beta^2/2)(alpha-alpha~)u~^2. The equation for u-u~ has bounded drift and
potential, source <= C_beta|alpha-alpha~|; for chi-chi~ the source is
<= C_beta(|alpha-alpha~|(s) + sup_z|u-u~|(s)) (expand alpha u chi_z -
alpha~ u~ chi~_z and use the uniform bound on chi~_z; factor the
difference of squares in the reaction term). Since each difference has
zero terminal value, the diffusion representation of these linear
equations proves (3.1a), first for Phi, then u, then chi.
Approximate alpha in L^1 by step functions. The stability estimates make
Phi,u,chi converge uniformly (uniformly also for differences of the
unbounded Phi); the fundamental theorem of calculus in z identifies the
limits of u,chi with the first two spatial derivatives of Phi.
Continuity, symmetry and non-strict bounds pass to the limit, and the
time-integrated step equation gives the PDE a.e.
The limiting drift in (3.1b) is measurable in time, bounded, and
uniformly Lipschitz in space, so (3.1b) has a strong solution and
pathwise uniqueness. Coupling two step-approximation solutions with the
same Brownian motion, Gronwall gives uniform convergence. Thus the
terminal lower bound passes to the limit:
chi(s,z) >= E_{s,z} sech^2(X_1) > 0.
Ito isometry passes the martingale identity, bounded convergence the
expectation identity; nothing uses the start (0,0). Starting at (s,z)
and using the Markov property gives (3.1e), and (3.1c) with continuity
of chi,X gives (3.1f).
TEMPERATURE CONTINUITY. Write b=beta^2 and repeat the subtraction with
different b. In the Phi-equation the extra source is (b~-b)(chi~ +
alpha u~^2)/2 <= C|b~-b|; the bound on chi~_z gives the same for u.
Thus Phi,u differ by O(|b~-b|) locally uniformly. For chi, use its
uniform spatial Lipschitz bound and a difference quotient of u: for h>0,
sup|chi-chi~| <= (2/h) sup|u-u~| + C h,
choose h small then b~ close to b. Step approximation transfers this to
all alpha. QED
FIRST VARIATIONS. For another distribution function alpha~ set
alpha_theta = alpha + theta(alpha~ - alpha). The mass variation is
d/dtheta P_beta(alpha_theta)|_{theta=0+}
= (beta^2/2) int_0^1 (alpha~-alpha)(s)(Gamma(s)-s) ds. (3.2)
With alpha fixed, the temperature derivative of the scalar value is
d/d(beta^2) Phi_alpha(0,0)
= (1/2) int_0^1 E[ chi(s,X_s) + alpha(s) u(s,X_s)^2 ] ds. (3.3)
BOTH PROVED BY DIFFERENCES. Subtract the Phi_{alpha_theta} and
Phi_alpha equations: drift (beta^2/2) alpha(u_{alpha_theta}+u_alpha),
source theta beta^2 (alpha~-alpha) u_{alpha_theta}^2/2. Introduce Y^theta
with Y^theta_0=0 and
dY^theta_s = beta dB_s + (beta^2/2) alpha(s)
(u_{alpha_theta}+u_alpha)(s,Y^theta_s) ds.
The diffusion representation of the difference equation is the exact
identity
(Phi_{alpha_theta}(0,0)-Phi_alpha(0,0))/theta
= (beta^2/2) E int_0^1 (alpha~-alpha)(s) u_{alpha_theta}(s,Y^theta_s)^2 ds.
For general alpha,alpha~ approximate by steps and take convex
combinations at fixed theta; (3.1a) gives convergence of the mixed drifts
in integrated spatial sup norm, sharing a spatial Lipschitz bound, so a
same-Brownian coupling plus Gronwall gives Y^theta -> X. Sending theta
down to 0 with |u|<=1 and uniform convergence of u gives the
right side (beta^2/2) int (alpha~-alpha)Gamma; subtracting the linear
penalty's derivative yields (3.2).
For (3.3), set b=beta^2, use superscript b, and for b~ != b let
Y^{b,b~}_0=0 with
dY^{b,b~}_s = sqrt(b) dB_s + (b/2) alpha(s)
(u^b+u^{b~})(s,Y^{b,b~}_s) ds.
Subtracting the two step equations gives
(Phi^{b~}(0,0)-Phi^b(0,0))/(b~-b)
= (1/2) E int_0^1 [chi^{b~} + alpha(u^{b~})^2](s,Y^{b,b~}_s) ds.
Pass to general alpha as above, then b~ -> b using parameter continuity
and the coupling; the integrands stay bounded and converge in integrated
expectation. QED
3.2 Minimizers and the energy gap.
The mass variation turns minimization into a condition on the support.
We use it to identify the expected scalar susceptibility at every time
and to show the minimizer is nontrivial when beta>1.
PROPOSITION 3.3 (support and stationarity identities). The scalar
functional has a minimizer mu. For every such minimizer, with its
associated scalar process:
(i) 0 is in supp(mu), and supp(mu) is contained in [0,1-eps_0] for some
eps_0>0.
(ii) At every q in supp(mu) cap (0,1), Gamma(q)=q and Gamma'(q)<=1; at
q=0, Gamma(0)=0 and Gamma'(0)<=1.
(iii) Define
d_*(s) = 1 - int_{(s,1]} t mu(dt),
A(s) = int_s^1 alpha(t) dt = d_*(s) - s alpha(s). (3.4)
Then at every s in [0,1],
E[ chi(s,X_s) + alpha(s) u(s,X_s)^2 ] = d_*(s), (3.5)
equivalently (since d_*(s)=A(s)+s alpha(s))
E chi(s,X_s) = A(s) + alpha(s)(s - Gamma(s)), (3.6)
and in particular
chi(0,0) = A(0), beta A(0) <= 1. (3.7)
Moreover alpha(s)>0 for every s in (0,1], A(h)<A(0) for every
h in (0,1], and d_*(0+) = A(0).
PROOF. EXISTENCE AND VARIATIONAL SUPPORT CONDITION. Weak convergence on
[0,1] gives pointwise convergence of distribution functions at continuity
points of the limit, hence L^1 convergence by bounded convergence. By
Lemma 3.1, P_beta is continuous for this topology; the space of
probability measures on [0,1] is compact, so a minimizer exists.
Fix a minimizer and set G(q)=int_q^1 (Gamma(s)-s) ds. Fubini and the mass
variation (3.2) give int G d mu~ >= int G d mu for every probability
measure mu~. Testing with point masses, mu is supported on the set of
global minima of G. Since G'=q-Gamma(q), G''=1-Gamma'(q), the first- and
second-derivative tests give the identities and inequalities at interior
support points. At the right endpoint Gamma(1)=E tanh^2(X_1)<1, so
G'(1)>0 and 1 is not a minimizer; the compact minimum set stays a
positive distance below 1.
LEFT ENDPOINT. Let q_0=min supp(mu). Suppose q_0 in (0,1). Then alpha=0
on [0,q_0), so X_s=beta B_s there and the chi-equation is the backward
heat equation; thus chi(s,X_s) is a bounded martingale on [0,q_0] (from
the heat semigroup, or by step approximations identically zero below
q_0). Its second moment, and hence Gamma'(s), is nondecreasing on this
interval. But Gamma(q_0)=q_0, Gamma(0)=0, and Gamma'(q_0)<=1, so the
average of Gamma' over [0,q_0] is 1 while its maximum is at most 1;
continuity forces Gamma' == 1 on [0,q_0].
To contradict this, note chi(q_0,.) is positive everywhere and cannot be
constant: otherwise u(q_0,.) would have a positive constant derivative,
contrary to |u|<=1. Being continuous and X_{q_0} a nondegenerate
Gaussian with full support, Var(chi(q_0,X_{q_0}))>0, while chi(0,X_0) is
deterministic. Then the martingale's second moment strictly increases
between 0 and q_0, contradicting the constancy of Gamma'. Hence q_0=0. At
this endpoint G has a minimum and symmetry gives G'(0)=0; the one-sided
second-derivative test yields Gamma'(0)<=1.
STATIONARITY WITH ATOMS. We have located the support and have Gamma(t)=t
on it. Using (3.1d), the terminal relation chi(1,z)=1-u(1,z)^2 and (3.1f),
E chi(s,X_s) = 1 - Gamma(1) + int_s^1 alpha(t) Gamma'(t) dt.
Stieltjes integration by parts with the right-continuous alpha gives the
following formula, keeping every atom (the integral over (s,1] while the
endpoint term uses alpha(s)):
int_s^1 alpha(t) Gamma'(t) dt
= Gamma(1) - alpha(s) Gamma(s) - int_{(s,1]} Gamma(t) mu(dt).
Substituting Gamma(t)=t on supp(mu), including at 0, gives (3.5). Fubini
gives the expression for A in (3.4). At s=0, (3.5) becomes chi(0,0)=A(0),
and Gamma'(0)=beta^2 chi(0,0)^2 <= 1 gives (3.7).
Since 0 is in supp(mu), every interval [0,s] with s>0 has positive
mu-mass, so A(0)-A(h)=int_0^h alpha(s) ds>0 for all h in (0,1]. The
identity d_*(s)=A(s)+s alpha(s) and continuity of A at 0 give
d_*(0+)=A(0). QED
For beta>1 the susceptibility bound excludes delta_0, making the
temperature derivative at a fixed minimizer strictly below beta/2. A
finite-volume secant estimate transfers this to the equilibrium energy.
LEMMA 3.4 (strict bound on the equilibrium energy). For each fixed
beta>1 there are e_0=e_0(beta)<beta/2 and N=N(beta) such that, for
n>=N,
p_n'(beta) = (1/n) E pi^J_{n,beta}(H_n^J) <= e_0. (3.8)
PROOF. Fix a minimizing measure mu at the given beta and hold it fixed
during the temperature variation. Combining (3.3) and (3.5) and
differentiating the penalty,
d/dgamma P_gamma(mu)|_{gamma=beta}
= beta int_0^1 (d_*(s) - s alpha(s)) ds
= beta int_0^1 A(s) ds
= (beta/2)( 1 - int_0^1 t^2 mu(dt) ),
the last step by two applications of Fubini. If mu=delta_0 then A(0)=1,
contradicting beta A(0)<=1 for beta>1; the second moment of mu is
therefore positive. Let L denote this derivative; we have L<beta/2.
Choose e_0 with L<e_0<beta/2, then eps>0 so small that
(P_{beta+eps}(mu)-P_beta(mu))/eps < e_0. The finite-volume pressure is
differentiable and convex in beta, so its derivative is bounded by the
forward secant. Using the scalar upper trial bound at beta+eps and
Theorem 2.4 at beta,
p_n'(beta) <= (p_n(beta+eps)-p_n(beta))/eps
<= (P_{beta+eps}(mu)-P_beta)/eps + (C_beta/eps) n^{-1/24}.
Since P_beta(mu)=P_beta, the fixed secant slope is strictly below e_0; the
strict margin absorbs the error for large n. Finally, differentiating the
finite partition sum and taking Gaussian expectation gives (3.8); the
integrable bound max_sigma |H_n^J(sigma)| justifies the passage. Only the
temperature in the functional of one fixed measure varied, so no
differentiability of P_beta or of a minimizing measure in beta is needed.
QED
----------------------------------------------------------------
4. LOCKING SMALL OVERLAPS ACROSS A LARGE OVERLAP
----------------------------------------------------------------
When two configurations overlap positively by a fixed amount h, their
small overlaps with a third configuration stay close, including signs.
This is the fixed-scale estimate. Spin reversal then gives the
absolute-overlap version.
Fix beta>1 and a minimizer mu; write pi=pi^J. The scalar inputs are
0<=chi<=1, |u|<=1, |chi(s,z)-chi(s,z')|<=C_beta|z-z'|,
E chi(s,X_s) = A(s) + alpha(s)(s - Gamma(s)),
E[ chi(s,X_s) + alpha(s) u(s,X_s)^2 ] = d_*(s),
beta A(0)<=1, A(h)<A(0) for 0<h<=1, d_*(s)->A(0) as s down to 0. (4.1)
We also use the scalar martingale (3.1c), the bounds alpha(s)>0 for
s>0, and 0<=d_*(s)<=1.
For a nonempty Gram constraint D write Z_{d,n}(D) for the unnormalized
sum in the constrained pressure, so F_{d,n}(D)=n^{-1}E log Z_{d,n}(D),
and Z_{d,n}(D)/Z^d is the probability of D under d independent Gibbs
draws.
LEMMA 4.1 (signed fixed-scale locking). Let e_*=1/100. For every fixed
h in (0,1) there is b>0 such that, for all sufficiently large n,
E pi^{x3}{ R(x,y)>=h, |R(v,x)|,|R(v,y)|<=b,
|R(v,x)-R(v,y)|>2 n^{-e*} } <= e^{-n^{9/10}}. (4.2)
The same holds after decreasing b.
We prove a pressure deficit for each forbidden overlap matrix and sum
probability bounds. The conversion below also applies to the shrinking
gaps of Section 7.
LEMMA 4.2 (pressure gap to probability). Fix a replica number d. If a
feasible overlap matrix D satisfies F_{d,n}(D) <= d P_beta - eta with
eta >= 2d C_beta n^{-1/24}, then, for all sufficiently large n,
E Z_{d,n}(D)/Z^d <= exp(-n eta/4) + exp(-c_{beta,d} n eta^2). (4.3)
The constants are uniform over D and over n-dependent gaps satisfying
the displayed bound.
PROOF. For fixed d, the derivative of log Z_{d,n}(D) in any J_ij has
absolute value at most beta d/sqrt n, and so does d log Z. Hence the
difference
T_D := log Z_{d,n}(D) - d log Z
has Lipschitz constant at most C_{beta,d} sqrt n and satisfies T_D<=0,
since e^{T_D} is a Gibbs probability. Theorem 2.4 and the gap hypothesis
give E T_D <= -n eta/2. Gaussian concentration bounds P{T_D > -n eta/4}
by exp(-c_{beta,d} n eta^2). On its complement e^{T_D} <= e^{-n eta/4},
and on the event e^{T_D} <= 1; summing proves (4.3). This uses the
original off-diagonal disorder, so no diagonal Gaussian enters the bound.
QED
Only d=2,3 are needed. There are at most (n+1)^{d(d-1)/2} feasible
overlap matrices, so a union over constraints costs a polynomial factor.
4.1 A pair constraint.
LEMMA 4.3 (pair pressure bound). For every nonempty pair constraint with
overlap q in [0,1],
F_{2,n}( 1 q ; q 1 ) <= 2 P_beta - (1/2)(Gamma(q)-q)^2. (4.4)
Consequently, for every fixed tau>0, the averaged Gibbs probability of
pairs with |Gamma(|R(x,y)|)-|R(x,y)|| > tau is at most C exp(-cn) for
large n.
PROOF. Use Proposition 2.3 with two coordinates sharing covariance
increments up to scalar time q and receiving independent increments
after. Give the common increments masses alpha(s)/2 and the independent
increments masses alpha(s). The endpoint is the prescribed Gram matrix.
At zero terminal multiplier this path has recursive value 2 Phi(0,0):
integrating the independent part first leaves Phi(q,z_x)+Phi(q,z_y); on
the earlier common part z_x=z_y, and integrating twice a scalar value at
mass alpha/2 is twice the scalar integral at mass alpha. The penalty has
the same factor two: before the split the squared norm is 4s^2 at mass
alpha/2, after the split its varying part is 2s^2 at mass alpha.
Add L s_x s_y to the terminal exponent and call the recursive value
Psi(L). The matrix convention sets lambda_xy=L/2, so lambda:D=Lq.
Differentiating at L=0 transports s_x s_y backward by conditional
expectation under the unperturbed tilted path. Given the common field at
q, the two later branches are independent and each has conditional spin
mean u(q,X_q), so
Psi'(0) = E u(q,X_q)^2 = Gamma(q).
Also Psi''(L)<=1 for every L: for a terminal observable O in [-1,1], the
terminal Hessian is its thermal variance; backward integration at mass m
in [0,1] averages the existing Hessian and adds m times the conditional
variance of the gradient, so the result is bounded by Var(O)<=1 under
the tilted path law (total-variance decomposition), preserved under the
outer quenched expectation. Taylor's inequality gives
F_{2,n}(q) <= 2 P_beta + L(Gamma(q)-q) + L^2/2.
Taking L=q-Gamma(q) yields (4.4).
These computations are first made with step approximations of alpha whose
segment endpoints include q; Lemma 3.1 gives convergence of the scalar
values, derivatives and tilted transitions, so (4.4) passes to the
minimizing alpha.
Finally reversing one configuration preserves its Gibbs weight and flips
the sign of its overlap, so the same estimate applies with |R| in place
of q. There are at most n+1 pair overlaps; summing (4.3) with the fixed
deficit tau^2/2 gives the probability assertion. QED
4.2 A three-coordinate path with an asymmetric perturbation.
Fix q in [h,1] and a nonempty constraint
D = ( 1 r+d r-d ;
r+d 1 q ;
r-d q 1 ), r>=0. (4.5)
We choose upper bounds for r and |d| depending only on beta,h. Write D_0
for the same matrix with d=0. Starting from a hierarchy ending at D_0 we
add opposite field increments to the x and y coordinates. This realizes
the desired first-order change in their overlaps with v. Keeping the
increments positive semidefinite also adds a second-order covariance
term; the free-endpoint matrix bound charges only its squared size, a
fourth-order cost.
The reason to perturb an early increment is the strict inequality
beta^2 A(h)A(0)<1 from (4.1). At a small branching time r the two scalar
branches are nearly independent, with susceptibility product bounded by
A(h)A(0) up to small errors. The Gaussian variance part of the
perturbation cancels the corresponding penalty up to the pair deviation
q-Gamma(q); the strict product inequality controls what remains.
The base hierarchy is valid for every 0<=r<=q<=1; only the perturbation
needs r small. Its three stages (the three-replica construction following
Talagrand's Proposition 4.4, masses divided by the size of each common
block), in local scalar time s:
(i) 0..r: all three coordinates share each increment, mass alpha/3;
(ii) r..q: v follows an independent branch at mass alpha, x,y share a
branch at mass alpha/2;
(iii) q..1: all three have independent increments at mass alpha.
In the middle stage each branch has its own clock; with clocks a (v) and
b (x,y) the current covariance is
Q(a,b) = ( a r r ; r b b ; r b b ), r<=a,b<=q.
One branch advances while the other is held. For a step function alpha,
merge the two finite nondecreasing mass lists in nondecreasing order
(ties either way consistent with the two local orders). First-stage
masses do not exceed either middle starting mass, and middle masses do
not exceed the last stage's starting mass, so the schedule is a valid
nondecreasing hierarchy. Insert a dummy Q_0=0 so that, even when
alpha(0)>0, the first genuine field increment has its prescribed
positive mass.
The endpoint is D_0 and the recursive value minus the penalty equals
3 P_beta(mu). Indeed a common block of size ell has scalar value ell Phi;
its mass alpha/ell gives the ordinary scalar tilted transition, and its
squared-norm differential ell^2 d(s^2) contributes ell times the scalar
penalty after multiplication by that mass. Independent branches add, and
when one branch is integrated the value of a frozen branch passes
unchanged through the logarithm. Applying these facts at each split
identifies the base tilted law. Denote the v-branch and the shared x,y
branch by X^v and X^x, and their common field at the first split by X_r.
If X_0 is the common prefix through r and K_{r,z} the scalar path law
from (r,z) to q, then
L( X^v_[r,q], X^x_[r,q] | X_0 ) = K_{r,X_r} (x) K_{r,X_r}. (4.6)
The frozen branch cancels from each normalized kernel, and the factor 3
or 2 in the common-block value cancels the divided mass; the two future
branches are independent given X_r, for every allowed merge. This base
hierarchy is reused in Section 7.
4.3 The perturbation and its penalty.
For the fixed-scale perturbation fix 0<s_1<s_2<h and suppose r<s_1.
Define
k(s) = 1_{[s_1,s_2]}(s)/(s_2-s_1), g(s)=int_0^s k,
G(s) = int_0^s k^2, K = G(s_2) = 1/(s_2-s_1).
Let L_{vx}=L_{xv}=1, L_{vy}=L_{yv}=-1, all other entries 0, and let L_2
vanish off its (x,y) block, giving that block (1 -1; -1 1). Then
|L|^2=|L_2|^2=4 and L:L_2=0.
During each v-increment with local clock in [s_1,s_2], add d k times that
increment to x and its negative to y. At covariance level this replaces
ds e_v e_v^T by
ds ( e_v + d k(e_x - e_y) ) ( e_v + d k(e_x - e_y) )^T,
a rank-one positive semidefinite form. The accumulated change is
d g L + d^2 G L_2 until the modification ends, then held. The new
endpoint is
D~ = D_0 + d L + d^2 K L_2 = D + d^2 K L_2.
Apply Proposition 2.3 with zero terminal multiplier and this endpoint.
The mismatch contribution is
(beta^2/4) |D - D~|^2 = beta^2 d^4 K^2. (4.7)
Along the base path Q:L=0; also Q:L_2=0 until the split at q, by which
time g=1 and G=K; in the final stage Q:L_2=2(s-q). Thus
|Q~|^2 - |Q|^2 = 4 d^2 g^2 + 2 d^2 G (Q:L_2) + 4 d^4 G^2.
The last term has nonnegative increments; the first changes only during
the v-increments (masses alpha), the middle only in the final stage. The
penalty increase is therefore at least
beta^2 d^2 ( int_0^1 alpha(s) d(g^2) + K A(q) ). (4.8)
4.4 The recursive value under the perturbation.
Integrate out the unchanged independent final stage. Let z be the common
base field of x,y at the end of the middle stage and Y the sum of the raw
v-increments weighted by k. The boundary value changes by
Delta = Phi(q, z + d Y) + Phi(q, z - d Y) - 2 Phi(q,z). (4.9)
Convexity, chi<=1 and the spatial Lipschitz bound give
0 <= Delta <= d^2 Y^2, |Delta - d^2 chi(q,z) Y^2| <= C_beta|d Y|^3. (4.10)
To propagate through the backward integrations: with base kernel K_i and
difference U_i of recursive values at a prefix, U_i = m_i^{-1} log K_i
e^{m_i U_{i+1}} (m_i>0). Put A_i = E_base[Delta|prefix i],
B_i = log E_base[e^Delta|prefix i]. At the boundary both equal Delta, and
if A_{i+1}<=U_{i+1}<=B_{i+1} the kernel inequalities and tower property
give A_i<=U_i<=B_i (Jensen at mass 0). Inducting through the hierarchy,
E_base Delta <= Psi~ - Psi <= log E_base e^Delta. (4.11)
Under the base tilted law take scalar diffusions X^v, X^x that agree
through r and have independent Brownian noises after. Then z = X_q^x and
Y = int_{s_1}^{s_2} k(s) dX_s^v, dX_s^v = beta dB_s^v + beta^2 alpha(s) u(s,X_s^v) ds.
So Y is a centered Gaussian increment of variance beta^2 K plus a
dependent random term of absolute value at most beta^2. There are
c,C>0 (depending only on beta,s_1,s_2) with E_base e^{c Y^2}<=C, uniformly
in q>=h, r<s_1 and step approximations. For small |d|, (4.10) and this
exponential moment give E(e^Delta - 1 - Delta) <= (1/2)E[Delta^2 e^Delta]
<= C d^4. With (4.11),
Psi~ - Psi <= d^2 E[ chi(q,X_q^x) Y^2 ] + C|d|^3. (4.12)
All matrix paths can be taken finite (include r,q,s_1,s_2 as endpoints;
step approximations of alpha). Lemma 3.1 gives convergence of scalar
values, derivatives and diffusions; coupling with the same Brownian
noises (independent after r) and the uniform exponential moment
justify the limit. Subtracting (4.8) from (4.12) and adding (4.7),
F_{3,n}(D) <= 3 P_beta + d^2 B(q,r) + C|d|^3, (4.13)
B(q,r) = E[ chi(q,X_q^x) Y^2 ]
- beta^2 K A(q) - beta^2 int_0^1 alpha(s) d(g^2).
The task is to choose the interval so this quadratic coefficient is
strictly negative.
4.5 Choosing an interval with a strict quadratic gain.
Define V_t = chi(t,X_t^v) + alpha(t) u(t,X_t^v)^2 and
Y_s = int_{s_1}^s k(t) dX_t^v. The martingale du(s,X_s^v)=beta
chi(s,X_s^v) dB_s^v and Ito, conditional on X_r, give for a.e. s
d/ds E[ Y_s u(s,X_s^v) | X_r ] = beta^2 k(s) E[ V_s | X_r ].
Since Y_{s_1}=0, Ito on Y_s^2 and conditional independence of the v and
x branches give
E[ chi(q,X_q^x) Y^2 ] = beta^2 K E chi(q,X_q)
+ 2 beta^4 int_{s_1}^{s_2} alpha(s) k(s)
int_{s_1}^s k(t) E[ chi(q,X_q^x) V_t ] dt ds. (4.14)
Only the common field at the small time r prevents the product in this
formula from factoring, and
| E[chi(q,X_q^x)V_t] - E chi(q,X_q) d_*(t) | <= C_beta sqrt(r), (4.15)
for s_1<=t<=s_2 and h<=q<=1. For (4.15): restart the x branch at an
independent copy X_r' of X_r (independent of the whole v branch), keeping
its post-r noise. The drift beta^2 alpha u is Lipschitz, so the two x
solutions at time q differ by at most e^{beta^2}|X_r-X_r'|; use chi
Lipschitz, 0<=V_t<=2 and E|X_r-X_r'|<=C_beta sqrt(r). The replacement has
the same marginal law, is independent of V_t, and factors with
E V_t=d_*(t).
Now beta A(0)<=1 and A(h)<A(0) give beta^2 A(h)A(0)<1. Choose s_2 in
(0,h) and gamma>0 with
beta^2 A(h) sup_{0<t<=s_2} d_*(t) <= 1 - 4 gamma, (4.16)
and set s_1=s_2/2 (fixing k,g,K). Also
W = 2 beta^2 int_{s_1}^{s_2} alpha(s)k(s) int_{s_1}^s k(t) dt ds > 0,
strictly positive since alpha(s)>0 for s>0.
Let chi_bar(q)=E chi(q,X_q). For q in [h,1] with |q-Gamma(q)|<=tau, the
all-time identity gives chi_bar(q)=A(q)+alpha(q)(q-Gamma(q))<=A(h)+tau.
Choose tau>0 small, then r_0 in (0,s_1) small; (4.15) and (4.16) then
give, uniformly for q in [h,1] with |q-Gamma(q)|<=tau, 0<=r<=r_0 and
t in [s_1,s_2],
beta^2 E[chi(q,X_q^x) V_t] - 1 <= -2 gamma, (4.17)
since (with 0<=d_*<=1) the left side is at most
-4 gamma + beta^2 tau + C_beta sqrt(r).
Using d(g^2)=2gk ds and substituting (4.14) into (4.13),
B(q,r) = beta^2 K alpha(q)(q-Gamma(q))
+ 2 beta^2 int_{s_1}^{s_2} alpha(s) k(s)
int_{s_1}^s k(t) { beta^2 E[chi(q,X_q^x)V_t] - 1 } dt ds. (4.18)
Decrease tau further until beta^2 K tau <= gamma W. The first term in
(4.18) is then at most gamma W, and (4.17) bounds the double integral by
-2 gamma W, so B(q,r)<=-gamma W. The cubic remainder in (4.13) is uniform
over these q,r; choose d_0>0 to absorb it. For some c_0>0 we obtain
F_{3,n}(D) <= 3 P_beta - c_0 d^2 (4.19)
whenever the constraint is nonempty, 0<=r<=r_0, |d|<=d_0, q in [h,1],
and |q-Gamma(q)|<=tau. No restriction r>=|d| is placed on the two small
signed overlaps.
4.6 From the pressure gap to locking.
PROOF OF LEMMA 4.1. Choose b<=min(r_0,d_0). For a triple in (4.2), set
q=R(x,y)>=h and reverse v if necessary to make
r = (R(v,x)+R(v,y))/2 >= 0, d = (R(v,x)-R(v,y))/2.
This preserves the Gibbs weight, the large overlap q and |d|. The event
gives r,|d|<=b and |d|>n^{-e*}; the two small overlaps need not have the
same sign. Lemma 4.3 bounds pairs with |q-Gamma(q)|>tau by C exp(-cn) in
averaged probability, and adding an independent Gibbs draw does not
change that. For every remaining feasible triple, (4.19) gives a
pressure deficit eta=c_0 d^2 >= c_0 n^{-2e*}. Since 2e_*=1/50<1/24, this
dominates the finite-size error in Lemma 4.2 uniformly over the
constraints, so the averaged probabilities are bounded by
exp(-c n^{49/50}) + exp(-c n^{24/25}).
There are at most (n+1)^3 triples and two choices of the reversal; the
total is at most C(n+1)^3 exp(-c n^{24/25}), below exp(-n^{9/10}) for
large n. QED
PROPOSITION 4.4 (absolute-overlap locking). For every fixed h in (0,1)
there is b>0 such that, for all sufficiently large n,
E pi^{x3}{ |R(x,y)|>=h, |R(v,x)|,|R(v,y)|<=b,
||R(v,x)|-|R(v,y)|| > 2 n^{-1/100} }
<= exp(-n^{9/10}). (4.20)
The same holds after decreasing b.
PROOF. Take b from Lemma 4.1. Reverse y if needed to make R(x,y)>=h;
this preserves the Gibbs weight and all absolute overlaps in the event.
Since ||a|-|b||<=|a-b|, the transformed triple is in the signed event.
The two possible reversals multiply the probability bound by at most
two, absorbed by the stronger bound C(n+1)^3 exp(-c n^{24/25}) from the
preceding proof. QED
----------------------------------------------------------------
5. ENERGY TAIL AND DISORDER ROTATION
----------------------------------------------------------------
The strict energy gap (Lemma 3.4) will force overlap coverage on both
stretched-exponential and polynomial mass scales. This section supplies
the two estimates behind that implication: an upper tail for the energy
of a Gibbs sample, and a bound on the partition-function change under a
Gaussian rotation. Work with the off-diagonal Hamiltonian throughout;
the auxiliary diagonal variables of Section 2 are absent here.
LEMMA 5.1 (upper energy tail). There are e_1 in (0,beta/2) and c_E>0
such that, for all sufficiently large n,
P_J( pi^J{ H^J > n e_1 } > e^{-c_E n} ) <= e^{-c_E n}. (5.1)
PROOF. Split concentration from the location of the mean. By Lemma 3.4
there is e_0<beta/2 with p_n'(beta)<=e_0 for large n. Choose e_1 in
(max{0,e_0}, beta/2) and c_E=(e_1-e_0)^2/2.
Sample J and then V~pi^J. For v in Sigma, Bayes gives the conditional
disorder density given V=v proportional to
exp( -|J|^2/2 + beta H^J(v) - log Z^J ).
The log partition function is convex in the disorder, so the negative
log-density has Hessian I + grad^2 log Z^J >= I. A linear tilt sH^J(v)
keeps that lower bound. Write H^J(v)=h_v.J with |h_v|^2=(1/n)sum_{i<j}
v_i^2 v_j^2=(n-1)/2. With phi_v(s)=log E[e^{sH^J(v)}|V=v],
differentiation under the tilted law and the linear Brascamp-Lieb bound
(Lemma 2.1) give phi_v''(s)=Var_{v,s}(H^J(v))<=(n-1)/2 for all s; strong
convexity gives integrability. Two integrations of the variance bound,
subtracting the conditional mean, give
E[ exp(s(H^J(v)-E[H^J(v)|V=v])) | V=v ] <= exp(s^2(n-1)/4). (5.2)
To identify the conditional mean, use the gauge transformation
J_ij -> J_ij v_i v_j; it preserves the Gaussian law, preserves Z^J, and
carries H^J(v) to H^J(all-plus). These transformations act transitively
on configurations, so V has uniform marginal and E[H^J(v)|V=v] is the
same for every v; its average over V is E pi^J(H^J)=n p_n'(beta)
(differentiating the finite pressure; Gaussian integrability allows the
interchange). The conditional mean is thus at most n e_0. Chernoff in
(5.2), followed by averaging,
E_J pi^J{ H^J > n e_1 } <= exp( -n^2(e_1-e_0)^2/(n-1) ) <= e^{-2 c_E n}.
Markov then gives (5.1). QED
LEMMA 5.2 (disorder rotation). Let J,G be independent standard Gaussians
and, for theta in (0,pi/2), J_theta=cos(theta) J + sin(theta) G. For
every real lambda,
E exp( lambda (log Z^{J_theta}-log Z^J) )
<= exp( lambda^2 theta^2 beta^2 (n-1)/4 ). (5.3)
In particular for u>0,
P( log Z^{J_theta}-log Z^J >= u )
<= exp( -u^2/(theta^2 beta^2 (n-1)) ). (5.4)
PROOF. Put F(J)=log Z^J. The derivative d_{J_ij}F=beta n^{-1/2}
pi^J(sigma_i sigma_j) gives |grad F(J)|^2 <= beta^2(n-1)/2 =: L_F^2.
For 0<=s<=theta let J_s=cos(s) J + sin(s) G and K_s=-sin(s) J + cos(s) G;
by orthogonal invariance J_s and K_s are independent standard Gaussians.
Differentiating along the rotation, F(J_theta)-F(J)=int_0^theta grad
F(J_s).K_s ds. Jensen on the uniform measure on [0,theta], then
conditioning on J_s and integrating the independent Gaussian K_s,
E exp(lambda(F(J_theta)-F(J)))
<= (1/theta) int_0^theta E exp(lambda theta grad F(J_s).K_s) ds
<= (1/theta) int_0^theta exp(lambda^2 theta^2 L_F^2/2) ds
= exp(lambda^2 theta^2 L_F^2/2).
This is (5.3). Exponential Markov and optimizing lambda>0 give (5.4).
The argument holds for every permitted angle, so also for angles
depending on n. QED
For coverage we parametrize the rotation by the variance of its fresh
disorder. If 0<t<1/2 and J'=sqrt(1-t) J + sqrt(t) G, take
theta=arcsin(sqrt t). Since theta^2<=2t, Lemma 5.2 gives, for z>0,
P( log Z^{J'} - log Z^J >= z )
<= exp( -c_beta z^2/(n t) ), c_beta = 1/(2 beta^2), (5.5)
uniform in t, including rotations whose variance decreases with n.
----------------------------------------------------------------
6. COVERAGE AT STRETCHED-EXPONENTIAL SCALES
----------------------------------------------------------------
Given a target x in a subset S, we seek a reference z in S with
|R(x,z)|>=q_* among independent Gibbs samples. Two parts: the total Gibbs
mass of targets that may be excluded is small, and every remaining target
has a neighborhood of sufficient Gibbs mass. Both masses use the
original Gibbs law, not conditioning on S, so the neighborhood mass is
the success probability of one sample.
Both mass bounds are on scale L=n^kappa. If a set has too few
overlapping pairs, fresh Gaussian disorder produces a gain in its
restricted partition sum; the energy tail limits the loss from
decreasing the original disorder, leaving a net increase that the
rotation estimate makes unlikely. To be uniform over all subsets, we
select a violating set using the original disorder before the
perturbation.
PROPOSITION 6.1 (stretched-exponential coverage). There exists q_* in
(0,1), depending only on the fixed beta>1, with the following property.
For each fixed D_1>0 there exist a fixed D_3=D_3(beta,D_1)>0 and events
C_n(D_1), measurable with respect to the disorder, such that
P_J(C_n(D_1))->1 and, on C_n(D_1),
pi^J( {x in S: pi^J{z in S: |R(x,z)|>=q_*} < e^{-D_3 L}} )
< e^{-D_1 L} for every S subset Sigma. (6.1)
PROOF. FIRST CONTROL PAIR MASS. Let e_1 in (0,beta/2) and c_E>0 be from
Lemma 5.1 and define
E_n = { pi^J{ x: H^J(x)>n e_1 } <= e^{-c_E n} }, P_J(E_n)->1.
Define g = beta^2/4 - beta e_1/2 > 0 and fix once (for this proposition
and Appendix A, before D_1 is chosen)
0<q_*<1, beta^2 q_* < g/8.
Given D_1>0 choose fixed constants
M>8(D_1+1)/g, D_2>beta^2 M/2 + 1, t=ML/n. (6.2)
For large n, 0<t<1/2, t->0, nt=ML->infinity.
CLAIM: with disorder probability tending to one,
(pi^J(.|S))^{x2}{ |R(x,y)|>=q_* } >= e^{-D_2 L}
for every S subset Sigma with pi^J(S)>=e^{-D_1 L}. (6.3)
Let V_n be the failure event. Order subsets of Sigma deterministically;
for J in E_n cap V_n select the first violating S(J). The Gibbs
quantities for each fixed subset are measurable in J, so the selection is
measurable, and after conditioning on J the chosen set cannot depend on
the independent disorder used below.
Fix such a disorder, pi=pi^J, and remove the upper energy tail from the
selected set:
T = S cap { x: H^J(x)<=n e_1 }, nu = pi(.|T).
Since L=o(n), for large n, e^{-c_E n} <= (1/2)e^{-D_1 L} and
pi(T)>=pi(S)-e^{-c_E n} >= (1/2)pi(S) >= (1/2)e^{-D_1 L}. Comparing
conditional pair laws,
nu^{x2}{ |R(x,y)|>=q_* }
<= (pi(S)/pi(T))^2 (pi(.|S))^{x2}{ |R(x,y)|>=q_* }
< 4 e^{-D_2 L}. (6.4)
GAIN FROM INDEPENDENT DISORDER. Sample an independent Gaussian disorder
G and set W=nu(e^{beta sqrt(t) H^G}), J'=sqrt(1-t) J + sqrt(t) G. Here
the subscript G means the original disorder and its selected set are
held fixed. The off-diagonal normalization gives E_G H^G(x)^2=(n-1)/2
and E_G[H^G(x)H^G(y)]=(n R(x,y)^2 - 1)/2. The Gaussian moment formula
gives
E_G W = e^{beta^2 t(n-1)/4},
E_G W^2/(E_G W)^2 = nu^{x2}( e^{beta^2 t(n R^2 - 1)/2} )
<= e^{beta^2 n t q_*^2/2} + 4 e^{(beta^2 M/2 - D_2)L}
<= 2 e^{beta^2 n t q_*^2/2}, (6.5)
splitting the pair sum at |R|=q_*, using (6.4) on the large-overlap part
and the choice of D_2 in (6.2). Paley-Zygmund gives
P_G( W >= (1/2) E_G W ) >= (1/8) e^{-A_0},
A_0 = beta^2 n t q_*^2/2. (6.6)
CONCENTRATION RAISES THIS TO 1/2. For f(G)=log W, differentiation gives
|d f/d G_ij|<=beta sqrt(t/n) and |grad f|^2<=beta^2 t(n-1)/2=:sigma^2.
Write a=beta^2 t(n-1)/4 - log2 and f_bar=E_G f. If a>f_bar, comparing
the upper concentration tail with (6.6),
(1/8)e^{-A_0} <= P_G(f>=a) <= exp(-(a-f_bar)^2/(2 sigma^2)),
so f_bar >= a - sigma sqrt(2(A_0+log8)); if a<=f_bar the same holds
immediately. Either way the lower concentration tail yields
P_G( f >= a - sigma sqrt(2(A_0+log8)) - sigma sqrt(2 log2) ) >= 1/2.
Since sigma<=beta sqrt(nt/2),
sigma sqrt(2(A_0+log8))+sigma sqrt(2 log2) <= beta^2 nt q_*/sqrt2 +
C_beta sqrt(nt) <= beta^2 nt q_* + C_beta sqrt(nt). Hence, with
conditional probability at least 1/2,
log W >= beta^2 t(n-1)/4 - beta^2 n t q_* - C_beta sqrt(nt) - log2. (6.7)
COMPARISON WITH THE ROTATION COST. The gain from G must be compared with
the change in the original energy. Linearity in the disorder gives
Z^{J'}/Z^J = pi( e^{beta(sqrt(1-t)-1)H^J + beta sqrt(t) H^G} )
>= pi(T) e^{-beta n e_1(1-sqrt(1-t))} W,
since on T the original energy is at most n e_1 and its coefficient
sqrt(1-t)-1 is negative. Combining with (6.7),
log Z^{J'}/Z^J >= -D_1 L - log2 - beta n e_1(1-sqrt(1-t)) + log W
>= (g - beta^2 q_*) n t - D_1 L - C_beta sqrt(nt)
- C_beta(n t^2 + 1),
using 1-sqrt(1-t)=t/2+O(t^2) uniformly for 0<t<1/2. Dividing by nt, the
limit inferior is at least g - beta^2 q_* - D_1/M > 3g/4. Thus for large
n and every J in E_n cap V_n,
P_G( log Z^{J'}-log Z^J >= (g/2) n t ) >= 1/2. (6.8)
Average (6.8) over J and use the unconditional rotation bound (5.5):
P_J(E_n cap V_n) <= 2 P_{J,G}( log Z^{J'}-log Z^J >= (g/2) n t )
<= 2 e^{-c'_beta n t} = 2 e^{-c'_beta M L} -> 0
for a fixed c'_beta>0. Adding P_J(E_n^c)=o(1) gives P_J(V_n)->0, hence
(6.3). Since V_n is the event that any violating subset exists, this is
already the simultaneous statement, with no union bound over subsets.
FROM PAIRS TO INDIVIDUAL TARGETS. Choose fixed D_3>D_1+D_2 and set
C_n(D_1)=V_n^c. Fix J in this event and any S. Let
B = { x in S: pi^J{z in S: |R(x,z)|>=q_*} < e^{-D_3 L} }.
If pi^J(B)>=e^{-D_1 L}, then since B subset S,
(pi^J(.|B))^{x2}{ |R(x,y)|>=q_* }
= (1/pi^J(B)^2) sum_{x in B} pi^J(x) pi^J{y in B: |R(x,y)|>=q_*}
< e^{-D_3 L}/pi^J(B) <= e^{-(D_3-D_1)L} < e^{-D_2 L},
contradicting (6.3) applied to B. Therefore pi^J(B)<e^{-D_1 L} for
every S, proving (6.1). QED
----------------------------------------------------------------
7. LOCKING ON A NARROW ANNULUS
----------------------------------------------------------------
Lemma 4.1 handles one large overlap and two near-zero small overlaps.
The path argument also needs a different regime: the two smaller overlaps
sit near a positive level r, while the larger overlap exceeds r by an
amount that may tend to zero. We obtain a uniform pressure loss for that
regime.
Fix a minimizing measure mu and its scalar data from Section 3. Recall
Gamma(s)=E u(s,X_s)^2, and write chi_s=chi(s,X_s). We work in the case
Gamma(s)=s on a fixed interval; if that fails there, a pair pressure gap
supplies the forbidden interval used in Section 8.
Fix t_0>0 with 3 t_0<q_* (q_* from Proposition 6.1). Recall rho=n^{-kappa}
with kappa=1/10000, and set
h = rho^8, epsilon = rho^20. (7.1)
Constants below may depend on beta, t_0 and the fixed minimizing measure,
but not on n or on the overlap parameters.
The comparison alters the fields by a contrast on the two sides of a
branching time, plus a short increment on the other branch. When the
surrounding interval has small Parisi mass, a tent integration by parts
shows the contrast contributes little beyond its Gaussian variance; the
mixed term with the other branch supplies the strict pressure loss.
LEMMA 7.1 (narrow-annulus locking). Suppose
Gamma(s)=s for t_0/2 < s < 3 t_0. (7.2)
For three independent Gibbs configurations v,x,y (conditionally on the
disorder) define
q=R(x,y), r=(R(v,x)+R(v,y))/2, d=(R(v,x)-R(v,y))/2.
Then, for all sufficiently large n,
E pi^{x3}{ t_0/2<r<3 t_0, mu([r-h,r+h])<=rho^4,
q>=r+rho, epsilon<=|d|<=2 epsilon }
<= exp(-n^{4/5}). (7.3)
PROOF. Fix a feasible overlap matrix in coordinate order v,x,y,
D = ( 1 r+d r-d ; r+d 1 q ; r-d q 1 ),
satisfying the event in (7.3). First impose the extra restriction
|q-Gamma(q)| <= rho^13. (7.4)
For an excluded pair overlap, (4.4) already gives a pressure deficit of
at least rho^26/2; at the end we apply Lemma 4.2 to these deficits and
sum over the at most n+1 pair overlaps, and the independent third draw
does not change their total probability.
The strict loss is already visible in the minimizing scalar data: the
identity Gamma'(r)=1 normalizes beta^2 E chi_r^2 to one, while the
conditional susceptibility evolution decreases the mixed moment,
beta^2 E[chi_q chi_r] <= 1 - c(q-r),
with a uniform c>0 verified in Step 8. We build a covariance perturbation
whose quadratic pressure change contains this deficit; its much larger
Gaussian variance cancels against the interpolation penalty.
STEP 1. FINITE SCALAR DATA AND BASE HIERARCHY. For large n the overlap
restrictions give 0<r-h<r<r+h<q<=1. Take increasingly fine partitions of
[0,1] containing r-h,r,r+h,q. On each half-open segment approximate
alpha by its value at the left endpoint; set its value at 1 to 1. These
nondecreasing step distribution functions converge in L^1 and preserve
the actual values at the four points. In particular each satisfies
alpha(r+h)-alpha(r-h) <= rho^4. (7.5)
During the finite computations omit the approximation index; the step
measures need not minimize, and stationarity is used only after passing
to the minimizing limit.
Index the integrated covariance increments: Q_0=0, Q_l-Q_{l-1}>=0, masses
m_l in [0,1], field covariances beta^2(Q_l-Q_{l-1}). Write Q_end=Q_N and
int m d|Q|^2 = sum_{l=1}^N m_l ( |Q_l|^2 - |Q_{l-1}|^2 ).
Prepending a zero-covariance quenched level matches Proposition 2.3. We
use zero terminal multiplier, so the terminal function is the sum of the
three scalar log(2 cosh).
Build the base path Q in three stages:
(i) 0..r: all three share the increment of variance beta^2 ds at mass
alpha(s)/3;
(ii) r..q: v has its own scalar branch at mass alpha(s), x,y share a
branch at mass alpha(s)/2, independent Gaussian increments, the two
finite schedules merged in nondecreasing mass order preserving each
branch's order;
(iii) q..1: three independent scalar increments on each segment, mass
alpha(s).
This is the base hierarchy of Section 4.2 with the finite approximation.
The merged schedule is nondecreasing and every increment is positive
semidefinite. Writing Psi_0 for the recursive value, the block-size
cancellation gives
Psi_0 - (beta^2/4) int m d|Q|^2
= 3 Phi(0,0) - (3 beta^2/2) int_0^1 s alpha(s) ds
= 3 P_beta(alpha). (7.6)
The endpoint is D with d=0, and the base tilted law is identified: after
the common path through r, the x,y branch and the v branch each carry the
scalar transition law. Denote these paths by X^x and X^v; they coincide
through r and then run to q on their separate clocks, and a frozen
branch's additive value cancels from every active normalized kernel, so
merging the schedules preserves conditional independence. Writing X_0 for
the common prefix through r and K_{r,z} for the scalar path law from
(r,z) to q,
L( X^x_[r,q], X^v_[r,q] | X_0 ) = K_{r,X_r} (x) K_{r,X_r}. (7.7)
In particular, knowing the whole x branch reveals no extra future noise
of the v branch.
STEP 2. A PERTURBATION PRESERVING POSITIVE SEMIDEFINITENESS. Set
theta=rho^2, a=1-theta and the linear combinations of field increments
Y_0 = ( (X^x_r - X^x_{r-h}) - (X^x_{r+h} - X^x_r) ) / h,
Y_1 = ( X^v_{r+h} - X^v_r ) / h, Y = a Y_0 + theta Y_1. (7.8)
Under the raw law these are Gaussian linear expressions; under the base
tilted law they use the scalar paths just identified. Y_0 includes the
common increment before the split and the x increment after; Y_1 uses the
post-split increment on the v branch.
At each level of the first two stages, add d times that level's
contribution to Y to the x field and subtract it from the y field, leaving
v unchanged. Each modified increment is a deterministic linear image of
its original Gaussian increment, so its covariance is positive
semidefinite and distinct-level increments stay independent. This is an
admissible path Q~ with the original masses; at the end of the second
stage the added fields are 0, dY, -dY.
For a prefix, let K_c be the accumulated raw variance of Y divided by
beta^2, and g_v,g_x its raw covariances with the base v,x fields in the
same units (its covariance with the base y field equals g_x). The
coefficients on the three active intervals are a/h,-a/h,theta/h, so
K = (2a^2+theta^2)/h, g_v^end = a+theta = 1, g_x^end = a-a = 0. (7.9)
With e_v,e_x,e_y the coordinate vectors and L_2=(e_x-e_y)(e_x-e_y)^T, at
every prefix
Q~ = Q + d L_1 + d^2 K_c L_2,
L_1 = ( 0 g_v -g_v ; g_v 2g_x 0 ; -g_v 0 -2g_x ). (7.10)
For the Frobenius product, Q and L_2 are both orthogonal to L_1, with
|L_1|^2=4 g_v^2+8 g_x^2 and |L_2|^2=4, so
|Q~|^2-|Q|^2 = d^2( 4 g_v^2+8 g_x^2+2 K_c Q:L_2 ) + 4 d^4 K_c^2. (7.11)
The endpoint is Q~_end=D+d^2 K L_2, possibly with nonunit diagonal; we
use the arbitrary-endpoint comparison of Proposition 2.3, whose mismatch
cost is
(beta^2/4)|D-Q~_end|^2 = beta^2 d^4 K^2. (7.12)
STEP 3. THE PENALTY GAIN. The base x,y fields coincide before the third
stage, so Q:L_2=0 there; in the third stage Q:L_2=2(s-q) and K_c=K is
fixed. The term 2 K_c Q:L_2 in (7.11) thus contributes beta^2 d^2 K A(q)
to the penalty. For the rest put
I = int m ( d(g_v^2) + 2 d(g_x^2) ).
Before the split, on [r-h,r], both covariances grow from 0 to a at mass
alpha/3, contributing alpha(r)a^2+O(rho^4); on the active v steps g_v
grows from a to a+theta with g_x fixed, alpha(r)(2a theta+theta^2)
+O(rho^4); on the active shared x,y steps g_x decreases from a to zero
with g_v fixed, and the factor 2 cancels the factor 1/2 in their masses,
giving -alpha(r)a^2+O(rho^4). The error in replacing each mass by
alpha(r) is controlled by (7.5) times the total variation of the relevant
covariance square, uniformly bounded over partitions and interleavings.
Hence
I = alpha(r)(2a theta+theta^2) + O(rho^4). (7.13)
Since K_c is nondecreasing and the masses are nonnegative, the
fourth-order contribution int m d(K_c^2) is nonnegative. Combining,
(beta^2/4) int m d( |Q~|^2 - |Q|^2 )
>= beta^2 d^2 ( K A(q) + alpha(r)(2a theta+theta^2) - C rho^4 ). (7.14)
STEP 4. THE RECURSIVE-VALUE COST. Let Psi~ be the modified one-site
value. Integrating the unchanged third stage backwards leaves the
boundary difference
U = Phi(q, X_q^x + dY) + Phi(q, X_q^x - dY) - 2 Phi(q, X_q^x). (7.15)
View this as a function of the full raw Gaussian prefix through the
second stage and let E_0 be expectation under its base tilted law. The
kernel comparison (4.11), with the entire raw prefix as the state (Y uses
several increments), gives
Psi~ - Psi_0 <= log E_0 e^U. (7.16)
The ratio of defining integrals still yields the kernel induction, and
no inverse transformation of the fields is used, so singular covariance
increments cause no difficulty; every kernel is from the base hierarchy,
whose tilted prefix law was identified in Step 1.
Write chi_q=chi(q,X_q^x). By Lemma 3.1,
0<=U<=d^2 Y^2, |U - d^2 chi_q Y^2| <= C_beta|d Y|^3. (7.17)
Under E_0 the diffusion representation writes Y=G+B_*, with G a centered
Gaussian of variance beta^2 K and |B_*|<=C_beta (each drift bounded by
beta^2, integrated for time h, divided by h). No independence between G
and B_* is needed. Since d^2/h=O(rho^32), Gaussian exponential moments
and |Y|<=|G|+C_beta give, for large n,
E_0|Y|^3 <= C_beta h^{-3/2}, E_0[ Y^4 e^{d^2 Y^2} ] <= C_beta h^{-2}.
Using e^u<=1+u+(1/2)u^2 e^u (u>=0), then log(1+z)<=z, then (7.17),
log E_0 e^U <= d^2 E_0[chi_q Y^2]
+ C_beta( |d|^3 h^{-3/2} + d^4 h^{-2} ). (7.18)
So everything reduces to E_0[chi_q Y^2]: its Gaussian variance term will
cancel the K A(q) part of the penalty up to the pair deviation, and the
strict gain must come from the mixed moment of Y_0 and Y_1.
STEP 5. THE TENT ON THE FIRST BRANCH. We will prove
E_0[chi_q Y^2] <= beta^2 K E_0 chi_q
+ 2 a theta beta^4 alpha(r) E_0[chi_q chi_r] + C_beta(rho^4+theta^2), (7.19)
with chi_r=chi(r,X_r^x).
For the scalar x path through q, partition 0=s_0<...<s_N=q with masses
m_j^sc=alpha(s_j). The normalized tilted density D_x relative to the raw
Gaussian increments has logarithm
log D_x = sum_{j=0}^{N-1} m_j^sc ( Phi(s_{j+1},X^x_{s_{j+1}})
- Phi(s_j,X^x_{s_j}) ), (7.20)
the scalar masses appearing because the base-law factorization of Step 1
has cancelled the divided matrix masses.
Let T be the continuous piecewise linear tent supported on [r-h,r+h],
zero at both endpoints and equal to one at r. For functions of the raw
cumulative coordinates, let d denote the derivative obtained by replacing
X^x_s with X^x_s+t T(s) and differentiating at t=0. Under the raw law,
Cov_raw(Y_0,X^x_s) = beta^2 T(s), Var_raw(Y_0) = 2 beta^2/h.
Finite-dimensional Gaussian integration by parts gives
E_raw[Y_0 f] = beta^2 E_raw[d f],
E_raw[Y_0^2 f] = (2 beta^2/h) E_raw f + beta^4 E_raw[d^2 f]. (7.21)
(Verify by multiplying the Gaussian density by exp(t Y_0
- t^2(2 beta^2/h)/2), which shifts every cumulative coordinate by
t beta^2 T(s); one and two differentiations give the two identities.
These act on raw coordinates, not on the tilted SDE's solution map.)
Telescope (7.20). Since T(0)=T(q)=0, only internal coefficients
m_{j-1}^sc - m_j^sc remain:
d log D_x = sum_{j=1}^{N-1}(m_{j-1}^sc-m_j^sc) T(s_j) u(s_j,X^x_{s_j}),
d^2 log D_x = sum_{j=1}^{N-1}(m_{j-1}^sc-m_j^sc) T(s_j)^2 chi(s_j,X^x_{s_j}).
Only points strictly between r-h and r+h contribute, and the sum of the
absolute coefficients there is at most alpha(r+h)-alpha(r-h). Thus
|d log D_x| <= rho^4, |d^2 log D_x| <= rho^4. (7.22)
This includes an atom at r; atoms at r-h or r+h contribute zero because
the tent vanishes there, and no continuity of alpha is assumed.
The endpoint q lies outside the tent, so d chi_q=0. Apply the second
identity of (7.21) to f=D_x chi_q:
E_0[chi_q Y_0^2] = (2 beta^2/h) E_0 chi_q
+ beta^4 E_0[ chi_q ((d log D_x)^2 + d^2 log D_x) ]
= (2 beta^2/h) E_0 chi_q + O_beta(rho^4). (7.23)
At the tent's peak put u_r=u(r,X_r^x), so d u_r=chi_r. Applying the first
identity of (7.21) to f=D_x chi_q u_r,
E_0[chi_q Y_0 u_r] = beta^2 E_0[chi_q chi_r]
+ beta^2 E_0[chi_q u_r d log D_x]
= beta^2 E_0[chi_q chi_r] + O_beta(rho^4). (7.24)
STEP 6. THE RAMP ON THE OTHER BRANCH AND THE MIXED MOMENT. Condition on
the entire path X^x through q. The product law of Step 1 leaves the v
branch as a scalar diffusion from the fixed value X_r. On [r,r+h] its
conditional tilted density has the form (7.20) starting at r. Use the
ramp S(s)=(s-r)/h and the raw-coordinate derivative d_v. The raw
covariance of Y_1 with the cumulative coordinate at s is beta^2 S(s), and
its raw variance is beta^2/h.
Let ell_v be this branch's conditional log density. Telescoping its
derivative gives the terminal term m_last u(r+h,X^v_{r+h}) and internal
terms with total absolute coefficient at most m_last-m_first<=1; the
initial value is fixed and the ramp vanishes there. With |u|<=1, chi<=1,
|d_v ell_v| <= 2, |d_v^2 ell_v| <= 2.
The conditional second integration-by-parts identity gives
E_0[Y_1^2|X^x] = beta^2/h
+ beta^4 E_0[ (d_v ell_v)^2 + d_v^2 ell_v | X^x ]
= beta^2/h + O_beta(1), (7.25)
uniformly in the starting field X_r. Multiplying by the X^x-measurable
chi_q and averaging,
E_0[chi_q Y_1^2] = (beta^2/h) E_0 chi_q + O_beta(1).
For the mixed moment use the conditional first moment of Y_1. The
Brownian increment has conditional mean zero, and the arbitrary-start
martingale identity (3.1c) gives E_0[u(z,X^v_z)|X^x]=u_r (the independent
branch starts at X_r), so the drift representation gives exactly
E_0[Y_1|X^x] = (beta^2/h) int_r^{r+h} alpha(z) E_0[u(z,X^v_z)|X^x] dz
= beta^2 alpha_bar u_r, alpha_bar = (1/h) int_r^{r+h} alpha(z) dz. (7.26)
Conditioning on the whole x path adds no conditioning on the v branch's
future noise. Moreover (7.5) gives |alpha_bar-alpha(r)|<=rho^4; and
Y_0,chi_q,u_r are X^x-measurable. Combining (7.24) with (7.26),
E_0[chi_q Y_0 Y_1] = beta^2 alpha_bar E_0[chi_q Y_0 u_r]
= beta^4 alpha(r) E_0[chi_q chi_r] + O_beta(rho^4). (7.27)
Finally expand Y^2=a^2 Y_0^2+2a theta Y_0 Y_1+theta^2 Y_1^2; (7.9),
(7.23), (7.25) and (7.27) prove (7.19). The distinction between the two
errors matters: the tent contributes O_beta(rho^4), while the ramp's
O_beta(1) error is multiplied by theta^2.
STEP 7. PASSING THE PRESSURE COMPARISON TO THE MINIMIZER. Apply (2.3) to
the modified finite hierarchy and combine the base value, mismatch,
penalty, recursive comparison and moment estimates (7.6),(7.12),(7.14),
(7.16),(7.18),(7.19). Since K=O(h^{-1}), the endpoint cost is part of the
d^4 h^{-2} error. Discarding the nonpositive term -beta^2 d^2
alpha(r)theta^2,
F_{3,n}(D) <= 3 P_beta(alpha)
+ d^2 { beta^2 K (E_0 chi_q - A(q))
+ 2 a theta beta^2 alpha(r)
( beta^2 E_0[chi_q chi_r] - 1 )
+ C_beta(rho^4+theta^2) }
+ C_beta( |d|^3 h^{-3/2} + d^4 h^{-2} ), (7.28)
constants independent of the partition.
Keep n,r,q,d fixed and send the mesh to zero. Lemma 3.1 gives uniform
convergence of the scalar derivatives and L^1 stability of values; coupling
the diffusions with the same Brownian motion (drifts bounded and
Lipschitz), L^1 convergence of alpha plus uniform convergence of u gives
path convergence by Gronwall. The bounded expectations in (7.28)
converge, as do A(q) and the scalar functional (to P_beta), every
approximation using the actual alpha(r). This limit is at fixed h, so it
needs no approximation rate uniform as h down to 0. Returning to the
minimizing data, with E the scalar-process expectation,
F_{3,n}(D) <= 3 P_beta
+ d^2 { beta^2 K (E chi_q - A(q))
+ 2 a theta beta^2 alpha(r)( beta^2 E[chi_q chi_r] - 1 )
+ C_beta(rho^4+theta^2) }
+ C_beta( |d|^3 h^{-3/2} + d^4 h^{-2} ). (7.29)
In the product chi_q chi_r both susceptibilities are on the same scalar
path.
STEP 8. THE STRICT QUADRATIC MARGIN AND THE SCALES. The identity (7.2) and
the scalar evolution imply beta^2 E chi_r^2 = Gamma'(r) = 1. Multiply the
conditional susceptibility identity (3.1e) by chi_r and average:
beta^2 E[chi_q chi_r] = 1 - beta^4 int_r^q alpha(z) E[chi_z^2 chi_r] dz
<= 1 - c(q-r) <= 1 - c rho, (7.30)
with a uniform c>0 over the allowed r,q. For uniformity, including q=1,
use the drift bound to get sup_{s<=1}|X_s| <= beta sup_{s<=1}|B_s| + beta^2.
Choose a fixed M so that the right side is at most M on an event of
probability p_M>0. Continuity and strict positivity of chi give
c_M := min_{0<=s<=1, |z|<=M} chi(s,z) > 0, hence E[chi_z^2 chi_r] >=
p_M c_M^3. Also alpha(z)>=alpha(t_0/2)>0 when z>=r. So c =
beta^4 alpha(t_0/2) p_M c_M^3 works. This uses positivity on a compact
set, not a lower bound for chi on all of R.
The all-time stationarity identity (3.6) and the pair restriction (7.4)
give E chi_q - A(q) = alpha(q)(q-Gamma(q)) <= rho^13. Since K=O(rho^{-8}),
the first brace term in (7.29) is at most C_beta rho^5. For large n
a>=1/2; with theta=rho^2, alpha(r)>=alpha(t_0/2)>0 and (7.30), the second
term is at most -c_1 rho^3. The remaining brace term is O_beta(rho^4). The
last two errors, after division by d^2, satisfy C_beta|d| h^{-3/2} <=
C_beta rho^8 and C_beta d^2 h^{-2} <= C_beta rho^24. Every positive error
is smaller than the negative rho^3 contribution for large n. Uniformly
over the feasible matrices,
F_{3,n}(D) <= 3 P_beta - c_2 d^2 rho^3 <= 3 P_beta - c_2 rho^43. (7.31)
STEP 9. FROM PRESSURE DEFICITS TO THE PROBABILITY. The choice
kappa=1/10000 satisfies 43 kappa < 1/24, so the deficit (7.31) dominates
the finite-size error required by Lemma 4.2. For each feasible triple
matrix that lemma gives two exponential bounds with exponents at least
constant multiples of n rho^43 and n rho^86; the latter equals
n^{1-86 kappa} = n^{0.9914}. Sum over the at most (n+1)^3 triple
matrices.
For the pairs removed in (7.4), (4.4) and Lemma 4.2 give exponents at
least constant multiples of n rho^26 and n rho^52 = n^{0.9948}, summed
over the at most n+1 pair overlaps. The fixed constants and polynomial
counts in both sums are absorbed by exp(-n^{4/5}) for large n, proving
(7.3). QED
----------------------------------------------------------------
8. REFERENCE BANKS, CROSSINGS, AND SLOW MIXING
----------------------------------------------------------------
All static inputs are ready. It remains to use them along a path:
coverage selects references, fixed-scale locking (Section 4) controls
incompatible references, and narrow-annulus locking (Section 7) preserves
constraints during backwards searches. We reduce Theorem 1.1 to a sign
passage, build the references, and bound the probability of all threshold
constraints. As before L=n^kappa, rho=n^{-kappa}, and constants may
depend on the fixed beta but not on n.
8.1 Stationary paths and a sign-passage criterion.
Given J, start the discrete heat-bath chain (x_k)_{k>=0} at x_0~pi^J;
each step picks a uniform site and resamples it from the conditional
Gibbs law. Stationarity gives marginal pi^J at every deterministic index.
For N an independent rate-n Poisson process, x_{N(t)} has conditional
transition kernel P^J_t from the realized x_0. Work up to
m = ceil(e^{2L}). (8.1)
Markov's inequality gives
P{ N(e^L)>m } <= n e^L/m <= n e^{-L} = o(1). (8.2)
For every fixed v, R(v,x_k) changes by at most 2/n in one step.
A bank is an ordered list of independent pi^J samples; given J the raw
entries are mutually independent and independent of the whole path, with
sizes deterministic in n. A chosen reference may be reversed at
selection, and that orientation is fixed thereafter.
Suppose a first bank selects v_1 with R(v_1,x_0)>=q_*, the choice and
orientation depending only on J,x_0 and this bank. Let S be successful
selection and define the sign-passage event
A = S cap { R(v_1,x_k)<=0 for some 0<=k<=m }.
Also let M={ ||P^J_{e^L}(x_0,.)-pi^J||_TV <= 1/4 }. Spin-flip symmetry
gives, for every oriented v, pi^J{ z: R(v,z)<=0 } >= 1/2. Condition on
J,x_0 and successful first-bank selection; that selection uses no future
updates, so the path and clock keep their conditional laws. On M, total
variation puts conditional probability at least 1/4 on the opposite-sign
half-space at time e^L. Removing clock overruns,
P(A) >= (1/4) P(M cap S) - P{ N(e^L)>m }. (8.3)
So it suffices to make the first reference available with probability
tending to one and its sign passage improbable.
Choose b in (0,1) at most the small-overlap cutoff of Lemma 4.1 with
large-overlap cutoff q_*, then b' in (0,b) at most that lemma's
small-overlap cutoff with large-overlap cutoff b. Fix t_0>0 small with
4 t_0 < min{ q_*, b', b^2/2 }. (8.4)
Write eta_n = n^{-1/100} = rho^{100} for the fixed-scale locking scale.
(8.5)
8.2 The case with a fixed forbidden overlap interval.
There are two scalar regimes. First, suppose Gamma(z)=z fails at some
point of (t_0/2,3t_0). Continuity gives fixed t_0/2<a_0<a_1<3t_0 and
d_0>0 with |q-Gamma(q)|>=d_0 for q in [a_0,a_1]. The pair gap (4.4),
Lemma 4.2 and the polynomial number of feasible pair overlaps give, for
some c>0 and large n,
E[ (pi^J)^{x2}{ (v,x): R(v,x) in [a_0,a_1] } ] <= e^{-c n}. (8.6)
Apply Proposition 6.1 with D_1=3, let D_3 be its constant, and take a
single bank with K=ceil(exp((D_3+1)L)) entries. Select its first entry
with |R(v,x_0)|>=q_*, oriented to give positive overlap. On the coverage
event, the Gibbs mass of starting states whose qualifying neighborhood
has mass below e^{-D_3 L} is at most e^{-3L}; for every other starting
state the independent bank misses that neighborhood with probability at
most e^{-e^L}. Hence P(S)->1.
At a deterministic k<=m the path point and a fixed signed bank entry are
independent Gibbs draws given J. Summing (8.6) over entries, signs and
indices,
P{ R(sigma v,x_k) in [a_0,a_1] for some entry v, sigma in {-1,1},
k<=m } <= 2 K (m+1) e^{-c n} = o(1).
For large n, a sequence beginning at overlap at least q_*>a_1 and
reaching nonpositive overlap, with jumps at most 2/n<a_1-a_0, must visit
[a_0,a_1]. Hence P(A)->0, and with (8.3) this proves the theorem in this
case.
In the second regime,
Gamma(z)=z for t_0/2<z<3t_0, (8.7)
and we set h=rho^8, epsilon=rho^20 (as in Section 7).
8.3 Thresholds and simultaneous bank properties.
Define fixed integers and the number of levels by
H_0 = ceil(2/b^2), B = H_0+2, p = B floor( t_0/(5 B rho) ). (8.8)
For large n, p>=B. Split the p levels into consecutive blocks of B levels.
At the first level of every block after the first we reset the selection
cell to the whole space; older retained references are kept unless they
meet the conflict rule below. Independently of everything, draw thresholds
r_i uniform on
I_i = [ t_0+4(i-1)rho, t_0+(4(i-1)+1)rho ]. (8.9)
These lie in [t_0,2t_0] and r_j-r_i>=3rho for i<j (8.10). Fubini gives
E[mu([r_i-2h,r_i+2h])]<=4h/rho, so Markov plus a union bound shows that
T = { mu([r_i-2h,r_i+2h])<=rho^4 for every 1<=i<=p } (8.11)
satisfies P(T^c)<=4ph/rho^5=O(rho^2). The Fubini step includes atoms; no
regularity of the minimizing measure is imposed.
There is a bank B_j at each level. Its size must cover the number of
earlier reference tuples in the current block. Using all preceding levels
would give a recursion of growing depth p, whose coverage constants are not
uniform in n. The reset confines the recursion to B fixed steps, so bank
sizes depend only on the position within a block and the total number of
samples is exp(O(L)). Older retained references still enter the crossing
constraints below.
We require coverage for every possible earlier tuple in the current block:
for entries u_i in B_i from those earlier levels define
S = { z: |R(u_i,z)|<=3 t_0 for every index in this tuple }, (8.12)
the empty tuple giving the whole space, and require
x_k in S, 0<=k<=m => some w in B_j cap S has |R(w,x_k)|>=q_*. (8.13)
Absolute values make this insensitive to orientation. Choose bank sizes
recursively over the fixed positions s=1,...,B: once smaller positions are
fixed, set
C_s = sum_{u<s}( D_{3,u}+2 ), D_{1,s} = C_s+5,
let D_{3,s} be a constant supplied by Proposition 6.1 for D_{1,s}, and use
K_s=ceil(exp((D_{3,s}+1)L)) entries at position s. For large n the number
of earlier tuples in the block is at most exp(C_s L). Only B fixed
applications of coverage are needed, so their disorder events intersect in
an event D with P(D)->1.
Fix a level at position s, J in D, and its earlier bank lists. Each cell
S has a bad subset
B_S = { x in S: pi^J{z in S: |R(z,x)|>=q_*} < e^{-D_{3,s}L} }
of Gibbs mass less than e^{-D_{1,s}L}. The path is independent of those
lists given J, and each deterministic-index marginal is pi^J, so a union
bound over tuples and indices gives
P{ some x_k lies in its cell's bad subset } <= (m+1) e^{(C_s-D_{1,s})L}
= O(e^{-3L}).
After excluding these, condition also on the whole path. The present bank
is still fresh, and its chance of missing a qualifying neighborhood is
(1-e^{-D_{3,s}L})^{K_s} <= e^{-e^L}. Union over the same tuples and
indices, then over the p=O(L) levels, shows (8.13) holds simultaneously
with probability 1-o(1); the recursion has only B steps, so the total
number of entries is exp(O(L)).
We also impose simultaneous avoidance of the exceptional triples in Lemma
4.1 (for the two cutoff pairs (q_*,b) and (b,b')) and in Lemma 7.1, for
every ordered triple of signed entries from distinct banks and every
ordered triple of two signed entries from distinct banks and one path
point x_k. For each deterministic choice the conditional law given J is
(pi^J)^{x3} (bank independence, stationarity at that deterministic index,
spin-flip symmetry). There are exp(O(L)) such choices, each with
exceptional probability at most C(e^{-n^{9/10}}+e^{-n^{4/5}}); a union
bound makes all these assertions simultaneous with probability 1-o(1). Let
G be the intersection of this event, the simultaneous bank property, and
T. Then
P(G^c)=o(1). (8.14)
All estimates are made before any reference or crossing time is chosen,
so later application at a backwards crossing uses this deterministic-index
event, not a claim of stationarity at a random time.
8.4 Backwards searches and deletion of conflicts.
Select v_1 from B_1 as the first entry with |R(v_1,x_0)|>=q_*, oriented
positive. If it exists, let tau_1 be the first k<=m with R(v_1,x_k)<=r_1;
on success the retained list is A_1={1}.
At a later level j, assuming all earlier levels succeeded, form the cell
(8.12) using the selected references in earlier positions of the current
block. Choose v_j as the first entry of B_j lying in this cell with
|R(v_j,x_{tau_{j-1}})|>=q_*, oriented so that R(v_j,x_{tau_{j-1}})>=q_*.
From A_{j-1} delete the conflicts, i.e. those i with
|R(v_i,v_j)| > b; (8.15)
the remaining old indices are compatible. Search backwards from
tau_{j-1} for the first point with overlap at most r_j with v_j:
tau_j = max{ 0<=k<=tau_{j-1}: R(v_j,x_k)<=r_j } (8.16)
if nonempty. Add j to the compatible list to obtain A_j.
To exploit independence of each fresh threshold, define v_j on failure
realizations too. A missing candidate or missing crossing ends the
procedure; a candidate already selected before its crossing fails is kept
as that level's reference; at a level with no candidate, and after any
earlier failure, use the first entry of the bank without reversal. These
defaults serve the final conditional-probability calculation. Selection
and orientation of v_j use only thresholds earlier than r_j; its own
threshold is used solely for the crossing.
Now work deterministically on G cap A. We show that, for large n, every
level succeeds, reference 1 survives, and
|R(v_i,x_{tau_j})-r_i| <= 6 j epsilon (i in A_j), (8.17)
|R(v_i,v_l)-r_i| <= 6 j epsilon (i,l in A_j, i<l). (8.18)
The induction also keeps the current block complete: after level j, all
references from that block's first level through j remain. Deletions occur
only at the first level of a new block, and at most H_0 indices, forming a
suffix, are deleted then.
At level 1, coverage of the whole space supplies the reference; sign
passage forces the first crossing, where the one-step bound puts the value
in [r_1-2/n,r_1]. This starts the induction. We use
1/n << eta_n=rho^{100} << epsilon=rho^{20}, p epsilon=O(rho^{19}) <<
h=rho^8 << rho. (8.19)
Suppose the assertions hold through j-1. All earlier references in the
current block are still retained (no deletions within the block after its
first level). Their overlaps with x_{tau_{j-1}} have absolute value at
most 2t_0+6p epsilon<3t_0, so the target is in the required cell and the
new selection w=v_j exists by (8.13).
For each compatible old i, the two small overlaps in (v_i,w,x_{tau_{j-1}})
are at most b while R(w,x_{tau_{j-1}})>=q_*; fixed-scale locking gives
|R(v_i,w)-R(v_i,x_{tau_{j-1}})| <= 2 eta_n, (8.20)
hence |R(v_i,w)-r_i| <= 6(j-1)epsilon+2 eta_n for compatible i. (8.21)
CONFLICTS OCCUPY A BOUNDED FINAL SEGMENT. A conflicting i cannot precede a
compatible l. Indeed by (8.18),(8.21) the magnitudes of R(v_l,v_i) and
R(v_l,w) are within 6(j-1)epsilon and 6(j-1)epsilon+2eta_n of r_i and r_l,
both below b' by (8.4), and their difference in magnitude is at least
3rho-12p epsilon-2eta_n>2eta_n. But |R(v_i,w)|>b; reversing one of the
pair to make their mutual overlap positive, the signed difference of the
two small overlaps is at least their difference in magnitude, contradicting
fixed-scale locking with cutoff pair (b,b'), which holds for all signs on
G. Hence conflicts form a suffix.
The number of conflicts is at most H_0. The induction bounds all absolute
overlaps between retained old references by 2t_0+6p epsilon<3t_0. If
d>=1 of them conflict with w, normalize them to unit vectors and reverse
each to give inner product greater than b with w/sqrt n; call them
u_1,...,u_d. Then
d^2 b^2 < < sum_a u_a, w/sqrt n >^2 <= | sum_a u_a |^2
<= d + 3 t_0 d(d-1).
Since 3t_0<b^2/2, this gives d<(1-3t_0)/(b^2-3t_0)<2/b^2<=H_0, so d<=H_0.
If j is not the first level of its block, the most recent old index j-1 is
compatible (the cell gives |R(v_{j-1},w)|<=3t_0<b), so the conflict suffix
is empty. At the first level of a new block, all B entries of the preceding
block are present, so removing at most H_0<B final indices cannot reach any
older block or the first index of the preceding block. In particular index
1 survives, including at the first reset. Adding the new index starts the
current block (or extends a complete one, with no deletion); this proves
the invariant and deletion claims.
THE BACKWARDS SEARCH PRESERVES OLD CONSTRAINTS. Following the search for
tau_j (including the crossing step when present), the new reference obeys
R(w,x_k) >= r_j - 2/n (8.22)
throughout. If there is no crossing this holds with the strict bound
R(w,x_k)>r_j down to zero; if there is a crossing, indices strictly after
it have overlap above r_j, and the jump bound gives (8.22) at the crossing.
For each compatible old v_i, (8.21) places R(v_i,w) near r_i, and the
larger threshold r_j separates. Narrow-annulus locking will show
|R(v_i,x_k)-R(v_i,w)| < 2 epsilon (8.23)
on the whole searched portion, (8.20) giving it at the target. At a first
violation while moving backwards the left side lies in
[2epsilon,2epsilon+2/n]. Use the Lemma 7.1 parameters of this triple,
r = (R(v_i,x_k)+R(v_i,w))/2, d = (R(v_i,x_k)-R(v_i,w))/2,
q = R(w,x_k).
Then epsilon<=|d|<=2epsilon and |r-r_i|<=6(j-1)epsilon+2eta_n+epsilon+1/n<h.
It follows that t_0/2<r<3t_0 and [r-h,r+h] subset [r_i-2h,r_i+2h], so T
gives mu([r-h,r+h])<=rho^4. Also, by (8.10),(8.22),(8.19),
q - r >= 3rho - 6(j-1)epsilon - 2eta_n - epsilon - 3/n >= rho.
All hypotheses of the forbidden narrow-annulus event hold, contradicting
its simultaneous avoidance on G, so (8.23) is proved.
The crossing must exist: otherwise the search reaches index 0, and
(8.21)-(8.23) apply there to the surviving reference 1, giving
R(v_1,x_0)<r_1+6(j-1)epsilon+2eta_n+2epsilon<q_*, contradicting the first
selection. So the crossing exists, its new reference overlap lies in
[r_j-2/n,r_j], and each retained old error at the crossing is at most
6(j-1)epsilon+2eta_n+2epsilon<=6j epsilon, while old-new errors satisfy
(8.21) and old-old errors are unchanged. This proves (8.17)-(8.18) and the
induction.
There are at most p/B reset occasions, so |A_p|>=p-H_0 p/B>=p/B. (8.24)
Thus G cap A implies that for some k in {0,...,m} and some subset of p/B
indices,
|R(v_i,x_k)-r_i| <= 6 p epsilon (8.25)
hold simultaneously. Sign passage is reduced to this existence event; the
following probability bound does not condition on G or on the random
retained list.
8.5 Predictable thresholds and completion of the proof.
Let F_0 be generated by J, all raw bank lists and the path
(x_0,...,x_m), and set F_i=sigma(F_0,r_1,...,r_i). Each r_i is uniform on
I_i and independent of F_{i-1}. The failure conventions ensure each
oriented v_i is F_{i-1}-measurable: at level 1 the selection uses no
threshold; inductively the earlier success/failure state, the selected
references and the previous crossing time are determined by earlier
thresholds, and the crossing may use r_i but never changes the chosen
reference. A default from an earlier failure likewise depends only on
earlier thresholds.
For deterministic k<=m let E_i(k)={|R(v_i,x_k)-r_i|<=6p epsilon} and
gamma_n=12p epsilon/rho. The defining interval has length at most
12p epsilon while I_i has length rho, so for large n
P(E_i(k)|F_{i-1}) <= gamma_n < 1. (8.26)
For a deterministic subset i_1<...<i_s, the earlier events
E_{i_1}(k),...,E_{i_{s-1}}(k) are F_{i_s-1}-measurable, so conditioning
first at the largest index and using (8.26) yields
P( cap_{a=1}^s E_{i_a}(k) ) <= gamma_n^s. (8.27)
The elimination order is essential (latest threshold integrated out
first); later centers may depend on earlier thresholds, but the
conditioning stays valid, and neither the random retained subset nor G is
conditioned on.
Take s=p/B and a union over deterministic subsets and indices:
P{ (8.25) holds for some k and some subset of size p/B }
<= (m+1) 2^p ( 12p epsilon/rho )^{p/B} = o(1). (8.28)
Indeed p=(t_0/5)L+O(1), rho=L^{-1}, and 12p epsilon/rho=O(rho^{18}); the
logarithm of the right-hand side is at most
2L+O(p)-(18p/B)log(1/rho) = -Omega(L log L).
Now (8.14) and the deterministic induction give
P(A) <= P(G^c) + P(G cap A) = o(1).
The first selection succeeds on the simultaneous bank event at level 1, so
P(S^c)=o(1). Finally (8.3) and (8.2) give
P(M) <= P(S^c) + 4 P(A) + 4 P{ N(e^L)>m } = o(1),
proving Theorem 1.1 under (8.7); the two regimes exhaust the possibilities.
DISCRETE TIME. Take T_n=floor(e^L) discrete attempts, below m for large n.
If its law is within 1/4 of equilibrium, the opposite half-space has
conditional probability at least 1/4 at that index, so the same
sign-passage inequality holds with no clock-overrun term. All bank,
locking and threshold estimates concern the discrete path, proving the
second assertion of Theorem 1.1 at exactly floor(e^L). QED
----------------------------------------------------------------
APPENDIX A. POLYNOMIAL COVERAGE
----------------------------------------------------------------
This appendix gives a self-contained coverage estimate at polynomial
scale: it proves (6.1) with n^{-D} in place of e^{-D L}. The threshold
q_* is chosen before D_1. The proof is the stretched-exponential argument
with L=log n; we keep it self-contained since the fixed-depth appendix
depends on it.
PROPOSITION A.1 (uniform polynomial coverage). Fix beta>1. There is
q_*=q_*(beta) in (0,1) with the following property. For every fixed
D_1>0 there is a constant D_3=D_3(beta,D_1)>0 such that, with disorder
probability tending to one, for every S subset Sigma,
pi^J{ x in S: pi^J{z in S: |R(x,z)|>=q_*} < n^{-D_3} }
< n^{-D_1}. (A.1)
PROOF. Let e_1 in (0,beta/2) and c_E>0 be from Lemma 5.1, and set
g = beta^2/4 - beta e_1/2 > 0,
0 < q_* < min{ 1, g/(8 beta^2) }, chosen once for A.1 and 6.1.
Fix D_1>0 and set
M = ceil( 8(D_1+1)/g ), D_2 = beta^2 M/2 + 2,
t = M log n / n, theta = arcsin sqrt t.
For large n, 0<t<1/2, t->0 and nt=M log n->infinity.
Let B_n be the event that the energy event of Lemma 5.1 holds and that
some S subset Sigma satisfies
pi^J(S) >= n^{-D_1}, (pi_S^J)^{x2}{ |R|>=q_* } < n^{-D_2}. (A.2)
We bound P(B_n) by choosing the first violating set. Order the subsets
deterministically; for a disorder in B_n take the first violating S(J).
Both Gibbs quantities in (A.2) are continuous in J for a fixed nonempty
set, so this selection is measurable, and once J is fixed, S(J) is fixed
and cannot depend on the independent disorder used next.
CONDITIONAL GAIN. Fix such a disorder, write pi=pi^J, and remove the
upper energy tail from the chosen set:
T = S cap { x: H^J(x)<=n e_1 }, nu = pi(.|T).
Since L=log n, for large n, e^{-c_E n}<=(1/2)n^{-D_1}, so
pi(T)>=pi(S)-e^{-c_E n}>=(1/2)pi(S)>=(1/2)n^{-D_1}. Comparing conditional
pair laws,
nu^{x2}{ |R|>=q_* } <= (pi(S)/pi(T))^2 (pi_S^J)^{x2}{ |R|>=q_* }
< 4 n^{-D_2} <= (1/2) n^{-D_2} (large n). (A.3)
Sample fresh G and set
W = nu( e^{beta sqrt t H^G} ), J' = sqrt(1-t) J + sqrt t G.
The measure nu is fixed by J, so it does not use G.
The off-diagonal normalization gives, for the fresh disorder,
E_G H^G(x)^2=(n-1)/2 and E_G[H^G(x)H^G(y)]=(n R(x,y)^2 - 1)/2. Two
Gaussian moments and (A.3) give
E_G W = e^{beta^2 t(n-1)/4},
E_G W^2/(E_G W)^2 = nu^{x2}( e^{beta^2 t(n R^2 - 1)/2} )
<= e^{beta^2 nt q_*^2/2} + 4 n^{-(D_2 - beta^2 M/2)}
<= 2 e^{beta^2 nt q_*^2/2}.
Paley--Zygmund yields, with A_0=beta^2 nt q_*^2/2,
P_G( W >= (1/2) E_G W ) >= (1/8) e^{-A_0}. (A.4)
Since nu is deterministic given G, log W is a function of G with
gradient |d log W/d G_ij|=|beta sqrt(t/n) nu(sigma_i sigma_j)|, so
|grad log W|^2<=beta^2 t(n-1)/2=:Sigma^2. Gaussian concentration of the
lower tail, combined with (A.4) exactly as in Section 6, upgrades (A.4)
to: for large n,
P_G( log W >= beta^2 t(n-1)/4 - beta^2 nt q_* - C_beta sqrt(nt)
- log2 ) >= 1/2. (A.5)
COMPARISON WITH THE ROTATION COST. Linearity in the disorder gives
Z^{J'}/Z^J = pi( e^{beta(sqrt(1-t)-1)H^J + beta sqrt t H^G} )
>= pi(T) e^{-beta n e_1(1-sqrt(1-t))} W,
because on T the energy is at most n e_1 and its coefficient
sqrt(1-t)-1 is negative while pi(T) W = sum_{x in T} pi(x)
e^{beta sqrt t H^G(x)}. Taking logarithms, inserting (A.5) and
pi(T)>=(1/2)n^{-D_1}, and using 1-sqrt(1-t)=t/2+O(t^2) uniformly for
0<t<1/2,
log( Z^{J'}/Z^J )
>= -D_1 log n - 2 log2
+ nt( g - beta^2 q_* - D_1/M - beta e_1 t/2 )
- C_beta sqrt(nt) - beta^2 t/4.
Since beta^2 q_*<g/8 and D_1/M<g/8, and nt=M log n->infinity,
log( Z^{J'}/Z^J ) >= (g/2) nt (A.6)
for all large n. Hence, for every disorder in B_n (in fact for every
disorder in the energy event),
P_G( log Z^{J'} - log Z^J >= (g/2) nt | J ) >= 1/2. (A.7)
Now average (A.7) over J and use the unconditional rotation bound (5.5):
P_J(B_n) <= 2 P_{J,G}( log Z^{J'} - log Z^J >= (g/2) nt )
<= 2 e^{-c'_\beta nt} = 2 n^{-c'_\beta M} -> 0.
(Here 2 P(B_n) bounds the joint probability of B_n and the gain event,
which has conditional probability at least 1/2 on B_n.) Adding
P_J(energy event^c)=o(1) proves P_J(any violating S exists)->0, i.e.
(A.2) fails for every S outside an event of probability o(1). This is
the simultaneous pair statement, with no union bound over subsets.
FROM PAIRS TO INDIVIDUAL TARGETS. Let V_n be the event that (A.2) holds
for some S; we have shown P_J(V_n)->0. Choose fixed D_3>D_1+D_2 and let
C_n(D_1)=V_n^c. Fix J in C_n(D_1) and any S, and let
B = { x in S: pi^J{z in S: |R(x,z)|>=q_*} < n^{-D_3} }.
If pi^J(B)>=n^{-D_1}, then since B subset S,
(pi^J(.|B))^{x2}{ |R|>=q_* }
= (1/pi^J(B)^2) sum_{x in B} pi^J(x) pi^J{y in B: |R(x,y)|>=q_*}
< n^{-D_3}/pi^J(B) <= n^{-(D_3-D_1)} < n^{-D_2},
contradicting (A.2)-failure applied to B. Hence pi^J(B)<n^{-D_1} for
every S, which is (A.1). QED
COROLLARY A.2 (target coverage within arbitrary subsets). Let the
constants be as in Proposition A.1. On C_n(D_1), for every S subset
Sigma and every fixed D_1'>0,
pi^J( { x in S: pi^J{z in S: |R(x,z)|>=q_*} < n^{-D_3} } )
< n^{-D_1'}, provided D_3-D_1>D_1'.
PROOF. The implication pi^J(B)>=n^{-D_1} => contradiction holds for any
B subset S; taking B equal to the set inside the outer pi^J in (A.1) and
using the displayed choice gives pi^J(B)<n^{-D_1}<=n^{-D_1'}. The
statement is deterministic on C_n(D_1) and holds for every S, including
sets chosen after seeing J. QED
----------------------------------------------------------------
APPENDIX B. A FIXED-DEPTH OBSTRUCTION AT POLYNOMIAL TIMES
----------------------------------------------------------------
The polynomial coverage of Appendix A has a direct dynamical
application. Together with the absolute-overlap locking estimate of
Section 4 it rules out mixing on each fixed polynomial time scale using
a fixed number of nested crossings. The number of levels and the
threshold intervals stay fixed as n grows, so delta_n=n^{-e_*} with
e_*=1/100 is used throughout.
THEOREM B.1 (fixed-depth crossings). For every fixed beta>1 and every
fixed a>0,
P_{J, x_0~pi^J}{ d^J(x_0,n^a) > 1/4 } -> 1, (B.1)
P_{J, x_0~pi^J}{ d^J_disc(x_0, floor(n^a)) > 1/4 } -> 1. (B.2)
Consequently P{T^J(x_0)>n^a}->1 and P{T^J_disc(x_0)>n^a}->1 under the
same joint law; equivalently the Gibbs mass of the indicated initial
states tends to one in probability over J.
As in the main theorem, the transition law starts from the realized x_0.
Stationarity samples possible targets along a path, and total variation
from the fixed initial state forces a sign passage whose probability the
independent thresholds make small.
B.1 Fixed path scales.
Use q_*=q_*(beta) of Proposition A.1. With e_1 from Lemma 5.1,
g=beta^2/4 - beta e_1/2>0, 0<q_*<min{1, g/(8 beta^2)}.
Choose an integer p>=2 with
p e_* > a + 2. (B.3)
This p is fixed. Choose t_p>0 with 2t_p<q_*/2, then for j=p,p-1,...,2
a cutoff b_j in (0,q_*/2) allowed by Lemma 4.1 for large-overlap
threshold h=t_j/2, and t_{j-1}>0 with
t_{j-1} < t_j/10, 4 t_{j-1} < b_j, 0<t_1<...<t_p. (B.4)
Independently of the disorder, draw r_j uniform on [t_j,2t_j] for
1<=j<=p, independently. Put
t_n=n^a, m=ceil(2 n^{a+1}), delta_n=n^{-e_*}. (B.5)
Conditional on J start x_0~pi^J and run the discrete heat-bath chain
(x_k)_{k>=0} with fresh resampling at each step (self-transitions
allowed). For a rate-n Poisson clock N independent of the chain, x_{N(t)}
is the continuous chain (its kernel is exp{nt(K^J-I)}=P^J_t). Stationarity
gives L(x_k|J)=pi for every deterministic k. Chernoff at log2, with
E N(t_n)=n^{a+1} and m>=2n^{a+1}, gives
eta_n := P{ N(t_n)>m } <= e^{-c n^{a+1}}. (B.6)
B.2 Polynomial banks and simultaneous properties.
For j=1,...,p sample a fresh bank B_j of independent pi^J samples; sizes
are M_j=ceil(exp((C_j+2) log n)) with constants chosen so the coverage
and locking failures below are o(1). For a tuple v from banks 1,...,j-1
define
S_j(v) = { x: |R(v_i,x)|<=3 t_i for every recorded index i }, (B.7)
so S_1 is the whole space.
LEMMA B.2 (simultaneous bank coverage). With probability 1-o(1), for
every 1<=j<=p, every tuple v from banks 1,...,j-1, and every 0<=k<=m,
x_k in S_j(v) implies some V_{j,l} in S_j(v) has |R(V_{j,l},x_k)|>=q_*.
The event depends only on J, the chain and the bank lists, and is
independent of the thresholds.
PROOF. Intersect the p disorder events of Corollary A.2. Since p is
fixed the intersection has probability 1-o(1). On it, for every S the
set of x in S with pi-mass of overlapping points below n^{-D_{3,j}} is
at most n^{-D_{1,j}}. Fix a disorder in this intersection and condition
on banks 1,...,j-1; each cell S_j(v) is fixed. The path is independent of
these banks given J, so the stationary marginal applies at every
deterministic k. A union bound over tuples and indices gives
P{ x_k in the bad subset for some v,k | J, banks< j } <= (m+1) n^{-D_{1,j}}
=o(1). The cell's pi-count of qualifying witnesses is at least n^{-D_{3,j}},
and the fresh bank of M_j samples misses it with probability at most
(1-n^{-D_{3,j}})^{M_j}=o(1). Summing gives the claim. QED
LEMMA B.3 (simultaneous locking). With probability 1-o(1), for every
1<=i<=j<=p, every tuple v from banks 1,...,i-1, every entry V_{i,l}, and
every 0<=k<=m,
D_{v_i}(k):=|R(v_i,x_k)|<=3 t_i and |R(v_i,x_k)-r_i|>2delta_n
=> no rescaling of the overlap yields the forbidden triple
(R(x,y)>=t_j/2 with both small overlaps <=b_j and differ by
more than delta_n).
PROOF. For fixed bank indices and deterministic k the triple
(v,x_k,w) has law pi^{x3} given J. Proposition 4.4 with h=t_j/2 and
cutoff b_j bounds the averaged failure probability by e^{-n^{9/10}}.
Only finitely many j meet the large-n threshold; a union bound gives
sum_{i<j}(m+1)M_iM_j e^{-n^{9/10}}=o(1),
a polynomial prefactor absorbed into the stretched-exponential. QED
Let G_n be the intersection of the two events. Then P(G_n^c)=o(1), and
G_n is determined by J, x_0,...,x_m and the bank lists; the thresholds
remain independent of G_n.
B.3 Deterministic nesting.
Suppose j>=2 and the earlier levels are defined. If active and
x_{tau_{j-1}} in S_j(v_1,...,v_{j-1}), select v_j as the first bank-j
entry in that cell with |R(v_j,x_{tau_{j-1}})|>=q_*. After a successful
selection search backwards:
tau_j=max{ 0<=k<=tau_{j-1}: D_{v_j}(k)<=r_j }, (B.8)
keeping active if this set is nonempty; otherwise retain v_j, set
tau_j=0 and deactivate. If inactive, outside the cell, or no witness,
use v_j=V_{j,1}, tau_j=0 and deactivate. An inactive construction stays
inactive. Successful selection gives depth at least q_*>2t_j>=r_j, so a
successful backwards crossing has tau_j<tau_{j-1}.
The filtration is W=sigma(J,x_0,...,x_m, all banks), F_0=W,
F_j=W v sigma(r_1,...,r_j). By induction v_j is F_{j-1}-measurable and
tau_j and the active flag are F_j-measurable: neither the selection of
v_j nor a default uses r_j or a later threshold.
Let C_1 be successful selection of the first witness. On C_1 set
s_1=sgn R(v_1,x_0) in {-1,1} and
S_n=C_1 cap { some 0<=k<=m has s_1 R(v_1,x_k)<=0 }. (B.9)
Take S_n false off C_1. Starting from signed overlap at least q_*, a
sign passage must visit absolute overlap at most 2/n, since signed
overlaps change by at most 2/n per step; for large n this forces the
first crossing in the sense of (B.8).
LEMMA B.4 (deterministic nesting). For all large n, on G_n cap S_n every
selection and crossing succeeds, and for every 1<=j<=p,
|D_{v_j}(tau_j)-r_j|<=2/n, (B.10)
|D_{v_i}(tau_j)-r_i|<=6 j delta_n (1<=i<=j). (B.11)
PROOF. At level 1, coverage supplies the witness and S_n the crossing;
the initial depth exceeds r_1, and minimality of tau_1 with the one-step
bound puts depth in [r_1-2/n,r_1]. Assume through j-1. For every i<j,
D_{v_i}(tau_{j-1}) <= 2t_i+6(j-1)delta_n < 3t_i (large n),
so the target is in its cell and coverage supplies v_j with new depth at
least q_*. Both D_{v_i}(tau_{j-1}) and |R(v_i,v_j)| are at most 3t_i<b_j
(since 3t_i<=3t_{j-1}<b_j), and the new depth at the target is
q_*>t_j/2. Locking gives
||R(v_i,v_j)|-r_i| <= |D_{v_i}(tau_{j-1})-r_i|+2delta_n
<= (6(j-1)+2)delta_n. (B.12)
Throughout the search after tau_{j-1}, (B.12) gives, for i<j,
|D_{v_i}(k)-r_i| <= (6(j-1)+4)delta_n. (B.13)
A crossing must occur, else at k=0 with i=1 this reads
q_*<=D_{v_1}(0)<=2t_1+(6(j-1)+4)delta_n<q_*. At the crossing the next
index toward the target has depth strictly above r_j, so
D_{v_j}(tau_j) in [r_j-2/n,r_j]; combining with (B.13) proves (B.10)-
(B.11). One n makes every buffer valid simultaneously. QED
B.4 Independent thresholds make the final shells unlikely.
Define, using the selected references including defaults,
A_n = { some 0<=k<=m has |D_{v_j}(k)-r_j|<=6p delta_n for all j<=p }.
(B.14)
Lemma B.4 at tau_p gives G_n cap S_n subset A_n.
For deterministic k let E_i(k)={|D_{v_i}(k)-r_i|<=6p delta_n} and
gamma_n=12p delta_n/min_j t_j. The interval in E_i(k) has length at most
12p delta_n while r_i has density at most 1/t_i<=1/min_j t_j on an
interval of that length; so for large n
P(E_i(k)|F_{i-1}) <= gamma_n < 1. (B.15)
For a deterministic subset i_1<...<i_s, the earlier events are
F_{i_s-1}-measurable, so conditioning at the largest selected index and
iterating,
P( cap_a E_{i_a}(k) ) <= gamma_n^s. (B.16)
The latest threshold is integrated out first; later centers may depend
on earlier thresholds but the conditioning stays valid, and neither a
random retained set nor G_n is conditioned on.
PROOF OF THEOREM B.1. Continuous time. Put
q_n=P_{J,x_0~pi}{d^J(x_0,t_n)<=1/4}. The first witness uses only
J,x_0 and bank 1. On C_1 let A={z: s_1 R(v_1,z)<=0}; spin reversal
preserves pi and swaps the signs of overlaps, so pi(A)>=1/2. Given J,x_0
with d^J(x_0,t_n)<=1/4 and any bank-1 realization with C_1, total
variation gives P{x_{N(t_n)} in A | J,x_0,bank 1}>=1/4. If N(t_n)<=m this
endpoint event implies S_n, and the clock is independent of the
conditioning variables, so the error (B.6) is uniform:
P(S_n) >= (1/4 - eta_n) P{ d^J(x_0,t_n)<=1/4, C_1 }
>= q_n/4 - eta_n - (1/4) P(C_1^c). (B.17)
The level-1 case of Lemma B.2 gives P(C_1^c)=o(1). Adding the independent
thresholds changes none of these probabilities. By (B.14),
P(G_n cap S_n) <= P(A_n) <= (m+1) 2^p gamma_n^p
= O( n^{a+1} n^{-p e_*} ) = O(n^{-(p e_*-a-1)}) = o(1),
using p e_*>a+2 and 2^p fixed. With P(G_n^c)=o(1), P(S_n)=o(1); then
(B.17) forces q_n->0, proving (B.1).
Discrete time. Take T_n=floor(n^a) attempts, below m for large n. If its
law is within 1/4 of equilibrium, the opposite half-space has conditional
probability at least 1/4 at that index, so the same sign-passage
inequality holds with no clock-overrun term; all bank, locking and
threshold estimates already concern the discrete path, giving (B.1) with
floor(n^a). This proves (B.2) and Theorem B.1. QED
----------------------------------------------------------------
REFERENCES
----------------------------------------------------------------
[1] D. Sherrington, S. Kirkpatrick, Solvable model of a spin-glass,
Phys. Rev. Lett. 35 (1975), 1792-1796.
[2] G. Parisi, A sequence of approximated solutions to the S-K model for
spin glasses, J. Phys. A: Math. Gen. 13 (1980), L115-L121.
[3] F. Guerra, Broken replica symmetry bounds in the mean field spin
glass model, Comm. Math. Phys. 233 (2003), 1-12.
[4] M. Talagrand, The Parisi formula, Ann. of Math. 163 (2006), 221-263.
[5] D. Panchenko, Free energy in the mixed p-spin models with vector
spins, Ann. Probab. 46 (2018), 865-896.
[6] G. Ben Arous, A. Jagannath, Spectral gap estimates in mean field
spin glasses, Comm. Math. Phys. 361 (2018), 1-52.
[7] M. Sellke, Exponentially slow mixing of the low temperature SK model,
preprint (2025), arXiv:2511.22621v2.
[8] J.-C. Mourrat, Free energy upper bound for mean-field vector spin
glasses, preprint (2020), arXiv:2010.09114.
[9] J. Barbier, N. Macris, The adaptive interpolation method for proving
replica formulas. Applications to the Curie-Weiss and Wigner spike
models, J. Phys. A: Math. Theor. 52 (2019), 294002.
[10] H. J. Brascamp, E. H. Lieb, On extensions of the Brunn-Minkowski and
Prekopa-Leindler theorems, including inequalities for log concave
functions, J. Funct. Anal. 22 (1976), 366-389.
[11] C. Monthus, T. Garel, Eigenvalue method to compute the largest
relaxation time of disordered systems, J. Stat. Mech. (2009), P12017.
[12] A. Billoire, Distribution of timescales in the
Sherrington-Kirkpatrick model, J. Stat. Mech. (2010), P11034.
[13] A. Auffinger, W.-K. Chen, Free energy and complexity for pure
p-spin models, and regularity of the Parisi functional; and the zero
external field result used for support properties.
[14] M. Talagrand, Mean Field Models for Spin Glasses (Volume I),
Springer, 2011.
[15] A. El Alaoui, A. Montanari, M. Sellke, Spectral gap of
replica-symmetric mean field models, and the sampling obstruction
(Theorem 2.6), preprint.
[16] A. Bandeira, A. El Alaoui, S. Rodder, polynomial worst-case mixing
with a large uniform external field (Corollary 1.2), preprint.
[17] W.-K. Chen, and A. Jagannath, Y. Tobasco, first-variation and scalar
regularity results for the Parisi functional used in Section 3.
============================================================
END OF DOCUMENT
============================================================