==== TABLE OF CONTENTS ====
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//main.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//references.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/01-introduction.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/02-experiments.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/03-cone.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/04-tree-decay.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/05-polynomial-certificates.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/06-finite-verification.tex
The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/07-code-appendix.tex
===========================
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//main.tex ====
\newcommand{\DoNotLoadEpstopdf}{}
\documentclass[11pt]{article}
\pdfinfoomitdate=1
\pdftrailerid{}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[margin=1in]{geometry}
\usepackage[expansion=false]{microtype}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage{booktabs,array,longtable}
\usepackage{xcolor,listings}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black,
urlcolor=blue!45!black,
pdftitle={The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model},
pdfauthor={OpenAI}}
\newcommand{\E}{\mathbb E}
\newcommand{\R}{\mathbb R}
\newcommand{\N}{\mathbb N}
\newcommand{\Deltafour}{\Delta_4}
\newcommand{\unif}{\boldsymbol u}
\newcommand{\Sym}{\mathfrak S_4}
\DeclareMathOperator{\TV}{TV}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\numberwithin{equation}{section}
\lstset{basicstyle=\ttfamily\scriptsize,columns=fullflexible,
keepspaces=true,breaklines=true,breakatwhitespace=false,
showstringspaces=false,tabsize=2,numbers=left,numberstyle=\tiny\color{gray},
numbersep=7pt,frame=none,aboveskip=1em,belowskip=1em}
\title{The Reconstruction Threshold for the\newline
Ferromagnetic Four-State Potts Model}
\author{OpenAI}
\date{October 5, 2026}
\begin{document}
\maketitle
\begin{abstract}
We establish the exact Kesten--Stigum reconstruction threshold for the
ferromagnetic four-state Potts broadcast model on every regular $d$-ary
tree with $d\ge2$ and every Poisson Galton--Watson tree of mean $d>0$.
Reconstruction occurs exactly when $d\lambda^2>1$; we prove
nonreconstruction at and below the threshold, including equality.
In the Poisson model the whole tree is observed and the reconstruction
advantage is averaged without conditioning on survival. The proof uses
reproducible exact-arithmetic verification of polynomial inequalities.
\end{abstract}
\input{sections/01-introduction}
\input{sections/02-experiments}
\input{sections/03-cone}
\input{sections/04-tree-decay}
\input{sections/05-polynomial-certificates}
\input{sections/06-finite-verification}
\input{references}
\appendix
\input{sections/07-code-appendix}
\end{document}
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//main.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//references.tex ====
\begin{thebibliography}{99}
\bibitem{BhatnagarManeva2011}
N.~Bhatnagar and E.~Maneva,
\emph{A computational method for bounding the probability of reconstruction
on trees}, SIAM J. Discrete Math. \textbf{25} (2011), no.~2, 854--871.
\href{https://doi.org/10.1137/090751244}{doi:10.1137/090751244}.
\bibitem{BleherRuizZagrebnov1995}
P.~M.~Bleher, J.~Ruiz, and V.~A.~Zagrebnov,
\emph{On the purity of the limiting Gibbs state for the Ising model
on the Bethe lattice},
J. Stat. Phys. \textbf{79} (1995), nos.~1--2, 473--482.
\href{https://doi.org/10.1007/BF02179399}{doi:10.1007/BF02179399}.
\bibitem{EvansKenyonPeresSchulman2000}
W.~Evans, C.~Kenyon, Y.~Peres, and L.~J.~Schulman,
\emph{Broadcasting on trees and the Ising model},
Ann. Appl. Probab. \textbf{10} (2000), no.~2, 410--433.
\href{https://doi.org/10.1214/aoap/1019487349}{doi:10.1214/aoap/1019487349}.
\bibitem{FormentinKulske2009}
M.~Formentin and C.~K\"ulske,
\emph{A symmetric entropy bound on the non-reconstruction regime of
Markov chains on Galton--Watson trees},
Electron. Commun. Probab. \textbf{14} (2009), 587--596.
\href{https://doi.org/10.1214/ECP.v14-1516}{doi:10.1214/ECP.v14-1516}.
\bibitem{Gu2026}
Y.~Gu,
\emph{Exact reconstruction thresholds on hypertrees over a symmetric
binary alphabet}, preprint (2026).
\href{https://arxiv.org/abs/2606.21699}{arXiv:2606.21699}.
\bibitem{KestenStigum1966}
H.~Kesten and B.~P.~Stigum,
\emph{Additional limit theorems for indecomposable multidimensional
Galton--Watson processes},
Ann. Math. Statist. \textbf{37} (1966), no.~6, 1463--1481.
\href{https://doi.org/10.1214/aoms/1177699139}{doi:10.1214/aoms/1177699139}.
\bibitem{Leroy2012}
R.~Leroy,
\emph{Convergence under subdivision and complexity of polynomial
minimization in the simplicial Bernstein basis},
Reliable Computing \textbf{17} (2012), 11--21.
\bibitem{Lyons1990}
R.~Lyons,
\emph{Random walks and percolation on trees},
Ann. Probab. \textbf{18} (1990), no.~3, 931--958.
\href{https://doi.org/10.1214/aop/1176990730}{doi:10.1214/aop/1176990730}.
\bibitem{MezardMontanari2006}
M.~M\'ezard and A.~Montanari,
\emph{Reconstruction on trees and spin glass transition},
J. Stat. Phys. \textbf{124} (2006), no.~6, 1317--1350.
\href{https://doi.org/10.1007/s10955-006-9162-3}{doi:10.1007/s10955-006-9162-3}.
\bibitem{Mossel2001}
E.~Mossel,
\emph{Reconstruction on trees: Beating the second eigenvalue},
Ann. Appl. Probab. \textbf{11} (2001), no.~1, 285--300.
\href{https://doi.org/10.1214/aoap/998926994}{doi:10.1214/aoap/998926994}.
\bibitem{MosselPeres2003}
E.~Mossel and Y.~Peres,
\emph{Information flow on trees},
Ann. Appl. Probab. \textbf{13} (2003), no.~3, 817--844.
\href{https://doi.org/10.1214/aoap/1060202828}{doi:10.1214/aoap/1060202828}.
\bibitem{MosselSlySohn2025}
E.~Mossel, A.~Sly, and Y.~Sohn,
\emph{Exact phase transitions for stochastic block models and
reconstruction on trees},
Ann. Probab. \textbf{53} (2025), no.~3, 967--1018.
\href{https://doi.org/10.1214/24-AOP1723}{doi:10.1214/24-AOP1723}.
Author preprint:
\href{https://arxiv.org/abs/2212.03362}{arXiv:2212.03362}.
\bibitem{RicciTersenghiSemerjianZdeborova2019}
F.~Ricci-Tersenghi, G.~Semerjian, and L.~Zdeborov\'a,
\emph{Typology of phase transitions in Bayesian inference problems},
Phys. Rev. E \textbf{99} (2019), no.~4, 042109.
\href{https://doi.org/10.1103/PhysRevE.99.042109}{doi:10.1103/PhysRevE.99.042109}.
\bibitem{Sly2011}
A.~Sly,
\emph{Reconstruction for the Potts model},
Ann. Probab. \textbf{39} (2011), no.~4, 1365--1406.
\href{https://doi.org/10.1214/10-AOP584}{doi:10.1214/10-AOP584}.
\end{thebibliography}
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//references.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/01-introduction.tex ====
\section{Introduction}\label{sec:introduction}
In a broadcast process on a tree, each vertex transmits a noisy copy of
its spin to its children. The reconstruction problem asks whether the
spins far from the root retain information about its initial spin.
For the symmetric four-state channel, the linear second-moment threshold
has long been expected to be the exact reconstruction threshold in the
ferromagnetic regime. We prove the nonreconstruction direction at and
below this threshold for all regular and Poisson branching parameters.
\subsection{Model and main result}
Write $[4]=\{1,2,3,4\}$. The root spin $\sigma_\rho$ is uniform on $[4]$.
For a parameter $\lambda\in[0,1]$, each edge independently transmits the
parent spin through the channel
\begin{equation}\label{eq:broadcast-channel}
P_\lambda(j\mid i)
=\lambda\mathbf 1_{\{i=j\}}+\frac{1-\lambda}{4},
\qquad i,j\in[4].
\end{equation}
The parameter $\lambda$ is the nontrivial eigenvalue of the channel;
its nonnegativity specifies the ferromagnetic regime.
We consider the rooted $d$-ary tree, where every vertex has exactly $d$
children, and a Galton--Watson tree with independent Poisson$(d)$ offspring
counts. In the latter case the tree is sampled independently of the root
spin and the randomness used by the edge channels. The
observer is given the entire rooted tree $T$ and the spins
$\sigma_{L_n}$ at level $L_n=\{v:\operatorname{dist}(v,\rho)=n\}$.
Let
\begin{equation}\label{eq:advantage}
a_n(d,\lambda)=
\E\left[\frac12\sum_{i=1}^4
\left|\Pr(\sigma_\rho=i\mid T,\sigma_{L_n})-\frac14\right|\right].
\end{equation}
The tree observation in the Galton--Watson model is unlabelled, the level
observation is empty when $L_n$ is empty, and the expectation is not
conditioned on survival. Nonreconstruction means that $a_n(d,\lambda)$
tends to zero.
\begin{theorem}\label{thm:main}
For the channel \eqref{eq:broadcast-channel}, if $d\lambda^2\leq1$, then
\[
\lim_{n\to\infty}a_n(d,\lambda)=0
\]
in each of the following models:
\begin{enumerate}
\item the rooted $d$-ary tree, for every integer $d\geq2$;
\item the Poisson$(d)$ Galton--Watson tree, for every real $d>0$.
\end{enumerate}
In particular, the assertion includes $d\lambda^2=1$.
\end{theorem}
Here $d$ denotes the number of children or its mean, not the total
undirected degree. The known Kesten--Stigum reconstruction direction for
$d\lambda^2>1$ makes Theorem~\ref{thm:main} an exact threshold statement
\cite{KestenStigum1966,MosselPeres2003,Lyons1990}. For Poisson trees,
the branching-number reconstruction criterion applies on survival,
where the branching number equals $d$; survival has positive probability
when $d\lambda^2>1$.
The theorem is computer assisted: all probabilistic arguments are proved
below, and the remaining polynomial inequalities are verified by the
complete exact-arithmetic programs in Appendix~\ref{app:verifiers}.
\subsection{History and significance}
The Kesten--Stigum criterion originates in the second-moment analysis of
multitype branching processes \cite{KestenStigum1966}. In tree broadcasting it gives the
reconstruction direction above $d\lambda^2=1$, but the corresponding
nonreconstruction assertion depends on the channel. For binary symmetric
channels, Bleher, Ruiz, and Zagrebnov established sharpness on regular
trees \cite{BleherRuizZagrebnov1995}; Evans, Kenyon, Peres, and Schulman
developed the general-tree theory
\cite{EvansKenyonPeresSchulman2000}. Mossel showed that the spectral
criterion need not be necessary for other channels \cite{Mossel2001}.
For Potts channels, this distinction becomes decisive as the number of
states increases. M\'ezard and Montanari proposed threshold coincidence
for small alphabets and discussed its extension to all regular degrees
\cite[Section~8]{MezardMontanari2006}.
Sly proved sharpness for the three-state model on regular trees of
sufficiently large degree and established failure of sharpness for
$q\geq5$ \cite{Sly2011}. The four-state case lies at the boundary between
these behaviors.
Mossel, Sly, and Sohn proved nonreconstruction, including the critical
point, for the three- and four-state models on Galton--Watson trees of
sufficiently large mean degree under hypotheses that cover both regular
and Poisson offspring \cite{MosselSlySohn2025}.
Theorem~\ref{thm:main} removes the large-degree restriction for the
ferromagnetic four-state model in these two families. Cavity expansions
and numerical investigations by Ricci-Tersenghi, Semerjian, and
Zdeborov\'a also support the four-state ferromagnetic threshold
\cite{RicciTersenghiSemerjianZdeborova2019}; those predictions are distinct
from a rigorous all-degree nonreconstruction theorem. The restriction
$\lambda\geq0$ matters: the four-state antiferromagnetic model can
reconstruct below the Kesten--Stigum threshold
\cite{MosselSlySohn2025}.
\subsection{The proof mechanism}
The key object is the distribution of a posterior probability vector
$p=(p_1,p_2,p_3,p_4)$, not an individual vector. Define its quadratic
information by
\[
A(p)=4\sum_{i=1}^4p_i^2-1.
\]
A channel step multiplies $\E A$ by $\lambda^2$. The problem is to control
the nonlinear combination of the observations arriving from different
children. We construct a degree-six polynomial $H$ for which the
additional constraint $\E H(p)\geq0$ is preserved by both channel steps
and the combination of observations. Two explicit polynomial inequalities
then make $\E A$ subadditive under combination, with a strictly positive
cubic saving when two informative branches are present.
Writing $m_n$ for the expected quadratic information at depth $n$, this
gives, for $\lambda>0$, a recursion of the form
\[
m_{n+1}\leq d\lambda^2m_n-cm_n^3,
\qquad c=c(d,\lambda)>0.
\]
The cubic term is essential at equality: it forces $m_n\to0$ even when
the linear coefficient equals one. The constraint on the posterior law
is linear, so it also survives mixtures over the observed offspring
count. This is what allows the same pairwise inequalities to treat the
Poisson and regular models.
Expected functionals of posterior distributions are central to earlier
entropy and stochastic Lyapunov methods, including the work of Formentin
and K\"ulske \cite{FormentinKulske2009}. Rigorous computational methods
for nonreconstruction include Bhatnagar and Maneva's survey method
\cite{BhatnagarManeva2011} and Gu's population-dynamics method for binary
Poisson hypertrees \cite{Gu2026}. The additional ingredient here is the
explicit polynomial constraint that remains valid during each pairwise
combination of observations. Its pairing with the two combination
inequalities gives a strict moment saving for every parameter in the two
branching families when $\lambda>0$.
The required inequalities are certified on products of
probability simplices by nonnegative homogeneous coefficients, using
Taylor lower bounds and interpolation with explicitly certified
remainders. The interpolation itself is never assumed to approximate
the target accurately. Thus the computation verifies fixed polynomial
inequalities on all posterior vectors; the preserved constraint on their
laws then supplies the tree argument.
Section~\ref{sec:experiments} gives the posterior operations, and
Section~\ref{sec:cone} states the explicit polynomial inequalities and
derives their consequences for posterior laws.
Section~\ref{sec:tree-decay} completes the probabilistic argument.
Sections~\ref{sec:polynomial-certificates} and
\ref{sec:finite-verification} prove the inequalities through a finite
exact-arithmetic calculation.
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/01-introduction.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/02-experiments.tex ====
\section{Symmetric posterior experiments}
\label{sec:experiments}
The observations below are experiments about an input that is uniform on
$[4]$. A tree combines such experiments in two ways: an observation passes
through one broadcast edge, and observations from different branches are
combined. We record the exact posterior laws for these operations, keeping
separate the independent laws used in a calculation and the actual law of a
combined observation. The normalized posterior update and its change of
observation law are standard in broadcasting recursions; see
\cite[Sections~2.2--2.4]{MezardMontanari2006}.
Write
\[
\Deltafour=\left\{p\in[0,1]^4:\sum_{i=1}^4p_i=1\right\},
\qquad \unif=(1/4,1/4,1/4,1/4),
\]
and let $\Sym$ be the group of permutations of $[4]$.
An experiment consists of a uniform input $I\in[4]$ and an observation $Y$.
Write $\kappa_i$ for the conditional law of $Y$ given $I=i$, and
$\kappa=\frac14\sum_i\kappa_i$ for its marginal law. Since each
$\kappa_i$ is absolutely continuous with respect to $\kappa$, its posterior
vector $p(Y)\in\Deltafour$ satisfies
\begin{equation}
p_i(y)=\frac14\frac{\mathrm d\kappa_i}{\mathrm d\kappa}(y),
\qquad
\frac{\mathrm d\kappa_i}{\mathrm d\kappa}(y)=4p_i(y).
\label{eq:posterior-likelihood}
\end{equation}
These identities also define the posterior on a general observation space,
up to a $\kappa$-null set. Denote by $\mu$ the law of $p(Y)$ under
$\kappa$. In particular,
\[
\int_{\Deltafour}p_i\,\mathrm d\mu(p)=\frac14
\qquad(i\in[4]).
\]
Conversely, any probability law $\mu$ with this barycenter is realized by
taking the observation space to be $\Deltafour$ and its conditional laws
to be $4p_i\,\mathrm d\mu(p)$.
We call the experiment symmetric if $\mu$ is invariant under all
permutations of its four coordinates. This is a condition on the law of
the posterior, not on an individual posterior vector.
The following coordinates remove the constant direction:
\begin{equation}
L=
\begin{pmatrix}
1&1&-1&-1\\
1&-1&1&-1\\
1&-1&-1&1
\end{pmatrix},
\qquad x=Lp,
\qquad A(p)=|Lp|^2.
\label{eq:posterior-coordinates}
\end{equation}
Since $L^{\mathsf T}L=4\operatorname{Id}-\boldsymbol{1}
\boldsymbol{1}^{\mathsf T}$, where $\boldsymbol{1}=(1,1,1,1)^{\mathsf T}$,
\begin{equation}
A(p)=4\sum_{i=1}^4(p_i-1/4)^2,
\qquad 0\le A(p)\le3,
\qquad
\frac12\sum_{i=1}^4|p_i-1/4|\le\frac12\sqrt{A(p)}.
\label{eq:quadratic-tv}
\end{equation}
Thus decay of the mean of $A$ will imply nonreconstruction.
\begin{lemma}[Bayes product]
\label{lem:bayes-product}
Let two experiments have the same uniform input and observations that are
independent conditional on that input. Let $\mu$ and $\nu$ be their
individual posterior laws. For $p,q\in\Deltafour$, define
\[
U_i(p,q)=4p_iq_i,
\qquad z(p,q)=\sum_{i=1}^4U_i(p,q),
\qquad P_i(p,q)=\frac{U_i(p,q)}{z(p,q)}
\quad\text{when }z(p,q)>0.
\]
Set $P(p,q)=\unif$ when $z(p,q)=0$. The posterior law of the combined
experiment, denoted by $\mu\star\nu$, is characterized by
\begin{equation}
\int_{\Deltafour} f(r)\,\mathrm d(\mu\star\nu)(r)
=\int_{\Deltafour\times\Deltafour}
z(p,q)f(P(p,q))\,\mathrm d\mu(p)\,\mathrm d\nu(q)
\label{eq:product-law}
\end{equation}
for every bounded measurable $f$. The measure on the right has total
mass one. If both experiments are symmetric, their combined experiment
is symmetric.
\end{lemma}
\begin{proof}
Let $\kappa,\eta$ be the marginal observation laws, with posterior vectors
$p(y),q(w)$. Conditional independence and
\eqref{eq:posterior-likelihood} show that the joint observation law has
density
\[
\frac14\sum_{i=1}^4(4p_i(y))(4q_i(w))=z(p(y),q(w))
\]
with respect to $\kappa\otimes\eta$. Bayes' formula then gives the
combined posterior $P$. Pushing this identity forward to the two
posterior vectors proves \eqref{eq:product-law}. Its normalization can
also be checked directly:
\[
\int z(p,q)\,\mathrm d\mu(p)\,\mathrm d\nu(q)
=4\sum_{i=1}^4
\left(\int p_i\,\mathrm d\mu\right)
\left(\int q_i\,\mathrm d\nu\right)=1.
\]
Finally, simultaneous coordinate permutation leaves $z$ unchanged and
permutes $P$ by the same permutation. Invariance of $\mu$ and $\nu$
therefore implies invariance of $\mu\star\nu$.
\end{proof}
In \eqref{eq:product-law}, $p$ and $q$ are independent under
$\mu\otimes\nu$. They generally are not independent under the actual
observation law $z\,\mathrm d\mu\,\mathrm d\nu$. All factorizations of
expectations below use the former measure, before the factor $z$ is
applied. The choice of $P$ at $z=0$ never affects a combined expectation.
\begin{lemma}[Passage through one edge]
\label{lem:channel}
Let $I$ be uniform on $[4]$, let $J$ be obtained from $I$ through the
channel $P_\lambda$, and let $Y$ be an experiment about $J$, independent
of $I$ conditional on $J$. If $\mu$ is the posterior law for $J$ given
$Y$, then the posterior law for $I$ given $Y$ is the pushforward of
$\mu$ by
\begin{equation}
C_\lambda(p)=\unif+\lambda(p-\unif),
\qquad L C_\lambda(p)=\lambda Lp,
\qquad A(C_\lambda(p))=\lambda^2A(p).
\label{eq:channel-scaling}
\end{equation}
In particular, this operation preserves symmetry.
\end{lemma}
\begin{proof}
The channel is symmetric and doubly stochastic, so $J$ is uniform and
$\Pr(I=i\mid J=j)=P_\lambda(i\mid j)$. If $p$ is the posterior of
$J$ given $Y$, the posterior of $I$ is consequently
\[
\sum_{j=1}^4P_\lambda(i\mid j)p_j
=\lambda p_i+\frac{1-\lambda}{4}.
\]
The marginal law of $Y$ is the same whether it is regarded as an
experiment about $I$ or about $J$. This proves the pushforward statement.
The remaining identities follow from $L\unif=0$, and symmetry follows
because $C_\lambda$ commutes with coordinate permutations.
\end{proof}
We will also use observed mixtures of experiments. Suppose an index $S$
is independent of the input and, conditional on $S=s$, the observation
has posterior law $\mu_s$. If $S$ itself is observed, the resulting
posterior law is $\int\mu_s\,\mathrm d\Pr_S(s)$. Hence symmetry and
any linear inequality on posterior laws are preserved under such
mixtures. In the tree application, $S$ will be the offspring count.
The uninformative experiment has posterior law concentrated at $\unif$;
the experiment that reveals the input has posterior law assigning mass
$1/4$ to each of the four coordinate vectors.
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/02-experiments.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/03-cone.tex ====
\section{A preserved constraint on posterior laws}\label{sec:cone}
The second moment $\E A(p)$ measures information about the input, but the
estimate we need for products also involves one higher-order statistic.
We now give this statistic explicitly. Its expectation will remain
nonnegative throughout the recursion, allowing a strict improvement on
second-moment subadditivity.
For $x=Lp$, with $L$ as in Section~\ref{sec:experiments}, set
\[
B(p)=x_1x_2x_3,\qquad
C(p)=x_1^2x_2^2+x_1^2x_3^2+x_2^2x_3^2.
\]
Together with $A(p)=x_1^2+x_2^2+x_3^2$, these polynomials are invariant under
permuting the four entries of $p$. Indeed, such a permutation acts on $x$
by a permutation of its coordinates and an even number of sign changes.
Define $H,F,G$ by the following coefficient table, whose entries are divided
by $1000$:
\begin{equation}\label{eq:polynomial-table}
\begin{array}{c|rrrrrrrrr}
&1&A&B&A^2&C&AB&A^3&AC&B^2\\ \hline
H&0&0&1000&-100&-150&300&-20&70&-510\\
F&0&4000&-3000&700&-4000&-800&0&0&0\\
G&1000&-1610&-3100&773&4000&-3980&0&0&0
\end{array}
\end{equation}
Thus, for example, $H=B-A^2/10-3C/20+3AB/10-A^3/50
+7AC/100-51B^2/100$. We also write $H(x)$ when its three coordinate
arguments, rather than the probability vector, are supplied.
For $p,q\in\Deltafour$ and $\pi\in\Sym$, put
\[
U_i^{\pi}=4p_iq_{\pi(i)},\qquad
z_\pi=\sum_{i=1}^4 U_i^{\pi},\qquad
P^{\pi}=U^{\pi}/z_\pi\quad(z_\pi>0).
\]
For a continuous function $\phi$ on $\Deltafour$, use the notation
\begin{equation}\label{eq:permutation-average}
[z\phi(P)](p,q)=\frac1{24}\sum_{\pi\in\Sym}
z_\pi\phi(P^{\pi}),
\end{equation}
with each summand set to zero when $z_\pi=0$. Finally, define
\begin{equation}\label{eq:cubic-saving}
D_0(p,q)=\frac{A(p)A(q)\bigl(A(p)+A(q)\bigr)}{1000}.
\end{equation}
\begin{proposition}[Polynomial inequalities]\label{prop:polynomial-inequalities}
For every $p,q\in\Deltafour$, the polynomials in
\eqref{eq:polynomial-table} satisfy $F(p)\geq0$, $G(p)\geq0$, and
$H(p)\geq-1/2$. For $x=Lp$ and $0\leq t\leq1$,
\begin{equation}\label{eq:H-scaling}
H(tx)\geq t^3H(x).
\end{equation}
Moreover,
\begin{align}
[zA(P)](p,q)
&\leq A(p)+A(q)-H(p)F(q)-F(p)H(q)-D_0(p,q),
\label{eq:A-product}\\
[zH(P)](p,q)
&\geq H(p)G(q)+G(p)H(q).
\label{eq:H-product}
\end{align}
\end{proposition}
Sections~\ref{sec:polynomial-certificates} and
\ref{sec:finite-verification} prove this proposition using exact
polynomial sign certificates. We first show how it controls posterior laws;
this identifies the purpose of each inequality before the coefficient
calculation begins.
Let $\mathcal C$ be the class of symmetric posterior laws $\mu$ for which
\begin{equation}\label{eq:cone-condition}
\E_{\mu} H(p)\geq0.
\end{equation}
The condition is linear in the law. It does not require $H(p)\geq0$ at
every posterior: for example, $p=(1/2,1/2,0,0)$ has $H(p)=-3/25$.
The completely informative experiment and the uninformative experiment
belong to $\mathcal C$, because
\begin{equation}\label{eq:initial-H}
H(e_i)=\frac{13}{100}\quad(1\leq i\leq4),\qquad H(\unif)=0.
\end{equation}
Here the informative experiment has posterior law uniform on the four
point masses $e_i$.
\begin{proposition}[Closure and moment saving]\label{prop:cone-closure}
The class $\mathcal C$ is preserved by a channel step with
$\lambda\in[0,1]$, by conditionally independent products of experiments,
and by mixtures whose mixing label is observed and independent of the
input. If $\mu,\nu\in\mathcal C$ are the marginal posterior laws of two
experiments, then their product posterior law $\mu\star\nu$ satisfies
\begin{align}
\E_{\mu\star\nu} A
\leq{}& \E_{\mu}A+\E_{\nu}A\notag\\
&-\frac{\E_{\mu}A^2\,\E_{\nu}A+
\E_{\mu}A\,\E_{\nu}A^2}{1000}.
\label{eq:moment-saving}
\end{align}
In particular, when $\E_{\mu}A=\E_{\nu}A=b$, the subtracted term is at
least $2b^3/1000$.
\end{proposition}
\begin{proof}
By Lemma~\ref{lem:channel}, a channel step scales $x=Lp$ by $\lambda$
without changing the marginal law of the observation. Consequently
\eqref{eq:H-scaling} gives
\[
\E H(\lambda x)\geq\lambda^3\E H(x)\geq0.
\]
The resulting law remains symmetric.
For a product, Lemma~\ref{lem:bayes-product} expresses its posterior
expectations as $\E_{\mu\otimes\nu}[z\phi(P)]$. The expectation here is
over independent marginal posterior laws, before multiplication by the
density $z$. Since $\nu$ is symmetric, it is unchanged by permuting its
four coordinates. We may therefore replace $z\phi(P)$ by its permutation
average whenever $\phi$ is $A$ or $H$. Integrating
\eqref{eq:H-product} and using independence gives
\[
\E_{\mu\star\nu}H
\geq \E_{\mu}H\,\E_{\nu}G+
\E_{\mu}G\,\E_{\nu}H\geq0.
\]
Here $G\geq0$ pointwise, whereas the two expectations of $H$ are
nonnegative by membership in $\mathcal C$. Symmetry is preserved by
Lemma~\ref{lem:bayes-product}.
Similarly, integration of \eqref{eq:A-product} yields
\[
\E_{\mu\star\nu}A
\leq \E_{\mu}A+\E_{\nu}A
-\E_{\mu}H\,\E_{\nu}F
-\E_{\mu}F\,\E_{\nu}H
-\E_{\mu\otimes\nu}D_0(p,q).
\]
The two terms involving $F$ can be discarded because $F\geq0$ and
$\mu,\nu\in\mathcal C$. Expanding \eqref{eq:cubic-saving} gives
\eqref{eq:moment-saving}. Since $A\geq0$, Jensen's inequality gives
$\E_{\mu}A^2\geq(\E_{\mu}A)^2$ and the analogous bound for $\nu$,
which proves the last assertion.
Finally, conditioning on an observed mixing label independent of the input
leaves the uniform prior unchanged. The posterior law of the mixed
experiment is the corresponding mixture of posterior laws. Symmetry and
\eqref{eq:cone-condition} are both preserved by this mixture.
\end{proof}
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/03-cone.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/04-tree-decay.tex ====
\section{Decay on the tree}
\label{sec:tree-decay}
We now apply Proposition~\ref{prop:cone-closure} to the observations in
successive generations. The saving from just two branches will suffice;
the remaining branches need only satisfy subadditivity.
For the calculation, supply an ordering of the children at every vertex.
In the Galton--Watson model, one may construct this ordered tree by giving
each vertex an independent offspring count and numbering its children
from $1$ to that count. Erasing the numbering gives the unlabelled tree
in the theorem. Write $\widehat T$ for the ordered tree and
$\widehat T_{\le n}$ for its truncation at depth $n$. Define
\[
Y_n=\bigl(\widehat T_{\le n},(\sigma_v)_{v\in L_n}\bigr),
\qquad p^{(n)}_i=\Pr(\sigma_\rho=i\mid Y_n).
\]
Every finite-depth truncation is finite almost surely. Let $\mu_n$ be
the law of $p^{(n)}$, and put
\begin{equation}
m_n=\int_{\Deltafour}A(p)\,\mathrm d\mu_n(p).
\label{eq:tree-moment}
\end{equation}
In the random-tree case this integral averages over the tree as well as
the spins, without conditioning on survival.
There are two information comparisons to check. First, conditional on
$\widehat T_{\le n}$, the part of $\widehat T$ below depth $n$ is
independent of the root and all spins used in $Y_n$. This follows from
the independence of the tree construction and the channel randomness.
Consequently, supplying the entire ordered tree leaves the posterior
unchanged:
\begin{equation}
\Pr\bigl(\sigma_\rho=i\mid
\widehat T,(\sigma_v)_{v\in L_n}\bigr)=p^{(n)}_i
\quad\text{almost surely}.
\label{eq:whole-tree-posterior}
\end{equation}
Second, forgetting the ordering cannot increase expected total variation
from the prior. Indeed, for observation sigma-fields
$\mathcal F\subseteq\mathcal G$, the posterior given $\mathcal F$ is
the conditional expectation of the posterior given $\mathcal G$;
convexity of the total-variation norm gives the assertion. Combining
this observation with \eqref{eq:quadratic-tv} and Jensen's inequality,
the advantage defined in Theorem~\ref{thm:main} satisfies
\begin{equation}
a_n(d,\lambda)\le\frac12\E\sqrt{A(p^{(n)})}
\le\frac12\sqrt{m_n}.
\label{eq:tree-tv-bound}
\end{equation}
It therefore remains to prove that $m_n$ tends to zero.
\begin{proposition}[Moment recursion]
\label{prop:tree-recursion}
In either tree family of Theorem~\ref{thm:main}, the posterior law
$\mu_n$ is symmetric and satisfies $\int H\,\mathrm d\mu_n\ge0$ for
every $n\ge0$. Let $D$ denote the offspring count, so $D=d$ on the
regular tree and $D$ has law $\operatorname{Poisson}(d)$ on the
Galton--Watson tree. Then
\begin{equation}
m_{n+1}\le d\lambda^2m_n
-\frac{2}{1000}\Pr(D\ge2)(\lambda^2m_n)^3.
\label{eq:tree-recursion}
\end{equation}
\end{proposition}
\begin{proof}
At depth zero the root spin is revealed. Thus $\mu_0$ assigns mass
$1/4$ to each coordinate vector, is symmetric, and satisfies
$\int H\,\mathrm d\mu_0=13/100>0$.
Suppose $\mu_n\in\mathcal C$.
Conditional on $D=k$, each child contributes an experiment obtained by
passing a depth-$n$ experiment through one broadcast edge. The branches
are independent conditional on the root spin, and their individual
posterior laws are all the pushforward $(C_\lambda)_*\mu_n$. For the
Galton--Watson tree this uses the independence of the child subtrees
from each other and from $D$; for the regular tree the subtrees are
deterministic copies of the same rooted tree. By
Lemma~\ref{lem:channel} and Proposition~\ref{prop:cone-closure}, each
branch law belongs to $\mathcal C$ and has mean $A$ equal to
\[
b=\lambda^2m_n.
\]
Combining the branches successively by Lemma~\ref{lem:bayes-product}
and Proposition~\ref{prop:cone-closure} preserves membership in
$\mathcal C$. If $k=0$, the posterior is $\unif$ and has $H=A=0$.
Since $D$ is independent of the root and is observed, mixing these laws
over $D$ also preserves membership in $\mathcal C$. This proves
the induction assertion for $\mu_{n+1}$.
For $k\ge2$, combine the first two branches before adding the others.
Their individual posterior laws lie in $\mathcal C$ and both have mean
$A$ equal to $b$. The final assertion of
Proposition~\ref{prop:cone-closure} therefore bounds the mean of $A$
after their combination by $2b-2b^3/1000$. Each additional branch
increases this upper bound by at most $b$, since the combined experiment
still belongs to $\mathcal C$. For $k=0$ the mean is zero, and for $k=1$ it is
$b$. In all cases,
\[
\E\bigl[A(p^{(n+1)})\mid D=k\bigr]
\le kb-\frac{2b^3}{1000}\boldsymbol{1}_{\{k\ge2\}}.
\]
Taking expectation over $D$, whose mean is $d$, proves
\eqref{eq:tree-recursion}.
\end{proof}
\begin{proof}[Proof of Theorem~\ref{thm:main}]
If $\lambda=0$, each branch observation is independent of the root;
equivalently, \eqref{eq:tree-recursion} gives $m_n=0$ for every $n\ge1$.
Assume henceforth that $\lambda>0$ and $d\lambda^2\le1$.
On the regular tree, $d\ge2$ and hence $\Pr(D\ge2)=1$. The recursion
gives
\[
0\le m_{n+1}\le m_n-\frac{2\lambda^6}{1000}m_n^3.
\]
Thus $(m_n)$ is decreasing and has a limit $\ell\ge0$. Passing to the
limit yields $\ell\le\ell-2\lambda^6\ell^3/1000$, so $\ell=0$.
For Poisson offspring,
\[
\Pr(D\ge2)=1-(1+d)e^{-d}>0\qquad(d>0).
\]
The same argument applies with the positive coefficient
$2\lambda^6(1-(1+d)e^{-d})/1000$ in place of $2\lambda^6/1000$.
In particular, it covers $d\le1$, including the noiseless critical case
$d=\lambda=1$, directly in the unconditioned tree law. No step requires
an infinite tree or a nonempty observed generation: when $L_n$ is empty,
the tree observation is independent of the root and the posterior is
$\unif$.
Both arguments allow $d\lambda^2=1$; the strictly positive cubic term
is what forces decay at that boundary. Finally,
\eqref{eq:tree-tv-bound} gives $a_n(d,\lambda)\to0$ in each family.
\end{proof}
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/04-tree-decay.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/05-polynomial-certificates.tex ====
\section{Exact polynomial certificates}
\label{sec:polynomial-certificates}
We now prove the polynomial inequalities in
Proposition~\ref{prop:polynomial-inequalities}. The single-posterior
inequalities follow from small homogeneous coefficient calculations. For the
two-posterior inequalities, we give two sufficient tests on a product of
simplices. Section~\ref{sec:finite-verification} applies those tests to a
finite subdivision and completes the proof.
\subsection{Ordered probabilities and homogeneous coefficients}
Let
\[
\mathcal S=\{p\in\Deltafour:p_1\ge p_2\ge p_3\ge p_4\},
\qquad
S_i=\frac{1}{i+1}\sum_{v=1}^{i+1}e_v
\quad(0\le i\le3),
\]
where $e_v$ is the $v$th standard basis vector of $\R^4$.
The set $\mathcal S$ is the simplex with vertices $S_0,S_1,S_2,S_3$.
Indeed, on setting $p_5=0$, its barycentric coordinates are
\begin{equation}
X_i=(i+1)(p_{i+1}-p_{i+2}),\qquad
p=\sum_{i=0}^3X_iS_i,\qquad \sum_{i=0}^3X_i=1.
\label{eq:ordered-barycentric}
\end{equation}
All $X_i$ are nonnegative. Conversely, each such convex combination lies
in $\mathcal S$.
A permutation of the four probabilities acts on $x=Lp$ by permuting its
three coordinates and changing an even number of their signs. One way to
check this is to note that, on the hyperplane $\sum_vp_v=1$,
$p=\unif+L^{\mathsf T}x/4$. For a permutation matrix $\Pi$, the induced
matrix is $L\Pi L^{\mathsf T}/4$; it is a signed permutation matrix whose
three nonzero entries have product $1$. Consequently $A,B,C$, and hence
$H,F,G$, are invariant. It is therefore enough to check the
single-posterior inequalities on $\mathcal S$. The permutation-averaged
two-posterior expressions are invariant under separate permutations of
$p$ and $q$: a permutation of $q$ reindexes the average, and a permutation
of $p$ can be moved to $q$ by simultaneous permutation of the output
coordinates. We may thus restrict both inputs to $\mathcal S$.
We use ordinary monomial coefficients throughout. For $r\ge0$, put
\[
\mathcal I_r=\{I\in\mathbb Z_{\ge0}^4:|I|=r\},\qquad
X^I=\prod_{i=0}^3X_i^{I_i},\qquad
W_r(X)=\left(\sum_{i=0}^3X_i\right)^r.
\]
The coefficient of $X^I$ in $W_r$ is the multinomial coefficient
$\binom rI=r!/\prod_iI_i!$. A polynomial of degree at most $r$ can be
homogenized to degree $r$ by multiplying each degree-$s$ monomial by
$W_{r-s}$. This does not change its values when $\sum_iX_i=1$.
If all coefficients of a homogeneous polynomial are nonnegative, then
the polynomial is nonnegative on the simplex. No converse is required.
The coefficients in the simplicial Bernstein basis differ from these
ordinary homogeneous coefficients by positive multinomial factors, so
their signs agree. This is the coefficient-positivity principle behind
simplicial Bernstein bounds and their refinement by subdivision;
see \cite{Leroy2012}.
The calculations below use only coefficient addition and the product rule
\begin{equation}
[X^I](RS)=\sum_{J+K=I}[X^J]R\,[X^K]S.
\label{eq:coefficient-convolution}
\end{equation}
For two sets of variables, write
$W_r(X,Y)=W_r(X)W_r(Y)$. A bihomogeneous polynomial of bidegree $(r,r)$,
meaning homogeneous of degree $r$ in each set of variables, is stored as
the matrix of its coefficients $[X^IY^J]$, with $I,J\in\mathcal I_r$.
Multiplication is convolution in both indices; multiplication by
$W_s(X,Y)$ raises both homogeneous degrees by $s$.
A monomial of degree $s$ in $X$ and degree $t$ in $Y$ is homogenized
to bidegree $(r,r)$ by multiplying it by
$W_{r-s}(X)W_{r-t}(Y)$.
\subsection{The single-posterior checks}
The coordinate forms on $\mathcal S$ are particularly small:
\begin{equation}
L\sum_{i=0}^3X_iS_i
=\left(X_0+X_1+\frac{X_2}{3},\,
X_0+\frac{X_2}{3},\,
X_0-\frac{X_2}{3}\right).
\label{eq:ordered-coordinate-forms}
\end{equation}
Let $\Phi_0,\ldots,\Phi_8$ be the polynomials
$1,A,B,A^2,C,AB,A^3,AC,B^2$ in the three coordinates, and let
\[
(e_0,\ldots,e_8)=(0,2,3,4,4,5,6,6,6)
\]
be their degrees. If $R=\sum_jc_j\Phi_j$, its degree-$r$ homogeneous
form on $\mathcal S$ is
\begin{equation}
\widehat R_r(X)
=\sum_{j:c_j\ne0}c_j\,
\Phi_j\left(L\sum_{i=0}^3X_iS_i\right)W_{r-e_j}(X),
\qquad r\ge\max_{c_j\ne0}e_j.
\label{eq:scalar-homogenization}
\end{equation}
Together with \eqref{eq:ordered-coordinate-forms} and
\eqref{eq:coefficient-convolution}, this formula specifies every
coefficient in the following check.
\begin{lemma}[Single-posterior certificate]
\label{lem:scalar-checks}
For every $p\in\Deltafour$,
\[
H(p)\ge-\frac12,\qquad F(p)\ge0,\qquad G(p)\ge0.
\]
Moreover, if $x=Lp$ and $0\le\ell\le1$, then
$H(\ell x)\ge\ell^3H(x)$, where $H$ in this formula is regarded as a
polynomial in the three coordinates.
\end{lemma}
\begin{proof}
Define the Euler operator on those coordinates by
$\mathcal E=\sum_{j=1}^3x_j\partial_{x_j}$. Thus
$\mathcal E\Phi_j=e_j\Phi_j$. The exact coefficient minima in
Table~\ref{tab:scalar-coefficients} are obtained from
\eqref{eq:scalar-homogenization}. The first row adds $1/2$ to the
constant coefficient of $H$; the last row replaces each coefficient
$c_j$ of $H$ by $(3-e_j)c_j$. The full scalar verifier is included in
Appendix~\ref{app:verifiers}.
\begin{table}[tb]
\centering
\begin{tabular}{lrrr}
\hline
Polynomial $R$ & Degree $r$ & Number of coefficients & Minimum\\
\hline
$H+1/2$ & 6 & 84 & $19/50$\\
$F$ & 5 & 56 & $0$\\
$G$ & 14 & 680 & $87/1000$\\
$(3-\mathcal E)H$ & 6 & 84 & $0$\\
\hline
\end{tabular}
\caption{Minimum ordinary monomial coefficients of the homogeneous
forms \eqref{eq:scalar-homogenization}, computed exactly over $\mathbb Q$.}
\label{tab:scalar-coefficients}
\end{table}
Coefficient nonnegativity proves the first three assertions and
$(3-\mathcal E)H\ge0$ on $L\mathcal S$. Permutation invariance extends
these statements to $L\Deltafour$. For $x\in L\Deltafour$ and
$0<\ell\le1$, the point $\ell x$ also lies in $L\Deltafour$, since
it corresponds to $\ell p+(1-\ell)\unif$. Therefore
\[
\frac{d}{d\ell}\bigl(\ell^{-3}H(\ell x)\bigr)
=\ell^{-4}(\mathcal E-3)H(\ell x)\le0.
\]
Comparing $\ell$ with $1$ gives the asserted scaling inequality.
At $\ell=0$ it follows from $H(0)=0$.
\end{proof}
\subsection{The two rational inequalities}
It remains to prove the two-posterior inequalities. We express each
as the nonnegativity of a rational function on
$\mathcal S\times\mathcal S$. For $\pi\in\Sym$, let
\[
U^\pi_v=4p_vq_{\pi(v)},\qquad
z_\pi=\sum_{v=1}^4U^\pi_v,\qquad
P^\pi=U^\pi/z_\pi\quad(z_\pi>0).
\]
Set
\begin{align}
K_a&=24\bigl(A(p)+A(q)-H(p)F(q)-F(p)H(q)-D_0(p,q)\bigr),\notag\\
K_b&=-24\bigl(H(p)G(q)+G(p)H(q)\bigr).
\label{eq:rational-K}
\end{align}
The remaining data are
\begin{equation}
\begin{array}{c|c|c|c}
\text{row} & k & N_\pi & m\\ \hline
a & 1 & -\displaystyle\sum_{j=1}^3(LU^\pi)_j^2 & 3\\[2mm]
b & 5 & z_\pi^6H(U^\pi/z_\pi) & 1/2
\end{array}
\label{eq:rational-rows}
\end{equation}
In row $b$, the expression for $N_\pi$ is a polynomial: each
degree-$s$ term of $H$ becomes the corresponding term in $LU^\pi$
multiplied by $z_\pi^{6-s}$. For either row define
\begin{equation}
\mathcal R=K+\sum_{\pi\in\Sym}\frac{N_\pi}{z_\pi^k}.
\label{eq:rational-target}
\end{equation}
In row $a$, the summand is $-z_\pi A(P^\pi)$; in row $b$, it is
$z_\pi H(P^\pi)$. Thus $\mathcal R\ge0$ is exactly the corresponding
inequality of Proposition~\ref{prop:polynomial-inequalities}, multiplied
by $24$.
These rational functions have continuous extensions to their apparent
singularities. All coordinates of $U^\pi$ are nonnegative, so
$z_\pi=0$ implies $U^\pi=0$. Since $P^\pi\in\Deltafour$ whenever
$z_\pi>0$, both $A(P^\pi)$ and $H(P^\pi)$ are bounded independently
of $p,q$. Hence the corresponding weighted summand tends to $0$ as
$z_\pi\to0$. We assign it that value on the boundary.
Now take any two nondegenerate subsimplices of $\mathcal S$, with
vertex lists $a=(a_0,\ldots,a_3)$ and $b=(b_0,\ldots,b_3)$, and write
\[
p=\sum_{i=0}^3X_ia_i,\qquad q=\sum_{j=0}^3Y_jb_j,
\qquad X_i,Y_j\ge0,\quad \sum_iX_i=\sum_jY_j=1.
\]
The ordinary bidegree-$(1,1)$ coefficient of $U^\pi_v$ at $X_iY_j$
is $4a_{iv}b_{j,\pi(v)}$. In particular, the coefficients of $z_\pi$
are nonnegative. Both $p$ and $q$ are strictly positive on the
relative interior of their subsimplices: a full-dimensional simplex
cannot lie in a coordinate face of $\Deltafour$. Thus every $z_\pi$
is strictly positive there. We represent $K$ homogeneously with
bidegree $(6,6)$ and $N_\pi$ with bidegree $(k+1,k+1)$.
The next two tests certify $\mathcal R\ge0$ on such a product of
simplices. They establish lower bounds on the entire region, not just
at the points used to construct the polynomials.
\subsection{A Taylor lower bound: Type T}
For a positive integer $k$, define
\[
t_k(z)=\sum_{i=0}^5\binom{-k}{i}(z-1)^i.
\]
For every $z>0$, Taylor's theorem gives
\begin{equation}
z^{-k}-t_k(z)
=\frac{k(k+1)\cdots(k+5)}{6!}\,
\xi^{-k-6}(z-1)^6\ge0
\label{eq:taylor-lower-bound}
\end{equation}
for some $\xi$ between $1$ and $z$; at $z=1$ the identity is
immediate. The bound holds for the full positive half-line, with no
restriction such as $|z-1|<1$.
For row $a$, $A(P)\le3$ on $\Deltafour$, because each coordinate of
$LP$ lies in $[-1,1]$. For row $b$, Lemma~\ref{lem:scalar-checks}
gives $H(P)\ge-1/2$. Consequently, in either row,
\begin{equation}
N_\pi+mz_\pi^{k+1}\ge0.
\label{eq:taylor-nonnegative-factor}
\end{equation}
\begin{lemma}[Type T certificate]
\label{lem:type-t}
For either row of \eqref{eq:rational-rows}, form the polynomial
\begin{equation}
T=K+\sum_{\pi\in\Sym}
\bigl((N_\pi+mz_\pi^{k+1})t_k(z_\pi)-mz_\pi\bigr).
\label{eq:type-t-polynomial}
\end{equation}
If its homogeneous coefficient matrix in bidegree $(k+6,k+6)$
has no negative entries, then $\mathcal R\ge0$ on the product of
simplices.
\end{lemma}
\begin{proof}
On the relative interior, multiply \eqref{eq:taylor-lower-bound} by
the nonnegative factor in \eqref{eq:taylor-nonnegative-factor} and
subtract $mz_\pi$. This yields
\[
\frac{N_\pi}{z_\pi^k}
\ge (N_\pi+mz_\pi^{k+1})t_k(z_\pi)-mz_\pi.
\]
Summing gives $\mathcal R\ge T$. The coefficient hypothesis makes
$T$ nonnegative on the product simplex. The continuous extension of
$\mathcal R$ then proves the boundary cases as well.
\end{proof}
\subsection{A polynomial lower bound with a certified remainder: Type P}
The second test constructs a lower bound for each rational summand
separately. Start with any bihomogeneous polynomial $J_\pi$ of bidegree $(3,3)$.
The way it is chosen affects the strength of the test, but not its
validity. We seek a constant $c_\pi\ge0$ such that
\[
\frac{N_\pi}{z_\pi^k}\ge J_\pi-c_\pi
\]
throughout the product simplex. On the relative interior, clearing the positive
denominator reduces this to nonnegativity of
$N_\pi-z_\pi^kJ_\pi+c_\pi z_\pi^k$.
To test that remainder by homogeneous coefficients, form in bidegree
$(k+3,k+3)$ the arrays
\begin{equation}
O_\pi=W_2N_\pi-z_\pi^kJ_\pi,\qquad
Q_\pi=z_\pi^kW_3,
\label{eq:type-p-remainder}
\end{equation}
where the arguments $(X,Y)$ of $W_2,W_3$ are suppressed.
Every coefficient of $Q_\pi$ is nonnegative.
Fix $M=2^{32}$. If an entry $(O_\pi)_{IJ}$ is negative and the
corresponding entry $(Q_\pi)_{IJ}$ is zero, the test is not
applicable. Otherwise define
\begin{equation}
c_\pi=\frac1M\max\left(
\{0\}\cup
\left\{
\left\lceil\frac{-M(O_\pi)_{IJ}}{(Q_\pi)_{IJ}}\right\rceil:
(O_\pi)_{IJ}<0
\right\}\right).
\label{eq:remainder-correction}
\end{equation}
By construction, $O_\pi+c_\pi Q_\pi$ is coefficientwise
nonnegative.
\begin{lemma}[Type P certificate]
\label{lem:type-p}
Suppose \eqref{eq:remainder-correction} is defined for every
$\pi\in\Sym$. If
\begin{equation}
K+\sum_{\pi\in\Sym}(J_\pi-c_\pi W_3)
\label{eq:type-p-polynomial}
\end{equation}
has nonnegative homogeneous coefficients in bidegree $(6,6)$,
then $\mathcal R\ge0$ on the product of simplices.
\end{lemma}
\begin{proof}
On the product simplex, $W_2=W_3=1$. On its relative interior,
\eqref{eq:type-p-remainder} gives the exact identity
\[
\frac{N_\pi}{z_\pi^k}
=J_\pi-c_\pi+
\frac{O_\pi+c_\pi Q_\pi}{z_\pi^k}
\ge J_\pi-c_\pi.
\]
Summing and using the coefficient hypothesis proves the claim on the
relative interior. Continuity gives the boundary cases.
\end{proof}
For reproducibility, we specify the polynomials $J_\pi$ used in the
finite check. For $I\in\mathcal I_3$, define the cardinal polynomial
\[
\ell_I(X)=\prod_{i=0}^3\binom{3X_i}{I_i},\qquad
\binom{t}{j}=\frac{t(t-1)\cdots(t-j+1)}{j!},\qquad
\binom{t}{0}=1.
\]
At a lattice point $J/3$, with $J\in\mathcal I_3$, its value is
$\prod_i\binom{J_i}{I_i}=\mathbf 1_{\{I=J\}}$. Indeed, if $I\ne J$
then some $J_ij$, maximize
lexicographically the tuple
\[
(w,y,i,j),\qquad
w=\|c_i-c_j\|_2^2
\begin{cases}
16,&c_i=\unif\text{ or }c_j=\unif,\\
1,&\text{otherwise}.
\end{cases}
\]
Replace vertex $j$ by the midpoint and recursively check that child; then
replace vertex $i$ by the midpoint and check the other child. Both children
have depth one greater than their parent.
\end{enumerate}
Skipping Type P on cells having a uniform vertex is part of this specified
rule; no claim about the success or failure of that test on such cells is
needed. Lemma~\ref{lem:subdivision} shows that successful termination proves
the required sign on the entire initial domain.
\subsection{The completed verification}
The verifier represents every coefficient matrix by integer numerators and
a common positive denominator, using arbitrary-precision integers for both.
Its polynomial arithmetic consists of convolution, degree elevation,
rational addition, and the exact substitutions of
Lemma~\ref{lem:subdivision}. The fixed-width quantities used for indices,
counters, vertices, and small combinatorial factors remain within their integer
ranges. Appendix~\ref{app:verifiers} proves these bounds and identifies
the implementation routines with the mathematical certificates. Thus a
successful run verifies exact coefficient signs, without a numerical
tolerance.
\begin{proposition}[Finite sign verification]\label{prop:finite-verification}
For each row of \eqref{eq:rational-rows}, the decision rule above terminates
without failure, with the counts in Table~\ref{tab:verification-counts}.
Every terminal cell is accepted by Type T or Type P. Consequently both
rational expressions \eqref{eq:rational-target} are nonnegative on
$\mathcal S\times\mathcal S$.
\end{proposition}
\begin{table}[ht]
\centering
\begin{tabular}{c|r|r|r|r|r}
Row & Cells visited & Maximum depth & Type T leaves & Type P leaves & Unresolved\\
\hline
(a)&4479&19&166&2074&0\\
(b)&1935&20&97&871&0
\end{tabular}
\caption{Exact subdivision counts. The initial cell has depth zero;
visited cells include both internal nodes and terminal cells.}
\label{tab:verification-counts}
\end{table}
\begin{proof}
Run the integer verifier in Appendix~\ref{app:verifiers}, once in each
mode, with assertions enabled. It returns the two lines
\begin{verbatim}
done 4479 19 lp=2074 lt=166
done 1935 20 lp=871 lt=97
\end{verbatim}
Here \texttt{lp} and \texttt{lt} count the terminal cells accepted by
Types P and T. The substitutions are those of Lemma~\ref{lem:subdivision},
and Appendix~\ref{app:implementation} verifies their exact implementation
and the coefficient arithmetic. Lemmas~\ref{lem:type-t} and~\ref{lem:type-p} certify the sign on
each accepted cell, and Lemma~\ref{lem:subdivision} proves coverage. The
continuous extension at zero denominators established in
Section~\ref{sec:polynomial-certificates} includes the cell boundaries.
\end{proof}
For reproduction, the paper directory contains \path{verification/checks/certificate.cpp}
and \path{verification/checks/small_polynomials.py}, printed in full in
Appendix~\ref{app:verifiers}. The first requires a C++17 compiler with
GCC-compatible standard-library headers and the Boost multiprecision
headers; the second uses only the Python 3 standard
library. For example, from the paper's \path{verification/} directory run
\begin{verbatim}
mkdir -p artifacts
g++ -std=c++17 -O3 -UNDEBUG checks/certificate.cpp \
-o artifacts/certificate
./artifacts/certificate
./artifacts/certificate b
python3 checks/small_polynomials.py
\end{verbatim}
The C++ program writes progress and its final result to standard error.
Its no-argument mode checks row (a); any argument selects row (b).
The Python program independently computes the four scalar coefficient
minima of Lemma~\ref{lem:scalar-checks}, using rational convolution, and
checks all 24 coordinate actions. Assertions must remain enabled in both
programs: do not define \texttt{NDEBUG} or run Python with \texttt{-O}.
Together with the scalar checks, Proposition~\ref{prop:finite-verification}
completes the proof of Proposition~\ref{prop:polynomial-inequalities}.
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/06-finite-verification.tex ====
==== BEGIN The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/07-code-appendix.tex ====
\section{Exact implementation and complete verifiers}\label{app:verifiers}
This appendix identifies the array operations with the certificates of
Section~\ref{sec:polynomial-certificates} and bounds the auxiliary
fixed-width arithmetic. The complete source listings follow these
implementation details. The command lines and expected C++ output are
given in Section~\ref{sec:finite-verification}.
\subsection{Exact coefficient arithmetic}\label{app:implementation}
The C++ type \texttt{P} represents a rational coefficient matrix of bidegree
$(r,r)$ by an integer array and a common positive denominator. Its entries
are indexed by $\mathcal I_r$ in descending lexicographic order. Integer
numerators and denominators use \texttt{boost::multiprecision::cpp\_int}.
The routine \texttt{ones(r)} constructs $W_r$; multiplication is ordinary
coefficient convolution, and \texttt{lift} raises both degrees by multiplying
by $W_1$. Addition first lifts to a common degree and then uses a common
denominator. Thus signs are tested on integer numerators, without a
floating-point tolerance.
We explain the correspondence between the remaining routines and the
mathematical certificates; this also fixes the normalizations in the
listing. Initially the coordinates of every vertex are stored as integers
at scale
\begin{equation}\label{eq:vertex-scale}
\kappa=12\cdot2^{24}.
\end{equation}
Removing the factor $2^{24}$ leaves the denominator 12 for the individual
coordinates. The coefficients of $U_v$ are
$4(a_i)_v(b_j)_{\pi(v)}$; their initialization removes $2^{48}$ and uses
denominator 144. The routine \texttt{inv} forms the nine invariant
polynomials in their stated order. The routine \texttt{dot} forms a linear
combination divided by 1000 and homogenizes lower-degree terms with its
third argument. With that argument equal to the homogeneous one it gives
$H(p)$, $F(p)$, or $G(p)$; with that argument equal to $z$ it gives
$z^6H(U/z)$.
There is one useful economy in constructing $K$. A polynomial depending
only on $X$ is nevertheless stored with both degrees equal, so it has the
form $f(X)(\sum_jY_j)^r$. Its column indexed by $(r,0,0,0)$ contains exactly
the coefficients of $f$. Taking this column and the analogous row of a
polynomial depending only on $Y$ gives the outer product used by
\texttt{tensor}. The factor 24 in \texttt{make} then gives exactly the $K$
of \eqref{eq:rational-K}. The array \texttt{t} is the Type T polynomial;
it is constructed once and thereafter restricted by midpoint substitution.
The arrays \texttt{N} and \texttt{D} store $N_\pi$ and $z_\pi$, respectively,
for the 24 permutations in lexicographic order.
The Type P interpolation uses ordinary matrix multiplication. The matrix
\texttt{ev(r,3)} has entries $I^J$, where $I\in\mathcal I_3$ indexes a
node and $J\in\mathcal I_r$ indexes a monomial. Consequently the two-sided
evaluation \texttt{act} must be divided by $3^{2r}$. The listing includes
this factor explicitly, using 9 when $r=1$. The routine \texttt{inverse}
constructs, rather than numerically inverts, the cardinal polynomials
in \eqref{eq:interpolation-polynomial}. It expands their homogeneous
linear factors $3X_h-m\sum_iX_i$, stores their coefficients multiplied by
960, and divides by the factorial denominators. Two-sided interpolation
therefore requires division by $960^2$.
After the node values of $N_\pi/z_\pi^k$ have been truncated toward zero in
multiples of $M^{-1}$, \texttt{testP} constructs the interpolant $J_\pi$.
Its subtraction \texttt{o=b-o} implicitly lifts $N_\pi$ by $W_2$, and hence
constructs precisely $O_\pi=W_2N_\pi-z_\pi^kJ_\pi$.
The array \texttt{w} is $Q_\pi=z_\pi^kW_3$. For each negative coefficient
of $O_\pi$, the program asserts that the corresponding coefficient of
$Q_\pi$ is positive. A violation aborts the verification rather than
merely rejecting that cell; no such violation occurs in the completed
runs. It then computes the integer ceiling in
\eqref{eq:remainder-correction}, by positive integer division, and retains
the largest value. The final test is exactly the coefficient test of
Lemma~\ref{lem:type-p}.
Finally, \texttt{sub} implements \eqref{eq:midpoint-substitution} with
$2^r$ cleared. Its integer multiplier is
\begin{equation}\label{eq:cleared-substitution}
C_t=2^{r-I_i-t}\binom{I_j}{t},\qquad
C_{t+1}=\frac{C_t(I_j-t)}{2(t+1)}.
\end{equation}
Here $r-I_i-t\ge0$ for every used term, so the indicated division is exact.
The resulting matrix denominator is multiplied by $2^r$.
\subsection{Bounds for fixed-width arithmetic}
Only indices, counters, vertex coordinates, and small combinatorial factors use
fixed-width integer types. Take \texttt{int} to have at least 32 bits and
\texttt{long long} to have at least 64 bits. The following bounds cover
every such operation in the listing.
All polynomial matrices in the C++ verifier have bidegree at most 11.
Thus there are at most $\binom{14}{3}=364$ indices in one dimension and
$132\,496$ entries in a matrix. The depth limit 24 allows at most
$2^{25}-1$ visited cells, so the counters for visited cells and terminal
cells also fit a 32-bit signed integer. The largest factorial initialized is
$19!=121\,645\,100\,408\,832\,000<2^{63}$, and products of factorials
appearing in a multinomial denominator do not exceed this bound. The
largest multinomial coefficient through degree 11 is $92\,400$, whose
square is $8\,537\,760\,000<2^{63}$.
Each scaled vertex coordinate belongs to $[0,\kappa]$. Initial products
are bounded by $4\kappa^2$, and even the conservative bound
\[
64\kappa^2
=2\,594\,073\,385\,365\,405\,696<2^{63}
\]
covers the weighted squared edge distances. The initial coordinates are
multiples of $2^{24}$, so all midpoint coordinates are integers through
depth 24. A point of $\mathcal S$ has fourth coordinate at most $1/4$, with
equality only at $\unif$. Thus the test that a stored fourth coordinate is
$\kappa/4$ detects a uniform vertex exactly.
The multipliers in \eqref{eq:cleared-substitution}, including the
intermediate numerator of the recurrence, are bounded by
$11\cdot2^{11}\binom{11}{5}<2^{24}$. The evaluation matrices contain
integers at most $3^6$, and the cardinal-polynomial construction uses only
three linear factors starting from 960. Even bounding the sum of absolute
coefficients at each multiplication by a factor 8 gives
$960\cdot8^3<2^{19}$. All products with polynomial coefficients are already
operations on unlimited integers. These bounds exclude fixed-width
overflow; in particular, the exact sign tests do not rely on floating-point
arithmetic or machine rounding.
\subsection{Rational sign certificates}
\begingroup
\interlinepenalty=10000
\lstinputlisting[language=C++,basicstyle=\ttfamily\scriptsize,
columns=fullflexible,keepspaces=true,breaklines=true,
showstringspaces=false,numbers=left,numberstyle=\tiny,
numbersep=6pt,tabsize=4]{../verification/checks/certificate.cpp}
\endgroup
\subsection{Scalar coefficients and symmetry}
\lstinputlisting[language=Python,basicstyle=\ttfamily\scriptsize,
columns=fullflexible,keepspaces=true,breaklines=true,
showstringspaces=false,numbers=left,numberstyle=\tiny,
numbersep=6pt,tabsize=4]{../verification/checks/small_polynomials.py}
==== END The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model//sections/07-code-appendix.tex ====