Matematikawan Temukan Cara Baru untuk ‘Mencium’ Bola

Di dimensi yang lebih tinggi, masalahnya semakin sulit.

Sudah diselesaikan dalam dimensi empatserta dalam dimensi 8 dan 24, di mana para ahli matematika telah mampu mengemas bola secara optimal ke dalam struktur kisi yang sangat simetris. Namun di semua dimensi lain, di mana terdapat lebih banyak ruang di antara bola-bola tersebut, masalahnya tetap terbuka. Para ahli matematika malah membuat perkiraan angka ciuman, menghitung batas atas dan bawah yang seringkali berjauhan. Dalam kasus ini, pertanyaannya bukan lagi apakah Anda dapat menambahkan satu bola ekstra, namun apakah Anda dapat menambahkan ratusan, ribuan, atau bahkan jutaan.

Untuk meningkatkan perkiraan ini, matematikawan biasanya mengikuti intuisi yang sama yang memberi mereka solusi dalam dimensi seperti 8 dan 24: Mereka mencari cara untuk menyusun bola sesimetris mungkin. Namun masih ada kemungkinan bahwa pengaturan terbaik akan terlihat jauh lebih aneh. “Mungkin ada struktur yang tidak memiliki simetri sama sekali,” katanya Gabriele Nebe dari RWTH Aachen University di Jerman. “Dan tidak ada cara yang baik untuk menemukannya.”

Kemudian, pada musim semi tahun 2022, seorang sarjana jurusan matematika di Massachusetts Institute of Technology bernama Anqi Li memutuskan untuk mencari struktur yang lebih aneh itu. Saat mengerjakan proyek kelas, dia mendapatkan ide sederhana yang kini memungkinkan dia dan profesornya, Henry Cohnke meningkatkan perkiraan jumlah ciuman dalam kelompok dimensi yang sangat menantang: 17 hingga 21. Pekerjaan ini menandai kemajuan pertama dalam mengatasi masalah dalam dimensi tersebut sejak tahun 1960an — dan menunjukkan manfaat dari memasukkan lebih banyak kekacauan ke dalam solusi potensial.

“Biasanya, Anda bekerja dengan kisi simetris yang sangat kuat,” kata Oleg Musin dari Universitas Texas, Rio Grande Valley, yang membuktikan angka ciuman optimal di dimensi empat pada tahun 2003. “Apa yang mereka usulkan adalah sesuatu yang berbeda.”

Faktanya, pembuktian mereka adalah yang terbaru dari serangkaian hasil pengepakan bola yang hanya mungkin terjadi karena para ahli matematika menyimpang dari pendekatan konvensional. “Segala sesuatunya terhenti karena masalah ciuman, tapi itu bukan karena kami menyatu pada kebenaran,” kata Cohn. “Kami baru saja terjebak.” Ternyata, untuk melepaskan diri, mereka harus melanggar beberapa aturan tak terucapkan.

Dari Kode hingga Ciuman

Sejak pertengahan abad ke-20, matematikawan mengandalkan matematika teori informasi dan koreksi kesalahan untuk membuat kemajuan dalam permasalahan yang berkaitan dengan penataan bola.

Kode koreksi kesalahan memungkinkan Anda mengirim pesan yang dapat dimengerti oleh penerima meskipun ada bagian pesan yang terdistorsi atau rusak selama transmisi. Kode ini pada dasarnya terdiri dari sekumpulan “kata kode” – kamus kemungkinan pesan – yang dapat digunakan penerima sebagai kunci untuk memulihkan pesan asli. Kata-kata kode ini perlu dipilih dengan hati-hati: Kata-kata tersebut harus cukup jelas agar penerima dapat mengetahui kata kode mana yang akan digunakan ketika memperbaiki kesalahan.

Matematikawan sering memvisualisasikan masalah ini dalam bentuk bidang. Anda dapat menganggap setiap kata kode sebagai titik berdimensi tinggi di pusat sebuah bola. Jika pesan berisi kesalahan (ketika direpresentasikan sebagai titik berdimensi tinggi) berada di dalam bola tertentu, Anda tahu bahwa kata kode di pusat bola adalah pesan yang dimaksud. Anda tidak ingin bidang ini tumpang tindih — jika tidak, pesan yang diterima mungkin diinterpretasikan lebih dari satu cara. Namun jarak kedua bola juga tidak boleh terlalu jauh. Mengemas bola dengan rapat berarti Anda dapat berkomunikasi dengan lebih efisien.

