OctoInformBeta

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

Lemma 7.1: Pruning preserves the condition, and direction changes admit edge certificates under the scheduling hypotheses

Child updates preserve the past boundary invariant.

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 window has a list of globally defined job sets, although only jobs between its boundaries belong to the current subproblem. Moving the left boundary changes which earlier jobs the list can retain. The past boundary condition concerns those jobs in the whole job set, including jobs outside the window.

Let TT be a valid deadline and JJ a finite job set of size N=3TN=3T, with precedence relation ≺\prec. A layout pp is a bijection from JJ to positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ The slot assignment τp\tau_p of a layout pp is the function given in (1).✦ A layout pp respects precedence when x≺yx\prec y entails τp(x)<τp(y)\tau_p(x)<\tau_p(y)✦; it is full when it respects precedence and its number of jobs is divisible by three.✦ For a slot assignment τ\tau, the open scheduling window W=(a,b)W=(a,b) is the set in (1).✦ τp(x)=⌊p(x)3⌋+1,(a,b)={x∈J:a<τ(x)<b}.\tau_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad (a,b)=\{x\in J:a<\tau(x)<b\}.(1)

A job triple ZZ is a three-element subset of JJ.✦ A scheduling boundary BB is a left endpoint ⊥\bot, an actual job triple ZZ, or a right endpoint ⊤\top.✦ A scheduling boundary BB is at slot ss if it is ⊥\bot and s=0s=0, is ⊤\top and s=T+1s=T+1, or is a triple with 1≤s≤T1\le s\le T consisting exactly of the jobs at ss.✦ The strict predecessor and successor cones P(B),D(B)P(B),D(B) and their weak versions P¯(B),D¯(B)\overline P(B), \overline D(B) are given by (2). BP(B)D(B)P¯(B)D¯(B)⊥⌀J⌀JZ{x:∃z∈Z,x≺z}{x:∃z∈Z,z≺x}P(Z)∪ZD(Z)∪Z⊤J⌀J⌀\begin{array}{c|cccc} B&P(B)&D(B)&\overline P(B)&\overline D(B)\\ \hline \bot&\varnothing&J&\varnothing&J\\ Z&\{x:\exists z\in Z,\ x\prec z\} &\{x:\exists z\in Z,\ z\prec x\}&P(Z)\cup Z&D(Z)\cup Z\\ \top&J&\varnothing&J&\varnothing \end{array}(2)

A boundary BB separates a job set UU with cutoff set SS at slot ss when the two containments in (3) hold; write this condition as 𝖲𝖾𝗉(B,U,S;s)\mathsf{Sep}(B,U,S;s).✦ {x∈U:τ(x)<s}\S⊆P(B),{x∈U:s<τ(x)}∩S⊆D(B).\{x\in U:\tau(x)<s\}\setminus S\subseteq P(B), \qquad \{x\in U:s<\tau(x)\}\cap S\subseteq D(B).(3)✦

Global Lists and Priorities

An indexed global set family ℒ=(I,(Li)i∈ℕ)\mathcal L=(I,(L_i)_{i\in\mathbb N}) consists of a finite set I⊆ℕI\subseteq\mathbb N of listed indices and a job set LiL_i at every index.✦ For a global family ℒ\mathcal L, a rank ρ:J→ℕ\rho:J\to\mathbb N and a scale M∈ℕM\in\mathbb N, the global qualifier set Q(ℒ)Q(\mathcal L), the membership index set IxI_x of a job xx, the last membership index ℓℒ(x)\ell_{\mathcal L}(x) and the numeric priority assignment kℒk_{\mathcal L} are the sets, index and assignment given in (4). Lexicographic list priority x<ℒ,ρyx<_{\mathcal L,\rho}y compares jobs first by their last membership indices and then, when those indices agree, by their ranks, as in (4).✦ Q(ℒ)=⋃i∈ILi,Ix={i∈I:x∈Li},ℓℒ(x)=max⁡(Ix∪{0}),kℒ(x)=Mℓℒ(x)+ρ(x),x<ℒ,ρy⇔(ℓℒ(x),ρ(x))<lex(ℓℒ(y),ρ(y)).\begin{gathered} Q(\mathcal L)=\bigcup_{i\in I}L_i,\qquad I_x=\{i\in I:x\in L_i\},\qquad \ell_{\mathcal L}(x)=\max(I_x\cup\{0\}),\\ k_{\mathcal L}(x)=M\ell_{\mathcal L}(x)+\rho(x),\qquad x<_{\mathcal L,\rho}y\ \Longleftrightarrow\ (\ell_{\mathcal L}(x),\rho(x)) <_{\mathrm{lex}}(\ell_{\mathcal L}(y),\rho(y)). \end{gathered}(4)

