Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$?

Statement

Let $f_k(n)$ be minimal such that if $n$ points in $\mathbb{R}^2$ have no $k+1$ points on a line then there must be at most $f_k(n)$ many lines containing at least $k$ points. Is it true that $f_k(n) = o(n^2)$ for $k \geq 4$?

Facts

- Prize \$100; status open (erdosproblems.com/588, reflects site-owner belief; "cannot be resolved with a finite computation" since this is an asymptotic-in-$n$ statement, one instance for every fixed $k\geq4$). - Falsifiable: no — an $o(n^2)$ claim over all $n$, for each fixed $k$, is not settleable by any finite computation. - Origin: Erdős [Er84] ("Research problems," Period. Math. Hungar. (1984), 101-103). Also listed as Conjecture 12 in Brass, Moser, Pach's problem-collection book (per the intro of arXiv:1107.0327, which cites it as "[3]"). - A **generalisation of Erdős #101 — four-point lines are $o(n^2)$ if no five on a line, which is exactly the $k=4$ special case (no 5 points on a line, are the 4-point lines $o(n^2)$?). - The restriction to $k\geq4$ is necessary: Sylvester showed $f_3(n) = n^2/6 + O(n)$ exactly (the classical orchard problem, $k=3$, no restriction needed since $f_3$ is already known exactly and is $\Theta(n^2)$, not $o(n^2)$ — so the $k\geq4$ threshold is where the question first becomes open). Burr, Grünbaum, Sloane [BGS74] ("The orchard problem," Geometriae Dedicata (1974)) and Füredi, Palásti [FuPa84] ("Arrangements of lines with a large number of triangles," Proc. AMS (1984)) give constructions with $f_3(n)\geq(1/6+o(1))n^2$. - Known bounds for $k\geq4$: - Kárteszi [Ka63] (1963) proved $f_k(n)\gg_k n\log n$, resolving Erdős's weaker conjecture that $f_k(n)/n\to\infty$. - Grünbaum [Gr76] (1976) proved $f_k(n)\gg_k n^{1+1/(k-2)}$; Erdős speculated this might be the true order of magnitude. - Solymosi & Stojaković, arXiv:1107.0327 (Discrete Comput. Geom. 50 (2013), 811-820) falsify Erdős's speculation: they construct, for every $k>3$, $n$-point sets with no $(k{+}1)$-tuple collinear but $\geq n^{2-c(k)/\sqrt{\log n}}$ collinear $k$-tuples — "reasonably close to the trivial upper bound $O(n^2)$" (their own phrasing). Technique: place points as lattice points on a sphere in a suitably high dimension $d$ (Gauss volume + pigeonhole to find $\gg$ pairs at equal distance $\Rightarrow$ many $k$-term arithmetic progressions collinear on that sphere), then project generically to the plane, preserving all collinearities and the no-$(k{+}1)$-collinear property. - Trivial upper bound**: $O(n^2)$ (each $k$-rich line accounts for $\binom{k}{2}$ point-pairs out of $\binom{n}{2}$ total, giving $f_k(n)\leq \binom{n}{2}/\binom{k}{2} = O_k(n^2)$). The Szemerédi–Trotter corollary for $k$-rich lines, $O(n^2/k^3+n/k)$, is the standard incidence-geometry sharpening — but for *fixed* $k$ (as here) it is still $O_k(n^2)$, i.e. does not give the needed $o(1)$-type saving. No unconditional $o(n^2)$ upper bound is known for any $k\geq4$. - Consequence: the gap between best lower bound ($n^{2-o(1)}$) and best upper bound ($O(n^2)$) is essentially just an $n^{o(1)}$ factor — any resolution (in either direction) requires a genuinely structural argument, not more pair-counting. - Related problems: Erdős #101 — four-point lines are $o(n^2)$ if no five on a line (the $k=4$, no-5-on-line special case), erdos/669 (Erdős [Er97f], the unrestricted analogue: estimate $F_k(n)$/$f_k(n)$ and their limits $/n^2$ without forbidding $k+1$ collinear points), erdos/102 (Erdős–Purdy, a dual question about forced line-multiplicity from $\geq cn^2$ lines with $>3$ points).

