OctoInformBeta

OpenAI preprint, September 2026 · §6. Short global lists and changes of direction

Lemma 6.7: Global switch sets and reverse induction seeds between separated scheduling windows

Cutoffs for a change of direction.

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 change of direction in a scheduling recursion requires a cutoff for the next child window. The cutoff is a set of jobs defined on the whole schedule, even when its coverage condition concerns only that child.

Let JJ be the job set, rr its precedence relation, and τ:J→ℕ\tau:J\to\mathbb N a working slot assignment with deadline TT. A job triple Z⊆JZ\subseteq J is a set of three jobs.✦ A scheduling triple boundary BB for the job set JJ is a left endpoint, an actual job triple, or a right endpoint.✦ A boundary BsB_s has time ss when the left endpoint has s=0s=0, the right endpoint has s=T+1s=T+1, or an actual triple ZZ has 1≤s≤T1\le s\le T and consists exactly of the jobs assigned to slot ss.✦

For boundary slots a<ba<b, the open scheduling window (a,b)(a,b) is the job set in (1): (a,b)={x∈J:a<τ(x)<b}.(a,b)=\{x\in J:a<\tau(x)<b\}.(1)✦

The strict predecessor and successor cones of a boundary BB are the sets P(B)P(B) and D(B)D(B) in (2); their weak versions P¯(B)\overline P(B) and D¯(B)\overline D(B) include the actual boundary triple. Write Ps,Ds,P¯s,D¯sP_s,D_s,\overline P_s,\overline D_s for the cones of BsB_s. BP(B)D(B)P¯(B)D¯(B)left⌀J⌀JZ{x:∃z∈Z,xrz}{x:∃z∈Z,zrx}P(Z)∪ZD(Z)∪ZrightJ⌀J⌀\begin{array}{c|cccc} B&P(B)&D(B)&\overline P(B)&\overline D(B)\\ \hline \mathrm{left}&\varnothing&J&\varnothing&J\\ Z&\{x:\exists z\in Z,\ xrz\}&\{x:\exists z\in Z,\ zrx\} &P(Z)\cup Z&D(Z)\cup Z\\ \mathrm{right}&J&\varnothing&J&\varnothing \end{array}(2)

A boundary BsB_s separates job sets X,S⊆JX,S\subseteq J when the two inclusions in (3) hold; denote this condition by Sep⁡(Bs;X,S)\operatorname{Sep}(B_s;X,S).✦ (X∩{x:τ(x)<s})\S⊆Ps,X∩{x:s<τ(x)}∩S⊆Ds.\bigl(X\cap\{x:\tau(x)<s\}\bigr)\setminus S\subseteq P_s, \qquad X\cap\{x:s<\tau(x)\}\cap S\subseteq D_s.(3)

A global upset FF for rr is a subset of JJ containing every successor of each of its jobs.✦ A global downset FF for rr is a subset of JJ containing every predecessor of each of its jobs; equivalently, it is a global upset for the reversed precedence ropr^{\mathrm{op}}, where xropyx r^{\mathrm{op}} y means yrxyrx.

Descriptions and Seeds

A Boolean structural formula pp over an index set II is a leaf carrying an index i∈Ii\in I and a positive or negative sign, or a conjunction or disjunction of two such formulas.✦ The interpretation ⟦p⟧𝒜\llbracket p\rrbracket_{\mathcal A} of a Boolean structural formula pp for an atomic family 𝒜=(Ai)i∈I\mathcal A=(A_i)_{i\in I} of subsets of JJ is the subset of JJ obtained by assigning AiA_i to a positive leaf and AicA_i^c to a negative leaf, and interpreting conjunction and disjunction as intersection and union.✦ The leaf count λ(p)\lambda(p) of a Boolean structural formula pp is the number of its leaves, given recursively by one at a leaf and the sum of the two counts at either binary operation.✦ The family ℬk\mathcal B_k of job sets with a bounded Boolean description of allowance kk is defined by (4).✦ ℬk={F⊆J:∃p,⟦p⟧𝒜=Fandλ(p)≤k}.\mathcal B_k=\{F\subseteq J:\exists p,\quad \llbracket p\rrbracket_{\mathcal A}=F\ \text{and}\ \lambda(p)\le k\}.(4)

A reverse induction seed for a window XX, a boundary BsB_s, and its slot ss is a global downset Q⊆JQ\subseteq J satisfying (5).✦ Denote the family of these seeds by ℛ(X,Bs,s)\mathcal R(X,B_s,s). Q∈ℬ24,X\Ps⊆Q⊆{x∈J:τ(x)<s}.Q\in\mathcal B_{24},\qquad X\setminus P_s\subseteq Q\subseteq\{x\in J:\tau(x)<s\}.(5)

