Halving lines, rank sweeps, and planar k-sets

Source and verification

This article explains family 183 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Balanced lines and separable subsets

Let $P$ be an even-sized set of $n$ planar points with no three collinear. A halving pair is a pair whose line leaves exactly $(n-2)/2$ other points in each open half-plane. Write $h(P)$ for the number of unordered halving pairs. Under the no-three-collinear assumption, these are also distinct halving lines.

A $k$-set is a subset of $k$ points strictly separable from the rest by a line. These notions measure the complexity of planar orderings under changes of direction.

Manuscript claim

There are absolute $\epsilon >0$, $C<\infty$, and $n_0$ such that $h(P)\le C{n}^{4/3-\epsilon }$ for every even $n\ge n_0$ and every such configuration. The exponent and constants are nonquantitative. (OpenAI, 2026)

The saving is uniform over configurations. The proof does not provide a numerical $\epsilon$, and it does not claim a corresponding improvement for pseudolines or arbitrary line segments.

🏷️ Rank sweeps

For a slope $s$, mark the $k$ points with smallest values of $y-sx$. In generic position, increasing $s$ changes the marked set one exchange at a time. Call each exchange a switch, and let $S_k(P)$ be the number of switches over all slopes.

At middle rank, switches are exactly halving pairs. The stronger theorem bounds $S_k(P)$ by $C{N}^{4/3-\epsilon }$ uniformly over every rank in a generic $N$-point configuration. At ranks zero and $N$, no switch occurs.

The generic assumptions include distinct first coordinates and determined slopes, as well as nondegeneracy of segment crossings. The source justifies perturbing the original halving-pair problem into this setting. The all-ranks uniformity is not cosmetic: restricting an interval of switches to its participating points changes the rank.

For a block of sweep steps, its activity is the number of distinct points that change membership during the block. A point can leave and later return, so activity can exceed the size of the difference between the two endpoint marked sets. The proof includes a reduction connecting these two quantities instead of identifying them.

🏷️ From a packing improvement to a power saving

Classical crossing arguments bound the number of disjoint sweep intervals with activity at least $b$ by $O((n/b{)}^{4/3})$. The manuscript proves a uniform little-oh improvement when $n/b\to \infty$.

A little-oh statement can yield a fixed exponent gain through a recurrence. Choose one sufficiently large fixed scale where the improvement beats the loss in subdividing the problem. Iterating at that scale gives a contraction each time, converting repeated constant savings into a power of the total size. This is why an ineffective geometric compactness argument can still establish existence of a positive exponent without calculating its value.

The main geometric work is proving the uniform packing improvement. Suppose it fails and take a near-extremal sequence. For an interval with endpoint differences $L$ and $G$, each of size $a$, the complete bipartite exchange graph between them has $a^2$ edges. Convex and concave chain partitions control its crossings.

🏷️ Rank coordinates and physical geometry

Smoothed counts of chain graphs below a point give bounded rank coordinates. Two separated time windows supply a coordinate pair, and crossing counts imply that a positive portion of edge activity has an absolutely continuous projection into the resulting rank square.

Bounded rank coordinates do not automatically control Euclidean distances. A tiny rank region could correspond to a severely distorted physical configuration. The source therefore uses sweep directions to recover geometry: coordinates from other windows become monotone functions, and their almost-everywhere derivatives force three transverse families of limiting directions.

A local rigidity lemma prevents these three families from collapsing after a suitable linear normalization. The order of limits matters: the proof first fixes a small rank scale and only then moves sufficiently far along the sequence. Interchanging these limits would lose the uniformity used in the geometric conclusion.

🏷️ Strip mass and boundary tokens

The crossing estimates also make edge-endpoint mass absolutely continuous with respect to vertex mass. This permits a positive-activity region whose vertex projection has bounded density in rank coordinates. After transferring to normalized Euclidean space, the source obtains a disk-mass bound $O(r^{32/17})$.

Covering a bounded strip of width $r$ by $O(1/r)$ disks gives the strip estimate

$$O(r^{-1})O(r^{32/17})=O(r^{15/17}).$$

In a narrow angular window, active vertices must lie in a few such strips unless their marked tokens cross the boundary of the selected region. A token follows a marked point through successive exchanges. Each token can cross the relevant boundary only a bounded number of times. Summing the strip and boundary contributions contradicts the retained positive activity.

The exponents $32/17$ and $15/17$ are auxiliary spatial estimates, not the final saving in the halving-line theorem.

🏷️ The dependence on the rank

The manuscript further derives, for $1\le k\le n/2$, a $k$-set bound

$$C_{0}n(k+1{)}^{1/3-{\epsilon }_0}.$$

The same estimate controls the complexity of the $k$th level in a generic arrangement of complete straight lines. A shallow cutting divides that level into $O(n/(k+1))$ cells, each crossed by $O(k+1)$ lines. Applying the all-ranks bound locally gives

$$O\left(\frac{n}{k+1}\right)O\left((k+1{)}^{4/3-{\epsilon }_0}\right),$$

