Undecidability of translational monotilings | What’s new

Math

Undecidability of translational monotilings | What’s new

keiseronlineuniversity.com

19 September 2023

Undecidability of translational monotilings | What’s new

[ad_1]

Rachel Greenfeld and I’ve simply uploaded to the arXiv our paper “Undecidability of translational monotilings“. This can be a sequel to our earlier paper wherein we constructed a translational monotiling ${A oplus F = {bf Z}^d}$ of a high-dimensional lattice ${{bf Z}^d}$ (thus the monotile ${F}$ is a finite set and the interprets ${a+F}$ , ${a in A}$ of ${F}$ partition ${{bf Z}^d}$ ) which was aperiodic (there isn’t a solution to “restore” this tiling right into a periodic tiling ${A' oplus F = {bf Z}^d}$ , wherein ${A'}$ is now periodic with respect to a finite index subgroup of ${{bf Z}^d}$ ). This disproved the periodic tiling conjecture of Stein, Grunbaum-Shephard and Lagarias-Wang, which asserted that such aperiodic translational monotilings don’t exist. (Examine with the “hat monotile“, which is a just lately found aperiodic isometric monotile for of ${{bf R}^2}$ , the place one is now allowed to make use of rotations and reflections in addition to translations, or the much more latest “spectre monotile“, which has similarities besides that no reflections are wanted.)

One of many motivations of this conjecture was the commentary of Hao Wang that if the periodic tiling conjecture had been true, then the translational monotiling drawback is (algorithmically) decidable: there’s a Turing machine which, when given a dimension ${d}$ and a finite subset ${F}$ of ${{bf Z}^d}$ , can decide in finite time whether or not ${F}$ can tile ${{bf Z}^d}$ . It’s because if a periodic tiling exists, it may be discovered by laptop search; and if no tiling exists in any respect, then (by the compactness theorem) there exists some finite subset of ${{bf Z}^d}$ that can’t be coated by disjoint interprets of ${F}$ , and this will also be found by laptop search. The periodic tiling conjecture asserts that these are the one two doable situations, thus giving the decidability.

However, Wang’s argument just isn’t identified to be reversible: the failure of the periodic tiling conjecture doesn’t routinely suggest the undecidability of the translational monotiling drawback, because it doesn’t rule out the existence of another algorithm to find out tiling that doesn’t depend on the existence of a periodic tiling. (As an illustration, even with the newly found hat and spectre tiles, it stays an open query whether or not the isometric monotiling drawback for (say) polygons with rational coefficients in ${{bf R}^2}$ is decidable, with or with out reflections.)

The primary results of this paper settles this query (with one caveat):

Theorem 1 There doesn’t exist any algorithm which, given a dimension ${d}$ , a periodic subset ${E}$ of ${{bf Z}^d}$ , and a finite subset ${F}$ of ${{bf Z}^d}$ , determines in finite time whether or not there’s a translational tiling ${A oplus F = E}$ of ${E}$ by ${F}$ .

The caveat is that we have now to work with periodic subsets ${E}$ of ${{bf Z}^d}$ , moderately than all of ${{bf Z}^d}$ ; we consider that is largely a technical restriction of our technique, and it’s possible that may be eliminated with extra effort and creativity. We additionally comment that when ${d=2}$ , the periodic tiling conjecture was established by Bhattacharya, and so the issue is decidable within the ${d=2}$ case. It stays open whether or not the tiling drawback is decidable for any fastened worth of ${d>2}$ (notice within the above consequence that the dimension ${d}$ just isn’t fastened, however is a part of the enter).

Due to a well-known hyperlink between algorithmic undecidability and logical undecidability (often known as logical independence), the principle theorem additionally implies the existence of an (in precept explicitly describable) dimension ${d}$ , periodic subset ${E}$ of ${{bf Z}^d}$ , and a finite subset ${F}$ of ${{bf Z}^d}$ , such that the assertion that ${F}$ tiles ${E}$ by translation can’t be confirmed or disproven in ZFC set principle (assuming in fact that this principle is constant).

As a consequence of our technique, we are able to additionally change ${{bf Z}^d}$ right here by “nearly two-dimensional” teams ${{bf Z}^2 times G_0}$ , with ${G_0}$ a finite abelian group (which now turns into a part of the enter, instead of the dimension ${d}$ ).

We now describe a few of the major concepts of the proof. It’s a widespread method to point out {that a} given drawback is undecidable by demonstrating that another drawback that was already identified to be undecidable might be “encoded” inside the unique drawback, in order that any algorithm for deciding the unique drawback would additionally determine the embedded drawback. Accordingly, we’ll encode the Wang tiling drawback as a monotiling drawback in ${{bf Z}^d}$ :

Drawback 2 (Wang tiling drawback) Given a finite assortment ${{mathcal W}}$ of Wang tiles (unit squares with all sides assigned some shade from a finite palette), is it doable to tile the airplane with interprets of those tiles alongside the usual lattice ${{bf Z}^2}$ , such that adjoining tiles have matching colours alongside their widespread edge?

It’s a well-known results of Berger that this drawback is undecidable. The embedding of this drawback into the higher-dimensional translational monotiling drawback proceeds via some intermediate issues. Firstly, it’s a simple matter to embed the Wang tiling drawback into the same drawback which we name the domino drawback:

Drawback 3 (Domino drawback) Given a finite assortment ${{mathcal R}_1}$ (resp. ${{mathcal R}_2}$ ) of horizontal (resp. vertical) dominoes – pairs of adjoining unit squares, every of which is adorned with a component of a finite set ${{mathcal W}}$ of “pips”, is it doable to assign a pip to every unit sq. in the usual lattice tiling of ${{bf Z}^2}$ , such that each horizontal (resp. vertical) pair of squares on this tiling is adorned utilizing a domino from ${{mathcal R}_1}$ (resp. ${{mathcal R}_2}$ )?

