When noisy descendants remember their ancestor: Potts reconstruction thresholds

← All digests

Family 229 · Probability and statistical mechanics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Imagine a message copied down a family tree. Each child receives a noisy version of its parent’s symbol. One distant descendant may remember almost nothing, but there can be exponentially many descendants. Can their combined observations still reveal something about the original message?

This is the reconstruction problem for broadcasting on trees. It connects information theory, statistical mechanics, and community detection in sparse random graphs. A simple second-moment calculation predicts a threshold from the branching rate and the channel’s retained correlation. The prediction is not exact for every alphabet, because nonlinear patterns among descendants can carry information that a linear calculation misses.

Family 229 contains three manuscripts. M1 claims the exact threshold for a ferromagnetic four-state channel on regular and Poisson trees. M2 gives a nonlinear-capacity criterion for that channel on arbitrary bounded-degree deterministic trees. M3 treats the three-state channel with either sign of correlation and derives an exact weak-recovery threshold for a symmetric three-community graph model.

2. Background and essential definitions

Broadcasting and posterior information

Choose the root symbol uniformly from $q$ possibilities. Across each edge, independently conditional on the parent, use the channel

$$P_\lambda(j\mid i)=\lambda\mathbf1_{\{i=j\}}+\frac{1-\lambda}{q}.$$

For positive $\lambda$, the child favors its parent’s symbol: this is the ferromagnetic regime. For three states, the full allowed range is $-1/2\leq\lambda\leq1$. Negative values favor a different symbol. At $\lambda=-1/2$, the child must choose one of the other two colors.

After observing the symbols at distance $n$ from the root, form the posterior vector $p^{(n)}$, whose coordinates are the conditional probabilities of each root symbol. The uniform vector is $u=(1/q,\ldots,1/q)$. Define the average information advantage

$$a_n=\mathbb E\left[\frac12\sum_{i=1}^q|p_i^{(n)}-1/q|\right].$$

This is expected total variation distance from having no information. Reconstruction means $\lim_{n\to\infty}a_n>0$; nonreconstruction means the limit is zero. It does not require recovering the root perfectly.

A regular $d$-ary tree has exactly $d$ children at every vertex. A Poisson Galton–Watson tree has independent offspring counts of mean $d$. Here $d$ counts children or their mean, not total undirected degree. The random tree is independent of the root symbol and is observed along with the relevant boundary spins.

Why the square of the channel parameter appears

A correlation transmitted along a path of length $n$ is scaled by $\lambda^n$. Second-moment information therefore has scale $\lambda^{2n}$, while a regular tree has $d^n$ descendants. Their competition produces

$$(d\lambda^2)^n.$$

The Kesten–Stigum condition $d\lambda^2>1$ is a known sufficient criterion for reconstruction. Showing impossibility at or below one requires control of nonlinear posterior updates. Equality is particularly delicate because the linear factor neither grows nor contracts.

3. Development history and previous partial results

Kesten and Stigum’s work on multitype branching processes supplied the second-eigenvalue scale. Evans, Kenyon, Peres, and Schulman developed the connection between broadcasting and the Ising model, including the role of tree geometry. For more than two symbols, the spectral criterion can cease to be necessary.

Mézard and Montanari proposed threshold coincidence for small alphabets and its extension across branching parameters. Sly’s Potts reconstruction work established the three-state result for sufficiently large regular degree and demonstrated nonsharpness for at least five states. Four states sit at the boundary between these behaviors, where higher-order terms become decisive.

Mossel, Sly, and Sohn established three- and four-state nonreconstruction at and below the spectral bound for sufficiently large mean degree in tree families covering regular and Poisson offspring. The present regular/Poisson claims remove those large-branching restrictions within their stated channel ranges.

For irregular trees, Pemantle and Peres developed critical Ising criteria through nonlinear capacities and concave recursions. M2 adapts that structural viewpoint to four-state reconstruction. Its capacity combines an $L^3$ exponent with squared channel resistances, a different combination from the earlier free- and plus-boundary Ising criteria.

