# Decidability of tiling R^2

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.

-
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. –  Jim Conant Jan 27 '11 at 19:45
add comment

## 4 Answers

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 decibility 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 Eistein 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...

-
arxiv.org/abs/1003.4279 –  Richard Borcherds Jan 28 '11 at 1:05
So can the Wang theorem be changed to prove it is the question, any news on this ? –  fastforward Jan 28 '11 at 17:18
add comment

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
http://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.
http://www.springerlink.com/content/x5nkq3640w6784w4/

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
http://arxiv.org/abs/1003.4279

I wrote a little bit about the story here:
http://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

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
http://math.uark.edu/A_Strong_Aperiodic_Set_of_Tiles_in_the_Hyberbolic_Plane%281%29.pdf

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
http://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
http://www.springerlink.com/content/673165n258t18741/

-
add comment

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 for examples.

-
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 –  fastforward Jan 27 '11 at 18:17
Is axiom of choice really needed for that? –  fastforward Jan 27 '11 at 18:17
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) –  Michael Blackmon Jan 27 '11 at 19:50
add comment

Yes.

Define the Jordan curve C by "(the Continuum Hypothesis is true and C is the counterclockwise path onto the unit square which starts at $\langle 0,0\rangle$ and has speed everywhere equal to 1/4) or (the Continuum Hypothesis is false and C is the counterclockwise path onto the unit circle which starts at $\langle 1,0\rangle$ and has speed everywhere equal to $\frac1{2\cdot \pi}$)".

Then it is undecidable in ZFC whether C can tile the plane.

EDIT:
Now, perhaps you could say what you do mean by "constructable in the same axiomatic system which it is undecidable", since I am completely stumped.

-
I am interested in pathological cases, but this contradicts the meaning I intended for it to be constructable in the same axiomatic system which it is undecidable :) –  fastforward Jan 27 '11 at 18:37
Ricky, do you think this is the intended interpretation of the question? –  Andres Caicedo Jan 27 '11 at 18:37
it must be constructable in the same axiomatic system as that which it is undecidable if it can tile the plane in. It could be that the tiling of a given curve is undecidable in some axiomatic theory, but decidable in another. –  fastforward Jan 27 '11 at 19:11
Yes, and if by "constructable in the same axiomatic system ..." you don't mean definable, you should say what you do mean. If you're looking for suggestions about that, you should say so. –  Ricky Demer Jan 27 '11 at 19:16
How does that define a Jordan curve? If CH is false, it doesn't. –  Jim Conant Jan 27 '11 at 19:41
show 3 more comments