Skip to content

Erdős Problem #1069

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: solved (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Choose \(n\) distinct points in the plane. A line is called \(k\)‑rich if it passes through at least \(k\) of the points. How many different rich lines can there be?

Erdős Problem #1069 asks for a bound on this number when \(2\le k\le\sqrt n\). The celebrated Szemerédi–Trotter theorem gives the answer:

\[ L_k(P)\le C\frac{n^2}{k^3}, \qquad 2\le k\le\sqrt n, \]

where \(C\) is one universal constant. The number of lines decreases rapidly as the richness threshold rises. The sharp possible value of \(C\) remains a separate problem.

A small example

Place nine points in a \(3\times3\) square lattice. Three horizontal lines, three vertical lines, and the two long diagonals each contain three points. There are precisely eight \(3\)‑rich lines.

For a \(4\times4\) grid there are ten \(4\)‑rich lines, and for a \(5\times5\) grid there are twelve \(5\)‑rich lines. These values can be confirmed by putting every line through a pair of integer points into its unique primitive equation \(ax+by=c\), then counting its grid points.

They also illustrate a general lower construction: for a \(q\times q\) grid, \(n=q^2\) and \(k=q\), there are at least \(2q+2\) rich lines. The general theorem says there are at most a constant times \(q\) such lines, because \(n^2/k^3=q\).

What is known

The claimed rich-line bound is a published theorem. The original primary source is Endre Szemerédi and William T. Trotter, Extremal problems in discrete geometry, Combinatorica 3 (1983), 381–392. On printed page 382, Theorem 2 gives the precise \(C n^2/k^3\) estimate.

The authors derive it from their incidence theorem, which bounds the total number of incidences between points and lines. In general the rich-line estimate also has an \(n/k\) term; the pure \(n^2/k^3\) expression is appropriate in the stated \(k\le\sqrt n\) regime.

The later Erdős retrospective attributes the conjecture to Erdős, Croft and Purdy. Its attribution and chronology still need comparison with the original pages; the 1983 paper calls the corollary an Erdős–Purdy conjecture.

GCL's current state

Authenticated source audit #2340 directly inspected and matched Theorem 2 on the original 1983 paper, page 382. It independently checked the small grid examples.

The theorem is externally established, not newly discovered or certified by GCL. GCL has not reproduced the entire covering-lemma proof of the underlying incidence theorem or finalized the 1987 historical source comparison.

What remains

The editorial proof review should reconstruct the short deduction from the incidence theorem to the rich-line bound, keeping the \(k\) range explicit. A separate attribution audit must compare the Erdős 1987 survey with the 1983 primary paper. Better constants and the extreme lattice constructions are legitimate continuing mathematical questions, but they must not obscure that the order-of-growth theorem itself is proved.

Sources and claim boundaries

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2340 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • 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.

Back to catalogue · Compendium introduction