Erdős-féle eltérő távolságok problémája

A diszkrét geometria területén az Erdős-féle eltérő távolságok problémája az az állítás, mi szerint egy síkban elhelyezkedő n különböző pont között legalább n^{1 − o(1)} különböző távolság létezik. A problémát Erdős Pál vetette fel 1946-ban, és (Guth & Katz 2015) oldotta meg.

A következőkben jelölje g(n) a sík n pontja közti minimális különböző távolságok számát.1946-os cikkében Erdős igazolta a ${\displaystyle {\sqrt {n-3/4}}-1/2\leq g(n)\leq cn/{\sqrt {\log n}}}$ becslést néhány ${\displaystyle c}$ konstansra. Az alsó korlát viszonylag könnyen belátható, a felső korlátot egy ${\displaystyle {\sqrt {n}}\times {\sqrt {n}}}$ négyzetrács adja (hiszen ${\displaystyle O(n/{\sqrt {\log n}})}$ olyan n-nél kisebb szám van, ami két négyzetszám összegeként felírható, lásd Landau–Rámánudzsan-konstans). Erdős sejtése szerint a felső korlát közelebb van a g(n) tényleges értékéhez, konkrétabban ${\displaystyle g(n)=\Omega (n^{c})}$ igaz minden c < 1 konstansra.

Erdős 1946-os g(n) = Ω(n^1/2) alsó korlátját sikeresen javították a következőkre:

• g(n) = Ω(n^2/3) (Moser 1952)
• g(n) = Ω(n^5/7) (Chung 1984)
• g(n) = Ω(n^4/5/log n) (Chung, Szemerédi & Trotter 1992)
• g(n) = Ω(n^4/5) (Székely 1993)
• g(n) = Ω(n^6/7) (Solymosi & Tóth 2001)
• g(n) = Ω(n^{(4e/(5e − 1)) − ɛ}) (Tardos 2003)
• g(n) = Ω(n^{((48 − 14e)/(55 − 16e)) − ɛ}) (Katz & Tardos 2004)
• g(n) = Ω(n/log n) (Guth & Katz 2015)

Erdős foglalkozott a probléma magasabb dimenziójú változataival is: d≥3-ra jelölje g_d(n) a d dimenziós euklideszi térben n pont közötti lehetséges távolságok minimális számát. Igazolta, hogy g_d(n) = Ω(n^1/d) és g_d(n) = O(n^2/d), továbbá sejtése szerint a felső korlát valójában éles, tehát g_d(n) = Θ(n^2/d) . (Solymosi & Vu 2008) pontosították az alsó korlátot a következőre: g_d(n) = Ω(n^{2/d - 2/d(d+2)}).

• Falconer-sejtés
• Erdős-féle egységtávolság-probléma

• Chung, Fan (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, <http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf>.
• Chung, Fan; Szemerédi, Endre & Trotter, William T. (1992), "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, <http://www.math.ucsd.edu/~fan/wp/124distances.pdf>.
• Erdős, Paul (1946), "On sets of distances of n points", American Mathematical Monthly 53: 248–250, 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, vol. 56, Student Mathematical Library, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1.
• Guth, Larry & Katz, Nets Hawk (2015), "On the Erdős distinct distances problem in the plane", Annals of Mathematics 181 (1): 155-190, DOI 10.4007/annals.2015.181.1.2. See also The Guth-Katz bound on the Erdős distance problem by Terry Tao and Guth and Katz’s Solution of Erdős’s Distinct Distances Problem by Pach János.
• Katz, Nets Hawk & Tardos, Gábor (2004), "A new entropy inequality for the Erdős distance problem", in Pach, János, Towards a theory of geometric graphs, vol. 342, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 119-126, ISBN 0-8218-3484-3, DOI 10.1090/conm/342/06136
• Moser, Leo (1952), "On the different distances determined by n points", American Mathematical Monthly 59: 85–91, DOI 10.2307/2307105.
• Solymosi, József & Tóth, Csaba D. (2001), "Distinct Distances in the Plane", Discrete and Computational Geometry 25: 629–634, DOI 10.1007/s00454-001-0009-z.
• 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.
• Székely, László A. (1993), "Crossing numbers and hard Erdös problems in discrete geometry", Combinatorics, Probability and Computing 11: 1–10, DOI 10.1017/S0963548397002976.
• Tardos, Gábor (2003), "On distinct sums and distinct distances", Advances in Mathematics 180: 275–289, DOI 10.1016/s0001-8708(03)00004-5.

• 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.