A global upset U⊆JU\subseteq J is a job set closed under taking successors.✦ A global family ℒ=(I,(Li)i∈ℕ)\mathcal L=(I,(L_i)_{i\in\mathbb N}) has upward closed entries when each listed LiL_i is a global upset.✦ A global family ℒ\mathcal L has injection entries disjoint within a job set UU when U∩Li∩Lj=⌀U\cap L_i\cap L_j=\varnothing for distinct listed i,j≥2i,j\ge2.✦ The past boundary invariant 𝖯𝖺𝗌𝗍τ(ℒ,B,s)\mathsf{Past}_\tau(\mathcal L,B,s) is the containment in (5).✦ Q(ℒ)∩{x:τ(x)≤s}⊆P¯(B).Q(\mathcal L)\cap\{x:\tau(x)\le s\}\subseteq\overline P(B).(5)✦

For a global family ℒ\mathcal L and a job set U⊆JU\subseteq J, the pruned family ℒ|U\mathcal L|_U is the global family that retains exactly the indices whose entries meet UU, leaving the global entries unchanged.✦ For a global family ℒ\mathcal L, a rank ρ\rho, an index dd and a rank threshold rr, the suffix carry⁡(ℒ,ρ,d,r)\operatorname{carry}(\mathcal L,\rho,d,r) is the global family obtained by discarding indices below dd, restricting the entry at dd to {x:r≤ρ(x)}\{x:r\le\rho(x)\}, and retaining entries above dd.✦ For a global family ℒ\mathcal L, rank ρ\rho, scale MM, sets D,P⊆JD,P\subseteq J and a nonnegative integer threshold tt, the unchanged-direction update 𝒰t(ℒ;ρ,M,D,P)\mathcal U_t(\mathcal L;\rho,M,D,P) is the family in (6).✦ For an indexed global set family ℒ\mathcal L on JJ and a job set F⊆JF\subseteq J, the appended global family is the family obtained by placing FF after the existing entries of ℒ\mathcal L.✦ 𝒰t(ℒ;ρ,M,D,P)=append⁡(carry(ℒ,ρ,⌊t/M⌋,tmod⁡M),D\P).\mathcal U_t(\mathcal L;\rho,M,D,P) =\operatorname{append}\!\left( \operatorname{carry}(\mathcal L,\rho,\lfloor t/M\rfloor,t\bmod M), D\setminus P\right).(6)✦

The same-list priority πℒ,ρ,M,Psame\pi^{\mathrm{same}}_{\mathcal L,\rho,M,P} is the natural-number priority assignment specified by a global family, rank, scale and distinguished job set PP. The direction-change priority πρ,M,Dswitch\pi^{\mathrm{switch}}_{\rho,M,D} is the natural-number priority assignment specified by a rank, scale and distinguished job set DD. For a priority assignment π\pi, a rank ρ\rho and a threshold kk, the priority cut Cπ(k)C_\pi(k) and the rank upper tail Rρ(k)R_\rho(k) are the job sets in (7). Cπ(k)={x:π(x)<k},Rρ(k)={x:k≤ρ(x)}.C_\pi(k)=\{x:\pi(x)<k\},\qquad R_\rho(k)=\{x:k\le\rho(x)\}.(7)

For layouts p,qp,q and a job set U⊆JU\subseteq J, qq is unchanged outside UU relative to pp when q(x)=p(x)q(x)=p(x) for every x∉Ux\notin U.✦ For a layout pp and a priority assignment π\pi, the priority signature of pp under π\pi is the sequence π(p−1(0)),…,π(p−1(N−1))\pi(p^{-1}(0)),\ldots,\pi(p^{-1}(N-1)).✦ A layout pp is locally normalized on a job set UU under a priority assignment π\pi when it respects precedence and its priority signature under π\pi is lexicographically no greater than that of every precedence-respecting layout unchanged outside UU relative to pp.✦

