Terobosan yang Mengungkap Struktur Tersembunyi Bilangan Prima

 (science.org)
1 poin oleh GN⁺ 2024-08-02 | 1 komentar | Bagikan ke WhatsApp
  • Preprint 31 Mei dari James Maynard dan Larry Guth menyingkirkan pengecualian tertentu pada Hipotesis Riemann, mencatat kemajuan pertama dalam beberapa dekade pada masalah berusia 165 tahun untuk menemukan struktur tersembunyi dalam distribusi bilangan prima
  • Fokus utamanya adalah zero nontrivial dari fungsi zeta Riemann, yang terkait langsung dengan pemahaman galat antara estimasi jumlah bilangan prima oleh Gauss dan distribusi bilangan prima yang sebenarnya
  • Komputer telah memastikan bahwa lebih dari 10 triliun zero semuanya memiliki bagian real 1/2, tetapi yang diinginkan matematikawan bukan verifikasi empiris, melainkan bukti bahwa posisi lain mustahil
  • Pencapaian ini menurunkan batas atas jumlah zero di titik 3/4 yang belum membaik sejak Albert Ingham pada 1940, serta memecahkan penghalang lama dengan menggabungkan teori bilangan analitik dan analisis harmonik
  • Pembuktian lengkap Hipotesis Riemann masih jauh, tetapi ini dapat mengarah pada alat baru untuk memperkirakan jumlah bilangan prima pada interval yang lebih pendek dan menangani masalah lain dalam teori bilangan

Hipotesis Riemann untuk memecahkan distribusi bilangan prima

  • Setiap bilangan asli dapat diuraikan menjadi hasil kali bilangan prima yang hanya habis dibagi oleh dirinya sendiri dan 1, dan matematikawan telah berusaha memahami bagaimana bilangan-bilangan prima ini tersusun di garis bilangan
  • Bilangan prima sekilas tampak cukup acak, tetapi diyakini memiliki struktur tersembunyi di dalamnya
  • Selama 165 tahun terakhir, Hipotesis Riemann menjadi pusat pencarian struktur tersebut
    • Jika terbukti, hipotesis ini dapat berperan seperti Rosetta Stone untuk memecahkan bilangan prima
    • Tersedia hadiah 1 juta dolar dari Clay Mathematics Institute

Estimasi Gauss dan zero zeta

  • Pada akhir 1700-an, ketika berusia 16 tahun, Carl Friedrich Gauss mengamati bahwa bilangan prima menjadi makin jarang saat angkanya makin besar, lalu memperkirakan bahwa jumlah bilangan prima hingga X kira-kira berskala X / ln X
  • Estimasi ini sejauh ini sangat cocok dengan jumlah bilangan prima sebenarnya, dengan nilai aktual berayun sedikit di atas dan di bawah kurva
  • Pada 1859, Bernhard Riemann mencoba menangani selisih antara kurva Gauss dan distribusi bilangan prima sebenarnya menggunakan fungsi zeta Riemann
    • Fungsi ini menerima bilangan kompleks sebagai input, yang memiliki komponen real dan imajiner
    • Zero zeta, yaitu titik ketika fungsi zeta Riemann bernilai 0, secara langsung menggambarkan fluktuasi galat di sekitar kurva Gauss

Batasan yang dituntut Hipotesis Riemann

  • Hipotesis Riemann memprediksi bahwa, kecuali beberapa solusi trivial dari input negatif, semua input zero zeta harus memiliki bagian real 1/2
  • Jika hipotesis ini benar, fluktuasi jumlah bilangan prima akan terbatas, yang berarti distribusi bilangan prima pada garis bilangan tidak memiliki gumpalan besar atau celah besar
  • Hingga kini, komputer telah memeriksa lebih dari 10 triliun zero zeta nontrivial, dan semuanya tepat berada pada bagian real 1/2
  • Namun verifikasi empiris saja tidak cukup
    • Maynard menilai bahwa bukti bukan sekadar mengonfirmasi kebenarannya, tetapi membantu memahami mengapa itu benar dan memberikan teknik baru yang kuat untuk menangani bilangan prima
    • Bahkan jalur serangan yang tampak masuk akal untuk membuktikan Hipotesis Riemann pun belum ada

