OctoInformBeta

OpenAI preprint, September 2026 · §7. Preserving the global boundary invariants

Proposition 7.3: Boundary conditions survive the root and edge constructions, and window size bounds recursive acceptance depth

Structural certificates persist through recursive scheduling.

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 subproblem consists of the jobs between two occupied slots of a full schedule. Its boundary conditions constrain jobs outside the subproblem as well as jobs inside it. The library states the root, center and edge constructions using structural certificates for these conditions.

Let JJ be the padded job set, with N=3TN=3T jobs and deadline TT. 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 its open window are given by (1). τp(x)=⌊p(x)3⌋+1,(a,b)p={x∈J:a<τp(x)<b}.\tau_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad (a,b)_p=\{x\in J:a<\tau_p(x)<b\}.(1) For a precedence relation rr on JJ, a layout pp is precedence feasible when r(x,y)r(x,y) entails τp(x)<τp(y)\tau_p(x)<\tau_p(y); a full schedule is a feasible layout whose number of jobs is divisible by three.✦ Times and precedence are measured in the working frame, which may have the direction opposite to the original schedule.

A boundary is the left endpoint, the right endpoint, or a triple Z⊆JZ\subseteq J of three jobs.✦ The endpoint slots are 00 and T+1T+1; an actual boundary at slot ss has 1≤s≤T1\le s\le T and consists exactly of the jobs scheduled at ss.✦ For an actual triple ZZ, its strict predecessor cone PZP_Z consists of jobs preceding some member of ZZ, and its strict successor cone DZD_Z consists of jobs preceded by some member of ZZ. For an actual boundary triple ZZ of JJ, the weak predecessor cone P¯Z\overline P_Z is the set of jobs in ZZ or preceding some member of ZZ, and the weak successor cone D¯Z\overline D_Z is the set of jobs in ZZ or preceded by some member of ZZ. At the left endpoint the predecessor cones are empty and the successor cones are JJ; at the right endpoint these assignments are reversed.

A boundary BB separates a job set UU relative to a set SS at slot ss when the two conditions in (2) hold.✦ Write this condition as Sep⁡p(B;U,S;s)\operatorname{Sep}_p(B;U,S;s). x∈U,τp(x)<s,x∉S⇒x∈PB,x∈U,s<τp(x),x∈S⇒x∈DB.\begin{aligned} x\in U,\ \tau_p(x)<s,\ x\notin S&\ \Longrightarrow\ x\in P_B,\\ x\in U,\ s<\tau_p(x),\ x\in S&\ \Longrightarrow\ x\in D_B. \end{aligned}(2)

Lists and Certificates

A Boolean structural formula over an atomic family 𝒜\mathcal A of subsets of JJ is built from atoms or their complements using conjunction and disjunction.✦ The interpretation of a Boolean structural formula over 𝒜\mathcal A is the job set obtained by interpreting signed atoms as their sets and replacing conjunction and disjunction by intersection and union. Each signed atom counts as one leaf, and the leaf counts add at either binary operation.✦ Write 𝒟k(F)\mathcal D_k(F) when a formula with at most kk leaves denotes FF.✦ For a job set LL and a window WW in JJ, a relative description of LL in WW is a Boolean structural formula denoting a global job set FF such that L=W∩FL=W\cap F. For a rank function ρ\rho on JJ, the atomic family 𝒜\mathcal A is expressive for (r,ρ)(r,\rho) when JJ, the empty set, every rank upper tail {x:k≤ρ(x)}\{x:k\le\rho(x)\}, every strict or weak boundary cone, and every job triple each have a one-leaf description.✦

