制图：陶兆巍
2022年11月，陶哲轩（Terence Tao）和博士后格林菲尔德（Rachel Greenfeld）宣布推翻了一个“周期性密铺猜想”。这个猜想具体说了些什么？它有着怎样的缘起？它背后的数学理论和数学家又怎样影响了这个世界？
撰文 | 陶兆巍
审校 | 王昱
“密铺”（Tiling）指的是用几种图案无重叠，无缝隙地铺满整个平面（或者高维空间）。自古以来，几何学家和建筑师在这上面倾注了无数的心血。
这类早期探索大多属于周期性密铺——我们总可以找到一个由一些基本图案组成的图案单元，整个平面就由这个图案单元的平移所铺成。
蜥蜴密铺（“Rep-tiling”），平面可以被三种颜色的蜥蜴图案的平移所铺满。三个相邻的异色蜥蜴构成一个周期性单元。图片来源：Hyperrogue 游戏截图
到了上世纪60年代，数学家第一次构造出了“非周期性密铺”——指的是一组基本瓷砖，它们能密铺平面，但不管怎么铺都没有周期性。此后非周期密铺的研究便雨后春笋般的在数学与科学界的各个领域涌现。
70年代，一位物理学家找到了一系列简洁美观的非周期密铺，经过马丁·加德纳（Martin Gardner）在《科学美国人》上的宣传，密铺问题一下火遍了全球。
80年代，一位化学家在一次晶体X射线衍射的图样中发现了同样的非周期图案，他把这种违背周期性的物质称为“准晶体”，这为他带来了2011年的诺贝尔化学奖。
一种非周期密铺瓷砖组。图片来源：https://tilings.math.uni-bielefeld.de/substitution/schaad-7-fold/
尽管非周期密铺这个几何问题既和物理学家有纠葛，又在化学里大放异彩，还和各种的数学领域和艺术设计相关，但你可曾知道的是，历史上第一个系统性研究非周期性密铺[2][3]的是一位中国数学家——王浩。某些读者可能在高中语文课上学过汪曾祺的《金岳霖先生》，文中提到：王浩是金先生最突出的学生。后来王浩赴美留学，成为了数理逻辑学家。早在1961年，他在研究图灵问题的时候，发现计算理论中的图灵机与几何中的密铺有神奇的关联，于是他针对某种特殊的图案提出了初代版本的“周期性密铺猜想”。这个猜想最终被他的学生在博士毕业论文中推翻。从此，非周期性密铺的研究拉开了序幕。
1991年，王浩（左）在哥德尔学会年会上接受采访。图片来源：https://www.youtube.com/watch?v=hnBSRxHDxBk

王浩的拼图游戏
在1961年的论文[2]中。为了研究某类逻辑学问题的证明，王浩提出了一个几何模型，它是一个简单到可以用两句话表述规则的小游戏：
我们要用几种瓷砖铺满无穷大的地板——也即整个二维平面，每种瓷砖都有上下左右四种颜色（可重复）。只有一个要求：两块瓷砖的相邻颜色必须相同。（瓷砖方向固定，你不能把它旋转或翻面使用）
我们来看一个最简单的情形——两种瓷砖：
由于禁止旋转，这两种瓷砖是不同的。首先各取两块拼成如下2×2矩形——它的上边和下边颜色完全一致，都是左绿右黄，左右也完全一致。因此我们只需以这个2×2方块为单位，像网格纸一样把它铺开，就能铺满整个平面。

