来源：机器学习研究组订阅
又一个看似坚固无比的数学理论，被证伪了！最近，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表示，对于学界一直集中精力试图证明这个猜想，自己的导师毫不掩饰自己的批评。「如果它是错的呢？」
Nikita GladkovIgor Pak的怀疑还有一个理由：这个说法过于宽泛了。它真的适用于每个可想象的图吗？「有些猜想是由实际动机驱动的，而其他猜想则是数学家的一厢情愿。」上下铺猜想看起来更像是后者。
Igor Pak的博客
早在2022年，他就开始着手推翻它。花了一年时间后，他以失败告终。Igor Pak意识到，是时候上一些暴力了！他让学生Gladkov使用计算机，对能找到的每一个图进行「暴力搜索」。这就涉及到一些复杂的编程，因此Gladkov找来了大学室友、现MIT研究生Aleksandr Zimin，也是自己睡在下铺的兄弟。
Aleksandr Zimin三人开始手动检查少于九个顶点的每一个可能的图。在这些图中，上下铺猜想是成立的。但对于更大的图，可能的情况数量就一下子激增，他们无法再通过穷举法，穷尽所有可能的边缘删除方式或路径形成方式了。随后，陷入困顿的三人转向了AI。使用机器学习方法，他们训练了一个神经网络，用于生成可能更偏好向上跳跃的迂回路径图。在众多示例中他们发现，下铺路径会比上铺替代路径概率稍高一点。但模型始终没有发现任何反例——也就是不同层路径概率更高的情况。还有一个问题，就是神经网络生成的每个图过于庞大，以至于数学家们根本不可能调查抛硬币步骤的每一个结果。相反，团队必须计算这些结果子集上上下路径的概率。他们意识到，自己可以对神经网络给出的任何反例有超过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）列为合著者。
团队介绍
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/阅读最新前沿科技研究报告，欢迎访问欧米伽研究所的“未来知识库”
未来知识库是“欧米伽未来研究所”建立的在线知识库平台，收藏的资料范围包括人工智能、脑科学、互联网、超级智能，数智大脑、能源、军事、经济、人类风险等等领域的前沿进展与未来趋势。目前拥有超过8000篇重要资料。每周更新不少于100篇世界范围最新研究资料。欢迎扫描二维码或点击本文左下角“阅读原文”进入。截止到10月25日 ”未来知识库”精选的100部前沿科技趋势报告
接下来，我们将为您逐一展示这100部精选报告的完整标题列表。
1. 牛津大学博士论文《深度具身智能体的空间推理与规划》230页
2. 2024低空经济场景白皮书v1.0（167页）
3. 战略与国际研究中心（CSIS）人类地月空间探索的总体状况研究报告（2024）
4. 人工智能与物理学相遇的综述（86页）
5. 麦肯锡：全球难题，应对能源转型的现实问题（196页）
6. 欧米伽理论，智能科学视野下的万物理论新探索（50页报告）
7. 《美国反无人机系统未来趋势报告（2024-2029 年）》
8. Gartner 2025 年主要战略技术趋势研究报告
9. 2024人工智能国外大模型使用手册+中文大模型使用手册
10. 详解光刻巨人ASML成功之奥妙-241015（94页）
11. CB Insights：未来变革者：2025年九大科技趋势研究报告
12. 国际电信联盟2023-2024年联合国人工智能AI活动报告388页
13. 《人工智能能力的人类系统集成测试和评估》最新51页，美国防部首席数字和人工智能办公室（CDAO）
14. 2024瑞典皇家科学院诺贝尔化学奖官方成果介绍报告
15. MHP：2024全球工业4.0晴雨表白皮书
16. 世界经济论坛白皮书《AI价值洞察：引导人工智能实现人类共同目标》
17. 瑞典皇家科学院诺贝尔物理学奖科学背景报告资料
18. AI智能体的崛起：整合人工智能、区块链技术与量子计算(研究报告，书）
19. OpenAI o1 评估：AGI 的机遇和挑战（280页）
20. 世界知识产权组织：2024 年全球创新指数（326页）
21. 美国白宫：国家近地天体防御策略与行动计划
22. 【CMU博士论文】持续改进机器人的探索，243页
23. 中国信通院：量子计算发展态势研究报告2024年58页
24. 2024年OpenAI最新大模型o1革新进展突出表现及领域推进作用分析报告
25. 【新书】通用人工智能，144页
26. 联合国：《未来契约》、《全球数字契约》和《子孙后代问题宣言》三合一
27. 世界气候组织：2024团结在科学中，守卫地球系统的未来
28. 世界经济论坛 《量子技术助力社会发展：实现可持续发展目标》研究报告
29. 人工智能科学家：迈向全自动开放式科学发现
30. 欧盟：石墨烯旗舰项目十年评估报告
31. 美国信息技术和创新基金会：美国的数字身份之路研究报告
32. 麦肯锡：2024能源转型挑战未来研究报告
33. 联合国贸易与发展会议：2024世界投资报告
34. 兰德：评估人工智能对国家安全和公共安全的影响
35. 兰德：2024评估人工智能基础模型市场的自然垄断条件
36. 经合组织：2015-2022 年生物多样性与发展融资
37. ITIF：中国半导体创新能力研究报告
38. 英国皇家学会：数学未来计划， 数学和数据教育的新方法研究报告
39. 欧盟：10年人类大脑计划创新评估报告
40. GLG格理集团：2024深度解读半导体行业关键趋势和专家洞见报告15页
41. 华为智能世界2030报告2024版741页
42. 联合国：2024为人类治理人工智能最终报告
43. 达信Marsh：2024全球科技产业风险研究报告英文版27页
44. 鼎帷咨询：2024英伟达人工智能发展战略研究报告149页
45. 【博士论文】大语言模型的测试与评价：准确性、无害性和公平性，223页pdf
46. 麦肯锡：2024世界能源产业展望
47. 世界经济论坛《太空：全球经济增长的 1.8 万亿美元机遇》
48. 世界经济论坛：世界“技术先锋”名单100家公司名单
49. 世界经济论坛：2024绘制地球观测的未来：气候情报技术创新
50. 核聚变技术作为清洁能源供应替代来源的全球发展和准备情况
51. 大模型生成的idea新颖性与人类对比研究报告（94页）
52. IQM ：2024 年量子状况报告
53. 2024十大新兴技术研究报告
54. 2024地球观测 (EO) 洞察带来的全球价值（58页）
55. 2023-2024世界基础设施监测报告
56. 世界银行：2024世界发展报告，中等收入陷阱
57. 2024国际前沿人工智能安全科学报告132页
58. 斯坦福大学2024人工智能指数报告
59. 美国总统科学技术顾问委员会：《利用人工智能应对全球挑战》63页报告
60. 柳叶刀行星健康：2024地球系统安全与健康评估报告
61. 中国未来50年产业发展趋势白皮书III
62. OpenAI o1系列产品原理与安全最新研究报告（80页）
63. 国家互联网信息办公室：国家信息化发展报告2023年110页
64. 埃森哲：2024年风险研究报告-重大颠覆需要持续重塑英文版39页
65. 36氪研究院：2024年中国城市低空经济发展指数报告41页
66. 美国信息技术与创新基金会：《中国在量子领域的创新能力如何》研究报告
67. 理解深度学习500页报告
68. 鼎帷咨询：2024全球人工智能发展研究报告44页
69. 【伯克利博士论文】大型语言模型迈向能够学习和发现一切的机器
70. 《量子技术：前景、危险和可能性》45页报告
71. 英国皇家学会报告：人工智能在科学、技术、工程和数学领域的应用
72. 未来今日研究所：2024世界技趋势报告（980页）
73. 面向大规模脉冲神经网络：全面综述与未来方向
74. 大模型+知识库市场全景报告
75. 《太空力量的理论基础：从经济学到不对称战争》2024最新94页报告
76. CBInsights：2024年第二季度全球企业风险投资状况报告英文版124页
77. 英国科学院：数据管理和使用：21 世纪的治理（2024），99页
78. 兰德智库：展望2045 一项前瞻性研究探讨未来 20 年全球趋势的影响
79. 世界知识产权组织：2024年世界知识产权报告：让创新政策促进发展
80. 全球灾难风险研究所：评估大型语言模型接管灾难的风险
81. 牛津马丁学院：人工智能风险国际科学评估的未来
82. 联合国贸易和发展署：2024世界投资报告
83. 兰德公司：人工智能军事应用的新风险和机遇
84. 英国皇家学会：AI时代的科学发展趋势研究报告
85. 百页风电行业研究方法论：从中国到世界从陆地到海洋-240902，98页
86. 中国信通院发布《大模型落地路线图研究报告（2024年）》
87. 星河智源：2024年无人驾驶技术全景报告35页
88. 星河智源：2024年光刻机技术全景报告37页
89. 人形机器人行业研究方法论：特斯拉领衔人形机器人的从1到N
90. 兰德：展望2045一项关于未来20年全球趋势影响的前瞻性研究报告英文版45页
91. 《军事创新与气候挑战》2024最新152页报告
92. 麦肯锡：2024困难点：驾驭能源转型的物理现实（196页）
93. 《麻省理工科技评论》万字长文：什么是人工智能？
94. 软件与服务行业：从特斯拉智能驾驶看人形机器人发展路径
95. 中国信通院：中国数字经济发展研究报告2024年82页
96. CB Insights：2024年第二季度全球风险投资状况报告 244页
97. 脑启发的人工智能：全面综述
98. 二十年关键技术跟踪报告
99. 中国首部城市大脑系列建设标准（8项）汇编
100. 麦肯锡2024技术趋势展望报告100页
