一切始于一场赌局。
20 世纪 80 年代末，在洛桑的一次会议上，两位数学家 Noga Alon 和 Peter Sarnak 伸开了一场友好的申辩。两东说念主那时王人在照顾由节点和边构成的齐集即图，他们绝顶想更好地聚集一种名为「扩展图」的看似矛盾的图类型，这种图的边相对较少，但仍然高度互连。
争论的焦点在于最优扩展图：那些连通性尽可能强的扩展图。Sarnak 认为这么的图很罕见，他和两位互助者很快发表了一篇论文，期骗数论中的复杂念念想来构建示例，并指出任何其他结构王人相似难以完毕。
而 Alon 则寄但愿于就舆图频繁展现出各式最优性质的事实，他认为这些极其优秀的扩展图会很常见。要是你从大批可能性中就地礼聘一个图，则险些不错保证它是一个最优扩展图。
左为 Peter Sarnak，右为 Noga Alon。
如今，Sarnak 和 Alon 是普林斯顿大学的共事。几十年来，这场赌局的细节还是变得隐约不清。「那时并不太严肃，」Alon 回忆说念，「咱们以致对赌局的本体王人见识不一。」
尽管如斯，这个传奇依然流传，它私密地教导着数学家们，究竟谁才是对的。
最近，三位数学家通过商酌物理学中一个关键时势，并将其推向极限，最终对这场赌局作念出了裁决。他们两东说念主王人错了。
论文标题： Ramanujan Property and Edge Universality of Random Regular GraphsarXiv 地址：https://arxiv.org/pdf/2412.20263
自 20 世纪 60 年代数学家开动照顾扩展图以来，它们就被用于大脑建模、统计分析和构建纠错码。由于扩展图的边数一丝，因此着力极高。同期，由于扩展图高度连通，因此仍然能够抵挡潜在的集聚故障。Sarnak 露出，这种矛盾「使得扩展图既违抗直观，又十分有效」。
因此，数学家们想要更好地聚集它们。「减少边数」和「增多图的连通性」之间的这种矛盾不错蔓延到多远？以及在张力最高的好的扩展图有多宽敞？
为了恢复这些问题，照顾东说念主员需要精确地界说扩展图。有许多设施不错作念到这一丝，其中一种是：为了将扩展图拆分红两个零丁的部分，你需要擦除许多边。另一种是：要是你沿着图的旯旮犹豫，在每一步就地礼聘场所，你很快就能探索通盘图。
下图为扩展图示例，每个节点惟一三条边，但连通性很高。要是你沿着图的边就地游走，那么探索通盘图不需要消费很万古刻。
下图为非扩展器示例，该图连通性较差，从一个节点到另一个节点的旅途很少。
1984 年，数学家 Józef Dodziuk 阐扬，扫数这些彭胀度量王人通过一个量辩论起来 —— 至少对于某些类型的图而言是如斯。在这些所谓的「正则图」中，每个节点王人有调换数目的边，这确保了通盘图的边数相对较少。因此，要使其成为扩展图，你只需阐扬它是连通的。这即是 Dodziuk 数（quantity）的着手。
要打算这个数，你必须领先构造一个由 1 和 0 构成的数组，称为相接矩阵。这个相接矩阵露出图中哪些节点通过边联接，哪些节点莫得通过边联接。
然后，你不错使用该矩阵打算一系列数字，称为特征值（eigenvalues），这些数字不错提供辩论原始图的有效信息。举例，最大的特征值给出了联接到图中每个节点的边数。Józef Dodziuk 发现，第二大特征值不错告诉你图的连通性。该数字越小，图的连通性越好 —— 这使得它成为一个更好的扩展图。
在 1988 年发表的一篇具有里程碑意旨的论文中，Sarnak、Alexander Lubotzky 和 Ralph Phillips 斯找到了设施。他们利用印度数学天才 Srinivasa Ramanujan 在数论范畴得回的一项精粹本领效果，构建了欢悦「Alon-Boppana 界限」的正则图。
因此，他们将这些最优扩展图称为「拉马努金图」（Ramanujan graphs）。（同庚，Grigorii Margulis 使用了不同但相似精粹的设施构建了其他示例。）
论文地址：https://link.springer.com/article/10.1007/BF02126799
新泽西州普林斯顿高档照顾院的 Ramon van Handel 露出：「直不雅地看，你似乎不错预感到构建拉马努金图险些难以完毕的难度。而且看起来，最优图应该十分难以完毕。」
但在数学中，难以构造的事物频频稀薄地常见。「这是数学界的宽敞时势，」van Handel 说。「任何你能联想的例子王人不会具备这些属性，但一个就地的例子却会。」
包括 Alon 在内的一些照顾东说念主员认为，拉马努金图概况也适用相似的旨趣。Alon 认为，寻找这些图所需的繁多勤快与其说是物资的丰富性，不如说更多地反应了东说念主类的念念维方式。这种信念促成 Sarnak 和 Alon 的赌局：Sarnak 打赌，要是把扫数正则图王人网罗起来，其中惟一极小一部分是拉马努金图；而 Alon 则认为险些扫数图王人是拉马努金图。
很快，对于 Sarnak 和 Alon 打赌的传闻就在社区里流传开来，尽管东说念主们对那时的牵记各不调换。「说真话，这更像是民间传奇，」Sarnak 承认说念，「我其实不牢记那件事了。」
几十年后，在 2008 年，对大批正则图过火特征值的分析标明，谜底并非一目了然。有些图相宜拉马努金定理，有些则否则。这只会让找出实在的比例变得愈加坚苦。
在阐扬一个适用于扫数图（或扫数图王人不适用）的性质时，数学家们领有丰富的器具箱。但要阐扬某些图相宜拉马努金定理，而其他图则否则，则需要精确度，而图论学家们并不细目这种精确度从何而来。
自后发现，在一个绝对不同的数学范畴，一位名叫姚鸿泽（Horng-Tzer Yau）的照顾员正在处置这个问题。在花了十多年时刻照顾与就舆图干系的矩阵之后，姚鸿泽处置了一个辩论它们举止的紧要难题。
姚鸿泽
在图论照顾者还在勤快聚集 2008 年那项照顾的意旨时，AG百家乐打闲最稳技巧哈佛大学陶冶姚鸿泽还是千里迷特征值问题好几年了。他照顾的特征值着手于更往往的一类矩阵，这些矩阵的元素是通过就地方式生成的 —— 比如抛硬币或进行其他就地历程。姚鸿泽想弄明晰：使用不同的就地历程，矩阵的特征值会若何变化。
这个问题不错顾忌到 1955 年，那时物理学家 Eugene Wigner 使用就地矩阵来模拟像铀这么重原子华夏子核的举止。他但愿通过照顾这些矩阵的特征值，来了解系统所具有的能量。
很快，Wigner 持重到一个奇怪的时势：不同的就地矩阵模子的特征值似乎王人呈现出调换的散播模式。对于任何一个就地矩阵，每个特征值自己亦然就地的 —— 你选择一个数值区间，某个特征值落在这个区间内的概率是不错打算的。但神奇的是，这种概率散播似乎与矩阵的具体构造无关：无论一个就地矩阵的元素只是由 1 和 −1 构成，如故不错是苟且实数，其特征值落入某个区间的概率王人险些不变。
Eugene Wigner
Wigner 在他照顾的各式就地系统中，不雅察到了出东说念主猜度的宽敞举止。如今，数学家们还是将这种举止的适用范围进一步拓展。
Wigner 曾揣摸，任何就地矩阵的特征值王人应驯顺调换的概率散播。这个瞻望自后被称为宽敞性揣摸。
姚鸿泽露出这个目的太过荒诞，导致许多东说念主根柢不驯服他说的是竟然。但跟着时刻推移，他和其他数学家束缚阐扬，这一揣摸在许多不同类型的就地矩阵中王人建树。一次又一次，Wigner 的表面被阐述是正确的。
姚鸿泽开动念念考，我方还能将这一揣摸鼓吹多远。他想寻找那些能冲破对圭臬矩阵聚集的问题。
于是，在 2013 年，当 Sarnak 提议让他照顾与就地正则图干系的矩阵的特征值时，他继承了这个挑战。
要是姚鸿泽能阐扬这些特征值也欢悦宽敞性揣摸，那么他就能掌捏它们的概率散播。接下来，他就不错利用这些信息来打算第二特征值达到 Alon–Boppana 界限的概率。
换句话说，他将能够为 Sarnak 和 Alon 的赌局 —— 有若干比例的正则图是拉马努金图 —— 给出一个明确谜底。
于是，他开动脱手了。
许多类型的就地矩阵，包括曾启发 Wigner 提议普适性揣摸的那些矩阵，自己具备一些风雅性质，使得东说念主们不错径直打算它们的特征值散播。然则，相接矩阵并不具备这些性质。
大要在 2015 年，姚鸿泽与他的照顾生黄骄阳（2010-201 年在清华大学交叉信息照顾院打算机科学实践班学习）以及另外两位互助者提议了一项打算。领先，他们将使用一个就地历程，对相接矩阵中的元素作念出狭窄转机，从而得到一个新的就地矩阵，这个矩阵具备他们所需的那些风雅性质。
接着，他们将打算这个新矩阵的特征值散播，并阐扬它欢悦宽敞性揣摸。
终末，他们还要阐扬，这些所作念的转机弥散小，不会影响原始相接矩阵的特征值 —— 这就意味着，原始相接矩阵也欢悦宽敞性揣摸。
黄骄阳在概率论范畴的照顾，使他涉足了数学、物理与打算机科学中的多个难题。
2020 年，黄博士毕业后，他与互助者终于能够借助这一设施，将宽敞性揣摸扩展到一定例模的正则图。只消图的边数弥散多，它的第二特征值就会呈现出几十年前 Wigner 照顾过的那种散播。但要解答 Alon 和 Sarnak 之间的赌约，只是阐扬一部分正则图还不够 —— 他们需要对扫数正则图王人阐扬这一揣摸建树。
到了 2022 年秋天，一位名叫 Theo McKenzie 的博士后照顾员来到哈佛大学，但愿真切了解黄骄阳、姚鸿泽过火互助者在 2020 年阐扬中使用的器具和设施。他有许多本体需要「补课」。「咱们还是在这个问题上钻研了很万古刻」姚鸿泽说。
但加州大学伯克利分校的数学家、McKenzie 的前博士导师 Nikhil Srivastava 露出，McKenzie 十分丧胆，他并不发怵去攻克这些十分毒手的问题。
在花了几个月时刻真切照顾黄骄阳和姚鸿泽的设施后，McKenzie 终于作念好准备，能够以新的视角和力量加入进来。「你但愿有东说念主能查抄大批细节，并提议各式不同的问题，」姚鸿泽说，「或然候，你即是需要更多东说念主手。」
一开动，这三位数学家只可得回部分截至。他们还无法精确地完成阐扬计谋中的第二步 —— 打算经过微调的矩阵的特征值散播，因此还不及以阐扬扫数正则图王人欢悦宽敞性揣摸。但他们还是能够阐扬，这些特征值仍然欢悦一些关键性质，而这些性质是非示意：这个揣摸极有可能建树。
McKenzie 是终末一位加入这个数学家团队的成员 —— 他们处置了一个对于所谓拉马努金图的争论，这个问题还是悬而未决了数十年。
「我知说念他们还是接近澈底处置这个问题的旯旮了。」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/