THE CONSTRUCTION OF SELF-SIMILAR TILINGS

RICHARD KENYON

Abstract. We give a construction of a self-similar tiling of the plane with any prescribed expansion coefficient λ ∈ ℂ (satisfying the necessary algebraic condition of being a complex Perron number).

For any integer m > 1 we show that there exists a self-similar tiling with 2π/mrotational symmetry group and expansion λ if and only if either λ or λe^{2πi/m} is a complex Perron number for which e^{2πi/m} is in ℚ[λ], respectively Q[λe^{2πi/m}].

1. Introduction

By a tile we will mean a compact subset of ℝ^{2} which is the closure of its interior. A tiling of the plane is a collection of tiles T = {T_{i}}_{i∈I}, whose union is ℝ^{2} and which have pairwise disjoint interiors.

In [18], Thurston introduced the notion of self-similar tiling. This definition was motivated from several sources: most notably, in tilings arising from Markov partitions for hyperbolic toral automorphisms, one-dimensional tilings arising from substitutions, and also the Penrose tilings, which have a simple subdivision rule to create new tilings out of old.

A self-similar tiling is a tiling T = {T_{i}}_{i∈I} of the plane which has the following properties:

(1) There is an equivalence relation ∼ on tiles, with a finite number of equivalence classes, such that T_{i} ∼ T_{j} implies T_{j} is a translate of T_{i}.

(2) There is a homothety φ: ℂ → ℂ, φ(z) = λz, such that the image of a tile is equal to a union of tiles of T ,

(3) If T_{i} ∼ T_{j}, and T_{i} + c = T_{j}, then for each tile T_{k} ⊂ φ(T_{i}), φ(c) + T_{k} is a tile of T equivalent to T_{k}.

(4) The tiling is quasiperiodic (see definition below). An example is shown in Figure 1 (more information about this example is given in section 6).

Let us make a few remarks regarding this definition.

1. The third condition simply states that two equivalent tiles “subdivide” in the same way.

2. Here by quasiperiodic we mean, any “arrangement” (finite collection of tiles, up to translation) of tiles in the tiling reoccurs at a bounded distance from any point in the tiling. More formally, for any r > 0 there is an R > 0 such that for all x, y ∈ C a translate of the arrangement of tiles in B_{r}(x) occurs as a subset of in B_{R}(y). This

Research at MSRI is supported in part by NSF grant DMS-9022140.

Figure 1. Part of a self-similar tiling (see section 6).

property is almost the same as the local isomorphism property of Radin and Wolff [15], and is identical if one assumes in their case that there are a finite number of local arrangements (which in our case is a consequence of the definition). This condition is really a compactness condition: indeed, this condition is equivalent to the condition that the orbit closure Y of the tiling (under the action of ℝ^{2} by translations) is minimal: every ℝ^{2}-leaf of Y is dense in Y [15]. Under reasonable assumptions on the subdivision rule for tiles, this condition is easily checkable, see Lemma 4, below.

3. By replacing “translations” in the first and third conditions by some other group of homeomorphisms of ℝ^{2}, e.g. by isometries, one arrives at a more general definition of self-similar tiling. So technically we should refer to our definition as that of a translation-self-similar tiling. However for succinctness (and to agree with Thurston’s terminology) in this paper we shall simply say “self-similar tiling”, with the translations understood. The results as stated below are unknown for isometry-self-similar tilings; for similarity-self-similar tilings, see [11].

Thurston proved that the expansion coefficient λ of a self-similar tiling had to be a special type of algebraic integer, a complex Perron number. He indicated, without proof, that for each complex Perron number there existed a tiling. In this article we give a construction of a self-similar tiling for any complex Perron number.

A complex Perron number is an algebraic integer which is strictly larger in modulus than its Galois conjugates (the other roots of its minimal polynomial), except for \overline{λ}, its complex conjugate.

Theorem 1 (Thurston [18]). The expansion of a self-similar tiling is a complex Perron number.

In section 4 we will prove by construction:

Theorem 2. For each complex Perron number λ there is a self-similar tiling with expansion λ.

The methods we use are very geometric and are inspired by conversations with and ideas of Thurston.

This construction allows an easy corollary, whose proof we give in section 5:

Theorem 3. λ is the expansion of a self-similar tiling invariant under a rotation e^{2πi/n} (n an integer) if and only if either λ ∉ ℝ and λ is a complex Perron number for which e^{2πi/n} ∈ ℚ[λ], or λe^{2πi/n} is a complex Perron number and e^{2πi/n} ∈ ℚ[λe^{2πi/n}].

Note that in the case n = 2 we conclude: any complex Perron number is the expansion for a self-similar tiling invariant under x → −x.

For an example of this theorem, consider the symmetric Penrose tiling, which is invariant under rotation by 2π/5. One possible expansion of this tiling is the degree-4 complex Perron number λ = 1 + e^{2πi/5} and ℚ[λ] = ℚ[e^{πi/5}].

In section 6 we will give a simpler construction for self-similar tilings whose expansion coefficients are of a particular type: those non-real complex Perron numbers λ satisfying an equation of the form

λ^{n} − aλ^{n−1} + bλ + c,

