查看原文
其他

业余爱好者的两番重要发现,帮组合数学迎来关键突破

嘉伟 返朴 2023-08-12

星标,才能不错过每日推送!方法见文末动图


2023年3月,一个由职业数学家和爱好者组成的小团队发表了一项重要的工作,他们发现了一个“帽子”图形,可以解决平面密铺领域的“爱因斯坦问题”。仅仅三个月后,他们再进一步,在帽子的基础上找到了无需镜像对称的非周期密铺图形。而这些惊人的发现,是从一位业余数学爱好者开始的。



撰文 | 嘉伟

“它竟然就隐藏在众目睽睽之下。”

——宾夕法尼亚州摩拉维亚大学名誉数学教授 Doris Schattschneider



2022年11月中旬,已退休的印刷技师David Smith有了充足的时间去做他最喜欢的事情之一:摆弄和设计拼图积木。
借助名为 PolyForm Puzzle Solver的软件包,他构建了一个看起来不起眼的形如帽子(hat)的瓷砖块(铺砌块)。他想看看是否可以仅用这种形状的瓷砖不留缝隙又不重叠地覆盖平面。
“我注意到它产生了一种我以前从未见过的组合镶嵌效果。”他说,“这是一种棘手的小瓷砖。” 
他向志趣相投的好友、加拿大滑铁卢大学的计算机科学家Craig Kaplan描述了自己的作品,令后者意识到某种可能性。Smith和Kaplan随后又邀请另两位研究人员——美国国家数学博物馆和阿肯色大学的数学家Chaim Goodman-Strauss 和英国剑桥的软件工程师 Joseph Samuel Myers——加入他们的团队。
拥有组合数学方向博士学位的Myers立刻将所有业余时间投入到对帽子形瓷砖的分析上,并在短短一周多的时间里,给出了关键性的证明过程。Kaplan说:“看到他如此迅速地搞定一切,我们都感到非常震惊。”
2023年3月20日,这支4人团队正式向数学界宣告,他们找到了所谓“Einstein问题”的解:Smith发现的帽子形瓷砖,以及由帽子形瓷砖连续变换生成的瓷砖族(剔除少数几个例外),全部都是可以非周期密铺全平面的单一形状瓷砖。[为什么叫“Einstein(爱因斯坦)”问题,且看后文。]
用“帽子”非周期密铺全平面。丨图源:@csk@mathstodon.xyz
一时整个数学界都为之震动。要知道,在过去半个世纪里,数学家连一块可以非周期密铺全平面的单一形状瓷砖都未能找到,结果Smith等人在不到半年的时间里,找到了无限多组。
同样令数学界匪夷所思的事情是,作为他们研究起点的帽子形瓷砖,竟然是一个如此平平无奇的十三边形。
形如帽子的瓷砖 | 图源: @csk@mathstodon.xyz
而且,包括上面4位做出了重要发现的当事人,当时只怕没有人能够想到,就在两个月后,他们将再次震撼数学界。
非周期密铺与Einstein问题


