Browse › Probability and statistical mechanics › 229 Exact three- and four-state reconstruction thresholds and four-state tree capacity
The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model
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 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\lambda^2\gt 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.
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.
Follow-up works
- Christopher D. Long, A Sharp Capacity Criterion for Heterogeneous Four-State Potts Broadcasting on Trees (GitHub preprint, 2026-10-11). Extends the two four-state papers to locally finite deterministic trees with edge-dependent eigenvalues satisfying $0<\lambda_e\le q<1$, claiming an exact $L^3$ capacity criterion whose necessity direction uses the threshold paper’s posterior moment-saving inequality. [family-level]
Possibly relevant literature (found by the agent, not checked)
- Wenjian Liu and Ning Ning, The non-tightness of the reconstruction threshold of a 4 states symmetric model with different in-block and out-block mutations (arXiv:1906.09479, 2019). Gives conditions for non-tightness of the Kesten–Stigum bound in a four-state model with distinct in-block and out-block transition probabilities, a contrast to the paper's tightness claim for the fully symmetric ferromagnetic four-state channel.
- 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 ranges for Potts channels on random trees, described as close to conjectured values for $q=4$, the regime of the paper's Poisson-tree theorem; the paper cites a different Formentin–Külske article (the symmetric-entropy bound).
- Yuzhou Gu and Yury Polyanskiy, Uniqueness of BP fixed point for the Potts model and applications to community detection (arXiv:2303.14688, 2023). Reports that for $q\ge4$, BP fixed-point uniqueness fails in some regimes below the Kesten–Stigum threshold, which bears on the paper's remark that four states lies at the boundary between sharp and non-sharp behaviour.
Elsewhere
- Emergent Mind: family 229
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026,
author = {{OpenAI}},
title = {{The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026/four-state-potts.pdf}{OAI:The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026}},
year = {2026}
}From OpenAI's README for this paper:
Verification
Use Python 3 without optimization, GCC-compatible C++17 with bits/stdc++.h
and Boost Multiprecision headers, and undefined-behavior sanitizer support.
From a temporary working copy of verification/, run:
python3 checks/verify.py
This reruns the rational polynomial checks and focused UBSan safety harness,
then checks the original source binding and retained full-traversal records.
Success writes artifacts/checks/verification.json with passing scalar,
symmetry, safety, and recorded-run checks; it does not repeat the long
certificate traversals. To repeat those full checks from the same directory:
mkdir -p artifacts
g++ -std=c++17 -O3 -UNDEBUG checks/certificate.cpp -o artifacts/certificate
./artifacts/certificate
./artifacts/certificate b
python3 checks/small_polynomials.py
The C++ modes must end with done 4479 19 lp=2074 lt=166 and
done 1935 20 lp=871 lt=97, respectively. Assertions must remain enabled.
The exact certificate and scalar-check sources in verification/checks/
are also the paper's code-listing inputs.
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:
- A Capacity Criterion for Four-State Potts Reconstruction on Trees · October 5, 2026
- The exact reconstruction threshold for the three-state symmetric channel · September 25, 2026