Erdőův problém se značnými vzdálenostmi - Erdős distinct distances problem

v diskrétní geometrie, Erdőův problém se značnými vzdálenostmi uvádí, že každá sada bodů v rovině má téměř lineární počet odlišných vzdáleností. Bylo to představováno Paul Erdős v roce 1946 a téměř prokázáno Guth & Katz (2015).

Domněnka

V následujícím textu pojďme $G (n)$ označují minimální počet různých vzdáleností mezi $n$ body v rovině nebo ekvivalentně nejmenší možný mohutnost Jejich nastavená vzdálenost. Ve svém článku z roku 1946 Erdős odhady prokázal

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

pro nějakou konstantu ${ displaystyle c}$ . Dolní mez byla dána jednoduchým argumentem. Horní mez je dána a ${ displaystyle { sqrt {n}} krát { sqrt {n}}}$ čtvercová mřížka. Pro takovou mřížku existují ${ displaystyle O (n / { sqrt { log n}})}$ čísla níže n což jsou součty dvou čtverců vyjádřené v velká O notace; vidět Konstanta Landau – Ramanujan. Erdős se domníval, že horní hranice je blíže skutečné hodnotě G(n), a to konkrétně (pomocí velká nota Omega ) ${ displaystyle g (n) = Omega (n ^ {c})}$ platí pro každého $C < 1$ .

Částečné výsledky

Paul Erdős '1946 dolní hranice $G (n) = Ω (n 1/2)$ byl postupně vylepšen na:

$G (n) = Ω (n 2/3)$ (Moser 1952 )
$G (n) = Ω (n 5/7)$ (Chung 1984 )
$G (n) = Ω (n 4/5 / log n)$ (Chung, Szemerédi a Trotter 1992 )
$G (n) = Ω (n 4/5)$ (Székely 1993 )
$G (n) = Ω (n 6/7)$ (Solymosi & Tóth 2001 )
$G (n) = Ω (n (4 E /(5 E - 1)) - ɛ)$ (Tardos 2003 )
$G (n) = Ω (n ((48 - 14 E)/(55 - 16 E)) - ɛ)$ (Katz & Tardos 2004 )
$G (n) = Ω (n / log n)$ (Guth & Katz 2015 )

Vyšší rozměry

Erdős také uvažoval o vícerozměrné variantě problému: pro ${ displaystyle d geq 3}$ nechat ${ displaystyle g_ {d} (n)}$ označují minimální možný počet různých vzdáleností mezi ${ displaystyle n}$ body v ${ displaystyle d}$ -dimenzionální Euklidovský prostor. Dokázal to ${ displaystyle g_ {d} (n) = Omega (n ^ {1 / d})}$ a ${ displaystyle g_ {d} (n) = O (n ^ {2 / d})}$ a domníval se, že horní hranice je ve skutečnosti ostrá, tj. ${ displaystyle g_ {d} (n) = Theta (n ^ {2 / d})}$ . Solymosi & Vu (2008) získal dolní mez ${ displaystyle g_ {d} (n) = Omega (n ^ {2 / d-2 / d (d + 2)})}$ .

Viz také

Reference

Chung, Fan (1984), "Počet různých vzdáleností určený $n$ body v rovině " (PDF), Journal of Combinatorial Theory, Series A, 36 (3): 342–354, doi:10.1016/0097-3165(84)90041-4, PAN 0744082CS1 maint: ref = harv (odkaz).
Chung, Fan; Szemerédi, Endre; Trotter, William T. (1992), „Počet různých vzdáleností určených množinou bodů v euklidovské rovině“ (PDF), Diskrétní a výpočetní geometrie, 7: 342–354, doi:10.1007 / BF02187820, PAN 1134448CS1 maint: ref = harv (odkaz).
Erdős, Paul (1946), "Na množinách vzdáleností $n$ body " (PDF), Americký matematický měsíčník, 53 (5): 248–250, doi:10.2307/2305092, JSTOR 2305092.
Garibaldi, Julia; Iosevich, Alex; Senger, Steven (2011), Erdőův problém vzdálenosti, Studentská matematická knihovna, 56, Providence, RI: American Mathematical Society, ISBN 978-0-8218-5281-1, PAN 2721878.
Guth, Larry; Katz, Nets Hawk (2015), „K problému Erdőových odlišných vzdáleností v letadle“, Annals of Mathematics, 181 (1): 155–190, arXiv:1011.4105, doi:10.4007 / annals.2015.181.1.2, PAN 3272924, Zbl 1310.52019CS1 maint: ref = harv (odkaz). Viz také Guth-Katz navázal na problém Erdőovy vzdálenosti podle Terry Tao a Guth a Katzovo řešení problému s Erdősovými odlišnými vzdálenostmi podle János Pach.
Katz, Nets Hawk; Tardos, Gábor (2004), „Nová entropická nerovnost pro Erdőův problém vzdálenosti“, Pach, János (ed.), Směrem k teorii geometrických grafů, Současná matematika, 342„Providence, RI: American Mathematical Society, s. 119–126, doi:10.1090 / conm / 342/06136, ISBN 978-0-8218-3484-8, PAN 2065258
Moser, Leo (1952), „Na různé vzdálenosti určené $n$ body ", Americký matematický měsíčník, 59 (2): 85–91, doi:10.2307/2307105, JSTOR 2307105, PAN 0046663CS1 maint: ref = harv (odkaz).
Solymosi, József; Tóth, Csaba D. (2001), „Zřetelné vzdálenosti v rovině“, Diskrétní a výpočetní geometrie, 25 (4): 629–634, doi:10.1007 / s00454-001-0009-z, PAN 1838423CS1 maint: ref = harv (odkaz).
Solymosi, József; Vu, Van H. (2008), „Téměř optimální hranice pro problém Erdőových zřetelných vzdáleností ve vysokých rozměrech“, Combinatorica, 28: 113–125, doi:10.1007 / s00493-008-2099-1, PAN 2399013CS1 maint: ref = harv (odkaz).
Székely, László A. (1993), „Křížení čísel a těžké Erdösovy problémy v diskrétní geometrii“, Kombinatorika, pravděpodobnost a výpočet, 11 (3): 1–10, doi:10.1017 / S0963548397002976, PAN 1464571CS1 maint: ref = harv (odkaz).
Tardos, Gábor (2003), „O různých částkách a různých vzdálenostech“, Pokroky v matematice, 180: 275–289, doi:10.1016 / s0001-8708 (03) 00004-5, PAN 2019225.

externí odkazy

William Gasarch je strana o problému
János Pach je příspěvek pro hosty na Gil Kalai blog uživatele
Terry Tao blog uživatele vstup na důkazu Guth-Katz poskytuje podrobnou výklad důkazu.