Fewer balanced lines through a planar point set

← All digests

Family 183 · Combinatorics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

Place an even number of points in the plane, with no three on one line. Some lines through pairs of points divide all the remaining points equally between their two sides. How many such balanced lines can there be?

This is the halving-line problem. Its formulation is elementary, but it sits at the center of longstanding questions about the complexity of planar separations. The classical general upper bound is of order $n^{4/3}$ for $n$ points.

The manuscript claims a fixed power improvement: at most $Cn^{4/3-\varepsilon}$ halving lines for some absolute $\varepsilon>0$. It also derives improved bounds for small subsets that can be separated by a line and for levels in arrangements of straight lines. The saving is nonquantitative: the proof supplies no numerical value of the exponent improvement.

2. Background and essential definitions

Let $P\subset\mathbb R^2$ contain $n$ points, where $n$ is even and no three points are collinear. An unordered pair $\{a,b\}$ is a halving pair if its line leaves exactly

$$\frac{n-2}{2}$$

other points in each open halfplane. The two defining points lie on the line and are not counted on either side. Because no three points are collinear, distinct pairs determine distinct lines. Counting halving pairs and halving lines therefore gives the same number $h(P)$.

A $k$-set is a subset of $k$ points that can be strictly separated from all remaining points by a line. “Strictly” means no point lies on the separating line. This is a related counting problem for every rank $k$, rather than only a balanced middle split.

A useful way to follow separations is to vary a slope $s$ and mark the $k$ points with smallest values of $y-sx$. These are the points below a suitable line of slope $s$. As the slope changes, one marked point can exchange places with one unmarked point. Such an exchange is a switch.

At middle rank $k=n/2$, the switches correspond to halving pairs. An interval’s activity counts distinct points that change membership somewhere during that interval. It differs from the number of switches and from the difference between the two endpoint marked sets: a point can leave and later return.

3. Development history and previous partial results

Early work by Lovász and by Erdős, Lovász, Simmons and Straus established an $O(n^{3/2})$ upper bound for halving lines. Rotating-line arguments and graphs drawn on the point configuration helped turn the problem into one about crossings.

Pach, Steiger and Szemerédi improved that bound by an iterated-logarithm factor. Dey’s 1998 theorem then gave the bound

$$O\bigl(n(k+1)^{1/3}\bigr)$$

for planar $k$-sets in the range $1\leq k\leq n/2$. At middle rank, this yields the familiar $O(n^{4/3})$ scale. Dey’s use of convex chains and crossing estimates is the finite combinatorial starting point of the present manuscript.

Lower bounds grew much more slowly. The early constructions gave $\Omega(n\log n)$ halving lines. Tóth obtained examples with

$$n\exp\bigl(\Omega(\sqrt{\log n})\bigr)$$

halving pairs, and Nivasch simplified the construction and improved its exponential constant. This exceeds every fixed multiple of $n$, but remains below $n^{1+\delta}$ for every fixed $\delta>0$ as $n$ grows.

Pinchasi related changes in slope-ordered balanced cuts to measure concentration in the plane. The new manuscript develops a related activity perspective, including points that change status and later return.

More recent work improved a lower-order term in the halving-line upper bound while retaining exponent $4/3$. The claimed advance here is a change in that exponent, using geometric information beyond the crossing estimate alone.

4. What the new manuscripts claim

The main theorem states that absolute constants $\varepsilon>0$, $C<\infty$ and $n_0$ exist such that

$$h(P)\leq Cn^{4/3-\varepsilon}$$

for every even $n\geq n_0$ and every $n$-point planar configuration with no three collinear.

An intermediate theorem bounds the number of switches uniformly over all ranks. For a generic $N$-point configuration and any $0\leq k\leq N$,

$$S_k(P)\leq CN^{4/3-\varepsilon}.$$

Here genericity adds distinct first coordinates, distinct determined slopes and some noncoincidence conditions on segment intersections. The paper explains how small perturbations preserve the relevant halving relations, so these auxiliary assumptions do not restrict the final theorem. At ranks zero and $N$, the marked set never changes.

The all-ranks conclusion yields a finer $k$-dependent corollary. For absolute constants $C_0$ and $\varepsilon_0>0$, the number of $k$-sets is at most

$$C_0n(k+1)^{1/3-\varepsilon_0} \qquad(1\leq k\leq n/2).$$

The same bound controls the complexity of the $k$-th level in an arrangement of $n$ nonvertical straight lines, assuming no parallel pair and no three concurrent lines. A level follows points on the lines with exactly $k$ other lines strictly below them; its complexity counts vertices and edge pieces in the resulting polygonal chain.

