太平洋科技要聞

首頁 > 科技要聞 > 科技> 正文

UCLA、MIT數(shù)學(xué)家推翻39年經(jīng)典數(shù)學(xué)猜想！AI證明卡在99.99%，人類最終證偽

新智元整合編輯：太平洋科技發(fā)布于：2024-11-06 17:04

又一個看似堅固無比的數(shù)學(xué)理論，被證偽了！

最近，UCLA和MIT的研究者證偽了概率論中眾所周知的假設(shè)——「上下鋪猜想」。

上下鋪猜想（Bunkbed Conjecture）也稱為雙層床猜想，是滲透理論中的一個陳述，該領(lǐng)域處理的是在圖的邊隨機刪除后存在的路徑和簇。

猜想指出，在生成的隨機子圖中，上（下）鋪的頂點連接到上（下）鋪的某個頂點的概率，大于或等于它連接到下（上）鋪頂點——即對應(yīng)同構(gòu)頂點的概率。

用白話說就是，在同一層的兩個頂點之間的連接概率不可能小于連接不同層頂點之間的概率。這看起來確實再明顯不過了！

1985年，數(shù)學(xué)家Pieter Kasteleyn首次提出了上下鋪猜想。

然而，這個問題的猜想?yún)s讓幾代概率論學(xué)家都束手無策，一直作為一個多年未解的難題存在至今。原因在于……它是錯的！

39年后，來自UCLA和MIT的三位研究者，在使用AI工具卻多次折戟后，采用了全新的方法，發(fā)現(xiàn)了它的反例。

論文地址：https://arxiv.org/abs/2410.02545

由此，在學(xué)界似乎堅固無比的「上下鋪猜想」自然就被推翻了。

此前，大量的工作都被用在證明這個猜想的正確性上，然而這幾位研究者卻反其道而行之，經(jīng)歷多次失敗后，終于找到了反例。

猜想十分符合直覺，但是錯的

許多數(shù)學(xué)家做研究的過程，是由直覺驅(qū)動的，比如可以感知數(shù)學(xué)真理的印度數(shù)學(xué)天才拉馬努金。

這種直覺，來自對某些事情應(yīng)該為真的深刻認知。但有時，直覺也會誤導(dǎo)數(shù)學(xué)家，因為早期證據(jù)無法代表全貌，一個看似顯而易見的陳述，也會有某些隱藏的細微之處。

20世紀80年代中期，一位名叫Pieter Kasteleyn的荷蘭物理學(xué)家，想要在數(shù)學(xué)上證明一個關(guān)于液體如何在多孔固體中流動的推斷。

由此，他提出了上下鋪猜想。

要理解這個猜想，要先從一個圖開始：這個圖是由線或邊連接的點或頂點的集合。

現(xiàn)在，讓我們做一個這個圖的精確副本，然后將它直接放置在原始圖的上方。

在它們之間畫一些垂直的柱子——這些是連接底部圖上一些頂點與頂部圖上對應(yīng)頂點的額外邊。

最終，我們會得到一個類似于上下鋪的結(jié)構(gòu)。

接下來，考慮底部圖中的一條邊。

拋一次硬幣，如果是正面，就擦掉這條邊；如果是反面，就保留這條邊。對兩個圖中的每條邊重復(fù)這一過程。

最終，頂部和底部的圖會看起來不同，但它們?nèi)匀粫ㄟ^垂直的「柱子」相連。

最后，在底部圖中選擇兩個頂點。

你能沿著圖的邊從一個頂點走到另一個頂點嗎，還是這兩個頂點現(xiàn)在已經(jīng)不連通了？

對于任何一個圖，你都可以計算出存在路徑的概率。

現(xiàn)在，再來看這兩個相同的頂點，不過把其中一個替換為它在頂部圖中正上方的頂點。有沒有一條路徑，可以讓你從底部圖中的起點頂點到頂部圖中的終點頂點？

