Twierdzenie o liczbach pierwszych

Twierdzenie o liczbach pierwszych, PNT (ang. prime number theorem) – twierdzenie opisujące asymptotyczny rozkład liczb pierwszych pośród liczb naturalnych. Jest ono jednym z najważniejszych wyników teorii liczb.

Wykresy funkcji $x^{-1}\pi (x)\log x$ oraz ${\pi (x)}{{\text{Li}}(x)^{-1}}$ dla $x<10^{24}$

Treść twierdzenia

Niech $\pi (x)$ będzie funkcją liczącą liczby pierwsze nie większe od $x.$ Na przykład $\pi (10)=4,$ ponieważ są cztery liczby pierwsze (2, 3, 5 i 7) mniejsze lub równe 10. Twierdzenie o liczbach pierwszych mówi, że ${\textstyle {x}/{\log x}}$ jest dobrym przybliżeniem $\pi (x)$ (gdzie $\log$ oznacza logarytm naturalny). Formalnie, granica funkcji będącej ilorazem $\pi (x)$ i $x/\log x$ dla $x$ dążącego do nieskończoności jest równa 1,

$\lim _{x\to \infty }{\frac {\pi (x)\log x}{x}}=1.$

Twierdzenie w pierwotnej formie nie opisuje zachowania różnicy funkcji $\pi (x)$ i ${\textstyle x/\log x}$ dla $x$ dążącego do nieskończoności. W zamian, zgodnie z twierdzeniem $x/\log x$ przybliża $\pi (x)$ w znaczeniu, że błąd względny dla tego przybliżenia dąży do 0 dla $x$ dążącego do nieskończoności.

Równoważne sformułowania

Choć treść twierdzenie sama w sobie opisuje jedynie zachowanie funkcji $\pi (x),$ można je przeformułować na wiele różnych sposobów, z wykorzystaniem różnych innych funkcji.

$n$-ta liczba pierwsza

Treść twierdzenia o liczbach pierwszych jest równoważna relacjom

$\lim _{x\to \infty }{\frac {\pi (x)\log \pi (x)}{x}}=1$

oraz

$\lim _{n\to \infty }{\frac {p_{n}}{n\log n}}=1,$

gdzie $p_{n}$ oznacza $n$-tą liczbę pierwszą.

Pierwsza zależność sama w sobie nie jest szczególnym krokiem w stronę dowodu PNT, ale stanowi krok pomiędzy wykazaniem równoważności $\pi (x)\sim x/\log x,$ a $p_{n}\sim n\log n.$

Funkcje Czebyszewa

Niech

$\vartheta (x)=\sum _{p\leqslant x}\log p$

będzie pierwszą funkcją Czebyszewa, a

$\psi (x)=\sum _{n\leqslant x}\Lambda (n)$

będzie drugą funkcją Czebyszewa (gdzie ${\textstyle \Lambda }$ oznacza funkcję von Mangoldta). Można wykazać, że twierdzenie o liczbach pierwszych jest równoważne granicom

$\lim _{x\to \infty }{\frac {\vartheta (x)}{x}}=0$

oraz

$\lim _{x\to \infty }{\frac {\psi (x)}{x}}=0.$

Funkcja Mertensa

Przez $M(x)$ oznaczmy funkcję Mertensa, daną jako

$M(x)=\sum _{n\leqslant x}\mu (n),$

gdzie $\mu$ oznacza funkcję Möbiusa.

Twierdzenie o liczbach pierwszych jest równoważne relacji

$\lim _{x\to \infty }{\frac {M(x)}{x}}=0.$

Funkcja Liouville’a

Niech

$L(x)=\sum _{n\leqslant x}\lambda (n)$

będzie funkcją sumującą funkcję Liouville’a $\lambda (n)$ (równą $(-1)^{e_{1}+\ldots +e_{k}}$ dla $n$ o rozkładzie $p_{1}^{e_{1}}\cdot \ldots \cdot p_{k}^{e_{k}}$).

PNT jest równoważne granicy

$\lim _{x\to \infty }{\frac {L(x)}{x}}=1.$

Dowód

Dowód w oparciu o funkcję zeta

Klasyczny dowód analityczny twierdzenia o liczbach pierwszych przeprowadza się korzystając z własności funkcji zeta Riemanna. Poniższy dowód pochodzi z wykładu Terence'a Tao z analitycznej teorii liczb.

Twierdzenie o liczbach pierwszych jest równoważne granicy

$\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1$

dla $\psi$ będącej drugą funkcją Czebyszewa. Zdefiniujmy funkcję $\zeta$ jako zbieżny szereg

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}}$

na półpłaszczyźnie $\Re (s)>1$ oraz jako jej przedłużenie analityczne na reszcie płaszczyzny zespolonej. Funkcja $\zeta$ ma iloczyn Eulera

$\zeta (s)=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)^{-1}$,

gdzie ${\textstyle \prod _{p}}$ oznacza iloczyn po wszystkich liczbach pierwszych. Stąd

$\zeta (s)^{-1}=\prod _{p}\left(1-{\frac {1}{p^{s}}}\right)=\sum _{n=1}^{\infty }{\frac {\mu (n)}{n^{s}}}$,

gdzie $\mu$ jest funkcją Möbiusa. Funkcja $\zeta$ ma pochodną równą

$\zeta '(s)=-\sum _{n=1}^{\infty }{\frac {\log n}{n^{s}}}$,

zbieżną na $\Re (s)>1$. Stąd, korzystając ze splotu Dirichleta, możemy zapisać

