小樂數學科普：新證明解決了幾十年來關于連通網絡的賭注——譯自Quanta Magazine量子雜志

★加星zzllrr小樂公眾號數學科普不迷路！

根據數學八卦，Peter Sarnak和Noga Alon在1980年代末押注了最優圖。現在他們都被證明是錯的。

圖源：Michele Sclafani / Quanta Magazine

作者：Leila Sloman（量子雜志特約記者）2025-4-18

譯者：zzllrr小樂（數學科普公眾號）2025-4-19

一切始于一場賭注。

1980年代末，在洛桑的一次會議上，數學家Noga Alon（諾加·阿隆，1963 -）和Peter Sarnak（彼得·薩納克，1953 -）進行了一場友好的辯論。兩人都在研究稱為圖（graph）的節點和邊的集合。特別是，他們希望更好地理解一種稱為擴展圖（expander）的矛盾類型的圖，這種圖的邊相對較少，但仍然高度互連。

爭論的焦點是最優的擴展圖：那些盡可能地連接的擴展圖。Sarnak提出這樣的圖很少見；他和兩位合作者很快發表了一篇論文 https://link.springer.com/article/10.1007/BF02126799 ，該論文使用數論中的復雜思想來構建示例，他認為任何其他結構都同樣難以實現。

另一方面，Alon寄希望于隨機圖經常顯示各種最優性質的事實。他認為這些非常好的擴展圖會很常見——如果你從一大堆可能性中隨機選擇一個圖，你幾乎可以保證它是一個最優的擴展圖。

如今，Alon和Sarnak是普林斯頓大學的同事。在這35年里，賭注的細節變得模糊不清。“情況不是很嚴重，”Alon回憶道。“我們甚至沒有就我們下注的內容達成一致。”

盡管如此，這個八卦仍然存在，微妙地推動數學家們想得出誰是對的。去年12月，三位數學家通過挖掘物理學中的一個關鍵現象并將其推向極限，終于做出了裁決 https://arxiv.org/abs/2412.20263 。Alon和Sarnak都錯了。

擴展的極限

自從數學家在1960年代開始研究以來，擴展圖一直被用來對大腦進行建模 https://colab.ws/articles/10.1007%2F978-94-017-2973-4_11 、進行統計分析和構建糾錯碼——即使它們在傳輸過程中出現亂碼，也可以讀取的加密信息。

因為擴展圖的邊很少，所以它們的效率非常高。但是，由于它們也是高度連通的，因此它們仍然能夠抵御潛在的網絡故障。Sarnak說，這種緊張關系“使它們既違反直覺，又非常有用”。

因此，數學家希望更好地理解它們。減少邊數和增加圖的連通性之間的這種緊張關系能推到多遠？這種張力最高的特別好的擴展圖有多常見？

為了回答這些問題，研究人員需要精確定義擴展。有很多方法可以做到這一點。其一，為了將擴展圖拆分為兩個單獨的部分，你必須擦除許多邊。其二，如果你沿著圖的邊徘徊，在每一步中隨機選擇方向，那么用不了多久，你就會探索完整個圖。

矛盾的圖

圖由通過邊連接的節點組成。在一種特殊的圖稱為擴展圖（expander）中，每個節點都有相對較少的邊，但圖仍然高度連通。這種特性使擴展圖在各種應用中非常實用。

擴展圖

在本例中，每個節點只有三條邊，但連通性很高：如果你隨機沿著圖中的邊漫游，很快你就會探索完整個圖。

不是擴展圖

此圖連通差：從一個節點到另一個節點的路徑很少。

圖源：Merrill Sherman / Quanta Magazine

1984年，數學家Józef Dodziuk證明，所有這些擴展都通過一個量相關聯——至少對于某些類型的圖來說是這樣。在這些所謂的正則圖（regular graph）上，每個節點都有相同數量的邊。這可確保整個圖形的邊相對較少。要使它成為擴展圖，你只需證明它連接良好。這就是Dodziuk數的來源。

