曉查發(fā)自凹非寺

　　量子位報(bào)道公眾號 QbitAI

　　數(shù)學(xué)家會代碼，就連困擾人類 90 年的數(shù)學(xué)猜想也擋不住。

　　來自斯坦福、CMU 等高校的 4 名數(shù)學(xué)家，直接將一個(gè)數(shù)學(xué)難題轉(zhuǎn)化成了對10 億個(gè)結(jié)果進(jìn)行“暴力搜索”。

　　△論文作者之一 CMU 助理教授 Marijn Heule

　　他們把這串代碼輸入40 臺電腦組成的計(jì)算集群，30 分鐘后，計(jì)算機(jī)給出了一個(gè)200GB大小的證明結(jié)果：

凱勒猜想在不超過 7 維的空間上都是正確的。

　　現(xiàn)在，任何人都可以去GitHub上克隆這串代碼，驗(yàn)證這一數(shù)學(xué)定理。

　　比較反轉(zhuǎn)的是，這段獲得計(jì)算機(jī)學(xué)術(shù)會議IJCAR（國際自動(dòng)推理聯(lián)合會議）最佳論文獎(jiǎng)的程序，上線 GitHub 半年，只攬獲了一顆星。

　　那么，這 4 位數(shù)學(xué)家要證明的“凱勒猜想”到底是什么？為何非要用計(jì)算機(jī)來證明？計(jì)算機(jī)證明的結(jié)果可靠嗎？

　　下面讓我們一一道來。

　　什么是凱勒猜想

　　假如用一批完全相同的正方形瓷磚鋪滿地面，中間不留空隙。顯然，瓷磚之間會共用一條邊，如下圖藍(lán)線所示：

　　在 3 維空間中，如果要用立方體占滿空間，是不是也和 2 維空間類似呢？

　　想象一下，如果像下圖那樣在空間中隨便放入幾個(gè)立方體，由此展開填滿整個(gè)空間，那么唯一的辦法就是讓接上的立方體共用藍(lán)色的面。

　　2 維、3 維皆如此，更高維度的空間會怎樣？

　　1930 年，德國數(shù)學(xué)家凱勒猜測，如果用n維立方體填滿無限空間，則立方體之間必然會出現(xiàn)“面對面”，對于任意維度都成立。

　　這便是凱勒猜想。

　　但數(shù)學(xué)猜想不能僅靠直覺，必須有嚴(yán)格的證明。90 年來，數(shù)學(xué)家一直不懈努力。

1940 年，數(shù)學(xué)家 Perron 證明了凱勒猜想在 1 到 6 維空間是正確的。

1992 年，另外兩位數(shù)學(xué)家 Lagarias 和 Shor 證明，凱勒猜想在 10 維空間上是錯(cuò)誤的。

　　（注：這位 Shor 就是那個(gè)提出用量子計(jì)算機(jī)求解質(zhì)因數(shù)分解的Shor 算法的數(shù)學(xué)家。）

　　非常不幸，凱勒猜想竟然是錯(cuò)的！然而問題并沒有到此結(jié)束。

　　還有 3 個(gè)維度沒有解決呢！在 7 維、8 維、9 維三個(gè)維度空間中，凱勒猜想是否成立？

　　只要解決這三個(gè)維度，纏繞數(shù)學(xué)家?guī)资甑膯栴}就徹底搞定了。

　　數(shù)學(xué)論證表明，如果凱勒猜想在n維空間上是錯(cuò)的，那么它在比n更高的維度上也一定是錯(cuò)的。

　　2002 年，數(shù)學(xué)家 Mackey 已證明，凱勒猜想在 8 維空間不成立，因此在 9 維空間也不成立。

　　至此，7 維空間成為唯一的難題。

　　△證明 8 維空間凱勒猜想錯(cuò)誤的 CMU 教授 Mackey

　　證明方法的改進(jìn)

　　可能你已經(jīng)發(fā)現(xiàn)，從上世紀(jì) 90 年代以來，凱勒猜想的證明速度大大加快，數(shù)學(xué)家只用了 10 年時(shí)間就把問題縮小到三個(gè)維度。

　　這主要得益于兩位數(shù)學(xué)家的貢獻(xiàn)。

　　當(dāng)年，Perron 求解 1 到 6 維時(shí)，沒有特殊的捷徑。而到 1990 年，凱勒猜想的證明方法發(fā)生了巨大的變化。