For a layout qq and jobs x,yx,y, the exchange qxyq^{xy} is the layout obtained by interchanging the positions of x,yx,y in qq.✦ The forbidden exchange invariant 𝖲𝗐𝖺𝗉(p,U,ℒ,ρ,B,s)\mathsf{Swap}(p,U,\mathcal L,\rho,B,s) requires that, for every precedence-respecting qq unchanged outside UU relative to pp, exchanging x∈U\D(B)x\in U\setminus D(B) with y∈Q(ℒ)y\in Q(\mathcal L) at slot ss fails precedence feasibility whenever x<ℒ,ρyx<_{\mathcal L,\rho}y.✦

Cutoff Walks

A relative order ideal UU on a finite job set EE is a set such that x,y∈Ex,y\in E, x≺yx\prec y, and y∈Uy\in U imply x∈Ux\in U.✦ A priority prefix UU on EE under π\pi is a set such that π(x)<π(y)\pi(x)<\pi(y) whenever x∈E∩Ux\in E\cap U and y∈E\Uy\in E\setminus U.✦

The local priority obstruction condition 𝖮𝖻𝗌(E,τ,π)\mathsf{Obs}(E,\tau,\pi) requires that whenever x,y∈Ex,y\in E satisfy τ(y)<τ(x)\tau(y)<\tau(x) and π(x)<π(y)\pi(x)<\pi(y), and every predecessor of xx in EE is earlier than yy, there is a successor zz of yy in EE with τ(z)≤τ(x)\tau(z)\le\tau(x).✦

The cutoff descendants at slot ss form the set DsD_s in (8).✦ An earliest exceptional job for E,U,sE,U,s is a job x∈E∩Ux\in E\cap U with s<τ(x)s<\tau(x) and x∉Dsx\notin D_s, such that every y∈E∩Uy\in E\cap U with s<τ(y)<τ(x)s<\tau(y)<\tau(x) belongs to DsD_s.✦ Ds={x∈J:∃y∈J,τ(y)=s and y≺x}.D_s=\{x\in J:\exists y\in J,\ \tau(y)=s\text{ and }y\prec x\}.(8)✦

