OctoInformBeta

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

Lemma 8.3: Global child and cutoff descriptions, with relative descriptions for scheduling split vertices

Structural predicates have bounded formula size.

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

Scheduling subproblems select jobs by their positions relative to boundary triples and by Boolean conditions on precedence cones and rank thresholds. The description size is the number of formula leaves, rather than the number of selected jobs.

Let JJ be a finite job set with precedence relation rr, written x≺yx\prec y. A layout pp is a bijection from JJ to positions 0,…,|J|−10,\ldots,|J|-1, read as consecutive triples.✦ For boundary slots a,ba,b, the time assignment τp\tau_p of a layout pp and its open scheduling window (a,b)p⊆J(a,b)_p\subseteq J are given by (1). τp(x)=⌊p(x)3⌋+1,(a,b)p={x∈J:a<τp(x)<b}.\tau_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad (a,b)_p=\{x\in J:a<\tau_p(x)<b\}.(1) A layout pp of JJ respects precedence when x≺yx\prec y implies τp(x)<τp(y)\tau_p(x)<\tau_p(y).✦ A full layout pp of JJ is a precedence-respecting layout with |J|=N=3T|J|=N=3T, where TT is its deadline.✦ Write W=(a,b)pW=(a,b)_p for the parent window in (1).

A job triple ZZ is a subset of JJ of cardinality three.✦ A scheduling boundary BB for JJ is a left endpoint, a job triple, or a right endpoint.✦ Their boundary times are respectively 00, a slot s∈{1,…,T}s\in\{1,\ldots,T\} whose jobs are exactly ZZ, and T+1T+1.✦ For an actual boundary, represented by a job triple ZZ, the strict predecessor and successor cones and their weak versions are given by (2). PZ={x:∃z∈Z,x≺z},DZ={x:∃z∈Z,z≺x},PZ≤=PZ∪Z,DZ≤=DZ∪Z.\begin{aligned} P_Z&=\{x:\exists z\in Z,\ x\prec z\},& D_Z&=\{x:\exists z\in Z,\ z\prec x\},\\ P_Z^{\leq}&=P_Z\cup Z,&D_Z^{\leq}&=D_Z\cup Z. \end{aligned}(2) For the left endpoint the predecessor cones are empty and the successor cones are JJ; the right endpoint has the opposite conventions. A boundary BB separates a job set UU at slot ss with cutoff CC when jobs of U\CU\setminus C earlier than ss belong to PBP_B, and jobs of U∩CU\cap C later than ss belong to DBD_B.✦

Boolean Descriptions and Runs

An atomic family 𝒜=(Aα)α\mathcal A=(A_\alpha)_\alpha assigns a job set to each atom. A Boolean structural formula ff over an atomic family 𝒜\mathcal A is a formula with signed atomic leaves and binary conjunctions or disjunctions.✦ The interpretation ⟦f⟧𝒜\llbracket f\rrbracket_{\mathcal A} of a Boolean structural formula ff over 𝒜\mathcal A is the job set obtained by assigning AαA_\alpha to a positive leaf and J\AαJ\setminus A_\alpha to a negative leaf, and interpreting the two connectives as intersection and union.✦ The leaf count ℓ(f)\ell(f) of a Boolean structural formula ff is the number obtained by assigning one to a leaf and adding the counts of the two subformulas at either connective.✦ For a job set U⊆JU\subseteq J and a leaf budget kk, the families ℬk\mathcal B_k of globally described sets and ℛk(U)\mathcal R_k(U) of relatively described sets in UU are the collections of job sets defined in (3). ℬk={F⊆J:∃f,⟦f⟧𝒜=Fandℓ(f)≤k},ℛk(U)={U∩F:F∈ℬk}.\begin{aligned} \mathcal B_k&=\{F\subseteq J:\exists f,\ \llbracket f\rrbracket_{\mathcal A}=F\ \text{and}\ \ell(f)\leq k\},\\ \mathcal R_k(U)&=\{U\cap F:F\in\mathcal B_k\}. \end{aligned}(3) For a rank function ρ:J→ℕ\rho:J\to\mathbb N and a threshold kk, the upper tail RkR_k is the job set Rk={x:k≤ρ(x)}R_k=\{x:k\leq\rho(x)\}.✦ Atomic predicate expressiveness means that JJ, the empty set, every RkR_k, every boundary cone in (2), and every job triple belong to ℬ1\mathcal B_1.✦

