Erdős #1207 · geometry / distances

Erdős [Er80] attributes this problem to Riddell, and states it is not hard to prove that $P_d(n)>n^{\epsilon_d}$ where $\epsilon_d\to 0$ as $d\to \infty$. Indeed, one can take any subset of points with all distinct distances, whence

with $f_d(n)$ defined as in [1208].

Erdős suggested that perhaps the worst set of points is the set of lattice points in a sphere of suitable radius.

The case $d=1$ is equivalent to finding sets with no three-term arithmetic progressions, and is the $k=3$ case of [201].

The bound of Pach and Tardos [PaTa02] on the maximum number of isosceles triangles in a point set, together with a random deletion argument, shows that $P_2(n) \gg n^{0.432}$. In Section 5.3 of [BMP05] they claim that the regular polygon shows that $P_2(n) \ll n^{1/2}$ but give no details. This seems to be incorrect, since an isosceles triangle from the vertices of a regular polygon correspond to three points whose angles form an arithmetic progression. This shows that $P_2(n)\ll r_3(n)$, where $r_3(n)$ is the maximum size of a subset of $\{1,\ldots,n\}$ without a non-trivial three-term arithmetic progression (see [140]).

A better construction, which proves that $P_2(n)<n^{1-c}$ for some absolute constant $c>0$, was found by Lee, Pohoata, and Zhu (assisted by ChatGPT) [LPZ26]. (This construction is similar to that used for the unit distance problem [90]).

Although this answers the main question of Erdős, I leave this open as a general challenge to estimate $P_d(n)$ more generally.

See [1208] (and also [657]) for a variant in which we ask for all sets of three points to have distinct distances.

The source labels this entry OPEN 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.