OctoInformBeta

OpenAI preprint, September 2026 · §2. Sweeps, activity, and exchange graphs

Lemma 2.3: Endpoint distances control the number of intervals with disjoint sweep steps

Greedy checkpoints bound interval packings.

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

The packing problem concerns intervals of a planar sweep whose endpoint selections differ in many point indices. Let P:I→ℝ2P:I\to\mathbb R^2 be an indexed configuration of nn points, where I={0,…,n−1}I=\{0,\ldots,n-1\}, and write P(i)=(xi,yi)P(i)=(x_i,y_i). The sweep projection at a real slope ss is the function in (1). πs(x,y)=y−sx.\pi_s(x,y)=y-sx.(1)✦

A subset M⊆IM\subseteq I is projection-separated at slope ss when its points precede all points outside MM in the strict projection order, as in (2). πs(P(i))<πs(P(j))(i∈M,j∈I\M).\pi_s(P(i))<\pi_s(P(j)) \qquad(i\in M,\ j\in I\setminus M).(2)✦

The directed set distance δ(M,N)\delta(M,N) between subsets of II counts the indices in MM but not in NN, as specified in (3). δ(M,N)=|M\N|.\delta(M,N)=|M\setminus N|.(3)✦

A rank kk sweep sequence SS with TT steps consists of slopes sts_t and marked sets Mt⊆IM_t\subseteq I, indexed by 0≤t≤T0\le t\le T, such that MtM_t is projection-separated at sts_t and the conditions in (4) hold. s0<⋯<sT,|Mt|=k(0≤t≤T),δ(Mt,Mt+1)≤1(0≤t<T).s_0<\cdots<s_T,\qquad |M_t|=k\quad(0\le t\le T),\qquad \delta(M_t,M_{t+1})\le1\quad(0\le t<T).(4)✦

The state distance D(u,v)D(u,v) in SS is the directed distance between the marked sets at states uu and vv, as in (5). D(u,v)=δ(Mu,Mv).D(u,v)=\delta(M_u,M_v).(5)✦

Checkpoints and Intervals

For a state ss of SS and a positive integer aa, the eligible checkpoint set Ea(s)E_a(s) is the set of states of SS later than ss and at distance at least aa from ss.✦ When Ea(s)E_a(s) is nonempty, the next checkpoint qa(s)q_a(s) of SS after ss at threshold aa is the least member of Ea(s)E_a(s), as in (6). Ea(s)={t∈{0,…,T}:s<t,a≤D(s,t)},qa(s)=min⁡Ea(s).E_a(s)=\{t\in\{0,\ldots,T\}:s<t,\ a\le D(s,t)\}, \qquad q_a(s)=\min E_a(s).(6)

For a state ss of SS and a positive integer aa, a greedy checkpoint sequence of distance aa in SS starting at ss is a sequence of states s=t0<t1<⋯<tR≤Ts=t_0<t_1<\cdots<t_R\le T satisfying (7); each interval between consecutive checkpoints is a complete batch, and RR is the number of these batches. D(tj,tj+1)=a(0≤j<R),s≤u≤v≤T,2a−1≤D(u,v)⇒∃j∈{1,…,R},u<tj≤v.\begin{gathered} D(t_j,t_{j+1})=a\qquad(0\le j<R),\\ s\le u\le v\le T,\quad 2a-1\le D(u,v) \quad\Longrightarrow\quad \exists j\in\{1,\ldots,R\},\quad u<t_j\le v. \end{gathered}(7) Write G(s,a)G(s,a) for the library’s chosen greedy checkpoint sequence, and R(s,a)R(s,a) for its number of complete batches.

The step set of an interval with endpoints u,v∈{0,…,T}u,v\in\{0,\ldots,T\} is (u,v]={r∈{0,…,T}:u<r≤v}(u,v]=\{r\in\{0,\ldots,T\}:u<r\le v\}. A finite family CC of pairs of states of SS is step-disjoint when distinct pairs have disjoint step sets, as in (8). (u,v]∩(u′,v′]=⌀((u,v),(u′,v′)∈C,(u,v)≠(u′,v′)).(u,v]\cap(u',v']=\varnothing \qquad\bigl((u,v),(u',v')\in C,\ (u,v)\ne(u',v')\bigr).(8)✦

The Claim

Theorem 1. Let SS be a rank kk sweep sequence. For a state ss and a positive integer aa with Ea(s)≠⌀E_a(s)\ne\varnothing, the next checkpoint satisfies D(s,qa(s))=a.D(s,q_a(s))=a.(9)✦ Let d≥1d\ge1 be an integer, and let CC be a finite step-disjoint family of pairs (u,v)(u,v) with u≤vu\le v and D(u,v)≥dD(u,v)\ge d. Then |C|≤R(0,⌈d/2⌉).|C|\le R\bigl(0,\lceil d/2\rceil\bigr).(10)✦

In the paper, the result reads: fix a rank and an integer d≥1d\ge1, put a=⌈d/2⌉a=\lceil d/2\rceil, start at the first state and end each batch at the first subsequent state at distance aa from its start, repeating while possible; if RR complete batches result, every collection of intervals with disjoint step sets and endpoint distance at least dd has at most RR members.

What Is Checked

The checkpoint identity (9) and packing bound (10) are stated over finite rank sweep sequences, with positive distance thresholds and, for the packing bound, ordered step-disjoint intervals. For every starting state ss and positive integer aa, the chosen greedy checkpoint sequence has consecutive checkpoint distance aa, and every interval with s≤u≤vs\le u\le v and D(u,v)≥2a−1D(u,v)\ge 2a-1 contains one of its later checkpoints in (u,v](u,v].✦