Background and relation to earlier work

Sherrington and Kirkpatrick introduced the model as a mean-field description of a spin glass [16]. Parisi’s variational description of its equilibrium free energy [14] was established rigorously through Guerra’s interpolation bound and Talagrand’s matching lower bound for the limiting pressure [9, 17]. These equilibrium results provide the scalar variational structure behind our argument. Passing from free energy to relaxation requires additional information about which overlap configurations a local trajectory can visit.

Ben Arous and Jagannath developed criteria that turn overlap free-energy barriers into exponentially small spectral gaps for mean-field spin glasses [4]. Their use of constrained replica pressures is an important antecedent of the overlap comparisons used here. Their barrier criteria require additional landscape hypotheses; the explicit Ising sufficient conditions in that work exclude the pure quadratic covariance of SK. They therefore do not directly give the present result throughout \(\beta>1\). For SK itself, Sellke proves exponentially slow worst-case Glauber mixing at sufficiently large inverse temperature [15]. That conclusion concerns the slowest initial states. It does not determine the Gibbs mass of the states that remain far from equilibrium after their initial configuration has been fixed.

The role of the external field is also substantial. Bandeira, El Alaoui, and Rödder prove polynomial worst-case mixing for lazy discrete heat-bath dynamics at every fixed inverse temperature when a sufficiently large constant uniform field is present, with high probability over the disorder [2]. Our result concerns zero field. Its distinctive combination is the entire range of fixed \(\beta>1\), Gibbs mass tending to one for realized initial states, and a stretched-exponential time scale. The exponent \(1/10000\) is not asserted to be optimal, and the constants in the proof may depend on \(\beta\); the argument does not give uniformity as \(\beta\) decreases to one.

El Alaoui, Montanari and Sellke prove a complementary obstruction to sampling at \(\beta>1\) for algorithms stable under disorder perturbations, in normalized \(2\)-Wasserstein distance [8]. Their stability hypothesis and approximation metric differ from the conditional Glauber transition law considered here.

Numerical studies have examined much sharper predictions for low-temperature relaxation. Billoire studies equilibrium autocorrelation times for binary couplings and sequential Metropolis updates [5]; Monthus and Garel compute inverse spectral gaps for small SK systems with Metropolis dynamics [11]. Both report evidence associated with an \(n^{1/3}\) scale for logarithmic relaxation times. Their observables and dynamics differ from the state-conditioned total variation distance studied here, and these numerical predictions do not fix the exponent in Theorem 1.

The static comparisons build on Guerra’s Gaussian interpolation framework [9] and Talagrand’s extensions to systems with prescribed replica overlaps [18]. Panchenko developed a general vector-spin formulation and proved the asymptotic sharpness of these constrained-overlap bounds [13]. Talagrand’s two- and three-copy bounds already retain an explicit cost when the prescribed overlaps differ from the covariance endpoint. In Section 2, we derive the finite-hierarchy matrix form needed here for the quadratic SK covariance, allowing arbitrary finite replica dimension and nonunit endpoint diagonals. The same section obtains a quantitative scalar free-energy comparison by choosing an interpolation path through a differential equation driven by overlap expectations. This choice has a methodological parallel in the adaptive interpolation method of Barbier and Macris [3]; their theorems are not inputs to our finite-size SK estimate. Gaussian concentration and the Brascamp–Lieb variance inequality [6] supply the probabilistic estimates used in these comparisons.

Proof strategy

Set \(L=n^\kappa\) and \(\rho=L^{-1}\). Our task is to exclude an overlap sign passage during the first \(e^L\) units of time. To connect that task to mixing, choose a reference \(v_1\) with \(R(v_1,x_0)\ge q_*\) for a fixed \(q_*>0\). The half-space \(\{z:R(v_1,z)\le0\}\) has Gibbs mass at least \(1/2\) by spin reversal. A transition law within \(1/4\) of equilibrium must therefore enter it with probability at least \(1/4\). The reference will be chosen from independent equilibrium samples, using the initial state but no future updates.

The first part of the paper establishes the static estimates that make this path argument possible. Section 2 compares the expected normalized log partition function \(n^{-1}\mathbb E\log Z^J\) with the minimum of the scalar Parisi functional, with error \(O_\beta(n^{-1/24})\), and proves the matrix comparison for constrained replica overlaps. Section 3 develops the scalar evolution and the variational identities of a minimizing measure. Section 4 uses these identities to compare three replicas: when one pair has a substantial positive overlap, their small signed overlaps with the third replica are forced to remain close, apart from a set of very small averaged Gibbs probability. Section 5 proves an equilibrium energy bound and a quantitative estimate for small Gaussian rotations of the disorder. All of these specialized inputs are proved within the paper.

There are two further static steps. First, the energy and rotation bounds imply a coverage statement in Section 6: simultaneously for every subset \(S\), outside a set of targets of absolute Gibbs mass less than \(e^{-D_1L}\), each \(x\in S\) has Gibbs mass at least \(e^{-D_3L}\) of \(z\in S\) with \(|R(x,z)|\ge q_*\). Here \(D_3\) is fixed after \(D_1\). Sampling \(\exp(O(L))\) independent Gibbs configurations can therefore supply a reference inside \(S\). Second, Section 7 treats triples whose two smaller overlaps lie near a positive level \(r\), while the larger overlap exceeds \(r\) by only a shrinking amount. It supplies locking at the scales required by the backwards searches. The estimate uses a scalar stationarity identity on a fixed interval; if that identity fails, a pair-overlap pressure gap supplies a forbidden interval instead. This alternative avoids assuming a complete description of the minimizing measure’s support.

Section 8 applies these estimates to a stationary discrete path \((x_k)\), and obtains the continuous-time path by an independent rate-\(n\) Poisson clock. At a crossing of a small positive overlap level, coverage supplies a new reference with large overlap with the current configuration. Searching backwards for the new reference’s crossing, the locking estimates keep the overlaps with previously retained references almost unchanged. Iterating creates many simultaneous overlap constraints at a single path index.

The reference samples are arranged in blocks of a fixed length \(B\). Within a block, each new reference is chosen in the set of configurations having small absolute overlap with all the earlier references in that block. At the start of the next block this restriction is reset. A conflict with older retained references can then delete only a suffix of length at most a fixed \(H_0<B\). Since \(H_0<B\), deletion cannot reach the first reference of the preceding block or any older retained reference. In particular, \(v_1\) survives; Figure 2 shows this invariant. This construction permits \(p\) levels of order \(L\) with only \(\exp(O(L))\) total reference samples, while retaining a fixed positive fraction of the levels.

The final probability estimate uses the order in which randomness is revealed. At level \(i\), the reference is already determined when the independent threshold \(r_i\) is drawn uniformly from an interval of length \(\rho\). Its overlap at any fixed path index is unlikely to fall in the much narrower permitted window. Removing constraints by conditional expectation in decreasing order of level bounds their joint probability, even though later reference choices depend on earlier thresholds. We sum over deterministic path indices and deterministic subsets of retained levels. This avoids conditioning on the adaptively chosen retained list and completes both clock versions.

Two auxiliary conclusions have a separate role. Appendix 9 proves that every disorder-selected set of Gibbs mass at least \(n^{-D_1}\) has polynomially large conditional mass of pairs with absolute overlap at least a fixed \(q_*(\beta)\); this threshold is chosen before \(D_1\), and the resulting exponent \(D_2\) is fixed before \(n\) grows. Its Gaussian-gain lemma and cell corollary are proved in full. Appendix 10 combines that result with the fixed-scale locking estimate to obtain a second proof of the polynomial-time obstruction. There the number of levels is fixed and the reference banks have polynomial sizes. These appendices reuse the energy, rotation and static locking proofs already established in the body, while retaining their own complete coverage and crossing arguments.

Two Gaussian tools and a hierarchy identity

We will need concentration for Gaussian disorder and a variance estimate after conditioning on a spin configuration. The following standard Gaussian and Brascamp–Lieb inequalities supply these two estimates.

The variance bound is the strongly log-concave case of the Brascamp–Lieb inequality [6]. For clarity, we prove the concentration estimate and the specialization of the variance bound to linear functions, which is the only specialization used below.

We next define the hierarchy and its probability law. Besides any quenched root randomness, take independent Gaussian fields \(g_0,\ldots,g_k\). The field \(g_0\) belongs to the quenched root. Choose masses \[0=x_{-1}\le x_0\le\cdots\le x_{k-1}\le x_k=1, \qquad w_l=x_l-x_{l-1},\] and a terminal log partition function \(F_k\) on a finite configuration space. Integrate the fields backwards by setting, for \(1\le j\le k\), \[ F_{j-1}=\frac1{x_{j-1}}\log\mathbb E_j e^{x_{j-1}F_j}. \tag{8}\] Here \(\mathbb E_j\) integrates the field \(g_j\). At a zero mass the right-hand side is interpreted as \(\mathbb E_jF_j\). After these recursive integrations, the hierarchy pressure is \(\mathbb EF_0\), with expectation also over all quenched randomness.

