If $cn^2$ lines each hold $>3$ of $n$ points, must some line hold $h_c(n)\to\infty$? (Erdős #102)
Statement
Fix $c>0$. Define $h_c(n)$ to be the largest integer $h$ with the property that every set of $n$ points in $\mathbb{R}^2$ which determines at least $cn^2$ lines, each containing more than three of the points, must contain some line with at least $h$ of the points. Estimate $h_c(n)$. In particular, is it true that for every fixed $c>0$ one has $h_c(n)\to\infty$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred) determining the growth order of $h_c(n)$ for each fixed $c>0$ — in particular settling whether $h_c(n)\to\infty$ — with matching upper and lower bounds, OR a construction proving $h_c(n)=O_c(1)$ (an explicit family with at least $cn^2$ lines each having more than three points, yet no line with more than a bounded number of points). ADVANCES (each independently checkable): (a) an improved upper-bound construction beating the best bound stated in the background ($h_c(n)\ll n^{1/\log(1/c)}$), delivered as explicit points plus a verifiable incidence count; (b) a proof of a nontrivial lower bound — for example that $h_c(n)\ge 5$, or any fixed constant, is forced for all large $n$ at a given $c$ — with proof or a machine-checkable finite-case certificate; (c) a rigorous reduction or a conditional resolution under a clearly stated hypothesis. Compare any bound to the background's. Deliver the proof file, the explicit configuration plus incidence certificate, or the search/SAT code plus certificate.
Background
A problem of Erdős and Purdy [Er92e; Er95; Er97c]; tagged 'geometry' (point-line incidences); no prize attached. Frontier: it is not even known whether $h_c(n)\ge 5$ — that is, whether having $\gg n^2$ lines each with more than three points forces a single line with five points; this is tied to the venue-neighbouring problem Erdős #101 (erdosproblems.com/101, also on this list, on the number of four-point lines). It is easy to see $h_c(n)\ll_c n^{1/2}$, and Erdős [Er95] at one point suggested a matching lower bound $h_c(n)\gg_c n^{1/2}$ might hold. Zach Hunter pointed out that this is false — even with 'more than three points' replaced by 'more than $k$ points' — using the grid $\{1,\ldots,m\}^d$ with $n\approx m^d$: every line meets it in $\ll_d n^{1/d}$ points, while $\gg_d n^2$ pairs of points lie on $k$-rich lines, and a generic projection into $\mathbb{R}^2$ preserves these properties; this yields the upper bound $h_c(n)\ll n^{1/\log(1/c)}$. Thus the growth rate of $h_c(n)$, and even whether it tends to infinity, is open. Listed as open on erdosproblems.com/102 (fetched 2026-07-13, status 'open'); no formalisation exists. Attacker's tool: explicit grid/projection and algebraic constructions to lower the $n^{1/\log(1/c)}$ upper bound (or bound $h_c$ from below), together with exact small-$n$ SAT/search to decide whether $h_c(n)\ge 5$ (or any fixed constant) is forced in concrete regimes.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #102 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #101 (related: number of four-point lines; T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.