聞樂(lè) 發(fā)自 凹非寺
量子位 | 公眾號(hào) QbitAI
一位“門外漢”閑來(lái)無(wú)事學(xué)了幾個(gè)月的新理論,居然找到了百年難題的最優(yōu)解。
用的還是已經(jīng)被淘汰的老方法。
不得不說(shuō),buff有點(diǎn)多(doge)。
這位“門外漢”Boaz Klartag破解的問(wèn)題是高維空間球體堆積,顧名思義,是探究如何在給定的高維空間中盡可能多地填充球體。
給定一個(gè)d維空間,用Klartag的方法進(jìn)行堆積,數(shù)量可擴(kuò)大至先前紀(jì)錄的d倍。
也就是說(shuō),在100維空間中,可以堆積球體的數(shù)量大約為先前數(shù)量的100倍;在百萬(wàn)維空間中,可以堆積大約100萬(wàn)倍的球體。
這是自羅杰斯在1947年發(fā)表論文以來(lái),在球體堆積效率方面最具實(shí)質(zhì)性的改進(jìn)。
而且他使用的方法,還是早就被主流數(shù)學(xué)家們拋棄的羅杰斯的“橢球體起始”方法。
其研究結(jié)果對(duì)于實(shí)際應(yīng)用領(lǐng)域也有重要意義,能為無(wú)線通信領(lǐng)域效果提升帶來(lái)新思路。
數(shù)十年的微小進(jìn)展
早在17世紀(jì)初,物理學(xué)家開普勒就提出,通過(guò)像雜貨店堆放橙子那樣堆疊三維球體,可以填充大約74%的空間,并猜測(cè)這是最佳排列方式。
然而,這一猜想的證明卻耗費(fèi)了數(shù)學(xué)家們將近400年時(shí)間。
對(duì)于空間球體堆積這一問(wèn)題,數(shù)學(xué)家赫爾曼·閔可夫斯基(Hermann Minkowski)在1905年提出了一種直觀的思維方式:
在空間中重復(fù)排列的點(diǎn)的周圍繪制球體,這些點(diǎn)被稱為格點(diǎn),這樣可以將尋找球體堆積問(wèn)題最優(yōu)解轉(zhuǎn)化為尋找排列最有效的格點(diǎn)的問(wèn)題。
例如,在二維空間中,最佳的格點(diǎn)是“六邊形”,那么產(chǎn)生的堆積看起來(lái)就像這樣:
羅杰斯1947年提供了一種不同的視角:
可以從任何晶格開始——即使是次優(yōu)的晶格,與其在每個(gè)點(diǎn)周圍畫一個(gè)球體,不如在一個(gè)點(diǎn)周圍畫一個(gè)稱為橢圓體的類似長(zhǎng)方體的結(jié)構(gòu),這樣它的表面會(huì)接觸但不會(huì)超出晶格中的其他點(diǎn)。
最后,把這些橢球體“擠壓”成標(biāo)準(zhǔn)球體。二維空間示意圖如下。
羅杰斯還提出了一種算法,可以利用這個(gè)橢球體作為起點(diǎn)來(lái)構(gòu)建密集的球體堆積。
該方法的優(yōu)勢(shì)在于,即使起始點(diǎn)的晶格效率不高,也能得到高效的球體堆積,關(guān)鍵在于選擇正確的橢球體
然而,這也增加了新的復(fù)雜性:與僅由半徑定義的球體不同,橢球體由多個(gè)不同長(zhǎng)度的軸定義,維度越高,可拉伸的方向越多,橢球體的起始形狀選擇也越多。
于是,數(shù)學(xué)家們逐漸放棄了羅杰斯的方法,回歸到閔可夫斯基的方法,專注于尋找最優(yōu)的晶格。
多年來(lái),盡管高維球體堆積的方法有所改進(jìn),但這些進(jìn)展都微乎其微。
除了維度8(2016年的E8格堆積方法)和24(2017年的利奇格堆積方法)之外,在更高維度中,數(shù)學(xué)家們至今仍未能確定最佳答案。
這種停滯狀態(tài)持續(xù)了幾十年,直到Klartag這位專注于研究凸形狀而不是高維球體的“局外人”的出現(xiàn)。
將凸形狀遷移到球體堆積
Boaz Klartag是魏茨曼科學(xué)研究所的數(shù)學(xué)家,說(shuō)是門外漢,主要是因?yàn)樗闹饕芯款I(lǐng)域是幾何學(xué)
去年11月,在完成一個(gè)重要項(xiàng)目后,他利用難得的空閑時(shí)間,開始學(xué)習(xí)晶格理論。
當(dāng)他讀到羅杰斯將橢球體變成球體堆積的技巧時(shí),他想知道為什么數(shù)學(xué)家們放棄了這種方法——
橢球體是凸形,所以Klartag知道如何操縱它們!
他還意識(shí)到羅杰斯使用的初始橢球體雖然直觀但效率低下,他說(shuō):
在高維度里,你根本不知道該怎么去擴(kuò)展它。自由度太高了。
Klartag認(rèn)為,只需要構(gòu)造一個(gè)更好的橢球體
一個(gè)在其邊界與晶格中的其他點(diǎn)接觸之前能夠覆蓋更多空間的橢球體,這樣他就能創(chuàng)造新的堆積記錄。
于是,他開始改進(jìn)早就被主流數(shù)學(xué)家們放棄的羅杰斯 (Claude Ambrose Rogers)的“橢球起始方法”
他采用了一種他很熟悉的方法,通過(guò)隨機(jī)過(guò)程沿各個(gè)軸生長(zhǎng)和收縮橢球體邊界。
每當(dāng)邊界擴(kuò)展到足以接觸晶格中的新的點(diǎn)時(shí),他就會(huì)凍結(jié)橢球體在該方向上的生長(zhǎng),從而確保該點(diǎn)永遠(yuǎn)不會(huì)落入橢球體內(nèi)部。
但橢球體可以在所有其他方向上繼續(xù)膨脹,直到撞到另一個(gè)點(diǎn)。
通過(guò)這種方式,橢球體的形狀會(huì)以不規(guī)則的方式改變,逐漸探索周圍的空間,最終其邊界會(huì)觸及足夠的點(diǎn),從而阻止橢球體進(jìn)一步生長(zhǎng)。
為了方便理解,下面展示了二維空間的示意圖。
隨著時(shí)間的推移,這項(xiàng)技術(shù)平均而言會(huì)使橢球體的體積增大。
但它是否能夠增大到足以超越羅杰斯直觀的橢球體呢?
由于Klartag的過(guò)程是隨機(jī)的,每次實(shí)施都會(huì)產(chǎn)生不同的橢球體。于是,他評(píng)估了這些橢球體可能達(dá)到的體積范圍,調(diào)整了橢球體隨機(jī)生長(zhǎng)過(guò)程的細(xì)節(jié)。
就這樣,他找到了比羅杰斯幾十年前使用的橢球體體積更大的橢球體。
這樣,他就證明了,至少在某些情況下,這個(gè)方法會(huì)產(chǎn)生足夠大的橢球體來(lái)刷新堆積紀(jì)錄。
在今年4月,他公開了相關(guān)工作。
在完成這項(xiàng)工作后,Klartag表示還將繼續(xù)探索凸形狀與晶格之間的聯(lián)系:
我的目標(biāo)是讓這兩個(gè)領(lǐng)域不像現(xiàn)在這樣脫節(jié)。
Klartag的結(jié)果也重新點(diǎn)燃了關(guān)于任意高維度中最優(yōu)堆積方法的辯論。
長(zhǎng)期以來(lái),數(shù)學(xué)家們認(rèn)為高度對(duì)稱、基于晶格的堆積是盡可能密集排列球體的最佳方式。
然而,在2023年,一個(gè)團(tuán)隊(duì)發(fā)現(xiàn)了一種不完全依賴于重復(fù)晶格的堆積方式,這是在Klartag的結(jié)果出現(xiàn)之前的記錄,一些數(shù)學(xué)家認(rèn)為這證明了在尋找最佳球體堆積時(shí)需要更多的無(wú)序性。
現(xiàn)在,Klartag的結(jié)果支持了有序(Klartag方法實(shí)際上是基于概率分布)和對(duì)稱性可能才是最終方向的觀點(diǎn)。
但仍有一些數(shù)學(xué)家還在討論是否存在更優(yōu)方法。
此外,在無(wú)線通信中,信號(hào)可看作高維空間中的 “點(diǎn)”,而噪聲則像包裹這些點(diǎn)的 “球體”。
為避免信號(hào)混淆(即不同信號(hào)點(diǎn)被噪聲球覆蓋),需要將信號(hào)點(diǎn)在高維空間中盡可能密集且不重疊地排列——這在本質(zhì)上就是球體填充問(wèn)題。
可以說(shuō),球體填充問(wèn)題的進(jìn)展可以給無(wú)線通信領(lǐng)域效果提升帶來(lái)新的思路。
論文地址:https://www.weizmann.ac.il/math/klartag/sites/math.klartag/files/uploads/oranges.pdf
https://www.quantamagazine.org/new-sphere-packing-record-stems-from-an-unexpected-source-20250707/
— 完 —
特別聲明:以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺(tái)“網(wǎng)易號(hào)”用戶上傳并發(fā)布,本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.