他47歲轉(zhuǎn)方向，一舉解決了球體堆積領(lǐng)域內(nèi)最大的未解問題

選自quantamagazine

作者：Joseph Howlett

機(jī)器之心編譯

編輯：澤南

在數(shù)學(xué)領(lǐng)域里，對(duì)于最優(yōu)模式的探索永無止境，球體填充問題也不例外，它旨在盡可能高效地將球體塞進(jìn)一個(gè)（高維）盒子里。幾個(gè)世紀(jì)以來，它一直吸引著數(shù)學(xué)家們，并在密碼學(xué)、遠(yuǎn)程通信等領(lǐng)域有著重要的應(yīng)用。

它看似簡(jiǎn)單，實(shí)則微妙。17 世紀(jì)初，天文學(xué)家、數(shù)學(xué)家約翰內(nèi)斯?開普勒證明：像在雜貨店堆放橙子一樣堆放三維球體，可以填滿大約 74% 的空間。他推測(cè)這是最佳的排列方式。但數(shù)學(xué)家們花了近 400 年的時(shí)間才證明這一點(diǎn)。

在更高維度上，數(shù)學(xué)家們?nèi)匀徊恢烂鞔_的答案（除了 8 維和 24 維這兩個(gè)奇怪的例外）。多年來，他們提出了更好的填充方法。但這些改進(jìn)規(guī)模很小，而且相對(duì)罕見。

如今，數(shù)學(xué)家 Boaz Klartag 在四月份發(fā)表的一篇論文《Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid》中，新方法以顯著優(yōu)勢(shì)打破了之前的記錄。一些研究人員甚至認(rèn)為，他的結(jié)果可能接近最優(yōu)解。

論文地址：https://arxiv.org/pdf/2504.05042

作為該研究領(lǐng)域的新人，Klartag 通過復(fù)興一種專家們幾十年前就已放棄的古老技術(shù)，實(shí)現(xiàn)了他的堆積方法 —— 該方法適用于所有任意高維空間。這項(xiàng)工作觸及了關(guān)于高維空間最優(yōu)堆積性質(zhì)的幾個(gè)長期爭(zhēng)論。它們應(yīng)該是有序的還是無序的？它們究竟能堆積到什么程度？

「這真是一個(gè)了不起的突破，」耶路撒冷希伯來大學(xué)的數(shù)學(xué)家 Gil Kalai 說道。「它是能讓近 100 年數(shù)學(xué)家興奮起來的成果。」

一個(gè)領(lǐng)域，兩種方向

1905 年，德國數(shù)學(xué)家赫爾曼?閔可夫斯基（Hermann Minkowski）建立了一種直觀的方法來思考堆積球體。首先，我們先從空間中重復(fù)排列的點(diǎn)開始，稱為「格」（lattice）然后圍繞每個(gè)點(diǎn)畫一個(gè)球體。這樣，在給定維度中尋找最優(yōu)球體堆積的問題實(shí)際上變成了尋找一個(gè)點(diǎn)排列盡可能高效的格子的問題。例如，在二維空間中，最優(yōu)格子是「六邊形」，其堆積形式如下：

看起來很符合直覺？但是在 1947 年，一位名叫克勞德?安布羅斯?羅杰斯（Claude Ambrose Rogers）的數(shù)學(xué)家提出了不同的觀點(diǎn)。他認(rèn)為，可以從任何格開始 —— 即使是次優(yōu)的位置。與其在每個(gè)點(diǎn)周圍畫一個(gè)球體，不如在一個(gè)點(diǎn)周圍畫一個(gè)橢圓形，稱為橢圓體，這樣橢圓體的表面會(huì)接觸但不會(huì)超出格中的其他點(diǎn)。羅杰斯提出了一種算法，以這個(gè)橢圓體為起點(diǎn)，構(gòu)建一個(gè)致密的球體堆積。

它的工作原理如下：

羅杰斯方法的優(yōu)勢(shì)在于，你無需從特別高效的格子開始就能獲得高效的球體堆積。你只需選擇合適的橢球體即可，但這帶來了新的復(fù)雜性。與完全由一個(gè)數(shù)字（半徑）定義的球體不同，橢球體由多個(gè)不同長度的軸定義。維度越高，可以拉伸橢球體的方向就越多，起始橢球體形狀的選擇就越多。

「在高維空間中，你不知道該如何擴(kuò)展它，擁有太多自由度了。」Klartag 說道。

