OctoInformBeta

OpenAI preprint, September 2026 · §6. Short global lists and changes of direction

Lemma 6.8: One-leaf rank tails support a uniform bound under carry, pruning, injection and direction switches

Run certificates bound global entry descriptions.

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

A global list in a scheduling computation retains sets of jobs as the current window changes. The relevant entry size is its Boolean formula leaf count. A rank threshold run certificate records descriptions of base sets separately from the rank cutoffs applied to them.

Let JJ be a job set, W⊆JW\subseteq J a window, and ρ:J→ℕ\rho:J\to\mathbb N a rank function. The rank upper tail RrR_r of a rank function ρ:J→ℕ\rho:J\to\mathbb N at a natural-number threshold rr is the subset of JJ defined in (1). Rr={x∈J:r≤ρ(x)}.R_r=\{x\in J:r\leq\rho(x)\}.(1)✦

Descriptions and Global Lists

An atomic assignment 𝒜=(Aα)α∈A\mathcal A=(A_\alpha)_{\alpha\in A} on a job set JJ is a family of subsets of JJ, indexed by an atom set AA, with AαA_\alpha assigned to each atom α∈A\alpha\in A. A Boolean structural formula φ\varphi over AA is an expression generated by (2), where negation is allowed only at a leaf. φ::=α∣¬α∣(φ∧φ)∣(φ∨φ).\varphi ::= \alpha\mid\neg\alpha\mid(\varphi\wedge\varphi) \mid(\varphi\vee\varphi).(2)✦ For Boolean structural formulas φ\varphi and ψ\psi over AA and an atomic assignment 𝒜\mathcal A on JJ, the interpretation val⁡𝒜(φ)\operatorname{val}_{\mathcal A}(\varphi) is a subset of JJ and the leaf count ℓ(φ)\ell(\varphi) is a natural number, both defined by (3). val⁡𝒜(α)=Aα,val⁡𝒜(¬α)=J\Aα,val⁡𝒜(φ∧ψ)=val⁡𝒜(φ)∩val⁡𝒜(ψ),val⁡𝒜(φ∨ψ)=val⁡𝒜(φ)∪val⁡𝒜(ψ),ℓ(α)=ℓ(¬α)=1,ℓ(φ∘ψ)=ℓ(φ)+ℓ(ψ)(∘∈{∧,∨}).\begin{aligned} \operatorname{val}_{\mathcal A}(\alpha)&=A_\alpha,\\ \operatorname{val}_{\mathcal A}(\neg\alpha)&=J\setminus A_\alpha,\\ \operatorname{val}_{\mathcal A}(\varphi\wedge\psi) &=\operatorname{val}_{\mathcal A}(\varphi) \cap\operatorname{val}_{\mathcal A}(\psi),\\ \operatorname{val}_{\mathcal A}(\varphi\vee\psi) &=\operatorname{val}_{\mathcal A}(\varphi) \cup\operatorname{val}_{\mathcal A}(\psi),\\ \ell(\alpha)&=\ell(\neg\alpha)=1,\\ \ell(\varphi\circ\psi)&=\ell(\varphi)+\ell(\psi) \quad(\circ\in\{\wedge,\vee\}). \end{aligned}(3) A description of a job set X⊆JX\subseteq J under an atomic assignment 𝒜\mathcal A is a Boolean structural formula whose interpretation is XX; the assertion that such a description has at most b∈ℕb\in\mathbb N leaves is written Desc⁡b(X)\operatorname{Desc}_b(X), as in (4). Desc⁡b(X)quad⇔∃φ(val⁡𝒜(φ)=Xandℓ(φ)≤b).\operatorname{Desc}_b(X)quad\Longleftrightarrow\quad \exists\varphi\;\bigl(\operatorname{val}_{\mathcal A}(\varphi)=X \ \text{and}\ \ell(\varphi)\leq b\bigr).(4)✦

An indexed global set family ℒ=(E,(Li)i∈ℕ)\mathcal L=(E,(L_i)_{i\in\mathbb N}) on JJ consists of a finite set E⊆ℕE\subseteq\mathbb N of listed indices and a job set Li⊆JL_i\subseteq J at every natural-number index.✦ The next global list index ν(ℒ)\nu(\mathcal L) of an indexed global set family ℒ=(E,(Li)i∈ℕ)\mathcal L=(E,(L_i)_{i\in\mathbb N}) is the natural number in (5), with max⁡⌀=0\max\varnothing=0 . ν(ℒ)=max⁡{1,max⁡E}+1.\nu(\mathcal L)=\max\{1,\max E\}+1.(5)✦ The appended family append⁡I(ℒ)\operatorname{append}_I(\mathcal L) of an indexed global set family ℒ\mathcal L and a job set I⊆JI\subseteq J is the indexed global set family obtained by adding II after the existing entries.✦ For job sets X,Y⊆JX,Y\subseteq J , the two-set global list pair⁡(X,Y)\operatorname{pair}(X,Y) is the indexed global set family with listed indices {0,1}\{0,1\} , entry XX at zero, and entry YY at every other index.✦

