Misplaced Pages

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 and almost proven by Larry Guth and Nets Katz in 2015.

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

${\displaystyle {\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}}$

for some constant ${\displaystyle c}$. The lower bound was given by an easy argument. The upper bound is given by a ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ square grid. For such a grid, there are ${\displaystyle O(n/{\sqrt {\log n}})}$ 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) ${\displaystyle g(n)=\Omega (n^{c})}$ holds for every c < 1.

Partial results

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

• g(n) = Ω(n) by Leo Moser in 1952,
• g(n) = Ω(n) by Fan Chung in 1984,

• g(n) = Ω(n/log n) by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,
• g(n) = Ω(n) by László A. Székely in 1993,
• g(n) = Ω(n) by József Solymosi and Csaba D. Tóth in 2001,
• g(n) = Ω(n) by Gábor Tardos in 2003,
• g(n) = Ω(n) by Nets Katz and Gábor Tardos in 2004,
• g(n) = Ω(n/log n) by Larry Guth and Nets Katz in 2015.

Higher dimensions

Erdős also considered the higher-dimensional variant of the problem: for ${\displaystyle d\geq 3}$ let ${\displaystyle g_{d}(n)}$ denote the minimal possible number of distinct distances among ${\displaystyle n}$ points in ${\displaystyle d}$-dimensional Euclidean space. He proved that ${\displaystyle g_{d}(n)=\Omega (n^{1/d})}$ and ${\displaystyle g_{d}(n)=O(n^{2/d})}$ and conjectured that the upper bound is in fact sharp, i.e., ${\displaystyle g_{d}(n)=\Theta (n^{2/d})}$. József Solymosi and Van H. Vu obtained the lower bound ${\displaystyle g_{d}(n)=\Omega (n^{2/d-2/d(d+2)})}$ in 2008.

See also

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

References

1. Erdős, Paul (1946). "On sets of distances of ${\displaystyle n}$ points" (PDF). American Mathematical Monthly. 53 (5): 248–250. doi:10.2307/2305092. JSTOR 2305092.
2. Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), The Erdős Distance Problem, Student Mathematical Library, vol. 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1, MR 2721878
3. ^ Guth, Larry; Katz, Nets Hawk (2015). "On the Erdős distinct distances problem in the plane". Annals of Mathematics. 181 (1): 155–190. arXiv:1011.4105. doi:10.4007/annals.2015.181.1.2. MR 3272924. Zbl 1310.52019.
4. The Guth-Katz bound on the Erdős distance problem, a detailed exposition of the proof, by Terence Tao
5. Guth and Katz’s Solution of Erdős’s Distinct Distances Problem, a guest post by János Pach on Gil Kalai's blog
6. Moser, Leo (1952). "On the different distances determined by ${\displaystyle n}$ points". American Mathematical Monthly. 59 (2): 85–91. doi:10.2307/2307105. JSTOR 2307105. MR 0046663.
7. Chung, Fan (1984). "The number of different distances determined by ${\displaystyle n}$ points in the plane" (PDF). Journal of Combinatorial Theory. Series A. 36 (3): 342–354. doi:10.1016/0097-3165(84)90041-4. MR 0744082.
8. Chung, Fan; Szemerédi, Endre; Trotter, William T. (1992). "The number of different distances determined by a set of points in the Euclidean plane" (PDF). Discrete & Computational Geometry. 7: 342–354. doi:10.1007/BF02187820. MR 1134448. S2CID 10637819.
9. 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. MR 1464571. S2CID 36602807.
10. Solymosi, József; Tóth, Csaba D. (2001). "Distinct Distances in the Plane". Discrete & Computational Geometry. 25 (4): 629–634. doi:10.1007/s00454-001-0009-z. MR 1838423.
11. Tardos, Gábor (2003). "On distinct sums and distinct distances". Advances in Mathematics. 180 (1): 275–289. doi:10.1016/s0001-8708(03)00004-5. MR 2019225.
12. Katz, Nets Hawk; Tardos, Gábor (2004). "A new entropy inequality for the Erdős distance problem". In Pach, János (ed.). Towards a theory of geometric graphs. Contemporary Mathematics. Vol. 342. Providence, RI: American Mathematical Society. pp. 119–126. doi:10.1090/conm/342/06136. ISBN 978-0-8218-3484-8. MR 2065258.
13. Solymosi, József; Vu, Van H. (2008). "Near optimal bounds for the Erdős distinct distances problem in high dimensions". Combinatorica. 28: 113–125. doi:10.1007/s00493-008-2099-1. MR 2399013. S2CID 2225458.

External links

• William Gasarch's page on the problem

• Conjectures
• Paul Erdős
• Discrete geometry
• Eponyms in geometry