Tiling,一般译作铺砌,平铺或者密铺,是组合数学领域里的一个大的分支。大意就是用某些形状单位,无缝隙且不重叠地覆盖住某个几何区域——可以是平面,也可以是空间;只不过对于后者,用于密铺的单位从二维瓷砖变成了三维或更高维的“积木”。
比如说,我们可以很“简单”地用单位正方形瓷砖密铺二维平面。当然,实际操作是不现实的,但数学思维赋予了我们一种自由的可能性,让我们能够从理性上体悟到,虽然实现它的过程需要无限的时间,但用单位正方形瓷砖密铺二维全平面,本质上是简单的。类似于,直线是线段向两个方向上无限延伸而来,而我们确实可以把握直线这个涉及无限的概念,并把它作为平面几何的基础。
如若再略加思考,我们还可以发现正六边形同样可以密铺平面。类似地,正三角形也可以。下面的密铺属于周期性密铺里最简单、最显然的实例。
正六边形瓷砖的周期性密铺样式丨图源:网络
我们将要介绍的Einstein问题,则属于aperiodic tiling——习惯上译作“非周期密铺”。所谓“非周期密铺“,指使用的那组瓷砖在密铺的同时,要保证拼接成的镶嵌图案不具有周期性。显而易见,正方形和正六边形瓷砖只能周期性地密铺平面,而做不到非周期性密铺。凭借直觉也很容易想到,能够非周期密铺平面的那些瓷砖应该具有不对称的特性,就如前面提到的帽子形瓷砖。此处需要说明的是,我们这里所说的图案不具有周期性的含义是,当确定所使用瓷砖的形状之后,无论如何搭配、组合、设计,都永远无法制造出全局性的周期性图案,这才能叫作非周期密铺,而许多密铺(瓷砖类)是周期性和非周期性同时存在的。因此我们可以把aperiodic tiling翻译成“本质非周期密铺”,即完全没有周期性存在的密铺。以下如未经说明,提及的“非周期密铺”均指“本质非周期密铺”。
数学家之所以对非周期性做出了如此严格的定义,一是为了排除一些过于平凡且无趣的几何结构,二则是和非周期密铺的历史起源相关。历史上首位系统性研究非周期密铺的数学家,是杰出的华裔数理逻辑学家王浩。
在研究图灵可计算函数的时候,王浩发现,某个可判定性命题与非周期密铺密切相关。他一度尝试证明如下猜想:如果对某类瓷砖存在(一般意义上的)非周期密铺,那么也一定存在周期性的密铺。
但是不久后,王浩的学生Robert Berger构造出了反例,他用20426种不同的瓷砖构造了本质上的非周期密铺——无论怎么重新铺排,都不会出现周期性结构。此后,数学家对本质非周期密铺给与了持续的关注度。数学界渴望了解,是否可以用更少种数目的瓷砖集构造出非周期密铺。
后来的人们成功降低了20426这个数字,变成了含92种的瓷砖集,然后是6种,最后是2种,即著名的彭罗斯瓷砖,后者来自后来的诺贝尔奖物理学奖得主罗杰·彭罗斯(Roger Penrose)

关于本质非周期密铺,上一次重大的发现要追溯到1974年,数学家罗杰·彭罗斯发现的彭罗斯菱形密铺:使用了一种风筝(浅黄)和一种飞镖(红)。技术细节:需要对图案做一点点小改动来避免形成右侧的菱形(全等的菱形当然可以周期性铺满平面),以满足本质“非周期密铺”的定义。丨图源:https://math.berkeley.edu/~kpmann/penrose%20reading.pdf


那么,是否还可以把数字降到1呢?
这就是著名的Einstein问题了:是否存在单一形状的瓷砖,可用它非周期密铺整个平面?
这里的Einstein,和那位著名的物理学家并无关系,单纯是德国几何学家Ludwig Danzer的双关语玩笑:在德语里“ein stein”的意思是“一块石头”。
现在回到故事开头,在2023年3月末,David Smith,Joseph Samuel Myers,Craig S. Kaplan和Chaim Goodman-Strauss为Einstein问题画上了句号。
但故事并没有结束。
艺术、灵感与最后一块拼图


实际上,Smith等人在使用帽子形瓷砖非周期密铺时,需要用到帽子形的镜像对称版瓷砖。在当前的语境下,我们默认,两个镜像对称的瓷砖,是同一种、同一形状的瓷砖。

上面所有瓷砖形状都相同(都是所谓的帽子)。然而,可借助染色揭示一些结构:深蓝色瓷砖和其它瓷砖是镜像对称的。每个深蓝色瓷砖都以相同的方式被其他三个浅蓝色包围。丨图源:@csk@mathstodon.xyz


