Crystallography & Symmetry
patterns derived from their groups
Concept

Certificate — where it appears

A finite object whose existence settles a question, checkable without repeating the search that found it. A block that tiles a torus certifies that a tile set covers the plane; a square that cannot be filled certifies that it does not.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

8 tiles over 5 colours. Wang tiles: unit squares with a colour on each edge, which may be laid side by side only where the touching edges agree, and which may never be turned or reflected. That last restriction is what makes them a computational object rather than a jigsaw — an edge colour is a symbol passed from one tile to its neighbour, and turning a tile would let a symbol change direction. The set here was generated from a stated seed.

Nothing decides whether a set of tiles tiles the plane

This collection rests on decidability — generate a pattern, forget the group, rediscover it, compare. One question in the same subject has no procedure at all: given a finite set of tiles, whether they cover the plane cannot be decided by any algorithm whatever. What can be done is two half-searches, and measuring what they leave behind.

classification · Decidability heesch-two: surrounded 2 times. A shape that tiles nothing, with the rings of copies it does accept: the seed in the first colour and 2 coronas of 7 and 16 copies round it. The search that built this finished, so the shape's Heesch number inside this box is exactly 2, and it cost 3,097 placements. Every cell touching a tile of one ring, corners included, is covered by the next.

Surrounded twice over, and covering nothing

A shape that tiles the plane can be surrounded by copies of itself for ever. A shape that tiles nothing cannot be surrounded for ever — but it can be surrounded once, and sometimes twice, and the number of times is a measurement of how much local success a global impossibility permits.

classification · Decidability

Named alongside it

The objects these essays reach for when they reach for this one.

DecidabilityLocal rulesTiling by a groupAperiodicityCase analysisEnumerationForcingHeesch numberMatching rulesWang tile

All concepts