The switch set GG associated with boundaries Ba−,Ba,Bv−B_{a_-},B_a,B_{v_-} and a job set Hext⊆JH^{\mathrm{ext}}\subseteq J is the intersection in (6).✦ G=Da−∩(P¯a)c∩(P¯v−)c∩Hext.G=D_{a_-}\cap(\overline P_a)^c\cap(\overline P_{v_-})^c \cap H^{\mathrm{ext}}.(6)

The Claim

Theorem 1. For transitive rr and a global upset HextH^{\mathrm{ext}}, the switch set has the property (7), for arbitrary scheduling triple boundaries: G is a global upset for r.G\text{ is a global upset for }r.(7)✦

For the assertion (9), let U=(a−,b−)U=(a_-,b_-) and W=(a,b)W=(a,b), with a−<v−≤a<b≤b−a_-<v_-\le a<b\le b_-, and let Ba−,Ba,Bv−B_{a_-},B_a,B_{v_-} be boundaries at their indicated slots. Suppose rr respects τ\tau, all job times lie between 11 and TT, and H,H⋆,Hext⊆JH,H^\star,H^{\mathrm{ext}}\subseteq J satisfy U∩Hext=U∩H,U∩H⊆H⋆∩Da−,W\H⊆Da,Sep⁡(Bv−;U,(H⋆)c),Sep⁡(Ba;(v−,b−),Hc).\begin{gathered} U\cap H^{\mathrm{ext}}=U\cap H,\qquad U\cap H\subseteq H^\star\cap D_{a_-},\qquad W\setminus H\subseteq D_a,\\ \operatorname{Sep}(B_{v_-};U,(H^\star)^c),\qquad \operatorname{Sep}(B_a;(v_-,b_-),H^c). \end{gathered}(8) Under the conditions in (8), W\Da⊆G,G⊆{x∈J:a<τ(x)}.W\setminus D_a\subseteq G, \qquad G\subseteq\{x\in J:a<\tau(x)\}.(9)✦

For the assertion (11), let W0=(a,b)W_0=(a,b), E=(a,v)E=(a,v), and W′=(a′,b′)W'=(a',b'), with a≤a′<b′≤v<ba\le a'<b'\le v<b, and let Bb,Bb′,BvB_b,B_{b'},B_v be boundaries at their indicated slots. Suppose rr is transitive and respects τ\tau, and all job times lie between 11 and TT. Let S,S⋆,Hext⊆JS,S^\star,H^{\mathrm{ext}}\subseteq J, with HextH^{\mathrm{ext}} a global downset, and assume the conditions in (10): W′\S⊆Pb′,W0∩S⊆Pb∩S⋆,W0∩Hext=W0∩S,Sep⁡(Bv;W0,S⋆),Sep⁡(Bb′;E,S),Hext∈ℬ21,Pb,D¯b′,D¯v∈ℬ1.\begin{gathered} W'\setminus S\subseteq P_{b'},\qquad W_0\cap S\subseteq P_b\cap S^\star,\qquad W_0\cap H^{\mathrm{ext}}=W_0\cap S,\\ \operatorname{Sep}(B_v;W_0,S^\star),\qquad \operatorname{Sep}(B_{b'};E,S),\\ H^{\mathrm{ext}}\in\mathcal B_{21},\qquad P_b,\overline D_{b'},\overline D_v\in\mathcal B_1. \end{gathered}(10) Then ℛ(W′,Bb′,b′)≠⌀.\mathcal R(W',B_{b'},b')\ne\varnothing.(11)✦

In the paper, the result reads: for a nonempty switched child W=(a,b)W=(a,b) with preceding parent U=(a−,b−)U=(a_-,b_-) and current-frame arrangement a−<v−≤a<b≤b−a_-<v_-\le a<b\le b_-, the preceding low cutoff’s extension H−*H_-^* gives a global upset G=Da−∩(P¯a)c∩(P¯v−)c∩H−*G=D_{a_-}\cap(\overline P_a)^c\cap(\overline P_{v_-})^c\cap H_-^* that covers W\DaW\setminus D_a and contains no job scheduled at or before aa.

What Is Checked

The claims are stated over precedence relations and slot assignments on JJ, using scheduling triple boundaries with their cone and separation conditions and the bounded Boolean descriptions in (4).