# The free uniform spanning forest is a factor of IID > One fixed rule builds the free uniform spanning forest from independent random labels on every infinite graph. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-231/ Last updated: 2026-10-14 **One fixed rule builds the free uniform spanning forest from independent random labels on every infinite graph.** **Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 25, 2026 · **Field:** Probability and statistical mechanics · **Entry:** 231 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. A spanning tree connects every point of a network without loops. On infinite networks a random version, the free uniform spanning forest, arises as a limit. The paper proves that one fixed rule can build it from independent random numbers at each point, on every such network. It also proves a similar result for a wider family of random sets on groups. ## At a glance - **First step:** 2013 (Russell Lyons, factor question for the free forest) - **Significance:** Solid. It settles the general factor question for the free uniform spanning forest, which a December 2025 paper listed as open. - **Trust:** Formal proof listed - **Field:** Probability and statistical mechanics (1 paper) ## The explanation Draw a square: four corners, four sides. A spanning tree keeps enough sides to connect all four corners, with no loop. Here that means dropping exactly one side, so there are four spanning trees. Pick one of them at random, each with chance 1/4. Each side then survives with probability 3/4. Now give the sides weights, and make heavy sides more likely to stay. Nudge one weight and every survival chance shifts a little. The paper uses a clean rule for the total shift. For a side kept with probability p, the summed responses equal 2p(1 − p), never more than 1/2[1]. For the square, p = 3/4 gives 2 × 3/4 × 1/4 = 0.375. With uneven weights 1, e, e^(−0.5) and e², the first side's chance becomes about 0.683. Its total response is then about 0.433, again equal to 2p(1 − p). On an infinite graph, such as an endless grid, a random spanning tree can be taken as a limit of finite ones. Grow larger and larger finite pieces, pick a uniform spanning tree in each, and look at the limit[2]. When nothing is glued at the boundary, the result is the free uniform spanning forest. It is a forest, not a tree, because it may split into several pieces. A factor of IID asks for a recipe. Give every vertex its own independent random number, called a label. Then one fixed rule turns all the labels into a choice of edges. The rule may not pick a starting vertex, and it must treat all vertices alike. Lyons discussed this question for the free forest on graphs of groups in 2013[3]. For a related object, the wired forest, a recipe was known on transient graphs[4]. A graph is transient when a random walk on it eventually leaves every region for good. Timár built a recipe for recurrent and invariantly amenable random graphs[5]. Amenable roughly means the graph can be cut into big pieces with small boundaries. His December 2025 paper still listed the general question as open[6]. The paper proves the free uniform spanning forest is a factor of IID on every infinite connected graph with finitely many neighbors per vertex[7]. One rule works for all such graphs at once, and it uses no root[8]. No amenability, no transience and no degree bound is assumed[9]. The rule is measurable, but it need not decide an edge from a bounded region of labels[10]. The obstacle is to draw one sample from the infinite forest, treating every vertex alike, while controlling all the edges together[11]. The paper adapts an observation method that Nam, Sly and Zhang used for Ising spins on trees[12]. Imagine watching each edge through slowly fading noise. Remove the part of what you see that you could already predict. What is left is fresh noise, called innovations, and it is independent across edges[13]. Labels can make such noise directly. The response rule above shows that predictions change only gently when the noise changes. That lets the paper run the process backwards from any noise input[14]. Running it for a long time then reveals which edges belong to the forest[15]. The same method gives a second result. Strongly Rayleigh processes are random sets whose generating polynomial never vanishes in a certain region. They include determinantal processes, which are built from a matrix. On every countable group, a strongly Rayleigh process that looks the same everywhere is a factor of IID[16]. This needs no amenability[17]. How sure is this? Lean, a computer proof checker, has formal versions of both results. The scope note says one equivariant rule works for all such graphs and uses no root. It also lists the group results for strongly Rayleigh and determinantal laws. No specialist review of the paper has been published. **What it doesn't show.** This does not say how far away the rule must look to decide one edge. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Solid if the proof holds. Lean has formal versions of the forest result and the group results; no specialist review is published, and no finitary coding is claimed. ## Words used - **Spanning tree:** A set of edges that connects every vertex of a graph with no loops. - **Free uniform spanning forest:** The limit of uniform random spanning trees on larger and larger finite pieces of an infinite graph, with nothing glued at the boundary. - **Factor of IID:** A fixed rule that turns independent random labels at the vertices into the random object, treating every vertex alike. - **Innovations:** The part of a noisy observation that could not be predicted from what was seen before. - **Strongly Rayleigh process:** A random set whose generating polynomial is never zero when every variable has positive imaginary part. - **Amenable:** Roughly, a graph or group that can be cut into large pieces with relatively small boundaries. ## The original paper - [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf) - September 25, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/231.md) ## Quoted lines from the paper (17) [1] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > Negative off-diagonal covariances and the fixed size of a finite tree give this identity. [2] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > The free uniform spanning forest is obtained by taking weak limits of uniform spanning trees on finite connected exhaustions, without identifying boundary vertices. [3] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > Lyons explicitly discussed the FUSF factor question for the group action on Cayley graphs in his report for the 2013 Oberwolfach workshop. [4] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > On transient graphs, the wired forest has an IID construction through cycle popping and Wilson's algorithm rooted at infinity; see. [5] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > For general graph laws, Tim\'ar proves FIID representability of the free forest on recurrent unimodular random graphs and, more generally, on invariantly amenable unimodular random graphs. [6] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > The introduction to that December 2025 version states the unrestricted FUSF factor question as open. [7] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > We prove that the free uniform spanning forest is a factor of IID on every infinite connected locally finite simple unweighted graph. [8] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > One Borel rule works for all such graphs and uses no root, answering affirmatively the general factor question for unimodular random graphs. [9] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > In particular, no amenability, transience, uniform degree bound, or degree moment is assumed. [10] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > The result asserts an ordinary Borel factor, without a finitary coding radius or a finite input alphabet. [11] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > The challenge is to obtain a single equivariant sample from the infinite-volume law while controlling all edges jointly. [12] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > A particularly close antecedent is Nam, Sly and Zhang: for free Ising measures on regular trees in their parameter range, they obtain FIID codings through Brownian-driven systems with posterior-mean drift and recover spins at large times. [13] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > They are independent Brownian motions. [14] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > The response bound makes the integral equation \[ Z_e(t)=w_e(t)+\int_0^t b_e(s,Z(s))\,ds \] uniquely solvable by a Borel Picard iteration for every continuous input field $w$. [15] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > Integer-time slopes recover $X$. [16] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > We also show that every translation-invariant strongly Rayleigh process indexed by a countable group is a factor of IID, including invariant determinantal processes with Hermitian positive-contraction kernels. [17] From [The free uniform spanning forest is a factor of IID](https://github.com/openai/math/blob/main/preprints/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026/The-free-uniform-spanning-forest-is-a-factor-of-IID-September-25-2026.pdf): > This group-action conclusion requires no amenability. ## Other sources - [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” - [I. Benjamini, R. Lyons, Y. Peres and O. Schramm, “Uniform Spanning Forests”, The Annals of Probability 29(1) (2001), 1–65](https://doi.org/10.1214/aop/1008956321) - [Á. Timár, “Factor of iid's through stochastic domination”, Israel Journal of Mathematics (2025), arXiv:2306.15120](https://doi.org/10.1007/s11856-025-2884-1) - [D. Nam, A. Sly and L. Zhang, “Ising Model on Trees and Factors of IID”, Communications in Mathematical Physics 389(2) (2022), 1009–1046](https://doi.org/10.1007/s00220-021-04260-2) ## Related - [GOE bulk universality for regular graphs with weak Anderson disorder](https://closedform.nishachay.tech/e/openai-math-2026-219/) - Probability and statistical mechanics - [The Benjamini–Schramm nonuniqueness conjecture](https://closedform.nishachay.tech/e/openai-math-2026-214/) - Probability and statistical mechanics - [Critical percolation on every quasi-transitive graph](https://closedform.nishachay.tech/e/openai-math-2026-213/) - Probability and statistical mechanics - [Bounded-degree coboundary expanders](https://closedform.nishachay.tech/e/openai-math-2026-177/) - Combinatorics - [Talagrand’s expectation thresholds, discrete convexity, and graph decompositions](https://closedform.nishachay.tech/e/openai-math-2026-175/) - Combinatorics - [Probability and statistical mechanics](https://closedform.nishachay.tech/science/mathematics/probability-and-statistical-mechanics/) - Field · 29 results - [Graph theory](https://closedform.nishachay.tech/topic/graph-theory/) - Topic · 40 results - [Open since the 2010s](https://closedform.nishachay.tech/open-since/2010s/) - Era · 31 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Solid results](https://closedform.nishachay.tech/significance/solid/) - Significance · 50 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20231%5D%20)