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. (Lean)
Manuscripts (3)
The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model
October 5, 2026 · source · cite as \cite{OAI:The-Reconstruction-Threshold-for-the-Ferromagnetic-Four-State-Potts-Model-October-5-2026}
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.
A Capacity Criterion for Four-State Potts Reconstruction on Trees
October 5, 2026 · source · cite as \cite{OAI:A-Capacity-Criterion-for-Four-State-Potts-Reconstruction-on-Trees-October-5-2026}
For the ferromagnetic four-state broadcast model with 0\lt \lambda\lt 1, we 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.
The exact reconstruction threshold for the three-state symmetric channel
September 25, 2026 · source · cite as \cite{OAI:The-exact-reconstruction-threshold-for-the-three-state-symmetric-channel-September-25-2026}
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.
Result 229 · Probability and statistical mechanics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.
Source: https://github.com/openai/math/blob/main/CONTENTS.md