Pengguna:Dedhert.Jr/Teorema bilangan prima

Dalam teori bilangan, teorema bilangan prima (TBP) menjelaskan asimtotik, distibusi dari bilangan prima di antara bilangan bulat positif. Itu meresmikan ide intuitif bahwa bilangan prima menjadi kurang umum saat mereka menjadi lebih besar dengan tepat mengukur laju terjadinya hal ini. Teorema ini dibuktikan secara independen oleh Jacques Hadamard dan Charles Jean de la Vallée Poussin pada tahun 1896 menggunakan ide-ide yang diperkenalkan oleh Bernhard Riemann (khususnya, fungsi zeta Riemann).

Distribusi pertama yang ditemukan adalah $\pi (N)\sim {\frac {N}{\log(N)}}$, dimana $\pi (N)$ adalah fungsi penghitungan bilangan prima dan $\log(N)$ adalah logaritma alami $N$. Ini berarti, bahwa untuk $N$ yang cukup besar, kemungkinan bahwa sebuah bilangan bulat acaktidak lebih besar daripada $N$ adalah bilangan prima sangat dekat ke ${\frac {1}{\log(N)}}$. Karena itu, sebuah bilangan bulat acak dengan paling banyak $2n$ digit (untuk $n$ yang cukup besar) kemungkinannya sekitar setengahnya menjadi bilangan prima sebagai bilangan bulat acak dengan paling banyak $n$ digit. Sebagai contoh, antara bilangan bulat positif paling banyak 1000 digit, sekitar satu dari 2300 adalah bilangan prima ($\log(10^{1000})\approx 2302.6$), sedangkan di antara bilangan bulat paling banyak 2000 digit, sekitar satu dari 4600 adalah bilangan prima ($\log(10^{2000})\approx 4605.2$). Dengan kata lain, jarak rata-rata antara bilangan prima berurutan sekitar bilangan bulat $N$ pertama kira-kira $\log(N)$.

Pernyataan

Grafiknya menunjukkan rasio dari fungsi penghitungan bilangan prima $\pi (x)$ hingga dua dari perkiraannya $x/\log x$ dan $\operatorname {Li} (x)$. Ketika $x$ meningkat (perhatikan sumbu $x$ adalah logaritmik),

Plot log-log menunjukkan galat absolut ${\textstyle {\frac {x}{\log x}}}$ dan $\operatorname {Li} (x)$, dua aporksimasi ke fungsi penghitungan prima $\pi (x)$. Tidak seperti rasio, selisih antara $\pi (x)$ dan ${\textstyle {\frac {x}{\log x}}}$ meningkat tanpa batas saat $x$ meningkat. Di samping itu, $\operatorname {Li} (x)-\pi (x)$ bertukar tanda berkali-kali.

Misalkan $\pi (x)$ adalah fungsi penghitung bilangan prima yang memberikan bilangna prima kurang dari sama dengan $x$, untuk setiap bilangna real $x$. Sebagai contoh, $\pi (10)=4$ karena terdapat empat bilangan prima (2, 3, 5, dan 7) kurang dari sama dengan 10. Teorema bilangna prima kemudian menyatakan bahwa ${\frac {x}{\log x}}$ adalah sebuah aprokismasi yang baik untuk $\pi (x)$ (dimana $\log$ disini berarti logaritma natural), dalam arti bahwa limit dari hasil bagi dari dua fungsi $\pi (x)$ dan ${\frac {x}{\log x}}$ saat $x$ meningkat tanpa batas adalah 1ː

$\lim _{x\to \infty }{\frac {\;\pi (x)\;}{\;\left[{\frac {x}{\log(x)}}\right]\;}}=1$,

dikenal sebagai hukum asimtotik distribusi bilangan prima. Menggunakan notasi asimtotik, hasil ini bisa dikemukakan kembali sebagai

$\pi (x)\sim {\frac {x}{\log x}}$.

Notasi ini (dan teoremanya) tidak mengatakan apapun tentang limit dan selisih dari dua fungsi saat $x$ meningkat tanpa batas. Sebagai gantinya, teoremanya mengatakan bahwa ${\frac {x}{\log x}}$ mendekati $\pi (x)$ dalam arti bahwa galat relatif dari aprokismasi ini mendekati 0

Teorema bilangan prima setara dengan pernyataan bahwa bilangan prima $p_{n}$ ke-$n$ memenuhiː

$p_{n}\sim n\log(n)$,

arti dari notasi asimtotik, lagi, bahwa galat relatif dari aproksimasi ini mendekati 0 saat $n$ meningkat tanpa batas. Sebagai contoh, bilangan prima ke $2\times 10^{17}$ adalah $8\ 512\ 677\ 386\ 048\ 191\ 063$, dan $(2\times 10^{17})\log(2\times 10^{17})$ membulatkan ke $7\ 967\ 418\ 752\ 291\ 744\ 388$, sebuah galat relatif sekitar $6.4\%$.

Seperti diuraikan di bawah, teorema bilangan prima juga setara dengan

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

dimana $\vartheta$ dan $\psi$ adalah fungsi Chebyshev pertama dan kedua masing-masing.

Sejarah dari bukti dari hukum asimtotik bilangan prima

