公元 4 世紀，亞歷山大的希臘數(shù)學家 Pappus 發(fā)現(xiàn)，蜜蜂的蜂巢的六角形結構似乎是將二維空間劃分為面積相等、周長最小的單元格的最佳方式(平鋪二維空間)，這使得蜜蜂減少了它們需要生產的蜂蠟的數(shù)量。

就單個圓而言，同樣的面積，周長最小，但是當排列在一起時，就會有空隙，這樣就不如六邊形來得更經(jīng)濟。

但是幾千年來，沒有人能證明六邊形是最優(yōu)的，直到 1999 年，數(shù)學家托馬斯?黑爾斯最終證明，沒有其他形狀能比六邊形更好。至于 3 維和更高維度的空間，數(shù)學家們仍然不知道哪些形狀的單元格是最“經(jīng)濟”的平鋪方式。

這個問題已經(jīng)被證明具有廣泛的應用，物理學家可以研究這些“泡沫(單元格)”的性質，化學家可以分析晶體的結構，數(shù)學家可以探索球體的排列方式，統(tǒng)計學家可以開發(fā)有效的數(shù)據(jù)處理技術。

最為重要的是，泡沫問題還與計算機科學有著深刻的聯(lián)系，利用這種聯(lián)系，計算機科學家能夠找到一種新的具有最小表面積的高維形狀。但這個形狀缺少了一個重要的東西，幾何基礎。因為它的存在是用計算機科學技術證明的，所以它的實際幾何形狀很難掌握。這就是紐約大學的計算機科學家 Oded Regev 上個月在網(wǎng)上發(fā)布的一份證明中試圖解決的問題。

現(xiàn)在，我們對“泡沫問題”稍作改變，只允許根據(jù)所謂的整數(shù)格劃分空間會怎樣？

首先我們要知道什么是“格”。在幾何和群論中，實坐標空間 R^n 中的“格”是這個空間中無限個點的集合，具有這樣的性質:格中兩點的相加或相減會產生另一個格點，格點之間都間隔著某個最小距離，而且空間中的每個點都在一個格點的最大距離內。簡單說，假如把空間里的向量的末端視為一個點，則格就是某空間里面的具有一些規(guī)律的離散的點集合，也可以說格是某空間中的一個離散的、具有加法運算的子群。

維空間中最簡單的格就是整數(shù)格。整數(shù)格中最簡單的就是基于笛卡爾坐標系的等基向量組成的空間。格在純數(shù)學中有許多重要的應用，特別是在李代數(shù)、數(shù)論和群論方面。

回到問題，我們取一個等距點的方陣列，并使每個格點成為形狀的中心，就像這樣:

現(xiàn)在的問題是，當以這種方式平鋪空間時，最小的表面積將是多少？我們把這個問題稱為“立方泡沫問題(Cubical Foams)”。這個問題可以幫助研究人員了解稱為流形的拓撲空間的性質。

對于正方形情況，面積為 1，周長為 4:

正方形沿著網(wǎng)格平鋪二維空間，但周長不是最小。

對于正六邊形，面積為 1，周長約為 3.72:

正六邊形以最小的周長平鋪二維空間，但沿著一種不同的網(wǎng)格。

對于非正六邊形，面積為 1，周長約為 3.86:

1989 年，數(shù)學家 Jaigyoung Choe 證明了這些六邊形在二維空間中沿著方格進行最佳平鋪:

這在幾何上也很有趣，因為它改變了 "最優(yōu)" 的含義。例如，在二維空間中，如果正六邊形只能在水平和垂直方向上移動整數(shù)個單位，那么它們就不能在平面上平鋪。

正四邊形可以。但這就是最好的方法嗎？Jaigyoung Choe 在 1989 年發(fā)現(xiàn)，最理想的形狀是一個六邊形，在一個方向上被壓扁，在另一個方向上被拉長。這些差異可能看起來微不足道，但在更高的維度上，它們會很明顯。

在給定體積的所有形狀中，表面積(二維空間中是周長)最小的形狀是球體(對應二維空間的圓)。隨著維數(shù) n 的增加，球體的表面積隨著根號 n 成比例地增加。

但球體不可能在不留下縫隙的情況下平鋪空間。而一個體積為 1 的 n 維立方體可以。問題是它的表面積是 2n，與它的維度成正比。體積為 1 的 1 萬維立方體的表面積為 2 萬。

因此，研究人員想知道他們是否能找到一個“球形立方體”—— 一種像立方體一樣平鋪 n 維空間的形狀，但其表面積像球體一樣增長緩慢。

這似乎不太可能。

現(xiàn)在我們知道事實并非如此。難題的難度

難題的難度

幾十年來，立方體泡沫問題在高維中相對未被探索。第一個在這方面取得進展的研究人員不是來自幾何領域，而是來自理論計算機科學。當時計算機科學家正在尋找一種方法來證明計算機鄰域領域中一個被稱為 UG 猜想(unique games conjecture)。UG 猜想是目前理論計算機科學中最大的懸而未決的問題。