An indexed global list ℒ=(I,(Li)i≥0)\mathcal L=(I,(L_i)_{i\ge0}) consists of a finite set I⊆ℕI\subseteq\mathbb N and global job sets LiL_i.✦ Its union, membership indices and last membership index are defined in (3); the maximum defaults to zero. Lexicographic list priority compares (ℓ(x),ρ(x))(\ell(x),\rho(x))✦, while kBk_B is its numeric key at scale BB. Qℒ=⋃i∈ILi,M(x)={i∈I:x∈Li},ℓ(x)=max⁡(M(x)∪{0}),kB(x)=Bℓ(x)+ρ(x).Q_{\mathcal L}=\bigcup_{i\in I}L_i,\qquad M(x)=\{i\in I:x\in L_i\},\qquad \ell(x)=\max(M(x)\cup\{0\}),\qquad k_B(x)=B\ell(x)+\rho(x).(3) A global upset FF of JJ is a job set containing every successor of each of its jobs. An indexed global list ℒ\mathcal L has upset entries when every listed LiL_i is a global upset.✦ The injection entries of an indexed global list ℒ\mathcal L are disjoint in a window WW when W∩Li∩LjW\cap L_i\cap L_j is empty for distinct listed indices i,j≥2i,j\ge2.✦ The pruning of an indexed global list ℒ\mathcal L at a window WW is the indexed global list obtained by retaining precisely the indices whose entries meet WW and leaving the entries themselves unchanged.✦ The singleton list of a set FF has sole listed index 11 and entry FF.✦

A rank threshold run for ℒ\mathcal L on WW consists of bases UiU_i, thresholds hi∈ℕh_i\in\mathbb N, and a second set SS, subject to (4).✦ Here ii is listed wherever an entry condition is imposed. Li=Ui∩{x:hi≤ρ(x)}(i∈I),𝒟2(Ui)(i∈I\{0}),𝒟24(U0),𝒟1(S),U1=S,W\S⊆U0,0∈I⇒(∀x∈W∩S,1∈I and x∈L1).\begin{gathered} L_i=U_i\cap\{x:h_i\le\rho(x)\}\quad(i\in I),\qquad \mathcal D_2(U_i)\quad(i\in I\setminus\{0\}),\\ \mathcal D_{24}(U_0),\qquad \mathcal D_1(S),\qquad U_1=S,\qquad W\setminus S\subseteq U_0,\\ 0\in I\ \Longrightarrow\ \bigl(\forall x\in W\cap S,\ 1\in I\text{ and }x\in L_1\bigr). \end{gathered}(4)

For a left boundary LL at slot aa, the past boundary invariant requires every job of QℒQ_{\mathcal L} scheduled at or before aa to lie in P¯L\overline P_L.✦ The forbidden exchange invariant on WW at (L,a)(L,a) concerns every feasible layout qq agreeing with pp outside WW. For x∈W\DLx\in W\setminus D_L and y∈Qℒy\in Q_{\mathcal L} with τq(y)=a\tau_q(y)=a, if xx has smaller lexicographic list priority than yy, exchanging their positions in qq must violate precedence feasibility.✦ For jobs x,y∈Jx,y\in J in a layout qq of JJ, their job exchange is the layout in which xx and yy trade positions and every other job keeps its position.

A reverse seed HH at a right boundary RR at slot bb is a downward closed job set with 𝒟24(H)\mathcal D_{24}(H), containing W\PRW\setminus P_R, whose jobs all occur before bb.✦ A switch seed GG at a left boundary LL at slot aa is an upset with 𝒟24(G)\mathcal D_{24}(G), containing W\DLW\setminus D_L, whose jobs all occur after aa.✦

A node certificate for (p,W,r,ρ,𝒜)(p,W,r,\rho,\mathcal A) consists of a full schedule, boundaries L,RL,R at slots a,ba,b with W=(a,b)pW=(a,b)_p, and a global list with a rank threshold run on WW. Its listed entries and second set are upsets, its injection entries are disjoint in WW, and it has at most five listed indices. The confinement and window description conditions are (5). W∩Qℒ⊆PR,W\Qℒ⊆DL,𝒟406(W).W\cap Q_{\mathcal L}\subseteq P_R,\qquad W\setminus Q_{\mathcal L}\subseteq D_L,\qquad \mathcal D_{406}(W).(5) The certificate also requires the past and forbidden exchange invariants at (L,a)(L,a) and a reverse seed at (R,b)(R,b). Let 𝖭ρ(p,W)\mathsf N_\rho(p,W) denote the collection of these node certificates, with rr and 𝒜\mathcal A understood.

