Przejdź do zawartości

Twierdzenie o liczbach pierwszych

Z Wikipedii, wolnej encyklopedii
Wykresy funkcji oraz dla

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]
  1. a b c d Tom M. Apostol, Introduction to Analytic Number Theory, „Undergraduate Texts in Mathematics”, 1976, DOI10.1007/978-1-4757-5579-4, ISSN 0172-6056 [dostęp 2023-08-22].
  2. a b Florian K. Richter, A new elementary proof of the Prime Number Theorem, „Bulletin of the London Mathematical Society”, London Mathematical Society, 2021, DOI10.1112/blms.12503 (ang.).
  3. Terence Tao, 254A, Notes 2: Complex-analytic multiplicative number theory [online], What's new, 10 grudnia 2014 [dostęp 2023-12-12] (ang.).
  4. 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.
  5. Selberg, Atle (1949). „An Elementary Proof of the Prime-Number Theorem”. Annals of Mathematics. 50(2): s. 305–313.
  6. 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.
  7. Cornaros, Charalambos; Dimitracopoulos, Costas (1994). „The prime number theorem and fragments of PA” (PDF). Archive for Mathematical Logic. 33(4): s. 265–281.
  8. a b Jeremy Avigad i inni, A formally verified proof of the prime number theorem, „arXiv [cs.AI]”, 2005, DOI10.48550/ARXIV.CS/0509025, arXiv:cs/0509025 [dostęp 2023-08-23].
  9. John Harrison, Formalizing an Analytic Proof of the Prime Number Theorem, „Journal of Automated Reasoning”, 43 (3), 2009, s. 243–261, DOI10.1007/s10817-009-9145-6 [dostęp 2023-08-23] (ang.).

Linki zewnętrzne

[edytuj | edytuj kod]