Model OpenAI telah menyangkal konjektur teras dalam geometri diskret

Selama hampir 80 tahun, ahli matematik telah mengkaji satu soalan yang kelihatan mudah tetapi mengelirukan: jika anda meletakkan $n$ titik pada satah, berapa banyak pasangan titik yang boleh berada pada jarak tepat $1$ antara satu sama lain?

Ini ialah masalah jarak unit satah, yang pertama kali dikemukakan oleh Paul Erdős pada tahun 1946. Ia ialah salah satu soalan paling terkenal dalam geometri kombinatorik, mudah dinyatakan dan amat sukar diselesaikan. Buku tahun 2005 Research Problems in Discrete Geometry, oleh Brass, Moser, dan Pach, menyebutnya sebagai “mungkin masalah yang paling terkenal (dan paling mudah dijelaskan) dalam geometri kombinatorik.” Noga Alon, seorang ahli kombinatorik terkemuka di Princeton, menggambarkannya sebagai “salah satu masalah kegemaran Erdős.” Erdős malah menawarkan hadiah wang untuk menyelesaikan masalah ini.

Hari ini, kami berkongsi satu penemuan besar tentang masalah jarak unit. Sejak kerja asal Erdős, kepercayaan yang dominan ialah pembinaan “grid segi empat” yang digambarkan lebih bawah pada asasnya adalah optimum untuk memaksimumkan bilangan pasangan jarak unit. Satu model dalaman OpenAI telah menyangkal konjektur yang telah lama bertahan ini, dengan menyediakan satu keluarga contoh tak terhingga yang menghasilkan penambahbaikan polinomial. Bukti itu telah diperiksa oleh sekumpulan ahli matematik luar. Mereka juga telah menulis kertas iringan yang menerangkan hujah tersebut serta memberikan latar belakang dan konteks lanjut tentang kepentingan hasil ini.

Hasil ini juga penting kerana cara ia ditemui. Bukti itu datang daripada model penaakulan tujuan umum yang baharu, bukannya daripada sistem yang dilatih khusus untuk matematik, dibina untuk mencari strategi pembuktian, atau disasarkan khusus kepada masalah jarak unit. Sebagai sebahagian daripada usaha yang lebih luas untuk menguji sama ada model lanjutan boleh menyumbang kepada penyelidikan termaju, kami menilainya pada satu koleksi masalah Erdős. Dalam kes ini, ia menghasilkan bukti yang menyelesaikan masalah terbuka itu.

Bukti ini ialah pencapaian penting bagi komuniti matematik dan AI. Ini menandakan kali pertama satu masalah terbuka yang menonjol, teras kepada satu subbidang matematik, diselesaikan secara autonomi oleh AI. Ia juga menunjukkan kedalaman penaakulan yang kini disokong oleh sistem ini. Matematik menyediakan medan ujian yang sangat jelas untuk penaakulan: masalahnya tepat, bukti yang berpotensi boleh diperiksa, dan hujah yang panjang hanya berfungsi jika penaakulan itu kekal kukuh dari awal hingga akhir. Kaedah yang digunakan untuk menyelesaikan masalah ini juga penting. Bukti itu membawa idea yang tidak dijangka dan canggih daripada teori nombor algebra untuk digunakan pada satu soalan geometri asas.

Pemenang Pingat Fields Tim Gowers, yang menulis dalam kertas iringan, menyebut hasil ini sebagai “satu pencapaian penting dalam matematik AI.” Menurut ahli teori nombor terkemuka Arul Shankar, “Pada pendapat saya kertas ini menunjukkan bahawa model AI semasa melangkaui sekadar pembantu kepada ahli matematik manusia – mereka mampu mempunyai idea asli yang bijak, dan kemudian melaksanakannya hingga berjaya”.

Bukti ini tersedia di sini⁠(dibuka dalam tetingkap baru). Kertas iringan oleh ahli matematik luar terkemuka tersedia di sini⁠(dibuka dalam tetingkap baru). Anda boleh menemui versi ringkas rantaian pemikiran model ini di sini⁠(dibuka dalam tetingkap baru).

