% low_temp_sk_glauber_typical_v2.txt
% A typical-start upper bound for low-temperature SK Glauber dynamics.
% Single-file clean rewrite. Read top to bottom.

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype,booktabs,array,enumitem}
\usepackage[colorlinks=true,linkcolor=black,citecolor=black,urlcolor=black]{hyperref}
\usepackage{tikz}
\usetikzlibrary{arrows.meta,calc,positioning}
\setlength{\emergencystretch}{3em}
\allowdisplaybreaks
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\title{A typical-start upper bound for low-temperature\\Sherrington--Kirkpatrick Glauber dynamics}
\author{OpenAI}
\date{September 24, 2026}
\begin{document}
\maketitle

\begin{abstract}
We study single-site heat-bath (Glauber) dynamics for the zero-field
Sherrington--Kirkpatrick spin glass at a fixed inverse temperature
$\beta>1$. We prove that a configuration sampled from equilibrium mixes
to equilibrium in subexponential time: for every fixed $\beta>1$ there
is a constant $c_\beta>0$ such that, with probability tending to one
over the disorder and the starting configuration, the total-variation
distance from equilibrium is below $1/4$ by time
$\exp(n^{1-c_\beta})$. The proof admits the explicit value
$c_\beta=1/40000000$ for all fixed $\beta>1$. The starting
configuration is held fixed before the distance to equilibrium is
measured; this is the essential subtlety, since averaging the start into
the law would make the distance zero at every time.
\end{abstract}

\tableofcontents

%======================================================================
\section{Introduction}
%======================================================================

\subsection{The question in plain terms}

The SK model is a mean-field spin glass: $n$ spins
$\sigma_i\in\{-1,1\}$ interact through random pairwise couplings.
The heat-bath (Glauber) dynamics is the natural local sampler. Each site
has an independent rate-one clock; when the clock at site $i$ rings,
the spin $\sigma_i$ is replaced by a fresh value drawn from its
conditional law given all the other spins. The chain has $2^n$ states
and is reversible with respect to the Gibbs measure $\pi^J_{n,\beta}$.

At \emph{high} temperature the chain mixes quickly, in polynomial time
from \emph{every} start. At \emph{low} temperature ($\beta>1$ in the
zero-field SK model) the landscape is glassy: there are deep valleys
separated by high barriers, and a configuration placed in the wrong
valley can take a very long time to escape. Sellke \cite{Sellke2025}
shows the \emph{worst} starting configuration can force an exponential
lower bound on the mixing time.

That leaves a sharper question. An adversarial start is unrealistic for
a sampler run on a freshly drawn instance. What happens if we start the
chain from a \emph{typical} equilibrium configuration, i.e. from one
sample $\sigma_0\sim\pi^J_{n,\beta}$? This paper answers the question
for every fixed $\beta>1$: the chain is fast, at most subexponential in
$n$, from such a start.

Two conventions are essential and we fix them now.
\begin{enumerate}[label=(\roman*)]
\item \textbf{The start is random and then held fixed.} We first draw the
  disorder $J$, then \emph{one} configuration $\sigma_0\sim\pi^J_{n,\beta}$,
  and only then look at the law $P_t^{J,\beta}(\sigma_0,\cdot)$ of the chain
  started at that single $\sigma_0$. The total-variation distance in the
  mixing time is between this fixed-start law and $\pi^J_{n,\beta}$. If one
  instead averaged $\sigma_0$ into the starting distribution, stationarity
  would force the distance to be zero at every time and the question would
  vanish.
\item \textbf{Time is continuous, one clock per site.} Each site rings at
  rate one, so the total jump rate of the chain is exactly $n$.
\end{enumerate}

\subsection{The model}

Let $n\ge2$ and let $(J_{ij})_{1\le i<j\le n}$ be independent standard
Gaussian variables. Put $J_{ji}=J_{ij}$ and $J_{ii}=0$. For a spin
configuration $\sigma\in\{-1,1\}^n$ set
\begin{equation}\tag{H}\label{eq:H}
 H^J_n(\sigma)=\frac1{\sqrt n}\sum_{i<j}J_{ij}\sigma_i\sigma_j,
 \qquad
 \pi^J_{n,\beta}(\sigma)
 =\frac{\exp\bigl(\beta H^J_n(\sigma)\bigr)}{Z^J_{n,\beta}},
\end{equation}
where $Z^J_{n,\beta}$ is the normalizing constant. There is no external
field. The local field at site $i$ is
\[
 h_i(\sigma)=\frac1{\sqrt n}\sum_{j\ne i}J_{ij}\sigma_j .
\]
When the clock at site $i$ rings, the new value equals $s\in\{-1,1\}$
with probability
\begin{equation}\label{eq:heatbath}
 \mathbb P\{\text{new spin}=s\mid\sigma\}
 =\frac{\exp\bigl(\beta s\,h_i(\sigma)\bigr)}
        {2\cosh\bigl(\beta h_i(\sigma)\bigr)} .
\end{equation}
The update may leave $\sigma_i$ unchanged. Let
$P_t^{J,\beta}(\sigma,\cdot)$ denote the law at time $t$ of this
continuous-time chain started from the fixed configuration $\sigma$, and
let
\begin{equation}\tag{T}\label{eq:T}
 T^J_{n,\beta}(\sigma)
 =\inf\Bigl\{t\ge0:
 \bigl\|P_t^{J,\beta}(\sigma,\cdot)-\pi^J_{n,\beta}\bigr\|_{\mathrm{TV}}
 \le\tfrac14\Bigr\}
\end{equation}
be the mixing time from that start. The joint law of interest samples
the disorder and \emph{one} Gibbs configuration,
$\mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}
=\mathbb E_J\,\pi^J_{n,\beta}$.

\subsection{Main results}

\begin{theorem}[Mixing from a typical Gibbs start]\label{thm:main}
For every fixed $\beta>1$ there is a constant $c_\beta\in(0,1)$ such
that
\[
 \mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}\Bigl\{
 T^J_{n,\beta}(\sigma_0)\le\exp\bigl(n^{1-c_\beta}\bigr)\Bigr\}
 \longrightarrow 1
 \qquad (n\to\infty).
\]
The constant may be taken as $c_\beta=1/40000000$ uniformly over every
fixed $\beta>1$, and it does not depend on the realized disorder.
\end{theorem}

Equivalently, in probability over the disorder $J$, the Gibbs mass of
the set of configurations whose mixing time is at most
$\exp(n^{1-c_\beta})$ tends to one. The exponent is not optimized, and
the dimension from which the estimates hold may depend on the fixed
$\beta$; all such thresholds are absorbed into ``tending to one''.

The companion lower bound in \cite{OpenAISKBarriers2026} gives a matching
stretched-exponential barrier. Combined with Theorem~\ref{thm:main} it
produces a two-sided statement.

\begin{corollary}[Two-sided typical-start bound]\label{cor:two-sided}
For every fixed $\beta>1$, in the model and continuous-time convention
above,
\[
 \mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}\Bigl\{
 \exp\bigl(n^{1/10000}\bigr)<T^J_{n,\beta}(\sigma_0)
 \le\exp\bigl(n^{1-1/40000000}\bigr)\Bigr\}
 \longrightarrow 1 .
\]
\end{corollary}

\begin{proof}
The continuous-time form of \cite[Theorem~1.1]{OpenAISKBarriers2026}
states that, with joint probability tending to one,
$\|P^{J,\beta}_{\exp(n^{1/10000})}(\sigma_0,\cdot)-\pi^J_{n,\beta}\|_{\mathrm{TV}}>1/4$
for $\sigma_0\sim\pi^J_{n,\beta}$. By \eqref{eq:T} and continuity of the
finite-state semigroup this forces the strict lower bound
$T^J_{n,\beta}(\sigma_0)>\exp(n^{1/10000})$. The upper bound is
Theorem~\ref{thm:main}. Both events use the same joint law of
$(J,\sigma_0)$ and the same rate-one clocks, so their intersection has
probability tending to one.
\end{proof}

\subsection{How the proof works}

The proof has five logical stages. We describe each in words, then point
to its section.

\begin{enumerate}[label=\textbf{Stage \arabic*.}]
\item \textbf{Equilibrium scalar inputs.} The Parisi theory of the SK
  model provides a scalar potential $\Phi$ and a magnetization martingale
  whose variance in overlap space is dictated by the minimizing Parisi
  measure. We state exactly which equilibrium inputs we use, in the
  normalization of this paper. See Section~\ref{sec:scalar}.

\item \textbf{The long diffusion and its entropy--energy identity.} We
  continue the scalar diffusion past the endpoint of the Parisi support,
  where the magnetizations pin down (level sets shrink exponentially). An
  exact It\^o calculation produces a scalar identity,
  equation~\eqref{eq:scalar-balance}, that balances the information
  acquired by matrix queries against the energy gained. This is the engine
  of the entropy bound. See Section~\ref{sec:scalar}.

\item \textbf{The Gaussian-query proposal.} We build a random spin by
  querying the matrix $W=W(G)$ along orthogonalized directions. Each query
  is conditionally Gaussian given the past and constructs a fresh
  coordinate of a driving Brownian motion. The proposal $Q_l$ has two
  controlled features: sublinear relative entropy ${\rm KL}(Q_l\Vert P)$,
  and a likelihood bound outside an exponentially unlikely event. See
  Section~\ref{sec:proposal}.

\item \textbf{Reversing the entropy: coverage.} Forward entropy alone says
  nothing about reaching a prescribed set. Conditioning the Gibbs joint law
  on the spin makes the remaining disorder law strongly log-concave; a
  small Gaussian smoothing plus the quadratic transport inequality then
  reverses the entropy comparison. The outcome is a coverage statement:
  any Gibbs set of mass at least $n^{-d}$ receives at least
  $\exp(-n^{1-2d})$ proposal mass for the realized target disorder and
  smoothing base. See Section~\ref{sec:reverse}.

\item \textbf{Balancing flows and mixing.} Two independent proposals joined
  across a cut contradict the avoidance of a small boundary \emph{unless}
  every cut of appreciable Gibbs mass carries stationary flow at least
  $B_{\min}=\exp(-n^{1-b/20})$. The geometry is elementary: a short
  sequence of spins crossing a cut must contain a spin close to the
  boundary. Fine-horizon spins supply endpoint coverage; coarse-horizon
  spins have rare enough failures along the connecting sequence, and
  rotating the Gaussian inputs makes consecutive coarse spins close in
  Hamming distance. Then a finite-state pruning lemma and entropy
  dissipation turn the flow bound into a statement about typical fixed
  starting states. See Sections~\ref{sec:connections} and~\ref{sec:mixing}.
\end{enumerate}

Theorems~\ref{thm:main} and \ref{cor:two-sided} are assembled from these
stages at the end of Section~\ref{sec:mixing}.

\subsection{Relation to prior work}

\emph{High-temperature, worst-start.} Eldan, Koehler and Zeitouni
\cite[Section~6]{EKZ2022} proved polynomial worst-start mixing for
$\beta<1/4$. Wang \cite[Theorem~1.1]{Wang2026} established optimal-order
Glauber mixing for every fixed $\beta<1/2$, and Boban, Li and Oveis
Gharan \cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
mixing in zero field to $\beta<1/2+\varepsilon_0$ for some absolute
$\varepsilon_0>0$.

\emph{Low-temperature, worst-start.} Sellke
\cite[Theorem~1.1]{Sellke2025} proved exponential worst-start lower
bounds and distinguished the worst-start obstruction from fast mixing
after Gibbs-distributed start. Theorem~\ref{thm:main} resolves the latter
throughout the fixed low-temperature phase.

\emph{Equilibrium Parisi theory.} The stationarity conditions that drive
the argument come from the variational theory of the Parisi functional:
Chen \cite[Theorem~2, Proposition~1]{Chen2017}, Jagannath and Tobasco
\cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}, and Zhou
\cite[Theorem~1]{Zhou2026}. For the whole low-temperature phase we use
full interval support from Lopatto \cite[Theorem~1.1]{Lopatto2026}
(version~3). Guerra \cite[Theorem~3]{Guerra2003} supplies the pressure
upper bound, and Auffinger--Chen \cite[Propositions~1--2]{AC2015}
supplies spatial regularity and step-approximation stability of the
Parisi equation.

