View source for Reconstruction thresholds for Potts broadcasting on trees

The '''reconstruction problem''' for broadcasting on trees asks whether the spins far from the root of a tree still carry information about the root spin. A uniform root spin is copied down the tree through a noisy symmetric channel with second eigenvalue ''λ''. With ''d'' children per vertex, or ''d'' on average, the Kesten–Stigum condition ''dλ''<sup>2</sup> > 1 gives reconstruction. Whether it is also necessary depends on the number of states. Three manuscripts in OpenAI's public mathematics collection ([https://github.com/openai/math github.com/openai/math]) make claims on the three- and four-state Potts channels: exact thresholds on regular and Poisson trees, a capacity criterion on general trees, and the weak-recovery threshold of the three-community stochastic block model. This page summarizes the published claims and lists publicly available follow-up work.

== Background ==
* As recounted in the introductions of the three-state and four-state manuscripts:
** ''Kesten–Stigum.'' The reconstruction direction above ''dλ''<sup>2</sup> = 1 comes from the second-moment analysis of multitype branching processes (Kesten and Stigum, 1966). Evans, Kenyon, Peres and Schulman developed broadcasting on general trees and its relation to the Ising model. For binary symmetric channels, Bleher, Ruiz and Zagrebnov proved sharpness on regular trees, and Mossel showed that the spectral criterion need not be necessary for other channels.
** ''Potts channels.'' Mézard and Montanari predicted that the Kesten–Stigum bound is sharp for small alphabets and discussed the extension to all regular degrees. Sly (2011) proved sharpness for three states on regular trees of sufficiently large degree, including non-reconstruction at equality, and proved that sharpness fails for five or more states (Conjecture 1 of that paper is the all-degree three-state formulation). The four-state case lies at the boundary between these behaviours.
** ''Large degree.'' Mossel, Sly and Sohn (2025) proved non-reconstruction at and below the bound, including the critical point, for three and four states on Galton–Watson trees of sufficiently large mean degree. They also showed that the antiferromagnetic four-state model can reconstruct below the Kesten–Stigum bound.
** ''Small degree.'' Bhatnagar and Maneva proved non-reconstruction for three-colourings of the regular ternary tree with certified finite representations of posterior laws.
** ''Block models.'' Decelle, Krzakala, Moore and Zdeborová predicted the Kesten–Stigum transition for weak recovery in the stochastic block model, and Ricci-Tersenghi, Semerjian and Zdeborová gave further cavity-method evidence for the three-state prediction (either sign) and the four-state ferromagnetic one. Mossel, Sly and Sohn proved information-theoretic impossibility at and below the bound for three or four communities at large mean degree, through a tree-to-graph transfer that has no large-degree restriction; Abbe and Sandon gave an efficient algorithm above the bound.

