OctoInformBeta

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

Lemma 6.1: Rank thresholds select qualifiers while preserving upward closure for ranks that increase along precedence

Suffix carry preserves list priorities.

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 list can give a job priority according to the last entry that contains it, with rank breaking ties between jobs in the same entry. Suffix carry cuts such a list at an index and a rank threshold. The library states its membership and order properties for arbitrary ranks, and its upward closure property for ranks that increase strictly along precedence.

An indexed global set family 𝒦=(I,(Ki)iβˆˆβ„•)\mathcal K=(I,(K_i)_{i\in\mathbb N}) on a job set JJ is a family of subsets KiβŠ†JK_i\subseteq J with a finite set IβŠ†β„•I\subseteq\mathbb N of listed indices.✦ The membership indices I𝒦(x)I_{\mathcal K}(x) of a job x∈Jx\in J are the listed indices whose entries contain xx✦; its last membership index λ𝒦(x)\lambda_{\mathcal K}(x) is their maximum, with default zero, as in (1).✦ I𝒦(x)={i∈I:x∈Ki},λ𝒦(x)=max⁡(I𝒦(x)βˆͺ{0}).I_{\mathcal K}(x)=\{i\in I:x\in K_i\}, \qquad \lambda_{\mathcal K}(x)=\max\bigl(I_{\mathcal K}(x)\cup\{0\}\bigr).(1)

The qualifier set Q𝒦Q_{\mathcal K}, also called the global entry union, is the set of jobs in JJ that belong to at least one listed entry, as defined in (2). Q𝒦=⋃i∈IKi.Q_{\mathcal K}=\bigcup_{i\in I}K_i.(2)✦

For a rank function ρ:Jβ†’β„•\rho:J\to\mathbb N, the key of a job xx is the pair κ𝒦,ρ(x)=(λ𝒦(x),ρ(x))\kappa_{\mathcal K,\rho}(x)=(\lambda_{\mathcal K}(x),\rho(x)). Lexicographic list priority βŠ²π’¦,ρ\triangleleft_{\mathcal K,\rho} for an indexed global set family 𝒦\mathcal K on JJ and a rank function ρ:Jβ†’β„•\rho:J\to\mathbb N is the strict order obtained by comparing job keys lexicographically, as given by (3). xβŠ²π’¦,ρy⇔λ𝒦(x)<λ𝒦(y)∨(λ𝒦(x)=λ𝒦(y)∧ρ(x)<ρ(y)).x\triangleleft_{\mathcal K,\rho}y \quad\Longleftrightarrow\quad \lambda_{\mathcal K}(x)<\lambda_{\mathcal K}(y) \ \lor\ \bigl(\lambda_{\mathcal K}(x)=\lambda_{\mathcal K}(y) \ \land\ \rho(x)<\rho(y)\bigr).(3)✦

A global upset UβŠ†JU\subseteq J for a precedence relation β‰Ί\prec is a set closed under passage to successors, with the condition in (4).✦ An upset list 𝒦\mathcal K on JJ for a precedence relation β‰Ί\prec is an indexed global set family whose listed entries are global upsets for β‰Ί\prec.✦ x∈U∧xβ‰Ίyβ‡’y∈U(x,y∈J).x\in U\ \land\ x\prec y\quad\Longrightarrow\quad y\in U \qquad(x,y\in J).(4)✦

For an indexed global set family 𝒦\mathcal K on JJ, a rank function ρ:Jβ†’β„•\rho:J\to\mathbb N, and natural numbers dd and rr, the global list suffix π’ž=carry⁡d,r(𝒦,ρ)\mathcal C=\operatorname{carry}_{d,r}(\mathcal K,\rho) is the indexed family on JJ that retains listed indices at least dd and restricts entry dd to jobs of rank at least rr.✦ Write CiC_i for the entry of π’ž\mathcal C at index ii, Iπ’žI_{\mathcal C} for its listed indices, Qπ’žQ_{\mathcal C} for its qualifiers, and Ξ»π’ž\lambda_{\mathcal C} for its last membership index.

The Claim

Theorem 1. Let 𝒦\mathcal K be an indexed global set family on JJ, let ρ:Jβ†’β„•\rho:J\to\mathbb N, and let d,rβˆˆβ„•d,r\in\mathbb N. Put π’ž=carry⁡d,r(𝒦,ρ)\mathcal C=\operatorname{carry}_{d,r}(\mathcal K,\rho). For every job x∈Jx\in J, suffix membership is characterized by (5). x∈Qπ’žβ‡”x∈Qπ’¦βˆ§(d<λ𝒦(x)∨(λ𝒦(x)=d∧r≀ρ(x))).x\in Q_{\mathcal C} \quad\Longleftrightarrow\quad x\in Q_{\mathcal K}\ \land\ \bigl(d<\lambda_{\mathcal K}(x) \ \lor\ (\lambda_{\mathcal K}(x)=d\ \land\ r\le\rho(x))\bigr).(5)✦ For jobs x,y∈Qπ’žx,y\in Q_{\mathcal C}, the key orders satisfy (6). xβŠ²π’ž,ρy⇔xβŠ²π’¦,ρy.x\triangleleft_{\mathcal C,\rho}y \quad\Longleftrightarrow\quad x\triangleleft_{\mathcal K,\rho}y.(6)✦ Suppose also that 𝒦\mathcal K is an upset list for a precedence relation β‰Ί\prec and that ρ(x)<ρ(y)\rho(x)<\rho(y) whenever xβ‰Ίyx\prec y. Then (7) holds. Ci is a global upset for β‰Ί(i∈Iπ’ž).C_i\text{ is a global upset for }\prec \qquad(i\in I_{\mathcal C}).(7)✦

In the paper, the result reads: for a global upset list (K1,…,Kβ„“)(K_1,\ldots,K_\ell) on a padded job set with valid deadline TT and size N=3TN=3T, 1≀d≀ℓ1\le d\le\ell, and 0≀r≀N+10\le r\le N+1, the list (Kd∩{x:ρ(x)β‰₯r},Kd+1,…,Kβ„“)(K_d\cap\{x:\rho(x)\ge r\},K_{d+1},\ldots,K_\ell) has exactly the old qualifiers with key at least (d,r)(d,r) in lexicographic order, its key order agrees with the old order on those qualifiers, and every entry remains a global upset.

What Is Checked

The statements concern arbitrary job sets and finitely indexed global set families, with natural number ranks and thresholds, and require rank to increase strictly along precedence for the upward closure conclusion.