How many fixed polyominoes does it take to force an aperiodic tiling of the plane

geometrypolyominoreference-requesttessellationstiling

A longstanding open problem asks whether there is a single connected tile that only tiles the plane aperiodically. As far as I know, this is still open even in the case of polyominoes: we do not know if there is a single polyomino that forces an aperiodic tiling of the plane.

I am curious about the case where we treat the polyominoes as fixed, i.e., when we consider rotated/reflected copies of a tile as distinct, and only permit translations. In this situation, we do know that more than one tile is needed; as shown in this paper, a single fixed polyomino tiles the plane periodically if it forms any tessellation at all. (In fact, we can ensure the tiling is isohedral!)

Conversely, there exist finite sets of fixed polyominoes which tile the plane, but not in a periodic manner. If we use Wang tiles to generate polyominoes, we can obtain a solution with $11$ tiles (which is minimal), but there are smaller solutions. For instance, consider Matthew Cook's set of three polyominoes which force an aperiodic tiling (with rotations and reflections allowed):

enter image description here

We observe that the tiling only makes use of $4$ orientations each of two of the tiles, and a single orientation of the third tile, so only $9$ fixed polyominoes are needed in total.

The answer is therefore somewhere between $2$ and $9$ inclusive; I am interested in learning of any improvements to either the upper or lower bounds, or pointers to discussion of this problem in the literature.

One potential avenue for a smaller upper bound is the aperiodic set of polyominoes described at this Wolfram MathWorld page as being announced by Roger Penrose in 1994, but it gives no further details, and I have been unable to track down a reference.

Best Answer

From this series of slides by Nicolas Ollinger, an 8-polyomino set is exhibited that claims to originate in a 1992 paper of Ammann et al, though I don't know the original source. This suggests that 8 is the best known.

enter image description here

Related Question