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^[1].

Treść twierdzenia

Niech ${\displaystyle \pi (x)}$ będzie funkcją liczącą liczby pierwsze nie większe od ${\displaystyle x.}$ Na przykład ${\displaystyle \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 ${\displaystyle \pi (x)}$ (gdzie ${\displaystyle \log }$ oznacza logarytm naturalny). Formalnie, granica funkcji będącej ilorazem ${\displaystyle \pi (x)}$ i ${\displaystyle x/\log x}$ dla ${\displaystyle x}$ dążącego do nieskończoności jest równa 1,

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

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

Równoważne sformułowania

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

${\displaystyle n}$-ta liczba pierwsza

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

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

oraz

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

gdzie ${\displaystyle p_{n}}$ oznacza ${\displaystyle n}$-tą liczbę pierwszą^[1].

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 ${\displaystyle \pi (x)\sim x/\log x,}$ a ${\displaystyle p_{n}\sim n\log n.}$

Funkcje Czebyszewa

Niech

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

będzie pierwszą funkcją Czebyszewa, a

${\displaystyle \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^[1]

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

oraz

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

Funkcja Mertensa

Przez ${\displaystyle M(x)}$ oznaczmy funkcję Mertensa, daną jako

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

gdzie ${\displaystyle \mu }$ oznacza funkcję Möbiusa.

Twierdzenie o liczbach pierwszych jest równoważne relacji^[1]

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

Funkcja Liouville’a

Niech

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

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

PNT jest równoważne granicy^[2]

${\displaystyle \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^[3].

Twierdzenie o liczbach pierwszych jest równoważne granicy

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle \Lambda }$ to funkcja von Mangoldta. Aby obliczyć sumę cząstkową ${\textstyle \psi (x)=\sum _{n\leqslant x}\Lambda (n)}$, skorzystamy ze wzoru Perrona. Mamy

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

${\displaystyle \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 ${\displaystyle \zeta }$. Z równania funkcyjnego funkcji ${\displaystyle \zeta }$ Riemanna wiemy, że zerami trywialnymi są ${\displaystyle -2,-4,-6,\;\ldots }$, więc jest to szereg potęgowy

${\displaystyle \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

${\displaystyle \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 ${\displaystyle \zeta }$ nie ma żadnych miejsc zerowych na prostej ${\displaystyle \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^[4]. 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ść

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

dla liczb pierwszych ${\displaystyle p}$^[5]. 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^[4][6]. 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 ${\displaystyle f}$ zachodzi relacja

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

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

Inne dowody

W 1994 roku Charalambos Cornaros i Costas Dimitracopoulos udowodnili twierdzenie o liczbach pierwszych, używając tylko ${\displaystyle I\Delta _{0}+\exp }$^[7], 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^[8]. 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^[8].

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

Przypisy

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Prime Number Theorem, [w:] MathWorld, Wolfram Research [dostęp 2024-05-12]  (ang.).