Exact three- and four-state reconstruction thresholds and four-state tree capacity

1 · The essentials

These manuscripts ask whether information passed down a branching tree can still reveal the state at its starting point far away. They study systems with three or four possible states. For the tree models covered, the answer is governed by a sharp rule: reconstruction is possible exactly when $d λ^{2} > 1$ , where $d$ describes branching and $λ$ describes how states are transmitted. At equality, reconstruction is not possible. The three-state result covers either sign of the transmission parameter, while the four-state result concerns the ferromagnetic model. A companion manuscript gives a different criterion for four-state transmission on trees whose branching need not be uniform. The main result has a Lean formalization, although the supplied source does not specify which additional claims that formalization covers.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine a message being relayed through a branching chain of people, with each relay potentially changing it. More branches provide more reports, but those reports may carry too little information about the original message; the threshold identifies which effect wins in the specified mathematical models.

Why it matters

The results settle the threshold itself, including the delicate equality case, rather than leaving a gap between possible and impossible reconstruction. The three-state manuscript also connects the tree result to an exact threshold for recovering three communities in a sparse random graph. The four-state capacity criterion extends the question beyond uniformly branching trees.

2 · Going further

The precise question is reconstruction of the root state from states far down a broadcast tree. For the ferromagnetic four-state Potts model, the main manuscript gives the exact Kesten–Stigum threshold on every regular $d$ -ary tree with $d \geq 2$ and every Poisson Galton–Watson tree with mean $d > 0$ : reconstruction occurs exactly when $d λ^{2} > 1$ . Nonreconstruction includes equality. In the Poisson setting, the whole tree is observed, and reconstruction advantage is averaged without conditioning on survival.

The argument's specific ingredient identified in the main abstract is reproducible exact-arithmetic verification of polynomial inequalities. The supplied abstract does not describe the inequalities or the intermediate argument, so a fuller proof outline cannot be extracted from it. The main result has a Lean formalization; the source does not detail its coverage of the companion results.

The capacity companion addresses bounded-degree deterministic rooted trees for the ferromagnetic four-state model with $0 < λ < 1$ . It states that reconstruction occurs exactly when the tree has positive $L^{3}$ capacity with edge resistances $λ^{- 2∣ e ∣}$ . This supplies an exact criterion without regularity or growth-rate assumptions, including at the exponential critical boundary.

The three-state companion gives the same threshold for every regular $b$ -ary tree with $b \geq 2$ , taking $d = b$ , and every observed Poisson Galton–Watson tree with mean $d > 1$ . It includes both signs of $λ$ and nonreconstruction at equality, resolving what the manuscript calls the all-degree three-state regular-tree prediction. Combining its Poisson theorem with known tree-to-graph and algorithmic results, the manuscript gives weak recovery in the symmetric three-community sparse stochastic block model exactly when $(a - b)^{2} > 3 (a + 2 b)$ . This graph statement assumes independent uniform labels, fixed rates $a, b > 0$ , and mean degree $(a + 2 b) /3 > 1$ ; above threshold recovery is achievable in $O (n lo g n)$ time, while at or below it weak recovery is information-theoretically impossible.

Useful notions

Rooted trees and branching
Random transmission of states
Averages over random trees
Thresholds and equality cases
Community recovery in random graphs

What was known before / what is new

Before

The source identifies the threshold as the Kesten–Stigum threshold and describes an all-degree three-state regular-tree prediction. It also refers to known tree-to-graph and algorithmic results used to obtain the graph-recovery conclusion. It does not provide a more detailed history of earlier bounds or cases.

New

The main manuscript establishes the exact four-state ferromagnetic threshold on the stated regular and Poisson trees, including nonreconstruction at equality; the main result has a Lean formalization. The three-state companion reports the exact threshold for either sign of the channel parameter and derives the stated three-community recovery threshold using known results. The capacity companion reports an exact four-state criterion for bounded-degree deterministic rooted trees without regularity or growth-rate assumptions.

Limits and assumptions

The four-state threshold concerns the ferromagnetic model, not arbitrary four-state channels. Regular trees require branching at least two; the Poisson mean ranges are $d > 0$ for four states and $d > 1$ for three states. Poisson trees are observed, and advantage is averaged without conditioning on survival. The capacity criterion requires a bounded-degree deterministic rooted tree and $0 < λ < 1$ . The graph-recovery statement is restricted to the symmetric three-community model and the label, rate, and mean-degree assumptions stated above. The main result has a Lean formalization, but its detailed scope is not supplied, so formal verification of every companion or algorithmic claim is not asserted here. The source lists no further open problems, and no conclusions outside these hypotheses are implied.

Mini glossary

Reconstruction: The task of retaining information about a tree's root state from states far down the tree.
Regular d-ary tree: A rooted tree in which every vertex has exactly $d$ children.
Poisson Galton–Watson tree: A random branching tree whose numbers of children follow a Poisson distribution with the specified mean.
Kesten–Stigum threshold: The boundary $d λ^{2} = 1$ that the source identifies as the exact reconstruction threshold for the stated models.
L³ capacity criterion: The companion manuscript's condition that the tree's $L^{3}$ capacity, with edge resistances $λ^{- 2∣ e ∣}$ , be positive for four-state reconstruction.

Keywords : Reconstruction threshold · Potts broadcasting · Tree capacity

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves the exact reconstruction threshold $d λ^{2} > 1$ , with nonreconstruction at equality, for three-state symmetric and four-state ferromagnetic broadcasting on regular trees (d ≥ 2) and observed Poisson trees (mean d > 1 and d > 0, respectively), with Poisson advantage averaged without conditioning on survival. The three-state theorem allows both signs of λ and gives the exact weak-recovery threshold for the symmetric three-community stochastic block model.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/229.md

Manuscripts in this family

★

The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model

05/10/2026

To be verified

We establish the exact Kesten–Stigum reconstruction threshold for the ferromagnetic four-state Potts broadcast model on every regular d-ary tree with d ≥ 2 and every Poisson Galton–Watson tree of mean d > 0. Reconstruction occurs exactly when $d λ^{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.

PDF GitHub folder

A Capacity Criterion for Four-State Potts Reconstruction on Trees

05/10/2026

To be verified

For the ferromagnetic four-state broadcast model with $0 < λ < 1$ , we prove that reconstruction on a bounded-degree deterministic rooted tree occurs exactly when its L³ capacity with edge resistances $λ^{- 2∣ e ∣}$ is positive. This gives an exact criterion without regularity or growth-rate assumptions on the tree, including at the exponential critical boundary.

PDF GitHub folder

The exact reconstruction threshold for the three-state symmetric channel

25/09/2026

To be verified

We determine the exact reconstruction threshold for the symmetric three-state broadcast process on every regular b-ary tree, b ≥ 2, and every observed Poisson Galton–Watson tree of mean d > 1. Reconstruction occurs exactly when $d λ^{2} > 1$ , with d = b in the regular model; there is non-reconstruction at equality for either sign of the channel parameter. The Poisson advantage is averaged over trees and spins without conditioning on survival. This resolves the all-degree three-state regular-tree prediction. Combining the Poisson theorem with known tree-to-graph and algorithmic results gives the exact weak-recovery threshold for the symmetric three-community sparse stochastic block model with independent uniform labels, fixed within- and between-community rates $a, b > 0$ , and mean degree $(a + 2 b) /3 > 1$ : recovery is possible exactly when $(a - b)^{2} > 3 (a + 2 b)$ . Above this threshold it is achievable in $O (n lo g n)$ time; at or below it, weak recovery is information-theoretically impossible.

PDF GitHub folder