Community detection supplies another motivation. Statistical-physics calculations by Decelle, Krzakala, Moore, and Zdeborová predicted the spectral transition for the assortative three-community model. The established tree-to-graph impossibility transfer and Abbe–Sandon above-threshold algorithms provide the ingredients for M3’s graph consequence once its all-degree Poisson theorem is available.

4. What the new manuscripts claim

Four states on regular and Poisson trees

M1 treats $q=4$ and $0\leq\lambda\leq1$. It claims nonreconstruction whenever

$$d\lambda^2\leq1$$

for every integer $d\geq2$ in the regular model and every real $d>0$ in the Poisson model. Combined with the known reconstruction direction above one, this gives the exact threshold, including nonreconstruction at equality.

For Poisson trees, the whole unlabelled rooted tree is given to the observer. The advantage averages over trees and spins without conditioning on survival. An extinct tree contributes no information at sufficiently deep levels. Above threshold, survival has positive probability and the known surviving-tree reconstruction criterion gives positive averaged advantage.

M1 does not treat negative four-state channel parameters. The manuscript explicitly notes that antiferromagnetic four-state behavior can differ from the claimed ferromagnetic threshold.

Three states, including negative correlation

M3 claims the same strict criterion for all $-1/2\leq\lambda\leq1$, on every regular tree with at least two children per vertex and every observed Poisson tree with mean $d>1$.

In its Poisson formulation, the observer receives the unlabelled tree through the observed level and the symbols on that level, without interior symbols or sibling ordering. The average again is not conditioned on survival.

On the negative side, reconstruction occurs precisely when

$$d>4,\qquad -\frac12\leq\lambda<-\frac1{\sqrt d}.$$

In particular, at $d=4$, the proper three-coloring channel $\lambda=-1/2$ is nonreconstructible in both tree models. This is an endpoint conclusion, not something obtained by leaving equality unspecified.

Irregular four-state trees: the capacity criterion

M2 assumes a deterministic infinite rooted tree with at most some finite number $B$ of children per vertex, and fixes $0<\lambda<1$. Vertices may have zero or one child, and there is no uniform-growth assumption.

A nonnegative flow $\theta$ assigns a number to each edge, conserving incoming and outgoing mass at every nonroot vertex. Its total mass $|\theta|$ leaves the root. For an infinite ray $\xi$, let

$$V_\lambda(\theta,\xi) =\sum_{e\in\xi}\bigl(\lambda^{-2|e|}\theta(e)\bigr)^2,$$

where $|e|$ is the depth of its child endpoint. Define

$$\operatorname{Cap}_{3,\lambda}(T) =\sup\left\{|\theta|:\sup_{\xi}V_\lambda(\theta,\xi)\leq1\right\}.$$

The zero flow is allowed. Positive capacity means that some positive amount can be distributed through the tree while keeping the accumulated nonlinear cost bounded on every ray.

M2 claims reconstruction if and only if this capacity is positive. It therefore sees branching bottlenecks and critical geometry that an exponential growth rate alone can miss. On a regular tree, equally splitting flow makes the path costs a geometric series with ratio $(d\lambda^2)^{-2}$, illustrating the connection to the regular threshold.

The exclusion of $\lambda=1$ matters: an infinite ray then transmits the root perfectly, while the displayed capacity of a single ray is zero.

Three-community weak recovery

In M3’s graph consequence, assign each of $n$ vertices an independent uniform label in $\{1,2,3\}$. Join each pair independently with probability $a/n$ for equal labels and $b/n$ for unequal labels. Assume fixed $a,b>0$ and mean degree $d=(a+2b)/3>1$.

Weak recovery means correctly labeling a fraction greater than $1/3$ by a fixed positive amount, after optimally permuting the three label names. M3 claims the exact condition

$$(a-b)^2>3(a+2b).$$

Above it, an algorithm allowed to depend on $a,b$ achieves weak recovery with probability tending to one in $O(n\log n)$ time. At or below it, every graph-based estimator, including randomized ones, has expected optimized overlap tending to $1/3$.