An edge certificate uses a full schedule pp, parent window W=(a,b)pW=(a,b)_p, and boundaries R,V,A′,B′R,V,A',B' at slots b,v,a′,b′b,v,a',b'. Its target B′B' is an actual triple, and its slots satisfy (6). a≤a′<b′≤v<b.a\le a'<b'\le v<b.(6) It has a cutoff CC and a final cutoff FF with 𝒟1(F)\mathcal D_1(F): VV separates WW relative to FF, and A′,B′A',B' separate (a,v)p(a,v)_p relative to CC at their respective slots. Its cutoff jobs in WW belong to PR∩FP_R\cap F. The edge list has a rank threshold run on WW, upset entries and second set, and disjoint injection entries in WW; its union agrees in WW with the complement of CC. It satisfies the past invariant at (A′,a′)(A',a') and the forbidden exchange invariant on (a′,b′)p(a',b')_p at that boundary. There are global sets C*C^* and H*H^* agreeing with CC in WW, with 𝒟205(C*)\mathcal D_{205}(C^*) and 𝒟21(H*)\mathcal D_{21}(H^*), and H*H^* is downward closed. Write 𝖤ρ(p,W;a,b,v,a′,b′;R,V,A′,B′)\mathsf E_\rho(p,W;a,b,v,a',b';R,V,A',B') for the collection of these certificates.

Priorities and Recursive Acceptance

For a priority assignment π:J→ℕ\pi:J\to\mathbb N, the priority signature of a layout lists the priorities of its jobs in position order.✦ A normalized layout pp on a job set UU for a priority assignment π\pi is a feasible layout whose priority signature is lexicographically minimal among feasible layouts agreeing with pp outside UU.✦ For a priority assignment π\pi on JJ, the numeric cut at threshold cc is the job set {x:π(x)<c}\{x:\pi(x)<c\}.✦ Write πs\pi_s for the same-direction priority determined by ℒ,ρ,B,PR\mathcal L,\rho,B,P_R, and π×\pi_\times for the direction-change priority determined by ρ,B,DL\rho,B,D_L.

A relative ideal UU on a finite job set EE is a job set containing every predecessor in EE of each of its jobs in EE.✦ A priority prefix UU on a finite job set EE is a job set whose jobs in EE precede all other jobs in EE in priority order.✦ The cutoff descendants at slot ss are the jobs preceded by some job scheduled at ss.✦ An earliest exceptional job xx for a set UU in a finite job set EE after slot ss is a job in E∩UE\cap U that occurs after ss and is outside the cutoff descendants, with every job of E∩UE\cap U at an intervening slot a cutoff descendant.✦ An exception cutoff walk on a finite job set EE with a specified priority order and final cut is a sequence of slots that starts at a cutoff aa and, at each step, chooses a relative ideal UU that is a priority prefix and is contained in the final cut within EE, then moves to the slot of an earliest exceptional job for UU.✦ A walk may have no steps.

Structural acceptance 𝖠dr(W)\mathsf A_d^r(W) has fixed allowance K=10000K=10000. At depth zero it requires 𝒟K(W)\mathcal D_K(W) and W=⌀W=\varnothing. At depth d+1d+1 it requires 𝒟K(W)\mathcal D_K(W) and either an empty window or structural split vertices u,vu,v joined by a possibly empty chain of admissible split transitions. The left region of uu, the right region of vv, and every intervening gap must have acceptance at depth dd.

The Claim

Theorem 1. Assume that 𝒜\mathcal A is expressive for (r,ρ)(r,\rho). For a full schedule pp, the root construction has the property (7). root⁡(p)∈𝖭ρ(p,J).\operatorname{root}(p)\in\mathsf N_\rho(p,J).(7)✦

