OctoInformBeta

OpenAI preprint, September 2026 · §2. Words and strict drift · §2

Proposition 2.2 [Finite word identity]: Bijection between tree-decorated maps and words, deletion-contraction recurrence, and anuna_n u^n from inventory words for Fortuin-Kasteleyn maps

Empty-reducing word probabilities match rooted map partition functions.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

For random planar maps weighted by Fortuin-Kasteleyn percolation with cluster weight q>4q > 4, the partition function of maps decorated by spanning trees can be computed through a bijection with words in an inventory alphabet. The inventory processes burgers and orders along a stack. An inventory word is empty-reducing when its execution consumes all burgers and satisfies all orders, leaving an empty stack. The central identity equates the probability that an independent inventory word of length 2n2n is empty-reducing to anuna_n u^n, where ana_n is the partition coefficient of maps with nn edges and u=(1−p)/16u = (1-p)/16 is the inventory radius with p=q/(q+2)p = \sqrt{q}/(\sqrt{q}+2). These notes go through that identity, the map-word bijection, and the definitions they are built on.

Planar Maps and Spanning Trees

A dart dd of size nn is an element of the finite set Dart⁡n={0,…,2n+1}\operatorname{Dart}_n = \{0, \dots, 2n+1\} indexing the 2(n+1)2(n+1) directed edges of a map with n+1n+1 edges.✦ An orbit [d]s[d]_s of a dart d∈Dart⁡nd \in \operatorname{Dart}_n under a permutation ss of Dart⁡n\operatorname{Dart}_n is the equivalence class of dd under the cyclic subgroup generated by ss✦, and the orbit set Orb⁡(s)\operatorname{Orb}(s) is the set of all such orbits.✦ The spanning subgraph G(a,s,A)G(a, s, A) associated with permutations aa and ss on Dart⁡n\operatorname{Dart}_n and a set of edge orbits A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a) is the simple graph with vertex set Orb⁡(s)\operatorname{Orb}(s) and an undirected edge between vv and ww whenever there exists a dart d∈Dart⁡nd \in \operatorname{Dart}_n with [d]a∈A[d]_a \in A, [d]s=v[d]_s = v, and [a(d)]s=w[a(d)]_s = w.✦ The unordered endpoints edgeEnds⁡(a,s,e)\operatorname{edgeEnds}(a, s, e) of an edge orbit e∈Orb⁡(a)e \in \operatorname{Orb}(a) under permutations aa and ss are the vertex orbits {[d]s,[a(d)]s}\{[d]_s, [a(d)]_s\} for any representative dart d∈ed \in e.✦

A pair of permutations (a,s)(a, s) on Dart⁡n\operatorname{Dart}_n satisfies the planar map conditions if aa is a fixed-point-free involution, the spanning graph G(a,s,Orb⁡(a))G(a, s, \operatorname{Orb}(a)) is connected, and the orbit counts satisfy the genus zero relation |Orb⁡(s)|+|Orb⁡(sa)|=n+3.|\operatorname{Orb}(s)| + |\operatorname{Orb}(s a)| = n + 3.(1)✦ A labelled planar map (a,s)(a, s) of size nn is a pair of permutations on Dart⁡n\operatorname{Dart}_n satisfying the planar map conditions.✦ An isomorphism of rooted maps rr between labelled planar maps (a,s)(a, s) and (a′,s′)(a', s') of size nn is a permutation of Dart⁡n\operatorname{Dart}_n fixing the root dart 00 such that rar−1=a′r a r^{-1} = a' and rsr−1=s′r s r^{-1} = s'.✦ A rooted planar map MM of size nn is an isomorphism class of labelled planar maps of size nn under root-preserving isomorphism.✦ For a rooted planar map MM of size nn represented by permutations (a,s)(a, s), the dart reversal involution aa is the permutation swapping opposite darts✦, the vertex rotation permutation ss is the permutation cyclically ordering darts around each vertex✦, and the edge set Edge⁡(M)\operatorname{Edge}(M) is the set of dart orbits under aa.✦

