Erdős distinct distances problem
In discrete geometry, the Erdős distinct distances problem states that every set of points in the plane has a nearly-linear number of distinct distances. It was posed by Paul Erdős in 1946[1][2] and almost proven by Larry Guth and Nets Katz in 2015.[3][4][5]
The conjecture
In what follows let g(n) denote the minimal number of distinct distances between n points in the plane, or equivalently the smallest possible cardinality of their distance set. In his 1946 paper, Erdős proved the estimates
- [math]\displaystyle{ \sqrt{n-3/4}-1/2\leq g(n)\leq c n/\sqrt{\log n} }[/math]
for some constant [math]\displaystyle{ c }[/math]. The lower bound was given by an easy argument. The upper bound is given by a [math]\displaystyle{ \sqrt{n}\times\sqrt{n} }[/math] square grid. For such a grid, there are [math]\displaystyle{ O( n/\sqrt{\log n}) }[/math] numbers below n which are sums of two squares, expressed in big O notation; see Landau–Ramanujan constant. Erdős conjectured that the upper bound was closer to the true value of g(n), and specifically that (using big Omega notation) [math]\displaystyle{ g(n) = \Omega(n^c) }[/math] holds for every c < 1.
Partial results
Paul Erdős' 1946 lower bound of g(n) = Ω(n1/2) was successively improved to:
- g(n) = Ω(n4/5/log n) by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,[8]
- g(n) = Ω(n4/5) by László A. Székely in 1993,[9]
- g(n) = Ω(n6/7) by József Solymosi and Csaba D. Tóth in 2001,[10]
- g(n) = Ω(n(4e/(5e − 1)) − ɛ) by Gábor Tardos in 2003,[11]
- g(n) = Ω(n((48 − 14e)/(55 − 16e)) − ɛ) by Nets Katz and Gábor Tardos in 2004,[12]
- g(n) = Ω(n/log n) by Larry Guth and Nets Katz in 2015.[3]
Higher dimensions
Erdős also considered the higher-dimensional variant of the problem: for [math]\displaystyle{ d\ge 3 }[/math] let [math]\displaystyle{ g_d(n) }[/math] denote the minimal possible number of distinct distances among [math]\displaystyle{ n }[/math] points in [math]\displaystyle{ d }[/math]-dimensional Euclidean space. He proved that [math]\displaystyle{ g_d(n)=\Omega(n^{1/d}) }[/math] and [math]\displaystyle{ g_d(n)=O(n^{2/d}) }[/math] and conjectured that the upper bound is in fact sharp, i.e., [math]\displaystyle{ g_d(n)=\Theta(n^{2/d}) }[/math]. József Solymosi and Van H. Vu obtained the lower bound [math]\displaystyle{ g_d(n)=\Omega(n^{2/d - 2/d(d+2)}) }[/math] in 2008.[13]
See also
References
- ↑ "On sets of distances of [math]\displaystyle{ n }[/math] points". American Mathematical Monthly 53 (5): 248–250. 1946. doi:10.2307/2305092. http://www.renyi.hu/~p_erdos/1946-03.pdf.
- ↑ Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), The Erdős Distance Problem, Student Mathematical Library, 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1
- ↑ 3.0 3.1 "On the Erdős distinct distances problem in the plane". Annals of Mathematics 181 (1): 155–190. 2015. doi:10.4007/annals.2015.181.1.2.
- ↑ The Guth-Katz bound on the Erdős distance problem, a detailed exposition of the proof, by Terence Tao
- ↑ Guth and Katz’s Solution of Erdős’s Distinct Distances Problem, a guest post by János Pach on Gil Kalai's blog
- ↑ "On the different distances determined by [math]\displaystyle{ n }[/math] points". American Mathematical Monthly 59 (2): 85–91. 1952. doi:10.2307/2307105.
- ↑ "The number of different distances determined by [math]\displaystyle{ n }[/math] points in the plane". Journal of Combinatorial Theory. Series A 36 (3): 342–354. 1984. doi:10.1016/0097-3165(84)90041-4. http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf.
- ↑ "The number of different distances determined by a set of points in the Euclidean plane". Discrete & Computational Geometry 7: 342–354. 1992. doi:10.1007/BF02187820. http://www.math.ucsd.edu/~fan/wp/124distances.pdf.
- ↑ Székely, László A. (1993). "Crossing numbers and hard Erdös problems in discrete geometry". Combinatorics, Probability and Computing 11 (3): 1–10. doi:10.1017/S0963548397002976.
- ↑ "Distinct Distances in the Plane". Discrete & Computational Geometry 25 (4): 629–634. 2001. doi:10.1007/s00454-001-0009-z.
- ↑ "On distinct sums and distinct distances". Advances in Mathematics 180 (1): 275–289. 2003. doi:10.1016/s0001-8708(03)00004-5.
- ↑ Pach, János, ed (2004). "A new entropy inequality for the Erdős distance problem". Towards a theory of geometric graphs. Contemporary Mathematics. 342. Providence, RI: American Mathematical Society. pp. 119–126. doi:10.1090/conm/342/06136. ISBN 978-0-8218-3484-8.
- ↑ "Near optimal bounds for the Erdős distinct distances problem in high dimensions". Combinatorica 28: 113–125. 2008. doi:10.1007/s00493-008-2099-1.
External links
- William Gasarch's page on the problem
 |  |