就像左、右手是镜像对称的,无法通过旋转和平移实现左右手的重合。两个镜像对称的瓷砖同样不能通过旋转和平移转化成彼此。既然如此,它们真的能叫“单一”瓷砖吗?

在数学界普遍认可了Smith等人的成果后,一个新的问题立刻浮出了水面:能否找到不借助镜像对称,仅通过旋转和平移,实现非周期密铺的真正单一形状的瓷砖。
当时所有人都认为,这个后续问题只怕十分困难,没有人期望能在近期做出突破。更没有人能够想到答案就在众人的眼皮底下……
北京时间2023年5月30日凌晨,David Smith,Joseph Samuel Myers等4人发布了一篇23页的新论文Achiral aperiodic monotile(之前关于“帽子”形瓷砖论文长达89页),宣布他们找到了最终的答案。
他们找到了不借助镜像对称,仅通过旋转和平移可以非周期密铺的真单一形状的瓷砖,他们将其命名为“Spectre”(姑且翻译成“幽灵”)

神奇又简单的幽灵瓷砖,是一个严格手性非周期单形,也就是说,它只能用平移和旋转来拼成没有重复图案的平铺;即便你想用镜像反射的瓷砖,也用不了。丨图源:@csk@mathstodon.xyz


Kaplan在上传论文后意犹未尽,又兴奋地在数学网络社区mathstodon分享了他们最新工作的大量细节,包括灵感来源、思考方式和证明思路等等。
如前文所述,他们发现的不是满足Einstein问题的唯一一个瓷砖单形,而是一组无限的瓷砖集,集合里的多边形瓷砖都可以满足Einstein问题——当构造出满足条件的帽子后,他们通过微妙地调节帽子的边,生成的类似图形也满足条件。
Kaplan等人发现,在一定规则下,这些多边形瓷砖的形状其实可被其中两条边的边长唯一决定。他们因此用Tile (a, b)来表示这些多边形,a和b是特定边长的数值。

按照这种表示法,帽子就是Tile (1, √3)。此外Tile (√3, 1) 也是非常受关注的一种构型,它还有一个通俗的名字——海龟(参考其直观外形)。海龟也能实现非周期密铺。对于Tile (a, b) ,当a和b在一定范围内连续变化时,得到的瓷砖构型总是非周期密铺的。
另一方面可以证明,边长全等的多边形Tile (1, 1) 是一个显著的例外,在之前仿帽子瓷砖的构造方式里(使用了镜像对称的瓷砖),它不是本质非周期的。
但是仅凭上面的知识,还无法带来突破。突破的灵感来自全然意想不到的艺术领域。
日本的镶嵌艺术家、平面和立体装置设计师荒木義明(Yoshiaki Araki)对由帽子系列衍生出的瓷砖镶嵌和密铺图案非常感兴趣。他分享了一个演示程序,可以显示瓷砖Tile (1, 1.01) 的平铺效果。
4人组里的David Smith虽然没有数学工作和教育的背景,但对几何拼图的直觉异常之好(不要忘记,正是他率先想出了帽子形)。当他看到荒木義明的演示程序的时候,敏锐地察觉到,瓷砖Tile (1, 1) 或许还有可被进一步挖掘的性质。
一旦找准了方向,似乎一切都豁然开朗。他们发现,原来最后的答案就在自己的手边:如果只允许通过平移和旋转来铺设瓷砖,那么Tile (1, 1) 能非周期密铺!
一开始之所以Tile (1, 1) 不成功,是因为他们把它放到了和帽子形同等的允许镜像对称的配置里。如果限制镜像对称Tile (1, 1) 的使用,反而能实现非周期密铺!他们称Tile (1, 1) 为“弱保手性非周期性单瓷砖”。因为如果要求加入镜像对称的瓷砖,则其必然不是本质非周期性的!这也就是“弱手性”里“弱”的含义。

到此为止,他们真正找到了不借助镜像对称,仅通过旋转和平移,实现非周期密铺的单一形状的瓷砖。