where a, b ≥ 0, c > 1 are integers. This construction has the advantage of being very concrete.

2. Historical remarks

Self-similar tilings appear in several quite different contexts. In fact up to now they have not really had a life of their own, but have rather been studied independently by people working in different fields.

Self-similar tilings did not really exist before the computer age, although some precursors can be found [8]. One could also trace back the roots to the work of Adler and Weiss [1], Bowen [3] and Sinai [16] on the construction of Markov partitions, which can be interpreted as the first general constructions for self-similar tilings.

Most of the first explicit examples of self-similar tilings were curiosities, found in popular books on fractals with fanciful names such as the “Heighway dragon curve” and “Gosper flowsnake”.

The Penrose tilings [6] were another curiosity until some nonperiodic crystals displaying 5-fold “symmetry” were actually discovered in nature; these “quasicrystals” gave life to a new field of crystallography.

The theory of wavelets is another new field which has caused people to become interested in “self-replicating” tilings (self-similar tilings with one tile type), and much work has been done since on this special class of self-similar tilings [2, 9, 17, 12, 20].

Our current construction has its origins in another point of view. Working in the field of symbolic dynamics, Lind [13] gave a characterization of the largest eigenvalues of nonnegative integer matrices, which gives as corollary a characterization of the expansions of self-similar tilings of the line.

Then Thurston [18] in 1989 took a step up from this result, defining self-similar tilings and proving the neat Theorem 1 above. As a thesis student of Thurston, I extended his result to n-dimensional self-affine tilings (in which the expansion is a linear map of ℝ^{n} diagonalizable over ℂ) [10].

Not much later Praggastis [14] gave a more explicit construction of Markov partitions for (certain) hyperbolic toral automorphisms using the theory of self-similar tilings. This work is also very close to that of Vershik [19] who constructs such Markov partitions arithmetically, that is, using radix representations.

Self-similar subdivisions (of various sorts) occur nowadays in the theory of rational maps, Kleinian and hyperbolic groups (via the action on the sphere at infinity or space of geodesics using an automatic structure), wavelets, crystallography (in quasicrystals), symbolic dynamics and number theory (in radix representations), and logic (in Wang tiles, aperiodic tilings, and computability: surprisingly, the only known aperiodic tilings are built from self-similar patterns).

3. Background

3.1. the subdivision rule. The tile types in a self-similar tiling are the distinct equivalence classes of tiles. To a self-similar tiling with n tile types is associated a nonnegative n×n integer matrix M = (m_{ij}), the subdivision matrix, in which m_{ij} is the number of tiles of type j that a tile of type i subdivides into upon scaling by λ. By property 3 this matrix is well-defined.

The Perron (i.e. largest) eigenvalue of this matrix is λ\overline{λ}, whose corresponding eigenvector is the vector of tile areas.

Recall that a nonnegative matrix is called primitive if some power is strictly positive. In the case of a self-similar tiling, the subdivision matrix must be primitive, since every tile, when scaled by λ^{n} for large enough n, must contain a copy of every tile type by quasiperiodicity. Primitivity also implies that the spectral radius λ\overline{λ} is a Perron number, that is, λ\overline{λ} is a real algebraic integer strictly larger than the modulus of any Galois conjugate.

We have the following result (whose proof is an application of the definitions) which we shall use later.

Lemma 4 ([14], see also [11]). A tiling which satisfies the first three hypotheses of a self-similar tiling, has a tile with the origin in its interior and has primitive subdivision matrix, is quasiperiodic, and hence self-similar.

3.2. The Delauney triangulation. We review here the definition of the Delauney triangulation. Given a discrete set of points P in ℝ^{2}, the Delauney triangulation is the triangulation of the convex hull of P, with triangles having vertices in P, with the property that, for any triangle t = (v_{1}, v_{2}, v_{3}), the circumcircle of t contains no point of P. Such a triangulation exists (for example, one can see this by using stereographic projection of the plane to the sphere in ℝ^{3}; the convex hull in ℝ^{3} of the image of P is a polyhedron whose faces are (generically) the triangles in the Delauney triangulation) and is unique unless some four or more points lie on the same empty circle.

Another property that we will use is the local nature of the triangulation: if for some small ϵ there is a point of P within a distance ϵ of any point of B_{1}(x), then the set of triangles with vertex x depend only on those points in B_{3ϵ}(x). (To see this, notice that an empty circle passing through x has diameter at most 2ϵ.)

4. Proof of Theorem 2

4.1. sketch. The idea of the construction is as follows. We define the set T of “archtypes” of the tiles in our eventual tiling to be the set of all triangles with vertices in an appropriate lattice and edges of bounded length. When we multiply a triangle in T by λ^{n} for large enough n, we can subdivide it approximately into triangles in T . (This is where we use the complex-Perron-number property of λ). However we need a way to define the subdivision of triangles so that, if two triangles are adjacent, their subdivisions agree at their common boundary. So rather than just keep track of a triangle we keep track of a triangle and all its immediate neighbors. This gives a new larger set of archtypes X. The subdivisions of elements of X can now be defined so that they agree whenever there is an overlap between them.

