選自quantamagazine
作者:Joseph Howlett
機器之心編譯
編輯:澤南
在數學領域里,對于最優模式的探索永無止境,球體填充問題也不例外,它旨在盡可能高效地將球體塞進一個(高維)盒子里。幾個世紀以來,它一直吸引著數學家們,并在密碼學、遠程通信等領域有著重要的應用。
它看似簡單,實則微妙。17 世紀初,天文學家、數學家約翰內斯?開普勒證明:像在雜貨店堆放橙子一樣堆放三維球體,可以填滿大約 74% 的空間。他推測這是最佳的排列方式。但數學家們花了近 400 年的時間才證明這一點。
在更高維度上,數學家們仍然不知道明確的答案(除了 8 維和 24 維這兩個奇怪的例外)。多年來,他們提出了更好的填充方法。但這些改進規模很小,而且相對罕見。
如今,數學家 Boaz Klartag 在四月份發表的一篇論文《Lattice packing of spheres in high dimensions using a stochastically evolving ellipsoid》中,新方法以顯著優勢打破了之前的記錄。一些研究人員甚至認為,他的結果可能接近最優解。
論文地址:https://arxiv.org/pdf/2504.05042
作為該研究領域的新人,Klartag 通過復興一種專家們幾十年前就已放棄的古老技術,實現了他的堆積方法 —— 該方法適用于所有任意高維空間。這項工作觸及了關于高維空間最優堆積性質的幾個長期爭論。它們應該是有序的還是無序的?它們究竟能堆積到什么程度?
「這真是一個了不起的突破,」耶路撒冷希伯來大學的數學家 Gil Kalai 說道。「它是能讓近 100 年數學家興奮起來的成果?!?/p>
一個領域,兩種方向
1905 年,德國數學家赫爾曼?閔可夫斯基(Hermann Minkowski)建立了一種直觀的方法來思考堆積球體。首先,我們先從空間中重復排列的點開始,稱為「格」(lattice)然后圍繞每個點畫一個球體。這樣,在給定維度中尋找最優球體堆積的問題實際上變成了尋找一個點排列盡可能高效的格子的問題。例如,在二維空間中,最優格子是「六邊形」,其堆積形式如下:
看起來很符合直覺?但是在 1947 年,一位名叫克勞德?安布羅斯?羅杰斯(Claude Ambrose Rogers)的數學家提出了不同的觀點。他認為,可以從任何格開始 —— 即使是次優的位置。與其在每個點周圍畫一個球體,不如在一個點周圍畫一個橢圓形,稱為橢圓體,這樣橢圓體的表面會接觸但不會超出格中的其他點。羅杰斯提出了一種算法,以這個橢圓體為起點,構建一個致密的球體堆積。
它的工作原理如下:
羅杰斯方法的優勢在于,你無需從特別高效的格子開始就能獲得高效的球體堆積。你只需選擇合適的橢球體即可,但這帶來了新的復雜性。與完全由一個數字(半徑)定義的球體不同,橢球體由多個不同長度的軸定義。維度越高,可以拉伸橢球體的方向就越多,起始橢球體形狀的選擇就越多。
「在高維空間中,你不知道該如何擴展它,擁有太多自由度了?!筀lartag 說道。
數學家們最終回歸了閔可夫斯基的方法,選擇專注于尋找合適的格子。他們更加專注于格子理論,而不再像羅杰斯那樣專注于幾何學。
這種策略帶來了高維球體堆積的改進。但在大多數情況下,它們只是在羅杰斯的堆積方法上取得了相對較小的進步。數學家們仍然期盼著更大的飛躍。幾十年來,他們一直未能如愿。只有一位局外人才能打破這種停滯的狀態。
局外視角
Klartag 是以色列魏茨曼科學研究所的數學家,他一直對格子和球體堆積很感興趣。不過,Klartag 一直沒時間對其進行深入研究,他原本的研究領域是幾何,擅長的研究領域是凸形。這些形狀包含各種對稱性,尤其是在高維度上。Klartag 堅信,這使得它們極其強大:他認為,凸形是被低估的數學工具。
博阿茲?克拉塔格(Boaz Klartag)長期以來一直認為凸幾何領域的方法可能有助于解決球體堆積問題。他只是一直沒時間去驗證自己的猜測 —— 直到現在。
去年 11 月,在他完成了自己慣常研究領域的一個重要項目后,發現自己的日程安排出乎預料的空?!肝蚁?,我已經 47 歲了,我這輩子都想研究格子,如果現在不做,就永遠也做不成了,」他說。他請特拉維夫大學的朋友 Barak Weiss 指導他進行這項新嘗試。
Weiss 和 Klartag 以及其他幾個人一起開了一個小型研討會,研究相關文獻。Klartag 的作業包括仔細閱讀閔可夫斯基和羅杰斯的球體堆積方法。
當他讀到羅杰斯將橢球體變成球體堆積的技巧時,他想知道為什么數學家們放棄了這種方法。橢球體是凸形,所以 Klartag 知道很多復雜的方法來操作它們。他還意識到,羅杰斯使用的初始橢球體雖然直觀,但效率低下。他只需構造一個更好的橢球體 —— 一個在邊界與格中的其他點接觸之前能夠覆蓋更大空間的橢球體 —— 就能創造新的填充記錄。
他首先采用了一種自己熟知的方法,即根據隨機過程沿橢球體的每個軸擴展和收縮其邊界。每當邊界擴展至足以觸及格中的新點時,他就凍結橢球體在該方向上的生長。這確保了該點永遠不會落入橢球體內部。但橢球體的形狀會繼續向其他方向膨脹,直到碰到另一個點。就這樣,橢球體會以急促、猶豫的運動改變形狀,逐漸「探索」周圍的空間。最終,邊界會碰到足夠多的點,阻止橢球體進一步生長。
隨著時間的推移,平均而言,這項技術會使橢球體的體積增加。但它是否增加到足以超越羅杰斯直觀的橢球體呢?
由于 Klartag 的方法是隨機的,因此每次實施都會產生不同的橢球體。他評估了這些橢球體可能擁有的體積范圍。如果他能找到一個體積比羅杰斯幾十年前使用的橢球更大的橢球,他就能用羅杰斯最初的方法把它變成更緊密的球體堆積。
但 Klartag 找不到一個足夠大的橢球,于是他調整了隨機生長過程的細節。僅僅一兩周后,他就證明了,至少在某些時候,這個過程會產生足夠大的橢球,足以創下新的紀錄。
他立即將結果告知了 Weiss。「我們下周見面吧,我會告訴你我之前是怎么搞錯的,」Klartag 告訴他的導師。此時,Klartag 對自己的證明已經更加自信了。
接近真相
新的證明已獲驗證。Klartag 新的起始橢球體在轉化為球體堆積后,其堆積效率實現了自羅杰斯 1947 年論文以來最顯著的提升。對于給定的維度 d,Klartag 可以堆積的球體數量是大多數先前結果所能堆積球體的 d 倍。也就是說,在 100 維空間中,他的方法可以堆積大約 100 倍的球體;在百萬維空間中,可以堆積大約 100 萬倍的球體
Klartag 僅用幾個月的研究和幾周的證明就破解了格和球體堆積領域的一個核心難題。「這感覺簡直是不公平,」Klartag 說道。但數學通常就是這樣運作的:有時一個棘手的問題只需要一些新的想法,而嘗試自己領域之外的研究可能會帶來回報。Klartag 對凸幾何(通常是另一個研究領域)的熟悉,恰恰是這個問題所需要的?!赣捎谖业墓ぷ鳎@個想法一直縈繞在我的腦海中,」他說。「對我來說,這顯然是可以嘗試的?!?/p>
他的成果也重新引發了該領域關于任意高維空間中最優堆積性質的爭論。數學家們曾一度認為高度對稱、基于格的堆積是盡可能密集地排列球體的最佳方式。但在 2023 年,一個團隊發現了一種不完全依賴于重復格子的堆積方式;在 Klartag 的研究結果之前,這是一項難以打破的紀錄。一些數學家認為,這表明在尋找最優球體堆積時,需要更多的無序性。
現在,Klartag 的工作支持了這樣一種觀點:有序和對稱或許才是最終的出路。
此外,關于球體堆積究竟能達到多高的密度,一直存在爭議。一些數學家認為 Klartag 的堆積方式距離最優值只有一步之遙 —— 實際上已經盡可能接近了。其他人則認為仍有改進的空間?!肝椰F在真的不知道該相信什么,」伊利諾伊大學芝加哥分校的 Marcus Michelen 說道?!肝艺J為所有現實情況都尚待確定。」
這個問題的答案對于密碼學和通信領域的潛在應用至關重要。因此,Klartag 的成果雖然對這些應用目前尚無立竿見影的效果,但卻激發了一些初步的熱情?!高@個問題對工程師來說非常嚴峻,而且近年來進展甚微,」希伯來大學的信息理論家 Or Ordentlich 說道?!杆赃@讓我們感到興奮?!?/p>
Klartag 則希望他的工作能夠引領人們回歸羅杰斯時代的實踐,那時凸幾何和格理論領域的聯系更為緊密?!肝艺J為我們現在對凸體的理解應該對格理論有用,甚至超越了堆積理論,」他表示。「我的目標是讓這兩個領域之間的聯系比現在更加緊密…… 這是我的計劃,我仍然想繼續走下去?!?/p>
參考內容:
https://www.quantamagazine.org/new-sphere-packing-record-stems-from-an-unexpected-source-20250707/
特別聲明:以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布,本平臺僅提供信息存儲服務。
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.