Sebuah model OpenAI telah membantah dugaan utama dalam geometri diskret

Selama hampir 80 tahun, para matematikawan telah mempelajari pertanyaan yang tampak sederhana namun menipu: jika Anda menempatkan $n$ titik pada bidang, berapa banyak pasangan titik yang dapat berjarak tepat $1$ satu sama lain?

Ini adalah masalah jarak satuan pada bidang, yang pertama kali diajukan oleh Paul Erdős pada tahun 1946. Ini adalah salah satu pertanyaan paling terkenal dalam geometri kombinatorial, yang mudah dinyatakan dan sangat sulit diselesaikan. Buku tahun 2005 Research Problems in Discrete Geometry, karya Brass, Moser, dan Pach, menyebutnya “mungkin masalah yang paling terkenal (dan paling mudah dijelaskan) dalam geometri kombinatorial.” Noga Alon, seorang pakar kombinatorika terkemuka di Princeton, menggambarkannya sebagai “salah satu masalah favorit Erdős.” Erdős bahkan menawarkan hadiah uang tunai bagi siapa pun yang berhasil memecahkan masalah ini.

Hari ini, kami membagikan sebuah terobosan pada masalah jarak satuan. Sejak karya asli Erdős, keyakinan yang berlaku adalah bahwa konstruksi “kisi persegi” yang digambarkan lebih bawah pada dasarnya optimal untuk memaksimalkan jumlah pasangan berjarak satuan. Sebuah model internal OpenAI telah membantah dugaan lama ini, dengan memberikan keluarga contoh tak hingga yang menghasilkan peningkatan polinomial. Bukti tersebut telah diperiksa oleh sekelompok matematikawan eksternal. Mereka juga telah menulis makalah pendamping yang menjelaskan argumennya dan memberikan latar belakang serta konteks lebih lanjut tentang pentingnya hasil ini.

Hasil ini juga menonjol karena cara ditemukannya. Bukti ini berasal dari model penalaran serbaguna baru, bukan dari sistem yang dilatih khusus untuk matematika, diberi scaffold untuk menelusuri strategi pembuktian, atau ditargetkan khusus pada masalah jarak satuan. Sebagai bagian dari upaya yang lebih luas untuk menguji apakah model canggih dapat berkontribusi pada riset terdepan, kami mengevaluasinya pada kumpulan masalah Erdős. Dalam kasus ini, model tersebut menghasilkan bukti yang menyelesaikan masalah terbuka itu.

Bukti ini merupakan tonggak penting bagi komunitas matematika dan AI. Ini menandai pertama kalinya sebuah masalah terbuka penting, yang menjadi pusat suatu subbidang matematika, diselesaikan secara otonom oleh AI. Ini juga menunjukkan kedalaman penalaran yang kini didukung sistem-sistem ini. Matematika menyediakan wahana uji yang sangat jelas untuk penalaran: masalahnya presisi, bukti potensial dapat diperiksa, dan argumen panjang hanya berhasil jika penalarannya tetap utuh dari awal hingga akhir. Metode yang digunakan untuk menyelesaikan masalah ini juga patut diperhatikan. Bukti ini membawa gagasan tak terduga dan canggih dari teori bilangan aljabar untuk diterapkan pada pertanyaan geometri elementer.

Peraih Medali Fields Tim Gowers, yang menulis dalam makalah pendamping, menyebut hasil ini “tonggak dalam matematika AI.” Menurut ahli teori bilangan terkemuka Arul Shankar, “Menurut saya makalah ini menunjukkan bahwa model AI saat ini melampaui sekadar pembantu bagi matematikawan manusia – mereka mampu memiliki gagasan orisinal yang cemerlang, lalu mewujudkannya hingga tuntas”.

Buktinya tersedia di sini⁠(terbuka di jendela baru). Makalah pendamping yang ditulis matematikawan eksternal terkemuka tersedia di sini⁠(terbuka di jendela baru). Anda dapat menemukan versi ringkas dari rantai pemikiran model di sini⁠(terbuka di jendela baru).