如果 UG 猜想是正確的，那么研究人員將能夠一下子理解大量其他計算任務的復雜性。

數(shù)學家們認為，一種被稱為 Weaire-Phelan 結構的形狀以最小的表面積平鋪三維空間。雖然他們還沒有證明這一點，但物理實驗為這一假設提供了支持。愛爾蘭都柏林三一學院的研究人員在一個特殊的模具里裝滿了肥皂泡，發(fā)現(xiàn)肥皂泡自然地排列成 Weaire-Phelan 圖案。

計算機科學家通常根據(jù)任務是否可以用有效的算法解決來對任務進行分類。例如，旅行推銷員問題是 NP 難題(NPH)，

旅行推銷員問題說的是，假設有一個旅行商人要拜訪 n 個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇目標是要求得的路徑路程為所有路徑之中的最小值。

圖著色問題也是 NP 難題。事實證明，要找到其中許多任務的近似解都是 NP 難題。

在 UG 猜想提出后不久，研究人員發(fā)現(xiàn)，如果猜想是正確的，那么可以很容易地計算出任何約束滿足問題的難度閾值。因此，理論計算機科學家開始證明 UG 猜想，這項任務最終導致他們中的一些人發(fā)現(xiàn)了球形立方體。

把難題變得更難

2005 年，O’Donnell 等人聯(lián)手解決了 UG 猜想問題。他們從一個關于圖形的問題開始，就是所謂的最大切割問題，當給定一個圖時，如何將其頂點劃分為兩個集合，以使連接這兩個集合的邊的數(shù)量盡可能大。

如果 UG 猜想為真，這就意味著，給定一些隨機圖，一個有效的逼近算法只能得到該圖真正最大切割的 87% 以內。如果想得到 87% 以上，就是 NP 難題了。

O 'Donnell 走的是相反的方向:他希望證明最大切割是很難近似的，然后用它來證明 UG 猜想。他們的計劃依賴于一種被稱為平行重復的方法，一種讓難題變得更難的方法。

假設你知道區(qū)分“一個你能解決的問題和一個你基本上可以解決的問題”是 NP 難題。平行重復可以讓你在此基礎上得到一個更難結果:區(qū)分一個你可以解決的問題和一個你幾乎無法解決的問題也是 NP 難題。

但有一個問題。并行重復并不總是像計算機科學家希望的那樣放大問題的難度。最大切割問題的某些方面“為平行重復制造了一個大麻煩。平行重復似乎有助于將最大裁剪與 UG 猜想聯(lián)系起來。

首先，研究人員試圖理解一個簡單的最大切割情況下的平行重復?？紤]由邊連接的奇數(shù)個頂點形成一個環(huán)。

你想用兩種顏色中的一種來標記每個頂點，使相鄰的頂點的顏色不同。顯然，這是不可能的，有一條邊總是連接相同顏色的頂點。你必須刪除那條邊，以打破奇數(shù)環(huán)。最終，你想要最小化你需要刪除的邊的數(shù)量來正確地著色圖形。

并行重復讓你考慮這個問題的高維版本。在這個問題的高維版本中，你必須打破所有出現(xiàn)的奇數(shù)環(huán)。O 'Donnell 需要證明，隨著維度的數(shù)量變得非常大，你必須刪除很大一部分邊來打破所有的奇數(shù)環(huán)。如果這是真的，這將意味著并行重復可以有效地放大這個“最大切割”問題的難度。

然后，研究小組發(fā)現(xiàn)了一個奇怪的巧合，有一種幾何方法來解釋平行重復是否會像他們希望的那樣工作。秘密在于立方體泡沫的表面積。

他們的問題，歸結起來就是表明球形立方體不存在 —— 不可能沿著整數(shù)格將高維空間劃分成表面積比立方體小得多的單元格。正如計算機科學家希望的那樣，更大的表面積對應著需要在奇循環(huán)圖中刪除更多邊。

所以在 2007 年，他們發(fā)表了一篇論文，概述了他們計劃如何利用這個問題來幫助攻擊 UG 猜想。很快，他們的希望就破滅了。

普林斯頓大學的理論計算機科學家 Ran Raz 已經(jīng)證明了幾個關于平行重復的主要結果。他決定分析奇循環(huán)問題的平行重復。Raz 證明了可以通過刪除更少的邊來打破圖中的所有奇循環(huán)。換句話說，平行重復不能充分放大最大切割問題的難度。同時，Raz 的結果也暗示了球形立方體的存在 —— 能夠平鋪 n 維空間的形狀，其表面積與 n 的平方根成正比。

2008 年，研究人員證明了球形立方體確實是可能的。

這就引出了幾何學方面的問題。球形立方體缺乏數(shù)學家喜歡的特性 —— 形狀更具體、更容易定義和研究、更適合潛在應用的特性。幾何學有很大的潛力。只是我們還不夠了解它。

鄭重聲明：此文內容為本網(wǎng)站轉載企業(yè)宣傳資訊，目的在于傳播更多信息，與本站立場無關。僅供讀者參考，并請自行核實相關內容。