A multiforest AA for permutations (a,s)(a, s) on Dart⁡n\operatorname{Dart}_n is a subset of edge orbits A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a) such that the spanning subgraph G(a,s,A)G(a, s, A) is acyclic without self-loops and edge endpoints are injective on AA.✦ The spanning tree completions treeExtensions⁡(a,s,C,R)\operatorname{treeExtensions}(a, s, C, R) of an edge subset C⊆Orb⁡(a)C \subseteq \operatorname{Orb}(a) within an edge subset R⊆Orb⁡(a)R \subseteq \operatorname{Orb}(a) for permutations (a,s)(a, s) on Dart⁡n\operatorname{Dart}_n are the collection of all edge subsets extending CC to a spanning tree of the map within C∪RC \cup R.✦ A tree-decorated rooted map (M,T)(M, T) of size nn is a pair consisting of a rooted planar map MM of size nn and a spanning tree T⊆Edge⁡(M)T \subseteq \operatorname{Edge}(M) of edges of MM.✦ For an involution aa on Dart⁡n\operatorname{Dart}_n and an edge subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a), the partial dart reversal aAa_A is the permutation of Dart⁡n\operatorname{Dart}_n that swaps dd and a(d)a(d) when [d]a∈A[d]_a \in A and fixes dd otherwise.✦

The loop polynomial Zloop(t,M)Z_{\mathrm{loop}}(t, M) of a rooted planar map MM of size nn at parameter t>0t > 0 is the sum over edge subsets Zloop(t,M)=∑A⊆Edge⁡(M)t|Orb⁡(s⋅aA)|−1,Z_{\mathrm{loop}}(t, M) = \sum_{A \subseteq \operatorname{Edge}(M)} t^{|\operatorname{Orb}(s \cdot a_A)| - 1},(2)✦ where aAa_A is the partial dart reversal along AA. The rooted map partition function ana_n is defined by a0=1a_0 = 1 and, for each integer n≥0n \ge 0, by the sum of loop polynomials an+1=∑M∈ℳnZloop(q,M),a_{n+1} = \sum_{M \in \mathcal{M}_n} Z_{\mathrm{loop}}(\sqrt{q}, M),(3)✦ where ℳn\mathcal{M}_n is the collection of all rooted planar maps of size nn. For an edge subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a), the submap component count c(a,s,A)c(a, s, A) is the number of connected components of the spanning subgraph G(a,s,A)G(a, s, A).✦ For a parameter t>0t > 0, permutations aa and ss on Dart⁡n\operatorname{Dart}_n, and edge subsets C,B⊆Orb⁡(a)C, B \subseteq \operatorname{Orb}(a), the residual configuration weight Wres(t,a,s,C,B)W_{\mathrm{res}}(t, a, s, C, B) is Wres(t,a,s,C,B)=t2c(a,s,C∪B)+|B|−c(a,s,C)−1.W_{\mathrm{res}}(t, a, s, C, B) = t^{2 c(a, s, C \cup B) + |B| - c(a, s, C) - 1}.(4)✦ The residual partition function Zres(t,a,s,C,R)Z_{\mathrm{res}}(t, a, s, C, R) is the sum of residual weights (4) over all subsets B⊆RB \subseteq R: Zres(t,a,s,C,R)=∑B⊆RWres(t,a,s,C,B).Z_{\mathrm{res}}(t, a, s, C, R) = \sum_{B \subseteq R} W_{\mathrm{res}}(t, a, s, C, B).(5)✦

A canonical rooted tree map (a,s,A)(a, s, A) of size nn is a triple where (a,s)(a, s) satisfies the planar map conditions (1) and the edge subset AA forms a spanning tree such that the tree tour s⋅aAs \cdot a_A equals the standard cyclic permutation (01…2n+1)(0 \, 1 \, \dots \, 2n+1) on Dart⁡n\operatorname{Dart}_n.✦ For any permutation pp of Dart⁡n\operatorname{Dart}_n consisting of a single cycle, the root tour numbering permutation is the permutation of Dart⁡n\operatorname{Dart}_n defined by i↦pi(0)i \mapsto p^i(0).✦ The canonicalization to tree normal form is the map sending a labelled planar map and a spanning tree of edges to a canonical rooted tree map by relabelling darts along the tour.✦ The rooted spanning tree canonical bijection is the bijection mapping each tree-decorated rooted map (M,T)(M, T) of size nn to its canonical rooted tree map in canonical normal form.✦ For a dart permutation rr of Dart⁡n\operatorname{Dart}_n, the permutation conjugation is the map sending a permutation pp to r−1prr^{-1} p r✦, and the orbit relabelling equivalence is the induced bijection between Orb⁡(r−1pr)\operatorname{Orb}(r^{-1} p r) and Orb⁡(p)\operatorname{Orb}(p).✦ For a dart permutation rr of Dart⁡n\operatorname{Dart}_n, the relabelling of an edge subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a) under an involution aa is the edge subset under r−1arr^{-1} a r obtained by pushforward along the inverse of the orbit relabelling equivalence.✦

