OctoInformBeta

OpenAI preprint, September 2026 · §3. Ladder cuts and a coefficient lower bound · §3

Definition 3.3 [L-cut and R-cut]: One-sided prefix and two-sided boundary conditions on pending orders and surviving burgers under word reduction

Left and right cuts for sequences 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

In the inventory encoding of random planar maps, finite words of burgers and orders are reduced sequentially as each order consumes the freshest eligible burger. Given a one-sided or bi-infinite sequence of such word pieces, which sequences or boundary locations ensure that no finite stretch leaves pending orders on the right or surviving burgers on the left?

Inventory Words and Reduction

Let 𝔹\mathbb{B} be the two-element set of burger types. The inventory order set 𝒪\mathcal{O} consists of two fixed orders, one for each burger type in 𝔹\mathbb{B}, and one flexible order.✦ The burger-order alphabet 𝒜\mathcal{A} is the disjoint union 𝔹⊔𝒪\mathbb{B} \sqcup \mathcal{O} of the set of burger types 𝔹\mathbb{B} and the inventory order set 𝒪\mathcal{O}.✦ For any set SS, write S*S^* for the set of finite words over SS with empty word ε\varepsilon and concatenation written by juxtaposition, and let wrevw^{\mathrm{rev}} denote the reversal of w∈S*w \in S^*.

An inventory stack evaluation state e=(ord(e),burg(e))∈ℰ=𝒪*×𝔹*e = (\mathrm{ord}(e), \mathrm{burg}(e)) \in \mathcal{E} = \mathcal{O}^* \times \mathbb{B}^* consists of a word ord(e)\mathrm{ord}(e) of pending orders and a word burg(e)\mathrm{burg}(e) of burger types stored freshest-first.✦ Given the single-step transition τ:ℰ×𝒜→ℰ\tau \colon \mathcal{E} \times \mathcal{A} \to \mathcal{E}, in which an incoming burger is added to the burger stack and an order consumes the freshest eligible burger or joins the pending orders, the evaluation ev(w,e)∈ℰ\mathrm{ev}(w, e) \in \mathcal{E} of a word w∈𝒜*w \in \mathcal{A}^* on a state e∈ℰe \in \mathcal{E} is defined recursively on ww by ev(ε,e)=e,ev(ℓu,e)=ev(u,τ(e,ℓ))\mathrm{ev}(\varepsilon, e) = e, \qquad \mathrm{ev}(\ell u, e) = \mathrm{ev}\bigl(u, \tau(e, \ell)\bigr)(1)✦ for all ℓ∈𝒜\ell \in \mathcal{A} and u∈𝒜*u \in \mathcal{A}^*. The word reduction red(w)∈ℰ\mathrm{red}(w) \in \mathcal{E} of a word w∈𝒜*w \in \mathcal{A}^* is the evaluation state obtained via word evaluation (1) from empty pending orders and an empty burger stack, red(w)=ev(w,(ε,ε)).\mathrm{red}(w) = \mathrm{ev}(w, (\varepsilon, \varepsilon)).(2)✦

For a sequence x:ℕ→𝒜*x \colon \mathbb{N} \to \mathcal{A}^* of inventory words, the concatenated piece prefix Pn(x)∈𝒜*P_n(x) \in \mathcal{A}^* of xx over its first n∈ℕn \in \mathbb{N} pieces is the word defined recursively by P0(x)=ε,Pn+1(x)=Pn(x)x(n)(n∈ℕ).P_0(x) = \varepsilon, \qquad P_{n+1}(x) = P_n(x)\, x(n) \qquad (n \in \mathbb{N}).(3)✦ Given a bi-infinite sequence x:ℤ→𝒜*x \colon \mathbb{Z} \to \mathcal{A}^* of inventory words indexed by the integers ℤ\mathbb{Z}, an integer a∈ℤa \in \mathbb{Z}, and n∈ℕn \in \mathbb{N}, the concatenated interval word Wa,n(x)∈𝒜*W_{a,n}(x) \in \mathcal{A}^* starting at aa and spanning nn pieces is the word obtained from the concatenated piece prefix (3) of a shifted sequence by Wa,n(x)=Pn((x(a+j))j∈ℕ).W_{a,n}(x) = P_n\bigl((x(a+j))_{j \in \mathbb{N}}\bigr).(4)✦

The Definition

Definition 1. A one-sided sequence x:ℕ→𝒜*x \colon \mathbb{N} \to \mathcal{A}^* of inventory words has a left cut if its concatenated piece prefixes (3) under word reduction (2) satisfy ord(red(Pn(x)))=εfor every n∈ℕ.\mathrm{ord}\bigl(\mathrm{red}(P_n(x))\bigr) = \varepsilon \qquad \text{for every } n \in \mathbb{N}.(5)✦ For a sequence x:ℕ→𝒜*x \colon \mathbb{N} \to \mathcal{A}^* of inventory words, xx has a right cut when the reversals of its concatenated piece prefixes satisfy burg(red(Pn(x)rev))=εfor every n∈ℕ.\mathrm{burg}\bigl(\mathrm{red}(P_n(x)^{\mathrm{rev}})\bigr) = \varepsilon \qquad \text{for every } n \in \mathbb{N}.(6)✦ Given a bi-infinite sequence x:ℤ→𝒜*x \colon \mathbb{Z} \to \mathcal{A}^* of inventory words and an integer a∈ℤa \in \mathbb{Z}, the sequence xx has a left cut at aa if its concatenated interval words (4) satisfy ord(red(Wa,n(x)))=εfor every n∈ℕ.\mathrm{ord}\bigl(\mathrm{red}(W_{a,n}(x))\bigr) = \varepsilon \qquad \text{for every } n \in \mathbb{N}.(7)✦ For a bi-infinite sequence x:ℤ→𝒜*x \colon \mathbb{Z} \to \mathcal{A}^* of inventory words and an integer b∈ℤb \in \mathbb{Z}, the sequence xx has a right cut at bb when its concatenated interval words starting at b−nb - n and spanning nn pieces satisfy burg(red(Wb−n,n(x)))=εfor every n∈ℕ.\mathrm{burg}\bigl(\mathrm{red}(W_{b-n,n}(x))\bigr) = \varepsilon \qquad \text{for every } n \in \mathbb{N}.(8)✦

What Is Checked

The one-sided cut definitions (5) and (6) are stated over sequences x:ℕ→𝒜*x \colon \mathbb{N} \to \mathcal{A}^* via word reduction (2) of concatenated piece prefixes (3) and their reversals, and the two-sided definitions (7) and (8) are stated over bi-infinite sequences x:ℤ→𝒜*x \colon \mathbb{Z} \to \mathcal{A}^* and integers a,b∈ℤa, b \in \mathbb{Z} via word reduction of concatenated interval words (4).