Berdasarkan pada tabel oleh Anton Felkel dan Jurij Vega, Adrien-Marie Legendre diduga pada tahun 1797 atau 1798 bahwa $\pi (a)$ didekati dengan fungsi ${\frac {a}{A\log a+B}}$, dimana $A$ dan $B$ adalah konstanta yang tidak ditentukan. Dalam edisi kedua dari bukunya pada teori bilangan (1808) dia kemudian membuat dugaan yang lebih tepat, dengan $A=1$ dan $B=-1.08366$. Carl Friedrich Gauss mempertimbangkan pertanyaan yang sama pada umur 15 atau 16 "pada tahun 1792 atau 1793", menurut ingatannya sendiri pada tahun 1849. Pada tahun 1838 Peter Gustav Lejeune Dirichlet muncul dengan fungsi aproksimasi sendiri, integral logaritmik $\operatorname {li} (x)$ (di bawah bentuk yang sedikit berbeda dari sebuah deret, yang dia menyampakan kepada Gauss). Kedua rumus Legendre dan Dirichlet mengartikan dugaan ekuivalen asimtotik yang sama dari $\pi (x)$ dan ${\frac {x}{\log x}}$ yang disebutkan di atas, meskipun ternyata bahwa aproksimasi Dirichlet jauh lebih baik jika salah satunya mempertimbangkan perbedaannya bukan hasil bagi.

Dalam dua makalah dari tahun 1848 dan 1850, matematikawan Rusia, Pafnuty Chebyshev mencoba untuk membuktikan hukum asosiatif distribusi bilangan prima. Karyanya penting untuk penggunaan dari fungsi zeta $\zeta (s)$, untuk nilai real dari argumen "$s$", seperti dalam karya Leonhard Euler,sejak tahun 1737. Makalah-makalah Chebyshev mendahului memoar Riemann tahun 1859, dan dia berhasil dalam membuktikan sebuah benetuk yang sedikit lemah dari hukum asimtotik, yakni, bahwa jika limit sebagai $x$ menuju takhingga dari ${\frac {\pi (x)}{x\log x}}$ ada sama sekali, maka itu perlu sama dengan satu. Dia mampu untuk membuktikan tanpa syarat bahwa rasio ini dibatasi di atas dan di bawah oleh dua konstanta yang diberikan secara eksplisit di dekat 1, untuk semua $x$ yang cukup besar. Meskipun makalah Chebyshev tidak membuktikan Teorema Bilangan Prima, perkiraan dia untuk $\pi (x)$ cukup kuat untuk dia untuk membuktikan postulat Bertrand bahwa ada bilangan prima antara $n$ dan $2n$ untuk setiap bilangan bulat $n\geq 2$.

Sebuah makalah penting mengenai distribusi bilangan prima adalah memoan Riemann tahun 1859 "On the Number of Primes Less Than a Given Magnitude", satu-satunya makalah yang pernah dia tulis pada subjek. Riemann memperkenalkan ide-ide baru menjadi subjek, terutama bahwa distribusi bilangna prima terhubung erat dengan nol dari fungsi zeta Riemann yang diperluas secara analitis dari sebuah variabel kompleks. Khususnya, di makalah iniliah ide-ide untuk menerapkan metode-metode analisis kompleks untuk mempelajari fungsi real $\pi (x)$ berasal. Memperluas ide-ide Riemann, dua bukti dari hukum asimtotik distribusi bilangan prima ditemukan secara independen oleh Jacques Hadamard dan Charles Jean de la Vallée Poussin dan munul dalam tahun yang sama (1896) Kedua bukti menggunakan metode-metode dari analisis kompleks, ditetapkan sebagai sebuah langkah utam dari bukti bahwa fungsi zeta Riemann $\zeta (s)$ adalah bukan nol untuk semua nilai-nilai kompleks dari variabel $s$ bahwa memiliki bentuk $s=1+it$ dengan $t>0$.

Selama abad ke-20, teorema Hadamard dan de la Vallée Poussin juga dikenal sebagai Teorema Bilangan Prima. Beberapa bukti-bukti yang berbeda darinya ditemukan, termasuk bukti-bukti "elementer" Atle Selberg dan Paul Erdős (1949). Bukti asli Hadamard dan de la Vallée Poussin sangat panjang dan rumit, bukti-bukti selanutnya diperkenalkan berbagai penyederhanaan melalui penggunaan teorema Tauberian tapi tetap sulit untuk dicerna. Sebuah bukti pendek ditemukan pada tahun 1980 oleh matematikawan Amerika, Donald J.Newman. Bukti Newman bisa dikatakan bukti paling sederhana dari teorema, meskipun itu bukan dasar dalam arti menggunakan teorema integral Cauchy dari analisis kompleks.

Sketsa bukti

Disini adalah sebuh sketsa dari bukti disebut di salah satu kuliah Terence Tao. Seperti kebanyakan bukti TBP, itu dimulai dengan merumuskan kembali masalah dalah hal yang kurang intuitif, tetapi berperilaku baik, fungsi penghitungan bilangan prima. Idenya adalah menghitung bilangna prima (atau sebuah himpunan terkait seperti himpunan dari pangkat-pangkat bilangan prima) dengan bobot untuk sampai pada sebuah fungsi dengan perilaku asimtotik yang lebih mulus. Yang paling umum seperti fungsi penghitungan rampat adalah fungsi Chebyshev $\psi (x)$, didefinisika sebagai

$\psi (x)=\!\!\!\!\sum _{\stackrel {p^{k}\leq x,}{p{\text{ is prime}}}}\!\!\!\!\log p$.

Ini terkadang ditulis sebagai

$\psi (x)=\sum _{n\leq x}\Lambda (n)$,

dimana $\Lambda (n)$ adalah fungsi von Mangoldt, yakni

$\Lambda (n)={\begin{cases}\log p&{\text{jika }}n=p^{k}{\text{ untuk beberapa bilangan prima }}p{\text{ dan bilangan bulat }}k\geq 1,\\0&{\text{jika tidak.}}\end{cases}}$

Sekarang relatif mudah untuk memeriksa bahwa TBP etara dengan klaim bahwa

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

Memang, ini mengikuti dari perkiraan yang mudah

$\psi (x)=\sum _{p\leq x}\log p\left\lfloor {\frac {\log x}{\log p}}\right\rfloor \leq \sum _{p\leq x}\log x=\pi (x)\log x$

