In the early 80's, a different perspective on self-similar tilings was
discovered by de Bruijn [dB81, dB90]. The basic idea
was to look at the grid 
inside 
for large dimensions
n from different angles. For example, in two dimensions, 
consists of the vertices of the tiling by the unit square; in three
dimensions, 
corresponds to the tiling by unit cubes. Inside
, we choose any subspace E of some smaller dimension d. We
want to form a ``wrinkly'' version of E made up of faces of the grid
in the following way. Suppose a unit n-cube C were centered
on a point of E. Then the number d is defined as the distance of
the furthest point of C from E (see this figure). Let R be the region of all points in
which are at most d away from E. Inside , we have vertices,
edges, faces, etc., of the grid lying entirely inside. This
network forms a wrinkled version F of E.
Figure 31: Definition of region R around E: E is a line inside 
For any point 
, there is an orthogonal projection
which is obtained by taking the point on E which is
closest to 
. Orthogonal projection is a linear map, i.e.
. If we now apply this
projection to F, keeping track of vertices, edges, faces, etc., we
obtain a tiling of E. Amazingly, certain choices of the subspace E
produce self-similar non-periodic tilings, including even the Penrose
tilings.
There is an amazing program that implements this procedure available at the Geometry Center in Minnesota. To access it on the Web, go to the site below
We will return to Quasitiler shortly, but first we should attend to a careful analysis of the simplest case.
Suppose that E is the line y= c x for some given constant slope
c, inside . A unit direction vector is 
. The orthogonal projection of into
E is the ``shadow'' or component of inside E. This is given by
the dot product:
Each vertex in the tiling inside E is an image of a vertex in
under this map P. Each segment of the tiling is the image of
an edge in . Any edge in is a translation of either a
unit horizontal segment or a unit vertical segment. This proves that
there are only two possible tile lengths: the shadows a and b of a
horizontal and vertical segments, respectively. They are found by
computing the dot products of 
with (1,0) and (0,1)
respectively:
We see c=b/a, and that a and b are just the components of the
unit vector . Projecting into the line orthogonal to E
essentially just reverses the components; therefore, the distance d
satisfies 2d= a+b (see the previous picture).
A unit vector orthogonal to is
So the vertices in out tiling come from 
satisfying
This simplifies to the inequality
or
For a given m, the solutions n fall into an interval of width
1+c. To make matters simpler, we shall assume c>1. If not, we can
always exchange the x- and y-axes to make this so. Let 
be
the smallest integer solution and 
the largest. Then we have the
inequalities:
Comparing the lengths of the intervals, we obtain the inequalities
This can be summarized as
Here we have to introduce the integer part 
,
discarding the fractional part of 1+c. Our inequality implies
that
Moreover, the last case happens only if c is an integer. If c is rational, say p/q, then all the lattice points (nq,np) for all integers n occur on the line E itself. An example is shown in this figure. Thus, our tiling of E is periodic. Let's assume now that c is irrational.
Figure 32: Periodic staircase for rational slope 5/3.
The region R is bounded by dotted lines.
We set 
. Then we have just shown that in the
zigzag path we are trying to trace out there are always L or L+1
vertical upward steps after each step horizontally to the right. It
turns out that these tilings for irrational c are always
recurrent (this is equivalent to a theorem about approximation
of irrational numbers by rationals known as Kronecker's
Theorem). However, for certain choices of c, we shall see that
the tiling is actually self-similar with a unique deflation. The
reason is that there is a linear transformation 
with a few convenient properties:
to points in . (The matrix
of T has integral entries.)
As an example we will consider the ``golden'' slope
, shown in this figure. The relevant transformation is
with matrix 
. Suppose 
is an eigenvector
with eigenvalue 
. Then 
implies that
Eliminating , we obtain 
. The roots of this equation
are 
and 
. So T leaves invariant the line E with
direction vector 
and
the line which is orthogonal to E with direction vector
. Since the eigenvalue
for 
is greater than 1, T expands vectors along E by that
factor, while it contracts vectors parallel to 
by the factor
, which has absolute value less than 1.
Figure 33: Self-similar staircase for golden mean slope.
This proves all the properties we claimed of T. Moreover, we see that an a-tile, which is the shadow of (1,0), expands under T to a b-tile, which is the shadow of (0,1). Similarly, a b-tile expands to the shadow of T(0,1)=(1,1) which is a union of a b-tile and an a-tile. Thus, the tiling of E by a's and b's corresponds exactly to our beloved Fibonacci L-system.
To obtain self-similar tilings of the plane, we can try to find
projections of higher-dimensional with the same expanding and
contracting properties. For , there are three types of edges in
the tiling corresponding to shadows of (1,0,0), (0,1,0) and
(0,0,1). There are also three types of tiles corresponding to the
faces parallel to the xy-plane, the yz-plane, and the xz-plane.
The shadow of a square on a plane is always a parallelogram because
opposite sides have the same length shadow. Thus, the shapes of the
tiles are determined by the shadows of the standard unit vectors into
our plane. The second control panel of
Quasitiler
shows the picture of these shadows in the plane E and the shapes of
the three basic tiles (all parallelograms). The third control is the
offset of the plane E from the origin. In 
, this is just a
single number determining the distance from the origin of the plane.
For an example, we will select the plane cutting across all three axes
given by the equation x+y+z=1. This plane has all three standard
basis vectors lying on it. Its distance from the origin is 
.
Click below to go to Quasitiler with this plane selected. When you press
``send changes,'' you'll see an image well-known to fans of the classic
video game Qubert.
To find a self-similar tiling, we need a choice of plane E that has
associated to it a linear transformation T that is expanding
along the plane (i.e. it is a similarity with scale factor greater
than 1) and it is contracting in directions perpendicular to the
plane. Finally, the matrix of T must have all integer entries.
Finding such transformations T is a delicate problem in number
theory. If you reset the values in Quasitiler, you will at last see
the results of the transformation and plane discovered by de Bruijn
that produces the Penrose Tilings by skinny and fat rhombi. The
projection is from the five-dimensional lattice 
. A PostScript
file that produces versions of these tiles suitable for copying and
cutting out can be obtained here.
rhombi.ps
These tiles have been marked with arc patterns which are used to
enforce the ``matching rules'' of the tiling. White arcs can only lay
against white arcs, and black arcs against only black. It is amusing
to try to lay the tiles down systematically, obeying the matching
rules. It is common to discover that a mistake was made that caused a
gap to appear that cannot be tiled. The matching rules do not prevent
these contradictions from occurring. That's the difference between a
set of matching rules and an as yet unknown recipe for ``local
growth.'' If a tiling of is successfully produced by following
the matching rules, it is guaranteed that the tiling will be
nonperiodic. For this reason, tilings by the rhombus prototiles with
the matching rules are called aperiodic.
There are similar tilings of (discovered by Ammann) by two
different golden rhombohedra each face of which is a copy of
the fat rhombus. De Bruijn showed that these tilings also arise by
projections from the six-dimensional lattice 
onto a certain
three-dimensional subspace of 
. Below we give links to PostScript
versions of the two rhombohedra:
The details of this projection are fascinating, but at this time in our course we must take what knowledge we have gained about self-similarity arising from linear maps which are expanding in some directions and contracting in orthogonal directions and move on to new territory.