==== TABLE OF CONTENTS ====
A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//main.tex
A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//references.bib
===========================

==== BEGIN A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\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}
\input{glyphtounicode}
\input{glyphtounicode-cmex}
\pdfgentounicode=1
\pdftrailerid{}
\pdfsuppressptexinfo=15
\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}
\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}
For the ferromagnetic four-state broadcast model with $0<\lambda<1$,
we prove that reconstruction on a bounded-degree deterministic rooted
tree occurs exactly when its $L^3$ capacity with edge resistances
$\lambda^{-2|e|}$ is positive. This gives an exact criterion without
regularity or growth-rate assumptions on the tree, including at the
exponential critical boundary.
\end{abstract}

\section{Introduction}
\label{sec:introduction}

Let $T$ be an infinite locally finite rooted tree with root $\rho$.
Assume that every vertex has at most $B$ children, where $B$ is a
fixed positive integer; vertices with zero or one child are allowed.
Write $|v|$ for the depth of a vertex, $\children(v)$ for its
children, and $L_n=\{v:|v|=n\}$. The tree is deterministic and
known to the observer.

Fix $0<\lambda<1$. Give the root a uniform spin in $[4]$, and
transmit spins independently along edges conditional on their
parent spins, using
\begin{equation}\label{eq:channel}
 P_\lambda(j\mid i)
 =\lambda\mathbf1_{\{i=j\}}+\frac{1-\lambda}{4}.
\end{equation}
For the uniform probability vector $\unif=(1/4,1/4,1/4,1/4)$, put
\[
 a_n(T,\lambda)=
 \E\,\TV\bigl(\Prob(\sigma_\rho\in\cdot\mid\sigma_{L_n}),
                    \unif\bigr),
 \qquad
 \TV(p,\unif)=\frac12\sum_{i=1}^4|p_i-1/4|.
\]
Data processing makes $a_n$ nonincreasing. We say that
\emph{reconstruction occurs} if its limit $a_\infty(T,\lambda)$
is positive.

