散文網(wǎng) » 生活 »日常 » 8維空間好砌墻——90年歷史的凱勒猜想被解決

8維空間好砌墻——90年歷史的凱勒猜想被解決

2020-09-19 04:24 作者:大老李聊數(shù)學(xué) 0人讀過(guò) | 我要投稿

每個(gè)人都應(yīng)該看到過(guò)用磚塊砌的墻。用磚塊砌墻時(shí)，有個(gè)基本規(guī)范是，總是讓某一層的磚塊的左右兩邊與上下層磚塊的中間對(duì)齊，而不是邊與邊對(duì)齊。如果有人把墻砌成像“田”字形的，那他砌墻不但業(yè)余，而且這墻也很危險(xiǎn)，不安全。

現(xiàn)在數(shù)學(xué)家問(wèn)你，有沒(méi)有辦法砌一堵墻，使得每塊磚的每條邊都與其他磚錯(cuò)開(kāi)呢？這里，我們需要先對(duì)“錯(cuò)開(kāi)”這個(gè)詞下個(gè)科學(xué)定義。

既然是墻，我們就先限制在二維平面上，這樣磚就看做矩形。我們可以這樣定義二維平面上的“錯(cuò)開(kāi)”：

在完全密鋪平面的情況下，沒(méi)有任何兩個(gè)矩形的邊是完全重合的。任何矩形的邊總是接觸2個(gè)或以上其他矩形的邊，而不是兩個(gè)矩形的等長(zhǎng)邊貼在一起。

那對(duì)磚塊來(lái)說(shuō)，能否做到這一點(diǎn)呢？答案是可以的（見(jiàn)圖），關(guān)鍵在于磚的長(zhǎng)寬長(zhǎng)度不同。但實(shí)際上很少有人用這種模式砌墻，因?yàn)檫@種方式單塊磚的承重更大，更不堅(jiān)固。

(上圖：一種矩形密鋪模式，英語(yǔ)稱(chēng)為Herringbone，中文俗稱(chēng)“人字紋”)

數(shù)學(xué)家又問(wèn)了：既然長(zhǎng)方形可以，那如果是正方形的磚呢？稍作思考，你就會(huì)發(fā)現(xiàn)對(duì)正方，無(wú)法做到全錯(cuò)開(kāi)的平鋪了，沒(méi)法做到水平和垂直兩個(gè)方向同時(shí)錯(cuò)開(kāi)。

數(shù)學(xué)家又問(wèn)了，二維上不行，三維可以嗎？這時(shí)我們又需要把三維下的問(wèn)題精確定義一下：

用正立方體填充空間，是否可能避免所有立方體的兩個(gè)面重合？也就是沒(méi)有面貼對(duì)面的情況。

三維略微復(fù)雜點(diǎn)，你可能需要拿好7、8個(gè)骰子來(lái)試試。很快你會(huì)發(fā)現(xiàn)，三維填充也做不到以上的全錯(cuò)開(kāi)要求。

（上圖：三維下的立方體填充的一個(gè)可能模式，接下來(lái)你必然會(huì)在某個(gè)藍(lán)色的面上出現(xiàn)無(wú)法錯(cuò)開(kāi)的情況）

當(dāng)然，數(shù)學(xué)家又問(wèn)了，你也猜到數(shù)學(xué)家的問(wèn)題了：以上這種問(wèn)題，對(duì)n維空間的一般結(jié)論如何？數(shù)學(xué)家夠無(wú)聊吧？

這個(gè)問(wèn)題最早是1896年，德國(guó)數(shù)學(xué)家，愛(ài)因斯坦的老師，閔可夫斯基提出的。也不知道他是不是在砌墻時(shí)（玩笑）想到了這個(gè)問(wèn)題：

用n維的超立方體去填充空間，是否存在可以使得不存在兩個(gè)立方體共享某個(gè)n-1維的“面”？這里他考慮的填充是“晶格填充”（Lattice Tilling），意思就是有周期性和對(duì)稱(chēng)性的填充。

閔可夫斯基認(rèn)為是不存在這樣的填充方案的，這也是符合我們直覺(jué)的。前面我們已經(jīng)分析過(guò)二維和三維的情況，很難想象高維情況下，存在全錯(cuò)開(kāi)的填充方案。閔可夫斯基一開(kāi)始也很自信，他發(fā)表這個(gè)猜想的時(shí)候直接說(shuō)：這會(huì)是一個(gè)定理，證明我稍后給出。