One small hitch is to make this subdivision rule primitive. To ensure this we define a special tile T_{0} that occurs in the subdivision of any tile, including itself. Our set of tiles will then be the strongly connected component of the “subdivision graph” which contains T_{0}.

Finally we redraw the boundaries of the elements of X ∪{T_{0}} by a recursive process so that the subdivision is exact, not just approximate.

4.2. The set-up. Let λ be a complex Perron number of degree d. Let q[x] ∈ ℤ[x] be the minimal polynomial for λ; it is monic and of degree d. Furthermore the roots λ_{0}, λ_{1}, …, λ_{d−1} of q(x) satisfy |λ_{i}| < |λ| except for the roots λ and \overline{λ}. The roots of q(x) are called the Galois conjugates of λ. Assume λ_{0} = λ.

Let K = ℚ[λ]. For each i with 0 ≤ i ≤ d − 1 there is an embedding σ_{i}: K → ℂ, sending an element p(λ) (a polynomial in λ with rational coefficients) to p(λ_{i}). If λ_{i} is real the image of this embedding is contained in ℝ.

Let r be the number of real Galois conjugates, and 2c the number of non-real Galois conjugates of λ, so that r + 2c = d.

There is a natural embedding σ: K → ℝ^{r} × ℂ^{c} ≅ ℝ^{d} which is the product of these individual embeddings σ_{i} (taking only one embedding for each complex conjugate pair).

At this point we must distinguish between the case λ real and the case λ is nonreal. If λ is nonreal, let W = ℝ^{d}; let π be the linear projection from W to ℂ such

that ∀x ∈ K, πσ(x) = x. Let m_{λ} be the linear map σ(K) → σ(K) induced by multiplication by λ in K, i.e. m_{λ}(σ(x)) = σ(λx). Then m_{λ} extends to a linear map of ℝ^{d} whose eigenvalues are exactly the λ_{i}, and eigenspaces are given by the coordinate axes/planes. Let A = O denote the ring of algebraic integers in K. The image σ(A) is a discrete lattice in W invariant under m_{λ}.

If λ is real let W = ℝ^{d} × ℝ^{d} and π be the projection π: W → ℝ^{2} satisfying π(σ(x) × σ(y)) = (x, y). Let m_{λ} be the linear map on W induced by multiplication by λ on K. The eigenvalues of m_{λ} are the λ_{i}, each with multiplicity 2. Let A = O×O where O is the ring of algebraic integers in K. The image σ(A) is again discrete lattice in W invariant under m_{λ}.

In either case let V_{λ} ⊂ W be the eigenplane (2-dimensional eigenspace) for m_{λ} corresponding to the eigenvalue λ. Then the map π: W → ℝ^{2} can be thought of as projection along eigenvectors of W onto V_{λ}.

We use the Euclidean metric on both ℝ^{2} and W. If x ∈ ℝ^{2} or x ∈ W let N_{R}(x) denote the neighborhood of radius R around x in ℝ^{2} or W, respectively. Similarly for a set S ⊂ ℝ^{2} or S ⊂ W let N_{R}(S) denote the R-neighborhood of S. For v ∈ K let ∥|v∥| denote the distance from σ(v) to the plane V_{λ}. This is the length of the “vertical” component of σ(v).

For a triangle t ⊂ ℝ^{2} with vertices v_{1}, v_{2}, v_{3} ∈ K, let σ(t) denote the triangle in W with vertices σ(v_{1}), σ(v_{2}), σ(v_{3}).

Lemma 5. Given a triangle t ⊂ ℝ^{2} with vertices v_{1}, v_{2}, v_{3} ∈ A and an ϵ > 0, there is an integer n such that σ(λ^{n}t) is almost parallel to V_{λ}, that is, the projection π is a (1 + ϵ)-biLipschitz mapping from σ(λ^{n}t) to its image λ^{n}t.

Proof. A non-zero vector v ∈ W lying in the plane of σ(t) has a non-zero component in the direction of the plane V_{λ}. Since λ is the strictly largest eigenvalue in modulus of m_{λ}, for n sufficiently large the component in direction V_{λ} of m_{λ}^{n}v dominates all the others, and so m_{λ}^{n}(v) lies almost parallel to V_{λ}. The result follows. □

4.3. The actors. Let T_{0} ⊂ ℝ^{2} be a polygon with vertices in A, having the origin in its interior and sufficiently “round” so that λT_{0} contains T_{0} in its interior. Triangulate the annulus λT_{0} − T_{0} with triangles whose vertices are in A (see Figure 2).

Let M be an integer large enough so that:

(1) M > 2|λ|^{2}∥|v_{1} −v_{2}∥| for any two vertices v_{1}, v_{2} in the triangulation of λT_{0} −T_{0}.

Figure 2. The triangulation of λT_{0}.

(2) M > |λ|^{2}|v_{1} − v_{2}| for any two such vertices.

(3) For any x ∈ W, N_{M/(2|λ|)}(x) contains a point of the discrete lattice σ(A). Let T be the set of triangles t = (v_{1}, v_{2}, v_{3}) with noncollinear vertices v_{1}, v_{2}, v_{3} ∈ A

