Skip to content

Erdős Problem #135

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: distances, 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

Choose \(n\) distinct points \(A\) in the Euclidean plane. Count the different positive distances between unordered pairs. Erdős and Gyárfás imposed a strong local condition: every four-point subset must determine at least five distinct distances among its six pairs.

They conjectured that this forces a quadratic number of different distances globally:

\[ |\{|x-y|:x,y\in A,\ x\ne y\}|\gg n^2. \]

The constant should be independent of \(n\) and the particular point set. It is insufficient that some four-point subsets determine five lengths; the condition is universal.

A small example

A unit square has six unordered point pairs but only two distinct lengths, its side and diagonal. It violates the local hypothesis and cannot serve as a counterexample. Four generic points may determine six different distances, satisfying the local condition for that finite set; this does not establish a global quadratic bound for large configurations.

The local condition restricts repetitions inside each four-point induced distance pattern but does not prohibit repetitions between pairs belonging to unrelated four-point configurations.

What is known

DISPROVED. Terence Tao's original 2024 paper, Planar point sets with forbidden 4-point patterns and few distinct distances, constructs for all sufficiently large \(n\) an \(n\) point planar set satisfying the every-four-point condition but determining at most

\[ O\left(\frac{n^2}{\sqrt{\log n}}\right) \]

distinct distances. This is \(o(n^2)\) and therefore contradicts the proposed positive-constant quadratic lower bound.

Tao's author explanation dated 3 September 2024 identifies three main components: Dumitrescu's classification of eight forbidden four-point distance patterns, Thiele and Dumitrescu's algebraic construction that avoids some patterns, and a randomized transformation eliminating the rest. The classification is a tool; it is not alone the desired asymptotic construction.

The problem belongs to a broader family asking how many distances are forced when every set of \(p\) points determines at least \(q\) distinct distances. The negative answer here does not automatically settle other pairs \((p,q)\).

GCL's current state

The pinned and maintained Erdős #135 classify it DISPROVED. The original source issue is #1404. The primary abstract and author exposition were inspected, but the entire randomized geometric construction has not been 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 finite fixture enumerates all four-point subsets of small rational-coordinate planar sets and counts distinct exact squared distances among their six unordered pairs. Acceptance: a unit square fails with two distinct squared lengths, while a generic fixture with six distinct lengths passes. Stop at finite semantics. This cannot certify the asymptotic construction or improve the asymptotic exponent.

Sources and claim boundaries

No new configuration, independently certified asymptotic proof, or editorial admission is claimed.

Catalogue and evidence provenance

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