TOPICS
Search

Erdős Distinct Distances Problem


The Erdős distinct distances problem asks for the smallest number D(n) of distinct positive Euclidean distances determined by n distinct points in the plane (Erdős 1946). The conjectured order of growth is

 D(n)=Theta(n/(sqrt(lnn))),

where Theta denotes asymptotic notation and ln is the natural logarithm. A square lattice gives the upper bound of this order.

Guth and Katz (2015) proved the lower bound D(n)>=cn/lnn for an absolute constant c>0 and n>=2. The remaining logarithmic gap is open (Bloom 2026a). For n=1, 2, ..., the exact values begin 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 6, ... (OEIS A186704).

This is problem 89 in the Erdős problems collection (Bloom 2026a).

A related pinned-distance question counts the distinct distances from each individual point. Problem 654(i) asks whether, for every epsilon>0, every sufficiently large planar point set of size n with no four concyclic points has a point with more than (1-epsilon)n distinct distances to the others. Feng et al. (2026) reported a counterexample discovered by Aletheia, using points on two perpendicular lines.

In the variant formalized by Veljjanoski (2026a), the 4m points are (+/-2i,0) and (0,+/-(2i-1)) for 1<=i<=m, with m>=10. A circle meets either axis in at most two points, and a circle through two on each axis would require equal products of its intercepts on the two axes. The products are even and odd, respectively. From any point there are at most 2m-1 distinct distances to points on its own axis and at most m to those on the other axis, by reflection across the axis containing that point. Palomar Registry (2026a) records kernel acceptance of the bound 3m-1 and the negative answer to part (i). The general position variant, which also excludes collinear triples, remains open.

A different restriction excludes isosceles triangles, including degenerate ones. The question asks whether, in each fixed dimension k, every such n-point set must determine at least nf_k(n) distinct positive distances, where f_k(n)->infty (Bloom 2026b). Straus observed that no such bound can hold uniformly in the dimension. An explicit construction takes all 2^k points whose ith coordinate is either 0 or sqrt(2^i), for 0<=i<k (Veljjanoski 2026b). The squared Euclidean distance between two points is the sum of 2^i over the coordinates where they differ. Uniqueness of finite binary expansions rules out an isosceles triangle, and the positive squared distances are precisely 1, 2, ..., 2^k-1. Palomar Registry (2026b) records kernel acceptance of this power-of-two construction. It does not settle the question in a fixed dimension, since k grows with the number of points.

A separated-distance variant assumes an averaged energy bound. For 1<s<2, let P subset= [0,1]^2 contain N distinct points and suppose

 N^(-2)sum_(x,y in P, x!=y)||x-y||^(-s)<=A,

where A is independent of N and ||·|| is the Euclidean norm. Burstein et al. (2026) obtained, for every epsilon>0, at least c_(s,A,epsilon)N^(1-epsilon) distances whose pairwise separations are at least N^(-1). This is a separation-scale conclusion under an energy hypothesis, rather than a resolution of the unrestricted logarithmic gap.


See also

Distance, Erdős Problems, Erdős Unit Distance Problem

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 89." Accessed Oct. 26, 2026a. https://www.erdosproblems.com/89.Bloom, T. F. "Erdős Problem 657." Accessed Nov. 12, 2026b. https://www.erdosproblems.com/657.Burstein, W.; Iosevich, A.; and Yavicoli, A. "Falconer's Conjecture Through Descent and Chaining." 11 Nov 2026. https://arxiv.org/abs/2611.14867v1.Erdős, P. "On Sets of Distances of n Points." Amer. Math. Monthly 53, 248-250, 1946. https://doi.org/10.1080/00029890.1946.11991674.Feng, T.; Trinh, T.; Bingham, G.; Kang, J.; Zhang, S.; Kim, S.-H.; Barreto, K.; Schildkraut, C.; Jung, J.; Seo, J.; Pagano, C.; Chervonyi, Y.; Hwang, D.; Hou, K.; Gukov, S.; Tsai, C.-C.; Choi, H.; Jin, Y.; Li, W.-Y.; Wu, H.-A.; Shiu, R.-A.; Shih, Y.-S.; Le, Q. V.; and Luong, T. "Semi-Autonomous Mathematics Discovery with Gemini: A Case Study on the Erdős Problems." 5 Feb 2026. https://arxiv.org/abs/2601.22401v3.Guth, L. and Katz, N. H. "On the Erdős Distinct Distances Problem in the Plane." Ann. Math. 181, 155-190, 2015. https://doi.org/10.4007/annals.2015.181.1.2.Palomar Registry. "Erdős Problem 654: Distinct Distances from a Point When No Four Points Are Concyclic." Entry PALOMAR-2026-11-02-000006, Nov. 2, 2026a. https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-02-000006.Palomar Registry. "Erdős Problem 657: Straus's Observation on Isosceles-Free Point Sets with Few Distances." Entry PALOMAR-2026-11-02-000007, Nov. 2, 2026b. https://palomar-registry.org/entry.html?id=PALOMAR-2026-11-02-000007.Veljjanoski, D. "Erdős Problem 654: Distinct Distances from a Point When No Four Points Are Concyclic." 2026a. https://github.com/veljjanoski/erdos654-palomar/tree/fd7a8dc3cf52f6dcadcf5c6bcd05a2dc387dc64f.Veljjanoski, D. "Erdős Problem 657: Straus's Observation on Isosceles-Free Point Sets with Few Distances." 2026b. https://github.com/veljjanoski/erdos657-palomar/tree/e44e1eb1d4a525f66a7a297235c956a29f56a535.Sloane, N. J. A. Sequence A186704in "The On-Line Encyclopedia of Integer Sequences."

Cite this as:

Weisstein, Eric W. "Erdős Distinct Distances Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ErdosDistinctDistancesProblem.html

Subject classifications