OctoInformBeta

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

Lemma 7.2

Exchange constraints persist in child windows.

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 child scheduling interval may later have all its jobs reordered. The exchange condition concerns a job inside that interval and a job on its left boundary, with the comparison determined by a global list of job sets.

Let JJ be a finite job set of size NN, with precedence relation rr, written x≺yx\prec y. A layout pp is a bijection from JJ to its zero-based positions.✦ Its jobs are read in consecutive triples, with slot map given by (1). τp(x)=⌊p(x)3⌋+1.\tau_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(1)✦ A feasible layout pp of JJ is a layout in which x≺yx\prec y requires τp(x)<τp(y)\tau_p(x)<\tau_p(y). A full schedule is a feasible layout with |J|=N=3T|J|=N=3T, where TT is its deadline.✦ For layouts p,qp,q and a job set U⊆JU\subseteq J, write p∼Uqp\sim_U q when every job outside UU has the same position in both layouts.✦ The exchange qxyq^{xy} interchanges the positions of xx and yy and leaves all other positions fixed.✦ The open window W=(a,b)W=(a,b) is the set of jobs xx with a<τp(x)<ba<\tau_p(x)<b.✦

A job triple ZZ of JJ is a three-element subset of JJ.✦ A boundary is a left endpoint ⊥\bot, an actual triple ZZ, or a right endpoint ⊤\top.✦ For a full schedule, these boundaries occur at slots 00, ss, and T+1T+1, respectively; an actual triple occurs at ss when 1≤s≤T1\leq s\leq T and Z={x:τp(x)=s}Z=\{x:\tau_p(x)=s\}.✦ The strict predecessor and successor cones are the sets in (2). PZ={x:some z∈Z satisfies x≺z},DZ={x:some z∈Z satisfies z≺x},P⊥=⌀,D⊥=J,P⊤=J,D⊤=⌀.\begin{aligned} P_Z&=\{x:\text{some }z\in Z\text{ satisfies }x\prec z\},& D_Z&=\{x:\text{some }z\in Z\text{ satisfies }z\prec x\},\\ P_{\bot}&=\varnothing,&D_{\bot}&=J,\\ P_{\top}&=J,&D_{\top}&=\varnothing. \end{aligned}(2) The weak cones P¯Z\overline P_Z and D¯Z\overline D_Z include ZZ itself; at endpoints the weak and strict cones agree.

For job sets U,C⊆JU,C\subseteq J, a separating boundary AA for UU by CC at slot ss in layout pp is a boundary such that every job of U\CU\setminus C earlier than ss belongs to PAP_A, and every job of U∩CU\cap C later than ss belongs to DAD_A.✦ Write this condition as Sep⁡p(A;U,C,s)\operatorname{Sep}_p(A;U,C,s).

Lists and Local Normalization

An indexed global set family ℒ=(I,(Li)i∈ℕ)\mathcal L=(I,(L_i)_{i\in\mathbb N}) consists of a finite index set I⊆ℕI\subseteq\mathbb N and job sets Li⊆JL_i\subseteq J.✦ The membership indices of xx are the listed indices containing xx; their maximum, with default zero, is its last membership index mℒ(x)m_{\mathcal L}(x). The global entry union QℒQ_{\mathcal L}, lexicographic list priority <ℒ,ρ<_{\mathcal L,\rho} for a rank ρ:J→ℕ\rho:J\to\mathbb N, and numeric priority key hℒ,ρ,Bh_{\mathcal L,\rho,B} for a scale BB are defined by (3). Qℒ=⋃i∈ILi,x<ℒ,ρy⇔(mℒ(x),ρ(x))<lex(mℒ(y),ρ(y)),hℒ,ρ,B(x)=Bmℒ(x)+ρ(x).\begin{aligned} Q_{\mathcal L}&=\bigcup_{i\in I}L_i,\\ x<_{\mathcal L,\rho}y &\quad\Longleftrightarrow\quad (m_{\mathcal L}(x),\rho(x)) <_{\mathrm{lex}}(m_{\mathcal L}(y),\rho(y)),\\ h_{\mathcal L,\rho,B}(x)&=B\,m_{\mathcal L}(x)+\rho(x). \end{aligned}(3) The pruned list ℒ|U\mathcal L|_U of a global set family ℒ\mathcal L is the indexed set family that retains exactly those indices i∈Ii\in I for which Li∩U≠⌀L_i\cap U\ne\varnothing and keeps every global entry unchanged.

