One tile, two lattices, and a row that slides

A tiling of the whole plane, decided on one tile’s edge found which polyominoes tile at all, and one shape, two kinds of tile asked with how many orbits. Both questions treat a tile’s tilings as one lump. This essay asks about the simplest tiling a tile can have, the kind a crystal is made of: copies of the shape, all facing the same way, one at each point of a lattice. The question is how many lattices a given shape can sit on.

The natural assumption is one, or close to it. In a crystal the molecule and the lattice look like a matched pair, since a particular cell with particular contents is what crystal structure means. A shape with protrusions and notches would seem to have one way of nesting with itself, and a rectangle, with no notches at all, would seem to be the exception.

The census says otherwise, and it says something definite. Plenty of tiles have more than one lattice, and several have as many as seven. But those lattices are not independent of one another. They group into families, and no tile tested has more than two families. Within a family, the lattices differ by how far a whole row of copies has been slid along the row below. That is what a stacking fault is, and it means a shape with a family has more than a few lattice tilings: it has uncountably many tilings, most with no period, all from one tile. This is the polytype, seen in a place with no atoms in it.

The test, and why it is exact #

The setup is simple enough to state completely. A polyomino is a connected set of $n$ cells of the square grid, counted up to rotation and reflection, and a lattice here is a subgroup of the grid’s translations. A tile lies on a lattice $L$ when the copies of the tile at the points of $L$ cover the grid exactly once. That requires $L$ to have index exactly $n$, since one tile must fill one cell of the lattice, and it requires the $n$ cells to fall in $n$ different cosets of $L$. Those two conditions are also enough.

So nothing has to be searched for. How many sublattices gave the list: the sublattices of index $n$ number exactly the sum of the divisors of $n$, and each is a basis $(a, 0)$, $(b, d)$ with $ad = n$ and $0 \le b < a$. Reduce each cell’s coordinates to that basis and see whether any coset repeats. That is at most a few dozen short checks per shape.

Only one point here is not a direct computation. A tile could conceivably tile by translations without being on a lattice, its copies arranged irregularly. Wijshoff and van Leeuwen proved in 1984 that for a polyomino this cannot be the only way: a polyomino that tiles by translations also tiles by a lattice. Beauquier and Nivat gave the criterion in terms of the boundary word in 1991: the boundary must split into six arcs in three opposite pairs, the shape of a pseudo-hexagon. Both are quoted. The criterion the earlier essay uses is Conway’s generalisation, which allows half turns, and this essay needs none of it directly, since the coset check gives the same answer more cheaply.

One tile, two fits #

The first interesting shape appears at five cells.

The shape in the figure, a skew five-cell tile, has exactly two lattices, and they are not related by anything obvious. It has no symmetry that could carry one to the other, since it has no symmetry at all, and the mirror image of a tiling of this tile is a tiling of a different tile. The two tilings are simply two different solutions of the same packing problem.

The plus-shaped pentomino has two lattices as well. Those are mirror images of one another: the plus has a mirror, so its two lattices are one fit seen from the two sides, and that is the classical chess-knight arrangement. So a tile can have two lattices for a reason that is visible in the tile, as the plus does, or for no reason that shows, as the skew tile does.

The literature calls such a shape a double square. When a tile’s boundary splits into four arcs in two opposite pairs, its lattice is a square-like one, and a double square is a boundary that splits in two different ways. Those were studied as words by Beauquier and Nivat, Xavier Provençal showed that a polyomino has at most two such splittings of a fixed kind, and Alexandre Blondin Massé, Srečko Brlek and others later built infinite families, using Christoffel words and Fibonacci words. The census here makes the same point from the other direction: it asks about lattices rather than words, and two is also where it stops, except for what the next section is about.

When there are more than two #

Count over all polyominoes up to size thirteen, and the histogram contains larger numbers than the double squares allow.

