Skip to content

Erdős Problem #210

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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

For \(n\) distinct planar points not all on a common line, an ordinary line is a line passing through exactly two of the points. Let \(f(n)\) be the smallest number of ordinary lines that any such \(n\) point set can determine. Erdős and de Bruijn asked whether \(f(n)\) tends to infinity and how quickly.

A line that contains three or more original points is not ordinary, even though it contains many pairs of points. Ordinary lines are distinct geometric lines rather than ordered point pairs.

A small example

Three noncollinear points form three ordinary lines. For four points with no three collinear, every pair determines an ordinary line, giving six. If three of the points lie on one line and the fourth is off it, that shared line is not ordinary, while the three lines from the off-line point to each point on the shared line are ordinary.

The elementary Sylvester–Gallai theorem guarantees at least one ordinary line whenever the point set is not collinear. It does not on its own show that their number grows linearly.

What is known

PROVED. Motzkin (1951) established \(f(n)\to\infty\). Kelly and Moser (1958) gave \(f(n)\ge3n/7\), and Csima and Sawyer (1993) improved this to \(6n/13\) for \(n\ge8\). Ben Green and Terence Tao, On sets defining few ordinary lines, Discrete & Computational Geometry 50 (2013), proved that

\[ f(n)\ge\frac n2 \]

for every sufficiently large \(n\). Their theorem also describes asymptotic extremal configurations. For sufficiently large odd \(n\), the more precise lower bound is \(3\lfloor n/4\rfloor\).

The even-order bound is sharp, via suitable near-cubic configurations. Historical descriptions involving points at infinity are projective models and should not be presented as literal finite configurations in the affine plane without a deprojection argument.

GCL's current state

Pinned and maintained Erdős #210 classify the question PROVED. Original issue #1479. Green–Tao's published theorem and its qualification for sufficiently large \(n\) were checked; its cubic-curve structure proof was not independently replayed.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task enumerates all point pairs from small rational-coordinate configurations, groups pairs by an exactly normalized line equation, and counts lines with exactly two incident points. Acceptance: three noncollinear points give three ordinary lines, while three collinear and one off-line give exactly three, and the algorithm does not double-count a line with three points. Stop short of extrapolating the extremal theorem for large \(n\).

Sources and claim boundaries

No new ordinary-line lower bound, independent full source proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1479 — 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