Power savings for planar halving lines and k-sets

The maximum number of halving lines for n points in the plane is below n to the power 4/3 by a fixed margin.

1 paper September 25, 2026 Explained by AI

A halving line passes through two of n points and splits the rest evenly. Since 1998 the best upper bound on their number was about n to the power 4/3. This paper proves the power can be lowered by some fixed amount. The proof gives no value for that amount.

First step

1971

László Lovász, with an n^(3/2) upper bound

Significance

Major

It improves an exponent that had stood since 1998 on a central problem in discrete geometry.

Trust

Formal proof listed

Field

Combinatorics

1 paper

The explanation

Put six points at the corners of a regular hexagon. Draw the line through two of them. Ask whether it leaves the other four split evenly, two on each side. Only the three long diagonals do. Such a pair is a halving pair, and its line is a halving lineSource 1. Move the six points around, keeping no three on one line, and the count changes. A computer search finds six-point arrangements with six halving lines.

How many halving lines can n points have? There are about n²/2 pairs in all, but only a few can split the rest evenly. Lovász, and then Erdős, Lovász, Simmons and Straus, showed the count is at most about n to the power 3/2Source 2. In 1992, Pach, Steiger and Szemerédi shaved this by a very slowly growing factorSource 3. In 1998, Tamal Dey lowered the power to 4/3Source 4. For a million points, n to the 4/3 is a hundred million, while n to the 3/2 is a billion.

From below, the known examples are much smaller. Erdős, Lovász, Simmons and Straus built sets with about n log n halving linesSource 5. Géza Tóth, and later Gabriel Nivasch, built better onesSource 6. But all known examples stay below n to any fixed power above 1Source 7. So the truth lies somewhere between just over n and n to the 4/3. Later work improved smaller terms in the upper bound but kept the power 4/3Source 8.

This paper proves a small drop in the power. Take any large enough even set of n points, with no three on a line. It has at most C times n to the power 4/3 − ε halving lines. Here ε is one fixed number above zero, the same for every setSource 9. The catch is that the proof gives no value for ε, or for CSource 10. It shows a saving exists, but not how big it is.

The paper also claims a matching bound for k-sets. A k-set is a group of k points that a straight line can cut off from the rest. Dey's method bounded their number by about n times (k + 1) to the 1/3. The paper lowers that power of k by a fixed amount tooSource 11. This k-set bound concerns straight lines only, not curved versions of the problemSource 12.

The obstacle was a counting step that had looked tight. Turn a line slowly, and track which points sit below it. Points swap in and out at each halving line. Dey's crossing argument counts how many busy stretches of this sweep can fitSource 13. The new proof shows that count can never be met, up to a constant, for huge sets. To do this it imagines a sequence of near-extreme examples. It then studies the shapes they approach in the limit. Positions measured by rank do not directly give real distancesSource 14. So the paper uses the order of the sweep directions to recover geometric control. A contradiction follows. One fixed scale then feeds a repeating argument, which yields the power savingSource 15.

How sure is this? A computer proof checker called Lean has checked a formal version of the main bound. It says some fixed ε above zero and some C bound the halving pairs, for all large enough even sets. It also covers the related count for every rank of the sweep. The constants are not given as numbers. The k-set corollary is not named in the Lean scope note. No specialist review of the paper has been published.

What it doesn't show. This does not give a numerical value for the saving in the exponent.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if the proof holds. Lean has checked a formal version of the halving-line bound. The saving has no stated value, the k-set corollary is outside the Lean note, and no specialist review is published.

Words used

Halving line: A line through two of the points that leaves the same number of other points on each side.
k-set: A group of k points that a straight line can separate from all the others.
Exponent: The power in a growth rate; n to the 4/3 grows faster than n but slower than n².
Power saving: A lowering of the exponent in a bound by a fixed positive amount.
Lean: A computer program that checks each step of a formally written proof.

The original paper

A power saving for planar halving lines (PDF, opens in a new tab)
September 25, 2026

