OctoInformBeta

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

Corollary 2.3 [Catalan upper bound]: Empty-reducing words as Dyck excursions bounded by killed random walks, and summability at the inventory radius u=(1−p)/16u = (1-p)/16

Endpoint summability for Fortuin-Kasteleyn maps with q>4q > 4..

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

Given a Potts parameter q>4q > 4, the problem is whether the partition function series of rooted Fortuin-Kasteleyn (FK) planar maps converges at its inventory radius. Through the burger-order inventory encoding of planar maps, the probability that a random word reduces to an empty stack is compared with the return probability of a simple symmetric random walk killed upon stepping below zero.

Rooted Planar Maps and the Partition Function

For n≥0n \ge 0, a dart dd of a planar map with n+1n+1 edges is an element of the finite set Dn={0,…,2(n+1)−1}D_n = \{0, \dots, 2(n+1)-1\} indexing its directed edges.✦ Given a permutation ss on DnD_n, the orbit [d]s[d]_s of a dart d∈Dnd \in D_n under ss is its equivalence class under the cycle containing dd, and the orbit set Orb⁡(s)\operatorname{Orb}(s) is the set of all such orbits. Given permutations aa and ss on DnD_n and a subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a), the spanning subgraph G(a,s,A)G(a, s, A) is the simple graph on Orb⁡(s)\operatorname{Orb}(s) in which two distinct vertex orbits vv and ww are adjacent whenever some dart d∈Dnd \in D_n satisfies [d]a∈A[d]_a \in A and {[d]s,[a(d)]s}={v,w}\{[d]_s, [a(d)]_s\} = \{v, w\}.✦

A labelled planar map of index nn is a pair (α,σ)(\alpha, \sigma) of permutations on DnD_n satisfying the planar map conditions: α\alpha is a fixed-point-free involution (α2=id\alpha^2 = \mathrm{id} and α(d)≠d\alpha(d) \neq d for every d∈Dnd \in D_n), the spanning subgraph G(α,σ,Orb⁡(α))G(\alpha, \sigma, \operatorname{Orb}(\alpha)) on all edges is connected, and |Orb⁡(σ)|+|Orb⁡(σα)|=n+3|\operatorname{Orb}(\sigma)| + |\operatorname{Orb}(\sigma\alpha)| = n + 3, ensuring genus zero.✦ An isomorphism of rooted maps between labelled planar maps (α,σ)(\alpha, \sigma) and (α′,σ′)(\alpha', \sigma') of index nn is a permutation rr of DnD_n such that r(0)=0r(0) = 0, α′∘r=r∘α\alpha' \circ r = r \circ \alpha, and σ′∘r=r∘σ\sigma' \circ r = r \circ \sigma.✦ A rooted planar map MM of index nn is an equivalence class of labelled planar maps of index nn under the equivalence relation generated by root-preserving map isomorphisms.✦

For a rooted planar map MM of index nn with representative (αM,σM)(\alpha_M, \sigma_M), the involution αM\alpha_M is the dart reversal involution, the permutation σM\sigma_M is the vertex rotation permutation, and the edge set E(M)E(M) is the orbit set Orb⁡(αM)\operatorname{Orb}(\alpha_M), whose elements are the edges of MM. Given an involution aa on DnD_n and a subset A⊆Orb⁡(a)A \subseteq \operatorname{Orb}(a), the partial dart reversal ρa,A\rho_{a, A} is the permutation on DnD_n mapping each dart dd with [d]a∈A[d]_a \in A to a(d)a(d) and fixing every other dart.✦ For t∈ℝt \in \mathbb{R} and a rooted planar map MM of index nn, the loop polynomial LM(t)L_M(t) is defined by (1): LM(t)=∑A⊆E(M)t|Orb⁡(σM∘ραM,A)|−1.L_M(t) = \sum_{A \subseteq E(M)} t^{|\operatorname{Orb}(\sigma_M \circ \rho_{\alpha_M, A})| - 1}.(1)✦ For q∈ℝq \in \mathbb{R}, the rooted FK map coefficient an=an(q)a_n = a_n(q) is given by a0=1a_0 = 1 and, for n≥0n \ge 0, by (2), where the sum runs over all rooted planar maps MM of index nn: an+1=∑MLM(q).a_{n+1} = \sum_{M} L_M(\sqrt{q}).(2)✦

An FK model parameter pp is a real number in (1/2,1)(1/2, 1).✦ For q>4q > 4, the induced parameter pqp_q and the inventory radius uqu_q are the real numbers defined by (3): pq=qq+2,uq=1−pq16.p_q = \frac{\sqrt{q}}{\sqrt{q} + 2}, \qquad u_q = \frac{1 - p_q}{16}.(3)

The Inventory Model and Killed Random Walk

An inventory order is either a flexible order or a fixed order specifying one of two burger types.✦ The burger-order alphabet 𝒜\mathcal{A} consists of burger tokens of one of those two types and order tokens carrying an inventory order, and a letter ℓ∈𝒜\ell \in \mathcal{A} is an element of that alphabet. For a letter ℓ∈𝒜\ell \in \mathcal{A}, the letter increment Δ(ℓ)∈ℤ\Delta(\ell) \in \mathbb{Z} is +1+1 if ℓ\ell is a burger letter and −1-1 if ℓ\ell is an order letter.

