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 n^{1 − 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.

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.

Partial results

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

• g(n) = Ω(n^2/3) (Leo Moser, 1952),
• g(n) = Ω(n^5/7) (Fan Chung, 1984),
• g(n) = Ω(n^4/5/log n) (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992),
• g(n) = Ω(n^4/5) (László Székely, 1993),
• g(n) = Ω(n^6/7) (József Solymosi, C. D. Tóth, 2001),
• g(n) = Ω(n^{(4e/(5e − 1)) − e}) (Gábor Tardos, 2003),
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − e}) (Nets Hawk Katz, Gábor Tardos, 2004),
• g(n) = Ω(n/log n) (Larry Guth, Nets Hawk Katz, 2010).

Higher dimensions

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

See also

• Falconer's conjecture
• The Erdős unit distance problem

References

• Chung, F. (1984), "The number of different distances determined by n points in the plane", Journal of Combinatorial Theory, (A) 36: 342–354, doi:10.1016/0097-3165(84)90041-4 .
• Chung, F.; Szemerédi, E.; Trotter, W. T. (1984), "The number of different distances determined by a set of points in the Euclidean plane", Discrete and Computational Geometry 7: 342–354, doi:10.1007/BF02187820 .
• 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 .

External links

• William Gasarch's page on the problem
• János Pach's guest post on Gil Kalai's blog
• Terry Tao's blog entry on the Guth-Katz proof, gives a detailed exposition of the proof.