The census is exhaustive at each size: 238,591 shapes at thirteen, each tested against every sublattice of index thirteen. Lattice tiles become rare fast, from all five tetrominoes at $n = 4$ to about 1.3% at $n = 13$. Of those at size twelve that are not rectangles, 2,400 have one lattice, 205 have two and 104 have more.

The shapes with more than two have a common property that one example makes obvious.

Copies of the S-tetromino at multiples of $(2, 0)$ make a row, and that row turns out to be a straight strip of height two, with flat top and bottom edges, even though the tile itself has notches. A row with a flat top can sit against the next row at any offset. So each offset gives a tiling, and each of those offsets repeated forever is a lattice.

That is what a family is, in this essay’s definition: lattices that share a translation along which copies touch. Inside a family, the lattices differ in how far a row is displaced. Between two families, nothing of the sort connects them. The computed result is that every tile from two to thirteen cells has at most two families, so the double-square count of two survives after all, once the slides are counted as one. And a tile with exactly one lattice per family has exactly the two rigid fits that the literature counts.

The largest counts are at twelve cells, where six tiles have seven lattices each. Twelve has many divisors, and that turns out to be the point.

Why prime sizes lie flat #

The size-by-size maximum has a very visible pattern.

At $n = 5$, $7$, $11$ and $13$ no tile that is not a straight bar lies on more than two lattices, and the reason can be shown in a few lines. Suppose a tile has a sliding family: a row of copies along a vector $v$ can sit against the next row at two different offsets. The difference between those offsets is a translation $w$ along the row that carries the shape of the row’s top edge onto itself, and also the bottom, since a row’s bottom edge has to fit the next row’s top. So the row, as a strip of cells, is invariant under both $v$ and $w$. Those two lie in a single infinite cyclic group of translations along that line, every member of it a multiple of one shortest step $u$, and $v = k u$ with $k \ge 2$, since $w$ is not a multiple of $v$.

The row has $n$ cells per $v$, and it has the same number of cells per $u$ everywhere, so it has $n / k$ per $u$. Thus $k$ divides $n$. For a prime $n$, $k$ must be $n$ itself, and the row has one cell per $u$. A row with one cell per step has all its cells in one coset of a single translation, and for the tile’s cells to touch along edges that translation must be one cell long. So the row is a straight line of cells, and the tile is a bar. So at prime size only the bars have slides, and everything else has at most the two rigid fits.

That argument accounts for the entire shape of the figure, and it holds at any prime, whereas the census reaches only to thirteen. It also says how much sliding a composite size allows: a tile whose rows have period $u$ with $n/k$ cells per $u$ has as many offsets as $k$ allows, and twelve has more divisors than any size below it.

The reasoning resembles something crystallographers already know. Only two and three can centre a lattice reached a list by asking which prime can divide what. There the prime was the index of a centring in the plane. Here it is the size of the motif, and a motif with a prime number of parts cannot be split into repeating sections that slide. It is another place where the arithmetic of the index decides what looks like a question about shape.

Rectangles deserve a sentence, since they are left out of the figure and they are where the expectation of many lattices came from. An $a \times b$ rectangle has rows along either of its two sides, with flat tops, so it has two families. Those have $a$ and $b$ lattices, sharing the single lattice with neither row displaced, for $a + b - 1$ in all when the two sides are both longer than one. Those are the most sliding that a given size allows, and the count of families is two here as well. The rectangle is simply the case where each family is as large as it can be, and it is the shape whose tilings are most like a stack of sheets. The non-rectangular shapes that come nearest, with seven lattices at twelve cells, are shapes with a row of three or four units whose top and bottom are stepped in the same rhythm.

This also explains why a shape’s bumps do not prevent sliding, which is the counter-intuitive part of the first example. It is tempting to think a notch locks a tile to its neighbour. It locks it only if the notch has nothing like it further along the row. If the row’s edge repeats at a finer period than the tile, a notch can engage the next tooth, and the row moves by one tooth. A mechanical analogy is a rack: teeth do not prevent a rack from being placed in any of many positions against another, they only require that the position be a whole number of teeth.

