OctoInformBeta

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

Lemma 6.3: Unchanged and switched priorities, pruning, and the structural certificate of a child window

List updates select and order high jobs.

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 recursive scheduling step must identify the high jobs in its child window, meaning the jobs whose priority is at least the chosen threshold, and retain their priority order. The step may keep the direction of the current list or switch direction before restricting the list to the child.

Let JJ be a finite job set of size N=3TN=3T, with precedence relation ≺\prec and natural-number rank ρ\rho. A layout pp is a bijection from JJ to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ For boundary slots aa and bb, the slot assignment of pp and its open window W=(a,b)W=(a,b) are given by (1). A full layout is a layout on N=3TN=3T jobs that respects precedence, meaning x≺yx\prec y requires τ(x)<τ(y)\tau(x)<\tau(y).✦ τ(x)=⌊p(x)3⌋+1,W={x∈J:a<τ(x)<b}.\tau(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad W=\{x\in J:a<\tau(x)<b\}.(1)

A boundary AA of a full layout on JJ is a left endpoint, a right endpoint, or a triple Z⊆JZ\subseteq J of cardinality three.✦ Its time is respectively 00, T+1T+1, or a slot ss between 11 and TT whose jobs are exactly ZZ.✦ For an actual boundary A=ZA=Z, the predecessor and successor cones and their weak versions are defined by (2). At the left endpoint, the predecessor cones are empty and the successor cones are JJ; at the right endpoint these conventions are reversed. PA={x:∃z∈Z,x≺z},DA={x:∃z∈Z,z≺x},P¯A=PA∪Z,D¯A=DA∪Z.\begin{aligned} P_A&=\{x:\exists z\in Z,\ x\prec z\}, &D_A&=\{x:\exists z\in Z,\ z\prec x\},\\ \overline P_A&=P_A\cup Z, &\overline D_A&=D_A\cup Z. \end{aligned}(2)

A boundary AA at slot ss separates a window UU by a cutoff C⊆JC\subseteq J when the conditions in (3) hold. {x∈U:τ(x)<s}\C⊆PA,{x∈U:s<τ(x)}∩C⊆DA.\{x\in U:\tau(x)<s\}\setminus C\subseteq P_A, \qquad \{x\in U:s<\tau(x)\}\cap C\subseteq D_A.(3)✦

Lists and Structural Certificates

An atomic family 𝒜\mathcal A on JJ is an assignment of subsets of JJ to atoms. A Boolean structural formula φ\varphi over an atomic family 𝒜\mathcal A on JJ is a signed atom or a conjunction or disjunction of formulas; its interpretation uses complement in JJ, intersection, and union. The leaf count ℓ(φ)\ell(\varphi) of a Boolean structural formula φ\varphi is one for a signed atom and adds across either binary operation.✦ A description with allowance kk of a subset X⊆JX\subseteq J is a Boolean structural formula with at most kk leaves whose interpretation is XX.✦ Atomic predicate expressiveness means that JJ, the empty set, every rank upper tail, every boundary cone in (2), and every job triple each have a description with one leaf.✦ The rank upper tail is the set Rρ(k)={x∈J:k≤ρ(x)}R_\rho(k)=\{x\in J:k\leq\rho(x)\}.✦

An indexed global set family ℒ=(I,(Li)i∈ℕ)\mathcal L=(I,(L_i)_{i\in\mathbb N}) consists of a finite set II of natural-number indices and subsets Li⊆JL_i\subseteq J.✦ Its membership indices, last membership index, global entry union, and numeric priority key at scale MM are given by (4), with maximum zero for an empty membership set. Iℒ(x)={i∈I:x∈Li},mℒ(x)=max⁡(Iℒ(x)∪{0}),Q(ℒ)=⋃i∈ILi,kℒ(x)=Mmℒ(x)+ρ(x).\begin{aligned} I_{\mathcal L}(x)&=\{i\in I:x\in L_i\}, &m_{\mathcal L}(x)&=\max\bigl(I_{\mathcal L}(x)\cup\{0\}\bigr),\\ Q(\mathcal L)&=\bigcup_{i\in I}L_i, &k_{\mathcal L}(x)&=M m_{\mathcal L}(x)+\rho(x). \end{aligned}(4) The lexicographic list priority on JJ is the relation in which x<ℒ,ρyx<_{\mathcal L,\rho}y means that (mℒ(x),ρ(x))(m_{\mathcal L}(x),\rho(x)) precedes (mℒ(y),ρ(y))(m_{\mathcal L}(y),\rho(y)) lexicographically.✦ The injection entries are disjoint in UU if distinct listed entries with indices at least two have disjoint intersections with UU.✦ A global upset GG of the job set JJ is a subset of JJ containing every successor of each of its jobs✦; a list has upward-closed entries if every listed entry is a global upset.✦

For an indexed global set family ℒ\mathcal L, rank ρ\rho, index dd, and rank threshold rr, the suffix carry⁡(ℒ,ρ,d,r)\operatorname{carry}(\mathcal L,\rho,d,r) is the indexed global set family obtained by discarding listed entries before dd, restricting the entry at dd to Rρ(r)R_\rho(r), and retaining later entries.✦ Appending a set places it at a new final index.✦ For subsets A,DA,D of JJ, the two-set list pair⁡(A,D)\operatorname{pair}(A,D) is the indexed global set family with indices 0,10,1 and entries A,DA,D.✦ Pruning prune⁡Uℒ\operatorname{prune}_U\mathcal L retains exactly the indices whose entries meet UU, leaving their global entries unchanged.✦

For subsets P,D,GP,D,G of JJ, a scale MM, and a threshold tt, let ℒs\mathcal L_{\mathrm s} and ℒ×\mathcal L_\times be the unchanged-direction and switched lists in (5). Write πs\pi_{\mathrm s} for the unchanged-direction priority specified by ℒ,ρ,M,P\mathcal L,\rho,M,P, and π×\pi_\times for the direction-change priority specified by ρ,M,D\rho,M,D. The priority cut of a natural-number priority π\pi on JJ at θ\theta is the job set Cπ(θ)={x:π(x)<θ}C_\pi(\theta)=\{x:\pi(x)<\theta\}.✦ ℒs=append⁡(carry⁡(ℒ,ρ,tdivM,tmodM),D\P),ℒ×=pair⁡(G∩Rρ(t),D).\begin{aligned} \mathcal L_{\mathrm s} &=\operatorname{append}\bigl( \operatorname{carry}(\mathcal L,\rho,t\mathbin{\mathrm{div}}M, t\mathbin{\mathrm{mod}}M),D\setminus P\bigr),\\ \mathcal L_\times &=\operatorname{pair}\bigl(G\cap R_\rho(t),D\bigr). \end{aligned}(5)

A rank-threshold run for ℒ,ρ,𝒜\mathcal L,\rho,\mathcal A on UU consists of bases Ui⊆JU_i\subseteq J, thresholds hih_i, and a distinguished second set E⊆JE\subseteq J. Every listed entry is Li=Ui∩Rρ(hi)L_i=U_i\cap R_\rho(h_i). The base U0U_0 has allowance 2424; each listed nonzero base has allowance 22; EE has allowance 11 and U1=EU_1=E. Coverage requires U\E⊆U0U\setminus E\subseteq U_0. If zero is listed, every job of U∩EU\cap E requires index one to be listed and belongs to L1L_1.

The exchange of jobs x,y∈Jx,y\in J in a layout qq is the layout in which xx and yy trade positions and every other job keeps its position.✦

The past boundary invariant at A,aA,a requires every job in Q(ℒ)Q(\mathcal L) scheduled at or before aa to belong to P¯A\overline P_A.✦ The forbidden exchange invariant on UU at A,aA,a concerns every precedence-respecting layout qq that agrees with pp outside UU. If x∈U\DAx\in U\setminus D_A, qq places y∈Q(ℒ)y\in Q(\mathcal L) at slot aa, and x<ℒ,ρyx<_{\mathcal L,\rho}y, exchanging the positions of xx and yy in qq must violate precedence.✦

A reverse induction seed at B,bB,b for UU is a downward closed set H⊆JH\subseteq J with allowance 2424 that contains U\PBU\setminus P_B and whose jobs all have time strictly less than bb.✦ A node structural certificate for ≺,ρ,𝒜,p,U\prec,\rho,\mathcal A,p,U consists of a full layout, left and right boundaries A,BA,B at a,ba,b identifying U=(a,b)U=(a,b), and a list with a rank-threshold run on UU. Its entries and second set are upward-closed, its injection entries are disjoint in UU, and it has at most five indices. Its confinement conditions are (6); it satisfies the past and forbidden exchange invariants at the left boundary, UU has allowance 406406, and it has a reverse induction seed at the right boundary. Write 𝒩≺,ρ,𝒜(p,U)\mathscr N_{\prec,\rho,\mathcal A}(p,U) for the collection of these certificates. U∩Q(ℒ)⊆PB,U\Q(ℒ)⊆DA.U\cap Q(\mathcal L)\subseteq P_B, \qquad U\setminus Q(\mathcal L)\subseteq D_A.(6)

An edge structural certificate ℰ\mathcal E for the full layout pp and parent W=(a,b)W=(a,b) consists of boundaries B,V,A′,B′B,V,A',B' at b,v,a′,b′b,v,a',b', with B′B' actual and a≤a′<b′≤v<ba\leq a'<b'\leq v<b, together with cutoffs S,F⊆JS,F\subseteq J. The final cutoff FF has allowance 11; VV separates WW by FF, and A′,B′A',B' separate (a,v)(a,v) by SS. The cutoff satisfies W∩S⊆PB∩FW\cap S\subseteq P_B\cap F. Its list has a rank-threshold run on WW, upward-closed entries and second set, disjoint injection entries in WW, and labels W∩Q(ℒ)=W\SW\cap Q(\mathcal L)=W\setminus S. It satisfies the past invariant at A′,a′A',a' and the forbidden exchange invariant on the child W′=(a′,b′)W'=(a',b') at that boundary. A global cutoff of allowance 205205 and a downward-closed extension of allowance 2121 each agree with SS inside WW.

The Claim

Theorem 1. Let ℒ\mathcal L be an indexed global set family, let ρ:J→ℕ\rho:J\to\mathbb N, and let the updated lists and side priorities be those of (5).

For unchanged-direction qualification, suppose M>0M>0, every rank is less than MM, W∩Q(ℒ)⊆PW\cap Q(\mathcal L)\subseteq P, W⊆D∪PW\subseteq D\cup P, and t≤(max⁡(I∪{0})+1)Mt\leq(\max(I\cup\{0\})+1)M. The qualification identity is (7). W∩Q(ℒs)=W\Cπs(M+t).W\cap Q(\mathcal L_{\mathrm s}) =W\setminus C_{\pi_{\mathrm s}}(M+t).(7)✦

Suppose every rank is less than MM and W∩Q(ℒ)⊆PW\cap Q(\mathcal L)\subseteq P in the unchanged-direction case. For x,y∈W∩Q(ℒs)x,y\in W\cap Q(\mathcal L_{\mathrm s}), the order agreement is (8). x<ℒs,ρy⇔πs(x)<πs(y).x<_{\mathcal L_{\mathrm s},\rho}y \quad\Longleftrightarrow\quad \pi_{\mathrm s}(x)<\pi_{\mathrm s}(y).(8)✦

For switched qualification, suppose t≤Mt\leq M and W\D⊆GW\setminus D\subseteq G. The qualification identity is (9). W∩Q(ℒ×)=W\Cπ×(t).W\cap Q(\mathcal L_\times)=W\setminus C_{\pi_\times}(t).(9)✦

Assume every rank is less than MM in the switched-direction case. For all jobs x,y∈Jx,y\in J, the order agreement is (10). x<ℒ×,ρy⇔π×(x)<π×(y).x<_{\mathcal L_\times,\rho}y \quad\Longleftrightarrow\quad \pi_\times(x)<\pi_\times(y).(10)✦

For every indexed global set family 𝒦\mathcal K and job set UU, pruning satisfies (11). U∩Q(prune⁡U𝒦)=U∩Q(𝒦).U\cap Q(\operatorname{prune}_U\mathcal K)=U\cap Q(\mathcal K).(11)✦

Let ℰ\mathcal E be an edge structural certificate with child W′=(a′,b′)W'=(a',b'). Suppose precedence is transitive and 𝒜\mathcal A has atomic predicate expressiveness for ≺,ρ\prec,\rho. The child construction, denoted 𝒩\mathcal N, yields the certificate in (12). 𝒩(ℰ)∈𝒩≺,ρ,𝒜(p,W′).\mathcal N(\mathcal E)\in \mathscr N_{\prec,\rho,\mathcal A}(p,W').(12)✦

In the paper, the result reads: for either update, with SS its side priority cut and, in the switched case, an upset GG containing W\DAW\setminus D_A and containing no job at or before aa, the qualifier union on WW before pruning is exactly W\SW\setminus S and its key order on these high jobs agrees with the side priority; after pruning it selects exactly W′\SW'\setminus S and satisfies the child’s first invariant.

What Is Checked

The list claims concern indexed global set families and natural-number priorities; the child construction concerns edge structural certificates under transitive precedence and atomic predicate expressiveness. For U′⊆UU'\subseteq U, pruning a rank-threshold run on UU gives a rank-threshold run on U′U' with the same ranks and atomic family.✦