which is the displayed dependence. The family scope page selects halving pairs and switch counts; the full $k$-sensitive corollary is a further manuscript deduction.

🏷️ Key steps and proof outlines

Convert a packing improvement into an exponent improvement

The combinatorial state is a marked set moving through an allowable sequence. A transfer exchanges one marked and one unmarked element. The activity of a block is the number of elements whose marked status changes inside it. Let $F(N)$ denote the maximum number of relevant transfers on $N$ elements, maximizing over the permitted ranks.

The source first proves a little-oh packing statement: for every $\eta >0$, once $N/b$ is large enough, there are at most $\eta (N/b{)}^{4/3}$ step-disjoint blocks having activity at least $b$. The threshold may depend ineffectively on $\eta$. Here is how that qualitative improvement produces a fixed power improvement. (OpenAI, 2026)

Put $a=4/3$, choose $\eta =(4\cdot 2^a{)}^{-1}$, and then fix a sufficiently large integer $q$. For $N\ge 4q$, set $d=\lfloor N/q\rfloor$ and $b=d-1$. Greedily finish a block the first time its activity reaches $b$. A final transfer changes the activity by at most two, so every block has at most $d$ active elements. Since $N/(2q)\le b<N/q$, the packing statement bounds the number of completed blocks by $q^a/4$. Including the final unfinished block still gives at most $q^a/2$ blocks.

Restriction preserves the problem

Outside a block’s active set, marked membership is constant. If that constant marked set has size $c$, restricting to the active elements gives another allowable-sequence problem at fixed rank $k-c$. Thus the block contains at most $F(d)$ transfers. This is why maximizing over ranks belongs in the definition of $F$.

Choose

$$\epsilon =\frac{\log 2}{2\log q},\beta =\frac{4}{3}-\epsilon .$$

Induction now closes because

$$F(N)\le \frac{q^{4/3}}{2}C(N/q{)}^{\beta }=\frac{C{N}^{\beta }}{\sqrt{2}}.$$

The spare factor pays for initial values. The argument explains both the positive exponent saving and the lack of an explicit numerical exponent: $q$ depends on the qualitative packing threshold.

Why too many active blocks contradict boundary transport

The difficult packing input is proved by contradiction through a limiting configuration. The source retains a region $G$ with positive limiting transfer mass and a spatial measure whose disk masses are at most $C{r}^d$, with $d=32/17$. This is a statement about the limiting measure; one should not transfer arbitrary restrictions to $G$ back to the finite configurations without justification.

All relevant forward displacements lie in a cone of aperture less than $\pi$. Choose two linear coordinates increasing on that cone, and use their level sets to form a parallelogram. A marked token moves monotonically in both coordinates, so it crosses the four sides at most four times. With $N$ tokens, the total boundary-crossing budget is at most $4N$.

For disjoint small angular windows $J$, let $b_J$ be normalized boundary traffic, ${\theta }_J$ their angular widths, and ${\mu }_J(G)$ the active mass in $G$. Then ${\sum }_J{b}_J\le 4$ and ${\sum }_J{\theta }_J\le \pi$. Geometric localization confines activity not accounted for by boundary traffic to a bounded number of thin strips. Covering a strip of width $r$ by $O(r^{-1})$ disks converts the disk exponent $d$ into the strip exponent $d-1$, giving

$${\mu }_J(G)\le 2b_J+C{\theta }_J^{d-1}.$$

Sum small windows, then remove the large ones

Let ${\lambda }_J(G)$ be transfer mass and $s_J$ the window’s normalized scale. An endpoint estimate gives ${\lambda }_J(G)\le C{s}_J{\mu }_J(G{)}^{1/3}$. At window size $\delta$, split at $s_J=M{\delta }^{3/4}$. The packing bound makes the total contribution of the large-scale windows at most $C{M}^{-4/3}$.

For the small windows, sum the preceding estimate, use Hölder on the boundary terms, and use concavity on ${\theta }_J^{d-1}$. The source obtains

$${\lambda }_{K_0}(G)\le C{M}^{-4/3}+CM\left({\delta }^{1/12}+{\delta }^{3/68}\right).$$

Here $K_0$ is the retained angular range. First send $\delta \to 0$ with $M$ fixed, then send $M\to \infty$. This contradicts the positive mass retained in $G$. The exponent $3/68$ belongs to this auxiliary summation, not to the final halving-line exponent. The proof architecture is developed in the manuscript’s boundary argument and recurrence section.

See Also

• Planar distance fibers also converts a compactness obstruction into a uniform statement about finite configurations.
• Heilbronn triangle lower bounds uses area constraints rather than rank sweeps to control planar triples.

🏷️ Manuscripts and verification scope

• A power saving for planar halving lines — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page selects halving pairs and uniform level-switch bounds with their respective position assumptions. The manuscript also derives the rank-sensitive k-set and straight-line-level corollary. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. A power saving for planar halving lines.