Erdős #101 — four-point lines are $o(n^2)$ if no five on a line

Statement

Given $n$ points in $\mathbb{R}^2$, no five of which are on a line, the number of lines containing (exactly) four points is $o(n^2)$.

Facts

- Prize \$100; status open (erdosproblems.com/101, reflects site-owner belief; "cannot be resolved with a finite computation" since it is an asymptotic-in-$n$ statement). - Falsifiable: no — this needs a genuine proof; there is no finite computation that settles an $o(n^2)$ asymptotic claim. - Origin: Erdős, repeatedly, across [Er84] [Er87b,p.170] [Er90] [Er92e] [Er95,p.181] [Er97c,p.66]. It is Problem 71 in Ben Green's "100 Open Problems" list (people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf), phrased as the (formally stronger) contrapositive-style question: "Suppose $A\subset\mathbb{R}^2$ has size $n$ with $cn^2$ collinear 4-tuples. Does it contain 5 points on a line?" — a "yes" there directly implies erdos/101. - Trivial upper bound: $O(n^2)$. A 4-point line accounts for $\binom{4}{2}=6$ point-pairs, and there are $\binom{n}{2}$ pairs total, so the number of 4-point lines is $\le n(n-1)/12$. The whole content of the problem is shaving an $o(1)$ factor off this trivial constant — a "removing-the-constant" extremal problem, not a power-saving one. - Lower-bound / construction side (how close to $n^2$ one can actually get with no 5-on-a-line): - Burr, Grünbaum, Sloane [BGS74] and Füredi, Palásti [FuPa84]: constructions with $\sim n^2/6$ collinear *triples* and no 4 points on a line (adjacent regime, $k=3$). - Grünbaum [Gr76]: a construction with $\gg n^{3/2}$ four-point lines, no five on a line; Erdős speculated $n^{3/2}$ might be the true order of magnitude. - Solymosi & Stojaković, "Many collinear $k$-tuples with no $k+1$ collinear points," arXiv:1107.0327 (Discrete Comput. Geom. 50 (2013), 811-820): for every $k>3$ they construct $n$-point sets with no $(k{+}1)$-tuple collinear but $\ge n^{2-c(k)/\sqrt{\log n}}$ collinear $k$-tuples. For $k=4$ this falsifies Grünbaum/Erdős's $n^{3/2}$ speculation: the truth is far closer to $n^2$ than $n^{3/2}$, getting "reasonably close to the trivial upper bound $O(n^2)$" (their own abstract's phrasing). This is exactly the construction cited in Green's Problem 71 comment ([287] there). - Consequence: any valid proof of $o(n^2)$ must be a genuine $o(1)$-type saving over the trivial bound — no simple counting/incidence bound (e.g. Szemerédi–Trotter, which is tight up to constants and gives $O(n^2)$ not $o(n^2)$ here) can work; whatever argument succeeds must exploit *global structure*, not just pair-counting. - The known proof strategy (Green's Problem 69 → 71 reduction): Green's comment on Problem 71 sketches a conditional route: many collinear 4-tuples $\Rightarrow$ many collinear triples $\Rightarrow$ (assuming no 5-on-a-line) a positive proportion of $A$ lies on a cubic curve, *if* Problem 69 (the Elekes–Szabó cubic-curve structure conjecture) is true; an iterative "peeling" argument would then put almost all of $A$ on a bounded union of cubic curves; and one can separately verify that point sets living on a union of cubic curves cannot have many collinear 4-tuples (Elekes–Szabó, arXiv:1302.5777). Green explicitly flags this chain is not a complete proof — Problem 69 itself is open, and he notes attempts to make the Solymosi–Stojaković extremal construction itself avoid cubic-curve structure (which would be needed to fully close the loop) failed and spawned two further open problems (73, 74) in his list. - Related problems: erdos/102, Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$?, erdos/669.

Literature state

Not resolved, and not close to resolved unconditionally — but the reduction structure is unusually well understood, which is the key finding here. - The problem sits inside a family of "how many lines with exactly $k$ points" questions: Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$? (Erdős, same source [Er84], asks $f_k(n)=o(n^2)$ for general $k\ge4$, of which #101 is the $k=4$, no-5-on-line special case) and erdos/669 (Erdős 1997, asks for $\lim F_k(n)/n^2$ and $\lim f_k(n)/n^2$ more generally, without the no-$(k{+}1)$ constraint). None of these are resolved. - The closest fully solved analog is the $k=3$ case *without* a no-4-on-a-line restriction: the Dirac–Motzkin conjecture on ordinary (2-point) lines and the "orchard-planting problem" (maximizing 3-point lines), both resolved for large $n$ by Ben Green & Terence Tao, "On sets defining few ordinary lines," arXiv:1208.4714 (Annals of Math. 2013). They prove $\ge n/2$ ordinary lines always exist and that the max number of 3-point lines is exactly $\lfloor n(n-3)/6\rfloor+1$ for large $n$, via a structure theorem: if $P$ has at most $Kn$ ordinary lines then all but $O(K)$ points of $P$ lie on a cubic curve. This cubic-curve dichotomy is the direct ancestor of the strategy proposed for #101. - Elekes & Szabó, "On Triple Lines and Cubic Curves — the Orchard Problem revisited," arXiv:1302.5777, explicitly generalize/conjecture that *any* asymptotically-near-optimal (quadratic-order) triple-line configuration must be related to a cubic curve, and their abstract states some special cases they prove "are also related to the four-in-a-line problem of Erdős" — i.e. this is the literature's own acknowledged bridge from #101 to the (still open) cubic-curve structure conjecture. This conjecture is Ben Green's Problem 69 in his 100-problems list, explicitly marked as largely open ("very little is known, except when $\delta=1-O(1/n)$"). - Solymosi, "On the structure of pointsets with many collinear triples," arXiv:2206.00889 (Discrete Comput. Geom. 2024), proves a case of the Elekes conjecture on structure from many collinear triples, plus a density version of Jamison's theorem (many pairwise directions $\Rightarrow$ conic structure) — incremental progress on the Problem-69 side, not a resolution. - Very recent (May 2026): "Visibility cliques, cubic containers, and dense orchard cores," arXiv:2605.00918, proves a deterministic "cubic-container theorem" and combines it with the Green–Tao structure theorem and the Elekes–Szabó triple-line/cubic-curve theorem to attack the (different but closely related) Big-Line-Big-Clique conjecture of Kara–Pór–Wood. This shows the cubic-curve/Elekes-Szabó toolkit is under active, current development, but it targets visibility-clique structure, not #101 directly — no claim there resolves erdos/101. - No evidence found (arXiv, OpenAlex, web search, erdosproblems.com forum) of any direct unconditional proof of $o(n^2)$ for exactly-4-point lines, nor of any AI-system (GPT/DeepMind/Aristotle/AlphaEvolve) contribution to this specific problem. - Bottom line: erdosproblems.com's "open" status is correct and current as of 2026-07-02. The problem is best understood as *conditionally reducible* to Green's Problem 69 (Elekes–Szabó cubic-curve structure conjecture), itself open; a full proof of Problem 69 (or even the $k=4$-relevant special case) plus the "peeling" argument Green sketches would very plausibly resolve #101, but neither has been carried out and published as a complete, unconditional proof.

Attack surface

- Mode: derivation+formalization, conditional on literature (not finite-search — an $o(n^2)$ claim over all $n$ is not finitely checkable, and not simple literature-resolution — the resolving argument does not yet exist in complete form). - Concrete first experiment: (1) formalize precisely, from Green's PDF and the Elekes–Szabó paper (arXiv:1302.5777), the exact conditional chain: "Problem 69 (Elekes–Szabó cubic-curve structure for $\ge\delta n^2$ collinear triples, no $k$ on a line) $\Rightarrow$ erdos/101," including the "peeling to a bounded union of cubic curves" step Green describes but does not spell out — this is a well-scoped writing/verification task, not new mathematics, and would clarify exactly what remains to prove; (2) separately, attempt the sub-case Green flags as open himself — modify the Solymosi–Stojaković (arXiv:1107.0327) $n^{2-c/\sqrt{\log n}}$ construction so that $O(1)$ points lie on any fixed cubic curve, which he tried and failed to do (spawning his Problems 73/74) — succeeding would be informative either way (a positive answer stress-tests whether the cubic-curve route can even be consistent with the known near-extremal construction). - Oracle: none for the core asymptotic claim (unfalsifiable by finite means, per erdosproblems.com). For sub-experiment (2), a candidate construction is checked exactly (is $O(1)$ points on every cubic curve? — a finite algebraic check for any concrete finite instance, though the "for all large $n$" claim about the family is not finite). - Feasibility: honest read — hard, but with an unusually concrete conditional roadmap. This is not a "grind a SAT/ILP search" problem (falsifiability is not-finite) and not a from-scratch derivation — Green's own problem list already lays out the reduction skeleton and names exactly which open sub-conjecture (his Problem 69 / the Elekes–Szabó cubic-curve conjecture) would close it, and recent (2026) work (arXiv:2605.00918) shows the same cubic-container/Elekes–Szabó machinery is being actively extended by others right now. Realistic near-term contribution: rigorously write up and stress-test the conditional reduction (part 1 above), or attempt Green's own stated-as-failed sub-problem (part 2). Full unconditional resolution requires resolving Problem 69 in generality, which is itself a recognized hard open problem — not in reach for a direct attack.

Related

- erdos/102 — same source family [Er92e][Er95][Er97c]: estimating $h_c(n)$, the largest line-multiplicity forced by $\ge cn^2$ lines with $>3$ points; explicit "See also" link on erdosproblems.com/101. - Erdős #588 — are $k$-rich lines $o(n^2)$ for $k\geq 4$? — Erdős's direct generalization (same origin [Er84]): is $f_k(n)=o(n^2)$ for all $k\ge4$ (no $k{+}1$ on a line)? erdos/101 is exactly the $k=4$ case. - 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 $\ge k$ / exactly $k$ points, without the no-$(k{+}1)$ restriction. - concept/cubic-curve-structure-theorem — Green–Tao's dichotomy (arXiv:1208.4714): few ordinary lines $\Rightarrow$ almost all points lie on a cubic curve; the ancestor tool for #101's proposed attack. - concept/elekes-szabo-conjecture — the general conjecture (Ben Green's Problem 69; Elekes–Szabó arXiv:1302.5777) that quadratically-many collinear triples force cubic-curve structure; #101's proposed resolution is conditional on this. - concept/orchard-planting-problem — the resolved ($k=3$, unrestricted) sibling: Green–Tao arXiv:1208.4714 proved the exact max number of 3-point lines is $\lfloor n(n-3)/6\rfloor+1$, and confirmed the Dirac–Motzkin ordinary-lines conjecture, via the cubic-curve structure theorem. - Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds — the ambient toolkit (Szemerédi–Trotter etc.) that gives the trivial $O(n^2)$ bound but cannot alone produce the required $o(1)$ saving.