An indexed global set family ℒ=(I,(Ei)i∈ℕ)\mathcal L=(I,(E_i)_{i\in\mathbb N}) is a pair consisting of a finite index set I⊆ℕI\subseteq\mathbb N and a sequence of job sets Ei⊆JE_i\subseteq J.✦ The qualifier union Q(ℒ)Q(\mathcal L) of an indexed global set family ℒ=(I,(Ei)i∈ℕ)\mathcal L=(I,(E_i)_{i\in\mathbb N}) is the job set Q(ℒ)=⋃i∈IEiQ(\mathcal L)=\bigcup_{i\in I}E_i.✦ For a job x∈Jx\in J and an indexed global set family ℒ=(I,(Ei)i∈ℕ)\mathcal L=(I,(E_i)_{i\in\mathbb N}), the membership-index set of xx is Ix={i∈I:x∈Ei}I_x=\{i\in I:x\in E_i\}, and the last membership index of xx in ℒ\mathcal L is m(x)=max⁡Ixm(x)=\max I_x, with default zero. Lexicographic list priority orders jobs by (m(x),ρ(x))(m(x),\rho(x)).✦ For an indexed global set family ℒ\mathcal L, an index threshold dd, and a rank threshold kk, the suffix ℒd,k\mathcal L^{d,k} is the family obtained by discarding listed entries before dd, restricting the entry at dd to RkR_k, and retaining listed entries after dd.✦

A rank threshold run certificate for ℒ\mathcal L in WW consists of bases UiU_i, thresholds kik_i, and a distinguished set S2S_2, satisfying (4): Ei=Ui∩Rki(i∈I),Ui∈ℬ2(i∈I\{0}),U0∈ℬ24,U1=S2∈ℬ1,W\S2⊆U0,0∈I⇒(∀x∈W∩S2,1∈Iandx∈E1).\begin{gathered} E_i=U_i\cap R_{k_i}\quad(i\in I),\qquad U_i\in\mathcal B_2\quad(i\in I\setminus\{0\}),\\ U_0\in\mathcal B_{24},\qquad U_1=S_2\in\mathcal B_1,\qquad W\setminus S_2\subseteq U_0,\\ 0\in I\ \Longrightarrow\ \bigl(\forall x\in W\cap S_2,\ 1\in I\ \text{and}\ x\in E_1\bigr). \end{gathered}(4)✦ A global upset U⊆JU\subseteq J is a job set closed under successors for rr; a global family ℒ\mathcal L has upward-closed entries when every listed entry is a global upset. The injection entries EiE_i with listed indices i≥2i\geq2 of a global family ℒ\mathcal L are disjoint in WW when W∩Ei∩EjW\cap E_i\cap E_j is empty for distinct listed i,j≥2i,j\geq2.✦

