Erdős – Kacova věta - Erdős–Kac theorem
v teorie čísel, Erdős – Kacova věta, pojmenoval podle Paul Erdős a Mark Kac, a také známý jako základní věta o pravděpodobnostní teorie čísel, uvádí, že pokud ω (n) je počet odlišných hlavní faktory z n (sekvence A001221 v OEIS ), pak, volně řečeno, rozdělení pravděpodobnosti z
je standard normální distribuce. Toto je rozšíření Hardy – Ramanujanova věta, ve kterém se uvádí, že normální pořadí ω (n) je log log n s typickou chybou velikosti .
Přesné prohlášení
Pro všechny pevné A < b,
kde je normální (neboli „gaussovské“) rozdělení definované jako
Obecněji, pokud f (n) je silně aditivní funkce () s pro všechny hlavní str, pak
s
Kacova původní heuristika
Intuitivně Kacova heuristika pro výsledek říká, že pokud n je náhodně zvolené velké celé číslo, pak počet odlišných prvočíselných faktorů n je přibližně normálně distribuován s logem průměrů a odchylekn. Vyplývá to ze skutečnosti, že dané náhodné přirozené číslo n„události“ číslo n je dělitelný některými prvočísly str" pro každého str jsou vzájemně nezávislé.
Nyní označíme událost „číslo n je dělitelné str"od , zvažte následující součet náhodných proměnných indikátoru:
Tento součet počítá, kolik odlišných prvočísel ovlivňuje naše náhodné přirozené číslo n má. Lze prokázat, že tato částka splňuje Lindebergův stav, a proto Lindebergova centrální limitní věta zaručuje, že po příslušném změně měřítka bude výše uvedený výraz gaussovský.
Skutečný důkaz věty, díky Erdősovi, používá teorie sít aby byla výše uvedená intuice důsledná.
Numerické příklady
Věta Erdős – Kac znamená, že konstrukce čísla kolem jedné miliardy vyžaduje v průměru tři prvočísla.
Například 1 000 000 003 = 23 × 307 × 141623. Následující tabulka poskytuje číselné shrnutí růstu průměrného počtu zřetelných prvočísel přirozeného čísla s přibývajícím .
n | Počet číslice v n | Průměrný počet různých prvočísel | Standard odchylka |
---|---|---|---|
1,000 | 4 | 2 | 1.4 |
1,000,000,000 | 10 | 3 | 1.7 |
1,000,000,000,000,000,000,000,000 | 25 | 4 | 2 |
1065 | 66 | 5 | 2.2 |
109,566 | 9,567 | 10 | 3.2 |
10210,704,568 | 210,704,569 | 20 | 4.5 |
101022 | 1022+1 | 50 | 7.1 |
101044 | 1044+1 | 100 | 10 |
1010434 | 10434+1 | 1000 | 31.6 |
Přibližně 12,6% z 10 000 číslic je vytvořeno z 10 různých prvočísel a přibližně 68% je vytvořeno ze 7 až 13 prvočísel.
Dutá koule o velikosti planety Země naplněná jemným pískem by měla asi 1033 zrna. Objem o velikosti pozorovatelného vesmíru by měl asi 1093 zrnka písku. Mohlo by tam být místo pro 10185 kvantové řetězce v takovém vesmíru.
Čísla této velikosti - se 186 číslicemi - by pro konstrukci vyžadovaly v průměru pouze 6 prvočísel.
Je velmi obtížné, ne-li nemožné empiricky objevit Erdös-Kacův teorém, protože Gaussian se projeví až začíná být kolem . Přesněji, Rényi a Turán ukázal, že nejlepší možná jednotná asymptotická vazba na chybu v aproximaci Gaussian je .[1]
Reference
- ^ Rényi, A .; Turán, P. (1958). „K teorému Erdös-Kaca“ (PDF). Acta Arithmetica. 4 (1): 71–84.
- Erdős, Paul; Kac, Marku (1940). „Gaussův zákon chyb v teorii teoretických funkcí aditivních čísel“. American Journal of Mathematics. 62 (1/4): 738–742. doi:10.2307/2371483. ISSN 0002-9327. Zbl 0024.10203.
- Kuo, Wentang; Liu, Yu-Ru (2008). „Věta Erdős – Kac a její zobecnění“. V De Koninck, Jean-Marie; Granville, Andrew; Luca, Florian (eds.). Anatomie celých čísel. Na základě workshopu CRM, Montreal, Kanada, 13. - 17. března 2006. Sborník CRM a poznámky k přednášce. 46. Providence, RI: Americká matematická společnost. 209–216. ISBN 978-0-8218-4406-9. Zbl 1187.11024.
- Kac, Mark (1959). Statistická nezávislost v pravděpodobnosti, analýze a teorii čísel. John Wiley and Sons, Inc.