# Erdős distinct distances problem

In discrete geometry, the Erdős distinct distances problem states that between n distinct points on a plane there are at least n1 − o(1) distinct distances. It was posed by Paul Erdős in 1946. In a 2010 preprint, Larry Guth and Nets Hawk Katz announced a solution.[1]

## The conjecture

In what follows let g(n) denote the minimal number of distinct distances between n points in the plane. In his 1946 paper, Erdős proved the estimates $\sqrt{n-3/4}-1/2\leq g(n)\leq c n/\sqrt{\log n}$ for some constant $c$. The lower bound was given by an easy argument, the upper bound is given by a $\sqrt{n}\times\sqrt{n}$ square grid (as there are $O( n/\sqrt{\log n})$ numbers below n which are sums of two squares, see Landau–Ramanujan constant). Erdős conjectured that the upper bound was closer to the true value of g(n), specifically, $g(n) = \Omega(n^c)$ holds for every c < 1.

↑Jump back a section

## Partial results

Paul Erdős' 1946 lower bound of g(n) = Ω(n1/2) was successively improved to:

↑Jump back a section

## Higher dimensions

Erdős also considered the higher dimensional variant of the problem: for d≥3 let gd(n) denote the minimal possible number of distinct distances among n point in the d-dimensional Euclidean space. He proved that gd(n) = Ω(n1/d) and gd(n) = O(n2/d) and conjectured that the upper bound is in fact sharp, i.e., gd(n) = Θ(n2/d) . In 2008, Solymosi and Vu obtained the gd(n) = Ω(n2/d(1-1/(d+2))) lower bound.

↑Jump back a section

## See also

↑Jump back a section

## Notes

1. ^ Guth, l.; Katz, N. H. (2010). "On the Erdős distinct distance problem on the plane". arXiv:1011.4105.. See also The Guth-Katz bound on the Erdős distance problem by Terry Tao and Guth and Katz’s Solution of Erdős’s Distinct Distances Problem by János Pach.
↑Jump back a section

## References

• .
• .
• Erdős, P. (1946), "On sets of distances of n points", American Mathematical Monthly 53: 248–250.
• Garibaldi, J.; Iosevich, A.; Senger, S. (2011), The Erdős Distance Problem, Providence, RI: American Mathematical Society.
• Guth, L.; Katz, N. H. (2010). "On the Erdős distinct distance problem on the plane". arXiv:1011.4105..
• Moser, L. (1952), "On the different distances determined by n points", American Mathematical Monthly 59: 85–91.
• Solymosi, J.; Tóth, Cs. D. (2001), "Distinct Distances in the Plane", Discrete and Computational Geometry 25: 629–634.
• Solymosi, J.; Vu, Van H. (2008), "Near optimal bounds for the Erdős distinct distances problem in high dimensions", Combinatorica 28: 113–125.
• Székely, L. (1993), "Crossing numbers and hard Erdös problems in discrete geometry", Combinatorics, Probability and Computing 11: 1–10.
• Tardos, G. (2003), "On distinct sums and distinct distances", Advances in Mathematics 180: 275–289.
↑Jump back a section

## Read in another language

This page is available in 2 languages

Last modified on 21 March 2013, at 20:57