A cutoff walk 𝖶𝖺𝗅𝗄(E,τ,π,S;a,a′)\mathsf{Walk}(E,\tau,\pi,S;a,a') is a finite sequence of cutoffs from aa to a′a', possibly of length zero, whose steps have the following form. At cutoff ss, choose a relative order ideal and priority prefix UU on EE with E∩U⊆SE\cap U\subseteq S, choose an earliest exceptional job xx for E,U,sE,U,s, and make τ(x)\tau(x) the next cutoff.

Structural Certificates

A Boolean structural formula φ\varphi over an atomic family 𝒜\mathcal A of job sets is an expression consisting of an atom or its complement, or a conjunction or disjunction of two Boolean structural formulas.✦ The interpretation FF of a Boolean structural formula φ\varphi over an atomic family 𝒜\mathcal A of job sets is the job set obtained by replacing conjunction and disjunction by intersection and union.✦ A leaf contributes one to the leaf count; either binary operation adds its two counts.✦ A job set FF has a description over an atomic family 𝒜\mathcal A with allowance kk if it is the interpretation of a Boolean structural formula over 𝒜\mathcal A with at most kk leaves; the fixed allowance is K=10000K=10000.✦

The family 𝒜\mathcal A has atomic predicate expressiveness for ≺,ρ\prec,\rho when JJ, ⌀\varnothing, every rank upper tail, every strict or weak boundary cone, and every job triple have descriptions with at most one leaf.✦ For a boundary LL at slot aa and a scheduling window WW, a switch seed FF at L,a,WL,a,W is a global upset described with at most 2424 leaves such that W\D(L)⊆FW\setminus D(L)\subseteq F and every job in FF is later than aa.✦

A rank threshold run certificate Γ\Gamma for ℒ,ρ,𝒜,W\mathcal L,\rho,\mathcal A,W is a collection of base sets UiU_i, thresholds kik_i and a second set S2S_2 satisfying (9). Every listed nonzero base has a description with at most two leaves, U0U_0 has one with at most 2424, and S2S_2 has one with at most one. Li=Ui∩Rρ(ki)(i∈I),U1=S2,W\S2⊆U0,x∈W∩S2,0∈I⇒1∈I and x∈L1.\begin{gathered} L_i=U_i\cap R_\rho(k_i)\quad(i\in I),\qquad U_1=S_2, \qquad W\setminus S_2\subseteq U_0,\\ x\in W\cap S_2,\ 0\in I\quad\Longrightarrow\quad 1\in I\text{ and }x\in L_1. \end{gathered}(9)

An edge structural certificate in 𝔈(r,ρ,𝒜;p,W,a,b,v,a′,b′,R,V,A′,B′)\mathfrak E(r,\rho,\mathcal A;p,W,a,b,v,a',b',R,V,A',B'), where rr denotes ≺\prec, has a full layout pp, parent W=(a,b)W=(a,b), and boundaries R,V,A′,B′R,V,A',B' at b,v,a′,b′b,v,a',b', respectively. Its target B′B' is actual, and a≤a′<b′≤v<ba\le a'<b'\le v<b. An edge structural certificate ℰ∈𝔈(r,ρ,𝒜;p,W,a,b,v,a′,b′,R,V,A′,B′)\mathcal E\in\mathfrak E(r,\rho,\mathcal A;p,W,a,b,v,a',b',R,V,A',B') is a collection of cutoff sets C,SC,S, a global family ℒ\mathcal L with a rank threshold run certificate, and global sets G,HG,H with the conditions in (10). The final cutoff SS has a one-leaf description. All listed entries and the run’s second set are global upsets, and the injection entries are disjoint within WW. The set GG has a description with at most 205205 leaves; HH has one with at most 2121 and is closed under taking predecessors. 𝖲𝖾𝗉(V,W,S;v),𝖲𝖾𝗉(A′,(a,v),C;a′),𝖲𝖾𝗉(B′,(a,v),C;b′),W∩C⊆P(R)∩S,W∩Q(ℒ)=W\C,𝖯𝖺𝗌𝗍τp(ℒ,A′,a′),𝖲𝗐𝖺𝗉(p,(a′,b′),ℒ,ρ,A′,a′),W∩G=W∩H=W∩C.\begin{gathered} \mathsf{Sep}(V,W,S;v),\qquad \mathsf{Sep}(A',(a,v),C;a'),\qquad \mathsf{Sep}(B',(a,v),C;b'),\\ W\cap C\subseteq P(R)\cap S,\qquad W\cap Q(\mathcal L)=W\setminus C,\\ \mathsf{Past}_{\tau_p}(\mathcal L,A',a'),\qquad \mathsf{Swap}(p,(a',b'),\mathcal L,\rho,A',a'),\\ W\cap G=W\cap H=W\cap C. \end{gathered}(10)

The Claim

Theorem 1. For the unchanged-direction assertion (11), let pp be full for a transitive precedence relation, with A,A′A,A' at a,a′a,a'. Let W=(a,b)W=(a,b) and E=(a,v)E=(a,v), where v<bv<b, a≤Ta\le T, and a′<va'<v. Suppose M>0M>0, ρ(x)<M\rho(x)<M for all jobs, and ρ\rho strictly increases along precedence. Let ℒ\mathcal L have upward closed entries, with W∩Q(ℒ)⊆P(Z)W\cap Q(\mathcal L)\subseteq P(Z) and W\Q(ℒ)⊆D(A)W\setminus Q(\mathcal L)\subseteq D(A) for a boundary ZZ. Assume 𝖯𝖺𝗌𝗍τp(ℒ,A,a)\mathsf{Past}_{\tau_p}(\mathcal L,A,a) and 𝖲𝗐𝖺𝗉(p,W,ℒ,ρ,A,a)\mathsf{Swap}(p,W,\mathcal L,\rho,A,a). Put m=max⁡(I∪{0})m=\max(I\cup\{0\}), take t≤(m+1)Mt\le(m+1)M, and set π=πℒ,ρ,M,P(Z)same\pi=\pi^{\mathrm{same}}_{\mathcal L,\rho,M,P(Z)} and S=Cπ(M+t)S=C_\pi(M+t). Suppose 𝖮𝖻𝗌(E,τp,π)\mathsf{Obs}(E,\tau_p,\pi), 𝖲𝖾𝗉(A′,E,S;a′)\mathsf{Sep}(A',E,S;a'), and 𝖶𝖺𝗅𝗄(E,τp,π,S;a,a′)\mathsf{Walk}(E,\tau_p,\pi,S;a,a'). Then $$\mathsf{Past}_{\tau_p}\!left( \mathcal U_t(\mathcal L;\rho,M,D(A),P(Z)),A',a'\right).$$(11)✦

