Erdős Problem #669
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: geometry.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Suppose we draw \(n\) distinct points in the plane and ask how many different straight lines pass through many of them. One line may contain two, three or more points, but it counts as one line rather than a new line for every pair of points along it.
Erdős Problem #669 asks for the greatest possible number of lines passing through at least \(k\) points and, separately, exactly \(k\) points. Write
Here \(X\) ranges over configurations of distinct planar points and \(\ell\) over different geometric lines. The catalogue says the general fixed \(k\) problem is OPEN, despite the well-known \(k=3\) orchard results.
A small example
Let \(X=\{(0,0),(1,0),(2,0),(0,1)\}\). Exactly one straight line goes through three of these points: the horizontal axis. It contains exactly three, and no line contains all four. Consequently for this particular configuration
Four points in general position have zero such lines. The problem therefore maximizes over configurations; it does not minimize the number of three-rich lines over all four-point sets.
What is known
Pair charging gives a general bound. Any line containing \(r\geq k\) points accounts for at least \(\binom{k}{2}\) unordered point pairs. Each pair of distinct planar points determines one and only one line, so pairs assigned to different rich lines cannot overlap. Hence for each configuration
Thus
This is an upper bound, not a construction reaching the bound. For \(k=2\) it is sharp: choose \(n\) points with no three collinear, and all \(\binom n2\) pairs determine different two-point lines, giving \(f_2(n)=F_2(n)=\binom n2\).
The case \(k=3\) is the classical orchard problem. The original study of Burr, Grünbaum and Sloane, The orchard problem, Geometriae Dedicata 2 (1974), 397–424, gives matching leading quadratic bounds for the maximum number of lines containing exactly three points. Its publisher abstract gives an estimate with leading term \(n^2/6\) and a linear-scale remainder. The maintained catalogue also reports that the maximum for at least three points has leading term \(n^2/6\). A source audit should check this latter extension independently: the publisher abstract on exactly-three-rich lines alone does not prove it.
For larger \(k\) the pair-counting coefficient \(1/[k(k-1)]\) leaves a genuine gap between broad combinatorial counting and geometric constructions.
GCL's current state
The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.
Critical source-scope distinction: extremum is MAXIMUM over configurations, exactly versus at least k points, k3 Orchard result versus general k.
What remains
A bounded successor could focus on \(k=4\), producing either a family with a rigorously counted positive multiple of \(n^2\) distinct exactly four-point lines, or an improved upper coefficient beyond \(1/12\). A correct construction must prove that the lines are distinct and contain exactly four configuration points; merely counting selected four-element subsets can overcount one geometric line.
Check the full 1974 primary source, separate exactly \(k\) from at-least \(k\) theorem claims and confirm the historical [Er97f] formulation. Critical editorial review, protected merge and public mathematical-rendering verification are still required before a separate V2 admission.
Sources and claim boundaries
-
Maintained Erdős Problem #669, statement and historical \(k=3\) remarks.
-
S. A. Burr, B. Grünbaum and N. J. A. Sloane, The orchard problem, Geom. Dedicata 2 (1974), 397–424, primary publisher abstract reviewed.
-
GCL issue-bound #669 source return, elementary counting and historical caveat.
-
P. Erdős [Er97f]: original statement passage not independently inspected.
Boundary: classical exact counting and an attributed published \(k=3\) theorem, no new general higher \(k\) result, completed full historical proof audit, internal Lean certificate, protected production, deployed MathJax readback or editorial admission.
Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1940 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.