Certainly, one simply has to interpet every Wang tile as a separate “pip”, and outline the domino units ${{mathcal R}_1}$ , ${{mathcal R}_2}$ to be the pairs of horizontally or vertically adjoining Wang tiles with matching colours alongside their edge.

Subsequent, we embed the domino drawback right into a Sudoku drawback:

Drawback 4 (Sudoku drawback) Given a column width ${N}$ , a digit set ${Sigma}$ , a set ${{mathcal S}}$ of capabilities ${g: {0,dots,N-1} rightarrow Sigma}$ , and an “preliminary situation” ${{mathcal C}}$ (which we won’t element right here, as it’s a little technical), is it doable to assign a digit ${F(n,m)}$ to every cell ${(n,m)}$ within the “Sudoku board” ${{0,1,dots,N-1} times {bf Z}}$ such that for any slope ${j in {bf Z}}$ and intercept ${i in {bf Z}}$ , the digits ${n mapsto F(n,jn+i)}$ alongside the road ${{(n,jn+i): 0 leq n leq N-1}}$ lie in ${{mathcal S}}$ (and in addition that ${F}$ obeys the preliminary situation ${{mathcal C}}$ )?

Essentially the most novel a part of the paper is the demonstration that the domino drawback can certainly be embedded into the Sudoku drawback. The embedding of the Sudoku drawback into the monotiling drawback follows from a modification of the strategies in our earlier papers, which had additionally launched variations of the Sudoku drawback, and created a “tiling language” which might be used to “program” numerous issues, together with the Sudoku drawback, as monotiling issues.

To encode the domino drawback into the Sudoku drawback, we have to take a domino perform ${{mathcal T}: {bf Z}^2 rightarrow {mathcal W}}$ (obeying the domino constraints related to some domino units ${{mathcal R}_1, {mathcal R}_2}$ ) and use it to construct a Sudoku perform ${F: {0,dots,N-1} times {bf Z} rightarrow Sigma}$ (obeying some Sudoku constraints referring to the domino units); conversely, each Sudoku perform obeying the foundations of our Sudoku puzzle has to come up one way or the other from a domino perform. The path to doing so was not instantly apparent, however after a useful tip from Emmanuel Jeandel, we had been in a position to adapt some concepts of Aanderaa and Lewis, wherein sure hierarchical buildings had been used to encode one drawback in one other. Right here, we interpret hierarchical construction ${p}$ -adically (utilizing two totally different primes as a result of two-dimensionality of the domino drawback). The Sudoku perform ${F}$ that may exemplify our embedding is then constructed from ${{mathcal T}}$ by the components

$displaystyle F(n,m) := ( f_{p_1}(m), f_{p_2}(m), {mathcal T}(nu_{p_1}(m), nu_{p_2}(m)) ) (1)$
the place ${p_1,p_2}$ are two massive distinct primes (as an example one can take ${p_1=53}$ , ${p_2=57}$ for concreteness), ${nu_p(m)}$ denotes the variety of occasions ${p}$ divides ${m}$ , and ${f_p(m) in {bf Z}/p{bf Z} backslash {0}}$ is the final non-zero digit within the base ${p}$ growth of ${m}$ :

$displaystyle f_p(m) := frac{m}{p^{nu_p(m)}} hbox{ mod } p$
(with the conventions ${nu_p(0)=+infty}$ and ${f_p(0)=1}$ ). Within the case ${p_1=3, p_2=5}$ , the primary element of (1) seems like this:

and a typical occasion of the ultimate element ${{mathcal T}(nu_{p_1}(m), nu_{p_2}(m))}$ seems like this:

Amusingly, the ornament right here is actually following the foundations of the kids’s sport “Fizz buzz“.

To exhibit the embedding, we thus want to provide a selected Sudoku rule ${{mathcal S}}$ (in addition to a extra technical preliminary situation ${{mathcal C}}$ , which is mainly required to exclude degenerate Sudoku options corresponding to a relentless answer) that may “seize” the goal perform (1), within the sense that the one options to this particular Sudoku puzzle are given by variants of ${F}$ (e.g., ${F}$ composed with numerous linear transformations). In our earlier paper we had been in a position to construct a Sudoku puzzle that might equally seize both of the primary two parts ${f_{p_1}(m)}$ , ${f_{p_2}(m)}$ of our goal perform (1) (as much as linear transformations), by a process very akin to fixing an precise Sudoku puzzle (mixed with iterative use of a “Tetris” transfer wherein we get rid of rows of the puzzle that we have now absolutely solved, to give attention to the remaining unsolved rows). Our earlier paper handled the case when ${p}$ was changed with an influence of ${2}$ , as this was the one case that we all know the way to embed in a monotiling drawback of the whole thing of ${{bf Z}^d}$ (versus a periodic subset ${E}$ of ${{bf Z}^d}$ ), however the evaluation is the truth is simpler when ${p}$ is a big odd prime, as an alternative of an influence of ${2}$ . As soon as the primary two parts ${f_{p_1}(m), f_{p_2}(m)}$ have been solved for, it’s a comparatively routine matter to design an extra constraint within the Sudoku rule that then constrains the third element to be of the specified kind ${{mathcal T}(nu_{p_1}(m), nu_{p_2}(m))}$ , with ${{mathcal T}}$ obeying the domino constraints.

[ad_2]

Like this:

LEAVE A REPLY Cancel reply