Biarkan $u(n)$ menjadi bilangan terbesar yang mungkin bagi pasangan jarak unit dalam kalangan $n$ titik pada satah. Contoh yang mencapai kadar pertumbuhan linear mudah dibina: meletakkan $n$ titik pada satu garis memberikan $n-1$ pasangan, manakala grid segi empat memberikan kira-kira $2n$ pasangan. Pembinaan terbaik yang diketahui sebelum ini, yang datang daripada grid segi empat sama yang diskalakan semula, rupa-rupanya memberikan lebih banyak lagi: $n^{1 + C / \log \log(n)}$ bagi suatu pemalar $C$. Oleh sebab $\log \log(n)$ menuju ke tak terhingga apabila $n$ bertambah, sebutan tambahan dalam eksponen menuju ke $0$, yang bermaksud pembinaan ini mencapai pertumbuhan yang hanya sedikit lebih pantas daripada linear. Selama beberapa dekad, ia dipercayai secara meluas bahawa kadar ini pada asasnya adalah yang terbaik, dan tiada pembinaan yang boleh menambah baik secara ketara berbanding grid segi empat. Dalam istilah teknikal, Erdős mengkonjekturkan had atas $n^{1+o(1)}$ yang mana tambahan $o(1)$ menunjukkan satu sebutan yang menuju ke $0$ apabila $n$ bertambah.

Hasil baharu kami menyangkal konjektur ini. Dengan lebih tepat, bagi tak terhingga banyak nilai $n$, bukti itu membina konfigurasi $n$ titik dengan sekurang-kurangnya $n^{1+\delta}$ pasangan jarak unit, bagi suatu eksponen tetap $\delta > 0$. (Bukti AI asal tidak memberikan $\delta$ yang eksplisit, tetapi penambahbaikan akan datang oleh profesor matematik Princeton Will Sawin telah menunjukkan bahawa seseorang boleh mengambil $\delta=0.014$.)

Sejarah masalah ini membantu untuk memahami mengapa hasilnya mengejutkan. Had bawah terbaik yang diketahui pada asasnya tidak berubah sejak pembinaan asal Erdős pada tahun 1946. Had atas terbaik, $O(n^{4/3})$, berasal daripada kerja Spencer, Szemerédi, dan Trotter pada tahun 1984, dan walaupun terdapat penambahbaikan kemudian serta kerja struktur berkaitan oleh Székely, Katz dan Silier, Pach, Raz, dan Solymosi serta yang lain, had atas itu pada asasnya kekal tidak berubah. Sebagai bukti yang menyokong konjektur ini, Matoušek dan Alon-Bucić-Sauermann mengkaji masalah ini dengan jarak bukan Euclid pada satah, dan membuktikan bahawa "kebanyakan" jarak bukan Euclid ini mematuhi konjektur ini dalam suatu erti.

Yang mengejutkan, bahan utama pembinaan ini datang daripada bahagian matematik yang sangat berbeza yang dikenali sebagai teori nombor algebra, yang mengkaji konsep seperti pemfaktoran dalam peluasan integer yang dikenali sebagai medan nombor algebra.

Pada tahap tinggi, bukti itu bermula dengan idea geometri yang biasa dan menolaknya ke arah yang tidak dijangka.

Had bawah asal Erdős boleh difahami melalui integer Gaussian: nombor dalam bentuk $a+bi$, dengan $a$ dan $b$ ialah integer dan $i$ ialah punca kuasa dua bagi $-1$. Integer Gaussian meluaskan integer biasa dan, seperti integer biasa, mempunyai sifat seperti pemfaktoran unik kepada nombor perdana. Peluasan integer biasa atau nombor rasional seperti ini dikenali sebagai medan nombor algebra. Hujah baharu ini menggantikan integer Gaussian dengan pengitlakan yang lebih rumit daripada teori nombor algebra dengan simetri yang lebih kaya yang boleh menghasilkan jauh lebih banyak perbezaan panjang unit.

Hujah yang tepat menggunakan alat seperti menara medan kelas tak terhingga dan teori Golod–Shafarevich untuk menunjukkan bahawa medan nombor yang diperlukan bagi hujah itu benar-benar wujud. Idea ini memang terkenal dalam kalangan ahli teori nombor algebra, tetapi amat mengejutkan bahawa konsep ini mempunyai implikasi untuk soalan geometri pada satah Euclid.

