選自 quantamagazine

作者：Leila Sloman

機器之心編譯

一切始于一場賭局。

20 世紀 80 年代末，在洛桑的一次會議上，兩位數學家 Noga Alon 和 Peter Sarnak 展開了一場友好的辯論。兩人當時都在研究由節(jié)點和邊組成的集合即圖，他們特別想更好地理解一種名為「擴展圖」的看似矛盾的圖類型，這種圖的邊相對較少，但仍然高度互連。

爭論的焦點在于最優(yōu)擴展圖：那些連通性盡可能強的擴展圖。Sarnak 認為這樣的圖很少見，他和兩位合作者很快發(fā)表了一篇論文，運用數論中的復雜思想來構建示例，并指出任何其他結構都同樣難以實現。

而 Alon 則寄希望于隨機圖通常展現出各種最優(yōu)性質的事實，他認為這些極其優(yōu)秀的擴展圖會很常見。如果你從大量可能性中隨機選擇一個圖，則幾乎可以保證它是一個最優(yōu)擴展圖。

左為 Peter Sarnak，右為 Noga Alon。

如今，Sarnak 和 Alon 是普林斯頓大學的同事。幾十年來，這場賭局的細節(jié)已經變得模糊不清。「當時并不太嚴肅，」Alon 回憶道，「我們甚至對賭局的內容都意見不一。」

盡管如此，這個傳說依然流傳，它微妙地提醒著數學家們，究竟誰才是對的。

最近，三位數學家通過探究物理學中一個關鍵現象，并將其推向極限，最終對這場賭局做出了裁決。他們兩人都錯了。

• 論文標題： Ramanujan Property and Edge Universality of Random Regular Graphs
• arXiv 地址：https://arxiv.org/pdf/2412.20263

擴展的極限

自 20 世紀 60 年代數學家開始研究擴展圖以來，它們就被用于大腦建模、統(tǒng)計分析和構建糾錯碼。由于擴展圖的邊數極少，因此效率極高。同時，由于擴展圖高度連通，因此仍然能夠抵御潛在的網絡故障。Sarnak 表示，這種矛盾「使得擴展圖既違反直覺，又非常有用」。

因此，數學家們想要更好地理解它們。「減少邊數」和「增加圖的連通性」之間的這種矛盾可以延伸到多遠？以及在張力最高的好的擴展圖有多普遍？

為了回答這些問題，研究人員需要精確地定義擴展圖。有很多方法可以做到這一點，其中一種是：為了將擴展圖拆分成兩個獨立的部分，你需要擦除許多邊。另一種是：如果你沿著圖的邊緣徘徊，在每一步隨機選擇方向，你很快就能探索整個圖。

下圖為擴展圖示例，每個節(jié)點只有三條邊，但連通性很高。如果你沿著圖的邊隨機游走，那么探索整個圖不需要花費很長時間。

下圖為非擴展器示例，該圖連通性較差，從一個節(jié)點到另一個節(jié)點的路徑很少。

1984 年，數學家 Józef Dodziuk 證明，所有這些擴張度量都通過一個量聯(lián)系起來 —— 至少對于某些類型的圖而言是如此。在這些所謂的「正則圖」中，每個節(jié)點都有相同數量的邊，這確保了整個圖的邊數相對較少。因此，要使其成為擴展圖，你只需證明它是連通的。這就是 Dodziuk 數（quantity）的來源。

要計算這個數，你必須首先構造一個由 1 和 0 組成的數組，稱為鄰接矩陣。這個鄰接矩陣表示圖中哪些節(jié)點通過邊連接，哪些節(jié)點沒有通過邊連接。

然后，你可以使用該矩陣計算一系列數字，稱為特征值（eigenvalues），這些數字可以提供有關原始圖的有用信息。例如，最大的特征值給出了連接到圖中每個節(jié)點的邊數。Józef Dodziuk 發(fā)現，第二大特征值可以告訴你圖的連通性。該數字越小，圖的連通性越好 —— 這使得它成為一個更好的擴展圖。

隨機性賭博

在 1988 年發(fā)表的一篇具有里程碑意義的論文中，Sarnak、Alexander Lubotzky 和 Ralph Phillips 斯找到了方法。他們利用印度數學天才 Srinivasa Ramanujan 在數論領域取得的一項高超技術成果，構建了滿足「Alon-Boppana 界限」的正則圖。

因此，他們將這些最優(yōu)擴展圖稱為「拉馬努金圖」（Ramanujan graphs）。（同年，Grigorii Margulis 使用了不同但同樣高超的方法構建了其他示例。）

論文地址：https://link.springer.com/article/10.1007/BF02126799

