OctoInformBeta

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

§2 (setting): states, activity, endpoint distance and batches: Discrete states and their activity, with batches specified by a common endpoint distance

Separating marked sets at increasing slopes.

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 planar sweep selects marked points by their order in a projection that varies with slope. Sampling the sweep gives a sequence of marked subsets; its endpoints and its intermediate states record different aspects of the changes in membership.

A planar point p=(x,y)∈ℝ2p=(x,y)\in\mathbb R^2 is a pair of real numbers.✦ For a nonnegative integer nn, let In={0,…,n−1}I_n=\{0,\ldots,n-1\} and let P:In→ℝ2P:I_n\to\mathbb R^2 be an indexed configuration, with pi=P(i)p_i=P(i). A marked set MM of the indexed configuration PP is a subset of InI_n.

For a finite family ℳ=(Mα)α∈F\mathcal M=(M_\alpha)_{\alpha\in F} of marked sets and a reference index α0∈F\alpha_0\in F, the active set A(ℳ;α0)⊆InA(\mathcal M;\alpha_0)\subseteq I_n is the set of indices whose membership differs from their membership in Mα0M_{\alpha_0} at some member of the family, as given in (1), where △\triangle denotes symmetric difference: A(ℳ;α0)=⋃α∈F(Mα△Mα0).A(\mathcal M;\alpha_0) =\bigcup_{\alpha\in F}(M_\alpha\mathbin{\triangle}M_{\alpha_0}).(1)✦

The Definition

Definition 1. The sweep projection πs:ℝ2→ℝ\pi_s:\mathbb R^2\to\mathbb R at slope s∈ℝs\in\mathbb R is the function given by (2): πs(x,y)=y−sx.\pi_s(x,y)=y-sx.(2)✦

A marked set M⊆InM\subseteq I_n is separated at slope s∈ℝs\in\mathbb R when the condition Sep⁡P(s,M)\operatorname{Sep}_P(s,M) in (3) holds: Sep⁡P(s,M)⇔πs(pi)<πs(pj)for every i∈M and j∈In\M.\operatorname{Sep}_P(s,M) \quad\Longleftrightarrow\quad \pi_s(p_i)<\pi_s(p_j) \quad\text{for every }i\in M\text{ and }j\in I_n\setminus M.(3)✦

The set distance d(M,N)d(M,N) of marked sets M,N⊆InM,N\subseteq I_n is the nonnegative integer defined in (4): d(M,N)=|M\N|.d(M,N)=|M\setminus N|.(4)✦

For nonnegative integers TT and kk, a discrete sweep 𝒮\mathcal S on PP is a sequence of states (st,Mt)(s_t,M_t), with real slopes sts_t and marked sets Mt⊆InM_t\subseteq I_n, satisfying (5): 𝒮=((st,Mt))t=0T,st<st′(0≤t<t′≤T),|Mt|=k,Sep⁡P(st,Mt)(0≤t≤T),d(Mt,Mt+1)≤1(0≤t<T).\begin{gathered} \mathcal S=((s_t,M_t))_{t=0}^{T}, \qquad s_t<s_{t'}\quad(0\leq t<t'\leq T),\\ |M_t|=k,\qquad \operatorname{Sep}_P(s_t,M_t) \quad(0\leq t\leq T),\\ d(M_t,M_{t+1})\leq 1\quad(0\leq t<T). \end{gathered}(5)✦

The interval activity 𝒜𝒮[u,v]⊆In\mathcal A_{\mathcal S}[u,v]\subseteq I_n of a discrete sweep 𝒮\mathcal S on PP with states indexed from 00 to TT, for state indices 0≤u≤v≤T0\leq u\leq v\leq T, is the active set in (6): 𝒜𝒮[u,v]=A((Mt)u≤t≤v;u).\mathcal A_{\mathcal S}[u,v] =A\bigl((M_t)_{u\leq t\leq v};u\bigr).(6)✦

For nonnegative integers R,k,aR,k,a, a system ℬ\mathcal B of RR batches of distance aa on PP, with kk marked points, is a sequence of real slopes rbr_b and marked sets Nb⊆InN_b\subseteq I_n satisfying (7): ℬ=((rb,Nb))b=0R,rb<rb′(0≤b<b′≤R),|Nb|=k,Sep⁡P(rb,Nb)(0≤b≤R),d(Nb,Nb+1)=a(0≤b<R).\begin{gathered} \mathcal B=((r_b,N_b))_{b=0}^{R}, \qquad r_b<r_{b'}\quad(0\leq b<b'\leq R),\\ |N_b|=k,\qquad \operatorname{Sep}_P(r_b,N_b) \quad(0\leq b\leq R),\\ d(N_b,N_{b+1})=a\quad(0\leq b<R). \end{gathered}(7)✦

In the paper, the result reads: states are representative slopes in the complementary intervals of the slopes determined by pairs of configuration points; an interval includes both endpoint states, and its activity |𝒜𝒮[u,v]||\mathcal A_{\mathcal S}[u,v]| counts distinct points changing membership at any intervening step; for two kk-element marked sets MM and M′M', d(M,M′)=|M\M′|=|M△M′|/2d(M,M')=|M\setminus M'|=|M\mathbin{\triangle}M'|/2; a batch of distance aa exchanges the aa points lost between its endpoint states with the aa points gained and contributes all a2a^2 exchange edges joining a lost point to a gained point.

What Is Checked

The sweep and batch definitions (5) and (7) are stated over arbitrary indexed configurations P:In→ℝ2P:I_n\to\mathbb R^2 and nonnegative integers T,k,R,aT,k,R,a, with activity taken over finite families of marked subsets.