A power saving over Dey's bound for planar halving lines

For a set $P$ of $n$ points in the plane in general position ( $n$ even), a halving line passes through two points of $P$ and leaves $(n-2)/2$ points on each side. Lovasz (1971) and Erdos, Lovasz, Simmons and Straus (1973) introduced the problem of determining the maximum number $h(n)$ of halving lines (and more generally of $k$ -sets), proving $O(n^{3/2})$ and constructing $\Omega(n\log n)$ . Dey (1998) proved $h(n)=O(n^{4/3})$ ; the best lower bound is $n e^{\Omega(\sqrt{\log n})}$ (Toth, Nivasch). What is the true order of $h(n)$ ; in particular, can Dey's exponent $4/3$ be improved?

Result: Proved(see note)
Status: Partial result
AI contribution: AI-discovered
Method: Argument
Field: Discrete and computational geometry; k-sets
Posed by: L. Lovasz, On the number of halving lines (1971); P. Erdos, L. Lovasz, A. Simmons and E. G. Straus, Dissection graphs of planar point sets (1973)
Year posed: 1971
Years open: 55y
Solved: 2026-09-25
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Lean-checked, statement unaudited
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 42 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: there are absolute $\varepsilon>0$ , $C$ , $n_0$ with $h(P)\le Cn^{4/3-\varepsilon}$ for every even $n\ge n_0$ and every $n$ -point planar set with no three collinear. Theorem 1.2 bounds the switches at every rank uniformly by $CN^{4/3-\varepsilon}$ , and Corollary 1.3 gives $O(n(k+1)^{1/3-\varepsilon_0})$ $k$ -sets for $1\le k\le n/2$ (also for levels in line arrangements). The constants and exponent are ineffective; no numerical value of $\varepsilon$ is given. It does not determine the order of $h(n)$ , which could still lie anywhere between $n e^{\Omega(\sqrt{\log n})}$ and $n^{4/3-\varepsilon}$ .

What the AI did

Produced by an unreleased internal OpenAI model as part of the openai/math release (pinned commit adc7f12). The release README says results were produced by one fixed procedure averaging about three hours of ChatGPT Pro thinking compute each; this result is not among the README exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored as OpenAI with no human author named. A Lean formalization of the main bounds accompanies it (Comparator challenge HalvingLines).

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction, Theorems 1.1 and 1.2 and Corollary 1.3 of the TeX source, read against the halving-line problem as cited. Lean: Comparator challenge HalvingLines, declaration OAI.PlanarHalving.power_bounds. This challenge is not in lean/formalization.yaml; its JSON config and solution module exist at the pinned commit. Its statement was read here: there exist $\varepsilon>0$ , $C$ , $n_0$ such that every even $n\ge n_0$ and every injective planar configuration with no three collinear has at most $Cn^{4/3-\varepsilon}$ unordered halving pairs; plus a uniform $Cn^{4/3-\varepsilon}$ bound on rank switches for generic configurations. That is the headline. The $k$ -sensitive corollary $O(n(k+1)^{1/3-\varepsilon_0})$ is not formalized. Not rebuilt here. The paper states the proof is nonquantitative.

A power saving over Dey's bound for planar halving lines

What was actually shown

What the AI did

Verification

Sources

Discussion