此處再復(fù)習(xí)一下：上下鋪猜想認為，在下鋪找到路徑，其概率總是大于或等于跳到上鋪找到路徑的概率。

無論從哪個圖開始，在上下鋪之間畫多少垂直柱，選擇哪些起始和終點頂點，都不影響這一事實。

從直覺上看，這是個理所當然的事。

「我們的大腦告訴我們的任何信息，都表明這個猜想應(yīng)該是正確的」，普林斯頓大學(xué)的圖論學(xué)家Maria Chudnovsky這樣說

也因此，幾十年來，數(shù)學(xué)家們一直認為這是真的。

他們的直覺告訴他們，在一個鋪位上移動應(yīng)該比在兩個鋪位之間移動更容易——從下鋪到上鋪所需的額外垂直跳躍，應(yīng)該會顯著減少可用路徑的數(shù)量。

而且，數(shù)學(xué)家們也希望它是真的。因為這些圖可以被視為流體如何在多孔材料中移動或滲透的簡化模型，就像水在海綿中移動一樣。

如果上下鋪猜想成立，物理學(xué)中被廣泛相信的流體通過固體的可能性也就成立，滲流物理學(xué)的相關(guān)問題也能被解決。

然而數(shù)學(xué)家們在39年間嘗試了無數(shù)次，卻無人能夠證明。

原因就在于——上下鋪猜想是錯的！

嘗試用神經(jīng)網(wǎng)絡(luò)證偽

并不是所有數(shù)學(xué)家都相信上下鋪猜想的真實性，加州大學(xué)洛杉磯分校的數(shù)學(xué)家Igor Pak就是其中一個。

他的研究生Nikita Gladkov表示，對于學(xué)界一直集中精力試圖證明這個猜想，自己的導(dǎo)師毫不掩飾自己的批評�！溉绻清e的呢？」

Nikita Gladkov

Igor Pak的懷疑還有一個理由：這個說法過于寬泛了。它真的適用于每個可想象的圖嗎？

「有些猜想是由實際動機驅(qū)動的，而其他猜想則是數(shù)學(xué)家的一廂情愿�！股舷落伈孪肟雌饋砀袷呛笳摺�

Igor Pak的博客

早在2022年，他就開始著手推翻它。

花了一年時間后，他以失敗告終。

Igor Pak意識到，是時候上一些暴力了！他讓學(xué)生Gladkov使用計算機，對能找到的每一個圖進行「暴力搜索」。

這就涉及到一些復(fù)雜的編程，因此Gladkov找來了大學(xué)室友、現(xiàn)MIT研究生Aleksandr Zimin，也是自己睡在下鋪的兄弟。

Aleksandr Zimin

三人開始手動檢查少于九個頂點的每一個可能的圖。在這些圖中，上下鋪猜想是成立的。

但對于更大的圖，可能的情況數(shù)量就一下子激增，他們無法再通過窮舉法，窮盡所有可能的邊緣刪除方式或路徑形成方式了。

隨后，陷入困頓的三人轉(zhuǎn)向了AI。

使用機器學(xué)習(xí)方法，他們訓(xùn)練了一個神經(jīng)網(wǎng)絡(luò)，用于生成可能更偏好向上跳躍的迂回路徑圖。

在眾多示例中他們發(fā)現(xiàn)，下鋪路徑會比上鋪替代路徑概率稍高一點。但模型始終沒有發(fā)現(xiàn)任何反例——也就是不同層路徑概率更高的情況。

還有一個問題，就是神經(jīng)網(wǎng)絡(luò)生成的每個圖過于龐大，以至于數(shù)學(xué)家們根本不可能調(diào)查拋硬幣步驟的每一個結(jié)果。

相反，團隊必須計算這些結(jié)果子集上上下路徑的概率。

他們意識到，自己可以對神經(jīng)網(wǎng)絡(luò)給出的任何反例有超過99.99%的信心，卻始終無法達到100%。

三人陷入懷疑：這種方法是否還值得？畢竟，只能達到99%而非百分百的證明，根本不足以說服數(shù)學(xué)圈，也不會被哪個著名期刊認為是足夠嚴謹?shù)淖C明。