數(shù)學(xué)家們最終回歸了閔可夫斯基的方法，選擇專注于尋找合適的格子。他們更加專注于格子理論，而不再像羅杰斯那樣專注于幾何學(xué)。

這種策略帶來了高維球體堆積的改進(jìn)。但在大多數(shù)情況下，它們只是在羅杰斯的堆積方法上取得了相對(duì)較小的進(jìn)步。數(shù)學(xué)家們?nèi)匀黄谂沃蟮娘w躍。幾十年來，他們一直未能如愿。只有一位局外人才能打破這種停滯的狀態(tài)。

局外視角

Klartag 是以色列魏茨曼科學(xué)研究所的數(shù)學(xué)家，他一直對(duì)格子和球體堆積很感興趣。不過，Klartag 一直沒時(shí)間對(duì)其進(jìn)行深入研究，他原本的研究領(lǐng)域是幾何，擅長的研究領(lǐng)域是凸形。這些形狀包含各種對(duì)稱性，尤其是在高維度上。Klartag 堅(jiān)信，這使得它們極其強(qiáng)大：他認(rèn)為，凸形是被低估的數(shù)學(xué)工具。

博阿茲?克拉塔格（Boaz Klartag）長期以來一直認(rèn)為凸幾何領(lǐng)域的方法可能有助于解決球體堆積問題。他只是一直沒時(shí)間去驗(yàn)證自己的猜測(cè) —— 直到現(xiàn)在。

去年 11 月，在他完成了自己慣常研究領(lǐng)域的一個(gè)重要項(xiàng)目后，發(fā)現(xiàn)自己的日程安排出乎預(yù)料的空。「我想，我已經(jīng) 47 歲了，我這輩子都想研究格子，如果現(xiàn)在不做，就永遠(yuǎn)也做不成了，」他說。他請(qǐng)?zhí)乩S夫大學(xué)的朋友 Barak Weiss 指導(dǎo)他進(jìn)行這項(xiàng)新嘗試。

Weiss 和 Klartag 以及其他幾個(gè)人一起開了一個(gè)小型研討會(huì)，研究相關(guān)文獻(xiàn)。Klartag 的作業(yè)包括仔細(xì)閱讀閔可夫斯基和羅杰斯的球體堆積方法。

當(dāng)他讀到羅杰斯將橢球體變成球體堆積的技巧時(shí)，他想知道為什么數(shù)學(xué)家們放棄了這種方法。橢球體是凸形，所以 Klartag 知道很多復(fù)雜的方法來操作它們。他還意識(shí)到，羅杰斯使用的初始橢球體雖然直觀，但效率低下。他只需構(gòu)造一個(gè)更好的橢球體 —— 一個(gè)在邊界與格中的其他點(diǎn)接觸之前能夠覆蓋更大空間的橢球體 —— 就能創(chuàng)造新的填充記錄。

他首先采用了一種自己熟知的方法，即根據(jù)隨機(jī)過程沿橢球體的每個(gè)軸擴(kuò)展和收縮其邊界。每當(dāng)邊界擴(kuò)展至足以觸及格中的新點(diǎn)時(shí)，他就凍結(jié)橢球體在該方向上的生長。這確保了該點(diǎn)永遠(yuǎn)不會(huì)落入橢球體內(nèi)部。但橢球體的形狀會(huì)繼續(xù)向其他方向膨脹，直到碰到另一個(gè)點(diǎn)。就這樣，橢球體會(huì)以急促、猶豫的運(yùn)動(dòng)改變形狀，逐漸「探索」周圍的空間。最終，邊界會(huì)碰到足夠多的點(diǎn)，阻止橢球體進(jìn)一步生長。

隨著時(shí)間的推移，平均而言，這項(xiàng)技術(shù)會(huì)使橢球體的體積增加。但它是否增加到足以超越羅杰斯直觀的橢球體呢？

由于 Klartag 的方法是隨機(jī)的，因此每次實(shí)施都會(huì)產(chǎn)生不同的橢球體。他評(píng)估了這些橢球體可能擁有的體積范圍。如果他能找到一個(gè)體積比羅杰斯幾十年前使用的橢球更大的橢球，他就能用羅杰斯最初的方法把它變成更緊密的球體堆積。

但 Klartag 找不到一個(gè)足夠大的橢球，于是他調(diào)整了隨機(jī)生長過程的細(xì)節(jié)。僅僅一兩周后，他就證明了，至少在某些時(shí)候，這個(gè)過程會(huì)產(chǎn)生足夠大的橢球，足以創(chuàng)下新的紀(jì)錄。

