← All problems

Erdős Problem #1083 — Distinct distances in fixed-dimensional spaces

80 years old · traced to

Let d≥3d\ge 3 be an integer and n≥2n\ge 2. For a set P⊂RdP\subset\mathbb R^d of nn distinct points, define its set of pairwise distances by

Δ(P)={∥x−y∥2:x,y∈P, x≠y}.\Delta(P)=\{\|x-y\|_2:x,y\in P,\ x\ne y\}.

Define

fd(n)=min⁡P⊂Rd∣P∣=n∣Δ(P)∣.f_d(n)=\min_{\substack{P\subset\mathbb R^d\\|P|=n}}|\Delta(P)|.

Thus fd(n)f_d(n) is the least number of distinct distances that can be forced for every such PP. For each fixed d≥3d\ge3, estimate fd(n)f_d(n) as n→∞n\to\infty; in particular, is

fd(n)=n2/d−o(1)?f_d(n)=n^{2/d-o(1)}?

Erdős Problems #1083

Background

This is the higher-dimensional version of the distinct-distance problem. Erdős’s 1946 work established the bounds n1/d≪dfd(n)≪dn2/dn^{1/d}\ll_d f_d(n)\ll_d n^{2/d}. The upper bound comes from lattice points: an approximately cubic section of Zd\mathbb Z^d with about nn points has squared distances given by sums of dd squares, with each summand at most on the order of n2/dn^{2/d}. The question emphasizes fixed dimension as nn grows; the lattice construction suggests the scale n2/dn^{2/d} for the minimum. Erdős (1946) arXiv:1406.1949

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 1

Claimed by OpenAI.See full solutionHide full solution

Claims that for every fixed integer d >= 3 there is c_d > 0 such that every set of n >= 2 distinct points in R^d determines at least c_d n^(2/d) distances; the bound has no spacing or position assumptions and implies the target's weaker asymptotic lower bound.

Repository: https://github.com/openai/math

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/The-higher-dimensional-Erdos-distinct-distances-conjecture-September-23-2026/paper.pdf

  • OpenAI-166-01-The-higher-dimensional-Erd-s-distinct-distances-conjecture.pdf946,536 bytesOpen