「博士生需要的是現(xiàn)實中的工作，而不是理論上的工作，」Pak在博客上寫道。Gladkov和Zimin很快就要找工作了，最終，三人停止了這項工作。

雖然他們放棄了計算方法，卻并未停止思考這個問題。接下來的幾個月，他們拼命想做出一個不需要計算機的理論論證，卻缺少所需的所有要素。

就在這時，一項來自英國的研究，讓事情有了轉(zhuǎn)機。

最后，不用計算機了

6月，劍橋大學(xué)的Lawrence Hollom在另一種語境下，證偽了上下鋪問題的一個版本。

這個猜想的表述并非針對圖，而是研究稱為超圖（hypergraph）的數(shù)學(xué)對象。在超圖中，邊的定義不再局限于連接一對頂點，而是可以連接任意數(shù)量的頂點。

Hollom找到了這個版本猜想的一個反例。他創(chuàng)建了一個小型超圖，每條邊都連接三個頂點：

Gladkov發(fā)現(xiàn)這篇論文后意識到，這正是他們?nèi)怂枰模?/span>

他從晚上一直讀到凌晨3點，并在睡覺前給Zimin發(fā)了短信。第二天，兩個人便通了電話。就能否將Hollom的反例轉(zhuǎn)化為一個能否推翻原始上下鋪猜想的普通圖，展開了討論。

其實，這對老朋友之前就考慮過如何將超圖轉(zhuǎn)化為圖。

去年年初，他們在一起參加音樂會之前討論過這個問題�！讣t辣椒樂隊在唱歌，而我在思考這個問題，」Gladkov說道。

后來，他們開發(fā)出了可以在特定情況下將超圖轉(zhuǎn)化為圖的技術(shù)。

如今，這些技術(shù)剛好可以用來改造Hollom的超圖。

Gladkov、Pak和Zimin用龐大的點集和普通邊組成的集群，替換了超圖中的每個三頂點邊。

最終，他們得到了一個巨大的圖，由7,222個頂點和14,422條邊連接而成。

他們放棄了AI的方法后，利用構(gòu)建的理論來重新證明。

最終，他們在圖中發(fā)現(xiàn)，對于位于下路徑的點，找到上路徑的概率比找到下路徑高出1/10^6,500個百分點——雖然這個數(shù)值極小，但并不為0。

由此可以證明：上下鋪猜想是錯誤的！

果然，數(shù)學(xué)家們在任何時刻都不能想當然地接受任何事。普林斯頓數(shù)學(xué)家Noga Alon表示：「我們必須保持懷疑，即便是那些直覺上看起來極有可能為真的事情�！�

不過，Gladkov、Pak和Zimin只是找到了許多符合該猜想的小圖，但這些例子并且最終反映出——當頂點和邊的數(shù)量足夠多時，數(shù)學(xué)家可以構(gòu)造出更為復(fù)雜且反直覺的圖。

正如Hollom所言，「我們真的像我們自認為的那樣，理解所有東西嗎？」

目前，數(shù)學(xué)家們?nèi)匀幌嘈偶ぐl(fā)上下鋪猜想的關(guān)于固體中連接位置的物理命題。但他們需要找到其他方法來證明它。

與此同時，Pak表示，數(shù)學(xué)家們顯然需要更積極地討論數(shù)學(xué)證明的本質(zhì)。他們最終并未依賴有爭議的計算方法，而是以完全確定的方式推翻了猜想。

但隨著計算機和AI的研究方法在數(shù)學(xué)研究中變得越來越普遍，一些數(shù)學(xué)家也在討論：該領(lǐng)域的規(guī)范是否需要改變？

「這是一個哲學(xué)問題，」Alon說道，「我們該如何看待那些僅在高概率下成立的證明呢？」