他立即將結(jié)果告知了 Weiss。「我們下周見面吧，我會(huì)告訴你我之前是怎么搞錯(cuò)的，」Klartag 告訴他的導(dǎo)師。此時(shí)，Klartag 對(duì)自己的證明已經(jīng)更加自信了。

接近真相

新的證明已獲驗(yàn)證。Klartag 新的起始橢球體在轉(zhuǎn)化為球體堆積后，其堆積效率實(shí)現(xiàn)了自羅杰斯 1947 年論文以來最顯著的提升。對(duì)于給定的維度 d，Klartag 可以堆積的球體數(shù)量是大多數(shù)先前結(jié)果所能堆積球體的 d 倍。也就是說，在 100 維空間中，他的方法可以堆積大約 100 倍的球體；在百萬維空間中，可以堆積大約 100 萬倍的球體

Klartag 僅用幾個(gè)月的研究和幾周的證明就破解了格和球體堆積領(lǐng)域的一個(gè)核心難題。「這感覺簡(jiǎn)直是不公平，」Klartag 說道。但數(shù)學(xué)通常就是這樣運(yùn)作的：有時(shí)一個(gè)棘手的問題只需要一些新的想法，而嘗試自己領(lǐng)域之外的研究可能會(huì)帶來回報(bào)。Klartag 對(duì)凸幾何（通常是另一個(gè)研究領(lǐng)域）的熟悉，恰恰是這個(gè)問題所需要的。「由于我的工作，這個(gè)想法一直縈繞在我的腦海中，」他說。「對(duì)我來說，這顯然是可以嘗試的。」

他的成果也重新引發(fā)了該領(lǐng)域關(guān)于任意高維空間中最優(yōu)堆積性質(zhì)的爭(zhēng)論。數(shù)學(xué)家們?cè)欢日J(rèn)為高度對(duì)稱、基于格的堆積是盡可能密集地排列球體的最佳方式。但在 2023 年，一個(gè)團(tuán)隊(duì)發(fā)現(xiàn)了一種不完全依賴于重復(fù)格子的堆積方式；在 Klartag 的研究結(jié)果之前，這是一項(xiàng)難以打破的紀(jì)錄。一些數(shù)學(xué)家認(rèn)為，這表明在尋找最優(yōu)球體堆積時(shí)，需要更多的無序性。

現(xiàn)在，Klartag 的工作支持了這樣一種觀點(diǎn)：有序和對(duì)稱或許才是最終的出路。

此外，關(guān)于球體堆積究竟能達(dá)到多高的密度，一直存在爭(zhēng)議。一些數(shù)學(xué)家認(rèn)為 Klartag 的堆積方式距離最優(yōu)值只有一步之遙 —— 實(shí)際上已經(jīng)盡可能接近了。其他人則認(rèn)為仍有改進(jìn)的空間。「我現(xiàn)在真的不知道該相信什么，」伊利諾伊大學(xué)芝加哥分校的 Marcus Michelen 說道。「我認(rèn)為所有現(xiàn)實(shí)情況都尚待確定。」

這個(gè)問題的答案對(duì)于密碼學(xué)和通信領(lǐng)域的潛在應(yīng)用至關(guān)重要。因此，Klartag 的成果雖然對(duì)這些應(yīng)用目前尚無立竿見影的效果，但卻激發(fā)了一些初步的熱情。「這個(gè)問題對(duì)工程師來說非常嚴(yán)峻，而且近年來進(jìn)展甚微，」希伯來大學(xué)的信息理論家 Or Ordentlich 說道。「所以這讓我們感到興奮。」

Klartag 則希望他的工作能夠引領(lǐng)人們回歸羅杰斯時(shí)代的實(shí)踐，那時(shí)凸幾何和格理論領(lǐng)域的聯(lián)系更為緊密。「我認(rèn)為我們現(xiàn)在對(duì)凸體的理解應(yīng)該對(duì)格理論有用，甚至超越了堆積理論，」他表示。「我的目標(biāo)是讓這兩個(gè)領(lǐng)域之間的聯(lián)系比現(xiàn)在更加緊密…… 這是我的計(jì)劃，我仍然想繼續(xù)走下去。」

參考內(nèi)容：

https://www.quantamagazine.org/new-sphere-packing-record-stems-from-an-unexpected-source-20250707/