Celah sempit yang disasar hasil kali ini

  • Karena belum mampu membuktikan seluruh Hipotesis Riemann secara langsung, matematikawan membagi masalahnya dengan mempersempit wilayah tempat zero zeta tidak mungkin berada
  • Zero zeta nontrivial sudah diketahui terkurung di antara 0 dan 1
  • Ada pula simetri cermin yang berpusat pada 1/2, sehingga jika zero di titik 3/4 disingkirkan, zero di titik 1/4 juga tersingkir
  • Teknik yang ada sebelumnya bekerja lebih baik di antara 1/2 dan 3/4, atau antara 3/4 dan 1, tetapi masih tersisa kemungkinan bahwa banyak zero bersembunyi di 3/4
  • Batas atas terbaik untuk jumlah zero yang bisa berada di 3/4 adalah hasil dari matematikawan Inggris Albert Ingham pada 1940, dan sejak itu belum ada yang berhasil memperbaikinya

Pendekatan Maynard dan Guth

  • Maynard adalah matematikawan spesialis teori bilangan analitik dan peraih Fields Medal 2022; selama 10 tahun terakhir ia berulang kali memikirkan masalah ini setiap Jumat sore, tetapi belum memperoleh hasil
  • Pada pertemuan American Mathematical Society tahun 2020, Maynard meminta bantuan Larry Guth dari MIT, yang berspesialisasi dalam analisis harmonik
    • Analisis harmonik adalah teknik yang terkait dengan cara meminjam ide dari fisika untuk memisahkan suara menjadi nada-nada penyusunnya
    • Guth juga bergelut dengan masalah ini selama beberapa tahun, dan tepat sebelum menyerah, ia menemukan terobosan bersama Maynard
  • Keduanya meminjam strategi dari bahasa matematika masing-masing dan bertukar ide lewat email hingga larut malam, lalu dengan cara yang tidak ortodoks mematahkan batas atas Ingham

Potensi dampak ke seluruh teori bilangan

  • Maksym Radziwill menilai karya ini sebagai ide baru pertama dalam 50 tahun untuk pencarian zero zeta, dan melihat bahwa bidang yang lama terabaikan dapat bergerak lagi
  • Batas atas yang lebih baik ini hampir tidak membantu pembuktian Hipotesis Riemann secara keseluruhan, tetapi dapat berdampak pada teori bilangan secara luas
    • Matematikawan dapat memperkirakan jumlah bilangan prima dengan lebih baik pada interval yang lebih pendek
    • Radziwill menilai strategi baru ini dapat membantu menyederhanakan karya sebelumnya yang terkait sistem dinamika
    • Ini juga dapat membantu masalah Kakeya
    • Guth tertarik menggunakan gagasan ini untuk mengeksplorasi hubungan mendalam antara fisika gelombang dan distribusi himpunan bilangan

Bacaan terkait

