Twierdzenie Erdősa-Kaca - Erdős–Kac theorem
W teorii liczb , twierdzenie Erdős-Kac , nazwany Paul Erdős i Mark Kac , a także znany jako fundamentalnego twierdzenia probabilistycznej teorii liczb , stwierdza, że jeśli ω ( n ) jest liczbą różnych czynników pierwszych z n , a następnie, luźno rzecz biorąc, rozkład prawdopodobieństwa o
jest standardowym rozkładem normalnym . ( jest sekwencją A001221 w OEIS.) Jest to rozszerzenie twierdzenia Hardy'ego-Ramanujana , które mówi, że normalny porządek ω( n ) to log log n z typowym błędem wielkości .
Dokładne stwierdzenie
Dla dowolnego ustalonego a < b ,
gdzie jest rozkład normalny (lub „Gaussowski”), zdefiniowany jako
Bardziej ogólnie, jeśli f( n ) jest funkcją silnie addytywną ( ) ze wszystkimi liczbami pierwszymi p , wtedy
z
Oryginalna heurystyka Kaca
Intuicyjnie, heurystyka Kaca dla wyniku mówi, że jeśli n jest losowo wybraną dużą liczbą całkowitą, to liczba odrębnych czynników pierwszych n ma w przybliżeniu rozkład normalny ze średnią i logarytmem wariancji log n . Wynika to z faktu, że przy danej losowej liczbie naturalnej n zdarzenia „liczba n jest podzielna przez pewną liczbę pierwszą p ” dla każdego p są od siebie niezależne.
Teraz, oznaczając zdarzenie „liczba n jest podzielna przez p ” przez , rozważmy następującą sumę wskaźników zmiennych losowych:
Ta suma zlicza, ile odrębnych czynników pierwszych ma nasza losowa liczba naturalna n . Można wykazać, że suma ta spełnia warunek Lindeberga , a zatem centralne twierdzenie graniczne Lindeberga gwarantuje, że po odpowiednim przeskalowaniu powyższe wyrażenie będzie gaussowskie.
Rzeczywisty dowód twierdzenia, dzięki Erdősowi, wykorzystuje teorię sitową, aby sprecyzować powyższą intuicję.
Przykłady liczbowe
Twierdzenie Erdősa-Kaca oznacza, że konstrukcja liczby około miliarda wymaga średnio trzech liczb pierwszych.
Na przykład 1 000 000 003 = 23 × 307 × 141623. Poniższa tabela zawiera liczbowe podsumowanie wzrostu średniej liczby różnych czynników pierwszych liczby naturalnej wraz ze wzrostem .
n | Liczba
cyfry w n |
Średnia liczba
różnych liczb pierwszych |
Standard
odchylenie |
---|---|---|---|
1000 | 4 | 2 | 1,4 |
1 000 000 000 | 10 | 3 | 1,7 |
1 000 000 000 000 000 000 000 000 | 25 | 4 | 2 |
10 65 | 66 | 5 | 2.2 |
10 9 566 | 9 567 | 10 | 3.2 |
10 210 704 568 | 210 704 569 | 20 | 4,5 |
10 10 22 | 10 22 +1 | 50 | 7,1 |
10 10 44 | 10 44 +1 | 100 | 10 |
10 10 434 | 10 434 +1 | 1000 | 31,6 |
Około 12,6% z 10 000 liczb cyfrowych składa się z 10 różnych liczb pierwszych, a około 68% składa się z od 7 do 13 liczb pierwszych.
Pusta kula wielkości planety Ziemia wypełniona drobnym piaskiem miałaby około 10 33 ziaren. Objętość wielkości obserwowalnego wszechświata miałaby około 10 93 ziaren piasku. W takim wszechświecie może być miejsce na 10 185 strun kwantowych.
Liczby tej wielkości — liczące 186 cyfr — wymagałyby do budowy średnio tylko 6 liczb pierwszych.
Odkrycie twierdzenia Erdösa-Kaca empirycznie jest bardzo trudne, jeśli nie niemożliwe, ponieważ Gaussian pojawia się tylko wtedy, gdy zaczyna być w pobliżu . Dokładniej, Rényi i Turán pokazali, że najlepszym możliwym jednorodnym asymptotycznym wiązaniem błędu w przybliżeniu do Gaussa jest .
Bibliografia
- Erdős, Paul ; Kac, Marek (1940). „Prawo Gaussa błędów w teorii addytywnych funkcji teoretycznych liczb”. 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). „Twierdzenie Erdősa-Kaca i jego uogólnienia”. W De Koninck, Jean-Marie; Granville, Andrzej ; Luca, Florian (red.). Anatomia liczb całkowitych. Na podstawie warsztatu CRM, Montreal, Kanada, 13-17 marca 2006 . Procedury CRM i notatki do wykładów. 46 . Providence, RI: Amerykańskie Towarzystwo Matematyczne . s. 209–216. Numer ISBN 978-0-8218-4406-9. Zbl 1187.11024 .
- Kac, Marek (1959). Statystyczna niezależność w prawdopodobieństwie, analizie i teorii liczb . John Wiley i Synowie, Inc.