OctoInformBeta

OpenAI preprint, September 2026 · §8. Global interval predicates and completion

Lemma 8.1: Boundary invariants and separation conditions determine the high and low job sets

Interval parts have global cone descriptions.

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

An interval in a three-machine schedule contains the jobs between two boundary slots. A cutoff set divides its jobs into a high part and a low part. Their descriptions involve predecessor and successor cones at boundary triples.

Let JJ be the job set, let rr be its precedence relation, and let τ:J→ℕ\tau:J\to\mathbb N assign slots to jobs, with deadline TT. For boundary slots aa and bb, the open scheduling window W=(a,b)W=(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) A job triple ZZ of JJ is a finite subset of JJ of cardinality three. A scheduling boundary BB for the slot assignment τ\tau is a left endpoint, a job triple, or a right endpoint.✦ The boundary time of a scheduling boundary is 00 at the left endpoint and T+1T+1 at the right endpoint. An actual boundary triple ZsZ_s has boundary time ss when 1≤s≤T1\le s\le T and its jobs are exactly those assigned slot ss.

For a boundary at slot ss, write PsP_s and DsD_s for its strict predecessor and successor cones, and P¯s\overline P_s and D¯s\overline D_s for its weak cones. At an actual boundary triple ZsZ_s, the strict predecessor and successor cones PsP_s and DsD_s and the weak cones P¯s\overline P_s and D¯s\overline D_s are the job sets defined by (2). Ps={x∈J:∃y∈Zs,r(x,y)},Ds={x∈J:∃y∈Zs,r(y,x)},P¯s=Ps∪Zs,D¯s=Ds∪Zs.\begin{aligned} P_s&=\{x\in J:\exists y\in Z_s,\ r(x,y)\},& D_s&=\{x\in J:\exists y\in Z_s,\ r(y,x)\},\\ \overline P_s&=P_s\cup Z_s,& \overline D_s&=D_s\cup Z_s. \end{aligned}(2) At the left endpoint, both predecessor cones are empty and both successor cones are JJ; at the right endpoint, both predecessor cones are JJ and both successor cones are empty.

A boundary at ss separates a job set UU relative to a set E⊆JE\subseteq J when the conditions in (3) hold. ∀x∈U,τ(x)<sandx∉E⇒x∈Ps,∀x∈U,s<τ(x)andx∈E⇒x∈Ds.\begin{aligned} &\forall x\in U,\quad \tau(x)<s\ \text{and}\ x\notin E\ \Longrightarrow\ x\in P_s,\\ &\forall x\in U,\quad s<\tau(x)\ \text{and}\ x\in E\ \Longrightarrow\ x\in D_s. \end{aligned}(3)✦

An indexed global set family 𝒦\mathcal K consists of a finite set I⊆ℕI\subseteq\mathbb N of listed indices and a job set Ki⊆JK_i\subseteq J for every i∈ℕi\in\mathbb N.✦ The qualifier union Q(𝒦)Q(\mathcal K) of an indexed global set family 𝒦\mathcal K is the job set defined in (4). Q(𝒦)=⋃i∈IKi.Q(\mathcal K)=\bigcup_{i\in I}K_i.(4) The past boundary invariant for 𝒦\mathcal K at boundary time aa is the condition in (5). ∀x∈Q(𝒦),τ(x)≤a⇒x∈P¯a.\forall x\in Q(\mathcal K),\qquad \tau(x)\le a\ \Longrightarrow\ x\in\overline P_a.(5)✦

The Claim

Theorem 1. Suppose τ\tau assigns every job a slot from 11 through TT and respects precedence: r(u,z)r(u,z) implies τ(u)<τ(z)\tau(u)<\tau(z).

Let boundaries have times aa and bb, and put W=(a,b)W=(a,b). Let 𝒦\mathcal K be an indexed global set family and S⊆JS\subseteq J a cutoff set. Suppose membership in Q(𝒦)Q(\mathcal K) agrees with membership outside SS on WW, every job in W\SW\setminus S belongs to PbP_b, and 𝒦\mathcal K satisfies the past boundary invariant at aa. Then the high part has the global description (6). W\S=Q(𝒦)∩Pb∩P¯ac.W\setminus S =Q(\mathcal K)\cap P_b\cap\overline P_a^{\,c}.(6)✦

Let boundaries have times a′a', bb, b′b', and vv, with a≤a′<b′≤v<ba\le a'<b'\le v<b, and put W=(a,b)W=(a,b) and W′=(a′,b′)W'=(a',b'). Let S,S⋆,H⊆JS,S^\star,H\subseteq J. Suppose HH agrees with SS on WW and W∩S⊆S⋆W\cap S\subseteq S^\star. Suppose the boundary at vv separates WW relative to S⋆S^\star, and the boundary at b′b' separates (a,v)(a,v) relative to SS. If every job in W′∩SW'\cap S belongs to Da′∩PbD_{a'}\cap P_b, then the low part has the global description (7). W′∩S=Da′∩Pb∩D¯b′c∩D¯vc∩H.W'\cap S =D_{a'}\cap P_b\cap\overline D_{b'}^{\,c} \cap\overline D_v^{\,c}\cap H.(7)✦

In the paper, the result reads: in a valid construction with child W′=(a′,b′)W'=(a',b') of W=(a,b)W=(a,b), parent center vv, cutoff SS, new pruned list 𝒦′\mathcal K', and global cutoff S̃\widetilde S agreeing with SS throughout WW, the edge frame, a working frame in which precedence and time may be reversed, satisfies W′\S=Q(𝒦′)∩Pb′∩P¯a′cW'\setminus S=Q(\mathcal K')\cap P_{b'}\cap\overline P_{a'}^{\,c} and W′∩S=Da′∩Pb∩D¯b′c∩D¯vc∩S̃W'\cap S=D_{a'}\cap P_b\cap\overline D_{b'}^{\,c} \cap\overline D_v^{\,c}\cap\widetilde S.

What Is Checked

The identities are stated over a precedence relation with a bounded, precedence-respecting slot assignment, endpoint or triple boundaries at the specified slots, and job subsets and finite indexed global set families satisfying the stated conditions.