OctoInformBeta

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

Lemma 4.3: Local normalization retains the obstruction after a reordering fixes the initial segment through the earlier job

Normalized layouts exclude feasible improving exchanges.

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

In three-machine unit-job scheduling, exchanging two jobs can change their slots without changing the number of jobs assigned to any slot. The question is whether rearranging later jobs can enable an exchange that brings a better-priority job forward.

A layout pp of a finite job set JJ is a bijection from JJ to the positions 0,…,|J|−10,\ldots,|J|-1; its jobs are read in consecutive triples.✦ The time slot tp(x)t_p(x) of a job x∈Jx\in J is the integer defined by (1). tp(x)=⌊p(x)3⌋+1.t_p(x)=\left\lfloor\frac{p(x)}{3}\right\rfloor+1.(1)✦ A layout pp is precedence feasible for a relation ≺\prec on JJ if every pair u≺vu\prec v has tp(u)<tp(v)t_p(u)<t_p(v).✦

A priority assignment π:J→ℕ\pi:J\to\mathbb N assigns a natural number to each job, with smaller numbers representing better priority. The priority signature σπ(p)\sigma_\pi(p) of a layout pp is the list in (2), compared with other signatures in lexicographic order. σπ(p)=(π(p−1(i)))0≤i<|J|.\sigma_\pi(p)=\bigl(\pi(p^{-1}(i))\bigr)_{0\leq i<|J|}.(2)✦ A normalized layout pp for ≺\prec and π\pi is a precedence feasible layout whose priority signature is lexicographically no greater than that of every precedence feasible layout.✦

For layouts p,qp,q of JJ and a set W⊆JW\subseteq J, the layout qq is unchanged outside WW relative to pp if q(x)=p(x)q(x)=p(x) for every x∉Wx\notin W.✦ A locally normalized layout pp on WW for ≺\prec and π\pi is a precedence feasible layout whose priority signature is lexicographically no greater than that of every precedence feasible layout unchanged outside WW relative to pp.✦

The exchange px↔yp^{x\leftrightarrow y} of jobs x,y∈Jx,y\in J in a layout pp is the layout in which xx and yy trade positions and every other job keeps its position.✦

The Claim

Theorem 1. Let pp be a normalized layout for ≺\prec and π\pi, and let x,y∈Jx,y\in J satisfy tp(y)<tp(x)t_p(y)<t_p(x) and π(x)<π(y)\pi(x)<\pi(y). Then ∃u,v∈J:u≺vandtpx↔y(v)≤tpx↔y(u).\exists u,v\in J:\quad u\prec v \quad\text{and}\quad t_{p^{x\leftrightarrow y}}(v)\leq t_{p^{x\leftrightarrow y}}(u).(3)✦

Let pp be locally normalized on WW for ≺\prec and π\pi, let x,y∈Wx,y\in W, and let qq be a layout unchanged outside WW relative to pp. Suppose that q−1(i)=p−1(i)q^{-1}(i)=p^{-1}(i) at every position i≤p(y)i\leq p(y), that tq(y)<tq(x)t_q(y)<t_q(x), and that π(x)<π(y)\pi(x)<\pi(y). Then ∃u,v∈J:u≺vandtqx↔y(v)≤tqx↔y(u).\exists u,v\in J:\quad u\prec v \quad\text{and}\quad t_{q^{x\leftrightarrow y}}(v)\leq t_{q^{x\leftrightarrow y}}(u).(4)✦

In the paper, the result reads: in a normalized schedule, a feasible exchange putting a better-priority job in an earlier slot is impossible, and after any feasible reordering confined strictly after a slot rr, exchanging a job at rr with a better-priority later job is still impossible.

What Is Checked

The claims (3) and (4) are stated over finite job sets, layouts grouped into consecutive triples, a precedence relation and natural-number priorities; the second also uses local normalization on WW, an unchanged exterior and an initial segment fixed through position p(y)p(y).