创新网

存在90年的凯勒猜想被完全破解

创新网 2020-08-27 08:34 出处:&nbsp;原理最近,一个由计算机科学家和数学家组成的团队,彻底解决了一个被称为凯勒猜想的数学难题。凯勒猜想是一个已存在了90年之久的谜题,它与不同空间维度上的密铺问题有关。我们可以先从最简单的二维情况开始。在二维空间中,用相同大小的" /> <meta name="tags" content="数学" /> <meta content="always" name="referrer" / 编辑:@科技资讯网
来源:原理 最近,一个由计算机科学家和数学家组成的团队,彻底解决了一个被称为凯勒猜想的数学难题。凯勒猜想是一个已存在了90年之久的谜题,它与不同空间维度上的密铺问题有关。

来源:原理

存在90年的凯勒猜想被完全破解

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

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

存在90年的凯勒猜想被完全破解

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

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

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

存在90年的凯勒猜想被完全破解

三维空间中用相同大小的立方体密铺,会导致两个立方体共享一个面。黄色方形便是共享会出现的地方。| 图片参考来源: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轴。接着,分别用红、绿、黑、白四种颜色任意地给每个点涂上颜色,并将红和绿,黑和白设定为两组“配对色”。

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

存在90年的凯勒猜想被完全破解

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

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

存在90年的凯勒猜想被完全破解

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

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

存在90年的凯勒猜想被完全破解

由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的证据来证明这个答案是正确的。

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

存在90年的凯勒猜想被完全破解

0

精彩评论

暂无评论...
验证码 换一张
取 消