This page is still under construction.
You will find a text only version of the paper below.
Check back again for the figures.
A Difficult Job in the Tiling Industry
Aimee Johnson
Department of Mathematics
Swarthmore College
Kathleen Madden
Department of Mathematics and Computer Science
Drew University
Suppose that you are hired to tile a huge floor, so huge, in fact, that
it goes on forever in every direction. The tiles you are to use are all
equal sized squares, with various colored edges. Only a finite number of
colored-edged tile types are available, but you may use as many tiles of
each type as you want. So far, the task seems long, but not complicated.
However, you then discover that your employer has two additional rules
that you must follow: 1) When placing two tiles next to each other, edge
colors must match. 2) You may not rotate your tiles. For example, you cannot
place a tile on its side or upside down. And of course, you must leave
no gaps.
You might become concerned that these additional
requirements may have made the task impossible; certainly you can envision
a situation where the tile types available cannot tile an infinite floor.
For instance, suppose the set of tiles types available are illustrated
below:
Figure 1
In this case, you would never be able to place one tile
on top of another without placing red next to yellow, violating Rule 1.
(Remember, Rule 2 does not allow you to turn the tiles upside down.)
Question: Can you look at the tile types available and determine,
before you accept the tiling job, whether the task is possible or not?
If it is possible, we will say that you can ``tile
the plane".
It is not always so easy to decide whether a set
of tile types will tile the plane. If you are hired to tile an infinite
floor with the four tile types shown below, should you accept the job?
(In Figure 2, numbers represent colors.)
Figure 2
In attempting to answer this question, you might begin
by trying to tile 2×2 squares. If you are successful in doing this
you might tile 3×3 squares and so on. Of course, if you find a size
square that you are unable to complete, you can conclude that it will be
impossible to use these tile types to tile the plane. (What size of square
are you unable to complete for the previous example?) But this process
might never end; even if you are able to tile larger and larger squares
you cannot conclude that the tile types can be used to tile the plane.
After all, even if you can tile a square with sides consisting of a million
tiles, it might be the square with sides consisting of a million and one
tiles that is the first size that you are unable to complete.
This issue was studied by Hao Wang [7] in 1961.
Wang speculated that this process would eventually end because either you
would find a size square that you could not complete or you would find
a ``periodic square". This idea is known as Wang's Conjecture:
Wang's Conjecture: Any set of tiles which can be used to tile
the plane, can be used to tile the plane with periodic squares.
An n×n square of tiles is periodic if
its top row of tiles is the same as its bottom row of tiles and if its
left column of tiles is the same as its right column of tiles. If you can
construct such a periodic square with your tile types, you know you can
tile the plane; periodic squares can be stacked end to end vertically and
horizontally with the matching edges of each square overlapping.
A tiling of the plane with periodic squares is said
to be a
periodic tiling. You can tell that a tiling is periodic
if there are least two places where you can stand from which the resulting
floor pattern looks exactly the same. (In fact there are many places you
can stand and see the same pattern and you can move from one spot to another
by a fixed translation.)
Below is a portion of a periodic tiling. (Note in
this simple example, the edges of the two tile types can meet all other
edges) Can you see the periodic squares? What translations move you between
spots where the pattern looks the same?
Figure 3
Wang conjectured that any set of tile types which could
be used to tile the plane could be used to tile a periodic square. This
idea seems reasonable because Wang's Conjecture is true in one dimension.
That is, suppose that instead of tiling a two dimensional floor you are
tiling a one dimensional strip by laying the tiles end to end. If this
can be done, since there are only finitely many tile types, you must use
at least one tile type twice. But this means you have a block of tiles,
beginning and ending with the same tile type, which you can use over and
over to yield a periodic tiling of the strip. For instance, suppose the
set of tile types is shown in figure 4. Then we can use the block in figure
5 to create a periodic tiling of the infinite strip.
Figure 4 Figure 5
If Wang's Conjecture is true in two dimensions as well,
it gives you a general method for determining if a given set of tile types
will tile the plane. You simply construct all tilings of 2×2 squares
and then all tilings of 3×3 squares and so on. If the tiles can not
be used to tile the plane, eventually you will find a square that you can
not tile. If the tiles can be used to tile the plane, Wang's Conjecture
says eventually you will find a periodic square. Either way, your method
will terminate and allow you to decide whether your tile types can be used
to tile the plane.
Wang's Conjecture remained an open question for
several years but, unfortunately for your tiling business, was shown to
be false in the thesis work of one of Wang's students, Robert Berger [1].
Berger constructed an example of a set of tile types which could be used
to tile the plane but for which any tiling constructed using these tiles
was not periodic. Berger's original example involved a set of over twenty
thousand tile types!
So the answer to the original question is ``no";
there is no general method for you to use to determine if a certain finite
set of tile types can be used to tile the plane. We recommend that you
make sure you are paid for your tiling jobs in advance!
Berger's example was published in 1966 and in 1971
Raphael Robinson [5] found a simpler example involving 28 tile types. Like
Berger's tiles, Robinson's tiles can be used to tile the plane but no such
tiling will be periodic, thus proving that Wang's Conjecture is false.
We will discuss this example next. In the final section we will consider
other familiar tilings, such as the Penrose tilings and the pinwheel tilings,
and their connection with Wang's Conjecture.
Robinson's Example
Before introducing Robinson's example [5], we mention a technique that
is quite common in the study of tiles and tilings. We have described tiles
as squares with colored edges; these colored edges give us ``matching rules".
We could equivalently use other types of markings to give us the desired
matching rules; for example, we might use arrows that must match head to
tail. The tiles in Figure 1 could then be replaced with the tiles shown
below:
Figure 6
Notice that the arrows allow the same horizontal matching,
but because arrow heads must meet arrow tails there are no vertical matchings.
The 28 tile types in Robinson's example are illustrated
below:
Figure 7
The four tiles with two arrows crossing each other (the
far left tiles above) are called crosses. The remaining tiles are called
arms. In addition to arrow heads meeting arrow tails, we will require the
following: Rule A: crosses must appear in every other position in every
other row as illustrated below (Figure 8). It is important to note that
crosses may appear elsewhere as well. Rule A is not technically a matching
rule, but we could increase the number of tile types used to 32 and include
additional markings on these tiles to obtain essentially this result. This
is in fact what Robinson does in [5]. (He also points out that if we wanted
to use only tiles with colored edges we could do so with a set of 56 tile
types.)
Figure 8
In this section we will discuss how this example is
able to disprove Wang's conjecture; that is, we will show that 1) these
tile types can be used to construct a tiling of the plane and 2) any tiling
of the plane constructed using these tiles is not periodic.
Let's think about the consequences of the matching
rule requiring arrow heads to meet arrow tails. First of all, a cross can
not sit next to (vertically or horizontally) another cross since that would
force arrow heads to meet arrow heads. Next, consider any two crosses with
a sequence of arms in between them; they must either face each other (Figure
9) or be back to back (Figure 10). When they are back to back, the second
cross may be a mirror image of the first or it may be inverted. These three
scenario's are the only possibilities: any other arrangement of the crosses
yields a configuration with a different number or different locations of
arrow heads on the sides of the crosses nearest to one another. But then
these cannot be connected by a sequence of arms alone; the number (and
location) of arrow heads or arrow tails on opposite sides of any arm are
always the same. For example, consider the two crosses below (Figure 11)
and try to fill in the middle tile with an arm. It can't be done!
Figure 9
Figure 10
Figure 11
A similar argument holds for crosses appearing vertically
with a sequence of arms in between them.
In particular, the crosses appearing in alternate
positions in alternate rows must either face each other or be back to back.
Thus, if we start with one of these crosses, we may assume that it is facing
another cross two units to its left or right. Let's consider a 3×3
square with these two crosses in the corners of the bottom row. We know
that we have crosses in the other corners of the 3×3 square (by Rule
A) and that these crosses must face the crosses in the bottom row. Thus
the 3×3 square looks like:
Figure 12
We also know that positions a-d must be arms (crosses
can't sit next to other crosses). We see there are three choices for the
arm in position a, tiles 5, 6 and 11. We note that all these choices have
their arrows pointing away from the center of the 3×3 square. Similarly
there are three choices for the arms that go in each of the positions b-d
and all these arms also have their arrows facing away from the center of
the 3×3 square. That means that no matter how we choose the various
arms for tiles a-d, the tile in position e will have arrow heads on all
four sides, so it will have to be a cross.
Some specific examples of possible 3×3 squares
are illustrated below:
Figure 13
We'll say that a 3×3 square faces in the direction
of its center cross; for example, the first 3×3 square in Figure
11 faces up and to the left based on the directions of the double arrows
of its center cross.
We can extend any 3×3 square in the direction
it faces; so we can extend the first 3×3 square in Figure 11 to a
7×7 square with itself in the lower right corner. We first note that
because all the exterior edges of the 3×3 square have arrow heads
and because crosses cannot meet edges with arrow heads, the top and left
sides of the 3×3 square must meet arms. Secondly, the positions of
the crosses in the 7×7 square must be as shown in Figure 14 (Rule
A). Then, because crosses cannot sit next to crosses, we have arms between
all these crosses.
Figure 14 Figure 15
In fact the crosses will be oriented as in Figure 15.
This is not obvious but if we play with our tiles a bit it becomes clear:
there are five choices for the arm in Figure 14 labeled A, tiles 5, 6,
8, 11, or 21. All of these have arrow tails on their top edge. Since arrow
heads must meet arrow tails, this forces the arm in the position labeled
B to have its arrow head(s) pointing away from the center of the 7×7
square. Similarly, by considering the choices for arm f, we see arm e also
points away from the center of the 7×7 square. But this means that
the center tile of the 7×7 square must have arrow heads on at least
two sides so it must be a cross.
The cross labeled # 1 will be back to back with
the cross in the upper left corner of the original 3×3 square. It
will either be inverted or a mirror image. If it is inverted then we have
the following in the center of our 7×7 square:
Figure 16
Try filling in the arms and the central cross in Figure
16. It can't be done. Thus, the cross labeled # 1 must be the mirror image
of the cross in the upper left corner of the original 3×3 square.
You can make a similar argument for the cross labeled # 2. Thus the crosses
labeled # 1 and # 2 are forced to appear as in Figure 15 and these two
crosses force the remaining crosses in Figure 14 to be oriented as in Figure
15.
Once we have Figure 15, we see that in each corner
we will be forced to have a 3×3 square with a central cross determined
by the central cross of our initial 3×3 square. (The central cross
of the lower left 3×3 square must face the central cross of the initial
3×3 square. Then the central cross of the upper left 3×3 square
must face the central cross of the lower left 3×3 square and so on.)
Finally, because all the 3×3 sub-squares have
arrow heads pointing away from their center cross, we see that the horizontal
and vertical rows of tiles radiating away from the center cross of the
7×7 square must also have arrows pointing away from the center cross.
A sample 7×7 square is illustrated below:
Figure 17
In a similar way, a 7×7 square can be extended
in the direction of its central cross to a 15×15 square. This 15×15
square will have a central cross with a row and column of arms pointing
away from it. The four corners of the 15×15 square will consist of
7×7 squares whose central crosses face each other. The 15×15
square can then be extended to a 31×31 square with a central cross
and with the central crosses of the 15×15 squares in each of its
four corners facing each other, and so on.
Because (2n-1) ×(2n-1)
squares can be tiled for all values of n, it follows that the plane can
be tiled with this set of tiles! However, none of the tilings can be periodic.
To see this we need to show that no matter how we translate a tiling of
the plane formed using these tiles, some tiles will fail to match up. (In
other words, you can't stand at two different spots on your infinite floor
and have the pattern look exactly the same.) So imagine you have tiled
the floor using these tiles and you are now standing on one of the crosses
found in alternate positions in alternate rows. As described before, this
cross must be part of a 3×3 square with a pattern as in Figure 13,
and this 3×3 square must lie in some 7×7 square as in Figure
17, and so on. Look at the 3×3 square you are standing on and memorize
its pattern. Now, move 4 units horizontally and/or vertically, staying
within the 7×7 square containing the 3×3 square. You are in
a new 3×3 square, so the pattern will look similar. However, since
the center cross of the new 3×3 square will face the center cross
of your original 3×3 square, these 3×3 squares cannot look
exactly the same! Thus the tiling is not invariant under a translation
by 22. It is also not invariant under a translation by 3 or
2; if you move horizontally or vertically by these amounts, the pattern
does not even look similar to your original 3×3 square.
Now return to the cross you started on and memorize
the pattern of the 7×7 square you are in. Move horizontally or vertically
by 8, staying in the 15×15 square which contains your 7×7 square.
Again you are in a 7×7 square, so the pattern looks similar to the
one you memorized. But, again, the center cross of the new 7×7 square
will face the center cross of the original 7×7 square, so these 7×7
squares cannot look exactly the same. So the tiling is not invariant under
a translation by 23. It is also not invariant under a translation
by 5, 6, or 7 because under these translations, the pattern is not even
similar to your original 7×7 square.
Similarly you can argue that the tiling is not invariant
under translation by any value 2n or any value m ¹
2n. This shows that the tilings as described in this section
are not periodic.
Other Facts And Examples
In disproving Wang's Conjecture, we constructed an example of a set
of tiles which could be used to tile the plane but for which no such tiling
is invariant under a translation. In fact, no tiling constructed using
this set of tiles is invariant under a rotation [5].
It is interesting to note that although no tiling
constructed with this set of tiles is periodic, they are ``almost periodic";
that is, when choosing a period large enough, an arbitrarily large percentage
of the tiles will repeat. For example, the crosses making up the corners
of the 3×3 squares will repeat horizontally and vertically with period
4. These crosses make up one quarter of the total tiles; to see this, divide
any 2n×2n block into 2×2 blocks. Each
will contain exactly one such cross. So one quarter of the tiles repeat
with period 4.
Similarly, we can divide any 2n×2n
block into 4×4 blocks, each containing exactly one 3×3 square.
The 3×3 squares are determined by their central cross and thus repeat
with period 8. So 9/16th of the tiles repeat with period 8.
In general, ([(2n -1)/( 2n)])2 of the
tiles repeat with period 2n+1.
Another famous tiling of the plane is the Penrose
tiling [4],[2]. First discovered by Roger Penrose in 1973, a modified version
done in 1974 uses only two tile shapes, commonly referred to as ``kites"
and ``darts", and finitely many different rotations of these shapes. A
tiling must satisfy the matching rule that colored vertices, indicated
below by shadings, must match (Figure 18).
Figure 18 Figure 19
The Penrose tilings (Figure 19) are not periodic under
any translation, however they can be periodic under rotations by a fifth
root of unity. The Penrose tilings are almost periodic in the sense that
the pattern seen in any arbitrarily large block will repeat within a bounded
translation. The Penrose tiles are actually patented and are useful in
understanding the geometric properties of quasicrystals [6].
In the Pinwheel tilings (Figure 20) there is a single
tile shape, a right triangle with sides 1-2-Ö5.
This example differs from our previous ones in that it involves infinitely
many different tiles because in each tiling the triangle occurs in infinitely
many different orientations [3]. The Pinwheel tilings are nonperiodic under
translations and rotations. They are almost periodic in the sense described
above.
Figure 20
There are many other interesting tiling examples and
we refer the reader to [2] for further exploration.
References
[1] Berger, R., ``The Undecidability of the Domino Problem", Mem. Amer.
Soc. 66, (1966).
[2] Grunbaum, B., and G. C. Shephard, ``Tilings and Patterns", W. H.
Freeman and Company, (1987).
[3] Radin, C., ``The Pinwheel Tilings of the Plane", Annals of Mathematics,
(to appear).
[4] Robinson, E. A., ``The Dynamical Properties of Penrose Tilings",
(preprint).
[5] Robinson, R. M., ``Undecidability and Nonperiodicity for Tilings
of the Plane", Invent. Math. 12 (1971), 177-209.
[6] Senechal, M., ``Crystalline Symmetries", Adam Hilger (1990).
[7] Wang, H.,``Proving Theorems By Pattern Recognition-II", Bell System
Tech. J. 40, 1-41 (1961).