Kode yang lebih baik menghasilkan pengepakan bola yang lebih baik, dan sebaliknya. Pada tahun 1967, misalnya, ahli matematika John Leech menggunakan kode yang sangat efisien – yang kemudian terkenal digunakan oleh NASA untuk berkomunikasi dengan wahana Voyager – untuk membangun kisi titik yang sekarang menyandang namanya. Lima puluh tahun kemudian, Cohn dan beberapa ahli matematika lainnya membuktikan bahwa Anda dapat menggunakan kisi ini bungkus bola sepadat mungkin ke dalam ruang 24 dimensi. Kisi-kisi tersebut juga memberikan pengaturan ciuman terbaik: Setiap bola menyentuh 196.560 tetangga. “Kisi Lintah adalah keajaiban matematika, bagaimana segala sesuatunya bisa menyatu,” kata Cohn.

Kisi tersebut juga memberikan perkiraan terbaik bagi para ahli matematika mengenai angka ciuman dalam dimensi 17 hingga 23. Mereka hanya mengambil irisan kisi untuk mendapatkan kisi berdimensi lebih rendah, sama seperti Anda dapat mengiris bola 3D untuk mendapatkan lingkaran 2D.

Tapi ini juga berarti bahwa kisi-kisi Lintah “memberikan bayangan besar” pada masalah ciuman di dimensi tersebut, kata Cohn. Tidak peduli seberapa keras para ahli matematika mencoba, mereka tidak dapat menemukan struktur yang memberikan perkiraan yang lebih baik – meskipun mereka curiga bahwa mengambil potongan kisi Lintah bukanlah jalan yang tepat untuk mendapatkan solusi.

Menjadi Nakal

Li awalnya tidak mencari jalan baru ketika dia mulai mengerjakan proyeknya pada tahun 2022. Awalnya, Cohn menyarankan agar dia fokus pada masalah ciuman dalam dimensi yang lebih tinggi dari 24. Dalam dimensi tersebut, perkiraan angka ciuman terbaik saat ini jauh lebih kasar. Memperbaikinya sering kali berujung pada kemajuan komputasi dibandingkan menemukan pendekatan baru yang kreatif. Cohn mengenal siswa lain yang telah membuat kemajuan dalam kasus-kasus berdimensi lebih tinggi dengan menggunakan metode berbasis komputer. Dia pikir Li juga bisa.

Namun dia merasa pekerjaan itu membuat frustrasi. “Saya merasakan firasat buruk bahwa tangan saya terikat,” katanya. “Mustahil untuk membayangkannya.” Jadi sebaliknya, dia menjadi sedikit nakal.

Dia mengarahkan pandangannya pada dimensi 17 hingga 23. “Saya mengatakan kepadanya bahwa dia masih bisa mendapat nilai A jika dia menjajaki kemungkinan perbaikan dan tidak ada yang berhasil,” kenang Cohn. Seandainya dia salah satu mahasiswa pascasarjananya, dia akan berusaha lebih keras meyakinkannya untuk mengerjakan hal lain. “Jika mereka mengerjakan sesuatu yang sia-sia, itu akan berdampak buruk bagi karier mereka,” katanya.

Namun hasil dari usahanya, tambahnya, “ternyata jauh lebih menarik.”

Dia memulai dengan melihat dimensi 16. Di sana, pengaturan ciuman terbaik berasal dari “kisi Barnes-Wall,” yang ditemukan pada tahun 1950-an menggunakan kode koreksi kesalahan yang elegan. (Ternyata itu juga merupakan bagian dari kisi Lintah, yang tidak akan ditemukan selama satu dekade berikutnya.)

Kode tersebut hanya terdiri dari dua jenis titik berbeda, yang masing-masing memenuhi pola koordinat tertentu.

Cara titik-titik ini didefinisikan mengarah pada sebuah kekhasan: Dalam kisi Barnes-Wall (dan semua irisan kisi Lintah berdimensi lebih tinggi), jenis titik atau pusat bola yang paling umum, selalu memiliki jumlah tanda minus yang genap. koordinatnya. Hal ini membantu memastikan adanya jarak yang cukup antar titik, dan menghasilkan struktur simetris yang sangat mudah untuk dikerjakan.

Tapi, pikir Li, bagaimana jika dia menggunakan tanda ganjil pada titik-titik itu? Jika dia berhati-hati, itu tidak akan menyebabkan bidang yang tumpang tindih. Sepengetahuannya, tidak ada seorang pun yang pernah mencobanya sebelumnya. “Saya rasa tidak ada satu pun dari kami yang menganggap hal itu penting,” kata Cohn. Tapi Li curiga ada kemungkinan, dengan mengubah beberapa titik pada kisi dengan cara ini, dia mungkin bisa mendistorsinya secukupnya untuk menampung lebih banyak bola.

