陶哲轩：用数独和俄罗斯方块游戏找反例，推翻周期性平铺猜想

·寻找非周期性平铺方案和相关瓷砖的过程，如同打碎一个花瓶然后再复原它。不过，研究者希望花瓶碎裂后形成的是均匀的碎片，且破碎的纹理是“非周期性的”。这样的瓷砖即使铺满全世界，拼接图案也不会重复。

华裔数学家、菲尔兹奖得主、美国加州大学洛杉矶分校数学系教授陶哲轩（Terence Tao）

能否寻找到一块这样的瓷砖，即使用它铺满全世界，其拼接图案也永不重复？

近日，数学界的“莫扎特”、华裔数学家、菲尔兹奖得主、美国加州大学洛杉矶分校数学系教授陶哲轩（Terence Tao）在个人博客上宣布，推翻了“周期性平铺猜想”。

他们在超高维空间中找到一块这样的“瓷砖”。

预印本网站arXiv显示，陶哲轩与合作者合著的相关论文于2022年11月29日凌晨上传。

但实际上，陶哲轩提前了两个多月就在其博客上宣布了上述消息；并在9月18日凌晨，他们向arXiv网站提交了一篇缩略的“公告”论文——announcement，全文共13页。

而完整版论文共48页。论文标题是《周期性平铺猜想的一个反例》（A counterexample to the periodic tiling conjecture）。

该论文的合著者是原美国加州大学洛杉矶分校数学系Hedrick助理教授、现美国普林斯顿高等研究院数学学院成员雷切尔·格林菲尔德（Rachel Greenfeld）。她是陶哲轩的博士后。

诺贝尔奖和永不重复的拼图 

什么是周期性平铺猜想？

设想用相同大小的正方形瓷砖，去铺满一个方方正正房间的地面，这似乎难度不大。人们只要像“复制黏贴”一样，不留空隙地将一块块大小合适的瓷砖平铺下去就行。在这样的地板上，图案的周期性显而易见：如果你将部分图案平移到另一个位置，就跟没有移动过一样。

这或许是最容易的“施工方案”之一，被称为周期性平铺。

周期性平铺和非周期性平铺产生的不同效果。截图来自《Aperiodic Texture Mapping》

六年前，2016年2月18日，来自印度孟买塔塔基础研究所数学院的数学家悉达多·巴塔查里亚（Siddhartha Bhattacharya）在arXiv网站上传预印本论文“Periodicity and decidability of tilings of ℤ^2”，宣布其在二维平面上证明了“周期平铺猜想”——通过平移，单个瓷砖在平面上只能进行周期性平铺，无法进行非周期性平铺。

数学家们推测，在二维以上更高维度上，也不存在用同一种就实现非周期性平铺的瓷砖。这一假设被称为“周期性平铺猜想”。

换句话说，“周期性平铺猜想”断言，如果只能以平移的方式平铺或填充，那么在任意维度上（二维及以上），不存在一块能以非周期性的方式铺满整个表面或填充整个空间的特殊瓷砖。即使设计出来这样一块瓷砖，那么它也只能以周期性的方式平铺或填满相应的空间。

但“周期性平铺猜想”似乎只在二维平面上成立。

彭罗斯瓷砖样式之一。截图自Eureka 39(1978) 16-32

早在六十年前，1960年左右，在牛津大学任教的华裔数学家王浩在对美国新泽西州的贝尔电话实验室进行学术访问期间，研究了周期性平铺问题，并提出“王砖”（或王氏砖、王浩瓷砖，aka Wang squares）模型。

部分王浩瓷砖。来自Parcly Taxel 

四年后，一种似乎更高级的方案出现了：非周期性平铺。它虽然也是很多块瓷砖拼接在一起，密密麻麻地铺满整个地板，但其拼接的图案永不重复，即使铺满整个世界也不重复。1964年，王浩的学生Robert Berger提出最早的非周期性平铺方案，需要20426块瓷砖组合。

用“王砖”进行的一种非周期性平铺。来自Claudio Rocchini

