OctoInformBeta

OpenAI preprint, September 2026 · §5. The interval construction and its invariants

§5 (setting): global lists, keys, and the three invariants: Membership keys and boundary conditions define structural certificates for the interval construction

Global priorities constrain interval exchanges.

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

The interval construction records which jobs may occur near either boundary of a scheduling window and which exchanges remain forbidden after its interior is reordered. For an instance with nn original jobs and valid deadline TT, let JJ be the padded job set, with N=3TN=3T jobs, and let rr be the precedence relation. A job layout pp is a bijection from JJ to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ The slot assignment τp\tau_p of a job layout pp is the function in (1); a full layout for precedence rr is a job layout satisfying the two conditions there, the second of which is precedence feasibility. τp(x)=⌊p(x)3⌋+1,Full⁡(p,r)⇔3∣N and τp(x)<τp(y) whenever r(x,y).\tau_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad \operatorname{Full}(p,r)\ \Longleftrightarrow\ 3\mid N\ \text{ and }\ \tau_p(x)<\tau_p(y)\text{ whenever }r(x,y).(1)

A job triple Z⊆JZ\subseteq J is a set of three jobs.✦ A scheduling triple boundary AA is an endpoint ⊥\bot or ⊤\top, or a job triple.✦ The boundary time relation At⁡p(A,s)\operatorname{At}_p(A,s) for a scheduling triple boundary AA and slot ss is the condition in (2). At⁡p(A,s)⇔{s=0,A=⊥,1≤s≤T and Z={x∈J:τp(x)=s},A=Z,s=T+1,A=⊤.\operatorname{At}_p(A,s)\ \Longleftrightarrow\ \begin{cases} s=0,&A=\bot,\\ 1\le s\le T\ \text{ and }Z=\{x\in J:\tau_p(x)=s\},&A=Z,\\ s=T+1,&A=\top. \end{cases}(2)✦ The strict predecessor cone PAP_A, strict successor cone DAD_A, and weak predecessor cone PAwP_A^{\mathrm w} are the sets in (3). APADAPAw⊥⌀J⌀Z{x:∃z∈Z,r(x,z)}{x:∃z∈Z,r(z,x)}PZ∪Z⊤J⌀J\begin{array}{c|ccc} A&P_A&D_A&P_A^{\mathrm w}\\ \hline \bot&\varnothing&J&\varnothing\\ Z&\{x:\exists z\in Z,\ r(x,z)\} &\{x:\exists z\in Z,\ r(z,x)\}&P_Z\cup Z\\ \top&J&\varnothing&J \end{array}(3) For boundary slots a,ba,b in a job layout pp, the open scheduling window W=(a,b)W=(a,b) is the job set in (4). Wp(a,b)={x∈J:a<τp(x)<b}.W_p(a,b)=\{x\in J:a<\tau_p(x)<b\}.(4)✦

Fix an atomic family 𝒜=(𝒜α)α∈Λ\mathcal A=(\mathcal A_\alpha)_{\alpha\in\Lambda} of subsets of JJ. A Boolean structural formula ff over the atomic family 𝒜\mathcal A is an expression built from atoms or their complements by conjunction and disjunction.✦ The interpretation ⟦f⟧𝒜\llbracket f\rrbracket_{\mathcal A} of a Boolean structural formula ff is the job set obtained by interpreting conjunction as intersection and disjunction as union.✦ The leaf count ℓ(f)\ell(f) of a Boolean structural formula ff is the natural number equal to one at a leaf and to the sum of the two operand counts at either operation.✦ Bounded leaf describability Desc⁡k(E)\operatorname{Desc}_k(E) of a job set EE with allowance kk is the condition in (5). Desc⁡k(E)⇔∃f,⟦f⟧𝒜=Eandℓ(f)≤k.\operatorname{Desc}_k(E)\ \Longleftrightarrow\ \exists f,\quad \llbracket f\rrbracket_{\mathcal A}=E \quad\text{and}\quad \ell(f)\le k.(5)✦

The Definition

Definition 1. An indexed global set family ℒ\mathcal L on JJ is a pair consisting of a finite set of natural indices and a sequence of subsets of JJ, as in (6). ℒ=(I,(Fi)i∈ℕ),I⊆ℕ finite,Fi⊆J.\mathcal L=(I,(F_i)_{i\in\mathbb N}),\qquad I\subseteq\mathbb N\text{ finite},\qquad F_i\subseteq J.(6)✦ The global entry union QℒQ_{\mathcal L} of an indexed global set family ℒ\mathcal L on JJ is the set in (7), whose members are called qualifying jobs. Qℒ=⋃i∈IFi.Q_{\mathcal L}=\bigcup_{i\in I}F_i.(7)✦ For a job x∈Jx\in J, the membership index set Mℒ(x)M_{\mathcal L}(x) is the set in (8), and its last membership index mℒ(x)m_{\mathcal L}(x) is the natural number given there, with default zero when the membership index set is empty. Mℒ(x)={i∈I:x∈Fi},mℒ(x)=max⁡(Mℒ(x)∪{0}).M_{\mathcal L}(x)=\{i\in I:x\in F_i\},\qquad m_{\mathcal L}(x)=\max\bigl(M_{\mathcal L}(x)\cup\{0\}\bigr).(8) For a rank function ρ:J→ℕ\rho:J\to\mathbb N and an indexed global set family ℒ\mathcal L on JJ, lexicographic list priority ⊲ℒ,ρ\triangleleft_{\mathcal L,\rho} is the relation on jobs in (9). x⊲ℒ,ρy⇔mℒ(x)<mℒ(y) or (mℒ(x)=mℒ(y) and ρ(x)<ρ(y)).x\mathrel{\triangleleft_{\mathcal L,\rho}}y \ \Longleftrightarrow\ m_{\mathcal L}(x)<m_{\mathcal L}(y) \ \text{ or }\ \bigl(m_{\mathcal L}(x)=m_{\mathcal L}(y)\ \text{ and }\rho(x)<\rho(y)\bigr).(9)✦ The numerical global list key vℒ,ρ,H(x)v_{\mathcal L,\rho,H}(x) of a job x∈Jx\in J, with natural parameter HH, is the natural number in (10). vℒ,ρ,H(x)=mℒ(x)H+ρ(x).v_{\mathcal L,\rho,H}(x)=m_{\mathcal L}(x)H+\rho(x).(10)✦ For a job set C⊆JC\subseteq J, the same-list priority σℒ,ρ,H,C\sigma_{\mathcal L,\rho,H,C} is a function from jobs to natural numbers, with parameters as in (11). σℒ,ρ,H,C:J→ℕ.\sigma_{\mathcal L,\rho,H,C}:J\longrightarrow\mathbb N.(11)✦ For a job set D⊆JD\subseteq J, the list-switch priority ωρ,H,D\omega_{\rho,H,D} is a function from jobs to natural numbers, with parameters as in (12). ωρ,H,D:J→ℕ.\omega_{\rho,H,D}:J\longrightarrow\mathbb N.(12)✦

A global upset U⊆JU\subseteq J is a set closed under successors: whenever x∈Ux\in U and r(x,y)r(x,y), also y∈Uy\in U.✦ The entries of ℒ\mathcal L are upward closed when every FiF_i with i∈Ii\in I is a global upset.✦ An indexed global set family ℒ\mathcal L on JJ has injection disjointness within WW when the sets Fi∩WF_i\cap W, for listed indices i≥2i\ge2, are pairwise disjoint.✦

The rank upper tail RkR_k at kk is the job set {x∈J:k≤ρ(x)}\{x\in J:k\le\rho(x)\}.✦ A rank threshold run certificate 𝒞\mathcal C for ℒ\mathcal L in WW is a family of base sets (Ui)i∈ℕ(U_i)_{i\in\mathbb N} and natural thresholds (ki)i∈ℕ(k_i)_{i\in\mathbb N}, together with a second set S⊆JS\subseteq J, satisfying (13). Fi=Ui∩Rki(i∈I),Desc⁡2(Ui)(i∈I\{0}),Desc⁡24(U0),Desc⁡1(S),U1=S,W\S⊆U0,x∈W∩S and 0∈I⇒1∈I and x∈F1.\begin{gathered} F_i=U_i\cap R_{k_i}\quad(i\in I),\qquad \operatorname{Desc}_2(U_i)\quad(i\in I\setminus\{0\}),\\ \operatorname{Desc}_{24}(U_0),\qquad \operatorname{Desc}_1(S),\qquad U_1=S,\qquad W\setminus S\subseteq U_0,\\ x\in W\cap S\text{ and }0\in I \quad\Longrightarrow\quad 1\in I\text{ and }x\in F_1. \end{gathered}(13)✦ A reverse induction seed at boundary BB and slot bb is a set E⊆JE\subseteq J closed under predecessors and satisfying (14). Desc⁡24(E),W\PB⊆E,E⊆{x∈J:τp(x)<b}.\operatorname{Desc}_{24}(E),\qquad W\setminus P_B\subseteq E,\qquad E\subseteq\{x\in J:\tau_p(x)<b\}.(14)✦

At a boundary AA and slot aa, the past boundary invariant Past⁡(p,ℒ,A,a)\operatorname{Past}(p,\mathcal L,A,a) is the condition in (15). Past⁡(p,ℒ,A,a)⇔Qℒ∩{x∈J:τp(x)≤a}⊆PAw.\operatorname{Past}(p,\mathcal L,A,a)\ \Longleftrightarrow\ Q_{\mathcal L}\cap\{x\in J:\tau_p(x)\le a\}\subseteq P_A^{\mathrm w}.(15)✦ A layout qq is fixed outside WW relative to pp when q(x)=p(x)q(x)=p(x) for every x∉Wx\notin W.✦ For jobs x,y∈Jx,y\in J, the job exchange qxyq^{xy} of a layout qq is the layout that interchanges the positions of xx and yy and keeps every other position fixed.✦ The forbidden exchange invariant Swap⁡(p,W,ℒ,ρ,A,a)\operatorname{Swap}(p,W,\mathcal L,\rho,A,a) is the condition that (16) holds for every precedence-feasible layout qq fixed outside WW, every x∈W\DAx\in W\setminus D_A, and every y∈Qℒy\in Q_{\mathcal L} with τq(y)=a\tau_q(y)=a and x⊲ℒ,ρyx\mathrel{\triangleleft_{\mathcal L,\rho}}y. ∃u,v∈J,r(u,v)andτqxy(u)≥τqxy(v).\exists u,v\in J,\qquad r(u,v) \quad\text{and}\quad \tau_{q^{xy}}(u)\ge\tau_{q^{xy}}(v).(16)✦

A node structural certificate for r,ρ,𝒜,p,Wr,\rho,\mathcal A,p,W consists of boundary slots a,ba,b, boundaries A,BA,B, a global list ℒ\mathcal L, a rank threshold run certificate 𝒞\mathcal C for that list in WW, and a reverse induction seed at B,bB,b, subject to (17). Full⁡(p,r),At⁡p(A,a),At⁡p(B,b),W=Wp(a,b),Fi is a global upset (i∈I),S is a global upset,ℒ has injection disjointness within W,|I|≤5,W∩Qℒ⊆PB,W\Qℒ⊆DA,Past⁡(p,ℒ,A,a),Swap⁡(p,W,ℒ,ρ,A,a),Desc⁡406(W).\begin{gathered} \operatorname{Full}(p,r),\qquad \operatorname{At}_p(A,a),\qquad \operatorname{At}_p(B,b),\qquad W=W_p(a,b),\\ F_i\text{ is a global upset }(i\in I),\qquad S\text{ is a global upset},\\ \mathcal L\text{ has injection disjointness within }W,\qquad |I|\le5,\\ W\cap Q_{\mathcal L}\subseteq P_B,\qquad W\setminus Q_{\mathcal L}\subseteq D_A,\\ \operatorname{Past}(p,\mathcal L,A,a),\qquad \operatorname{Swap}(p,W,\mathcal L,\rho,A,a),\qquad \operatorname{Desc}_{406}(W). \end{gathered}(17)✦

In the paper, the result reads: a node W=(a,b)W=(a,b) in its tag frame, a working frame that may reverse precedence and time, has an ordered list of global upsets whose qualifier union selects the local old-high set OO, a qualifying job’s key is its largest membership index followed by rank, and the invariants are O⊆PBO\subseteq P_B and W\O⊆DAW\setminus O\subseteq D_A, every qualifying job scheduled at or before aa lies in PAwP_A^{\mathrm w}, and after every feasible reordering of WW no job in W\DAW\setminus D_A with a better key can feasibly exchange with a qualifying job at aa, with same and switched sides using the cutoffs and priorities of §5.2.

What Is Checked

These definitions are stated over a finite job set JJ with precedence rr, a natural-valued rank ρ\rho, an assignment 𝒜\mathcal A of job sets to atoms, layouts, and scheduling triple boundaries.