存在90年的凱勒猜想被完全破解

最近,一個由電腦科學家和數學家組成的團隊,徹底解決了一個被稱為凱勒猜想的數學難題。凱勒猜想是一個已存在了90年之久的謎題,它與不同空間維度上的密鋪問題有關。

我們可以先從最簡單的二維情況開始。在二維空間中,用相同大小的正方形瓷磚進行密鋪時,是否總會出現兩塊瓷磚具有一整條共享的邊的情況?從圖形上不難看出,情況的確是這個樣子。

在二維空間中,用同等大小的正方形瓷磚密鋪時,黃色的邊表示的即是兩塊完全連結的瓷磚。| 圖片參考來源:cs.cmu.edu

將這個問題從二維提升到三維空間,情況也是如此嗎?

不難看出,當用大小相同的立方體來完全填充一個空間時,必定有兩個立方體完全共享一個面的情況出現。

三維空間中用相同大小的立方體密鋪,會導致兩個立方體共享一個面。黃色方形便是共享會出現的地方。| 圖片參考來源:cs.cmu.edu

二維、三維的情況是我們尚可想象的空間,但是在更高的維度上,情況又是如何?1930年,德國數學家奧特-海因裡希·凱勒(Ott-Heinrich Keller)提出猜想,認為這種模式適用於任何維度。這便是凱勒猜想。

在那之後的幾十年裡,凱勒猜想取得了眾多進展。1940年,數學家Oskar Perron成功證明,凱勒猜想在六維以及更小的維度上是正確的。然而在1992年,Jeffrey LagariasPeter Shor的工作表明,當維度提高到十以及以上時,這個猜想便不再成立。到了2002年,John Mackey進一步將這個「不適用範圍」縮小到了八維空間,表明它在八個或八個以上的維度上便不再適用。如此一來,仍處於未知狀態的就是七維空間中的情況了。

從Perron到Lagarias和Shor,在數學家們向這個猜想發起挑戰的過程中,研究方法發生了重大變化。在Perron的年代,他依靠的是筆和紙來計算這種模式在前六個維度中的適用情況;到了1990年代,為了能讓強大的計算機加入這項挑戰,數學家Keresztély CorrádiSándor Szabó對這一猜想進行了重新表述,將它轉化成了一種完全不同的形式。

凱勒猜想原本涉及到的是光滑的連續空間,在這種空間裡,存在無窮多種方式來進行無窮多個瓷磚的密鋪,而這種無窮大是計算機並不擅長處理的問題。因此Corrádi和Szabó將猜想轉化成了某種涉及到離散的、有限的物體的問題來處理。這樣一種等價方法有效地將一個關於無窮大的問題,簡化成了關於幾個數字的算術問題,它所涉及到的一個基礎核心是一種被稱為凱勒圖的圖形。

簡單說來,凱勒圖是由具有特定點數的骰子,以及這些骰子之間的連線構成的。點數對應於維數,要判斷凱勒猜想在n維空間上是否正確,可以透過在凱勒圖上尋找是否存在2ⁿ個彼此之間相互連接的骰子組成的小集合,如果存在,那麼凱勒猜想在n維中就是不正確的。

以二維空間中的凱勒猜想為例,首先想象桌子上擺放著一些骰子,且對於每個骰子來說,朝上擺放的那一面的點數為2——這兩個點就對應於二維,它們的位置就代表著座標系中的x軸和y軸。接著,分別用紅、綠、黑、白四種顏色任意地給每個點塗上顏色,並將紅和綠黑和白設定為兩組「配對色」。

現在,當兩個骰子的相同位置的點有不同的顏色,而另一個位置的點的顏色不僅不同,且顏色配對(紅和綠,或者黑和白),就將這兩個骰子骰子用直線連接起來,如下圖中的第四種情況,就滿足用線連接的條件。

二維的凱勒圖中的骰子上有兩個點,如果兩個骰子上的點的顏色完全相同,意味著兩個瓷磚在空間中完全重合;如果兩個骰子既沒有共同顏色,也沒有配對色,意味著瓷磚部分重疊(一種密鋪問題中是不允許存在的情況);如果兩個骰子有一位置上的顏色配對,另一個位置上的顏色相同,意味著兩塊瓷磚有一個共享面;當兩個骰子之間存在連接,代表著兩個瓷磚相互接觸,但彼此略微錯位。最後這種情況是在證明凱勒猜想時所要尋找的例子,它代表著那些相互接觸卻沒有共享面的瓷磚。| 圖片參考來源:Samuel Velasco / Quanta Magazine

在凱勒圖中,每個骰子可被看成是凱勒猜想中的一塊瓷磚;骰子上的顏色可被看作是座標,定義了瓷磚在空間中的位置;而骰子之間存在連接與否,可被看作是對兩個瓷磚的相對位置的描述。

二維空間的凱勒圖。| 圖片參考來源:cs.cmu.edu

上圖所示的就是二維情況的凱勒圖,它由16個點數為2的骰子組成。就像前面已經提到的,這張圖能將凱勒猜想的證明,變成判斷能否找到4(即2²)個這樣的骰子形成一個完全彼此相互連接的小集合,如果能,那麼就證明凱勒猜想在二維空間中是錯誤的。

由4個骰子組成的完全彼此連接的小集合。| 圖片參考來源:Quanta Magazine

但從二維凱勒圖上可以看出,這樣的小集合並不存在,因此凱勒猜想在二維空間中是正確的。

Corrádi和Szabó利用這種方法,用216個具有3個點的骰子證明了凱勒猜想適用於三維空間,在這種情況下,他們要尋找的反例是8(即2³)個相互連接的骰子。Mackey則透過找到256(即2⁸)個具有8個點的骰子的小集合,證明了凱勒猜想不適用於八維以及更高的維度。

要判斷七維空間是否適用於凱勒猜想,需要判斷能否找到128(即2⁷)個具有7個點的骰子的小集合。七維空間一直是個難點,這與它是的素數本質不無關係,這意味著它無法被分解成更低的維度。

終於,在新的研究中,數學家Joshua BrakensiekMarijn Heule、Mackey以及David Narváez在40臺計算機的幫助下解決了這個問題。計算機就給出的最終答案是:是的。這意味著,我們終於知道了凱勒猜想在最後一個維度上的適用情況,證明凱勒猜想在七維空間中仍然正確。而計算機提供的答案也遠不止一個簡單的結論,它還包括了一個大小為200Gb的證據來證明這個答案是正確的。

至此,凱勒猜想可被認為已被完全解決。

參考來源:

https://www.cs.cmu.edu/~mheule/Keller/

https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/

https://mathworld.wolfram.com/KellersConjecture.html