The recursion also specifies a probability law on fields and terminal configurations. Conditional on the prefix through level \(j-1\), multiply the original Gaussian law of \(g_j\) by the density \[ W_j=\exp\{x_{j-1}(F_j-F_{j-1})\}. \tag{9}\] Equation (8) normalizes this density. After sampling level \(k\), draw a configuration from the terminal Gibbs law. For a pair of paths indexed by a level \(l\), sample their root and fields through \(l\) once, and then sample the two continuations independently conditional on this prefix. We denote expectation under that pair law by \(\mathbb E_l^{(2)}\). At \(l=k\) the only independent choices are the terminal thermal draws. More generally, a finite tree is sampled by drawing each shared prefix once and making its descendants conditionally independent. In particular, every branch has the single-path marginal law. This convention fixes the shared randomness in all subsequent integration-by-parts calculations.

A matrix interpolation bound

We now apply the differentiation identity to a prescribed overlap constraint. For \(d\) configurations \(\sigma^1,\ldots,\sigma^d\), write \(D_{ab}=R(\sigma^a,\sigma^b)\) for their Gram matrix. If \(D\) is feasible, meaning that at least one such tuple realizes it, define \[ F_{d,n}(D)=\frac1n\mathbb E\log \sum_{\substack{\sigma^1,\ldots,\sigma^d\in\{-1,1\}^n\\ R(\sigma^a,\sigma^b)=D_{ab}\ \forall a,b}} \exp\left\{\beta\sum_{a=1}^dH_n(\sigma^a)\right\}. \tag{12}\] The sum is unnormalized. We use the Frobenius notation \(U:V=\sum_{a,b}U_{ab}V_{ab}\) and \(|U|^2=U:U\). To compare this pressure with a single-site recursion, choose a symmetric matrix path \[Q_{-1}=0,\qquad Q_j-Q_{j-1}\succeq0\quad(0\le j\le k), \qquad Q_k=Q_{\rm end}.\] Within these conditions, the endpoint is free: it may differ from \(D\) and may have nonunit diagonal. Increments of zero covariance are allowed. If the first nonzero increment should carry positive mass, insert a quenched level \(Q_0=0\); the first genuine increment is then integrated at mass \(x_0\). At a single 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\left\{\left(\sum_{j=0}^kg_j\right)\cdot s +s^{\mathsf T}\lambda s\right\}.\] For the deterministic correction to the pressure, set \[ \int x\,\,\mathrm d|Q|^2 =\sum_{j=0}^kx_{j-1}\bigl(|Q_j|^2-|Q_{j-1}|^2\bigr). \tag{13}\] The initial quenched increment therefore carries mass zero in this integral. The next bound keeps the cost of the free endpoint explicit.

The scalar functional