Misalkan $u(n)$ adalah jumlah terbesar yang mungkin dari pasangan berjarak satuan di antara $n$ titik pada bidang. Contoh yang mencapai laju pertumbuhan linear mudah dibangun: menempatkan $n$ titik pada satu garis menghasilkan $n-1$ pasangan, sedangkan kisi persegi menghasilkan sekitar $2n$ pasangan. Konstruksi terbaik yang sebelumnya diketahui, yang berasal dari kisi persegi yang diskalakan ulang, ternyata menghasilkan lebih banyak lagi: $n^{1 + C / \log \log(n)}$ untuk suatu konstanta $C$. Karena $\log \log(n)$ menuju tak hingga seiring $n$, suku tambahan pada eksponen menuju $0$, yang berarti konstruksi ini mencapai pertumbuhan yang hanya sedikit lebih cepat daripada linear. Selama beberapa dekade, secara luas diyakini bahwa laju ini pada dasarnya adalah yang terbaik, dan tidak ada konstruksi yang dapat meningkat secara signifikan dibanding kisi persegi. Dalam istilah teknis, Erdős menduga batas atas $n^{1+o(1)}$ di mana tambahan $o(1)$ menunjukkan suku yang menuju $0$ seiring $n$.

Hasil baru kami membantah dugaan ini. Lebih tepatnya, untuk tak hingga banyak nilai $n$, bukti ini membangun konfigurasi $n$ titik dengan setidaknya $n^{1+\delta}$ pasangan berjarak satuan, untuk suatu eksponen tetap $\delta > 0$. (Bukti AI asli tidak memberikan $\delta$ yang eksplisit, tetapi penyempurnaan mendatang oleh profesor matematika Princeton Will Sawin telah menunjukkan bahwa kita dapat mengambil $\delta=0.014$.)

Sejarah masalah ini membantu pembaca memahami mengapa hasilnya mengejutkan. Batas bawah terbaik yang diketahui pada dasarnya tidak berubah sejak konstruksi asli Erdős pada 1946. Batas atas terbaik, $O(n^{4/3})$, berasal dari karya Spencer, Szemerédi, dan Trotter pada 1984, dan meskipun ada penyempurnaan di kemudian hari serta karya struktural terkait oleh Székely, Katz dan Silier, Pach, Raz, dan Solymosi serta yang lain, batas atas itu pada dasarnya tetap tidak berubah. Sebagai bukti yang mendukung dugaan tersebut, Matoušek dan Alon-Bucić-Sauermann mempelajari masalah ini dengan jarak non-Euklides pada bidang, dan membuktikan bahwa “sebagian besar” jarak non-Euklides ini mematuhi dugaan tersebut dalam arti tertentu.

Yang mengejutkan, bahan utama konstruksi ini berasal dari bagian matematika yang sangat berbeda yang dikenal sebagai teori bilangan aljabar, yang mempelajari konsep seperti faktorisasi dalam perluasan bilangan bulat yang dikenal sebagai medan bilangan aljabar.

Pada tingkat tinggi, bukti ini dimulai dari gagasan geometri yang familier dan mendorongnya ke arah yang tak terduga.

Batas bawah asli Erdős dapat dipahami melalui bilangan bulat Gaussian: bilangan berbentuk $a+bi$, di mana $a$ dan $b$ adalah bilangan bulat dan $i$ adalah akar kuadrat dari $-1$. Bilangan bulat Gaussian memperluas bilangan bulat biasa dan, seperti halnya bilangan bulat biasa, memiliki sifat seperti faktorisasi unik ke dalam bilangan prima. Perluasan dari bilangan bulat biasa atau bilangan rasional seperti ini dikenal sebagai medan bilangan aljabar. Argumen baru ini menggantikan bilangan bulat Gaussian dengan generalisasi yang lebih rumit dari teori bilangan aljabar dengan simetri yang lebih kaya yang dapat menciptakan jauh lebih banyak selisih panjang satuan.

Argumen yang tepat menggunakan alat seperti menara medan kelas tak hingga dan teori Golod–Shafarevich untuk menunjukkan bahwa medan bilangan yang diperlukan bagi argumen ini benar-benar ada. Gagasan-gagasan ini sudah dikenal baik oleh para ahli teori bilangan aljabar, tetapi sangat mengejutkan bahwa konsep-konsep ini memiliki implikasi bagi pertanyaan geometri pada bidang Euklides.

Hasil ini menandai momen penting dalam interaksi antara AI dan matematika: sebuah sistem AI telah secara otonom menyelesaikan masalah terbuka lama yang berada di pusat bidang yang aktif. Ini juga menawarkan gambaran awal tentang jenis kolaborasi baru antara AI dan matematikawan manusia. Dalam kasus ini, karya pendamping oleh matematikawan eksternal memberikan gambaran yang jauh lebih kaya daripada solusi asli saja.