新澤西州普林斯頓高等研究院的 Ramon van Handel 表示：「直觀地看，你似乎可以預料到構建拉馬努金圖幾乎難以實現的難度。并且看起來，最優(yōu)圖應該非常難以實現。」

但在數學中，難以構造的事物往往出奇地常見。「這是數學界的普遍現象，」van Handel 說。「任何你能想象的例子都不會具備這些屬性，但一個隨機的例子卻會。」

包括 Alon 在內的一些研究人員認為，拉馬努金圖或許也適用同樣的原理。Alon 認為，尋找這些圖所需的巨大努力與其說是物質的豐富性，不如說更多地反映了人類的思維方式。這種信念促成 Sarnak 和 Alon 的賭局：Sarnak 打賭，如果把所有正則圖都收集起來，其中只有極小一部分是拉馬努金圖；而 Alon 則認為幾乎所有圖都是拉馬努金圖。

很快，關于 Sarnak 和 Alon 打賭的傳聞就在社區(qū)里流傳開來，盡管人們對當時的記憶各不相同。「說實話，這更像是民間傳說，」Sarnak 承認道，「我其實不記得那件事了。」

幾十年后，在 2008 年，對大量正則圖及其特征值的分析表明，答案并非一目了然。有些圖符合拉馬努金定理，有些則不然。這只會讓找出確切的比例變得更加艱巨。

在證明一個適用于所有圖（或所有圖都不適用）的性質時，數學家們擁有豐富的工具箱。但要證明某些圖符合拉馬努金定理，而其他圖則不然，則需要精確度，而圖論學家們并不確定這種精確度從何而來。

后來發(fā)現，在一個完全不同的數學領域，一位名叫姚鴻澤（Horng-Tzer Yau）的研究員正在解決這個問題。在花了十多年時間研究與隨機圖相關的矩陣之后，姚鴻澤解決了一個有關它們行為的重大難題。

姚鴻澤

一個「瘋狂」的想法

在圖論研究者還在努力理解 2008 年那項研究的意義時，哈佛大學教授姚鴻澤已經沉迷特征值問題好幾年了。他研究的特征值來源于更廣泛的一類矩陣，這些矩陣的元素是通過隨機方式生成的 —— 比如拋硬幣或進行其他隨機過程。姚鴻澤想弄清楚：使用不同的隨機過程，矩陣的特征值會如何變化。

這個問題可以追溯到 1955 年，當時物理學家 Eugene Wigner 使用隨機矩陣來模擬像鈾這樣重原子中原子核的行為。他希望通過研究這些矩陣的特征值，來了解系統(tǒng)所具有的能量。

很快，Wigner 注意到一個奇怪的現象：不同的隨機矩陣模型的特征值似乎都呈現出相同的分布模式。對于任何一個隨機矩陣，每個特征值本身也是隨機的 —— 你選定一個數值區(qū)間，某個特征值落在這個區(qū)間內的概率是可以計算的。但神奇的是，這種概率分布似乎與矩陣的具體構造無關：無論一個隨機矩陣的元素只是由 1 和 ?1 組成，還是可以是任意實數，其特征值落入某個區(qū)間的概率都幾乎不變。

Eugene Wigner

Wigner 在他研究的各種隨機系統(tǒng)中，觀察到了出人意料的普遍行為。如今，數學家們已經將這種行為的適用范圍進一步拓展。

Wigner 曾猜想，任何隨機矩陣的特征值都應遵循相同的概率分布。這個預測后來被稱為普遍性猜想。

姚鴻澤表示這個想法太過瘋狂，導致很多人根本不相信他說的是真的。但隨著時間推移，他和其他數學家不斷證明，這一猜想在許多不同類型的隨機矩陣中都成立。一次又一次，Wigner 的理論被證實是正確的。

姚鴻澤開始思考，自己還能將這一猜想推進多遠。他想尋找那些能突破對標準矩陣理解的問題。

于是，在 2013 年，當 Sarnak 提出讓他研究與隨機正則圖相關的矩陣的特征值時，他接受了這個挑戰(zhàn)。

如果姚鴻澤能證明這些特征值也滿足普遍性猜想，那么他就能掌握它們的概率分布。接下來，他就可以利用這些信息來計算第二特征值達到 Alon–Boppana 界限的概率。

換句話說，他將能夠為 Sarnak 和 Alon 的賭局 —— 有多少比例的正則圖是拉馬努金圖 —— 給出一個明確答案。

于是，他開始動手了。

快要成功了

許多類型的隨機矩陣，包括曾啟發(fā) Wigner 提出普適性猜想的那些矩陣，本身具備一些良好性質，使得人們可以直接計算它們的特征值分布。然而，鄰接矩陣并不具備這些性質。