想解题的朋友，请看文章的最后几个稍难一些的王浩拼图游戏。
AI：我来试试？
我们很自然地提问：能让计算机来解这个游戏吗？也就是说，能否写个程序，我们输入一个瓷砖组合，它就能够告诉我们拼图问题有没有解？
AI连围棋都能搞定，这种问题难道不是小儿科？事实并非如此，这两者的区别在于，围棋是一个“有限”的游戏，但是拼图游戏的瓷砖种数量可以任意多，它是“无限”的游戏。对于这种无限游戏是否有机器解法，我们必须使用数学推理进行论证。
王浩的论文给出了解答：可以用程序解答，但前提是“周期性密铺猜想”成立——如果对于一组四色瓷砖这个游戏有解，那么一定有周期性的解。所谓周期性解，指的是类似于教程例子中，我们用基础瓷砖拼出一个n×m的长方形，使得它的上下颜色完全相同，左右颜色也完全相同。把它以网格纸的方式铺开得到的解我们称为周期性解。
王浩的程序。如果周期性密铺猜想成立，那它将回答任何一个拼图游戏是否有解。否则，程序永不停止的情况对应着非周期解。图片来源：Branko Grünbaum, G. C. Shephard - Tilings and patterns，page 603。翻译：陶兆巍
1964年，王浩的学生罗伯特·博格（Robert Berger）把这个问题写成了他的博士论文[4]。不过，他推翻了猜想：有一组20426种不同的瓷砖，会使拼图游戏只有非周期解。
博格的回答定下了非周期密铺研究的历史基调，甚至如今陶和格林菲尔德的研究过程也押着相同的韵脚——猜测某种周期性密铺猜想成立 → 尝试证明并且得到一些正面结论 → 结果找到了反例。同时，它也表明了王浩的拼图游戏难度如此之高——最好的AI也没法打包票说自己能够通关（或者证明无解）每一关拼图游戏。
王浩拼图这类问题我们称为“图灵完备的”，它代表着所有人类能想到的问题中最难的一类，反映着计算机计算能力的上限。数学上严格证明这件事实需要用到一种“反向编程技术”（simulation）——也就是说，密铺瓷砖的选择本身可以成为一种编程语言。就如同我们可以在Minecraft里面造一个计算机，只不过这次我们用的不是红石，而是密铺瓷砖。
这组（铺满一个象限的）王浩瓷砖等价于一个枚举素数的程序。不同数字代表不同颜色。☆代表1，P代表素数，C代表合数。图片来源：Branko Grünbaum, G. C. Shephard - Tilings and patterns，page 607
开枝散叶
尽管非周期性密铺的研究始于一个计算理论方向的数学问题，但它和各个领域有着广泛的关系。
首先，王浩拼图可以很容易地变成一个纯粹的几何问题。如图，我们可以把瓷砖的每一种颜色替换成一种“多边形锁钥”，而颜色匹配规则变成形状的匹配。问题就转化为“给定一组多边形，能否用它们铺满整个平面，但只有非周期性的铺满方式”。