The scalar version of the hierarchy gives the variational quantity against which we compare the unconstrained pressure. Let \(\mu\) be a probability measure on \([0,1]\) and put \(\alpha(s)=\mu([0,s])\). Define \(\Phi_\alpha(s,z)\) by the terminal condition \(\Phi_\alpha(1,z)=\log(2\cosh z)\) and the backward equation \[ -\partial_s\Phi_\alpha =\frac{\beta^2}{2} \left(\partial_{zz}\Phi_\alpha +\alpha(s)(\partial_z\Phi_\alpha)^2\right). \tag{15}\] For a step function \(\alpha\), the equation means the Gaussian recursion already defined: over an interval of length \(b-a\) with constant mass \(x\), its terminal function \(f\) is mapped to \[z\longmapsto\frac1x\log\mathbb 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; Lemma 9 proves that this definition exists, is independent of the approximation, and has the stability properties we use. Define \[ \mathcal P_\beta(\mu)=\Phi_\alpha(0,0) -\frac{\beta^2}{2}\int_0^1s\alpha(s)\,\mathrm ds, \qquad P_\beta=\inf_\mu\mathcal P_\beta(\mu). \tag{16}\] The infimum is attained by compactness and continuity, as proved in Proposition 10. These scalar approximation and compactness arguments are independent of the pressure comparison; the lower comparison below will use only finitely supported trial measures. Apply Proposition 5 with \(d=1\), \(D=Q_{\rm end}=1\), and \(\lambda=0\). First for step measures and then by approximation, this gives the upper comparison \[ p_n(\beta):=\frac1n\mathbb E\log Z_{n,\beta}\le P_\beta. \tag{17}\]

The remaining task is the lower comparison. We will choose an interpolation path from expectations of overlaps, using a hierarchical backward system. Such expectation-dependent choices are also a feature of the adaptive interpolation method of Barbier and Macris [3]. Here we first prove an explicit overlap error estimate for the hierarchy, without assuming a prior description of the Gibbs measure, and then use it along the chosen path. Mourrat’s enriched-free-energy and Hamilton–Jacobi viewpoint [12] provides related motivation for organizing errors by hierarchical overlaps. This is a methodological connection only: the direct covariance and concentration argument and the quantitative bound here do not invoke a Hamilton–Jacobi theorem.

Concentration along a hierarchy

To obtain an error estimate that can be summed over the levels, we use equally spaced masses for the remainder of the section: \[w_j=\frac1{k+1},\qquad x_j=\frac{j+1}{k+1}\quad(0\le j\le k).\] Fix \(0\le t\le1\) and levels \(0=q_{-1}<q_0<\cdots<q_k\). Set \(\Delta_j=\beta^2(q_j-q_{j-1})\) and use the terminal exponent \[ U(\sigma)=\sqrt t\,\beta\widehat H_n(\sigma) +\sum_{j=0}^k\sqrt{\Delta_j}\,z_j\cdot\sigma, \tag{19}\] where \(z_0,\ldots,z_k\) are independent standard Gaussian vectors in \(\mathbb R^n\). Let \(\mathcal A_j\) contain the prefix through level \(j\), including the quenched Hamiltonian disorder. Under the path law, put \[ m_j=\mathbb E[\sigma\mid\mathcal A_j],\qquad M_j=\frac{\|m_j\|^2}{n},\qquad r_j=\mathbb EM_j. \tag{20}\] The conditional means \(m_j\) form a martingale. Consequently \(0\le r_0\le\cdots\le r_k\le1\). They can also be obtained by differentiating \(F_j\) with respect to an additional deterministic field coupled linearly to the spins. We begin by controlling the Gaussian field energy under the same path law.

Adaptive interpolation and the finite-size error

Regularity and first variations

We next differentiate the scalar functional in two directions: a change of its distribution function and a change of temperature with the distribution function fixed. We prove both formulas by differences, so they require no differentiability of a minimizing measure. For another distribution function \(\widetilde\alpha\), set \(\alpha_\theta=\alpha+\theta(\widetilde\alpha-\alpha)\). The first variation is \[ \left.\frac{\,\mathrm d}{\,\mathrm d\theta}\mathcal P_\beta(\alpha_\theta) \right|_{\theta=0+} =\frac{\beta^2}{2}\int_0^1 (\widetilde\alpha-\alpha)(s)(\Gamma(s)-s)\,\mathrm ds. \tag{47}\] We use \(\mathcal P_\beta(\alpha)\) to denote the functional of the measure having distribution function \(\alpha\). With \(\alpha\) held fixed, the temperature derivative of the scalar value is \[ \frac{\partial}{\partial(\beta^2)}\Phi_\alpha(0,0) =\frac12\int_0^1 \mathbb E\bigl[\chi(s,X_s)+\alpha(s)u(s,X_s)^2\bigr]\,\mathrm ds. \tag{48}\] For each formula, start with step paths, where the equations are classical between finitely many breakpoints. Subtraction gives an integral representation, and that representation passes to general paths by the stability lemma.

Variation of the distribution function. Subtract the equations for \(\Phi_{\alpha_\theta}\) and \(\Phi_\alpha\). The resulting drift is \(\beta^2\alpha(u_{\alpha_\theta}+u_\alpha)/2\), and the source is \(\theta\beta^2(\widetilde\alpha-\alpha)u_{\alpha_\theta}^2/2\). Introduce \(Y^\theta\) by \(Y^\theta_0=0\) and \[\,\mathrm dY_s^\theta=\beta\,\mathrm dB_s +\frac{\beta^2}{2}\alpha(s) (u_{\alpha_\theta}+u_\alpha)(s,Y_s^\theta)\,\mathrm ds.\] The diffusion representation of the difference equation is the exact identity \[ \frac{\Phi_{\alpha_\theta}(0,0)-\Phi_\alpha(0,0)}{\theta} =\frac{\beta^2}{2}\mathbb E\int_0^1 (\widetilde\alpha-\alpha)(s) u_{\alpha_\theta}(s,Y_s^\theta)^2\,\mathrm ds. \tag{49}\] For general \(\alpha,\widetilde\alpha\), choose step approximations converging to each in \(L^1\), and take their convex combinations at a fixed \(\theta>0\). Equation (41) shows that the mixed drifts converge in integrated spatial supremum norm. They also have a common spatial Lipschitz bound. A coupling with the same Brownian motion and Gronwall’s inequality therefore gives uniform convergence of the corresponding \(Y^\theta\) processes. The sources converge in integrated expectation by \(|u|\le1\), the spatial Lipschitz bound for \(u\), its uniform convergence, and the \(L^1\) convergence of \(\widetilde\alpha-\alpha\). Hence Equation (49) holds for arbitrary distribution functions.

We may now send \(\theta\downarrow0\). The same estimates give \(Y^\theta\to X\) and uniform convergence of \(u_{\alpha_\theta}\) to \(u_\alpha\). The right-hand side converges to \(\frac{\beta^2}{2}\int(\widetilde\alpha-\alpha)\Gamma\). Subtract the derivative of the linear penalty to obtain Equation (47).

Variation of the temperature. Set \(b=\beta^2\) and use a superscript \(b\) for scalar functions with parameter \(\sqrt b\). For \(\widetilde b\ne b\), let \(Y^{b,\widetilde b}_0=0\) and define its evolution by \[\,\mathrm dY_s^{b,\widetilde b}=\sqrt b\,\mathrm dB_s +\frac b2\alpha(s)(u^b+u^{\widetilde b}) (s,Y_s^{b,\widetilde b})\,\mathrm ds.\] Subtract the two step-path equations with diffusion coefficient \(b/2\) to obtain \[ \frac{\Phi^{\widetilde b}(0,0)-\Phi^b(0,0)}{\widetilde b-b} =\frac12\mathbb E\int_0^1 [\chi^{\widetilde b}+\alpha(u^{\widetilde b})^2] (s,Y_s^{b,\widetilde b})\,\mathrm ds. \tag{50}\] For fixed \(b,\widetilde b\), pass to general \(\alpha\) by the same step approximation and Brownian coupling used above. The additional term involving \(\chi\) is controlled by its uniform spatial Lipschitz bound. Next let \(\widetilde b\to b\). Parameter continuity in Lemma 9 and the coupling give \(Y^{b,\widetilde b}\to X\). The integrands remain bounded and converge in integrated expectation. The limit in Equation (50) therefore proves Equation (48) for approach from either side.

Minimizers and the energy gap

The mass variation converts minimization into a condition on the support. We will use that condition both to identify the expected scalar susceptibility at every time and to show that the minimizing measure is nontrivial when \(\beta>1\).

For \(\beta>1\), the susceptibility bound excludes the measure \(\delta_0\). This makes the temperature derivative at a fixed minimizer strictly smaller than \(\beta/2\). A finite-volume secant estimate transfers that strict inequality to the equilibrium energy.

A pair constraint

The three-replica comparison will use a large overlap \(q\) for which \(\Gamma(q)\) is close to \(q\). We first show that the remaining pair overlaps already have an exponentially small Gibbs probability.

A three-coordinate path with an asymmetric perturbation

Fix \(q\in[h,1]\) and a nonempty constraint \[ D=\begin{pmatrix} 1&r+\delta&r-\delta\\ r+\delta&1&q\\ r-\delta&q&1 \end{pmatrix},\qquad r\geq0. \tag{61}\] We will choose upper bounds for \(r\) and \(|\delta|\) depending only on \(\beta,h\). Write \(D_0\) for the same matrix with \(\delta=0\). Starting from a hierarchy ending at \(D_0\), we will 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, so that correction has a fourth-order cost.

The reason to perturb an early increment is the strict inequality \(\beta^2A(h)A(0)<1\), supplied by (57). At a small branching time \(r\), the two scalar branches are nearly independent. Their susceptibility product is then bounded above by \(A(h)A(0)\), up to small errors. The Gaussian variance part of the perturbation will cancel the corresponding penalty up to the pair deviation \(q-\Gamma(q)\); this strict product inequality controls what remains.

The base hierarchy itself is valid for every \(0\le r\le q\le1\); only the later perturbation will require \(r\) to be small. We use the three-replica construction in Talagrand’s discussion following [18], with masses divided by the size of each common block. Its three stages, in local scalar time \(s\), are:

1. From \(0\) to \(r\), all three coordinates share each increment, integrated at mass \(\alpha(s)/3\).

2. From \(r\) to \(q\), the coordinate \(v\) follows an independent branch at mass \(\alpha(s)\), while \(x,y\) share a branch at mass \(\alpha(s)/2\).

3. From \(q\) to \(1\), all three coordinates have independent increments at mass \(\alpha(s)\).

In the middle stage each branch has its own clock. If these clocks are \(a\) for \(v\) and \(b\) for the common \(x,y\) branch, the current covariance is \[Q(a,b)=\begin{pmatrix}a&r&r\\r&b&b\\r&b&b\end{pmatrix}, \qquad r\le a,b\le q.\] Thus one branch can advance while the other is held fixed. For a step function \(\alpha\), merge the two finite lists of increments in nondecreasing order of mass, retaining the order within each list. Each list is nondecreasing, so such a merge exists; ties may be ordered in either way consistent with the two local orders. The first-stage masses do not exceed either middle starting mass, and the middle masses do not exceed the starting mass of the last stage. Thus the entire schedule is a valid nondecreasing hierarchy. Insert a dummy initial covariance \(Q_0=0\) to ensure that, even when \(\alpha(0)>0\), the first genuine field increment has its prescribed positive mass and the quenched initial level has zero covariance.

The endpoint is \(D_0\), and the recursive value minus the penalty equals \(3\mathcal P_\beta(\mu)\). To check both assertions about the value, observe that 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\,\mathrm d(s^2)\) contributes \(\ell\) times the scalar penalty after multiplication by that mass. Independent branches have additive values. When one branch is integrated, the value of a frozen branch is independent of that increment and passes unchanged through the logarithm. Applying these facts at each split proves the claimed value and penalty for every allowed interleaving. It also identifies the base tilted law. Denote the \(v\) path and the shared \(x,y\) path by \(X^v\) and \(X^x\), and their common field at the first split by \(X_r\). Write \(K_{r,z}\) for the scalar path law started at \((r,z)\) and run to time \(q\). If \(\mathcal X_0\) denotes the common prefix through \(r\), then \[ \mathcal L(X^v_{[r,q]},X^x_{[r,q]}\mid\mathcal X_0) =K_{r,X_r}\otimes K_{r,X_r}. \tag{62}\] Indeed, the frozen branch cancels from each normalized kernel, while the factor three or two in the common-block value cancels the divided mass. The two future branches are therefore independent conditional on \(X_r\), for every allowed merge. We will use this same base hierarchy in Section 7.

For the fixed-scale perturbation, now fix \(0<s_1<s_2<h\) and suppose \(r<s_1\). Define \[k(s)=\frac{\mathbf 1_{[s_1,s_2]}(s)}{s_2-s_1},\qquad g(s)=\int_0^s k(t)\,\mathrm dt,\qquad G(s)=\int_0^s k(t)^2\,\mathrm dt,\qquad K=G(s_2)=\frac1{s_2-s_1}.\] Let \(L_{vx}=L_{xv}=1\), \(L_{vy}=L_{yv}=-1\), with all other entries of \(L\) zero. Let \(L_2\) vanish outside its \((x,y)\) block and give that block the value \(\left(\begin{smallmatrix}1&-1\\-1&1\end{smallmatrix}\right)\). Then \[|L|^2=|L_2|^2=4,\qquad L:L_2=0.\] During each \(v\)-increment with local clock in \([s_1,s_2]\), add \(\delta k\) times that increment to \(x\) and its negative to \(y\). At the covariance level, this replaces \(\,\mathrm ds\,e_ve_v^{\mathsf T}\) by \[\,\mathrm ds\, \bigl(e_v+\delta k(e_x-e_y)\bigr) \bigl(e_v+\delta k(e_x-e_y)\bigr)^{\mathsf T}.\] This rank-one form is positive semidefinite. The accumulated change is \(\delta gL+\delta^2GL_2\) until the modification ends, and is then held fixed. The new endpoint is consequently \[\widetilde D=D_0+\delta L+\delta^2KL_2 =D+\delta^2KL_2.\] Apply Proposition 5 with zero terminal multiplier and this endpoint. Its mismatch contribution is \[ \frac{\beta^2}{4}|D-\widetilde D|^2 =\beta^2\delta^4K^2. \tag{63}\]

We next isolate the beneficial increase in the penalty. 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 \[|\widetilde Q|^2-|Q|^2 =4\delta^2g^2+2\delta^2G(Q:L_2)+4\delta^4G^2.\] The last term has nonnegative increments. The first changes only during the \(v\)-increments, whose masses are \(\alpha(s)\); the middle term changes only in the independent final stage. The penalty increase is therefore at least \[ \beta^2\delta^2\left( \int_0^1\alpha(s)\,\mathrm d(g(s)^2)+K A(q)\right). \tag{64}\]