Saat dia membuat kisi Barnes-Wall versi “aneh” di dimensi 16, tidak ada ruang untuk bola tambahan, meski tidak memperburuk keadaan. Namun ketika dia merekatkan salinannya menjadi beberapa lapisan untuk membuat struktur 17 dimensi, jelas ada celah di mana titik-titik baru dapat ditambahkan — lubang di mana, ketika dia menghitung jarak ke bola yang ada dalam struktur, terlihat jelas bahwa itu adalah bola baru. bisa muat. Awalnya, dia tidak percaya. Dia merasa tidak nyaman, tidak gembira. “Saya ingat memberi tahu teman-teman saya, saya yakin saya melakukan kesalahan aritmatika dasar,” katanya.

Cohn menuruti sikap skeptisnya pada awalnya – sangat mudah untuk membuat sedikit kesalahan dalam perhitungan semacam ini, terutama ketika angan-angan mungkin terlibat. Jadi mereka memeriksa susunan titik barunya di komputer. Berhasil: Semua bola terpasang dengan benar.

Musim panas itu, Li bekerja dengan Cohn sebagai pekerja magang di Microsoft Research, di mana pasangan tersebut dengan hati-hati menyempurnakan kode koreksi kesalahan yang mereka gunakan sehingga mereka dapat terus menambahkan bola yang kompatibel ke struktur 17 dimensi “aneh” Li. Pada akhirnya, mereka mampu menambahkan 384 bola baru ke dalam perkiraan berdasarkan Leech pada tahun 1967, sehingga batas bawah jumlah ciuman menjadi 5.730.

Mereka kemudian menerapkan teknik serupa untuk meningkatkan angka ciuman di dimensi 18 hingga 21. Namun di dimensi 22 dan 23, strategi mereka gagal. Tampaknya mereka sudah kehabisan tenaga dalam pendekatan membalik tanda.

Pasangan itu konfigurasi baru kemungkinan besar tidak optimal. Dalam dimensi 17, misalnya, perkiraan batas atas adalah 10.978; Meskipun hal ini dianggap terlalu berlebihan terhadap solusi sebenarnya, hal ini menunjukkan bahwa masih ada ruang yang signifikan untuk meningkatkan batas bawah.

Namun para ahli matematika lebih tertarik pada bagaimana Cohn dan Li memperoleh hasil tersebut. Struktur baru mereka terlihat sangat berbeda dari struktur simetris tinggi yang terinspirasi oleh kisi Lintah. Metode berbasis kode yang mereka gunakan untuk menambahkan bola memberi mereka konfigurasi yang lebih tidak beraturan — sesuatu yang benar-benar baru.

Sebuah Jalan Baru ke Depan

Tidak jelas mengapa mengubah rambu akan menciptakan ruang yang cukup untuk lebih banyak bola. Memang benar. “Saya masih terkesima dengan hal itu sekarang,” kata Cohn. Namun penelitian ini menunjukkan bagaimana “perubahan yang tampaknya tidak signifikan membuka atau menutup kemungkinan,” tambahnya. Dalam hal ini, hal ini mengungkapkan betapa sedikitnya pengetahuan ahli matematika tentang masalah ciuman.

Saat membuat kode koreksi kesalahan dan pengepakan bola baru, matematikawan umumnya mengandalkan simetri. Itulah yang dilakukan Lintah. Hal ini membuat proses konstruksi lebih mudah dan intuitif. Namun hal ini juga dapat menutup kemungkinan-kemungkinan, sehingga sulit untuk melihat lebih jauh dari solusi bagus untuk struktur lain – struktur yang mungkin memiliki lebih banyak ketidakteraturan atau melibatkan bentuk simetri yang kurang intuitif. “Mungkin kita tidak mendekati kebenaran karena tidak ada penjelasan yang dapat dipahami secara manusiawi,” kata Cohn.

Beberapa hasil terbaru mendukung janji akan kemungkinan-kemungkinan yang kurang dapat diakses ini. Dalam beberapa tahun terakhir, para ahli matematika telah menemukan jawabannya konstruksi baru yang cerdas dalam dimensi 5, 10 dan 11 dengan membengkokkan atau melanggar aturan simetri biasa.

Cohn sangat kagum dengan hasil karya Ferenc Szöllősiseorang matematikawan Hongaria yang dengan sengaja memulai dengan susunan bola suboptimal dalam dimensi empat dan mengembangkannya cocok dengan perkiraan terbaik yang ada di dimensi lima. Selama beberapa dekade, ada dua struktur yang menghasilkan perkiraan tersebut; kebanyakan ahli matematika mengira tidak mungkin ada yang lain. Tiba-tiba di sini ada Szöllősi dengan orang ketiga. “Ini membuktikan bahwa Anda bisa saja terkejut,” kata Cohn, yang kemudian terinspirasi untuk bekerja sama dengan salah satu muridnya temukan yang keempat.

Setiap struktur tidak biasa yang mereka temukan memberi mereka “sedikit petunjuk tentang apa yang sebenarnya terjadi,” tambahnya. “Masalah ciuman masih penuh misteri.”