OctoInformBeta

OpenAI preprint, September 2026 · §8. From activity packing to a power saving

Proposition 8.1: An absolute exponent below 4/34/3 applies to every rank of a generic planar configuration

Activity packing gives uniform switch bounds.

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

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 planar configuration. The rank-switch problem concerns exchanges across a fixed position in the projection order as the slope varies.

For planar points p,q,rp,q,r and a real slope ss, the pair slope s(p,q)s(p,q), sweep projection πs(p)\pi_s(p) and orientation determinant orient⁡(p,q,r)\operatorname{orient}(p,q,r) are the real quantities given by (1). s(p,q)=q2−p2q1−p1,πs(p)=p2−sp1,orient⁡(p,q,r)=det⁡(q−p,r−p).\begin{aligned} s(p,q)&=\frac{q_2-p_2}{q_1-p_1}, &\pi_s(p)&=p_2-sp_1,\\ \operatorname{orient}(p,q,r)&=\det(q-p,r-p). \end{aligned}(1) A configuration PP is in general position if it is injective and the orientation determinant in (1) is nonzero for every three distinct indices.✦ A generic configuration P:In→ℝ2P:I_n\to\mathbb R^2 is a configuration in general position whose first coordinates are pairwise distinct, whose unordered point pairs have pairwise distinct slopes, and for which no point common to the open segments of two distinct point pairs belongs to the closed segment of a third distinct point pair.✦ Unordered pairs are represented by indices i<ji<j.

The below-pair count Bij(P)B_{ij}(P) is the number of indices satisfying the strict projection inequality in (2). Bij(P)=#{ℓ∈In:πs(P(i),P(j))(P(ℓ))<πs(P(i),P(j))(P(i))}.B_{ij}(P)=\#\{\ell\in I_n: \pi_{s(P(i),P(j))}(P(\ell))<\pi_{s(P(i),P(j))}(P(i))\}.(2)✦ For a configuration P:In→ℝ2P:I_n\to\mathbb R^2 and an integer rank k≥0k\ge0, the rank-switch count Sk(P)S_k(P) is the number of unordered pairs with below-pair count k−1k-1 when 0<k<n0<k<n, and is zero otherwise, as in (3). Sk(P)={#{(i,j)∈In2:i<j,Bij(P)=k−1},0<k<n,0,otherwise.S_k(P)= \begin{cases} \#\{(i,j)\in I_n^2:i<j,\ B_{ij}(P)=k-1\},&0<k<n,\\ 0,&\text{otherwise}. \end{cases}(3)✦

Sweeps and Activity

A marked set M⊆InM\subseteq I_n is projection-separated at slope ss if πs(P(i))<πs(P(j))\pi_s(P(i))<\pi_s(P(j)) for every i∈Mi\in M and j∉Mj\notin M.✦ The directed set distance d(M,N)d(M,N) between marked sets M,N⊆InM,N\subseteq I_n is the number |M\N||M\setminus N| of indices in MM that are absent from NN.✦ A rank kk sweep sequence SS with TT steps consists of slopes sts_t and marked sets Mt⊆InM_t\subseteq I_n, 0≤t≤T0\le t\le T, with MtM_t projection-separated at sts_t and the conditions (4). s0<⋯<sT,|Mt|=k(0≤t≤T),d(Mt,Mt+1)≤1(0≤t<T).s_0<\cdots<s_T,\qquad |M_t|=k\quad(0\le t\le T),\qquad d(M_t,M_{t+1})\le1\quad(0\le t<T).(4)✦

The critical slopes of PP form the set 𝒞(P)={s(P(i),P(j)):i,j∈In,i≠j}\mathcal C(P)=\{s(P(i),P(j)):i,j\in I_n,\ i\ne j\}.✦ A critical slope traversal of a finite set 𝒞⊂ℝ\mathcal C\subset\mathbb R is a strictly increasing list c0,…,cm+1c_0,\ldots,c_{m+1} whose interior cuts are precisely 𝒞\mathcal C.✦ The canonical traversal of a finite set 𝒞⊂ℝ\mathcal C\subset\mathbb R is the increasing list of its elements with an exterior cut on either side.✦ The intercritical sample slopes sts_t of a critical slope traversal c0,…,cm+1c_0,\ldots,c_{m+1} are the midpoints in (5). st=ct+ct+12(0≤t≤m).s_t=\frac{c_t+c_{t+1}}2\qquad(0\le t\le m).(5)✦ For a generic configuration and 0≤k≤n0\le k\le n, the canonical rank kk sweep S(P,k)S(P,k) is a rank sweep sequence of (4) with mm steps, where mm is the interior-cut count of the canonical traversal of 𝒞(P)\mathcal C(P).✦