A nonnegative flow $\theta$ to infinity assigns a nonnegative
number to each edge, with incoming flow equal to the sum of outgoing
flows at every nonroot vertex. Its mass is
\[
 |\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$ denote the infinite rays from the root.
Define
\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\left\{|\theta|:
       \sup_{\xi\in\partial T}V_\lambda(\theta,\xi)\leq1\right\}.
       \label{eq:capacity}
\end{align}
The zero flow is allowed. This is the $L^3$ nonlinear capacity
with edge resistances $\lambda^{-2|e|}$: in the standard $L^p$
normalization, the path potential has exponent $p-1$
\cite[Section~2]{PP10}.

\begin{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}

There is no regularity or growth-rate assumption on the tree.
In particular, the criterion applies at the exponential
Kesten--Stigum boundary, where an exponential-growth test alone
does not settle the question. The exclusion of $\lambda=1$ is
essential: an infinite ray then reconstructs perfectly, whereas
its capacity in \eqref{eq:capacity} is zero.

\subsection*{History and relation to earlier work}
The second-eigenvalue scale in tree broadcasting originates in
the branching-process work of Kesten and Stigum \cite{KS66}.
For a regular tree with $d$ children per vertex, the corresponding
bound guarantees reconstruction when $d\lambda^2>1$
\cite{MP03}. Evans, Kenyon, Peres, and Schulman
\cite{EKPS00} developed the relation between broadcasting, the
Ising model, and electrical capacity. For Potts channels, Sly
\cite{Sly11} proved sharpness of the second-eigenvalue bound for
three states on regular trees of sufficiently large degree,
including nonreconstruction at equality, and proved nonsharpness
for at least five states. Mossel, Sly, and Sohn \cite{MSS25}
established three- and four-state nonreconstruction at and below
the bound for Galton--Watson families of sufficiently large mean
degree, under hypotheses covering regular and Poisson offspring.
At four states the quadratic correction vanishes, making
higher-order terms decisive \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 channel resistances, whereas their plus-boundary
criterion uses $L^3$ capacity with unsquared channel resistances
\cite[Theorems~2.1--2.2]{PP10}. The present four-state
reconstruction criterion has the $L^3$ exponent but the squared
channel resistance $\lambda^{-2|e|}$. The nonlinear recursion
used below is the $p=3$ instance of their capacity recursion
\cite[Lemma~3.1 and Corollary~3.4]{PP10}; we give the needed
flow construction directly.

Our essential probabilistic input is the preserved class of
posterior laws and its moment-saving inequality from
\emph{The Reconstruction Threshold for the Ferromagnetic Four-State
Potts Model} \cite[Proposition~3.2]{OpenAI26Potts}. That companion
studies the threshold on regular and Poisson Galton--Watson trees.
Its posterior-law statement allows arbitrary channel parameters
and conditionally independent products, which is the scope
needed here. We state this input precisely in
Section~\ref{sec:posteriors}; its polynomial-certificate proof is
not repeated. All remaining arguments for Theorem~\ref{thm:main}
are proved below.

\subsection*{Proof strategy}
We measure a posterior $p$'s information by the quadratic statistic
$m=4\E|p-\unif|^2$. The companion inequality saves a cubic term when two
informative branches are combined. For the implication from
reconstruction to capacity, a change of variables $m\mapsto m+Km^3$
turns this branching saving into a nonlinear inequality that also
has a strict saving at one-child vertices. A direct telescoping
construction then produces an admissible flow of positive mass.

The converse starts from a flow and scales it down. At each
observation level we add independent noise, chosen separately at
each vertex $v$ so that its terminal information equals the
scaled flow entering $v$ divided by $\lambda^{2|v|}$.
The resulting information stays below this depth-weighted flow profile.
To bound what is lost, we track a signed third moment in addition
to $m$. In the four-state coordinates, the mixed quadratic term
in the product formula cancels. The remaining loss is controlled
by the third moment, whose propagation along an edge has factor
$\lambda^3$, rather than $\lambda^2$.

Sampling a ray according to the flow converts the accumulated
loss into sums along a single path. The two propagation factors
leave a summable kernel $\lambda^{j-i}$ between depths $i$ and
$j$. The capacity bound controls its quadratic path sum, and a
single choice of noise scale works at every observation depth.
This flow-calibrated degradation and third-moment estimate avoid
any need for comparable branch sizes or a strict exponential
growth inequality.

Section~\ref{sec:posteriors} introduces the posterior calculus
and the companion input. Section~\ref{sec:necessity} constructs
the flow from reconstruction. Section~\ref{sec:moments} proves
the local moment estimates, and Section~\ref{sec:sufficiency}
uses them to prove the converse. Throughout, set
\[
 r=\lambda^2\in(0,1).
\]

\section{Posterior experiments and the companion input}
\label{sec:posteriors}

An experiment consists of an observation about a uniform input
spin in $[4]$. Let $p$ be its posterior vector and $\mu$ 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. Define
\[
 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, vector norms are Euclidean. The rows of $L$ are
orthogonal and span the orthogonal complement of the constant
vector. Consequently
\begin{equation}\label{eq:posterior-bounds}
 A(p)=4|p-\unif|^2,\qquad 0\leq A(p)\leq3,
 \qquad \frac18A(p)\leq\TV(p,\unif)\leq\frac12\sqrt{A(p)}.
\end{equation}
The lower bound follows from $|p_i-1/4|^2\leq|p_i-1/4|$;
the upper bound is Cauchy--Schwarz. In expectation,
\begin{equation}\label{eq:expected-TV}
 \frac18m(\mu)\leq\E\,\TV(p,\unif)
       \leq\frac12\sqrt{m(\mu)}.
\end{equation}
Under degradation of an observation, the new posterior is the
conditional expectation of the old one given the new observation.
Convexity of $A$ therefore makes $m$ nonincreasing under data
processing.

\subsection{Channels and products}

In a channel step with parameter $t\in[0,1]$, first transmit a
uniform input $I$ to $J$ through $P_t$, then observe an experiment
about $J$. The uniform distribution is stationary and the channel
is symmetric, so the posterior about $I$ is
$\unif+t(p-\unif)$. Thus
\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 completely revealing experiment has $m=3$, while the
uninformative experiment has $m=h=0$.

If two observations are independent conditional on the same
input spin, write $\mu\star\nu$ for their combined posterior law.
The normalized-product rule below is standard in posterior
recursions for reconstruction; see M\'ezard and Montanari
\cite[Sections~2.2--2.4]{MM06}.
Sample $p,q$ independently from their marginal posterior laws
$\mu,\nu$. The joint marginal law of the observations is obtained
by weighting this 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}
The value of $P$ at $Z=0$ is irrelevant. Indeed, the likelihood
of each observation conditional on input $i$, relative to its
marginal law, is $4p_i$ or $4q_i$. Formula~\eqref{eq:product-rule}
follows by averaging their product over the uniform input.
In particular, $\E Z=1$. Symmetry is preserved by both channel
steps and products.

The columns of $L$ are the four sign triples whose product is
one. Permuting these columns acts on $x$ by coordinate permutations
and even sign changes. For any symmetric posterior law, it follows
that
\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 expectation. Also $|x_i|\leq1$. Any coordinate monomial
of degree at least two is therefore bounded in absolute value
by $|x|^2$: retain two factors and use
$|x_ix_j|\leq(x_i^2+x_j^2)/2$, or $|x_i|^2$ when the indices
agree. In particular,
\begin{equation}\label{eq:h-bound}
 h(\mu)\leq m(\mu).
\end{equation}

\subsection{The moment-saving input}

We use the following statement from the companion manuscript.
The existence and preservation of the class, not only symmetry,
are essential to its upper bound.

\begin{proposition}[Companion input, {\cite[Proposition~3.2 and Equations~(3.8)--(3.9)]{OpenAI26Potts}}]
\label{prop:companion}
There is a class $\calC$ of symmetric posterior laws containing
the revealing and uninformative laws and preserved by channel
steps with any parameter in $[0,1]$ and by conditionally independent
products. For $\mu,\nu\in\calC$,
\begin{equation}\label{eq:moment-saving}
 m(\mu\star\nu)\leq m(\mu)+m(\nu)
 -c\left(\E_\mu[A^2]m(\nu)+m(\mu)\E_\nu[A^2]\right),
 \qquad c=\frac1{1000}.
\end{equation}
\end{proposition}

Every finite-depth subtree experiment used here 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, membership follows
from the revealing law and channel closure; an empty observation
is uninformative. Working toward the subtree root uses channel
steps and products, with conditional independence supplied by the
broadcast process. The same argument covers every partial product
at a vertex. No assertion about a limiting posterior law belonging
to $\calC$ will be needed.

\section{From reconstruction to capacity}
\label{sec:necessity}

The nonlinear capacity recursion of Pemantle and Peres
\cite[Lemma~3.1 and Corollary~3.4]{PP10} has a particularly 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
\begin{equation}\label{eq:label-recursion}
 z_v\leq\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 potential
\eqref{eq:potential} is at most one on every ray. In particular,
$\Capacity_{3,\lambda}(T)\geq z_\rho$.
\end{lemma}
\begin{proof}
At each vertex choose coefficients
\[
 0\leq d_{vw}\leq\frac{r}{\sqrt{1+z_w^2}}
 \quad\text{such that}\quad
 z_v=\sum_{w\in\children(v)}d_{vw}z_w.
\]
If the upper-bound sum is positive, multiply all its coefficients
by the ratio of $z_v$ to that sum; otherwise all labels in the
displayed equality are zero and take all coefficients to be zero.
Set $\ell_\rho=1$, $\ell_w=\ell_vd_{vw}$ recursively, and define
\[
 \theta(v,w)=\ell_wz_w.
\]
The displayed equality gives conservation at every nonroot vertex
and mass $z_\rho$ at the root. Put $g_v=r^{-|v|}\ell_v$. Then
\[
 g_w^2(1+z_w^2)\leq g_v^2,
 \qquad
 \bigl(r^{-|w|}\theta(v,w)\bigr)^2
       =(g_wz_w)^2\leq g_v^2-g_w^2.
\]
Summing along any finite initial segment of a ray gives a bound
by $g_\rho^2=1$. Monotone convergence of the nonnegative sums
proves the assertion for every infinite ray.
\end{proof}

For a vertex $v$, let $m_v^{(n)}$ be the quadratic information
about $\sigma_v$ obtained from its descendants at distance $n$,
with $m_v^{(0)}=3$. Data processing gives limits
\[
 m_v=\lim_{n\to\infty}m_v^{(n)}\in[0,3].
\]
If reconstruction occurs, \eqref{eq:expected-TV} implies
$m_\rho>0$. We show that these limiting numbers yield labels
satisfying Lemma~\ref{lem:flow} with a positive root label.

For a fixed vertex $v$, put
\[
 b_w=rm_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 fewer than two children are present. Then
\begin{equation}\label{eq:pair-saving}
 m_v\leq S-cD.
\end{equation}
At finite depth the parent information is $m_v^{(n+1)}$, and
the child values after their edge channels are $b_w=rm_w^{(n)}$.
Choose any pair of children and combine their branch experiments first.
Jensen's inequality gives $\E A^2\geq(\E A)^2$, so
Proposition~\ref{prop:companion} saves at least
$c b_wb_{w'}(b_w+b_{w'})$. Combine the remaining children using
the subadditivity part of the same proposition. Maximize over the
pair and pass to the limit. All sums and maxima are finite. With
zero or one child, the empty observation or channel scaling gives
the assertion directly.

There are at most $B^3$ ordered triples of children, and every
mixed product in $S^3$ is at most the largest $b_w$ squared times
the second largest, hence at most $D$. Therefore
\begin{equation}\label{eq:cubic-sum}
 S^3\leq\sum_w b_w^3+B^3D.
\end{equation}
Choose $K>0$ with $KB^3\leq c$ and set $y_v=m_v+Km_v^3$.
Since $m_v\leq S$, Equations~\eqref{eq:pair-saving} and
\eqref{eq:cubic-sum} yield
\begin{align}
 y_v&\leq S-cD+KS^3
       \leq S+K\sum_w b_w^3\notag\\
    &=r\sum_w y_w-Kr(1-r^2)\sum_wm_w^3.
       \label{eq:renormalized-saving}
\end{align}
This correction supplies a saving even at a one-child vertex,
where the original pair term vanishes: the positive factor is
$r-r^3$.

The bound $m_w\leq3$ gives $y_w\leq(1+9K)m_w$. With
\[
 \delta=\frac{K(1-r^2)}{(1+9K)^3}>0,
\]
Equation~\eqref{eq:renormalized-saving} implies
\[
 y_v\leq r\sum_wy_w(1-\delta y_w^2)
      \leq r\sum_w\frac{y_w}{\sqrt{1+2\delta y_w^2}}.
\]
The second inequality is the tangent bound
$(1+2t)^{-1/2}\geq1-t$ for $t\geq0$. Thus
$z_v=\sqrt{2\delta}\,y_v$ satisfies
\eqref{eq:label-recursion}, with $z_\rho>0$.
Lemma~\ref{lem:flow} proves positive capacity and completes the
first implication of Theorem~\ref{thm:main}.

\section{Local estimates for information loss}
\label{sec:moments}

For the converse, subadditivity alone is not enough: we must
bound the information lost when branches are combined. The next
lemma uses only symmetry and one channel-smoothed input. Unlike
Proposition~\ref{prop:companion}, it does not require 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)
 &\geq m(\mu)+m(\nu)
   -C\bigl(h(\mu)m(\nu)+m(\mu)h(\nu)\bigr),
       \label{eq:local-m-lower}\\
 h(\mu\star\nu)
 &\leq 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 in this proof are over independent marginal
