理所当然也能错，数学界震动：「上下铺猜想」被证伪

科技 2024-11-03 00:01 北京

来源 | 机器之心

数学的很大一部分是由直觉驱动的，但有时想当然会让人误入歧途。早期的证据可能并不代表大局，一个陈述可能看起来很明显，但一些隐藏的微妙之处会自行显露出来。

三位数学家现在已经证明，概率论中一个著名的假设，即双层床猜想（bunkbed conjecture）就属于这一类。这个猜想 —— 关于当数学迷宫（称为图、graphs）像双层床一样堆叠在一起时，你可以用不同的方式导航 —— 这似乎是自然的，甚至是不言而喻的。

「我们的大脑告诉我们的任何事情都表明，这个猜想应该是正确的，」普林斯顿大学图论学家 Maria Chudnovsky 说道。

论文链接：https://arxiv.org/abs/2410.02545

但这就是错误的。上个月，三位数学家宣布了一个反例，反驳了这一猜想。这一结果为解决固体材料性质相关物理问题提供了新的指导。但它也涉及了关于数学如何运作的更深层次的问题。大量的数学努力都花在试图证明猜想是正确的上。这项新工作的团队在最终找到反例之前失败了很多次。他们的故事表明，数学家可能需要更频繁地质疑他们的假设。

图中之图

在 1985 年，一位名叫 Pieter Kasteleyn 的荷兰物理学家想要用数学方法证明液体如何在多孔固体中流动。他的工作使他提出了双层床猜想。

要理解这个理论，我们先从一张图开始：一组由线或边连接的点或顶点。

现在复制一份该图并将其直接放在原图上方。在它们之间画一些垂直柱子 —— 将底部图上的一些顶点与顶部图上的孪生顶点连接起来的附加边。最终得到的结构类似于双层床。

接下来，我们考虑底部图中的一条边，开始抛硬币。如果硬币正面朝上，则擦除边。如果硬币反面朝上，则保留边。对两个图中的每条边重复此过程。你的下铺和上铺最终看起来会有所不同，但它们仍将通过垂直柱子连接起来。

最后，在下部图中选取两个顶点。你能沿着图的边缘从一个顶点到达另一个顶点吗？还是说这两个顶点现在断开了？

对于任何图，你都可以计算出存在路径的概率。现在看看同样的两个顶点，但对于其中一个顶点，跳转到顶部图中它正上方的顶点。是否有一条路径可以带你从底部图上的起始顶点到达顶部图上的终止顶点？

双层床猜想认为，找到下铺路径的概率总是大于或等于找到跳到上铺路径的概率。无论你从哪个图开始，在双层床之间画多少个垂直柱子，或者选择哪个起始和结束顶点，都无关紧要。

看起来很合理是吧，这难道还能证伪吗？

几十年来，数学家们一直认为这是成立的。直觉告诉我们，在一个铺位上寻路应该比去另一个铺位的路径更简单 —— 从下铺到上铺所需的额外垂直跳跃应该会大大限制可用路径的数量。

数学家们希望双层床猜想是真的。它属于渗透理论领域的一类陈述，该理论处理在随机删除图的边后存在的路径和簇。这些图可以被认为是流体如何移动或渗透通过多孔材料的简化模型，就像水通过海绵一样。双层床猜想则暗示了物理学中一个被广泛接受的假设，即流体穿过固体的可能性。它还暗示了如何解决渗透物理学的相关问题。

但只有当有人能证明双层床猜想是正确的时候，这种情况才会发生。没有人能证明这一点是有原因的。

问题显现

加州大学洛杉矶分校（UCLA）数学家 Igor Pak 一直怀疑双层床猜想是否正确。「他从一开始就持怀疑态度，」他的一名研究生 Nikita Gladkov 说道。「他非常不相信旧猜想。」Pak 一直直言不讳地批评数学家们倾向于集中精力证明这些猜想。同样重要的进步也可以来自设问「如果它们全都错了怎么办？」

Igor Pak 怀疑双层床猜想还有一个特别的理由：它似乎是一个过于宽泛的说法。他怀疑这个猜想是否真的适用于所有可以想象的图。有些猜想是由实质驱动的，有些则是由一厢情愿的想法驱动的，双层床猜想似乎是后者。

Nikita Gladkov 对每个图表进行了详尽的强力搜索，以寻找反例。

2022 年，他开始寻求反驳这一理论。他花了一年时间尝试，但都以失败告终。然后，他指示 Gladkov 使用计算机对他能找到的每一张图进行详尽的强力搜索。Gladkov 意识到这项任务需要一些复杂的编程，于是请来了高中时就认识的朋友 Aleksandr Zimin（现在他是麻省理工学院的在读博士）。「我们实际上是大学时的室友 —— 我们的宿舍里有一张真正的双层床，」Gladkov 说道。

