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

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

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

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

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

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

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

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

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

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

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

猜想十分符合直覺，但是錯(cuò)的

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

這種直覺，來自對(duì)某些事情應(yīng)該為真的深刻認(rèn)知。但有時(shí)，直覺也會(huì)誤導(dǎo)數(shù)學(xué)家，因?yàn)樵缙谧C據(jù)無法代表全貌，一個(gè)看似顯而易見的陳述，也會(huì)有某些隱藏的細(xì)微之處。

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

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

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

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

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

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

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

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

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

最后，在底部圖中選擇兩個(gè)頂點(diǎn)。

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

對(duì)于任何一個(gè)圖，你都可以計(jì)算出存在路徑的概率。

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

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

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

從直覺上看，這是個(gè)理所當(dāng)然的事。

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

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

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

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

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

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

原因就在于——上下鋪猜想是錯(cuò)的！

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

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

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

Nikita Gladkov

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

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

Igor Pak的博客

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

花了一年時(shí)間后，他以失敗告終。

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

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

Aleksandr Zimin

三人開始手動(dòng)檢查少于九個(gè)頂點(diǎn)的每一個(gè)可能的圖。在這些圖中，上下鋪猜想是成立的。

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

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

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

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

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

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

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

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

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

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

就在這時(shí)，一項(xiàng)來自英國(guó)的研究，讓事情有了轉(zhuǎn)機(jī)。

最后，不用計(jì)算機(jī)了

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

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

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

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

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

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

去年年初，他們?cè)谝黄饏⒓右魳窌?huì)之前討論過這個(gè)問題。「紅辣椒樂隊(duì)在唱歌，而我在思考這個(gè)問題，」Gladkov說道。

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

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

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

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

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

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

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

果然，數(shù)學(xué)家們?cè)谌魏螘r(shí)刻都不能想當(dāng)然地接受任何事。普林斯頓數(shù)學(xué)家Noga Alon表示：「我們必須保持懷疑，即便是那些直覺上看起來極有可能為真的事情?！?/span>

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

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

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

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

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

「這是一個(gè)哲學(xué)問題，」Alon說道，「我們?cè)撊绾慰创切﹥H在高概率下成立的證明呢？」

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

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

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

但也有一些人，則擔(dān)心這樣的未來可能會(huì)危及一些根本性的東西。「概率性證明可能會(huì)削弱我們對(duì)問題本質(zhì)的理解和直覺，」Alon認(rèn)為。

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

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

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

團(tuán)隊(duì)介紹

Nikita Gladkov

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

此前，他在俄羅斯高等經(jīng)濟(jì)學(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é)研究組，這是美國(guó)最古老的組合數(shù)學(xué)研究組之一。

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

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

Aleksandr Zimin

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

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

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

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

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