Twierdzenie o liczbach pierwszych - π(x) ~ x/ln x

Q: Ile jest liczb pierwszych mniejszych od x?

W przybliżeniu x/ln x - to właśnie mówi twierdzenie o liczbach pierwszych. Na przykład do miliona jest ich 78 498, a wzór daje około 72 000.

Q: Co to jest funkcja π(x)?

Funkcja zliczająca liczby pierwsze: π(x) to liczba liczb pierwszych nie większych od x, np. π(10) = 4 (liczby 2, 3, 5, 7). Nie ma nic wspólnego z liczbą π ≈ 3,14 poza oznaczeniem.

Q: Czy istnieje wzór na n-tą liczbę pierwszą?

Nie ma prostego wzoru, ale jest przybliżenie: n-ta liczba pierwsza jest w przybliżeniu równa n ln n.

Q: Co ma twierdzenie o liczbach pierwszych do hipotezy Riemanna?

Twierdzenie mówi, że π(x) sim x/ln x. Hipoteza Riemanna, gdyby była prawdziwa, podawałaby bardzo dokładne oszacowanie błędu tego przybliżenia.

Twierdzenie o liczbach pierwszych

Niech $\pi(x)$ oznacza liczbę liczb pierwszych nie większych od $x$ . Wtedy

$\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1, \qquad \text{czyli} \qquad \pi(x) \sim \frac{x}{\ln x}.$

Wniosek: $n$ -ta liczba pierwsza $p_n \sim n \ln n$ , a w okolicy liczby $x$ co mniej więcej $\ln x$ -ta liczba jest pierwsza.

Co mówi twierdzenie

Twierdzenie o liczbach pierwszych mówi, ile jest liczb pierwszych do danej granicy: liczba $\pi(x)$ liczb pierwszych nie większych od $x$ rośnie w przybliżeniu jak $\frac{x}{\ln x}$ - stosunek tych dwóch wielkości dąży do $1$ . Liczb pierwszych jest nieskończenie wiele, ale robią się coraz rzadsze: w okolicy liczby $x$ średni odstęp między kolejnymi liczbami pierwszymi wynosi około $\ln x$ .

Pojedynczych liczb pierwszych nie da się przewidzieć wzorem, ale ich liczba zachowuje się zaskakująco regularnie:

x	π(x)	x / ln x	stosunek
10	4	4	0,921
100	25	22	1,151
1 000	168	145	1,161
10 000	1 229	1 086	1,132
100 000	9 592	8 686	1,104
1 000 000	78 498	72 382	1,084
10⁷	664 579	620 421	1,071
10⁸	5 761 455	5 428 681	1,061
10⁹	50 847 534	48 254 942	1,054
10¹⁰	455 052 511	434 294 482	1,048

Stosunek maleje do $1$ , choć bardzo powoli. Dokładniejszym przybliżeniem jest logarytm całkowy $\operatorname{Li}(x) = \int_2^x \frac{dt}{\ln t}$ , który dla $x = 10^{10}$ myli się o mniej niż $0{,}001\%$ .

Założenia

Twierdzenie dotyczy zwykłych liczb pierwszych w zbiorze liczb naturalnych; $\ln$ to logarytm naturalny (o podstawie $e$ ). Zapis $f(x) \sim g(x)$ oznacza, że $\frac{f(x)}{g(x)} \to 1$ - różnica $\pi(x) - \frac{x}{\ln x}$ może przy tym rosnąć do nieskończoności.

Dowód dolnego oszacowania (Czebyszew)

Pokaż dowódUkryj dowód

Pełny dowód twierdzenia jest długi, ale jego „połowę” - że $\pi(x)$ rośnie co najmniej jak $\frac{x}{\ln x}$ - można pokazać elementarnie, za pomocą symbolu Newtona $\binom{2n}{n}$ .

Krok 1. $\binom{2n}{n}$ jest duże. Suma wszystkich $2n + 1$ współczynników $\binom{2n}{k}$ wynosi $2^{2n} = 4^n$ , a $\binom{2n}{n}$ jest największym z nich, więc $\binom{2n}{n} \ge \frac{4^n}{2n + 1}$ .

Krok 2. Potęgi liczb pierwszych w $\binom{2n}{n}$ są małe. Wykładnik liczby pierwszej $p$ w rozkładzie $\binom{2n}{n}$ to (wzór Legendre’a) $\sum_{k \ge 1} \left(\left\lfloor \frac{2n}{p^k} \right\rfloor - 2\left\lfloor \frac{n}{p^k} \right\rfloor\right)$ . Każdy składnik jest równy $0$ albo $1$ , a dla $p^k > 2n$ wynosi $0$ . Jeśli więc $p^e$ dzieli $\binom{2n}{n}$ , to $p^e \le 2n$ .

Krok 3. Zestawienie. Wszystkie dzielniki pierwsze $\binom{2n}{n}$ są nie większe od $2n$ , a każdy wchodzi w potędze nie większej od $2n$ . Stąd $\binom{2n}{n} \le (2n)^{\pi(2n)}$ . Łącząc z krokiem 1:

$\frac{4^n}{2n + 1} \le (2n)^{\pi(2n)} \quad\Longrightarrow\quad \pi(2n) \ge \frac{n \ln 4 - \ln(2n + 1)}{\ln(2n)}.$

Dla $x = 2n$ daje to $\pi(x) \ge \frac{x \ln 2 - \ln(x + 1)}{\ln x}$ - czyli co najmniej około $0{,}69 \cdot \frac{x}{\ln x}$ . $\blacksquare$

