\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1.08in]{geometry}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{microtype}
\usepackage{xcolor}
\usepackage[colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,urlcolor=blue!45!black]{hyperref}
\pdfgentounicode=1
\hypersetup{pdftitle={A Capacity Criterion for Four-State Potts Reconstruction on Trees},pdfauthor={OpenAI}}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}{Definition}[section]
\newtheorem*{remark}{Remark}
\numberwithin{equation}{section}
\newcommand{\E}{\mathbb E}
\newcommand{\Prob}{\mathbb P}
\newcommand{\calC}{\mathcal C}
\newcommand{\unif}{\mathsf u}
\newcommand{\Capacity}{\operatorname{Cap}}
\newcommand{\TV}{\operatorname{TV}}
\newcommand{\children}{\operatorname{ch}}
\title{A Capacity Criterion for Four-State Potts Reconstruction on Trees}
\author{OpenAI}
\date{October 5, 2026}
\begin{document}
\maketitle
\begin{abstract}
Consider the ferromagnetic four-state broadcast model with retention
parameter $0<\lambda<1$ on a rooted tree of bounded degree. We prove
that reconstruction (deciding the root from a distant level better than
chance) holds if and only if the tree has positive $L^3$ capacity with
edge resistances $\lambda^{-2|e|}$. The criterion needs no regularity or
growth-rate hypothesis and is sharp on the exponential Kesten--Stigum
boundary. Both directions are proved completely below.
\end{abstract}
\section*{How to read this paper}
\addcontentsline{toc}{section}{How to read this paper}
\emph{The story in one paragraph.} A rumor starts at the root of a tree.
Every person repeatedly tells the rumor to each of their children, but
along each edge the message may be corrupted: with probability
$\lambda$ the child hears the true value, and with probability
$1-\lambda$ the child hears a uniformly random value among the four
possibilities. This is the \emph{four-state Potts broadcast}. A distant
level of the tree is observed. \emph{Reconstruction} means that the
observed leaves still reveal, better than a blind guess, which rumor the
root started. The question is to decide, for a given tree and given
$\lambda$, whether reconstruction occurs.
\emph{The answer.} Attach to the tree a single number, its \emph{$L^3$
capacity} with edge resistances $\lambda^{-2|e|}$. Positive capacity
means that a fluid can be pushed from the root to infinity so that its
quadratic energy stays bounded on every ray. The main theorem states that
reconstruction occurs exactly when this number is positive. No assumption
on how fast the tree grows is needed, and the test is sharp even when the
tree is critically balanced.
\emph{How the proof is organized.} Section~\ref{sec:model} fixes notation
and states the theorem. Section~\ref{sec:toolbox} builds the bookkeeping:
a symmetric quadratic statistic $m$ that measures how much a posterior
knows, plus a signed third moment that controls what is lost when branches
are merged. Section~\ref{sec:necessity} proves that reconstruction forces
positive capacity by converting a saving of information at every branching
into an admissible flow. Section~\ref{sec:moments} proves the local
estimates. Section~\ref{sec:sufficiency} proves the converse: a positive
flow is turned into a controlled amount of added noise at each level, and
a path-averaging argument shows the surviving information never drops to
zero. Section~\ref{sec:history} places the result among earlier work.
\section{The model, reconstruction, and the main theorem}
\label{sec:model}
Let $T$ be an infinite locally finite rooted tree with root $\rho$. Fix an
integer $B$ with $1\le B<\infty$ and assume every vertex has at most $B$
children; vertices with zero or one child are allowed. Write $|v|$ for the
depth of a vertex, $\children(v)$ for its set of children, and
$L_n=\{v:|v|=n\}$ for the level at depth $n$. The tree is deterministic and
known to the observer.
Fix $0<\lambda<1$. Give the root spin $\sigma_\rho$ a uniform value in
$[4]=\{1,2,3,4\}$. Conditionally on the parent spin, spins pass down each
edge independently, and a spin $i$ is replaced by $j$ with probability
\begin{equation}\label{eq:channel}
P_\lambda(j\mid i)
=\lambda\,\mathbf1_{\{i=j\}}+\frac{1-\lambda}{4}.
\end{equation}
Thus $\lambda$ is the probability that a single edge transmits the value
correctly.
Let $\unif=(1/4,1/4,1/4,1/4)$. The information at depth $n$ about the root
is
\[
a_n(T,\lambda)
=\E\,\TV\!\bigl(\Prob(\sigma_\rho\in\cdot\mid\sigma_{L_n}),\unif\bigr),
\qquad
\TV(p,\unif)=\tfrac12\sum_{i=1}^4|p_i-\tfrac14|.
\]
By data processing, observing a deeper level cannot decrease the
information, so $a_n$ is nonincreasing and has a limit
$a_\infty(T,\lambda)\ge0$.
\begin{definition}\label{def:reconstruction}
\emph{Reconstruction occurs} if $a_\infty(T,\lambda)>0$. Otherwise it fails.
\end{definition}
A \emph{flow} $\theta$ to infinity assigns a nonnegative number to each
edge so that at every nonroot vertex the incoming flow equals the sum of
the outgoing flows. Its \emph{mass} is the flow leaving the root,
\[
|\theta|=\sum_{w\in\children(\rho)}\theta(\rho,w).
\]
For an edge $e$ let $|e|$ be the depth of its child endpoint, and let
$\partial T$ be the set of infinite rays from the root. Define the
\emph{energy} of a flow along a ray and the \emph{$L^3$ capacity} by
\begin{align}
V_\lambda(\theta,\xi)
&=\sum_{e\in\xi}\bigl(\lambda^{-2|e|}\theta(e)\bigr)^2,
\qquad \xi\in\partial T,\label{eq:potential}\\
\Capacity_{3,\lambda}(T)
&=\sup\Bigl\{|\theta|:
\sup_{\xi\in\partial T}V_\lambda(\theta,\xi)\le1\Bigr\}.
\label{eq:capacity}
\end{align}
The zero flow is allowed, so the capacity is a nonnegative number, possibly
$0$ or $+\infty$.
\begin{theorem}[Main theorem]\label{thm:main}
Let $T$ be an infinite rooted tree with at most $B<\infty$ children per
vertex and let $0<\lambda<1$. For the broadcast model \eqref{eq:channel},
\[
a_\infty(T,\lambda)>0
\quad\Longleftrightarrow\quad
\Capacity_{3,\lambda}(T)>0.
\]
\end{theorem}
\begin{remark}
No regularity or growth-rate assumption on $T$ enters. In particular the
criterion decides the exponential Kesten--Stigum boundary, where a bound
based on growth rate alone is inconclusive.
\end{remark}
\begin{remark}
The exclusion of $\lambda=1$ is essential. At $\lambda=1$ the channel is
perfect: an infinite ray reconstructs the root exactly, yet the resistances
$\lambda^{-2|e|}$ equal $1$ and any nonzero flow has infinite energy along
a ray, so the capacity in \eqref{eq:capacity} is zero. Thus the
equivalence genuinely needs $\lambda<1$.
\end{remark}
Throughout, set
\[
r=\lambda^2\in(0,1).
\]
The number $r$ is the squared retention and appears wherever an edge
shrinks the quadratic information defined in the next section.
\section{Measuring the information in a posterior}
\label{sec:toolbox}
An \emph{experiment} is an observation about a uniform input spin in
$[4]$. Its posterior is a probability vector $p$, and $\mu$ denotes the law
of $p$ under the marginal law of the observation. A posterior law is
\emph{symmetric} if it is invariant under all permutations of the four
entries.
\subsection{The quadratic and cubic statistics}
Define the fixed $3\times4$ matrix
\[
L=\begin{pmatrix}
1&1&-1&-1\\
1&-1&1&-1\\
1&-1&-1&1
\end{pmatrix},
\qquad x=Lp,\qquad A(p)=|x|^2,
\]
and put
\begin{equation}\label{eq:statistics}
m(\mu)=\E_\mu A,
\qquad \tau(\mu)=\E_\mu[x_1x_2x_3],
\qquad h(\mu)=|\tau(\mu)|.
\end{equation}
Here and below $\|\cdot\|$ is the Euclidean norm. The rows of $L$ are
mutually orthogonal of length $2$ and each sums to zero, so they span the
orthogonal complement of the all-ones vector. Consequently
\begin{equation}\label{eq:posterior-bounds}
A(p)=4\,|p-\unif|^2,\qquad 0\le A(p)\le3,
\qquad \tfrac18A(p)\le\TV(p,\unif)\le\tfrac12\sqrt{A(p)}.
\end{equation}
The identity $A(p)=4|p-\unif|^2$ uses $LL^{\mathsf T}=4I$ and
$L^{\mathsf T}L=4(I-\tfrac14\mathbf1\mathbf1^{\mathsf T})$. The bound
$A\le3$ is attained at a vertex of the simplex. The lower TV bound follows
from $|p_i-\tfrac14|^2\le|p_i-\tfrac14|$, and the upper bound is
Cauchy--Schwarz. Taking expectations gives
\begin{equation}\label{eq:expected-TV}
\tfrac18m(\mu)\le\E\,\TV(p,\unif)\le\tfrac12\sqrt{m(\mu)}.
\end{equation}
Thus $a_\infty>0$ is equivalent to the root quadratic information being
positive, which is why $m$ is the central quantity.
Finally, if an observation is degraded by conditioning on less
information, the new posterior is the conditional expectation of the old
one. Since $A$ is convex, $m$ cannot increase under data processing.
\subsection{Channel steps and independent products}
\emph{Channel step with parameter $t\in[0,1]$.} Transmit a uniform input
$I$ to $J$ through $P_t$, then run an experiment about $J$. Because the
uniform law is stationary and the channel is symmetric, the posterior
about $I$ is $\unif+t(p-\unif)$, where $p$ is the posterior about $J$.
Hence
\begin{equation}\label{eq:channel-scaling}
x\longmapsto tx,\qquad
m\longmapsto t^2m,\qquad
\tau\longmapsto t^3\tau,\qquad
h\longmapsto t^3h.
\end{equation}
The revealing experiment has $m=3$; the uninformative experiment has
$m=h=0$.
\emph{Independent product.} Suppose two observations are conditionally
independent given the same input spin; write $\mu\star\nu$ for the
posterior law of the pair. Sample $p\sim\mu$ and $q\sim\nu$
independently. The joint marginal law of the two observations is obtained
by reweighting the product law by
\begin{equation}\label{eq:product-rule}
Z=4\sum_{i=1}^4p_iq_i,
\qquad P_i=\frac{4p_iq_i}{Z}.
\end{equation}
Indeed the likelihood of each observation given input $i$, relative to
its marginal, is $4p_i$ respectively $4q_i$; averaging their product over
the uniform input produces \eqref{eq:product-rule}. In particular
$\E Z=1$, and the value of $P$ where $Z=0$ is irrelevant. Both channel
steps and products preserve symmetry.
\subsection{Symmetric moments and the bound $h\le m$}
The columns of $L$ are exactly the four sign triples whose product is
$+1$. Permuting the four columns acts on $x$ by coordinate permutations
and even sign changes. For a symmetric posterior law this forces
\begin{equation}\label{eq:symmetric-moments}
\E x_i=0,\qquad
\E x_ix_j=\frac{m}{3}\,\mathbf1_{\{i=j\}},
\end{equation}
and every degree-three coordinate monomial except $x_1x_2x_3$ has zero
mean. Since $\max_i|x_i|\le1$, every coordinate monomial of degree at
least two is bounded in absolute value by $|x|^2$: keep two factors and
use $|x_ix_j|\le\tfrac12(x_i^2+x_j^2)$, or $|x_i|^2$ when indices agree.
In particular
\begin{equation}\label{eq:h-bound}
h(\mu)\le m(\mu).
\end{equation}
\subsection{The companion input}
The following statement is the one external probabilistic input; it is
proved by a polynomial certificate in the companion manuscript
\cite{OpenAI26Potts} and is not reproved here. Its preserved \emph{class}
$\calC$, not merely symmetry, is what makes the saving in
\eqref{eq:moment-saving} available.
\begin{proposition}[Companion input, {\cite[Proposition~3.2]{OpenAI26Potts}}]
\label{prop:companion}
There is a class $\calC$ of symmetric posterior laws containing the
revealing and uninformative laws and stable under channel steps with any
parameter in $[0,1]$ and under conditionally independent products. For
$\mu,\nu\in\calC$,
\begin{equation}\label{eq:moment-saving}
m(\mu\star\nu)\le m(\mu)+m(\nu)
-c\bigl(\E_\mu[A^2]\,m(\nu)+m(\mu)\,\E_\nu[A^2]\bigr),
\qquad c=\frac1{1000}.
\end{equation}
\end{proposition}
Every finite-depth subtree experiment used below has law in $\calC$: this
includes observations of a descendant level, and observations in which
each terminal spin is independently passed through its own channel $P_t$.
At the terminals this is closure from the revealing law; an empty
observation is uninformative. Working up toward the subtree root uses only
channel steps and products, with conditional independence supplied by the
broadcast process. The same reasoning covers every partial product at a
vertex. No assertion about a limiting posterior law is ever needed.
\section{Reconstruction implies positive capacity}
\label{sec:necessity}
The nonlinear capacity recursion of Pemantle and Peres
\cite[Lemma~3.1, Corollary~3.4]{PP10} has a direct flow interpretation in
the present normalization. We first give that construction, then derive
its hypothesis from the posterior information.
\begin{lemma}[A flow from recursive labels]\label{lem:flow}
Suppose nonnegative finite labels $(z_v)_{v\in T}$ satisfy, for every
vertex $v$,
\begin{equation}\label{eq:label-recursion}
z_v\le\sum_{w\in\children(v)}\frac{r\,z_w}{\sqrt{1+z_w^2}}.
\end{equation}
Then there is a flow of mass $z_\rho$ whose energy \eqref{eq:potential} is
at most $1$ on every ray. In particular
$\Capacity_{3,\lambda}(T)\ge z_\rho$.
\end{lemma}
\begin{proof}
At each vertex $v$ choose coefficients
\[
0\le d_{vw}\le\frac{r}{\sqrt{1+z_w^2}}
\quad\text{with}\quad
z_v=\sum_{w\in\children(v)}d_{vw}z_w .
\]
This is possible: if the upper sum
$U=\sum_w r z_w/\sqrt{1+z_w^2}$ is positive, set
$d_{vw}=(z_v/U)\,r/\sqrt{1+z_w^2}$, which satisfies
$z_v\le U$ by \eqref{eq:label-recursion}; if $U=0$ then $z_v=0$ and all
$z_w=0$, and we take $d_{vw}=0$. Define $g_\rho=1$ and, recursively,
\[
\ell_\rho=1,\qquad \ell_w=\ell_v\,d_{vw},\qquad g_v=r^{-|v|}\ell_v,
\qquad \theta(v,w)=\ell_w z_w .
\]
Conservation holds at every nonroot vertex: the incoming flow is
$\ell_vz_v$ and the outgoing flow is
$\sum_w\ell_wz_w=\ell_v\sum_wd_{vw}z_w=\ell_vz_v$. The mass at the root is
$\sum_wd_{\rho w}z_w=z_\rho$. Since
$d_{vw}\le r/\sqrt{1+z_w^2}$,
\[
g_w^2\,(1+z_w^2)\le g_v^2,
\qquad\text{hence}\qquad
\bigl(r^{-|w|}\theta(v,w)\bigr)^2=(g_wz_w)^2\le g_v^2-g_w^2 .
\]
Summing the edge energies along any finite initial segment of a ray and
telescoping gives a total at most $g_\rho^2=1$. Monotone convergence of
these nonnegative sums extends the bound to every infinite ray.
\end{proof}
For a vertex $v$, let $m_v^{(n)}$ be the quadratic information about
$\sigma_v$ obtained from descendants at distance exactly $n$, with
$m_v^{(0)}=3$ (the revealing value). Data processing gives limits
\[
m_v=\lim_{n\to\infty}m_v^{(n)}\in[0,3].
\]
If reconstruction occurs then \eqref{eq:expected-TV} gives $m_\rho>0$. We
now show that these limiting numbers satisfy \eqref{eq:label-recursion}
with a positive label at the root.
For a fixed vertex $v$, put
\[
b_w=r\,m_w,\qquad S=\sum_{w\in\children(v)}b_w,
\qquad
D=\max_{w\ne w'}b_wb_{w'}(b_w+b_{w'}),
\]
where $D=0$ if $v$ has fewer than two children.
\emph{The pair saving.} At finite depth the parent information is
$m_v^{(n+1)}$, and the child values after their edge channels are
$b_w=r\,m_w^{(n)}$. Combine any two children first. Since
$\E A^2\ge(\E A)^2=m^2$, Proposition~\ref{prop:companion} saves at least
$c\,b_wb_{w'}(b_w+b_{w'})$ when those two branches are merged; combine the
remaining children by the subadditivity part of the same proposition and
maximize over the chosen pair. Passing to the limit yields
\begin{equation}\label{eq:pair-saving}
m_v\le S-cD.
\end{equation}
With zero or one child the empty observation or channel scaling gives the
same assertion directly (here $D=0$).
\emph{The cubic bound.} There are at most $B^3$ ordered triples of
children, and every mixed product in $S^3=(\sum_wb_w)^3$ is at most the
square of the largest $b_w$ times the second largest, which is at most
$D$. Therefore
\begin{equation}\label{eq:cubic-sum}
S^3\le\sum_w b_w^3+B^3D.
\end{equation}
\emph{Renormalizing.} Choose $K>0$ with $KB^3\le c$ and set
$y_v=m_v+Km_v^3$. Since $m_v\le S$, Equations~\eqref{eq:pair-saving} and
\eqref{eq:cubic-sum} give
\begin{align}
y_v&\le S-cD+KS^3
\le S+K\sum_wb_w^3\notag\\
&=r\sum_w y_w-Kr(1-r^2)\sum_wm_w^3.
\label{eq:renormalized-saving}
\end{align}
The correction supplies a saving even at a one-child vertex, where the
pair term vanishes: the coefficient $r-r^3=r(1-r^2)$ is strictly positive.
Since $m_w\le3$ we have $y_w\le(1+9K)m_w$. Let
\[
\delta=\frac{K(1-r^2)}{(1+9K)^3}>0 .
\]
Then \eqref{eq:renormalized-saving} and the tangent bound
$(1+2t)^{-1/2}\ge1-t$ for $t\ge0$ give
\[
y_v\le r\sum_wy_w\bigl(1-\delta y_w^2\bigr)
\le r\sum_w\frac{y_w}{\sqrt{1+2\delta y_w^2}} .
\]
Thus $z_v=\sqrt{2\delta}\,y_v$ satisfies \eqref{eq:label-recursion}. Since
$m_\rho>0$ gives $y_\rho>0$, we have $z_\rho>0$, and Lemma~\ref{lem:flow}
produces a flow of positive mass with energy at most one on every ray.
Hence $\Capacity_{3,\lambda}(T)\ge z_\rho>0$, completing the first
implication of Theorem~\ref{thm:main}.
\section{The local moment estimates}
\label{sec:moments}
For the converse, subadditivity alone does not control the information lost
when branches are merged. The next lemma bounds that loss using only
symmetry and one channel-smoothed input; unlike
Proposition~\ref{prop:companion} it does not need membership in $\calC$.
\begin{lemma}\label{lem:local-moments}
Fix $0<\lambda<1$. Let $\mu,\nu$ be symmetric posterior laws, with $\nu$
obtained by a channel step of parameter $\lambda$. There is a finite
constant $C=C(\lambda)$ such that
\begin{align}
m(\mu\star\nu)
&\ge m(\mu)+m(\nu)
-C\bigl(h(\mu)m(\nu)+m(\mu)h(\nu)\bigr),\label{eq:local-m-lower}\\
h(\mu\star\nu)
&\le h(\mu)+h(\nu)+C\,m(\mu)m(\nu).\label{eq:local-h-upper}
\end{align}
The first inequality holds with $C=7$.
\end{lemma}
\begin{proof}
All expectations are over independent marginal posterior vectors $p,q$ of
laws $\mu,\nu$. Put
\[
x=Lp,\quad y=Lq,\quad s=x\cdot y,\quad
a=m(\mu),\; b=m(\nu),\quad \alpha=\tau(\mu),\;\beta=\tau(\nu).
\]
Because $p=\unif+L^{\mathsf T}x/4$ and likewise for $q$, the product rule
\eqref{eq:product-rule} becomes
\begin{equation}\label{eq:product-coordinates}
Z=1+s,\qquad LP=\frac{N}{1+s},\qquad
N=x+y+R,\quad R_i=x_jy_k+x_ky_j,
\end{equation}
where $\{i,j,k\}=\{1,2,3\}$. Each coordinate of $q$ is at least
$(1-\lambda)/4$, so
\begin{equation}\label{eq:denominator}
1+s\ge1-\lambda>0,\qquad -\lambda\le s\le3 .
\end{equation}
\emph{The quadratic statistic.} Using the marginal weight $Z$ in
\eqref{eq:product-rule},
\[
m(\mu\star\nu)=\E\frac{|N|^2}{1+s}.
\]
The second moments \eqref{eq:symmetric-moments} give
\[
\E|R|^2=\tfrac23ab,
\qquad \E s^2=\tfrac13ab,
\]
and the third-moment bookkeeping below (with $\E[x_1x_2x_3]=\alpha$ etc.)
gives
\[
\E[s\,x\cdot R]=2\alpha b,\quad
\E[s\,y\cdot R]=2a\beta,\quad
\E[s|R|^2]=6\alpha\beta .
\]
For example $x\cdot R=2(x_1x_2y_3+x_1x_3y_2+x_2x_3y_1)$; after
multiplication by $s=x\cdot y$ only multiples of $x_1x_2x_3$ survive the
expectation over $x$. Insert these into
$\E[|N|^2(1-s)]=\E|N|^2-\E[s|N|^2]$; the term $\E|R|^2$ cancels
$2\E s^2$, and all terms of degree one in either vector vanish. The result
is exact:
\begin{equation}\label{eq:quadratic-cancellation}
\E[|N|^2(1-s)]
=a+b-4(\alpha b+a\beta)-6\alpha\beta .
\end{equation}
Writing $(1+s)^{-1}=1-s+s^2/(1+s)$ we obtain
\begin{equation}\label{eq:exact-m-product}
m(\mu\star\nu)
=a+b-4(\alpha b+a\beta)-6\alpha\beta
+\E\frac{|N|^2s^2}{1+s}.
\end{equation}
The last term is nonnegative. Since $h(\mu)\le a$ and $h(\nu)\le b$, the
factor bound \eqref{eq:h-bound} gives
$|\alpha\beta|\le\tfrac12(h(\mu)b+a h(\nu))$, and also
$|\alpha b+a\beta|\le h(\mu)b+a h(\nu)$. Along with the nonnegativity of
the remainder in \eqref{eq:exact-m-product}, these yield
\begin{equation}\label{eq:lower-expanded}
m(\mu\star\nu)\ge a+b-7\bigl(h(\mu)b+a\,h(\nu)\bigr),
\end{equation}
which is \eqref{eq:local-m-lower} with $C=7$, with no sign assumption on
$\alpha,\beta$.
\emph{The third moment.} The corresponding product formula is
\[
\tau(\mu\star\nu)=\E\frac{N_1N_2N_3}{(1+s)^2}.
\]
Use the exact identity
\begin{equation}\label{eq:denominator-remainder}
(1+s)^{-2}-(1-2s)=\frac{s^2(3+2s)}{(1+s)^2}.
\end{equation}
The numerator $N_1N_2N_3$ is bounded and, by \eqref{eq:denominator}, the
multiplier in \eqref{eq:denominator-remainder} is at most a constant
depending only on $\lambda$ times $s^2$. Since $\E s^2=\tfrac13ab$, the
error in replacing $(1+s)^{-2}$ by $1-2s$ is at most $C_0(\lambda)ab$.
In the finite polynomial $N_1N_2N_3(1-2s)$ the only pure terms are
$x_1x_2x_3+y_1y_2y_3$; each carries coefficient $1$, because
$s\,x_1x_2x_3$ has zero mean. Every mixed monomial of degree one in one
vector has zero expectation, and every other mixed monomial has degree at
least two in each vector, so its absolute expectation is at most $ab$ by
independence and the monomial bound after \eqref{eq:symmetric-moments}.
Summing the finitely many coefficients and taking absolute values gives
\eqref{eq:local-h-upper} after enlarging $C(\lambda)$ to at least seven,
which proves both estimates.
\end{proof}
\section{Positive capacity implies reconstruction}
\label{sec:sufficiency}
Assume $\Capacity_{3,\lambda}(T)>0$ and choose an admissible flow $\theta$
of positive mass. We build degraded observations at every finite depth and
bound their information from below uniformly in that depth; the noise
level is fixed only after the total loss is estimated. Noisy boundary
observations also underlie robust reconstruction \cite{JM04}; here the
noise is chosen vertex by vertex from the flow.
\subsection{A flow profile and terminal observations}
For $0<\epsilon\le1$ let $\Theta(v)$ be the flow $\epsilon\theta$ entering
a nonroot vertex $v$, and define
\[
\Theta(\rho)=M:=\epsilon|\theta|,\qquad X_v=r^{-|v|}\Theta(v).
\]
Conservation becomes the linear identity
\begin{equation}\label{eq:linear-profile}
X_v=r\sum_{w\in\children(v)}X_w .
\end{equation}
Every edge of positive flow extends to an infinite ray, because at every
vertex with positive flow conservation forces a positive-flow child. Since
the energy is at most one on every ray, admissibility gives
$X_v\le\epsilon$ for every nonroot $v$; in particular $\theta(\rho,w)\le r$
for each child of the root and $|\theta|\le Br$. On each ray
$\xi=(v_0=\rho,v_1,v_2,\dots)$ we therefore have
\begin{equation}\label{eq:path-energy}
\sum_{j=0}^{\infty}X_{v_j}^2\le Q\epsilon^2,
\qquad Q=1+(Br)^2 .
\end{equation}
The extra $1$ in $Q$ accounts for $X_\rho=M$, which need not be at most
$\epsilon$.
Fix $n\ge1$. At every $v\in L_n$ observe the spin only after an extra
independent channel $P_{t_v}$ with parameter
\begin{equation}\label{eq:terminal-noise}
t_v=\sqrt{X_v/3}.
\end{equation}
These parameters are valid since $X_v\le\epsilon\le1$. For $|v|\le n$ let
$\widehat m_v,\widehat h_v$ be the statistics of the experiment about
$\sigma_v$ using these degraded terminal observations in its subtree (the
dependence on $n$ is suppressed). These laws and all their partial
products lie in $\calC$, as explained after Proposition~\ref{prop:companion}.
By channel scaling, at the terminal level,
\begin{equation}\label{eq:terminal-values}
\widehat m_v=X_v,\qquad \widehat h_v\le X_v
\qquad(|v|=n).
\end{equation}
Subadditivity in \eqref{eq:moment-saving}, channel scaling, and
\eqref{eq:linear-profile} then give inductively
\begin{equation}\label{eq:m-below-profile}
\widehat m_v\le X_v\qquad(|v|\le n).
\end{equation}
A vertex with no observed descendants has the uninformative experiment;
finite branches carry no flow, so early leaves and zero-flow subtrees are
consistent with these bounds.
\subsection{Local and accumulated losses}
For $|v|<n$ define the deficit from linear addition by
\begin{equation}\label{eq:deficit}
D_v=r\sum_{w\in\children(v)}\widehat m_w-\widehat m_v .
\end{equation}
We first prove that, for a fixed finite $C_1$ depending only on
$(B,\lambda)$,
\begin{align}
\widehat h_v&\le\lambda^3\sum_w\widehat h_w+C_1X_v^2,
\label{eq:h-recursion}\\
0\le D_v&\le C_1X_v\Bigl(\lambda^3\sum_w\widehat h_w+X_v^2\Bigr).
\label{eq:loss-recursion}
\end{align}
The coefficient of the propagated third moment is exactly $\lambda^3$; the
constant $C_1$ multiplies only the freshly created error.
Combine the child branches one at a time. After the edge channel, each
child branch is about the spin at $v$ with statistics
\[
b_w=r\widehat m_w,\qquad h'_w=\lambda^3\widehat h_w .
\]
Every partial product has $m$ at most the sum of its $b_w$'s, hence at
most $X_v$. Applying \eqref{eq:local-h-upper} at each addition gives the
partial bound
\[
h\le\sum_wh'_w+C\,X_v\sum_wb_w\le H+CX_v^2,\qquad H=\sum_wh'_w,
\]
proving \eqref{eq:h-recursion} after enlarging $C_1$. Every addition has
nonnegative deficit by Proposition~\ref{prop:companion}, and its deficit is
at most $C((H+CX_v^2)b_w+X_vh'_w)$ by \eqref{eq:local-m-lower}. Summing and
using $\sum_wb_w\le X_v$ gives $D_v\le2CX_vH+C^2X_v^3$, which proves
\eqref{eq:loss-recursion}. At every use of Lemma~\ref{lem:local-moments}
the second input is a single child branch after its channel of parameter
$\lambda$, as required.
Write $u\succeq v$ when $u$ is a descendant of $v$, including $u=v$.
Iterating \eqref{eq:h-recursion} inside \eqref{eq:loss-recursion} and using
\eqref{eq:terminal-values} gives, for $i=|v|<n$,
\begin{equation}\label{eq:unfolded-loss}
D_v\le C_2X_v\Bigl(
\sum_{\substack{u\succeq v\\|u|<n}}\lambda^{3(|u|-i)}X_u^2
+\sum_{\substack{u\succeq v\\|u|=n}}\lambda^{3(n-i)}X_u\Bigr),
\end{equation}
where $C_2=\max\{C_1,C_1^2\}$ suffices. At each internal descendant the
term $C_1X_u^2$ is inserted once and then propagated with a factor
$\lambda^3$ per edge; no power of $C_1$ grows with depth.
Telescoping the deficits \eqref{eq:deficit} over the finite tree above
$L_n$ yields
\begin{equation}\label{eq:loss-telescope}
\widehat m_\rho
=r^n\sum_{v\in L_n}X_v-\sum_{|v|<n}r^{|v|}D_v
=M-\sum_{|v|<n}r^{|v|}D_v,
\end{equation}
the last equality by conservation of $\Theta$. It remains to show that the
total loss is at most a fixed fraction of $M$, uniformly in $n$.
\subsection{Averaging the losses along a flow path}
Sample a vertex of $L_n$ with probabilities $\Theta(v)/M$ and let
$(V_0=\rho,V_1,\dots,V_n)$ be its ancestors. Conservation gives
$\sum_{v\in L_j}\Theta(v)=M$ for every $j\le n$, hence
\begin{equation}\label{eq:path-marginals}
\Prob(V_j=u)=\frac{\Theta(u)}M\qquad(u\in L_j).
\end{equation}
This remains true with early leaves, whose flow is zero. Every path of
positive probability extends to an infinite ray, so \eqref{eq:path-energy}
bounds $\sum_iX_{V_i}^2$.
For $i\le j$ and $|u|=j$ the identity behind the summable path kernel is
\begin{equation}\label{eq:weight-identity}
r^i\lambda^{3(j-i)}X_u=\lambda^{j-i}\Theta(u).
\end{equation}
The unique depth-$i$ ancestor of $u$ is specified once $u$ is chosen, so
for $0\le i\le j<n$,
\begin{align}
&\sum_{|v|=i}r^iX_v\!\!\sum_{\substack{u\succeq v\\|u|=j}}
\lambda^{3(j-i)}X_u^2
=M\lambda^{j-i}\,\E[X_{V_i}X_{V_j}],
\label{eq:internal-path-sum}\\
&\sum_{|v|=i}r^iX_v\!\!\sum_{\substack{u\succeq v\\|u|=n}}
\lambda^{3(n-i)}X_u
=M\lambda^{n-i}\,\E X_{V_i}.
\label{eq:terminal-path-sum}
\end{align}
Combining these with \eqref{eq:unfolded-loss} gives
\begin{equation}\label{eq:total-path-loss}
\sum_{|v|<n}r^{|v|}D_v
\le C_2M\,\E\Bigl[
\sum_{0\le i\le j<n}\lambda^{j-i}X_{V_i}X_{V_j}
+\sum_{0\le i<n}\lambda^{n-i}X_{V_i}\Bigr].
\end{equation}
For each fixed difference $k=j-i\ge0$, Cauchy--Schwarz and
\eqref{eq:path-energy} give, on every path in the support,
\[
\sum_{i=0}^{n-1-k}X_{V_i}X_{V_{i+k}}
\le\Bigl(\sum_{i=0}^{n-1-k}X_{V_i}^2\Bigr)^{1/2}
\Bigl(\sum_{i=0}^{n-1-k}X_{V_{i+k}}^2\Bigr)^{1/2}
\le Q\epsilon^2 .
\]
Each individual $X_{V_i}$ is at most $\sqrt Q\,\epsilon$. Summing the
geometric weights in \eqref{eq:total-path-loss}, the bracketed expectation
is at most
\begin{equation}\label{eq:uniform-loss-bound}
\frac{Q\epsilon^2}{1-\lambda}+\frac{\sqrt Q\,\epsilon}{1-\lambda}.
\end{equation}
Choose $\epsilon\in(0,1]$ so small that $C_2$ times this expression is at
most $\tfrac12$; the choice does not depend on $n$.
Equations~\eqref{eq:loss-telescope} and \eqref{eq:total-path-loss} now give
\[
\widehat m_\rho\ge M/2>0\qquad\text{for every }n\ge1 .
\]
The original, undegraded level observation has at least this much quadratic
information by data processing, so by \eqref{eq:expected-TV}
\[
a_n(T,\lambda)\ge M/16\qquad(n\ge1).
\]
Hence $a_\infty(T,\lambda)>0$, proving the second implication of
Theorem~\ref{thm:main}. The degraded experiments may depend on $n$; the
argument needs only one common positive lower bound at every depth, not
convergence of the experiments or monotonicity in $n$.
\section{Relation to earlier work}
\label{sec:history}
The second-eigenvalue scale in tree broadcasting goes back to
Kesten--Stigum \cite{KS66}. On a regular tree with $d$ children per vertex
the corresponding bound gives reconstruction when $d\lambda^2>1$
\cite{MP03}. Evans, Kenyon, Peres, and Schulman \cite{EKPS00} tied
broadcasting, the Ising model, and electrical capacity together. For Potts
channels, Sly \cite{Sly11} proved sharpness of the second-eigenvalue bound
for three states on regular trees of large degree (including
nonreconstruction at equality) and nonsharpness for five or more states.
Mossel, Sly, and Sohn \cite{MSS25} proved three- and four-state
nonreconstruction at and below the bound for Galton--Watson families of
large mean degree. At four states the quadratic correction vanishes, so
finer, higher-order terms decide the question \cite{Sly11,MSS25}.
Pemantle and Peres \cite{PP10} formulated critical Ising criteria on
arbitrary trees using nonlinear capacities and concave recursions. Their
free-boundary criterion uses $L^2$ capacity with squared resistances; their
plus-boundary criterion uses $L^3$ capacity with unsquared resistances
\cite[Theorems~2.1--2.2]{PP10}. The present four-state criterion has the
$L^3$ exponent but the squared resistance $\lambda^{-2|e|}$. The
recursion \eqref{eq:label-recursion} is the $p=3$ instance of their
capacity recursion \cite[Lemma~3.1, Corollary~3.4]{PP10}; the flow
construction in Lemma~\ref{lem:flow} is given directly. The single external
probabilistic input is Proposition~\ref{prop:companion} from
\cite{OpenAI26Potts}; all other arguments are self-contained above.
\begin{thebibliography}{99}
\bibitem[KS66]{KS66} H.~Kesten and B.~P.~Stigum, \emph{Additional limit
theorems for indecomposable multidimensional Galton--Watson processes},
Ann. Math. Statist. \textbf{37} (1966), 1463--1481.
\bibitem[EKPS00]{EKPS00} W.~Evans, C.~Kenyon, Y.~Peres, and L.~J.~Schulman,
\emph{Broadcasting on trees and the Ising model}, Ann. Appl. Probab.
\textbf{10} (2000), 410--433.
\bibitem[MP03]{MP03} E.~Mossel and Y.~Peres, \emph{Information flow on
trees}, Ann. Appl. Probab. \textbf{13} (2003), 817--844.
\bibitem[MM06]{MM06} M.~M\'ezard and A.~Montanari, \emph{Reconstruction on
trees and spin glass transition}, J. Stat. Phys. \textbf{124} (2006),
1317--1350.
\bibitem[JM04]{JM04} S.~Janson and E.~Mossel, \emph{Robust reconstruction
on trees is determined by the second eigenvalue}, Ann. Probab. \textbf{32}
(2004), 2630--2649.
\bibitem[PP10]{PP10} R.~Pemantle and Y.~Peres, \emph{The critical Ising
model on trees, concave recursions and nonlinear capacity}, Ann. Probab.
\textbf{38} (2010), 184--206.
\bibitem[Sly11]{Sly11} A.~Sly, \emph{Reconstruction for the Potts model},
Ann. Probab. \textbf{39} (2011), 1365--1406.
\bibitem[MSS25]{MSS25} E.~Mossel, A.~Sly, and Y.~Sohn, \emph{Exact phase
transitions for stochastic block models and reconstruction on trees}, Ann.
Probab. \textbf{53} (2025), 967--1018.
\bibitem[OAI26]{OpenAI26Potts} OpenAI, \emph{The reconstruction threshold
for the ferromagnetic four-state Potts model}, OpenAI Math Release preprint,
2026.
\end{thebibliography}
\end{document}