OctoInformBeta

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

Theorem 2.1: Uniform savings for intervals with disjoint step sets and embedded exchange batches

A cubic bound for sweep activity.

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 sweep of lines through a planar configuration gives a changing set of kk points below the sweeping line. The question concerns collections of intervals during which many points change membership.

A planar configuration is an indexed map P:{0,…,n−1}→ℝ2P:\{0,\ldots,n-1\}\to\mathbb R^2, where a planar point is a pair of real numbers.✦ For planar points p,q,rp,q,r, the orientation determinant and the slope are defined by (1): or⁡(p,q,r)=det⁡(q−p,r−p),m(p,q)=q2−p2q1−p1.\operatorname{or}(p,q,r)=\det(q-p,r-p), \qquad m(p,q)=\frac{q_2-p_2}{q_1-p_1}.(1) A planar configuration PP is in general position if PP is injective and or⁡(Pi,Pj,Pℓ)≠0\operatorname{or}(P_i,P_j,P_\ell)\ne0 for distinct indices i,j,ℓi,j,\ell.✦ A planar configuration PP is generic if it is in general position, its first coordinates are pairwise distinct, its unordered point pairs have pairwise distinct slopes, and, for any three distinct unordered pairs, the intersection of the open segments of the first two pairs is disjoint from the closed segment of the third pair.✦ Unordered pairs are represented by indices i<ji<j.

The sweep projection πs\pi_s at slope ss is the function in (2): πs(x,y)=y−sx.\pi_s(x,y)=y-sx.(2)✦ A marked set M⊆{0,…,n−1}M\subseteq\{0,\ldots,n-1\} is separated at slope ss if πs(Pi)<πs(Pj)\pi_s(P_i)<\pi_s(P_j) whenever i∈Mi\in M and j∉Mj\notin M.✦ The directed set distance d(M,N)d(M,N) of marked sets MM and NN is |M\N||M\setminus N|.✦

The critical slope set 𝒞(P)\mathcal C(P) of a planar configuration PP is the finite set in (3): 𝒞(P)={m(Pi,Pj):0≤i<j<n}.\mathcal C(P)=\{m(P_i,P_j):0\le i<j<n\}.(3)✦ A traversal (ct)t=0T+1(c_t)_{t=0}^{T+1} of a finite slope set 𝒟\mathcal D is a sequence of cuts c0<⋯<cT+1c_0<\cdots<c_{T+1} whose interior terms are exactly 𝒟\mathcal D.✦ The canonical critical slope traversal (ct)t=0T+1(c_t)_{t=0}^{T+1} of a planar configuration PP is the chosen traversal of 𝒞(P)\mathcal C(P).✦ The intercritical sample slopes sts_t of the canonical critical slope traversal are the midpoints in (4): st=ct+ct+12,0≤t≤T.s_t=\frac{c_t+c_{t+1}}2, \qquad 0\le t\le T.(4)✦

A rank-kk sweep sequence (st,Mt)(s_t,M_t) of a planar configuration PP is a sequence of strictly increasing slopes and kk-element marked sets, separated at their respective slopes, such that consecutive marked sets have directed set distance at most one.✦ For generic PP and 0≤k≤n0\le k\le n, the canonical rank-kk sweep has marked sets (Mt)t=0T(M_t)_{t=0}^T separated at the intercritical sample slopes sts_t, where TT is the size of the canonical critical slope traversal.✦

The active set 𝒜((Ni),i0)\mathcal A((N_i),i_0) of a finite family (Ni)(N_i) relative to a member Ni0N_{i_0} is the set of indices whose membership differs from its membership in Ni0N_{i_0} in at least one member of the family.✦ The interval active set 𝒜[u,v]\mathcal A[u,v] of a sweep (Mt)(M_t) on [u,v][u,v], with u≤vu\le v, is the active set of (Mt)u≤t≤v(M_t)_{u\le t\le v} relative to MuM_u; both sets are given in (5): 𝒜((Ni),i0)=⋃i(Ni△Ni0),𝒜[u,v]=⋃u≤t≤v(Mt△Mu).\mathcal A((N_i),i_0)=\bigcup_i(N_i\mathbin{\triangle}N_{i_0}), \qquad \mathcal A[u,v]=\bigcup_{u\le t\le v}(M_t\mathbin{\triangle}M_u).(5) The activity of [u,v][u,v] is |𝒜[u,v]||\mathcal A[u,v]|. A collection CC of sweep intervals is step-disjoint if the sets of steps (u,v]={u+1,…,v}(u,v]=\{u+1,\ldots,v\} are pairwise disjoint for distinct (u,v)∈C(u,v)\in C.✦

Exchange Batches

A system of RR distance-aa exchange batches on PP is a sequence of strictly increasing slopes τ0<⋯<τR\tau_0<\cdots<\tau_R and kk-element marked sets B0,…,BRB_0,\ldots,B_R, separated at the respective slopes, with the distances in (6): d(Bj,Bj+1)=a,0≤j<R.d(B_j,B_{j+1})=a, \qquad 0\le j<R.(6)✦ A generic batch configuration FF is a system of RR distance-aa exchange batches of rank kk on a generic nn-point configuration, where n,R,an,R,a are positive integers and kk is nonnegative.✦ A sweep embedding (ij)j=0R(i_j)_{j=0}^R of a generic batch configuration FF is a strictly increasing choice of indices i0<⋯<iRi_0<\cdots<i_R in the canonical rank-kk sweep of its underlying configuration, with k≤nk\le n, satisfying (7): Bj=Mij,0≤j≤R.B_j=M_{i_j}, \qquad 0\le j\le R.(7)✦

The Claim

Theorem 1. For every c>0c>0 there is Qc>0Q_c>0 such that every generic batch configuration FF with a sweep embedding and n/a≥Qcn/a\ge Q_c satisfies (8): R3a4≤cn4.R^3a^4\le c n^4.(8)✦ For every δ>0\delta>0 there is Qδ>0Q_\delta>0 such that, whenever PP is generic, 0≤k≤n0\le k\le n, bb is a positive integer and n/b≥Qδn/b\ge Q_\delta, every finite step-disjoint collection CC of intervals of the canonical rank-kk sweep with |𝒜[u,v]|≥b|\mathcal A[u,v]|\ge b for every (u,v)∈C(u,v)\in C satisfies (9): |C|3b4≤219δn4.|C|^3b^4\le 2^{19}\delta n^4.(9)✦

In the paper, the result reads: for every ξ>0\xi>0 there is a finite QξQ_\xi such that, for every generic nn-point configuration, every rank 0≤k≤n0\le k\le n and every integer 1≤b≤n1\le b\le n with n/b≥Qξn/b\ge Q_\xi, any collection of intervals with disjoint step sets and activity at least bb has at most ξ(n/b)4/3\xi(n/b)^{4/3} members.

What Is Checked

The assertions are stated over canonical rank sweeps of generic planar configurations and positive generic batch configurations with sweep embeddings.