但几位数学家还未满足。他们试图找到一种“强保手性非周期性单瓷砖",大致上是说,即便允许加入镜像对称的瓷砖,你也用不上!要想密铺平面,我们只能用单一手性的瓷砖,且必然非周期的。他们利用Tile (1, 1) 等边的方便属性,如下图一样巧妙地修改其边缘,便得到了Spectre,“幽灵”。
图源:参考文献[3]
为了证明“幽灵”满足条件,最开始的时候,他们一度认为在“幽灵”上做计算会很有挑战性,因为它们不像之前的帽子和海龟——“幽灵”不是多边形。但Joseph发现,“幽灵”的每一种平铺都等价于帽子和海龟的混合平铺,这让他们可以在风筝网格这个漂亮的离散世界中工作。

显示了上面描述的幽灵和由帽子+海龟组合之间的等价关系。丨图源:A chiral aperiodic monotile (uwaterloo.ca)


他们证明“幽灵”可以拼成一个分层替代系统,也就是说,在任何由“幽灵”形成的平铺中,每个“幽灵”都包含在一个无限的、唯一的、越来越大的超级块(supertile)的层次结构中。超级块是由多个“幽灵”按照一定的规则组合而成的更大的形状。这种分层替代系统保证了“幽灵”的非周期性,亦即它不可能形成有重复单元的平铺。

这里的“替代平铺”技术的严格定义,就连该领域的专家也很难清楚表述,但它的本质思路却非常好懂:用一组规则来把小块拼成大块,然后再把大块按照相同的规则拼成更大的块,以此类推,最终形成一个覆盖整个平面的图案。替代平铺有时也可以用来定义非周期密铺。

替代平铺技术,用多个小块拼成相似的大块。丨图源:arXiv: https://arxiv.org/abs/2305.17743.


这支4人团队给他们刚刚解决的问题命名为 “Vampire Einstein”问题。这又是什么意思呢?

Vampire本意是吸血鬼,据说吸血鬼在镜子里是没有影像的。所以,上面的俏皮话翻译过来,就是“没有镜像的Einstein问题”。

思考·补记


David Smith等人的论文提交还不太久,其正确性尚需一段时间的严格审核。不过像这种直接构造出具体对象的数学研究,往往短时间内就足以判断出其正确与否。目前看来,数学界已经认可了他们的结论。
早在3月末他们发布第一篇Einstein问题的论文的时候,就引来了广泛的关注。关注者不仅仅是数学工作者,还包括大量的艺术家。除了平面设计艺术家和拼图爱好者之外,甚至有作曲家尝试把实现非周期密铺的算法转化成旋律,实验某种新型音乐形式。

2023720日,笔者惊奇地发现,爱尔兰著名啤酒品牌white hag推出了一款应用非周期性瓷砖“帽子”设计包装啤酒罐。丨图源:作者供图
这种广泛的关注,最终给数学的发展带来了意想不到的好处——最后的证明正是受到了日本艺术家荒木義明的作品的启发。
现在除了论文的几位作者之外,最高兴的就是这位日本艺术家了。他在论文发出一天后,非常开心地在社交媒体上分享了论文的截图,因为几位作者把他的名字放到了致谢里。

另一个值得思考的是,作为业余数学爱好者的David Smith在这一重大数学进展里所起到的关键作用。
事实上,这远不是业余爱好者第一次在拼贴几何领域取得重大突破。担任邮件分拣员的Robert Ammann在 1970 年代独立发现了几种非周期性密铺,以及一种名为Ammann bars的非周期性密铺的系统生成方法;1975 年,加州家庭主妇Marjorie Rice 发现了一个新的五边形瓷砖族;随后Joan Taylor发现了后来著名的Socolar-Taylor瓷砖。
以至于有位数学家开玩笑说,在一个具体数学领域里(这里的“具体数学”是和“应用数学”类似的提法,是一个门类。指对象直观可见的以及和计算机相关的数学内容),也许业余爱好者与职业数学家最大的不同之处在于,前者“并不需要知道这个问题有多难”,所以才能做出出乎意料的精彩发现。
这里索性给大家留一个思考题,一个本质上不需要任何数学知识就能解答的经典骨牌平铺问题:

