17
$\begingroup$

Does there exist a closed curve, with finite area and finite circumference, of which it is undecidable (in an axiomatic system where it is constructable) whether it can tile the plane?

I know the general problem of a set of polygons is undecidable, but I haven't found any information on the single tile case.

$\endgroup$
1
  • $\begingroup$ This is related to a question at Math Stacexchange: math.stackexchange.com/questions/19205/… I thought I had heard that there is a single tile such that the fact that it tiles the plane is independent of ZFC, but now I'm not so sure. $\endgroup$
    – Jim Conant
    Jan 27, 2011 at 19:45

3 Answers 3

16
$\begingroup$

If I remember right any Turing machine can be translated into a set of Wang tiles, so that the tiling problem for this set of tiles is equivalent to the decidability of the turing machine.

Assuming the non-existence of an aperiodic set of tiles, Wang provided the Decidability of any tiling problem in R^2. Since this is not possible, it basically proves the existence of aperiodic tiles.

So the general decidability problem turned out to be equivalent to the non-existence of an aperiodic set of tiles , which suggests that the decidability problem for 1 tile might be equivalent to the non-existence of an aperiodic 1 tile. I wonder if the Wang theorem can be changed to prove this, could be a starting point.

Such a tile is called an Einstein tile, and if I remember right the problem of its existence was open until few months ago, but it was reported recently that one was found...

$\endgroup$
5
  • 4
    $\begingroup$ arxiv.org/abs/1003.4279 $\endgroup$ Jan 28, 2011 at 1:05
  • 1
    $\begingroup$ So can the Wang theorem be changed to prove it is the question, any news on this ? $\endgroup$ Jan 28, 2011 at 17:18
  • $\begingroup$ I think there is a confusion here between two notions of decidability. What is known to be undecidable is the algorithmic problem of whether a given set of Wang tiles can tile the plane. The OP seems to be asking whether there exists a fixed tile for which no proof (in say ZFC) exists one way or another. Even if the algorithmic problem for a given single tile turns out to be undecidable (which is not known), I don't think that would (immediately) imply the existence of a single tile for which no proof exists. $\endgroup$
    – Algernon
    Sep 12, 2022 at 11:35
  • 1
    $\begingroup$ @Algernon: "No algorithm exists that handles all cases" is a strictly stronger statement than "it is not possible to prove every case", because one possible algorithm is "generate all strings in some ordering until you find one encoding a proof in ZFC of tiling or non-tiling". If there were always a proof, that algorithm would decide the problem. $\endgroup$ Sep 12, 2022 at 15:24
  • $\begingroup$ @RavenclawPrefect: Hmm... you are right. It seems I was the one who was confused. $\endgroup$
    – Algernon
    Sep 12, 2022 at 15:34
34
$\begingroup$

The answer by Nick S is essentially correct, but I can provide a little more detail.

It is not hard to show that the tiling problem (if a set of shapes admits a tiling of the plane) is decidable if every set of shapes that tile admit a periodic tiling. The algorithm is to put shapes together, look at the way two shapes can combine, 3 shapes and so on. If the shapes cannot tile you will eventually find a ball that cannot be covered, if they can tile periodically you will eventually find the patch that can go periodic.

The discovery of aperiodic tilings and the result that the tiling problem was undecidable were proved at the same time by Berger. In fact Berger used an aperiodic tiling to show that the tiling problem was undecidable (originally in his thesis). Note that he (and others) call it the "domino problem", as the question was originally posed for squares with coloured edges, called Wang tiles.

R Berger The undecidability of the domino problem
Mem. Amer. Math. Soc. 66 1966
https://books.google.com/books/about/Undecidability_of_the_Domino_Problem.html?id=8AmiHD0Lbu8C

Berger's proof was significantly simplified by Rafeal Robinson. An important part of the simplification was considering a smaller set of aperiodic tiles. Berger's example required 20,426 tiles, whereas Robinson's required just 6.