Literature state

Not resolved for any $k\geq4$, and the $k=4$ instance (Erdős #101 — four-point lines are $o(n^2)$ if no five on a line) is separately tracked by erdosproblems.com and Ben Green's problem list — both still open as of 2026-07-02. - Solymosi & Stojaković (arXiv:1107.0327) is explicit that their construction shows Erdős's conjecture, *if true*, is essentially sharp (cannot replace the exponent 2 by $2-c$ for any constant $c>0$), and that they see "no way to improve [their] bound significantly" with more advanced lattice-point-counting. They also state directly: "It seems that the key to attack this question would be to understand the group structure behind point sets with many collinear triples. A recent result of Green and Tao — proving the Motzkin-Dirac conjecture — might be an important development in this direction." - That Green–Tao result, arXiv:1208.4714 ("On sets defining few ordinary lines," Ann. of Math. 2013), resolves the adjacent but different unrestricted $k=3$ problem exactly (max 3-rich lines $=\lfloor n(n-3)/6\rfloor+1$ for large $n$, via a structure theorem: point sets with $\leq Kn$ ordinary lines lie, all but $O(K)$ points, on a cubic curve). It does not resolve #588, but it is the acknowledged technical ancestor of the only concrete attack route in the literature. - Ben Green's "100 Open Problems" list (people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf), Problem 69, is precisely the general-$k$ cubic-curve structure conjecture underlying this whole family: fix $k$, let $A\subset\mathbb{R}^2$ have $n$ points with no more than $k$ on any line; if $\geq\delta n^2$ pairs $(x,y)$ have a third point of $A$ on line $xy$, is there a cubic curve containing $\geq c(k,\delta)n$ points of $A$? Green states "very little is known" about Problem 69 in general (except in the near-extremal regime $\delta=1-O(1/n)$, via Elekes–Szabó [100]=arXiv:1302.5777, or when $A$ lies on curves of higher constant degree). Green's Problem 71 is exactly Erdős #101 — four-point lines are $o(n^2)$ if no five on a line (the $k=4$ case of #588), and his comment sketches the conditional chain: many collinear 4-tuples $\Rightarrow$ many collinear triples $\Rightarrow$ (assuming no 5-on-a-line, via Problem 69) a cubic curve captures a positive proportion, then an iterative "peeling" argument puts almost all of $A$ on a bounded union of cubics, and Elekes–Szabó's cubic-curve analysis (arXiv:1302.5777) shows such sets cannot have many 4-rich lines. This chain generalizes in spirit to every $k\geq4$, i.e. Problem 69 is the natural common bottleneck for all of #588, not just its $k=4$ instance — but Green explicitly flags the chain as incomplete (Problem 69 unresolved) and notes that attempts to make the Solymosi–Stojaković extremal construction itself *avoid* cubic-curve structure (needed to fully close even the $k=4$ loop) failed, spawning further open Problems 73–74 in his list. - Green also notes a relevant tool: Barak, Dvir, Wigderson, Yehudayoff, "Fractional Sylvester-Gallai theorems," PNAS 110(48) (2013) (pmc.ncbi.nlm.nih.gov/articles/PMC3845162) — if every point of $V$ has $\geq\delta|V|$ other points forming a 3-rich line through it, then $V$ lies in an affine subspace of dimension $\ll\delta^{-2}$. Green writes he has "often thought this should be relevant to Problem 69 but have not managed to establish a connection" — i.e. a real but unexploited tool. - Elekes & Szabó, arXiv:1302.5777 (DCG, 2013/2023), pose the conjecture that any asymptotically near-optimal (quadratic-order) triple-line configuration must relate to a cubic curve, and explicitly connect special cases to "the four-in-a-line problem of Erdős" — the acknowledged literature bridge from the $k=3$-unrestricted case toward $k\geq4$. - Solymosi, arXiv:2206.00889 (DCG 2024), proves a case of the Elekes structure conjecture for many collinear triples plus a density version of Jamison's theorem — incremental progress on the Problem-69 side, not a resolution, and not $k$-general. - "A group-action Szemerédi–Trotter theorem...", arXiv:2411.13084 (2024), extends the Elekes–Szabó machinery (group-action version of Szemerédi–Trotter, generalizing Bourgain's $\mathrm{SL}_2(k)$ result) to all characteristics, with quantitative bounds on collinear triples on reducible cubic surfaces — active current development of exactly the toolkit Green flags as the bottleneck, but not yet applied to close #588. - "Elekes-Szabó for collinearity on cubic surfaces", arXiv:2212.14059 (2022/2023), classifies which cubic surfaces admit unbounded families with quadratically-many 3-rich lines not concentrated on a plane — further structural machinery in the same family, not a resolution of #588. - Very recent (May 2026): "Visibility cliques, cubic containers, and dense orchard cores," arXiv:2605.00918, proves a deterministic cubic-container theorem "for every fixed $k$" (no $k$ collinear points assumed) and combines it with the Green–Tao structure theorem and the Elekes–Szabó cubic-curve theorem to resolve structured cases of the Big-Line-Big-Clique conjecture. This is the most $k$-general recent use of the same cubic-curve/Elekes–Szabó toolkit that would be needed for #588, and confirms the machinery is under active, current development — but it targets visibility-clique structure (Kara–Pór–Wood conjecture), not #588's $f_k(n)=o(n^2)$ question directly. - No evidence found (arXiv, OpenAlex-style web search, erdosproblems.com forum, GitHub teorth/erdosproblems wiki) of any unconditional proof of $o(n^2)$ for $k$-rich lines with $k\geq4$, for any single $k$, nor of any AI-system (GPT/DeepMind/Aristotle/AlphaEvolve) contribution to #588 specifically. - Bottom line: erdosproblems.com's "open" status is correct and current as of 2026-07-02. #588 is best understood as the $k$-general version of a family whose $k=4$ instance is Erdős/Green Problem 71, and whose entire family is conditionally reducible to Green's Problem 69 (the general-$k$ Elekes–Szabó cubic-curve structure conjecture), itself open with "very little known." A full proof of Problem 69 — or even a $k$-specific special case beyond $k=4$ — would very plausibly resolve the corresponding instance of #588, but no such proof exists in the literature as of this search.

Attack surface

- Mode: derivation+formalization, conditional on literature (not finite-search — the $o(n^2)$ claim is not finitely checkable for any single $k$ — and not simple literature-resolution, since the resolving argument does not yet exist in complete, unconditional form for any $k\geq4$). - Concrete first experiment: (1) Formalize, from Green's PDF (Problem 69) and Elekes–Szabó (arXiv:1302.5777), the exact conditional chain generalized to arbitrary fixed $k\geq4$ (not just $k=4$ as in Green's Problem 71 comment): "Problem 69 for parameter $k$ (cubic-curve structure for $\geq\delta n^2$ collinear triples inside a no-$(k{+}1)$-collinear set) $\Rightarrow$ $f_k(n)=o(n^2)$," spelling out the "peeling to a bounded union of cubic curves" step and checking whether the final "sets on a union of cubics can't have many $k$-rich lines" step (which Elekes–Szabó verify for $k=4$) actually generalizes cleanly to larger $k$ — this is a well-scoped writing/verification task, not new mathematics, and would clarify precisely what remains open per-$k$. (2) Separately, attempt to determine whether the recent (2024-2026) group-action Szemerédi–Trotter / cubic-container machinery (arXiv:2411.13084, arXiv:2605.00918) — built for adjacent problems (Big-Line-Big-Clique) — can be repurposed to give even a $k$-dependent partial saving (e.g. $f_k(n) = O_k(n^2/(\log n)^{\epsilon})$) for some explicit $k\geq5$, which would be new even as a partial result. - Oracle: none for the core asymptotic claim (unfalsifiable by finite means, per erdosproblems.com, for every $k$). For sub-experiment (1), the logical chain itself is checkable by careful proof-review (do the hypotheses of each cited theorem actually match up for general $k$?). For sub-experiment (2), any claimed quantitative bound reduces to checking whether a cited theorem's hypotheses are met and its constants track $k$ correctly — a verifiable (though not fully mechanical) proof-reading task. - Feasibility: honest read — hard, but with a documented and currently-active-research conditional roadmap. Not a grind-a-search problem (falsifiability is not-finite) and not from-scratch derivation — Green's own list (Problem 69) already names the exact bottleneck conjecture, and multiple 2024-2026 papers (arXiv:2411.13084, arXiv:2605.00918) show the cubic-curve/Elekes-Szabó/group-action toolkit is being actively extended by working researchers right now, in directions adjacent to but not yet covering #588. Full unconditional resolution for any fixed $k\geq4$ requires resolving a case of Problem 69, itself a recognized hard open conjecture — not in reach for a direct attack. Realistic near-term contribution: the conditional-chain writeup (part 1), or spotting whether one of the very recent papers' techniques already yields an unnoticed partial bound for some $k$ (part 2).

