Twierdzenie o liczbach pierwszych

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

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.

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 $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,

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

Twierdzenie w pierwotnej formie nie opisuje zachowania różnicy funkcji $\pi (x)$ i $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

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

oraz

$\underset{n\to \mathrm{\infty }}{\lim }\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⩽x}\log p$

będzie pierwszą funkcją Czebyszewa, a

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

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

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

oraz

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

Funkcja Mertensa

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

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

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

Twierdzenie o liczbach pierwszych jest równoważne relacji

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

Funkcja Liouville’a

Niech

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

będzie funkcją sumującą funkcję Liouville’a $\lambda (n)$ (równą $(-1{)}^{e_1+\dots +e_k}$ dla $n$ o rozkładzie $p_1^{e_1}\cdot \dots \cdot p_k^{e_k}$).

PNT jest równoważne granicy

$\underset{x\to \mathrm{\infty }}{\lim }\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

$\underset{x\to \mathrm{\infty }}{\lim }\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}^{\mathrm{\infty }}\frac{1}{n^s}$

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

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

gdzie $\prod _p$ oznacza iloczyn po wszystkich liczbach pierwszych. Stąd

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

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

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

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

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

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

${\psi }_0(x)=\frac{1}{2\pi i}\underset{T\to \mathrm{\infty }}{\lim }\underset{1-iT}{\overset{1+iT}{\int }}\frac{{\zeta }^{\prime }(s)}{\zeta (s)}\frac{x^s}{s}ds$,

gdzie ${\psi }_0(x)=\psi (x)$ dla $x$ niecałkowitych oraz ${\psi }_0(x)=\psi (x)-\frac{1}{2}\mathrm{\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 $\sum _{{\rho }_t}$ i $\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,\dots$, więc jest to szereg potęgowy

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

a stąd

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

Pozostała część dowodu, ze względu na pozostałą sumę $\sum _{\rho }$, polega na udowodnieniu, że funkcja $\zeta$ nie ma żadnych miejsc zerowych na prostej $\mathrm{\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⩽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⩽N}f(\mathrm{\Omega }(n)+1)=\frac{1}{N}\sum _{n⩽N}f(\mathrm{\Omega }(N))+o(1),$

gdzie $\mathrm{\Omega }(n)$ oznacza liczbę dzielników pierwszych $n,$ liczonych wraz z wielokrotnościami $(\mathrm{\Omega }(p_1^{e_1}\cdot \dots \cdot p_k^{e_k})=e_1+\dots +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{\mathrm{\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ą.

Linki zewnętrzne

• Szablon:MathWorld