　　數(shù)學(xué)家 Corrádi 和 Szabó提出了一種新的思路，把原來無限空間的問題變成有限的、離散的問題，也讓計(jì)算機(jī)解決凱勒猜想成為可能。

　　他們巧妙地把凱勒猜想變成了圖論問題，就是構(gòu)造所謂的凱勒圖（Keller Graph），而圖論正是計(jì)算機(jī)所擅長的。

　　在這種方法的指導(dǎo)下，Lagarias 和 Shor 兩人很快在 2 年后就證明了 10 維空間的情況：凱勒猜想不成立。又過了 10 年，Mackey 證明，凱勒猜想在 8 維空間不成立。

　　那么，凱勒圖究竟是什么，它為什么能夠加速凱勒猜想的證明？

　　構(gòu)造“凱勒圖”

　　首先，我們從最簡單的 2 維情況說起。

　　現(xiàn)在，我們有一種牌，牌上畫著兩個(gè)有顏色的點(diǎn)。兩個(gè)點(diǎn)是有順序的，不能調(diào)換。比如，1 黑 2 白≠1 白 2 黑。

　　兩個(gè)點(diǎn)總共可以涂 4 種顏色，顏色分成 2 對：紅色對綠色、白色對黑色。

　　數(shù)學(xué)家已經(jīng)證明，分配給點(diǎn)的顏色相當(dāng)于正方形在空間中的坐標(biāo)。兩張牌的顏色是否配對表示兩個(gè)正方形的相對位置。

　　點(diǎn)的顏色與正方形的具體關(guān)系是這樣的：

　　1、兩對點(diǎn)完全相同，表示兩個(gè)正方形完全重疊

　　2、兩對點(diǎn)顏色都不同，且顏色都不配對，表示兩個(gè)正方形有部分重疊

　　3、一對點(diǎn)顏色相同，另一對點(diǎn)顏色配對，表示兩個(gè)正方形共用一個(gè)邊

　　4、一對點(diǎn)顏色不同，另一對點(diǎn)顏色配對，表示兩個(gè)正方形的邊相互接觸但不重合

　　2 個(gè)點(diǎn)的凱勒圖，要用 2 對顏色去填充牌面，總共有 16 種情況。

　　然后我們把這 16 張牌擺在桌上，只有符合前面條件4的兩張牌，才用線將二者連起來。這樣就構(gòu)成了一張“凱勒圖”。

　　包含 16 張牌的凱勒圖就描繪了正方形填補(bǔ)平面的所有可能。

　　如果 2 維空間中凱勒猜想不成立，那么我們肯定能找到 4 個(gè)正方形，它們之間沒有共用的邊，但是能夠無縫隙填在一起。然后在屏幕上無限復(fù)制這 4 個(gè)正方形，就能填滿整個(gè)屏幕。

　　實(shí)際上并不可能。如果按此操作，只會得到有著無數(shù)孔隙（下圖紫色部分）的填充方式。

　　對應(yīng)到凱勒圖中，就是找在圖中找到 4 張牌，它們兩兩之間都有連線。（在數(shù)學(xué)里，這叫做完全圖。）

　　顯然，在 2 維問題的凱勒圖中，我們找不到這樣的 4 張牌。（可以自己去上面的凱勒圖中找找看。）

　　這樣，我們把就把n維立方體以及位移s與牌的點(diǎn)數(shù)n、顏色對數(shù)s聯(lián)系起來。

　　作為更一般的規(guī)則，如果要證明n維凱勒猜想是錯(cuò)的，就要在對應(yīng)的凱勒圖中找到2ⁿ張牌，且這些牌兩兩相連。

　　正因?yàn)槟阏也坏?4 個(gè)張牌組成的完全圖，所以 2 維空間的凱勒猜想是對的。

　　為了在 3 維空間中證明凱勒猜想，可以使用 216 張牌，每張牌上 3 個(gè)點(diǎn)，并可以使用 3 對顏色（這一點(diǎn)相對靈活）。然后，我們需要尋找2³=8 張牌 ，它們兩兩之間都有連線，但還是找不到。

　　到了 8 維空間中，我們總算可以找到符合條件的 256 張牌，所以 8 維空間的凱勒猜想是錯(cuò)的。

　　△8 維空間中的一個(gè)反例（一個(gè)凱勒圖的完全子圖）

　　接下來的事情就是在 7 維空間對應(yīng)的凱勒圖上尋找完全子圖。然而這個(gè)問題卻從 8 維問題解決后被擱置了 17 年。