Gladkov、Pak 和 Zimin 能够手动挨个检查每个少于九个顶点的可能图。在这些情况下，他们可以验证上下铺猜想成立。但对于更大的图，可能情况的数量将会急剧增加，以至于他们无法穷尽所有可能的边删除方式或路径形成方式。

团队随后转向 AI 领域，使用机器学习方法。他们训练了一个神经网络来生成可能偏好向上跳跃的曲折路径图。在模型生成的许多示例中，他们发现下铺路径仅比上铺路径的概率略高一点。但模型未能找到任何反过来的例子。

还有另一个问题出现了：神经网络生成的每个图仍然很大，以至于数学家们无法逐一调查掷硬币步骤的所有可能结果。团队不得不计算在这些结果的子集上找到上下路径的概率，就像民意调查通过抽样部分选民来预测选举结果一样。

数学家们意识到，他们可以对神经网络提供的任何反例有超过 99.99% 的信心确认其是正确的，但却无法达到 100%。他们开始怀疑这种方法是否值得继续追求。这样的证明方式不太可能说服数学界，更不用说任何权威期刊会将其视为严谨的证明了。

「博士生在现实中需要找工作，而不是理论上，」Pak 在他的博客上写道，而 Gladkov 和 Zimin 很快也将开始找工作。「这才是我们停下来的真正原因，」他接着说道。「当你可以尝试做别的事情时，为什么还要坚持并制造争议呢？」

他们放弃了他们的计算方法，但并未停止对这个问题的思考。在接下来的几个月里，他们专注于制定一个不需要计算机的理论论证。但他们仍然缺少完成它所需的所有拼图。

然后，一个来自国外的突破性研究出现了。

计算机？不用了

今年六月，剑桥大学的 Lawrence Hollom 在不同的背景下推翻了上下铺问题的一个变体版本。这个版本的猜想不是关于图，而是关于一种称为「超图」（hypergraphs）的对象。在超图中，「边」不再被定义为两个顶点之间的连接线，而是可以任意数量的顶点间的连接线。

Hollom 成功找到了这个猜想的反例。他创建了一个小型超图，每条边都连接三个顶点：

Gladkov 偶然发现了这篇论文，意识到它正是他们三人所需要的。「我是在晚上发现的，读到凌晨三点。我心想，『哇，这太疯狂了，简直令人难以置信，』」他说。他在睡前给 Zimin 发了短信，第二天两人便通了电话。

这时候考验来了：他们是否可以将 Hollom 找到的反例重新构造成一个普通图，从而推翻原来的上下铺猜想？

这其实并不是这对老朋友第一次考虑如何将超图转化为图。去年年初，他们在一起参加演唱会前的不久就曾讨论过这个问题。「当时红辣椒乐队（The Red Hot Chili Peppers）在台上唱歌，而我却在想着这个问题，」Gladkov 说。「我完全没心思听音乐。」

后来，他们就开发出了在特定情况下将超图转化为图的方法。

他们意识到，现在他们终于可以使用这些技术来转换 Hollom 的超图。Gladkov、Pak 和 Zimin 将超图中每条具有三顶点的边替换为由大量点和普通边组成的集群。这使他们得到了一张巨大的图，包含 7222 个顶点和 14422 条边。

然后，他们放弃了使用人工智能的方法后，利用所构建的理论进行论证。在他们的这张图中，找到上路径的概率比找到下路径高出% ，这是一个极小但不为零的数值。

至此，上下铺猜想终于被他们证明是错误的。

普林斯顿大学数学家 Noga Alon 对此表示，他们的研究结果显示了不应把任何事情视为理所当然的重要性。「我们必须保持怀疑，即便是那些直观上看起来很可能为真的事情。」

Gladkov、Pak 和 Zimin 在之后，找到了许多满足该猜想的小图示例，但最终，这些示例并未反映在具有足够多顶点和边时他们能构建出的更复杂、更不直观的图中。

正如 Hollom 所说：「我们真的像我们认为的那样理解这些内容了吗？」

数学家们仍然相信激发了上下铺猜想的关于固体内连接位置的物理陈述。但他们需要找到另一种方法来证明它。

Aleksandr Zimin 在大学期间与 Gladkov 同住一间宿舍，宿舍里还有一张真正的上下铺。

与此同时，Pak 表示，很明显，数学家需要更积极地讨论数学证明的本质。他和同事最终并未依赖有争议的计算方法，而是以完全确定的方式推翻了该猜想。但随着计算机和 AI 方法在数学研究中的使用日益普及，一些数学家开始争论该领域的规范是否需要改变。

「这是一个哲学问题，」Alon 说道。「我们应如何看待那些仅在高概率下才能成立的证明？」

「我认为未来的数学界会接受这样的概率证明，」罗格斯大学的数学家 Doron Zeilberger 说道（这位数学家因在他本人许多的论文中将计算机列为合著者而闻名），「在 50 年内，或许更短，人们将有新的态度。」

