One shape, two kinds of tile

Look at a floor tiled with one shape and there is nothing to see. Every tile is the same size and the same outline; a tile lifted from one place would fit in any other. It is hard to imagine what could make one of them different from another.

The symmetry group of the tiling can. Congruence is a relation between two shapes, and it is settled by picking one up and putting it down on the other. Being in the same orbit is a relation between two tiles of a particular pattern, and it is settled by asking whether some motion of the whole pattern — every tile at once — takes the first to the second. Those are different questions, and the second can fail where the first succeeds.

A tiling whose group carries any tile to any other is isohedral. A shape all of whose tilings need more than one orbit is anisohedral. Hilbert asked, as the second half of his eighteenth problem in 1900, whether anisohedral tiles exist. Heesch answered in 1935 by producing one.

What “the same tile” means in a pattern #

The distinction takes a moment to feel real, so it is worth taking that moment.

Consider a tiling and a tile in it. The set of motions carrying the whole tiling onto itself is a plane group — every tile goes to a tile, every edge to an edge. Within that group, the tiles fall into orbits: two tiles are in one orbit when some operation of the group carries the first exactly onto the second.

A tile’s orbit is decided by its surroundings, not by its shape. Two tiles in one orbit have identical neighbourhoods out to any distance, because the motion carrying one to the other carries the neighbourhood too. Two tiles in different orbits do not: somewhere, at some distance, the pattern round them differs, and no motion of the pattern repairs it.

That is the same distinction the whole of this collection rests on, in a new place. A pattern is an orbit: a motif and a group, with the group deciding what is the same as what. Here the motif is a tile and the surprise is that the group may see two kinds where the eye sees one.

The search, and why it terminates #

Showing that a shape has an isohedral tiling means exhibiting one. Showing that it has none means searching, and the search has to be finite or the claim is worthless.

It is finite, and the bound is short enough to state. An isohedral tiling has a symmetry group G. The tiles are unions of cells of the square grid, so G maps grid cells to grid cells, and every symmetry of the grid of cells is v ↦ M v + t with M one of the eight matrices of the square’s point group and t an integer vector — the group of the grid is ℤ² ⋊ D₄ and nothing else, which is the finiteness argument this collection uses everywhere in miniature. So:

• G’s point group P has order at most eight;
• G’s translation lattice L has one orbit of tiles per cell, so a cell of L contains |P| tiles, divided by however many operations fix a tile;
• a cell of L therefore has area at most eight times the tile’s.

Every lattice of index at most 8n, every point group inside D₄, and every assignment of translation parts to that point group’s generators — a finite list, enumerated. For each candidate the tile’s orbit is generated and the covering checked cell by cell. No isohedral tiling is then a result rather than a report of failure.

The shape #

The cell those tilings need is long and thin, and that is a fact about the tile rather than about the drawing. The search finds the shape’s tilings on tori and prefers the squarest torus among those needing the fewest orbits, so the cell in the figure above is as square as this shape allows — and it is still elongated, because nothing squarer admits a tiling by it at all. A reader who expects a picture of a tiling to be a comfortable block is meeting the constraint directly: the two orbits are not a decoration on an otherwise ordinary pattern, they come with a lattice that has no freedom in it either.

Nothing about the picture betrays it. That is the point, and it is the same point this collection makes about pattern figures generally: a wrong caption over a well-drawn pattern looks exactly like a right one, and the only thing that catches the difference is a computation. Here the computation is the orbit count, and it is run on every tiling of every torus the search reaches rather than on the one that happens to be drawn.

Why the eye is no help #

The failure mode here is worth naming, because it is the reason this is a theorem rather than an observation.

Given a patch of the anisohedral tiling, a reader can see that some tiles sit in one orientation and some in another. That is not the point: plenty of isohedral tilings use several orientations, and the group carries between them. What has to be shown is that no operation of the whole pattern exchanges the two kinds, and that no other tiling of the plane by the same shape does better.

The first is a computation on one tiling. The second is a computation over all of them, and it is the one the bound above makes possible.

Two orbits, and what a crystallographer would call it #

There is a translation of all this into the language the rest of the site uses, and it is exact.

An isohedral tiling is a tiling in which the tiles form one orbit — one Wyckoff position, in the vocabulary of a crystal structure. An anisohedral tiling is one in which they form two, so the structure has two crystallographically distinct sites occupied by the same object.

