How many 4-point lines can $n$ points with no 5 collinear span? Prove the count is $o(n^2)$ (Erdős #101)
Statement
Let $n$ points be given in $\mathbb{R}^2$ with no five of them on a common line (so every line meets the set in at most four points). Prove that the number of lines containing exactly four of the points is $o(n^2)$ as $n\to\infty$. Equivalently: is it true that for every $\epsilon>0$ there is an $n_0$ such that any configuration of $n\ge n_0$ points with no five collinear determines fewer than $\epsilon n^2$ four-point lines?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable preferred) that every $n$-point planar configuration with no five collinear has $o(n^2)$ four-point lines — OR a disproof: an explicit infinite family of configurations with no five collinear and at least $c\,n^2$ four-point lines for some fixed $c>0$, given with a verifiable coordinate description and incidence count. ADVANCES (each independently checkable): (a) an improved lower-bound construction beating the best bound stated in the background (currently $n^{2-O(1/\sqrt{\log n})}$ four-point lines with no five collinear), delivered as explicit coordinates plus a machine-checkable incidence certificate; (b) a nontrivial upper bound $o(n^2)$ under an added hypothesis, or an unconditional bound of the form $O(n^2/\phi(n))$ with $\phi(n)\to\infty$, with proof; (c) new exact values or improved lower bounds for the maximal number of four-point lines (OEIS A006065) at specific $n$, with the search program and a certificate. Deliver the proof file, the explicit configuration plus incidence certificate, or the search code plus extended table.
Background
Posed by Erdős in several places [Er84; Er87b, p.170; Er90; Er92e; Er95, p.181; Er97c, p.66]; tagged 'geometry' (point-line incidences). Erdős offered $100 for a solution. Frontier: there are constructions of $n$ points with $\sim n^2/6$ collinear triples and no four points on a line, due to Burr, Grünbaum and Sloane [BGS74] and to Füredi and Palásti [FuPa84]. For four-point lines, Grünbaum [Gr76] built a set with $\gg n^{3/2}$ of them, and Erdős guessed $n^{3/2}$ might be the correct order — but this guess is now known to be false: Solymosi and Stojaković [SoSt13] constructed $n$-point sets with no five collinear and at least $n^{2-O(1/\sqrt{\log n})}$ lines containing exactly four points, so the truth is $n^{2-o(1)}$, only just below the conjectured $o(n^2)$ ceiling. Related problems: Erdős #102 (the venue neighbour on this list, on how many points a line must contain when $\gg n^2$ lines are $3$-rich), #669, and the general-position generalisation Erdős #588/#589 (on the venue as 'Compute $\alpha_4(n)$ ... no 4 on a line'). This is Problem 71 on Ben Green's open-problems list. The maximal number of four-point lines is tracked as OEIS A006065. A Lean formalisation exists. Listed as open on erdosproblems.com/101 (fetched 2026-07-13, status 'open'). Attacker's tool: extremal constructions (algebraic curves and lattice-projection designs in the style of Solymosi–Stojaković) to push the lower bound toward $n^2$; exact small-$n$ search to extend A006065; and Szemerédi–Trotter-type incidence bounds toward the $o(n^2)$ upper bound.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #101 (T. F. Bloom) | website |
| REF-02 | OEIS A006065 — maximal number of lines through exactly four of n points (orchard-type) | website |
| REF-03 | B. Green, Open problems in additive combinatorics/geometry (Problem 71) | website |
| REF-04 | Lean formalisation of Erdős #101 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.