The recursive value under the perturbation

To compare this penalty gain with the recursive value, first 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 let \(Y\) be the sum of the raw \(v\)-increments weighted by \(k\). The boundary value changes by \[ \Delta=\Phi(q,z+\delta Y)+\Phi(q,z-\delta Y)-2\Phi(q,z). \tag{65}\] Convexity, the bound \(\chi\leq1\), and its spatial Lipschitz bound yield \[ 0\leq\Delta\leq\delta^2Y^2, \qquad \bigl|\Delta-\delta^2\chi(q,z)Y^2\bigr| \leq C_\beta|\delta Y|^3. \tag{66}\]

The remaining backward integrations are nonlinear, so a bound on the boundary change must be propagated through their normalized kernels. If the future value changes by \(U\), an integration at positive mass \(m\) changes by \[\frac1m\log\mathbb E_{\rm base} [e^{mU}\mid\text{current prefix}],\] where the expectation uses the unperturbed tilted kernel. At zero mass, the change is its conditional expectation of \(U\). For \(0<m\leq1\), Jensen’s inequality and the power-mean inequality put the displayed expression between \(\mathbb E_{\rm base}[U\mid\text{prefix}]\) and \(\log\mathbb E_{\rm base}[e^U\mid\text{prefix}]\).

Here is the resulting induction explicitly. Let \(K_i\) be the normalized base kernel at level \(i\), and \(U_i\) the difference of recursive values at that prefix. Taking the ratio of the two defining integrals gives \(U_i=m_i^{-1}\log K_i e^{m_iU_{i+1}}\) for \(m_i>0\); this identity uses the base kernel only. Put \[A_i=\mathbb E_{\rm base}[\Delta\mid\text{prefix }i],\qquad B_i=\log\mathbb E_{\rm base}[e^\Delta\mid\text{prefix }i].\] At the boundary these equal \(U_i=\Delta\). If \(A_{i+1}\leq U_{i+1}\leq B_{i+1}\), the kernel inequalities and tower property give \[U_i\geq K_iU_{i+1}\geq A_i,\qquad U_i\leq\log K_ie^{U_{i+1}} \leq\log K_ie^{B_{i+1}}=B_i.\] Jensen’s inequality gives the same conclusions at zero mass. Applying this induction through the hierarchy proves \[ \mathbb E_{\rm base}\Delta \ \leq\ \widetilde\Psi-\Psi \ \leq\ \log\mathbb E_{\rm base}e^\Delta. \tag{67}\] Jensen’s inequality also preserves these bounds under an outer quenched expectation.

Under the base tilted law, take scalar diffusions \(X^v,X^x\) that agree through time \(r\) and have independent Brownian noises thereafter. The identified path law gives \[z=X_q^x,\qquad Y=\int_{s_1}^{s_2} k(s)\,\mathrm dX_s^v, \qquad \,\mathrm dX_s^v=\beta\,\mathrm dB_s^v +\beta^2\alpha(s)u(s,X_s^v)\,\mathrm ds.\] Thus \(Y\) is a centered Gaussian increment of variance \(\beta^2K\) plus a possibly dependent random term of absolute value at most \(\beta^2\). In particular, there are \(c,C>0\), depending only on \(\beta,s_1,s_2\), such that \[ \mathbb E_{\rm base}e^{cY^2}\leq C. \tag{68}\] This estimate is uniform in \(q\geq h\), \(r<s_1\), and the step approximations of \(\alpha\). For small enough \(|\delta|\), (66) and this exponential moment imply \[\mathbb E\bigl(e^\Delta-1-\Delta\bigr) \leq\tfrac12\mathbb E\bigl[\Delta^2e^\Delta\bigr] \leq C\delta^4.\] Combining with (67) bounds the recursive change by \[ \widetilde\Psi-\Psi \leq\delta^2\mathbb E\bigl[\chi(q,X_q^x)Y^2\bigr]+C|\delta|^3. \tag{69}\]

At this point all matrix paths can still be taken finite. Include \(r,q,s_1,s_2\) in their segment endpoints and choose nondecreasing step approximations converging to \(\alpha\) in \(L^1([0,1])\). Lemma 9 gives convergence of the scalar values, derivatives, and diffusions. Couple the diffusions with the same Brownian noises, keeping the noises independent after \(r\). The uniform exponential moment (68) then justifies passage to the limit in the expectation in (69). The penalty integrals converge as well: \(\,\mathrm d(g^2)/\,\mathrm ds\) is bounded and supported on \([s_1,s_2]\), and \(A(q)\) is an integral of \(\alpha\). We have therefore applied the matrix comparison only to finite hierarchies and passed their upper bounds to the limit. No infinite hierarchy has been differentiated. In particular, convergence at a possible atom \(q\) is unnecessary; only \(L^1\) convergence of the masses is used. The minimizing identities will be applied after this limit.

Subtracting (64) from (69) and including the fourth-order cost (63) gives \[ \begin{split} F_{3,n}(D)\leq 3P_\beta+\delta^2\mathcal B(q,r)+C|\delta|^3,\\ \mathcal B(q,r)= \mathbb E\bigl[\chi(q,X_q^x)Y^2\bigr] -\beta^2KA(q)-\beta^2\int_0^1\alpha(s)\,\mathrm d(g(s)^2). \end{split} \tag{70}\] The task is now to choose the perturbation interval so that this quadratic coefficient is strictly negative.

Choosing an interval with a strict quadratic gain

The strict inequality \(A(h)<A(0)\) will supply the gain. To expose it, define \[V_t=\chi(t,X_t^v)+\alpha(t)u(t,X_t^v)^2, \qquad Y_s=\int_{s_1}^{s}k(t)\,\mathrm dX_t^v \quad(s\in[s_1,s_2]).\] The martingale identity \(\,\mathrm du(s,X_s^v)=\beta\chi(s,X_s^v)\,\mathrm dB_s^v\) and Itô’s formula, conditional on the common starting field \(X_r\), give for almost every \(s\) \[\frac{\,\mathrm d}{\,\mathrm ds}\mathbb E[Y_su(s,X_s^v)\mid X_r] =\beta^2 k(s)\mathbb E[V_s\mid X_r].\] Since \(Y_{s_1}=0\), apply Itô’s formula once more to \(Y_s^2\) and use conditional independence of the \(v\) and \(x\) branches. This yields \[ \begin{split} \mathbb E\bigl[\chi(q,X_q^x)Y^2\bigr] ={}&\beta^2K\mathbb E\chi(q,X_q)\\ &+2\beta^4\int_{s_1}^{s_2}\alpha(s)k(s) \int_{s_1}^{s}k(t) \mathbb E\bigl[\chi(q,X_q^x)V_t\bigr]\,\mathrm dt\,\mathrm ds. \end{split} \tag{71}\] All factors except \(Y\) are bounded, and its required moments follow from (68). The conditioning and integrations are therefore justified.