Related

- Erdős #101 — four-point lines are $o(n^2)$ if no five on a line — the $k=4$ special case (no 5 on a line): are 4-point lines $o(n^2)$? Same origin [Er84]; this is Problem 71 in Green's list, with the most concretely worked-out (still incomplete) conditional proof strategy. - erdos/669 — Erdős's most general version [Er97f]: determine $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$ for lines with $\geq k$ / exactly $k$ points, *without* the no-$(k{+}1)$-collinear restriction that #588 imposes. - erdos/102 — Erdős–Purdy: dual question, what line-multiplicity is forced by $\geq cn^2$ lines with $>3$ points; "It is not even known if $h_c(n)\geq5$." - concept/cubic-curve-structure-theorem — Green–Tao's dichotomy (arXiv:1208.4714): point sets with few ordinary lines lie, all but $O(K)$ points, on a cubic curve; the technical ancestor of every proposed attack on #588. - concept/elekes-szabo-conjecture — Ben Green's Problem 69 (general $k$) / Elekes–Szabó's cubic-curve conjecture (arXiv:1302.5777): the recognized common bottleneck for #588 across all $k\geq4$, "very little known" per Green. - concept/orchard-planting-problem — the fully-resolved $k=3$, unrestricted sibling (Green–Tao, exact max $=\lfloor n(n-3)/6\rfloor+1$); shows the ceiling of what cubic-curve methods can deliver when they work. - Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds — Szemerédi–Trotter and its $k$-rich-line corollary $O(n^2/k^3+n/k)$: gives the standard (but for fixed $k$, insufficient) upper bound. - concept/fractional-sylvester-gallai — Barak–Dvir–Wigderson–Yehudayoff's rank/dimension bound from local collinearity density (PNAS 2013): a flagged-but-unexploited tool Green thinks may bear on Problem 69. - concept/lattice-points-on-sphere-construction — Solymosi–Stojaković's winning lower-bound technique for #588: pigeonhole on lattice points at equal distance on a high-dimensional sphere, then generic projection to the plane, preserving collinearity structure. - concept/big-line-big-clique-conjecture — Kara–Pór–Wood's conjecture (attacked in arXiv:2605.00918 via the same cubic-curve/Elekes–Szabó toolkit, for general fixed $k$): the most $k$-general recent application of this machinery, closest in spirit to what #588 would need.