substitution-tiling.md

Start with a finite set of shapes, the prototiles, and a rule that cuts each of them into smaller copies of the prototiles. Scale the pieces back up to the original size and the rule can be applied again, to every piece at once. That rule is a substitution, and the step of scaling up is the inflation: a tile grows by a fixed factor and is cut into tiles of the old size. After n rounds one tile has become a large patch, a supertile of level n, and the tilings of the whole plane in which every finite patch sits inside some supertile are the substitution tilings of the rule.

The chair is the first example to hold in mind. It is an L of three unit squares, a square of side 2 with one quarter missing. Double it and the L of side 4 is cut exactly into four chairs: two pointing the same way as the parent, one in its corner and one in its middle, and two turned a quarter turn, one each way, one on each arm. The figure is one chair cut three times, 64 chairs in all, with the gaps between them narrowing level by level, wide between the four chairs of the first cut and narrow between the 64 of the last, so the four big chairs, the sixteen middle ones and the 64 small ones all read at once. The chairs are coloured by which diagonal they point along, and each cut turns two of the four children onto the other diagonal, so the 64 split 32 and 32.

Counting the pieces is a matter of one table. Give each kind of tile a row and a column, and in column j write how many tiles of each kind sit inside the inflated tile of kind j. That is the substitution matrix M, and the numbers of tiles of each kind in a level-n supertile are the columns of M^n. The chair up to turning is one kind, M = [4], and level n holds 4^n chairs. Keeping track of the four turns, M is a 4 by 4 table with 2 on the diagonal, for the two children that point the parent's way, and 1 in each of the two places for a quarter turn either way.

When some power of M has every entry positive, its largest eigenvalue, the spectral radius rho, is a simple positive root with a positive eigenvector, and the tile counts grow like rho^n with the kinds in the proportions of that eigenvector. The same number is fixed by area. Inflating by a factor lambda in the plane multiplies every area by lambda^2, and the inflated tile is exactly covered by its pieces, so the row of tile areas is an eigenvector of M with eigenvalue lambda^2. Since the areas are positive that eigenvalue is rho, and the inflation factor is lambda = sqrt(rho), or rho^(1/d) in d dimensions. For the chair rho = 4 and lambda = 2.

The sphinx is a shape of six equilateral triangles that, doubled, is cut into four sphinxes in exactly one way, and three of the four are mirror images. So the rule needs two kinds, the sphinx and its reflection, each inflating to one of its own kind and three of the other: M = [[1, 3], [3, 1]], Perron root 4 again, and inflation factor 2.

The kites and darts of Penrose 1979 are two kinds that no grid underlies. Cut every dart in half along its axis; then two half-darts and one kite make a large dart, and two half-darts and two kites make a large kite. Counted in whole tiles a large kite holds two kites and a dart, and a large dart one kite and one dart, so M = [[2, 1], [1, 1]]. Its Perron root is (3 + sqrt 5)/2 = 2.618..., the square of the golden ratio tau = 1.618..., so the inflation factor is tau and the kites outnumber the darts by tau to 1 in any large patch. A tiling that repeats holds a whole number of kites and darts in each period, so their ratio would be a fraction, and tau is not one: these tilings never repeat.

The Sierpinski carpet is a substitution of two tiles, a black square and a white one, both cut into a 3 by 3 board. A black square becomes eight black squares round a white one, and a white square becomes nine white ones, so M = [[8, 0], [1, 9]] with the black row first. Its Perron root is 9, the area factor of the inflation by 3, as it must be. But the black tiles feed only themselves eight at a time, so the black part of a level-n supertile is 8^n squares of side 3^-n, and the black set that survives has fractal dimension log 8 / log 3. The white tiles only fill holes. This is the idea of a graph-directed construction: a few sets, each made of scaled copies of the sets, and the dimension of what is kept read off the spectral radius of the part of the matrix that feeds itself, log rho / log lambda. The matrix is a transfer matrix on the kinds of tile, and each small tile inside a supertile of level n is the end of a walk of n steps through it.

The square grid is a substitution too, one square cut into four, and the Kronecker product is the two-tile version: a filled cell becomes a copy of the picture and an empty cell an empty block. A picture with f filled cells out of b^2 has M = [[f, 0], [b^2 - f, b^2]], the carpet being f = 8, b = 3.

A substitution says how to grow a patch from the top down. A tiling can also be held together from the bottom up, by matching rules that say only which tiles may touch, as Wang tiles do with coloured edges, or as the kites and darts do with marks on their corners. The two views meet in a theorem of Mozes: for substitutions in the plane that replace each square by a rectangular block of squares, under a mild condition, there is a finite set of Wang tiles whose tilings, once the extra colours are forgotten, are exactly the substitution tilings. Goodman-Strauss 1998 proves the same for substitution tilings in every dimension above one, with decorated tiles and a mild condition on their edges. So every substitution whose tilings never repeat yields a finite set of tiles that can tile the plane only without repeating.

In the tree

The core grows every design by the Kronecker product, which is a substitution on two square tiles, filled and empty, and the sponge demo draws it level by level. Spectra cuts the parity solid along a diagonal plane and finds a graph-directed set on two prototiles, a hexagon and a triangle, whose dimension is read off the top root of a 2 by 2 matrix in exactly the way above.