Erdős #1082 · geometry / distances

A conjecture of Szemerédi, who proved this with $n/2$ replaced by $n/3$. More generally, Szemerédi gave a simple proof that if there are no $k$ points on a line then some point determines $\gg n/k$ distinct distances (a weak inverse result to the distinct distance problem [89]).

This is a stronger form of [93]. The second question is a stronger form of [982].

Szemerédi's proof is unpublished, but given in [Er75f].

In [Er75f] Erdős asks whether, given $n$ points in $\mathbb{R}^3$ with no three on a line, do they determine $\gg n$ distances? Altman proved the answer is yes if the points form the vertices of a convex polyhedron (see [660] for a stronger form of this), and Szemerédi proved the answer is yes if there are no four points on a plane.

The second stronger question has a negative answer: there is a construction of $8$ points such that each point has exactly three distinct distances to the others. This first appeared in the literature in a paper of Erdős and Fishburn [ErFi97b], where they credit the construction to Harborth. This configuration is studied in detail by Fishburn [Fi02].

(This construction was later found by DeepMind. An earlier construction was also given by Xichuan in the comments, who gave a set of $42$ points in $\mathbb{R}^2$, with no three on a line, such that each point determines only $20$ distinct distances.)

The source labels this entry FALSIFIABLE in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.