★加星zzllrr小樂公眾號數(shù)學(xué)科普不迷路！

根據(jù)數(shù)學(xué)八卦，Peter Sarnak和Noga Alon在1980年代末押注了最優(yōu)圖?，F(xiàn)在他們都被證明是錯(cuò)的。

圖源：Michele Sclafani / Quanta Magazine

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

譯者：zzllrr小樂（數(shù)學(xué)科普公眾號）2025-4-19

一切始于一場賭注。

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

爭論的焦點(diǎn)是最優(yōu)的擴(kuò)展圖：那些盡可能地連接的擴(kuò)展圖。Sarnak提出這樣的圖很少見；他和兩位合作者很快發(fā)表了一篇論文 https://link.springer.com/article/10.1007/BF02126799 ，該論文使用數(shù)論中的復(fù)雜思想來構(gòu)建示例，他認(rèn)為任何其他結(jié)構(gòu)都同樣難以實(shí)現(xiàn)。

另一方面，Alon寄希望于隨機(jī)圖經(jīng)常顯示各種最優(yōu)性質(zhì)的事實(shí)。他認(rèn)為這些非常好的擴(kuò)展圖會很常見——如果你從一大堆可能性中隨機(jī)選擇一個(gè)圖，你幾乎可以保證它是一個(gè)最優(yōu)的擴(kuò)展圖。

如今，Alon和Sarnak是普林斯頓大學(xué)的同事。在這35年里，賭注的細(xì)節(jié)變得模糊不清。“情況不是很嚴(yán)重，”Alon回憶道?！拔覀兩踔翛]有就我們下注的內(nèi)容達(dá)成一致?！?/p>

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

擴(kuò)展的極限

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

因?yàn)閿U(kuò)展圖的邊很少，所以它們的效率非常高。但是，由于它們也是高度連通的，因此它們?nèi)匀荒軌虻钟鶟撛诘木W(wǎng)絡(luò)故障。Sarnak說，這種緊張關(guān)系“使它們既違反直覺，又非常有用”。

因此，數(shù)學(xué)家希望更好地理解它們。減少邊數(shù)和增加圖的連通性之間的這種緊張關(guān)系能推到多遠(yuǎn)？這種張力最高的特別好的擴(kuò)展圖有多常見？

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

矛盾的圖

圖由通過邊連接的節(jié)點(diǎn)組成。在一種特殊的圖稱為擴(kuò)展圖（expander）中，每個(gè)節(jié)點(diǎn)都有相對較少的邊，但圖仍然高度連通。這種特性使擴(kuò)展圖在各種應(yīng)用中非常實(shí)用。

擴(kuò)展圖

在本例中，每個(gè)節(jié)點(diǎn)只有三條邊，但連通性很高：如果你隨機(jī)沿著圖中的邊漫游，很快你就會探索完整個(gè)圖。

不是擴(kuò)展圖

此圖連通差：從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的路徑很少。

圖源：Merrill Sherman / Quanta Magazine

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

要計(jì)算此數(shù)量，你必須首先構(gòu)造一個(gè)1和0的數(shù)組，稱為鄰接矩陣（adjacency matrix）。此鄰接矩陣表示圖形中的哪些節(jié)點(diǎn)由邊連接，哪些節(jié)點(diǎn)不是。

然后，你可以使用此矩陣計(jì)算一個(gè)數(shù)字（稱為特征值eigenvalue）序列，這些數(shù)字提供有關(guān)原始圖的有用信息。例如，最大的特征值給出了連接到圖的每個(gè)節(jié)點(diǎn)的邊數(shù)。Dodziuk發(fā)現(xiàn)，第二大的特征值告訴你圖的連通程度。這個(gè)數(shù)字越小，圖形的連通性就越強(qiáng) — 使其成為更好的擴(kuò)展圖。

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

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

圖源：Peter Sarnak、Nurit Alon

對于某些數(shù)學(xué)家（其中包括Sarnak）來說，Alon-Boppana界限是一個(gè)令人著迷的挑戰(zhàn)。他們想知道，能否構(gòu)建達(dá)到這個(gè)極限的圖？

關(guān)于隨機(jī)性的對賭

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

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

“直覺上，你似乎預(yù)料到”構(gòu)建拉馬努金圖所涉及的幾乎令人望而卻步的困難，新澤西州普林斯頓高等研究所的Ramon van Handel（拉蒙·范·漢德爾）說?！翱雌饋碜詈玫膱D應(yīng)該很難實(shí)現(xiàn)?！?/p>