　　根據(jù)前面的說明，求解 8 維空間和 10 維空間的凱勒猜想，要尋找2⁸=256 和2¹⁰=1024 張牌的子圖，而 7 維空間只要尋找2⁷=128 張牌的子圖。

　　后者的難度似乎更小，7 維空間的問題應(yīng)該更簡單啊！其實(shí)不然。

　　因?yàn)椋瑥哪撤N意義上說，8 維和 10 維可以“分解”為容易計(jì)算的較低維度，但 7 維不行。

　　證明了 10 維情況的 Lagarias 說：“7 維不好，因?yàn)樗琴|(zhì)數(shù)，這意味著你無法將其分解為低維。因此別無選擇，只能處理這些圖的全部組合。”

　　對于人腦來說，尋找大小為 128 的子圖是一項(xiàng)艱巨的任務(wù)，但這恰恰是計(jì)算機(jī)擅長回答的問題。

　　計(jì)算機(jī)幫忙

　　說干就干，此前證明 8 維問題的 CMU 教授 Mackey 拉上了斯坦福的數(shù)學(xué)在讀博士 Brakensiek 和專長計(jì)算機(jī)輔助證明的助理教授 Heule。

　　回憶起立項(xiàng)的那天，Mackey 說，Brakensiek 是真正的天才，看著他就像看著 NBA 總決賽里的詹姆斯。Brakensiek 本人確實(shí)很厲害，他曾是 2013/14 兩屆國際信息學(xué)奧賽金牌得主。

　　△論文第一作者 Brakensiek

　　言歸正傳。為了方便計(jì)算機(jī)求解，他們換了個(gè)方向來思考：

　　先設(shè)定牌上有 7 個(gè)點(diǎn)、6 種可能的顏色，按照前面的“條件4”對這些牌上色，看看能不能找到 128 種不同的填色方法。如果找不到，那么凱勒猜想成立。

　　用計(jì)算機(jī)輔助證明數(shù)學(xué)問題，還需要把它變成一系列邏輯運(yùn)算，也就是處理 01 之間的與或非關(guān)系。

　　若要求解 7 維，則總共包含 39000 個(gè)不同布爾變量（0 或1），有2³⁹⁰⁰⁰種可能性，這是一個(gè)非常非常大的數(shù)字，有 11741 位數(shù)。

　　△2 的 39000 次方（來自 Wolfram Alpha 運(yùn)算結(jié)果）

　　一臺普通電腦只能處理 324 位數(shù)種可能，離解決問題還遠(yuǎn)得很。就算交給超級計(jì)算機(jī)也不夠。

　　但是，這幾位數(shù)學(xué)家想到了排除法，只要得到結(jié)論，而不必實(shí)際檢查所有可能性。效率才是王道！

　　比如，用計(jì)算機(jī)規(guī)則給 128 張牌上色，當(dāng)你涂到第 12 張牌的時(shí)候，發(fā)現(xiàn)找不到符合條件的下一張牌了。那么所有包含這 12 張牌的排列都可以排除。

　　提升效率的另一種方式是利用對稱性。如果已經(jīng)驗(yàn)證了某種排列不可能，那與之對稱的所有情況都可以排除。

　　通過這兩種方法，他們把搜索空間縮小到 10 億（2³⁰）。這樣一來，用計(jì)算機(jī)搜索變成了可能。

　　最終，他們僅計(jì)算了半個(gè)小時(shí)，便有了答案。

　　計(jì)算機(jī)沒有找到符合條件的 128 張牌，所以 7 維空間的凱勒猜想確實(shí)成立。

　　實(shí)際上，計(jì)算機(jī)提供的不僅僅是一個(gè)答案，證明的內(nèi)容多達(dá)200GB。4 位論文作者將證明送入計(jì)算機(jī)的證明檢查器，確認(rèn)了它的可靠性。

　　解決了凱勒猜想后，Heule 的下一個(gè)目標(biāo)是用計(jì)算機(jī)證明數(shù)學(xué)里“最簡單的不可能問題”——3n+1 猜想，去年陶哲軒已經(jīng)“幾乎”解決了這個(gè)問題，現(xiàn)在可能只差一步之遙了。

　　參考鏈接：
　　https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/

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

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

　　論文地址：

　　https://arxiv.org/abs/1910.03740

　　源代碼：

　　https://github.com/marijnheule/Keller-encode

　　—完—

總結(jié)

以上是生活随笔為你收集整理的困扰数学家90年的猜想，被计算机搜索30分钟解决了的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。