Only the common field at the small time \(r\) prevents the product expectation in this formula from factoring. Its effect is bounded by \[ \left|\mathbb E\bigl[\chi(q,X_q^x)V_t\bigr] -\mathbb E\chi(q,X_q)\,d_*(t)\right| \leq C_\beta\sqrt r, \qquad s_1\leq t\leq s_2,\quad h\leq q\leq1. \tag{72}\] To prove this estimate, restart the \(x\) branch at an independent copy \(X_r'\) of \(X_r\), independent also of the whole \(v\) branch, and retain its post-\(r\) Brownian noise. The drift \(\beta^2\alpha u\) is uniformly Lipschitz in space, so the two \(x\) solutions at time \(q\) differ by at most \(e^{\beta^2}|X_r-X_r'|\). Use the spatial Lipschitz bound for \(\chi\), the bound \(0\leq V_t\leq2\), and \(\mathbb E|X_r-X_r'|\leq C_\beta\sqrt r\), the latter following from the bounded drift. The replacement has the same marginal law and is independent of \(V_t\); its expectation therefore factors, with \(\mathbb EV_t=d_*(t)\) by (57).

The two inequalities \(\beta A(0)\leq1\) and \(A(h)<A(0)\) imply \[\beta^2 A(h)A(0)<1.\] Choose \(s_2\in(0,h)\) and \(\gamma>0\) small enough that \[ \beta^2A(h)\sup_{0<t\leq s_2}d_*(t)\leq1-4\gamma, \tag{73}\] and set \(s_1=s_2/2\). The functions \(k,g\) and the constant \(K\) are now fixed. Also set \[W=2\beta^2\int_{s_1}^{s_2}\alpha(s)k(s) \int_{s_1}^{s}k(t)\,\mathrm dt\,\mathrm ds>0.\] The strict positivity follows from \(\alpha(s)>0\) for every \(s>0\).

Let \(\bar\chi(q)=\mathbb E\chi(q,X_q)\). For \(q\geq h\) with \(|q-\Gamma(q)|\leq\tau\), the all-time scalar identity gives \[\bar\chi(q)=A(q)+\alpha(q)(q-\Gamma(q))\leq A(h)+\tau.\] First choose \(\tau>0\) small enough and then \(r_0\in(0,s_1)\) small enough. Equations (72) and (73) give \[ \beta^2\mathbb E\bigl[\chi(q,X_q^x)V_t\bigr]-1\leq-2\gamma \tag{74}\] uniformly for \(q\in[h,1]\) with \(|q-\Gamma(q)|\leq\tau\), \(0\leq r\leq r_0\), and \(t\in[s_1,s_2]\). More explicitly, since \(0\leq d_*(t)\leq1\), the left side is bounded above by \(-4\gamma+\beta^2\tau+C_\beta\sqrt r\).

We can now compare the entire quadratic term with this strict margin. Using \(\,\mathrm d(g^2)=2gk\,\mathrm ds\), substitute (71) into (70). The result is the exact identity \[ \begin{split} \mathcal B(q,r) ={}&\beta^2K\alpha(q)\bigl(q-\Gamma(q)\bigr)\\ &+2\beta^2\int_{s_1}^{s_2}\alpha(s)k(s) \int_{s_1}^{s}k(t) \left\{\beta^2\mathbb E\bigl[\chi(q,X_q^x)V_t\bigr]-1\right\} \,\mathrm dt\,\mathrm ds. \end{split} \tag{75}\] Decrease \(\tau\) further until \(\beta^2K\tau\leq\gamma W\). The first term in (75) is then at most \(\gamma W\), and (74) bounds the double integral by \(-2\gamma W\). Hence \[\mathcal B(q,r)\leq\gamma W-2\gamma W=-\gamma W.\] The cubic remainder in (70) is uniform over these \(q,r\). Choose \(\delta_0>0\) small enough to absorb it. For some \(c_0>0\) we have obtained \[ F_{3,n}(D)\leq3P_\beta-c_0\delta^2 \tag{76}\] whenever the constraint is nonempty, \(0\leq r\leq r_0\), \(|\delta|\leq\delta_0\), \(q\in[h,1]\), and \(|q-\Gamma(q)|\leq\tau\). In particular, this estimate places no restriction \(r\geq|\delta|\) on the two small signed overlaps.

From the pressure gap to locking

Stationary paths and a sign-passage criterion

Given \(J\), start the discrete heat-bath chain \((x_k)_{k\ge0}\) at \(x_0\sim\pi^J\). Each step chooses a uniform site and resamples its spin from the conditional Gibbs law. Stationarity gives marginal \(\pi^J\) at every deterministic index. If \(N\) is an independent rate-\(n\) Poisson process, \(x_{N(t)}\) has conditional transition kernel \(P_t^J\) from the realized \(x_0\). We work up to the deterministic index \[ m=\lceil e^{2L}\rceil. \tag{123}\] Markov’s inequality gives \[ \mathbb P\{N(e^L)>m\}\leq \frac{ne^L}{m}\leq ne^{-L}=o(1). \tag{124}\] For every fixed configuration \(v\), the overlap \(R(v,x_k)\) changes by at most \(2/n\) at a single step.

A bank is an ordered list of independent \(\pi^J\) samples. Given \(J\), all raw bank entries are mutually independent and independent of the complete path. Their sizes are deterministic functions of \(n\). A chosen reference may be reversed in sign at selection; that orientation is thereafter fixed.

Suppose a first bank is used to select a reference \(v_1\) satisfying \(R(v_1,x_0)\geq q_*\), with the choice and orientation depending only on \(J,x_0\) and this bank. Write \(\mathcal S\) for successful selection, and define its sign-passage event by \[\mathcal A=\mathcal S\cap \{R(v_1,x_k)\leq0\text{ for some }0\leq k\leq m\}.\] Also write \[\mathcal M=\left\{ \lVert P_{e^L}^J(x_0,\cdot)-\pi^J\rVert_{\mathrm{TV}}\leq\frac14\right\}.\] Spin-flip symmetry implies, for every oriented \(v\), \[\pi^J\{z:R(v,z)\leq0\}\geq\frac12.\] Condition on \(J,x_0\) and successful first-bank selection. Since that selection uses no future updates, the path and clock still have their original conditional laws. On \(\mathcal M\), total variation therefore puts conditional probability at least \(1/4\) on the opposite-sign half-space at time \(e^L\). Removing clock overruns gives \[ \mathbb P(\mathcal A)\geq \frac14\mathbb P(\mathcal M\cap\mathcal S) -\mathbb P\{N(e^L)>m\}. \tag{125}\] Thus the remaining task is concrete: make the first reference available with probability tending to one, and make its sign passage have probability tending to zero.

Choose a fixed \(b\in(0,1)\) no larger than the small-overlap cutoff in Lemma 12 with large-overlap cutoff \(q_*\). Next choose \(b'\in(0,b)\) no larger than that lemma’s small-overlap cutoff with large-overlap cutoff \(b\). Fix \(t_0>0\) so small that \[ 4t_0<\min\{q_*,b',b^2/2\}. \tag{126}\] We use the notation \[ \eta_n=n^{-1/100}=\rho^{100} \tag{127}\] for the scale in fixed-scale locking.

The case with a fixed forbidden overlap interval

There are two possible scalar regimes. In the first, \(\Gamma(z)=z\) fails at some point of \((t_0/2,3t_0)\). Continuity then supplies fixed constants \[t_0/2<a_0<a_1<3t_0,\qquad d_0>0,\] such that \(|q-\Gamma(q)|\geq d_0\) for all \(q\in[a_0,a_1]\). The pair gap (60), Lemma 13, and the polynomial number of feasible pair overlaps imply, for some \(c>0\) and all sufficiently large \(n\), \[ \mathbb E\big[(\pi^J)^{\otimes2} \{(v,x):R(v,x)\in[a_0,a_1]\}\big]\leq e^{-cn}. \tag{128}\]

Apply Proposition 18 with \(D_1=3\), let \(D_3\) be its constant, and take a single bank with \(K=\lceil\exp((D_3+1)L)\rceil\) entries. Select its first entry with \(|R(v,x_0)|\geq q_*\), oriented to give positive overlap. On the disorder event of coverage for the whole configuration space, the Gibbs mass of starting states whose qualifying neighborhood has mass below \(e^{-D_3L}\) is at most \(e^{-3L}\). For every other starting state, the independent bank misses that neighborhood with probability at most \(e^{-e^L}\). Hence \(\mathbb P(\mathcal S)\to1\).

At a deterministic \(k\le m\), the path point and a fixed signed bank entry are independent Gibbs draws conditional on \(J\). Sum (128) over entries, signs and indices: \[\mathbb P\{R(\sigma v,x_k)\in[a_0,a_1] \text{ for some bank entry }v,\ \sigma\in\{-1,1\},\ k\leq m\} \leq 2K(m+1)e^{-cn}=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]\). Therefore \(\mathbb P(\mathcal A)\to0\). Together with (125), this proves the theorem in this case.

This completes the forbidden-interval case. In the second regime we have \[ \Gamma(z)=z\qquad(t_0/2<z<3t_0), \tag{129}\] and put \[ h=\rho^8,\qquad \varepsilon=\rho^{20}. \tag{130}\]

Thresholds and simultaneous bank properties

Define the fixed integers and the number of levels by \[ H_0=\lceil 2/b^2\rceil,\qquad B=H_0+2,\qquad p=B\left\lfloor\frac{t_0}{5B\rho}\right\rfloor. \tag{131}\] For large \(n\), \(p\ge B\). Divide the \(p\) levels into consecutive blocks of \(B\) levels each. 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 specified below. Independently of the disorder, banks and path, draw independent thresholds \(r_i\), uniform on \[ I_i=[t_0+4(i-1)\rho,\ t_0+(4(i-1)+1)\rho]. \tag{132}\] These intervals lie in \([t_0,2t_0]\), and \[ r_j-r_i\geq3\rho\qquad(i<j). \tag{133}\] Fubini’s theorem gives \[\mathbb E\big[\mu([r_i-2h,r_i+2h])\big]\leq\frac{4h}{\rho}.\] Consequently Markov’s inequality and a union bound show that the event \[ \mathcal T=\{\mu([r_i-2h,r_i+2h])\leq\rho^4 \text{ for every }1\leq i\leq p\} \tag{134}\] satisfies \[ \mathbb P(\mathcal T^c)\leq\frac{4ph}{\rho^5}=O(\rho^2). \tag{135}\] The Fubini calculation includes atoms; no regularity of the distribution of the minimizing measure is imposed here.

