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.
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 for some constant . The lower bound was given by an easy argument, the upper bound is given by a square grid (as there are 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, holds for every c < 1.
Paul Erdős' 1946 lower bound of g(n) = Ω(n1/2) was successively improved to:
- g(n) = Ω(n2/3) (Leo Moser, 1952),
- g(n) = Ω(n5/7) (Fan Chung, 1984),
- g(n) = Ω(n4/5/log n) (Fan Chung, Endre Szemerédi, W. T. Trotter, 1992),
- g(n) = Ω(n4/5) (László Székely, 1993),
- g(n) = Ω(n6/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).
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.
- 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.