Redian新闻
>
陶哲轩再逼近60年几何学难题!周期性密铺问题又获新突破

陶哲轩再逼近60年几何学难题!周期性密铺问题又获新突破

公众号新闻



  新智元报道  

编辑:Aeneas
【新智元导读】关于60年的几何学难题周期性密铺问题,陶哲轩最近又有新突破了。

陶哲轩一直在研究的周期性密铺问题,又有新突破了。

9月18日,陶哲轩和Rachel Greenfeld将预印本论文《平移单密铺的不可判定性 (Undecidability of translational monotilings)》上传到了arXiv。

论文地址:https://arxiv.org/abs/2309.09504

这篇论文的主要结论是,如果网格的维数是无界的,那么确定网格的有限子集是否可以平铺该网格的周期子集的问题,就是不可判定的。

要知道,此问题在维度1和维度2中是可判定的。

陶哲轩表示,有点奇怪的是,文中所证明的大多数组件都跟流行的游戏类似——

多米诺骨牌的密铺类似物,数独,电脑游戏「俄罗斯方块」,甚至连儿童游戏「Fizz buzz」都出现了。

为什么研究一个数学问题,会涉及到这么多游戏呢?陶哲轩也无法解释。

平移单密铺的不可判定性

这次的论文,是两人上一篇论文的续集。链接  周期性密铺问题

在上篇论文中,他们构建了一个高维网格的平移单密铺

(因此单密铺是一个有限集合 ),它是非周期性的(没有办法将这个密铺「修复」成周期性密铺,其中现在相对于有限索引子群是周期性的)。

这就反驳了Stein、Grunbaum-Shephard和Lagarias-Wang的周期性密铺猜想,他们断言这种非周期性密铺单体不存在。

(「帽子单密铺」是一种最近发现的非周期等距单密铺,在这种单密铺中,可以允许使用旋转、反射以及平移,或者更新的「幽灵单片」。上述单片与帽子单密铺相似,除了不需要反射)。

激发陶哲轩和Rachel Greenfeld这个猜想的原因之一,是数学家Hao Wang的观察。

他发现,如果周期密铺猜想为真,那么平移密铺问题在算法上是可判定的——

有一个图灵机,对于当给定一个维度和一个有限子集时,可以在有限的时间内确定是否可以密铺

这是因为如果存在周期性密铺,就可以通过计算机搜索找到它。

如果根本不存在密铺,那么通过紧致性定理可知,存在一些有限的子集,这些子集不能被不相交的平移所覆盖,这也可以通过计算机搜索来发现。

周期性密铺猜想断言这是仅有的两种可能的情况,从而给出了可判定性。

另一方面,Wang的论点是不可逆的:周期性密铺猜想的失败,并不自动意味着平移单密铺问题的不可判定性,因为它不排除存在一些其他算法来确定密铺,这种密铺可以不依赖于周期性密铺的存在。

(例如,即使有新发现的帽子和幽灵密铺,对于中有理系数的多边形的等距单密铺问题是否是可判定的,仍然是一个悬而未决的问题,无论它有没有反射。

本文的主要结果解决了这个问题(有一个警告):

定理1

不存在任何算法,对于,给定一个维度一个周期性子集,和一个有限子集,能在有限时间内确定是否存在一个平移密铺

需要注意的是,必须使用的周期性子集,而不是全部的这在很大程度上是由于这种方法的技术限制,并且很可能通过额外的努力和创造力来消除。

另外,陶哲轩和Rachel Greenfeld还注意到,当,周期性密铺猜想是由Bhattacharya建立的,因此在这种情况下问题可判定。

对于任何的固定值,密铺问题是否可判定仍然是开放的(注意,在上面的结果中,维度不是固定的,而是输入的一部分)。

由于算法不可判定性和逻辑不可判定性(也称为逻辑独立性)之间存在众所周知的联系,此定理还暗示了存在一个(原则上明确可描述的)维度的周期性子集的有限子集,使得能通过平移密铺不能在ZFC集合论中被证实或证伪(当然假设这个理论是一致的)。

作为这种方法的结果,我们也可以在这里用「几乎二维」群来代替,其中是一个有限阿贝尔群(现在成为输入的一部分,代替维度)。

接下来,描述证明的一些主要思想。

证明某个问题不可判定的常用方法是,将已知不可判定的其他问题「编码」到原始问题中,这样,任何判定原始问题的算法也能判定嵌入的问题。

因此,我们将 Wang密铺问题编码为单密铺问题

问题2(Wang密铺问题)

给定一个有限的王氏密铺集合(单位正方形,每条边都从有限调色板中指定了某种颜色),是否有可能用标准的格通过平移来密铺平面,使得相邻的密铺在共同边缘上具有相同的颜色?

Berger曾给出一个著名的结果,即这个问题是不可判定的。

Berger, Robert,<The undecidability of the domino problem>

将这一问题嵌入高维平移单密铺问题需要经过一些中间问题。

首先,我们可以很容易地将王氏密铺问题嵌入到一个类似的问题中,我们称之为多米诺骨牌问题:

问题 3(多米诺骨牌问题)

给定一个水平(或垂直)的多米诺骨牌的有限集合,它们是一对相邻的单元正方形,每个单元正方形都用有限集合中的一个元素点来点缀,是否可以在标准格密铺中为每个单元正方形分配一个点,使得这个密铺中的每一对水平(或垂直)的方格都能用到来自的多米诺骨牌?

事实上,我们只需要将每个王氏密铺作为一个单独的「点」插入,并定义多米诺骨牌集为水平或垂直相邻、边缘具有相同颜色的王氏密铺对。

接下来,将多米诺骨牌问题嵌入到数独问题中:

问题 4(数独问题)

给定列宽、数字集、函数的集合和「初始条件」(在这里就不详细介绍了),是否可以为「数独棋盘」中的每个单元格分配一个数字,以便对于任何斜率和截距沿着线的数字位于中(并且服从初始条件)?

这篇论文最新颖的部分是证明了多米诺骨牌问题确实可以嵌入到数独问题中。

将数独问题嵌入到单密铺问题中,源于之前论文中修改的方法。

这些论文也引入了数独问题的版本,并创造了一种「密铺语言」,可用于把各种问题(包括数独问题)「编码」为单密铺问题。

要将多米诺骨牌问题编码为数独问题,我们需要获取一个多米诺函数

(遵守与某些多米诺骨牌集相关的多米诺骨牌约束),并使用它来构建数独函数(遵守与多米诺骨牌集相关的一些数独约束);反过来说,每个遵守数独谜题规则的数独函数,都必须以某种方式从多米诺函数中产生。

这种做法并不是很显而易见,但是在Emmanuel Jeandel的帮助下,陶哲轩和Rachel Greenfeld改编了Aanderaa和Lewis的一些想法,某些层次结构被用来将一个问题编码另一个问题。

在这里,我们解释分层结构(由于多米诺骨牌问题的二维性,需要使用两个不同的素数)。

然后,通过公式构建数独函数,它将体现某种嵌入。

其中是两个不同的大素数(例如,可以取),表示除以的次数,并且

展开中的最后一个非零数字:

,且)。

