Věta o prvočíslech: definice a vzorec n/ln(n)

Formální tvrzení

Nejběžnější formou věty o prvočíslech je:

• π(x) ~ x / ln x při x → ∞,
• ekvivalentně: lim_{x→∞} π(x) / (x/ln x) = 1.

Z praktického hlediska to znamená, že pravděpodobnost, že náhodně zvolené velké celé číslo přibližně velikosti x bude prvočíslem, je přibližně 1/ln(x). Z této hustoty plyne i fakt, že průměrná mezera mezi po sobě jdoucími prvočísly v okolí x je zhruba ln(x).

Intuitivní vysvětlení a příklady

Věta formalizuje myšlenku, že pravděpodobnost, že náhodně zvolené číslo z intervalu [1, n] bude prvočíslem, klesá s růstem n a přibližně odpovídá poměru 1/ln(n). To vede k jednoduchým odhadům například pro počet prvočísel mezi 1 a velkým N nebo pro očekávanou vzdálenost mezi nimi.

Příklad s počtem číslic: mezi kladnými celými čísly s nejvýše N číslicemi leží všechna čísla ≤ 10^N. Pro hustotu prvočísel v tomto rozsahu tedy platí přibližně 1/ln(10^N) = 1/(N·ln 10). Pro N = 1000 dostaneme ln(10^1000) = 1000·ln 10 ≈ 2302,585, takže zhruba jedno z 2303 čísel má 1000 nebo méně číslic a je prvočíslem. Pro N = 2000 je ln(10^2000) ≈ 4605,17, tedy hustota je přibližně poloviční oproti N = 1000; pravděpodobnost, že náhodné číslo o 2000 číslicích je prvočíslem, je přibližně o polovinu menší než pro číslo o 1000 číslicích.

Historie a důkaz

Už v roce 1793 si patnáctiletý Carl Friedrich Gauss všiml souvislosti mezi rozložením prvočísel a logaritmy. Podobné podezření měl i Adrien‑Marie Legendre (kolem roku 1798). Formální důkaz věty o prvočíslech přinesli v roce 1896 nezávisle na sobě Jacques Hadamard a Charles‑Jean de La Vallée Poussin. Jejich důkaz využívá metody komplexní analýzy a fakta o Riemannově zeta‑funkci, zejména nepřítomnost nulových bodů na přímce Re(s) = 1.

Důsledky, upřesnění a přesnější odhady

Není pravda, že n/ln(n) je jediné či nejlepší možné přiblížení. Lepší aproximací počtu prvočísel je funkce Li(x) = ∫_2^x dt/ln t (logaritmická integrál), která dává přesnější hodnoty než x/ln x. De La Vallée Poussin dokázal také explicitní odhad chyby; později byly vyvinuty jemnější odhady. Pokud by platila Riemannova hypotéza, pak by odhad chyby v PNT mohl být zlepšen na řád O(√x·ln x).

V praxi se výsledky věty o prvočíslech používají i v kryptografii a při odhadech četnosti prvočísel v generovaných velkých náhodných číslech. Je však třeba mít na paměti, že "pravděpodobnost" vyplývající z PNT je asypmtotická — pro konkrétně malá čísla může být skutečná četnost prvků odhadů vzdálená.

Stručně řečeno: věta o prvočíslech říká, že prvočísla se stávají vzácnějšími a jejich hustota klesá jako inverzní logaritmus čísla, což umožňuje jednoduché asymptotické odhady počtu a mezer mezi prvočísly v závislosti na velikosti zkoumaného intervalu.