satisfying ∥|v_{i} − v_{j}∥| < 3M and |v_{i} − v_{j}| < 3M for all i, j ∈ {1, 2, 3}. For any t ∈ T , σ(t) is a triangle with vertices in the discrete lattice σ(A) and edges of bounded length. Thus T is a finite set up to translation, i.e. if we consider (v_{1}, v_{2}, v_{3}) = (v_{1} + a, v_{2} + a, v_{3} + a) for all v_{1}, v_{2}, v_{3}, a ∈ A.

Let X be the set of surroundings of elements of T by elements of T . By definition a surrounding of t ∈ T is a collection X of elements of T , with t ∈ X, which tiles in an edge-to-edge fashion a neighborhood of t and such that every element of X touches t in at least a vertex (see Figure 3.) Note that X is also a finite set up to translation.

Figure 3. A surrounding.

Recall that for t = (v_{1}, v_{2}, v_{3}) ∈ T by σ(t) we mean the triangle in W with vertices (σ(v_{1}), σ(v_{2}), σ(v_{3})). For X ∈ X, by σ(X) we mean the union of the σ(t)’s for each triangle t in X. So σ(X) is a piecewise flat surface in W.

Let θ > 0 be the smallest vertex angle of any triangle in T . Let r_{2} = 2M and r_{1} = r_{2}/sin(θ/2). Then in any homothetically scaled copy of a triangle in T , the r_{2}-neighborhoods of any two edges do not intersect outside of the r_{1}-neighborhoods of the vertices (Figure 4).

Figure 4. Neighborhood of a vertex.

Let n be an integer large enough so that for each t ∈ T :

(1) λ^{n}t is 1/2-flat in the sense of Lemma 5 (the projection π from σ(λ^{n}t) is 3/2biLipschitz).

(2) the inscribed radius of λ^{n}t is at least 2diam(λT_{0}) + 2r_{2}.

4.4. subdividing an element of X. Let X ∈ X be a surrounding of t ∈ T . Each triangle in λ^{n}X is large and flat by our choice of n. The subdivision proceeds in three stages: first we must subdivide a neighborhood of the vertices of λ^{n}t, then a neighborhood of the edges of λ^{n}t, and then λ^{n}t itself. (In the final construction we’ll use n + 2 in place of n; the rules are the same, though.)

4.4.1. near a vertex. Let X ∈ X be a surrounding of t ∈ T . Let v be a vertex of t. Let N = N_{r_{1}}(λ^{n}v) ⊂ λ^{n}X. Let

Y_{v} = {y ∈ A ∩ N : ∥|y − λ^{n}X∥| < M/|λ|}.

Here by ∥|y −λ^{n}X∥| we mean the distance vertically from σ(y) to σ(λ^{n}X). This is the Euclidean distance d(σ(y), z) where z ∈ W is defined by π(z) = y and z ∈ σ(λ^{n}X). Then Y_{v} is a discrete subset of N. (Later on Y_{v} will be the vertices in a triangulation of N in which the triangles are in T .)

4.4.2. near an edge. Let e = e_{ij} = \overline{v_{i}v_{j}} be an edge of t and let

N′ = N_{r_{2}}(λ^{n}e) − (N_{r_{1}}(λ^{n}v_{i}) ∪ N_{r_{1}}(λ^{n}v_{j}))

be the r_{2}-neighborhood of λ^{n}e which is outside the vertex-neighborhoods defined in the previous paragraph. Let

Y_{e} = {y ∈ A ∩ N′ : ∥|y − λ^{n}X∥| < M/|λ|},

where ∥|y − λ^{n}X∥| is as defined above. Again, Y_{e} is a discrete subset of N′.

4.4.3. for a triangle. Once the sets Y_{v}, Y_{e} have been defined as above for each vertex and edge of t, define

Y_{t} = {y ∈ A ∩ λ^{n}t : ∥|y − λ^{n}X∥| < M/|λ|}.

Let

Y = Y_{t} ∪ Y_{v_{1}} ∪ Y_{v_{2}} ∪ Y_{v_{3}} ∪ Y_{e_{12}} ∪ Y_{e_{23}} ∪ Y_{e_{31}};

then Y is a discrete set of points in the r_{2}-neighborhood of λ^{n}t.

Triangulate the set Y using the Delauney triangulation, leaving out triangles whose circumcircle is not completely contained in N_{r_{2}}(λ^{n}t). Each triangle t′ = (w_{1}, w_{2}, w_{3}) in this triangulation satisfies:

|w_{i} − w_{j}| < M/|λ| (1)

since the circumcircle of t′ contains no point of Y, and so must have diameter bounded by M/|λ| by condition (3) on M. Furthermore each triangle satisfies

∥|w_{i} − w_{j}∥| < ∥|w_{i} − λ^{n}X∥| + ∥|λ^{n}X − w_{j}∥| + \frac{1}{2}|w_{i} − w_{j}| < \frac{M}{|λ|}(1 + 1 + \frac{1}{2}) (2)

here using the fact that σ(λ^{n}X) is \frac{1}{2}-flat (condition (1) on n).

