新证明解决了关于互连网络数十年来的争论
摘要
20世纪80年代末，数学家Peter Sarnak和Noga Alon就最优扩展图（拉马努金图）在所有正则图中的比例打了一个赌。Sarnak认为拉马努金图极为稀少，Alon则认为几乎所有正则图都是拉马努金图。经过数十年的研究，哈佛大学的Horng-Tzer Yau及其合作者通过将随机矩阵普适性猜想推广到正则图的邻接矩阵，最终证明双方都错了。
核心概念及解读
拉马努金图（Ramanujan graphs）——达到Alon-Boppana界限的最优扩展图，以印度数学家拉马努金命名，具有极佳的连通性和信息传播效率：
Alon-Boppana界限——正则图第二大特征值的理论下界，用于衡量一个图作为扩展图的最优程度：
普适性猜想（Universality conjecture）——由物理学家Wigner提出，指出不同类型随机矩阵的特征值都遵循相同的概率分布，与矩阵条目的具体随机过程无关：
邻接矩阵——用矩阵形式描述图中节点之间连接关系的数学工具，其特征值可揭示图的结构性质：
扩展图（Expander graphs）——一类高度连通且稀疏的图结构，在计算机科学、网络设计和纠错编码等领域有广泛应用：
New Proof Settles Decades-Old Bet About Connected Networks | Quanta Magazine
作者 Leila Sloman
2025年4月18日
根据数学界的传说，Peter Sarnak 和 Noga Alon 在20世纪80年代末对最优图打了个赌。现在证明他们都错了。
Michele Sclafani 为 Quanta Magazine 供图
在20世纪80年代末，数学家 Peter Sarnak（左）和 Noga Alon 就一种最优图的普遍性打了个赌。结果证明他们都错了。
图片由 Peter Sarnak 和 Nurit Alon 提供
对于某些数学家——包括 Sarnak 在内——Alon-Boppana 界限是一个引人入胜的挑战。他们想知道，能否构建达到这个极限的图？
押注随机性
在 1988年发表的一篇里程碑式论文 (opens a new tab) 中，Sarnak、Alexander Lubotzky 和 Ralph Phillips 找到了方法。他们利用印度数学天才 Srinivasa Ramanujan 在数论中的一个高度技术性成果，Sarnak 和他的合作者们构造出了达到 Alon-Boppana 界限的正则图。因此，他们将这些最优扩展图称为“拉马努金图”（Ramanujan graphs）。（同年，Grigorii Margulis 使用了不同但同样高度技术性的方法 构建了其他示例 (opens a new tab)。）
普林斯顿高等研究院的 Ramon van Handel (opens a new tab) 说：“直观上，你似乎可以预料到”构造拉马努金图所涉及的近乎令人望而却步的困难。“最好的图似乎应该很难实现。”
但在数学中，难以构造的对象往往出人意料地普遍。“这是这个领域的一个普遍现象，”van Handel 说。“任何你能想象的例子都不会具有这些性质，但随机例子会。”
在花费十多年研究与随机图相关的矩阵后，Horng-Tzer Yau 解决了一个关于它们行为的重要问题。
图片由 Horng-Tzer Yau 提供
包括 Alon 在内的一些研究人员认为，这可能也适用于拉马努金图。Alon 认为，找到这些图所需的巨大努力更多地说明了人类思维的局限性，而不是图的普遍性。这种信念促成了 Alon 和 Sarnak 的打赌：Sarnak 赌，如果你收集所有正则图，其中拉马努金图的比例可以忽略不计；Alon 赌，几乎所有的都是拉马努金图。很快，关于 Alon 和 Sarnak 打赌的传言就在数学界流传开来，即使关于那个时刻的回忆各不相同。
“说实话，这更多是坊间传说，”Sarnak 承认。“我其实不记得那个具体事件了。”
几十年后，在2008年，对大量正则图及其特征值的分析表明，答案并非一清二楚 (opens a new tab)。一些图是拉马努金图，一些则不是。这使得找出确切的比例变得更加困难。在证明适用于所有（或没有）图的性质时，数学家有大量的工具可以使用。但要证明有些图是拉马努金图，有些则不是——这需要精确性，而图论家不确定这种精确性从何而来。
结果发现，在一个完全不同的数学领域，一位名叫 Horng-Tzer Yau (opens a new tab) 的研究人员正在解决这个问题。
一个“疯狂”的设想
正当图论家们努力应对2008年研究的含义时，哈佛大学教授 Yau 已经沉迷于特征值好几年了。这些特征值来自一类更广泛的矩阵，它们的条目是随机生成的——比如通过抛硬币或进行其他随机过程。Yau 想了解矩阵的特征值如何随所使用的随机过程而变化。
这个问题可以追溯到1955年，当时物理学家 Eugene Wigner 使用随机矩阵来模拟铀等重原子核的行为。通过研究这些矩阵的特征值，他希望深入了解系统的能量。Wigner 很快注意到了奇怪的事情：不同随机矩阵模型的特征值似乎都表现出相同的模式。对于任何随机矩阵，每个特征值也是随机的；选取一个值域，特征值有一定概率落在这个值域内。但似乎无论随机矩阵的条目是只有1和−1，还是可以是任意实数，其特征值落在特定值域内的概率都没有改变。
物理学家 Eugene Wigner 在他研究的各种随机系统中观察到了令人惊讶的普适行为。数学家们现在已经扩展了这种行为的范围。
橡树岭国家实验室，美国能源部
Wigner 推测，任何随机矩阵的特征值都应该始终遵循相同的概率分布。他的预测被称为 普适性猜想。
Yau 说，这个想法“太疯狂了”。“很多人不相信他所说的。”但随着时间的推移，他和其他数学家证明了普适性猜想对许多类型的随机矩阵都成立。Wigner 的观点一次又一次得到证实。
Yau 现在想看看他能将这个猜想推进多远。他说：“我一直在寻找那些能够超越我们对标准矩阵理解的问题。”
因此，在2013年，当 Sarnak 提议让 Yau 研究与随机正则图相关的矩阵的特征值时，他接受了挑战。
如果 Yau 能够证明这些特征值遵循普适性猜想，他就能知道它们的概率分布。然后他就可以利用这些信息来计算第二大特征值达到 Alon-Boppana 界限的可能性有多大。换句话说，他将能够对 Sarnak 和 Alon 关于正则图中拉马努金图比例的打赌给出明确的答案。
Yau 说：“[Sarnak] 不断地催促我，‘你能做到吗？’”
于是他便着手进行了。
几近成功
许多种类的随机矩阵，包括启发 Wigner 猜想的那些，都具有可以直接计算其特征值分布的良好性质。但邻接矩阵不具备这些性质。
大约在2015年，Yau 和他的研究生 Jiaoyang Huang (opens a new tab) 以及另外两名合作者想出了一个计划。首先，他们会使用一个随机过程稍微调整其邻接矩阵的条目，得到一个具有他们所需性质的新随机矩阵。然后他们会计算这个新矩阵的特征值分布，并证明它满足普适性猜想。最后，他们会证明他们所做的调整太小，不会影响原始矩阵的特征值——这意味着原始矩阵也满足普适性猜想。
Jiaoyang Huang 在概率论方面的研究使他能够处理数学、物理和计算机科学领域的问题。
Tong Li
2020年，在 Huang 完成研究生学业后，数学家们能够利用这种方法 将普适性猜想 (opens a new tab) 扩展到特定大小的正则图。只要一个图有足够的边，它的第二大特征值就会拥有 Wigner 几十年前研究过的相同分布。但要找出 Alon 和 Sarnak 打赌的答案，数学家们需要证明普适性猜想对所有正则图都成立，而不仅仅是部分图。
随后，在2022年秋季，一位名叫 Theo McKenzie (opens a new tab) 的博士后研究员来到哈佛，渴望了解 Huang、Yau 及其合作者为2020年的证明开发的工具。有很多东西需要赶上。“我们已经工作了很长时间，”Yau 说。
但 McKenzie “非常无畏”，加州大学伯克利分校数学家、McKenzie 的前博士导师 Nikhil Srivastava (opens a new tab) 说。“他不害怕攻克这类非常困难的问题。”
在研究了 Huang 和 Yau 的方法数月后，McKenzie 终于觉得准备好提供新的视角和帮助了。Yau 说：“你希望人们能够检查很多细节并提出许多不同的问题。有时你需要更多的人力。”
起初，这三位数学家不得不满足于部分结果。他们无法精确地执行其证明策略的第二步——计算调整后矩阵的特征值分布——来证明普适性猜想对所有正则图都成立。但他们能够证明特征值仍然满足重要的性质。这些性质强烈地表明猜想是正确的。
Theo McKenzie 是最后加入这个数学团队的成员，该团队解决了关于所谓拉马努金图性质的数十年来的争论。
Jennifer Halliday
Sarnak 说：“我知道他们离彻底解决这个问题只有一步之遥了。”
事实证明，在一个单独的项目中，Huang 已经在研究他们所需的最后一个要素。
完成闭环
Huang 一直在独立研究一组方程，称为循环方程（loop equations），它们描述了随机矩阵模型中特征值的行为。他意识到，如果他、McKenzie 和 Yau 能够证明他们的矩阵以足够高的精度满足这些方程，那将为他们提供使第二步成功所需的缺失信息。
他们做到了。经过数月艰苦的计算，他们得到了证明。所有正则图都遵循 Wigner 的普适性猜想：随机选择一个正则图，其特征值将表现出相同的已知值分布。
这也意味着三人现在知道了第二大特征值将采取的精确值分布。他们可以计算出这些特征值中达到 Alon-Boppana 界限的比例——也就是说，随机正则图中完美扩展图的比例。三十多年后，Sarnak 和 Alon 得到了他们打赌的答案。这个比例大约是69%，使得这些图既不普遍也不罕见。
Sarnak 是第一个得知这个消息的人。Huang 说：“他告诉我们，这是他收到的最好的圣诞礼物。”“所以我们觉得一切都值得。”
这一结果也表明，普适性猜想比研究人员预测的更加广泛和强大。数学家们希望继续探索这些极限，并利用新证明的技术来解决相关问题。
但与此同时，他们可以享受更多了解神秘的拉马努金图宇宙的乐趣。
Alon 说：“我们俩都有些错了。”他笑着补充说：“不过，我稍微正确一点，因为概率大于一半。”