Can coin flips grow a forest?
A preprint claims the free uniform spanning forest is a factor of IID, by one rule for every graph
Covers result 231 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
4:33. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
A spanning tree of a network is a set of edges that connects every vertex with no loops. On a 3×3 grid there are 192 of them, and David Wilson’s algorithm, built from random walks that erase their own loops, picks one uniformly at random (our 192,000 runs hit every tree about equally often). On an infinite network there are two natural limits: the free forest uses bigger and bigger finite pieces as they are, and the wired forest first glues each piece’s boundary into one point. On the square grid they agree; on a tree where every vertex has three neighbours the free forest keeps every edge and the wired one keeps each with probability two thirds.
Can you build the forest from coin flips? A factor of IID is one fixed rule turning independent random labels on the vertices into the forest, treating every vertex alike, with no root. For the wired forest, Wilson’s method rooted at infinity (Benjamini, Lyons, Peres and Schramm, 2001) does it on transient graphs, as Angel, Ray and Spinka proved in 2021. For the free forest, Russell Lyons asked the question for Cayley graphs in 2013, and Ádám Timár wrote in December 2025 that it was open in full generality.
Result 231 is one OpenAI preprint, 19 pages, dated September 25, 2026. It claims a single rule that works on every infinite, connected, locally finite, simple, unweighted graph at once, turning independent uniform vertex labels into a forest with exactly the law of the free uniform spanning forest; no amenability, transience or degree bound is needed. The same method shows every translation-invariant strongly Rayleigh process on a countable group, including invariant determinantal processes, is a factor of IID under the group’s own translations: the case of a question of Lyons and Thom where the process lives on the group itself.
What it doesn’t claim
A finitary rule, an isomorphism with a Bernoulli shift, weighted graphs, or the fixed-price problem in group theory, for which this is only one of two ingredients Lyons described.
Where it stands
- Posted as a preprint
- OpenAI, 19 pages, dated September 25, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- Yes (docs)
Last checked October 19, 2026. The preprint has not been revised since release. In Lean, two comparators cover the main theorems, about 330 files with no unproved steps; we did not build them, and the item is not yet in the formalization list. A companion paper, result 236, uses the same idea for Ising spins on trees. Not among those OSVerify reviewed; we found no public reaction.
How the proof goes
- Listen, don’t build. Watch every edge through its own noisy channel, Ye(t) = t·Xe + Be(t). Subtract the best guess given everything seen so far; what remains, the innovations, is pure Brownian noise, independent across edges.
- Spanning trees are calm. Shift the evidence on every edge by at most some amount, and no edge’s probability moves by more than half that amount. On a four-cycle each edge is in with probability 3/4 and each pair has covariance −1/16, so the absolute row sum is 3/8 = 2·(3/4)·(1/4).
- Decode backwards. Because of that bound, the noise decodes uniquely, for every input. Feed in fresh noise made from the vertex labels, decode, and out comes a forest with the right law.
The numbers in the video
- Ours: Wilson’s algorithm on the 3×3 grid (192 trees, χ² = 152 on 191 degrees of freedom); free and wired edge probabilities on square-grid boxes (both squeeze to 1/2) and on the 3-regular tree (1 and 2/3).
- Ours: a discretized version of the decoder on the four-cycle and on K4, reading off each edge’s final probability: uniformly random spanning trees out, within sampling error (χ² = 0.9 and 7.5). For a law that is all edges or none, the response grows with the number of edges and the argument breaks.
Read the source
- The free uniform spanning forest is a factor of IID (PDF), 19 pages.
- The Lean formalization notes.
- The collection’s catalog, where this is result 231.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
Take a network and pick one of its spanning trees uniformly at random: a set of edges that connects every vertex with no loops. On a 3×3 grid there are 192 of them, and David Wilson’s algorithm, built from random walks that erase their own loops, picks one perfectly at random. Our computer ran it 192,000 times, and every tree came up about equally often. On an infinite network there are two natural limits. The free forest uses bigger and bigger finite pieces as they are; the wired forest first glues each piece’s boundary into one point. On the square grid they agree: our computation shows the chance of keeping a given edge squeezing to one half from both sides. On a tree where every vertex has three neighbors, they differ: the free forest keeps every edge, the wired one keeps two thirds. Can you build the forest from coin flips? A factor of IID is one fixed rule that turns independent random labels on the vertices into the forest, treating every vertex alike, with no root. For the wired forest, Wilson’s method rooted at infinity, from Benjamini, Lyons, Peres and Schramm in 2001, does it on transient graphs, as Angel, Ray and Spinka proved in 2021. For the free forest, Russell Lyons asked the question for Cayley graphs in 2013, and Ádám Timár wrote in December 2025 that it was open in full generality.
1:27The claim
Result 231 is one OpenAI preprint, 19 pages, dated September 25, 2026. It claims a single rule that works on every infinite, connected, locally finite, simple, unweighted graph at once, and turns independent uniform labels on the vertices into a forest with exactly the law of the free uniform spanning forest. No amenability, no transience, no bound on degrees. The same machine also shows that every translation-invariant strongly Rayleigh process on a countable group, including invariant determinantal processes, is a factor of IID under the group’s own translations. That settles the case of a question by Lyons and Thom where the process lives on the group itself. Not claimed: a finitary rule, an isomorphism with a Bernoulli shift, weighted graphs, or the fixed-price problem in group theory, for which this is only one of two ingredients Lyons described.
2:27How the proof goes
The idea is not to build the forest, but to listen to it. Watch every edge through its own noisy channel: a signal that grows with time if the edge is in the forest, plus Brownian noise. Subtract the best guess given everything seen so far, and what remains, the innovations, is pure Brownian noise, independent across edges. The key fact is that spanning trees are calm. Shift the evidence on every edge by at most some amount, and no edge’s probability moves by more than half that amount. On a four-cycle, each edge is in with probability three quarters, and each pair of edges has covariance minus one sixteenth; the absolute row sum is three eighths, exactly twice three quarters times one quarter. Because of this bound, the noise can be decoded backwards uniquely, for every input. So feed in fresh noise, made from the vertex labels, decode, and out comes a forest with the right law. As an illustration, our computer ran a discretized version of the decoder on the four-cycle and on the complete graph with four vertices, reading off each edge’s final probability: fresh noise in, uniformly random spanning trees out, within sampling error. Negative dependence is what makes it work: for a law that is all edges or none, the response grows with the number of edges, and the argument breaks.
3:50Where it stands
The preprint is unrefereed and unchanged since release. In Lean, two comparators cover the main theorems, about 330 files with no unproved steps; we did not build them, and the item is not yet in the formalization list. A companion paper, result 236, uses the same listening idea for Ising spins on trees. Not among those OSVerify reviewed, and we found no public reaction. If it holds, the free uniform spanning forest can be grown from coin flips on every infinite, connected, locally finite graph, by listening to it through noise and decoding the noise back into a forest.
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.