== The original results ==
* '''Three states (25 September 2026).''' The manuscript ''The exact reconstruction threshold for the three-state symmetric channel'' considers the channel with diagonal entries (1 + 2''λ'')/3 and off-diagonal entries (1 − ''λ'')/3, −1/2 ≤ ''λ'' ≤ 1. The tree is the ''b''-ary tree (''b'' ≥ 2, ''d'' = ''b'') or the Galton–Watson tree with Poisson(''d'') offspring, ''d'' > 1. The observer sees the unlabelled tree through depth ''ℓ'' and the spins at depth ''ℓ''; in the Poisson case the advantage is averaged over trees and spins without conditioning on survival.
** Theorem 1.1: reconstruction occurs if and only if ''dλ''<sup>2</sup> > 1, and there is non-reconstruction at every admissible equality. On the negative side, reconstruction occurs exactly when ''d'' > 4 and −1/2 ≤ ''λ'' < −''d''<sup>−1/2</sup>; in particular the three-colouring channel ''λ'' = −1/2 is non-reconstructible at branching parameter four.
** The manuscript states that this resolves the three-state regular-tree prediction in its all-degree form.
** Corollary 1.2, for the symmetric three-community block model with within- and between-community parameters ''a'', ''b'' > 0 and mean degree (''a'' + 2''b'')/3 > 1: if (''a'' − ''b'')<sup>2</sup> ≤ 3(''a'' + 2''b''), every estimator has expected overlap tending to 1/3; if (''a'' − ''b'')<sup>2</sup> > 3(''a'' + 2''b''), an ''O''(''n'' log ''n'') algorithm achieves overlap at least 1/3 + ''ε'' with probability tending to one. The proof combines the Poisson theorem with the transfer theorem of Mossel, Sly and Sohn and the algorithm of Abbe and Sandon. The cases ''a'' = 0 or ''b'' = 0 are excluded.
** ''Method, as described:'' at positive equality, an entropy functional and an analytic radial inequality; at negative equality, a uniform gap (at every nonuniform symmetric fixed point, the mean squared modulus of the complex posterior mean exceeds 1/20), weighted logarithm identities and, near the colouring channel, certified finite experiments that dominate the true observation. The negative argument is computer-assisted; the programs are printed in an appendix, and the manuscript states that no simulation estimate enters a certification decision.
** ''Programs.'' The README describes a replay (<code>verification/reproduce.py</code>) that succeeds with 37 passing subprocess records, and a supplemental undefined-behaviour check of the interval program.
* '''Four states (5 October 2026).''' The manuscript ''The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model'' considers ''P''<sub>''λ''</sub>(''j'' | ''i'') = ''λ''<b>1</b><sub>{''i'' = ''j''}</sub> + (1 − ''λ'')/4 with 0 ≤ ''λ'' ≤ 1.
** Theorem 1.1: if ''dλ''<sup>2</sup> ≤ 1, the reconstruction advantage tends to zero on the ''d''-ary tree for every integer ''d'' ≥ 2 and on the Poisson(''d'') Galton–Watson tree for every real ''d'' > 0, including equality. With the known Kesten–Stigum direction this gives the exact threshold.
** ''Method, as described:'' a degree-six polynomial ''H'' whose expectation constraint E ''H''(''p'') ≥ 0 on posterior laws is preserved by channel steps and by combining observations, and two polynomial inequalities, give the recursion ''m''<sub>''n''+1</sub> ≤ ''dλ''<sup>2</sup>''m''<sub>''n''</sub> − ''c m''<sub>''n''</sub><sup>3</sup> for the expected quadratic information. The cubic term forces decay at equality. The inequalities are certified by exact-arithmetic programs printed in an appendix.
** ''Programs.'' The README describes a quick check (<code>checks/verify.py</code>) and two full certificate traversals with stated final lines.
* '''Capacity criterion (5 October 2026).''' The manuscript ''A Capacity Criterion for Four-State Potts Reconstruction on Trees'', Theorem 1.1: for the ferromagnetic four-state channel with 0 < ''λ'' < 1 on an infinite deterministic rooted tree with at most ''B'' children per vertex, reconstruction occurs if and only if the ''L''<sup>3</sup> capacity with edge resistances ''λ''<sup>−2|''e''|</sup> is positive. There is no regularity or growth assumption on the tree. The manuscript relates this to the capacity criteria of Pemantle and Peres for the critical Ising model, and imports the posterior moment-saving inequality of the four-state manuscript (its Proposition 3.2).
* '''Sources.''' Commit <code>1581d4c</code> of the openai/math repository:
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026 ''The exact reconstruction threshold for the three-state symmetric channel''] (with its <code>verification/</code> directory);
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026 ''The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model''] (with its <code>verification/</code> directory);
** [https://github.com/openai/math/tree/1581d4cbdd69a0faf34b2089614fe2a814316a6a/preprints/A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees-October-5-2026 ''A Capacity Criterion for Four-State Potts Reconstruction on Trees''].
* '''Formalization, as described by the repository.'''
** The scope note [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/docs/229.md lean/docs/229.md] links only the three-state manuscript. The formalized result is the supercritical direction: reconstruction when ''bλ''<sup>2</sup> > 1 on the ''b''-ary tree and when ''dλ''<sup>2</sup> > 1 on the observed Poisson tree, with the Poisson advantage averaged over trees and spins. The note states: "Non-reconstruction at or below the threshold and the stochastic-block-model consequences in the paper are outside them."
** Two Comparator challenges state this direction: [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/ThreeStateSupercritical.lean ThreeStateSupercritical.lean] (<code>regular_supercritical</code>, <code>poisson_supercritical</code>) and [https://github.com/openai/math/blob/1581d4cbdd69a0faf34b2089614fe2a814316a6a/lean/ComparatorChallenges/ThreeStateTreeClauses.lean ThreeStateTreeClauses.lean] (<code>regular_reconstructs_above_KS</code>, <code>poisson_reconstructs_above_KS</code>).
** The four-state manuscripts are not among the selected statements.

== Public follow-up work ==
{| class="wikitable"
! Date !! Work !! Relation !! Public claim !! Public status (checked 17 October 2026)
|-
| 2026-10-08 || [https://github.com/mathvet/mathvet MathVet] (GitHub; review of openai/math, tables at repository commit <code>c76f1e4</code>, 14 October 2026) || Review (fidelity of the formal statements) || Rates the family "weaker-statement" against its summary. Only the supercritical (Kesten–Stigum) direction for the three-state channel is stated; the exact threshold with non-reconstruction at equality, the four-state case and the block-model threshold are not. Records sandboxed Comparator passes for <code>ThreeStateSupercritical</code> and <code>ThreeStateTreeClauses</code>. || MathVet states that it does not claim any theorem false and reports what was machine-checked as stated.
|-
| 2026-10-08 || J. Guo, [https://github.com/aster2024/openai-math-followups/blob/133da59f528afa0ea185baa3f5f776652749796c/consequences/README.md aster2024/openai-math-followups] (GitHub), consequences list, item 10 || Use (conditional consequence) || Conditional on Theorem 1.1 of the four-state manuscript, and through the transfer theorem of Mossel, Sly and Sohn and the algorithm of Abbe and Sandon: for the symmetric four-community block model with ''a'' ≥ ''b'' > 0 and mean degree (''a'' + 3''b'')/4 > 1, weak recovery is possible exactly when (''a'' − ''b'')<sup>2</sup> > 4(''a'' + 3''b''), and impossible at equality. || The repository states that the list was compiled with AI systems under the author's direction and that the author takes responsibility for its content.
|-
| 2026-10-10 to 2026-10-14 || [https://github.com/leanprover/con-leche/blob/90577d9e49ee3aed45da3d421bdf5dc780192304/DESIGN.md con-leche development journal] (task #348) || Verification (second kernel) || In its run over all Comparator challenges of the collection at commit <code>fd4aeeb</code>, the journal's table of exceptions (time-outs, fuel, memory, errors) lists neither <code>ThreeStateSupercritical</code> nor <code>ThreeStateTreeClauses</code>. Both challenges were therefore accepted by con-leche and by Lean's official kernel. || Development journal.
|-
| 2026-10-10 || cert-machine, openai/math lane K, run 38040214623: [https://github.com/carlostoledo1891/cert-machine/blob/ee027e39e5b91ba93d24cb895e9302e858a73637/corpus/openai-math/kernel-runs/38040214623/ThreeStateSupercritical.json ThreeStateSupercritical], [https://github.com/carlostoledo1891/cert-machine/blob/32739df1a7e9b09f6b56216444fa32927ffdeaad/corpus/openai-math/kernel-runs/38040214623/ThreeStateTreeClauses.json ThreeStateTreeClauses] || Verification (two kernels) || Records that Lean's default kernel and the nanoda kernel accept both solutions (242 s and 237 s). The project reports two-kernel certification of 398 of 416 challenges of the collection. || Repository.
|-
| 2026-10-11 || Christopher D. Long, ''A Sharp Capacity Criterion for Heterogeneous Four-State Potts Broadcasting on Trees'', Paper I of [https://github.com/long-mathematics/openai-math-extensions/tree/bc45a6906e11db8ca737f803058120b1b88fdf3f long-mathematics/openai-math-extensions] (GitHub) || Extends || Extends the capacity criterion to edge-dependent channels with 0 < ''λ''<sub>''e''</sub> ≤ ''q'' < 1 on every locally finite deterministic rooted tree, without a degree bound: reconstruction occurs if and only if the ''L''<sup>3</sup> capacity with path weights given by products of squared edge eigenvalues is positive. Also claims equivalence with robust reconstruction, two-sided comparison of root information with capacity, and an exact series criterion for spherically symmetric trees. The necessity direction imports the four-state moment-saving inequality; the sufficiency direction does not. Without a uniform contraction bound, it proves only a necessary weighted-capacity criterion, and states the full converse as open. || Manuscript and LaTeX source in a GitHub repository, pinned to openai/math commit <code>fd4aeeb</code>.
|-
| 2026-10-10 || cert-machine, openai/math lane F, checks [https://github.com/carlostoledo1891/cert-machine/blob/ee027e39e5b91ba93d24cb895e9302e858a73637/instruments/openaimath/finite/f433_potts_four.py F-433] (four-state) and [https://github.com/carlostoledo1891/cert-machine/blob/ee027e39e5b91ba93d24cb895e9302e858a73637/instruments/openaimath/finite/f435_potts_three.py F-435] (three-state) || Partial verification (finite certificates) || For the four-state manuscript, re-decides in exact arithmetic the single-posterior certificate and the first product inequality on the whole product domain, by a subdivision independent of the manuscript's; the second product inequality is decided only on corner regions, about 0.4% of the domain by volume. For the three-state manuscript, decides the pair coefficient certificate, the grid certificate and the interval inequality on the part of its domain with ''q'' at most 4/5; the near-uniform corner is not decided. Both items are recorded as refused, with the undecided parts attributed to cost. || Repository; the project's [https://github.com/carlostoledo1891/cert-machine/blob/ee027e39e5b91ba93d24cb895e9302e858a73637/certs/openai-math-finite.json ledger] records the decided checks (checked 17 October 2026).
|}

== Notes ==
* The kernel checks above concern the supercritical three-state statements as written. Non-reconstruction at and below the threshold, the four-state theorem, the capacity criterion and the block-model corollary have no formal statement in the collection; the non-reconstruction arguments rely on the manuscripts' exact-arithmetic programs.
* The list covers follow-ups found in public sources up to the date above; it is not a priority or completeness claim.

[[Category:OpenAI results]]