用户名:  密码:   
网站首页即时通讯活动公告最新消息科技前沿学人动向两岸三地人在海外历届活动关于我们联系我们申请加入
栏目导航 — 美国华裔教授专家网科技动向科技前沿
关键字  范围   
 
存在90年的凯勒猜想被完全破解
来源:佐佑 | 2020/8/25 23:36:01 | 浏览:169 | 评论:0

 

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

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

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

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

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

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

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

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

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

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

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

从Perron到Lagarias和Shor,在数学家们向这个猜想发起挑战的过程中,研究方法发生了重大变化。在Perron的年代,他依靠的是笔和纸来计算这种模式在前六个维度中的适用情况;到了1990年代,为了能让强大的计算机加入这项挑战,数学家Keresztély CorrádiSá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 BrakensiekMarijn Heule、Mackey以及David Narváez40台计算机的帮助下解决了这个问题。计算机就给出的最终答案是:是的。这意味着,我们终于知道了凯勒猜想在最后一个维度上的适用情况,证明凯勒猜想在七维空间中仍然正确。而计算机提供的答案也远不止一个简单的结论,它还包括了一个大小为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

相关栏目:『科技前沿
欧盟公布五大研究领域:癌症、气候变化、碳中和城市、健康水域及土壤健康 2020-09-23 [6]
2020年度国家自然科学基金申请项目评审结果公布 2020-09-20 [51]
2020软科中国大学排名系列:学科精度排名 2020-09-20 [84]
30年升温10℃ “新北极”正在形成 2020-09-20 [32]
教育部正式公布首批国家“拔尖计划”2.0名单,33所高校入选 2020-09-20 [83]
Clarivate Analytics 公布 ESI(基本科学指标)全球大学排名 2020-09-17 [170]
量子纠缠很好地解释了人与人之间的缘分 2020-09-17 [115]
20年消失176种期刊的背后…… 2020-09-16 [71]
五个人类无法破解的宇宙之谜 2020-09-15 [241]
10名华裔精英入选加拿大皇家学会新院士! 2020-09-13 [134]
相关栏目更多文章
最新图文:
Colleen Flaherty 翻译 刘勤:MIT教授发文《美国经济评论》 :生命科学受益于明星科学家们的死亡 :北京和上海金融人的最新鄙视链 :日本政府《氢能利用进度表》 :美国《2016-2045年新兴科技趋势报告》 :天津工业大学“经纬英才”引进计划 :浙江财经大学国际青年学者论坛的邀请函 (10/31-11/1) :南宁职业技术学院2019年招聘公告 :美国加大审查范围 北大多名美国留学生遭联邦调查局质询
更多最新图文
更多《即时通讯》>>
 
打印本文章
 
您的名字:
电子邮件:
留言内容:
注意: 留言内容不要超过4000字,否则会被截断。
未 审 核:  是
  
关于我们联系我们申请加入后台管理设为主页加入收藏
美国华裔教授专家网版权所有,谢绝拷贝。如欲选登或发表,请与美国华裔教授专家网联系。
Copyright © 2020 ScholarsUpdate.com. All Rights Reserved.