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

What OpenAI claims

Proves the exact reconstruction threshold dλ² > 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. (Lean)

Papers (3)

1. The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model

   5 October 2026 · Preprint, not peer reviewed · PDF

   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λ² > 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.

2. A Capacity Criterion for Four-State Potts Reconstruction on Trees

   5 October 2026 · Preprint, not peer reviewed · PDF

   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 L3 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.

3. The exact reconstruction threshold for the three-state symmetric channel

   25 September 2026 · Preprint, not peer reviewed · PDF

   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λ² > 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+2b)/3 > 1: recovery is possible exactly when (a-b)² > 3(a+2b). Above this threshold it is achievable in O(n log n) time; at or below it, weak recovery is information-theoretically impossible.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.