Erdős sejtése a különböző távolságok számáról

Az Erdős-sejtés a különböző távolságok számáról a kombinatorikus geometria állítása , amely szerint a sík különböző pontjai között nem kisebb, mint különböző távolságok. A sejtést Erdős Pal fogalmazta meg 1946 - ban , 2010 -ben Larry Guth és Nets Hawk Katz jelentett be egy lehetséges megoldást erre a problémára [ 1] , Guth és Katz végső bizonyítása 2015 -ben készült el . $n$ $n^{1-o(1)}$

Hipotézis

Legyen a minimális számú különböző távolság a pontok között a síkon. 1946-ban Erdős határt szabott valami állandónak . Az alsó korlátot egyszerű bizonyítással kapjuk meg, a felső korlátot négyzetrács alapján kapjuk meg, és az alapján , hogy a két négyzet összegénél kisebb egész szám egyenlő a Landau-Ramanujan eredmény szerint . Erdős azt javasolta, hogy a felső korlát közelebb van a valódi értékhez , és mindenre igaz . $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$

Eredmények

Az Erdős alsó korlát g ( n ) = Ω ( n 1/2 ) következetesen javult:

g ( n ) = Ω( n 2/3 ) - Leo Moser ( angolul Leo Moser ), 1952;
g ( n ) = Ω ( n 5/7 ) - Fan Chung , 1984 ;
g ( n ) = Ω( n 4/5 /log n ) - Fang Chun, Szemedi Endre , William Trotter, 1992;
g ( n ) = Ω( n 4/5 ) - Székely László 1993;
g ( n ) = Ω ( n 6/7 ) - Jozsef Shoimoshi , Chaba Tot, 2001;
g ( n ) = Ω( n (4 e /(5 e − 1)) − e ) Tardos Gábor, 2003 ;
g ( n ) = Ω( n ((48 − 14 e )/(55 − 16 e )) − e ) – Nets Katz, Gábor Tardos, 2004;
g ( n ) = Ω( n /log n ) – Larry Guth, Nets Katz, 2015.

Egyéb méretek

Erdős a nagyobb térméretek problémáját is figyelembe vette. Legyen az euklideszi dimenziós tér pontjaihoz tartozó különböző távolságok minimális száma . Bebizonyította, hogy g d ( n ) = Ω( n 1/ d ) és g d ( n ) = O( n 2/ d ) , és feltételezte, hogy a felső korlát közel van, azaz g d ( n ) = Θ( n 2 ) / d ) . 2008- ban Shoimoshi és Van Vu ( angol. Van Vu) ) alsó korlátot kapott g d ( n ) = O( n 2/ d (1-1/( d +2)) ) . $g_{d}(n)$ $n$ $d$

Lásd még

Falconer sejtése _ __
Mértékegység távolság grafikonja

Jegyzetek

↑ Guth, l. & Katz, NH (2010), Az Erdős megkülönböztetett távolságproblémáról a síkon, arΧiv : 1011.4105 . . Lásd még Guta-Kac határát az Erdős-távolság problémájához Archivált 2013. április 25-én a Wayback Machine -nél és Guta-Kac megoldását a különböző távolságok Erdős-problémájára Archivált 2013. május 9-én a Wayback Machine -nél .

Irodalom

Chung, F. (1984), A sík n pontja által meghatározott különböző távolságok száma , 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 > Archiválva : 2012. március 3. a Wayback Machine -nél .
Chung, F .; Szemerédi, E. & Trotter, WT (1984), Az euklideszi síkban lévő pontkészlet által meghatározott különböző távolságok száma , Discrete and Computational Geometry vol. 7: 342–354, doi : 10.1007/BF02187820 , < http:/ /www.math.ucsd.edu/~fan/wp/124distances.pdf > Archiválva : 2012. március 3. a Wayback Machine -nél
Erdős, P. (1946), On sets of distances of n points , American Mathematical Monthly vol. 53: 248–250 , < http://www.renyi.hu/~p_erdos/1946-03.pdf > Archivált márciustól 5, 2012 a Wayback Machine -nél
Garibaldi, J.; Iosevich, A. & Senger, S. (2011), The Erdős Distance Problem , Providence, RI: American Mathematical Society
Guth, L. & Katz, NH (2010), Az Erdős megkülönböztetett távolságproblémáról a síkon, arΧiv : 1011.4105 .
Moser, L. (1952): Az n pont által meghatározott különböző távolságokról , American Mathematical Monthly vol. 59: 85–91 .
Solymosi, J. & Tóth, Cs. D. (2001), Distinct Distances in the Plane, Discrete and Computational Geometry vol. 25: 629–634 .
Solymosi, J. & Vu, Van H. (2008), Near optimal bounds for the Erdős different distances problem in high dimensions, Combinatorica T. 28: 113–125 .
Székely, L. (1993), Keresztező számok és kemény Erdös-problémák a diszkrét geometriában, Kombinatorika, Valószínűség és számítástechnika 11. kötet: 1–10 .
Tardos, G. (2003), On different sum and different distances, Advances in Mathematics vol. 180: 275–289 .

Linkek

William Gasarch. Egy weboldal az Erdos-távolság problémájáról
Pach János: Guth és Katz megoldása Erdős megkülönböztető távolságai problémájára Archivált 2013. május 9. a Wayback Machine -nál ( Gil Kalay blogján )
Részletes Gut-Katz-bizonyíték archiválva 2013. április 25-én a Wayback Machine oldalán, Terence Tao blogján