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
[edytuj | edytuj kod]Niech będzie funkcją liczącą liczby pierwsze nie większe od Na przykład ponieważ są cztery liczby pierwsze (2, 3, 5 i 7) mniejsze lub równe 10. Twierdzenie o liczbach pierwszych mówi, że jest dobrym przybliżeniem (gdzie oznacza logarytm naturalny). Formalnie, granica funkcji będącej ilorazem i dla dążącego do nieskończoności jest równa 1,
Twierdzenie w pierwotnej formie nie opisuje zachowania różnicy funkcji i dla dążącego do nieskończoności. W zamian, zgodnie z twierdzeniem przybliża w znaczeniu, że błąd względny dla tego przybliżenia dąży do 0 dla dążącego do nieskończoności.
Równoważne sformułowania
[edytuj | edytuj kod]Choć treść twierdzenie sama w sobie opisuje jedynie zachowanie funkcji można je przeformułować na wiele różnych sposobów, z wykorzystaniem różnych innych funkcji.
-ta liczba pierwsza
[edytuj | edytuj kod]Treść twierdzenia o liczbach pierwszych jest równoważna relacjom
oraz
gdzie oznacza -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 a
Funkcje Czebyszewa
[edytuj | edytuj kod]Niech
będzie pierwszą funkcją Czebyszewa, a
będzie drugą funkcją Czebyszewa (gdzie oznacza funkcję von Mangoldta). Można wykazać, że twierdzenie o liczbach pierwszych jest równoważne granicom[1]
oraz
Funkcja Mertensa
[edytuj | edytuj kod]Przez oznaczmy funkcję Mertensa, daną jako
gdzie oznacza funkcję Möbiusa.
Twierdzenie o liczbach pierwszych jest równoważne relacji[1]
Funkcja Liouville’a
[edytuj | edytuj kod]Niech
będzie funkcją sumującą funkcję Liouville’a (równą dla o rozkładzie ).
PNT jest równoważne granicy[2]
Dowód
[edytuj | edytuj kod]Dowód w oparciu o funkcję zeta
[edytuj | edytuj kod]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
dla będącej drugą funkcją Czebyszewa. Zdefiniujmy funkcję jako zbieżny szereg
na półpłaszczyźnie oraz jako jej przedłużenie analityczne na reszcie płaszczyzny zespolonej. Funkcja ma iloczyn Eulera
,
gdzie oznacza iloczyn po wszystkich liczbach pierwszych. Stąd
,
gdzie jest funkcją Möbiusa. Funkcja ma pochodną równą
,
zbieżną na . Stąd, korzystając ze splotu Dirichleta, możemy zapisać
,
gdzie to funkcja von Mangoldta. Aby obliczyć sumę cząstkową , skorzystamy ze wzoru Perrona. Mamy
,
gdzie dla niecałkowitych oraz dla całkowitych (wykazanie jest równoważne z wykazaniem ). Z powyższego wzoru możemy odczytać zależność
,
gdzie i są odpowiednio sumami po wszystkich trywialnych i nietrywialnych miejscach zerowych funkcji . Z równania funkcyjnego funkcji Riemanna wiemy, że zerami trywialnymi są , więc jest to szereg potęgowy
,
a stąd
.
Pozostała część dowodu, ze względu na pozostałą sumę , polega na udowodnieniu, że funkcja nie ma żadnych miejsc zerowych na prostej .
Dowód elementarny
[edytuj | edytuj kod]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ść
dla liczb pierwszych [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 zachodzi relacja
gdzie oznacza liczbę dzielników pierwszych liczonych wraz z wielokrotnościami Podstawiając za funkcję Liouville’a, udowodnił twierdzenie równoważne PNT[2].
Inne dowody
[edytuj | edytuj kod]W 1994 roku Charalambos Cornaros i Costas Dimitracopoulos udowodnili twierdzenie o liczbach pierwszych, używając tylko [7], systemu formalnego, który jest słabszy od aksjomatyki Peano.
Weryfikacja komputerowa
[edytuj | edytuj kod]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
[edytuj | edytuj kod]- ↑ a b c d Tom M. Apostol , Introduction to Analytic Number Theory, „Undergraduate Texts in Mathematics”, 1976, DOI: 10.1007/978-1-4757-5579-4, ISSN 0172-6056 [dostęp 2023-08-22] .
- ↑ a b Florian K. Richter , A new elementary proof of the Prime Number Theorem, „Bulletin of the London Mathematical Society”, London Mathematical Society, 2021, DOI: 10.1112/blms.12503 (ang.).
- ↑ Terence Tao , 254A, Notes 2: Complex-analytic multiplicative number theory [online], What's new, 10 grudnia 2014 [dostęp 2023-12-12] (ang.).
- ↑ a b Goldfeld, Dorian (2004). „The elementary proof of the prime number theorem: an historical perspective” (PDF). In Chudnovsky, David; Chudnovsky, Gregory; Nathanson, Melvyn. Number theory (New York, 2003). New York: Springer-Verlag, s. 179–192.
- ↑ Selberg, Atle (1949). „An Elementary Proof of the Prime-Number Theorem”. Annals of Mathematics. 50(2): s. 305–313.
- ↑ Baas, Nils A.; Skau, Christian F. (2008). „The lord of the numbers, Atle Selberg. On his life and mathematics” (PDF). Bull. Amer. Math. Soc. 45(4): s. 617–649.
- ↑ Cornaros, Charalambos; Dimitracopoulos, Costas (1994). „The prime number theorem and fragments of PA” (PDF). Archive for Mathematical Logic. 33(4): s. 265–281.
- ↑ a b Jeremy Avigad i inni, A formally verified proof of the prime number theorem, „arXiv [cs.AI]”, 2005, DOI: 10.48550/ARXIV.CS/0509025, arXiv:cs/0509025 [dostęp 2023-08-23] .
- ↑ John Harrison , Formalizing an Analytic Proof of the Prime Number Theorem, „Journal of Automated Reasoning”, 43 (3), 2009, s. 243–261, DOI: 10.1007/s10817-009-9145-6 [dostęp 2023-08-23] (ang.).
Linki zewnętrzne
[edytuj | edytuj kod]- Eric W. Weisstein , Prime Number Theorem, [w:] MathWorld, Wolfram Research [dostęp 2024-05-12] (ang.).