The translation is exact enough to carry the arithmetic across. A Wyckoff position’s multiplicity is the size of an orbit, its site symmetry is the stabiliser of one member, and the product of the two is the order of the group acting on one cell — which is precisely the relation the figure below checks on the two orbits of tiles. A crystallographer reading a structure report sees that relation as a column of numbers whose product is fixed; here it is the same relation with the object being a tile rather than an atom, and with the extra condition that the tiles fill the plane exactly.

That is completely ordinary in a crystal. A mineral with two independent molecules in its asymmetric unit is a mineral whose molecules come in two kinds by symmetry and one kind by chemistry, and the crystallographic literature calls it Z′ = 2 without comment. The site symmetry of each is trivial, the two are related by no operation of the group, and a structure report lists both. What is unusual here is only that the object is a tile and the tiles are required to fill space exactly, so the two kinds cannot differ by even a small displacement. Where a crystal may sit at a special position or near one, a tile has no room to be nearly anywhere.

Conway’s criterion could never have certified this shape, and the reason is structural rather than a matter of it being missed. The criterion’s output is a group — one translation and four half turns — and the tiling it produces is the orbit of one tile under that group, so it acts transitively on tiles by construction. Anything the criterion certifies is therefore isohedral, which the census confirms in the strongest available form: of the five hundred and thirty-three shapes, not one is certified by the criterion and lacking an isohedral tiling. That cell of the table is empty and the figure asserts that it is. A shape sitting in it would not be a curiosity about polyominoes; it would be a defect in the criterion.

How the search could be wrong, and what catches it #

An exhaustive search that quietly fails to be exhaustive is worse than no search, because it returns a confident negative. Three things could go wrong here and each is checked rather than argued.

The bound could be wrong. If a tiling existed whose translation lattice had index above 8n, the search would miss it. The bound comes from the point group of the grid having order at most eight, which is a fact about D₄ and is not an estimate — and the machinery asserts, for every product it forms, that a product of grid symmetries is again one of the eight, so a bug that let an unexpected linear part through would raise rather than pass.

The covering test could be loose. A candidate group is accepted only when its orbit covers every cell of one lattice cell exactly once — counted, not sampled. A group whose orbit leaves a gap or doubles a cell is rejected there, which is the same check the criterion’s own construction runs on the tilings it builds.

The translation lattice could be wrong. A candidate group whose closure contains a translation outside the lattice it was built on has a larger translation lattice than assumed, so the count of tiles per cell is wrong. Such a candidate is rejected rather than adjusted, because the same group will be found again in the search over its true lattice. Dropping that test would let one group be counted twice and, worse, at the wrong index.

A fourth failure mode is not caught by any of that, and is worth stating plainly. The search is over tilings whose symmetry group is a group of the grid. A tiling by these shapes whose symmetry group is not — one using an irrational translation, say — is outside it. No such tiling can exist for a polyomino, because the tiles’ corners are lattice points and a symmetry of the tiling permutes them; but that is an argument rather than a computation, and it is the one place this result rests on a sentence rather than a check.

Heesch, and how far the question goes #

Heesch’s tile of 1935 was not a polyomino. It was a hexagon with its edges modified — the standard way of building a tile with a prescribed group — and the point of it was to answer Hilbert rather than to be small. The construction is the one every ornamentalist uses: start from a shape that tiles, and modify each edge in a way the group carries onto the modification of its partner.

The small examples came later, and they came from search. The smallest anisohedral polyomino has area eight, which is what the census here reproduces. There are anisohedral polyominoes needing three orbits, and four, and more; Myers’s catalogues run into the thousands. The largest number of orbits any polyomino is known to need is a number that keeps rising as the searches get longer, and there is no theorem bounding it.

Hilbert’s question had a second half that is still open in three dimensions in a form worth stating. He asked whether a polyhedron could tile space without a group acting transitively on the copies; Reinhardt gave one in 1928, before Heesch’s plane example. What remains awkward there is the same as here: exhaustive search is possible only because the number of candidate groups is bounded, and in space the bound is much larger.

It is worth holding the opposite extreme in mind for orientation. A tiling by two different shapes — a trihexagonal floor of triangles and hexagons, say — also has two orbits of tiles, and nobody finds that surprising: the group is transitive on the triangles and transitive on the hexagons, and it obviously cannot carry a triangle to a hexagon. That is the ordinary situation, and it is what makes the anisohedral case strange. Two orbits is unremarkable. Two orbits carrying one shape is what Hilbert had to ask about, because the thing that usually distinguishes orbits — the tiles being different — has been removed, and they stay distinguished anyway.

What this says about local and global #