A stack with no period #

Now the connection the essay has been heading towards. If a row can sit against the next row at two offsets, the choice can be made independently at every row.

Every sequence of the two offsets gives a tiling, and they are uncountably many. Each is a set of copies of one tile, all facing the same way, in which each row is periodic and the stacking need not be. Only the two constant sequences, and the periodic ones with a repeating block, are lattices or lattice-with-basis. The others have no two-dimensional period at all.

This is precisely the structure of a polytype. How many polytypes counted the stackings of close-packed layers in a crystal, where each layer can sit in one of two positions on the one below it, and silicon carbide has hundreds of observed stacking sequences for that reason. A stack with no space group drew the case with no repeat at all. There the layer is a layer of atoms and here it is a row of tiles, but the logic is one: a layer whose boundary has a period finer than its own repeat can slide, and that freedom makes a family of structures that differ only in a sequence. An ordered sequence of faults is a polytype, a random one is a disordered stacking, and the diffuse streak of what a faulted stack makes is its diffraction pattern.

It is worth noticing what that shows about the phrase “a tile that tiles only periodically”. The S-tetromino tiles periodically and it also tiles with no period at all. It is not a candidate for anything aperiodic in the sense of the hat, because it does have periodic tilings. But a statement like “this shape packs in a lattice” says little about whether its copies must be so arranged. A molecule with a flat-faced row in its packing is telling a crystallographer to expect stacking disorder, and that can be read from the shape and its size, before growing anything.

What the census does not reach #

The census is exhaustive up to thirteen cells and silent above that. The statement about at most two families is therefore a measurement rather than a theorem, in the form given here. The known theorem about double squares concerns a specific kind of boundary factorisation, and it fits the count of rigid fits, but the translation from factorisations to these families has not been carried out on this page. Above thirteen, a tile with three families would be a surprise to the theory and is not excluded by anything computed here.

Reflections and half turns are excluded by the question. A tile can have many tilings using rotated or reflected copies that do not appear here at all, and the earlier census covers those. So a shape that “lies on no lattice” may tile perfectly well in another way. The U-pentomino lies on no lattice and tiles with half turns. Equally, a tile with exactly one lattice may have many non-lattice tilings using half turns.

The figures show only small windows, and a tiling is an infinite object. The stacking figure shows twelve rows of a sequence that is arbitrary, and nothing about those particular digits means anything. The check that any such stack really is a tiling is exact for the rows drawn, because no two copies are allowed to overlap in the construction, and the row structure guarantees the rest.

How the shapes were held to it #

The cases with known answers come first. A bar of five has five lattices, one for each offset of a row of length five. The plus has its two mirror lattices. The U has none, and it would be a serious fault if it had any, since a tile with a pocket cannot fill the pocket with a translated copy of itself. The stacking construction refuses any arrangement where two copies share a cell, so a mistaken slide fails rather than draws. The prime argument was found by looking at the output, and it was then tested against all of it.

Still open: the third dimension, and a slide along a plane #

A polycube tile in space raises the same question with more room. Its copies at a three-dimensional lattice form layers, and a layer with a flat face can slide freely along two directions, not one. So a family could be two-dimensional, each lattice in it labelled by a pair of offsets from a set whose size again divides the tile’s volume. Whether the bound of two families holds there, or whether the third dimension allows three independent fits, is not known here. The theorem of Wijshoff and van Leeuwen does not even hold in general: there are polycubes that tile by translation and not by a lattice. So in space the lattice question and the translation question genuinely come apart, and a census that tested only lattices would miss what is most interesting. A tile that fills space by translations in layers that slide, with no lattice among its tilings at all, would be the three-dimensional counterpart of what the S-tetromino only half is. Aperiodic is two words in space found that the plane’s two senses of aperiodic also split on the way up. It has not been computed here.