的情况下,(1) 的第一个分量如下所示:

最终分量的典型实例如下所示:

有趣的是,不知为何,这里的装饰基本上遵循了儿童游戏「Fizz buzz」的规则。

参考资料:
https://terrytao.wordpress.com/2023/09/18/undecidability-of-translational-monotilings/




微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
陶哲轩:初学者不宜用AI工具做专家级任务,GPT对专家帮助不大GPT-4野生代言人陶哲轩:搞论文学新工具没它得崩溃!11页“超简短”新作已上线陶哲轩疯狂安利Copilot:它帮我完成了一页纸证明,甚至能猜出我后面的过程陶哲轩新论文:部分证明著名素数猜想,新方法用到了自己的旧模型陶哲轩论文漏洞竟被AI发现,26年预言要成真!看定理名猜出研究方向,大神直呼AI能力惊人陶哲轩支持!AI奥林匹克数学奖来了,奖金500万美元,寻找能得IMO金牌的大模型陶哲轩上手Copilot:不可思议,它能从定理名字猜出我想要的方向数据分析经典方法之:周期性分析法谁统治下次大战的天空星雲與李玟:學會放下不容易对标GPT-4代码解释器!港中大让模型写代码解决数学难题,得分超越GPT-4又获突破!光伏组件功率有望加速迈入700W+时代蔚来,周期性危机与自救GitHub Copilot让陶哲轩感到“不安”AI颠覆数学研究!陶哲轩借AI破解数学猜想,形式化成功惊呆数学圈谁是真正的不完美受害人?陶哲轩用大模型辅助解决数学问题:生成代码、编辑LaTeX公式都很好用一加十周年:投身周期,穿越周期,逆周期真香!陶哲轩:用ChatGPT写代码太省时间了!29个重大科学难题公布:Chiplet和AI被列入暗物质不存在?无暗物质宇宙模型又获新证据;“室温超导”科学家学术不端论文被撤稿,并将面临调查 | 环球科学要闻AIGC日报丨TikTok推AIGC内容打标功能,不标记内容将被删;DeepMind新AI模型有望解决人类遗传学难题GPT-4成功得出P≠NP,陶哲轩预言成真!97轮「苏格拉底式推理」对话破解世界数学难题陶哲轩:用 ChatGPT 写代码太省时间了「陶哲轩×GPT-4」合写数学论文!数学大佬齐惊呼,LLM推理神助证明不等式定理成长陶哲轩发新论文了,又是AI帮忙的那种华人攻破上世纪数学难题:求一张白纸上的所有线条上共有多少灰尘|普林斯顿&纽大陶哲轩:我用GPT-4辅助证明不等式定理,论文还会上传arXiv数学难?借用披萨学习《几何中的角》,So easy!包爸洋葱数学返场!新学期无痛解决数学难题,就学洋葱~直播间奖品、免单全都有,预约不错过!陶哲轩又来安利AI工具了:新论文排版用上VSCode Copilot+插件魯秋警官的故事2陶哲轩:GPT-4神助攻,写Python代码轻松省半小时英特尔:在周期性低迷中挣扎
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。