An inventory stack evaluation state is a pair (O,B)(O, B) consisting of a list OO of pending orders and a list BB of burger types stored freshest-first.✦ Given a word ww of letters in 𝒜\mathcal{A} and an evaluation state ee, the word evaluation run⁡(w,e)\operatorname{run}(w, e) is the evaluation state obtained by processing ww recursively from left to right from state ee, and the word reduction is reduce⁡(w)=run⁡(w,(∅,∅))\operatorname{reduce}(w) = \operatorname{run}(w, (\emptyset, \emptyset)).✦ A word ww of letters in 𝒜\mathcal{A} is empty-reducing if reduce⁡(w)=(∅,∅)\operatorname{reduce}(w) = (\emptyset, \emptyset), leaving neither pending orders nor burgers.✦

For an FK model parameter p∈(1/2,1)p \in (1/2, 1), the letter mass function mpm_p on 𝒜\mathcal{A} is given by (4): mp(ℓ)={1/4if ℓ is a burger letter,p/2if ℓ is the flexible order,(1−p)/4if ℓ is a fixed order.m_p(\ell) = \begin{cases} 1/4 & \text{if } \ell \text{ is a burger letter}, \\ p/2 & \text{if } \ell \text{ is the flexible order}, \\ (1-p)/4 & \text{if } \ell \text{ is a fixed order}. \end{cases}(4)✦ The letter distribution νp\nu_p on 𝒜\mathcal{A} is the probability measure obtained by normalizing mpm_p, and the independent and identically distributed (i.i.d.) inventory stream measure ℙp\mathbb{P}_p is the product measure on 𝒜ℕ\mathcal{A}^{\mathbb{N}} with marginal distribution νp\nu_p. For a stream x∈𝒜ℕx \in \mathcal{A}^{\mathbb{N}} and N≥0N \ge 0, the initial word wN(x)w_N(x) is the prefix (x0,…,xN−1)(x_0, \dots, x_{N-1}) of length NN. The empty-reducing word probability rp(N)r_p(N) at length NN is given by (5): rp(N)=ℙp(reduce⁡(wN(x))=(∅,∅)).r_p(N) = \mathbb{P}_p\bigl(\operatorname{reduce}(w_N(x)) = (\emptyset, \emptyset)\bigr).(5)✦

For integers n,a,b≥0n, a, b \ge 0, the killed walk transition probability Kn(a,b)K_n(a, b) on {0,1,2,…}\{0, 1, 2, \dots\} is defined recursively by K0(a,b)=𝟏a=bK_0(a, b) = \mathbf{1}_{a = b} and, for n≥0n \ge 0, by (6): Kn+1(0,b)=12Kn(1,b),Kn+1(a+1,b)=Kn(a,b)+Kn(a+2,b)2.K_{n+1}(0, b) = \frac{1}{2} K_n(1, b), \qquad K_{n+1}(a+1, b) = \frac{K_n(a, b) + K_n(a+2, b)}{2}.(6)✦

The Claim

Theorem 1. Let w=(ℓ1,…,ℓN)w = (\ell_1, \dots, \ell_N) be a word of letters in 𝒜\mathcal{A}. If ww is empty-reducing, then its letter increments form a Dyck excursion (7): ∑i=1NΔ(ℓi)=0,∑i=1jΔ(ℓi)≥0(0≤j≤N).\sum_{i=1}^{N} \Delta(\ell_i) = 0, \qquad \sum_{i=1}^{j} \Delta(\ell_i) \ge 0 \quad (0 \le j \le N).(7)✦ For every n≥0n \ge 0, the empty-reducing probability obeys the killed-walk bound (8): rp(n)≤Kn(0,0).r_p(n) \le K_n(0, 0).(8)✦ The killed-walk transition probabilities satisfy (9), while the empty-reducing probabilities satisfy (10) and (11): ∑n=0∞Kn(a,b)<∞,\sum_{n=0}^{\infty} K_n(a, b) < \infty,(9)✦ ∑n=0∞rp(n)<∞,\sum_{n=0}^{\infty} r_p(n) < \infty,(10)✦ ∑n=0∞rp(2n)<∞.\sum_{n=0}^{\infty} r_p(2n) < \infty.(11)✦ For every Potts parameter q>4q > 4 with inventory radius u=uqu = u_q, the rooted FK map coefficients satisfy (12): ∑n=0∞anun<∞.\sum_{n=0}^{\infty} a_n u^n < \infty.(12)✦

In the paper, the result reads: for every n≥0n \ge 0, anun≤4−n(n+1)−1(2nn)=O((n+1)−3/2)a_n u^n \le 4^{-n}(n+1)^{-1}\binom{2n}{n} = O((n+1)^{-3/2}), where u=uqu = u_q.

What Is Checked

The claims are stated over words on the burger-order alphabet 𝒜\mathcal{A}, their increments and stack reductions, the i.i.d. inventory stream measure ℙp\mathbb{P}_p for p∈(1/2,1)p \in (1/2, 1), the killed simple symmetric random walk transitions Kn(a,b)K_n(a, b), and, for q>4q > 4, the rooted FK map coefficients ana_n at the inventory radius u=uqu = u_q. The partial dart reversal ρa,A\rho_{a, A} along any subset AA of edge orbits of a dart involution aa on DnD_n is an involution.✦