Since |λ| > 1, these imply t′ ∈ T . We have defined a subdivision of a neighborhood of t into triangles in T . In addition, for each such triangle t′, we have λt′ ∈ T by (1) and (2).

If two surroundings X_{1}, X_{2} (of t_{1}, t_{2} respectively) overlap, i.e. t_{2} ∈ X_{1} and t_{1} ∈ X_{2}, then their subdivisions agree near where λ^{n}t_{1} intersects λ^{n}t_{2} (by the local nature of the Delauney triangulation), so that X_{1} ∪ X_{2} has a well-defined subdivision.

4.4.4. the central tile. We need to alter slightly this subdivision rule for triangles so as to insert a copy of the region λT_{0} in the subdivision. Let t and X be as before with Y_{v}, Y_{e} defined for each vertex and edge. Put a translate C of λT_{0} in the interior of λ^{n}t so that for any vertex w of C, we have

∥|w − λ^{n}t∥| < M, (3)

and C does not intersect the sets N_{r_{2}}(λ^{n}e) for edges e of t. This can be accomplished by conditions (1) on M and (2) on n: just put C near the center of the inscribed circle of λ^{n}t, so that vertices of C are in A, and so that σ(C) is (vertically) within M of σ(λ^{n}t). Take

Y′ = {y ∈ Y | y ∉ interior(C)}.

As before use the Delauney triangulation of Y′, except near C: the edges of the boundary of C may unfortunately not be edges of Delauney triangles. Take only those Delauney triangles whose circumcircle doesn’t penetrate into C. The remaining untriangulated area is an annulus around C, and for any vertex x of the outer boundary Z of this annulus, the distance to the inner boundary ∂C is at most M/|λ|, since x is on a circle of diameter at most M/|λ| which touches C. In particular x is at distance at most 2M/|λ| from a vertex of ∂C, since the edges of ∂C have length at most M/|λ|^{2} < M/|λ|. So we can triangulate this annulus in the following manner: for each edge c_{1}c_{2} of ∂C, connect c_{1}, c_{2} to their closest common neighbor on Z. Connect the remaining vertices c_{3} on Z to the only place now possible on ∂C which doesn’t cross edges already present. Each such triangle has edge lengths at most 3M/|λ|. By the condition (3) on T , each triangle is in T .

This defines a subdivision of a neighborhood of t into triangles in T and a region C which is tiled by a translate of the original tiling of λT_{0}. Furthermore triangles t near the edges of λ^{n}t satisfy: λt ∈ T . (Figure 5).

Figure 5. Subdividing a triangle.

4.5. the tiling. We can now define the tiling of the plane as follows. Start with a tile T_{0} at the origin. When we multiply by λ, the image λT_{0} subdivides into T_{0} union the given triangulation of λT_{0} − T_{0}. We multiply by λ n + 2 more times, mapping the annuli λT_{0} − T_{0} successively to λ^{2}T_{0} − λT_{0}, λ^{3}T_{0} − λ^{2}T_{0}, and so on, up to λ^{n+3}T_{0} − λ^{n+2}T_{0}. At this stage we have a concentric sequence of annuli (each with a triangulation homothetic to the triangulation in λT_{0}), and a tile T_{0} at the origin.

Each triangle except those in the innermost and outermost annulus has a surrounding by triangles. The surroundings of triangles in the second innermost annulus are in X, since the triangles in the first three annuli are in T by conditions (1) and (2) on M. So each surrounding is a homothetic copy of an element of X. At this point the surroundings of the triangles in the 2nd outermost annulus are of the form λ^{n}X for some X ∈ X. Now subdivide (as in section 4.4.1,4.4.2) all vertices and edges which are on the boundary between the outermost and 2nd outermost annulus (i.e. on λ^{n+2}∂T_{0}).

Multiply once more by λ. Subdivide all triangles in the 2nd outermost annulus λ^{n+3}T_{0} − λ^{n+2}T_{0} using the subdivision as in sections 4.4.1,4.4.2, 4.4.4. That is, first subdivide any vertices which have not yet been subdivided (i.e. were not subdivided at the previous stage), then any edges which have not yet been subdivided, then finally subdivide triangles when all their vertices and edges have been subdivided. Those triangles adjacent to λ^{n+2}∂T_{0} have a previously defined subdivision on one or more of their vertices and edges. The new subdivisions will by construction agree with the old subdivisions near these vertices and edges. Note that in this way the subdivision of a triangle depends only on the triangles in its surrounding (i.e. on the appropriate element of X).

We now continue multiplying by λ and subdividing, with the following rule: label the triangles by their “size”: those in λT_{0} − T_{0} are labeled 1, the image of a triangle of label k is a triangle of label k + 1 unless k = n + 2, in which case the image is subdivided into a copy of T_{0} and lots of small triangles in T of label 1 again.

As we continue multiplying these tilings fill out the whole plane, and there is a unique limiting tiling since larger and larger portions around the origin are fixed.