There will be a bank \(\mathcal B_j\) at every level. Its size must compensate for the number of earlier reference tuples that can define the selection cell. Using all preceding levels would give a recursion of growing depth \(p\); Proposition 18 does not control its constants uniformly in \(n\). The reset confines this recursion to \(B\) fixed steps. Bank sizes can then depend only on the position within a block, keeping the total number of samples at \(\exp(O(L))\). Older retained references will still enter the crossing constraints below.

We require coverage for every possible earlier tuple in the current block. For entries \(u_i\in\mathcal B_i\) from those earlier levels, define \[ S=\{z:|R(u_i,z)|\leq3t_0 \text{ for every index in this tuple}\}. \tag{136}\] The empty tuple gives the whole space. We require \[ x_k\in S,\quad 0\leq k\leq m \quad\Longrightarrow\quad \text{some }w\in\mathcal B_j\cap S \text{ satisfies }|R(w,x_k)|\geq q_*. \tag{137}\] Absolute values make this property insensitive to orientations.

Choose the bank sizes recursively over the fixed positions \(s=1,\ldots,B\). Once the constants at smaller positions are fixed, set \[C_s=\sum_{u<s}(D_{3,u}+2),\qquad D_{1,s}=C_s+5.\] Let \(D_{3,s}\) be a constant supplied by Proposition 18 for \(D_{1,s}\), and use \[K_s=\lceil\exp((D_{3,s}+1)L)\rceil\] entries at position \(s\). For large \(n\), the number of earlier tuples in the block is at most \(\exp(C_sL)\). Only \(B\) fixed applications of coverage are needed, so their disorder events have an intersection \(\mathcal D\) with \(\mathbb P(\mathcal D)\to1\).

Fix a level at position \(s\), a realization \(J\in\mathcal 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)|\geq 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\). A union bound over tuples and deterministic indices therefore bounds the probability that any \(x_k\) lies in its cell’s bad subset by \[(m+1)e^{(C_s-D_{1,s})L}=O(e^{-3L}).\] After excluding these bad targets, condition also on the complete path. The bank at the present level is still fresh. Its probability of missing a qualifying neighborhood inside the cell is at most \[(1-e^{-D_{3,s}L})^{K_s}\leq e^{-e^L}.\] Union over the same tuples and indices, and then over the \(p=O(L)\) levels, shows that (137) holds simultaneously with probability \(1-o(1)\). The recursion has only \(B\) steps, so the total number of entries across all \(p\) banks is \(\exp(O(L))\).

