又一个看似坚固无比的数学理论，被证伪了！
最近，UCLA和MIT的研究者证伪了概率论中众所周知的假设——「上下铺猜想」。上下铺猜想（Bunkbed Conjecture）也称为双层床猜想，是渗透理论中的一个陈述，该领域处理的是在图的边随机删除后存在的路径和簇。猜想指出，在生成的随机子图中，上（下）铺的顶点连接到上（下）铺的某个顶点的概率，大于或等于它连接到下（上）铺顶点——即对应同构顶点的概率。
用白话说就是，在同一层的两个顶点之间的连接概率不可能小于连接不同层顶点之间的概率。这看起来确实再明显不过了！
![]()
1985年，数学家Pieter Kasteleyn首次提出了上下铺猜想。
然而，这个问题的猜想却让几代概率论学家都束手无策，一直作为一个多年未解的难题存在至今。原因在于……它是错的！
39年后，来自UCLA和MIT的三位研究者，在使用AI工具却多次折戟后，采用了全新的方法，发现了它的反例。
论文地址：https://arxiv.org/abs/2410.02545
由此，在学界似乎坚固无比的「上下铺猜想」自然就被推翻了。
此前，大量的工作都被用在证明这个猜想的正确性上，然而这几位研究者却反其道而行之，经历多次失败后，终于找到了反例。
许多数学家做研究的过程，是由直觉驱动的，比如可以感知数学真理的印度数学天才拉马努金。
这种直觉，来自对某些事情应该为真的深刻认知。但有时，直觉也会误导数学家，因为早期证据无法代表全貌，一个看似显而易见的陈述，也会有某些隐藏的细微之处。
20世纪80年代中期，一位名叫Pieter Kasteleyn的荷兰物理学家，想要在数学上证明一个关于液体如何在多孔固体中流动的推断。
由此，他提出了上下铺猜想。
要理解这个猜想，要先从一个图开始：这个图是由线或边连接的点或顶点的集合。
![]()
现在，让我们做一个这个图的精确副本，然后将它直接放置在原始图的上方。
在它们之间画一些垂直的柱子——这些是连接底部图上一些顶点与顶部图上对应顶点的额外边。
最终，我们会得到一个类似于上下铺的结构。
![]()
接下来，考虑底部图中的一条边。
抛一次硬币，如果是正面，就擦掉这条边；如果是反面，就保留这条边。对两个图中的每条边重复这一过程。
最终，顶部和底部的图会看起来不同，但它们仍然会通过垂直的「柱子」相连。
![]()
最后，在底部图中选择两个顶点。
你能沿着图的边从一个顶点走到另一个顶点吗，还是这两个顶点现在已经不连通了？
对于任何一个图，你都可以计算出存在路径的概率。
现在，再来看这两个相同的顶点，不过把其中一个替换为它在顶部图中正上方的顶点。有没有一条路径，可以让你从底部图中的起点顶点到顶部图中的终点顶点？
![]()
此处再复习一下：上下铺猜想认为，在下铺找到路径，其概率总是大于或等于跳到上铺找到路径的概率。
无论从哪个图开始，在上下铺之间画多少垂直柱，选择哪些起始和终点顶点，都不影响这一事实。
从直觉上看，这是个理所当然的事。
「我们的大脑告诉我们的任何信息，都表明这个猜想应该是正确的」，普林斯顿大学的图论学家Maria Chudnovsky这样说
也因此，几十年来，数学家们一直认为这是真的。
他们的直觉告诉他们，在一个铺位上移动应该比在两个铺位之间移动更容易——从下铺到上铺所需的额外垂直跳跃，应该会显著减少可用路径的数量。
而且，数学家们也希望它是真的。因为这些图可以被视为流体如何在多孔材料中移动或渗透的简化模型，就像水在海绵中移动一样。
![]()
如果上下铺猜想成立，物理学中被广泛相信的流体通过固体的可能性也就成立，渗流物理学的相关问题也能被解决。
然而数学家们在39年间尝试了无数次，却无人能够证明。
原因就在于——上下铺猜想是错的！
并不是所有数学家都相信上下铺猜想的真实性，加州大学洛杉矶分校的数学家Igor Pak就是其中一个。
他的研究生Nikita Gladkov表示，对于学界一直集中精力试图证明这个猜想，自己的导师毫不掩饰自己的批评。「如果它是错的呢？」
![]()
Igor Pak的怀疑还有一个理由：这个说法过于宽泛了。它真的适用于每个可想象的图吗？「有些猜想是由实际动机驱动的，而其他猜想则是数学家的一厢情愿。」上下铺猜想看起来更像是后者。Igor Pak的博客
Igor Pak意识到，是时候上一些暴力了！他让学生Gladkov使用计算机，对能找到的每一个图进行「暴力搜索」。这就涉及到一些复杂的编程，因此Gladkov找来了大学室友、现MIT研究生Aleksandr Zimin，也是自己睡在下铺的兄弟。![]()
三人开始手动检查少于九个顶点的每一个可能的图。在这些图中，上下铺猜想是成立的。但对于更大的图，可能的情况数量就一下子激增，他们无法再通过穷举法，穷尽所有可能的边缘删除方式或路径形成方式了。使用机器学习方法，他们训练了一个神经网络，用于生成可能更偏好向上跳跃的迂回路径图。在众多示例中他们发现，下铺路径会比上铺替代路径概率稍高一点。但模型始终没有发现任何反例——也就是不同层路径概率更高的情况。还有一个问题，就是神经网络生成的每个图过于庞大，以至于数学家们根本不可能调查抛硬币步骤的每一个结果。他们意识到，自己可以对神经网络给出的任何反例有超过99.99%的信心，却始终无法达到100%。三人陷入怀疑：这种方法是否还值得？毕竟，只能达到99%而非百分百的证明，根本不足以说服数学圈，也不会被哪个著名期刊认为是足够严谨的证明。「博士生需要的是现实中的工作，而不是理论上的工作，」Pak在博客上写道。Gladkov和Zimin很快就要找工作了，最终，三人停止了这项工作。虽然他们放弃了计算方法，却并未停止思考这个问题。接下来的几个月，他们拼命想做出一个不需要计算机的理论论证，却缺少所需的所有要素。6月，剑桥大学的Lawrence Hollom在另一种语境下，证伪了上下铺问题的一个版本。这个猜想的表述并非针对图，而是研究称为超图（hypergraph）的数学对象。在超图中，边的定义不再局限于连接一对顶点，而是可以连接任意数量的顶点。Hollom找到了这个版本猜想的一个反例。他创建了一个小型超图，每条边都连接三个顶点：Gladkov发现这篇论文后意识到，这正是他们三人所需要的！他从晚上一直读到凌晨3点，并在睡觉前给Zimin发了短信。第二天，两个人便通了电话。就能否将Hollom的反例转化为一个能否推翻原始上下铺猜想的普通图，展开了讨论。去年年初，他们在一起参加音乐会之前讨论过这个问题。「红辣椒乐队在唱歌，而我在思考这个问题，」Gladkov说道。后来，他们开发出了可以在特定情况下将超图转化为图的技术。如今，这些技术刚好可以用来改造Hollom的超图。Gladkov、Pak和Zimin用庞大的点集和普通边组成的集群，替换了超图中的每个三顶点边。最终，他们得到了一个巨大的图，由7,222个顶点和14,422条边连接而成。他们放弃了AI的方法后，利用构建的理论来重新证明。最终，他们在图中发现，对于位于下路径的点，找到上路径的概率比找到下路径高出1/10^6,500个百分点——虽然这个数值极小，但并不为0。果然，数学家们在任何时刻都不能想当然地接受任何事。普林斯顿数学家Noga Alon表示：「我们必须保持怀疑，即便是那些直觉上看起来极有可能为真的事情。」不过，Gladkov、Pak和Zimin只是找到了许多符合该猜想的小图，但这些例子并且最终反映出——当顶点和边的数量足够多时，数学家可以构造出更为复杂且反直觉的图。正如Hollom所言，「我们真的像我们自认为的那样，理解所有东西吗？」目前，数学家们仍然相信激发上下铺猜想的关于固体中连接位置的物理命题。但他们需要找到其他方法来证明它。与此同时，Pak表示，数学家们显然需要更积极地讨论数学证明的本质。他们最终并未依赖有争议的计算方法，而是以完全确定的方式推翻了猜想。但随着计算机和AI的研究方法在数学研究中变得越来越普遍，一些数学家也在讨论：该领域的规范是否需要改变？「这是一个哲学问题，」Alon说道，「我们该如何看待那些仅在高概率下成立的证明呢？」罗格斯大学的数学家Doron Zeilberger认为，未来的数学圈会接受这样的概率性证明。在50年内或更短时间内，人们就会形成全新的态度。在论文中，他经常把自己的计算机（Shalosh B. Ekhad）列为合著者。![]()
「Shalosh」和「Ekhad」在希伯来语中分别意为「三」和「一」，也就是Zeilberger第一台计算机AT&T 3B1；代指他所用到的任意一台——从新泽西办公室里的戴尔电脑，到偶尔在奥地利调用的超级计算机但也有一些人，则担心这样的未来可能会危及一些根本性的东西。「概率性证明可能会削弱我们对问题本质的理解和直觉，」Alon认为。最后Pak建议，鉴于这类研究日益增多，应该为它们创建专门的学术期刊，以免其价值被数学界忽视。「这个问题没有标准答案。但我希望学术界能够认真思考，当下一个类似的研究结果出现时，我们是否应该接受它。」随着AI等技术持续渗透和改变数学领域，这个问题只会愈发紧迫。
Nikita Gladkov
Nikita Gladkov是加州大学洛杉矶分校数学系博士生，导师是Igor Pak。此前，他在俄罗斯高等经济学院获得数学学士学位，导师是Alexander Kolesnikov，并曾在Yandex数据分析学校学习数据分析。Igor Pak
Igor Pak是加州大学洛杉矶分校数学系教授，隶属于组合数学研究组，这是美国最古老的组合数学研究组之一。此前，他曾在明尼苏达大学和麻省理工学院担任过副教授，在耶鲁大学担任过J. W. Gibbs讲师，并在MSRI担任过博士后研究员。他于1993年在莫斯科国立大学获得数学学士学位，1997年在哈佛大学获得数学博士学位Aleksandr Zimin
Aleksandr Zimin是麻省理工学院数学系博士三年级学生，在Philippe Rigollet教授的指导下进行研究。主要研究领域是最优运输理论。他正在和Alexander Kolesnikov和Nikita Gladkov一起研究Monge-Kantorovich问题的广义化，并与Aleh Tsyvinski（耶鲁大学）和Job Boerma（威斯康星大学麦迪逊分校）合作研究在经济学中的应用。同时，他还对计算机科学有浓厚的兴趣——曾在Yandex数据分析学校完成了为期两年的课程，深入学习了机器学习的不同领域。他具有丰富的高质量计算机代码编写经验，从而能够在研究中进行复杂的数值实验。他于2019年在莫斯科高等经济大学以最高荣誉获得数学学士学位，2021年在俄罗斯斯科尔科沃科学技术研究院获得数学与理论物理硕士学位，同年在莫斯科高等经济大学获得数学硕士学位。https://www.quantamagazine.org/maths-bunkbed-conjecture-has-been-debunked-20241101/https://igorpak.wordpress.com/2024/10/01/the-bunkbed-conjecture-is-false/
想要了解更多资讯，请扫描下方二维码，关注机器学习研究会
![]()
转自：新智元