Robert Ammann使用六种多边形（不计旋转、反射）构造出非周期密铺。不妨想想怎么把它补全到全平面。图片来自此链接。
不过这种思路构造出的密铺都是基于正方形的。到了70年代，彭罗斯（Goger Penrose）发现了一系列极其简洁美观的非周期性密铺[5]，而且他可以只用两种瓷砖。这类密铺与此前基于正方形的密铺看起来完全不像，反倒更像古代伊斯兰教堂的装饰[6]。彭罗斯本职是物理学家，他因黑洞信息论获得了2020年的诺贝尔物理学奖（这倒是和密铺毫无关系）。彭罗斯提出这种密铺只是出于数学上美感，没想到，这种设计的拼图游戏在商业上大受欢迎，给他带来了不少的专利费，他还因此和随意印刷这种图案的商家打了一场官司。更没想到，这种有时蕴含着“五重旋转对称”的密铺最终还带来了一个诺贝尔化学奖。
彭罗斯菱形密铺：使用了一种风筝（浅黄）和一种飞镖（红），消耗风筝的数量是飞镖的（1+√5）/ 2倍。一个技术细节：需要对图案做一点点小改动来阻止形成右侧的菱形（它当然可以周期性铺满平面），以满足严格的“非周期密铺”的定义。
图片来源：tilings.math.uni-bielefeld.de ；https://math.berkeley.edu/~kpmann/penrose%20reading.pdf
1982年，丹·谢赫特曼（Dan Shechtman）在研究铝锰合金时发现了一种五重旋转对称的原子排列。这是当时人们从未见过也不相信会存在的晶体排列模式——几何学告诉我们晶体的对称只能是2,3,4或者6重的。谢赫特曼把它称为准晶体，他的工作花了两年才得以正式发表，却受到了化学界的广泛批评，尤其以两届诺奖得主鲍林对他的攻击最为尖锐。同事认为他不会正确使用X射线仪而得到了错误的结论，把他赶出了研究小组。
铝锰合金准晶体的X衍射图。图片来源：Materialscientist/wikipedia
为了解释世界上为什么会自然形成这种非周期的准晶体，数学家引入了一些新方法。比较重要的观点来自玻尔（Harald Bohr）[7]和德布勒因（De Bruijin）[8]，他们证明这种非周期图案来自高维周期晶格的二维“无理”切面——如果说晶体是化学中的有理数，那么准晶体就是化学中的无理数。但与无理数的发现者传说中被处死的悲剧不同，一开始缺乏支持者的谢赫特曼最终得以独享2011年的诺贝尔化学奖。
回到数学上的非周期密铺。一开始博格使用了两万多个瓷砖，之后数学家把所需的瓷砖数越缩越小，彭罗斯只用了两块瓷砖（但可旋转），那么，一块够吗？
只要两块瓷砖，而且可以是分形的。图片来源：https://tilings.math.uni-bielefeld.de/substitution/fractal-kite-dart/
答案分几种情况：
  1. 如果允许瓷砖旋转，那么一块瓷砖可以做到非周期密铺[9]。（这被戏称为“爱因斯坦问题”，因为Ein Stein 的德语意思是“一块瓷砖”）
  2. 如果不允许旋转和反射，那么在2维的情况下[10]，一块瓷砖无法形成非周期密铺。
  3. 但同样不允许旋转和反射，对于很大的维数d（d大概是一个10¹⁹⁹位数），一块“瓷砖”就够了。甚至这块瓷砖可以选择地如此巧妙，使得拼图问题是否有解变得数学上不可判定（ZFC-undecidable）——它在我们标准的数学宇宙中有解，但在“非标准的数学”中无解——王浩曾表明不可判定的密铺一定是非周期的[3][11]。这“一块瓷砖”正是陶和格林菲尔德最新的成果。他们的主要证明技巧仍然保有王浩时代的痕迹——用瓷砖作为编程语言，编写了一个“只有非周期解的数独问题”。

三维爱因斯坦问题的瓷砖。图片来源：Edmund Harriss/wikipedia
关于王浩瓷砖本身的探索也从来没有停止过。其实，陶哲轩团队的前一篇文章[12]使用的就是王浩瓷砖；数学以外，程序员用王浩瓷砖法来绘制纹理[13]；游戏制作者用它来生成游戏地图[14]；音乐家甚至试图使用它作曲[15]。

较为简单的王浩拼图往往有着很多容易构造的解，这可以用来生成游戏地图。图片来源：https://ijdykeman.github.io/ml/2017/10/12/wang-tile-procedural-generation.html
王浩还留下了什么？
作为逻辑学黄金时代——20世纪中叶时期世界范围内极其重要的逻辑学家，王浩先生似乎反而在中文材料中较少被提及。从西南联大和清华毕业以后，王浩来到美国，花了两年拿到哈佛的博士学位。王浩的研究领域一开始主要在逻辑和数学哲学上。他是哥德尔和维特根斯坦的继承人，在哲学方面有广泛的著作。

