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

来源:ob欧宝官网

阅读 30
发布时间 2021-10-21 09:45:58

  来自斯坦福、CMU等高校的4名数学家,直接将一个数学难题转化成了对10亿个结果进行“暴力搜索”。

  他们把这串代码输入40台电脑组成的计算集群,30分钟后,计算机给出了一个200GB大小的证明结果:

  比较反转的是,这段获得计算机学术会议IJCAR(国际自动推理联合会议)最佳论文奖的程序,上线GitHub半年,只揽获了一颗星。

  那么,这4位数学家要证明的“凯勒猜想”到底是什么?为何非要用计算机来证明?计算机证明的结果可靠吗?

  假如用一批完全相同的正方形瓷砖铺满地面,中间不留空隙。显然,瓷砖之间会共用一条边,如下图蓝线维空间中,如果要用立方体占满空间,是不是也和2维空间类似呢?

  想象一下,如果像下图那样在空间中随便放入几个立方体,由此展开填满整个空间,那么唯一的办法就是让接上的立方体共用蓝色的面。

  1930年,德国数学家凯勒猜测,如果用n维立方体填满无限空间,则立方体之间必然会出现“面对面”,对于任意维度都成立。

  可能你已经发现,从上世纪90年代以来,凯勒猜想的证明速度大大加快,数学家只用了10年时间就把问题缩小到三个维度。

  当年,Perron求解1到6维时,没有特殊的捷径。而到1990年,凯勒猜想的证明方法发生了巨大的变化。

  数学家Corrádi和Szabó提出了一种新的思路,把原来无限空间的问题变成有限的、离散的问题,也让计算机解决凯勒猜想成为可能。

  他们巧妙地把凯勒猜想变成了图论问题,就是构造所谓的凯勒图(Keller Graph),而图论正是计算机所擅长的。

  在这种方法的指导下,Lagarias和Shor两人很快在2年后就证明了10维空间的情况:凯勒猜想不成立。又过了10年,Mackey证明,凯勒猜想在8维空间不成立。

  现在,我们有一种牌,牌上画着两个有颜色的点。两个点是有顺序的,不能调换。比如,1黑2白≠1白2黑。

  数学家已经证明,分配给点的颜色相当于正方形在空间中的坐标。两张牌的颜色是否配对表示两个正方形的相对位置。

  然后我们把这16张牌摆在桌上,只有符合前面条件4的两张牌,才用线将二者连起来。这样就构成了一张“凯勒图”。

  如果2维空间中凯勒猜想不成立,那么我们肯定能找到4个正方形,它们之间没有共用的边,但是能够无缝隙填在一起。然后在屏幕上无限复制这4个正方形,就能填满整个屏幕。

  对应到凯勒图中,就是找在图中找到4张牌,它们两两之间都有连线。(在数学里,这叫做完全图。)

  作为更一般的规则,如果要证明n维凯勒猜想是错的,就要在对应的凯勒图中找到2n张牌,且这些牌两两相连。

  为了在3维空间中证明凯勒猜想,可以使用216张牌,每张牌上3个点,并可以使用3对颜色(这一点相对灵活)。然后,我们需要寻找23=8张牌 ,它们两两之间都有连线,但还是找不到。

  接下来的事情就是在7维空间对应的凯勒图上寻找完全子图。然而这个问题却从8维问题解决后被搁置了17年。

  根据前面的说明,求解8维空间和10维空间的凯勒猜想,要寻找28=256和210=1024张牌的子图,而7维空间只要寻找27=128张牌的子图。

  证明了10维情况的Lagarias说:“7维不好,因为它是质数,这意味着你无法将其分解为低维。因此别无选择,只能处理这些图的全部组合。”

  说干就干,此前证明8维问题的CMU教授Mackey拉上了斯坦福的数学在读博士Brakensiek和专长计算机辅助证明的助理教授Heule。

  回忆起立项的那天,Mackey说,Brakensiek是真正的天才,看着他就像看着NBA总决赛里的詹姆斯。Brakensiek本人确实很厉害,他曾是2013/14两届国际信息学奥赛金牌得主。

  先设定牌上有7个点、6种可能的颜色,按照前面的“条件4”对这些牌上色,看看能不能找到128种不同的填色方法。如果找不到,那么凯勒猜想成立。

  若要求解7维,则总共包含39000个不同布尔变量(0或1),有239000种可能性,这是一个非常非常大的数字,有11741位数。

  比如,用计算机规则给128张牌上色,当你涂到第12张牌的时候,发现找不到符合条件的下一张牌了。那么所有包含这12张牌的排列都可以排除。

  提升效率的另一种方式是利用对称性。如果已经验证了某种排列不可能,那与之对称的所有情况都可以排除。

  实际上,计算机提供的不仅仅是一个答案,证明的内容多达200GB。4位论文作者将证明送入计算机的证明检查器,确认了它的可靠性。

  解决了凯勒猜想后,Heule的下一个目标是用计算机证明数学里“最简单的不可能问题”——3n+1猜想,去年陶哲轩已经“几乎”解决了这个问题,现在可能只差一步之遥了。

上一篇:冬奥云端学习增添新平台 “学习冬奥”集结文体大咖上线 下一篇:云计算是怎么定义的核心技术有哪些?