Rekor Baru Sphere Packing Muncul dari Sumber yang Tak Terduga
(quantamagazine.org)- Dalam masalah sphere packing berdimensi tinggi, Boaz Klartag pada April mempublikasikan sebuah manuskrip singkat secara online yang memuat peningkatan efisiensi terbesar sejak Claude Ambrose Rogers pada 1947
- Metode baru ini berangkat dari lattice sembarang, membuat ellipsoid yang lebih besar, lalu membangun sphere packing yang rapat dengan prosedur Rogers, sekaligus menghidupkan kembali pendekatan geometris yang sempat tersisih
- Konstruksi Klartag dapat memuat sekitar d kali lebih banyak bola daripada banyak hasil sebelumnya pada dimensi d; kira-kira 100 kali lipat di 100 dimensi dan sekitar 1 juta kali lipat di 1 juta dimensi
- Berbeda dari diskusi tentang kemungkinan packing tak beraturan yang menguat setelah rekor non-lattice pada 2023, hasil ini menunjukkan bahwa keteraturan dan simetri mungkin masih menjadi kandidat kuat dalam packing optimal berdimensi tinggi
- Meski masalah sphere packing penting untuk aplikasi kriptografi dan komunikasi, hasil ini belum langsung dapat diterapkan, tetapi bisa menjadi momentum untuk kembali menghubungkan geometri konveks dan teori lattice
Kemajuan besar dalam sphere packing berdimensi tinggi
- Masalah sphere packing adalah masalah mencari cara mengisi ruang berdimensi tinggi dengan bola seefisien mungkin
- Masalah ini telah menarik perhatian matematikawan selama berabad-abad, dan juga memiliki potensi aplikasi penting dalam kriptografi serta komunikasi jarak jauh
- Pada awal abad ke-17, Johannes Kepler menunjukkan bahwa jika bola tiga dimensi ditumpuk seperti jeruk di toko bahan makanan, bola-bola itu dapat mengisi sekitar 74% ruang, dan ia menduga itu adalah yang optimal
- Dugaan ini baru terbukti hampir 400 tahun kemudian
- Pada dimensi yang lebih tinggi, kecuali dimensi 8 dan 24, jawaban optimalnya belum diketahui
- Matematikawan sudah lama mencari packing yang lebih baik, tetapi peningkatannya kecil dan jarang terjadi
- Dalam manuskrip singkat yang dipublikasikan pada April, Boaz Klartag melampaui rekor sebelumnya dengan selisih besar, dan sebagian peneliti menilai hasil ini mungkin mendekati optimal
Gagasan lama yang menghubungkan lattice ke ellipsoid
- Pada 1905, Hermann Minkowski membangun cara memikirkan sphere packing melalui lattice
- Caranya adalah membuat susunan titik yang berulang di ruang, lalu menggambar bola di sekitar setiap titik
- Dalam dimensi tertentu, masalah mencari sphere packing optimal berubah menjadi masalah mencari lattice dengan susunan titik paling efisien
- Di dua dimensi, lattice heksagonal adalah yang optimal
- Pada 1947, Claude Ambrose Rogers mengajukan sudut pandang lain
- Ia dapat memulai bahkan dari lattice sembarang yang tidak optimal
- Alih-alih menggambar bola di setiap titik, ia menggambar ellipsoid di sekitar satu titik, dengan permukaannya menyentuh titik lain pada lattice tetapi tidak melewatinya
- Ia menyajikan algoritme untuk membuat sphere packing yang rapat dari ellipsoid ini sebagai titik awal
- Keunggulan metode Rogers adalah lattice awal tidak perlu sangat efisien
- Selama ellipsoid yang tepat dipilih, sphere packing yang efisien dapat dibuat
- Namun ellipsoid lebih sulit ditangani daripada bola
- Bola ditentukan oleh satu jari-jari, sedangkan ellipsoid ditentukan oleh banyak sumbu dengan panjang berbeda
- Semakin tinggi dimensinya, arah yang dapat diperpanjang dan bentuk yang mungkin meningkat secara drastis
- Pada akhirnya, matematikawan kembali ke pendekatan lattice ala Minkowski, dan dengan lebih berfokus pada teori lattice mereka menjauh dari pendekatan geometris Rogers
- Strategi ini juga memperbaiki sphere packing berdimensi tinggi, tetapi sebagian besar peningkatannya lebih kecil daripada packing Rogers
Peneliti geometri konveks menghidupkan kembali pendekatan Rogers
- Klartag adalah matematikawan di Weizmann Institute of Science yang terutama meneliti geometri konveks
- Bangun konveks adalah bangun yang tidak memiliki cekungan ke dalam
- Di dimensi tinggi, bangun-bangun ini mencakup berbagai simetri, dan Klartag melihatnya sebagai alat matematika yang kuat
- Ia tertarik pada lattice dan sphere packing, tetapi belum punya waktu untuk mempelajari bidang itu secara mendalam
- Setelah menyelesaikan proyek besar pada November tahun lalu, jadwalnya menjadi kosong, lalu ia meminta Barak Weiss dari Tel Aviv University untuk membimbingnya mempelajari bidang baru
- Weiss memulai seminar kecil tempat Klartag dan beberapa orang lain membaca literatur bersama
- Klartag membaca secara rinci metode sphere packing Minkowski dan Rogers
- Setelah membaca cara Rogers mengubah ellipsoid menjadi sphere packing, Klartag bertanya-tanya mengapa matematikawan meninggalkan metode itu
- Karena ellipsoid adalah bangun konveks, Klartag memiliki berbagai cara canggih untuk memanipulasinya
- Ia menilai ellipsoid awal yang digunakan Rogers intuitif tetapi tidak efisien
- Jika ia dapat membuat ellipsoid dengan volume lebih besar, prosedur asli Rogers bisa menghasilkan rekor packing baru
Membuat ellipsoid lebih besar lewat pertumbuhan acak
- Klartag mulai dari metode yang sudah ia kenal: memperbesar dan mengecilkan batas ellipsoid di sepanjang tiap sumbu melalui proses acak
- Ketika batasnya sudah cukup mengembang hingga menyentuh titik baru pada lattice, pertumbuhan ke arah itu dihentikan
- Titik tersebut tidak akan masuk ke dalam ellipsoid
- Di arah lain, ellipsoid terus mengembang sampai menyentuh titik lain
- Dalam proses ini, ellipsoid berhenti dan bergerak seperti tersentak-sentak sambil secara bertahap menjelajahi ruang di sekitarnya
- Seiring waktu, rata-rata volume ellipsoid meningkat
- Pertanyaan kunci Klartag adalah apakah peningkatan volume ini cukup untuk melampaui ellipsoid intuitif Rogers
- Karena proses acak menghasilkan ellipsoid yang berbeda setiap kali dijalankan, Klartag mengevaluasi rentang volume ellipsoid yang mungkin
- Awalnya ia tidak menemukan satu pun ellipsoid yang cukup lebih besar daripada ellipsoid Rogers
- Setelah menyesuaikan detail proses pertumbuhan acak, dalam satu atau dua minggu ia membuktikan bahwa sesekali proses itu menghasilkan ellipsoid yang cukup besar untuk mencetak rekor baru
Makna matematis dari peningkatan sekitar d kali lipat
- Bukti Klartag telah diverifikasi, dan ketika ellipsoid awal yang baru diubah menjadi sphere packing, hasilnya memberikan peningkatan efisiensi terbesar sejak makalah Rogers tahun 1947
- Pada dimensi d tertentu, metode Klartag dapat memuat sekitar d kali lebih banyak bola daripada banyak hasil sebelumnya
- Di ruang 100 dimensi, metode ini memuat kira-kira 100 kali lebih banyak bola
- Di ruang 1 juta dimensi, metode ini memuat kira-kira 1 juta kali lebih banyak bola
- Klartag mempelajari bidang sphere packing selama beberapa bulan, menulis buktinya selama beberapa minggu, lalu membuat kemajuan besar pada salah satu masalah sentralnya
- Pengalamannya dalam geometri konveks berperan langsung dalam menerapkan teknik yang biasanya diperlakukan sebagai bidang terpisah ke masalah sphere packing
- Gil Kalai menilai hasil ini sebagai “terobosan yang benar-benar mengejutkan” dan melihatnya sebagai capaian yang terkait dengan masalah yang telah menggairahkan matematikawan selama hampir 100 tahun
Perdebatan tentang keteraturan dan ketakteraturan
- Hasil Klartag menghidupkan kembali perdebatan tentang sifat packing optimal berdimensi tinggi
- Selama beberapa waktu, matematikawan menganggap packing berbasis lattice dengan simetri tinggi sebagai cara terbaik untuk menyusun bola paling rapat
- Pada 2023, ditemukan packing yang tidak bergantung secara rapi pada lattice berulang, dan itu menjadi rekor sebelum Klartag
- Sebagian matematikawan melihatnya sebagai bukti bahwa pencarian sphere packing optimal membutuhkan lebih banyak ketakteraturan
- Pekerjaan Klartag kembali mendukung gagasan bahwa keteraturan dan simetri mungkin menjadi kandidat kuat
- Seberapa rapat sphere packing bisa dibuat masih menjadi perdebatan
- Sebagian matematikawan menilai packing Klartag sangat dekat dengan optimal
- Matematikawan lain melihat masih ada ruang untuk perbaikan
- Marcus Michelen dari University of Illinois, Chicago mengatakan bahwa saat ini ia tidak tahu harus percaya pada apa, dan semua kemungkinan masih terbuka
Koneksi lintas bidang yang lebih besar daripada aplikasi langsung
- Jawaban atas masalah sphere packing penting karena potensi aplikasinya dalam kriptografi dan komunikasi
- Or Ordentlich, ahli teori informasi di Hebrew University, mengatakan bahwa masalah ini besar bagi para insinyur tetapi kemajuannya sedikit, sehingga hasil ini memicu antusiasme
- Namun hasil Klartag belum langsung berguna untuk aplikasi semacam itu
- Klartag berharap pekerjaannya menjadi momentum untuk kembali ke cara pada era Rogers, ketika geometri konveks dan teori lattice lebih saling terhubung
- Ia menilai pemahaman saat ini tentang benda konveks dapat berguna untuk masalah lattice, melampaui sphere packing
- Tujuan Klartag adalah membuat kedua bidang itu tidak lagi seterpisah sekarang
1 komentar
Komentar Hacker News
Menjelaskan kepada orang tua bahwa pekerjaanku adalah pekerjaan sungguhan saja sudah sulit, apalagi membayangkan harus menjelaskan bahwa aku “hanya meneliti bentuk yang tidak punya bagian menonjol lalu masuk ke dalam”
Sebenarnya pilihannya cuma tiga. Kalau dijelaskan singkat dengan bahasa yang dipahami lawan bicara, pekerjaannya terlihat mudah dan mereka jadi berpikir, “Bagaimana bisa dibayar untuk ini?”
Kalau menjelaskan apa yang dilakukan dan mengapa itu penting dengan bahasa yang dipahami lawan bicara, penjelasannya jadi terlalu panjang, membosankan, dan membuat mereka menyesal sudah bertanya
Atau bisa menjelaskan singkat dengan istilah teknis yang tidak mereka pahami, sehingga membosankan tapi membuat mereka terkesan; di antara pilihan yang buruk, ini yang terbaik
Aku masih belum menemukan cara untuk menjelaskan bisnisku agar orang awam bisa memahaminya sedikit saja. Semuanya terlalu rumit dan berjarak beberapa tingkat dari kehidupan sehari-hari
Bukan berarti pasti kompleks, tetapi terlalu banyak detail yang tidak pernah akrab ditemui orang rata-rata, dan hampir tidak ada analogi sehari-hari
Untuk bangun cembung, aku kurang tahu
Gaya bicara yang terlihat terlalu mendetail bisa menjadi racun yang membuat orang menjauh
Jelaskan dari sudut pandang seperti, “Saya ingin melakukan XYZ tapi terlalu sulit sehingga membuat frustrasi, jadi saya membuat dugaan yang mudah. Memikirkan masalah ini secara kasar seperti ini lebih mudah ditangani, dan karena saya tahu ABC, saya membuat ABC. Lalu ketika menggunakannya, hasilnya lebih mendekati bekerja lebih baik daripada apa yang pernah dicoba sejauh ini, jadi saya bersemangat”
Untuk orang nonteknis, penjelasan yang memuat emosi juga cukup efektif. Mereka mungkin lebih terbiasa berpikir secara emosional, sementara kita tenggelam dalam logika pekerjaan dan kadang matematika. Jadi emosi perlu dimasukkan kembali ke dalam penjelasan
Ketika aku menjelaskannya seperti itu kepada keluarga, mereka bisa mengikuti dan benar-benar paham
Dalam artikel disebutkan bahwa “di ruang berdimensi 100, metodenya mengisi kira-kira 100 kali lebih banyak bola, dan di ruang berdimensi satu juta, kira-kira 1 juta kali lebih banyak”, dan ini contoh bagus yang menunjukkan betapa anehnya ruang berdimensi tinggi.
Artinya, ketika orang-orang pintar mencoba memasukkan sebanyak mungkin jeruk 100 dimensi ke dalam kotak 100 dimensi, sejauh ini mereka bahkan belum bisa mengisi 1% ruangnya, dan selama puluhan tahun mencari pun belum menemukan tempat untuk menambahkan satu lagi.
Jika kita membayangkan bola-n satuan yang dilingkupi kubus satuan, makin besar n, makin hilang rasio volume yang ditempati bola itu. Tambahan lagi, anehnya hubungan ini tidak monoton dan mencapai maksimum pada n=6.
Pada n=100, volume bola-100 satuan kira-kira 10^-40, dan jelas tidak mungkin memasukkan bola kedua ke dalam kubus ini. Jadi tidak terlalu mengejutkan kalau keuntungan dari peningkatan pengisian bisa menjadi sebesar itu.
Banyak orang mengatakan bisa memvisualisasikan 4 dimensi, tetapi saya belum pernah melihat orang yang benar-benar bisa. Termasuk banyak matematikawan, meski biasanya yang membuat klaim seperti itu justru bukan matematikawan.
Saya suka animasi[0] dalam tulisan Math Overflow ini, karena ada banyak kompleksitas tersembunyi yang tidak terpikirkan oleh kebanyakan orang. Animasi itu sebenarnya ilusi optik dan kita sedang melihat “halusinasi”. Gambar di atas memproyeksikan kubus ke bidang datar? Sebenarnya itu bukan kubus. Itu sudah merupakan proyeksi kubus ke 2 dimensi. Secara teknis memang 3 dimensi, tetapi dimensi ketiganya bukan dimensi ruang, melainkan dimensi waktu. Ini sendiri menjadi pelajaran bagus untuk mempelajari abstraksi dimensi.
Jadi kita berhalusinasi melihat kubus yang berputar, lalu setelah melihat proyeksinya pada bidang datar, kita kembali berhalusinasi seolah-olah itu memiliki kedalaman, bukan sekadar persegi yang tidak terpuntir. Ini sendiri sudah cukup ganjil.
Sebenarnya kita juga kesulitan melakukan imajinasi 2 dimensi. Kebanyakan orang mengklaim bisa memvisualisasikan 2 dimensi, dan klaim itu biasanya tidak terbantahkan.
Jika belum pernah membaca Flatland[1], saya ingin merekomendasikannya kepada semua orang. Banyak orang membacanya dengan keliru. Biasanya mereka membacanya sebagai analogi dengan menurunkan satu dimensi: kita sebagai makhluk 3 dimensi berpadanan dengan makhluk 2 dimensi, dan makhluk 4 dimensi akan sama membingungkannya bagi kita seperti makhluk 3 dimensi bagi Flatlander. Itu benar, tetapi ada jebakan di sana. Kita mengira memahami 2 dimensi itu sangat mudah. Namun saya berani menjamin apa yang Anda gambarkan di kepala saat ini keliru. Sejujurnya, bukunya juga tidak sepenuhnya akurat.
Kita benar-benar harus menempatkan diri pada posisi Flatlander. Bukan di dalam buku, melainkan posisi Flatlander yang sebenarnya. Jika membayangkan diri sebagai Flatlander berbentuk persegi yang melihat segitiga, apa yang akan terlihat? Anda mungkin membayangkan sebuah garis, tetapi itu keliru. Anda telah memberinya ketebalan dan memasukkan dimensi ketiga. Coba lagi, lalu tantang diri sendiri untuk menambahkan lebih banyak kedalaman dan membayangkan Flatland yang sebenarnya; Anda akan menyadari bahwa itu tidak bisa dilakukan.
Sebagai gantinya, kita bisa memvisualisasikan dan menalar ruang 2 dimensi yang tertanam di dalam 3 dimensi. Orang bisa menyebut ini mencari-cari kesalahan, tetapi kalau tidak begitu, maka menyebut ini[2,3] sebagai hiperkubus 4 dimensi, bukan representasi hiperkubus 4 dimensi, seharusnya sepenuhnya baik-baik saja.
Saya rasa memahami hal ini sangat membantu untuk memahami dimensi yang sangat tinggi. Jika kita menghadapi betapa luar biasanya sulitnya memvisualisasikan secara tepat penambahan atau pengurangan satu dimensi, kemungkinan kita menipu diri sendiri saat menalar dimensi yang jauh lebih tinggi akan berkurang.
Seperti kata Feynman, prinsip pertama adalah jangan menipu diri sendiri, dan orang yang paling mudah ditipu adalah diri sendiri.
[0] https://math.stackexchange.com/a/2286226
[1] http://www.geom.uiuc.edu/~banchoff/Flatland/
[2] [https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-s...](https://en.wikipedia.org/wiki/Tesseract#/media/File:8-cell-simple.gif)
[3] Ini video bagus Carl Sagan yang menjelaskan sambil memegang proyeksi 3 dimensi dari hiperkubus, yaitu bayangannya. Apa pun yang ditampilkan pasti tertanam di dalam 2 dimensi. Ia mengangkatnya mulai 6:20 https://www.youtube.com/watch?v=UnURElCzGc0
Menarik. Saya pernah mencoba memakai pendekatan pengisian bola selama sebulan untuk membuat algoritma kompresi yang lebih baik.
Ada banyak vektor dan semuanya dikelompokkan lewat clustering, tetapi saya menyimpulkan bahwa pendekatan teoretis hanya bekerja baik pada data seragam dan tidak terlalu cocok untuk data dunia nyata.
Misalnya, katakanlah data memiliki struktur berdimensi tinggi tetapi secara lokal seragam. Ini umum terjadi, dan muncul karena proses yang menimbulkan noise. Jika menghitung dan menyimpan titik pusat, datanya menjadi lebih seragam daripada data asli dan jumlahnya tidak banyak, jadi bagaimanapun bukan masalah besar.
Setiap vektor disimpan sebagai indeks titik pusat dan offset vektor. Dalam hal ini SoA, bukan AoS. Indeks dapat dikompresi dengan metode bilangan bulat berbasis entropi favorit Anda, dan jika urutan tidak perlu dipertahankan, bisa dilakukan lebih baik lagi.
Karena offset kini, berdasarkan asumsi, kira-kira seragam, Anda bisa memakai strategi bola favorit dari literatur.
Tentu saja, bisa juga tidak demikian jika use case nyata terlalu heterogen sehingga teknik umum tidak efektif.
Para matematikawan merasa bahwa beberapa tahun setelah doktor pertama, mereka seharusnya bisa mengambil gelar setingkat doktor kedua di bidang yang berdekatan, meski tidak persis sama dengan bidang mereka sendiri
Banyak peneliti melakukan pelatihan ulang ke bidang berdekatan atau menambah minat riset pada masa pascadoktoral atau setelahnya. Sejak titik itu, itu pada dasarnya hanyalah riset
Namun dalam lingkungan akademik modern, mencobanya tidak akan mudah
Khususnya, menghubungkan berbagai bidang dalam matematika bisa sangat kuat
Setidaknya di Jerman, ini cukup mirip dengan yang dijelaskan
Untuk dimensi d tertentu, Klartag mengatakan ia bisa mengisi d kali lebih banyak bola dibanding sebagian besar hasil sebelumnya
Artinya di 100 dimensi kira-kira 100 kali lebih banyak, dan di satu juta dimensi kira-kira satu juta kali lebih banyak bola, yang terdengar seperti angka yang luar biasa. Apakah ini berarti dalam berbagai sistem komunikasi, bandwidth bisa bertambah beberapa orde magnitudo atau konsumsi daya berkurang?
Jadi ini hanya membantu objek yang secara alami berdimensi tinggi. Objek digital tidak punya dimensi alami, yaitu panjang byte, sehingga kita bisa memilih dimensi kecil
https://en.m.wikipedia.org/wiki/Sphere_packing
Dari latar pelatihannya, Klartag memang bukan spesialis pengisian bola, tetapi ia adalah salah satu pemecah masalah terbaik yang ada
Awal tahun ini ia memecahkan Hyperplane Conjecture, dan selama ini berkontribusi pada kemajuan masalah terkait teori konveksitas seperti KLS Conjecture, Mahler Conjecture, dan teorema limit pusat untuk benda konveks
Riset muridnya, Eldan, tentang Stochastic Localization juga terbukti krusial dalam algoritma pengambilan sampel log-konkaf; ini terkait dengan KLS Conjecture dan juga dipresentasikan di ICM
Selain itu, alat-alat yang dipakai dalam geometri konveks, terutama beberapa alat analisis harmonik, juga cukup berguna dalam riset pengisian bola
Jadi sulit menyebutnya “tak terduga”
Saya setuju dengan pandangan Klartag bahwa bentuk konveks adalah alat matematika yang diremehkan. Saya bukan matematikawan, tetapi pernah melihat algoritma convex hull menyelesaikan masalah di tempat yang sama sekali tidak saya duga
Misalnya, saya tidak akan terpikir bahwa algoritma convex hull dipakai dalam makalah tentang dekomposisi palet otomatis pada gambar
https://www.rose-hulman.edu/class/cs/csse451/Papers/DILvGRB....
Pertanyaan pemula: apakah pengisian bola optimal berkorelasi dengan kisi reguler? Di 2 dan 3 dimensi bukankah begitu? Kalau begitu, apakah bisa diperluas ke n dimensi?
Ini dibuktikan oleh Maryna Viazovska pada 2017, dan untuk makalah kedua ia menulis bersama para kolaborator. https://doi.org/10.4007/annals.2017.185.3.7 https://doi.org/10.4007/annals.2017.185.3.8
Ini juga layak dijadikan rujukan: https://www.ams.org/journals/notices/201702/rnoti-p102.pdf
Untuk dimensi lain, ini masih masalah terbuka, dan secara umum tampaknya kecil kemungkinan benar. Di beberapa dimensi, pengisian nonreguler terpadat yang diketahui lebih padat daripada pengisian reguler terpadat yang diketahui
Namun semuanya memiliki kepadatan yang sama dengan kisi FCC. Pengisian seperti ini bisa dibuat dengan menggeser lapisan-lapisan horizontal FCC secara horizontal relatif satu sama lain
Di dimensi tinggi, ada dugaan bahwa pengisian terpadat akan selalu non-kisi. Alasannya, ruang seperti itu tidak memiliki simetri yang cukup
Hari ini sebelumnya ada tulisan bahwa manusia Neanderthal melakukan rendering lemak
Ada pembahasan bahwa para antropolog tidak tahu bahwa merebus sudah mungkin dilakukan bahkan sebelum penemuan tembikar, dan ada juga yang mengatakan bahwa guru sains mengetahui kemungkinan itu karena mereka melakukannya di kelas
Terakhir, alurnya membahas bahwa hal yang sama bisa ditemukan kembali di bidang yang berbeda, seperti seseorang yang meneliti glukosa menemukan kembali rumus trapesium untuk integral
Ini juga contoh lain bagaimana keahlian dari bidang lain bisa membantu
Cukup lihat satu video YouTube yang menunjukkan metode yang digunakan dalam situasi bertahan hidup. Pasti ada banyak yang serupa: https://www.youtube.com/shorts/0zun_UxO2vU
Memang saya tidak tahu konteksnya, tetapi klaim mengejutkan seperti itu tanpa sumber tidak masuk akal. Bahkan tidak lolos “tes tawa”