OctoInformBeta

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

Lemma 6.5: Paired entries reduce to a distinguished set union a rank suffix

Certified flattening preserves a window union.

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 scheduling recursion maintains a finite list of job sets inside a current window. Flattening changes the distinguished entry of this list to a union with a rank suffix. The quantity of interest is the set of jobs covered inside the window.

Let JJ be a set of jobs, let W⊆JW\subseteq J be a window, and let ρ:J→ℕ\rho:J\to\mathbb N be a rank. The rank upper tail HkH_k at threshold k∈ℕk\in\mathbb N is the job set in (1). Hk={x∈J:ρ(x)≥k}.H_k=\{x\in J:\rho(x)\geq k\}.(1)✦ A global list ℒ=(I,(Ei)i∈ℕ)\mathcal L=(I,(E_i)_{i\in\mathbb N}) on JJ is a family of job sets Ei⊆JE_i\subseteq J with a finite set I⊆ℕI\subseteq\mathbb N of listed indices.✦ The global entry union Q(ℒ)Q(\mathcal L) of a global list ℒ\mathcal L on JJ is the job set defined in (2). Q(ℒ)=⋃i∈IEi.Q(\mathcal L)=\bigcup_{i\in I}E_i.(2)✦

Descriptions and Run Certificates

An atomic family 𝒜=(Aa)a∈A\mathcal A=(A_a)_{a\in A} is an assignment of a job set Aa⊆JA_a\subseteq J to each index aa in a set AA. A Boolean structural formula pp over AA is a positive or negative leaf at an index aa, or a conjunction or disjunction of two such formulas.✦ The interpretation ⟦p⟧𝒜\llbracket p\rrbracket_{\mathcal A} of a Boolean structural formula pp over AA in the atomic family 𝒜\mathcal A is the job set obtained by assigning AaA_a to a positive leaf and J\AaJ\setminus A_a to a negative leaf, and assigning intersection to conjunction and union to disjunction.✦ The leaf count ℓ(p)\ell(p) of a Boolean structural formula pp over AA is the natural number equal to one for a leaf and to the sum of the two constituent counts for either operation.✦

A bounded description pp of a job set F⊆JF\subseteq J with allowance b∈ℕb\in\mathbb N is a formula satisfying (3); write Desc⁡b(F)\operatorname{Desc}_b(F) for the existence of such a formula. ⟦p⟧𝒜=F,ℓ(p)≤b.\llbracket p\rrbracket_{\mathcal A}=F, \qquad \ell(p)\leq b.(3)✦

A rank threshold run certificate ℛ\mathcal R for (ℒ,ρ,𝒜,W)(\mathcal L,\rho,\mathcal A,W) consists of base sets Ci⊆JC_i\subseteq J, thresholds ki∈ℕk_i\in\mathbb N, and a distinguished second set S⊆JS\subseteq J satisfying (4), together with the following coverage and pairing conditions. Every job in W\SW\setminus S belongs to C0C_0. Whenever zero is listed, each job in W∩SW\cap S belongs to E1E_1 and requires that one is listed. Ei=Ci∩Hki(i∈I),C1=S,Desc⁡2(Ci)(i∈I\{0}),Desc⁡24(C0),Desc⁡1(S).\begin{gathered} E_i=C_i\cap H_{k_i}\quad(i\in I), \qquad C_1=S,\\ \operatorname{Desc}_2(C_i)\quad(i\in I\setminus\{0\}), \qquad \operatorname{Desc}_{24}(C_0), \qquad \operatorname{Desc}_1(S). \end{gathered}(4)✦ The flattened entry Ẽi\widetilde E_i of ℛ\mathcal R is the job set defined in (5). Ẽi={S∪Hk0,i=0,Ei,i≠0.\widetilde E_i= \begin{cases} S\cup H_{k_0},&i=0,\\ E_i,&i\ne0. \end{cases}(5)✦

The Claim

Theorem 1. Let Q0,U,D,G,B⊆JQ_0,U,D,G,B\subseteq J and k∈ℕk\in\mathbb N. Suppose that U⊆Q0U\subseteq Q_0, Q0\D⊆GQ_0\setminus D\subseteq G, and U∩B=U∩DU\cap B=U\cap D. Then U∩((G∩Hk)∪B)=U∩(D∪Hk).U\cap\bigl((G\cap H_k)\cup B\bigr) =U\cap(D\cup H_k).(6)✦ For any rank threshold run certificate ℛ\mathcal R for (ℒ,ρ,𝒜,W)(\mathcal L,\rho,\mathcal A,W), its flattened entries satisfy W∩⋃i∈IẼi=W∩Q(ℒ).W\cap\bigcup_{i\in I}\widetilde E_i =W\cap Q(\mathcal L).(7)✦

In the paper, the result reads: if a run begins at an initial threshold hh by switching out of Q0Q_0 with entries G∩HhG\cap H_h and DD, where Q0\D⊆GQ_0\setminus D\subseteq G, and U⊆Q0U\subseteq Q_0 is a later parent at which the entry descended from the first switch entry survives an unpruned carry with current threshold kk, then the carried portion of the pair agrees on UU with D∪HkD\cup H_k.

What Is Checked

The pair identity (6) is stated over arbitrary job sets with a natural-number rank, and the union identity (7) is stated over finite global lists equipped with the base descriptions, coverage, and pairing conditions of a rank threshold run certificate.