OctoInformBeta

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

Lemma 6.6: Rank threshold runs with at most five entries yield bounded Boolean descriptions

Short global extensions of carried cutoffs.

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 subproblem selects jobs within a region WW of the job set JJ. A global extension must agree with that selection on WW while satisfying precedence closure throughout JJ. Let rr be the precedence relation in the working frame and ρ:J→ℕ\rho:J\to\mathbb N its rank function; the region W⊆JW\subseteq J is arbitrary. A global upset F⊆JF\subseteq J is a set containing yy whenever x∈Fx\in F and r(x,y)r(x,y).✦ A global downset F⊆JF\subseteq J for rr is an upset for the reversed relation r(y,x)r(y,x).

Global Lists and Descriptions

An atomic family 𝒜=(Aα)α∈Λ\mathcal A=(A_\alpha)_{\alpha\in\Lambda} assigns a subset of JJ to each atom. A Boolean structural formula pp over Λ\Lambda is a signed atomic leaf or a conjunction or disjunction of two such formulas.✦ The interpretation ⟦p⟧𝒜\llbracket p\rrbracket_{\mathcal A} of a Boolean structural formula pp over the atomic family 𝒜\mathcal A is the subset of JJ obtained by assigning AαA_\alpha to a positive leaf and J\AαJ\setminus A_\alpha to a negative leaf, with conjunction and disjunction interpreted as intersection and union.✦ The leaf count ℓ(p)\ell(p) of a Boolean structural formula pp is the number obtained by counting one at a leaf and summing the two counts at either binary operation.✦ A bounded Boolean description pp of F⊆JF\subseteq J with allowance qq is a Boolean structural formula whose interpretation is FF and whose leaf count is at most qq; (1) states that such a description exists: 𝖣𝖾𝗌𝖼q(F)⇔∃p(⟦p⟧𝒜=Fandℓ(p)≤q).\mathsf{Desc}_q(F) \quad\Longleftrightarrow\quad \exists p\;\bigl(\llbracket p\rrbracket_{\mathcal A}=F \ \text{and}\ \ell(p)\le q\bigr).(1)✦

An indexed global set family ℒ\mathcal L on JJ consists of a finite set I⊆ℕI\subseteq\mathbb N of listed indices and an entry Ei⊆JE_i\subseteq J for every i∈ℕi\in\mathbb N.✦ The global entry union QQ of an indexed global set family ℒ\mathcal L on JJ is the subset of JJ given by (2): Q=⋃i∈IEi.Q=\bigcup_{i\in I}E_i.(2) An indexed global set family ℒ\mathcal L on JJ, with listed indices II and entries EiE_i, has upward-closed list entries when each EiE_i with i∈Ii\in I is a global upset for rr.

The rank upper tail RkR_k at threshold k∈ℕk\in\mathbb N is the set in (3): Rk={x∈J:k≤ρ(x)}.R_k=\{x\in J:k\le\rho(x)\}.(3)✦ The global list suffix ℒd,k\mathcal L^{d,k} of an indexed global set family ℒ\mathcal L, for cutoffs d,k∈ℕd,k\in\mathbb N, is the indexed global set family obtained by discarding listed indices below dd, replacing the entry at dd by Ed∩RkE_d\cap R_k when dd is listed, and retaining entries above dd. Write Qd,kQ_{d,k} for its global entry union.

Boundaries and Run Certificates

A job triple ZZ in JJ is a finite set of three jobs.✦ A scheduling triple boundary BB is a left endpoint, an actual job triple, or a right endpoint.✦ For an actual boundary given by a job triple ZZ in JJ, the strict predecessor and successor cones P(Z)P(Z) and D(Z)D(Z) and the weak cones P¯(Z)\overline P(Z) and D¯(Z)\overline D(Z) are the subsets of JJ defined by (4): P(Z)={x∈J:∃y∈Z,r(x,y)},D(Z)={x∈J:∃y∈Z,r(y,x)},P¯(Z)=P(Z)∪Z,D¯(Z)=D(Z)∪Z.\begin{aligned} P(Z)&=\{x\in J:\exists y\in Z,\ r(x,y)\},& D(Z)&=\{x\in J:\exists y\in Z,\ r(y,x)\},\\ \overline P(Z)&=P(Z)\cup Z,& \overline D(Z)&=D(Z)\cup Z. \end{aligned}(4) At the left endpoint both predecessor cones are empty and both successor cones are JJ; at the right endpoint these assignments are reversed. The atomic family 𝒜\mathcal A has atomic predicate expressiveness for (r,ρ)(r,\rho) when JJ, the empty set, every rank upper tail, all four cones of every boundary, and every job triple each have a one-leaf description.✦

A rank threshold run certificate CC for (ℒ,ρ,𝒜,W)(\mathcal L,\rho,\mathcal A,W) is a family of base sets Ui⊆JU_i\subseteq J and thresholds ti∈ℕt_i\in\mathbb N, together with a distinguished second set S⊆JS\subseteq J, satisfying (5): Ei=Ui∩Rti(i∈I),𝖣𝖾𝗌𝖼2(Ui)(i∈I,i≠0),𝖣𝖾𝗌𝖼24(U0),𝖣𝖾𝗌𝖼1(S),U1=S,W\S⊆U0,0∈I⇒(∀x∈W∩S,1∈Iandx∈E1).\begin{aligned} E_i&=U_i\cap R_{t_i} &&(i\in I),\\ \mathsf{Desc}_2(U_i)& &&(i\in I,\ i\ne0),\\ \mathsf{Desc}_{24}(U_0)&,\qquad \mathsf{Desc}_1(S),\qquad U_1=S,\\ W\setminus S&\subseteq U_0,\\ 0\in I&\ \Longrightarrow\ \bigl(\forall x\in W\cap S,\ 1\in I\ \text{and}\ x\in E_1\bigr). \end{aligned}(5)✦

The Claim

Theorem 1. Let ℒ\mathcal L have a rank threshold run certificate on WW and at most five listed indices. Suppose its listed entries and its second set SS are global upsets for rr, and r(x,y)r(x,y) always gives ρ(x)<ρ(y)\rho(x)<\rho(y). Suppose every rank upper tail and the empty set have one-leaf descriptions. There is a global upset H+⊆JH_+\subseteq J satisfying (6): 𝖣𝖾𝗌𝖼20(H+),W∩H+=W∩Q.\mathsf{Desc}_{20}(H_+),\qquad W\cap H_+=W\cap Q.(6)✦

Assume additionally that rr is transitive and 𝒜\mathcal A has atomic predicate expressiveness for (r,ρ)(r,\rho). For every scheduling triple boundary BB and cutoffs d,k∈ℕd,k\in\mathbb N, there is a global downset Hlow⊆JH_{\mathrm{low}}\subseteq J satisfying (7): 𝖣𝖾𝗌𝖼21(Hlow),W∩Hlow=W∩(P(B)\Qd,k).\mathsf{Desc}_{21}(H_{\mathrm{low}}),\qquad W\cap H_{\mathrm{low}}=W\cap\bigl(P(B)\setminus Q_{d,k}\bigr).(7)✦

In the paper, the result reads: for an already constructed edge from parent UU to child WW in its old working frame, its low cutoff H−H_- has a global downset extension agreeing with it on all of UU and having at most 2121 leaves.

What Is Checked

The extension statements are over indexed global set families and rank threshold run certificates on W⊆JW\subseteq J, with upward closure, strict rank growth and atomic description hypotheses; the carried low cutoff also uses a scheduling triple boundary and transitive precedence.