1 komentar

 
GN⁺ 2024-08-02
Opini Hacker News

  • Ini materi dari Mei, dan artikel yang lebih baik sudah terbit di Quanta serta sudah dibahas juga di sini
    https://www.quantamagazine.org/sensational-proof-delivers-ne...

  • Membayangkan temuan ini mengarah ke terobosan yang lebih besar tentang bilangan prima, membuat faktorisasi prima bilangan bulat besar menjadi mudah dan kriptografi kunci publik seperti RSA lumpuh dalam semalam
    Jika kunci berukuran layanan nyata bisa dipecahkan siapa saja bahkan dengan CPU konsumen, apakah industri punya rencana pemulihan bencana untuk situasi seperti itu? Bisakah pemain besar cepat beralih ke sistem kriptografi lain yang belum terpecahkan? Bagi developer jailbreak, modder konsol, atau kubu “kebebasan perangkat”, itu akan menjadi hari yang seperti surga, tetapi dampak keseluruhannya tampaknya akan katastrofik dan sulit diperkirakan
    Rasanya industri tidak menganggap terobosan teori bilangan yang mendadak sebagai kejadian yang mungkin

    • Di RSA, hal seperti itu sudah terjadi beberapa kali
      Pernah ada masa ketika pemerintah AS membatasi ekspor kunci RSA panjang, dan pada suatu waktu sebagian besar dunia memakai kunci RSA 128-bit, lalu buru-buru pindah ke kunci 512-bit karena metode Dixon. Setelah itu naik tergesa-gesa ke 1024-bit karena special number field sieve, lalu naik lagi ke 2048-bit karena general number field sieve, dan itu juga belum terlalu lama
      Jika melihat perangkat keras enkripsi RSA dari era 80-an, ada perangkat yang dengan bangga menyatakan mampu menangani 512-bit. Sekarang itu tidak berguna
      https://people.csail.mit.edu/rivest/pubs/pubs/Riv84.pdf
      Rumus kompleksitas special/general number field sieve hanya berbeda beberapa konstanta, dan melihat konstanta-konstanta itu membuat saya bertanya-tanya apakah benar terlihat seperti batas fundamental. Rasanya sulit sekali percaya tidak ada cara untuk menurunkan konstanta itu lagi sampai kunci 2048-bit pun menjadi tidak berguna
      Tidak perlu bertanya “apa yang terjadi jika RSA pecah”. Dari pengalaman mengalami hal seperti ini beberapa kali, saya bisa langsung bilang kita akan panik menaikkan ukuran kunci lagi dan mengaudit semua data yang berpotensi bocor
    • Jika ditemukan cara untuk memfaktorkan bilangan bulat besar dengan mudah di perangkat keras konsumen, itu akan sangat menyakitkan karena RSA adalah salah satu algoritma kunci publik utama
      Namun sebelum khawatir, perlu diingat bahwa RSA sudah bertahan dari 47 tahun kriptoanalisis aktif. Selama itu banyak algoritma alternatif yang diusulkan sebagai lebih unggul, tetapi banyak pula yang tak lama kemudian berhasil dipecahkan
      Arus untuk beralih ke algoritma kurva eliptik juga terutama karena komputer dapat menangani enkripsi/dekripsi dengan lebih mudah
      Secara pribadi, jika harus bertaruh pada algoritma kunci publik yang masih ada 10 tahun lagi, saya akan memilih RSA
    • Tampaknya di titik inilah perpindahan ke kurva eliptik muncul, dan baik tanda tangan maupun handshake (Diffie-Hellman) sepertinya sudah cukup jauh berjalan
      Pemulihan bencana memang bukan pekerjaan 1 menit, tetapi jika RSA/DH menjadi tidak aman dalam semalam, rasanya tidak berarti semuanya akan tetap terbuka begitu saja. Kunci SSH saya sendiri sekarang juga sudah campuran beberapa metode
    • Industri bahkan tidak siap menghadapi satu pembaruan CrowdStrike yang buruk, tetapi setelah beberapa hari tetap berhasil membereskannya
      Kemampuan menyiapkan skenario katastrofik tampaknya dilebih-lebihkan, sementara kemampuan bertahan hidup justru diremehkan
    • Ada pandangan bahwa penemuan faktorisasi cepat sangat langka. Begitu banyak orang pintar sudah menelitinya, jadi untuk saat ini mungkin mustahil—namun cerita itu sendiri bisa juga menjadi kelemahan
      Risiko ini sama nyatanya dengan risiko badai Matahari besar yang meruntuhkan jaringan listrik, lalu menyebabkan masa pemulihan bertahun-tahun seperti zaman batu karena keterlambatan produksi trafo dan kurangnya cadangan. Namun dari sudut pandang itu, risikonya tampak terlalu kecil dan teoretis sehingga sulit mencurahkan banyak waktu
      Soal perencanaan, saya tidak tahu apakah sekadar beralih ke ECC semudah itu. Enkripsi asimetris aktual pada ECC bergantung pada rahasia bersama, dan jika diasumsikan RSA sudah pecah sehingga kanal pertukaran tidak aman, mungkin itu menjadi lebih rentan terhadap serangan man-in-the-middle dibanding RSA. Sepertinya bukan penggantian yang mudah
      Secara terpisah, ada juga kemungkinan RSA sebenarnya sudah pecah, dan solusinya dirahasiakan oleh badan-badan kriptoanalisis. Bagi mereka, menyembunyikan terobosan akan sangat menarik, dan mereka mungkin berusaha mencari cara untuk menekan “terobosan teori bilangan yang mendadak”

  • Orang-orang selalu menganggap struktur bilangan prima itu rumit, tetapi sebenarnya saya melihatnya hanya sebagai struktur rekursif dari ukuran celah yang tidak dapat dicapai oleh kelipatan celah-celah sebelumnya.
    Ini tidak berarti menjadi mudah untuk “memprediksi” tanpa melacak semua celah sebelumnya, tetapi pada dasarnya itu bukan struktur yang rumit. Menarik bahwa struktur sesederhana ini begitu sulit ditangkap. Mirip dengan bagaimana deret 3n+1 melahirkan kompleksitas, atau bagaimana peta logistik menjadi rumit setelah melewati nilai ambang.

    • Generator yang menghasilkan “semua bilangan prima” cukup sederhana dan deterministik.
      Namun, jika hanya diberi bilangan prima n dan ingin mendapatkan bilangan prima berikutnya, kita harus menghitung ulang sisa-sisa nontrivial, sehingga representasi biner dari angka n saja tidak memuat informasi yang cukup untuk menjawab dengan cepat apa bilangan prima berikutnya. Pertama-tama harus dihitung lebih dulu beberapa titik acuan. Pada akhirnya memang ada kompleksitas tambahan, tetapi tetap saja sederhana dan cukup jelas, dan bahkan bukan masalah yang masuk NP.
    • Ah, benar. Tidak ada yang sesederhana menyediakan teori dasar untuk teori bilangan, salah satu bidang paling ketat dan paling mengintimidasi secara intelektual dalam matematika /s
    • Saya penasaran mengapa ini tidak dianggap sebagai masalah yang sudah terpecahkan.
      https://en.wikipedia.org/wiki/Information_theory
      https://en.wikipedia.org/wiki/Computational_irreducibility
      https://en.wikipedia.org/wiki/Aperiodic_tiling

  • Bagian “dalam sesi berpikir khusus Jumat sore, ia terus kembali ke masalah ini selama 10 tahun terakhir, tetapi tanpa hasil” terasa memberi semangat.

    • Seingat saya Richard Hamming juga biasa mengosongkan Jumat sore sebagai waktu untuk berpikir mendalam dan besar. Cara yang keren.

  • Jika kurva Gauss dan kurva Riemann digambar di ruang tertentu, terlihat sesuatu yang lebih ajaib.
    Untuk melihat apa yang dimaksud dengan nol trivial dan nol nontrivial, lihat animasi Wikipedia ini: [https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_I...](https://en.wikipedia.org/wiki/File:Riemann3d_Re_0.1_to_0.9_Im_1_to_51.ogg)
    Pada dasarnya, saya melihatnya sebagai petunjuk bahwa ada relasi lain antara bilangan real dan imajiner yang belum kita temukan.
    Dan karena matematika Riemann terlibat dalam mekanika kuantum, ini juga punya implikasi untuk pencarian teori gravitasi.
    Rasanya seperti sains yang aneh bahwa bilangan prima terlibat, atau bisa terlibat, dalam teori gravitasi.

  • Saya penasaran dengan ungkapan “mereka akhirnya melakukan beberapa langkah tidak ortodoks untuk menembus batas Ingham”.
    Mengapa mengambil metode dari bidang lain dianggap tidak ortodoks? Dari latar belakang rekayasa, itu justru hal yang umum. Analisis harmonik adalah alat dasar di berbagai bidang seperti audio, gelombang, analisis listrik, statistik, dan algoritmanya pun secara internal adalah matematika murni.
    Kalau ingin menemukan struktur berulang dalam suatu sistem basis, bukankah wajar mencoba berbagai teknik penggambaran lalu memilih yang paling cocok untuk masalahnya?

    • Kutipan itu tidak terbaca seolah bagian tidak ortodoks dari pendekatan tersebut hanya berarti memakai ide analisis harmonik. Memakai analisis harmonik dalam teori bilangan sama sekali bukan hal baru.
      Dalam kuliah pertama teori bilangan analitik, ide kuncinya—dan ide kunci dari makalah terkenal Riemann tahun 1859—bisa disebut “analisis harmonik”. Itu juga bukan kebetulan, karena Riemann adalah pelopor bidang ini: https://old.reddit.com/r/math/comments/16bh3mi/what_is_the_b...
      Arus besar paling panas dalam teori bilangan saat ini pun pada dasarnya adalah analisis harmonik “berdimensi tinggi” di atas medan bilangan: https://en.wikipedia.org/wiki/Automorphic_form, https://en.wikipedia.org/wiki/Langlands_program. Kasus satu dimensi yang ingin digeneralisasi oleh program Langlands adalah https://en.wikipedia.org/wiki/Tate%27s_thesis, yang juga disebut “analisis Fourier di atas medan bilangan” dan merupakan salah satu ide terpenting dalam teori bilangan abad ke-20.
      Di antara referensi makalah Guth-Maynard juga ada buku tahun 1994 H. Montgomery, Ten Lectures On The Interface Between Analytic Number Theory And Harmonic Analysis, No. 84. American Mathematical Soc., 1994. Pada 1994 sudah ada sepuluh kuliah tentang titik temu itu, dan kalau melihat jumlah sitasi buku tersebut, ada jauh lebih banyak lagi titik temu. Saya sendiri mengutip buku ini di lebih dari separuh makalah saya.
      Yang mengejutkan bukan fakta bahwa mereka memakai analisis harmonik itu sendiri, melainkan di mana dan bagaimana mereka menerapkannya. Ini bagian yang benar-benar mustahil disampaikan kepada pembaca umum, jadi saya tidak ingin menyalahkan penulis artikelnya.
      Kedengarannya seperti mengatakan “mengapa membuat koneksi itu mengejutkan”, padahal terobosan sering muncul dari koneksi baru, dan fakta bahwa terobosan seperti itu sesekali terjadi tidak membuat koneksi baru menjadi tidak mengejutkan.
    • “Tidak ortodoks” mungkin agak terlalu kuat, tetapi maksudnya barangkali adalah bahwa mereka menerapkan teknik yang sudah ada dari bidang lain dengan cara baru.
      Dalam matematika, terobosan besar cukup sering muncul ketika seseorang menyadari paralelisme antara dua area yang tampaknya tidak berkaitan, lalu memakai ide dari satu area sebagai wawasan untuk area lain.
      Bagian sulitnya adalah koneksi lintas area seperti ini biasanya tidak jelas. Untuk melihat kemiripannya, bisa diperlukan lompatan pemahaman yang cukup besar.
    • Ungkapan yang agak lucu. Itu hanya wartawan yang menulis seperti wartawan.
      Bisa dibilang setiap penemuan matematika mengandung sejumlah langkah “tidak ortodoks”. Yang ortodoks, bagaimanapun, hanyalah semua yang sudah diketahui sejauh ini.

  • Dari pernyataan “Sekilas terlihat cukup acak. Namun sebenarnya diyakini ada struktur tersembunyi seperti ini di dalam bilangan prima”, saya jadi penasaran seperti apa kira-kira pola bilangan prima hipotetis itu
    Apakah yang diharapkan semacam rumus bentuk tertutup? Jika Hipotesis Riemann terbukti, apa langkah berikutnya untuk memahami distribusinya? Atau apakah pembuktiannya sendiri diharapkan memuat jawaban ini?

  • Setiap kali mendengar cerita tentang James Maynard, keyakinan saya makin kuat bahwa ia adalah genius yang hanya muncul sekali dalam satu generasi
    Ia sudah memberi begitu banyak kontribusi pada teori bilangan prima, dan saya merasa mungkin saja pembuktian Hipotesis Riemann muncul semasa hidup saya

  • Ini gambar yang baru pertama kali saya lihat, tapi sangat menarik sehingga membuat penasaran. Apakah pola yang muncul ketika bilangan prima digambar sebagai grafik koordinat polar adalah temuan terbaru, atau sudah lama dikenal dan hanya dipakai sebagai ilustrasi? Saya penasaran dengan nama dan sejarahnya

  • Sedikit menyimpang, tetapi kalimat ini mengingatkan saya pada aspek yang ditangani pembukti otomatis, yang mungkin bahkan belum mulai kita pikirkan
    “Matematikawan Rutgers University, Alex Kontorovich, mengatakan, ‘Itu adalah terobosan sensasional. Pembuktian ini berisi banyak ide baru yang akan digali orang selama bertahun-tahun ke depan’”
    Pembuktian atas sesuatu sering kali lebih menarik bukan sebagai sarana untuk memberi ketelitian, melainkan sebagai sudut pandang baru untuk melihat objek tersebut. Saya penasaran apakah ada pekerjaan semacam itu dalam matematika otomatis