要計算此數量，你必須首先構造一個1和0的數組，稱為鄰接矩陣（adjacency matrix）。此鄰接矩陣表示圖形中的哪些節點由邊連接，哪些節點不是。

然后，你可以使用此矩陣計算一個數字（稱為特征值eigenvalue）序列，這些數字提供有關原始圖的有用信息。例如，最大的特征值給出了連接到圖的每個節點的邊數。Dodziuk發現，第二大的特征值告訴你圖的連通程度。這個數字越小，圖形的連通性就越強 — 使其成為更好的擴展圖。

在Dodziuk的發現之后不久，Alon和Ravi Boppana證明，如果正則圖中的每個節點都有d條邊，則第二特征值不會比2√(d?1)小得多。第二特征值接近此“Alon-Boppana界限”的正則圖是一個好的擴展圖；相對于具有相同邊數的其他正則圖，它連接良好。但是第二特征值實際上達到界限的正則圖——這種圖是可以想象到的最好的擴展圖。

在1980年代末，數學家Peter Sarnak（上）和Noga Alon（下）押注了一種最優圖的普遍性。事實證明，這兩種說法都不是正確的。

圖源：Peter Sarnak、Nurit Alon

對于某些數學家（其中包括Sarnak）來說，Alon-Boppana界限是一個令人著迷的挑戰。他們想知道，能否構建達到這個極限的圖？

關于隨機性的對賭

1988年發表的一篇具有里程碑意義的論文中 https://link.springer.com/article/10.1007/BF02126799 ，Sarnak、Alexander Lubotzky和Ralph Phillips想出了如何做到這一點。利用印度數學天才Srinivasa Ramanujan（斯里尼瓦瑟·拉馬努金，1887 - 1920）在數論方面的高技術性結果，Sarnak和他的合作者制作了實現Alon-Boppana界限的正則圖。

因此，他們將這些最優擴展圖稱為“拉馬努金圖”（Ramanujan graph）。（同年，Grigorii Margulis使用不同但仍然技術性很強的方法來構建其他示例。https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=686&option_lang=eng ）

“直覺上，你似乎預料到”構建拉馬努金圖所涉及的幾乎令人望而卻步的困難，新澤西州普林斯頓高等研究所的Ramon van Handel（拉蒙·范·漢德爾）說。“看起來最好的圖應該很難實現。”

但在數學中，難以構建的對象往往出奇地常見。“這是這個行業的普遍現象，”van Handel說。“你可以可視化的任何示例都不會有這些性質，但一個隨機示例卻有。”

包括Alon在內的一些研究人員認為，這同樣可能適用于拉馬努金圖。Alon認為，找到這些圖所需的艱巨努力更多地說明了人類的思想并不豐饒。這種信念導致了 Alon和Sarnak的賭注：

Sarnak打賭，如果你收集所有正則圖，拉馬努金圖的比例可以忽略不計；Alon打賭，那些幾乎都是拉馬努金圖。很快，關于Alon和Sarnak打賭的傳言在社區中流傳，即使當時的記憶有所不同。

“說實話，這更像是民間八卦，”Sarnak承認。“我實際上不記得那件事了。”

幾十年后的2008年，對大量正則圖及其特征值的分析表明，答案并不明朗 https://projecteuclid.org/journals/experimental-mathematics/volume-17/issue-2/The-Distribution-of-the-Largest-Nontrivial-Eigenvalues-in-Families-of/em/1227118974.full 。有些圖是拉馬努金圖，有些不是。這讓弄清楚確切的比例更加令人困惑。當證明一個適用（或都不適用）于所有圖的性質時，數學家們有一個可以求助的大型工具包。

但是要證明一些圖是拉馬努金，而另一些不是——這需要精度，圖論學家不確定這種精度從何而來。

