8维空间好砌墙——90年历史的凯勒猜想被解决

2020-09-19 04:24 作者:大老李聊数学 0人读过 | 我要投稿

每个人都应该看到过用砖块砌的墙。用砖块砌墙时，有个基本规范是，总是让某一层的砖块的左右两边与上下层砖块的中间对齐，而不是边与边对齐。如果有人把墙砌成像“田”字形的，那他砌墙不但业余，而且这墙也很危险，不安全。

现在数学家问你，有没有办法砌一堵墙，使得每块砖的每条边都与其他砖错开呢？这里，我们需要先对“错开”这个词下个科学定义。

既然是墙，我们就先限制在二维平面上，这样砖就看做矩形。我们可以这样定义二维平面上的“错开”：

在完全密铺平面的情况下，没有任何两个矩形的边是完全重合的。任何矩形的边总是接触2个或以上其他矩形的边，而不是两个矩形的等长边贴在一起。

那对砖块来说，能否做到这一点呢？答案是可以的（见图），关键在于砖的长宽长度不同。但实际上很少有人用这种模式砌墙，因为这种方式单块砖的承重更大，更不坚固。

(上图：一种矩形密铺模式，英语称为Herringbone，中文俗称“人字纹”)

数学家又问了：既然长方形可以，那如果是正方形的砖呢？稍作思考，你就会发现对正方，无法做到全错开的平铺了，没法做到水平和垂直两个方向同时错开。

数学家又问了，二维上不行，三维可以吗？这时我们又需要把三维下的问题精确定义一下：

用正立方体填充空间，是否可能避免所有立方体的两个面重合？也就是没有面贴对面的情况。

三维略微复杂点，你可能需要拿好7、8个骰子来试试。很快你会发现，三维填充也做不到以上的全错开要求。

（上图：三维下的立方体填充的一个可能模式，接下来你必然会在某个蓝色的面上出现无法错开的情况）

当然，数学家又问了，你也猜到数学家的问题了：以上这种问题，对n维空间的一般结论如何？数学家够无聊吧？

这个问题最早是1896年，德国数学家，爱因斯坦的老师，闵可夫斯基提出的。也不知道他是不是在砌墙时（玩笑）想到了这个问题：

用n维的超立方体去填充空间，是否存在可以使得不存在两个立方体共享某个n-1维的“面”？这里他考虑的填充是“晶格填充”（Lattice Tilling），意思就是有周期性和对称性的填充。

闵可夫斯基认为是不存在这样的填充方案的，这也是符合我们直觉的。前面我们已经分析过二维和三维的情况，很难想象高维情况下，存在全错开的填充方案。闵可夫斯基一开始也很自信，他发表这个猜想的时候直接说：这会是一个定理，证明我稍后给出。

但是在1907年出版的一本闵可夫斯基所著的书中，他还是把以上这个命题作为一个猜想给出，而没有给出证明。这说明他自己考虑过了，但是没能找出一个完满的证明，这个问题没有看上去得那样简单。

1930年，德国数学家奥特-海因里希·凯勒把闵可夫斯基的猜想作了少许一般化，把“晶格填充”里的“晶格”两字去掉了，意思就是用任何方式填充都可以。而且他同样猜想，用n维立方体填充n维空间，至少有两个立方体会“共享”一个n-1维的“面”。这个猜想后来就被称为“凯勒猜想”（Keller's Conjecture）。

这个猜想看上去很像是真的。1940年，德国数学家Oskar Perron证明，凯勒猜想在6维及更少维度下的都是对的。

但是万没想到，1992年，两位数学家Lagarias和Shor证明，凯勒猜想在10维空间上是错误的。

这两位数学家找到了凯勒猜想在10维空间上的一个反例，也就是在10维空间上，你可以用10维立方体填充空间，并且确保没有任何两个立方体共享9维的面。而之前有其他人证明过，如果凯勒猜想在n维上有反例，则可以构造大于n维的所有维度上的反例。所以10维有了反例后，那么10维以上，凯勒猜想都不成立了，是不是够意外？

那么还剩下7，8，9三个维度的情况不清楚。2002年，数学家Mackey找到了凯勒猜想在8维的一个反例，那么同理，9维情况下，凯勒猜想也不成立。