The constants and size threshold are not effective numerical outputs of the proof. The auxiliary geometric exponents appearing in the argument are not the final value of $\varepsilon$.

5. Why the advance matters

Importance: 4/5. A power improvement over the classical halving-line exponent is a major advance in discrete geometry. The associated $k$-set and line-level bounds affect a broader family of separation-complexity questions.

The improvement is qualitatively stronger than dividing $n^{4/3}$ by a logarithm or adjusting a lower-order term. A fixed positive saving in the exponent eventually beats every such logarithmic improvement.

At the same time, the theorem would not determine the true growth rate. The known lower constructions remain close to linear on the scale of fixed powers, leaving a wide gap. The significance lies in breaking the long-standing upper-bound exponent and in identifying additional geometric restrictions that prevent the classical crossing argument from being sharp for these configurations.

6. The main idea

Turn a sweep into exchange graphs

Take an interval of the slope sweep. Let $L$ be points marked at the beginning but not at the end, and $G$ those marked at the end but not at the beginning. These sets have the same size, say $a$.

Join every point of $L$ to every point of $G$. This produces a complete bipartite exchange graph with $a^2$ edges. Convex and concave chain decompositions control how its edges can cross.

The usual crossing argument limits how many disjoint sweep intervals can each have large activity. At activity scale $b$, it gives an upper bound of order $(n/b)^{4/3}$. The manuscript seeks a uniform improvement that is little-o of this quantity as $n/b$ grows: the ratio to the classical bound must tend to zero.

Examine a hypothetical near-extremal sequence

Suppose the packing bound remained close to sharp. The paper places configurations into compact rank coordinates, which record smoothed proportions of certain chain graphs lying below a point. It then passes to limiting measures describing vertices, edges and crossings.

Rank coordinates preserve ordering information, but can distort ordinary distances. A tiny region in the coordinate square might correspond to an elongated or collapsed region of the original plane. The manuscript therefore uses sweep information from several separated direction ranges.

Monotonicity and almost-everywhere differentiation produce three transverse limiting families of directions. A rigidity statement says that these families prevent collapse after a suitable linear normalization. This is the step that returns meaningful Euclidean geometry to the compact limiting picture.

Show the activity cannot fit

Crossing estimates and the geometric normalization yield a spatial measure with quantitative bounds on how much mass fits inside a small disk or a thin strip. A narrow angular window can then activate points only in a few thin strips, except for points accounted for by boundary crossings.

To control the latter, imagine a token following a marked point through exchanges. Each token crosses the chosen boundary only a bounded number of times. Summing the strip and boundary contributions contradicts the positive amount of activity retained by the limiting construction.

This rules out asymptotic saturation of the classical packing bound. Choosing one sufficiently large fixed scale turns that little-o gain into a contracting recurrence. Iteration gives the fixed exponent saving, even though the limiting argument does not provide its numerical value.

Pass from middle rank to shallow levels

Uniformity over all ranks is needed because restricting attention to the points active in one block changes the rank. It also lets the paper use a shallow cutting: cover a low line-arrangement level by relatively few cells, each crossed by only $O(k+1)$ lines.

Inside each cell the global level becomes one fixed local rank. Applying the all-ranks bound there and summing over cells produces the sharper dependence $n(k+1)^{1/3-\varepsilon_0}$. The argument thus turns a global power saving into a rank-sensitive geometric estimate.

7. Scope, limitations, and open questions

The halving-line theorem assumes an even number of points and no three collinear. Its generality is over all configurations satisfying those conditions, not just random or convex-position sets.

The line-arrangement corollary concerns complete straight lines. It does not assert the same improvement for pseudolines, which may be curved but satisfy analogous crossing rules, or for finite line segments. The geometric rigidity used in the proof is specific to the stated setting.

The exponent improvement is existential. The paper does not give a usable numerical $\varepsilon$, an effective threshold, or a practical finite-size estimate. In particular, the disk and strip exponents used inside the proof should not be substituted into the final theorem.

The sharp order of the maximum number of halving lines remains unresolved by this claim. The gap between the near-linear lower constructions and the improved upper power still leaves substantial room. Related higher-dimensional separation problems are also outside the theorem.

8. Sources and further reading

The manuscript introduces switches and activity before its limiting-measure argument, then derives the $k$-set and straight-line-level consequences at the end.

Primary landmarks include Dey’s classical exponent, Tóth’s lower construction, Nivasch’s refinement, and Pinchasi’s measure-concentration approach. The Agarwal–Aronov–Chan–Sharir paper supplies the shallow-cutting framework used for the level corollary.

Source manuscripts

• M1. OpenAI, A power saving for planar halving lines (September 25, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.