Doron Zeilberger 常将他的计算机 Shalosh B. Ekhad 列为合著者，成为一桩趣事。

其他人则担心这样的未来会威胁到某种重要的东西。「也许概率证明会让你对事情的真实本质缺乏理解或直觉，」Alon 说道。

Pak 建议随着此类结果变得更加常见，应创建专门的期刊来发表这些研究结果，以免它们的价值被数学家们忽视。但他的主要目的是为了在数学界引发大讨论。

「没有正确答案，」他说。「我希望数学界思考，下一次此类结果是否应该被视为有效。」随着技术不断渗透和改变数学领域，这个问题将变得更加紧迫。

参考内容：

https://www.quantamagazine.org/maths-bunkbed-conjecture-has-been-debunked-20241101/

https://www.reddit.com/r/math/comments/1fulfpu/the_bunkbed_conjecture_is_false/

http://mp.weixin.qq.com/s?__biz=MzIxNDgzNDg3NQ==&mid=2247549744&idx=5&sn=ea92b4eae4d37e83f306f3f67bc47156

深度学习与NLP

专注深度学习、NLP相关技术、资讯，追求纯粹的技术，享受学习、分享的快乐。

最新文章

离谱！裁员裁出新高度了。。

斯坦福大学教授李飞飞团队：关于 2024 年人工智能发展报告总结

多模态大模型技术点总结

中科院院士：青年科学家 5 年内拿不出成果就面临淘汰，有的单位已现「马太」效应，重复给某一人奖励

[送5本]《科技论文写作指南》理工科学生福音

o1圈杀疯了，阿里又开源Marco-o1

吴恩达力荐，100%好评-《LangChain大型语言模型(LLM)应用开发》免费分享

这才是真・开源模型！公开「后训练」一切，性能超越Llama 3.1 Instruct

新一轮高校裁员潮，来了！

[送5本]《动手学自然语言处理》大模型改变了NLP的游戏规则了吗

LLM逻辑推演策略选择：推理时计算 vs 训练时计算

仅仅一天，Gemini就夺回了GPT-4o拿走的头名

教育部公布！25考研人数，再降50万！

大模型代肝，自动刷《崩铁》升级材料，Claude操纵计算机还能这么用！

一篇小型语言模型技术最新全面综述

M3DocRAG：文档问答用哪个多模态大模型效果最好？

已公示！“东方理工大学”，来了

聊一聊做角色扮演大模型的经验

绝对顶流！清华博导倾力编写的《图神经网络导论》pdf免费分享

最高9.0分！这16篇最高分ICLR2025论文必看！从生成模型到MOE等

ICLR 高分：深入研究多模态大模型的对齐策略

谷歌大佬编写，我唯一熬夜看完的机器学习神作pdf分享！

双非二战字节算法岗，拿下70k offer.....

猫猫运动方程，首次被物理学家破解！ |《美国物理学杂志》正经研究

o1的风又吹到多模态，直接吹翻了GPT-4o-mini

谷歌大佬编写，我唯一熬夜看完的机器学习神作pdf分享！

微调图像大模型的经验分享

昨夜， LLM 已经彻底凉凉了...

Karpathy后悔了：2015年就看到了语言模型的潜力，却搞了多年强化学习

微软开源角色Agents，直接模拟了整个世界~

2024最新神书-《大模型应用程序构建指南》免费pdf分享

2024最新,李宏毅深度学习教程pdf免费分享！绝对值得反复阅读的神书！

已注销！985新校区，不建了

RAG黑盒被打开了，可视化RAGViz闪亮全场

LLM性能优化中的一些概念扫盲

Nature:「人类亲吻难题」彻底难倒LLM，所有大模型全部失败！LLM根本不会推理，只是工具

Cursor一不小心把自家的底牌也放出来了~

[送5本]《动手学机器学习》上海交大ACM班总教头团队重磅新作，带你动手学机器学习！

传说中Ilya Sutskever精选论文清单：AI领域40大论文完整版「破解」完成

神书《从零构建大模型》分享，尚未发布，GitHub标星22k！！

LLM性能优化中的一些概念扫盲

暴跌94%，裁员9600人。。。

[送5本]《大语言模型：原理、应用与优化》大模型未来发展方向大揭秘！

多个中国团队斩获EMNLP'24最佳论文！UCLA华人学者中三篇杰出论文，明年顶会落户苏州

DRL2022新书-《深度强化学习》免费pdf分享

陶哲轩：计算机通用方法，往往比深奥的纯数学更能解决问题

中央批准：中央候补委员、教育部副部长，任C9大学书记

谷歌2024博士奖学金公布，KAN作者刘子鸣等数十位年轻华人学者入选

上交2024最新-《动手学大模型》实战教程及ppt分享！

分类

时事

民生

政务

教育

文化

科技

财富

体娱

健康

情感

旅行

百科

职场

楼市

企业

乐活

学术

汽车

时尚

创业

美食

幽默

美体

文摘

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