The signature of a natural-number priority π\pi in a layout pp is the sequence of priorities in position order.✦ A locally normalized layout pp on a job set UU for priority π\pi is a feasible layout whose signature satisfies (4) for every feasible qq with p∼Uqp\sim_U q. (π(p−1(0)),…,π(p−1(N−1)))≤lex(π(q−1(0)),…,π(q−1(N−1))).\bigl(\pi(p^{-1}(0)),\ldots,\pi(p^{-1}(N-1))\bigr) \leq_{\mathrm{lex}} \bigl(\pi(q^{-1}(0)),\ldots,\pi(q^{-1}(N-1))\bigr).(4)✦ Write Norm⁡r(p,U;π)\operatorname{Norm}_r(p,U;\pi) for this condition. The same-list priority πℒ,ρ,B,P=\pi^{=}_{\mathcal L,\rho,B,P} is the natural-number assignment specified by ℒ\mathcal L, rank ρ\rho, scale BB, and distinguished set PP. The direction-change priority πρ,B,Dsw\pi^{\mathrm{sw}}_{\rho,B,D} is the natural-number assignment specified by ρ\rho, BB, and a distinguished set DD.

For a natural-number threshold kk, the priority cut Cπ(k)C_\pi(k) and rank upper tail Rρ(k)R_\rho(k) are the sets in (5). Cπ(k)={x:π(x)<k},Rρ(k)={x:k≤ρ(x)}.C_\pi(k)=\{x:\pi(x)<k\},\qquad R_\rho(k)=\{x:k\leq\rho(x)\}.(5)

The exchange invariant 𝖲rρ(p,U,ℒ;A,s)\mathsf S_r^\rho(p,U,\mathcal L;A,s) is the following condition on a layout, a job set, a global list, and a boundary: for every feasible qq with p∼Uqp\sim_U q, jobs x∈U\DAx\in U\setminus D_A and y∈Qℒy\in Q_{\mathcal L} with τq(y)=s\tau_q(y)=s and x<ℒ,ρyx<_{\mathcal L,\rho}y have an infeasible exchange qxyq^{xy}.✦ The past boundary invariant 𝖯𝖺𝗌𝗍r(p,ℒ;A,s)\mathsf{Past}_r(p,\mathcal L;A,s) requires every job of QℒQ_{\mathcal L} scheduled at or before ss to belong to P¯A\overline P_A.✦

Descriptions and Structural Certificates

A Boolean structural formula φ\varphi over an atomic family 𝒜\mathcal A of job sets is a signed atom or a conjunction or disjunction of two formulas.✦ The interpretation ⟦φ⟧𝒜\llbracket\varphi\rrbracket_{\mathcal A} of a Boolean structural formula φ\varphi over an atomic family 𝒜\mathcal A is the job set obtained by assigning an atom its job set, a negative atom its complement, and conjunction and disjunction intersection and union.✦ The leaf count ℓ(φ)\ell(\varphi) of a Boolean structural formula φ\varphi is the natural number that is one at an atom and adds across either binary operation.✦ A bounded description of a job set FF over an atomic family 𝒜\mathcal A with allowance kk, denoted 𝒜⊨kF\mathcal A\models_k F, is the condition in (6). 𝒜⊨kF⇔there is a formula φ with ⟦φ⟧𝒜=F and ℓ(φ)≤k.\mathcal A\models_k F \quad\Longleftrightarrow\quad \text{there is a formula }\varphi\text{ with } \llbracket\varphi\rrbracket_{\mathcal A}=F \text{ and }\ell(\varphi)\leq k.(6) A relative description of U⊆WU\subseteq W is an equality U=W∩FU=W\cap F with FF globally described. The fixed description allowance is K=10000K=10000. Atomic predicate expressiveness means that JJ, ⌀\varnothing, every rank upper tail, every strict or weak boundary cone, and every job triple each have a description with one leaf.✦

An upward-closed job set contains every successor of each of its jobs; a downward-closed set contains every predecessor.✦ A list has upward-closed entries when every listed entry is upward closed.✦ The injection entries of a global list ℒ\mathcal L are disjoint in WW when W∩Li∩Lj=⌀W\cap L_i\cap L_j=\varnothing for distinct listed i,j≥2i,j\geq2.✦ A rank threshold run certificate for ℒ\mathcal L on WW consists of base sets UiU_i, thresholds kik_i, and a second set Σ\Sigma, with the factorization in (7). Li=Ui∩Rρ(ki)(i∈I),U1=Σ.L_i=U_i\cap R_\rho(k_i)\quad(i\in I),\qquad U_1=\Sigma.(7) Every listed nonzero base has a description with at most two leaves; U0U_0 has one with at most 2424 leaves and Σ\Sigma one with at most one. The certificate also requires W\Σ⊆U0W\setminus\Sigma\subseteq U_0 and, whenever 0∈I0\in I and x∈W∩Σx\in W\cap\Sigma, requires 1∈I1\in I and x∈L1x\in L_1.