所以只剩7维的情况。而最近，来自斯坦福和卡内基梅隆大学等高校的4名数学家，把7维的情况解决了，他们证明7维情况下，凯勒猜想是成立的。由此凯勒猜想被彻底解决，结论就是：凯勒猜想仅在7维及以下空间成立。

以上我们看到1990年以后，凯勒猜想的证明进程被大大加速。这个加速的原因在于，1990年，Corrádi和Szabó提出了一个称为“凯勒图”的概念，可以将凯勒猜想转化为一个离散数学中的图论问题，并且可以借助计算机去搜索这个图，从而帮我们解决问题。下面简单介绍下这个思路。

n维空间的凯勒图有4^n个点构成，每个点用n个元素的向量标识，向量可以视为元素在坐标系中的坐标。

向量的元素为集合{0，1，2，3}元素之一。两个点之间有连线，当且仅当：两个点至少在两个坐标点上不同，且在至少一个坐标点上的差为2（模4）。其实能连线就表示那两个立方体的能“错开”

比如，对二维凯勒图，它有16个点。如果用颜色表示数字：黑/B=0，红/R=1，白/W=2，绿/G=3。则16个点的标识为:

[('B', 'R'), ('B', 'W'), ('B', 'G'), ('R', 'B'), ('R', 'W'), ('R', 'G'), ('W', 'B'), ('W', 'R'), ('W', 'G'), ('G', 'B'), ('G', 'R'), ('G', 'W')]

根据之前凯勒图定义，二维凯勒图只可能在1个坐标上相同，另一个坐标上“配对”（差为2，则黑与白是一对，红与绿是一对）。

不同的点的坐标关系可以看下图的解释：

根据之前的定义，可以画出二维的凯勒图如下：

（图片来源：https://www.quantamagazine.org/computer-search-settles-90-year-old-math-problem-20200819/）

根据凯勒图的定义，如果我们可以在上图中找到4个两两连接的点，则表示我们可以用这四个正方形填充平面，且互相错开，这样就推翻了凯勒猜想。这种若干个两两相连的点，术语称为“Clique”，小圈子。显然二维凯勒图中找不到这样的小圈子。

Corrádi and Szabó 在1990年证明，n维图中最多有2^n点构成的小圈子，而如果存在这种2^n个点的小圈子，则可推出n维的凯勒猜想不成立。但是，不存在小圈子，不能证明凯勒猜想正确。

1992年，Lagarias和Shor利用计算机，发现了在10维的凯勒图中，能找到个2^10=1024点构成的小圈子，所以10维情况下，凯勒猜想不成立。

之后，8维也是类似，数学家找到了这样一个256个点的小圈子:

按理说，7维的情况，凯勒图的点更少，需要找的小圈子也只有128个点，看上去更容易，那为什么是最后一个解决的情况呢？一个主要原因是7是一个质数。而8和10都是合数。要知道在高维情况下，凯勒图中的点数是很多的。比如7维情况下，有4^7个点，要对其中每2^7个点的组合一一检查，可能的组合数有10^323数量级，完全枚举的话太大了。

在8维和10维的情况下，利用对称性我们可以把高维的问题转换成低维，从而节省时间，但对7维就需要一些新的优化搜索方法。

这次，研究者在使用一些全新优化方法后，使用40台电脑，对7维的凯勒图进行搜索，仅30分钟后，计算机输出了200G的数据，确认没有找到128个点的小圈子。当然，如前所述，找不到小圈子不代表凯勒猜想成立。所以，研究者还必须提供其他一些证明，最终的论文有24页，确认7维空间中，凯勒猜想是对的。

至此，一个90年历史的数学猜想被完整解决。我最大感想是宇宙构造的奇妙，7维以上空间，你可以用正方体的砖完美填充一个空间，且每一块都错开，但为何分水岭是7到8呢？太奇妙了。

另外，凯勒猜想还有一些延伸内容，比如当初闵可夫斯基是在思考一类丢番图不等式时（而不是砌砖时），提出这个猜想的。凯勒猜想还有一个群论中的等价版本，这些留读者自行研究。

附记：《老师没教的数学》已由韩国Davinci House出版社翻译为韩文，现已上市：