For a layout pp, a global family ℒ\mathcal L, and a boundary A′A' at time a′a', the past boundary invariant requires every job of Q(ℒ)Q(\mathcal L) scheduled at or before a′a' to belong to PA′≤P_{A'}^{\leq}.✦ A layout qq is unchanged outside a set UU relative to pp when every job outside UU keeps its position.✦ Exchanging xx and yy swaps their positions and fixes all other jobs.✦ The forbidden exchange invariant for p,U,ℒ,ρ,A′,a′p,U,\mathcal L,\rho,A',a' requires that whenever qq is a precedence-respecting layout unchanged outside UU relative to pp and jobs x,yx,y satisfy x∈U\DA′x\in U\setminus D_{A'}, τq(y)=a′\tau_q(y)=a', y∈Q(ℒ)y\in Q(\mathcal L), and list priority of xx over yy, exchanging xx and yy in qq violates precedence feasibility.✦ The job exchange of jobs xx and yy in a layout qq is the layout obtained by swapping their positions and leaving every other job in its position.✦

Edge Certificates and Split Vertices

An edge structural certificate uses a full layout pp, parent W=(a,b)pW=(a,b)_p, and boundaries B,V,A′,B′B,V,A',B' at times b,v,a′,b′b,v,a',b', respectively, where B′B' is actual and a≤a′<b′≤v<b.a\leq a'<b'\leq v<b.(5) Besides (5), it has a cutoff CC and a final cutoff S∈ℬ1S\in\mathcal B_1. Boundary VV separates WW at vv with cutoff SS; A′A' and B′B' separate (a,v)p(a,v)_p at their respective times with cutoff CC. It requires W∩C⊆PB∩SW\cap C\subseteq P_B\cap S.

Its family ℒ\mathcal L has a run certificate in WW, upward-closed entries, an upward-closed distinguished set S2S_2, and disjoint injection entries in WW. It satisfies W∩Q(ℒ)=W\CW\cap Q(\mathcal L)=W\setminus C, the past boundary invariant at A′,a′A',a', and the forbidden exchange invariant on (a′,b′)p(a',b')_p at that boundary. The certificate also has sets G∈ℬ205G\in\mathcal B_{205} and H∈ℬ21H\in\mathcal B_{21} with W∩G=W∩H=W∩CW\cap G=W\cap H=W\cap C, where HH is downward closed under precedence.

A scheduling split vertex 𝒱\mathcal V in WW is a partition of WW into pairwise disjoint regions L,M,RL,M,R, where MM is a job triple and an antichain. There is no precedence from a later region to an earlier one in the order L,M,RL,M,R, and L,R∈ℛK(W)L,R\in\mathcal R_K(W) with the fixed allowance K=10000K=10000. Write Split⁡r,𝒜(W)\operatorname{Split}_{r,\mathcal A}(W) for the collection of these vertices.

The Claim

Theorem 1. Assume atomic predicate expressiveness for rr and ρ\rho. For a rank threshold run certificate of ℒ\mathcal L in WW with |I|≤5|I|\leq5, the qualifier bound is (6): Q(ℒ)∈ℬ195.Q(\mathcal L)\in\mathcal B_{195}.(6)✦ For the same run, every boundary BB and thresholds d,kd,k satisfy the suffix cutoff bound (7): PB\Q(ℒd,k)∈ℬ205.P_B\setminus Q(\mathcal L^{d,k})\in\mathcal B_{205}.(7)✦ Let ℒ′\mathcal L' be a global family with Q(ℒ′)∈ℬ195Q(\mathcal L')\in\mathcal B_{195}, and let S̃∈ℬ205\widetilde S\in\mathcal B_{205}. Suppose boundaries A′,B,B′,VA',B,B',V, a job set W′W', and a cutoff SS satisfy the high and low part identities W′\S=(Q(ℒ′)∩PB′)\PA′≤,W′∩S=(((DA′∩PB)\DB′≤)\DV≤)∩S̃.\begin{aligned} W'\setminus S&=(Q(\mathcal L')\cap P_{B'})\setminus P_{A'}^{\leq},\\ W'\cap S&=\bigl(((D_{A'}\cap P_B)\setminus D_{B'}^{\leq}) \setminus D_V^{\leq}\bigr)\cap\widetilde S. \end{aligned}(8) The child bound under (8) is (9): W′∈ℬ406.W'\in\mathcal B_{406}.(9)✦ For an edge structural certificate with target time b′b', the target description is (10): ∃F∈ℬ210,W∩F={x∈W:τp(x)<b′}.\exists F\in\mathcal B_{210},\qquad W\cap F=\{x\in W:\tau_p(x)<b'\}.(10)✦ Independently, let pp be a full layout, W=(a,b)pW=(a,b)_p, and a<s<ba<s<b. Let ZZ be the actual boundary triple at ss. Suppose F∈ℬkF\in\mathcal B_k, k+1≤10000k+1\leq10000, Z∈ℬ1Z\in\mathcal B_1, and W∩F={x∈W:τp(x)<s}W\cap F=\{x\in W:\tau_p(x)<s\}. The split vertex 𝒱s\mathcal V_s at time ss has left region {x∈W:τp(x)<s}\{x\in W:\tau_p(x)<s\}, middle region ZZ, and right region {x∈W:s<τp(x)}\{x\in W:s<\tau_p(x)\}, and belongs to the collection in (11): 𝒱s∈Split⁡r,𝒜(W).\mathcal V_s\in\operatorname{Split}_{r,\mathcal A}(W).(11)✦

In the paper, the result reads: the global child predicates and relative marked-split predicates of Lemmas 8.1 and 8.2 have fewer than 500500 leaves, with at most 195195 for the qualifier union, 196196 for a same-direction cutoff (205205 allowed uniformly), 197197 and 209209 for the high and low child predicates, 406406 for their union, three for the center, 210210 for an internal split, and one additional leaf for reverse conversion.

What Is Checked

The claims are stated over finite job sets with atomic families and rank functions; the scheduling constructions additionally use full precedence-respecting layouts, boundary times and separation, and the specified run and edge structural certificates.