OctoInformBeta

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

Lemma 5.1: Node reconstruction under transitive precedence and expressive atomic predicates

Edge certificates yield smaller child intervals.

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 decomposition of a three-machine schedule assigns jobs to open intervals between boundary slots. A child interval needs the same structural conditions as a parent interval, including conditions on jobs outside it and on exchanges across its left boundary.

Let TT be a valid deadline and JJ a finite job set of size N=3TN=3T, with precedence relation rr and rank ρ:J→ℕ\rho:J\to\mathbb N. A layout pp is a bijection from JJ to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ Its slot assignment and open scheduling windows are given by (1); a full layout respects precedence, meaning that r(x,y)r(x,y) requires τ(x)<τ(y)\tau(x)<\tau(y). τ(x)=⌊p(x)3⌋+1,(a,b)={x∈J:a<τ(x)<b}.\tau(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad (a,b)=\{x\in J:a<\tau(x)<b\}.(1)

A scheduling triple boundary is a left endpoint, a set Z⊆JZ\subseteq J of three jobs, or a right endpoint.✦ Their boundary times are respectively 00, a slot ss with 1≤s≤T1\le s\le T and Z={x:τ(x)=s}Z=\{x:\tau(x)=s\}, and T+1T+1.✦ For an actual boundary ZZ, its strict 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 assignments are reversed. PZ={x:∃z∈Z,r(x,z)},DZ={x:∃z∈Z,r(z,x)},P¯Z=PZ∪Z,D¯Z=DZ∪Z.\begin{aligned} P_Z&=\{x:\exists z\in Z,\ r(x,z)\},& D_Z&=\{x:\exists z\in Z,\ r(z,x)\},\\ \overline P_Z&=P_Z\cup Z,& \overline D_Z&=D_Z\cup Z. \end{aligned}(2)

A boundary BB at slot ss separates a job set UU relative to a cutoff CC when (3) holds. {x∈U\C:τ(x)<s}⊆PB,{x∈U∩C:s<τ(x)}⊆DB.\{x\in U\setminus C:\tau(x)<s\}\subseteq P_B, \qquad \{x\in U\cap C:s<\tau(x)\}\subseteq D_B.(3)✦

Descriptions and Structural Conditions

An atomic family 𝒜\mathcal A assigns a subset of JJ to each atom. A Boolean structural formula φ\varphi over 𝒜\mathcal A is a formula whose leaves are signed atoms and whose binary operations are conjunction and disjunction.✦ Its interpretation uses complement in JJ for a negative leaf, intersection for conjunction and union for disjunction.✦ Its leaf count ℓ\ell is one at a leaf and adds the counts of the two subformulas at either binary operation.✦ A set F⊆JF\subseteq J has description bound kk, written Desck(F)\mathrm{Desc}_k(F), when (4) holds. Desck(F)⇔∃φ(F=⟦φ⟧𝒜andℓ(φ)≤k).\mathrm{Desc}_k(F) \quad\Longleftrightarrow\quad \exists\varphi\ \bigl(F=\llbracket\varphi\rrbracket_{\mathcal A} \ \text{and}\ \ell(\varphi)\le k\bigr).(4)✦

The family 𝒜\mathcal A has atomic predicate expressiveness for rr and ρ\rho if JJ, the empty set, every rank upper tail {x:k≤ρ(x)}\{x:k\le\rho(x)\}, every boundary’s strict and weak cones, and every job triple each have description bound one.✦

An indexed global set family 𝒦\mathcal K consists of a finite index set I⊆ℕI\subseteq\mathbb N and job sets KiK_i for all natural numbers ii.✦ Its global entry union QQ, membership indices MxM_x and last membership index m(x)m(x) are specified in (5). Lexicographic list priority orders jobs by (m(x),ρ(x))(m(x),\rho(x)).✦ Q=⋃i∈IKi,Mx={i∈I:x∈Ki},m(x)=max⁡(Mx∪{0}).Q=\bigcup_{i\in I}K_i, \qquad M_x=\{i\in I:x\in K_i\}, \qquad m(x)=\max(M_x\cup\{0\}).(5) The family obtained by pruning 𝒦\mathcal K relative to a job set WW retains precisely the listed indices whose entries meet WW, with every global entry unchanged.

A job set F⊆JF\subseteq J is globally upward closed for rr when it contains every successor of each of its jobs.✦ An indexed global set family 𝒦\mathcal K has upward-closed entries when every listed job set KiK_i is globally upward closed for rr.✦ For a scheduling window W⊆JW\subseteq J, the injection entries of an indexed global set family 𝒦\mathcal K are disjoint within WW when W∩Ki∩Kj=⌀W\cap K_i\cap K_j=\varnothing for distinct listed indices i,j≥2i,j\ge2.✦

A rank threshold run certificate for 𝒦\mathcal K on WW consists of base sets UiU_i, thresholds kik_i and a distinguished second set S2S_2, satisfying (6). Listed nonzero bases have description bound two, U0U_0 has bound 2424, and S2S_2 has bound one. If 0∈I0\in I and W∩S2W\cap S_2 is nonempty, then 1∈I1\in I and every job of W∩S2W\cap S_2 belongs to K1K_1. Ki=Ui∩{x:ki≤ρ(x)}(i∈I),U1=S2,W\S2⊆U0.K_i=U_i\cap\{x:k_i\le\rho(x)\}\quad(i\in I), \qquad U_1=S_2, \qquad W\setminus S_2\subseteq U_0.(6)

The past boundary invariant for 𝒦\mathcal K at a boundary AA with time aa is {x∈Q:τ(x)≤a}⊆P¯A\{x\in Q:\tau(x)\le a\}\subseteq\overline P_A.✦

A layout qq is unchanged outside WW relative to pp if q(x)=p(x)q(x)=p(x) for every x∉Wx\notin W.✦ Exchanging xx and yy in qq trades their positions and leaves every other position fixed.✦ The forbidden exchange invariant on WW at A,aA,a requires the following: for every precedence-respecting qq unchanged outside WW, jobs x∈W\DAx\in W\setminus D_A and y∈Qy\in Q with τq(y)=a\tau_q(y)=a and (m(x),ρ(x))<(m(y),ρ(y))(m(x),\rho(x))<(m(y),\rho(y)) have an exchange that fails precedence feasibility.✦

A reverse induction seed at a boundary BB with time bb for a window WW is a job set HH closed under predecessors, with description bound 2424, such that W\PB⊆HW\setminus P_B\subseteq H and every job of HH has slot strictly before bb.✦

A node structural certificate on WW consists of a full layout pp, boundaries A,BA,B at slots a,ba,b with W=(a,b)W=(a,b), and an indexed family with a rank threshold run certificate on WW. Its entries and second set are upward closed, its injection entries are disjoint within WW, and |I|≤5|I|\le5. Its confinement conditions are (7); it satisfies the past boundary and forbidden exchange invariants at A,aA,a, has Desc406(W)\mathrm{Desc}_{406}(W), and has a reverse induction seed at B,bB,b. Write Node⁡(r,ρ,𝒜,p,W)\operatorname{Node}(r,\rho,\mathcal A,p,W) for these certificates. W∩Q⊆PB,W\Q⊆DA.W\cap Q\subseteq P_B, \qquad W\setminus Q\subseteq D_A.(7)

Edge Certificates

An edge structural certificate ℰ\mathcal E on a parent window W=(a,b)W=(a,b) has a full layout pp and boundaries B,V,A′,B′B,V,A',B' at times b,v,a′,b′b,v,a',b' respectively. The target B′B' is an actual triple and the slot bounds are (8). Set E=(a,v)E=(a,v) and W′=(a′,b′)W'=(a',b'). a≤a′<b′≤v<b.a\le a'<b'\le v<b.(8)

The certificate has a cutoff CC and final cutoff SS, with Desc1(S)\mathrm{Desc}_1(S). The center VV separates WW relative to SS; both A′A' and B′B' separate EE relative to CC, at their respective boundary times. It has an indexed family with a rank threshold run certificate on WW, upward-closed entries and second set, and injection entries disjoint within WW. The labels and cutoff satisfy (9). The past boundary invariant holds at A′,a′A',a' and the forbidden exchange invariant holds on W′W' at that boundary. W∩C⊆PB∩S,W∩Q=W\C.W\cap C\subseteq P_B\cap S, \qquad W\cap Q=W\setminus C.(9)

The edge certificate has a global cutoff GG of description bound 205205 and a lower extension HH of description bound 2121. The set HH is closed under predecessors, and their agreement with CC is given by (10). W∩G=W∩C=W∩H.W\cap G=W\cap C=W\cap H.(10)

The Claim

Theorem 1. Let ℰ\mathcal E be an edge structural certificate as above. If rr is transitive and 𝒜\mathcal A has atomic predicate expressiveness for r,ρr,\rho, the child node construction 𝒩\mathcal N satisfies (11). 𝒩(ℰ)∈Node⁡(r,ρ,𝒜,p,W′).\mathcal N(\mathcal E)\in \operatorname{Node}(r,\rho,\mathcal A,p,W').(11)✦ For every edge structural certificate, the child window satisfies (12). W′⊊W.W'\subsetneq W.(12)✦

In the paper, the result reads: at every child edge B′B' is an actual triple in WW and A′A' is either the boundary at aa or an actual triple in the open side EE; for W′=(a′,b′)W'=(a',b') with shared cutoff SS, W′∩S⊆DA′∩PBW'\cap S\subseteq D_{A'}\cap P_B and W′\S⊆PB′W'\setminus S\subseteq P_{B'}; every child excludes the center and is strictly smaller than its parent, and the root has no nonempty switched child.

What Is Checked

The claims concern finite job sets, full layouts and edge structural certificates; child node reconstruction also assumes transitive precedence and atomic predicate expressiveness.

For W0⊆WW_0\subseteq W, a rank threshold run certificate for 𝒦\mathcal K on WW yields a pruned run certificate for the family pruned relative to W0W_0 on W0W_0, with the same rank and atomic family.✦