A periodic tiling is one that is preserved by a nontrivial
translation 
(i.e. 
). A two-dimensional tiling
may have one or two independent translational symmetries. For
instance, the hexagonal tiling in this figure is invariant under both
assuming that the side of the hexagon is length 1. The square and equilateral tilings are also invariant under two independent translations.
The triomino and sphinx tilings have no translational symmetries. This is because there is a unique way to group the tiles into groups of 4 which form larger copies of the prototile. This may be formulated precisely as follows. Suppose the self-similar tiling is
where we have listed the individual tiles 
in some order.
Suppose the self-similarity of the tiling is 
. A
group of tiles is a finite set 
, ..., 
such
that the union
is congruent to 
for some j. The property we want is that
each tile belongs to a unique group G. This is not true for
the square or equilateral triangle tilings (see this
figure), because each tile can belong to several
choices of groups. In fact, each tile belongs to four different groups,
in those cases.
A bit of examination (and a larger bit of proof) should convince the reader that each triomino fits into exactly one group of four triominoes that forms a larger triomino. The same is true for the sphinx tiling. We say these tilings have a unique deflation; a large portion of the triomino tiling with the grouping marked is portrayed in this picture.
Figure 27: Piece of triomino tiling with groups marked in thick lines
The relation to the existence of translational symmetries is described by:
THEOREM: ([GS87], p. 524) A self-similar tiling with a unique deflation has no translational symmetries.
The proof is an interesting example of the interplay between dynamics
and symmetry (or lack thereof). Suppose there is a translation
such that for every tile we have 
for some other j. Suppose 
is the unique group of tiles
containing which is congruent to 
for some tile 
with U being the self-similarity of the tiling. Then T takes each
tile in to another tile. Thus, 
is a group of tiles
containing 
which is still congruent to . By uniqueness,
is the only such group of tiles. It follows that T
is also a symmetry of the deflated tiling by groups G. The deflated
tiling is similar to the original tiling, and so it also has a unique
deflation. Thus, we can keep deflating the tiling (which enlarges the
tiles) and T will continue to be a symmetry of the ever larger
tilings. Eventually, all the tiles will be larger than the
translation length 
, and so the translation by T of a tile
will have to overlap with the original tile. This contradiction shows
that no such translational symmetry can exist.
The non-periodicity is forced upon the tiling by the way the tiles fit together to form larger versions. This has important implications for physical processes. Crystals are formed by the positioning of atoms at the vertices of some three-dimensional tilings. Until 1984, it was postulated that the underlying tiling of a crystal had to have three independent translational symmetries. However, in the late 80's new kinds of crystal-like solids were discovered that had no translational symmetries. The mechanism by which these new solids, called quasicrystals, form has not yet been explained. However, it may be true that the building blocks may have unusual shapes like the sphinx or triomino. Grouping may in fact create arrangements of minimal energy; the need for the blocks to form groups may explain why the non-periodic arrangements occur. For more information on quasicrystals, see [Sen95].
Periodic tilings repeat themselves in the sense that any arrangement of tiles that is found in one position in the tiling will recur infinitely often throughout the tiling. Self-similar tilings without translational symmetry have the same property, which is called recurrence. A patch of tiles is simply an arrangement of tiles that occurs somewhere in the tiling which is connected and has no ``holes.'' For instance, The figure below shows a patch of seven triominoes.
Figure 28: A patch of triominoes
A patch has diameter 
if there is a circular disk of radius
r enclosing the patch. For instance, in the above figure, the patch
has diameter 
, given that the short side of a triomino has
length 1. The property of recurrence may now be stated.
RECURRENCE: A tiling is recurrent if for any r>0 there is an R>0 such that a copy of any patch in the tiling of diameterSo the given patch occurs infinitely often throughout the tiling, and fairly frequently at that. Recurrent non-periodic tilings have a builtin sense of disorientation: just knowing the arrangement of tiles around a given position is not enough information to be able to decide where that position is in the whole tiling.
This notion of recurrence is exactly analogous to the notion of a
recurrent symbolic dynamical system which we discussed in connection
with the Thue-Morse system (see this section). Through the deflation process (repeated), the
given patch of tiles must eventually be contained in the union of at
most four larger adjacent tiles. Suppose it takes N repeated
deflations to accomplish this. Up to translation, there are only finitely
many possible arrangements of a collection of at most four touching
tiles. Starting from one triomino, suppose it takes M generations
of inflation to obtain a patch that contains all the possible
configurations of at most four adjacent tiles. Choose
so that any disk of radius R must contain a copy
of a super-tile of the M+N-th generation. It follows that any disk
of radius greater than R must contain a copy of the original
patch.
The triomino and sphinx tilings are a bit of a cheat since they both have similarity factors 2 and since they have an underlying image of the square and equilateral triangle tilings, respectively. (Just draw in all the edges that decompose each triomino into three squares and each sphinx into 6 equilateral triangles.) We might find more interesting tilings by answering the following questions:
To start investigating these questions, we will look at a
one-dimensional example. Tiles in 
are simply line segments.
With only one prototile, the tiling has to be periodic; things are
more involved when there are two or more prototiles. Let's suppose
there are precisely two line segments of length a and b, with
a<b. We will propose an inflation process for the prototiles. Under
some scaling factor c, a tile of length a becomes a tile of length
b. Under the same scaling, a tile of length b splits into a tile
of length b followed by a tile of length a. These conditions are
equivalent to two equations:
Substituting for b in the second, we obtain
Cancelling a on both sides, we have
the quadratic equation whose roots are the golden mean and its negative reciprocal
Since the similarity constant must be greater than 1, we see that
this inflation process will work if 
. Starting
with a single a tile, repeating the inflation produces a tiling of a
half-line. The generations of the inflation process are shown in
this figure. This is the
tiling version of the Fibonacci L-system described in this
section. To get a complete tiling of
, simply flip a copy of this half-line over and append it to
the original half-line. The resulting tiling is self-similar with
scale factor 
.
This tiling also has the property of a unique deflation. The tiling
consists of individual a's separated by one or two b's. To group
the tiles into versions which are scaled by a factor of
, we must group each a with the b to the
left (in the right half-line; reverse this pattern in the left
half-line) and that will leave some individual b tiles. There is no
choice in this grouping. So our theorem about self-similar tilings
with a unique deflation implies that this tiling is non-periodic.
This example suggest how to create many different self-similar tilings
of . In fact, any L-system gives such a tiling. Wonderful
new phenomena of this type happen in higher dimensions. Around 1974, to
amuse a sick friend, Roger
Penrose, a
mathematician at Oxford with a passion for recreational
mathematics,
began playing around with subdividing pentagons. (Penrose's first
article on the subject was Pentaplexity! [Pen79].)
A smaller pentagon may be placed in each corner of a pentagon with
sizes chosen so that the smaller pentagons just touch to make a sixth
pentagon in the middle. The ratio of the side of the original
pentagon to that of the six smaller pentagons is
This construction may be repeated on the smaller pentagons. The result of three generations of subdividing is shown in this figure.
Figure 30: Subdividing Pentagons
Penrose noticed that the gaps formed were of the same general type:
polygons with thin spikes of angle 
. He discovered a method
of subdividing the gaps into smaller pentagons and similar spiked
shapes, so that in general only six different shapes were required.
Thus, through the process of inflation, Penrose arrived at a
non-periodic tiling of the plane by these six shapes with a similarity
constant of the square of the golden mean.
The whole procedure has been codified into L-systems in many different ways. The original Pentaplexity! subdivision is produced in FRACTINT by selecting the L-system Stars&Penta1 (in the file penrose.l. Variations are Stars&Penta2 and Stars&PentaColor. Having found a set of six prototiles that tile non-periodically, Penrose attempted to decrease the number, and discovered that the tiling by the six shapes could be dissected and reassembled into a tiling by two simple kites, which John Conway christened ``kites'' and ``darts.'' This dissection is exhibited in color in Stars&PentaColor. An alternative scheme was discovered which led to a pair of ``golden'' rhombi as prototiles, one ``fat'' and the other ``skinny.'' Many L-systems showing these variations can be found in FRACTINT.
Convex quadrilaterals may always be used to tile 
periodically.
What is unusual about the Penrose tiles (kites-darts or fat-skinny) is
that they may be marked in such a way that they may only tile
non-periodically. The marking is accomplished in the L-system
Penrose1Forced in tiling.l by coloring the sides of
the skinny and fat rhombi. It is amazing that these beautiful tilings
were discovered by a dynamical systems construction. No one has yet
discovered a single tile with or without a marking that tiles only
non-periodically.