Lean notes

All quoted lines (15)

A pair of points is a halving pair if its line leaves exactly $(n-2)/2$ other points in each open halfplane.
A power saving for planar halving lines Back to text
The early work of Lov\'asz and of Erd\Hos, Lov\'asz, Simmons and Straus established the $O(n^{3/2})$ scale for halving lines and developed the rotating-line and dissection-graph viewpoint.
A power saving for planar halving lines Back to text
Pach, Steiger and Szemer\'edi improved the upper bound by an iterated-logarithm factor.
A power saving for planar halving lines Back to text
Dey then proved the bound $O(n(k+1)^{1/3})$ for $k$ -sets with $1\le k\le n/2$ , giving $O(n^{4/3})$ for halving lines.
A power saving for planar halving lines Back to text
Erd\Hos, Lov\'asz, Simmons and Straus constructed configurations with $\Omega(n\log n)$ halving lines.
A power saving for planar halving lines Back to text
T\'oth obtained $n\exp(\Omega(\sqrt{\log n}))$ halving pairs, and Nivasch subsequently simplified the construction and improved its exponential constant.
A power saving for planar halving lines Back to text
T\'oth obtained $n\exp(\Omega(\sqrt{\log n}))$ halving pairs, and Nivasch subsequently simplified the construction and improved its exponential constant. These bounds remain far below a fixed power $n^{1+\delta}$ .
A power saving for planar halving lines Back to text
More recently, Alonso, L\'opez and Rodrigo improved a lower-order term in the upper bound while retaining the exponent $4/3$ .
A power saving for planar halving lines Back to text
The improvement is in the exponent and is uniform over all configurations.
A power saving for planar halving lines Back to text
The proof is nonquantitative: it supplies neither a numerical value of $\varepsilon$ nor effective values of $C$ and $n_0$ .
A power saving for planar halving lines Back to text
There are absolute constants $\varepsilon_0>0$ and $C_0<\infty$ such that, for every integer $n\ge2$ and every integer $1\le k\le n/2$ , the number of $k$ -sets of any $n$ -point set $Q\subset\mathbb R^2$ with no three collinear is at most $C_0 n(k+1)^{1/3-\varepsilon_0}.$
A power saving for planar halving lines Back to text
This corollary concerns planar point sets and complete straight lines only; it asserts no corresponding saving for pseudolines or line segments.
A power saving for planar halving lines Back to text
The central estimate concerns disjoint intervals of sweep steps with activity at least $b$ . The usual crossing argument bounds their number by $O((n/b)^{4/3})$ .
A power saving for planar halving lines Back to text
Compact rank coordinates alone do not control physical distances: a small region in the rank square could represent a highly distorted part of the original plane.
A power saving for planar halving lines Back to text
Choosing one sufficiently large fixed scale then gives a contracting recurrence and the power saving in Theorem ….
A power saving for planar halving lines Back to text

Other sources

L. Lovász, “On the Number of Halving Lines”, Annales Univ. Sci. Budapest, Sectio Math. 14 (1971), 107–108 (no online copy found)
T. K. Dey, “Improved Bounds for Planar k-Sets and Related Problems”, Discrete & Computational Geometry 19(3) (1998), 373–382
G. Tóth, “Point Sets with Many k-Sets”, Discrete & Computational Geometry 26(2) (2001), 187–194
G. Nivasch, “An Improved, Simple Construction of Many Halving Edges”, Contemporary Mathematics 453 (2008), 299–305
openai/math release notes (2026): model provenance and review status manuscripts and supporting proof artifacts produced by an internal OpenAI model

182Power savings for intersective polynomial differences and prime argumentsCombinatorics
172Classification of finite Euclidean Ramsey configurationsCombinatorics
171The hypercube Ramsey conjectureCombinatorics
164Hindman’s finite sums and products conjectureCombinatorics
162Counterexamples to Ryser’s covering conjectureCombinatorics

Browse Combinatorics Open since the 1970s Lean-checked results