\emph{Techniques.} The Gaussian-query construction is the exact
finite-dimensional analogue of Bolthausen's iterative TAP construction
\cite[Sections~2--3]{Bolthausen2014} and of Montanari's incremental
approximate message passing \cite[Sections~2--3]{Montanari2021}: query,
orthogonalize, reveal. The reverse-entropy step uses triangular transport
under strong convexity \cite[Corollary~3.10]{BKM2005} together with the
convolution comparison recorded in \cite[Lemma~11]{LugosiNeu2022}. The
mixing step combines the coarea proof of the reversible Cheeger
inequality \cite[Theorem~3.5]{LawlerSokal1988} with entropy dissipation
for finite Markov chains \cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}.

%======================================================================
\section{Notation and Gaussian completion}\label{sec:notation}
%======================================================================

Fix a finite $\beta>1$. Constants may depend on this fixed parameter;
when that dependence matters we write $C_\beta$ or $O_\beta(\cdot)$. All
logarithms are natural.

\paragraph{Distances and inner products.} For probability measures
$\mu\ll\nu$ on a common space, set
${\rm KL}(\mu\Vert\nu)=\int\log(d\mu/d\nu)\,d\mu$. On the spin cube,
total variation is one half of the $\ell^1$ distance. For vectors
$v,w\in\mathbb R^n$ write
\[
 \langle v,w\rangle_n=\frac1n\sum_i v_i w_i,
 \qquad |v|_n^2=\langle v,v\rangle_n .
\]
The symbols $\|v\|$ and $\|A\|$ denote the Euclidean norm of a vector and
the operator norm of a matrix.

\paragraph{The GOE completion.} A heat-bath update at site $i$ never sees
$J_{ii}$. We \emph{complete} the interaction matrix by adding independent
diagonal entries of law $N(0,2/n)$: define a symmetric matrix $W=W(G)$
whose entries above the diagonal are $W_{ij}=J_{ij}/\sqrt n$ and whose
diagonal entries are independent $N(0,2/n)$. Write $G$ for the vector of
independent standard Gaussian drivers of all these entries and
$\gamma$ for its law. Since $x_i^2=1$ for every spin,
\[
 \tfrac12\,x^{\mathsf T}\operatorname{diag}(W)\,x
 =\tfrac12\sum_i W_{ii}
\]
is the same random constant for every configuration. Hence the diagonal
contributes the same additive constant to every Gibbs weight; it changes
neither $\pi^J_{n,\beta}$ nor any heat-bath rate nor the transition
kernel. Its effect on $\mathbb E F(G)$ is a deterministic constant that
we absorb into the pressure functional $\mathcal P$ below.

\paragraph{Gibbs weights on the completed matrix.} Define, with $W=W(G)$,
\[
 \widehat H_G(x)=\tfrac12 x^{\mathsf T}W(G)\,x,
 \quad
 F(G)=\log\sum_{x\in\{-1,1\}^n}e^{\beta\widehat H_G(x)},
 \quad
 \pi_G(x)=e^{\beta\widehat H_G(x)-F(G)}.
\]
Because the diagonal is a configuration-independent constant,
$\pi_G=\pi^J_{n,\beta}$ as probability measures. We work with
$\widehat H_G$ everywhere. The Gibbs joint law of disorder and spin is
\[
 P(dG,x)=\gamma(dG)\,\pi_G(dx).
\]
This is exactly the joint law of the starting configuration in
Theorem~\ref{thm:main}. It is crucial that $P$ is a \emph{joint} law:
downstream we compare a proposal law $Q_l$ to $P$ on the joint
$(G,x)$-space. The transition kernel for a \emph{fixed} disorder and a
\emph{fixed} initial configuration is a different object, and the final
mixing argument must separate the two carefully.

%======================================================================
\section{Scalar inputs and the entropy--energy identity}\label{sec:scalar}
%======================================================================

This section extracts the one-dimensional input that drives the whole
proof. The endpoint is Proposition~\ref{lem:scalar-balance}
(equation~\eqref{eq:scalar-balance}): an exact scalar balance between the
energy a matrix-query proposal gains and the information it pays for.
Everything here is about a single diffusion and a few deterministic
functions of a scalar time; no high-dimensional geometry enters yet.

\subsection{Equilibrium inputs, stated once}

Let $\mu_\beta$ be a minimizing Parisi probability measure for the
zero-field Gaussian SK model at the fixed finite $\beta>1$. We use the
following external inputs.

\begin{itemize}[leftmargin=*]
\item \textbf{Pressure.} Guerra's finite-volume interpolation bound
  \cite[Theorem~3]{Guerra2003}: $\mathbb E F(G)\le n\mathcal P$, where
  $\mathcal P$ is the Parisi pressure functional, whose exact
  normalization we give below.
\item \textbf{Regularity and stability.} Auffinger--Chen
  \cite[Propositions~1--2]{AC2015}: the scalar Parisi equation has
  continuous spatial derivatives, and its solution is stable under step
  approximation of the CDF of $\mu_\beta$.
\item \textbf{Full support and stationarity.} Lopatto
  \cite[Theorem~1.1, Lemma~2.2, Proposition~2.4, Lemma~2.5]{Lopatto2026}:
  the minimizing measure has full interval support,
  \[
   \operatorname{supp}(\mu_\beta)=[0,q_*],\qquad 0<q_*<1,
  \]
  and the associated scalar solution obeys the stationarity identity used
  in \eqref{eq:martingale} below.
\end{itemize}

The stationarity identity is also given, in the form we quote, in
Jagannath--Tobasco \cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}.
What full support buys is precisely the ability to apply the identity at
\emph{every} overlap in $[0,q_*]$; mere infinite support would not suffice.

\subsection{Normalization and the scalar Parisi equation}

Use the scalar variance time $v=\beta^2 s$ with $s$ the Parisi time
variable, and put $\alpha_v=\mu_\beta([0,v/\beta^2])$ for
$0\le v\le\beta^2$. Let $\Phi$ solve the backward Parisi equation
\begin{equation}\label{eq:parisi-pde}
 \Phi_v=-\tfrac12\bigl(\Phi_{yy}+\alpha_v\Phi_y^2\bigr),
 \qquad
 \Phi(\beta^2,y)=\log(2\cosh y),
\end{equation}
with subscripts denoting derivatives. Equivalently, if $u$ is the scalar
solution in \cite{Lopatto2026}, then
$\Phi(v,y)=u(v/\beta^2,y)+\log2$. Combining the independent ordered pair
couplings of the source gives the unordered pair coefficient
$\beta/\sqrt n$ used in \eqref{eq:H}, plus a centered diagonal term. Thus
this scalar normalization agrees with our completed Hamiltonian.

Set $v_*=\beta^2 q_*$. The pressure functional and the finite-volume
upper bound read
\begin{equation}\label{eq:pressure}
 \mathcal P=\Phi(0,0)-\frac1{2\beta^2}\int_0^{\beta^2}v\alpha_v\,dv,
 \qquad
 \mathbb E F(G)\le n\mathcal P .
\end{equation}
The centered diagonal shifts neither $\mathcal P$ nor $\mathbb E F(G)$
in any way that matters below. Since $\alpha_v=1$ above $v_*$, the
Gaussian recursion gives, at $v_*$,
\begin{equation}\label{eq:phi-at-vstar}
 \Phi(v_*,y)=\log(2\cosh y)+\frac{\beta^2-v_*}{2} .
\end{equation}

\subsection{Continuation past the support endpoint}

For all $v>v_*$ we continue the potential by the explicit formula
\begin{equation}\label{eq:phi-extension}
 \Phi(v,y)=\log(2\cosh y)+\frac{\beta^2-v}{2},
 \qquad \alpha_v=1 .
\end{equation}
This agrees with the original solution up to $\beta^2$ and satisfies the
same PDE for every $v\ge v_*$. It describes the regime in which the
magnetizations \emph{pin down}: the level sets of the magnetization
shrink and the spin becomes deterministic. Continue for every $v\ge0$
the two scalar functions
\[
 m(v,y)=\Phi_y(v,y),\qquad a(v,y)=\Phi_{yy}(v,y),
\]
so that on the extension $m(v,y)=\tanh y$ and
$a(v,y)=1-\tanh^2 y$.

Let $Z$ be a standard Brownian motion and let $Y$ solve
\begin{equation}\label{eq:Y}
 dY_v=\alpha_v\,m(v,Y_v)\,dv+dZ_v,\qquad Y_0=0 .
\end{equation}
The drift is bounded and spatially Lipschitz, so the scalar SDE has a
unique strong solution. Abbreviate $m_v=m(v,Y_v)$ and
$a_v=a(v,Y_v)$. The stationarity identity, the differentiated PDE, and
It\^o's formula give the key scalar facts
\begin{equation}\label{eq:martingale}
 m_0=0,\qquad dm_v=a_v\,dZ_v,\qquad
 \mathbb E m_v^2=\frac{v}{\beta^2}\quad(0\le v\le v_*),
\end{equation}
and this martingale equation continues past $v_*$ by direct It\^o
calculus with the explicit functions \eqref{eq:phi-extension}. We use,
repeatedly, the deterministic bounds
\begin{equation}\label{eq:a-m-bound}
 0<a(v,y)\le1-m(v,y)^2\le1,\qquad |m(v,y)|<1 .
\end{equation}

