Browse › Probability and statistical mechanics › 229 Exact three- and four-state reconstruction thresholds and four-state tree capacity
The exact reconstruction threshold for the three-state symmetric channel
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
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\lambda^2\gt 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\gt 0$, and mean degree $(a+2b)/3\gt 1$: recovery is possible exactly when $(a-b)^2\gt 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.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Formalization
- OpenAI, Exact three- and four-state reconstruction thresholds and four-state tree capacity — Lean scope (OpenAI Math Release, lean/docs/229.md, 2026-10-06). The scope note records formalization of three-state reconstruction above the Kesten–Stigum threshold ($b\lambda^2>1$ or $d\lambda^2>1$) on regular and observed Poisson trees, excluding non-reconstruction at or below the threshold and the stochastic-block-model consequences. [family-level]
- OpenAI math release, ThreeStateSupercritical.lean (lean/ComparatorChallenges, release of 2026-10-06). The comparator statement file gives the Lean statements
regular_supercriticalandpoisson_supercriticalfor reconstruction above the Kesten–Stigum threshold in the regular and Poisson models.
Possibly relevant literature (found by the agent, not checked)
- Yuzhou Gu and Yury Polyanskiy, Uniqueness of BP fixed point for the Potts model and applications to community detection (arXiv:2303.14688, 2023). Studies BP fixed-point uniqueness for $q$-ary Potts broadcasting on Galton–Watson trees, with consequences for the $q$-community block model, which is the setting of the paper's Corollary (three-community weak recovery).
- M. Formentin and C. Külske, On the Purity of the free boundary condition Potts measure on random trees (arXiv:0810.0677, 2008). Gives explicit non-reconstruction (extremality) ranges for Potts channels on random trees, described as close to conjectured values for $q=3$, a precursor setting for the paper's Poisson-tree non-reconstruction statement; the paper cites a different Formentin–Külske article (the symmetric-entropy bound).
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 229
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026,
author = {{OpenAI}},
title = {{The exact reconstruction threshold for the three-state symmetric channel}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026/paper.pdf}{OAI:The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026}},
year = {2026}
}From OpenAI's README for this paper:
Verification
Use Python 3.9 or newer with SymPy, and a g++ supporting C++17, signed __int128, and a plain int type of at least 32 bits. Run from this paper directory, choosing a new output directory outside verification/:
python3 -B verification/reproduce.py --output-dir .verification-output --jobs 2
The complete replay succeeds when .verification-output/summary.json has passed: true and 37 passing subprocess records. Do not use Python's -O or -OO options or define NDEBUG.
Run the supplemental interval undefined-behavior check as well:
g++ -std=c++17 -O2 -UNDEBUG -fsanitize=undefined -fno-sanitize-recover=undefined verification/interval.cpp -o .verification-output/interval-ubsan
for j in 0 1 2; do .verification-output/interval-ubsan "$j"; done
All three cases must exit zero without sanitizer diagnostics and end at visited-box totals 414080, 756096, and 1004426, respectively. verification/README.md is the verification guide.
Lean formalization
OpenAI provides Lean files for this family: lean/docs/229.md. The Lean statements have not been checked by people against the paper's claims.
Family 229: Exact three- and four-state reconstruction thresholds and four-state tree capacity
Proves the exact reconstruction threshold $d\lambda^2\gt 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.
Other papers in this family:
- The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model · October 5, 2026
- A Capacity Criterion for Four-State Potts Reconstruction on Trees · October 5, 2026