陶哲軒再逼近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的觀察

他發現，如果週期密鋪猜想為真，那麼平移密鋪問題在演算法上是可判定的－

有一個圖靈機，對於，當給定一個維度和一個有限子集時，可以在有限的時間內確定是否可以密舖#。

這是由於如果存在周期性的密舖，就可以透過電腦搜尋來找到它

如果根本不存在密舖，那麼透過緊緻性定理可知，存在一些有限的子集，這些子集不能被不相交的平移所覆蓋，這也可以透過計算機搜尋來發現。

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

另一方面，王的觀點是不可改變的：週期性密舖猜想的失敗，並不自動意味著平移單密舖問題的不可判定性，因為它並不排除存在其他演算法來確定密鋪，這種密舖可以不依賴週期性密舖的存在

（例如，即使有新發現的帽子和幽靈密鋪，對於中有理係數的多邊形的等距單密舖問題是否是可判定的，仍然是一個懸而未決的問題，無論它有沒有反射。

本文的主要結果解決了這個問題（有一個警告）：

需要重寫的內容是：定理1

不存在任何演算法，對於，給定一個維度 ，一個週期性子集，和一個有限子集#，能在有限時間內確定是否存在一個平移密舖#。

#

要注意的是，必須使用的周期性子集#，而不是全部的 ；這在很大程度上是由於這種方法的技術限制，並且很可能透過額外的努力和創造力來消除。

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

對於任何的固定值，密舖問題是否可判定仍然是開放的（注意，在上面的結果中，維度 不是固定的，而是輸入的一部分）。

由於演算法不可判定性和邏輯不可判定性（也稱為邏輯獨立性）之間存在眾所周知的聯繫，此定理還暗示了存在一個（原則上明確可描述的）維度、#的周期性子集，的有限子集，使得能透過平移密舖不能在ZFC集合論中被證實或證偽（當然假設這個理論是一致的）。

作為這種方法的結果，我們也可以在這裡用「幾乎是二維」群組來取代 #，其中是一個有限阿貝爾群組（現在成為輸入的一部分，代替維度）。

接下來，描述證明的一些主要想法。

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

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

##第二個問題是關於王密舖問題

給定一個有限的王氏密鋪集合（單位正方形，每條邊都從有限調色板中指定了某種顏色），是否有可能用標準的格通過平移來密鋪平面，使得相鄰的密舖在共同邊緣上具有相同的顏色？

Berger曾經提出了一個著名的結論，即這個問題無法確定

需要重寫的內容是：Berger，Robert，

#將這個問題轉化為高維度平移單密鋪問題需要解決一些中間問題

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

重寫內容如下：骨牌問題是問題3

給定一個水平（或垂直）的骨牌的有限集合或，它們是一對相鄰的單元正方形，每個單元正方形都用有限集合中的一個元素點來點綴，是否可以在標準格密舖#中為每個單元正方形分配一個點，使得這個密舖中​​的每一對水平（或垂直）的方格都能用到來自或的骨牌？

事實上，我們只需要將每個王氏密舖作為一個單獨的「點」插入，並定義骨牌集，為水平或垂直相鄰、邊緣具有相同顏色的王氏密鋪對。

在接下來的步驟中，我們將把骨牌問題與數獨問題結合：#

問題4（數獨問題）

給定列寬#、數字集、函數的集合#與「初始條件」 #（這裡就不詳細介紹了），是否可以為「數獨棋盤」中的每個單元格分配一個數字，以便對於任何斜率和截距，沿著線的數字位於#中（並且服從初始條件）？

這篇論文最新穎的部分是證明了骨牌問題確實可以嵌入到數獨問題中。

將數獨問題嵌入到單密鋪問題中，是基於先前論文中提出的修改方法

這些論文也提出了數獨問題的不同版本，並創造了一種名為「密舖語言」的方法，可以將各種問題（包括數獨問題）轉化為單一的密舖問題

要將骨牌問題編碼為數獨問題，我們需要取得一個多米諾函數

#（遵守與某些骨牌集

##################################################相關的骨牌約束），並使用它來構建數獨函數#########（遵守與多米諾骨牌集相關的一些數獨約束）；反過來說，每個遵守數獨謎題規則的數獨函數，都必須以某種方式從多米諾函數產生。 ######

這種做法並不是很顯而易見，但是在Emmanuel Jeandel的幫助下，陶哲軒和Rachel Greenfeld改編了Aanderaa和Lewis的一些想法，某些層次結構被用來將一個問題編碼另一個問題。

在這裡，我們解釋分層結構（由於骨牌問題的二維性，需要使用兩個不同的質數）。

然後，透過公式用#建構數獨函數，它將體現某種嵌入。

其中是兩個不同的大質數（例如，可以取，#），表示除以#的次數，並且

是的

##（

，且）。

在

的情況下，（1） 的第一個分量如下所示：

#最終分量

的典型實例如下所示：

##################有趣的是，不知道為什麼，這裡的裝飾基本上遵循了兒童遊戲“Fizz buzz”的規則######

以上是陶哲軒再逼近60年幾何學難題！週期性密鋪問題又獲新突破的詳細內容。更多資訊請關注PHP中文網其他相關文章！