Inventory Words and Stack Evaluation

An inventory order type is an element of the set {flexible⁡,fixed⁡(0),fixed⁡(1)}\{\operatorname{flexible}, \operatorname{fixed}(0), \operatorname{fixed}(1)\}, where flexible\operatorname{flexible} represents an order satisfied by either burger type.✦ An inventory alphabet letter is either a burger of boolean type b∈{0,1}b \in \{0, 1\} or an inventory order type.✦ A typed burger-order letter is either a burger of boolean type b∈{0,1}b \in \{0, 1\} or a fixed order of boolean type b∈{0,1}b \in \{0, 1\}.✦ An inventory stack evaluation state (O,B)(O, B) is a pair consisting of a list of pending orders OO and a list of available burgers BB stored freshest-first.✦ The evaluation of a word is the transition map on inventory stack evaluation states obtained by processing letters sequentially, pushing each burger onto the burger stack, and letting each order consume the freshest eligible burger or join the pending orders when no match is available.✦ The word reduction reduce⁡(w)\operatorname{reduce}(w) is the evaluation state obtained by processing a word ww starting from empty stacks.✦ A word ww of alphabet letters is empty-reducing if reduce⁡(w)=(∅,∅)\operatorname{reduce}(w) = (\emptyset, \emptyset).✦