Hasil ini menandakan detik penting dalam interaksi antara AI dan matematik: satu sistem AI telah menyelesaikan secara autonomi satu masalah terbuka yang telah lama wujud di pusat satu bidang yang aktif. Ia juga menawarkan gambaran awal tentang jenis kerjasama baharu antara AI dan ahli matematik manusia. Dalam kes ini, kerja iringan oleh ahli matematik luar memberikan gambaran yang jauh lebih kaya berbanding penyelesaian asal sahaja.

Seperti yang ditulis oleh Thomas Bloom dalam nota iringan:

“Apabila menilai kepentingan dan pengaruh sesuatu bukti yang dijana AI, satu soalan yang saya tanyakan kepada diri saya ialah: adakah ini mengajar kita sesuatu yang baharu tentang masalah ini? Adakah kita kini memahami geometri diskret dengan lebih baik? Saya fikir jawapannya ialah ya yang sederhana: ini menunjukkan bahawa pembinaan teori nombor mempunyai jauh lebih banyak untuk diperkatakan tentang soalan seperti ini daripada yang kita sangka; lebih-lebih lagi, teori nombor yang diperlukan boleh menjadi sangat mendalam. Tidak syak lagi ramai ahli teori nombor algebra akan meneliti dengan dekat masalah terbuka lain dalam geometri diskret dalam bulan-bulan akan datang.”

Hubungan yang tidak dijangka antara teori nombor algebra dan geometri diskret yang didedahkan oleh penyelesaian ini ialah sebahagian daripada apa yang menjadikan hasil ini penting. Ia bukan sekadar menyelesaikan satu konjektur tertentu, tetapi mungkin menyediakan ahli matematik dengan jambatan untuk mula meneroka masalah berkaitan yang lain.

Bloom juga menunjukkan satu kemungkinan yang lebih luas:

“Sempadan pengetahuan sangat tidak sekata, dan tidak syak lagi bulan-bulan dan tahun-tahun akan datang akan menyaksikan kejayaan serupa dalam banyak bidang matematik lain, apabila masalah terbuka yang telah lama wujud diselesaikan oleh AI yang mendedahkan hubungan tidak dijangka dan menolak jentera teknikal sedia ada ke hadnya. AI membantu kita meneroka dengan lebih menyeluruh katedral matematik yang telah kita bina selama berabad-abad; keajaiban tersembunyi lain apakah yang sedang menunggu di balik tabir?”

Hasil ini memberikan contoh yang menjanjikan: AI menyumbang bukan sahaja penyelesaian, tetapi penemuan matematik yang kepentingannya menjadi lebih jelas dan lebih kaya melalui pemahaman manusia yang menyusul.

Pengajarannya lebih besar daripada hasil khusus ini. Penaakulan matematik yang lebih baik boleh menjadikan AI rakan penyelidikan yang lebih kuat: sesuatu yang boleh mengekalkan garis pemikiran yang sukar, menghubungkan idea merentas bidang pengetahuan yang jauh, menonjolkan laluan yang menjanjikan yang mungkin tidak diutamakan oleh pakar, dan membantu penyelidik membuat kemajuan pada masalah yang jika tidak akan terlalu rumit atau memakan masa untuk ditangani.

Keupayaan itu penting melangkaui matematik. Jika model boleh mengekalkan keselarasan hujah yang rumit, menghubungkan idea merentas bidang pengetahuan yang jauh, dan menghasilkan kerja yang tahan penelitian pakar, itu juga kebolehan yang berguna dalam biologi, fizik, sains bahan, kejuruteraan, dan perubatan, dan ia adalah sebahagian daripada laluan jangka panjang kami ke arah penyelidikan yang lebih automatik: sistem yang boleh membantu saintis dan jurutera meneroka lebih banyak idea dan mengejar soalan teknikal yang lebih sukar.

AI akan mula memainkan peranan yang sangat serius dalam bahagian kreatif penyelidikan, dan yang paling penting penyelidikan AI itu sendiri. Walaupun kemajuan ini tidak dijangka, ia mengukuhkan rasa mendesak kami untuk memahami fasa seterusnya pembangunan AI ini, cabaran menyelaraskan sistem yang sangat pintar, dan masa depan kerjasama manusia-AI.

Masa depan itu masih bergantung pada pertimbangan manusia. Kepakaran menjadi lebih bernilai, bukan kurang. AI boleh membantu mencari, mencadangkan, dan mengesahkan. Manusia memilih masalah yang penting, mentafsir hasilnya, dan memutuskan soalan apa yang hendak diteruskan seterusnya.