2022年11月,陶哲轩(Terence Tao)和博士后格林菲尔德(Rachel Greenfeld)宣布推翻了一个“周期性密铺猜想”。这个猜想具体说了些什么?它有着怎样的缘起?它背后的数学理论和数学家又怎样影响了这个世界?
“密铺”(Tiling)指的是用几种图案无重叠,无缝隙地铺满整个平面(或者高维空间)。自古以来,几何学家和建筑师在这上面倾注了无数的心血。这类早期探索大多属于周期性密铺——我们总可以找到一个由一些基本图案组成的图案单元,整个平面就由这个图案单元的平移所铺成。
到了上世纪60年代,数学家第一次构造出了“非周期性密铺”——指的是一组基本瓷砖,它们能密铺平面,但不管怎么铺都没有周期性。
此后非周期密铺的研究便雨后春笋般的在数学与科学界的各个领域涌现。70年代,一位物理学家找到了一系列简洁美观的非周期密铺,经过马丁·加德纳(Martin Gardner)在《科学美国人》上的宣传,密铺问题一下火遍了全球。80年代,一位化学家在一次晶体X射线衍射的图样中发现了同样的非周期图案,他把这种违背周期性的物质称为“准晶体”,这为他带来了2011年的诺贝尔化学奖。
尽管非周期密铺这个几何问题既和物理学家有纠葛,又在化学里大放异彩,还和各种的数学领域和艺术设计相关,但你可曾知道的是,历史上第一个系统性研究非周期性密铺的是一位中国数学家——王浩。早在1961年,他在研究图灵问题的时候,发现计算理论中的图灵机与几何中的密铺有神奇的关联,于是他针对某种特殊的图案提出了初代版本的“周期性密铺猜想”。这个猜想最终被他的学生在博士毕业论文中推翻。
从此,非周期性密铺的研究拉开了序幕。
王浩的拼图游戏在1961年的论文中。为了研究某类逻辑学问题的证明,王浩提出了一个几何模型,它是一个简单到可以用两句话表述规则的小游戏:我们要用几种瓷砖铺满无穷大的地板——也即整个二维平面,每种瓷砖都有上下左右四种颜色(可重复)。只有一个要求:两块瓷砖的相邻颜色必须相同。(瓷砖方向固定,你不能把它旋转或翻面使用)
我们来看一个最简单的情形——两种瓷砖:由于禁止旋转,这两种瓷砖是不同的。首先各取两块拼成如下2×2矩形——它的上边和下边颜色完全一致,都是左绿右黄,左右也完全一致。因此我们只需以这个2×2方块为单位,像网格纸一样把它铺开,就能铺满整个平面。
尽管非周期性密铺的研究始于一个计算理论方向的数学问题,但它和各个领域有着广泛的关系。首先,王浩拼图可以很容易地变成一个纯粹的几何问题。如图,我们可以把瓷砖的每一种颜色替换成一种“多边形锁钥”,而颜色匹配规则变成形状的匹配。问题就转化为“给定一组多边形,能否用它们铺满整个平面,但只有非周期性的铺满方式”。
不过这种思路构造出的密铺都是基于正方形的。
到了70年代,彭罗斯(Goger Penrose)发现了系列极其简洁美观的非周期性密铺,而且他可以只用两种瓷砖。这类密铺与此前基于正方形的密铺看起来完全不像,反倒更像古代伊斯兰教堂的装饰。彭罗斯本职是物理学家,他因黑洞信息论获得了2020年的诺贝尔物理学奖(这倒是和密铺毫无关系)。
彭罗斯提出这种密铺只是出于数学上美感,没想到,这种设计的拼图游戏在商业上大受欢迎,给他带来了不少的专利费,他还因此和随意印刷这种图案的商家打了一场官司。更没想到,这种有时蕴含着“五重旋转对称”的密铺最终还带来了一个诺贝尔化学奖。
1982年,丹·谢赫特曼(Dan Shechtman)在研究铝锰合金时发现了种五重旋转对称的原子排列。这是当时人们从未见过也不相信会存在的晶体排列模式——几何学告诉我们晶体的对称只能是2,3,4或者6重的。谢赫特曼把它称为准晶体,他的工作花了两年才得以正式发表,却受到了化学界的广泛批评,尤其以两届诺奖得主鲍林对他的攻击最为尖锐。同事认为他不会正确使用X射线仪而得到了错误的结论,把他赶出了研究小组。
为了解释世界上为什么会自然形成这种非周期的准晶体,数学家引入了一些新方法。比较重要的观点来自玻尔(Harald Bohr)和德布勒因(De Bruijin),他们证明这种非周期图案来自高维周期晶格的二维“无理”切面——如果说晶体是化学中的有理数,那么准晶体就是化学中的无理数。但与无理数的发现者传说中被处死的悲剧不同,一开始缺乏支持者的谢赫特曼最终得以独享2011年的诺贝尔化学奖。
回到数学上的非周期密铺。一开始博格使用了两万多个瓷砖,之后数学家把所需的瓷砖数越缩越小,彭罗斯只用了两块瓷砖(但可旋转),那么,一块够吗?答案分几种情况:1. 如果允许瓷砖旋转,那么一块瓷砖可以做到非周期密铺。(这被戏称为“爱因斯坦问题”,因为Ein Stein的德语意思是“一块瓷砖”)2. 如果不允许旋转和反射,那么在2维的情况下,一块瓷砖无法形成非周期密铺。
3. 但同样不允许旋转和反射,对于很大的维数d(d大概是一个101??位数),一块“瓷砖”就够了。甚至这块瓷砖可以选择地如此巧妙,使得拼图问题是否有解变得数学上不可判定(ZFC-undecidable)——它在我们标准的数学宇宙中有解,但在“非标准的数学”中无解——王浩曾表明不可判定的密铺一定是非周期的。这“一块瓷砖”正是陶和格林菲尔德最新的成果。
他们的主要证明技巧仍然保有王浩时代的痕迹——用瓷砖作为编程语言,编写了一个“只有非周期解的数独问题”。
关于王浩瓷砖本身的探索也从来没有停止过。其实,陶哲轩团队的前一篇文章使的就是王浩瓷砖;数学以外,程序员用王浩瓷砖法来绘制纹理;游戏制作者用它来生成游戏地图;音乐家甚至试图使用它作曲。
作为逻辑学黄金时代——20世纪中叶时期世界范围内极其重要的逻辑学家,王浩先生似乎反而在中文材料中较少被提及。
从西南联大和清华毕业以后,王浩来到美国,花了两年拿到哈佛的博士学位。王浩的研究领域一开始主要在逻辑和数学哲学上。他是哥德尔和维特根斯坦的继承人,在哲学方面有广泛的著作。但是,王浩在计算机理论上却建树繁多。据他自己所说,父亲劝他回国为新中国的工业化做贡献,但“光是懂得一些哲学怎么对工业化作贡献”?于是他开始转而研究计算机。
除了在密铺问题和早期的“生命游戏”上的贡献,王浩还是机器证明的奠基人,1958年他在IBM-704计算机上写了个精妙的程序,只用几分钟就证明了罗素的《数学原理》中220条定理,这个工作为他赢得了1983年的机器证明里程碑奖。