江苏龙网

  1. 首页 > 社会 > >

困扰数学家90年的猜想，被计算机搜索30分钟解决了( 二 )

困扰数学家90年的猜想，被计算机搜索30分钟解决了
包含16张牌的凯勒图就描绘了正方形填补平面的所有可能 。如果2维空间中凯勒猜想不成立 ， 那么我们肯定能找到4个正方形 ， 它们之间没有共用的边 ， 但是能够无缝隙填在一起 。 然后在屏幕上无限复制这4个正方形 ， 就能填满整个屏幕 。实际上并不可能 。 如果按此操作 ， 只会得到有着无数孔隙（下图紫色部分）的填充方式 。困扰数学家90年的猜想，被计算机搜索30分钟解决了
对应到凯勒图中 ， 就是找在图中找到4张牌 ， 它们两两之间都有连线 。 （在数学里 ， 这叫做完全图 。 ）困扰数学家90年的猜想，被计算机搜索30分钟解决了
显然 ， 在2维问题的凯勒图中 ， 我们找不到这样的4张牌 。 （可以自己去上面的凯勒图中找找看 。 ）这样 ， 我们把就把n维立方体以及位移s与牌的点数n、颜色对数s联系起来 。作为更一般的规则 ， 如果要证明n维凯勒猜想是错的 ， 就要在对应的凯勒图中找到2n张牌 ， 且这些牌两两相连 。正因为你找不到4个张牌组成的完全图 ， 所以2维空间的凯勒猜想是对的 。为了在3维空间中证明凯勒猜想 ， 可以使用216张牌 ， 每张牌上3个点 ， 并可以使用3对颜色（这一点相对灵活） 。 然后 ， 我们需要寻找23=8张牌， 它们两两之间都有连线 ， 但还是找不到 。到了8维空间中 ， 我们总算可以找到符合条件的256张牌 ， 所以8维空间的凯勒猜想是错的 。困扰数学家90年的猜想，被计算机搜索30分钟解决了
△8维空间中的一个反例（一个凯勒图的完全子图）接下来的事情就是在7维空间对应的凯勒图上寻找完全子图 。 然而这个问题却从8维问题解决后被搁置了17年 。根据前面的说明 ， 求解8维空间和10维空间的凯勒猜想 ， 要寻找28=256和210=1024张牌的子图 ， 而7维空间只要寻找27=128张牌的子图 。后者的难度似乎更小 ， 7维空间的问题应该更简单啊！其实不然 。因为 ， 从某种意义上说 ， 8维和10维可以“分解”为容易计算的较低维度 ， 但7维不行 。证明了10维情况的Lagarias说：“7维不好 ， 因为它是质数 ， 这意味着你无法将其分解为低维 。 因此别无选择 ， 只能处理这些图的全部组合 。 ”对于人脑来说 ， 寻找大小为128的子图是一项艰巨的任务 ， 但这恰恰是计算机擅长回答的问题 。计算机帮忙说干就干 ， 此前证明8维问题的CMU教授Mackey拉上了斯坦福的数学在读博士Brakensiek和专长计算机辅助证明的助理教授Heule 。回忆起立项的那天 ， Mackey说 ， Brakensiek是真正的天才 ， 看着他就像看着NBA总决赛里的詹姆斯 。 Brakensiek本人确实很厉害 ， 他曾是2013/14两届国际信息学奥赛金牌得主 。困扰数学家90年的猜想，被计算机搜索30分钟解决了
△ 论文第一作者Brakensiek言归正传 。 为了方便计算机求解 ， 他们换了个方向来思考：先设定牌上有7个点、6种可能的颜色 ， 按照前面的“条件4”对这些牌上色 ， 看看能不能找到128种不同的填色方法 。 如果找不到 ， 那么凯勒猜想成立 。用计算机辅助证明数学问题 ， 还需要把它变成一系列逻辑运算 ， 也就是处理01之间的与或非关系 。若要求解7维 ， 则总共包含39000个不同布尔变量（0或1） ， 有239000种可能性 ， 这是一个非常非常大的数字 ， 有11741位数 。困扰数学家90年的猜想，被计算机搜索30分钟解决了
△2的39000次方（来自Wolfram Alpha运算结果）一台普通电脑只能处理324位数种可能 ， 离解决问题还远得很 。 就算交给超级计算机也不够 。但是 ， 这几位数学家想到了排除法 ， 只要得到结论 ， 而不必实际检查所有可能性 。 效率才是王道！比如 ， 用计算机规则给128张牌上色 ， 当你涂到第12张牌的时候 ， 发现找不到符合条件的下一张牌了 。 那么所有包含这12张牌的排列都可以排除 。提升效率的另一种方式是利用对称性 。 如果已经验证了某种排列不可能 ， 那与之对称的所有情况都可以排除 。通过这两种方法 ， 他们把搜索空间缩小到10亿（230） 。 这样一来 ， 用计算机搜索变成了可能 。最终 ， 他们仅计算了半个小时 ， 便有了答案 。计算机没有找到符合条件的128张牌 ， 所以7维空间的凯勒猜想确实成立 。实际上 ， 计算机提供的不仅仅是一个答案 ， 证明的内容多达200GB 。 4位论文作者将证明送入计算机的证明检查器 ， 确认了它的可靠性 。解决了凯勒猜想后 ， Heule的下一个目标是用计算机证明数学里“最简单的不可能问题”——3n+1猜想 ， 去年陶哲轩已经“几乎”解决了这个问题 ， 现在可能只差一步之遥了 。参考链接：https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/https://www.cs.cmu.edu/~mheule/Keller/https://mathworld.wolfram.com/KellerGraph.html论文地址：https://arxiv.org/abs/1910.03740源代码：https://github.com/marijnheule/Keller-encode来源：量子位


推荐阅读


上一篇：大胃王吃播被喊停：别让美食成为健康的负担！

下一篇：不爱运动的日本人，为何却是全球最瘦？