zbMATH — the first resource for mathematics

An aperiodic set of 13 Wang tiles. (English) Zbl 0865.05033
Wang tiles are unit squares with colored edges. A tile set is a family of Wang tiles. The aim is to cover up the infinite Euclidean plane by using arbitrarily many copies within a given tile set. The tiles are placed on the integer lattice points with edges oriented horizontally and vertically. The tiles may not be rotated and contiguous edges must be of the same color. If \(T\) is a tile set then a tiling of Euclidean plane can be viewed as a function of \(Z^2\rightarrow T\). A tiling is called periodic if the associated function \(f\) is doubly periodic. A tile set is called aperiodic iff it allows a tiling of the plane but no periodic ones.
The first aperiodic tile set was constructed by Berger and consisted of 20426 tiles. Later on this was reduced to 104 tiles. Knuth, Penrose and others gave constructions for tile sets having less tiles. The best known construction up to now was that of Ammann and consisted of 16 tiles. The present paper gives a construction of an aperiodic tile set consisting of 13 tiles and 5 colors.
The proof of its aperiodicity is very elegant and uses a mapping of tiles to the states of a finite automaton that can be used for multiplication of real numbers in balanced representations by real constants. The aperiodicity of the tile set is based upon the numbers 2 and 3 being relative prime.

05B45 Combinatorial aspects of tessellation and tiling problems
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
Full Text: DOI
[1] Beatty, S.; Beatty, S., Problem 3173, Amer. math. monthly, Amer. math. monthly, 34, 159, (1927), solutions in · JFM 53.0198.06
[2] Berger, R., The undecidability of the domino problem, Mem. amer. math. soc., 66, (1966) · Zbl 0199.30802
[3] Grünbaum, B.; Shephard, G.C., Tilings and patterns, (1987), Freeman New York · Zbl 0601.05001
[4] J. Kari, A small aperiodic set of Wang tiles, Discrete Math., to appear. · Zbl 0861.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.