Potts-model reconstruction below the Kesten–Stigum bound

About 22 years old · traced to 2004

Consider the symmetric Potts channel $M$ on $q\geq 3$ symbols, with $b$ -ary tree branching factor $b$ and second eigenvalue $\lambda_2(M)$ . Potts-model below-bound conjecture. There exist $b$ and $\delta$ such that reconstruction is solvable on the $b$ -ary tree, while

b\lambda_2^2(M)<1.

If true, this would show that the Kesten–Stigum bound is not the reconstruction threshold for these Potts models, and that census-only algorithms are inferior to optimal reconstruction.

References

Primary source

Elchanan Mossel, “Survey: Information flow on trees”, arXiv:math/0406446 (2004).

Posted 1 month ago

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

RemarkAI-assistedClaimed by OpenAI. Claims reconstruction for ferromagnetic four-state Potts broadcasting exactly when d lambda^2>1, on every regular d-ary tree with d>=2 and every observed Poisson Galton–Watson tree of mean d>0. Includes nonreconstruction at equality. Poisson advantage averages over the full tree and spins without conditioning on survival. No conclusion for arbitrary q is claimed.See full solutionHide full solution

Claimed by OpenAI. Claims reconstruction for ferromagnetic four-state Potts broadcasting exactly when d lambda^2>1, on every regular d-ary tree with d>=2 and every observed Poisson Galton–Watson tree of mean d>0. Includes nonreconstruction at equality. Poisson advantage averages over the full tree and spins without conditioning on survival. No conclusion for arbitrary q is claimed.

For the ferromagnetic four-state regular-tree models covered here, the source claims that reconstruction does not occur below or at the Kesten–Stigum boundary. This does not assert the same conclusion for every number q>=3 of symbols.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026/four-state-potts.pdf

OpenAI-229-01-The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model.pdf514,729 bytesOpen

RemarkAI-assistedClaimed by OpenAI. Related four-state tree criterion: for the ferromagnetic four-state broadcast model with 0 < λ < 1, the manuscript claims to prove that reconstruction on a bounded-degree deterministic rooted tree occurs exactly when its L3 capacity with edge resistances lambda^(-2|e|) is positive. This gives an exact criterion without regularity or growth-rate assumptions on the tree, including at the exponential critical boundary. No conclusion for arbitrary q is claimed.See full solutionHide full solution

Claimed by OpenAI. Related four-state tree criterion: for the ferromagnetic four-state broadcast model with 0 < λ < 1, the manuscript claims to prove that reconstruction on a bounded-degree deterministic rooted tree occurs exactly when its L3 capacity with edge resistances lambda^(-2|e|) is positive. This gives an exact criterion without regularity or growth-rate assumptions on the tree, including at the exponential critical boundary. No conclusion for arbitrary q is claimed.

This is a four-state ferromagnetic bounded-degree deterministic-tree capacity criterion, related to the regular-tree threshold question. This does not assert the same conclusion for every number q>=3 of symbols.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees-October-5-2026/four-state-capacity.pdf

OpenAI-229-02-A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees.pdf345,473 bytesOpen

RemarkAI-assistedClaimed by OpenAI. Claims to 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 > 1, with d = b in the regular model; there is non-reconstruction at equality for either sign of the channel parameter. No conclusion for arbitrary q is claimed.See full solutionHide full solution

Claimed by OpenAI. Claims to 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 > 1, with d = b in the regular model; there is non-reconstruction at equality for either sign of the channel parameter. No conclusion for arbitrary q is claimed.

For the three-state regular-tree channels covered here, the source claims that reconstruction does not occur below or at the Kesten–Stigum boundary, for either allowed sign of the channel parameter. This does not assert the same conclusion for every number q>=3 of symbols.

GitHub repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026/paper.pdf

OpenAI-229-03-The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel.pdf533,465 bytesOpen