【組合】【幾何】

[離散幾何學突破]球體裝填問題: 如何用最少空間裝填最多顆球?

張貼日期：May 31, 2016 9:9:59 AM

作者：俞韋亘（Michigan State University）

2016 年 3 月 14 日白色情人節，一位年輕的數學家，任職德國柏林洪堡大學 (Humboldt-Universität zu Berlin) 博士後，Maryna S. Viazovska 在 Arxiv 上傳了一篇重量級的文章 `The sphere packing problem in dimension 8'，探討八維空間的球體裝填問題。這篇文章迅速在全世界各地的離散幾何學家傳開，爭相走告。筆者也是在此文章發表當天就接獲第一手消息，欣喜拜讀大作。

from Maryna Viazovska’s home page

說到 Maryna S. Viazovska，她可以算是數學界的一個奇葩。還在讀博士時候就發表了一篇論文 `Optimal asymptoticbounds for spherical designs' 刊在數學界最高榮譽的雜誌－Annals of Mathematics。

球面設計 (Spherical designs) 的存在性問題是離散幾何的經典難題之一。當年她與另外兩個合作者突發奇想，巧妙用了不動點定理來切入並且獲得了相當好的結果，論文因而被接受刊載在 2013 年的 Annals of Math. 上，引起學術界不小轟動。畢竟，這世上有多少數學家夢寐以求能夠發表一篇 Annals of Math. 的文章。而這回是 1 個博士後(Bondarenko)加上 1 個博士生(Viazovska)和 1 個大學生(Radchenko)就發了刊載在第一流期刊的論文，非常難得。[筆者OS: 是說台灣有沒有機會培養出大學生發 Annals of Math. 呢? 希望我有生之年會看到呀!]

沒想到事隔沒多久，這回 Maryna Viazovska 又有嶄新的突破，著實令人期待她之後還會有什麼曠世巨作出現。今天我們先來談一談這一次的球體裝填究竟是甚麼樣的有趣問題。

球體裝填問題 / Sphere packing problem

你的維他命罐子裡裝有多少顆維他命呢？可曾注意到喝咖啡時舀起來放進杯子裡的糖有幾顆嗎？乍聽之下好像很無俚頭的問題，實際上卻非常重要阿！用儘可能少的空間來裝填物品，對於食品公司、包裝公司或者搬家業者來說，有明顯的利害關係。這樣的問題不只數學家、物理學家、化學家關注，連路邊攤賣橘子的攤販都關注呀～

這個問題目前聽起來有點過於攏統，為求精確並且簡單，我們考慮完美的球體（數學上的球體），而裝填的效率好不好就用球體佔整體空間的體積比值，也就是

密度＝球體體積／罐子體積

有人做過實驗，隨機地裝填大約可以得到密度＝０.６左右的裝填效率，如果此時將瓶罐輕微搖一搖讓球彼此互相壓縮一些距離，那麼可以達到大約０.６４，這是透過大量實驗所得到的數據，隨機裝填最大的效能就只能到這裡了。

不過，追求完美的數學家可不會就此滿足的。

最密堆積

球體裝填問題是離散幾何(discrete geometry)領域的一個古老且經典的難題。在固定體積之下，如何安置一堆同樣大小的球越多越好? 達到最多的情況就稱為最密堆積。最密堆積就是數學家所追求的理想中完美的狀態！

photo from http://weusemath.org/

首先，我們來說說平面上的例子。

如果你注意看路邊攤賣橘子的攤位，小販會喜歡在有限大小的攤位上擺滿越多橘子越好，如果為了避免壓壞下層的水果而只能擺在同一層平面的話，那麼最密堆積就像上面這張照片一樣。這個擺盤方式稱為六角形堆積 (Hexagonal lattice packing)，每個橘子旁邊都有六顆橘子相鄰，如果你把它們的球心連起來，看起來就像是個正六邊形。1940 年 L. Fejes Tóth [1] 證明了六角形堆積就是平面上的最密堆積方式，密度是

