Twierdzenie Erdősa – Kaca

W teorii liczb twierdzenie Erdősa – Kaca , nazwane na cześć Paula Erdősa i Marka Kaca , a także znane jako fundamentalne twierdzenie probabilistycznej teorii liczb , stwierdza, że jeśli ω ( n ) jest liczbą różnych czynników pierwszych n , to luźno mówiąc, rozkład prawdopodobieństwa

{\ Displaystyle {\ Frac {\ omega (n) - \ log \ log n} {\ sqrt {\ log \ log n}}}}

jest standardowym rozkładem normalnym . ( ${\ Displaystyle \ omega (n)}$ to sekwencja A001221 w OEIS .) Jest to rozszerzenie twierdzenia Hardy'ego-Ramanujana , które stwierdza, że normalny porządek ω ( n ) to log log n z a typowy błąd wielkości ${\ displaystyle {\ sqrt {\ log \ log n}}}$ .

Precyzyjne stwierdzenie

Dla dowolnego ustalonego a < b ,

{\ Displaystyle \ lim _ {x \rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {\omega (n)-\log \log n} {\sqrt {\log \log n}}}\leq b\right\}\right)=\Phi (a,b)}

gdzie jest rozkładem normalnym (lub „gaussowskim”), zdefiniowanym jako ${\ Displaystyle \ Phi (a, b)}$

{\ Displaystyle \ Phi (a, b) = {\ Frac {1} {\ sqrt {2 \ pi}}} \ int _ {a} ^ {b} e ^ {-t ^ {2}/2} \ tł.}

Bardziej ogólnie, jeśli fa ( n ) jest funkcją silnie addytywną ( ${\ Displaystyle \ scriptstyle f (p_ {1 }^{a_{1}}\cdots p_{k}^{a_{k}})=f(p_{1})+\cdots +f(p_{k})} )$ z ${\ Displaystyle \ scriptstyle | f (p) | \ równoważnik 1}$ dla wszystkich liczb pierwszych p wtedy

{\ Displaystyle \ lim _ {x \ rightarrow \infty }\left({\frac {1}{x}}\cdot \#\left\{n\leq x:a\leq {\frac {f(n)-A(n)}{B(n )}}\równik b\prawo\}\prawo)=\Phi (a,b)}

z

{\ Displaystyle A (n) = \ suma _ {p \ równoważnik n} {\ Frac {f (p)}} {p}}, \ qquad B (n) = {\ sqrt {\ suma _ {p \ równoważnik n }{\frac {f(p)^{2}}{p}}}}.}

Oryginalna heurystyka Kaca

Intuicyjnie, heurystyka Kaca dla wyniku mówi, że jeśli n jest losowo wybraną dużą liczbą całkowitą, to liczba różnych czynników pierwszych n ma w przybliżeniu rozkład normalny ze średnią i log wariancji log n . Wynika to z faktu, że przy 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 ${\ displaystyle n_ {p}}$ , rozważmy następującą sumę wskaźników losowych zmiennych:

{\ Displaystyle I_ {n_ {2}} + ja_ {n_ {3}} + ja_ {n_ {5}} + ja_ {n_ {7} }+\lddotki }

Ta suma określa, ile różnych czynników pierwszych ma nasza losowa liczba naturalna n . Można wykazać, że suma ta spełnia warunek Lindeberga , a zatem centralne twierdzenie Lindeberga gwarantuje, że po odpowiednim przeskalowaniu powyższe wyrażenie będzie gaussowskie.

Rzeczywisty dowód twierdzenia, ze względu na Erdősa, wykorzystuje teorię sit , aby uczynić powyższą intuicję rygorystyczną.

Przykłady liczbowe

Twierdzenie Erdősa – Kaca oznacza, że konstrukcja liczby około miliarda wymaga średnio trzech liczb pierwszych.

$n}$ 307 × 141623. Poniższa tabela zawiera liczbowe podsumowanie wzrostu średniej liczby różnych czynników pierwszych liczby naturalnej wraz ze wzrostem $displaystyle$ .

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 ⁶⁵	66	5	2.2
10 ⁹⁵⁶⁶	9567	10	3.2
10 ^{210 704 568}	210 704 569	20	4.5
10 ^{10 ²²}	10 ²² + 1	50	7.1
10 ^{10 ⁴⁴}	10 ⁴⁴ + 1	100	10
10 ^{10 ⁴³⁴}	10 ⁴³⁴ + 1	1000	31,6

Rozprzestrzeniający się rozkład Gaussa różnych liczb pierwszych ilustrujący twierdzenie Erdosa-Kac

Około 12,6% z 10 000 cyfr składa się z 10 różnych liczb pierwszych, a około 68% z 7 do 13 liczb pierwszych.

Wydrążona kula wielkości planety Ziemia wypełniona drobnym piaskiem zawierałaby około 10 ³³ ziaren. Objętość wielkości obserwowalnego Wszechświata zawierałaby około 10 ⁹³ ziaren piasku. W takim wszechświecie może być miejsce na 10 ^{185 strun kwantowych.}

Liczby tej wielkości — ze 186 cyframi — wymagałyby średnio tylko 6 liczb pierwszych do skonstruowania.

$displaystyle$ pojawia się tylko wtedy, gdy zaczyna osiągać około $10 ^ {100}}$ . Dokładniej, Rényi i Turán wykazali, że najlepszą możliwą jednolitą asymptotyczną granicą błędu w przybliżeniu do Gaussa jest ${\ Displaystyle O \ lewo ({\ Frac {1} {\ sqrt { \log \log n}}}\right)}$ .

Erdős, Paweł ; Kac, Marek (1940). „Prawo błędów Gaussa w teorii addytywnych funkcji teoretycznych liczb”. American Journal of Mathematics . 62 (1/4): 738–742. doi : 10.2307/2371483 . ISSN 0002-9327 . JSTOR 2371483 . 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 warsztatów CRM, Montreal, Kanada, 13-17 marca 2006 r . Postępowanie CRM i notatki z wykładów. Tom. 46. Providence, RI: Amerykańskie Towarzystwo Matematyczne . s. 209–216. ISBN 978-0-8218-4406-9 . Zbl 1187.11024 .
Kac, Marek (1959). Niezależność statystyczna w rachunku prawdopodobieństwa, analizie i teorii liczb . John Wiley and Sons, Inc.

Linki zewnętrzne