聞樂(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/

— 完 —