We also impose simultaneous avoidance of the exceptional triples in Lemma 12, for the two cutoff pairs \((q_*,b)\) and \((b,b')\), and in Lemma 19. We do so for every ordered triple of signed entries from distinct banks, and for every ordered triple consisting of two signed entries from distinct banks and one path point \(x_k\), \(0\leq k\leq m\). For each deterministic choice, the conditional law given \(J\) is \((\pi^J)^{\otimes3}\): bank independence, stationarity at that deterministic index, and spin-flip symmetry suffice. The sampled configurations themselves need not be different.

There are \(\exp(O(L))\) such choices, including all orders and signs. The exceptional probability for each is bounded by a constant times \(e^{-n^{9/10}}+e^{-n^{4/5}}\). A union bound thus makes all these locking assertions simultaneous with probability \(1-o(1)\). Let \(\mathcal G\) be the intersection of this event, the simultaneous bank property, and \(\mathcal T\). We have proved \[ \mathbb P(\mathcal G^c)=o(1). \tag{138}\] We have made all these estimates simultaneously before choosing references or crossing times. Later application at a backwards crossing therefore uses this deterministic-index event, not an assertion of stationarity at a random time.

Backwards searches and deletion of conflicts

Select \(v_1\) from \(\mathcal B_1\) as the first entry whose absolute overlap with \(x_0\) is at least \(q_*\), and orient it positively. If it exists, let \(\tau_1\) be the first \(k\leq m\) with \(R(v_1,x_k)\leq r_1\). On success initialize the ordered retained list as \(A_1=\{1\}\).

At a subsequent level \(j\), assuming all earlier levels have succeeded, form the cell (136) using the selected references in earlier positions of the current block. Choose as \(v_j\) the first entry of \(\mathcal B_j\) lying in this cell and having absolute overlap at least \(q_*\) with \(x_{\tau_{j-1}}\). Orient it so that \(R(v_j,x_{\tau_{j-1}})\geq q_*\). From \(A_{j-1}\) delete the conflicts, namely those indices \(i\) with \[ |R(v_i,v_j)|>b. \tag{139}\] The remaining old indices are called compatible. Search backwards from \(\tau_{j-1}\), stopping at the first point encountered with overlap at most \(r_j\) with \(v_j\). Equivalently, if the set is nonempty, define \[ \tau_j=\max\{0\leq k\leq\tau_{j-1}:R(v_j,x_k)\leq r_j\}. \tag{140}\] Add \(j\) to the compatible list to obtain \(A_j\).

To use independence of each fresh threshold, define \(v_j\) on failure realizations as well. 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 at all levels after an earlier failure, use the first entry of the corresponding bank without sign 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 subsequent crossing. The first reference, when selected successfully, uses only \(J,x_0\) and \(\mathcal B_1\) as required by (125).

We now work deterministically on \(\mathcal G\cap\mathcal A\). For all sufficiently large \(n\), we will show that every level succeeds, that reference \(1\) survives, and that \[\begin{align*} |R(v_i,x_{\tau_j})-r_i|&\leq6j\varepsilon &&(i\in A_j),\tag{141}\\ |R(v_i,v_\ell)-r_i|&\leq6j\varepsilon &&(i,\ell\in A_j,\ i<\ell). \tag{142}\end{align*}\] The induction also keeps the current block complete: after level \(j\), all references from that block’s first level through \(j\) remain on the list. At the next reset, the preceding block is therefore intact. Older blocks may already have gaps, but the complete preceding block will prevent a new deletion from reaching them.

Deletions occur only at the first level of a new block, and at most \(H_0\) indices, forming a suffix of the old list, are deleted at each such level.

At level \(1\), coverage of the whole space supplies the reference. Sign passage forces the first crossing, where the one-step overlap bound puts the value in \([r_1-2/n,r_1]\). This starts the induction. In the following induction we use the scale relations \[ \frac1n\ll\eta_n=\rho^{100}\ll\varepsilon=\rho^{20},\qquad p\varepsilon=O(\rho^{19})\ll h=\rho^8\ll\rho. \tag{143}\]

Suppose the assertions hold through level \(j-1\). All earlier references in the current block are still retained, since there have been no deletions within that block after its first level. Their overlaps with \(x_{\tau_{j-1}}\) have absolute value at most \(2t_0+6p\varepsilon<3t_0\). Thus this target belongs to the required cell, and the new selection \(w=v_j\) exists by (137).

For each compatible old index \(i\), the two small overlaps in the triple \((v_i,w,x_{\tau_{j-1}})\) have absolute value at most \(b\), whereas \(R(w,x_{\tau_{j-1}})\geq q_*\). Fixed-scale locking gives \[ |R(v_i,w)-R(v_i,x_{\tau_{j-1}})|\leq2\eta_n. \tag{144}\] In particular, \[ |R(v_i,w)-r_i|\leq6(j-1)\varepsilon+2\eta_n \qquad(i\text{ compatible}). \tag{145}\]

Conflicts occupy a bounded final segment. A conflicting old index \(i\) cannot precede a compatible old index \(\ell\). Indeed, by (142) and (145), the magnitudes of \(R(v_\ell,v_i)\) and \(R(v_\ell,w)\) are within \(6(j-1)\varepsilon\) and \(6(j-1)\varepsilon+2\eta_n\) of \(r_i\) and \(r_\ell\), respectively. Both magnitudes are less than \(b'\), by (126). Their difference in magnitude is at least \[3\rho-12p\varepsilon-2\eta_n>2\eta_n.\] On the other hand \(|R(v_i,w)|>b\). Reverse one of this pair if necessary to make their mutual overlap positive. The signed difference of the two small overlaps has absolute value at least their difference in magnitude. This contradicts fixed-scale locking with cutoff pair \((b,b')\), which holds for all signs on \(\mathcal G\). The conflicts consequently form a suffix of the old retained list.

The number of conflicts is bounded by \(H_0\). Indeed, the induction bounds all absolute overlaps between retained old references by \(2t_0+6p\varepsilon<3t_0\). If \(d\geq1\) of them conflict with \(w\), normalize them to unit vectors and reverse each sign to give inner product greater than \(b\) with \(w/\sqrt n\). Denote these vectors by \(u_1,\ldots,u_d\). Then \[d^2b^2<\left\langle\sum_{a=1}^d u_a,\frac{w}{\sqrt n}\right\rangle^2 \leq\lVert \sum_{a=1}^d u_a\rVert^2 \leq d+3t_0d(d-1).\] Since \(3t_0<b^2/2\), this implies \[d<\frac{1-3t_0}{b^2-3t_0}<\frac{2}{b^2}\leq H_0.\] In particular \(d\leq H_0\).

If \(j\) is not the first level of its block, the most recent old index \(j-1\) is compatible: the cell condition gives \(|R(v_{j-1},w)|\leq3t_0<b\). A suffix of conflicts is therefore empty. At the first level of a new block, the additional invariant says that all \(B\) entries selected in the preceding block are still present. 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 as a retained singleton; at a nonreset it extends the complete current block because there is no deletion. This establishes the additional invariant and the deletion claims before proving that the new crossing exists.

The backwards search preserves old constraints. Follow the search for \(\tau_j\), including the crossing step when there is one. The new reference satisfies throughout this search \[ R(w,x_k)\geq r_j-2/n. \tag{146}\] If there is no crossing, this follows with the stronger strict bound \(R(w,x_k)>r_j\) at every index down to zero. If there is a crossing, all indices strictly after it have overlap greater than \(r_j\), and the jump bound gives (146) at the crossing itself.

For each compatible old reference \(v_i\), (145) places the fixed value \(R(v_i,w)\) near \(r_i\). The larger threshold \(r_j\) separates the new overlap from that old level throughout the search. We will use narrow-annulus locking to prove \[ |R(v_i,x_k)-R(v_i,w)|<2\varepsilon \tag{147}\] on this entire searched portion. Equation (144) proves the claim at the target. At a first violation while moving backwards, the one-step bound puts the left side in \([2\varepsilon,2\varepsilon+2/n]\). For this triple use the parameters of Lemma 19: \[r=\frac{R(v_i,x_k)+R(v_i,w)}2,\qquad \delta=\frac{R(v_i,x_k)-R(v_i,w)}2,\qquad q=R(w,x_k).\] Then \[\varepsilon\leq|\delta|\leq\varepsilon+1/n\leq2\varepsilon, \qquad |r-r_i|\leq6(j-1)\varepsilon+2\eta_n+\varepsilon+1/n<h.\] It follows that \(t_0/2<r<3t_0\) and \([r-h,r+h]\subseteq[r_i-2h,r_i+2h]\). Thus \(\mathcal T\) gives the required bound \(\mu([r-h,r+h])\leq\rho^4\). Also, by (133), (146), and (143), \[q-r\geq3\rho-6(j-1)\varepsilon-2\eta_n-\varepsilon-3/n \geq\rho.\] All conditions of the forbidden narrow-annulus event hold, contradicting its simultaneous avoidance on \(\mathcal G\). This proves (147).

The crossing must exist. Otherwise the search reaches index zero, and (145)–(147) apply there to the surviving compatible reference \(1\). They would give \[R(v_1,x_0)<r_1+6(j-1)\varepsilon+2\eta_n+2\varepsilon<q_*,\] contradicting the first selection. Hence the crossing exists. Its new reference overlap belongs to \([r_j-2/n,r_j]\). For each retained old reference, the error at the new crossing is at most \(6(j-1)\varepsilon+2\eta_n+2\varepsilon\leq6j\varepsilon\). The old-new reference errors satisfy the same claimed bound by (145), and old-old reference errors are unchanged. This proves (141)–(142) and completes the induction.

There are at most \(p/B\) reset occasions, so the final list has size at least \[ |A_p|\geq p-H_0p/B\geq p/B. \tag{148}\] Consequently \(\mathcal G\cap\mathcal A\) implies that, for some index \(k\) in \(\{0,\ldots,m\}\) and some subset of \(p/B\) indices, the inequalities \[ |R(v_i,x_k)-r_i|\leq6p\varepsilon \tag{149}\] hold simultaneously. We have reduced sign passage to this existence event. The probability bound that follows will not condition on \(\mathcal G\) or on the random retained list.

Predictable thresholds and completion of the proof

Let \(\mathcal F_0\) be generated by \(J\), all raw bank lists, and the path \((x_0,\ldots,x_m)\), and set \[\mathcal F_i=\sigma(\mathcal F_0,r_1,\ldots,r_i), \qquad 1\leq i\leq p.\] Every \(r_i\) is uniform on \(I_i\) and independent of \(\mathcal F_{i-1}\). The failure conventions ensure that each oriented \(v_i\) is \(\mathcal F_{i-1}\)-measurable. Here is the complete induction. At level \(1\) its selection does not use any threshold. Inductively, whether a prior level failed, the previously selected references, and the preceding crossing time are all determined by earlier thresholds. Selection at level \(i\) uses only that information and the bank and path data in \(\mathcal F_0\). The subsequent crossing may use \(r_i\), but never changes that selected reference. A default caused by an earlier failure likewise depends only on earlier thresholds. This proves the claim, including on failure events.

For each deterministic \(k\leq m\), let \[E_i(k)=\{|R(v_i,x_k)-r_i|\leq6p\varepsilon\},\qquad \gamma_n=\frac{12p\varepsilon}{\rho}.\] The interval defining \(E_i(k)\) has length at most \(12p\varepsilon\), while \(I_i\) has length \(\rho\). Thus, for all sufficiently large \(n\), \[ \mathbb P(E_i(k)\mid\mathcal F_{i-1})\leq\gamma_n<1. \tag{150}\] For a deterministic subset \(\{i_1<\cdots<i_s\}\), the earlier events \(E_{i_1}(k),\ldots,E_{i_{s-1}}(k)\) are \(\mathcal F_{i_s-1}\)-measurable. Conditioning first at the largest selected index and using (150) yields \[\mathbb P\left(\bigcap_{a=1}^s E_{i_a}(k)\right) \leq\gamma_n\, \mathbb P\left(\bigcap_{a=1}^{s-1}E_{i_a}(k)\right) \leq\gamma_n^s.\] The elimination order is essential: the latest selected threshold is integrated out first. Later centers may depend on earlier thresholds, but the displayed conditioning remains valid. Neither the random retained subset nor the good event has been conditioned on.

Taking \(s=p/B\), then taking a union over all deterministic subsets and all deterministic indices \(k\), proves \[ \mathbb P\{\text{\eqref{eq:dyn-small-target-windows} holds for some }k \text{ and some subset of size }p/B\} \leq(m+1)2^p\left(\frac{12p\varepsilon}{\rho}\right)^{p/B} =o(1). \tag{151}\] Indeed \(p=(t_0/5)L+O(1)\), \(\rho=L^{-1}\), and \(12p\varepsilon/\rho=O(\rho^{18})\). The logarithm of the right-hand side is therefore bounded above by \[2L+O(p)-\frac{18p}{B}\log(1/\rho) =-\Omega(L\log L).\]

The deterministic induction and (138) now imply \[\mathbb P(\mathcal A) \leq\mathbb P(\mathcal G^c) +\mathbb P(\mathcal G\cap\mathcal A)=o(1).\] The first selection succeeds on the simultaneous bank event at level \(1\), so \(\mathbb P(\mathcal S^c)=o(1)\) as well. Finally, (125) and (124) give \[\mathbb P(\mathcal M) \leq\mathbb P(\mathcal S^c)+4\mathbb P(\mathcal A) +4\mathbb P\{N(e^L)>m\}=o(1).\] This proves Theorem 1 also under (129), and the two cases exhaust the possibilities.

Finally take \(T_n=\lfloor e^L\rfloor\) discrete update attempts. This deterministic index lies below \(m\) for large \(n\). If its transition law is within \(1/4\) of equilibrium, the opposite-sign half-space has conditional probability at least \(1/4\) at that index. Thus the same sign-passage inequality holds with no clock-overrun term. All bank, locking and threshold estimates already concern the discrete path, so they prove the second assertion of Theorem 1 at exactly \(\lfloor e^L\rfloor\) attempts.

Gain under independent Gaussian disorder

Uniform coverage over all subsets

Target coverage within arbitrary subsets

For the crossing argument, we need a bound on the total Gibbs mass of targets lacking polynomial Gibbs mass of overlapping references in the same subset. Both masses below use the original Gibbs measure. This is the form needed when targets have Gibbs marginals and reference banks contain unconditioned Gibbs samples. Uniformity of the pair statement gives the target bound by applying it to the set of points that would violate it.

A stationary path and fixed overlap scales

Fix \(\beta>1\) and \(a>0\), and abbreviate \(\pi^J\) to \(\pi\). Put \[ t_n=n^a,\qquad m=\lceil2n^{a+1}\rceil,\qquad e_*=\frac1{100},\qquad \delta_n=n^{-e_*}. \tag{169}\] Conditional on \(J\), start \(x_0\) with law \(\pi\) and generate an infinite discrete heat-bath chain \((x_k)_{k\ge0}\). At each step choose a uniform site and use fresh resampling randomness, including possible self-transitions. Let \(N(t)\) be an independent rate-\(n\) Poisson process. The process \(x_{N(t)}\) is the continuous-time chain with rate one at each site. Indeed, if \(K_i^J\) denotes resampling at site \(i\), then \(K^J=n^{-1}\sum_iK_i^J\) and its generator is \(\sum_i(K_i^J-I)=n(K^J-I)\). Therefore \[\mathbb E[(K^J)^{N(t)}]=\exp\{nt(K^J-I)\}=P_t^J.\] Stationarity gives, for every deterministic \(k\), \[ \mathcal L(x_k\mid J)=\pi. \tag{170}\] Moreover, Chernoff’s inequality at parameter \(\log2\), with \(\mathbb EN(t_n)=n^{a+1}\) and \(m\ge2n^{a+1}\), gives \[ \eta_n:=\mathbb P\{N(t_n)>m\} \le\exp\{-(2\log2-1)n^{a+1}\}=o(1). \tag{171}\]

Use the common threshold \(q_*=q_*(\beta)>0\) of Proposition 20. With the same energy cutoff \(e_1\) as in the main coverage argument, its choice satisfies \[g=\frac{\beta^2}{4}-\frac{\beta e_1}{2}>0,\qquad 0<q_*<\min\{1,g/(8\beta^2)\}.\] Choose an integer \(p\ge2\) such that \[ pe_*>a+2. \tag{172}\] This integer is fixed throughout the limit. First choose \(t_p>0\) with \(2t_p<q_*/2\). For \(j=p,p-1,\ldots,2\), take a cutoff \(b_j\in(0,q_*/2)\) allowed by Proposition 15 for large-overlap threshold \(h=t_j/2\), and then choose \(t_{j-1}>0\) with \[ t_{j-1}<t_j/10,\qquad 4t_{j-1}<b_j. \tag{173}\] Thus \(0<t_1<\cdots<t_p\), and all scale gaps are fixed positive constants. Independently of the disorder and of all other randomness introduced below, draw \[ r_j\sim\operatorname{Unif}[t_j,2t_j],\qquad 1\le j\le p, \tag{174}\] independently for different \(j\).

Polynomial reference banks cover every possible target

We next sample finite lists of Gibbs configurations. These lists provide references for the later crossing construction. Their sizes are chosen so that coverage holds for every earlier reference choice and every deterministic index of the path segment \(x_0,\ldots,x_m\).

Conditional on \(J\), all entries in all banks are independent with law \(\pi\), and all banks are independent of the entire chain. Choose their sizes recursively. Having chosen \(D_{3,i}\) for \(i<j\), set \[B_j=\sum_{i<j}(D_{3,i}+1),\qquad B_1=0,\] choose \(D_{1,j}>B_j+a+3\), and use Corollary 22 with exponent \(D_{1,j}\) to obtain \(D_{3,j}>0\). Bank \(j\) consists of \[ M_j=\lceil n^{D_{3,j}+1}\rceil \quad\hbox{entries}\quad V_{j,1},\ldots,V_{j,M_j}. \tag{175}\] The constants are chosen before any bank entries or thresholds are sampled. In particular, the number of tuples with one entry from each of the first \(j-1\) banks satisfies \[ Q_j:=\prod_{i<j}M_i\le2^{j-1}n^{B_j}. \tag{176}\] For the empty product, \(Q_1=1\).

For such a tuple \(\boldsymbol v=(v_1,\ldots,v_{j-1})\), define its cell by \[ S_j(\boldsymbol v) =\{z\in\{-1,1\}^n: |R(v_i,z)|\le3t_i\text{ for every }i<j\}. \tag{177}\] In particular \(S_1=\{-1,1\}^n\). The cell restricts the small overlaps with the earlier references, while coverage will supply a large overlap with the current target inside that cell.

Let \(\mathcal G_n\) be the intersection of the events in the two lemmas. Then \[ \mathbb P(\mathcal G_n^c)=o(1). \tag{182}\] It is determined by \(J,x_0,\ldots,x_m\) and the bank lists. We have now obtained coverage and locking simultaneously for every choice the crossing construction can make; the thresholds remain independent of this event.

A measurable construction of nested crossings

For a reference \(v\in\{-1,1\}^n\), write \(D_v(k)=|R(v,x_k)|\). A single update changes at most one spin, so \[ |D_v(k+1)-D_v(k)|\le2/n \qquad\text{for every }v,k. \tag{183}\] We select the first acceptable entry in each bank, in its given order. To keep every selected reference defined even on exceptional events, we specify both successful selections and defaults.

At level \(1\), choose \(v_1\) as the first entry of bank \(1\) satisfying \(D_{v_1}(0)\ge q_*\). If there is no such entry, set \(v_1=V_{1,1}\), \(\tau_1=0\), and declare the construction inactive. If selection succeeds, set \[ \tau_1=\min\{0\le k\le m:D_{v_1}(k)\le r_1\} \tag{184}\] when the set is nonempty, and declare the construction active. If that set is empty, set \(\tau_1=0\) and declare it inactive.

Suppose \(j\ge2\) and the earlier levels are defined. If the construction is active and \(x_{\tau_{j-1}}\in S_j(v_1,\ldots,v_{j-1})\), select \(v_j\) as the first entry of bank \(j\) in that cell with \[|R(v_j,x_{\tau_{j-1}})|\ge q_*.\] After a successful selection, search backwards from \(\tau_{j-1}\): \[ \tau_j=\max\{0\le k\le\tau_{j-1}:D_{v_j}(k)\le r_j\} \tag{185}\] if this set is nonempty, keeping the construction active. If it is empty, retain the selected \(v_j\), set \(\tau_j=0\), and declare the construction inactive. If the construction was already inactive, the target was outside its cell, or the reference selection failed, set \(v_j=V_{j,1}\) and \(\tau_j=0\), and declare it inactive. An inactive construction stays inactive at all later levels. At every successful selection, the depth at the target is at least \(q_*>2t_j\ge r_j\); hence any successful backwards crossing has \(\tau_j<\tau_{j-1}\).

The information used in these choices is central to the proof. Define \[\mathcal W=\sigma(J,x_0,\ldots,x_m,\text{ all bank lists}),\qquad \mathcal F_0=\mathcal W,\qquad \mathcal F_j=\mathcal W\vee\sigma(r_1,\ldots,r_j).\] Induction through the explicit rules above gives \[ v_j\text{ is }\mathcal F_{j-1}\text{-measurable},\qquad \tau_j\text{ and the active flag after level }j \text{ are }\mathcal F_j\text{-measurable}. \tag{186}\] In particular, neither the selection of \(v_j\) nor any default for it uses \(r_j\) or a later threshold.

Let \(C_1\) denote successful selection of the first reference. On \(C_1\) define \(s_1=\operatorname{sgn}R(v_1,x_0)\in\{-1,1\}\) and let \[ \mathcal S_n=C_1\cap \{\text{there exists }0\le k\le m: s_1R(v_1,x_k)\le0\}. \tag{187}\] Take this event to be false outside \(C_1\). Starting from signed overlap at least \(q_*\), a sign passage must visit absolute overlap at most \(2/n\), because signed overlaps also change by at most \(2/n\). For sufficiently large \(n\), it therefore forces the first crossing in (184).

Independent thresholds make the final shells unlikely

The deterministic construction has reduced a sign passage to a single time at which all selected reference depths lie in narrow intervals about their thresholds. Define this event, using the references from the construction including its defaults, by \[ \mathcal A_n= \{\text{there exists }0\le k\le m: |D_{v_j}(k)-r_j|\le6p\delta_n \text{ for every }1\le j\le p\}. \tag{191}\] Lemma 26, applied at \(\tau_p\), shows that \[ \mathcal G_n\cap\mathcal S_n\subseteq\mathcal A_n. \tag{192}\]

Fix a deterministic \(k\) and set \(E_{j,k}=\{|D_{v_j}(k)-r_j|\le6p\delta_n\}\). By (186), its center \(D_{v_j}(k)\) is \(\mathcal F_{j-1}\)-measurable, while \(r_j\) is independent of \(\mathcal F_{j-1}\) and uniform on an interval of length \(t_j\). Thus \[ \mathbb P(E_{j,k}\mid\mathcal F_{j-1}) \le\min\{1,12p\delta_n/t_j\}. \tag{193}\] The earlier events \(E_{i,k}\), \(i<j\), are \(\mathcal F_{j-1}\)-measurable. Applying conditional expectation successively for \(j=p,p-1,\ldots,1\) therefore gives \[\mathbb P\!\left(\bigcap_{j=1}^pE_{j,k}\,\middle|\,\mathcal W\right) \le\prod_{j=1}^p\min\{1,12p\delta_n/t_j\}.\] The centers may depend on earlier thresholds; the displayed filtration is exactly what allows this product estimate. A union bound over the deterministic indices \(k=0,\ldots,m\) now yields \[ \mathbb P(\mathcal A_n) \le(m+1)\prod_{j=1}^p\frac{12p\delta_n}{t_j} \le C_{\beta,a}n^{a+1-pe_*}=o(1). \tag{194}\] The exponent is less than \(-1\) by (172).

A fast realized initial state forces a sign passage