OctoInformBeta

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

Lemma 3.5 [Bottom supply and terminal demand]: Equal-length stacks and order lists evaluate to empty when bottom burger counts dominate terminal fixed-order counts per type and suffix length

Complete inventory matching under the supply condition.

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

Consider a deterministic inventory system with two burger types, two fixed orders (one for each type), and one flexible order. Burgers sit on a stack ordered freshest-first, and each order consumes the freshest eligible burger. Given an initial burger stack and an equal-length sequence of orders, when does evaluating the orders clear both the burger stack and the list of pending orders?

Inventory Definitions

The set ℬ\mathcal{B} of burger types is a two-element set. The set 𝒪\mathcal{O} of inventory orders consists of fixed orders fix(a)\mathrm{fix}(a) for a∈ℬa \in \mathcal{B}, eligible for burgers of type aa, and the flexible order 𝖿𝗅𝖾𝗑\mathsf{flex}, eligible for burgers of either type.✦ The burger-order alphabet 𝒜\mathcal{A} is the finite set consisting of burger tokens 𝖻(b)\mathsf{b}(b) for b∈ℬb \in \mathcal{B} and order tokens 𝗈(x)\mathsf{o}(x) for x∈𝒪x \in \mathcal{O}.✦

The set 𝒮\mathcal{S} of burger stacks is the set of finite lists over ℬ\mathcal{B} stored freshest-first. The set ℰ\mathcal{E} of inventory stack evaluation states is the set of pairs ξ=(r,s)\xi = (r, s) consisting of a finite list rr of pending orders in 𝒪\mathcal{O} and a burger stack s∈𝒮s \in \mathcal{S}.✦

For an order a∈𝒪a \in \mathcal{O} and a burger stack s∈𝒮s \in \mathcal{S}, the pop operation P(a,s)P(a, s) is the element of 𝒮∪{⊥}\mathcal{S} \cup \{\bot\} that removes the freshest eligible burger from ss, returning the failure value ⊥\bot when none is present, defined by (1): P(a,[])=⊥,P(a,b::s′)={s′if b is eligible for a,b::P(a,s′)otherwise,P(a, []) = \bot, \qquad P(a, b :: s') = \begin{cases} s' & \text{if } b \text{ is eligible for } a, \\ b :: P(a, s') & \text{otherwise}, \end{cases}(1)✦ with b::⊥=⊥b :: \bot = \bot for b∈ℬb \in \mathcal{B}.

Given a single-step transition τ(ξ,ℓ)∈ℰ\tau(\xi, \ell) \in \mathcal{E} for ξ∈ℰ\xi \in \mathcal{E} and ℓ∈𝒜\ell \in \mathcal{A}, the evaluation E(w,ξ)∈ℰE(w, \xi) \in \mathcal{E} of a word ww over 𝒜\mathcal{A} from state ξ\xi is defined recursively by (2): E([],ξ)=ξ,E(ℓ::w′,ξ)=E(w′,τ(ξ,ℓ)).E([], \xi) = \xi, \qquad E(\ell :: w', \xi) = E(w', \tau(\xi, \ell)).(2)✦

The order evaluation on supply Eord(ω,s)E_{\mathrm{ord}}(\omega, s) of a finite order list ω\omega over 𝒪\mathcal{O} against a burger stack s∈𝒮s \in \mathcal{S} is the evaluation state in ℰ\mathcal{E} defined by (3), where ωord=(𝗈(x))x∈ω\omega^{\mathrm{ord}} = (\mathsf{o}(x))_{x \in \omega} is the word of order tokens: Eord(ω,s)=E(ωord,([],s)).E_{\mathrm{ord}}(\omega, s) = E(\omega^{\mathrm{ord}}, ([], s)).(3)✦

For a finite list u=(u1,…,um)u = (u_1, \dots, u_m) of length |u|=m|u| = m and an integer k≥0k \ge 0, the bottom suffix u↓ku_{\downarrow k} of uu is the terminal suffix of length min⁡(k,m)\min(k, m) given by (4): u↓k=(umax⁡(m−k,0)+1,…,um).u_{\downarrow k} = (u_{\max(m - k, 0) + 1}, \dots, u_m).(4)✦

A stack s∈𝒮s \in \mathcal{S} and an order list ω\omega over 𝒪\mathcal{O} satisfy the supply condition when (5) holds, where Nx(u)N_x(u) denotes the number of occurrences of an entry xx in a finite list uu: |s|=|ω|andNfix(a)(ω↓k)≤Na(s↓k)for all 0≤k≤|ω|,a∈ℬ.|s| = |\omega| \quad \text{and} \quad N_{\mathrm{fix}(a)}(\omega_{\downarrow k}) \le N_a(s_{\downarrow k}) \quad \text{for all } 0 \le k \le |\omega|,\; a \in \mathcal{B}.(5)✦

The Claim

Whenever a burger stack s∈𝒮s \in \mathcal{S} and a type b∈ℬb \in \mathcal{B} satisfy Nb(s)>0N_b(s) > 0, there exists a stack t∈𝒮t \in \mathcal{S} fulfilling (6): P(fix(b),s)=t.P(\mathrm{fix}(b), s) = t.(6)✦

If a stack s∈𝒮s \in \mathcal{S} and a nonempty order list a::ωa :: \omega with a∈𝒪a \in \mathcal{O} satisfy (5), then there exists a stack t∈𝒮t \in \mathcal{S} satisfying (7): P(a,s)=tand(t,ω) satisfies the supply condition.P(a, s) = t \quad \text{and} \quad (t, \omega) \text{ satisfies the supply condition}.(7)✦

Theorem 1. Suppose a burger stack s∈𝒮s \in \mathcal{S} and an order list ω\omega over 𝒪\mathcal{O} satisfy the supply condition (5). Then the order evaluation on supply satisfies (8): Eord(ω,s)=([],[]).E_{\mathrm{ord}}(\omega, s) = ([], []).(8)✦

In the paper, the result reads: if a burger stack ss and an order word ω\omega both have length hh and, for every 1≤k≤h1 \le k \le h and each burger type aa, the number of fixed type-aa orders among the terminal kk orders of ω\omega is at most the number of type-aa burgers among the original bottom kk burgers of ss, then the greedy inventory rule matches all orders and leaves no burgers.

What Is Checked

The matching theorem (8), together with (6) and (7), is stated over inventory orders in 𝒪\mathcal{O}, burger-order alphabet letters in 𝒜\mathcal{A}, evaluation states in ℰ\mathcal{E} with freshest-first burger stacks in 𝒮\mathcal{S}, word evaluation, order evaluation on supply, the pop operation, and the supply condition (5) built from bottom suffixes.