OctoInformBeta

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

§4 (setting): Definition 4.1 and lexicographic normalization: Relative ideals, boundary cones, and lexicographic normalization of feasible layouts

Separators constrain jobs across a cutoff.

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

Let JJ be a finite set of unit jobs with precedence relation ≺\prec, and let W⊆JW\subseteq J be a scheduling domain. A set S⊆JS\subseteq J designates the low jobs; the high jobs are J\SJ\setminus S. Separation concerns jobs whose temporal side of a cutoff disagrees with their low or high classification.

A job triple Z⊆JZ\subseteq J is a set of cardinality three.✦ A scheduling boundary zz for the job set JJ is a left endpoint ℓ\ell, a job triple ZZ of JJ, or a right endpoint ρ\rho.✦ The strict predecessor cone PzP_z, strict successor cone DzD_z, and weak successor cone D¯z\overline D_z of a scheduling boundary zz are the sets defined by (1). (Pℓ,Dℓ,D¯ℓ)=(⌀,J,J),PZ={x∈J:∃y∈Z,x≺y},DZ={x∈J:∃y∈Z,y≺x},D¯Z=DZ∪Z,(Pρ,Dρ,D¯ρ)=(J,⌀,⌀).\begin{aligned} (P_\ell,D_\ell,\overline D_\ell)&=(\varnothing,J,J),\\ P_Z&=\{x\in J:\exists y\in Z,\ x\prec y\},\\ D_Z&=\{x\in J:\exists y\in Z,\ y\prec x\}, &\overline D_Z&=D_Z\cup Z,\\ (P_\rho,D_\rho,\overline D_\rho)&=(J,\varnothing,\varnothing). \end{aligned}(1)

For a time assignment τ:J→ℕ\tau:J\to\mathbb N and a cutoff s∈ℕs\in\mathbb N, the cutoff predecessor cone PsP_s and cutoff successor cone DsD_s are the sets in (2). Ps={x∈J:∃y∈J,τ(y)=sandx≺y},Ds={x∈J:∃y∈J,τ(y)=sandy≺x}.\begin{aligned} P_s&=\{x\in J:\exists y\in J,\ \tau(y)=s\ \text{and}\ x\prec y\},\\ D_s&=\{x\in J:\exists y\in J,\ \tau(y)=s\ \text{and}\ y\prec x\}. \end{aligned}(2) Earlier high coverage E(W,S,s)E(W,S,s) and later low coverage F(W,S,s)F(W,S,s) are the conditions in (3). E(W,S,s)⇔∀x∈W\S,τ(x)<s⇒x∈Ps,F(W,S,s)⇔∀x∈W∩S,s<τ(x)⇒x∈Ds.\begin{aligned} E(W,S,s)&\iff \forall x\in W\setminus S,\quad \tau(x)<s\ \Longrightarrow\ x\in P_s,\\ F(W,S,s)&\iff \forall x\in W\cap S,\quad s<\tau(x)\ \Longrightarrow\ x\in D_s. \end{aligned}(3)

A job layout pp of JJ is a bijection from JJ to the positions 0,…,|J|−10,\ldots,|J|-1, read in consecutive groups of three.✦ The time slot τp(x)\tau_p(x) of a job xx in a layout pp of JJ is the natural number given by (4). τp(x)=⌊p(x)3⌋+1.\tau_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(4)✦ A precedence-feasible layout pp of JJ is a layout for which τp(x)<τp(y)\tau_p(x)<\tau_p(y) whenever x≺yx\prec y.✦ A layout qq of JJ is fixed outside WW relative to a layout pp of JJ if q(x)=p(x)q(x)=p(x) for every x∉Wx\notin W.✦

For a priority function π:J→ℕ\pi:J\to\mathbb N, the priority signature σπ(p)\sigma_\pi(p) of a layout pp of JJ is the sequence in (5); signatures are compared lexicographically. σπ(p)=(π(p−1(i)))0≤i<|J|.\sigma_\pi(p)= \bigl(\pi(p^{-1}(i))\bigr)_{0\leq i<|J|}.(5)✦

The Definition

Definition 1. A relative order ideal SS on WW is a subset of JJ whose restriction to WW satisfies (6). ∀x,y∈W,x≺yandy∈S⇒x∈S.\forall x,y\in W,\qquad x\prec y\ \text{and}\ y\in S\ \Longrightarrow\ x\in S.(6)✦

A shared cutoff separator ss for WW and SS is a cutoff satisfying (7). E(W,S,s)∧F(W,S,s).E(W,S,s)\ \land\ F(W,S,s).(7)✦

A separating boundary zz for SS in WW at cutoff ss is a scheduling boundary satisfying (8). ∀x∈W\S,τ(x)<s⇒x∈Pz,∀x∈W∩S,s<τ(x)⇒x∈Dz.\begin{aligned} \forall x\in W\setminus S,\quad \tau(x)<s&\ \Longrightarrow\ x\in P_z,\\ \forall x\in W\cap S,\quad s<\tau(x)&\ \Longrightarrow\ x\in D_z. \end{aligned}(8)✦

The boundary prefix set Bz(H)B_z(H) of a scheduling boundary zz relative to a set H⊆JH\subseteq J is the set in (9). Bz(H)=Pz∪(H\D¯z).B_z(H)=P_z\cup\bigl(H\setminus\overline D_z\bigr).(9)✦

A normalized layout pp of JJ for priority π\pi is a layout satisfying (10). p is precedence feasible,σπ(p)≤lexσπ(q)for every precedence feasible layout q.\begin{gathered} p\text{ is precedence feasible},\\ \sigma_\pi(p)\leq_{\mathrm{lex}}\sigma_\pi(q) \quad\text{for every precedence feasible layout }q. \end{gathered}(10)✦

A locally normalized layout pp of JJ on WW for priority π\pi is a layout satisfying (11). p is precedence feasible,σπ(p)≤lexσπ(q)for every precedence feasible layout qfixed outside W relative to p.\begin{gathered} p\text{ is precedence feasible},\\ \sigma_\pi(p)\leq_{\mathrm{lex}}\sigma_\pi(q) \quad\text{for every precedence feasible layout }q\\ \text{fixed outside }W\text{ relative to }p. \end{gathered}(11)✦

In the paper, the result reads: for an ideal SS of low jobs in a contiguous domain, a separator zz has every earlier high job in PzP_z and every later low job in DzD_z; an exterior left boundary separates when all low domain jobs descend from it; Bz(H)=Pz∪(H\D¯z)B_z(H)=P_z\cup(H\setminus\overline D_z); a normalized schedule is lexicographically least after each triple is sorted by a precedence-extending priority order.

What Is Checked

The separation definitions are stated for a finite domain WW, subsets S,H⊆JS,H\subseteq J, a precedence relation, a natural-number time assignment and scheduling boundaries; the normalization definitions range over layouts of finite JJ and natural-number priority functions.