Power savings for planar halving lines and k-sets

1 · The essentials

Take an even number of points on a flat surface, with no three lying on one straight line. Choose two points and draw the line through them: the pair counts as a halving pair if equal numbers of the remaining points lie on either side. How many such pairs can one arrangement have? The main result gives a smaller upper limit than the classical bound, lowering the power of the number of points from $4/3$ by a fixed positive amount. This applies to every sufficiently large arrangement satisfying the assumptions, not just to typical arrangements. The repository also reports a related improvement for counting groups of points that a straight line can completely separate from the rest. The main result has a Lean formalization, but the supplied text does not specify its detailed scope or give explicit numerical values for the improvement.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, imagine dots on a sheet of paper and a ruler placed through two dots so that the other dots are split equally between its sides. The result limits how many different pairs can support such a balanced placement; the image does not explain why that limit holds.

Why it matters

The improvement changes the exponent in the classical bound, rather than merely reducing a multiplying constant. The repository summary also reports an improved bound for strictly separable groups of varying sizes, placing the halving-line question within a broader counting problem.

2 · Going further

Let $P$ be a set of $n$ points in the plane with no three collinear. A halving pair is an unordered pair of points whose line leaves equal numbers of the other points in the two open half-planes. The main manuscript states that there are absolute constants $ε > 0$ and $C$ such that, for every sufficiently large even $n$ , the number of halving pairs is at most $C n^{4/3 - ε}$ . The context supplied by the abstract is the classical upper bound $O (n^{4/3})$ .

More generally, the repository summary reports that the number of strictly separable $k$ -subsets is $O (n (k + 1)^{1/3 - ε_{0}})$ for $1 \leq k \leq n /2$ , where $ε_{0} > 0$ is absolute. Here strict separability means that a line places the selected points on one side and all remaining points on the other, with no points on the separating line. This statement retains the assumption that no three points are collinear.

The supplied abstract describes the argument as nonquantitative: it does not supply explicit constants or an explicit positive exponent saving. It gives no further description of the argument's main mechanism, so a proof outline cannot be extracted from this material. Only the main manuscript's abstract is supplied; the broader $k$ -set statement appears in the repository summary, without companion-manuscript details. The main result has a Lean formalization, but the supplied material does not establish which additional claims that formalization covers.

Useful notions

Points and lines in the plane
Counting unordered pairs and subsets
Powers and growth rates
Big-O upper bounds
Separation by a straight line

What was known before / what is new

Before

The main abstract identifies $O (n^{4/3})$ as the classical upper bound for planar halving lines. The supplied text gives no further historical account or earlier bounds for the broader $k$ -set problem.

New

The main result replaces the classical halving-line bound with $O (n^{4/3 - ε})$ for an absolute $ε > 0$ , under the stated assumptions. The repository summary also reports $O (n (k + 1)^{1/3 - ε_{0}})$ strictly separable $k$ -subsets for an absolute $ε_{0} > 0$ . Both improvements are nonquantitative: explicit values for the constants and positive exponent savings are not supplied.

Limits and assumptions

The halving-pair statement assumes a sufficiently large even number of planar points and no three collinear. The reported k-set bound assumes no three collinear and applies for $1 \leq k \leq n /2$ . The main result has a Lean formalization, but its detailed scope is not specified here, so coverage of the broader k-set statement should not be inferred. Explicit constants and exponent savings are not provided, and the supplied text identifies no particular remaining open problem.

Mini glossary

Halving pair: An unordered pair of points whose line leaves equal numbers of the remaining points on either side.
Collinear: Points are collinear when they lie on a single straight line.
Strictly separable k-subset: A selection of k points that a line can place strictly on one side while placing all remaining points strictly on the other.
Big-O upper bound: An upper bound up to a fixed multiplying constant over the stated range.
Power saving: A reduction by a fixed positive amount in the exponent of a growth bound.
Nonquantitative: Establishing the existence of constants or positive savings without supplying explicit numerical values.

Keywords : Halving lines · Planar k-sets · Power savings

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Improves the planar halving-line bound to $O (n^{4/3 - ε})$ for sets with no three collinear and an absolute ε > 0. More generally, an n-point set with no three collinear has $O (n (k + 1)^{1/3 - ε_{0}})$ strictly separable k-subsets for $1 \leq k \leq n /2$ , with an absolute $ε_{0} > 0$ . The constants and positive exponents are nonquantitative.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/183.md

Manuscripts in this family

★

A power saving for planar halving lines

25/09/2026

To be verified

There are absolute constants ε > 0 and C such that every sufficiently large even n-point set in the plane with no three collinear has at most $C n^{4/3 - ε}$ unordered halving pairs. This gives a power saving over the classical $O (n^{4/3})$ bound for planar halving lines. The proof is nonquantitative and does not supply explicit constants.

PDF GitHub folder