The Fortuin-Kasteleyn parameter is p=q/(q+2)∈(1/2,1)p = \sqrt{q}/(\sqrt{q}+2) \in (1/2, 1) for q>4q > 4✦, with inventory radius u=(1−p)/16u = (1-p)/16.✦ The letter mass function mm assigns to each letter aa probability 1/41/4 to each burger type, p/2p/2 to the flexible order, and (1−p)/4(1-p)/4 to each fixed order type: m(a)={1/4if a is a burger,p/2if a is a flexible order,(1−p)/4if a is a fixed order.m(a) = \begin{cases} 1/4 & \text{if } a \text{ is a burger}, \\ p/2 & \text{if } a \text{ is a flexible order}, \\ (1-p)/4 & \text{if } a \text{ is a fixed order}. \end{cases}(6)✦ The letter distribution is the probability measure on the inventory alphabet with masses given by (6)✦, and the inventory stream measure is the infinite product measure of the letter distribution on infinite sequences of letters.✦ The letter stream initial word of length NN is the prefix consisting of the first NN letters of an inventory stream.✦ The empty-reducing word probability emptyProb⁡(p,N)\operatorname{emptyProb}(p, N) is the probability under the inventory stream measure that the initial word of length NN is empty-reducing.✦

The canonical tour matching word wa,Aw_{a, A} of an involution aa on Dart⁡n\operatorname{Dart}_n and an edge subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a) is the sequence of typed letters defined on darts i∈Dart⁡ni \in \operatorname{Dart}_n by wa,A(i)={burger⁡(𝟏{[i]a∈A})if i<a(i),order⁡(𝟏{[i]a∈A})if i>a(i).w_{a, A}(i) = \begin{cases} \operatorname{burger}(\mathbf{1}_{\{[i]_a \in A\}}) & \text{if } i < a(i), \\ \operatorname{order}(\mathbf{1}_{\{[i]_a \in A\}}) & \text{if } i > a(i). \end{cases}(7)✦ The typed word stack execution is the evaluation map sending a sequence of typed letters and a boolean burger stack to an updated stack upon successful matching or failure upon illegal closure.✦ A successful dart word ww of size nn is an assignment from Dart⁡n\operatorname{Dart}_n to typed letters whose typed stack execution across the standard dart order empties the boolean stack, with 𝒲n\mathcal{W}_n denoting the set of all such words.✦ The canonical tree tour word of a canonical rooted tree map (a,s,A)(a, s, A) is the successful dart word wa,Aw_{a, A} defined by (7).✦ The canonical tree word equivalence is the bijection between canonical rooted tree maps of size nn and successful dart words in 𝒲n\mathcal{W}_n given by the tour matching word.✦ The rooted map-word bijection Φn\Phi_n is the composite bijection identifying tree-decorated rooted maps of size nn with successful dart words in 𝒲n\mathcal{W}_n.✦ The flexible closing count k(w)k(w) is the number of flexible order closures encountered when evaluating a typed word ww against an initially empty boolean stack.✦

The Claim

Theorem 1. Let q>4q > 4, t=qt = \sqrt{q}, p=t/(t+2)p = t / (t + 2), and u=(1−p)/16u = (1-p)/16. For every integer n≥0n \ge 0, the inventory identity holds: anun=emptyProb⁡(p,2n).a_n u^n = \operatorname{emptyProb}(p, 2n).(8)✦ For every integer n≥0n \ge 0, the empty-reducing word probability is given by the Fortuin-Kasteleyn sum emptyProb⁡(p,2(n+1))=un+1∑M∈ℳnZloop(q,M).\operatorname{emptyProb}(p, 2(n+1)) = u^{n+1} \sum_{M \in \mathcal{M}_n} Z_{\mathrm{loop}}(\sqrt{q}, M).(9)✦ For every t≠0t \ne 0 and every function F:ℳn→ℝF \colon \mathcal{M}_n \to \mathbb{R}, the weighted pushforward to words satisfies ∑M∈ℳnF(M)Zloop(t,M)=∑w∈𝒲nF(π(w))(1+t)k(w),\sum_{M \in \mathcal{M}_n} F(M) Z_{\mathrm{loop}}(t, M) = \sum_{w \in \mathcal{W}_n} F(\pi(w)) (1+t)^{k(w)},(10)✦ Here 𝒲n\mathcal{W}_n is the set of successful dart words of size nn, π(w)\pi(w) is the underlying rooted map of the tree-decorated map Φn−1(w)\Phi_n^{-1}(w), and k(w)k(w) is the flexible closing count. For permutations aa and ss on Dart⁡n\operatorname{Dart}_n with aa an involution, finite subsets of edge orbits CC and RR, and an edge orbit e∉Re \notin R whose endpoints are disconnected in the spanning subgraph G(a,s,C)G(a, s, C), the residual partition function satisfies the deletion-contraction recurrence Zres(t,a,s,C,R∪{e})=Zres(t,a,s,C,R)+Zres(t,a,s,C∪{e},R).Z_{\mathrm{res}}(t, a, s, C, R \cup \{e\}) = Z_{\mathrm{res}}(t, a, s, C, R) + Z_{\mathrm{res}}(t, a, s, C \cup \{e\}, R).(11)✦ For an integer N≥1N \ge 1, any fixed-point-free involution aa on {0,…,N−1}\{0, \dots, N-1\}, and any function c:{0,…,N−1}→{0,1}c \colon \{0, \dots, N-1\} \to \{0, 1\} constant on orbits of aa without monochromatic crossings, the flexible closing count of the matching word equals the outer chord count (12). k(wa,c)=∑i=0N−1𝟏{a(i)<i and ∄j,a(i)<j<i<a(j)}.k(w_{a,c}) = \sum_{i = 0}^{N-1} \mathbf{1}_{\{a(i) < i \text{ and } \nexists j, \, a(i) < j < i < a(j)\}}.(12)✦

In the paper, the result reads: for every integer n≥0n \ge 0, an independent word of length 2n2n satisfies ℙ(the word is empty-reducing)=anun\mathbb{P}(\text{the word is empty-reducing}) = a_n u^n.

What Is Checked

The identities (8) and (9) are stated over the Potts parameter q>4q > 4 and the inventory stream measure. The transport formula (10) is stated over rooted planar maps and successful dart words, the deletion-contraction recurrence (11) over dart permutations and confirmed forests, and the chord identity (12) over non-crossing involutions.

The library establishes that dart relabelling preserves the planar map conditions✦, that partial dart reversal is an involution✦, that cycle tour numbering is bijective✦, and that the canonical normal form of tree-decorated rooted maps is a bijection.✦