Adjacent triangles in the limiting tiling have the same size or else their size differs by 1 mod n+2. If adjacent triangles have size both < n+2, then they don’t subdivide on multiplication by λ. If the sizes are n + 2, n + 2 then their subdivisions agree by definition. If the sizes are n + 1, n + 2, then the n + 2-sized tile subdivides, so the common egde or vertex subdivides. At the next multiplication by λ, the other tile will subdivide with a subdivision which by construction matches the existing subdivision along the common edge or vertex. If adjacent sizes are 1 and n + 2, then they just came from a pair of tiles of sizes n + 2 and n + 1, so again their subdivisions agree.

4.6. refining the boundaries. We have defined a subdivision rule for triangles, or rather, elements of X, and a tiling of the plane with scaled elements of X ∪{λT_{0}}. To make this a true self-similar tiling we need to redraw the boundaries of the triangles and of T_{0} so that the image of a tile covers exactly a set of tiles in the tiling.

Let X ∈ X be a surrounding of t ∈ T . For each edge e in t (between vertices v_{i} and v_{j} of t) draw a polygonal arc α_{e} from λ^{n+2}v_{i} to λ^{n+2}v_{j}, which is contained in N_{r_{2}}(λ^{n+2}e), and has edges contained in the set of edges of triangles in the triangulation of N_{r_{2}}(λ^{n+2}t).

The part of the path α_{e} in N_{r_{1}}(λ^{n+2}v_{i}) should depend only on this neighborhood; similarly the part of the path in N_{r_{1}}(λ^{n+2}v_{j}) should depend only on that neighborhood, and the part of the path along the edge should depend only on N_{r_{2}}(λ^{n+2}e). This is to guarantee that the paths for different surroundings agree whenever there is overlap. For example, if triangles t_{1} and t_{2} are adjacent along an edge e, then the path α_{e} along λ^{n+2}e will be the same for the surrounding of t_{1} as for t_{2}.

Furthermore the choice of paths in vertex neighborhoods N_{r_{1}}(λ^{n+2}v_{i}) should be made so that the paths going out along different edges incident at the vertex should be non-crossing and diverging (although such paths may have common initial segments, they are disjoint except for a connected initial segment). See Figure 6.

Figure 6. Choosing a path around t.

Define β_{e} = λ^{−n−2}α_{e}, so that β_{e} is a polygonal arc between vertices of t which follows closely the edge e. Define γ_{t}^{1} to be the concatenation of the 3 edge paths β_{e_{12}}, β_{e_{23}}, β_{e_{31}}, removing any “backtracking” which may occur near the three vertices: that is, if the last edge of β_{e_{12}} is the same as the first edge of β_{e_{23}} in the reverse direction, remove these two edges from γ_{t}^{1}, and so on. So γ_{t}^{1} is a simple closed polygonal path running once around t.

The paths λ^{n+2}γ_{t}^{1} are composed of edges of triangles in T . To each such edge e_{j} is associated its arc β_{e_{j}}. Define γ_{t}^{2} by replacing each edge λ^{−n−2}e_{j} in γ_{t}^{1} with a copy of λ^{−n−2}β_{e_{j}}, again removing backtracks near the vertices of the e_{j}. Inductively define γ_{t}^{k+1} by replacing each edge λ^{−(n+2)k}e_{j} in γ_{t}^{k} by a copy of λ^{−(n+2)k}β_{e_{j}} and removing backtracks.

These paths γ_{t}^{k} converge as k → ∞ to a simple closed curve γ_{t} running around t: γ_{t}^{k} lies in the cλ^{−k(n+2)}-neighborhood of γ_{t}^{k−1}, for some constant c, so the paths converge in the Hausdorff metric. The limits are arcs by our choice of n, which is so large that any potential non-injectivity in γ_{t}^{k} must occur near a vertex of γ_{t}^{k−1}, where by construction it cannot occur.

For each X ∈ X, the Jordan curve γ_{t} forms the boundary of a tile T_{X}. A similar construction gives a Jordan curve for the boundary of T_{0}. These tiles T_{X} have the property that λ^{n+2}T_{X} subdivides exactly into other tiles in {T_{0}} ∪ {T_{X′} : X ∈ X }. Also λT_{0} subdivides exactly into a copy of T_{0} and certain T_{X}.

4.7. proof of self-similarity. Let S = {T_{0}} ∪ S_{1} ∪ S_{2} ∪ … ∪ S_{n+2}, where S_{i} = {λ^{i}T_{X} | X ∈ X }. We have now constructed a tiling of the plane, with tiles which are translates of tiles in a subset of S (not every element of S may actually occur in the tiling). By construction when we multiply the tiling by λ and subdivide each tile according to the rules established above (T_{0} subdivides into the tiles as defined in section 2, each tile in S_{i} maps homothetically to a tile in S_{i+1} unless i = n + 2 in which case a tile subdivides as described in section 4.4.4).

Furthermore tiles of the same type (i.e. those arising from the same element of X, and which are of the same size) subdivide in the same way.

Furthermore each tile occurring in the tiling arises from eventual subdivision of the tile T_{0}, since T_{0} has the origin in its interior. Each tile eventually has a copy of T_{0} in its subdivision. So the subdivision matrix is primitive, and hence the tiling is quasiperiodic (Lemma 4).

This completes the proof.

5. Tilings invariant under rotations

