diff 3ff9228..b34550f low_temp_sk_glauber_typical_v2.txt
diff --git a/low_temp_sk_glauber_typical_v2.txt b/low_temp_sk_glauber_typical_v2.txt
index 98a9a3e..b2148e0 100644
--- a/low_temp_sk_glauber_typical_v2.txt
+++ b/low_temp_sk_glauber_typical_v2.txt
@@ -2,28 +2,28 @@
% 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}
-
-\begin{document}
+
+
+
+
+
+# A typical-start upper bound for low-temperature\\Sherrington--Kirkpatrick Glauber dynamics
+
+
\maketitle
-\begin{abstract}
+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
@@ -36,15 +36,15 @@ $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}
+# Introduction
%======================================================================
-\subsection{The question in plain terms}
+## 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.
@@ -54,46 +54,46 @@ 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
+At high temperature the chain mixes quickly, in polynomial time
+from every start. At low temperature ($\beta>1$ in the
zero-field SK model) the landscape is glassy: there are deep valleys
separated by high barriers, and a configuration placed in the wrong
-valley can take a very long time to escape. Sellke \cite{Sellke2025}
-shows the \emph{worst} starting configuration can force an exponential
+valley can take a very long time to escape. Sellke [cite]
+shows the worst starting configuration can force an exponential
lower bound on the mixing time.
That leaves a sharper question. An adversarial start is unrealistic for
a sampler run on a freshly drawn instance. What happens if we start the
-chain from a \emph{typical} equilibrium configuration, i.e. from one
+chain from a 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}$,
+[label=(\roman*)]
+\item The start is random and then held fixed. We first draw the
+ disorder $J$, then 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
+\item 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}
+
+## 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}
+ =\frac{\exp(\beta H^J_n(\sigma))}{Z^J_{n,\beta}},
+
where $Z^J_{n,\beta}$ is the normalizing constant. There is no external
field. The local field at site $i$ is
\[
@@ -101,40 +101,40 @@ field. The local field at site $i$ is
\]
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}
+
+ \mathbb P\{new spin=s\mid\sigma\}
+ =\frac{\exp(\beta s\,h_i(\sigma))}
+ {2cosh(\beta h_i(\sigma))} .
+
The update may leave $\sigma_i$ unchanged. Let
$P_t^{J,\beta}(\sigma,\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}}
+ \bigl\|P_t^{J,\beta}(\sigma,\cdot)-\pi^J_{n,\beta}\bigr\|_{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,
+the disorder and one Gibbs configuration,
$\mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}
=\mathbb E_J\,\pi^J_{n,\beta}$.
-\subsection{Main results}
+## Main results
-\begin{theorem}[Mixing from a typical Gibbs start]\label{thm:main}
+[Mixing from a typical Gibbs start]
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).
+ T^J_{n,\beta}(\sigma_0)\le\exp(n^{1-c_\beta})\Bigr\}
+ → 1
+ \qquad (n\to∞).
\]
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
@@ -142,72 +142,72 @@ $\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
+The companion lower bound in [cite] gives a matching
+stretched-exponential barrier. Combined with Theorem~thm:main it
produces a two-sided statement.
-\begin{corollary}[Two-sided typical-start bound]\label{cor:two-sided}
+[Two-sided typical-start bound]
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 .
+ \exp(n^{1/10000})<T^J_{n,\beta}(\sigma_0)
+ \le\exp(n^{1-1/40000000})\Bigr\}
+ → 1 .
\]
-\end{corollary}
-\begin{proof}
+
+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
+$\|P^{J,\beta}_{\exp(n^{1/10000})}(\sigma_0,\cdot)-\pi^J_{n,\beta}\|_{TV}>1/4$
+for $\sigma_0\sim\pi^J_{n,\beta}$. By (eq:T) and continuity of the
finite-state semigroup this forces the strict lower bound
$T^J_{n,\beta}(\sigma_0)>\exp(n^{1/10000})$. The upper bound is
-Theorem~\ref{thm:main}. Both events use the same joint law of
+Theorem~thm:main. Both events use the same joint law of
$(J,\sigma_0)$ and the same rate-one clocks, so their intersection has
probability tending to one.
-\end{proof}
-\subsection{How the proof works}
+
+## 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
+[label=Stage \arabic*.]
+\item 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}.
+ normalization of this paper. See Section~sec:scalar.
-\item \textbf{The long diffusion and its entropy--energy identity.} We
+\item 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
+ equation~(eq:scalar-balance), that balances the information
acquired by matrix queries against the energy gained. This is the engine
- of the entropy bound. See Section~\ref{sec:scalar}.
+ of the entropy bound. See Section~sec:scalar.
-\item \textbf{The Gaussian-query proposal.} We build a random spin by
+\item 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}.
+ Section~sec:proposal.
-\item \textbf{Reversing the entropy: coverage.} Forward entropy alone says
+\item 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}.
+ smoothing base. See Section~sec:reverse.
-\item \textbf{Balancing flows and mixing.} Two independent proposals joined
- across a cut contradict the avoidance of a small boundary \emph{unless}
+\item Balancing flows and mixing. Two independent proposals joined
+ across a cut contradict the avoidance of a small boundary unless
every cut of appreciable Gibbs mass carries stationary flow at least
$B_{\min}=\exp(-n^{1-b/20})$. The geometry is elementary: a short
sequence of spins crossing a cut must contain a spin close to the
@@ -216,29 +216,29 @@ to its section.
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}
+ starting states. See Sections~sec:connections and~sec:mixing.
-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}
+Theorems~thm:main and cor:two-sided are assembled from these
+stages at the end of Section~sec:mixing.
-\emph{High-temperature, worst-start.} Eldan, Koehler and Zeitouni
+## Relation to prior work
+
+High-temperature, worst-start. Eldan, Koehler and Zeitouni
\cite[Section~6]{EKZ2022} proved polynomial worst-start mixing for
$\beta<1/4$. Wang \cite[Theorem~1.1]{Wang2026} established optimal-order
Glauber mixing for every fixed $\beta<1/2$, and Boban, Li and Oveis
Gharan \cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
-mixing in zero field to $\beta<1/2+\varepsilon_0$ for some absolute
-$\varepsilon_0>0$.
+mixing in zero field to $\beta<1/2+ε_0$ for some absolute
+$ε_0>0$.
-\emph{Low-temperature, worst-start.} Sellke
+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
+after Gibbs-distributed start. Theorem~thm:main resolves the latter
throughout the fixed low-temperature phase.
-\emph{Equilibrium Parisi theory.} The stationarity conditions that drive
+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
@@ -249,7 +249,7 @@ 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
+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,
@@ -261,34 +261,34 @@ 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}
+# Notation and Gaussian completion
%======================================================================
Fix a finite $\beta>1$. Constants may depend on this fixed parameter;
when that dependence matters we write $C_\beta$ or $O_\beta(\cdot)$. All
logarithms are natural.
-\paragraph{Distances and inner products.} For probability measures
+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 .
+ < v,w>_n=\frac1n\sum_i v_i w_i,
+ \qquad |v|_n^2=< v,v>_n .
\]
The symbols $\|v\|$ and $\|A\|$ denote the Euclidean norm of a vector and
the operator norm of a matrix.
-\paragraph{The GOE completion.} A heat-bath update at site $i$ never sees
-$J_{ii}$. We \emph{complete} the interaction matrix by adding independent
+The GOE completion.: A heat-bath update at site $i$ never sees
+$J_{ii}$. We complete the interaction matrix by adding independent
diagonal entries of law $N(0,2/n)$: define a symmetric matrix $W=W(G)$
whose entries above the diagonal are $W_{ij}=J_{ij}/\sqrt n$ and whose
diagonal entries are independent $N(0,2/n)$. Write $G$ for the vector of
independent standard Gaussian drivers of all these entries and
$\gamma$ for its law. Since $x_i^2=1$ for every spin,
\[
- \tfrac12\,x^{\mathsf T}\operatorname{diag}(W)\,x
+ \tfrac12\,x^{\mathsf T}diag(W)\,x
=\tfrac12\sum_i W_{ii}
\]
is the same random constant for every configuration. Hence the diagonal
@@ -297,7 +297,7 @@ 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)$,
+Gibbs weights on the completed matrix.: Define, with $W=W(G)$,
\[
\widehat H_G(x)=\tfrac12 x^{\mathsf T}W(G)\,x,
\quad
@@ -312,122 +312,122 @@ $\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:
+Theorem~thm:main. It is crucial that $P$ is a joint law:
downstream we compare a proposal law $Q_l$ to $P$ on the joint
-$(G,x)$-space. The transition kernel for a \emph{fixed} disorder and a
-\emph{fixed} initial configuration is a different object, and the final
+$(G,x)$-space. The transition kernel for a fixed disorder and a
+fixed initial configuration is a different object, and the final
mixing argument must separate the two carefully.
%======================================================================
-\section{Scalar inputs and the entropy--energy identity}\label{sec:scalar}
+# Scalar inputs and the entropy--energy identity
%======================================================================
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
+proof. The endpoint is Proposition~lem:scalar-balance
+(equation~(eq:scalar-balance)): an exact scalar balance between the
energy a matrix-query proposal gains and the information it pays for.
Everything here is about a single diffusion and a few deterministic
functions of a scalar time; no high-dimensional geometry enters yet.
-\subsection{Equilibrium inputs, stated once}
+## 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
+[leftmargin=*]
+\item 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
+\item 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
+\item 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,
+ 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}
+ in (eq:martingale) below.
+
The stationarity identity is also given, in the form we quote, in
Jagannath--Tobasco \cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}.
What full support buys is precisely the ability to apply the identity at
-\emph{every} overlap in $[0,q_*]$; mere infinite support would not suffice.
+every overlap in $[0,q_*]$; mere infinite support would not suffice.
-\subsection{Normalization and the scalar Parisi equation}
+## 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),
+
+ \Phi_v=-\tfrac12(\Phi_{yy}+\alpha_v\Phi_y^2),
\qquad
- \Phi(\beta^2,y)=\log(2\cosh y),
-\end{equation}
+ \Phi(\beta^2,y)=\log(2cosh y),
+
with subscripts denoting derivatives. Equivalently, if $u$ is the scalar
-solution in \cite{Lopatto2026}, then
+solution in [cite], then
$\Phi(v,y)=u(v/\beta^2,y)+\log2$. Combining the independent ordered pair
couplings of the source gives the unordered pair coefficient
-$\beta/\sqrt n$ used in \eqref{eq:H}, plus a centered diagonal term. Thus
+$\beta/\sqrt n$ used in (eq:H), plus a centered diagonal term. Thus
this scalar normalization agrees with our completed Hamiltonian.
Set $v_*=\beta^2 q_*$. The pressure functional and the finite-volume
upper bound read
-\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}
+ \Phi(v_*,y)=\log(2cosh y)+(\beta^2-v_*)/(2) .
+
+
+## Continuation past the support endpoint
For all $v>v_*$ we continue the potential by the explicit formula
-\begin{equation}\label{eq:phi-extension}
- \Phi(v,y)=\log(2\cosh y)+\frac{\beta^2-v}{2},
+
+ \Phi(v,y)=\log(2cosh y)+(\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
+magnetizations 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$.
+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}
+ \mathbb E m_v^2=(v)/(\beta^2)\quad(0\le v\le v_*),
+
and this martingale equation continues past $v_*$ by direct It\^o
-calculus with the explicit functions \eqref{eq:phi-extension}. We use,
+calculus with the explicit functions (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
+
+\paragraph{Why (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
\[
@@ -440,51 +440,51 @@ $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') .
+ (Tf)''=\mathbb E_\lambda f''+\lambdaVar_\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 .
+ 0<(Tf)''\le1-((Tf)')^2-(1-\lambda)Var_\lambda(f')
+ \le1-((Tf)')^2 .
\]
-Inducting from $f(y)=\log(2\cosh y)$ proves the bound for step CDFs;
+Inducting from $f(y)=\log(2cosh y)$ proves the bound for step CDFs;
stability \cite[Propositions~1--2]{AC2015} passes the non-strict bound to
the minimizing CDF, and the strict lower bound on $\Phi_{yy}$ in
\cite[Proposition~2.4]{Lopatto2026} gives strict positivity in the limit.
Hence $m$ is strictly increasing and $|m|<1$, giving
-\eqref{eq:a-m-bound}. On the extension these assertions follow from
-$\tanh$ directly.
+(eq:a-m-bound). On the extension these assertions follow from
+$tanh$ directly.
-\subsection{Tail estimates for the extended diffusion}
+## 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
+ \qquad \rho(v)=\beta√(r(v)) .
+
+The martingale second-moment identity (eq:martingale) and
continuity give $r(v)=1/\beta^2$ on $[0,v_*]$, endpoints included. The
next lemma controls the continuation and confirms that $\rho$ is an
admissible noise-mixing coefficient in $[0,1]$.
-\begin{lemma}[Scalar tail bounds]\label{lem:scalar-tail}
+[Scalar tail bounds]
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}
+
+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
+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
@@ -507,21 +507,21 @@ 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
+proportional to $cosh y$; dividing by it leaves the asserted symmetric
decreasing profile.
-Weighting either $\operatorname{sech}y$ or $\operatorname{sech}^3y$ by a
+Weighting either $sechy$ or $sech^3y$ by a
decreasing profile can only increase the expectation of
-$\operatorname{sech}^2y$, since two nonincreasing functions of $|y|$ have
+$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).
+ \frac{\int_{\mathbb R}sech^{k+2}y\,dy}
+ {\int_{\mathbb R}sech^{k}y\,dy}
+ =(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
+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 .
@@ -530,80 +530,80 @@ 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}
+
+## 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},
+ \mathcal H(z)=-(1+z)/(2)\log(1+z)/(2)
+ -(1-z)/(2)\log(1-z)/(2),
\]
with continuous values at $z=\pm1$. For $V>v_*$ define the two scalars
that will be the energy per spin and the information cost per spin of the
matrix proposal:
-\begin{equation}\label{eq:ej}
- e(V)=\int_0^V\sqrt{r(v)}\,p(v)\,\rho(v)\,dv,
+
+ e(V)=\int_0^V√(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}
+ \mathbb E(a_v^2)/(1-m_v^2)\,dv .
+
The factor $\rho(v)^2$ inside $j$ accounts for the independent noise we
introduce in the proposal. Below the support endpoint, It\^o's formula
together with the PDE and stationarity gives
\[
- \mathbb E[Y_{v_*}m_{v_*}]=\int_0^{v_*}\bigl(p(v)+\alpha_v v/\beta^2\bigr)\,dv,
+ \mathbb E[Y_{v_*}m_{v_*}]=\int_0^{v_*}(p(v)+\alpha_v v/\beta^2)\,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}
+spatial derivatives. Substituting the endpoint value (eq:phi-at-vstar)
+and using $\mathcal H(tanh y)=\log(2cosh y)-ytanh y$ gives
+
\int_0^{v_*}p(v)\,dv+\mathbb E\,\mathcal H(m_{v_*})
- =\mathcal P-\frac{\beta^2}{4}(1-q_*)^2 .
-\end{equation}
+ =\mathcal P-(\beta^2)/(4)(1-q_*)^2 .
+
-\begin{proposition}[Entropy--energy identity]\label{lem:scalar-balance}
+[Entropy--energy identity]
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}
+ \log2-j(V)+\beta e(V)=\mathcal P-(\beta^2)/(4)\,p(V)^2 .
+
+
+
+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
+ \frac12\int_0^{v_*}\mathbb E(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
+$[0,v_*]$, the two identities above prove (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
+(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
+
+The terminal error $(\beta^2)/(4)p(V)^2$ on the right of
+(eq:scalar-balance) is at most $C_\beta e^{-V}$ by
+(eq:1). We take $V$ proportional to $\log n$, so this error is a
negative power of $n$ while the spin is nearly pinned.
%======================================================================
-\section{The Gaussian-query proposal}\label{sec:proposal}
+# The Gaussian-query proposal
%======================================================================
We now build a random spin using the matrix $W=W(G)$ together with
auxiliary randomness. The construction has a single design principle:
-\emph{each query of the matrix is orthogonal to the earlier queries and
-is independent given the past.} This exposes fresh Gaussian information
+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
+(eq:scalar-balance) will then control both the relative entropy of
the resulting law $Q_l$ and its likelihood outside a small exceptional
event.
@@ -611,47 +611,47 @@ 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
+is new here is the exact conditional-law bookkeeping for a finite
mesh, including the independent auxiliary noises that complete each
increment.
-\subsection{Construction and conditional Gaussian laws}
+## Construction and conditional Gaussian laws
-\paragraph{Mesh.} Fix a horizon parameter\footnote{We use the letter
+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}.}
+$l=b$ for the coarse connecting sequence; see Section~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}.
+endpoint of Section~sec:scalar.
-\paragraph{The two driving streams.} The disorder $G$ retains its ordinary
+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}
+follow the scalar SDE (eq:Y), driven by two independent streams,
+
+ dZ=\rho(v)\,dB+√(1-\rho(v)^2)\,dD .
+
Here $D$ is an auxiliary standard Brownian motion, independent of
everything; $B$ is to be constructed from matrix queries together with
auxiliary completions so that, after averaging over the disorder, $(B,D)$
-is a standard Brownian pair. By \eqref{eq:1} the weight $\rho\le1$ equals
+is a standard Brownian pair. By (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$
+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
+
+Project $T_k$ off the preceding query directions $u_1,...,u_{k-1}$ and
normalize the residual to obtain $|u_k|_n=1$. If the residual is exactly
zero, choose a new direction measurably from the past: project the
coordinate basis vectors in their fixed order, take the first nonzero
@@ -661,21 +661,21 @@ 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)
+
+ g_k=h^{-1/2}(B(t_{k+1})-B(t_k))
=\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
+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
+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
@@ -685,14 +685,14 @@ 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)
+ d_k=< u_k,Wu_k>_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
+has covariance $\Pi_{\le k}$, so $g_k$ in (eq:gk) is a fresh
standard Gaussian vector. Induction, followed by the independent bridge
-filling, proves that $(B,D)$ in \eqref{eq:4} is a standard Brownian pair.
+filling, proves that $(B,D)$ in (eq:4) is a standard Brownian pair.
-\paragraph{Coordinate symmetry.} After forgetting the matrix, the
+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
@@ -700,47 +700,47 @@ 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}
+## 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}
+[Proposal comparison]
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}
+
+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}.
+(eq:scalar-balance).
-\paragraph{Empirical inner products.} Form the empirical matrix of all
+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
+
+which follows from (eq:1). An exponential martingale estimate
bounds the linear form by its deterministic quadratic-variation bound.
The $g_k$ part is Gaussian and the spin term is bounded; the correlations
with the first part do not affect the resulting sub-Gaussian bound: for
@@ -749,7 +749,7 @@ $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).
+ 2\exp(-c_\beta n\eta^2e^{-4V}).
\]
A $1/4$-net of the unit sphere in dimension $O(K)$ has $\exp(O(K))$
points, by ball packing. The quadratic-form norm inequality and a union
@@ -757,20 +757,20 @@ 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
+(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
+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
@@ -792,27 +792,27 @@ 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
+writing $c_k=< u_k,x>_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\|
+ \left\|(\mathbf1_{j\le k}< u_j,g_k>_n)_{jk}\right\|
&\le C\eta\log(2K),\\
- \bigl\|(\langle g_k,x\rangle_n)_k-b\bigr\|&\le\eta .
- \end{aligned}
+ \bigl\|(< g_k,x>_n)_k-b\bigr\|&\le\eta .
+
\]
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
+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
+ =\sum_kc_k< x,\Pi_{>k}g_k>_n
+\tfrac12\sum_kc_k^2d_k
- +\tfrac12\langle x,H_0WH_0x\rangle_n .
+ +\tfrac12< x,H_0WH_0x>_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
@@ -820,23 +820,23 @@ 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
+$(\log r)'$ in (eq:1) implies $s_k/\sqrt h$ differs from
+$√(r(v))$ on $[t_k,t_{k+1}]$ by a relative $O(h)$. The missing initial
interval contributes $O(h)$, and $e(V)$ is bounded. Hence $s\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}
+
+ \widehat H_G(x)/n=e(V)+O_\beta(h+\eta\log(2K)).
+
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
+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}
+all unconditioned proposal inputs. Call this the 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).
+ \prod_i(1+x_i\,m(V,Y_{V,i})).
\]
For fixed $x$, the scalar martingale shows this is a stochastic
exponential with coordinate integrands
@@ -844,27 +844,27 @@ 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
+against the streams $Z_i$ in (eq:4). Call the resulting law the
+linked experiment. Summing the linking density over the uniform
spin shows the path and disorder marginal is unchanged.
For a continuous local martingale $N$ starting at zero write
-$\mathcal E(N)_V=\exp(N_V-\langle N\rangle_V/2)$. The linking density
+$\mathcal E(N)_V=\exp(N_V-< N>_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}
+
+ E_B&=\mathcal E(\sum_i\int_0^{\cdot}\xi_i\rho\,dB_i)_V,\\
+ E_D&=\mathcal E(\sum_i\int_0^{\cdot}\xi_i√(1-\rho^2)\,dD_i)_V,
+
\]
using the zero quadratic covariation of $B$ and $D$. Define the
-\emph{auxiliary reference} to have density $E_D$ relative to the unlinked
+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
+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
@@ -874,8 +874,8 @@ 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
+fixed by that past. Thus $\mathcal F_v⊆\mathcal G_v$. One can
+also see this pathwise: $\rho=1$ before $v_*$, and (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$.
@@ -890,12 +890,12 @@ $(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
+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).
+ L=\log E_B=\sum_i(\int_0^V\xi_i\rho\,dB_i
+ -\tfrac12\int_0^V\xi_i^2\rho^2\,dv).
\]
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
@@ -905,9 +905,9 @@ 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
@@ -915,7 +915,7 @@ 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
+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
@@ -926,7 +926,7 @@ relative to it is
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
+(eq:pressure) therefore implies
\[
F(G)\le n\mathcal P+n\eta
\]
@@ -934,92 +934,92 @@ 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
+Substituting the scalars.: Insert (eq:scalar-balance),
+(eq:7), $p(V)^2\le C_\beta e^{-V}$ and (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).
+ C_\beta n(h+\eta\log(2K)+e^{-V})=o(n^{1-l/2}).
\]
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
+restricted output marginal gives (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
+The entropy bound.: The same comparison in expectation proves
+(eq:5) by contraction of relative entropy under marginalization. The
exceptional paths contribute negligibly: $L$ has second moment
$O(n^2(1+V)^2)$, and the supremum of the absolute spin energies has second
moment $O(n^2)$ by Gaussian tails and a union bound. The log partition
function is bounded by $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}
+# Reversing the entropy: coverage
%======================================================================
-Proposition~\ref{prop:proposal} controls ${\rm KL}(Q_l\Vert P)$, the
-entropy cost of \emph{producing} a proposal spin. But entropy in the
+Proposition~prop:proposal controls ${\rm KL}(Q_l\Vert P)$, the
+entropy cost of producing a proposal spin. But entropy in the
forward direction is not enough: a set of large Gibbs mass might still
receive negligible proposal mass, and we will need in
-Section~\ref{sec:connections} that a proposed spin reaches such a set with
-appreciable probability. We therefore need a \emph{reverse} comparison.
+Section~sec:connections that a proposed spin reaches such a set with
+appreciable probability. We therefore need a reverse comparison.
The idea is to condition the Gibbs joint law on the spin. With the spin
fixed, the remaining law of the disorder is strongly log-concave. A small
Gaussian smoothing then turns the forward comparison into the reverse one
via the quadratic transport inequality.
-\subsection{Horizons and the smoothing map}
+## 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
+connecting sequence in Section~sec:connections: its exceptional-event
estimate $\exp(-n^{1-10b})$ is far stronger, even though its entropy bound
-\eqref{eq:5} is weaker.
+(eq:5) is weaker.
-\begin{definition}[Smoothing map $\mathcal S$]
+[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}
+
+ G^\circ=√(1-\delta)\,G+\sqrt\delta\,\bar G,
+
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'
+ √(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}
+## 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}
+[Smoothing reverses KL]
+
{\rm KL}(\mathcal SP\Vert\mathcal SQ_f)
\le\delta^{-1}\,{\rm KL}(Q_f\Vert P) .
-\end{equation}
-\end{proposition}
-\begin{proof}
+
+
+Proof.
The two unsmoothed laws have the same uniform spin marginal (see
-Section~\ref{sec:proposal}). Given $x$, the conditional disorder density
+Section~sec:proposal). Given $x$, the conditional disorder density
of $P$ has negative logarithm, up to a normalizing constant,
\[
U_x(G)=\tfrac12\|G\|^2-\beta\widehat H_G(x)+F(G).
@@ -1036,25 +1036,25 @@ 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
+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).
+ =\int(U(T(z))-U(z)-\log\det\nabla T(z))\,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
+replaces the linear term by $div(T-id)$. There is
no boundary term: on a face where the $i$-th coordinate is an endpoint of
the box, the conditional quantile map fixes that endpoint, so the normal
component $T_i-z_i$ vanishes; tangential motion does not matter. The
Jacobian terms are nonnegative because $z-1-\log 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
+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
@@ -1065,63 +1065,63 @@ 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
+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 .
+ {\rm KL}(N(√(1-\delta)\,g,\delta I)
+ \Vert N(√(1-\delta)\,\widetilde g,\delta I))
+ =(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}
+transport bound then proves (eq:8).
-\subsection{Coverage conditional on a target and its base}
-The smoothed entropy comparison \eqref{eq:8} is a joint-law statement. We
+## Coverage conditional on a target and its base
+
+The smoothed entropy comparison (eq:8) is a joint-law statement. We
now extract a statement for the original Gibbs law at a realized target
disorder $G$, using only the base $G^\circ$ that we also sample. The
following proposition records both the expected entropy estimate and the
coverage consequence used in the next section.
-\begin{proposition}[Coverage at a target disorder]\label{prop:coverage}
+[Coverage at a target disorder]
Let $G,\bar G$ be independent standard Gaussian disorder vectors, set
-$G^\circ=\sqrt{1-\delta}\,G+\sqrt\delta\,\bar G$, and let
+$G^\circ=√(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)
+$\mathcal SQ_f$ (eq:smoothing). Then
+
+ \mathbb E\,{\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))
\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}
+
+ {\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))\le n^{1-4d} .
+
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}
+$A⊆\{-1,1\}^n$ with $\pi_G(A)\ge n^{-d}$,
+
\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}
+
+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)\\
+
+ \mathbb E\,{\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))
+ &=\mathbb E\,{\rm KL}(\pi_G\Vert
+ \overline\pi(\cdot\mid G^\circ))\\
&\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
@@ -1134,43 +1134,43 @@ 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}.
+supremum by $O(n\sqrt\delta)$. Combining this estimate with (eq:8)
+and (eq:5) proves (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.
+The power-of-$n$ event. Since $4d<f/8$ and $4d<f/4$ (recall
+$d=f/100$ and $f=1/100$), Markov's inequality applied to (eq:9) gives
+(eq:10) with probability tending to one.
-\emph{Coverage from the entropy.} On the single event \eqref{eq:10},
+Coverage from the entropy. On the single event (eq:10),
let $A$ be any set with $\pi_G(A)\ge n^{-d}$. For $s=\pi_G(A)$ and
$t=\nu(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}
+ \log(1/t)\le n^d(n^{1-4d}+\log2)\le n^{1-2d}
\]
for sufficiently large $n$. The implication is deterministic once the
target and base are fixed, which proves the simultaneous assertion
-\eqref{eq:cov}.
-\end{proof}
+(eq:cov).
-Note that the coverage bound \eqref{eq:cov} deteriorates with
+
+Note that the coverage bound (eq:cov) deteriorates with
$d$, but this cost is well within the slack that the mixing argument
-needs. The choice $b\ll d$ in \eqref{eq:exponents} is exactly what makes
+needs. The choice $b\ll d$ in (eq:exponents) is exactly what makes
the connecting-sequence exception
-$\exp(-n^{1-10b})$ in Section~\ref{sec:connections} smaller than the
+$\exp(-n^{1-10b})$ in Section~sec:connections smaller than the
coverage probability $\exp(-n^{1-2d})$.
%======================================================================
-\section{Connecting proposals across a cut}\label{sec:connections}
+# Connecting proposals across a cut
%======================================================================
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
+about a single proposal. We now plant two proposals on either side
of a putative low-flow cut and force a contradiction with an elementary
geometric fact: a short sequence of spin flips that crosses a cut must
pass near the boundary.
-\subsection{Setup and statement}
+## Setup and statement
For distinct spins $x,y$, write $c_G(x,y)$ for the heat-bath jump rate and
\[
@@ -1179,24 +1179,24 @@ For distinct spins $x,y$, write $c_G(x,y)$ for the heat-bath jump rate and
\]
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 cut; it is also the quantity the mixing Lemma~lem:pruning
of the next section uses.
-\begin{proposition}[Balanced-cut flow]\label{prop:cuts}
+[Balanced-cut flow]
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 }
+ \quadfor every S with
\min(\pi_G(S),\pi_G(S^{\rm c}))\ge n^{-d}.
-\end{equation}
-\end{proposition}
-\begin{proof}
+
+
+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}
+## 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
@@ -1208,13 +1208,13 @@ $\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\}
+ ∂ S=\{x:\,d_H(x,S)=1 and d_H(x,S^{\rm c})=1\}
\]
has Gibbs mass at most $2B_{\min}\exp(O_\beta(\sqrt n))$, since each
boundary vertex controls at most $2n$ unit-rate crossings each carrying a
heat-bath acceptance probability at least $\exp(-O_\beta(\sqrt n))$.
-Set $R_n=\lceil n^{1-b/4}\rceil$ and enlarge $\partial S$ by Hamming
+Set $R_n=\lceil n^{1-b/4}\rceil$ and enlarge $∂ S$ by Hamming
distance $R_n$. For two spins at Hamming distance at most $R_n$ and with
$\|W(G)\|\le C$, the logarithmic Gibbs weight ratio is bounded by
$O_\beta(n^{1-b/8})$: the change in $\widehat H_G$ along any path of
@@ -1222,60 +1222,60 @@ $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}
+
+ \exp(-\tfrac12 n^{1-b/20})
+
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
+Among cuts violating (eq:11), select the first one in a fixed ordering
of the subsets of the cube whenever such a cut exists and $\|W(G)\|\le C$.
Let $\mathcal D(G)$ be its enlarged boundary, and set
-$\mathcal D(G)=\varnothing$ if no such cut exists or the norm bound fails.
+$\mathcal D(G)=∅$ 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
+holds, and the coverage statement (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)$.
+(eq:11) to showing $\Pr(\mathcal E)=o(1)$.
-\subsection{A sequence with independent fine endpoints}
+## 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
+[leftmargin=*]
+\item Fine horizon supplies coverage. On $\mathcal E$, the coverage
+ statement (eq:cov) gives each side of the cut fine-proposal
probability at least $\exp(-n^{1-2d})$. Two conditionally independent
fine endpoints therefore cross the cut with probability at least
$\exp(-2n^{1-2d})$.
-\item \emph{Coarse horizon supplies rare failures.} We need an unconditional
+\item 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
+ smaller than the endpoint-coverage probability. The fine-horizon
+ exceptional-event bound of Proposition~prop:proposal is
$\exp(-n^{1-10f})$, which is too weak: $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
+
+We therefore use fine spins at the two endpoints for coverage, and
+coarse spins along a grid for the connecting sequence. The shared
path prefixes plus the magnetization martingale keep each fine endpoint
close to its coarse output.
-\paragraph{Rotating the inputs.} Given the target $G$ and the base
-$G^\circ$ from Section~\ref{sec:reverse}, introduce independent standard
+Rotating the inputs.: Given the target $G$ and the base
+$G^\circ$ from Section~sec:reverse, introduce independent standard
Gaussian vectors $G'_1,G'_2$, independent of both, and set
-\begin{equation}\label{eq:rotation}
- G(\theta)=\sqrt{1-\delta}\,G^\circ
- +\sqrt\delta\bigl(\cos\theta\,G'_1+\sin\theta\,G'_2\bigr),
+
+ G(\theta)=√(1-\delta)\,G^\circ
+ +\sqrt\delta(\cos\theta\,G'_1+\sin\theta\,G'_2),
\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
+$O(\exp(n^{1/4}))$. Rotate two independent collections of all
+auxiliary Gaussian path inputs by the same cosine-sine rule, so that small
changes in $\theta$ produce small changes in the auxiliary inputs.
-\paragraph{Running the proposals.} At each grid point, run the coarse
+Running the proposals.: At each grid point, run the coarse
proposal to horizon
\[
V_b=h\lceil b\log n/h\rceil
@@ -1284,13 +1284,13 @@ 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
+and draw a fine spin. Coarse spin draws are not used in any
continuation. All final spin draws may use fresh independent randomness.
-\paragraph{Conditional structure.} The two fine endpoints are independent
+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
+auxiliary inputs on the right side of (eq:rotation) gives the
appropriate proposal law; its primitive auxiliary collection is
independent of all target, base, and proposal matrix drivers. The
one-point estimates and their union bound require no independence across
@@ -1299,45 +1299,45 @@ 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*)]
+[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 probability here is unconditional. Figure~fig:connection shows
the deterministic obstruction that (a) and (b) together create, once we
sample two fine endpoints that provably lie on opposite sides of the cut.
-\subsection{Avoiding a boundary selected from the target}
+## 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
+variance $2\delta$, by (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
+Apply the likelihood estimate (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}
+ \quadfor almost every g .
+
The primitive auxiliary inputs and the final spin draw for this run are
independent of all the matrix drivers. Thus, after fixing
-$G(\theta)=g$ and adjoining $(G,G^\circ)$, this remains the \emph{conditional}
+$G(\theta)=g$ and adjoining $(G,G^\circ)$, this remains the conditional
good-output kernel given the past. In particular, the inequality applies
to the random set $\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.
+it is not built into the proposal good event.
-By \eqref{eq:12}, the resulting boundary probability on the complement of
+By (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).
+ \exp(n^{1-b/2}+O_\beta(n\sqrt\delta)-\tfrac12 n^{1-b/20}).
\]
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
@@ -1347,61 +1347,61 @@ 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}
+## 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$
+Proposition~prop:proposal puts the Gram matrix of the coarse $T_k$
within $n^{-b}$ of the identity except with probability
$\exp(-n^{1-10b})$. On this event all $|T_k|_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
+Gram--Schmidt residual has norm at least $1/2$, so we do not touch
+the zero-residual fallback of Section~sec:proposal. The reciprocals
$1/s_k$ are bounded by a fixed power of $n$ on the deterministic coarse
-horizon, by \eqref{eq:1}.
+horizon, by (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
+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
+deterministic coefficients $\rho$ and $√(1-\rho^2)$. On a filled
interval include only the centered bridge in this primitive bound; its
endpoint is handled separately. All these norms are at most $n^3$ outside
an event of probability $O(e^{-cn})$. Gaussian tails give the matrix and
vector estimates. For the path integrals, write a bridge as Brownian
motion minus its linearly interpolated endpoint and use the Gaussian
martingale maximal bound for a bounded deterministic integrand. Rotation
-\eqref{eq:rotation} makes the differences of the primitive inputs at two
+(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
+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
+matrix-query and completion formula (eq:gk). The cumulative driving
+signals from (eq:4) differ by the primitive integral differences plus
the endpoint difference multiplied by a deterministic factor at most
-$\sqrt h$. Finally, the scalar integral equation \eqref{eq:Y} and its
+$\sqrt h$. Finally, the scalar integral equation (eq:Y) and its
spatially Lipschitz drift control the differences in $Y$ and $M$ over this
interval at constant cost, by Gronwall's inequality. Starting with the
entirely auxiliary first interval and taking successive maxima of these
-differences proves \eqref{eq:13} after increasing $C_1$ if necessary.
+differences proves (eq:13) after increasing $C_1$ if necessary.
Only the Gram conditions at the two endpoints of each grid step were used.
Since $K_b=O(n^{1/16}\log n)$ and the mesh spacing $O(\exp(-n^{1/4}))$ is
-exponentially smaller, \eqref{eq:13} makes every consecutive coarse
+exponentially smaller, (eq:13) makes every consecutive coarse
magnetization difference negligible relative to $n^{-b/3}$.
-\subsection{From magnetizations to spins}
+## 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
@@ -1417,16 +1417,16 @@ 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
+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}
+## The crossing contradiction
-On $\mathcal E$, the coverage statement \eqref{eq:cov} gives each side of
+On $\mathcal E$, the coverage statement (eq:cov) gives each side of
the chosen cut fine-endpoint probability at least $\exp(-n^{1-2d})$.
Conditional independence therefore puts the two fine endpoints on opposite
sides of the cut with probability at least $\exp(-2n^{1-2d})$.
@@ -1434,23 +1434,23 @@ 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$,
+path between the pair meets $∂ 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
+(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]
+[!htbp]
\centering
-\begin{tikzpicture}[x=1cm,y=1cm,font=\small,
+[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,
@@ -1498,221 +1498,221 @@ bath.
\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}
+ {$d_H(u,∂ S),\,d_H(v,∂ S)\le\ell\le R_n
+ \;⇒\; u,v\in\mathcal D(G)$.};
+
\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
+$u$ to $v$ meets the two-sided boundary $∂ 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).
+used in Section~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}
+# From balanced flows to typical-state mixing
%======================================================================
-The flow estimate \eqref{eq:11} is available only when \emph{both} sides
+The flow estimate (eq:11) is available only when both sides
of a cut have appreciable Gibbs mass. We now convert exactly this
information into a mixing statement about typical fixed starting states.
The finite-state argument below has three steps:
-\begin{enumerate}[label=\arabic*.,leftmargin=*]
+[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
+\item Use entropy dissipation of the full chain plus stationarity to
bound the $\pi$-average of the fixed-start total variation at time $T$,
and finish with Markov's inequality over the starting state.
-\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}
+## 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
+[Pruning and averaged mixing]
+Let $Ω$ be a finite set, $\pi$ a strictly positive probability on
+$Ω$, and $P_t$ a continuous-time Markov semigroup reversible with
respect to $\pi$ with jump rates $c(x,y)$. Assume that for some $R>0$
\[
- \sum_{y\ne x}c(x,y)\le R\qquad(x\in\Omega).
+ \sum_{y\ne x}c(x,y)\le R\qquad(x\inΩ).
\]
-Let $0<\varepsilon<1/3$ and $B>0$. Suppose that
+Let $0<ε<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.
+ \quadwhenever ε\le\pi(S)\le1-ε.
\]
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,
+
+ \sum_{x\inΩ}\pi(x)\bigl\|P_T(x,\cdot)-\pi\bigr\|_{\rm TV}
+ \le\frac{√(2R\,H(\pi))}{B\sqrt T}+2ε,
\qquad H(\pi)=-\sum_x\pi(x)\log\pi(x).
-\end{equation}
-\end{lemma}
-\begin{proof}
+
+
+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.
+ \mathfrak D(u)=\sum_{\{x,y\}}q(x,y)(u(x)-u(y))^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
+Step 1: removing sets that do not expand.: Start with
+$C=Ω$. Whenever a nonempty $U\subset C$ satisfies
\[
- \pi(U)\le\pi(C)/2,\qquad Q(U,C\setminus U)<B\pi(U),
+ \pi(U)\le\pi(C)/2,\qquad Q(U,C∖ 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$,
+endpoint was removed, so whenever $A\ne∅$,
\[
- Q(A,\Omega\setminus A)<B\pi(A).
+ Q(A,Ω∖ 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
+Suppose the removed mass first reached $ε$. Its preceding mass
+$a$ was less than $ε$, and the newly removed set has mass at
most $(1-a)/2$. The new total is therefore at most
-$(1+a)/2<(1+\varepsilon)/2<1-\varepsilon$. This contradicts the
+$(1+a)/2<(1+ε)/2<1-ε$. 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}
+set satisfies $\pi(C)>1-ε$ and
+
+ Q(U,C∖ U)\ge B\pi(U)
+ \quadfor every U\subset C with \pi(U)\le\pi(C)/2 .
+
-\paragraph{Step 2: a Poincar\'e inequality on the retained set.} Use the
+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),
+
+ \sum_{y\in C}\pi(y)(u(y)-\bar u_C)^2
+ \le(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$
+Integrating (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|.
+ \le\sum_{\{x,y\}\subset C}q(x,y)|w(x)^2-w(y)^2|.
\]
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},
+ (\sum_{\{x,y\}\subset C}q(x,y)(w(x)-w(y))^2)^{1/2}
+ (2R\sum_C\pi w^2)^{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}.
+error, proving (eq:14).
-\paragraph{Step 3: entropy dissipation for the full chain.} For a fixed
+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
+
+ \int_0^T\sum_x\pi(x)\,\mathfrak D(√(f_t^x))\,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).
+ (f_t^x(y)-f_t^x(z))(\log f_t^x(y)-\log f_t^x(z)).
\]
The initial entropy is $\log(1/\pi(x))$ and the final entropy is
-nonnegative. Averaging in $x\sim\pi$ and integrating proves \eqref{eq:15}.
+nonnegative. Averaging in $x\sim\pi$ and integrating proves (eq:15).
Vanishing densities and reducible chains cause no problem: start with
-$(1-\eta)f_0^x+\eta$ and pass to $\eta\downarrow0$, or calculate on
+$(1-\eta)f_0^x+\eta$ and pass to $\eta↓0$, 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
+Step 4: averaging fixed-state distances.: Combining (eq:14)
+and (eq:15) supplies some $t\in(0,T]$ with
\[
- \sum_x\pi(x)r_x^2\le\frac{R\,H(\pi)}{2TB^2},
+ \sum_x\pi(x)r_x^2\le(R\,H(\pi))/(2TB^2),
\quad
- r_x^2=\sum_C\pi(y)\bigl(\sqrt{f_t^x(y)}-a_x\bigr)^2,
+ r_x^2=\sum_C\pi(y)(√(f_t^x(y))-a_x)^2,
\quad
- a_x=\frac1{\pi(C)}\sum_C\pi(y)\sqrt{f_t^x(y)} .
+ a_x=\frac1{\pi(C)}\sum_C\pi(y)√(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 .
+ \sum_C\pi|f_t^x-a_x^2|\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)$.
+$|\sum_C\pi(f_t^x-1)|\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|
+ \sum_Ω\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}
+at the prescribed time $T$, establishing (eq:averaged-mixing).
-\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
+## Proof of the main theorem
+
+Proof. [Proof of Theorem~thm:main]
+On the disorder event of Proposition~prop:cuts, apply
+Lemma~lem:pruning to the SK chain with
\[
- \varepsilon=n^{-d},\qquad B=\exp\bigl(-n^{1-b/20}\bigr),\qquad R=n .
+ ε=n^{-d},\qquad B=\exp(-n^{1-b/20}),\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}.
+ \le\frac{√(2\log2)\;n}{B\sqrt T}+2n^{-d}.
\]
Take
\[
- T=\exp\bigl(n^{1-b/40}\bigr).
+ T=\exp(n^{1-b/40}).
\]
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 .
+ \log(n)/(B\sqrt T)
+ =\log n+n^{1-b/20}-\tfrac12 n^{1-b/40}→-∞ .
\]
-The flow event \eqref{eq:11} itself has disorder probability tending to
+The flow event (eq:11) itself has disorder probability tending to
one. Markov's inequality therefore shows that the Gibbs mass of fixed
states whose distance at time $T$ exceeds $1/4$ tends to zero in disorder
probability. The added diagonal changes neither this Gibbs law nor the
transition rates, so the same statement holds for the model $H^J_n$ in
-\eqref{eq:H}. This proves Theorem~\ref{thm:main} with
+(eq:H). This proves Theorem~thm:main with
\[
- c_\beta=\frac{b}{40}=\frac1{40000000}.
+ c_\beta=(b)/(40)=\frac1{40000000}.
\]
All threshold dimensions may depend on the fixed $\beta>1$.
-\end{proof}
-\subsection{Reading the final exponents}
+
+## Reading the final exponents
For orientation, here is the chain of inequalities that governs the
-constants, all in the ``$1-\text{exponent}$'' scale:
+constants, all in the ``$1-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
+The two competing probabilities in Section~sec:connections were the
coverage probability $\exp(-2n^{1-2d})$ and the sequence failure
probability $\exp(-n^{1-d/2})$: the ratio of their exponents is $2d$ versus
$d/2$, and $d/2\ll d<2d$ gives the gap. The mixing time $T=\exp(n^{1-b/40})$
@@ -1724,143 +1724,143 @@ were chosen in a strict hierarchy to keep every exponent well separated.
%======================================================================
% References
%======================================================================
-\begin{thebibliography}{99}
+{99}
\bibitem{AC2015}
A.~Auffinger and W.-K.~Chen,
\newblock On properties of Parisi measures,
-\newblock \emph{Probab.\ Theory Related Fields} \textbf{161} (2015),
+\newblock Probab.\ Theory Related Fields 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}.
+\newblock doi:10.1007/s00440-014-0563-y;
+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$,
+$\beta\le\tfrac12+ε$,
\newblock preprint (2026),
-\href{https://arxiv.org/abs/2609.13138v1}{arXiv: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}.
+\newblock Sbornik: Math. 196 (2005), no.~3, 309--335.
+\newblock 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}.
+\newblock Comm.\ Math.\ Phys. 325 (2014), 333--366.
+\newblock doi:10.1007/s00220-013-1862-3;
+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.
+\newblock 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}.
+\newblock Ann.\ Probab. 45 (2017), no.~6A, 3929--3966.
+\newblock doi:10.1214/16-AOP1154;
+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}.
+\newblock Ann.\ Appl.\ Probab. 6 (1996), no.~3, 695--750.
+\newblock 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),
+\newblock Probab.\ Theory Related Fields 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}.
+\newblock doi:10.1007/s00440-021-01085-x;
+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}.
+\newblock Comm.\ Math.\ Phys. 233 (2003), 1--12.
+\newblock doi:10.1007/s00220-002-0773-5;
+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),
+\newblock Probab.\ Theory Related Fields 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}.
+\newblock doi:10.1007/s00440-015-0691-z;
+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,
+\newblock Trans.\ Amer.\ Math.\ Soc. 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}.
+\newblock 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}.
+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}.
+\newblock Proc.\ Mach.\ Learn.\ Res. 178 (2022), 3524--3546.
+\newblock Proceedings article.
\bibitem{Montanari2021}
A.~Montanari,
\newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
-\newblock \emph{SIAM J.\ Comput.} \textbf{54} (2025), no.~4,
+\newblock SIAM J.\ Comput. 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}.
+\newblock doi:10.1137/20M132016X;
+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.
+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}.
+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}.
+\newblock Phys.\ Rev.\ Lett. 35 (1975), no.~26, 1792--1796.
+\newblock 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}.
+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}.
+\newblock Comm.\ Pure Appl.\ Math. 79 (2026), 1746--1770.
+\newblock doi:10.1002/cpa.70038.
+
+
-\end{thebibliography}
-\end{document}