Let rr be transitive and let D∈𝖭ρ(p,W)D\in\mathsf N_\rho(p,W) have nonempty window WW, endpoints a,ba,b and right boundary RR. There are a layout qq, a slot vv and a boundary VV satisfying (8). q(x)=p(x)(x∉W),q is precedence feasible,a<v<b,V is at slot v in q,Sep⁡q(V;W,PR;v).\begin{gathered} q(x)=p(x)\quad(x\notin W),\qquad q\text{ is precedence feasible},\\ a<v<b,\qquad V\text{ is at slot }v\text{ in }q,\qquad \operatorname{Sep}_q(V;W,P_R;v). \end{gathered}(8)✦

For the edge constructions assume transitivity, expressiveness for (r,ρ)(r,\rho), ρ(x)<B\rho(x)<B for every job, and strict increase of ρ\rho along rr. Let W=(a,b)pW=(a,b)_p, let L,RL,R be boundaries at a,ba,b, and let V,A′,B′V,A',B' be boundaries at v,a′,b′v,a',b' satisfying (6), with B′B' actual.

In the same-direction case, take a node certificate DD with these endpoints and right boundary RR, and assume B>0B>0. Let m=max⁡(I∪{0})m=\max(I\cup\{0\}), take t≤(m+1)Bt\le(m+1)B, and put C={x:πs(x)<B+t}C=\{x:\pi_s(x)<B+t\}. Assume VV separates WW relative to PRP_R, pp is normalized on (a,v)p(a,v)_p for πs\pi_s, and A′,B′A',B' separate that window relative to CC. If there is an exception cutoff walk from aa to a′a' on the finite set (a,v)p(a,v)_p with final cut CC, then (9) holds. 𝖤ρ(p,W;a,b,v,a′,b′;R,V,A′,B′)≠⌀.\mathsf E_\rho(p,W;a,b,v,a',b';R,V,A',B')\ne\varnothing.(9)✦

In the direction-change case, let pp be full, assume W⊆DL∪PRW\subseteq D_L\cup P_R, and take a switch seed at (L,a)(L,a). Take t≤Bt\le B and put C={x:π×(x)<t}C=\{x:\pi_\times(x)<t\}. Assume VV separates WW relative to J\DLJ\setminus D_L, pp is normalized on (a,v)p(a,v)_p for π×\pi_\times, and A′,B′A',B' separate that window relative to CC. Then (10) holds. 𝖤ρ(p,W;a,b,v,a′,b′;R,V,A′,B′)≠⌀.\mathsf E_\rho(p,W;a,b,v,a',b';R,V,A',B')\ne\varnothing.(10)✦

For an edge certificate EE, transitivity and expressiveness for (r,ρ)(r,\rho) give the child construction in (11). child⁡(E)∈𝖭ρ(p,(a′,b′)p).\operatorname{child}(E)\in\mathsf N_\rho\bigl(p,(a',b')_p\bigr).(11)✦ Every edge certificate satisfies the strict inclusion (12). (a′,b′)p⊊W.(a',b')_p\subsetneq W.(12)✦

Let rr be transitive and let ρ,ρ‾\rho,\bar\rho be injective ranks, strictly increasing along rr and reversed rr, respectively. Suppose both ranks are below a positive bound BB, and 𝒜\mathcal A is expressive in both frames. For D∈𝖭ρ(p,W)D\in\mathsf N_\rho(p,W) and |W|≤d|W|\le d, recursive acceptance satisfies (13). 𝖠dr(W).\mathsf A_d^r(W).(13)✦

In the paper, the result reads: starting from any feasible full schedule, the marking and list construction is defined at every node, its pruned lists are global upset lists of length at most five with fewer than 4040 leaves per entry satisfying all three invariants, and every branch terminates.

What Is Checked

The statements concern finite full layouts, global lists and their rank threshold runs, boundary cones and Boolean descriptions, with the transitivity and rank hypotheses specified for each construction. Whenever 𝒟1(J)\mathcal D_1(J) holds, the singleton list of JJ has a root rank threshold run on every window WW, for the given rank function and atomic family; a run on WW restricts to a run for the pruned list on every smaller window W′⊆WW'\subseteq W.✦