随后，英国数学物理学家、牛津大学数学系名誉教授罗杰·彭罗斯（Roger Penrose）把需要的瓷砖组合减少到5种，最后只用2种形状的瓷砖组合，比如一大一小两个菱形，就可以在二维平面上实现非周期性平铺。这种瓷砖被称为彭罗斯瓷砖。它成为数学艺术的象征之一，被铺在牛津大学数学系等知名大学相关建筑物的地板上。相关平铺样式被称为彭罗斯平铺，或彭罗斯镶嵌、彭罗斯密铺、彭罗斯拼图、彭罗斯几何拼图等。

平面上的非周期图案具有一个奇特的性质，排布位置的信息似乎能够通过某种方式跨过很大距离进行传递，防止数百（甚至数千、数百万）块之外的瓷砖出现某种排列类型。阿肯色大学助理教授埃蒙德·哈里斯（Edmund Harriss）的博士论文主题就是彭罗斯贴砖。他说：“局部约束鬼使神差地拓展为全局约束。”

而彭罗斯瓷砖不只在数学界很有名，在建筑装潢领域甚至材料科学领域也成功圈粉，给人们带来新的启示。

彭罗斯瓷砖或拼图的样式之一。来自Taktaal 

1982年，在美国正进行学术休假的以色列材料科学家丹·谢特曼（Dan Shechtman），在实验室里观察到合金的奇特衍射图样，不符合此前人们关于晶体的印象，缺乏标准的对称。它们原子排列的样子，跟彭罗斯地砖拼接的图案一样，是非重复、非周期性的。他后来称之为“准晶体”（quasicrystal）。

丹·谢特曼拍摄到的电子衍射图片。截图自Phys. Rev. Lett. Vol. 53(20),1984

丹·谢特曼的论文和他的发现引起了极大的争议和攻击。直到20多年后，2011年，他因“发现准晶体”，被授予诺贝尔化学奖。

准晶体的电子衍射图片。来自nobelprize.org

此外，彭罗斯也是诺贝尔奖得主之一。

1965年1月18日，彭罗斯在《物理评论快报》（Physical Review Letters）发表论文，阐述了彭罗斯奇点定理。斯蒂芬·霍金（Stephen Hawking）与彭罗斯一起研究奇点后，以彭罗斯定理颠覆了有关宇宙起源的理论。奇点后来被人们熟知，称为“黑洞”。

2020年，89岁的彭罗斯被授予诺贝尔物理学奖，表彰他“发现黑洞的形成是对广义相对论的有力预测”。他独享一半奖金，与“在银河系的中心发现了一个超大质量致密天体”的德国科学家赖因哈德·根策尔（Reinhard Genzel）和美国科学家安德烈娅·盖兹（Andrea Ghez）分享了2020年的诺贝尔物理学奖。

但问题是，一直没人用一块瓷砖完成非周期平铺“游戏”。直到最近，陶哲轩和合作者在超高维空间找到一块这样奇特的“瓷砖”。

用数独、俄罗斯方块游戏寻找一个反例

寻找非周期性平铺方案和相关瓷砖的过程，如同打碎一个花瓶然后再复原它。不过，研究者希望花瓶碎裂后形成的是均匀的碎片，且破碎的纹理是“非周期性的”。

从在二维平面“拼图”到更高维空间里“堆积木”，陶哲轩希望找到一块能够实现非周期性地堆叠的单一“瓷砖”。

立方形密铺。来自Tomruen 

在解释其最新证明策略和方法的博客文章中，陶哲轩提到数独和俄罗斯方块游戏，还有电脑编程。

在印度数学家悉达多·巴塔查里亚证明“周期平铺猜想”在二维平面上成立三年后，2019年，格林菲尔德以博士后身份来到加州大学洛杉矶分校。随后，她和陶哲轩用不同于悉达多·巴塔查里亚的另一种方法，再次证明了二维平面中的“周期平铺猜想”。但是，当他们想推进到在三维空间中也证明这一猜想时，碰壁了。

陶哲轩说，无法在更高维度上证明这个猜想成立也许是有原因的，应该开始寻找反例。