Let T be a self-similar tiling invariant under e^{iθ} and having expansion constant λ. If λ is real, then by redefining the subdivision rule we have that T is self-similar with expansion e^{iθ}λ. Thus we can assume λ is not real unless e^{iθ} = −1.

In [11] it is shown that for any self-similar tiling with expansion λ ∉ ℝ there is a homothetic copy K′ of ℚ[λ] such that translations between tiles of the same type must be in K′. So if the tiling is invariant under x → xe^{iθ}, then if a ≠ 0 is a translation between tiles of the same type, both a and ae^{iθ} are in K′, so their ratio e^{iθ} must be in ℚ[λ].

In case e^{iθ} = −1 we also have e^{iθ} ∈ ℚ[λ].

To construct a tiling invariant under rotation by θ = 2π/m, modify the construction of section 4 as follows.

Select the tile T_{0} to be invariant under e^{iθ}. Then the region between λT_{0} and T_{0} has a e^{iθ}-invariant triangulation.

The construction now proceeds as before. Note that e^{iθ} is an algebraic integer, and multiplication by e^{iθ} acts as an isometry on the space W and the lattice σ(A). Since the subdivision defined in section 4.4 depends solely on the metric properties of the objects involved, the subdivision is natural in the sense that two elements X_{1}, X_{2} ∈ X (surroundings of t_{1}, t_{2} respectively) which are isometric copies of each other have subdivisions which are isometric. (Note that even if X_{1} and X_{2} overlap, the naturality of the subdivision implies that they will subdivide isometrically).

The only place in the construction where we again had a choice was in defining the paths running around the tiles. However we claim that we can make this choice in a way which only depends on the isometry type of the relevant vertex or edge. The only difficulty arises when isometric surroundings overlap. If t_{1} and t_{2} meet at a vertex v and the isometry from t_{1} to t_{2} takes v to v, then the subdivision near v is already θ-invariant, so one can choose paths running out from that vertex in a θ-invariant fashion. Similarly if t_{1} and t_{2} meet along an edge e, and the isometry taking t_{1} to t_{2} takes e to e, then the subdivision of e is invariant under this isometry and so one can choose the path α_{e} to also be invariant. These choices imply the naturality of the entire construction.

So the resulting tiling will be invariant under e^{iθ}.

6. Construction from free group endomorphisms

In this section we give a construction for self-similar tilings whose expansion coefficient is a complex Perron number which satisfies

λ^{n} − pλ^{n−1} + qλ + r = 0 (4)

for some n ≥ 3 and integers p, q ≥ 0, r ≥ 1.

We will first do the case n = 3. Let a, b, c be vectors pointing in different directions in ℝ^{2}. Let F be the set of compact polygonal paths starting at the origin, each of whose edges is a translate of ±a, ±b, or ±c, and which are non-backtracking in the sense that along the path a segment x is never immediately followed by −x.

Thus to each element in F is associated a unique element in the free group on three symbols F (a, b, c). Indeed, one can easily define a product on F in such a way that the map F (a, b, c) → F is a group isomorphism: to obtain the product of two paths, translate the second to the end of the first, and then cancel any “backtrackings”.

Let f: F (a, b, c) → F be this isomorphism.

Define an endomorphism ϕ: F (a, b, c) → F (a, b, c) by:

ϕ(a) = b
ϕ(b) = c,
ϕ(c) = c^{p}a^{−r}b^{−q}.

Consider the three commutators [a, b] = aba^{−1}b^{−1}, [b, c], and [a, c]; they represent three closed paths. Their images under ϕ can be written:

(5)  ϕ([a, b]) = [ϕ(a), ϕ(b)] = [b, c]
(6)  ϕ([b, c]) = [c, c^{p}a^{−r}b^{−q}] = c^{p}a^{−r}[a^{r}, c](b^{−q}[b^{q}, c]b^{q})a^{r}c^{−p}
(7)  ϕ([a, c]) = [b, c^{p}a^{−r}b^{−q}] = [b, c^{p}]c^{p}a^{−r}[a^{r}, b]a^{r}c^{−p}

Using the identities

[x^{n}, y] = (x^{n−1}[x, y]x^{1−n}) ⋯ (x[x, y]x^{−1})[x, y]

and

[x, y^{n}] = [x, y](y[x, y]y^{−1}) … (y^{n−1}[x, y]y^{1−n})

in the above, we see that each of ϕ([a, b]), ϕ([b, c]) and ϕ([a, c]) can be written as a product of conjugates of [a, b], [b, c], and [a, c]. Interpreting this in terms of paths in ℝ^{2}, the closed paths fϕ([a, b]), fϕ([b, c]), fϕ([a, c]) can each be tiled by translates of copies of the parallelograms f([a, b]), f([b, c]), f([a, c]).

Geometrically, the images f([a, b]), f([b, c]), f([c, a]) are “archtiles” for a self-similar tiling of the plane. Let S = {[a, b], [b, c], [a, c]}. The images f(ϕ(x)), where x ∈ S can be tiled by translates of tiles in S: the exact translates can be calculated from the formulas in (5),(6),(7).

