Szemerédi's conjecture: n points with no 3 collinear determine at least n/2 distinct distances (Erdős #1082)
Statement
Let $A\subset \mathbb{R}^2$ be a set of $n$ points with no three on a line. Must $A$ determine at least $\lfloor n/2\rfloor$ distinct distances? (The distances determined by $A$ are the values $|a-b|$ over unordered pairs $a\neq b\in A$; the question asks whether the number of DISTINCT such values is always at least $\lfloor n/2\rfloor$ under the no-three-collinear hypothesis.) Note: the original problem also asked the stronger single-point form — must some one point of $A$ see at least $\lfloor n/2\rfloor$ distinct distances to the others? — but that form is now known to be FALSE (see background); only the total-count question above is open.
Acceptance. FULLY RESOLVES: (a) a proof that every finite set of $n$ points in $\mathbb{R}^2$ with no three collinear determines at least $\lfloor n/2\rfloor$ distinct distances — machine-checkable (Lean/Coq) preferred (a formal statement exists in formal-conjectures), else a complete written proof; or (b) a counterexample: an explicit $n$-point set with exact coordinates (rational or algebraic, given exactly), together with a machine-checkable certificate that (i) no three points are collinear and (ii) the number of distinct pairwise distances (compared in exact arithmetic on squared distances) is strictly less than $\lfloor n/2\rfloor$; include the verification code. ADVANCES: a proven lower bound $cn$ with a constant $c$ strictly better than the $1/3$ stated in the background; a resolution of the $\mathbb{R}^3$ variant ($\gg n$ distances for no-three-collinear sets); or a Lean formalization of Szemerédi's $n/3$ argument. Deliver the proof file, or the coordinates + collinearity/distance-count certificates + verification code.
Background
A conjecture of Szemerédi, circulated by Erdős [Er75f, p.101], [Er87b], [Er97e]; listed as open on erdosproblems.com/1082 (fetched 2026-07-13, status 'falsifiable', tagged 'geometry | distances'). Szemerédi proved the bound with $n/2$ replaced by $n/3$ (proof unpublished but reproduced in [Er75f]); the conjectured bound would be sharp, since the vertices of a regular $n$-gon have no three collinear and determine exactly $\lfloor n/2\rfloor$ distinct distances. More generally he showed by a simple argument that if no $k$ points of $A$ are collinear then some single point determines $\gg n/k$ distinct distances — a weak inverse to Erdős's distinct distances problem, Erdős #89 (erdosproblems.com/89). The present question is a stronger form of Erdős #93 (erdosproblems.com/93). The single-point strengthening (a stronger form of Erdős #982) has a NEGATIVE answer: an 8-point configuration in which every point has exactly $3<\lfloor 8/2\rfloor$ distinct distances to the others, credited by Erdős–Fishburn [ErFi97b] to Harborth and studied in detail by Fishburn [Fi02]; it was independently rediscovered by DeepMind, and Xichuan (site comments) gave a 42-point set with no three collinear in which each point determines only 20 distinct distances. In $\mathbb{R}^3$, Erdős asked in [Er75f] whether $n$ points with no three collinear determine $\gg n$ distances; Altman proved yes for vertices of a convex polyhedron (cf. Erdős #660) and Szemerédi proved yes when no four points are coplanar. A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tools: structured construction search (as in the DeepMind/Xichuan discoveries) for a no-three-collinear point set whose TOTAL number of distinct distances falls below $\lfloor n/2\rfloor$, certified in exact arithmetic; or sharpening Szemerédi's $n/3$ counting argument toward $n/2$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1082 (T. F. Bloom) | website |
| REF-02 | Formalised statement (Lean, formal-conjectures) | website |
| REF-03 | Erdős Problem #89 — the distinct distances problem (context) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.