2021年8月，他们第一次接近目标：他们在超高维空间找到了两块可以实现非周期性填充的瓷砖，但不是一块。

2021年8月17日，格林菲尔德在arXiv网站上传她和陶哲轩共同署名的论文，标题是“Undecidable translational tilings with only two tiles, or one nonabelian tile”。六天后，她上传了更新版。

“2非常接近了，但还不够。” 格林菲尔德说。

像“俄罗斯方块游戏”一样消行。截图自陶哲轩2022年9月19日的博客文章

2022年9月19日，陶哲轩在其博客文章中表示，“格林菲尔德和我刚刚将我们的公告——‘周期性平铺猜想的反例’上传到 arXiv。这是我们目前正在撰写（并希望在几周内发布）的一篇更长的论文的公告。其中，我们推翻了 Grünbaum-Shephard 和 Lagarias-Wang 的周期性平铺猜想。”

在上述博客文章中，陶哲轩写道，他们创建了一种“平铺语言”（“tiling language”），使用平铺方程组来描述非周期函数。“这个证明，让人强烈地联想到解决数独谜题所需的推理类型，因此，我们在论点中采用了一些类似数独的术语来提供直觉和视觉效果。一个关键步骤是，对拼图进行剪切变换……然后执行消除常量行的‘俄罗斯方块’移动以得出次级数独谜题，然后依次分析该谜题。正是这个过程的迭代最终生成了非周期性p-adic结构。”

在其两个月后、11月29日的博客文章中，陶哲轩写道：“格林菲尔德和我刚刚将论文上传到 arXiv。这是我几个月前在这个博客上公布的结果的完整版本……这篇论文完成的时间比预期的要长一些，这是由于我们在发布公告时没有意识到的一个技术问题需要个解决方法。”

陶哲轩进一步解释说，如公告中所述，最初的策略是构建一种“平铺语言”——一种能够用来编码“P进数数独谜题”（P-adic Sudoku puzzle）的语言；然后证明如果P是一个足够大的素数，那么后一种类型的谜题只有非周期性的解决方案。“事实证明，该策略的后半部分成功了。”“在编程过程中，我们还发现，一旦引入‘可表达属性’和‘弱表达属性’两个新定义，证明的编码部分将变得更加模块化和概念化。”

陶哲轩和格林菲尔德将他们的方程式系统看作一个计算机程序：每一行代码或方程式都是一个命令，这些命令组合起来可以生成一个实现特定目标的程序。

最终，他们在一个非常高维度的空间中，尚未被详细计算，但大约2^100^100维里，找到一块目标“瓷砖”——一块非常复杂、弯弯曲曲、充满孔洞的“瓷砖”。

此外，陶哲轩表示，使用他们最新创造的“语言”应该能创造一个无法判定的谜题。“（比如）可能存在一些瓷砖，我们永远也无法证明，它是否能铺满它所在的空间。”

既无法证明也无法反驳，数学中充满了这样的“不可判定”（undecidable）的陈述。为了证明一个陈述是不可判定的，数学家通常证明它等价于另一个已知不可判定的问题。所以，如果平铺问题被证明是不可判定的，它将可以作为新工具，证明更多其他问题的不可判定性。

格林菲尔德的简历显示，其研究课题“平移平铺和正交系统指数”（translational tiling and orthogonal systems exponentials）获得了美国国家科学基金会（NSF）11.7056万的资助，编号是DMS-2242871，资助期限是2022年到2025年。

参考资料：

1.https://www.quantamagazine.org/nasty-geometry-breaks-decades-old-tiling-conjecture-20221215/#newsletter

2.https://nautil.us/impossible-cookware-and-other-triumphs-of-the-penrose-tile-rp-234895/?_sp=1048d065-5002-434f-85c5-fa868cbccae2.1671370700212

3.https://huanqiukexue.com/a/qianyan/cailiao__huaxue/2017/0527/27301.html

4.https://terrytao.wordpress.com/2022/09/19/a-counterexample-to-the-periodic-tiling-conjecture/

5.https://arxiv.org/abs/1602.05738