困扰数学家90年的猜想，被计算机搜索30分钟解决了
晓查 发自 凹非寺量子位 报道 | 公众号 QbitAI数学家会代码 ， 谁也挡不住！就连困扰人类90年的数学猜想也挡不住 。来自斯坦福、CMU等高校的4名数学家 ， 将一个数学难题转化成了对10亿个结果进行“暴力搜索” 。
△ 论文作者之一CMU助理教授Marijn Heule他们把这串代码输入40台电脑组成的计算集群 ， 30分钟后 ， 计算机给出了一个200GB大小的证明结果：凯勒猜想在不超过7维的空间上都是正确的 。现在 ， 任何人都可以去GitHub上克隆这串代码 ， 验证这一数学定理 。
比较反转的是 ， 这段获得计算机学术会议IJCAR（国际自动推理联合会议）最佳论文奖的程序 ， 上线GitHub半年 ， 只揽获了一颗星 。那么 ， 这4位数学家要证明的“凯勒猜想”到底是什么？为何非要用计算机来证明？计算机证明的结果可靠吗？下面让我们一一道来 。什么是凯勒猜想假如用一批完全相同的正方形瓷砖铺满地面 ， 中间不留空隙 。 显然 ， 瓷砖之间会共用一条边 ， 如下图蓝线所示：
在3维空间中 ， 如果要用立方体占满空间 ， 是不是也和2维空间类似呢？想象一下 ， 如果像下图那样在空间中随便放入几个立方体 ， 由此展开填满整个空间 ， 那么唯一的办法就是让接上的立方体共用蓝色的面 。
2维、3维皆如此 ， 更高维度的空间会怎样？1930年 ， 德国数学家凯勒猜测 ， 如果用n维立方体填满无限空间 ， 则立方体之间必然会出现“面对面” ， 对于任意维度都成立 。这便是凯勒猜想 。但数学猜想不能仅靠直觉 ， 必须有严格的证明 。 90年来 ， 数学家一直不懈努力 。1940年 ， 数学家Perron证明了凯勒猜想在1到6维空间是正确的 。1992年 ， 另外两位数学家Lagarias和Shor证明 ， 凯勒猜想在10维空间上是错误的 。（注：这位Shor就是那个提出用量子计算机求解质因数分解的Shor算法的数学家 。 ）非常不幸 ， 凯勒猜想竟然是错的！然而问题并没有到此结束 。还有3个维度没有解决呢！在7维、8维、9维三个维度空间中 ， 凯勒猜想是否成立？只要解决这三个维度 ， 缠绕数学家几十年的问题就彻底搞定了 。数学论证表明 ， 如果凯勒猜想在n维空间上是错的 ， 那么它在比n更高的维度上也一定是错的 。2002年 ， 数学家Mackey已证明 ， 凯勒猜想在8维空间不成立 ， 因此在9维空间也不成立 。至此 ， 7维空间成为唯一的难题 。
△ 证明8维空间凯勒猜想错误的CMU教授Mackey证明方法的改进可能你已经发现 ， 从上世纪90年代以来 ， 凯勒猜想的证明速度大大加快 ， 数学家只用了10年时间就把问题缩小到三个维度 。这主要得益于两位数学家的贡献 。当年 ， Perron求解1到6维时 ， 没有特殊的捷径 。 而到1990年 ， 凯勒猜想的证明方法发生了巨大的变化 。数学家Corrádi和Szabó提出了一种新的思路 ， 把原来无限空间的问题变成有限的、离散的问题 ， 也让计算机解决凯勒猜想成为可能 。他们巧妙地把凯勒猜想变成了图论问题 ， 就是构造所谓的凯勒图（Keller Graph） ， 而图论正是计算机所擅长的 。在这种方法的指导下 ， Lagarias和Shor两人很快在2年后就证明了10维空间的情况：凯勒猜想不成立 。 又过了10年 ， Mackey证明 ， 凯勒猜想在8维空间不成立 。那么 ， 凯勒图究竟是什么 ， 它为什么能够加速凯勒猜想的证明？构造“凯勒图”首先 ， 我们从最简单的2维情况说起 。现在 ， 我们有一种牌 ， 牌上画着两个有颜色的点 。 两个点是有顺序的 ， 不能调换 。 比如 ， 1黑2白≠1白2黑 。两个点总共可以涂4种颜色 ， 颜色分成2对：红色对绿色、白色对黑色 。数学家已经证明 ， 分配给点的颜色相当于正方形在空间中的坐标 。 两张牌的颜色是否配对表示两个正方形的相对位置 。点的颜色与正方形的具体关系是这样的：1、两对点完全相同 ， 表示两个正方形完全重叠
2、两对点颜色都不同 ， 且颜色都不配对 ， 表示两个正方形有部分重叠
3、一对点颜色相同 ， 另一对点颜色配对 ， 表示两个正方形共用一个边
4、一对点颜色不同 ， 另一对点颜色配对 ， 表示两个正方形的边相互接触但不重合
2个点的凯勒图 ， 要用2对颜色去填充牌面 ， 总共有16种情况 。然后我们把这16张牌摆在桌上 ， 只有符合前面条件4的两张牌 ， 才用线将二者连起来 。 这样就构成了一张“凯勒图” 。
推荐阅读
- 抑郁了？别怕，能治好！
- 慈禧太后下葬时的豪华穿戴，首次曝光
- “抖音家乡食光里”走进大唐芙蓉园
- 中国黄金周的经济复苏，是全球的榜样
- 消失了16年的诺贝尔奖得主，又有重大发现！
- 我和我的“十一”账单，“花出了过年的感觉”
- 9毛钱骑一周，共享电单车行业再现“彩虹大战”
- 三千年的青史，三千年的妲己
- 杭州小伙背着30年的房贷去相亲，结果姑娘吓到了
- 黑洞研究还不如花石纲