\paragraph{Why \eqref{eq:a-m-bound} holds.} We derive it in the form that
behaves well under step approximation. One Parisi step of CDF height
$\lambda\in[0,1]$ and variance $\delta>0$ maps a profile $f$ to
\[
 (Tf)(y)=\frac1\lambda\log\mathbb E\,
 e^{\lambda f(y+\sqrt\delta U)},\qquad U\sim N(0,1),
\]
with $Tf(y)=\mathbb E f(y+\sqrt\delta U)$ when $\lambda=0$. Write
$\mathbb E_\lambda$ for the Gaussian expectation tilted by
$e^{\lambda f(y+\sqrt\delta U)}$ and renormalized. Differentiating gives
the exact formulas
\[
 (Tf)'=\mathbb E_\lambda f',\qquad
 (Tf)''=\mathbb E_\lambda f''+\lambda\operatorname{Var}_\lambda(f') .
\]
Suppose $0<f''\le1-(f')^2$. Then
\[
 0<(Tf)''\le1-\bigl((Tf)'\bigr)^2-(1-\lambda)\operatorname{Var}_\lambda(f')
 \le1-\bigl((Tf)'\bigr)^2 .
\]
Inducting from $f(y)=\log(2\cosh y)$ proves the bound for step CDFs;
stability \cite[Propositions~1--2]{AC2015} passes the non-strict bound to
the minimizing CDF, and the strict lower bound on $\Phi_{yy}$ in
\cite[Proposition~2.4]{Lopatto2026} gives strict positivity in the limit.
Hence $m$ is strictly increasing and $|m|<1$, giving
\eqref{eq:a-m-bound}. On the extension these assertions follow from
$\tanh$ directly.

\subsection{Tail estimates for the extended diffusion}

Define the three deterministic functions
\begin{equation}\label{eq:prho}
 p(v)=\mathbb E a_v,\qquad r(v)=\mathbb E a_v^2,
 \qquad \rho(v)=\beta\sqrt{r(v)} .
\end{equation}
The martingale second-moment identity \eqref{eq:martingale} and
continuity give $r(v)=1/\beta^2$ on $[0,v_*]$, endpoints included. The
next lemma controls the continuation and confirms that $\rho$ is an
admissible noise-mixing coefficient in $[0,1]$.

\begin{lemma}[Scalar tail bounds]\label{lem:scalar-tail}
For $v\ge v_*$ the extended diffusion obeys
\begin{equation}\tag{1}\label{eq:1}
 \rho(v)\le1,\qquad -2\le(\log r)'(v)\le0,
 \qquad p'(v)=-r(v),
 \qquad p(v)\le C_\beta e^{-v/2} .
\end{equation}
At $v=v_*$ the derivatives are from the right.
\end{lemma}

\begin{proof}
We use the transformed-density method of
\cite[Proposition~7.1]{Lopatto2026} and the moment comparison of
\cite[Proposition~9.3]{Lopatto2026}, which together give the required
estimates for the arbitrary-time continuation.

\emph{Two moment ratios.} For $v>v_*$, the density of $Y_v$ divided by
$\cosh y$ is symmetric and nonincreasing in $|y|$. It suffices to check
this for step CDFs and pass to the limit; stability
\cite[Propositions~1--2]{AC2015} justifies the passage. For a step CDF
with masses $\alpha^{(j)}$ on intervals $[v_j,v_{j+1}]$, and
$\varphi_t$ the centered Gaussian density of variance $t$, the transition
density on one interval is
\[
 K_j(z,y)=\varphi_{v_{j+1}-v_j}(y-z)
 \exp\bigl\{\alpha^{(j)}[\Phi(v_{j+1},y)-\Phi(v_j,z)]\bigr\} .
\]
The Gaussian recursion normalizes $K_j$; its Doob transform has drift
$\alpha^{(j)}\Phi_y$. In a product of kernels the intermediate factors at
$y_j$ reduce to
\[
 \exp\bigl\{-(\alpha^{(j)}-\alpha^{(j-1)})\Phi(v_j,y_j)\bigr\},
\]
which is even and nonincreasing in $|y_j|$ because the masses are
nondecreasing and $\Phi$ is even and convex. The first positive-time
Gaussian convolution turns the initial point mass at zero into a
symmetric decreasing density, and multiplication by these factors plus
further Gaussian convolutions preserve that property (using the
centered-interval level-set representation of a symmetric decreasing
profile). Extending the final mass to one leaves an endpoint factor
proportional to $\cosh y$; dividing by it leaves the asserted symmetric
decreasing profile.

Weighting either $\operatorname{sech}y$ or $\operatorname{sech}^3y$ by a
decreasing profile can only increase the expectation of
$\operatorname{sech}^2y$, since two nonincreasing functions of $|y|$ have
nonnegative covariance. Integration by parts gives
\[
 \frac{\int_{\mathbb R}\operatorname{sech}^{k+2}y\,dy}
      {\int_{\mathbb R}\operatorname{sech}^{k}y\,dy}
 =\frac{k}{k+1}\qquad(k>0).
\]
Consequently $r/p\ge1/2$ and $\mathbb E a_v^3/r(v)\ge3/4$.

\emph{Differential identities.} On the extension $a_v=1-m_v^2$, and
direct It\^o calculations yield
\[
 p'=-r,\qquad r'=4r-6\,\mathbb E a_v^3 .
\]
The two moment ratios imply $p'\le-p/2$ and $r'\le0$. Since
$0<a_v\le1$, the second identity also gives $r'\ge-2r$. Integrating
$p'\le-p/2$ gives $p(v)\le C_\beta e^{-v/2}$. Finally
$r(v_*)=1/\beta^2$ and monotonicity of $r$ imply $\rho\le1$.
\end{proof}

\subsection{The entropy--energy identity}

Let $\mathcal H(z)$ be the entropy of a sign with mean $z\in(-1,1)$:
\[
 \mathcal H(z)=-\frac{1+z}{2}\log\frac{1+z}{2}
              -\frac{1-z}{2}\log\frac{1-z}{2},
\]
with continuous values at $z=\pm1$. For $V>v_*$ define the two scalars
that will be the energy per spin and the information cost per spin of the
matrix proposal:
\begin{equation}\label{eq:ej}
 e(V)=\int_0^V\sqrt{r(v)}\,p(v)\,\rho(v)\,dv,
 \qquad
 j(V)=\frac12\int_0^V\rho(v)^2\,
        \mathbb E\frac{a_v^2}{1-m_v^2}\,dv .
\end{equation}
The factor $\rho(v)^2$ inside $j$ accounts for the independent noise we
introduce in the proposal. Below the support endpoint, It\^o's formula
together with the PDE and stationarity gives
\[
 \mathbb E[Y_{v_*}m_{v_*}]=\int_0^{v_*}\bigl(p(v)+\alpha_v v/\beta^2\bigr)\,dv,
 \qquad
 \mathbb E\Phi(v_*,Y_{v_*})=\Phi(0,0)
   +\frac12\int_0^{v_*}\alpha_v v/\beta^2\,dv .
\]
These also follow by step approximation with bounded first and second
spatial derivatives. Substituting the endpoint value \eqref{eq:phi-at-vstar}
and using $\mathcal H(\tanh y)=\log(2\cosh y)-y\tanh y$ gives
\begin{equation}\tag{2}\label{eq:pre-balance}
 \int_0^{v_*}p(v)\,dv+\mathbb E\,\mathcal H(m_{v_*})
 =\mathcal P-\frac{\beta^2}{4}(1-q_*)^2 .
\end{equation}

\begin{proposition}[Entropy--energy identity]\label{lem:scalar-balance}
For every $V>v_*$,
\begin{equation}\tag{3}\label{eq:scalar-balance}
 \log2-j(V)+\beta e(V)=\mathcal P-\frac{\beta^2}{4}\,p(V)^2 .
\end{equation}
\end{proposition}

\begin{proof}
The same martingale calculation applied to binary entropy yields
\[
 \frac12\int_0^{v_*}\mathbb E\frac{a_v^2}{1-m_v^2}\,dv
 =\log2-\mathbb E\,\mathcal H(m_{v_*}).
\]
Localization justifies It\^o's formula near $z=\pm1$; the integrand is
bounded because $a\le1-m^2$. Since $\rho=1$ and $\beta\sqrt r=1$ on
$[0,v_*]$, the two identities above prove \eqref{eq:scalar-balance} at
$V=v_*$. Above $v_*$ the derivative of the left side of
\eqref{eq:scalar-balance} is $(\beta^2/2)\,r(v)\,p(v)$: indeed
$a_v=1-m_v^2$ there, and $\rho^2=\beta^2 r$. The derivative of
$-\beta^2p(v)^2/4$ is the same, by $p'=-r$. Integrating from $v_*$
therefore proves the claim for every $V>v_*$.
\end{proof}

The terminal error $\tfrac{\beta^2}{4}p(V)^2$ on the right of
\eqref{eq:scalar-balance} is at most $C_\beta e^{-V}$ by
\eqref{eq:1}. We take $V$ proportional to $\log n$, so this error is a
negative power of $n$ while the spin is nearly pinned.

%======================================================================
\section{The Gaussian-query proposal}\label{sec:proposal}
%======================================================================

We now build a random spin using the matrix $W=W(G)$ together with
auxiliary randomness. The construction has a single design principle:
\emph{each query of the matrix is orthogonal to the earlier queries and
is independent given the past.} This exposes fresh Gaussian information
while leaving a compressed GOE block unrevealed, so that a clean
conditional-Gaussian argument applies at every step. The scalar identity
\eqref{eq:scalar-balance} will then control both the relative entropy of
the resulting law $Q_l$ and its likelihood outside a small exceptional
event.

The spirit is the same as Bolthausen's iterative TAP construction
\cite[Sections~2--3]{Bolthausen2014} and Montanari's incremental
approximate message passing \cite[Sections~2--3]{Montanari2021}, both of
which reveal Gaussian information along orthogonalized directions. What
is new here is the \emph{exact} conditional-law bookkeeping for a finite
mesh, including the independent auxiliary noises that complete each
increment.

\subsection{Construction and conditional Gaussian laws}

\paragraph{Mesh.} Fix a horizon parameter\footnote{We use the letter
$l$ both for the horizon parameter and, later, for the horizon value.
Context disambiguates. The final paper uses $l=f$ for fine coverage and
$l=b$ for the coarse connecting sequence; see Section~\ref{sec:reverse}.}
$0<l\le1/100$ and set
\begin{equation}\label{eq:mesh}
 h=n^{-1/16},\qquad K=\lceil l\log n/h\rceil,\qquad
 t_k=kh,\qquad V=t_K .
\end{equation}
For all sufficiently large $n$, $K<n$, and $V>v_*$ with $v_*$ the support
endpoint of Section~\ref{sec:scalar}.

\paragraph{The two driving streams.} The disorder $G$ retains its ordinary
Gaussian law $\gamma$. We build a vector-valued process whose coordinates
follow the scalar SDE \eqref{eq:Y}, driven by two independent streams,
\begin{equation}\tag{4}\label{eq:4}
 dZ=\rho(v)\,dB+\sqrt{1-\rho(v)^2}\,dD .
\end{equation}
Here $D$ is an auxiliary standard Brownian motion, independent of
everything; $B$ is to be constructed from matrix queries together with
auxiliary completions so that, after averaging over the disorder, $(B,D)$
is a standard Brownian pair. By \eqref{eq:1} the weight $\rho\le1$ equals
one up to $v_*$ and is nonincreasing afterwards; this is exactly what
keeps the level sets pinning while retaining unit variance in $Z$. Write
$M(v)_i=m(v,Y_{v,i})$.

\paragraph{Building $B$.} On the first interval $[0,h]$ we generate $B$
entirely from independent auxiliary Brownian noise. For each subsequent
interval $[t_k,t_{k+1}]$, $1\le k<K$, the previous scalar increment
determines
\begin{equation}\label{eq:skTk}
 s_k^2=\int_{t_{k-1}}^{t_k}r(v)\,dv,
 \qquad T_k=\frac{M(t_k)-M(t_{k-1})}{s_k} .
\end{equation}
Project $T_k$ off the preceding query directions $u_1,\dots,u_{k-1}$ and
normalize the residual to obtain $|u_k|_n=1$. If the residual is exactly
zero, choose a new direction measurably from the past: project the
coordinate basis vectors in their fixed order, take the first nonzero
projection, and normalize it. Since $k<n$, such a direction always
exists. Let $\Pi_{\le k}$ be the orthogonal projection onto the span
through $u_k$, and $\Pi_{>k}=I-\Pi_{\le k}$.

Query the column $Wu_k$. For an independent standard Gaussian vector
$z_k$, set the endpoint of the next Brownian increment to be
\begin{equation}\label{eq:gk}
 g_k=h^{-1/2}\bigl(B(t_{k+1})-B(t_k)\bigr)
    =\Pi_{>k}Wu_k+\Pi_{\le k}z_k .
\end{equation}
Fill the interval by linear interpolation between its endpoints plus an
independent centered Brownian bridge. Every new bridge and completion
noise is fresh. A deterministic-coefficient integral against this filled
path may equivalently be obtained by conditioning Brownian motion on its
endpoint.

\paragraph{The spin.} At time $V$, given the path, draw the coordinates
$x_i\in\{-1,1\}$ independently with means $M_i(V)$. Let $Q_l$ be the
marginal law of $(G,x)$ produced this way.

\paragraph{Why $(B,D)$ is a standard Brownian pair.} Condition on the
columns already revealed and on the auxiliary inputs already used.
Gaussian orthogonal invariance leaves the unqueried block a GOE matrix on
the orthogonal complement, with the original variance scale. The next
direction $u_k$ is measurable with respect to this past. In an
orthonormal basis beginning with $u_k/\sqrt n$, the new diagonal entry,
the remaining entries of that column, and the next compressed block are
independent. Hence $\Pi_{>k}Wu_k$ is a fresh Gaussian with covariance
$\Pi_{>k}$, and
\[
 d_k=\langle u_k,Wu_k\rangle_n\sim N(0,2/n)
\]
conditionally, before the column is revealed. The independent completion
has covariance $\Pi_{\le k}$, so $g_k$ in \eqref{eq:gk} is a fresh
standard Gaussian vector. Induction, followed by the independent bridge
filling, proves that $(B,D)$ in \eqref{eq:4} is a standard Brownian pair.

\paragraph{Coordinate symmetry.} After forgetting the matrix, the
coordinate paths and their final spins are i.i.d. The conditional mean of
$x$ given the streams through time $v$ is $M(v)$, and its unconditional
law is uniform on the cube by the symmetry of the scalar process. The
spin marginal of $P$ is also uniform, by coordinate-sign symmetry of the
disorder. Both are facts about marginals; the proposal spin remains
correlated with its own matrix.

\subsection{Entropy and likelihood estimates}

The next proposition supplies two distinct comparisons. Entropy will
yield coverage after smoothing; the likelihood estimate will keep
intermediate proposals out of the small boundary of a putative low-flow
cut. Both are stated for the joint law $Q_l$ on $(G,x)$-space.

\begin{proposition}[Proposal comparison]\label{prop:proposal}
For every fixed $0<l\le1/100$ and all sufficiently large $n$,
\begin{equation}\tag{5}\label{eq:5}
 {\rm KL}(Q_l\Vert P)\le2n^{1-l/2} .
\end{equation}
Moreover, there is an event in the proposal experiment of probability at
least $1-\exp(-n^{1-10l})$ such that the output subprobability
restricted to this event is dominated on $(G,x)$-space by
\begin{equation}\tag{6}\label{eq:6}
 \exp(n^{1-l/2})\,P .
\end{equation}
The good event is determined entirely by the inputs of this one proposal
run. Finally, the empirical Gram matrix of the $T_k$ is within $n^{-l}$ of
the identity in operator norm, except with probability at most
$\exp(-n^{1-10l})$. The dimension from which all this holds may depend on
the fixed $l$.
\end{proposition}

\begin{proof}
Put $\eta=n^{-l}$. We evaluate the proposal energy from empirical inner
products, then compute the information cost of its matrix channel, and
combine with the pressure bound and the scalar identity
\eqref{eq:scalar-balance}.

\paragraph{Empirical inner products.} Form the empirical matrix of all
normalized inner products among $T_k,g_k$ ($1\le k<K$) and $x$. It is an
average of $n$ i.i.d. row outer products, by the coordinate law above.
Every unit linear form of a row is sub-Gaussian with norm at most
$C_\beta e^V$. For the $T_k$ part, use their disjoint martingale
increments, $|a|\le1$, and
\begin{equation}\label{eq:sk-lower}
 s_k^2\ge c_\beta h\,e^{-2V},
\end{equation}
which follows from \eqref{eq:1}. An exponential martingale estimate
bounds the linear form by its deterministic quadratic-variation bound.
The $g_k$ part is Gaussian and the spin term is bounded; the correlations
with the first part do not affect the resulting sub-Gaussian bound: for
squared linear forms the moments are bounded by
$k!\,(C_\beta e^{2V})^k$, and expanding the centered exponential moment
followed by exponential Markov gives, at deviation scale $\eta/2$, a
quadratic-form tail
\[
 2\exp\bigl(-c_\beta n\eta^2e^{-4V}\bigr).
\]
A $1/4$-net of the unit sphere in dimension $O(K)$ has $\exp(O(K))$
points, by ball packing. The quadratic-form norm inequality and a union
bound therefore put the whole empirical matrix within $\eta$ of its
expectation, with exceptional probability at most $\exp(-n^{1-8l})$.

The population identities are
\begin{equation}\label{eq:pop}
 \mathbb E[T_jT_k]_{\rm row}=\mathbf1_{j=k},\quad
 \mathbb E[T_jg_k]_{\rm row}=0\ (j\le k),\quad
 \mathbb E[T_kx]_{\rm row}=s_k,\quad
 \mathbb E[g_kx]_{\rm row}=b_k,
\end{equation}
where
$b_k=h^{-1/2}\int_{t_k}^{t_{k+1}}p(v)\rho(v)\,dv$. These follow from the
martingale bracket, the conditional mean of the final spin, and
\eqref{eq:4}. The vectors $s=(s_k)$ and $b=(b_k)$ each have Euclidean
norm at most one, by projection of the unit-variance spin onto the
corresponding orthonormal scalar variables.

\paragraph{Triangular Cholesky and matrix norms.} We need a matrix-norm
estimate that does not lose a factor $K$ under orthogonalization. Taking
the triangular part of an $m\times m$ matrix costs at most $C\log(2m)$ in
operator norm: pad to a power of two and partition the strict triangle by
dyadic scales; at each scale the rectangles have disjoint row and column
sets, so retaining that scale is contractive; summing over scales proves
the bound.

Let $A$ be a Gram matrix with $\|A-I\|\le\eta<1/2$, and let
$R^{\mathsf T}R=A$ be its upper Cholesky factor. Along
$A(t)=I+t(A-I)$, differentiation shows that $\dot RR^{-1}$ is the upper
triangular part, with half the diagonal, of
$R^{-\mathsf T}\dot AR^{-1}$. The norms of $R$ and $R^{-1}$ are uniformly
bounded; the preceding triangular estimate plus integration give
\[
 \|R-I\|\le C\eta\log(2m).
\]
(Differentiability follows directly from the triangular Cholesky
recursion.)

Apply this with the Gram matrix of the $T_k$. The query matrix with
columns $u_k$ is the matrix with columns $T_k$ multiplied by $R^{-1}$. So,
writing $c_k=\langle u_k,x\rangle_n$, the empirical event gives
\[
 \begin{aligned}
 \|c-s\|&\le C\eta\log(2K),\\
 \left\|\bigl(\mathbf1_{j\le k}\langle u_j,g_k\rangle_n\bigr)_{jk}\right\|
 &\le C\eta\log(2K),\\
 \bigl\|(\langle g_k,x\rangle_n)_k-b\bigr\|&\le\eta .
 \end{aligned}
\]
The middle estimate uses that left multiplication of the population cross
matrix by the lower-triangular $R^{-\mathsf T}$ preserves its zero upper
triangle, including the diagonal. Also $\|c\|\le1$, because the query
directions are orthonormal in $|\cdot|_n$.

\paragraph{Energy of the final spin.} Let $H_0=\Pi_{>K-1}$. Revealing the
columns in order decomposes the quadratic form exactly as
\[
 \frac{\widehat H_G(x)}n
 =\sum_kc_k\langle x,\Pi_{>k}g_k\rangle_n
  +\tfrac12\sum_kc_k^2d_k
  +\tfrac12\langle x,H_0WH_0x\rangle_n .
\]
The last two terms are $O(\eta)$ outside an event of probability at most
$CK\exp(-cn\eta^2)$: the diagonal estimate follows from the conditional
Gaussian law and $\sum c_k^2\le1$, while the residual term uses that the
spin has not seen the unrevealed block. Removing the projections in the
first term costs at most $C\eta\log(2K)$ by the triangular bound. Its
remaining value is $s\cdot b$ up to the same error. The bound on
$(\log r)'$ in \eqref{eq:1} implies $s_k/\sqrt h$ differs from
$\sqrt{r(v)}$ on $[t_k,t_{k+1}]$ by a relative $O(h)$. The missing initial
interval contributes $O(h)$, and $e(V)$ is bounded. Hence $s\cdot b=e(V)+O_\beta(h)$,
and altogether
\begin{equation}\tag{7}\label{eq:7}
 \widehat H_G(x)/n=e(V)+O_\beta\bigl(h+\eta\log(2K)\bigr).
\end{equation}
This is the energy contribution to the comparison. We next isolate the
entropy paid for the matrix information alone.

\paragraph{The auxiliary reference law.} Start on an enlarged path space
with an independent uniform spin $x$, the ordinary Gaussian disorder, and
all unconditioned proposal inputs. Call this the \emph{unlinked}
experiment. To obtain the actual proposal, multiply the density of the
unlinked experiment by
\[
 \prod_i\bigl(1+x_i\,m(V,Y_{V,i})\bigr).
\]
For fixed $x$, the scalar martingale shows this is a stochastic
exponential with coordinate integrands
\[
 \xi_i(v)=\frac{x_i\,a(v,Y_{v,i})}{1+x_i\,m(v,Y_{v,i})},
 \qquad |\xi_i(v)|\le2,
\]
against the streams $Z_i$ in \eqref{eq:4}. Call the resulting law the
\emph{linked} experiment. Summing the linking density over the uniform
spin shows the path and disorder marginal is unchanged.

For a continuous local martingale $N$ starting at zero write
$\mathcal E(N)_V=\exp(N_V-\langle N\rangle_V/2)$. The linking density
factors as $E_BE_D$ with
\[
 \begin{aligned}
 E_B&=\mathcal E\Bigl(\sum_i\int_0^{\cdot}\xi_i\rho\,dB_i\Bigr)_V,\\
 E_D&=\mathcal E\Bigl(\sum_i\int_0^{\cdot}\xi_i\sqrt{1-\rho^2}\,dD_i\Bigr)_V,
 \end{aligned}
\]
using the zero quadratic covariation of $B$ and $D$. Define the
\emph{auxiliary reference} to have density $E_D$ relative to the unlinked
law. Its $(G,x)$-marginal is again the independent product of Gaussian
disorder and uniform spin. The conditional mean-one assertion behind this
fact needs a filtration check, since the matrix-query endpoints depend on
the past of $D$.

\paragraph{Filtration check.} Let $\mathcal A$ contain all primitive
auxiliary inputs except $D$, and under the unlinked law set
\[
 \mathcal F_v=\sigma(x,B_{[0,v]},D_{[0,v]}),\qquad
 \mathcal G_v=\sigma(x,G,\mathcal A,D_{[0,v]}).
\]
Interval by interval, every query direction is determined by past $D$ and
by information in $\mathcal G_0$. Each new endpoint and its entire bridge
are known before using the current $D$-increment. Deterministic-coefficient
bridge integrals are linear Gaussian integrals with the endpoint term
fixed by that past. Thus $\mathcal F_v\subseteq\mathcal G_v$. One can
also see this pathwise: $\rho=1$ before $v_*$, and \eqref{eq:1} gives
$-\rho\le\rho'\le0$ afterward, so $\rho$ has bounded variation and the
identity $\int\rho\,dB=\rho B-\int B\,d\rho$, applied on successive
intervals, uses no future $D$.

The pair $(B,D)$ is Brownian in $\mathcal F$, and $D$ is Brownian in
$\mathcal G$ because its time-zero information is independent of $D$. The
bounded continuous $D$-integrand has the same stochastic integral in
these two filtrations: identical left-endpoint approximations converge in
$L^2$ by the It\^o isometry. The bounded-integrand exponential-martingale
theorem in $\mathcal G$ now gives conditional mean one given
$(x,G,\mathcal A)$, proving the claimed marginal. All later Brownian
changes of measure use $\mathcal F$; no Brownian property for $B$ in the
enlarged filtration is required.

\paragraph{Information cost and likelihood.} The density of the linked
experiment relative to the auxiliary reference is $E_B$, whose logarithm
is
\[
 L=\log E_B=\sum_i\Bigl(\int_0^V\xi_i\rho\,dB_i
                  -\tfrac12\int_0^V\xi_i^2\rho^2\,dv\Bigr).
\]
Under the linked law, compensating the $B_i$-drift by $\rho\xi_i$ leaves
a centered integral with bracket at most $4nV$, so it has
exponential-martingale tails. The remaining half-bracket is a sum of
independent coordinate variables, each bounded by $2V$. Coordinate
independence holds after linking because the linking density factors
across the i.i.d. coordinate streams and uniform spins; conditionally on
the streams through time $v$, the linked spin has probabilities
$(1\pm m(v,Y_{v,i}))/2$. We obtain
\begin{equation}\label{eq:L-conc}
 \mathbb E L=nj(V),\qquad L=nj(V)+O(n\eta),
\end{equation}
outside an event of probability at most $\exp(-n^{1-4l})$ for large $n$.
The centered integral is controlled by exponential Markov; the
half-bracket by bounded-variable concentration. The Brownian drift change
follows either from Girsanov's theorem for bounded integrands, or from
bounded predictable step approximation together with the mean-one
exponential identities.

\paragraph{Changing the reference to $P$.} Change the auxiliary reference a
second time, multiplying only by the density of $P$ relative to
independent disorder and uniform spin. The new reference has
$(G,x)$-marginal $P$, and the log density of the linked experiment
relative to it is
\[
 L-n\log2+F(G)-\beta\widehat H_G(x).
\]
Differentiating the log partition function gives a Gaussian Lipschitz
constant at most $C_\beta\sqrt n$. The Gaussian concentration inequality
\cite[Section~5.4, Theorem~5.6]{BLM2013} together with the pressure bound
\eqref{eq:pressure} therefore implies
\[
 F(G)\le n\mathcal P+n\eta
\]
outside an event of probability at most $2\exp(-c_\beta n\eta^2)$. This
uses the ordinary Gaussian marginal of $G$, which is unchanged after
linking.

\paragraph{Substituting the scalars.} Insert \eqref{eq:scalar-balance},
\eqref{eq:7}, $p(V)^2\le C_\beta e^{-V}$ and \eqref{eq:L-conc} into the log
density. On the events just proved it is at most
\[
 C_\beta n\bigl(h+\eta\log(2K)+e^{-V}\bigr)=o\bigl(n^{1-l/2}\bigr).
\]
Indeed $V=l\log n+O(h)$, $\log(2K)=O(\log n)$, and
$0<l\le1/100<1/16$. The union of the exceptional events has probability
at most $\exp(-n^{1-10l})$ for sufficiently large $n$. Taking the
restricted output marginal gives \eqref{eq:6}, and its good event is
defined entirely from the inputs of this one proposal run.

\paragraph{The entropy bound.} The same comparison in expectation proves
\eqref{eq:5} by contraction of relative entropy under marginalization. The
exceptional paths contribute negligibly: $L$ has second moment
$O(n^2(1+V)^2)$, and the supremum of the absolute spin energies has second
moment $O(n^2)$ by Gaussian tails and a union bound. The log partition
function is bounded by $n\log2$ plus that energy supremum. Cauchy--Schwarz
controls all exceptional contributions. The Gram estimate was already
established.
\end{proof}

%======================================================================
\section{Reversing the entropy: coverage}\label{sec:reverse}
%======================================================================

Proposition~\ref{prop:proposal} controls ${\rm KL}(Q_l\Vert P)$, the
entropy cost of \emph{producing} a proposal spin. But entropy in the
forward direction is not enough: a set of large Gibbs mass might still
receive negligible proposal mass, and we will need in
Section~\ref{sec:connections} that a proposed spin reaches such a set with
appreciable probability. We therefore need a \emph{reverse} comparison.

The idea is to condition the Gibbs joint law on the spin. With the spin
fixed, the remaining law of the disorder is strongly log-concave. A small
Gaussian smoothing then turns the forward comparison into the reverse one
via the quadratic transport inequality.

\subsection{Horizons and the smoothing map}

For the rest of the proof fix the four exponents
\begin{equation}\label{eq:exponents}
 f=\frac1{100},\qquad d=\frac f{100}=\frac1{10000},\qquad
 b=\frac d{100}=\frac1{1000000},\qquad \delta=n^{-f/4}.
\end{equation}
The relation $b\ll d\ll f$ is the whole hierarchy. The longer horizon
$l=f$ is used for coverage: it is the one whose proposal mass on Gibbs
sets will be bounded below. The shorter horizon $l=b$ is reserved for the
connecting sequence in Section~\ref{sec:connections}: its exceptional-event
estimate $\exp(-n^{1-10b})$ is far stronger, even though its entropy bound
\eqref{eq:5} is weaker.

\begin{definition}[Smoothing map $\mathcal S$]
For any joint law of disorder and spin, let $\mathcal S$ retain the spin
and replace its disorder by
\begin{equation}\label{eq:smoothing}
 G^\circ=\sqrt{1-\delta}\,G+\sqrt\delta\,\bar G,
\end{equation}
where $\bar G\sim\gamma$ is independent of everything.
\end{definition}

Both $\mathcal SP$ and $\mathcal SQ_f$ have standard Gaussian disorder
marginal. To generate the conditional spin kernel $\nu(\cdot\mid G^\circ)$
of $\mathcal SQ_f$ given the smoothed disorder, use Gaussian regression:
given $G^\circ$, run the $l=f$ proposal on
\[
 \sqrt{1-\delta}\,G^\circ+\sqrt\delta\,G'
\]
with fresh independent standard Gaussian $G'$ and fresh independent
auxiliary inputs. This is the conditional law of the proposal given the
smoothed disorder, by the Bayes rule for Gaussian vectors.

\subsection{Why smoothing reverses the entropy comparison}

The central reverse inequality is the following.

\begin{proposition}[Smoothing reverses KL]\label{prop:smoothing}
\begin{equation}\tag{8}\label{eq:8}
 {\rm KL}(\mathcal SP\Vert\mathcal SQ_f)
 \le\delta^{-1}\,{\rm KL}(Q_f\Vert P) .
\end{equation}
\end{proposition}

\begin{proof}
The two unsmoothed laws have the same uniform spin marginal (see
Section~\ref{sec:proposal}). Given $x$, the conditional disorder density
of $P$ has negative logarithm, up to a normalizing constant,
\[
 U_x(G)=\tfrac12\|G\|^2-\beta\widehat H_G(x)+F(G).
\]
Its Hessian is at least the identity: the Hamiltonian is linear in $G$
(hence contributes nothing to the Hessian), and $F$ is a convex
log-sum-exp of linear functions.

We use the following consequence of strong convexity. Suppose $\mu$ has
density proportional to $e^{-U}$ with $\nabla^2U\ge I$, and $\lambda\ll\mu$.
Then there are couplings of $\mu,\lambda$ whose mean squared displacement
is at most $2{\rm KL}(\lambda\Vert\mu)$ (or tends to that bound). This is
the quadratic transport inequality; the triangular-transport form is
\cite[Corollary~3.10]{BKM2005}. We recall the proof for the
finite-dimensional densities used here.

\emph{Transport bound on a box.} Restrict to a box and suppose both
densities are smooth and strictly positive up to its boundary. Map $\mu$
to $\lambda$ by successive increasing conditional quantile maps. The
resulting triangular map $T$ has positive diagonal derivatives, whose
product is its Jacobian determinant. The entropy formula is
\[
 {\rm KL}(\lambda\Vert\mu)
 =\int\bigl(U(T(z))-U(z)-\log\det\nabla T(z)\bigr)\,d\mu(z).
\]
Strong convexity bounds the first difference below by
$\nabla U(z)\cdot(T(z)-z)+\tfrac12\|T(z)-z\|^2$. Integration by parts
replaces the linear term by $\operatorname{div}(T-\mathrm{id})$. There is
no boundary term: on a face where the $i$-th coordinate is an endpoint of
the box, the conditional quantile map fixes that endpoint, so the normal
component $T_i-z_i$ vanishes; tangential motion does not matter. The
Jacobian terms are nonnegative because $z-1-\log z\ge0$ for every positive
diagonal derivative $z$. This proves the coupling bound on the box.

\emph{Approximation.} For fixed $n$, the conditional proposal density is
bounded by a constant times a Gaussian density, since its spin probability
is at most one. Truncate both conditional laws to increasing boxes and
normalize them. On each box, approximate $\lambda$ by smoothing and mixing
with a small positive constant density; the smooth reference density is
bounded away from zero on the box, so the relative entropies with respect
to the reference converge. The original laws have Gaussian tails up to
constants for fixed $n$ and finite relative entropy. Thus the truncated
entropies converge, and tightness plus lower semicontinuity pass the
coupling bound to the original laws.

\emph{Applying to $P$ and $Q_f$.} Apply the transport bound with
$\mu=P(\cdot\mid x)$ and $\lambda=Q_f(\cdot\mid x)$. For any coupling of
two disorder values $g,\widetilde g$, the Gaussian smoothing kernels
satisfy
\[
 {\rm KL}\bigl(N(\sqrt{1-\delta}\,g,\delta I)
       \Vert N(\sqrt{1-\delta}\,\widetilde g,\delta I)\bigr)
 =\frac{1-\delta}{2\delta}\|g-\widetilde g\|^2 .
\]
The convolution comparison is also recorded in
\cite[Lemma~11]{LugosiNeu2022}. Joint convexity of entropy bounds the
divergence between the mixtures by this averaged kernel quantity. Average
over the common spin marginal and use the entropy chain rule. The
transport bound then proves \eqref{eq:8}.
\end{proof}

\subsection{Coverage conditional on a target and its base}

The smoothed entropy comparison \eqref{eq:8} is a joint-law statement. We
now extract a statement for the original Gibbs law at a realized target
disorder $G$, using only the base $G^\circ$ that we also sample. The
following proposition records both the expected entropy estimate and the
coverage consequence used in the next section.

\begin{proposition}[Coverage at a target disorder]\label{prop:coverage}
Let $G,\bar G$ be independent standard Gaussian disorder vectors, set
$G^\circ=\sqrt{1-\delta}\,G+\sqrt\delta\,\bar G$, and let
$\nu(\cdot\mid G^\circ)$ be the conditional spin kernel of
$\mathcal SQ_f$ \eqref{eq:smoothing}. Then
\begin{equation}\tag{9}\label{eq:9}
 \mathbb E\,{\rm KL}\bigl(\pi_G\Vert\nu(\cdot\mid G^\circ)\bigr)
 \le O_\beta(n\sqrt\delta)+2n^{1-f/2}/\delta .
\end{equation}
With probability tending to one over the target/base pair,
\begin{equation}\tag{10}\label{eq:10}
 {\rm KL}\bigl(\pi_G\Vert\nu(\cdot\mid G^\circ)\bigr)\le n^{1-4d} .
\end{equation}
On the same event, simultaneously for every set
$A\subseteq\{-1,1\}^n$ with $\pi_G(A)\ge n^{-d}$,
\begin{equation}\tag{Cov}\label{eq:cov}
 \nu(A\mid G^\circ)\ge\exp(-n^{1-2d}).
\end{equation}
The set $A$ may be chosen after the target and base are realized.
\end{proposition}

\begin{proof}
Let $\overline\pi(\cdot\mid G^\circ)$ be the conditional spin law of
$\mathcal SP$, the conditional mixture of $\pi_G$ over the target that
produced the base $G^\circ$. Inserting this law into the logarithmic ratio
gives the exact decomposition
\[
 \begin{aligned}
 \mathbb E\,{\rm KL}\bigl(\pi_G\Vert\nu(\cdot\mid G^\circ)\bigr)
 &=\mathbb E\,{\rm KL}\bigl(\pi_G\Vert
                 \overline\pi(\cdot\mid G^\circ)\bigr)\\
 &\quad+{\rm KL}(\mathcal SP\Vert\mathcal SQ_f).
 \end{aligned}
\]
Both expectations are over the target/base pair $(G,G^\circ)$ of the
statement. The conditional mixture minimizes averaged divergence among
spin laws depending only on the base, so the first term on the right is
at most $\mathbb E\,{\rm KL}(\pi_G\Vert\pi_{G^\circ})$.

For any two Hamiltonians, the Gibbs divergence is bounded by twice $\beta$
times the supremum of their absolute energy difference. Here those
differences, for each fixed spin, are centered Gaussians of variance
$O(n\delta)$: the smoothed and unsmoothed disorders differ by coordinate
strength $O(\sqrt\delta)$ on $\sqrt n$-scale couplings. A union bound over
the $2^n$ spins, or an exponential moment argument, bounds the expected
supremum by $O(n\sqrt\delta)$. Combining this estimate with \eqref{eq:8}
and \eqref{eq:5} proves \eqref{eq:9}.

\emph{The power-of-$n$ event.} Since $4d<f/8$ and $4d<f/4$ (recall
$d=f/100$ and $f=1/100$), Markov's inequality applied to \eqref{eq:9} gives
\eqref{eq:10} with probability tending to one.

\emph{Coverage from the entropy.} On the single event \eqref{eq:10},
let $A$ be any set with $\pi_G(A)\ge n^{-d}$. For $s=\pi_G(A)$ and
$t=\nu(A\mid G^\circ)$, entropy contraction to the two-point partition
gives $s\log(1/t)\le{\rm KL}(\pi_G\Vert\nu)+\log2$. Hence
\[
 \log(1/t)\le n^d\bigl(n^{1-4d}+\log2\bigr)\le n^{1-2d}
\]
for sufficiently large $n$. The implication is deterministic once the
target and base are fixed, which proves the simultaneous assertion
\eqref{eq:cov}.
\end{proof}

Note that the coverage bound \eqref{eq:cov} deteriorates with
$d$, but this cost is well within the slack that the mixing argument
needs. The choice $b\ll d$ in \eqref{eq:exponents} is exactly what makes
the connecting-sequence exception
$\exp(-n^{1-10b})$ in Section~\ref{sec:connections} smaller than the
coverage probability $\exp(-n^{1-2d})$.

%======================================================================
\section{Connecting proposals across a cut}\label{sec:connections}
%======================================================================

This is the combinatorial heart of the proof. Everything so far has been
about a \emph{single} proposal. We now plant two proposals on either side
of a putative low-flow cut and force a contradiction with an elementary
geometric fact: a short sequence of spin flips that crosses a cut must
pass near the boundary.

\subsection{Setup and statement}

For distinct spins $x,y$, write $c_G(x,y)$ for the heat-bath jump rate and
\[
 Q_G^{\rm edge}(S,S^{\rm c})
 =\sum_{x\in S,\,y\notin S}\pi_G(x)\,c_G(x,y)
\]
for the stationary flow of the chain across the set $S$. Detailed balance
makes the edge weights symmetric, so this flow is the reversible measure
of the cut; it is also the quantity the mixing Lemma~\ref{lem:pruning}
of the next section uses.

\begin{proposition}[Balanced-cut flow]\label{prop:cuts}
With probability tending to one in the target disorder,
\begin{equation}\tag{11}\label{eq:11}
 Q_G^{\rm edge}(S,S^{\rm c})>B_{\min}:=\exp(-n^{1-b/20})
 \quad\text{for every }S\text{ with }
 \min(\pi_G(S),\pi_G(S^{\rm c}))\ge n^{-d}.
\end{equation}
\end{proposition}

\begin{proof}
We split the argument into (a) the geometry of a putative low-flow cut,
(b) the construction of a proposal sequence, and (c) two estimates that
make this sequence impossible.

\subsection{A low-flow cut has a small enlarged boundary}

For a sufficiently large fixed $C$, Gaussian quadratic-form tails on a
$1/4$-net give $\|W(G)\|\le C$ except with probability $O(e^{-cn})$. On this
event every one-spin energy difference is $O(\sqrt n)$, because flipping a
single spin changes $x^{\mathsf T}Wx/2$ by an $O(\|W\|\sqrt n)$ amount. The
heat-bath rate across any one-spin edge is therefore at least
$\exp(-O_\beta(\sqrt n))$.

If a cut has stationary flow at most $B_{\min}$, then its two-sided vertex
boundary
\[
 \partial S=\{x:\,d_H(x,S)=1\text{ and }d_H(x,S^{\rm c})=1\}
\]
has Gibbs mass at most $2B_{\min}\exp(O_\beta(\sqrt n))$, since each
boundary vertex controls at most $2n$ unit-rate crossings each carrying a
heat-bath acceptance probability at least $\exp(-O_\beta(\sqrt n))$.

Set $R_n=\lceil n^{1-b/4}\rceil$ and enlarge $\partial S$ by Hamming
distance $R_n$. For two spins at Hamming distance at most $R_n$ and with
$\|W(G)\|\le C$, the logarithmic Gibbs weight ratio is bounded by
$O_\beta(n^{1-b/8})$: the change in $\widehat H_G$ along any path of
$R_n$ flips is at most $C\sqrt n\cdot R_n/\sqrt n\cdot n^{1/2}=O_\beta(n^{1-b/8})$,
and a Hamming ball of radius $R_n$ has logarithmic cardinality
$O(n^{1-b/4}\log n)$. The enlarged boundary
$\mathcal D_R(G)$ therefore has target Gibbs mass at most
\begin{equation}\tag{12}\label{eq:12}
 \exp\bigl(-\tfrac12 n^{1-b/20}\bigr)
\end{equation}
for $n$ large, since $1-b/20<1-b/8$ and $b/20<b/4$.

Among cuts violating \eqref{eq:11}, select the first one in a fixed ordering
of the subsets of the cube whenever such a cut exists and $\|W(G)\|\le C$.
Let $\mathcal D(G)$ be its enlarged boundary, and set
$\mathcal D(G)=\varnothing$ if no such cut exists or the norm bound fails.
This is measurable because the cube has finitely many subsets. Let
$\mathcal E$ be the event that a witness cut exists, the target-norm bound
holds, and the coverage statement \eqref{eq:10} holds for the sampled
base $G^\circ$. The norm and coverage estimates reduce
\eqref{eq:11} to showing $\Pr(\mathcal E)=o(1)$.

\subsection{A sequence with independent fine endpoints}

The fine horizon $l=f$ and the coarse horizon $l=b$ serve distinct
purposes.

\begin{itemize}[leftmargin=*]
\item \emph{Fine horizon supplies coverage.} On $\mathcal E$, the coverage
  statement \eqref{eq:cov} gives each side of the cut fine-proposal
  probability at least $\exp(-n^{1-2d})$. Two conditionally independent
  fine endpoints therefore cross the cut with probability at least
  $\exp(-2n^{1-2d})$.
\item \emph{Coarse horizon supplies rare failures.} We need an unconditional
  bound on the failure probability of the connecting sequence that is
  \emph{smaller} than the endpoint-coverage probability. The fine-horizon
  exceptional-event bound of Proposition~\ref{prop:proposal} is
  $\exp(-n^{1-10f})$, which is too weak: $10f\gg d$. The coarse bound
  $\exp(-n^{1-10b})$ is strong enough, since $10b\ll d\ll2d$.
\end{itemize}

We therefore use \emph{fine} spins at the two endpoints for coverage, and
\emph{coarse} spins along a grid for the connecting sequence. The shared
path prefixes plus the magnetization martingale keep each fine endpoint
close to its coarse output.

\paragraph{Rotating the inputs.} Given the target $G$ and the base
$G^\circ$ from Section~\ref{sec:reverse}, introduce independent standard
Gaussian vectors $G'_1,G'_2$, independent of both, and set
\begin{equation}\label{eq:rotation}
 G(\theta)=\sqrt{1-\delta}\,G^\circ
          +\sqrt\delta\bigl(\cos\theta\,G'_1+\sin\theta\,G'_2\bigr),
 \qquad 0\le\theta\le\tfrac\pi2 .
\end{equation}
Use a deterministic equally spaced grid in $[0,\pi/2]$ that includes both
endpoints, with spacing $O(\exp(-n^{1/4}))$ and cardinality
$O(\exp(n^{1/4}))$. Rotate \emph{two independent collections of all
auxiliary Gaussian path inputs} by the same cosine-sine rule, so that small
changes in $\theta$ produce small changes in the auxiliary inputs.

\paragraph{Running the proposals.} At each grid point, run the coarse
proposal to horizon
\[
 V_b=h\lceil b\log n/h\rceil
\]
and draw its coarse spin. At each endpoint, also continue the path to
\[
 V_f=h\lceil f\log n/h\rceil
\]
and draw a fine spin. Coarse spin draws are \emph{not} used in any
continuation. All final spin draws may use fresh independent randomness.

\paragraph{Conditional structure.} The two fine endpoints are independent
conditional on $(G,G^\circ)$ and each has law $\nu(\cdot\mid G^\circ)$.
For each individual grid point, averaging over the disorder and
auxiliary inputs on the right side of \eqref{eq:rotation} gives the
appropriate proposal law; its primitive auxiliary collection is
independent of all target, base, and proposal matrix drivers. The
one-point estimates and their union bound require no independence across
grid points. The shared rotation supplies the nearby inputs needed for
continuity along the grid.

We now prove that, outside an event of probability at most
$\exp(-n^{1-d/2})$, the following two properties both hold:
\begin{enumerate}[label=(\alph*)]
\item every coarse spin avoids $\mathcal D(G)$;
\item the sequence consisting of the first fine spin, all coarse spins in
  grid order, and the last fine spin has consecutive Hamming distances at
  most $R_n$.
\end{enumerate}
The probability here is unconditional. Figure~\ref{fig:connection} shows
the deterministic obstruction that (a) and (b) together create, once we
sample two fine endpoints that provably lie on opposite sides of the cut.

\subsection{Avoiding a boundary selected from the target}

At a fixed grid point, the driver difference $G-G(\theta)$ has coordinate
variance $2\delta$, by \eqref{eq:rotation}. Gaussian tails and a union
bound over spins show that the supremum of absolute energy differences is
$O(n\sqrt\delta)$, except with probability $O(e^{-cn})$. On the complement,
Gibbs weight ratios between the two disorders are at most
$\exp(O_\beta(n\sqrt\delta))$.

Apply the likelihood estimate \eqref{eq:6} with coarse horizon $l=b$. Its
good event depends only on this proposal run. If
$q_{\rm good}(dx\mid g)$ is the corresponding output subprobability kernel,
disintegration against the Gaussian disorder marginal gives
\begin{equation}\label{eq:disintegration}
 q_{\rm good}(dx\mid g)\le\exp(n^{1-b/2})\,\pi_g(dx)
 \quad\text{for almost every }g .
\end{equation}
The primitive auxiliary inputs and the final spin draw for this run are
independent of all the matrix drivers. Thus, after fixing
$G(\theta)=g$ and adjoining $(G,G^\circ)$, this remains the \emph{conditional}
good-output kernel given the past. In particular, the inequality applies
to the random set $\mathcal D(G)$ once those matrices have been fixed.
The separate energy-change event is used only to compare Gibbs weights;
it is \emph{not} built into the proposal good event.

By \eqref{eq:12}, the resulting boundary probability on the complement of
the energy-change event is at most
\[
 \exp\bigl(n^{1-b/2}+O_\beta(n\sqrt\delta)-\tfrac12 n^{1-b/20}\bigr).
\]
Add the proposal exceptional probability $\exp(-n^{1-10b})$ and the
energy-change exception. Since $\sqrt\delta=n^{-f/8}$ and $f=1/100$, the
exponent $1-b/20$ dominates both $1-b/2$ and $O_\beta(n\sqrt\delta)$ for
large $n$, so this proves the required one-point avoidance bound.
Correlations with auxiliary inputs at other grid points do not change this
calculation, because the good event depends only on the inputs of the run
at that point.

\subsection{Continuity of coarse magnetizations}

We now control the increments along the grid. At any grid point,
Proposition~\ref{prop:proposal} puts the Gram matrix of the coarse $T_k$
within $n^{-b}$ of the identity except with probability
$\exp(-n^{1-10b})$. On this event all $|T_k|_n\le2$, and each
Gram--Schmidt residual has norm at least $1/2$, so we do \emph{not} touch
the zero-residual fallback of Section~\ref{sec:proposal}. The reciprocals
$1/s_k$ are bounded by a fixed power of $n$ on the deterministic coarse
horizon, by \eqref{eq:1}.

For neighboring grid points satisfying these Gram conditions, we claim
\begin{equation}\tag{13}\label{eq:13}
 |M_\theta(V_b)-M_{\theta'}(V_b)|_n
 \le(n^{C_1})^{K_b+1}\,|\theta-\theta'|,
 \qquad K_b=V_b/h,
\end{equation}
provided the primitive inputs have polynomially bounded norms. The
constant $C_1$ is independent of the grid and of $n$.

\paragraph{Input bounds.} Bound the operator norms of
$W(G^\circ),W(G'_1),W(G'_2)$ and the normalized norms of all completion
vectors $z_k$ in the two input collections. For their Brownian and bridge
inputs, bound the supremum norms of cumulative integrals against the
deterministic coefficients $\rho$ and $\sqrt{1-\rho^2}$. On a filled
interval include only the centered bridge in this primitive bound; its
endpoint is handled separately. All these norms are at most $n^3$ outside
an event of probability $O(e^{-cn})$. Gaussian tails give the matrix and
vector estimates. For the path integrals, write a bridge as Brownian
motion minus its linearly interpolated endpoint and use the Gaussian
martingale maximal bound for a bounded deterministic integrand. Rotation
\eqref{eq:rotation} makes the differences of the primitive inputs at two
angles at most a polynomial factor times $|\theta-\theta'|$.

\paragraph{Interval induction.} At a Gram--Schmidt step, the difference of
the two projection operators is bounded by twice the sum of preceding
direction differences in $|\cdot|_n$. Normalizing residuals of norm at
least $1/2$ costs only a fixed factor. Using $1/s_k$, the new direction
difference is controlled by earlier magnetization and direction
differences at polynomial cost. The same is true of the new $g_k$, by its
matrix-query and completion formula \eqref{eq:gk}. The cumulative driving
signals from \eqref{eq:4} differ by the primitive integral differences plus
the endpoint difference multiplied by a deterministic factor at most
$\sqrt h$. Finally, the scalar integral equation \eqref{eq:Y} and its
spatially Lipschitz drift control the differences in $Y$ and $M$ over this
interval at constant cost, by Gronwall's inequality. Starting with the
entirely auxiliary first interval and taking successive maxima of these
differences proves \eqref{eq:13} after increasing $C_1$ if necessary.

Only the Gram conditions at the two endpoints of each grid step were used.
Since $K_b=O(n^{1/16}\log n)$ and the mesh spacing $O(\exp(-n^{1/4}))$ is
exponentially smaller, \eqref{eq:13} makes every consecutive coarse
magnetization difference negligible relative to $n^{-b/3}$.

\subsection{From magnetizations to spins}

For either a coarse spin or a fine endpoint spin compared with its own
coarse magnetization, the normalized squared distance has mean
\[
 1-\mathbb E m_{V_b}^2=p(V_b)\le C_\beta n^{-b/2},
\]
by $p(V_b)\le C_\beta e^{-V_b}$ and $V_b=b\log n$. For a fine spin this
follows from the martingale conditional mean through the continuation.
Under the unconditioned single-run law, each squared distance is an average
of bounded i.i.d. coordinate variables; consequently it is at most
$n^{-b/3}$ except with probability $O(\exp(-n^{1-b}))$. The triangle
inequality in $|\cdot|_n$, along with the negligible magnetization
increments above, then gives Hamming step sizes at most $R_n$ for large $n$,
since $n^{-b/3}\ll R_n^2/n=n^{1-b/2}/n=n^{-b/2}$.

\paragraph{Union bound.} We now union bound all one-point and
consecutive-point exceptions for the two desired properties, including the
primitive-input event. The grid costs only $\exp(O(n^{1/4}))$ points, and
$10b<b/2<d/2$: the boundary exponent $1-b/20$ also exceeds $1-d/2$, since
$b<d$. The total failure probability is at most $\exp(-n^{1-d/2})$ for
sufficiently large $n$.

\subsection{The crossing contradiction}

On $\mathcal E$, the coverage statement \eqref{eq:cov} gives each side of
the chosen cut fine-endpoint probability at least $\exp(-n^{1-2d})$.
Conditional independence therefore puts the two fine endpoints on opposite
sides of the cut with probability at least $\exp(-2n^{1-2d})$.

But if both sequence properties (a) and (b) hold and the fine endpoints
lie on opposite sides, then some consecutive pair in the sequence must
cross the cut. Each such pair contains a coarse spin. A shortest one-spin
path between the pair meets $\partial S$ and has length at most $R_n$,
placing that coarse spin in $\mathcal D(G)$. This contradicts property (a).

Consequently
\begin{equation}\label{eq:contradiction}
 \Pr(\mathcal E)\,\exp(-2n^{1-2d})\le\exp(-n^{1-d/2}) .
\end{equation}
Since $d/2<2d$, this implies $\Pr(\mathcal E)=o(1)$ and proves
\eqref{eq:11}. The auxiliary diagonal and smoothing base are used
only in this proof; the resulting flow bound concerns the original heat
bath.
\end{proof}

%----------------------------------------------------------------------
\begin{figure}[!htbp]
\centering
\begin{tikzpicture}[x=1cm,y=1cm,font=\small,
  coarse/.style={circle,draw=blue!55!black,fill=white,line width=.8pt,
    minimum size=5.5mm,inner sep=0pt},
  fine/.style={rectangle,draw=black!80,fill=black!12,line width=.8pt,
    minimum size=5.5mm,inner sep=0pt},
  forced/.style={coarse,draw=red!65!black,fill=red!8,line width=1.2pt},
  boundary/.style={circle,draw=red!65!black,fill=red!8,line width=.8pt,
    minimum size=3mm,inner sep=0pt}]
  \fill[black!3] (-.05,-.75) rectangle (7.3,.9);
  \fill[blue!3] (7.3,-.75) rectangle (13.5,.9);
  \draw[densely dotted,black!55] (7.3,-.75) -- (7.3,.9);
  \node at (3.6,.63) {$S$};
  \node at (10.4,.63) {$S^{\mathrm c}$};
  \node[fine] (leftfine) at (.65,0) {};
  \node[coarse] (coarsezero) at (2.5,0) {};
  \node[coarse] (coarseone) at (4.4,0) {};
  \node[forced] (crossleft) at (6.3,0) {};
  \node[forced] (crossright) at (8.3,0) {};
  \node[coarse] (coarselast) at (10.3,0) {};
  \node[fine] (rightfine) at (12.8,0) {};
  \draw[black!65] (leftfine) -- (coarsezero) -- (coarseone) -- (crossleft);
  \draw[black!65] (crossright) -- (coarselast) -- (rightfine);
  \draw[red!65!black,line width=1.1pt] (crossleft) -- (crossright);
  \node[below=1mm] at (leftfine.south) {$x_{\rm f}^{(0)}$};
  \node[below=1mm] at (rightfine.south) {$x_{\rm f}^{(1)}$};
  \node[below=1mm] at (crossleft.south) {$u$};
  \node[below=1mm] at (crossright.south) {$v$};
  \node[fill=white,inner sep=1.5pt] at (7.3,.48) {$d_H(u,v)\le R_n$};
  \node at (6.9,-1.15)
    {Every step has a coarse endpoint; coarse outputs avoid $\mathcal D(G)$.};
  \node at (7.3,-1.9)
    {Expand the crossing step into single-spin flips: length $\ell\le R_n$.};
  \draw[densely dotted,black!55] (7.3,-2.25) -- (7.3,-3.35);
  \node[forced] (pathleft) at (3.8,-2.85) {};
  \node[boundary] (boundaryleft) at (6.2,-2.85) {};
  \node[boundary] (boundaryright) at (8.4,-2.85) {};
  \node[forced] (pathright) at (10.8,-2.85) {};
  \draw[black!65] (pathleft) -- (boundaryleft);
  \draw[black!65] (boundaryright) -- (pathright);
  \draw[red!65!black,line width=1.1pt] (boundaryleft) -- (boundaryright);
  \node[above=2mm,red!65!black] at (7.3,-2.85) {boundary edge};
  \node[below=1mm] at (pathleft.south) {$u=y_0$};
  \node[below=1mm] at (boundaryleft.south) {$y_t$};
  \node[below=1mm] at (boundaryright.south) {$y_{t+1}$};
  \node[below=1mm] at (pathright.south) {$v=y_\ell$};
  \node at (2.6,-2.85) {$S$};
  \node at (12,-2.85) {$S^{\mathrm c}$};
  \node[red!65!black,align=center] at (7.3,-3.8)
    {$d_H(u,\partial S),\,d_H(v,\partial S)\le\ell\le R_n
     \;\Longrightarrow\; u,v\in\mathcal D(G)$.};
\end{tikzpicture}
\caption{The boundary obstruction for the finite sequence of proposals.
Squares are fine endpoints, circles are coarse outputs. Consecutive
configurations in the sequence are at Hamming distance at most $R_n$.
If the two fine endpoints lie on opposite sides of a cut $S$, some
consecutive pair $(u,v)$ in the sequence crosses the cut; every pair
contains a coarse endpoint. Any shortest path of single-spin flips joining
$u$ to $v$ meets the two-sided boundary $\partial S$, and its length is at
most $R_n$, so $u$ and $v$ lie in the enlarged boundary $\mathcal D(G)$
used in Section~\ref{sec:connections}. This contradicts property (a).
The drawing is schematic: grid outputs are very correlated, and lines do
not represent continuous spin trajectories.}
\label{fig:connection}
\end{figure}
%----------------------------------------------------------------------

%======================================================================
\section{From balanced flows to typical-state mixing}\label{sec:mixing}
%======================================================================

The flow estimate \eqref{eq:11} is available only when \emph{both} sides
of a cut have appreciable Gibbs mass. We now convert exactly this
information into a mixing statement about typical fixed starting states.
The finite-state argument below has three steps:

\begin{enumerate}[label=\arabic*.,leftmargin=*]
\item Find a set $C$ of large stationary mass with good internal expansion,
  by repeatedly pruning away subsets that do not expand.
\item On $C$, obtain a Poincar\'e inequality from the coarea proof of the
  reversible Cheeger inequality.
\item Use entropy dissipation of the \emph{full} chain plus stationarity to
  bound the $\pi$-average of the fixed-start total variation at time $T$,
  and finish with Markov's inequality over the starting state.
\end{enumerate}

Crucially, the argument never asks a trajectory to stay inside $C$; that
is exactly what lets rare slow starting states be excluded later rather
than obstructing the bound.

\subsection{The pruning lemma}

\begin{lemma}[Pruning and averaged mixing]\label{lem:pruning}
Let $\Omega$ be a finite set, $\pi$ a strictly positive probability on
$\Omega$, and $P_t$ a continuous-time Markov semigroup reversible with
respect to $\pi$ with jump rates $c(x,y)$. Assume that for some $R>0$
\[
 \sum_{y\ne x}c(x,y)\le R\qquad(x\in\Omega).
\]
Let $0<\varepsilon<1/3$ and $B>0$. Suppose that
\[
 Q(S,S^{\rm c}):=\sum_{x\in S,\,y\notin S}\pi(x)c(x,y)>B
 \quad\text{whenever }\varepsilon\le\pi(S)\le1-\varepsilon.
\]
Then for every $T>0$,
\begin{equation}\tag{14}\label{eq:averaged-mixing}
 \sum_{x\in\Omega}\pi(x)\bigl\|P_T(x,\cdot)-\pi\bigr\|_{\rm TV}
 \le\frac{\sqrt{2R\,H(\pi)}}{B\sqrt T}+2\varepsilon,
 \qquad H(\pi)=-\sum_x\pi(x)\log\pi(x).
\end{equation}
\end{lemma}

\begin{proof}
Put $q(x,y)=\pi(x)c(x,y)=q(y,x)$, and use the unordered-edge Dirichlet form
\[
 \mathfrak D(u)=\sum_{\{x,y\}}q(x,y)\bigl(u(x)-u(y)\bigr)^2.
\]
Only distinct vertices occur, and every unordered pair is counted once.

\paragraph{Step 1: removing sets that do not expand.} Start with
$C=\Omega$. Whenever a nonempty $U\subset C$ satisfies
\[
 \pi(U)\le\pi(C)/2,\qquad Q(U,C\setminus U)<B\pi(U),
\]
remove $U$ from $C$. This terminates because each removal eliminates at
least one vertex. If $A$ denotes all vertices removed so far, then every
edge between $A$ and its current complement was counted when its first
endpoint was removed, so whenever $A\ne\varnothing$,
\[
 Q(A,\Omega\setminus A)<B\pi(A).
\]
Suppose the removed mass first reached $\varepsilon$. Its preceding mass
$a$ was less than $\varepsilon$, and the newly removed set has mass at
most $(1-a)/2$. The new total is therefore at most
$(1+a)/2<(1+\varepsilon)/2<1-\varepsilon$. This contradicts the
balanced-cut hypothesis, since $B\pi(A)\le B$. Consequently the terminal
set satisfies $\pi(C)>1-\varepsilon$ and
\begin{equation}\label{eq:internal-expansion}
 Q(U,C\setminus U)\ge B\pi(U)
 \quad\text{for every }U\subset C\text{ with }\pi(U)\le\pi(C)/2 .
\end{equation}

\paragraph{Step 2: a Poincar\'e inequality on the retained set.} Use the
coarea proof of the reversible Cheeger inequality
\cite[Theorem~3.5]{LawlerSokal1988}, keeping the original unnormalized
weights on $C$. The resulting estimate is
\begin{equation}\tag{15}\label{eq:14}
 \sum_{y\in C}\pi(y)\bigl(u(y)-\bar u_C\bigr)^2
 \le\frac{2R}{B^2}\,\mathfrak D(u),
 \qquad \bar u_C=\frac1{\pi(C)}\sum_{y\in C}\pi(y)u(y).
\end{equation}
To prove it, choose a weighted median $m$ of $u$ on $C$. Each of
$w=(u-m)_+$ and $w=(m-u)_+$ has support of mass at most $\pi(C)/2$.
Integrating \eqref{eq:internal-expansion} over the level sets of $w^2$
gives
\[
 B\sum_C\pi w^2
 \le\sum_{\{x,y\}\subset C}q(x,y)\bigl|w(x)^2-w(y)^2\bigr|.
\]
By Cauchy--Schwarz this is at most
\[
 \left(\sum_{\{x,y\}\subset C}q(x,y)(w(x)-w(y))^2\right)^{1/2}
 \left(2R\sum_C\pi w^2\right)^{1/2},
\]
since $(w(x)+w(y))^2\le2(w(x)^2+w(y)^2)$ and the total outgoing rate is at
most $R$. If $\sum_C\pi w^2$ vanishes the estimate is immediate; otherwise
divide and square. The sum of the energies of the positive and negative
parts is at most $\mathfrak D(u)$. The weighted mean minimizes squared
error, proving \eqref{eq:14}.

\paragraph{Step 3: entropy dissipation for the full chain.} For a fixed
starting state $x$, set $f_t^x(y)=P_t(x,y)/\pi(y)$. Reversibility together
with $(a-b)(\log a-\log b)\ge4(\sqrt a-\sqrt b)^2$ for $a,b>0$ gives the
entropy-dissipation estimate
\cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}
\begin{equation}\tag{16}\label{eq:15}
 \int_0^T\sum_x\pi(x)\,\mathfrak D\bigl(\sqrt{f_t^x}\bigr)\,dt
 \le\tfrac14 H(\pi).
\end{equation}
Indeed, the derivative of $\sum_y\pi(y)f_t^x(y)\log f_t^x(y)$ is
\[
 -\sum_{\{y,z\}}q(y,z)
  \bigl(f_t^x(y)-f_t^x(z)\bigr)\bigl(\log f_t^x(y)-\log f_t^x(z)\bigr).
\]
The initial entropy is $\log(1/\pi(x))$ and the final entropy is
nonnegative. Averaging in $x\sim\pi$ and integrating proves \eqref{eq:15}.
Vanishing densities and reducible chains cause no problem: start with
$(1-\eta)f_0^x+\eta$ and pass to $\eta\downarrow0$, or calculate on
communicating classes.

\paragraph{Step 4: averaging fixed-state distances.} Combining \eqref{eq:14}
and \eqref{eq:15} supplies some $t\in(0,T]$ with
\[
 \sum_x\pi(x)r_x^2\le\frac{R\,H(\pi)}{2TB^2},
 \quad
 r_x^2=\sum_C\pi(y)\bigl(\sqrt{f_t^x(y)}-a_x\bigr)^2,
 \quad
 a_x=\frac1{\pi(C)}\sum_C\pi(y)\sqrt{f_t^x(y)} .
\]
Cauchy--Schwarz and $a_x^2\pi(C)\le\sum_C\pi f_t^x\le1$ imply
\[
 \sum_C\pi\bigl|f_t^x-a_x^2\bigr|\le2r_x .
\]
Also, total normalization gives
$\bigl|\sum_C\pi(f_t^x-1)\bigr|\le\sum_{C^{\rm c}}\pi(f_t^x+1)$.
Comparing $f_t^x$ first with $a_x^2$ and then with $1$ on $C$, and adding
the complement, yields
\[
 \sum_\Omega\pi|f_t^x-1|
 \le4r_x+2\sum_{C^{\rm c}}\pi(f_t^x+1).
\]
The last sum before its factor two has average $2\pi(C^{\rm c})$ over
$x\sim\pi$, because stationarity gives $\sum_x\pi(x)f_t^x(y)=1$. Dividing
by two for total variation and applying Cauchy--Schwarz in $x$ proves the
upper bound at time $t$. Contraction under $P_{T-t}$ gives the same bound
at the prescribed time $T$, establishing \eqref{eq:averaged-mixing}.
\end{proof}

\subsection{Proof of the main theorem}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
On the disorder event of Proposition~\ref{prop:cuts}, apply
Lemma~\ref{lem:pruning} to the SK chain with
\[
 \varepsilon=n^{-d},\qquad B=\exp\bigl(-n^{1-b/20}\bigr),\qquad R=n .
\]
The last choice is valid because there are exactly $n$ rate-one update
clocks, so the total jump rate at any vertex is $n$. Also
$H(\pi_G)\le n\log2$, since the state space has $2^n$ elements. Hence
\[
 \sum_x\pi_G(x)\bigl\|P_T^G(x,\cdot)-\pi_G\bigr\|_{\rm TV}
 \le\frac{\sqrt{2\log2}\;n}{B\sqrt T}+2n^{-d}.
\]
Take
\[
 T=\exp\bigl(n^{1-b/40}\bigr).
\]
Then the first term tends to zero, because
\[
 \log\frac{n}{B\sqrt T}
 =\log n+n^{1-b/20}-\tfrac12 n^{1-b/40}\longrightarrow-\infty .
\]

The flow event \eqref{eq:11} itself has disorder probability tending to
one. Markov's inequality therefore shows that the Gibbs mass of fixed
states whose distance at time $T$ exceeds $1/4$ tends to zero in disorder
probability. The added diagonal changes neither this Gibbs law nor the
transition rates, so the same statement holds for the model $H^J_n$ in
\eqref{eq:H}. This proves Theorem~\ref{thm:main} with
\[
 c_\beta=\frac{b}{40}=\frac1{40000000}.
\]
All threshold dimensions may depend on the fixed $\beta>1$.
\end{proof}

\subsection{Reading the final exponents}

For orientation, here is the chain of inequalities that governs the
constants, all in the ``$1-\text{exponent}$'' scale:
\[
 10b\ \ll\ b/4\ \ll\ b/2\ \ll\ b/20\ \ll\ d
 =100b\ \ll\ 2d\ll f\ll 1 .
\]
The two competing probabilities in Section~\ref{sec:connections} were the
coverage probability $\exp(-2n^{1-2d})$ and the sequence failure
probability $\exp(-n^{1-d/2})$: the ratio of their exponents is $2d$ versus
$d/2$, and $d/2\ll d<2d$ gives the gap. The mixing time $T=\exp(n^{1-b/40})$
sits below both because $b/40\ll b/20$, so the exponential
$\exp(-n^{1-b/20})$ flow bound has enough time to accumulate. Nothing here
is optimized; the only requirement was a positive $b$, and the constants
were chosen in a strict hierarchy to keep every exponent well separated.

%======================================================================
% References
%======================================================================
\begin{thebibliography}{99}

\bibitem{AC2015}
A.~Auffinger and W.-K.~Chen,
\newblock On properties of Parisi measures,
\newblock \emph{Probab.\ Theory Related Fields} \textbf{161} (2015),
817--850.
\newblock \href{https://doi.org/10.1007/s00440-014-0563-y}{doi:10.1007/s00440-014-0563-y};
\href{https://arxiv.org/abs/1303.3573v1}{arXiv:1303.3573v1}.

\bibitem{BLO2026}
M.~Boban, A.~Li and S.~Oveis Gharan,
\newblock Rank-1-perturbed trickledown theorems: mixing time of Glauber
dynamics for the Sherrington--Kirkpatrick model up to
$\beta\le\tfrac12+\varepsilon$,
\newblock preprint (2026),
\href{https://arxiv.org/abs/2609.13138v1}{arXiv:2609.13138v1}.

\bibitem{BKM2005}
V.~I. Bogachev, A.~V. Kolesnikov and K.~V. Medvedev,
\newblock Triangular transformations of measures,
\newblock \emph{Sbornik: Math.} \textbf{196} (2005), no.~3, 309--335.
\newblock \href{https://doi.org/10.1070/SM2005v196n03ABEH000882}{doi:10.1070/SM2005v196n03ABEH000882}.

\bibitem{Bolthausen2014}
E.~Bolthausen,
\newblock An iterative construction of solutions of the TAP equations for
the Sherrington--Kirkpatrick model,
\newblock \emph{Comm.\ Math.\ Phys.} \textbf{325} (2014), 333--366.
\newblock \href{https://doi.org/10.1007/s00220-013-1862-3}{doi:10.1007/s00220-013-1862-3};
\href{https://arxiv.org/abs/1201.2891}{arXiv:1201.2891}.

\bibitem{BLM2013}
S.~Boucheron, G.~Lugosi and P.~Massart,
\newblock \emph{Concentration Inequalities: A Nonasymptotic Theory of
Independence}, Oxford University Press, 2013.

\bibitem{Chen2017}
W.-K.~Chen,
\newblock Variational representations for the Parisi functional and the
two-dimensional Guerra--Talagrand bound,
\newblock \emph{Ann.\ Probab.} \textbf{45} (2017), no.~6A, 3929--3966.
\newblock \href{https://doi.org/10.1214/16-AOP1154}{doi:10.1214/16-AOP1154};
\href{https://arxiv.org/abs/1501.06635v2}{arXiv:1501.06635v2}.

\bibitem{DiaconisSaloffCoste1996}
P.~Diaconis and L.~Saloff-Coste,
\newblock Logarithmic Sobolev inequalities for finite Markov chains,
\newblock \emph{Ann.\ Appl.\ Probab.} \textbf{6} (1996), no.~3, 695--750.
\newblock \href{https://doi.org/10.1214/aoap/1034968224}{doi:10.1214/aoap/1034968224}.

\bibitem{EKZ2022}
R.~Eldan, F.~Koehler and O.~Zeitouni,
\newblock A spectral condition for spectral gap: fast mixing in
high-temperature Ising models,
\newblock \emph{Probab.\ Theory Related Fields} \textbf{182} (2022),
nos.~3--4, 1035--1051.
\newblock \href{https://doi.org/10.1007/s00440-021-01085-x}{doi:10.1007/s00440-021-01085-x};
\href{https://arxiv.org/abs/2007.08200v1}{arXiv:2007.08200v1}.

\bibitem{Guerra2003}
F.~Guerra,
\newblock Broken replica symmetry bounds in the mean field spin glass
model,
\newblock \emph{Comm.\ Math.\ Phys.} \textbf{233} (2003), 1--12.
\newblock \href{https://doi.org/10.1007/s00220-002-0773-5}{doi:10.1007/s00220-002-0773-5};
\href{https://arxiv.org/abs/cond-mat/0205123v1}{arXiv:cond-mat/0205123v1}.

\bibitem{JT2017}
A.~Jagannath and I.~Tobasco,
\newblock Some properties of the phase diagram for mixed $p$-spin glasses,
\newblock \emph{Probab.\ Theory Related Fields} \textbf{167} (2017),
615--672.
\newblock \href{https://doi.org/10.1007/s00440-015-0691-z}{doi:10.1007/s00440-015-0691-z};
\href{https://arxiv.org/abs/1504.02731v2}{arXiv:1504.02731v2}.

\bibitem{LawlerSokal1988}
G.~F. Lawler and A.~D. Sokal,
\newblock Bounds on the $L^2$ spectrum for Markov chains and Markov
processes: a generalization of Cheeger's inequality,
\newblock \emph{Trans.\ Amer.\ Math.\ Soc.} \textbf{309} (1988), no.~2,
557--580.
\newblock \href{https://doi.org/10.1090/S0002-9947-1988-0930082-9}{doi:10.1090/S0002-9947-1988-0930082-9}.

\bibitem{Lopatto2026}
P.~Lopatto,
\newblock Full replica symmetry breaking in the Sherrington--Kirkpatrick
model,
\newblock preprint (2026),
\href{https://arxiv.org/abs/2607.11756v3}{arXiv:2607.11756v3}.

\bibitem{LugosiNeu2022}
G.~Lugosi and G.~Neu,
\newblock Generalization bounds via convex analysis,
\newblock \emph{Proc.\ Mach.\ Learn.\ Res.} \textbf{178} (2022), 3524--3546.
\newblock \href{https://proceedings.mlr.press/v178/lugosi22a.html}{Proceedings article}.

\bibitem{Montanari2021}
A.~Montanari,
\newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
\newblock \emph{SIAM J.\ Comput.} \textbf{54} (2025), no.~4,
FOCS19-1--FOCS19-38 (online 2021).
\newblock \href{https://doi.org/10.1137/20M132016X}{doi:10.1137/20M132016X};
\href{https://arxiv.org/abs/1812.10897v2}{arXiv:1812.10897v2}.

\bibitem{OpenAISKBarriers2026}
OpenAI,
\newblock Stretched-exponential barriers for typical SK initial states,
\newblock
\href{https://github.com/openai/math/blob/main/preprints/Stretched-exponential-barriers-for-typical-SK-initial-states-September-24-2026/paper.pdf}{OpenAI Math Release preprint}, 2026.

\bibitem{Sellke2025}
M.~Sellke,
\newblock Exponentially slow mixing of the low temperature SK model,
\newblock preprint (2025),
\href{https://arxiv.org/abs/2511.22621v2}{arXiv:2511.22621v2}.

\bibitem{SK1975}
D.~Sherrington and S.~Kirkpatrick,
\newblock Solvable model of a spin-glass,
\newblock \emph{Phys.\ Rev.\ Lett.} \textbf{35} (1975), no.~26, 1792--1796.
\newblock \href{https://doi.org/10.1103/PhysRevLett.35.1792}{doi:10.1103/PhysRevLett.35.1792}.

\bibitem{Wang2026}
S.~Wang,
\newblock Optimal mixing of Glauber dynamics for the
Sherrington--Kirkpatrick model at $\beta<1/2$,
\newblock preprint (2026),
\href{https://arxiv.org/abs/2608.22159v2}{arXiv:2608.22159v2}.

\bibitem{Zhou2026}
Y.~Zhou,
\newblock Existence of full replica symmetry breaking for the
Sherrington--Kirkpatrick model at low temperature,
\newblock \emph{Comm.\ Pure Appl.\ Math.} \textbf{79} (2026), 1746--1770.
\newblock \href{https://doi.org/10.1002/cpa.70038}{doi:10.1002/cpa.70038}.

\end{thebibliography}

\end{document}