但是在1907年出版的一本閔可夫斯基所著的書(shū)中，他還是把以上這個(gè)命題作為一個(gè)猜想給出，而沒(méi)有給出證明。這說(shuō)明他自己考慮過(guò)了，但是沒(méi)能找出一個(gè)完滿(mǎn)的證明，這個(gè)問(wèn)題沒(méi)有看上去得那樣簡(jiǎn)單。

1930年，德國(guó)數(shù)學(xué)家?jiàn)W特-海因里希·凱勒把閔可夫斯基的猜想作了少許一般化，把“晶格填充”里的“晶格”兩字去掉了，意思就是用任何方式填充都可以。而且他同樣猜想，用n維立方體填充n維空間，至少有兩個(gè)立方體會(huì)“共享”一個(gè)n-1維的“面”。這個(gè)猜想后來(lái)就被稱(chēng)為“凱勒猜想”（Keller's Conjecture）。

這個(gè)猜想看上去很像是真的。1940年，德國(guó)數(shù)學(xué)家Oskar Perron證明，凱勒猜想在6維及更少維度下的都是對(duì)的。

但是萬(wàn)沒(méi)想到，1992年，兩位數(shù)學(xué)家Lagarias和Shor證明，凱勒猜想在10維空間上是錯(cuò)誤的。

這兩位數(shù)學(xué)家找到了凱勒猜想在10維空間上的一個(gè)反例，也就是在10維空間上，你可以用10維立方體填充空間，并且確保沒(méi)有任何兩個(gè)立方體共享9維的面。而之前有其他人證明過(guò)，如果凱勒猜想在n維上有反例，則可以構(gòu)造大于n維的所有維度上的反例。所以10維有了反例后，那么10維以上，凱勒猜想都不成立了，是不是夠意外？

那么還剩下7，8，9三個(gè)維度的情況不清楚。2002年，數(shù)學(xué)家Mackey找到了凱勒猜想在8維的一個(gè)反例，那么同理，9維情況下，凱勒猜想也不成立。

所以只剩7維的情況。而最近，來(lái)自斯坦福和卡內(nèi)基梅隆大學(xué)等高校的4名數(shù)學(xué)家，把7維的情況解決了，他們證明7維情況下，凱勒猜想是成立的。由此凱勒猜想被徹底解決，結(jié)論就是：凱勒猜想僅在7維及以下空間成立。

以上我們看到1990年以后，凱勒猜想的證明進(jìn)程被大大加速。這個(gè)加速的原因在于，1990年，Corrádi和Szabó提出了一個(gè)稱(chēng)為“凱勒?qǐng)D”的概念，可以將凱勒猜想轉(zhuǎn)化為一個(gè)離散數(shù)學(xué)中的圖論問(wèn)題，并且可以借助計(jì)算機(jī)去搜索這個(gè)圖，從而幫我們解決問(wèn)題。下面簡(jiǎn)單介紹下這個(gè)思路。

n維空間的凱勒?qǐng)D有4^n個(gè)點(diǎn)構(gòu)成，每個(gè)點(diǎn)用n個(gè)元素的向量標(biāo)識(shí)，向量可以視為元素在坐標(biāo)系中的坐標(biāo)。

向量的元素為集合{0，1，2，3}元素之一。兩個(gè)點(diǎn)之間有連線(xiàn)，當(dāng)且僅當(dāng)：兩個(gè)點(diǎn)至少在兩個(gè)坐標(biāo)點(diǎn)上不同，且在至少一個(gè)坐標(biāo)點(diǎn)上的差為2（模4）。其實(shí)能連線(xiàn)就表示那兩個(gè)立方體的能“錯(cuò)開(kāi)”

比如，對(duì)二維凱勒?qǐng)D，它有16個(gè)點(diǎn)。如果用顏色表示數(shù)字：黑/B=0，紅/R=1，白/W=2，綠/G=3。則16個(gè)點(diǎn)的標(biāo)識(shí)為:

[('B', 'R'), ('B', 'W'), ('B', 'G'), ('R', 'B'), ('R', 'W'), ('R', 'G'), ('W', 'B'), ('W', 'R'), ('W', 'G'), ('G', 'B'), ('G', 'R'), ('G', 'W')]

根據(jù)之前凱勒?qǐng)D定義，二維凱勒?qǐng)D只可能在1個(gè)坐標(biāo)上相同，另一個(gè)坐標(biāo)上“配對(duì)”（差為2，則黑與白是一對(duì)，紅與綠是一對(duì)）。

不同的點(diǎn)的坐標(biāo)關(guān)系可以看下圖的解釋?zhuān)?/p>

根據(jù)之前的定義，可以畫(huà)出二維的凱勒?qǐng)D如下：

（圖片來(lái)源：https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/）

根據(jù)凱勒?qǐng)D的定義，如果我們可以在上圖中找到4個(gè)兩兩連接的點(diǎn)，則表示我們可以用這四個(gè)正方形填充平面，且互相錯(cuò)開(kāi)，這樣就推翻了凱勒猜想。這種若干個(gè)兩兩相連的點(diǎn)，術(shù)語(yǔ)稱(chēng)為“Clique”，小圈子。顯然二維凱勒?qǐng)D中找不到這樣的小圈子。

Corrádi and Szabó 在1990年證明，n維圖中最多有2^n點(diǎn)構(gòu)成的小圈子，而如果存在這種2^n個(gè)點(diǎn)的小圈子，則可推出n維的凱勒猜想不成立。但是，不存在小圈子，不能證明凱勒猜想正確。

1992年，Lagarias和Shor利用計(jì)算機(jī)，發(fā)現(xiàn)了在10維的凱勒?qǐng)D中，能找到個(gè)2^10=1024點(diǎn)構(gòu)成的小圈子，所以10維情況下，凱勒猜想不成立。

之后，8維也是類(lèi)似，數(shù)學(xué)家找到了這樣一個(gè)256個(gè)點(diǎn)的小圈子:

按理說(shuō)，7維的情況，凱勒?qǐng)D的點(diǎn)更少，需要找的小圈子也只有128個(gè)點(diǎn)，看上去更容易，那為什么是最后一個(gè)解決的情況呢？一個(gè)主要原因是7是一個(gè)質(zhì)數(shù)。而8和10都是合數(shù)。要知道在高維情況下，凱勒?qǐng)D中的點(diǎn)數(shù)是很多的。比如7維情況下，有4^7個(gè)點(diǎn)，要對(duì)其中每2^7個(gè)點(diǎn)的組合一一檢查，可能的組合數(shù)有10^323數(shù)量級(jí)，完全枚舉的話(huà)太大了。

在8維和10維的情況下，利用對(duì)稱(chēng)性我們可以把高維的問(wèn)題轉(zhuǎn)換成低維，從而節(jié)省時(shí)間，但對(duì)7維就需要一些新的優(yōu)化搜索方法。

這次，研究者在使用一些全新優(yōu)化方法后，使用40臺(tái)電腦，對(duì)7維的凱勒?qǐng)D進(jìn)行搜索，僅30分鐘后，計(jì)算機(jī)輸出了200G的數(shù)據(jù)，確認(rèn)沒(méi)有找到128個(gè)點(diǎn)的小圈子。當(dāng)然，如前所述，找不到小圈子不代表凱勒猜想成立。所以，研究者還必須提供其他一些證明，最終的論文有24頁(yè)，確認(rèn)7維空間中，凱勒猜想是對(duì)的。

至此，一個(gè)90年歷史的數(shù)學(xué)猜想被完整解決。我最大感想是宇宙構(gòu)造的奇妙，7維以上空間，你可以用正方體的磚完美填充一個(gè)空間，且每一塊都錯(cuò)開(kāi)，但為何分水嶺是7到8呢？太奇妙了。

另外，凱勒猜想還有一些延伸內(nèi)容，比如當(dāng)初閔可夫斯基是在思考一類(lèi)丟番圖不等式時(shí)（而不是砌磚時(shí)），提出這個(gè)猜想的。凱勒猜想還有一個(gè)群論中的等價(jià)版本，這些留讀者自行研究。

附記：《老師沒(méi)教的數(shù)學(xué)》已由韓國(guó)Davinci House出版社翻譯為韓文，現(xiàn)已上市：