For natural-number cutoffs d,rd,r , the carry family carry⁡d,r(ℒ)\operatorname{carry}_{d,r}(\mathcal L) of an indexed global set family ℒ\mathcal L is the indexed global set family obtained by discarding indices before dd , intersecting the entry at dd with RrR_r , and retaining entries after dd .✦ For a subwindow W′⊆WW'\subseteq W , the pruned family prune⁡W′(ℒ)\operatorname{prune}_{W'}(\mathcal L) of an indexed global set family ℒ\mathcal L is the indexed global set family obtained by retaining precisely the listed indices ii for which Li∩W′≠⌀L_i\cap W'\ne\varnothing , leaving every global entry unchanged.✦

Run Certificates

A rank threshold run certificate 𝒞\mathcal C for ℒ\mathcal L, ρ\rho, 𝒜\mathcal A and WW is a family of base sets Ui⊆JU_i\subseteq J and thresholds ti∈ℕt_i\in\mathbb N, together with a distinguished second set S⊆JS\subseteq J, satisfying (6).✦ Write ℛ(ℒ,ρ,𝒜,W)\mathcal R(\mathcal L,\rho,\mathcal A,W) for the collection of these certificates. Li=Ui∩Rti(i∈E),Desc⁡2(Ui)(i∈E\{0}),Desc⁡24(U0),Desc⁡1(S),U1=S,W\S⊆U0,0∈E⇒[for every x∈W∩S,1∈Eandx∈L1].\begin{gathered} L_i=U_i\cap R_{t_i}\qquad(i\in E),\\ \operatorname{Desc}_2(U_i)\qquad(i\in E\setminus\{0\}),\\ \operatorname{Desc}_{24}(U_0),\qquad \operatorname{Desc}_1(S),\qquad U_1=S,\\ W\setminus S\subseteq U_0,\\ 0\in E\ \Longrightarrow\ \bigl[\text{for every }x\in W\cap S,\quad 1\in E\ \text{and}\ x\in L_1\bigr]. \end{gathered}(6)

The Claim

Theorem 1. Let 𝒞∈ℛ(ℒ,ρ,𝒜,W)\mathcal C\in\mathcal R(\mathcal L,\rho,\mathcal A,W). If every rank upper tail has a description with at most one leaf, every listed entry satisfies (7). Desc⁡25(Li)(i∈E).\operatorname{Desc}_{25}(L_i)\qquad(i\in E).(7)✦ For natural-number cutoffs d,rd,r , carrying 𝒞\mathcal C gives a certificate 𝒞d,rcarry\mathcal C^{\mathrm{carry}}_{d,r} satisfying (8). 𝒞d,rcarry∈ℛ(carry⁡d,r(ℒ),ρ,𝒜,W).\mathcal C^{\mathrm{carry}}_{d,r}\in \mathcal R\bigl(\operatorname{carry}_{d,r}(\mathcal L),\rho,\mathcal A,W\bigr).(8)✦ For a subwindow W′⊆WW'\subseteq W , pruning 𝒞\mathcal C gives a certificate 𝒞W′prune\mathcal C^{\mathrm{prune}}_{W'} satisfying (9). 𝒞W′prune∈ℛ(prune⁡W′(ℒ),ρ,𝒜,W′).\mathcal C^{\mathrm{prune}}_{W'}\in \mathcal R\bigl(\operatorname{prune}_{W'}(\mathcal L),\rho,\mathcal A,W'\bigr).(9)✦ Injection with a job set II satisfying Desc⁡2(I)\operatorname{Desc}_2(I) extends 𝒞\mathcal C to a certificate 𝒞Iappend\mathcal C^{\mathrm{append}}_I satisfying (10). 𝒞Iappend∈ℛ(append⁡I(ℒ),ρ,𝒜,W).\mathcal C^{\mathrm{append}}_I\in \mathcal R\bigl(\operatorname{append}_I(\mathcal L),\rho,\mathcal A,W\bigr).(10)✦ Let G,S⊆JG,S\subseteq J satisfy Desc⁡24(G)\operatorname{Desc}_{24}(G), Desc⁡1(S)\operatorname{Desc}_1(S) and W\S⊆GW\setminus S\subseteq G. For a natural-number threshold rr , the direction switch gives a certificate 𝒞G,S,rswitch\mathcal C^{\mathrm{switch}}_{G,S,r} satisfying (11). 𝒞G,S,rswitch∈ℛ(pair⁡(G∩Rr,S),ρ,𝒜,W).\mathcal C^{\mathrm{switch}}_{G,S,r}\in \mathcal R\bigl(\operatorname{pair}(G\cap R_r,S),\rho,\mathcal A,W\bigr).(11)✦

In the paper, the result reads: every constructed entry has fewer than 4040 leaves, and this remains true through any number of same-direction updates.

What Is Checked

The statements concern run certificates for finite indexed global families on an arbitrary job set, with an arbitrary rank function and atomic assignment; the entry bound assumes one-leaf descriptions of all rank upper tails.