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

{\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\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. For such a grid, there are $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) $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)$ by Leo Moser in 1952,^[6]
$g (n) = Ω(n 5/7)$ by Fan Chung in 1984,^[7]

$g (n) = Ω(n 4/5 /log n)$ by Fan Chung, Endre Szemerédi, and William T. Trotter in 1992,^[8]
$g (n) = Ω(n 4/5)$ by László A. Székely in 1993,^[9]
$g (n) = Ω(n 6/7)$ by József Solymosi and Csaba D. Tóth in 2001,^[10]
$g (n) = Ω(n (4 e /(5 e - 1)) - ɛ)$ by Gábor Tardos in 2003,^[11]
$g (n) = Ω(n ((48 - 14 e)/(55 - 16 e)) - ɛ)$ 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 $d\geq 3$ let $g_{d}(n)$ denote the minimal possible number of distinct distances among $n$ points in $d$ -dimensional Euclidean space. He proved that $g_{d}(n)=\Omega (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)=\Theta (n^{2/d})$ . József Solymosi and Van H. Vu obtained the lower bound $g_{d}(n)=\Omega (n^{2/d-2/d(d+2)})$ in 2008.^[13]

References

^ Erdős, Paul (1946). "On sets of distances of $n$ points" (PDF). American Mathematical Monthly. 53 (5): 248–250. doi:10.2307/2305092. JSTOR 2305092.
^ 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
^ ^a ^b 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.
^ 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
^ Moser, Leo (1952). "On the different distances determined by $n$ points". American Mathematical Monthly. 59 (2): 85–91. doi:10.2307/2307105. JSTOR 2307105. MR 0046663.
^ Chung, Fan (1984). "The number of different distances determined by $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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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

[Erdos1946-1] Erdős, Paul (1946). "On sets of distances of $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

[GuthKatz2015-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 $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 $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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

The conjecture

Partial results

Higher dimensions

See also

References

External links