王浩有许多哲学著作，这是其中的一本。图片来源：豆瓣
但是，王浩在计算机理论上却建树繁多。据他自己所说[19]，父亲劝他回国为新中国的工业化做贡献，但“光是懂得一些哲学怎么对工业化作贡献”？于是他开始转而研究计算机。除了在密铺问题和早期的“生命游戏”上的贡献，王浩还是机器证明的奠基人，1958年他在IBM-704计算机上写了个精妙的程序，只用几分钟就证明了罗素的《数学原理》中220条定理，这个工作为他赢得了1983年的机器证明里程碑奖[16]。
2022年，“计算机界的菲尔兹奖”——Abacus奖得主Mark Braverman[17]，因为他建立了“信息交流的复杂度理论”。他的导师是斯蒂芬·库克（Stephen Cook）——计算复杂度理论的奠基人，P=NP猜想的提出者。库克使用了类似的“反向编程方法”，找到了历史上第一个NP-完全问题。
库克的博士生导师是王浩。据此文[18]考证，王浩早在1953年（未能发表）的文章中就提出了“计算速度函数”——也就是如今大O小o记号的雏形，用来反映（当时还不存在的）计算复杂度的概念。王浩的灵感则可能来源与1939年图灵和维特根斯坦的讨论记录。
在这条隐秘的线索中，我们得以窥见承载着整个信息时代的理论根基，而王浩，则无疑是其中最重要的一位筑基人。
来解题吧！
难度：☆×1
难度：☆×2
难度：☆×3
难度：☆×4
难度：☆×99
图片来源：Emmanuel Jeandel，Michael Rao
（答案在本次推送的最后一条）
（还可以尝试“有限版本的王浩拼图游戏”[20]，链接需要用电脑打开）
参考文献：
[1]陶哲轩团队最新论文 https://arxiv.org/abs/2211.15847
[2王浩瓷砖的第一篇论文 https://doi.org/10.1002/j.1538-7305.1961.tb03975.x
[3]王浩几年后对瓷砖问题的回顾
https://www.semanticscholar.org/paper/Notes-on-a-class-of-tiling-problems-Wang/7813ebbf4262194e0dbdd8a8e89e899ff9d3e67f
[4]R. Berger, The undecidability of the domino problem, Memoirs of the American Mathematical Society, 66 (1966) 72. Link：https://www.doi.org/10.1090/MEMO/0066
[5]R., Penrose. (1974). The role of aesthetics in pure and applied mathematical research.  10:266-271.
[6]https://dx.doi.org/10.1126/science.1135491
[7]DOI: 10.1007/BF02395468
[8]de Bruijn, N. (1981). "Algebraic theory of Penrose's non-periodic tilings of the plane". Nederl. Akad. Wetensch. Proc. A84: 39.
[9]https://en.wikipedia.org/wiki/Einstein_problem
[10]https://arxiv.org/abs/1602.05738
[11]R. M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, (1971), 12 (3), 177-–209.
[12]https://arxiv.org/pdf/2108.07902.pdf
[13]王浩瓷砖用于绘制图案纹理 https://link.springer.com/book/10.1007/978-3-031-79537-4
[14]https://www.youtube.com/watch?v=XVIYY0AQF-8
[15]一位音乐家提出构想，使用王浩瓷砖生成周期性和非周期性的音乐片段https://gershonwolfe.com/wordpress_6/?page_id=2
[16]https://www.ams.org/profession/prizes-awards/ams-supported/atp-prizes
[17]https://www.quantamagazine.org/mark-braverman-wins-the-imu-abacus-medal-20220705/
[18]https://arxiv.org/abs/2206.05274
[19]王浩访谈 https://gershonwolfe.com/wordpress_6/?page_id=2
[20]游戏链接（需要用电脑打开）：https://smart-games.org/en/tetravex/game

来源：科普中国-星空计划（创作培育）
《环球科学》1月新刊
正在热卖

各电商平台均有销售
点击【在看】，及时接收我们的内容更新 
继续阅读
阅读原文