Erdősova domněnka o počtu různých vzdáleností

Erdős dohad o množství různých vzdáleností je prohlášení kombinatorické geometrie , podle kterého tam jsou ne méně než různé vzdálenosti mezi různými body na letadle. Dohadu zformuloval Pal Erdős v roce 1946 , v roce 2010 Larry Guth a Nets Hawk Katz oznámili možné řešení tohoto problému [ 1] , finální důkaz Gutha a Katze byl dokončen v roce 2015 . $n$ $n^{1-o(1)}$

Hypotéza

Nechť minimální počet různých vzdáleností mezi body v rovině. V roce 1946 se Erdős ukázal jako hranice pro nějakou konstantu . Spodní hranici získáme jednoduchým důkazem, horní hranici získáme na základě čtvercové mřížky a skutečnosti, že počet celých čísel menší než součet dvou čtverců se rovná podle Landau-Ramanujanova výsledku . Erdős navrhl, že horní hranice je blíže skutečné hodnotě a platí pro všechny . $g(n)$ $n$ ${\sqrt {n-3/4}}-1/2\leqslant g(n)\leqslant cn/{\sqrt {\log n}}$ $C$ ${\sqrt {n}}\times {\sqrt {n}}$ $n$ $O(n/{\sqrt {\log n)))$ $g(n)$ $g(n)=\Omega (n^{c})$ $c<1$

Výsledky

Erdős spodní mez g ( n ) = Ω ( n 1/2 ) byla trvale vylepšena:

g ( n ) = Ω ( n 2/3 ) - Leo Moser ( anglicky Leo Moser ), 1952;
g ( n ) = Ω ( n 5/7 ) - Fan Chung , 1984 ;
g ( n ) = Ω ( n 4/5 /log n ) - Fang Chun, Endre Szemeredi , William Trotter, 1992;
g ( n ) = Ω ( n 4/5 ) - Laszlo Szekely 1993;
g ( n ) = Ω ( n 6/7 ) - Jozsef Shoimoshi , Chaba Tot, 2001;
g ( n ) = Ω( n (4 e /(5 e − 1)) − e ) od Gábora Tardose , 2003 ;
g ( n ) = Ω( n ((48 − 14 e )/(55 − 16 e )) − e ) — Nets Katz, Gabor Tardos, 2004;
g ( n ) = Ω ( n /log n ) - Larry Guth, Nets Katz, 2015.

Jiné rozměry

Erdős také zvažoval problém pro vyšší vesmírné dimenze. Nechť minimální počet zřetelných vzdáleností pro body v euklidovském prostoru dimenze . Dokázal, že g d ( n ) = Ω( n 1/ d ) a g d ( n ) = O( n 2/ d ) a předpokládal, že horní mez je blízko, tj. g d ( n ) = Θ( n 2 / d ) . V roce 2008 Shoimoshi a Van Vu ( angl. Van Vu) ) získali dolní mez gd ( n ) = O( n 2/ d ( 1-1/( d +2 )) ) . $g_{d}(n)$ $n$ $d$

Viz také

Falconerova domněnka _ __
Graf jednotkové vzdálenosti

Poznámky

↑ Guth, l. & Katz, NH (2010), O problému zřetelné vzdálenosti Erdős na rovině, arΧiv : 1011.4105 . . Viz také hranice Guta-Kac pro problém Erdős vzdálenosti Archivováno 25. dubna 2013 na Wayback Machine a Guta-Kacovo řešení problému Erdős různých vzdáleností Archivováno 9. května 2013 na Wayback Machine .

Literatura

Chung, F. (1984), Počet různých vzdáleností určených n body v rovině , Journal of Combinatorial Theory , (A) sv. 36: 342–354, doi : 10.1016/0097-3165(84)90041-4 , < http://www.math.ucsd.edu/~fan/mypaps/fanpap/67distances.pdf > Archivováno 3. března 2012 ve Wayback Machine .
Chung, F .; Szemerédi, E. & Trotter, WT (1984), Počet různých vzdáleností určených sadou bodů v euklidovské rovině , Discrete and Computational Geometry vol. 7: 342–354, doi : 10.1007/BF02187820 , < http:/ /www.math.ucsd.edu/~fan/wp/124distances.pdf > Archivováno 3. března 2012 na Wayback Machine
Erdős, P. (1946), O souborech vzdáleností n bodů , American Mathematical Monthly vol. 53: 248–250 , < http://www.renyi.hu/~p_erdos/1946-03.pdf > Archivováno z března 5, 2012 na Wayback Machine
Garibaldi, J.; Iosevich, A. & Senger, S. (2011), The Erdős Distance Problem , Providence, RI: American Mathematical Society
Guth, L. & Katz, NH (2010), O problému zřetelné vzdálenosti Erdős na rovině, arΧiv : 1011.4105 .
Moser, L. (1952), O různých vzdálenostech určených n body, American Mathematical Monthly vol. 59: 85–91 .
Solymosi, J. & Tóth, Cs. D. (2001), Distinct Distances in the Plane, Discrete and Computational Geometry , svazek 25: 629–634 .
Solymosi, J. & Vu, Van H. (2008), Blízké optimální hranice pro Erdősův problém odlišných vzdáleností ve vysokých dimenzích, Combinatorica T. 28: 113–125 .
Székely, L. (1993), Křížení čísel a tvrdé Erdösovy problémy v diskrétní geometrii, Combinatorics, Probability and Computing, svazek 11: 1–10 .
Tardos, G. (2003), O odlišných součtech a odlišných vzdálenostech, Advances in Mathematics vol. 180: 275–289 .

Odkazy

William Gasarch. Webová stránka o problému vzdálenosti Erdos
János Pach: Guth and Katz's Solution of Erdős's Distinct Distances Problem Archived 9. května 2013 na Wayback Machine (na blogu Gil Kalay )
Podrobný důkaz Gut-Katz Archivováno 25. dubna 2013 na Wayback Machine na blogu Terence Taa