羅格斯大學(xué)的數(shù)學(xué)家Doron Zeilberger認為，未來的數(shù)學(xué)圈會接受這樣的概率性證明。在50年內(nèi)或更短時間內(nèi)，人們就會形成全新的態(tài)度。

在論文中，他經(jīng)常把自己的計算機（Shalosh B. Ekhad）列為合著者。

「Shalosh」和「Ekhad」在希伯來語中分別意為「三」和「一」，也就是Zeilberger第一臺計算機AT&T 3B1；代指他所用到的任意一臺——從新澤西辦公室里的戴爾電腦，到偶爾在奧地利調(diào)用的超級計算機

但也有一些人，則擔心這樣的未來可能會危及一些根本性的東西�！父怕市宰C明可能會削弱我們對問題本質(zhì)的理解和直覺，」Alon認為。

最后Pak建議，鑒于這類研究日益增多，應(yīng)該為它們創(chuàng)建專門的學(xué)術(shù)期刊，以免其價值被數(shù)學(xué)界忽視。

「這個問題沒有標準答案。但我希望學(xué)術(shù)界能夠認真思考，當下一個類似的研究結(jié)果出現(xiàn)時，我們是否應(yīng)該接受它�！�

隨著AI等技術(shù)持續(xù)滲透和改變數(shù)學(xué)領(lǐng)域，這個問題只會愈發(fā)緊迫。

團隊介紹

Nikita Gladkov

Nikita Gladkov是加州大學(xué)洛杉磯分校數(shù)學(xué)系博士生，導(dǎo)師是Igor Pak。

此前，他在俄羅斯高等經(jīng)濟學(xué)院獲得數(shù)學(xué)學(xué)士學(xué)位，導(dǎo)師是Alexander Kolesnikov，并曾在Yandex數(shù)據(jù)分析學(xué)校學(xué)習(xí)數(shù)據(jù)分析。

Igor Pak

Igor Pak是加州大學(xué)洛杉磯分校數(shù)學(xué)系教授，隸屬于組合數(shù)學(xué)研究組，這是美國最古老的組合數(shù)學(xué)研究組之一。

此前，他曾在明尼蘇達大學(xué)和麻省理工學(xué)院擔任過副教授，在耶魯大學(xué)擔任過J. W. Gibbs講師，并在MSRI擔任過博士后研究員。

他于1993年在莫斯科國立大學(xué)獲得數(shù)學(xué)學(xué)士學(xué)位，1997年在哈佛大學(xué)獲得數(shù)學(xué)博士學(xué)位

Aleksandr Zimin

Aleksandr Zimin是麻省理工學(xué)院數(shù)學(xué)系博士三年級學(xué)生，在Philippe Rigollet教授的指導(dǎo)下進行研究。主要研究領(lǐng)域是最優(yōu)運輸理論。

他正在和Alexander Kolesnikov和Nikita Gladkov一起研究Monge-Kantorovich問題的廣義化，并與Aleh Tsyvinski（耶魯大學(xué)）和Job Boerma（威斯康星大學(xué)麥迪遜分校）合作研究在經(jīng)濟學(xué)中的應(yīng)用。

同時，他還對計算機科學(xué)有濃厚的興趣——曾在Yandex數(shù)據(jù)分析學(xué)校完成了為期兩年的課程，深入學(xué)習(xí)了機器學(xué)習(xí)的不同領(lǐng)域。

他具有豐富的高質(zhì)量計算機代碼編寫經(jīng)驗，從而能夠在研究中進行復(fù)雜的數(shù)值實驗。

他于2019年在莫斯科高等經(jīng)濟大學(xué)以最高榮譽獲得數(shù)學(xué)學(xué)士學(xué)位，2021年在俄羅斯斯科爾科沃科學(xué)技術(shù)研究院獲得數(shù)學(xué)與理論物理碩士學(xué)位，同年在莫斯科高等經(jīng)濟大學(xué)獲得數(shù)學(xué)碩士學(xué)位。

本文來源：新智元

上下鋪猜想證偽數(shù)學(xué)

新智元

原創(chuàng)欄目