后來，在數學的一個完全不同的領域，一位名叫姚鴻澤（Horng-Tzer Yau，1959 -）的研究人員正在弄清楚這一點。

通過十余年研究隨機圖的矩陣，姚鴻澤（Horng-Tzer Yau）攻克了有關其性質的一個重大難題。

“瘋狂”的愿景

當圖論學家努力思考2008年研究的含義時，哈佛大學教授姚鴻澤對特征值的癡迷已經有幾年了。這些特征值來自更廣泛的矩陣類，其元素是隨機生成的 — 例如，通過拋硬幣或執行其他一些隨機過程。姚鴻澤想了解矩陣的特征值如何根據你使用的隨機過程而變化。

這個問題可以追溯到1955年，當時物理學家Eugene Wigner（尤金·維格納，1902 - 1995）使用隨機矩陣對鈾等重原子中的原子核行為進行建模。通過研究這些矩陣的特征值，他希望深入了解該系統有多少能量。

Wigner很快就注意到了一些奇怪的事情：不同隨機矩陣模型的特征值似乎都表現出相同的模式。對于任何隨機矩陣，每個特征值也是隨機的；選擇一個值域，它有一定的概率落在該范圍內。但是，如果隨機矩陣僅由1和-1組成，或者它的元素可以是任何實數，這些似乎并不重要。在每種情況下，其特征值落在特定值范圍內的概率都沒有改變。

物理學家尤金·維格納（Eugene Wigner）在他正在研究的各種隨機系統中觀察到令人驚訝的普遍行為。數學家現在已經擴展了這種行為的范圍。

圖源：美國能源部橡樹嶺國家實驗室

Wigner推測，任何隨機矩陣的特征值都應該始終服從相同的概率分布。他的預測被稱為普遍性猜想（universality conjecture）。

這個想法很“瘋狂”，姚鴻澤說。“很多人不相信他說的話。”但隨著時間的推移，他和其他數學家證明了普遍性猜想適用于許多種類的隨機矩陣。一次又一次，Wigner被證明是正確的。

姚鴻澤現在想看看他能把這個猜想推到什么程度。“我試圖尋找可能超出我們對一個標準矩陣的理解的問題，”他說。

因此，在2013年，當Sarnak提議姚鴻澤研究與隨機正則圖相關的矩陣特征值時，他接受了這個挑戰。

如果姚鴻澤能夠證明這些特征值服從普遍性猜想，他就會知道它們的概率分布。然后，他可以使用該信息來計算第二特征值達到Alon-Boppana界限的可能性。換句話說，他將能夠對Sarnak和Alon關于正則圖中拉馬努金圖的占比賭注給出明確的答案。

“[Sarnak]一直戳我，'你能做到嗎？'”姚鴻澤說。

所以他開始行動了。

幾乎到達

許多種類的隨機矩陣，包括激發Wigner猜想的隨機矩陣，都具有良好的性質，可以直接計算其特征值的分布。但是鄰接矩陣不具有這些性質。

2015年左右，姚鴻澤和他的研究生黃驕陽以及另外兩名合作者提出了一個計劃。首先，他們將使用一種隨機過程稍微調整鄰接矩陣中的元素，得到一個表現出他們需要的性質的新隨機矩陣。

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

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

黃驕陽在概率論方面的研究使他致力于研究數學、物理和計算機科學方面的問題。

圖源：Tong Li

2020年，黃驕陽研究生畢業后，數學家們能夠使用這種方法將普遍性猜想擴展到一定大小的正則圖 https://link.springer.com/article/10.1007/s00039-020-00538-0 。只要圖有足夠的邊，它的第二特征值就會具有與Wigner幾十年前研究的相同的分布。但要找出 Alon和Sarnak賭注的答案，數學家需要證明所有正則圖的普遍性猜想，而不僅僅是一些。

