Pirminio skaičiaus teorema yra skaičių teorijos teorema, apibūdinanti, kaip išsidėsto pirminiai skaičiai tarp natūraliųjų skaičių. Teorema teigia, kad skaičių kiekis, mažesnis arba lygus n (žymimas π(n)), asimptotiškai elgiasi kaip n/ln(n). Kitaip sakant, π(n) ≍ n / ln(n), arba formaliai

limn→∞ π(n) / (n / ln n) = 1.

Iš to seka, jog tankis (tikimybė), kad atsitiktinis pakankamai didelis skaičius yra pirminis, yra maždaug 1 / ln(n), o ne n/ln(n). Taigi, jei renkamės skaičių apytiksliai dydžio n, tikimybė, kad jis bus pirminis, yra maždaug 1/ln(n). Todėl vidutinis atstumas (tarpas) tarp iš eilės einančių pirminių skaičių tarp pirmųjų N natūraliųjų skaičių yra maždaug ln(N).

Formulė ir geresnės aproksimacijos

Grubus apytikslis skaičiaus pirminių skaičių skaičius iki n yra n/ln(n), bet tam tikroms paskaitoms geresnė yra logaritminė integralė li(n) = ∫_2^n dt / ln t, kuri duoda tikslesnę aproksimaciją: π(n) ~ li(n). Tačiau pagrindinė ir paprastesnė teoreminė forma, dažnai vadinama „pirminių skaičių teorema“, yra π(n) ~ n / ln n.

Istorija ir įrodymai

Penkiolikmetis Carlas Friedrichas Gaussas apie 1793 m. neprisiminė formalios formulės, bet pasiūlė mintį, kad pirminių skaičių tankis susijęs su logaritmais. Adrienas‑Marie Legendre'as 1798 m. taip pat pateikė panašią hipotezę ir netgi pasiūlė konkretesnę formulę su konstantomis. Iki XIX a. antros pusės Chebyshev parodė užuominas ir ribas, kurios rodė, kad π(n) turi tos pačios eilės augimą kaip n/ln n, bet pilną įrodymą pateikė Žakas Hadamaras (Jacques Hadamard) ir Šarlis Žanas de La Vallée Poussin 1896 m. Jų įrodymas panaudojo kompleksinę analizę ir Riemanno zeta funkcijos savybes — svarbiausia buvo įrodyti, kad ζ(s) neturi nulių plokštumoje Re(s) = 1, kas leido užtikrinti reikiamą asimptotinį elgesį.

Įrodymo idėja (trumpai)

  • Analitiniai metodai: pagrindinis įrankis yra Riemanno zeta funkcija ζ(s) ir jos analizė kompleksinėje plokštumoje.
  • Chebyshev rodmenys ir funkcijos θ(x), ψ(x) (susijusios su pirminių logaritmais) naudojamos siekiant pereiti tarp suminių funkcijų ir pirminių skaičių skaičiaus π(x).
  • Hadamard ir de La Vallée Poussin rodė, kad ζ(s) ≠ 0 kai Re(s)=1, o tai leido gauti reikiamas asimptotes ir baigti įrodymą.

Klaidos termai ir Riemanno hipotezė

Nors pagrindinis teiginys π(x) ~ x/ln x yra jau visapusiškai įrodytas, svarbi matematikos dalis yra, kiek tiksliai π(x) skiriasi nuo x/ln x arba li(x). Riemanno hipotezė, jeigu ji būtų įrodyta, duotų daug griežtesnius arba „optimalius“ klaidos termus (pvz., reikšmingai mažesnis maksimumo dydis). Be RH, yra gauti įvairūs vienareikšmiški, bet silpnesni netiesioginiai ir eksponentiniai klaidos termų įverčiai naudojant pažangius analizės metodus.

Pavyzdžiai ir praktinė reikšmė

Išeinant iš tankio 1/ln(n), gauname praktinių pavyzdžių, svarbių, pavyzdžiui, kriptografijai (kai generuojami dideli atsitiktiniai pirminiai skaičiai):

  • Tikimybė, kad atsitiktinis ~n dydžio skaičius bus pirminis, yra apytiksliai 1/ln(n).
  • Skaičiams, turintiems k dešimčių (skaityt skaitmenų skaičių), n apytikriai 10^(k-1). Todėl tikimybė, kad atsitiktinis k‑skaitmenų skaičius bus pirminis, yra apytiksliai 1/(k ln 10). Pavyzdžiui, tarp skaičių, turinčių ne daugiau kaip 1000 skaitmenų, tikimybė būti pirminiu yra apie 1/ln(10^1000) = 1/(1000 ln 10) ≈ 1/2302,6, t. y. maždaug vienas iš 2300. Tarp skaičių su ne daugiau kaip 2000 skaitmenų analogiškai – maždaug vienas iš 4605 (ln(10^2000) ≈ 4605,2).
  • Vidutinis tarpats tarp dviejų greta esančių pirminių, kai skaičiai dideli, yra apie ln(n); tai paaiškina, kodėl pirminių tarpai didėja, nors jie ir toliau pasitaiko be aiškaus periodiškumo.

Pirminių skaičių teorema — vienas iš kertinių rezultatais skaičių teorijoje — suteikia pagrindą daugeliui praktinių taikymų (pvz., saugumo protokoluose) ir yra atspirties taškas giliau suprasti pirminių skaičių pasiskirstymą bei ryšius su kompleksine analize ir zeta funkcijos teorija.