R M Robinson, Undecidability and Nonperiodicity for Tilings of the Plane
Inventiones math. 12 177-209, 1971
http://www.lif.univ-mrs.fr/~fernique/qc/robinson.pdf

Although it proved useful in these proofs, the existence of aperiodic tilings is not equivalent to the undecidability of the tiling problem. For one thing, by definition, the tiling problem is decidable for all known aperiodic tilings. The best case for the tiling problem is a result of Nicolas Ollinger. He shows that the tiling problem is undecidable for sets of 5 tiles using a construction based on polyominoes.

N Ollinger, Tiling the Plane with a Fixed Number of Polyominoes.
Proceedings of LATA 2009, Lecture Notes in Computer Science 5457, Springer 2009, pp. 638-647.
Link

For the question of aperiodic sets of shapes, we have had examples with two tiles (e.g. the Penrose tiling) for a long time, although there are still only a handful of examples with a small number of shapes (<10 for example). The question of a single tile was a longstanding open question, and became known as the einstein problem (a german pun). The answer now depends on your definition of "tile". For a permissive definition (a tile is a compact set that is the closure of its interior, for example) the problem was solved by Joan Taylor, who is not a professional mathematician but decided to take on this particular problem over several years. This is a significant development, but perhaps not the final answer. The tile that she found is not connected. With respect to the setting of this question, the boundary is not a closed Jordan curve, and, for me, this means that it fails "the laser cutter test" I cannot easily make the thing! This result is the preprint given in Richard Borcherds comment:

J E S Socolar, J M Taylor An aperiodic hexagonal tile
Journal of Combinatorial Theory, Series A 118 pp. 2207-2231 2011
https://arxiv.org/abs/1003.4279

I wrote a little bit about the story here:
https://maxwelldemon.com/2010/04/01/socolar_taylor_aperiodic_tile/
and you can also find Joan Taylor's original paper, with beautiful hand-drawn images:
http://www.math.uni-bielefeld.de/sfb701/files/preprints/sfb10015.pdf (Wayback Machine)

On the hyperbolic plane the first strongly aperiodic set (having no symmetries of infinite order) was discovered in 2005, by Chaim Goodman-Strauss:

C Goodman-Strauss A strongly aperiodic set of tiles in the hyperbolic plane
Inventiones Mathematicae, 159, Number 1, 119-132, 2005, DOI: 10.1007/s00222-004-0384-1, http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf (Wayback Machine)

The tiling problem took a little longer, and was only shown to be undecidable recently (in 2006-7), independently by Maurice Margenstern and Jarkko Kari, who give distinct proofs.

M Margenstern, The Domino Problem of the Hyperbolic Plane is Undecidable
The Bulletin of the EATCS 93 220--237 2007
https://arxiv.org/abs/0706.4161

J Kari, On the Undecidability of the Tiling Problem
SOFSEM 2008: Theory and Practice of Computer Science Springer Lecture Notes in Computer Science, 4910, 74-82 2008
Link

$\endgroup$
3
$\begingroup$

Isn't this question equivalent to the Heesch Problem of determining how much of the plane can be tiled by a given single tile?

See http://math.uttyler.edu/cmann/math/heesch/heesch.htm (Wayback Machine) for examples.

$\endgroup$
3
  • $\begingroup$ Hmm maybe, or almost, "an argument based on the axiom of choice shows that a shape with infinite Heesch number must tile the plane" ics.uci.edu/~eppstein/junkyard/heesch $\endgroup$ Jan 27, 2011 at 18:17
  • $\begingroup$ Is axiom of choice really needed for that? $\endgroup$ Jan 27, 2011 at 18:17
  • $\begingroup$ Yes, an instance of it would definitely pop out. Because to show the tiling partitions R^2 is the same as showing there is a choice function from the infinite cardinal in question into the partition (in fact you will be showing that a lot of them exist) $\endgroup$
    – Not Mike
    Jan 27, 2011 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.