然后，在2022年秋天，一位名叫Theo McKenzie（西奧·麥肯齊）的博士后研究員來到哈佛，渴望更多地了解黃驕陽、姚鴻澤和他們的合作者為2020年證明開發的工具。還有很多工作要做。“我們已經工作了這么長時間，”姚鴻澤說。

但McKenzie“相當無所畏懼”，加州大學伯克利分校的數學家、McKenzie的前博士生導師Nikhil Srivastava（尼基爾·斯里瓦斯塔瓦）說。“他不怕解決這些非常困難的問題。”

在研究了黃驕陽和姚鴻澤的方法數月后，McKenzie終于覺得準備好了幫忙提供一雙全新的眼睛和雙手了。“你希望大家能夠檢查許多細節并提出許多不同的問題，”姚鴻澤說。“有時你需要更多的人力。”

起初，這三位數學家不得不接受部分結果。他們無法執行證明策略的第二步 — 計算調整后的矩陣的特征值分布 — 精確到足以證明所有正則圖的普遍性猜想。但他們能夠證明特征值仍然滿足重要的性質。這些特性強烈表明猜想是正確的。

Theo McKenzie（西奧·麥肯齊）是最后一個加入數學家團隊的人，該團隊解決了關于所謂拉馬努金圖性質的數十年爭論。

圖源：Jennifer Halliday

“我知道他們正處于解決這個問題的邊緣，”Sarnak說。

后來，在一個單獨的項目中，黃驕陽已經在考慮他們需要的最終成分。

閉合循環

黃驕陽一直在獨立研究一組循環方程（loop equations），這些方程描述隨機矩陣模型中特征值的行為。他意識到，如果他、McKenzie和姚鴻澤能夠證明他們的矩陣以足夠高的準確度滿足這些方程，那么他們將獲得所需的缺失信息，以讓他們進行第二步工作。

他們就是這樣做的。經過幾個月的艱苦計算，他們得到了證明。所有正則圖都遵循Wigner的普遍性猜想：隨機選擇一個正則圖，其特征值將表現出相同的已知值分布。

這也意味著這三人組現在知道第二特征值取值的精確分布。他們可以計算這些特征值中有多少部分達到Alon-Boppana界限，即隨機正則圖的哪一部分是完美擴展圖。

三十多年后，Sarnak和Alon找到了他們賭注的答案。結果證明這個比例約為69%，這使得這些圖既不常見也不罕見。

Sarnak是第一個得到這個消息的人。“他告訴我們，這是他收到過的最好的圣誕禮物，”黃驕陽說。“所以我們覺得一切都是值得的。”

結果還表明，普遍性猜想比研究人員預測的更廣泛、更強大。數學家希望繼續突破這些極限，并使用新證明的技術來解決相關問題。

但與此同時，他們可以享受更多地了解難以捉摸的拉馬努金圖宇宙的樂趣。

“我們倆打賭的都有點錯了，”Alon說。“不過，”他笑著補充道，“我說得更正確一點，因為概率大于一半。”

參考資料

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

https://link.springer.com/article/10.1007/BF02126799

https://arxiv.org/abs/2412.20263

https://colab.ws/articles/10.1007%2F978-94-017-2973-4_11

https://link.springer.com/article/10.1007/BF02126799

https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=686&option_lang=eng

https://projecteuclid.org/journals/experimental-mathematics/volume-17/issue-2/The-Distribution-of-the-Largest-Nontrivial-Eigenvalues-in-Families-of/em/1227118974.full

https://link.springer.com/article/10.1007/s00039-020-00538-0

科普薦書

【更多讀者好評數學書單推薦、數學科普作家自薦、出版社書單推薦通道已陸續打開，敬請期待】

·開放 · 友好 · 多元 · 普適 · 守拙·

讓數學

更加

易學易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點贊、在看、在聽

收藏、分享、轉載、投稿

查看原始文章出處

點擊zzllrr小樂

公眾號主頁

加星★

數學科普不迷路！