在1977年發射“旅行者”號雙子探測器之前，美國宇航局的工程師們面臨一個難題：當探測器到達木星和土星時，如何使用大約一個燈泡的功率將彩色照片傳回地球？
這是一項需要極度節約的任務：每張影像都必須轉換為一系列24位二進位制序列，稱為“碼字”，並透過無線電波傳送到太空中，這些無線電波透過其波峰和波谷的位置來表示每個1或0。但是資料傳輸是有噪聲的。工程師們知道，當碼字向地球傳輸時，一些1會被扭曲成0，一些0會被扭曲成1。為了重建“旅行者”號的標誌性照片，他們必須能夠糾正程式碼。
關於支援科學新聞
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道： 訂閱。透過購買訂閱，您正在幫助確保未來有關塑造我們當今世界的發現和想法的重大報道。
“旅行者”號探測器需要使用其序列足夠獨特，即使有一些位被破壞也能識別的碼字。但是，使用不那麼獨特的碼字可以在24位限制內提供更多的可能性，從而實現更快的資料傳輸。這些相互競爭的需求轉化為一個幾何問題，其中位對應於空間座標，每個碼字是24維空間中一個球體的中心點。如果球體重疊，則相關的碼字將不再是唯一可識別的。為了最佳化可以傳輸然後糾正的資料量，問題變成了：球體在24維空間中可以堆積得多緊密？
“糾正這種嘈雜通訊通道上的錯誤的問題正是球體堆積問題，”位於馬薩諸塞州劍橋市的微軟新英格蘭研究院的數學家亨利·科恩說。
球體堆積問題幾乎是所有數字通訊和儲存的基礎，從手機到CD到網際網路。但是，這些傳輸形式的最佳程式碼對應於在日常經驗的三個維度之外的維度中球體的最密集堆積，而更高維度的問題已被證明是令人生畏的。更難以解決的是不同大小的球體或更尖銳的形狀的密集堆積——與材料科學和工業製造相關的二維和三維問題。數學家們幾個世紀以來一直在努力解決堆積問題，他們被這些問題的難度及其現實世界的應用所吸引，但是每種情況都引發了其特殊的難題。“這太荒謬了，”科恩說。“我們甚至不知道在平面上堆積五邊形的最佳方法。”
現在，一種新的計算技術使許多幾十年來一直停滯不前的重大案例取得了進展。法國波爾多大學的數學家克里斯汀·巴霍克和德國科隆大學的數學家弗蘭克·瓦倫丁在2008年開發了這種工具，稱為“半正定規劃界限”，它借鑑了荷蘭阿姆斯特丹大學的亞歷山大·施賴弗的早期論文。該技術透過識別上限來粗略估計物件的最大密度堆積，隨著邊界的計算變得越來越詳細，上限可以逐漸降低到精確解。該工具正在為堆積問題的基礎幾何提供新的見解，包括關於對稱性是否是最大密度堆積中心特徵的長期問題。
瓦倫丁是應用數學和計算機科學教授，他和他的同事最近使用半正定規劃來降低二維空間中五邊形的最大密度堆積和四維、五維、六維、七維和九維空間中球體的最大密度堆積的上限。“這是讓我們超越我們以前擁有的分析技術的真正突破，”科恩說，他共同發現了那些維度中的先前最佳邊界。
迄今為止取得的漸進式進展幾乎沒有實際應用，但研究人員表示，這可能預示著更大的飛躍。“現在，更多的是關於開發方法，”瓦倫丁說。
半正定規劃改進了一種稱為線性規劃的技術，線性規劃幾十年來一直是上限發現方法的首選。利用線性規劃，研究人員列出物件對之間可能的相關性的約束，例如兩個球體的間距不能小於其半徑的兩倍的規則。然後，一種演算法會搜尋滿足約束列表的最高密度，從而透過排除一系列密度來產生上限。在半正定規劃中，該列表還可以包括對三元組、四元組或更大的物件集合的約束，從而提供更豐富的幾何描述，從而產生更好的邊界。
“最大的權衡是在邊界的複雜性和我們期望它們接近真相的程度之間，”科恩解釋說。
新工具已經使研究人員能夠改進類似於“旅行者”號探測器使用的二進位制程式碼的最佳化。在2012年5月和2013年11月發表在《IEEE 資訊理論彙刊》上的兩篇論文中，兩個小組改進了長度從18到28位的程式碼的界限。
但是，除了深空通訊之外，那些長度的程式碼只有很少的應用。大多數現代數字傳輸都涉及更大的資料包，並且傳輸效率與數百或數千個空間維度中的球體堆積相對應。在這些情況下，普林斯頓大學教授薩爾瓦託雷·托爾誇託和弗蘭克·斯蒂林格在2006年推測的最大密度堆積是稀疏的，球體僅填充了空間中千分之幾的百分比。“在更高的維度中，沒有證據表明最大密度堆積是什麼，”托爾誇託說。“隨著你增加空間的維度，事實上，無序最終會戰勝有序，而最大密度堆積是一種隨機排列，這是一種可能性。”
然而，無序排列很難在數學上定義並用作糾錯碼。自從美國數學家克勞德·夏農在他1948年的經典論文（該論文是資訊理論的基礎）中揭示了該問題與資料傳輸的相關性以來，研究人員一直在努力尋找高維空間中球體的密集、對稱的晶格。瓦倫丁和外部研究人員表示，半正定規劃界限可能是在確定可能實現的大致密度方面有所幫助的方法。
該工具還有助於解決更廣義的堆積問題。瓦倫丁和他的同事最近應用他們的演算法，找到了一些關於兩種不同大小的球體的最大密度堆積的首次上限，這是一個與許多晶體的研究以及某些訊息比其他訊息更重要的程式碼相關的問題。他們還表明，五邊形不能填充超過二維空間的98％。
普林斯頓大學的凝聚態物理學家約阿夫·卡盧斯說：“獲得這些型別問題的上限極具挑戰性。”三年前，卡盧斯和他的合作者證明，稱為四面體的金字塔形物體不能填充超過空間99.99999999999999999999999974％。“顯然，我們不期望堆積能達到那麼高，”他說。“只是很難獲得任何上限。”
瓦倫丁正在完善他的演算法，希望最終將四面體的上限降低到更接近最佳密度的水平。（到目前為止，密歇根大學的莎倫·格洛策和她的同事在2010年發現的最大密度排列，填充了空間的85.63％。）該演算法也將適用於各種其他形狀。“最終目標是：你把你的形狀給計算機，計算機給你一個關於你能把它堆積多密集的合理上限，”瓦倫丁說。
考慮到二維和三維堆積問題的複雜性，旅行者號探測器是如何使用24維碼字傳輸照片的？幸運的是，對於美國宇航局來說，在已解決的少量堆積問題中，24維球體晶格是特例。“在24維空間中，有一個驚人的對稱和密集的晶格，稱為‘李奇晶格’，”托爾誇託說。這種球體的緊密排列是英國數學家約翰·裡奇在20世紀60年代發現的，它為旅行者號探測器在資料傳輸期間提供了4,096個豐富的碼字。但是，李奇晶格不僅僅表示24維空間中球體的最大密度堆積。它屬於一類新的幾何結構，這些結構是各種方式相互作用的物體的首選排列方式，而不僅僅是像球體那樣不能重疊的物體。這些“普遍最優”是“最有趣、最美麗、最重要的結構，”科恩說，他與麻省理工學院的數學副教授阿比納夫·庫瑪一起研究它們。
普遍最優表現出某些奇蹟般的特性，例如科恩稱之為“不會卡住”的現象。考慮嘗試在平面上找到圓的最大密度堆積。你可能會從在一張紙的中間畫一個圓開始，並在其周圍儘可能多地安裝額外的圓。你很快就會發現六個圓在中心圓周圍形成一個緊密的六邊形。沒有理由認為這種模式應該繼續保持下去（例如，如果你畫的是五邊形，你只能畫一圈鄰居，然後就會出現尷尬的間隙），但事實證明，你可以按照六邊形模式不斷新增圓，而不會遇到麻煩。“一切都井然有序，”科恩說。
由蜜蜂建造的連續蜂巢平面所例證的這種二維六邊形晶格的罕見特徵，在24維空間中的李奇晶格和八維空間中稱為E8晶格的結構中也存在。儘管無法視覺化，但在數學上，這些晶格的構造同樣簡單。“一切都各就各位，”科恩解釋說。“模式會以你期望的方式繼續下去。你永遠不會卡住。”
該特性與普遍最優性有關。在2009年發表於《數學年刊》上的論文中，Cohn和Kumar證明了8維和24維的上界，這些上界與E8和Leech格子的密度相差不到百分之一，這表明它們幾乎肯定是各自維度中最密集的球體堆積。但這些格子似乎也普遍是最優的配置，不僅適用於球體，也適用於彼此施力的粒子，例如兩個互相排斥的電子。Cohn表示，對於“粒子之間任何合理的排斥力”，粒子都會在2維中自組裝成六邊形格子，在8維中自組裝成E8格子，在24維中自組裝成Leech格子。這些排列不僅是最密集的，而且是“普遍”最優的。
也許正是由於這個原因，這些結構廣泛地出現在數學和物理學中。“從組合數學和圖論到幾何學和代數幾何等等，它們到處都有出現，”Kumar說。
E8在弦理論中發揮著作用，弦理論是一種假設的“萬物理論”，它認為時空是10維的，電子和夸克等粒子是以不同頻率振動的微小一維弦。在20世紀80年代，弦理論學家表明，一種被稱為雜交弦理論的變體可以使用兩個E8副本的對稱性來構建。“我們可以從E8雜交弦理論出發，精確地生成我們所知的現實世界，”賓夕法尼亞大學的弦理論學家Burt Ovrut說。當以一種使世界看起來是三維的方式來簡化E8理論時，它包含了“夸克、輕子、希格斯玻色子以及我們觀察到的所有其他粒子”。
普遍最優性是一個年輕的概念，研究人員仍在探索其意義和結果。最近，Cohn和他的前實習生Jeechul Woo使用半定規劃界限發現了新的普遍最優解，其中包括一些比預期對稱性低得多的排列。“對稱性無疑發揮著重要作用，”Kallus說，“但我認為Henry Cohn展示的有趣的事情之一是，存在一些普遍最優的配置，它們不具備這種對稱性。”
數學家長期以來在處理堆積問題時都假設，正如任何旅行者所知，在堆積方面，有序通常勝過無序。對稱性並非在高維度中（隨機性占主導地位）或在一些新研究的低維度案例中都不是全部，這意味著科學家可能需要一些其他原則來理解堆積的潛在幾何結構及其宏大的延伸——普遍最優性。
“目前，我認為我們沒有一個根本的統一原則，”Kumar說。“我認為那裡存在各種有趣的事情。我們正在尋找對稱性的替代品。”
經Quanta Magazine許可轉載，該雜誌是SimonsFoundation.org的一個編輯獨立的部門，其使命是透過報道數學以及物理和生命科學領域的研究進展和趨勢來增進公眾對科學的理解。