大約在 2015 年，姚鴻澤與他的研究生黃驕陽（2010-201 年在清華大學交叉信息研究院計算機科學實驗班學習）以及另外兩位合作者提出了一項計劃。首先，他們將使用一個隨機過程，對鄰接矩陣中的元素做出微小調整，從而得到一個新的隨機矩陣，這個矩陣具備他們所需的那些良好性質。

接著，他們將計算這個新矩陣的特征值分布，并證明它滿足普遍性猜想。

最后，他們還要證明，這些所做的調整足夠小，不會影響原始鄰接矩陣的特征值 —— 這就意味著，原始鄰接矩陣也滿足普遍性猜想。

黃驕陽在概率論領域的研究，使他涉足了數學、物理與計算機科學中的多個難題。

2020 年，黃博士畢業(yè)后，他與合作者終于能夠借助這一方法，將普遍性猜想擴展到一定規(guī)模的正則圖。只要圖的邊數足夠多，它的第二特征值就會呈現出幾十年前 Wigner 研究過的那種分布。但要解答 Alon 和 Sarnak 之間的賭約，僅僅證明一部分正則圖還不夠 —— 他們需要對所有正則圖都證明這一猜想成立。

到了 2022 年秋天，一位名叫 Theo McKenzie 的博士后研究員來到哈佛大學，希望深入了解黃驕陽、姚鴻澤及其合作者在 2020 年證明中使用的工具和方法。他有很多內容需要「補課」。「我們已經在這個問題上鉆研了很長時間」姚鴻澤說。

但加州大學伯克利分校的數學家、McKenzie 的前博士導師 Nikhil Srivastava 表示，McKenzie 非常無畏，他并不害怕去攻克這些非常棘手的問題。

在花了幾個月時間深入研究黃驕陽和姚鴻澤的方法后，McKenzie 終于做好準備，能夠以新的視角和力量加入進來。「你希望有人能檢查大量細節(jié)，并提出各種不同的問題，」姚鴻澤說，「有時候，你就是需要更多人手。」

一開始，這三位數學家只能取得部分結果。他們還無法精準地完成證明策略中的第二步 —— 計算經過微調的矩陣的特征值分布，因此還不足以證明所有正則圖都滿足普遍性猜想。但他們已經能夠證明，這些特征值仍然滿足一些關鍵性質，而這些性質強烈暗示：這個猜想極有可能成立。

McKenzie 是最后一位加入這個數學家團隊的成員 —— 他們解決了一個關于所謂拉馬努金圖的爭論，這個問題已經懸而未決了數十年。

「我知道他們已經接近徹底解決這個問題的邊緣了。」Sarnak 說。

而事實證明，在另一項研究中，黃驕陽其實早已在嘗試他們最終所需的那一關鍵要素。

閉合循環(huán)

黃驕陽正在獨立研究一組被稱為「循環(huán)方程（loop equations）」的數學公式，這些方程描述了隨機矩陣模型中特征值的行為。他意識到，如果他、McKenzie 和姚鴻澤能夠證明他們的矩陣足夠精確地滿足這些方程，那就能補上他們在第二步推理中所缺失的信息。

他們最終確實做到了。經過數月細致入微的計算，他們完成了證明。所有的正則圖都遵循 Wigner 普遍性猜想：隨機選取一個正則圖，它的特征值將呈現出已知的那種分布形式。

這也意味著，這三位數學家現在已經知道第二特征值取值的具體分布情況。他們可以進一步計算出，有多少比例的第二特征值達到了 Alon-Boppana 界限 —— 也就是說，有多少比例的隨機正則圖是完美擴展圖。三十多年后，Sarnak 和 Alon 終于得到了他們打賭的答案。這個比例大約是 69%，這意味著這些圖既不算常見，也不算稀有。

最先得知這個消息的是 Sarnak。黃驕陽說：「他告訴我們，這是他收到過的最棒的圣誕禮物。」他笑著補充道：「所以我們覺得一切都值得了。」

這一結果也表明，普遍性猜想比研究者原先預想的更加廣泛且強大。數學家們希望繼續(xù)突破這一猜想的適用邊界，并利用這次新證明中的技術來解決相關問題。

而與此同時，他們也可以稍稍放松一下，享受在神秘莫測的拉馬努金圖宇宙中，又多掌握了一點點知識的喜悅。

「我們兩個其實都不太對，」Alon 說道。「不過，我還是稍微更接近正確一些，因為這個概率超過了一半。」他笑著補充道。

https://www.quantamagazine.org/new-proof-settles-decades-old-bet-about-connected-networks-20250418/