Erdős Problem #733
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: combinatorics, 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
A nondecreasing sequence X_i≥2 is line-compatible if exactly m rich lines occur in a planar configuration of n distinct points, and the i-th rich line contains X_i points. Erdős asked whether the number f(n) of such sorted line-size sequences is at most exp(O(√n)); this is PROVED. A later question asking for lim log f(n)/√n is distinct and not resolved by the bound.
A small example
Three non-collinear points yield exactly three rich lines of size 2: (2,2,2). Four points in general position yield six size-2 lines; exactly three of four collinear give one size-3 line and three size-2 lines, hence (2,2,2,3). Multiplicity and the condition 'containing at least two of the points' are essential.
What is known
Original pinned teorth catalogue #733 and issue #2004 report PROVED; live maintained https://www.erdosproblems.com/733 attributes the upper bound to Szemerédi–Trotter [SzTr83], and gives a lower exp(c√n). The exact primary incidence-theorem proof, sequence-encoding reduction and any limiting constant have not been independently read.
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: Szemerédi–Trotter line-compatible count exp(O(sqrt n)), subsequent normalized log limit open.
What remains
Fix exact integer coordinates for the n=3 and n=4 configurations and enumerate rich lines. Inspect original Szemerédi–Trotter 1983 incidence theorem, then verify how its rich-line bound implies the claimed count of multiplicity-sensitive sorted sequences. Keep the limiting-constant question open.
Sources and claim boundaries
Maintained #733 and original issue source return. Exact primary SzTr83 theorem proof not replayed; Independent historical proof replay is outstanding.
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: #2004 — 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.