OctoInformBeta

OpenAI preprint, September 2026 · §4. Separators with a shared cutoff

Lemma 4.4: Nested precedence ideals and adjacent numeric cuts under a local priority obstruction

Advancing to a shared priority separator.

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 boundary in a schedule separates low jobs from high jobs through the precedence constraints incident to its slot. The question is whether a boundary can serve two priority prefixes when one job changes from high to low.

Let JJ be a job set, let x≺yx\prec y denote precedence, and let τ:J→ℕ\tau:J\to\mathbb N assign jobs to time slots. Let W⊆JW\subseteq J be a finite domain, and let π:J→ℕ\pi:J\to\mathbb N assign priorities, with smaller numbers coming first. Relative to a set S⊆JS\subseteq J, the low jobs are W∩SW\cap S and the high jobs are W\SW\setminus S.

A domain WW is slot-closed for τ\tau when it contains every job sharing a slot with one of its jobs.✦ An admissible position s∈ℕs\in\mathbb N for WW is either the slot of a job in WW or a position strictly before every job in WW.✦

The cutoff predecessor cone PsP_s consists of the jobs preceding some job in slot ss✦, and the cutoff successor cone DsD_s consists of the jobs following some job in that slot, as in (1). Ps={x∈J:∃y∈J,τ(y)=s∧x≺y},Ds={x∈J:∃y∈J,τ(y)=s∧y≺x}.P_s=\{x\in J:\exists y\in J,\ \tau(y)=s\ \land\ x\prec y\}, \qquad D_s=\{x\in J:\exists y\in J,\ \tau(y)=s\ \land\ y\prec x\}.(1)

Earlier high job coverage at a cutoff ss for SS in WW is the condition that every x∈W\Sx\in W\setminus S with τ(x)<s\tau(x)<s belongs to PsP_s.✦ Later low job coverage at a cutoff ss for SS in WW is the condition that every x∈W∩Sx\in W\cap S with s<τ(x)s<\tau(x) belongs to DsD_s.✦ A separator ss for SS in WW is a cutoff satisfying earlier high job coverage and later low job coverage for SS in WW; write Sep⁡W(S,s)\operatorname{Sep}_W(S,s) for this property.✦

Priority Prefixes and Exception Advances

A relative precedence ideal SS on WW is a set of jobs such that, whenever x,y∈Wx,y\in W, x≺yx\prec y and y∈Sy\in S, one has x∈Sx\in S.✦ A priority prefix SS on WW is a set of jobs for which π(x)<π(y)\pi(x)<\pi(y) whenever x∈W∩Sx\in W\cap S and y∈W\Sy\in W\setminus S.✦ The numeric priority cut SkS_k at k∈ℕk\in\mathbb N is the set of jobs in JJ with priority less than kk, as in (2). Sk={x∈J:π(x)<k}.S_k=\{x\in J:\pi(x)<k\}.(2)✦

The local priority obstruction property on WW is the condition that (3) holds for every pair x,y∈Wx,y\in W with τ(y)<τ(x)\tau(y)<\tau(x) and π(x)<π(y)\pi(x)<\pi(y). (∀u∈W,u≺x⇒τ(u)<τ(y))⇒∃v∈W,y≺v∧τ(v)≤τ(x).\left(\forall u\in W,\ u\prec x\ \Longrightarrow\ \tau(u)<\tau(y)\right) \ \Longrightarrow\ \exists v\in W,\ y\prec v\ \land\ \tau(v)\leq\tau(x).(3)✦

An exceptional job xx at ss for SS is a job in W∩SW\cap S scheduled after ss and outside DsD_s, such that every y∈W∩Sy\in W\cap S with s<τ(y)<τ(x)s<\tau(y)<\tau(x) belongs to DsD_s.✦ An advance path s⤳Sts\leadsto_S t is a finite sequence s=s0<⋯<sm=ts=s_0<\cdots<s_m=t, with m≥0m\geq0, whose next position si+1s_{i+1} is τ(xi)\tau(x_i) for an exceptional job xix_i at sis_i for SS.✦

The Claim

Theorem 1. Let precedence be transitive, and suppose x≺yx\prec y implies τ(x)<τ(y)\tau(x)<\tau(y) for all jobs in JJ. Let WW be a finite slot-closed domain satisfying the local priority obstruction property. Suppose SS and S+S^+ are relative precedence ideals and priority prefixes on WW, and let a∈Ja\in J satisfy z∈S+⇔z∈S∨z=az\in S^+\iff z\in S\ \lor\ z=a for every z∈Wz\in W. If ss is an admissible position separating SS, then ∃t≥s,s⤳S+t∧Sep⁡W(S,t)∧Sep⁡W(S+,t).\exists t\geq s,\quad s\leadsto_{S^+}t\ \land\ \operatorname{Sep}_W(S,t)\ \land\ \operatorname{Sep}_W(S^+,t).(4)✦

For arbitrary finite WW, precedence, time assignment and cutoff uu, let A,B⊆JA,B\subseteq J agree on WW. Then Sep⁡W(A,u)⇔Sep⁡W(B,u).\operatorname{Sep}_W(A,u)\ \Longleftrightarrow\ \operatorname{Sep}_W(B,u).(5)✦

For numeric cuts, retain the transitivity, time, closure and local obstruction assumptions, and suppose π\pi is injective on WW and satisfies π(x)<π(y)\pi(x)<\pi(y) whenever x,y∈Wx,y\in W and x≺yx\prec y. If ss is an admissible position separating SkS_k, then ∃t≥s,s⤳Sk+1t∧Sep⁡W(Sk,t)∧Sep⁡W(Sk+1,t).\exists t\geq s,\quad s\leadsto_{S_{k+1}}t\ \land\ \operatorname{Sep}_W(S_k,t)\ \land\ \operatorname{Sep}_W(S_{k+1},t).(6)✦

In the paper, the result reads: fix a normalized full schedule of a domain and consecutive priority prefixes S,S+S,S^+ differing by promoting one job from high to low; from a separator ss of SS, internal or at the exterior left boundary, some t≥st\geq s is reached by advancing only to domain slots on the right and separates both SS and S+S^+, with t=st=s permitted when the promoted job lies outside the domain.

What Is Checked

The shared cutoff assertions (4) and (6) are stated over finite slot-closed domains with time assignments respecting transitive precedence and the local priority obstruction property, while separator extensionality (5) is stated for arbitrary finite domains, relations and time assignments.