Podobnym rozumowaniem Czebyszew pokazał też ograniczenie z góry, więc $\pi(x)$ jest „rzędu” $\frac{x}{\ln x}$ . Udowodnienie, że stosunek dąży dokładnie do $1$ , wymagało jednak innych narzędzi.

Dlaczego pełny dowód jest trudny

Klucz leży w funkcji dzeta Riemanna $\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}$ , którą Euler powiązał z liczbami pierwszymi iloczynem $\zeta(s) = \prod_p \frac{1}{1 - p^{-s}}$ . Riemann w 1859 roku pokazał, że rozkład liczb pierwszych zależy od miejsc zerowych $\zeta$ w liczbach zespolonych. Twierdzenie o liczbach pierwszych okazało się równoważne temu, że $\zeta$ nie ma zer na prostej $\operatorname{Re}(s) = 1$ - i właśnie to udowodnili w 1896 roku, niezależnie od siebie, Jacques Hadamard i Charles-Jean de la Vallée Poussin. Dowód „elementarny”, bez analizy zespolonej, podali dopiero w 1949 roku Paul Erdős i Atle Selberg.

Słynna hipoteza Riemanna - że wszystkie nietrywialne zera leżą na prostej $\operatorname{Re}(s) = \frac{1}{2}$ - mówi, jak dokładne jest przybliżenie $\pi(x) \approx \operatorname{Li}(x)$ . To jeden z problemów milenijnych, wciąż nierozwiązany.

Przykład - ile liczb pierwszych jest do miliona?

Z przybliżenia: $\frac{10^6}{\ln 10^6} \approx \frac{10^6}{13{,}8} \approx 72\,382$ . W rzeczywistości $\pi(10^6) = 78\,498$ - błąd około $8\%$ . Losowo wybrana liczba w okolicy miliona jest pierwsza z prawdopodobieństwem około $\frac{1}{\ln 10^6} \approx 7{,}2\%$ , a średni odstęp między liczbami pierwszymi wynosi tam około $14$ .

Tysięczna liczba pierwsza to $7919$ , a przybliżenie $n \ln n$ daje $1000 \cdot \ln 1000 \approx 6908$ - zgodność jest rzędu $15\%$ i poprawia się dla większych $n$ .

Po co to komu

Kryptografia - klucze RSA wymagają losowych liczb pierwszych mających setki cyfr. Twierdzenie mówi, że wśród liczb 300-cyfrowych mniej więcej co $690$ -ta jest pierwsza, więc losowanie i sprawdzanie kandydatów kończy się szybko.
Szacowania w teorii liczb - wiele twierdzeń o liczbach pierwszych zaczyna się od oszacowania $\pi(x)$ .
Postulat Bertranda (między $n$ a $2n$ zawsze jest liczba pierwsza) - wynika z oszacowań Czebyszewa.

Kto i kiedy

Przybliżenie odgadł z tablic liczb pierwszych Carl Friedrich Gauss jako piętnastolatek (około 1792 roku); Adrien-Marie Legendre opublikował podobne przybliżenie w 1798 roku, a w 1808 roku podał je w postaci $\frac{x}{\ln x - 1{,}08366}$ . Pafnutij Czebyszew udowodnił około 1850 roku, że stosunek $\pi(x) : \frac{x}{\ln x}$ leży między dwiema stałymi bliskimi $1$ . Pełny dowód - Hadamard i de la Vallée Poussin (1896), elementarny - Erdős i Selberg (1949).

Najczęstsze pytania

Ile jest liczb pierwszych mniejszych od x? W przybliżeniu $\frac{x}{\ln x}$ - to właśnie mówi twierdzenie o liczbach pierwszych. Na przykład do miliona jest ich $78\,498$ , a wzór daje około $72\,000$ .

Co to jest funkcja π(x)? Funkcja zliczająca liczby pierwsze: $\pi(x)$ to liczba liczb pierwszych nie większych od $x$ , np. $\pi(10) = 4$ (liczby $2, 3, 5, 7$ ). Nie ma nic wspólnego z liczbą $\pi \approx 3{,}14$ poza oznaczeniem.

Czy istnieje wzór na n-tą liczbę pierwszą? Nie ma prostego wzoru, ale jest przybliżenie: $n$ -ta liczba pierwsza jest w przybliżeniu równa $n \ln n$ .

Czy liczby pierwsze się kończą? Nie - jest ich nieskończenie wiele (twierdzenie Euklidesa). Twierdzenie o liczbach pierwszych mówi więcej: jak szybko ich przybywa.

Co ma twierdzenie o liczbach pierwszych do hipotezy Riemanna? Twierdzenie mówi, że $\pi(x) \sim \frac{x}{\ln x}$ . Hipoteza Riemanna, gdyby była prawdziwa, podawałaby bardzo dokładne oszacowanie błędu tego przybliżenia.

Podsumowanie

$\pi(x) \sim \frac{x}{\ln x}$ : liczba liczb pierwszych do $x$ rośnie jak $\frac{x}{\ln x}$ .
Średni odstęp między liczbami pierwszymi w okolicy $x$ to około $\ln x$ ; $p_n \sim n \ln n$ .
Elementarnie (Czebyszew): $\pi(x) \ge \frac{x \ln 2 - \ln(x + 1)}{\ln x}$ - dowód przez $\binom{2n}{n}$ .
Pełny dowód: Hadamard i de la Vallée Poussin (1896) przez funkcję dzeta; elementarny: Erdős i Selberg (1949).
Powiązane: nieskończoność liczb pierwszych, podstawowe twierdzenie arytmetyki, ciekawe liczby.