A reverse induction seed Q−Q_- for WW at a right boundary RR and slot bb is a downward-closed set with a description of at most 2424 leaves, containing W\PRW\setminus P_R, all of whose jobs occur before bb.✦ A switch seed Q+Q_+ for WW at a left boundary LL and slot aa is an upward-closed set with a description of at most 2424 leaves, containing W\DLW\setminus D_L, all of whose jobs occur after aa.✦

A node structural certificate 𝒩\mathcal N for pp and W=(a,b)W=(a,b) consists of a full schedule, boundaries L,RL,R at a,ba,b, and a global list ℒ\mathcal L with a rank threshold run certificate on WW. Its listed entries and second set are upward closed, its injection entries are disjoint in WW, and |I|≤5|I|\leq5. Its confinement conditions are (8). W∩Qℒ⊆PR,W\Qℒ⊆DL.W\cap Q_{\mathcal L}\subseteq P_R,\qquad W\setminus Q_{\mathcal L}\subseteq D_L.(8) It requires 𝖯𝖺𝗌𝗍r(p,ℒ;L,a)\mathsf{Past}_r(p,\mathcal L;L,a) and 𝖲rρ(p,W,ℒ;L,a)\mathsf S_r^\rho(p,W,\mathcal L;L,a), a description of WW with at most 406406 leaves, and a reverse induction seed at R,bR,b.

An edge structural certificate belongs to the collection ℰ(p,W;a,b,v,a′,b′;R,V,A′,B′)\mathscr E(p,W;a,b,v,a',b';R,V,A',B') when pp is full, W=(a,b)W=(a,b), the boundaries R,V,A′,B′R,V,A',B' occur at b,v,a′,b′b,v,a',b', and B′B' is an actual triple, with the inequalities in (9). a≤a′<b′≤v<b.a\leq a'<b'\leq v<b.(9) It has cutoff sets C,SC,S, with 𝒜⊨1S\mathcal A\models_1 S, such that Sep⁡p(V;W,S,v)\operatorname{Sep}_p(V;W,S,v) holds and both A′A' and B′B' separate (a,v)(a,v) by CC at their respective slots. The certificate contains a global list ℋ\mathcal H with a rank threshold run certificate on WW, upward-closed entries and second set, and injection entries disjoint in WW. Its cutoff coverage and labels satisfy (10). W∩C⊆PR∩S,W∩Qℋ=W\C.W\cap C\subseteq P_R\cap S,\qquad W\cap Q_{\mathcal H}=W\setminus C.(10) It also requires 𝖯𝖺𝗌𝗍r(p,ℋ;A′,a′)\mathsf{Past}_r(p,\mathcal H;A',a') and 𝖲rρ(p,(a′,b′),ℋ;A′,a′)\mathsf S_r^\rho(p,(a',b'),\mathcal H;A',a'). A global cutoff FF with at most 205205 description leaves and a downward-closed extension HH with at most 2121 description leaves satisfy W∩F=W∩C=W∩HW\cap F=W\cap C=W\cap H.

Exception Cutoff Walks

The cutoff descendants at slot ss form the set Δs\Delta_s in (11). Δs={x:some y satisfies τp(y)=s and y≺x}.\Delta_s=\{x:\text{some }y\text{ satisfies }\tau_p(y)=s \text{ and }y\prec x\}.(11)✦ An earliest exceptional job xx for a finite window EE, a low set UU, and cutoff ss is a job satisfying x∈E∩U\Δsx\in E\cap U\setminus\Delta_s later than ss such that every y∈E∩Uy\in E\cap U strictly between slots ss and τp(x)\tau_p(x) belongs to Δs\Delta_s. A relative order ideal UU on a finite window EE is a job set that contains each predecessor in EE of every job in E∩UE\cap U.✦ A priority prefix UU on a finite window EE for priority π\pi is a job set satisfying π(x)<π(y)\pi(x)<\pi(y) for every x∈E∩Ux\in E\cap U and y∈E\Uy\in E\setminus U.✦ An exception cutoff walk on a finite window EE from aa to a′a' for priority π\pi and final set CC is a finite sequence of cutoffs beginning at aa and ending at a′a'. Each step chooses an order ideal UU on EE that is a priority prefix, with E∩U⊆CE\cap U\subseteq C, and moves to the slot of an earliest exceptional job for UU at the current cutoff. A walk of zero steps is allowed.

The Claim

Theorem 1. Let pp be a layout of a finite job set with precedence rr and rank ρ\rho.

