Erdős #1208 · geometry / distances

It is known that

for some constant $c>0$. The lower bound was proved by Charalambides [Ch13]. The upper bound was proved by Lee, Pohoata, and Zhu [LPZ26].

Thiele [Th95] proved $F_d(n) \gg n^{\frac{1}{3d-2}}$ for all $d\geq 3$. This was improved to

by Conlon, Fox, Gasarch, Harris, Ulrich, and Zbarsky [CFGHUZ15]. The example of integer lattice points shows that $F_d(n)\ll n^{1/d}$ for $d\geq 2$.

Erdős and Guy [ErGu70] consider the problem of determining the maximal size of such a subset of the $n^{1/d}\times\cdots \times n^{1/d}$ integer grid, showing that it is at least $n^{\frac{2}{3d}-o(1)}$ (and at most $n^{1/d}$). Lefmann and Thiele [LeTh95] have improved the lower bound to $n^{\frac{2}{3d}}$.

The case $d=1$ is the subject of [530], and Komlós, Sulyok, and Szemerédi [KSS75] have proved that $F_1(n)\asymp n^{1/2}$.

See also [1207]. The behaviour of $F_d(n)$ for fixed $n\geq 3$ as $d\to \infty$ is the subject of [1088].

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.