Are Penrose tilings universal? Do aperiodic universal tilings exist? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T19:15:25Z http://mathoverflow.net/feeds/question/47131 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/47131/are-penrose-tilings-universal-do-aperiodic-universal-tilings-exist Are Penrose tilings universal? Do aperiodic universal tilings exist? Louigi Addario-Berry 2010-11-23T18:47:57Z 2010-11-24T04:29:59Z <p>Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile types as $t_1,\ldots,t_k$. Say that an {\em animal} using tiles $t_1,\ldots,t_k$ is a connected subset of the plane that can be obtained by gluing a finite number of tiles together along their edges; identify congruent subsets. If there is only one type, this is often called a <i>polyomino</i>; here are some pictures of polyominoes in the square lattice (which has only one type of tile and is not in fact an interesting lattice from the point of view of this question). </p> <p><img src="http://mathworld.wolfram.com/images/eps-gif/Polyominoes_1300.gif" width="400"> </p> <p>Say that a tiling of the plane using (distinct) tiles $t_1,\ldots,t_k$ is <i>universal</i> if it contains every possible lattice animal using tiles $t_1,\ldots,t_k$. To explain what I mean by "possible", suppose that $k=2$, that $t_1$ is the "thin diamond" from the Penrose tiling and that $t_2$ is the "thick diamond. By gluing together four copies of $t_1$ one can obtain the following "animal". </p> <p><img src="http://www.math.mcgill.ca/louigi/images/penroseexample.jpg"></p> <p>This animal can't be contained within <em>any</em> tiling (Penrose or otherwise) using $t_1$ and $t_2$. So it makes sense to restrict to animals which, for example, are contained within <em>some</em> tiling of the plane with the given tiles. </p> <blockquote> <p>My question is: are there $k \geq 2$ for which (aperiodic -- adjective added in edit) universal tilings exist? </p> <p><b>Edit:</b> when I first posted the question I omitted the adjective aperiodic above. As pointed out in comments, in this case the answer is obviously yes, which is good to have had pointed out. </p> </blockquote> <p>We can also restrict the allowed animals. For example, we could restrict to animals which exhibit some form of symmetry. </p> <blockquote> <p>One could then ask: do aperiodic tilings exist which are universal for animals in a (non-trivial) restricted class? Are there any interesting results along these lines? Is the Penrose tiling itself known to be universal for some interesting class of animals? </p> </blockquote> <p><img src="http://upload.wikimedia.org/wikipedia/commons/1/1a/Penrose_Tiling_(Rhombi).svg"></p> http://mathoverflow.net/questions/47131/are-penrose-tilings-universal-do-aperiodic-universal-tilings-exist/47152#47152 Answer by Aaron Meyerowitz for Are Penrose tilings universal? Do aperiodic universal tilings exist? Aaron Meyerowitz 2010-11-23T21:52:34Z 2010-11-24T01:44:19Z <p>I thought that EVERY plane tiling by the two Penrose tiles is universal (<strong>later</strong> I checked, that is indeed the case as Peter explains nicely below). It is cheap but you could take any (set of) possible animal(s) and call them new tiles. I think that Penrose started with a set of 6 tiles, probably with the same property (and probably derivable in the way I mentioned from the two tile set). You could also split one or both Penrose tiles into weird pieces which only fit together to recreate that piece.</p> <p>If I recall correctly, it is an open question if there is a single tile which only tiles aperiodically. SO it is premature to ask if there is one which has a universal tiling (not that you asked that).</p> <p>In the periodic case (from when that was part of the question) I can certainly specify two (or even any k) gawky tiles which only tile in one way so that is automatically universal. It is easier to think of colored tiles. (maybe squares constrained to fit 4 at each corner) it is easy to see how to make a universal tiling. There are ways to replace these with huge squarish polyomonoes with lock and key bumps.</p> http://mathoverflow.net/questions/47131/are-penrose-tilings-universal-do-aperiodic-universal-tilings-exist/47193#47193 Answer by James Currie for Are Penrose tilings universal? Do aperiodic universal tilings exist? James Currie 2010-11-24T04:29:59Z 2010-11-24T04:29:59Z <p>A very nice reference on this family of questions is Grunbaum and Shephard's book Tilings and Patterns (now out in paperback). It has starred problems which are hard, and double-starred problems which are research projects. It is in this book that we find the problem of whether there is a tile which only tiles aperiodically. (There is such a beast for the 3-dimensional analog, but it's a bit of a cheat.) I contacted Grunbaum about this a few years ago, and he said the problem was still open.</p>