Wang World

Wang Tiles Encyclopedia · Article 3 of 10

Aperiodicity: Tilings That Can Never Repeat

What periodicity means, how small aperiodic Wang sets force hierarchy, and how finite computation helps reveal structures that no translation can preserve.

The complete Culik 13-tile and Jeandel–Rao 11-tile protosets, shown before their tilings. Colors are symbolic and mapped independently for each set.
The complete Culik 13-tile and Jeandel–Rao 11-tile protosets, shown before their tilings. Colors are symbolic and mapped independently for each set.

A plane tiling is periodic when translating it by some nonzero integer vector leaves the entire assignment unchanged. A protoset is aperiodic when it can tile the whole plane but none of its full-plane tilings has such a translational symmetry.

Why aperiodicity is subtle

It is easy to prevent one small period and easy to create a tile set that cannot tile at all. The challenge is to permit infinite tilings while excluding every period. Successful constructions force information to propagate across scales: rows encode arithmetic, markers organize larger blocks, or substitutions make each apparent motif part of a larger nonrepeating hierarchy.

A finite picture cannot prove aperiodicity. Any 15 × 15 patch is finite and could occur inside a larger periodic pattern made with different rules. The theorem is about all infinite tilings admitted by the specified protoset. Nevertheless, finite patches are valuable: they reveal bands, fault lines, substitutions, and candidate periods worth testing.

Compact landmark protosets

Berger’s first aperiodic Wang construction was historically decisive but contained 20,426 tiles. Later reductions made complete sets practical to inspect. The two compact landmarks displayed above are Culik’s 13 tiles and the minimal Jeandel–Rao 11 tiles. Each square is one prototype; unlimited translated copies may be used, but classical Wang tiles are not rotated or reflected.

The Culik 13-tile set

Karel Culik II’s 1996 construction reduced aperiodicity to 13 tiles using five symbolic colors. It belongs to the Kari–Culik family, whose rows encode division by 2 or multiplication by 3 through local transitions. Irrational average values prevent the resulting hierarchy from closing into a period.

Gapless 15 by 15 tiling with the Culik 13-tile aperiodic set
A gapless 15 × 15 Culik patch generated with the published 13 edge tuples. Equal colors meet continuously across every internal edge.

Jeandel and Rao’s 11 tiles

Jeandel and Rao combined structural arguments with computer enumeration. Their search ruled out aperiodic sets of ten or fewer tiles, then isolated an 11-tile candidate and proved it aperiodic. Later work by Sébastien Labbé exposed substitutive and dynamical structure in its tiling space. The result is both a minimality theorem and a model of computer-assisted discovery.

Gapless 15 by 15 tiling with the Jeandel–Rao 11-tile aperiodic set
A gapless 15 × 15 Jeandel–Rao patch generated from the 11 prototypes shown at the beginning of this article.
State of the art: 11 is minimal for Wang tiles under the classical fixed-orientation, translation-only definition. Allowing rotations, reflections, shaped tiles, or different matching rules creates different minimization problems.

Admitting an aperiodic tiling is not enough

A set admits an aperiodic tiling if at least one legal full-plane tiling has no translational period. It forces aperiodicity only if every legal full-plane tiling is nonperiodic. The distinction is easy to miss: a flexible protoset may support both kinds.

The four prototypes below are indexed by two bits. Their top and bottom colors carry a column bit, while left and right carry a row bit. Every row sequence and every column sequence can be chosen independently. Choosing two nonperiodic bi-infinite sequences produces an aperiodic plane tiling; choosing repeating sequences produces the illustrated periodic tiling.

A four-tile protoset and a periodic tiling with a highlighted three-by-two fundamental rectangle
This four-tile set admits aperiodic tilings but does not force them. In the displayed tiling, the highlighted 3 × 2 rectangle is a fundamental period and repeats in both directions.

There is also a general, deliberately simple construction: take any forced-aperiodic set, such as Culik’s, and add one monochrome tile using a brand-new edge color. The original set still supplies aperiodic tilings, while copies of the new tile alone supply a 1 × 1 periodic tiling. The enlarged protoset therefore admits both without forcing either behavior.

Wang World’s hard-set search uses a related finite signal without claiming to prove aperiodicity. Candidate protosets are tested against small periodic rectangles. If a set quickly admits short horizontal or vertical periods, it often produces repetitive and comparatively easy finite boards. Rejecting those candidates concentrates computation on sets whose constraints remain unresolved over larger scales.

This is a heuristic filter, not an aperiodicity certificate. Passing all tested periods only means that no period in the tested range was found. The surviving protosets are then evaluated as puzzles using seeded search and contradiction counts. Read Searching for hard puzzles for the complete pipeline.

Sources

  1. Karel Culik II, “An Aperiodic Set of 13 Wang Tiles,” Discrete Mathematics 160 (1996).
  2. Emmanuel Jeandel and Michael Rao, “An aperiodic set of 11 Wang tiles,” arXiv:1506.06492.
  3. Sébastien Labbé, “A Markov partition for the Jeandel–Rao aperiodic Wang shift,” arXiv:1903.06137.
  4. The displayed edge tuples follow the public examples in Sébastien Labbé’s slabbe mathematical software.