Suppose E=(u,w)E=(u,w) and W′=(a′,b′)W'=(a',b'), with u<a′<b′≤wu<a'<b'\leq w. Let pp be locally normalized on EE for priority π\pi. Suppose W′\DA′⊆QℒW'\setminus D_{A'}\subseteq Q_{\mathcal L} and that, for x∈W′∩Qℒx\in W'\cap Q_{\mathcal L} and y∈Qℒy\in Q_{\mathcal L} at slot a′a' in pp, the comparison x<ℒ,ρyx<_{\mathcal L,\rho}y requires π(x)<π(y)\pi(x)<\pi(y). Then (12) holds. 𝖲rρ(p,W′,ℒ;A′,a′).\mathsf S_r^\rho(p,W',\mathcal L;A',a').(12)✦

Let W,W′⊆JW,W'\subseteq J, and let ℒ′\mathcal L' be an indexed global set family. Suppose 𝖲rρ(p,W,ℒ;A,a)\mathsf S_r^\rho(p,W,\mathcal L;A,a) holds, W′⊆WW'\subseteq W, and Qℒ′⊆QℒQ_{\mathcal L'}\subseteq Q_{\mathcal L}. Assume that for x∈W′\DAx\in W'\setminus D_A and y∈Qℒ′y\in Q_{\mathcal L'}, x<ℒ′,ρyx<_{\mathcal L',\rho}y requires x<ℒ,ρyx<_{\mathcal L,\rho}y. Then (13) holds. 𝖲rρ(p,W′,ℒ′;A,a).\mathsf S_r^\rho(p,W',\mathcal L';A,a).(13)✦

Suppose 𝖲rρ(p,W,ℒ;A,a)\mathsf S_r^\rho(p,W,\mathcal L;A,a) holds. Pruning gives (14). 𝖲rρ(p,W,ℒ|W;A,a).\mathsf S_r^\rho(p,W,\mathcal L|_W;A,a).(14)✦

Let B,t∈ℕB,t\in\mathbb N. Suppose pp is full, rr is transitive, 𝒜\mathcal A has atomic predicate expressiveness, ρ(x)<B\rho(x)<B for every job, and x≺yx\prec y requires ρ(x)<ρ(y)\rho(x)<\rho(y). Let W=(a,b)W=(a,b), E=(a,v)E=(a,v), with a<v<ba<v<b and a≤a′<b′≤va\leq a'<b'\leq v. Let L,R,V,A′,B′L,R,V,A',B' occur at a,b,v,a′,b′a,b,v,a',b', respectively, with B′B' an actual triple.

Suppose a node structural certificate 𝒩\mathcal N has boundaries L,RL,R and list ℒ\mathcal L, and B>0B>0. Let π=πℒ,ρ,B,PR=\pi=\pi^{=}_{\mathcal L,\rho,B,P_R} and C=Cπ(B+t)C=C_\pi(B+t), where t≤(max⁡(I∪{0})+1)Bt\leq(\max(I\cup\{0\})+1)B. Suppose Sep⁡p(V;W,PR,v)\operatorname{Sep}_p(V;W,P_R,v) holds, pp is locally normalized on EE for π\pi, and A′,B′A',B' separate EE by CC at a′,b′a',b'. If there is an exception cutoff walk on EE from aa to a′a' for π\pi and final set CC, then (15) holds. ℰ(p,W;a,b,v,a′,b′;R,V,A′,B′)≠⌀.\mathscr E(p,W;a,b,v,a',b';R,V,A',B')\ne\varnothing.(15)✦

Suppose W⊆DL∪PRW\subseteq D_L\cup P_R and there is a switch seed at L,aL,a. Let π=πρ,B,DLsw\pi=\pi^{\mathrm{sw}}_{\rho,B,D_L} and C=Cπ(t)C=C_\pi(t), with t≤Bt\leq B. Suppose Sep⁡p(V;W,J\DL,v)\operatorname{Sep}_p(V;W,J\setminus D_L,v) holds, pp is locally normalized on EE for π\pi, and A′,B′A',B' separate EE by CC at a′,b′a',b'. Then (16) holds. ℰ(p,W;a,b,v,a′,b′;R,V,A′,B′)≠⌀.\mathscr E(p,W;a,b,v,a',b';R,V,A',B')\ne\varnothing.(16)✦

In the paper, the result reads: the pruned child list satisfies the exchange invariant, quantifying over every feasible reordering of W′W' in its existing slots.

What Is Checked

The assertions concern finite job layouts and global job sets, with local normalization and list comparison hypotheses for exchange preservation, and with transitive precedence, increasing bounded ranks, atomic expressiveness, and the stated boundary and seed conditions for edge certificate existence.