但在數(shù)學(xué)中，難以構(gòu)建的對象往往出奇地常見?！斑@是這個(gè)行業(yè)的普遍現(xiàn)象，”van Handel說?！澳憧梢钥梢暬娜魏问纠疾粫羞@些性質(zhì)，但一個(gè)隨機(jī)示例卻有?！?/p>

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

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

“說實(shí)話，這更像是民間八卦，”Sarnak承認(rèn)?！拔覍?shí)際上不記得那件事了?！?/p>

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

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

后來，在數(shù)學(xué)的一個(gè)完全不同的領(lǐng)域，一位名叫姚鴻澤（Horng-Tzer Yau，1959 -）的研究人員正在弄清楚這一點(diǎn)。

通過十余年研究隨機(jī)圖的矩陣，姚鴻澤（Horng-Tzer Yau）攻克了有關(guān)其性質(zhì)的一個(gè)重大難題。

“瘋狂”的愿景

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

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

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

物理學(xué)家尤金·維格納（Eugene Wigner）在他正在研究的各種隨機(jī)系統(tǒng)中觀察到令人驚訝的普遍行為。數(shù)學(xué)家現(xiàn)在已經(jīng)擴(kuò)展了這種行為的范圍。

圖源：美國能源部橡樹嶺國家實(shí)驗(yàn)室

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

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

姚鴻澤現(xiàn)在想看看他能把這個(gè)猜想推到什么程度?！拔以噲D尋找可能超出我們對一個(gè)標(biāo)準(zhǔn)矩陣的理解的問題，”他說。

因此，在2013年，當(dāng)Sarnak提議姚鴻澤研究與隨機(jī)正則圖相關(guān)的矩陣特征值時(shí)，他接受了這個(gè)挑戰(zhàn)。

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

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

所以他開始行動了。

幾乎到達(dá)

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

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

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

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

黃驕陽在概率論方面的研究使他致力于研究數(shù)學(xué)、物理和計(jì)算機(jī)科學(xué)方面的問題。

圖源：Tong Li

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

然后，在2022年秋天，一位名叫Theo McKenzie（西奧·麥肯齊）的博士后研究員來到哈佛，渴望更多地了解黃驕陽、姚鴻澤和他們的合作者為2020年證明開發(fā)的工具。還有很多工作要做?！拔覀円呀?jīng)工作了這么長時(shí)間，”姚鴻澤說。

但McKenzie“相當(dāng)無所畏懼”，加州大學(xué)伯克利分校的數(shù)學(xué)家、McKenzie的前博士生導(dǎo)師Nikhil Srivastava（尼基爾·斯里瓦斯塔瓦）說?！八慌陆鉀Q這些非常困難的問題?！?/p>

在研究了黃驕陽和姚鴻澤的方法數(shù)月后，McKenzie終于覺得準(zhǔn)備好了幫忙提供一雙全新的眼睛和雙手了。“你希望大家能夠檢查許多細(xì)節(jié)并提出許多不同的問題，”姚鴻澤說?！坝袝r(shí)你需要更多的人力。”

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

Theo McKenzie（西奧·麥肯齊）是最后一個(gè)加入數(shù)學(xué)家團(tuán)隊(duì)的人，該團(tuán)隊(duì)解決了關(guān)于所謂拉馬努金圖性質(zhì)的數(shù)十年?duì)幷摗?/p>

圖源：Jennifer Halliday

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

后來，在一個(gè)單獨(dú)的項(xiàng)目中，黃驕陽已經(jīng)在考慮他們需要的最終成分。

閉合循環(huán)

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

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

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

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

Sarnak是第一個(gè)得到這個(gè)消息的人?！八嬖V我們，這是他收到過的最好的圣誕禮物，”黃驕陽說?！八晕覀冇X得一切都是值得的。”

結(jié)果還表明，普遍性猜想比研究人員預(yù)測的更廣泛、更強(qiáng)大。數(shù)學(xué)家希望繼續(xù)突破這些極限，并使用新證明的技術(shù)來解決相關(guān)問題。

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

“我們倆打賭的都有點(diǎn)錯(cuò)了，”Alon說?！安贿^，”他笑著補(bǔ)充道，“我說得更正確一點(diǎn)，因?yàn)楦怕蚀笥谝话??！?/p>

參考資料

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

科普薦書

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

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

讓數(shù)學(xué)

更加

易學(xué)易練

易教易研

易賞易玩

易見易得

易傳易及

歡迎評論、點(diǎn)贊、在看、在聽

收藏、分享、轉(zhuǎn)載、投稿

查看原始文章出處

點(diǎn)擊zzllrr小樂

公眾號主頁

加星★

數(shù)學(xué)科普不迷路！