A tile is a local object. A tiling is a global one. The relation between them is what the previous rung’s criterion exploits: read something bounded, force something unbounded.

Anisohedrality is the place where that relation runs out. The shape is one shape everywhere; every tile has the same outline and the same area; and yet the pattern the shape is forced into distinguishes them. No amount of looking at the tile predicts it — the criterion cannot, and neither can any of the eight other boundary conditions, since all of them certify isohedral tilings and this shape has none.

What settles it is a search over the global object: all the groups, all the tilings, all the orbits. That search is finite here because the tiles live on a grid. Move to shapes with curved edges and the bound goes, and with it the guarantee that a negative answer means anything.

What the two orbits look like from inside #

A last way of seeing the distinction, which is the one that makes it stop feeling like a technicality.

Stand on a tile of the anisohedral tiling and look at the pattern around it out to some radius. Do the same from a tile of the other colour. The two views differ, and they differ at every radius large enough to reach the neighbours — because if they agreed out to every radius the two tiles would be in one orbit, by an argument about limits of motions that is standard and is not made here.

That is what having two kinds of tile means physically. It is not a labelling and it is not a matter of how the picture is coloured: a reader with a large enough window and enough patience could sort the tiles into the two classes without being told which is which, by comparing surroundings.

And it is the reason the count of orbits is the right invariant rather than the count of orientations. Orientations are a property of how the tiles sit; orbits are a property of what the pattern can do. A tiling may use eight orientations and have one orbit, or two orientations and two orbits, and only the second number says anything about the pattern’s symmetry.

The isohedral tilings are themselves a finite list #

The search on this page asks whether a shape has an isohedral tiling. There is a prior question — how many kinds of isohedral tiling there are at all — and it has a finite answer, which is what makes the search’s bound believable.

An isohedral tiling can be classified by the combinatorics of how a tile meets its neighbours: which edges are identified with which, and by which operations. Two tilings of the same type are the same arrangement with different shapes drawn in, exactly as two patterns of the same plane group are the same symmetry with different motifs. Counting the types is a finite computation, and the answer is eighty-one.

That number is doing real work. It says the space of arrangements a monohedral tiling can have is small and enumerable, so a search over it is exhaustive rather than hopeful — and it explains why the bound on this page can be stated at all. A tiling by n-cell shapes with a translation lattice of index at most 8n is a bound on one of eighty-one arrangements rather than on an open-ended family.

The classification also supplies the vocabulary for the negative results. A shape that tiles isohedrally does so in one or more of the eighty-one types; a shape that tiles anisohedrally fits none of them, and saying so is a stronger statement than saying a search failed, because the eighty-one are a complete list rather than a search space.

How many orbits a shape can need #

Two orbits is the smallest departure from isohedral, and it is not the largest. The obvious next question — how many orbits a shape can be forced into — has an answer that has moved several times and is not finished.

A tiling in which the tiles fall into k orbits is k-isohedral, and a shape whose best tiling is k-isohedral is k-anisohedral. Heesch’s shape and the eight-cell polyomino on this page are 2-anisohedral. Searches over polyominoes have since produced shapes requiring three orbits, then four, and then rather more — each one found by exhaustive search over a larger set of shapes, and each raising the known maximum without bounding it.

Whether the number is bounded at all is open. Nothing known forbids a shape that tiles the plane and requires a hundred orbits, and nothing known constructs one. That is an unusual position for a question about polyominoes, where most things are settled by a large enough computation, and it is a consequence of the same asymmetry this page’s search has: exhibiting a k-isohedral tiling is a certificate, and showing that no tiling with fewer orbits exists is a search.

It also puts the anisohedral shape in context. It is not an exception to a rule that shapes tile homogeneously; it is the first member of a sequence whose length nobody knows, and the reason the smallest one has eight cells rather than four is that the shapes are ordinary and the property is rare, not that the property is fragile.

Where the ladder goes next #

Two directions lead out. One is how much local success a shape that tiles nothing can have: a shape can be surrounded, and surrounded again, and still cover nothing, and the number of times is a measurement rather than a guess.

The other is back towards the classification this site is built on. A tiling with two orbits of one shape is a pattern whose group has two Wyckoff positions carrying the same object, and that is a statement about subgroups and orbits rather than about tiles. The tile is a way of making the distinction visible, and the distinction was there all along.

That is also the right way to read the census on this page. Five hundred and thirty-three shapes were examined and one of them is anisohedral, which sounds like a curiosity; the honest reading is that the property is rare among small shapes and nothing known says it stays rare, and the search found the smallest instance rather than the only one.