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