OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

§1 (setting): halving pairs and generic rank sweeps: Side counts, general position and genericity for indexed planar configurations

Halving pairs and switches of projection ranks.

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

Halving pairs concern the numbers of points on the two sides of a determined line. Rank switches concern the order of projected heights as the direction varies. The configurations are indexed, so each pair is counted using its indices in increasing order.

The Definition

Definition 1. A point pp of the plane is an ordered pair of real numbers, as in (1): ℝ2=ℝ×ℝ.\mathbb{R}^2=\mathbb{R}\times\mathbb{R}.(1)✦ For a nonnegative integer nn, let In={i∈ℤ:0≤i<n}I_n=\{i\in\mathbb{Z}:0\le i<n\}. An indexed configuration of nn planar points is a map P:In→ℝ2P:I_n\to\mathbb{R}^2; write Pi=(xi,yi)P_i=(x_i,y_i) and En={(i,j)∈In2:i<j}E_n=\{(i,j)\in I_n^2:i<j\} for its unordered index pairs.

The orientation determinant D(p,q,r)D(p,q,r) of three planar points is the signed area determinant in (2), where p=(px,py)p=(p_x,p_y), q=(qx,qy)q=(q_x,q_y) and r=(rx,ry)r=(r_x,r_y): D(p,q,r)=(qx−px)(ry−py)−(qy−py)(rx−px).D(p,q,r)=(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).(2)✦ A configuration PP is in general position if its points are distinct and its orientation determinants satisfy (3): GP⁡(P)quad⇔{Pi≠Pjfor i≠j,D(Pi,Pj,Pl)≠0for pairwise distinct i,j,l∈In.\operatorname{GP}(P)quad\Longleftrightarrow\quad \left\{ \begin{aligned} &P_i\ne P_j &&\text{for }i\ne j,\\ &D(P_i,P_j,P_l)\ne0 &&\text{for pairwise distinct }i,j,l\in I_n. \end{aligned} \right.(3)✦

The left-side count Lij(P)L_{ij}(P) is the number of indexed points with positive orientation relative to Pi,PjP_i,P_j, as in (4): Lij(P)=#{l∈In:D(Pi,Pj,Pl)>0}.L_{ij}(P)=\#\{l\in I_n:D(P_i,P_j,P_l)>0\}.(4)✦ The halving-pair count h(P)h(P) is the number of unordered index pairs satisfying the two side-count conditions in (5): h(P)=#{(i,j)∈En:Lij(P)=Lji(P)=⌊max⁡{n−2,0}2⌋}.h(P)=\#\left\{(i,j)\in E_n: L_{ij}(P)=L_{ji}(P)= \left\lfloor\frac{\max\{n-2,0\}}{2}\right\rfloor\right\}.(5)✦

The slope sl⁡(p,q)\operatorname{sl}(p,q) of two planar points is the quotient in (6), with division by zero assigned the value zero: sl⁡(p,q)=qy−pyqx−px.\operatorname{sl}(p,q)=\frac{q_y-p_y}{q_x-p_x}.(6)✦ For e=(i,j)∈Ene=(i,j)\in E_n, write σe=sl⁡(Pi,Pj)\sigma_e=\operatorname{sl}(P_i,P_j), ℓe=[Pi,Pj]\ell_e=[P_i,P_j] for the closed segment, and ℓe∘=(Pi,Pj)\ell_e^\circ=(P_i,P_j) for the open segment. A generic configuration PP is a configuration in general position satisfying the coordinate, slope and segment conditions in (7): Generic⁡(P)⇔{GP⁡(P),xi≠xjfor i≠j,σe≠σffor distinct e,f∈En,ℓe∘∩ℓf∘∩ℓg=⌀for pairwise distinct e,f,g∈En.\operatorname{Generic}(P)\quad\Longleftrightarrow\quad \left\{ \begin{aligned} &\operatorname{GP}(P),\\ &x_i\ne x_j &&\text{for }i\ne j,\\ &\sigma_e\ne\sigma_f &&\text{for distinct }e,f\in E_n,\\ &\ell_e^\circ\cap\ell_f^\circ\cap\ell_g=\varnothing &&\text{for pairwise distinct }e,f,g\in E_n. \end{aligned} \right.(7)✦

The below count Bij(P)B_{ij}(P) is the number of indexed points whose projected height at slope sl⁡(Pi,Pj)\operatorname{sl}(P_i,P_j) is strictly less than that of PiP_i, as in (8): Bij(P)=#{l∈In:yl−sl⁡(Pi,Pj)xl<yi−sl⁡(Pi,Pj)xi}.B_{ij}(P)=\#\{l\in I_n: y_l-\operatorname{sl}(P_i,P_j)x_l <y_i-\operatorname{sl}(P_i,P_j)x_i\}.(8)✦ For a nonnegative integer kk, the rank-switch count Sk(P)S_k(P) is the pair count in (9): Sk(P)={#{(i,j)∈En:Bij(P)=k−1},0<k<n,0,k=0 or k≥n.S_k(P)= \begin{cases} \#\{(i,j)\in E_n:B_{ij}(P)=k-1\},&0<k<n,\\ 0,&k=0\text{ or }k\ge n. \end{cases}(9)✦

In the paper, the result reads: for an even nn and an nn-point planar set PP with no three collinear, a halving pair leaves (n−2)/2(n-2)/2 other points in each open halfplane and h(P)h(P) counts unordered pairs; a generic set additionally has distinct first coordinates and distinct determined slopes, with no proper intersection of two determined segments lying on a third determined segment; for 0≤k≤n0\le k\le n, the sweep at slope ss marks the kk smallest values of y−sxy-sx, and Sk(P)S_k(P) counts exchanges as ss increases from −∞-\infty to +∞+\infty.

What Is Checked

These definitions are stated for every finite indexed configuration P:In→ℝ2P:I_n\to\mathbb{R}^2 and every nonnegative rank kk.