OctoInformBeta

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

§2.1 (setting): parameters and reduction of words: Parameters pp and uu, the five-letter inventory alphabet, freshest-first reduction, and empty-reducing words for Fortuin-Kasteleyn maps

Parameters and stack reduction of inventory words.

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

Random planar maps weighted by Fortuin-Kasteleyn loop percolation are encoded through an exploration walk and an associated inventory process. A rooted planar map MM with n+1n+1 edges is represented by a rotation system (α,σ)(\alpha, \sigma) on the set of 2(n+1)2(n+1) darts 𝒟n={0,1,…,2n+1}\mathcal{D}_n = \{0, 1, \dots, 2n+1\}, quotiented by root-preserving dart relabelling. The dart reversal involution α\alpha is fixed-point free, and its orbits form the edge set E(M)E(M). The vertex rotation permutation σ\sigma cyclically orders darts around each vertex. The map conditions require that the spanning graph on all edges is connected and that the Euler characteristic satisfies V+F=n+3V + F = n + 3, where VV is the number of vertex orbits and FF is the number of face orbits of σ∘α\sigma \circ \alpha. For a subset of active edges A⊆E(M)A \subseteq E(M), the partial reversal involution τA\tau_A reverses darts on edges in AA and fixes all other darts. The orbits of σ∘τA\sigma \circ \tau_A are the alternating boundary loops of the percolation configuration (M,A)(M, A). For a rooted planar map MM with n+1n+1 edges and a loop weight t>0t > 0, the loop polynomial Z(M,t)Z(M, t) is the sum over active edge subsets A⊆E(M)A \subseteq E(M) of tc(M,A)−1t^{c(M, A) - 1}, where c(M,A)=|Orbit⁡(σ∘τA)|c(M, A) = |\operatorname{Orbit}(\sigma \circ \tau_A)| is the number of alternating boundary loops: Z(M,t)=∑A⊆E(M)tc(M,A)−1.Z(M, t) = \sum_{A \subseteq E(M)} t^{c(M, A) - 1}.(1)✦

The partition function of rooted planar maps and the drift parameters of the peeling exploration are determined by the Potts parameter, with the partition function of maps with n+1n+1 edges obtained by summing the loop polynomial over the finite set ℳn\mathcal{M}_n of rooted planar maps with n+1n+1 edges. For a Potts parameter q>4q > 4, the map coefficients an(q)a_n(q) satisfy a0(q)=1a_0(q) = 1 and the relation given in (2): an+1(q)=∑M∈ℳnZ(M,q).a_{n+1}(q) = \sum_{M \in \mathcal{M}_n} Z(M, \sqrt{q}).(2)✦ The peeling exploration corresponds to an inventory random walk whose drift is controlled by a parameter pp. The inventory parameter pp is constrained to the interval 12<p<1.\frac{1}{2} < p < 1.(3)✦ For a given Potts parameter q>4q > 4 with loop weight t=q>2t = \sqrt{q} > 2, the parameter pp is defined by p=qq+2.p = \frac{\sqrt{q}}{\sqrt{q} + 2}.(4)✦ The associated inventory radius uu, which determines the disc of convergence for the percolation generating function, is given by u=1−p16.u = \frac{1 - p}{16}.(5)✦

The exploration process tracks two burger types b1,b2b_1, b_2 and orders produced during map decomposition. An order specifies either a fixed burger type from {b1,b2}\{b_1, b_2\} or a flexible order that accepts either burger type. The set of orders is 𝒪={o1,o2,F},\mathcal{O} = \{o_1, o_2, F\},(6)✦ where o1o_1 and o2o_2 are the fixed orders and FF is the flexible order. The inventory alphabet 𝒜\mathcal{A} is the five-letter set consisting of the two burger types b1,b2b_1, b_2 and the three orders o1,o2,Fo_1, o_2, F: 𝒜={b1,b2,o1,o2,F}.\mathcal{A} = \{b_1, b_2, o_1, o_2, F\}.(7)✦

At each step of the peeling exploration, the state of unmatched items is recorded by an evaluation pair. The set of evaluation states ℰ\mathcal{E} consists of pairs (O,B)(O, B) of a list of unfilled orders O∈𝒪*O \in \mathcal{O}^* and a list of surviving burgers B∈{b1,b2}*B \in \{b_1, b_2\}^*: ℰ=𝒪*×{b1,b2}*.\mathcal{E} = \mathcal{O}^* \times \{b_1, b_2\}^*.(8)✦ The burger list BB is maintained freshest-first, while the order list OO is maintained oldest-first. When a letter arrives, an incoming order consumes the freshest matching burger in BB, or is appended at the end of OO if no matching burger is available; an incoming burger is always pushed onto the burger stack BB and never fills a pending order. Word evaluation runs this transition along a finite word w∈𝒜*w \in \mathcal{A}^*.✦ The reduction reduce⁡(w)\operatorname{reduce}(w) of a finite word w∈𝒜*w \in \mathcal{A}^* is the evaluation state produced by evaluating ww starting from the empty state (∅,∅)(\emptyset, \emptyset).✦

The letters of the exploration walk are independent and identically distributed under a stream law. For a parameter p∈(1/2,1)p \in (1/2, 1), the letter distribution νP\nu_P on 𝒜\mathcal{A} is the probability distribution that assigns mass 1/41/4 to each burger type b1b_1 and b2b_2, mass (1−p)/4(1-p)/4 to each fixed order o1o_1 and o2o_2, and mass p/2p/2 to the flexible order FF. The stream law μP\mu_P is the product measure on the sequence space 𝒜ℕ\mathcal{A}^\mathbb{N}: μP=⨂i=1∞νP.\mu_P = \bigotimes_{i=1}^\infty \nu_P.(9)✦

The Definition

Definition 1. A finite word w∈𝒜*w \in \mathcal{A}^* over the inventory alphabet is empty-reducing if its reduction leaves both the order list and the burger list empty: reduce⁡(w)=(∅,∅).\operatorname{reduce}(w) = (\emptyset, \emptyset).(10)✦

In the paper, the result reads: with parameters t=qt = \sqrt{q}, p=t/(t+2)p = t / (t + 2), and u=(1−p)/16u = (1 - p) / 16, the alphabet contains two burger letters b1,b2b_1, b_2, two fixed order letters o1,o2o_1, o_2, and one flexible order FF, with probabilities ℙ(b1)=ℙ(b2)=1/4\mathbb{P}(b_1) = \mathbb{P}(b_2) = 1/4, ℙ(o1)=ℙ(o2)=(1−p)/4\mathbb{P}(o_1) = \mathbb{P}(o_2) = (1-p)/4, and ℙ(F)=p/2\mathbb{P}(F) = p/2, an order consumes the freshest eligible burger, the reduction of a finite word is its list of unfilled orders followed by its list of surviving burgers, and a word is empty-reducing if both lists are empty.

What Is Checked

The definition of empty-reducing words is stated over the five-letter inventory alphabet, the evaluation state of unmatched orders and surviving burgers, freshest-first word reduction, the parameters p=q/(q+2)p = \sqrt{q}/(\sqrt{q}+2) and u=(1−p)/16u = (1-p)/16 for q>4q > 4, the stream law of independent letters, and the rooted planar map partition function weighted by the loop polynomial. For those constructions, the parameter pp satisfies 1/2<p<11/2 < p < 1 for every q>4q > 4, the letter masses define a probability distribution summing to 11, and the partial edge reversal on darts is an involution.