這5個數學猜想最早在30年前提出，如今AI證明它們都錯了

編譯 | 琰琰

編輯 | 青暮

近日，以色列特拉維夫大學研究團隊在預印論文庫提交了一篇名為“Constructions in combinatorics via neural networks“的論文，在這篇論文中，研究人員透過機器學習演算法證偽了圖論（Graph Theory）領域的5個數學猜想。

圖論是數學領域的一個重要分支，存在著大量長期無法證實或證偽的數學猜想。論文一作Adam Zsolt Wagner表示，“數學家認為這些猜想是正確的，但無法證明它們，我們嘗試使用AI演算法來尋找一些示例，發現這些示例將反駁圖論中一些長期存在的猜想”。

要證偽一個數學猜想雖然只需要提出一個反例，但不一定是件容易的事情。比如近期被證偽的單位猜想，從提出到被證偽，相隔了80年的時間。

論文地址：https：//arxiv。org/pdf/2104。14516。pdf

這些猜想包括：

1、關於圖的最大特徵值和匹配數之和的猜想，由M。 Aouchiche 和 P。 Hansen在論文“A survey of automated conjectures in spectral graph theory”中提出，論文發表於2010年。

2、Aouchiche–Hansen提出的關於圖的距離譜和鄰近性的猜想，由M。 Aouchiche 和 P。 Hansen在論文“Proximity， remoteness and distance eigenvalues of a graph”中提出，論文發表於2016年。

3、K。 L。 Collins在論文“On a conjecture of Graham and Lovasz about distance matrices”（發表於1989年）中提出的猜想，作者透過證明樹的鄰接多項式和距離多項式的係數序列的峰值可以相距很遠反駁了這個猜想。

4、L。 Hogben and C。 Reinhart在論文“Spectra of variants of distance matrices of graphs and digraphs： a survey”（發表於2021年）中提出的猜想，作者證明了在距離拉普拉斯運算元的餘譜下，圖的傳輸正則性不保持，從而反駁了這個猜想。

5、J。 Aaronson， C。 Groenland， A。 Grzesik， B。 Kielak，和 T。 Johnston在論文“Exact hyperplane covers for subsets of the hypercube”（發表於2020年）中提出的猜想，其提出可以用很少的超平面覆蓋超立方體的某些子集。

交叉熵方法

計算機輔助證明在數學猜想中有著悠久的歷史，如Appel和Haken在1976年證明了四色定理，Hales在1998年證明了開普勒猜想。近幾年，隨著人工智慧技術不斷取得新突破，機器學習演算法，尤其是強化學習逐漸成為數學家們普遍使用的科學工具之一。

在最新的研究中，基於強化學習的AI已經能夠在Atari遊戲中達到超過人類的水平。這些研究成果，引起了作者的思考：如果不為演算法提供任何關於問題的先驗知識，它是否可以在組合數學和圖論中發現證實或證偽猜想的反例？

在強化學習領域，深度Q網路及其變體，如Double Deep Q-Networks和Dueling Deep Q-Networks已經取得了廣泛成功。

這些演算法適合小動作空間問題，對於圖論問題都是不錯的選擇。作者表示，在經過嘗試後，他們發現這些方法在稀疏獎勵設定環節需要很長時間的訓練。雖然該問題可以得到有效的解決，如在sessions 期間給予某種人工獎勵來指導agent，但這樣做會引入其它問題，或者在不知情的下影響反駁猜想的目標。

因此，在有限的計算資源下，作者發現一種名為深度交叉熵（ deep cross-entropy）方法的演算法更為成功。雖然該演算法不如上述深度Q網路先進，但它具有很好的收斂性，而且對選擇合適的超引數的敏感性要低得多。

下面來簡單介紹一下如何應用交叉熵方法來尋找結構。

在交叉熵（deep cross-entropy）方法中，神經網路只學習預測給定狀態下最佳的移動路徑，而不學習狀態或狀態-動作下的值函式。給定任意一個狀態作為神經網路的輸入，然後輸出該狀態下所有可能移動的機率分佈，機率最高的代表最佳路徑。

用神經網路生成如下結構，首先要求它預測最好的第一個字元應該是什麼，然後輸出是字元表上的機率分佈，從中隨機抽取一個元素，並將其反饋到網路中，詢問第二個字元的最佳值是多少。

每次迭代都會按照上述方法生成大量的隨機sessions（構造）。計算每個獎勵，然後扔掉除了y的最高值。接下來再讓神經網路從剩下的sessions中學習，這意味著稍微調整一下神經網路的權重，使其更有可能輸出在效能最好的sessions中使用的移動路徑。這樣做的目的是加強我們的神經網路，以執行那些導致良好獎勵的行動。

