陶哲軒一直在研究的周期性密鋪問題，又有新突破了。

9月18日，陶哲軒和Rachel Greenfeld將預(yù)印本論文《平移單密鋪的不可判定性 (Undecidability of translational monotilings)》上傳到了arXiv。

論文地址：https://arxiv.org/abs/2309.09504

這篇論文的主要結(jié)論是，如果網(wǎng)格的維數(shù)是無(wú)界的，那么確定網(wǎng)格的有限子集是否可以平鋪該網(wǎng)格的周期子集的問題，就是不可判定的。

要知道，此問題在維度1和維度2中是可判定的。

陶哲軒表示，有點(diǎn)奇怪的是，文中所證明的大多數(shù)組件都跟流行的游戲類似——

多米諾骨牌的密鋪類似物，數(shù)獨(dú)，電腦游戲「俄羅斯方塊」，甚至連兒童游戲「Fizz buzz」都出現(xiàn)了。

為什么研究一個(gè)數(shù)學(xué)問題，會(huì)涉及到這么多游戲呢？陶哲軒也無(wú)法解釋。

平移單密鋪的不可判定性

這次的論文，是兩人上一篇論文的續(xù)集。鏈接  周期性密鋪問題

在上篇論文中，他們構(gòu)建了一個(gè)高維網(wǎng)格的平移單密鋪

（因此單密鋪是一個(gè)有限集合 ），它是非周期性的（沒有辦法將這個(gè)密鋪「修復(fù)」成周期性密鋪，其中現(xiàn)在相對(duì)于有限索引子群是周期性的)。

這就反駁了Stein、Grunbaum-Shephard和Lagarias-Wang的周期性密鋪猜想，他們斷言這種非周期性密鋪單體不存在。

（「帽子單密鋪」是一種最近發(fā)現(xiàn)的非周期等距單密鋪，在這種單密鋪中，可以允許使用旋轉(zhuǎn)、反射以及平移，或者更新的「幽靈單片」。上述單片與帽子單密鋪相似，除了不需要反射）。

激發(fā)陶哲軒和Rachel Greenfeld這個(gè)猜想的原因之一，是數(shù)學(xué)家Hao Wang的觀察。

他發(fā)現(xiàn)，如果周期密鋪猜想為真，那么平移密鋪問題在算法上是可判定的——

有一個(gè)圖靈機(jī)，對(duì)于，當(dāng)給定一個(gè)維度和一個(gè)有限子集時(shí)，可以在有限的時(shí)間內(nèi)確定是否可以密鋪。

這是因?yàn)槿绻嬖谥芷谛悦茕仯涂梢酝ㄟ^計(jì)算機(jī)搜索找到它。

如果根本不存在密鋪，那么通過緊致性定理可知，存在一些有限的子集，這些子集不能被不相交的平移所覆蓋，這也可以通過計(jì)算機(jī)搜索來(lái)發(fā)現(xiàn)。

周期性密鋪猜想斷言這是僅有的兩種可能的情況，從而給出了可判定性。

另一方面，Wang的論點(diǎn)是不可逆的：周期性密鋪猜想的失敗，并不自動(dòng)意味著平移單密鋪問題的不可判定性，因?yàn)樗慌懦嬖谝恍┢渌惴▉?lái)確定密鋪，這種密鋪可以不依賴于周期性密鋪的存在。

（例如，即使有新發(fā)現(xiàn)的帽子和幽靈密鋪，對(duì)于中有理系數(shù)的多邊形的等距單密鋪問題是否是可判定的，仍然是一個(gè)懸而未決的問題，無(wú)論它有沒有反射。

本文的主要結(jié)果解決了這個(gè)問題（有一個(gè)警告）：

定理1

不存在任何算法，對(duì)于，給定一個(gè)維度，一個(gè)周期性子集，和一個(gè)有限子集，能在有限時(shí)間內(nèi)確定是否存在一個(gè)平移密鋪。

需要注意的是，必須使用的周期性子集，而不是全部的；這在很大程度上是由于這種方法的技術(shù)限制，并且很可能通過額外的努力和創(chuàng)造力來(lái)消除。

另外，陶哲軒和Rachel Greenfeld還注意到，當(dāng)，周期性密鋪猜想是由Bhattacharya建立的，因此在這種情況下問題可判定。

對(duì)于任何的固定值，密鋪問題是否可判定仍然是開放的（注意，在上面的結(jié)果中，維度不是固定的，而是輸入的一部分）。

由于算法不可判定性和邏輯不可判定性（也稱為邏輯獨(dú)立性）之間存在眾所周知的聯(lián)系，此定理還暗示了存在一個(gè)（原則上明確可描述的）維度、的周期性子集，的有限子集，使得能通過平移密鋪不能在ZFC集合論中被證實(shí)或證偽（當(dāng)然假設(shè)這個(gè)理論是一致的）。