For the general update assertion (12), let pp be full for a transitive precedence relation, A,A′A,A' be at a,a′a,a', and E=(a,v)E=(a,v), with a≤Ta\le T and a′<va'<v. Let ℒ,ℒ′\mathcal L,\mathcal L' be global families, let S,H⊆JS,H\subseteq J, and let π\pi be a priority assignment. Assume 𝖯𝖺𝗌𝗍τp(ℒ,A,a)\mathsf{Past}_{\tau_p}(\mathcal L,A,a), with HH a global upset contained in Q(ℒ)Q(\mathcal L). Every qualifier of ℒ′\mathcal L' at or before aa must belong to HH, and both E∩Q(ℒ′)E\cap Q(\mathcal L') and E∩HE\cap H must be disjoint from SS. Assume 𝖲𝖾𝗉(A′,E,S;a′)\mathsf{Sep}(A',E,S;a'), 𝖮𝖻𝗌(E,τp,π)\mathsf{Obs}(E,\tau_p,\pi), and 𝖶𝖺𝗅𝗄(E,τp,π,S;a,a′)\mathsf{Walk}(E,\tau_p,\pi,S;a,a'). Finally, suppose that whenever UU is a relative order ideal and priority prefix on EE with E∩U⊆SE\cap U\subseteq S, xx is an earliest exceptional job for E,U,aE,U,a, and y∈Hy\in H is at slot aa, there is u∈Eu\in E with y≺uy\prec u and τp(u)≤τp(x)\tau_p(u)\le\tau_p(x). Then 𝖯𝖺𝗌𝗍τp(ℒ′,A′,a′).\mathsf{Past}_{\tau_p}(\mathcal L',A',a').(12)✦

Let τ\tau be any slot assignment and let ℒ,A,a\mathcal L,A,a satisfy 𝖯𝖺𝗌𝗍τ(ℒ,A,a)\mathsf{Past}_\tau(\mathcal L,A,a). For every job set UU, 𝖯𝖺𝗌𝗍τ(ℒ|U,A,a).\mathsf{Past}_\tau(\mathcal L|_U,A,a).(13)✦

For the direction-change assertion (14), let pp be full for a transitive precedence relation. Suppose 𝒜\mathcal A has atomic predicate expressiveness, ρ(x)<M\rho(x)<M for every job, and ρ\rho strictly increases along precedence. Let W=(a,b)W=(a,b), with L,RL,R at a,ba,b and W⊆D(L)∪P(R)W\subseteq D(L)\cup P(R), and assume a switch seed at L,a,WL,a,W exists. Choose a<v<ba<v<b and a boundary VV at vv with 𝖲𝖾𝗉(V,W,J\D(L);v)\mathsf{Sep}(V,W,J\setminus D(L);v). Let a≤a′<b′≤va\le a'<b'\le v, with A′,B′A',B' at a′,b′a',b' and B′B' actual. Take t≤Mt\le M and put π=πρ,M,D(L)switch\pi=\pi^{\mathrm{switch}}_{\rho,M,D(L)}. Suppose pp is locally normalized on (a,v)(a,v) under π\pi, and both 𝖲𝖾𝗉(A′,(a,v),Cπ(t);a′)\mathsf{Sep}(A',(a,v),C_\pi(t);a') and 𝖲𝖾𝗉(B′,(a,v),Cπ(t);b′)\mathsf{Sep}(B',(a,v),C_\pi(t);b') hold. Then ∃ℰ∈𝔈(r,ρ,𝒜;p,W,a,b,v,a′,b′,R,V,A′,B′).\exists\mathcal E\in \mathfrak E(r,\rho,\mathcal A;p,W,a,b,v,a',b',R,V,A',B').(14)✦

In the paper, the result reads: the updated child list satisfies the invariant that every global qualifier scheduled at or before its left boundary belongs to that boundary’s weak predecessor cone.

What Is Checked

The assertions are stated over finite job layouts and global set families, with boundary separation and cutoff walks for updates, rank and bounded-description conditions for direction changes, and arbitrary slot assignments for pruning.