猜想1：關於圖的匹配值與最大特徵值之和

猜想1：設G是n≥ 3個頂點的連通圖，λ_1是最大特徵值和是匹配數，那麼它們滿足不等式：

該猜想最初透過使用AutoGraphiX被證實，AutoGraphiX是一種可以用來自動查詢各種圖形引數之間關係的軟體。後來被Stevanovi（n=600）推翻。在本文中，作者透過交叉熵方法找到了一個更小的顯性反例，如下：

當n=19，獎勵函式為λ_1 + 時，每個迭代中前10% sessions的平均獎勵變化情況：

值得注意的是，它對n≤ 18都是正確的，最小反例是n=19。

如圖4所示，它有最大的特徵值√ 10和匹配數2，所以λ_1 + ≈ 5。16 < 5。24 ≈ √（ 19 1）+1。

圖3顯示了最佳sessions是如何隨著迭代次數的增加而變化的。雖然有明顯的 run-to-run的變化，但通常需要幾個小時才能在平均PC上的程式找到反例。

很容易看出樹狀圖是上述猜想最佳反例之一。事實上，給定一個具有最大匹配數M的圖G，可以在不將圖斷開的情況下從E（G）\M中重複刪除邊。這樣做不會改變（G）但是減小了最大特徵值。有趣的是，如圖3所示，網路迅速發現了樹狀圖是最好的，然後它開始減小直徑並收斂到圖4中的圖形。

猜想2：關於圖的鄰近特徵值和距離特徵值

猜想2：由於Auchiche–Hansen提出。設G是n≥4個頂點的連通圖，直徑為D，接近度為π，距離譜為1≥ 。。。 ≥ n，那麼它們滿足不等式：

駁斥該猜想的策略與上述猜想完全相同，唯一的變化將是改變獎勵函式。當n=30時訓練神經網路可得到下圖：

對於n=30，上圖可能不是最優的：當我們中止演算法時，最佳圖仍然在變化。之所以選擇終止學習過程，是因為在這個階段，迭代前10%的每個圖基本上都有相同的結構：一條長路徑，中間有一個交點，其鄰域被劃分為不相交的區域，唯一不同的是這些區域的規模。

給定這些資訊，可以簡單地增加頂點的數量並改變這個構造中的區域大小，直到最終找到一個反例，如圖6所示：

這個反例是在13個頂點上取一條路徑，並將n個懸垂頂點附加到與其中相鄰頂點來構造的。這幅圖的直徑為12，經計算機驗證，只要n≥ 190，它滿足π + 8<0。這種圖被稱為雙尾彗星，已被證明在給定階數和直徑的樹類上最小化接近度，它可以證明

不一定總是正的。從有限的計算機實驗來看，203個頂點上的圖接近該猜想的最小反例，這似乎是合理的。

猜想3：關於樹和鄰接多項式峰值的距離

該猜想由Collins提出，非零係數的絕對值序列構成單峰序列，其峰值與CPD（T）的歸一化係數的峰值位於同一位置。其中CPD（T）為樹狀圖T的距離矩陣的特徵多項式。

這裡作者只關注峰值的位置，一旦知道了極值的近似情況，證明如下定理就可以有力地駁斥Collins的猜想。

該定理表明，即使假設兩個序列有許多非零項，兩個峰值也可能相距很遠，這避免了m（T）在何時很小的問題。

第四個猜想

關於各種圖矩陣的譜，主要考慮：圖的哪些資訊可以從這樣一個矩陣譜中恢復？作者重點討論了G的拉普拉斯（Laplacian）距離，用DL（G）表示。

這個問題由來已久，要了解關於這個問題的廣泛研究概況，可參見L。 Hogben 和 C。 Reinhart發表的論文“Spectra of variants of distance matrices of graphs and digraphs： a survey”。在這項研究中，Hogben和Reinhart非常重視透射正則圖的譜特性——事實上，如他們調查中的表7。2所示，自然圖特性不知是否被DL共譜所保留。

本篇論文主要是透過顯示DL餘譜不保持傳輸規律來填補這一研究空白。

得到的結構並不是唯一的，有許多不同的方法可以設計一個獎勵函式，與交叉熵方法一起使用產生如下一對共譜圖。在之前的實驗中，獎勵函式的表現不是很好，最後在一次偶然運算中，演算法發現了一個結構。這聽起來是一種偶然，也很有可能其他演算法更適合這個問題。