作為這種方法的結(jié)果，我們也可以在這里用「幾乎二維」群來(lái)代替，其中是一個(gè)有限阿貝爾群（現(xiàn)在成為輸入的一部分，代替維度）。

接下來(lái)，描述證明的一些主要思想。

證明某個(gè)問題不可判定的常用方法是，將已知不可判定的其他問題「編碼」到原始問題中，這樣，任何判定原始問題的算法也能判定嵌入的問題。

因此，我們將 Wang密鋪問題編碼為單密鋪問題：

問題2（Wang密鋪問題）

給定一個(gè)有限的王氏密鋪集合（單位正方形，每條邊都從有限調(diào)色板中指定了某種顏色），是否有可能用標(biāo)準(zhǔn)的格通過平移來(lái)密鋪平面，使得相鄰的密鋪在共同邊緣上具有相同的顏色？

Berger曾給出一個(gè)著名的結(jié)果，即這個(gè)問題是不可判定的。

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

將這一問題嵌入高維平移單密鋪問題需要經(jīng)過一些中間問題。

首先，我們可以很容易地將王氏密鋪問題嵌入到一個(gè)類似的問題中，我們稱之為多米諾骨牌問題：

問題 3（多米諾骨牌問題）

給定一個(gè)水平（或垂直）的多米諾骨牌的有限集合或，它們是一對(duì)相鄰的單元正方形，每個(gè)單元正方形都用有限集合中的一個(gè)元素點(diǎn)來(lái)點(diǎn)綴，是否可以在標(biāo)準(zhǔn)格密鋪中為每個(gè)單元正方形分配一個(gè)點(diǎn)，使得這個(gè)密鋪中的每一對(duì)水平（或垂直）的方格都能用到來(lái)自或的多米諾骨牌？

事實(shí)上，我們只需要將每個(gè)王氏密鋪?zhàn)鳛橐粋€(gè)單獨(dú)的「點(diǎn)」插入，并定義多米諾骨牌集，為水平或垂直相鄰、邊緣具有相同顏色的王氏密鋪對(duì)。

接下來(lái)，將多米諾骨牌問題嵌入到數(shù)獨(dú)問題中：

問題 4（數(shù)獨(dú)問題）

給定列寬、數(shù)字集、函數(shù)的集合和「初始條件」（在這里就不詳細(xì)介紹了），是否可以為「數(shù)獨(dú)棋盤」中的每個(gè)單元格分配一個(gè)數(shù)字，以便對(duì)于任何斜率和截距，沿著線的數(shù)字位于中（并且服從初始條件）？

這篇論文最新穎的部分是證明了多米諾骨牌問題確實(shí)可以嵌入到數(shù)獨(dú)問題中。

將數(shù)獨(dú)問題嵌入到單密鋪問題中，源于之前論文中修改的方法。

這些論文也引入了數(shù)獨(dú)問題的版本，并創(chuàng)造了一種「密鋪語(yǔ)言」，可用于把各種問題（包括數(shù)獨(dú)問題）「編碼」為單密鋪問題。

要將多米諾骨牌問題編碼為數(shù)獨(dú)問題，我們需要獲取一個(gè)多米諾函數(shù)

（遵守與某些多米諾骨牌集相關(guān)的多米諾骨牌約束），并使用它來(lái)構(gòu)建數(shù)獨(dú)函數(shù)（遵守與多米諾骨牌集相關(guān)的一些數(shù)獨(dú)約束）；反過來(lái)說，每個(gè)遵守?cái)?shù)獨(dú)謎題規(guī)則的數(shù)獨(dú)函數(shù)，都必須以某種方式從多米諾函數(shù)中產(chǎn)生。

這種做法并不是很顯而易見，但是在Emmanuel Jeandel的幫助下，陶哲軒和Rachel Greenfeld改編了Aanderaa和Lewis的一些想法，某些層次結(jié)構(gòu)被用來(lái)將一個(gè)問題編碼另一個(gè)問題。

在這里，我們解釋分層結(jié)構(gòu)（由于多米諾骨牌問題的二維性，需要使用兩個(gè)不同的素?cái)?shù)）。

然后，通過公式用構(gòu)建數(shù)獨(dú)函數(shù)，它將體現(xiàn)某種嵌入。

其中是兩個(gè)不同的大素?cái)?shù)（例如，可以取，），表示除以的次數(shù)，并且

是的展開中的最后一個(gè)非零數(shù)字：

（，且）。

在的情況下，（1） 的第一個(gè)分量如下所示：

最終分量的典型實(shí)例如下所示：

有趣的是，不知為何，這里的裝飾基本上遵循了兒童游戲「Fizz buzz」的規(guī)則。