Type: Article
Publication Date: 2023-01-04
Citations: 6
DOI: https://doi.org/10.1007/s00454-022-00426-4
Abstract We construct an example of a group $$G = \mathbb {Z}^2 \times G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>×</mml:mo><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:mrow></mml:math> for a finite abelian group $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> , a subset E of $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> , and two finite subsets $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> of G , such that it is undecidable in ZFC whether $$\mathbb {Z}^2\times E$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup><mml:mo>×</mml:mo><mml:mi>E</mml:mi></mml:mrow></mml:math> can be tiled by translations of $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> . In particular, this implies that this tiling problem is aperiodic , in the sense that (in the standard universe of ZFC) there exist translational tilings of E by the tiles $$F_1,F_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>F</mml:mi><mml:mn>1</mml:mn></mml:msub><mml:mo>,</mml:mo><mml:msub><mml:mi>F</mml:mi><mml:mn>2</mml:mn></mml:msub></mml:mrow></mml:math> , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mn>2</mml:mn></mml:msup></mml:math> ). A similar construction also applies for $$G=\mathbb {Z}^d$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mi>Z</mml:mi></mml:mrow><mml:mi>d</mml:mi></mml:msup></mml:mrow></mml:math> for sufficiently large d . If one allows the group $$G_0$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msub><mml:mi>G</mml:mi><mml:mn>0</mml:mn></mml:msub></mml:math> to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F . The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.