首页科技快讯困扰数学界90年的难题：凯勒猜想被完全破解

困扰数学界90年的难题：凯勒猜想被完全破解

来源：晰数塔互联网快讯时间：2020年08月24日 10:08

本文来自微信公众号：原理（ID：principia1687），作者：佐佑，头图来自：pixabay

一

最近，一个由计算机科学家和数学家组成的团队，彻底解决了一个被称为凯勒猜想的数学难题。凯勒猜想是一个已存在了90年之久的谜题，它与不同空间维度上的密铺问题有关。

我们可以先从最简单的二维情况开始。在二维空间中，用相同大小的正方形瓷砖进行密铺时，是否总会出现两块瓷砖具有一整条共享的边的情况？从图形上不难看出，情况的确是这个样子。

在二维空间中，用同等大小的正方形瓷砖密铺时，黄色的边表示的即是两块完全链接的瓷砖。| 图片参考来源：cs.cmu.edu

将这个问题从二维提升到三维空间，情况也是如此吗？

不难看出，当用大小相同的立方体来完全填充一个空间时，必定有两个立方体完全共享一个面的情况出现。

三维空间中用相同大小的立方体密铺，会导致两个立方体共享一个面。黄色方形便是共享会出现的地方。| 图片参考来源：cs.cmu.edu

二维、三维的情况是我们尚可想象的空间，但是在更高的维度上，情况又是如何？1930年，德国数学家奥特-海因里希·凯勒（Ott-Heinrich Keller）提出猜想，认为这种模式适用于任何维度。这便是凯勒猜想。

二

在那之后的几十年里，凯勒猜想取得了众多进展。1940年，数学家Oskar Perron成功证明，凯勒猜想在六维以及更小的维度上是正确的。然而在1992年，Jeffrey Lagarias和Peter Shor的工作表明，当维度提高到十以及以上时，这个猜想便不再成立。到了2002年，John Mackey进一步将这个“不适用范围”缩小到了八维空间，表明它在八个或八个以上的维度上便不再适用。如此一来，仍处于未知状态的就是七维空间中的情况了。

从Perron到Lagarias和Shor，在数学家们向这个猜想发起挑战的过程中，研究方法发生了重大变化。在Perron的年代，他依靠的是笔和纸来计算这种模式在前六个维度中的适用情况；到了1990年代，为了能让强大的计算机加入这项挑战，数学家Keresztély Corrádi和Sándor Szabó对这一猜想进行了重新表述，将它转化成了一种完全不同的形式。

凯勒猜想原本涉及到的是光滑的连续空间，在这种空间里，存在无穷多种方式来进行无穷多个瓷砖的密铺，而这种无穷大是计算机并不擅长处理的问题。因此Corrádi和Szabó将猜想转化成了某种涉及到离散的、有限的物体的问题来处理。这样一种等价方法有效地将一个关于无穷大的问题，简化成了关于几个数字的算术问题，它所涉及到的一个基础核心是一种被称为凯勒图的图形。

三

简单说来，凯勒图是由具有特定点数的骰子，以及这些骰子之间的连线构成的。点数对应于维数，要判断凯勒猜想在n维空间上是否正确，可以通过在凯勒图上寻找是否存在2ⁿ个彼此之间相互连接的骰子组成的小集合，如果存在，那么凯勒猜想在n维中就是不正确的。

以二维空间中的凯勒猜想为例，首先想象桌子上摆放着一些骰子，且对于每个骰子来说，朝上摆放的那一面的点数为2——这两个点就对应于二维，它们的位置就代表着坐标系中的x轴和y轴。接着，分别用红、绿、黑、白四种颜色任意地给每个点涂上颜色，并将红和绿，黑和白设定为两组“配对色”。

现在，当两个骰子的相同位置的点有不同的颜色，而另一个位置的点的颜色不仅不同，且颜色配对（红和绿，或者黑和白）时，就将这两个骰子骰子用直线连接起来，如下图中的第四种情况，就满足用线连接的条件。

二维的凯勒图中的骰子上有两个点，如果两个骰子上的点的颜色完全相同，意味着两个瓷砖在空间中完全重合；如果两个骰子既没有共同颜色，也没有配对色，意味着瓷砖部分重叠（一种密铺问题中是不允许存在的情况）；如果两个骰子有一位置上的颜色配对，另一个位置上的颜色相同，意味着两块瓷砖有一个共享面；当两个骰子之间存在连接，代表着两个瓷砖相互接触，但彼此略微错位。最后这种情况是在证明凯勒猜想时所要寻找的例子，它代表着那些相互接触却没有共享面的瓷砖。| 图片参考来源：Samuel Velasco / Quanta Magazine

在凯勒图中，每个骰子可被看成是凯勒猜想中的一块瓷砖；骰子上的颜色可被看作是坐标，定义了瓷砖在空间中的位置；而骰子之间存在连接与否，可被看作是对两个瓷砖的相对位置的描述。

二维空间的凯勒图。| 图片参考来源：cs.cmu.edu

上图所示的就是二维情况的凯勒图，它由16个点数为2的骰子组成。就像前面已经提到的，这张图能将凯勒猜想的证明，变成判断能否找到4（即2²）个这样的骰子形成一个完全彼此相互连接的小集合，如果能，那么就证明凯勒猜想在二维空间中是错误的。

由4个骰子组成的完全彼此连接的小集合。| 图片参考来源：Quanta Magazine

但从二维凯勒图上可以看出，这样的小集合并不存在，因此凯勒猜想在二维空间中是正确的。

四

Corrádi和Szabó利用这种方法，用216个具有3个点的骰子证明了凯勒猜想适用于三维空间，在这种情况下，他们要寻找的反例是8（即2³）个相互连接的骰子。Mackey则通过找到256（即2⁸）个具有8个点的骰子的小集合，证明了凯勒猜想不适用于八维以及更高的维度。

要判断七维空间是否适用于凯勒猜想，需要判断能否找到128（即2⁷）个具有7个点的骰子的小集合。七维空间一直是个难点，这与它是的素数本质不无关系，这意味着它无法被分解成更低的维度。

终于，在新的研究中，数学家Joshua Brakensiek、Marijn Heule、Mackey以及David Narváez在40台计算机的帮助下解决了这个问题。计算机就给出的最终答案是：是的。这意味着，我们终于知道了凯勒猜想在最后一个维度上的适用情况，证明凯勒猜想在七维空间中仍然正确。而计算机提供的答案也远不止一个简单的结论，它还包括了一个大小为200Gb的证据来证明这个答案是正确的。

至此，凯勒猜想可被认为已被完全解决。

参考来源：

https://www.cs.cmu.edu/~mheule/Keller/

https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/

https://mathworld.wolfram.com/KellersConjecture.html

本文来自微信公众号：原理（ID：principia1687），作者：佐佑，头图来自：pixabay