SOLVED
This has been resolved in some other way than a proof or disproof.
Given any $n$ points in $\mathbb{R}^2$, the number of $k$-rich lines (lines which contain $\geq k$ of the points) is, provided $k\leq n^{1/2}$,\[\ll \frac{n^2}{k^3}.\]
In
[Er87b] Erdős describes this as a conjecture of himself, Croft, and Purdy.
This is true, and was proved by Szemerédi and Trotter
[SzTr83].
The best possible value of the implied constant is unknown. When $k=n^{1/2}$ the lattice points show that there can be $\geq(2+o(1))n^{1/2}$ many $n^{1/2}$-rich lines. Erdős thought that perhaps this is best possible, but Sah
[Sa87] gave a construction achieving $\geq (3+o(1))n^{1/2}$ many $n^{1/2}$-rich lines.
View the LaTeX source
This page was last edited 02 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1069, https://www.erdosproblems.com/1069, accessed 2026-01-14
