Max number of $k$-rich lines when no $k+1$ points are collinear: is $f_k(n)=o(n^2)$ for $k\ge4$? (Erdős #588)
Statement
Let $f_k(n)$ be minimal such that: any set of $n$ points in $\mathbb{R}^2$ with no $k+1$ of them on a common line contains at most $f_k(n)$ lines passing through at least $k$ of the points. Is it true that $$f_k(n)=o(n^2)$$ for every $k\ge4$?
Acceptance. FULLY RESOLVES: a proof that $f_k(n)=o(n^2)$ for every $k\ge4$, OR a construction together with a proof that $\limsup_n f_k(n)/n^2>0$ for some $k\ge4$ (ruling out $o(n^2)$). Settling a single fixed $k\ge4$ either way counts as a full resolution for that $k$. Provide a machine-checkable proof (preferred) or a complete written proof. ADVANCES: improve the best known lower bound beyond the Solymosi–Stojaković almost-quadratic bound $n^{2-O_k(1/\sqrt{\log n})}$ stated in the background, for some fixed $k\ge4$, with proof; OR prove $f_k(n)=o(n^2)$ under an explicitly stated additional hypothesis; OR compute exact values of $f_k(n)$ for small $n$ with a reproducible search and an optimality certificate, extending the known extremal table. Deliver the proof, or the search code plus the point configurations and certified values.
Background
Posed by Erdős [Er84]; Erdős offered $100 for a solution. Listed as open on erdosproblems.com/588 (fetched 2026-07-13, status 'open', tagged 'geometry'). It generalises Erdős #101 (erdosproblems.com/101), which is the $k=4$ case. There is a trivial upper bound $f_k(n)=O(n^2)$: each line through at least $k$ points accounts for at least $\binom{k}{2}$ of the $\binom{n}{2}$ point-pairs, and no pair lies on two distinct lines, so the whole question is whether the count is in fact $o(n^2)$. The exponent $k\ge4$ is essential: for $k=3$, Sylvester showed $f_3(n)=n^2/6+O(n)$, and Burr–Grünbaum–Sloane [BGS74] and Füredi–Palásti [FuPa84] give constructions with $f_3(n)\ge(1/6+o(1))n^2$. For $k\ge4$, Kárteszi [Ka63] proved $f_k(n)\gg_k n\log n$ (confirming Erdős's earlier conjecture that $f_k(n)/n\to\infty$), and Grünbaum [Gr76] proved $f_k(n)\gg_k n^{1+\frac{1}{k-2}}$. Erdős speculated the latter might be the true order, but Solymosi–Stojaković [SoSt13] constructed point sets with $f_k(n)\gg_k n^{2-O_k(1/\sqrt{\log n})}$ — almost quadratic — so the gap between the known lower bound and the trivial quadratic upper bound is now sub-polynomial. This is closely related to the venue's generalised-orchard problem (Erdős #669), which estimates the analogous rich-line counts without the no-$(k+1)$-collinear restriction; relevant OEIS extremal tables are A006065 ($k=4$ rows) and A008997 ($k=5$ rows). Attacker's tool: computer search over structured point configurations (grids, algebraic-curve and group-law constructions) to build improved lower-bound constructions or to compute exact $f_k(n)$ for small $n$, together with incidence-geometry arguments for the upper side.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #588 (T. F. Bloom) | website |
| REF-02 | OEIS A006065 — Maximal number of 4-tree rows in the n-tree orchard problem | website |
| REF-03 | OEIS A008997 — Orchard problem with 5 trees in a row | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.