dan (menggunakan notasi O besar) untuk setiap $\varepsilon >0$,

$\psi (x)\geq \!\!\!\!\sum _{x^{1-\varepsilon }\leq p\leq x}\!\!\!\!\log p\geq \!\!\!\!\sum _{x^{1-\varepsilon }\leq p\leq x}\!\!\!\!(1-\varepsilon )\log x=(1-\varepsilon )\left(\pi (x)+O\left(x^{1-\varepsilon }\right)\right)\log x$.

Langkah selanjutnya adalah mencari sebuah representasi yang berguna untuk $\psi (x)$. Misalkan $\zeta (s)$ menjadi sebuah fungsi zeta Riemann. Ini bisa enunjukkkan bahwa $\zeta (s)$ berakitan dengan fungsi von Mangoldt $\Lambda (n)$,

$-{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{n=1}^{\infty }\Lambda (n)n^{-s}$.

Sebuah analisis yang rumit dari persamaan ini dan sifat-sifat yang terkati dengan fungsi zeta, menggunakan transformasi Mellin dan rumus Perron, menunjukkkan bahwa untuk bukan bilangan bulat $x$ persamaan

$\psi (x)=x-\sum _{\rho }{\frac {x^{\rho }}{\rho }}-\log(2\pi )$berlaku, dimana jumlah di atas semuanya nol (trivial dan nontrivial) dari fungsi zeta. Rumus yang mencolok ini adalah salah satu yang disebut rumus eksplisit teori bilangan, dan sudah menunjukkan dari hasil yang kita buktikan, sejak suku $x$ (diklaim menjadi perbaikan urutan asimtotik $\psi (x)$) muncul pada sebelah kanan, diikuti oleh (agaknya) suku asimtotik urutan lebih rendah.

Langkah selanjutnya dalam bukti melibatkan sebuah studi dari nol dari fungsi zeta. Nol trivial $-2,-4,-6,-8,\dots$ bisa ditangani secara terpisahː

$\sum _{n=1}^{\infty }{\frac {1}{2n\,x^{2n}}}=-{\frac {1}{2}}\log \left(1-{\frac {1}{x^{2}}}\right)$,

yang lenyap untuk sebuah $x$ besar. Untuk nol nontrivial, yaitu yang ada di garis kritis $0\leq \operatorname {Re} (s)\leq 1$, berpotensi menjadi sebuah urutan asimtotik sebanding ke suku utama $x$ jika $\operatorname {Re} (\rho )=1$, jadi kita perlu menunjukkan bahwa semua nol memiliki bagian real sangat kurang dari $1$.

Untuk melakukan ini, kita menerima begitu saja bahwa $\zeta (s)$ adalah meromorfik dalam setengah bidang $\operatorname {Re} (s)>0$, dan analitik di sana kecuali untuk sebuah kutub sederhana pada $s=1$, dan itu terdapat sebuah rumus produk

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

untuk $\operatorname {Re} (s)>1$. Rumus produk ini mengikuti dari adanya faktorisasi bilangan prima tunggal dari bilangan bulat, dan menunjukkan bahwa $\zeta (s)$ tidak pernah nol di daerah ini, jadi logaritmanya didefinisikan di sana dan

$\log \zeta (s)=-\sum _{p}\log \left(1-p^{-s}\right)=\sum _{p,n}{\frac {p^{-ns}}{n}}$ .

Tulis $s=x+iy$, lalu

${\big |}\zeta (x+iy){\big |}=\exp \left(\sum _{n,p}{\frac {\cos ny\log p}{np^{nx}}}\right).$Sekarang mengamati identitas

$3+4\cos \phi +\cos 2\phi =2(1+\cos \phi )^{2}\geq 0$ ,

sehingga

$\left|\zeta (x)^{3}\zeta (x+iy)^{4}\zeta (x+2iy)\right|=\exp \left(\sum _{n,p}{\frac {3+4\cos(ny\log p)+\cos(2ny\log p)}{np^{nx}}}\right)\geq 1$

untuk semua $x>1$. Misalkan bahwa $\zeta (1+iy)=0$. Tentu saja $y$ bukan nol, karena $\zeta (s)$ memiliki sebuah kutub sederhana pada $s=1$. Misalkan bahwa $x>1$ dan misalkan $x$ cenderung ke $1$ dari atas. Karena $\zeta (s)$ adalah sebuah kutub sederhana pada $s=1$ dan $\zeta (x+2iy)$ tetap analitik, sisi kiri di pertidaksamaan sebelumnya cenderung ke $0$, sebuah kontradiksi.

Terakhir, kita bisa menyimpulkan bahwa TBP secara heuristik benar. Untuk menyelesaikan bukti dengan teliti, masih ada teknik-tenik yang serius untuk diatasi, karena faktanya bahwa penjumlahan pada nol zeta dalam rumus eksplisit untuk $\psi (x)$ tidak konvergen sepenuhnya tetapi hanya bersyarat dan dalam sebuah arti "nilai utama". Terdapat beberapa cara di sekitar masalah ini tapi banyak dari mereka membutuhkan perkiraan analisis kompleks yang agak rumit. Buku Edward menyediakan detailnya. Metode lainnya adalah menggunakan teorema Tauberian Ikehara, meskipun teorema ini sendiri cukup sulit untuk membuktikan. D. J. Newman mengamati bahwa kekuatan penuh dari teorema Ikehara tidak dibutuhkan untuk teorema bilangan prima, dan salah satunya bisa lolos dengan sebuah kasus spesial yang jauh lebih mudah untuk membuktikan.

Bukti Newman dari Teorema Bilangan Prima

D. J. Newman membeiirkan sebuah bukti cepat dari Teorema Bilangan Prima (TBP). Buktinya adalah "nondasar" berdasarkan mengandalkan analisis kompleks, tetapi perkiraan kritis hanya menggunakan teknik-teknik dasar dari sebuah kursus pertama dalam subjek. Rumus integral Cauchy, Teorema integral Cauchy dan perkiraan integral-integral kompleks. Ini adalah sebuah sketsa singkatnya dari bukti iniː

Fungsi Chebyshev pertama dan kedua masing-masing

$\psi (x)=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\quad {\text{ dan }}\quad \vartheta (x)=\sum _{p\leq x}\log p.$

Deret kedua diperoleh dengan menjatuhkan suku-suku dengan $k\geq 2$ dari yang pertama. TBP setara dengan $\lim _{x\to \infty }{\frac {\psi (x)}{x}}=1$ atau $\lim _{x\to \infty }{\frac {\vartheta (x)}{x}}=1$.

Jumlah untuk adalah $\psi$ dan $\vartheta$ jumlah parsial dari koefisien dari deret Dirichlet

$-{\frac {\zeta '(s)}{\zeta (s)}}=\sum _{k\geq 1}\sum _{p^{k}\leq x}\log p\,\,p^{-ks}\quad {\text{ dan }}\quad \quad \Phi (s)=\sum _{p\leq x}\log p\,\,p^{-s},$dimana $\zeta$ adalah fungsi zeta Riemann. Seperti jumlah parisal, deret kedua diperoleh dengan menjatuhkan suku-suku dengan $k\geq 2$ dari yang pertama. Deret Dirichlet dibentuk oleh suku-suku dengan $k\geq 2$ didominasi oleh deret Dirichlet untuk $\zeta (2s+\varepsilon )$ untuk setiap positif $\varepsilon$, jadi turunan logaritmik $\zeta$ dan $\Phi (s)$ berbeda dengan sebuah holomorfik fungsi dalam $\Re s>{\frac {1}{2}}$, dan oleh karena itu memiliki singularitas yang sama pada garis $\Re s=1$.

Mengintegrasi dengan bagian diberikan untuk $\Re s>1$,

$\Phi (s)=\int _{1}^{\infty }x^{-s}d\vartheta (x)=s\int _{1}^{\infty }\vartheta (x)x^{-s-1}\,dx=s\int _{0}^{\infty }\vartheta (e^{t})e^{-st}\,dt$.

Semua bukti-bukti analitik dari Teorema Bilangan Prma menggunakan fakta bahwa $\zeta$ tidak memiliki nol pada garis $\Re s=1$. Satu informasi lebih lanjut dalam pembuktian Newman adalah ${\frac {\vartheta (x)}{x}}$ dibatasi, Ini bisa dengan mudah membuktikan metode-metode dasar.

Metode Newman membuktikan TBP dengan menunjukkan integral

$\Phi (s)=\int _{1}^{\infty }x^{-s}d\vartheta (x)=s\int _{1}^{\infty }\vartheta (x)x^{-s-1}\,dx=s\int _{0}^{\infty }\vartheta (e^{t})e^{-st}\,dt.$konvergen, dan karena itu integrand menuju nol karena $t\to \infty$. Secara umum, konvergensi dari integral tak wajar tidak menyiratkan bahwa integrand menuju nol, karena itu mungkin berosilasi, tetapi karena $\vartheta$ meningkat, itu mudah untuk ditampilkan dalam kasus ini.

Untuk $\Re s>0$, misalkan

$g_{T}(z)=\int _{0}^{T}\left({\frac {\vartheta (e^{t})}{e^{t}}}-1\right)e^{-zt}\,dt\quad \quad$

mka

$\lim _{T\to \infty }g_{T}(z)=g(z)={\frac {\Phi (s)}{s}}-{\frac {1}{s-1}}\quad \quad {\text{where}}\quad z=s-1$

yang holomorfik pada garis $\Re z=0$. Konvergensi dari integral $I$ dibuktikan dengan menunjukkan bahwa $\lim _{T\to \infty }g_{T}(0)=g(0)$. Ini melibatkan perubahan urutan limit karena itu bisa ditulis

$\lim _{T\to \infty }\lim _{s\to 0}g_{T}(z)=\lim _{s\to 0}\lim _{T\to \infty }g_{T}(z)$

dan karena itu digolongkan sebagai teorema Tauberian.

Selisih $g(0)-g_{T}(0)$ diekspresikan menggunakan rumus integral Cauchy dan kemudian perkiraan diterapkan ke integral. Menetapkan $R>0$ dan $\delta >0$, seperti $g(z)$ holomorfik dalam daerah dimana $\left|z\right|\leq R$ dan $\Re z>-\delta$ dan misalkan $C$ menjadi batasnya. Karena $0$ ada di bagian dalam, rumus integral Cauchy memberikan

$g(0)-g_{T}(0)={\frac {1}{2\pi i}}\int _{C}\left(g(z)-g_{T}(z)\right){\frac {dz}{z}}.$ Untuk mendapatkan sebuah taksiran kasar pada integrand, misalkan $B$ menjadi sebuah batas atas untuk ${\frac {\vartheta (e^{t})}{e^{t}}}-1$, maka untuk $\Re z>0$

$|g(z)-g_{T}(z)|\leq B\int _{T}^{\infty }e^{-\Re (z)t}\,dt={\frac {Be^{-\Re (z)T}}{\Re z}}.$

Batas ini tidak cukup baik untuk membuktikan hasilnya, tetapi Newman memperknelakan faktor

$F(z)=e^{zT}\left(1+{\frac {z^{2}}{R^{2}}}\right)$

menjadi integrand untuk $g(0)-g_{T}(0)$. Karena faktor Newman $F$ adalah menyeluruh dan $F(0)=1$, sisi kiri ttap tidak berubah. Sekarang taksiran di atas untuk $\left|g(z)-g_{T}(z)\right|$ dan taksiran pada $F$ menggabungkan untuk diberikan

$\left|{\frac {1}{2\pi i}}\int _{C_{+}}\left(g(z)-g_{T}(z)\right)F(z){\frac {dz}{z}}\right|\leq {\frac {B}{R}}$.

dimana $C_{+}$ adalah setengah lingkaran $C\cup \{z\mid \Re z>0\}$

Misalkan $C_{-}$ menjadi kontur $C\cap \{\Re z\leq 0\}$. Fungsi $g_{T}$ adalah menyeluruh, jadi oleh teorema integral Cauchy, kontur $C$ bisa dimodifikasi ke sebuah setengah lingakran dari jari-jari $R$ dalam kiri setengah bidang tanpa mengubah integral ${\frac {g_{T}(z)F(z)}{2\pi iz}}$, dan argumen yang sama memberikan nilai mutlak dari integral ini sebagai $\leq {\frac {B}{R}}$. Akhirnya, memisalkan $T\to \infty$, integral ${\frac {g_{T}(z)F(z)}{z}}$ pada kontur $C_{\delta }$ karena $F$ menuju nol pada kontur. Menggabungkan tifga taksiran, mendapatkan

$\limsup _{T\to \infty }|g(0)-g_{T}(0)|\leq {\frac {2B}{R}}$.

Ini berlaku untuk setiap $R$ jadi $\lim _{T\to \infty }g_{T}(0)=g(0)$, dan TBP berikut.

Fungsi penghitung bilangan prima dalam istilah dari integral logaritmik

Dalam sebuah catatan tulisan tangan pada sebuah cetakan ulang makalahnya tahun 1838 "Sur l'usage des séries infinies dans la théorie des nombres" yang dia dikirim ke Gauss, Dirichlet menduga (di bawah bentuk yang sedikir berbeda untuk sebuah deret daripada sebuah integral) bahwa aproksimasi yang lebih baik untuk $\pi (x)$ diberikan oleh fungsi integral logaritmik pengimbangan $\operatorname {Li} (x)$, didefinisikan oleh

$\operatorname {Li} (x)=\int _{2}^{x}{\frac {dt}{\log t}}=\operatorname {li} (x)-\operatorname {li} (2)$.

Bahkan, integral ini merupakan sugestif yang kuat dari gagasan bahwa "kepadatan" bilangan prima di sekitar $t$ harus ${\frac {1}{\log t}}$. Fungsi ini berakitan dengan logaritma oleh ekspansi asimtotik

$\operatorname {Li} (x)\sim {\frac {x}{\log x}}\sum _{k=0}^{\infty }{\frac {k!}{(\log x)^{k}}}={\frac {x}{\log x}}+{\frac {x}{(\log x)^{2}}}+{\frac {2x}{(\log x)^{3}}}+\cdots$

Jadi, teorema bilangan prima dapat juga ditulis sebagai $\pi (x)\sim \operatorname {Li} (x)$. Faktanya, dalam makalah lainnya pada tahun 1899 de la Vallée Poussin membuktikan bahwa

$\pi (x)=\operatorname {Li} (x)+O\left(xe^{-a{\sqrt {\log x}}}\right)\quad {\text{karena }}x\to \infty$

untuk beberapa konstanta positif $a$, dimana $O(\dots )$ adalah notasi O besar. Ini telah ditingkatkan menjadi

$\pi (x)=\operatorname {li} (x)+O\left(x\exp \left(-{\frac {A(\log x)^{\frac {3}{5}}}{(\log \log x)^{\frac {1}{5}}}}\right)\right)$ dimana $A=0.2098$ .

Pada tahun 2016, Trudgian membuktikan sebuah batas atas eksplisit untuk selisih antara $\pi (x)$ dan $\operatorname {li} (x)$ː

${\big |}\pi (x)-\operatorname {li} (x){\big |}\leq 0.2795{\frac {x}{(\log x)^{3/4}}}\exp \left(-{\sqrt {\frac {\log x}{6.455}}}\right)$

untuk $x\geq 229$.

Hubungan antara fungsi zeta Riemann dan $\pi (x)$ merupakan salah satu alasan hipotesis Riemann sangat penting dalam teori bilanganː jika ditetapkan, itu akan menghasilkan perkiraan kesalahan yang terlibat dalam teorema bilangan prima yang jauh lebih baik daripada yang tersedia saat ini. Lebih spesifik, Helge von Koch menunjukkan pada tahun 1901 bahwa jika hipotesis Riemann adalah benar, istilah galat dalam relasi di atas bisa ditingkatkan menjadi

$\pi (x)=\operatorname {Li} (x)+O\left({\sqrt {x}}\log x\right)$

(perkiraan terakhir ini sebenarnya setara dengan hipotesis Riemann). Konstantanya melibatkan dalam notasi O besar diperkirakan pada tahun 1976 oleh Lowell Schoenfeldː dengan asumsi hipotesis Riemann,

${\big |}\pi (x)-\operatorname {li} (x){\big |}<{\frac {{\sqrt {x}}\log x}{8\pi }}$

untuk semua $x\geq 2657$. Dia juga menurunkan sebuah batas serupa untuk fungsi penghitung bilangan prima Chebyshev $\psi$ː

${\big |}\psi (x)-x{\big |}<{\frac {{\sqrt {x}}(\log x)^{2}}{8\pi }}$

untuk semua $x\geq 73.2$. Batas terakhir ini telah ditunjukkan untuk mengekspresikan sebuah perbedaan yang berarti hukum pangkat (ketika dianggap sebagai sebuah fungsi acak pada bilangan bulat) dan ${\frac {1}{7}}$ derau dan juga sesuai dengan Distribusi Poisson majemuk Tweedie (distribusi Tweedie mewakili sebuah keluarga distribusi skala invarian yang berfungsi sebagai fokus konvergensi untuk generalisasi teorema limit pusat.)

Integral logaritmik $\operatorname {li} (x)$ lebih besar dari $\pi (x)$ untuk nilai "kecil" $x$. Ini dikarenakan ini (dalam beberapa arti) menghitung bukan bilangan prima, tetapi pangkat bilangan prima, dimana $a$ pangkat $p^{n}$dari sebuah bilangna prima $p$ dihitung sebagai ${\frac {1}{n}}$ dari sebuah bilangan prima. Ini menunjukkan bahwa $\operatorname {li} (x)$ biasanya harus lebih besar dari $\pi (x)$ kira-kira ${\frac {\operatorname {li} ({\sqrt {x}})}{2}}$, dan khususnya harus selalu lebih besar dari $\pi (x)$. Namun, pada tahun 1914, J. E. Littlewood membuktikan bahwa $\pi (x)-\operatorname {li} (x)$ sering berubah tanda. Nilai pertama $x$ dimana $\pi (x)$ melebihi $\operatorname {li} (x)$ mungkin ada di sekitar $x=10^{316}$; lihat artikel bilangan Skewes untuk detail lebih lanjut. (Di samping itu, integral logaritmik pengimbangan $\operatorname {Li} (x)$ lebih kecil dari $\pi (x)$ sudah untuk $x=2$; memang, $\operatorname {Li} (2)=0$, sementara $\pi (2)=1$.)

Bukti-bukti dasar

Di paruh pertama abad kedua puluh, beberapa matematikawan (terutama G. H. Hardy) percaya bahwa ada sebuah hierarki metode-metode bukti dalam matematika tergantung dari jenis bilangannya (bilangan bulat, bilangan real, bilangan kompleks) sebuah bukti dibutuhkan, dan bahwa terema bilangan prima (TBP) adalah sebuah teorema yang "dalam" berdasarkan analisis kompleks. Kepercayaan ini agak terguncang oleh bukti TBP berdasarkan teorema tauberian Wiener, meskipun ini bisa dikesamping jika teorema Wiener dianggap memiliki "kedalaman" yang setara dengan metode variabel kompleks.

Pada bulan Maret 1948, Atle Selberg menetapkan, dengan cara "dasar", rumus asimtotik

$\vartheta (x)\log(x)+\sum \limits _{p\leq x}{\log(p)}\ \vartheta \left({\frac {x}{p}}\right)=2x\log(x)+O(x)$ dimana

$\vartheta (x)=\sum \limits _{p\leq x}{\log(p)}$

untuk bilangan prima $p$. Pada bulan Juli tahun itu, Selberg dan Paul Erdős telah masing-masing memperoleh bukti-bukti dasar dari TBP, keduanya menggunakan rumus asimtotik Selberg sebagai titik awal. Bukti-bukti ini secara efektif meletakkan gagasan bahwa TBP "dalam" dalam arti itu, dan menunjukkan bahwa secara teknis metode "elementer" lebih kuat daripada yang diyakini. Tentang sejarah dari bukti-bukti dasar TBP, termasuk sengketa prioritas Erdős–Selberg, lihat sebuah artikel oleh Dorian Goldfeld.

Ada beberapa debat tentang makna signifikansi hasil Erdős and Selberg. Tidak ada definisi yang ketak dan diterima secara luas dari gagasan bukti elementer dalam teori bilangan, jadi tidak jelas persis dalam apa arti bukti mereka "elementer". Meskipun ini tidak menggunakan analisis kompleks, ini sebenarnya jauh lebih teknis daripada bukti standar TBP. Salah satu kemungkinan definisi dari sebuah bukti "elementer" adalah "salah satu bahwa bisa dilakukan dalam urutan pertama aritmetika Peano." Terdapat pernyataan teori bilangan (sebagai contoh, teorema Paris–Harrington) dapat dibuktikan menggunakan tingkat kedua tetapi bukan metode tingkat pertama, tetapi teorema seperti itu jarang terjadi. Bukti Erdős dan Selberg diformalkan dalam aritmetika Peano, dna pada tahun 1994. Charalambos Cornaros dan Costas Dimitracopoulos membuktian bahwa bukti mereka bisa diformalkan dalam fragmen PA yang sangat lemah, yaitu $I\Delta _{0}+\exp$. Namun, ini tidak membahas pertanyaan apakah bukti standar TBP bisa diformalkan dalam PA atau tidak.

Verifikasi komputer

Pada tahun 2005, Avigad et.al. menggunakan pembukti teorema Isabelle untuk merancang varian yang diverifikasi komputer dari bukti dari TBP. Ini adalah bukti terverifikasi mesin pertama dari TBP. Avigad memilih untuk meresmikan bukti Erdős–Selberg daripada yang analitik karena sementara perpustakaan Isabelle pada saat itu dapat mengimplementasikan gagasan tentang limit, turunan, dan fungsi transendental, hampir tidak ada teori integrasi untuk dibicarakan.

Pada tahun 2009, John Harrison menggunakan HOL Light untuk meresmikab sebuah bukti yang menggunakan analisis kompleks. Dengan mengembangkan mesin analitik yang diperlukan, termasuk rumus integral Cauchy, Harrison sudah bisa meresmikan "sebuah bukti langsung, modern dan elegan termasuk melibatkan argumen Erdős–Selberg 'elementer'".

Teorema bilangan prima untuk barisan aritmetika

Misalkan $\pi _{n,a}(x)$ melambangkan bilangan prima dalam barisan aritmetika $a,a+n,a+2n,a+3n,\dots$ lebih kecil dari $x$. Dirichlet dan Legendre menduga, dan de la Vallée Poussin membuktikan, bahwa, jika $a$ dan $n$ adalah koprima, maka

$\pi _{n,a}(x)\sim {\frac {1}{\varphi (n)}}\operatorname {Li} (x),$dimana $\varphi$ adalah fungsi total Euler. Dengan kata lain, bilangan prima didistribusikan secara merata di sekitar kelas residu $[a]$ modulo $n$ dengan $\gcd(a,n)=1$. Ini leih kuat dari pada teorema Dirichlet pada barisan aritmetika (yang hanya menyatakan bahwa ada sebuah bilangan prima yang tak terhingga dalam setiap kelas) dan bisa dibuktikan menggunakan metode serupa yang digunakan oleh Newman untuk buktinya dari teorema bilangan prima.

Teorema Siegel–Walfisz memberikan sebuah taksiran yang baik untuk distribusi bilangan prima dalam kelas residu.

Perlombaan bilangan prima

Meskipun kita memiliki secara khusus

$\pi _{4,1}(x)\sim \pi _{4,3}(x),$

secara empiris bilangan prima kongruen dengan 3 lebih banyak dan hampir selalu unggul dalam "perlombaan bilangan prima" ini, pembalikan pertama terjadi pada $x=26861$..^:1–2 Namun Littlewood menunjukkan pada tahun 1914^:2 bahwa ada tanda yang tak terhingganya banyaknya

$\pi _{4,1}(x)-\pi _{4,3}(x),$

jadi keunggulan dalam perlombaan beralih berkali-kali tanpa batas. Fenomena yang $\pi _{4,3}(x)$ di depan sebagian besar waktu disebut bias Chebyshev. Perlombaan bilangan prima menggeneralisasi ke moduli lain dan merupakan subjek dari banyak penelitian; Pál Turán bertanya apakah selalu demikian bahwa $\pi (x,a,c)$ dan $\pi (x,b,c)$ mengubah tempat dimana $a$ dan $b$ merupakan koprima ke $c$. Granville dan Martin memberikan eksposisi dan survei yang menyeluruh.

Batasan non-asimtotik pada fungsi penghitung bilangan prima

Teorema bilangan prima adalah sebuah hasil asimtotik. Ini memberikan sebuah batas tidak efektif pada $\pi (x)$ sebagai sebuah konsekuensi langsung dari definisi dari limit: untuk semua $\varepsilon >0$, terdapat $S$ sehingga untuk semua $x>S$,

$(1-\varepsilon ){\frac {x}{\log x}}<\pi (x)<(1+\varepsilon ){\frac {x}{\log x}}.$

Namun, batas yang lebih baik pada $\pi (x)$ dikenal, misalnya Pierre Dusart

${\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}\right)<\pi (x)<{\frac {x}{\log x}}\left(1+{\frac {1}{\log x}}+{\frac {2.51}{(\log x)^{2}}}\right).$

Pertidaksamaan pertama berlaku untuk semua $x\geq 599$ dan yang kedua untuk $x\geq 355991$.

Batas yang lemah tapi terkadang berguna untuk $x\geq 55$ adalah

${\frac {x}{\log x+2}}<\pi (x)<{\frac {x}{\log x-4}}.$

Dalam tesis Pierre Dusart ada versi lebih kuat dari jenis ini pertidaksamaan bahwa sah untuk $x$ lebih besar. Kemudian pada tahun 2010, Dusart membuktikan.

${\begin{aligned}{\frac {x}{\log x-1}}&<\pi (x)&&{\text{untuk }}x\geq 5393,{\text{ dan}}\\\pi (x)&<{\frac {x}{\log x-1.1}}&&{\text{untuk }}x\geq 60184.\end{aligned}}$

Bukti oleh de la Vallée Poussin menyiratkan sebagai berikut. Untuk setiap $\varepsilon >0$, terdapat $S$ sehingga untuk semua $x>S$,

${\frac {x}{\log x-(1-\varepsilon )}}<\pi (x)<{\frac {x}{\log x-(1+\varepsilon )}}.$

Aproksimasi untuk bilangan prima ke-n

Sebagai konsekuensi dari teorema bilangan prima, salah satu mendapatkan sebuah ekspresi asimtotik untuk bilangan prima ke-$n$, dilambangkan dengan $p_{n}$.

$p_{n}\sim n\log n.$

Sebuah aproksimasi yang lebih baik adalah

${\frac {p_{n}}{n}}=\log n+\log \log n-1+{\frac {\log \log n-2}{\log n}}-{\frac {(\log \log n)^{2}-6\log \log n+11}{2(\log n)^{2}}}+o\left({\frac {1}{(\log n)^{2}}}\right).$

Lagi andaikan bilangan prima ke-$2\times 10^{17}$: $8\ 512\ 677\ 386\ 048\ 191\ 063$, ini diberikan sebuah taksiran $8\ 512\ 681\ 315\ 554\ 715\ 386$; 5 digit pertama cocok dan galat relatif sekitar $0.00005\%$.

Teorema Rosser menyatakan bahwa

$p_{n}>n\log n.$

Ini bisa diperbaiki dengan mengikuti sepasang batas berikut.

Tabel $\pi (x)$, ${\frac {x}{\log x}}$, dan $\operatorname {li} (x)$

Tabelnya membandingkan nilai eksak $\pi (x)$ dengan aproksimasi ${\frac {x}{\log x}}$ dan $\operatorname {li} (x)$. Kolom terakhir, ${\frac {x}{\pi (x)}}$, adalah rerata celah bilangan prima di bawah $x$.

$x$	$\pi (x)$	$\pi (x)-{\frac {x}{\log x}}$	${\frac {\pi (x)}{\frac {x}{\log x}}}$	$\operatorname {li} (x)-\pi (x)$	${\frac {x}{\pi (x)}}$
10	4	−0.3	0.921	2.2	2.5
102	25	3.3	1.151	5.1	4
103	168	23	1.161	10	5.952
104	1229	143	1.132	17	8.137
105	9592	906	1.104	38	10.425
106	78498	6116	1.084	130	12.740
107	664579	44158	1.071	339	15.047
108	5761455	332774	1.061	754	17.357
109	50847534	2592592	1.054	1701	19.667
1010	455052511	20758029	1.048	3104	21.975
1011	4118054813	169923159	1.043	11588	24.283
1012	37607912018	1416705193	1.039	38263	26.590
1013	346065536839	11992858452	1.034	108971	28.896
1014	3204941750802	102838308636	1.033	314890	31.202
1015	29844570422669	891604962452	1.031	1052619	33.507
1016	279238341033925	7804289844393	1.029	3214632	35.812
1017	2623557157654233	68883734693281	1.027	7956589	38.116
1018	24739954287740860	612483070893536	1.025	21949555	40.420
1019	234057667276344607	5481624169369960	1.024	99877775	42.725
1020	2220819602560918840	49347193044659701	1.023	222744644	45.028
1021	21127269486018731928	446579871578168707	1.022	597394254	47.332
1022	201467286689315906290	4060704006019620994	1.021	1932355208	49.636
1023	1925320391606803968923	37083513766578631309	1.020	7250186216	51.939
1024	18435599767349200867866	339996354713708049069	1.019	17146907278	54.243
1025	176846309399143769411680	3128516637843038351228	1.018	55160980939	56.546
OEIS	A006880	A057835		A057752

Nilai untuk $\pi (10^{24})$ awalan dihitung dengan asumsi hipotesis Riemann; itu telah diverifikasi tanpa syarat.

Analog dari polinomial taktereduksi lagi pada sebuah medan berhingga

Ada sebuah analog dari teorema bilangan prima bahwa menggambarkan polinomial taktereduksi "distribusi" pada sebuah medan berhingga terbatas, bentuknya sangat mirip dengan kasus teorema bilangan prima klasik.

Untuk menyatakannya dengan tepat, misalkan $F=\operatorname {GF} (q)$ menjadi medan berhingga dengan anggota $q$, dan misalkan $N_{n}$ menjadi bilangan polinomial taktereduksi monik pada $F$ yag derajatnya sama dengan $n$. Artinya, kita sedang melihat pada polinomial yang koefisiennya terpilih dari $F$, yang tidak bisa ditulis sebagai produk polinomial derajat lebih kecil. Dalam pengaturan ini, polinomial ini memainkan peran dari bilangan prima, karena semua polinomial monik lainnya dibangun dari produk mereka. Salah satunya kemudian membuktikan bahwa

$N_{n}\sim {\frac {q^{n}}{n}}.$

Jika kita membuat substitusi $x=q^{n}$, maka di sisi sebelah kanan hanya

${\frac {x}{\log _{q}x}},$

yang membuat analoginya lebih jelas. Karena tepatnya ada polinomial monik $q^{n}$ derajat $n$ (termasuk yang dapat direduksi), ini bisa diubah sebagai berikut: jika sebuah polinomial monik derajat $n$ dipilih secara acak, maka kemungkinan itu tidaktereduksi sekitar ${\frac {1}{n}}$.

Salah satunya bisa membuktikan sebuah analog dari hipotesis Riemann, yaitu

$N_{n}={\frac {q^{n}}{n}}+O\left({\frac {q^{\frac {n}{2}}}{n}}\right).$

Bukti dari pernyataan-pernyataan ini jauh lebih sederhana daripada dalam kasus klasik. Ini melibatkan argumen kombinatorika singkat, diringkas sebagai berikut: setiap anggota dari derajat $n$ ekstensi $F$ adalah sebuah akar dari beberapa polinomial taktereduksi yang derajat $d$ membagi $n$, dengan menghitung akar-akar ini dalam dua cara yang berbeda salah satunya menetapkan bahwa

$q^{n}=\sum _{d\mid n}dN_{d},$

dimana jumlah pada semua pembagi $d$ pada $n$. Invers Möbius kemudian menghasilkan

$N_{n}={\frac {1}{n}}\sum _{d\mid n}\mu \left({\frac {n}{d}}\right)q^{d},$

dimana $\mu (k)$ adalah fungsi Möbius. (Rumus ini diketahui Gauss.) Suku utama terjadi untuk $d=n$, dan ini tidak sulit untuk membatasi suku-suku yang tersisa. Pernyataan "hipotesis Riemann" tergantung pada fakta bahwa pembagi terbesar pada $n$ tidak boleh lebih besar dari ${\frac {n}{2}}$.

Lihat pula

• Hipotesis Riemann
• Teorema ideal bilangan prima Landau untuk sebuah generalisasi untuk ideal bilangan prima dalambidang bilangan aljabar
• Teori bilangan analitik abstrak untuk informasi tentang generalisasi dari teorema.

Referensi

• Hardy, G. H.; Littlewood, J. E. (1916). "Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes". Acta Mathematica. 41: 119–196. doi:10.1007/BF02422942. 
• Granville, Andrew (1995). "Harald Cramér and the distribution of prime numbers" (PDF). Scandinavian Actuarial Journal. 1: 12–28. doi:10.1080/03461238.1995.10413946. 

Tautan eksternal

• Hazewinkel, Michiel, ed. (2001) [1994], "Distribution of prime numbers", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• Table of Primes by Anton Felkel.
• Short video visualizing the Prime Number Theorem.
• Prime formulas and Prime number theorem at MathWorld.
• Prime number theorem, PlanetMath.org.
• How Many Primes Are There? and The Gaps between Primes by Chris Caldwell, University of Tennessee at Martin.
• Tables of prime-counting functions by Tomás Oliveira e Silva