Take a, b, c to be the vectors 1, λ, and λ^{2} ∈ ℂ respectively. The equation (4) implies that the argument of λ is less than π/2 degrees, so that f[a, b], f[b, c], f[a, c] each have the same orientation. (In particular this implies that the tiling will be non-overlapping.) Then fϕ(a) = f(b) = λf(a), fϕ(b) = f(c) = λf(b), and fϕ(c) is a path whose endpoint is at λf(c).

Now the closed paths f(ϕ^{n}(x)) for x ∈ S converge after rescaling^{1} to the boundaries of certain tiles T_{1}, T_{2}, T_{3}, and λT_{i} can be tiled by exactly by translates of T_{1}, T_{2} and T_{3}. This is sufficient to make a self-similar tiling of the plane.

An example is given in Figures 7,8,9 and 1.

Figure 7. The case (p, q, r) = (1, 2, 1) (λ ≈ .696 + 1.436i). The three archtiles f([a, b]), f([b, c]), f([a, c]).

Figure 8. The successive approximations to the subdivision of [b, c]:

here we took fϕ^{n}([b, c]) for n = 2, 3, 4, 5, 6, and 10.

For the case n > 3, a similar construction will work. Here we must use the free group on n letters a_{1}, …, a_{n}, with an endomorphism ϕ(a_{i}) = a_{i+1} for 1 ≤ i ≤ n − 1 and ϕ(a_{n}) = a_{n}^{p}a_{1}^{−q}a_{2}^{−r}. The archtiles are the (n^{2} − n)/2 words/paths [a_{i}, a_{j}] with i < j.

1a rigorous argument for convergence can be made along the lines of Dekking [4, 5]

Figure 9. The subdivisions of tiles T_{1}, T_{2}, T_{3}: T_{1} gives a T_{2}, T_{2} gives two copies of T_{2} and a copy of T_{3}, and T_{3} subdivides into a T_{2} and a T_{1}.

This same construction in fact works with any endomorphism ϕ which has the property that each ϕ([a_{i}, a_{j}]) can be written as a product of conjugates of the [a_{i′}, a_{j′}]. Since conjugates of the [a_{i}, a_{j}] generate the commutator subgroup [F, F], this condition amounts to the requirement that the conjugates which appear have nonnegative exponent.

For an arbitrary endomorphism, one can also attempt to change the basis of F so that it has the correct form; a necessary condition is that the induced linear map on [F, F]/[F, [F, F]] ≅ ℤ^{(n^{2}−n)/2} have matrix with nonnegative coefficients.

References

1. R. Adler, B. Weiss; Entropy is a complete metric invariant for automorphisms of the torus. Proc. Nat. Acad. Sci. 57, No. 6. (1967):1573-1576.

2. C. Bandt. Self-Similar Sets 5. Integer Matrices and fractal tilings of ℝ^{n}, Proc. AMS. 112, number 2 (1991), 549-562.

3. R. Bowen; Equilibrium states and the ergodic theory of Anosov diffeomorphisms. Lecture Notes in Math 470., Springer Verlag, 1975.

4. F.M. Dekking. Recurrent Sets. Adv. in Math 44 (1982), 78–104.

5. F.M. Dekking. Replicating superfigures and endomorphisms of free groups. J. Combin. Th. Ser. A 32 (1982), 315–320.

6. M. Gardner; Extraordinary nonperiodic tiling that enriches the theory of tiles. Scientific American (January 1977):116-119.

7. W. Gilbert. Radix Representations of Quadratic Fields. Journal of Math. Anal. and Appl. 83 (1981).

8. S. Golomb; Replicating figures in the plane.Math. Gaz.48 (1964):403-412.

9. K. Gröchenig, A. Haas; Self-similar lattice tilings. J. Fourier Analysis.

10. R. Kenyon, Self-similar tilings, Thesis, Princeton Univ, 1990.

11. R. Kenyon, Inflationary Similarity-tilings. Comment. Math. Helv (to appear).

12. J. Lagarias, Y. Wang; Integral self-affine tiles in ℝ^{n}. I: Standard and non-standard digit sets. J. London Math. Soc. (to appear).

13. D. Lind, The entropies of topological Markov shifts and a related class of algebraic integers. Erg. Th. Dyn. Sys. 4 (1984):283-300.

14. B. Praggastis, Markov partitions for hyperbolic toral automorphisms, Thesis, Univ of Washington, Seattle (1992).

15. C. Radin, M. Wolff; Space tilings and local isomorphism, Geometriae Dedicata 42 (1992):355-360.

16. Y. Sinai. Constructions of Markov partitions, Func. Anal. and its Appl. 2, (1968) no. 2., 70-80.

17. R. S. Strichartz; Wavelets and Self-Affine Tilings. Constructive Approximation 9,(1993):327-346.

18. W. P. Thurston, Groups, tilings, and finite state automata, Lecture notes, AMS colloquium lectures, (1990).

19. A. M. Vershik, Arithmetic Isomorphism of hyperbolic toral automorphisms and sofic shifts. Func. Anal. 1992 no. 2.

20. A. Vince; Replicating Tessellations, SIAM J. Disc. Math 6(1993):501-521.

CNRS UMR 128, Ecole Normale Supérieure de Lyon, 46, allée d’Italie, 69364 Lyon, France.