最后,关于密铺,还有很多值得一说的东西。比如,虽然这一次着重介绍的是非周期密铺,但并不意味着周期性密铺是个无关紧要的课题。直到2015年,数学家才借助计算机发现了第15种也是最后一种可以进行周期性密铺的五边形,从而找到了全部的周期性单密铺多边形。
周期性密铺和非周期密铺,就好比有理数和无理数。虽然有理数确实相对于无理数要简单,但仍有大量未知内容尚待挖掘。
此外,除了平面密铺,高维空间上的非周期密铺也有很多值得一提的成果。如2022年11月,陶哲轩(Terence Tao)和Rachel Greenfeld宣布推翻了一个高维空间上的“周期性密铺猜想”。就Einstein问题瓷砖而言,也有所谓的三维Einstein问题瓷砖(如下图)

图源:Socolar–Taylor tile Wikipedia


非周期密铺在很多数学领域都有重要的应用和研究价值,比如自动机理论、组合数学、离散几何、动力系统、群论、调和分析和数论,以及晶体学和化学。其中在晶体和化学上最有名的应用,是在理论上为准晶体的结构和性能提供数学和物理上的解释。(如果事后诸葛亮的话,我们甚至可以说,非周期密铺揭示了准晶体的存在性——只不过在自然界里发现准晶体之前,并未有人意识到这一点。)非周期性密铺和准晶体之间的关系是一个跨越数学、物理、化学、材料等多个领域的精彩话题。

参考资料

[1] Hobbyist Finds Math’s Elusive ‘Einstein’ Tile | Quanta Magazine
[2] Craig S. Kaplan (@csk@mathstodon.xyz) - Mathstodon[3] Achiral aperiodic monotile,https://arxiv.org/abs/2305.17743[4] Anaperiodic monotile,https://arxiv.org/pdf/2303.10798.pdf[5] David Smith使用的软件(PolyForm Puzzle Solver (jaapsch.net)):https://www.jaapsch.net/puzzles/polysolver.htm[6] Craig S. Kaplan分享的工具:https://cs.uwaterloo.ca/~csk/spectre/
感谢加州理工学院数学系倪忆教授对本文的审核和指正。

本文受科普中国·星空计划项目扶持

出品:中国科协科普部

监制:中国科学技术出版社有限公司、北京中科星河文化传媒有限公司



相关阅读

1  "拉马努金复生才能解决”:E₈格与装球问题

2  数学史上最强家庭主妇,只有高中学历却做出了4项重要发现

3  自然界为何处处是六边形?这里有深刻的数学和物理

4  彭罗斯:不思考生物化学的诺贝尔物理学奖得主不是好的数学家

5 这位中学物理老师,是一位真正的组合数学大家


近期推荐

1  基因测序20年后,终于搞清了垃圾DNA是干啥的

2  IBM量子计算最新进展:量子计算的chatGPT时刻即将来临?

3  抑郁症患者告白:我心为谁闭与开?

4  动物们也热得受不了:几十年完成百万年演化

5  镍氧化物:高温超导的新希望!


特 别 提 示

1. 进入『返朴』微信公众号底部菜单“精品专栏“,可查阅不同主题系列科普文章。

2. 『返朴』提供按月检索文章功能。关注公众号,回复四位数组成的年份+月份,如“1903”,可获取2019年3月的文章索引,以此类推。

版权说明:欢迎个人转发,任何形式的媒体或机构未经授权,不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。


找不到《返朴》了?快加星标!!



长按下方图片关注「返朴」,查看更多历史文章

微信实行乱序推送,常点“在看”,可防失联

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存