When does a tree forget its root?
Three preprints claim exact reconstruction thresholds for three colours and four ferromagnetic colours on trees
Covers result 229 in OpenAI’s catalog: all 3 papers. See its connections to other results and the work it cites.
4:47. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
Play telephone on a family tree. The root gets one of three colours at random; each child copies its parent’s colour, but with noise. Far down the tree you see only the descendants’ colours, and the tree’s shape. Can you guess the root better than chance, by a margin that never fades however deep you look? In a tiny case our computer worked out exactly (two levels, leaves A, A, A, B, a channel that keeps a colour 13 times in 15), the chance the root was A is 733/807, about 91%. The noise is measured by λ, the channel’s second eigenvalue; each generation shrinks the signal by λ and multiplies the witnesses by d, the number of children. Counting colours works exactly when dλ² > 1: the Kesten–Stigum line, from 1966. For two colours nothing does better (at or below the line, nothing works); from five colours up, Allan Sly showed in 2011 that cleverer inference beats the line. Three and four colours were settled only on trees with many children.
Result 229 is three OpenAI preprints, 93 pages, dated September 25 and October 5, 2026. The first claims that for three colours reconstruction happens exactly when dλ² > 1, on every regular tree with at least two children and every Poisson tree with mean above one, for either sign of λ, with no reconstruction at equality; so random proper three-colourings of a tree with four children per vertex forget the root. It also gives the exact threshold for detecting three hidden communities in a sparse random network, (a − b)² > 3(a + 2b) for a, b > 0 and mean degree above one, relying on earlier transfer and algorithm results. The second claims the same line for four colours in the ferromagnetic case only; the other sign can beat the line at some degrees, as Mossel, Sly and Sohn showed. The third shows that for four ferromagnetic colours on any tree with bounded degree, reconstruction happens exactly when a certain flow capacity of the tree is positive.
What it doesn’t claim
Antiferromagnetic four colours, five or more colours, community detection with four groups, rates of decay, or trees with one child per vertex. Parts of the proofs are computer-assisted.
Where it stands
- Posted as preprints
- OpenAI, three papers, 93 pages, dated September 25 and October 5, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- In part (docs)
Last checked October 19, 2026. None of the three preprints has been revised since release. In Lean, the listed comparators check only the classical direction above the line, for three colours; the Lean folders also prove the full threshold for positive λ, and both signs on the binary tree, but none of it is catalogued, and the four-colour papers have no Lean. We reran the two small certificate scripts and they pass; we did not run the long ones. None is among those OSVerify reviewed, and we found no expert reaction.
How the proof goes
- Four colours. One polynomial of degree six whose average stays non-negative at every step down the tree. That buys a small cubic loss of information each time branches combine, so the information falls at every level, even at equality, where the linear loss is zero. The polynomial inequalities are checked by exact computer arithmetic, printed in the paper.
- Three colours, positive λ. Analytic: an entropy bookkeeping that cannot balance at any informative fixed point.
- Three colours, negative λ. Computer-assisted throughout; near the colouring case it adds finite experiments built to be more informative than the truth, and shows even those fall below a certified gap.
The numbers in the video
- Ours, exact: the depth-2 worked example (posterior 733/807, 61/807, 13/807).
- Ours, simulation: three colours on the binary tree to depth 14 by population dynamics, checked against direct simulation on real trees. Below the line the advantage dies away; well above it levels off; at the line it is still 0.23 at depth 14, and at depth 160 the information is still not gone. Simulation cannot settle the threshold case.
Read the source
- The exact reconstruction threshold for the three-state symmetric channel (PDF), 60 pages.
- The Reconstruction Threshold for the Ferromagnetic Four-State Potts Model (PDF), 22 pages.
- A Capacity Criterion for Four-State Potts Reconstruction on Trees (PDF), 11 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 229.
The 3 papers in this result
OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.
Transcript
Read the full script
0:00The question
Play telephone on a family tree. The root gets one of three colors at random. Each child copies its parent’s color, but with some noise: it keeps the color with a certain probability, and otherwise switches. Far down the tree you see only the descendants’ colors, and the tree’s shape. Can you guess the root’s color better than chance, by a margin that never fades, however deep you look? That is the reconstruction problem. Here is a tiny case our computer worked out exactly. Two levels, four leaves, colored A, A, A and B, with a channel that keeps a color 13 times in 15. The chance the root was A is 733/807, about 91%. The noise is measured by one number, λ, the channel’s second eigenvalue. Each generation shrinks the signal by λ, and multiplies the witnesses by d, the number of children. Simply counting colors works exactly when dλ² exceeds one: the Kesten–Stigum line, from 1966. But is counting the best you can do? For two colors, yes: at or below the line, nothing works. For five or more, no: Allan Sly showed in 2011 that, from five colors up, cleverer inference beats the line. Three and four colors sat in between. Sly proved the line exact for three colors on trees with many children, and a 2025 paper by Mossel, Sly and Sohn settled three colors, and four ferromagnetic colors, at large average degree. Small trees stayed largely open.
1:33The claim
Result 229 is three OpenAI preprints, 93 pages, dated September 25 and October 5, 2026. The first claims, for three colors, that reconstruction happens exactly when dλ² exceeds one, on every regular tree with at least two children and every Poisson tree with mean above one, for either sign of λ, with no reconstruction at equality. So a random proper three-coloring of a tree with four children per vertex forgets the root. It also gives the exact threshold for finding three hidden communities in a sparse random network, relying on earlier transfer and algorithm results. The second paper claims the same line for four colors, in the ferromagnetic case only, where children tend to copy; the other sign can beat the line at some degrees, as Mossel, Sly and Sohn showed. The third shows that, for four ferromagnetic colors on any tree with bounded degree, reconstruction happens exactly when a certain flow capacity of the tree is positive.
2:38How the proof goes
Above the line, counting already works. The hard part is the other side, and especially the line itself. For four colors, the proof rests on one polynomial of degree six, whose average stays non-negative at every step down the tree. That buys a small cubic loss of information each time branches combine, so the information falls a little at every level, even at equality, where the linear loss is zero. The polynomial inequalities are checked by exact computer arithmetic, printed in the paper. For three colors and positive λ, the proof is analytic: an entropy bookkeeping that cannot balance at any informative fixed point. For negative λ the argument is computer-assisted throughout; near the coloring case it adds finite experiments built to be more informative than the truth, and shows even those fall below a certified gap. As an illustration, our computer simulated three colors on the binary tree to depth 14, checked against direct simulation on real trees. Below the line, the advantage dies away; well above, it levels off. Exactly at the line it is still 0.23 at depth 14, falling slowly, and at depth 160 the information is still not gone. Simulation could never settle this. That is why the proofs matter.
3:59Where it stands
All three preprints are unrefereed and unchanged since release, and partly computer-assisted. In Lean, the listed comparators check only the classical direction above the line, for three colors; the Lean folders also prove the full threshold for positive λ, and for both signs on the binary tree, but none of it is catalogued, and the four-color papers have no Lean. We reran the two small certificate scripts, and they pass; we did not run the long ones. Not among those OSVerify reviewed, and we found no expert reaction. If they hold, the sixty-year-old Kesten–Stigum line is exactly where trees forget, for three colors and for four ferromagnetic colors, at every degree from two children up.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.