${\frac {\zeta '(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }{\frac {(-\log \;*\;\mu )(n)}{n^{s}}}=\sum _{n=1}^{\infty }{\frac {\Lambda (n)}{n^{s}}}$,

gdzie $\Lambda$ to funkcja von Mangoldta. Aby obliczyć sumę cząstkową ${\textstyle \psi (x)=\sum _{n\leqslant x}\Lambda (n)}$, skorzystamy ze wzoru Perrona. Mamy

$\psi _{0}(x)={\frac {1}{2\pi i}}\lim _{T\to \infty }\int _{1-iT}^{1+iT}{\frac {\zeta '(s)}{\zeta (s)}}{\frac {x^{s}}{s}}ds$,

gdzie $\psi _{0}(x)=\psi (x)$ dla $x$ niecałkowitych oraz ${\textstyle \psi _{0}(x)=\psi (x)-{\frac {1}{2}}\Lambda (x)}$ dla $x$ całkowitych (wykazanie $\psi (x)\sim x$ jest równoważne z wykazaniem $\psi _{0}(x)\sim x$). Z powyższego wzoru możemy odczytać zależność

$\psi _{0}(x)=x-\log(2\pi )-\sum _{\rho _{t}}{\frac {x^{\rho _{t}}}{\rho _{t}}}-\sum _{\rho }{\frac {x^{\rho }}{\rho }}$,

gdzie ${\textstyle \sum _{\rho _{t}}}$ i ${\textstyle \sum _{\rho }}$ są odpowiednio sumami po wszystkich trywialnych i nietrywialnych miejscach zerowych funkcji $\zeta$. Z równania funkcyjnego funkcji $\zeta$ Riemanna wiemy, że zerami trywialnymi są $-2,-4,-6,\;\ldots$, więc jest to szereg potęgowy

$\sum _{\rho _{t}}{\frac {x^{\rho _{t}}}{\rho _{t}}}=-\sum _{n=1}^{\infty }{\frac {x^{-2n}}{2n}}=\log \left(1-{\frac {1}{x^{2}}}\right)$,

a stąd

$\psi _{0}(x)=x-\log(2\pi )-\log \left(1-{\frac {1}{x^{2}}}\right)-\sum _{\rho }{\frac {x^{\rho }}{\rho }}$.

Pozostała część dowodu, ze względu na pozostałą sumę ${\textstyle \sum _{\rho }}$, polega na udowodnieniu, że funkcja $\zeta$ nie ma żadnych miejsc zerowych na prostej $\Re (s)=1$.

Dowód elementarny

W pierwszej połowie XX wieku niektórzy matematycy (m.in. G.H. Hardy) uważali, że istnieje hierarchia metod dowodzenia matematycznego, zależna od rodzaju liczb (całkowite, rzeczywiste, zespolone), które są używane w dowodzie. Twierdzenie o liczbach pierwszych jest „głębokie” w rozumieniu, że wymaga analizy zespolonej. To przekonanie zostało podważone przez dowód twierdzenia o liczbach pierwszych wykorzystujący twierdzenie Weinera. Nie ma ścisłej i powszechnie akceptowanej definicji „dowodu elementarnego” w teorii liczb. Jedna z definicji mówi, iż jest to dowód, który może zostać przeprowadzony, wykorzystując aksjomaty Peano. Istnieją twierdzenia w teorii liczb (np. twierdzenie Parisa-Harringtona), które można udowodnić, używając metod arytmetyki drugiego rzędu, ale nie pierwszego rzędu, jednak są one rzadkie.

W marcu 1948 roku Atle Selberg udowodnił, używając elementarnych metod, asymptotyczną zależność

$\vartheta (x)\log(x)+\sum _{p\leqslant x}\log(p)\ \vartheta \left({\frac {x}{p}}\right)=2x\log(x)+O(x)$

dla liczb pierwszych $p$. Do lipca tegoż roku, Selberg i Paul Erdős niezależnie uzyskali elementarny dowód twierdzenia o liczbach pierwszych, używając powyższego wzoru Selberga jako punkt wyjścia. Te dowody ostatecznie zaprzeczyły poglądowi, że twierdzenie o liczbach pierwszych jest „głębokie” i pokazały, że technicznie elementarne metody są silniejsze niż sądzono.

W 2021 r. Florian K. Richter udowodnił elementarnie, że dla każdej ograniczonej funkcji arytmetycznej $f$ zachodzi relacja

${\frac {1}{N}}\sum _{n\leqslant N}f(\Omega (n)+1)={\frac {1}{N}}\sum _{n\leqslant N}f(\Omega (N))+o(1),$

gdzie $\Omega (n)$ oznacza liczbę dzielników pierwszych $n,$ liczonych wraz z wielokrotnościami $(\Omega (p_{1}^{e_{1}}\cdot \ldots \cdot p_{k}^{e_{k}})=e_{1}+\ldots +e_{k}).$ Podstawiając za $f$ funkcję Liouville’a, udowodnił twierdzenie równoważne PNT.

Inne dowody

W 1994 roku Charalambos Cornaros i Costas Dimitracopoulos udowodnili twierdzenie o liczbach pierwszych, używając tylko $I\Delta _{0}+\exp$, systemu formalnego, który jest słabszy od aksjomatyki Peano.

Weryfikacja komputerowa

W 2005 roku Avigad et al. użyli Isabelle do stworzenia weryfikowalnego komputerowo dowodu twierdzenia o liczbach pierwszych autorstwa Erdősa i Selberga. Była to pierwsza próba komputerowego dowiedzenia twierdzenia o liczbach pierwszych. Avigad wybrał do sformalizowania dowód autorstwa Erdősa i Selberga, a nie analityczny dowód, gdyż co prawda biblioteka Isabelle wtedy potrafiła implementować granice funkcji, pochodne i funkcje przestępne, jednak nie zawierała rachunku całkowego.

W 2009 roku John Harrison wykorzystał HOL Light do sformalizowania dowodu wykorzystującego analizę zespoloną.