本篇文章3684字，读完约9分钟
我知道了从凹非寺出发
量子报道|公众号qbitai
数学家可以编写代码，甚至阻止不了困扰人类的90年数学推测。
来自斯坦福、cmu等大学的4名数学家，把一个数学课题直接变成了10亿的结果“暴力搜索”。
△论文作者之一cmu助理教授marijn heule
他们把这一系列代码输入到由40台计算机组成的计算集群中，30分钟后，计算机得出了200gb大小的说明结果。
凯勒推测在7维以下的空间里是正确的。
现在每个人都可以去github克隆这个代码串，验证这个数学定理了。
相反，获得该计算机学术会议ijcar (国际自动推理联合会议)最佳论文奖的程序在半年内只获得了一颗星。
那么，这四位数学家想说明的“凯勒猜想”到底是什么呢？ 你为什么必须用电脑解释？ 计算机说明的结果可靠吗？
一起来吧。
什么是凯勒猜想
如果用完全相同的正方形瓷砖铺满地面，不要留下间隙。 很明显，在瓷砖之间共享边缘。 下图中的蓝线表示。
在三维空间中，如果用立方体填补空间的话，不是也类似于二维空间吗？
请想象一下，如果您在空间中自由放置几个立方体，从而填充整个空间，那么连接的立方体有唯一的共享蓝色面的方法。
二维、三维都是这样，但更高维度的空间会怎么样？
1930年，德国数学家凯勒推测，如果用n维立方体填补无限空间，立方体之间必然会“面对面”，对任意维度成立。
这是凯勒的预想。
但是数学推测光凭直觉是不行的，需要严密的说明。 九十年来，数学家不懈地努力。
1940年，数学家perron解释了凯勒推测在1~6维空间是正确的。
1992年，另外两名数学家lagarias和shor解释了凯勒推测在10维空间中是错误的。
(注:该shor是提出用量子计算机求解素因数分解的shor算法的数学家。 中选择所需的墙类型
很遗憾，我认为凯勒错了！ 但是，问题并没有就此结束。
还有三个维度没有处理啊！ 你认为凯勒在7维、8维、9维的3维空间中成立吗？
只要处理这三个维度，缠着数学家几十年的问题就能彻底解决。
根据数学论证，如果凯勒的猜想在n维空间中是错误的，那即使是高于n的维也一定是错误的。
2002年，数学家mackey推测凯勒在8维空间中不成立。 这是因为在9维空间中也不成立。
至此，7维空间成为了唯一的难题。
△8说明空间凯勒预想错误的cmu教授mackey
说明做法的改进
20世纪90年代以来，凯勒预想的解释速度大幅加快，数学家可能在短短10年内就把问题缩小到了三维。
这首先是两个数学家的贡献。
那一年，perron求解1~6维时，没有什么特别的捷径。 到1990年凯勒预想的解释方法发生了很大变化。
数学家corrádi和szabó提出了一个新的构想，使原来的无限空间问题变成有限离散的问题，从而使凯勒的预想能够由计算机处理。
他们巧妙地把凯勒的预想变成了图论问题。 就是构筑所谓的凯勒图( keller graph )，图论擅长计算机。
在这种方法的指导下，lagarias和shor两人很快在两年后说明了10维空间的状况:凯勒的预想不成立。 另外10年后，mackey解释说凯勒推测在8维空间中不成立。
那么，凯勒图是什么呢？ 为什么可以加速凯勒对推测的解释？
制作“凯勒图”
首先，让我们从最简单的二维情况开始。
现在我们有卡了。 卡片上画了两个有色点。 两点有顺序，不能互换。 例如，一黑二白≠一白二黑。
两个点一共可以涂四种颜色，颜色分为红和绿，白和黑两对。
数学家说明分配给点的颜色相当于正方形空间中的坐标。 两张卡的颜色是否成对表示两个正方形的相对位置。
点的颜色和正方形的具体关系如下。
一两对点完全相同，表示两个正方形完全重叠
两对点颜色不同，没有成对的颜色，因此表示两个正方形部分重叠
3，一对点的颜色相同，另一对点的颜色成对，表示两个正方形共用一条边。
4，一对点的颜色不同，另一对点的颜色成对，这表明两个正方形的边互相接触，但不重合
两点凯勒图用两对颜色填充牌面。 总共有16种情况。
然后，把这16张卡放在桌子上，只有符合前面条件4的2张卡用线把两者连接起来。 这样构成了“凯勒图”。
包含16张卡的凯勒图描绘了正方形填补平面的所有可能性。
如果在二维空间中凯勒的预想不成立，就能找到四个正方形，它们之间没有共同的边，但一定能无间隙地填补。 然后，把这四个正方形无限复制到画面上，整个画面就被填满了。
实际上是不可能的。 进行这个操作的话，只能得到有无数孔(下图紫色的部分)的填充方法。
与凯勒图对应的是，在图中找到四张卡，那两者之间有连接。 (在数学中，这称为完全图。 中选择所需的墙类型
很明显，在二维问题凯勒图中没有找到这样的四张卡。 (你可以在上面的凯勒图里自己找一下。 中选择所需的墙类型
因此，将n维立方体及位移s与卡片的点数n、颜色对数s相关联。
作为更一般的规则，要说明n维凯勒的预想是错误的，必须在对应的凯勒图中找到2n张卡，并将这些卡片连接两个。
正因为找不到由四张卡构成的完整图，所以二维空间的凯勒猜想是正确的。
为了在三维空间中说明凯勒猜想，可以采用216张卡，一张卡打3分，采用3对颜色(这些比较灵活)。 。 而且，需要找23=8张卡。 两者之间都有连接，但还没有找到。
在8维空间中，终于可以找到符合条件的256张卡，所以8维空间的凯勒猜想是错误的。
△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本人确实很厉害。 他曾是/14届国际新闻学奥林匹克金牌。
△论文第一作者brakensiek
回到正题。 为了方便电脑的解决，他们改变了方向想了想。
首先，卡片上设定了7个点，6个可能的颜色，按照前面的“条件4”给这些卡片上色，看看能不能找到128种不同的涂装方法。 如果找不到，凯勒的预想就成立。
计算机辅助说明数学问题，它需要解决一系列的逻辑运算，即01之间的逻辑与或非关系。
要求解7维，总共包含39000个不同的布尔变量( 0或1 )，可能有239000种。 这是一个非常大的数字，11741位。
△2的39000次方(根据wolfram alpha运算结果)
普通电脑只能解决324位数的可能性，离处理问题还很远。 交给超级计算机也不够。
但是，这几位数学家想出排除法，得出结论的话，就没有必要实际检查所有的可能性。 效率才是王道！
例如，根据电脑规则给128张卡上色，涂在第12张卡上，就找不到符合条件的下一张卡了。 那么可以排除所有包含这12张卡的排列。
提高效率的另一种形式是利用对称性。 如果验证了任何数组是不可能的，就可以排除与其对称的所有情况。
通过这两种方法，他们把搜索空间缩小到了10亿( 230亿)。 这样，就可以在计算机上进行检索。
结果，他们只计算了半个小时，就得出了答案。
计算机找不到符合条件的128张卡，所以7维空间凯勒猜想确实成立了。
事实上，计算机不仅提供了答案，而且提供了高达200gb的副本。 4位论文作者对发送到计算机的说明检查器进行了说明，确认了其可靠性。
处理凯勒猜想后，heule的下一个目标是用计算机解释数学中“最简单的不可能问题”——3n+1猜想，去年陶哲轩已经“差不多”处理了这个问题，现在可能晚了一步。
参考链接:
quanta magazine/computer-search-settles-90-year-old-math-problem-0819 /
cs.cmu.edu/~mheule/keller/
mathworld.wolfram/kellergraph
论文地址:
arxiv/abs/1910.03740
源代码:
github/marijnheule/keler-encode
——完
本文是网易信息网易号特色文案激励计划合同账号【量子位】原创文案，未经账号授权，禁止擅自转载。
原标题:“困扰数学家的90年预想，在电脑上被搜索了30分钟后处理了。”
阅读原文。
