OctoInformBeta

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

Lemma 6.4: A finite boundary comparison under upward closure and disjointness, with a three-job specialization

Boundary bounds for pruned global lists.

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 scheduling construction may retain several global sets of jobs as the region of interest changes. The issue is how a boundary of jobs constrains the number of sets that remain relevant. The library states the comparison for two subsets WW and W′W' of a job set JJ, with precedence relation rr on JJ.

A global list ℒ=(A,(Ui)i∈ℕ)\mathcal L=(A,(U_i)_{i\in\mathbb N}) on JJ is an indexed family of job sets, with a finite set A⊆ℕA\subseteq\mathbb N of listed indices and an entry Ui⊆JU_i\subseteq J at every natural-number index.✦ The global entry union QQ of a global list ℒ\mathcal L on JJ is the set of jobs belonging to at least one listed entry, as in (1). Q=⋃i∈AUi.Q=\bigcup_{i\in A}U_i.(1)✦

A job set U⊆JU\subseteq J is globally upward closed for rr when every successor under rr of a job in UU also belongs to UU.✦ A global list ℒ\mathcal L on JJ has upward-closed entries for rr when each of its listed entries is a globally upward-closed subset of JJ for rr.✦

The injection entries UiU_i of a global list ℒ\mathcal L on JJ are its listed job sets with indices at least two. The injection entries of a global list ℒ\mathcal L on JJ are disjoint within WW when the condition in (2) holds. Ui∩Uj∩W=⌀(i,j∈A,i,j≥2,i≠j).U_i\cap U_j\cap W=\varnothing \qquad (i,j\in A,\ i,j\geq2,\ i\ne j).(2)✦

The pruning of a global list ℒ\mathcal L on JJ relative to W′W' is the global list on JJ with listed indices A′A' from (3) and the same entry UiU_i at every index. A′={i∈A:Ui∩W′≠⌀}.A'=\{i\in A:U_i\cap W'\ne\varnothing\}.(3)✦

A job triple BB in JJ is a finite subset of JJ of cardinality three.✦

The Claim

Theorem 1. Let ℒ\mathcal L be a global list on JJ with upward-closed entries for rr. Let W,W′⊆JW,W'\subseteq J and let B⊆WB\subseteq W be finite. Suppose that every job in W′∩QW'\cap Q precedes some job in BB under rr.

Let I⊆AI\subseteq A be a set of indices whose entries each meet W′W' and whose restrictions to WW are pairwise disjoint. Then |I|≤|B|.|I|\leq |B|.(4)✦

If BB is a job triple and the injection entries of ℒ\mathcal L are disjoint within WW, then the pruned list satisfies |A′|≤5.|A'|\leq5.(5)✦

In the paper, the result reads: every pruned list produced by the construction has at most five entries, of which at most three are injections from its current run.

What Is Checked

The bounds (4) and (5) are stated over finite indexed families of job sets with upward-closed entries, two arbitrary job subsets, and a finite boundary set that each relevant job precedes, specialized to a job triple for (5).