，大約０.９０６９。

球體裝填問題在三維空間便是著名的克卜勒猜想 (Kepler Conjecture)。沒錯！正是大家熟知的天文學家克卜勒－Johannes Kepler。就連天后孫燕姿也有一首歌以他為名呢！

.... 一閃一閃亮晶晶，好像你的身體～

藏在眾多孤星之中，還是～找得到你。

掛在天上放光明～反射我的孤寂～

提醒我～我也只是一顆寂寞的星星～

克卜勒1610年肖像畫，作者不詳。

之前提到隨機裝填的最大密度大約有０.６４，不過若是適當地排列球的位置，可以提高達到更高的密度０.７４左右。在第一層，先將球以六角形堆積的方式排列，然後第二層的球放在「第一層球之上能讓球中心位置最低的點」之上，然後依此類推一層接著一層。每個階段對於下一層該如何擺放，都有著兩種選擇，此法最為人熟知的兩種形式即是面心立方和六方最密堆積這兩種方法，如下圖。

面心立方（左）與六方最密堆積（右）示意圖

photo by Christophe Dang Ngoc Chan

這兩種方法得到的平均密度相同：

（即大約７４％左右的空間被球所佔據）

在約莫 400 年前（西元 1611 年），克卜勒就猜想說，這是所有可能的排列法所能達到的最高密度，沒有更高的了。

《Strena Seu de Nive Sexangula》書裡克卜勒猜想的原圖

Photo from Wikipedia

他提出了這個猜測，但是卻無法證明。套一句現正熱映中的電影《天才無限家》裡印度天才數學家拉馬努金的台詞

「你是怎麼知道答案的？」

「我也不知道，我就是會啊！」

不過，在數學的世界裡，證明就是一切。正如戲裡一生追求真理的純數學家哈代所說

「對於無法證明的事，我沒有辦法相信。」

克卜勒猜想懸宕近四百年之久，困惑了多少歷史上最了不起的數學家，像是高斯和牛頓也對此有所研究，大名鼎鼎的希爾伯特 23 個問題中的第 18 個問題關心的非等質多面體密鋪空間和球體最密堆積，也跟克卜勒猜想有關。最後，終於在 1998 年被匹茲堡大學的黑爾斯 (Thomas Hales) 解決。其中運用了大量的電腦輔助來驗證，由於這樣的證明方式不那麼令人滿意，為了檢查論證是否正確無誤，12名審稿者花了四年時間檢查，得出了一個可能會讓數學家憂鬱症發作的結論，「黑爾斯的證明９９％是正確的。」為此黑爾斯還發展出一套驗證工具 Project FlysPecK，終於在 2014 年完成了克卜勒猜想的形式化證明。黑爾斯也因為 2005 年這篇落落長(一百多頁)刊載在 Annals of Math. 上的文章 [2] 而名滿天下。

高維空間的球體裝填

除了三維空間中的實際堆疊應用之外，４維以上的概念大概只能存在人們的想像中，一般人哪管４維空間發生甚麼事，更遑論其應用。不過數學家在發展一套理論時，通常也不管一般人會考慮到的「做這個有甚麼用」就是了。然而，高維度的球體裝填問題卻在現在這個資訊時代，扮演著無比重要的功能，它被應用於糾錯碼（error correcting code）的研究，舉凡所有資訊壓縮、儲存和傳送的機制中，都會使用它，包含影片、音樂等檔案以及光碟和硬碟等儲存裝置。

誰曉得五百年後會不會還有什麼實際的問題需要用到４維空間的球體裝填問題的解呢，呵呵~

什麼是 E₈-lattice?

在 Maryna 文章出來之前，４維以上的球體裝填問題都尚未完全解決! 她解決８維的球體裝填問題，是使用 Modular forms 作為工具，這個手法獨具巧思，令人驚奇。隨後沒多久，Henry Cohn 與其他人(包含Maryna)，用相同手法也解決了２４維的問題。