posterior vectors $p,q$ of laws $\mu,\nu$. Put
\[
 x=Lp,\qquad y=Lq,\qquad s=x\cdot y,
 \qquad a=m(\mu),\quad b=m(\nu),
 \quad \alpha=\tau(\mu),\quad\beta=\tau(\nu).
\]
Since $p=\unif+L^{\mathsf T}x/4$ and similarly 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,\qquad 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\geq1-\lambda>0,\qquad -\lambda\leq s\leq3.
\end{equation}

\paragraph{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 in \eqref{eq:symmetric-moments} give
\[
 \E|R|^2=\frac23ab,\qquad \E s^2=\frac13ab.
\]
In the expansion of $\E[|N|^2(1-s)]$, the term
$\E|R|^2$ therefore cancels $2\E s^2$.
Terms of degree one in either vector have zero expectation.
For the remaining terms,
\[
 \E[s\,x\cdot R]=2\alpha b,\qquad
 \E[s\,y\cdot R]=2a\beta,\qquad
 \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$, only terms proportional to
$x_1x_2x_3$ survive expectation over $x$. The last identity follows in
the same way by retaining only terms with all three indices in
each vector. Thus the expansion is exactly
\begin{equation}\label{eq:quadratic-cancellation}
 \E[|N|^2(1-s)]
 =a+b-4(\alpha b+a\beta)-6\alpha\beta.
\end{equation}
As $(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 final term is nonnegative. Moreover, \eqref{eq:h-bound}
implies
\[
 |\alpha\beta|\leq
 \frac12\bigl(h(\mu)b+a h(\nu)\bigr).
\]
This proves \eqref{eq:local-m-lower} with constant seven,
without any sign assumption on $\alpha$ or $\beta$.

\paragraph{The third moment.}
The corresponding product formula is
\[
 \tau(\mu\star\nu)=\E\frac{N_1N_2N_3}{(1+s)^2}.
\]
Use the exact remainder
\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
\eqref{eq:denominator} bounds the multiplier in
\eqref{eq:denominator-remainder} by a constant depending only
on $\lambda$ times $s^2$. The error in replacing the denominator
factor by $1-2s$ is consequently 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$. Every mixed monomial of degree
one in one vector has zero expectation. 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 following \eqref{eq:symmetric-moments}. Summing the finitely
many coefficients and taking absolute values proves
\eqref{eq:local-h-upper}. Increase the common $C(\lambda)$ to
at least seven to obtain both estimates.
\end{proof}

\section{From capacity to reconstruction}
\label{sec:sufficiency}

Assume $\Capacity_{3,\lambda}(T)>0$ and choose an admissible flow
$\theta$ of positive mass. We construct degraded observations at
every finite depth and bound their information from below
uniformly in that depth. The noise scale will be fixed only after
the total loss has been estimated.
Noisy boundary observations also underlie robust reconstruction
\cite{JM04}. Here we choose the noise separately at each vertex
from the flow and use the resulting information to bound that
of the original observations.

\subsection{A flow profile and terminal observations}

For $0<\epsilon\leq1$, 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
\begin{equation}\label{eq:linear-profile}
 X_v=r\sum_{w\in\children(v)}X_w.
\end{equation}
Every positive-flow edge extends to an infinite ray: at every
positive-flow vertex, conservation gives at least one positive-flow
child. Hence admissibility implies $X_v\leq\epsilon$ for all
nonroot vertices. In particular, $\theta(\rho,w)\leq r$ for
each child of the root, and $|\theta|\leq Br$.
On every ray $\xi=(v_0=\rho,v_1,v_2,\ldots)$, we therefore have
\begin{equation}\label{eq:path-energy}
 \sum_{j=0}^{\infty}X_{v_j}^2\leq Q\epsilon^2,
 \qquad Q=1+(Br)^2.
\end{equation}
The extra term in $Q$ is needed
because $X_\rho=M$ need not be at most $\epsilon$.

Fix $n\geq1$. At each $v\in L_n$, observe its spin only after
an additional independent channel $P_{t_v}$, where
\begin{equation}\label{eq:terminal-noise}
 t_v=\sqrt{X_v/3}.
\end{equation}
These are valid parameters since $X_v\leq\epsilon\leq1$.
For $|v|\leq 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 their partial products
belong to $\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\leq X_v
 \qquad (|v|=n).
\end{equation}
Subadditivity in \eqref{eq:moment-saving}, channel scaling,
and \eqref{eq:linear-profile} give inductively
\begin{equation}\label{eq:m-below-profile}
 \widehat m_v\leq X_v\qquad (|v|\leq 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, with a fixed finite $C_1$ depending only
on $B,\lambda$,
\begin{align}
 \widehat h_v
 &\leq\lambda^3\sum_w\widehat h_w+C_1X_v^2,
      \label{eq:h-recursion}\\
 0\leq D_v
 &\leq C_1X_v\left(\lambda^3\sum_w\widehat h_w+X_v^2\right).
      \label{eq:loss-recursion}
\end{align}
The coefficient of the propagated third moment is exactly
$\lambda^3$; the constant $C_1$ multiplies only the new error.

Combine the child branches one at a time. After the edge channel,
their individual statistics, now about the spin at $v$, are
\[
 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\leq\sum_w h'_w+C X_v\sum_wb_w
   \leq H+CX_v^2,\qquad H=\sum_wh'_w.
\]
The sums on the right may be taken over all children, so this
also proves \eqref{eq:h-recursion} after increasing $C_1$.
Every addition has nonnegative deficit by
Proposition~\ref{prop:companion}. Its deficit is at most
\[
 C\bigl((H+CX_v^2)b_w+X_vh'_w\bigr)
\]
by \eqref{eq:local-m-lower}. Summing and using
$\sum_wb_w\leq X_v$ gives
$D_v\leq2CX_vH+C^2X_v^3$, proving
\eqref{eq:loss-recursion}. The second input at every use of
Lemma~\ref{lem:local-moments} 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} in
\eqref{eq:loss-recursion} and using \eqref{eq:terminal-values}
gives, for $i=|v|<n$,
\begin{equation}\label{eq:unfolded-loss}
 D_v\leq C_2X_v\left(
    \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
                   \right).
\end{equation}
Here $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$ now 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 uses conservation of $\Theta$. It remains to
show that this 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,\ldots,V_n)$ be its ancestors. Conservation
gives $\sum_{v\in L_j}\Theta(v)=M$ for every $j\leq n$ and
therefore
\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: their flow is zero. Every
path with positive probability extends to an infinite ray, so
\eqref{eq:path-energy} bounds the sum of its $X_{V_i}^2$.

For $i\leq j$ and $|u|=j$, the identity responsible for 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. Thus, for $0\leq i\leq j<n$,
\begin{align}
 &\sum_{|v|=i}r^iX_v
       \sum_{\substack{u\succeq v\\|u|=j}}
                      \lambda^{3(j-i)}X_u^2\notag\\
 &\hspace{35mm}=M\lambda^{j-i}\E[X_{V_i}X_{V_j}],
       \label{eq:internal-path-sum}
\end{align}
whereas the terminal terms satisfy
\begin{equation}\label{eq:terminal-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}.
\end{equation}
Combining these identities with \eqref{eq:unfolded-loss} gives
\begin{equation}\label{eq:total-path-loss}
 \sum_{|v|<n}r^{|v|}D_v
 \leq C_2M\,\E\left[
       \sum_{0\leq i\leq j<n}\lambda^{j-i}X_{V_i}X_{V_j}
       +\sum_{0\leq i<n}\lambda^{n-i}X_{V_i}
                        \right].
\end{equation}

For each fixed difference $k=j-i\geq0$, 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}}
 \leq
 \left(\sum_{i=0}^{n-1-k}X_{V_i}^2\right)^{1/2}
 \left(\sum_{i=0}^{n-1-k}X_{V_{i+k}}^2\right)^{1/2}
 \leq 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 expectation there 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 $1/2$. The choice is independent of $n$.
Equations~\eqref{eq:loss-telescope} and
\eqref{eq:total-path-loss} now give
\[
 \widehat m_\rho\geq M/2>0\qquad\text{for every }n\geq1.
\]
The original, undegraded level observation has at least this
much quadratic information by data processing. By
\eqref{eq:expected-TV},
\[
 a_n(T,\lambda)\geq M/16\qquad(n\geq1).
\]
Thus $a_\infty(T,\lambda)>0$, proving the remaining implication
of Theorem~\ref{thm:main}. The degraded experiments may vary with
$n$; the proof requires only the same positive lower bound at
each depth, not their convergence or mutual monotonicity.

\bibliographystyle{amsplain}
\bibliography{references}
\end{document}
==== END A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//main.tex ====

==== BEGIN A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//references.bib ====
@article{KS66,
  author = {Kesten, Harry and Stigum, Bernt P.},
  title = {Additional limit theorems for indecomposable multidimensional {Galton--Watson} processes},
  journal = {Annals of Mathematical Statistics},
  volume = {37},
  number = {6},
  pages = {1463--1481},
  year = {1966},
  doi = {10.1214/aoms/1177699139}
}

@article{Lyons90,
  author = {Lyons, Russell},
  title = {Random walks and percolation on trees},
  journal = {Annals of Probability},
  volume = {18},
  number = {3},
  pages = {931--958},
  year = {1990},
  doi = {10.1214/aop/1176990730}
}

@article{BRZ95,
  author = {Bleher, Pavel M. and Ruiz, Jean and Zagrebnov, Valentin A.},
  title = {On the purity of the limiting {Gibbs} state for the {Ising} model on the {Bethe} lattice},
  journal = {Journal of Statistical Physics},
  volume = {79},
  number = {1--2},
  pages = {473--482},
  year = {1995},
  doi = {10.1007/BF02179399}
}

@article{EKPS00,
  author = {Evans, William and Kenyon, Claire and Peres, Yuval and Schulman, Leonard J.},
  title = {Broadcasting on trees and the {Ising} model},
  journal = {Annals of Applied Probability},
  volume = {10},
  number = {2},
  pages = {410--433},
  year = {2000},
  doi = {10.1214/aoap/1019487349}
}

@article{Mossel01,
  author = {Mossel, Elchanan},
  title = {Reconstruction on trees: Beating the second eigenvalue},
  journal = {Annals of Applied Probability},
  volume = {11},
  number = {1},
  pages = {285--300},
  year = {2001},
  doi = {10.1214/aoap/998926994}
}

@article{MP03,
  author = {Mossel, Elchanan and Peres, Yuval},
  title = {Information flow on trees},
  journal = {Annals of Applied Probability},
  volume = {13},
  number = {3},
  pages = {817--844},
  year = {2003},
  doi = {10.1214/aoap/1060202828}
}

@article{MM06,
  author = {M{\'e}zard, Marc and Montanari, Andrea},
  title = {Reconstruction on trees and spin glass transition},
  journal = {Journal of Statistical Physics},
  volume = {124},
  number = {6},
  pages = {1317--1350},
  year = {2006},
  doi = {10.1007/s10955-006-9162-3}
}

@article{JM04,
  author = {Janson, Svante and Mossel, Elchanan},
  title = {Robust reconstruction on trees is determined by the second eigenvalue},
  journal = {Annals of Probability},
  volume = {32},
  number = {3B},
  pages = {2630--2649},
  year = {2004},
  doi = {10.1214/009117904000000153}
}

@article{PP10,
  author = {Pemantle, Robin and Peres, Yuval},
  title = {The critical {Ising} model on trees, concave recursions and nonlinear capacity},
  journal = {Annals of Probability},
  volume = {38},
  number = {1},
  pages = {184--206},
  year = {2010},
  doi = {10.1214/09-AOP482}
}

@article{Sly11,
  author = {Sly, Allan},
  title = {Reconstruction for the {Potts} model},
  journal = {Annals of Probability},
  volume = {39},
  number = {4},
  pages = {1365--1406},
  year = {2011},
  doi = {10.1214/10-AOP584}
}

@article{MSS25,
  author = {Mossel, Elchanan and Sly, Allan and Sohn, Youngtak},
  title = {Exact phase transitions for stochastic block models and reconstruction on trees},
  journal = {Annals of Probability},
  volume = {53},
  number = {3},
  pages = {967--1018},
  year = {2025},
  doi = {10.1214/24-AOP1723},
  note = {Author preprint: arXiv:2212.03362}
}

@misc{OpenAI26Potts,
  author = {{OpenAI}},
  title = {{The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026/four-state-potts.pdf}{OAI:The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026}},
  year = {2026}
}
==== END A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees//references.bib ====