Seperti yang ditulis Thomas Bloom dalam catatan pendamping:

“Saat menilai pentingnya dan pengaruh sebuah bukti yang dihasilkan AI, pertanyaan yang saya ajukan kepada diri saya adalah: apakah ini mengajarkan sesuatu yang baru kepada kita tentang masalah tersebut? Apakah kita sekarang memahami geometri diskret dengan lebih baik? Saya pikir jawabannya adalah ya, dengan kadar tertentu: ini menunjukkan bahwa konstruksi teori bilangan memiliki jauh lebih banyak hal untuk dikatakan tentang pertanyaan-pertanyaan semacam ini daripada yang kami duga; terlebih lagi, teori bilangan yang dibutuhkan bisa sangat dalam. Tidak diragukan lagi banyak ahli teori bilangan aljabar akan mencermati masalah terbuka lain dalam geometri diskret dalam beberapa bulan mendatang.”

Keterkaitan tak terduga antara teori bilangan aljabar dan geometri diskret yang diungkap oleh solusi ini adalah bagian dari apa yang membuat hasil ini menonjol. Hasil ini tidak sekadar menyelesaikan dugaan tertentu, tetapi juga dapat memberi para matematikawan jembatan untuk mulai menjelajahi masalah terkait lainnya.

Bloom juga menunjuk pada kemungkinan yang lebih luas:

“Batas pengetahuan sangat bergerigi, dan tidak diragukan lagi bulan-bulan dan tahun-tahun mendatang akan menyaksikan keberhasilan serupa di banyak bidang matematika lainnya, ketika masalah terbuka lama diselesaikan oleh AI yang mengungkap keterkaitan tak terduga dan mendorong perangkat teknis yang ada hingga batasnya. AI membantu kita menjelajahi dengan lebih penuh katedral matematika yang telah kita bangun selama berabad-abad; keajaiban tak terlihat apa lagi yang sedang menunggu di balik layar?”

Hasil ini memberikan contoh yang menjanjikan: AI berkontribusi bukan hanya solusi, tetapi juga penemuan matematika yang signifikansinya menjadi lebih jelas dan lebih kaya melalui pemahaman manusia selanjutnya.

Inti pelajarannya lebih besar daripada hasil khusus ini. Penalaran matematika yang lebih baik dapat menjadikan AI mitra riset yang lebih kuat: sesuatu yang dapat menjaga alur pemikiran sulit tetap utuh, menghubungkan gagasan lintas bidang pengetahuan yang berjauhan, menampilkan jalur menjanjikan yang mungkin tidak diprioritaskan para ahli, dan membantu peneliti membuat kemajuan pada masalah yang jika tidak akan terlalu rumit atau memakan waktu untuk ditangani.

Kemampuan-kemampuan itu penting melampaui matematika. Jika sebuah model dapat menjaga argumen yang rumit tetap koheren, menghubungkan gagasan lintas bidang pengetahuan yang berjauhan, dan menghasilkan karya yang lolos dari telaah pakar, maka itu juga merupakan kemampuan yang berguna dalam biologi, fisika, ilmu material, rekayasa, dan kedokteran, dan merupakan bagian dari jalur jangka panjang kami menuju riset yang lebih otomatis: sistem yang dapat membantu ilmuwan dan insinyur menjelajahi lebih banyak gagasan dan mengejar pertanyaan teknis yang lebih sulit.

AI akan segera mulai mengambil peran yang sangat serius dalam bagian-bagian kreatif dari riset, dan yang terpenting riset AI itu sendiri. Meskipun kemajuan ini tidak tak terduga, hal ini memperkuat urgensi yang kami rasakan untuk memahami fase berikutnya dari pengembangan AI, tantangan menyelaraskan sistem yang sangat cerdas, dan masa depan kolaborasi manusia-AI.

Masa depan itu tetap bergantung pada penilaian manusia. Keahlian menjadi lebih berharga, bukan sebaliknya. AI dapat membantu mencari, menyarankan, dan memverifikasi. Manusia memilih masalah yang penting, menafsirkan hasilnya, dan memutuskan pertanyaan apa yang akan dikejar selanjutnya.