VibeMathedMath problems solved with AI
Sign in

Sharpness of the Kesten-Stigum reconstruction threshold for three-state symmetric and ferromagnetic four-state Potts channels on trees

A root spin, uniform on qq states, is broadcast down a tree through a symmetric channel with second eigenvalue λ\lambda; reconstruction means the spins at depth ℓ\ell keep non-vanishing information about the root. Kesten-Stigum gives reconstruction when dλ2>1d\lambda^2>1 (dd the branching number); Sly showed this is not sharp for q≥5q\ge5, and proved sharpness for q=3q=3 on regular trees of large degree. Mezard and Montanari conjectured sharpness for three states (either sign of λ\lambda) and small alphabets, and discussed all branching parameters. For q=3q=3 and for the ferromagnetic q=4q=4 channel, on every regular tree and every Poisson Galton-Watson tree, is there non-reconstruction whenever dλ2≤1d\lambda^2\le1?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Broadcasting on trees; reconstruction and community detection
Posed by
Marc Mezard and Andrea Montanari (Reconstruction on trees and spin glass transition, J. Stat. Phys. 2006, Conjecture 2 and Section 8); all-degree regular-tree form in Allan Sly (2011, Conjecture 1)
Year posed
2006
Years open
20y
Solved
2026-09-25
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
28 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Three-state theorem: for the symmetric channel with −1/2≤λ≤1-1/2\le\lambda\le1, on every bb-ary tree (b≥2b\ge2) and every observed Poisson(dd) tree with d>1d>1, reconstruction holds iff dλ2>1d\lambda^2>1, with non-reconstruction at equality for both signs (so the 3-coloring channel is non-reconstructible at branching four). Corollary: weak recovery in the symmetric three-community sparse block model is possible iff (a−b)2>3(a+2b)(a-b)^2>3(a+2b). Four-state theorem: for the ferromagnetic channel (0≤λ≤10\le\lambda\le1), non-reconstruction whenever dλ2≤1d\lambda^2\le1 on dd-ary and Poisson trees. Companion: an L3L^3-capacity criterion for four-state reconstruction on bounded-degree trees. Not shown: the antiferromagnetic four-state channel.

What the AI did

Produced by an unreleased internal OpenAI model as part of OpenAI's openai/math release. The release README says the results used one fixed procedure averaging about three hours of ChatGPT Pro thinking compute per result; this family is not among the README's stated exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscripts are authored as OpenAI with no human author named.

Verification

No independent mathematician has checked this yet. Checked here: abstracts, introductions and main theorems of the three manuscripts, read against the Mezard-Montanari and Sly conjectures as quoted; proofs not refereed. Both threshold papers are computer assisted (certified finite recursions near the coloring channel; exact-arithmetic verification of polynomial inequalities for four states), and those programs were not rerun here. Lean: the release's Comparator challenges ThreeStateSupercritical and ThreeStateTreeClauses cover only reconstruction above the Kesten-Stigum threshold, the classical direction, not non-reconstruction at or below it, so the tier is unreviewed. The stochastic block model corollary also imports Mossel-Sly-Sohn and Abbe-Sandon.

Sources

Changelog1 change

Discussion