為什麼８跟２４這麼特別呢? 因為在 2003 年 Henry Cohn 與 Noam Elkies 發表了一篇論文 [3] 得到了維數４到３６的 sphere packing 問題最好的解(在當年)。其中８維與２４維是＂幾乎＂被解決了。

值得一提的是８維，上界跟下界非常的接近，僅僅只差了 1.000001 倍。球體裝填問題，如果你能找到一個很密的堆積方式，那這個構造就會提供最密堆積的下界。８維空間中下界是由 E₈ -lattice 所得到。而上界是用 Linear programming (簡稱LP)手法。Cohn & Elkies 通篇文章就是 LP 的手法得到維數４到３６的最佳上界。

以８維為例，原本只知道８維空間中球體裝填問題最大的密度不可能超過 0.25367。

而這個上界剛好跟 E₈ -lattice packing 所得到的密度非常接近(只差1.000001倍)。Maryna 就是站在巨人(Cohn& Elkies)的肩膀上，用 Laplace transform on modular forms 找到一個很好的函數代入 LP 手法，把這 1.000001 倍的困擾處理掉，證明

E₈ -lattice 就是８維空間中的最密堆積。

我們如果固定住一顆球，考慮其它球跟它相接觸的點。最密的堆積方式，換個角度想就是希望相接觸的點越多越好。E₈ -lattice 是８維空間 R⁸中的單位球(也就是七維球面 S⁷)上面的 240 個點，按照這 240 個點的位子當作球跟球之間的接觸點，就可以想像最密堆積的具體形式了。

下面直接把這 240 (=112+128) 個點算出來給大家看看。

第一類是八個位子有六個 0，兩個可以是 1 或 -1。其排列的情況是C8取2等於28，再乘上4(兩個地方有正負號選取)=112。
第二類是八個位子都是1/2，一共有 2⁸種，又規定負號要偶數個，所以一共有 2⁸/ 2 =128。一共有 240 個點，都躺在 R⁸半徑根號 2 的球上。E₈ -lattice packing 就是按照這 240 點的位子當作球跟球之間的切點，這樣一擺就會是８維的球體裝填問題最佳解。

除此之外，E₈ -lattice 在許多問題中扮演神奇角色。例如它也是 Kissing number 在８維空間的解。也是 Maximum 3-distance set in R⁸。總之是個很奇妙很特別的構造。

Henry Cohn ＆ Noam Elkies

文末最後來聊一聊這幾位重要數學人物 Henry Cohn 和 Noam Elkies 是何許人也。

Noam Elkies 現年 49 歲，14 歲的時候以滿分拿下數學奧林匹亞金牌。16 歲讀哥倫比亞大學時拿普特南獎(putnan)，創下最年輕得獎紀錄。20 歲拿了哈佛的數學博士。24 歲升等哈佛 Tenure 副教授，26 歲獲正教授創下哈佛最年輕教授紀錄。(筆者 26 歲時候才剛退伍，根本還沒開始到美國念博士，人家已經哈佛正教授了 XD)

他的研究專長是數論與代數幾何(橢圓曲線)，離散幾何只是他的小小副業而已。除了數學之外，還精通音樂作曲與圍棋。

Noam Elkies

Henry Cohn

Henry Cohn 則是數論、密碼學、離散幾何專家。2000 年的時候在 Noam Elkies 指導下拿了哈佛數學博士。目前是 Microsoft 新英格蘭區研究院的 principal researcher，同時也兼任 MIT 數學系教職。Henry 研究興趣十分廣泛，筆者常在美國各大會議中遇見他，是個非常風趣與活力充沛的數學家。雄厚的數論與基礎數學背景，讓他時常一出手就是把某些問題所有類型一口氣全都解決，其他人可能連一丁點肉湯都沒得喝。