The translation uses $\lambda=(a-b)/(a+2b)$ and established graph results. The conclusion concerns weak recovery, not exact recovery of every vertex label.

5. Why the advance matters

Importance: 4/5. The family would complete important all-degree small-alphabet threshold predictions and extend four-state reconstruction to arbitrary bounded-degree tree geometry through an exact criterion.

The equality cases are substantive: they decide whether a barely balanced flow of information can persist indefinitely. The graph consequence then turns the three-state classification into a sharp statistical and algorithmic boundary for a widely studied sparse network model.

The capacity theorem also adds information beyond a single critical number. It describes how uneven branching affects reconstruction, making the geometry of the whole tree relevant rather than just its average size at one depth.

The score reflects a major advance at the intersection of probability and inference. The claims remain specific to the stated alphabets and channels; larger-state Potts models can have different thresholds.

6. The main idea

A posterior vector is updated in two stages. Passing through one edge moves it toward the uniform distribution, multiplying its deviation by $\lambda$. Combining child observations then multiplies likelihoods and renormalizes. This second operation is nonlinear, and the observations are independent only conditional on the parent symbol.

For four states, M1 tracks quadratic information together with an additional polynomial statistic of the law of the posterior. It claims a preserved constraint that makes combining two informative branches lose a strictly positive cubic amount. If $m_n$ is expected quadratic information, the resulting estimate has the form

$$m_{n+1}\leq d\lambda^2m_n-cm_n^3, \qquad c>0,$$

in the relevant nontrivial parameter regime. At equality, the cubic loss still forces information to vanish. The source reports exact-arithmetic polynomial certificates for the required inequalities; these are components of its claimed proof, not computations performed for this digest.

M2 uses that posterior-law inequality as an essential companion input. In one direction, surviving information is transformed into a positive flow with bounded path cost. In the other, a capacity flow prescribes how much noise to add to observations at each leaf. Tracking a third moment controls losses while preserving a positive amount of root information, even through irregular branches.

M3 uses entropy identities for positive three-state channels. For negative channels, it separates small posterior information from a possible nonuniform fixed point: such a fixed point must exceed a stated positive gap. Analytic inequalities and finite, more-informative comparison experiments rule out the remaining possibilities, with computer-assisted certificates near the coloring boundary. The graph conclusion then invokes the previously established transfer and algorithmic theorems.

7. Scope, limitations, and open questions

The three-state result allows either sign of correlation; the four-state results are ferromagnetic. Their scopes should not be exchanged. M2’s bounded-degree deterministic-tree criterion does not directly include an unbounded-offspring Poisson tree, which is covered separately by M1.

The Poisson advantages average over extinction as well as survival. The results are not statements that a root can be recovered from every sampled tree. Likewise, reconstruction uses an indefinitely distant full level of symbols, rather than an arbitrary incomplete or adaptively chosen sample.

The graph corollary assumes independent uniform labels, three symmetric communities, positive fixed connectivity rates, and mean degree greater than one. It does not settle all asymmetric or many-community block models, nor exact label recovery.

Extensions to other channels and irregular random trees remain separate questions. The source’s certificate claims are reported as stated; no independent certificate execution or proof verification is part of this exposition.

8. Sources and further reading

Sly and Mossel–Sly–Sohn provide the principal threshold predecessors. Abbe–Sandon supplies the above-threshold algorithmic result used for the graph application. For the irregular-tree viewpoint, see Pemantle and Peres, The critical Ising model on trees, concave recursions and nonlinear capacity, Annals of Probability 38 (2010), 184–206.

M1 below is the four-state regular/Poisson theorem, M2 its capacity companion, and M3 the three-state theorem with its community-detection consequence.

Source manuscripts

• M1. OpenAI, The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model (October 5, 2026).
• M2. OpenAI, A Capacity Criterion for Four-State Potts Reconstruction on Trees (October 5, 2026).
• M3. OpenAI, The exact reconstruction threshold for the three-state symmetric channel (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.