For a finite family of marked sets (Mi)i∈J(M_i)_{i\in J} and a reference index i0∈Ji_0\in J, the active set A(M;i0)⊆InA(M;i_0)\subseteq I_n consists of indices whose membership differs from that in Mi0M_{i_0}.✦ For a sweep SS, the interval active set AS[u,v]A_S[u,v] is the set of indices whose membership in some state from uu through vv differs from their membership in state uu.✦ The activity size aS(u,v)a_S(u,v) of a sweep SS is the cardinality of its interval active set when u≤vu\le v and is zero when u>vu>v, as in (6), where △\triangle denotes symmetric difference.✦ A(M;i0)=⋃i∈J(Mi△Mi0),AS[u,v]=⋃u≤t≤v(Mt△Mu)(u≤v),aS(u,v)={|AS[u,v]|,u≤v,0,u>v.\begin{aligned} A(M;i_0)&=\bigcup_{i\in J}(M_i\mathbin{\triangle}M_{i_0}),\\ A_S[u,v]&=\bigcup_{u\le t\le v}(M_t\mathbin{\triangle}M_u) \qquad(u\le v),\\ a_S(u,v)&=\begin{cases}|A_S[u,v]|,&u\le v,\\0,&u>v.\end{cases} \end{aligned}(6) Sweep intervals are step-disjoint when their step-index sets {u,…,v−1}\{u,\ldots,v-1\} are disjoint.

A greedy activity checkpoint system for a sweep SS, initial state uu and integer threshold b>0b>0 is an increasing list u=t0<⋯<tg≤Tu=t_0<\cdots<t_g\le T satisfying (7), with activity measured by (6). b≤aS(tj,tj+1)≤b+1(0≤j<g),aS(tg,T)<b.b\le a_S(t_j,t_{j+1})\le b+1\quad(0\le j<g),\qquad a_S(t_g,T)<b.(7)✦ For a sweep SS, an initial state uu and an integer threshold b>0b>0, the canonical activity checkpoints form a greedy activity checkpoint system satisfying (7).✦ For an integer threshold b>0b>0, the checkpoint count gb(P,k)g_b(P,k) is the number gg of intervals between consecutive canonical activity checkpoints when S=S(P,k)S=S(P,k) and u=0u=0.

For A⊆InA\subseteq I_n, let eA:I|A|→Ae_A:I_{|A|}\to A be its increasing enumeration.✦ The induced point configuration P|A:I|A|→ℝ2P|_A:I_{|A|}\to\mathbb R^2 is the restriction with this indexing, as in (8). (P|A)(i)=P(eA(i)).(P|_A)(i)=P(e_A(i)).(8)✦

For integers q≥4q\ge4 and n≥4qn\ge4q, the activity scale bq(n)b_q(n) is the integer given by (9). bq(n)=⌊nq⌋−1.b_q(n)=\left\lfloor\frac nq\right\rfloor-1.(9)

The Claim

Theorem 1 (Activity packing and rank-switch bounds). There is an integer q≥4q\ge4 such that every generic P:In→ℝ2P:I_n\to\mathbb R^2 with n≥4qn\ge4q, at every rank 0≤k≤n0\le k\le n, satisfies the packing estimate (10) at the scale (9). gbq(n)(P,k)+1≤q4/32.g_{b_q(n)}(P,k)+1\le\frac{q^{4/3}}2.(10)✦

For every generic P:In→ℝ2P:I_n\to\mathbb R^2, rank 0≤k≤n0\le k\le n and integer b>0b>0, there are subsets Aj⊆InA_j\subseteq I_n and integer ranks rjr_j, indexed by 0≤j≤gb(P,k)0\le j\le g_b(P,k), giving the switch decomposition (11); the induced configurations are those of (8). |Aj|≤b+1,0≤rj≤|Aj|(0≤j≤gb(P,k)),Sk(P)≤∑j=0gb(P,k)Srj(P|Aj).\begin{gathered} |A_j|\le b+1,\qquad 0\le r_j\le|A_j| \qquad(0\le j\le g_b(P,k)),\\ S_k(P)\le\sum_{j=0}^{g_b(P,k)}S_{r_j}(P|_{A_j}). \end{gathered}(11)✦

For each integer q≥4q\ge4, there is a real ε\varepsilon satisfying the strict exponent conditions (12). ε>0,43−ε>0,q4/32≤q4/3−ε.\varepsilon>0,\qquad \frac43-\varepsilon>0,\qquad \frac{q^{4/3}}2\le q^{4/3-\varepsilon}.(12)✦

Fix an integer q≥4q\ge4 and a real β>0\beta>0. Suppose that gbq(n)(P,k)+1≤qβg_{b_q(n)}(P,k)+1\le q^\beta for every generic nn-point configuration with n≥4qn\ge4q and every rank 0≤k≤n0\le k\le n. Then every generic nn-point configuration, including n=0n=0, satisfies the induction bound (13) at every such rank. Sk(P)≤(4q)2nβ.S_k(P)\le(4q)^2n^\beta.(13)✦

There are absolute real constants ε>0\varepsilon>0 and CC such that every generic P:In→ℝ2P:I_n\to\mathbb R^2 with n≥1n\ge1 satisfies the uniform bound (14) for the switch counts of (3) at every rank 0≤k≤n0\le k\le n. Sk(P)≤Cn4/3−ε.S_k(P)\le Cn^{4/3-\varepsilon}.(14)✦

In the paper, the result reads: if for every η>0\eta>0 there is Rη<∞R_\eta<\infty such that, for every generic planar NN-point configuration, every rank and every integer 1≤b≤N1\le b\le N with N/b≥RηN/b\ge R_\eta, any collection of step-disjoint intervals of activity at least bb has at most η(N/b)4/3\eta(N/b)^{4/3} members, then there are absolute ε>0\varepsilon>0 and CC such that every such rank sweep has at most CN4/3−εCN^{4/3-\varepsilon} switches.

What Is Checked

The statements concern indexed generic planar configurations at all ranks, their canonical rank sweeps and canonical activity checkpoints, and the induced configurations on subsets of their indices.