Tilings, C^{∗}-algebras and K-theory

Johannes Kellendonk and Ian F. Putnam

Abstract. We describe the construction of C^{∗}-algebras from tilings. We describe the K-theory of such C^{∗}-algebras and discuss applications of these ideas in physics. We do not assume any familiarity with C^{∗}-algebras or Ktheory.

1. Introduction

Our starting point for this article is the development of the mathematical theory of tilings, especially that of aperiodic tilings which began with the work of Wang, Robinson and Penrose [GS]. The connections of this field with dynamical systems and ergodic theory is, by now, quite well-established. More specifically, there are various ways of viewing a tiling of d-dimensional Euclidean space, ℝ^{d}, as giving rise to an action of the group ℝ^{d} on a topological space. The elements of this space are themselves tilings and the action is by the natural notion of translation. We will explain a version of this in section 2.

The connection between ergodic theory and von Neumann algebras begins with the pioneering work of Murray and von Neumann. The analogous connection between C^{∗}-algebras and topological dynamics also has a long history. For a general reference to operator algebras, see [Da, Fi, Pe]. Basically, there is a construction which begins with a general topological dynamical system and produces a C^{∗}-algebra. By a “general topological dynamical system”, we certainly include the actions of locally compact groups on locally compact Hausdorff spaces as well as some topological equivalence relations and foliations of manifolds. (See the references above for various special cases and [Ren] for a very general version.) While this study began somewhat later than that in ergodic theory and von Neumann algebras, in the last twenty years it has blossomed. This is mainly due to the development of the technical tools needed. In particular, K-theory has had a major impact on the general theory of C^{∗}-algebras and especially on the aspects relating to dynamics. Thus, it seems natural to try to investigate the special case of the dynamics obtained from tilings and their associated C^{∗}-algebras. This was already observed by Alain Connes in [Co2]. The goal is two-fold. First, to produce interesting examples of C^{∗}-algebras. The second point is to use C^{∗}-algebras and techniques from their study to learn more about the tilings.

While written mainly from the mathematical point of view, the article also aims at explaining briefly the physical aspects of (topological) tiling theory. The tilings have been used by physicists as models in the study of quasicrystals. (See, for example, [Ja, StO].) On the other hand, operator algebras began as mathematical models in quantum mechanics. These C^{∗}-algeras are closely related with the physics of quasicrystals. We will discuss this and especially the rôle of K-theory in physics. K-theory enters in physics through Bellissard’s formulation of the gap labelling [Be1, Be2]. Also see his and his co-authors’ contribution to this volume.

The article is written for the reader having little or no background in the theory of C^{∗}-algebras. This means that we will sacrifice some precision in our discussions. We hope that the main ideas are accessible if we avoid getting bogged down in technicalities (even if they are important ones).

We will begin by describing tilings as dynamical systems. The general theory is presented in the next section and in the following section we discuss tilings possessing self-similarity in the form of a substitution rule. Of course, much of this is fairly standard by now. However, there are certain points where our view anticipates the questions we will look at later when dealing with C^{∗}-algebras.

There are several different constructions of C^{∗}-algebras from a tiling. We present two of these in sections 4 and 5. The first is to proceed from the continuous dynamics of the natural action of Euclidean space as translations of the tilings. The second takes a more discrete view of the situation. It tends to be more combinatorial and probably more accessible for someone unfamiliar with operator algebras. It is also the important one for physics, if one uses the tight-binding approximation. This is discussed in section 6. In fact, the two C^{∗}-algebras are not so different. They are equivalent to one another in Rieffel’s sense of strong Morita equivalence. We will describe this notion and its consequences briefly in section 5 also. There is a third approach to constructing C^{∗}-algebras from tilings. It has been developed by J. Bellissard and is strongly motivated by physical considerations. It is more operator theoretic than the constructions we consider, which tend to be more geometric.

Section 7 gives a short (and highly incomplete) introduction to K-theory for C^{∗}-algebras and in the following section we discuss its relevance within physics. In particular, we will give a physical motivation for the study of the K-theory of the C^{∗}-algebras we have constructed from tilings.

The final section gives on outline of the computations made of the K-theory of the two C^{∗}-algebras we have constructed earlier. These computations concentrate on the case of substitution tiling systems. The case of tilings obtained from the projection method have been considered recently by Forrest, Hunton and Kellendonk [FHK].

The case of the first C^{∗}-algebra (from the continuous dynamics) was done by the second author, in collaboration with Jared Anderson. The second C^{∗}-algebra was done by the first author. The fact that these two are strongly Morita equivalent implies that they will have isomorphic K-theories.

Unfortunately, our desire to provide an introduction forces us to limit our discussions. Let us quickly mention some items which we do not include. The more intricate computations of the K theory are sometimes omitted. In particular, we do not describe the computation of the kernel of the map from K_{0}(AF_{T}) to K_{0}(A_{T}) which appears in [Kel2]. We use the simplest possible definiton of a substitution tiling system. There are many generalizations, which actually occur in certain examples of interest. We do not discuss topological equivalence of tilings.

We present an example, the octagonal tiling. More examples can be found in the references, especially to our own papers [AP, Kel1, Kel2, Kel3].

2. Tilings as dynamics

In this section, we show how a tiling T of ℝ^{d} gives rise to a topological dynamical system (Ω_{T} , ℝ^{d}). That is, Ω_{T} is a compact metric space with an action of ℝ^{d} or, equivalently, a d-dimensional flow. The construction is a fairly standard one in dynamics. We refer the reader to [GS, RW, ER1, Rud, So1].

Let us begin with some notation. ℝ^{d} denotes the usual d-dimensional Euclidean space. For x in ℝ^{d}, r > 0, B(x, r) denotes the open ball, centred at x with radius r. If X ⊂ ℝ^{d} and x ∈ ℝ^{d}, then X + x = {x′ + x | x′ ∈ X}, the translate of X by x.

A tiling, T, of ℝ^{d} is a collection of subsets {t_{1}, t_{2}, ⋯ }, called tiles, such that their union is ℝ^{d} and their interiors are pairwise disjoint. We will also assume, for simplicity, that each is homeomorphic to the closed unit ball, \overline{B(0, 1)}. We also allow the possibility that our tiles carry labels. So that if two tiles have the same label, then one is a translate of the other. If we include labels, then when we write t + x = t′, for t, t′ in T, x in ℝ^{d}, we mean not only that the sets are the same, but the labels on t and t′ are the same. Generally, we say two tiles are the same tile type if one is a translate of the other.

If T is a tiling and x is in ℝ^{d}, then

T + x = {t + x | t ∈ T }

the translate of T by x is also a tiling. Beginning with a single tiling T, we consider all of its translates T + ℝ^{d} and endow this set with a metric d as follows. For 0 < ϵ < 1, we say the distance between T_{1} and T_{2} in T + ℝ^{d} is less than ϵ if we may find vectors x_{1}, x_{2} in B(0, ϵ) such that T_{1} + x_{1} and T_{2} + x_{2} are equal on B (0, \frac{1}{ϵ}). If there are no such x_{1}, x_{2} for any ϵ, then we set the distance to be 1. (See also [RW, ER1, Rud, So1].)

The construction is a standard one. Notice already that it is measuring something interesting about the way patterns in T repeat: for x, y in ℝ^{d} d(T − x, T − y) is small when the patterns in T at x and y agree, up to a small translation.

Definition 2.1. Given a tiling T, we let Ω_{T} denote the completion of the metric space (T + ℝ^{d}, d). We refer to this as the continuous hull of T.

It is important (but fairly easy) to observe that the elements of Ω_{T} can be viewed as tilings and that the same definition of our metric d extends to Ω_{T}.

Theorem 2.2. [RW] Let T be a tiling. Suppose that, for any R > 0, there are, up to translation, only finitely many patches in T (i.e. subsets of T) whose union has diameter less than R. Then (Ω_{T} , d) is compact.

We will refer to the hypothesis of this theorem as the finite pattern condition although it is also called finite local complexity ([La]).

It is clear that ℝ^{d} acts by translation on the elements of Ω_{T}; if T′ is a tiling in Ω_{T}, so is T′ + x, for any x in ℝ^{d}. It is clear also that (Ω_{T} , ℝ^{d}) is topologically transitive, i.e. there is a dense orbit (namely that of T). More subtley, we can ask whether every orbit is dense. In this case, we say (Ω_{T} , ℝ^{d}) is minimal.

Theorem 2.3. (Ω_{T} , ℝ^{d}) is minimal if and only if, for every finite patch P in T, there is an R > 0 , such that for every x in ℝ^{d}, there is a translate of P contained in T and in B(x, R).

The condition in the theorem is also called repetitivity. We say that a tiling T is aperiodic if T +x ≠ T, for any non-zero vector x. We will mainly be interested in aperiodic tilings T and for such a tiling, it is possible that Ω_{T} will contain periodic tilings. (Consider tiling the plane with unit squares, fitting edge to edge. Remove four of them meeting at a point and replace with a square of side length two. This tiling is aperiodic, but its hull contains the original tiling by unit squares.)

Throughout the rest of the paper we will say that

(i) T is minimal, if the conditions of Theorem 2.3 are satisfied.

(ii) T is strongly aperiodic, if Ω_{T} contains no periodic tilings. We will note, but not prove, the following.

Proposition 2.4. If the tiling T is aperiodic and minimal, then it is strongly aperiodic.

3. The dynamics of substitution tilings

Many tilings of interest possess a self-similarity structure. In fact, one can begin with a finite set of tiles with a substitution rule and produce tilings from iteration of the rule. The self-similarity appears as this substitution applied to the resulting tilings. (See also [GS, Ken, ER1, So1].)

We begin as follows. Suppose we have a finite collection of non-empty, compact sets, each being homeomorphic to the closed unit ball, {p_{1}, …, p_{N}}, in ℝ^{d}. These we call the prototiles. (This is not necessarily the standard use of this term.) We suppose we have a substitution rule ω and a scaling factor λ > 1. This means that, for each p_{i}, ω(p_{i}) is a finite collection of subsets, each one being a translate of one of the prototiles, overlapping only on their boundaries. Moreover the union of these sets is exactly λp_{i}. Thus, ω allows us to replace prototiles by patches.

We can extend the definition of ω to translates of the original prototiles, p, by setting ω(p + x) = ω(p) + λx, for x in ℝ^{d}. If P is any patch made up of such translates (in a non-overlapping fashion), then we define

ω(P) = {ω(t) | t ∈ P }

If T is a tiling, then so is ω(T). This also means that we can iterate, forming a sequence of patches, ω^{k}(p_{i}), for k = 1, 2, 3, . . ..

We will assume that our substitution is primitive: for some k > 1, a translate of each p_{i} appears inside the patch ω^{k}(p_{j}), for all i, j.

It is a fairly standard argument, which we now sketch, to show that such a system will actually admit tilings. (For more details, see [GS].) One can find a translate of one of the prototiles t and a k > 1 so that the sequence of patches ω^{kn}(t), for n = 1, 2, 3, …, grows to cover the plane and is consistent in the sense that any two agree where they overlap. We let T denote the union of these patches which is a tiling. With the hypothesis of primitivity, the hull Ω_{T} is independent of the choice of T constructed in this way. To emphasize this fact, we will drop the subscript T from our notation. (In fact, there is another equivalent definition of the space Ω which avoids making a choice of T. The construction above is needed however, to show that this space is non-empty.) We will also assume that T satisfies the finite pattern condition.

As we noted above, there is an extension of ω to tilings. Its restriction to Ω is continuous and surjective [Mo, AP] and we also have ω(Ω) ⊆ Ω. From now on we will also assume that ω : Ω → Ω is injective as well. This is quite a subtle point. It amounts to what is usually called “recognizability”. As an example, consider having a single tile which is a unit square in the plane. The scaling factor λ is 2 and the map ω simply divides the square into four smaller squares, and then rescales by 2. If we centre this square at the origin and interate to obtain our tiling, T, we obtain the tiling of the plane by unit squares with vertices on the integer lattice points. Consider T and T + (.5, .5), which is the same tiling, but aligned so that the centres are on the integer lattice. Now, we have ω(T) = ω(T + (.5, .5)) = T, and so ω is not injective. In fact, it is fairly easy to generalize this example to show that our hypothesis that ω is injective implies that Ω contains no periodic tilings. (For the converse, see [So2].)

Let us mention that this set-up can be generalized considerably. First, the constant λ can be replaced by any expansive linear transformation of ℝ^{d}. In [Kel2], there is an even more general version where a substitution is defined as (roughly) a map from the set of patches in a tiling to itself satisfying certain conditions. The expansiveness (λ > 1) is replaced by a growth condition.

We may consider (Ω, ω) as a dynamical system of its own. As such, it possesses special features which are common in the field of hyperbolic dynamics. Let us give some background for this material.

In his seminal paper [Sm], Smale proposed and initiated the study of Axiom A systems. The idea is to consider a compact Riemannian manifold M with a diffeomorphism, f. We then isolate a closed invariant subset Λ of M, based on the idea of recurrence. More specifically, Λ is the set of chain recurrent points of f. We then assume that f is hyperbolic on Λ in the following sense. The tangent bundle to M, T M, when restricted to Λ, T_{Λ}M, may be decomposed as a direct sum

T_{Λ}M = E^{s} ⊕ E^{u}

where each summand is invariant under the derivative of f and, at least roughly speaking, the derivative contracts vectors in E^{s} while the derivative of f^{−1} contracts vectors in E^{u}. (For a general reference to such systems, see [KH].)

Smale made the key observation that, although (M, f) is smooth, Λ need not be a manifold. (For example, see Smale’s horseshoe [Sm].) Now the system (Λ, f|Λ) exists only in the topological category and motivated by this idea, Ruelle gave a definition of a Smale space [Rue]. The name is slightly mis-leading since the object is both a space and a map.

Basically, a Smale space is a compact metric space with a homeomorphism so that, locally, the space may be written as the product of two subsets. This decomposition (or rather its germs) are invariant under the map and the map contracts the first subset, while its inverse contracts the second.

It is fairly easy to see that our system, (Ω, ω), arising from a substitution tiling with hypotheses as above, has the structure of a Smale space [Ken, ER1, AP]. Let T be any tiling in Ω. We want to produce two subsets of Ω containing T, whose Cartesian product is, in a natural way, homeomorphic to a neighbourhood of T. For the first, consider all tilings which agree with T on a ball at the origin of radius one. First, notice that the map ω acts as a contraction on this set since iteration of the map on two such tilings, produces tilings which agree on larger and larger balls and so the distance between them contracts at an exponential rate. For the second set, take all tilings which are translates of T by a small amount. Notice that the equation

ω^{−n}(T + x) = ω^{−n}(T) + λ^{−n}x

immediately implies that any two such tilings get closer together under iteration of the map ω^{−1}. Finally, it follows at once from the definition of our metric on Ω that for any tiling, T′ close to T, we may find a unique small vector x so that T′ + x agrees with T on a ball of radius one. Then the map sending T′ to the pair (T′ + x, T − x) is a homeomorphism from a neighbourhood of T to the Cartesian product of the two sets mentioned above.

We remark that in this local description of Ω, the local contracting direction is totally disconnected while the other local coordinate is homeomorphic to an open set in ℝ^{d} [ER1].

Our next objective is to present the space, Ω, as an inverse limit of more tractable spaces. The substitution rule allows us to be very specific about this. In particular, all the spaces are copies of the same space, which we will denote Γ. Moreover, the maps between these spaces will also be stationary.

Let Γ̃ be the disjoint union of the prototiles. We define an equivalence relation on this space as follows. For x in p_{i} and y in p_{j}, we set x ∼ y if there are tiles p_{i} +z and p_{j} + w in T such that x + z = y + w. This simply means that if, somewhere in T, we see copies of p_{i} and p_{j} overlapping at the points corresponding to x and y, then we set x ∼ y. At this point ∼ may not be transitive. We define ∼ to be the equivalence relation generated by this relation. The space Γ is the quotient of Γ̃ by ∼. It is a compact Hausdorff space.

In specific examples, all of which having tiles which are polygons, this space has a cellular structure. In the top dimension d, the d-cells are the interiors of the prototiles. This idea has not been developed in generality.

There is a natural map γ : Γ → Γ which is induced by ω. If x is in Γ̃, then x is in some p_{i}. Then the point λx lies in some tile in ω(p_{i}), say t. This is a translate of some other prototile, say t = p_{j} + y. We then define γ(x) to be λx − y, which is in p_{j} and hence in Γ̃. It is possible that λx lies in more than one prototile in ω(p_{i}), but it this case, it is easy to see that the ∼-equivalence class of the resulting point is unique. It is easy to see this induces a well-defined map on Γ. Now the inverse limit

Γ ⟵^{γ} Γ ⟵^{γ} Γ ⟵^{γ}

is denoted by Ω_{0}. It can be defined as

{(x_{0}, x_{1}, x_{2}, …) | x_{i} ∈ Γ, γ(x_{i+1}) = x_{i}, for all i ∈ ℕ}.

Theorem 3.1. [AP] If the substitution system “forces its border”, then Ω is homeomorphic to Ω_{0}.

We will define the condition of “forcing the border” as we give a sketch of the proof. For the moment, let us make a few remarks.

The homeomorphism will actually be a topological conjugacy between the map ω on Ω and the natural shift map on the inverse limit

ω_{0}(x_{0}, x_{1}, …) = (x_{1}, x_{2}, …).

The class of dynamical systems obtained via this inverse limit construction was introduced and studied intensely by R.F. Williams [W] as models for “expanding attractors” within the context of Smale’s program for Axiom A systems. It seems appropriate to refer to such systems as “Williams solenoids”. It is interesting to see that our “forcing the border” condition appears in Williams’ work in the form of a “flattening” axiom.

We will give a short sketch of the proof describing the homeomorphism from Ω to Ω_{0}. The idea is fairly simple. Begin with any tiling T in Ω. We want to define a sequence (x_{0}, x_{1}, …) in the inverse limit. First, locate the tile in T which contains the origin. It is the form p + x, for some prototile p and vector x in ℝ^{d}. Since the origin is in p + x, we have −x in p. This gives us a point in Γ̃ and its image in Γ is x_{0}. Of course, the origin may lie on two or more tiles in T. In this case, all of the points obtained in Γ̃ will be ∼-equivalent and so the point in Γ is unique.

To obtain x_{k}, for k ≥ 1, we repeat this proceedure using ω^{−k}(T) instead of T. It is simple to check that γ(x_{k+1}) = x_{k}, for all k and so this sequence defines a point in Ω_{0}. The important issue here is that this map is injective. To see this, first notice that if the origin is in the interior of a tile in T, then the point x_{0} uniquely determines the tile covering the origin in T. In the case when the origin lies in more than one tile, things are a bit more subtle and one must work more carefully. We will not go into the details in this case. Similarly, x_{k} determines the tile covering the origin in ω^{−k}(T). Let us call this tile t_{k}. This means that x_{k} determines a patch, ω^{k}(t_{k}), in T which contains the origin. The idea is that we can hope these patches grow to cover the plane as k increases. In this case, the sequence (x_{0}, x_{1}, …) then determines T. This will not be true in general, but it is enough that the substitution “forces its border”, in the following sense [Kel1]. There is a k ≥ 1 such that, if T and T′ are two tilings containing a tile t, then the patches in ω^{k}(T) and ω^{k}(T′) consisting of all tiles which meet ω^{k}(t) are identical.

Consider the following one-dimensional example given as a substitution on the alphabet a, b, c. Suppose we define

ω(a) = baabc  ω(b) = bbbc,  ω(c) = bbcaaac.

Notice each word begins in b and ends in c. So we don’t really need to know the symbols to the left or right of an a in an infinite string to know that we will see

… c \underbrace{baabc}_{ω(a)} b …

after applying ω to the infinite string. This is an example of a sustitution forcing its border. The Penrose substitution also forces it border.

Of course, this seems like a strong hypothesis. However, given any substitution tiling system, we can replace it by one that forces it border and has exactly the same collection of tilings. (More precisely, the tilings from the new system are mutually locally derivable in the sense of [BSJ] with those of the old.) We form a new set of prototiles as follows. For each of our original prototiles, p, look at all patches in all tilings in Ω consisting of a translate of p and all its neighbouring tiles. For each such patch (there are only finitely many) create a copy of p and give it a label, which consists of this patch. (The patch only functions as a label; the actual points are the same as in p.) It is easy to see how to define a substitution map on these new labelled prototiles. It is also easy to see that the collection of tilings will be “the same” as before and that this new system forces it border.

It is worth noting that that although the result is quite nice from an abstract viewpoint, this situation can be difficult from a practical one. As an example, the “chair”, “boot” or “triomino” substitution has four prototiles. Unfortunately, it does not force its border. Applying the strategy above yields an equivalent system with fifty-six prototiles. The space Γ will be a cell complex with fifty-six 2-cells.

The last result which produced a description of the space Ω as an inverse limit was in the context of substitution tiling systems. In fact, a weaker version of this seems possible in much more generality.

Problem: For an aperiodic minimal tiling T, express Ω_{T} as an inverse limit of spaces which are fundamentally simpler, such as finite cell complexes.

In section 8, we will use this description of Ω to compute the K-theory of certain C^{∗}-algebras. Before getting quite so involved in the theory of C^{∗}-algebras, it seems interesting to ask at this point, whether the algebraic topology, especially the K-theory and cohomolgy of the space Ω contains information about the tiling? In a similar spirit, Geller and Propp [GP] introduced the notion of the projective fundamental group of a ℤ^{2}-action which will generalize to tilings. Presumably, this presentation of Ω as an inverse limit will make the computation of such invariants more accessible. In particular, it seems to be an interesting question: “To what extent does H^{∗}(Ω_{T}) or K^{∗}(Ω_{T}) determine the almost periodic structure of T?”

4. The C^{∗}-algebra of a tiling I: the continuous case

Let T_{0} be a fixed tiling. We construct Ω_{T_{0}}, which we now denote simply by Ω, as in Section 2. We will assume tht T_{0} is minimal and aperiodic. We want to construct a C^{∗}-algebra from (Ω, ℝ^{d}).

A C^{∗}-algebra is a ℂ-algebra (not necessarily commutative) with an involution a → a^{∗} and a norm in which it is complete [Da, Pe]. There are further hypotheses which are fairly standard. The most important item is the C*-condition on the norm; that is, for every element, a, in the algebra, we have ∥a^{∗}a∥ = ∥a∥^{2}. The two canonical examples are the following. First, let X be any compact Hausdorff space. The collection of continuous ℂ-functions on X with supremum norm and pointwise operations of addition, multiplication and complex conjugation is a commutative C^{∗}-algebra, denoted C(X). The second example is to begin with a complex Hilbert space H and let B(H) denote the set of bounded linear operators on H. With the operator norm and usual algebraic structure it is a C^{∗}-algebra. This second example is non-commutative provided dim H ≥ 2.

To create our C^{∗}-algebra, C^{∗}(Ω, ℝ^{d}), we begin with C_{c}(Ω×ℝ^{d}), the continuous ℂ-functions of compact support on Ω × ℝ^{d}. It is a linear space in the obvious way. We define a product and involution on it by

(4.1)  f · g(T, x) = ∫_{y∈ℝ^{d}} f(T, y) g(T − y, x − y) dy
(4.2)  f^{∗}(T, x) = \overline{f(T − x, −x)},

for f, g in C_{c}(Ω×ℝ^{d}), T in Ω and x in ℝ^{d}. This makes C_{c}(Ω×ℝ^{d}) into a ∗-algebra. There are a number of subtle technical points about equipping it with a norm. We will mention here only that this can be done in a natural way. Unfortunately, it will not be complete. Its completion is C^{∗}(Ω, ℝ^{d}) and is indeed a C^{∗}-algebra. This is an example of the construction of the crossed product C^{∗}-algebra. (For more details of this construction, see [Pe, Z-M].)

We want to present several other views of this C^{∗}-algebra. First, for the reader who likes to think of operators on Hilbert space, we proceed as follows. Consider the Hilbert space L^{2}(ℝ^{d}). We define, for each f in C_{c}(Ω × ℝ^{d}), an operator λ(f) on L^{2}(ℝ^{d}) by

(λ(f)ξ) (x) = ∫_{y∈ℝ^{d}} f(T_{0} + x, y) ξ(x − y) dy (4.3)

for ξ in L^{2}(ℝ^{d}) and x in ℝ^{d}. The map λ is a ∗-homomorphism of C_{c}(Ω × ℝ^{d}) into B (L^{2}(ℝ^{d})) which extends to an isometric ∗-isomorphism between C^{∗}(Ω, ℝ^{d}) and the closure of the collection of λ(f)’s in the operator norm. It is worth noting that there are many other representations, not all as natural as this.

With this description of operators, this C^{∗}-algebra is still not the most intuitive of objects. Let us now take yet another view. Suppose we return to formulae (4.1) and (4.2), defining our product and involution, and change T − y in the first and T − x in the second to simply T. This then removes any hint that ℝ^{d} is acting on Ω. Performing the Fourier transform in the ℝ^{d} variable, one obtains functions on Ω × ℝ^{d} which are continuous and vanish at infinity. The product and involution of (4.1) and (4.2) become pointwise product and conjugate. This Fourier transform extends to an isometric isomorphism of the resulting C^{∗}-algebra onto C_{0}(Ω × ℝ^{d}), the continuous functions vanishing at infinity on Ω × ℝ^{d}, which is a commutative C^{∗}-algebra.

If we return to (4.1) and (4.2) again and replace T − y and T − x with T − hx and T − hy, where 0 ≤ h < ∞ is a parameter, then we can actually view C^{∗}(Ω, ℝ^{d}) (h = 1) as a deformation of C_{0}(Ω × ℝ^{d}) (h = 0). (For much more general situations viewed in this way, see [Ri2].)

The action of ℝ^{d} on Ω makes C^{∗}(Ω, ℝ^{d}) non-commutative. In fact, its centre is trivial. We have the following even stronger result.

Theorem 4.1. [EH, GR] If T_{0} is aperiodic and minimal, then C^{∗}(Ω_{T_{0}}, ℝ^{d}) is simple; i.e. it has no non-trivial closed two-sided ideals.

We describe another formulation of C^{∗}(Ω, ℝ^{d}). Let

R_{T} = {(T, T′) ∈ Ω × Ω | T′ is a translate of T } .

This is an equivalence relation on Ω whose classes are simply the ℝ^{d}-orbits. The map sending (T, x) in Ω×ℝ^{d} to (T, T +x) is obviously a surjection and if we assume that Ω has no periodic tilings, then it is injective as well. If we simply translate our product and involution on C_{c}(Ω × ℝ^{d}) to C_{c}(R_{T}), they become

(4.4)  (f · g)(T, T′) = ∫_{T′′} f(T, T′′) g(T′′, T′) dT′′
(4.5)  f^{∗}(T, T′) = \overline{f(T′, T)},

for T, T′ in Ω, f, g in C_{c}(R_{T}). The nice thing about this formulation is that it reminds one of matrix multiplication and conjugate transpose. Also this definition can then be extended to study other equivalence relations [Ren]. We will do this in Section 5. There are, however, some topological subtleties. We have implicitly transfered the topology of Ω × ℝ^{d} over to R_{T} via our bijection. This is not the relative topology of R_{T} ⊂ Ω×Ω; for large x, T and T +x may be close so (T, T +x) is close to (T, T) in the relative topology, but not in that form Ω × ℝ^{d}. (It is worth noting that in the relative topology, R_{T} is not locally compact and hence, a bit of a disaster from an analytic view.)

We will close this section with a bit of philosophy. We have a group, ℝ^{d}, which is acting freely on a space, Ω. In Alain Connes’ program of non-commutative geometry [Co2], the C^{∗}-algebra C^{∗}(Ω, ℝ^{d}) acts as a replacement for the orbit space, Ω/ℝ^{d}. This should be interpreted as follows. If the space Ω/ℝ^{d} is reasonable (i.e. Hausdorff), then C^{∗}(Ω, ℝ^{d}) should be equivalent to the commutative C^{∗}-algebra C(Ω/ℝ^{d}). In our situation of a minimal, aperiodic tiling, the orbit space Ω/ℝ^{d} has the indiscrete topology and is effectively useless as a topological space, while the non-commutative C^{∗}-algebra contains much interesting imformation. Much more on this point of view may be found in [Co2].

5. The C^{∗}-algebra of a tiling II: the discrete case

In this section, we want to construct another C^{∗}-algebra from a tiling T. The description of this algebra will be simpler than that of C^{∗}(Ω, ℝ^{d}) in the last section. The point is that this new C^{∗}-algebra is equivalent in a certain sense (strong Morita equivalence) to C^{∗}(Ω, ℝ^{d}). First, we will describe the new algebra and then discuss its relation to the old one.

To motivate our discussion, let us examine the simplest non-commutative C^{∗}- algebra: M_{n}, the n × n complex matrices, for n ≥ 2.

For each pair, 1 ≤ i, j ≤ n, let e(i, j) denote the matrix which is one in the (i, j) entry and zero elsewhere. Clearly, these elements satisfy the relations:

(5.1)  e(i, j)^{∗} = e(j, i)
(5.2)  e(i, j) e(i′, j′) = \begin{cases}e(i, j′) & if i′ = j, \\ 0 & otherwise. \end{cases}

In fact, it turns out that M_{n} is the universal C^{∗}-algebra generated by a collection {e(i, j) | 1 ≤ i, j ≤ n} satisfying the relations (5.1) and (5.2). (As an aside, the general construction of C^{∗}-algebras from generators and relations is rather tricky. For instance, there is no free C^{∗}-algebra on one element.)

Now let us turn to our tiling T. We look at all triples (P, t_{1}, t_{2}) where P ⊂ T is finite (i.e. a patch) and t_{1}, t_{2} ∈ P (allowing t_{1} = t_{2}). We say two of these triples are equivalent if one is a translate of the other. We let [P, t_{1}, t_{2}] denote the equivalence class under translation of (P, t_{1}, t_{2}) and call this a doubly pointed pattern class. Our C^{∗}-algebra, which we will denote A_{T} [Kel1, Kel2], is generated by elements e[P, t_{1}, t_{2}], where [P, t_{1}, t_{2}] is a doubly pointed pattern class, subject to some relations. The first is that

e[P, t_{1}, t_{2}]^{∗} = e[P, t_{2}, t_{1}]. (5.3)

The second is that, if (P, t_{1}, t_{2}) and (P′, t′_{1}, t′_{2}) are both contained in a larger patch in such a way that t_{2} = t′_{1}, then

e [P, t_{1}, t_{2}] e [P′, t′_{1}, t′_{2}] = e [P ∪ P′, t_{1}, t′_{2}] (5.4)

whereas otherwise that product is 0. Finally, we require the following. Suppose P is any patch, t is any tile in P and P_{1}, P_{2}, …, P_{k} are a collection of patches, each containing P and so that any tiling which contains P contains exactly one of the P_{i}, then we have

e [P, t, t] = ∑_{i=1}^{k} e [P_{i}, t, t] (5.5)

Observe first, that if P is fixed, each element e[P, t, t] is a self-adjoint idempotent and also that

(5.6)  e [P, t_{1}, t_{2}] e [P, t_{1}, t_{2}]^{∗} = e [P, t_{1}, t_{1}]
(5.7)  e [P, t_{1}, t_{2}]^{∗} e [P, t_{1}, t_{2}] = e [P, t_{2}, t_{2}] .

Secondly, if we list representatives of all tile types: t_{1}, t_{2}, …, t_{n}, then

∑_{i=1}^{n} e [{t_{i}} , t_{i}, t_{i}] (5.8)

is a unit for our C^{∗}-algebra. Now, we want to give an indication of why this C^{∗}-algebra is related to C^{∗}(Ω, ℝ^{d}).

At the same time, we will obtain another description of it.

Recall Ω, our space of tilings. For each tile type (or labelled tile type) in T, we choose a point in the interior which we call a puncture. Now in our tiling each tile, t, is given a puncture x(t), so that if two tiles t_{1} and t_{2} are translates, say t_{1} = t_{2} + x, then x(t_{1}) = x(t_{2}) + x. In the same way, each tile in every tiling in Ω also gets a puncture.

Definition 5.1. [Kel1] We define the discrete hull of T, which we denote by Ω_{punc}, to be all the tilings T′ in Ω such that the origin is a puncture of some tile t in T′; that is, x(t) = 0. (Note that, since the punctures do not lie on the boundaries of tiles, the choice of t is unique.)

First observe the following simple facts about Ω_{punc}.

1. If T′ is any tiling in Ω, T′ + x is in Ω_{punc} for some x in ℝ^{d}.

2. If T′ is in Ω_{punc}, there is an ϵ > 0 such that T′ + x is \underline{not} in Ω_{punc}, for any x with 0 < |x| < ϵ.

3. Ω_{punc} is closed in Ω.

We summarize by saying that Ω_{punc} is a transversal to the ℝ^{d}-action. (See [MRW].) Somewhat less obvious is that, if we assume T satisfies the finite pattern condition, then Ω_{punc} is a Cantor set; that is, it is compact, has no isolated points and its topology is generated by sets which are both closed and open. Let us present such sets. Let P be a finite patch in T and let t be an element of P. Then P − x(t) is a patch having a puncture on the origin. Look at all tilings in Ω_{punc} which contain the patch P − x(t); i.e.

U(P, t) = {T′ ∈ Ω | P − x(t) ⊂ T′} .

One can check that U(P, t) is both open and closed in the relative topology of Ω_{punc} and that such sets generate the topology of Ω_{punc}.

We now define an equivalence relation R_{punc} on Ω_{punc} as follows:

R_{punc} = {(T_{1}, T_{2}) | T_{1}, T_{2} ∈ Ω_{punc} and ∃x ∈ ℝ^{d} : T_{1} = T_{2} + x} .

This means we are taking the equivalence relation on Ω_{T} whose classes are simply the ℝ^{d}-orbits, which we called R_{T} in section 4, and we are restricting it to Ω_{punc} : R_{punc} = R_{T} ∩ (Ω_{punc} × Ω_{punc}). We provide R_{punc} with a topology as follows. A sequence (T_{n}, T_{n} + x_{n}) in R_{punc} converges to (T, T + x) if and only if d(T_{n,}T) and |x_{n} − x| both tend to zero. There are a number of technical subtleties here, but we proceed to define a C^{∗}-algebra A_{T} = C^{∗}(R_{punc}) as follows [Kel1, Ren]. Begin with C_{c}(R_{punc}) as a linear space and define product and involution by

(5.9)  (f · g)(T_{1}, T_{2}) = ∑_{T′ s.t. (T_{1},T′)∈R_{T}} f(T_{1}, T′) g(T′, T_{2})
(5.10)  f^{∗}(T_{1}, T_{2}) = \overline{f(T_{2}, T_{1})}.

These formulas should certainly remind one of matrix multiplication and adjoint and (4.6) and (4.7). As with C^{∗}(Ω, ℝ^{d}), this ∗-algebra must be given a norm and completed to get a C^{∗}-algebra. We will not discuss this here, but the result is C^{∗}(R_{T}) which we will call simply A_{T}. We point out that Bellissard etal. make a very similar construction with measures instead of tilings (see their contribution in this book).

We must address two issues: first, to see the elements e [P, t_{1}, t_{2}] we discussed earlier and secondly to see how this C^{∗}-algebra is related to C^{∗}(Ω, ℝ^{d}).

For the first part, let (P, t_{1}, t_{2}) be a doubly pointed pattern class in T. The map sending T′ in U(P, t_{1}) to T′ + x(t_{2}) − x(t_{1}) in U(P, t_{2}) is a homeomorphism. Its graph is not only contained in R_{punc}, but is actually a compact and open subset. Let e [P, t_{1}, t_{2}] denote its characteristic function. Now one checks easily from the definitions (5.10) and (5.9) that these elements satisfy the relations (5.3) and (5.4). Also, the graphs of such functions actually generate the topology of R_{punc}, so the linear span of the e [P, t_{1}, t_{2}]’s is dense in C_{c}(R_{punc}) and hence in A_{T}.

To continue our analogy of A_{T} with M_{n}, we observe the following analogue of the subalgebra of diagonal matrices.

Proposition 5.2. The map sending the characteristic function of U(P, t) to e [P, t, t] is a unital injective ∗-homomorphism of C(Ω_{punc}) to A_{T}.

We now turn to the second problem, relating A_{T} with C^{∗}(Ω, ℝ^{d}). These algebras are strongly Morita equivalent – a concept introduced by Marc Rieffel [Ri1, MRW]. In fact, any time one considers a transversal to an equivalence relation satisfying conditions 1, 2, 3 as above, the associated C^{∗}-algebras will be related in this way.

Rather than describe this in detail, we will give some simple examples and some consequences. If A is any C^{∗}-algebra, it is strongly Morita equivalent to M_{n}(A), the C^{∗}-algebra of n × n matrices over A. Also, if h is any self-adjoint element of A whose spectrum is non-negative, then A is strongly Morita equivalent to the closure of hAh, provided the closed two-sided ideal in A generated by h is all of A.

If two C^{∗}-algebras are strongly Morita equivalent, then there is a natural bijective correspondence between their ideal structures (ideal means closed two-sided ideal), their representation theories and their K-theories. Although the definition of strong Morita equivalence is complicated enough that we omit it here, it is the most natural notion of equivalence for C^{∗}-algebras — perhaps even more natural than isomorphism.

6. C^{∗}-algebras in physics

In this section, we will discuss the role of the C^{∗}-algebra, A_{T}, in physics. In the quantum mechanical model of the motion of a particle in Euclidean space, an observable is a self-adjoint operator. Ignoring internal degrees of freedom (like spin) and provided there are no external forces (like an external magnetic field) such an operator is constructed from position and momentum operators. So we can work entirely inside the algebra generated by the momentum and position operators. We choose to work within the C^{∗}-algebra which is the closure of this algebra and refer to it as the C^{∗}-algebra of observables. We want to study the impact of the topology of this underlying non commutative space, in the sense of [Co2]. A first difficulty is that many of these operators are unbounded. One approach to dealing with this is to pass to resolvants of the operators. Instead, we want to consider the tight binding approximation for a particle in a solid. In this, the solid can be modelled by a tiling; the tiles representing the locations of the atoms so that congruent arrangements are represented by congruent patches in the tiling. The particle motion becomes discrete. The particle hops from tile to tile. The Hilbert space of wave functions is replaced by the space of square summable functions on the set of tiles. This has two immediate consequences. First, (absolute) position is described by a tile in the tiling and second, momentum — usually thought of as a generator of translation — has to be replaced by finite translation (or strictly speaking, its difference with the identity). However, as a consequence of locality of interaction, observables like the potential, which are independent of momentum, depend only on the position of the particle (i.e. a tile) inside a patch whose position in the tiling doesn’t matter. (The larger the interaction radius, the larger the patch.) More technically, let P be a patch and t be a tile in P. Then the momentum-independent observables will be functions of the e[P, t, t], operators which describe whether the particle is at t in a patch which is a translate of P. Now, suppose we consider a patch, P in T, consisting of a pair of adjacent tiles (meaning their intersection is codimension one) t_{1}, t_{2}. Our operator e[{t_{1}, t_{2}}, t_{1}, t_{2}] represents the operator associated with the transition from a tile of type t_{2} to an adjacent one of type t_{1} in all patches which are translations of P. It is not a unitary, but rather a partial isometry. It can be regarded as a “partial translation”; partial in the sense that its domain corresponds only to those tiles which are translates of t_{2} in the translate of P. These partial translations are the operators which replace momentum. The C^{∗}- algebra these generate is exactly our algebra A_{T}. A similar construction has been given by Bellissard [Be2, BCL] for the case of standard tilings obtained from the projection method.

There is another approach which comes from the ideas of disordered systems. This has been developed principally by J. Bellissard [Be2]. The idea is to begin with a bounded operator A acting on the Hilbert space H = L^{2}(ℝ^{d}), which should be thought of as a bounded function of the Hamiltonian for our particle. There is a natural action of ℝ^{d} on this same Hilbert space via translations. We use V_{x} to denote the unitary operator

(V_{x}ξ)(y) = ξ(y − x),

for any ξ in H, x and y in ℝ^{d}.

One considers the set of translations of A under conjugation by this unitary representation of ℝ^{d} and its closure in the strong operator topology. This we define to be the strong operator hull of A

Hull(A) = {V_{x}^{∗}AV_{x}|x ∈ ℝ^{d}}^{−SOT}

(Here, SOT refers to convergence in the strong operator topology on B(H). We recall that a sequence of operators, A_{n}, converges to an operator A in the strong operator topology in ∥A_{n}ξ − Aξ∥ converges to zero, for every vector ξ in (H).)

The idea is to think of measures on Hull(A) as probabilities of the different translates of A. Now, one can view Hull(A) and the action of ℝ^{d} on it as a dynamical system and perform with it the same constructions we did with (Ω_{T} , ℝ^{d}). In fact, in many cases one can show that these dynamical systems are conjugate, provided the operator A reflects the structure of the tiling (e.g. by being quasiperiodic with respect to the tiling), but to make the last statement precise in general is still partly an open problem. The analogous approach works also in the tight binding approximation if the tiling can be identified with an (amenable) discrete group which plays the role of ℝ^{d}.

7. K-theory for C^{∗}-algebras

The subject of K-theory has revolutionized the subject of C^{∗}-algebras in the past twenty-five years. For longer discussions on the matter, we refer the reader to [Da, Bl, W-O].

Let A be a C^{∗}-algebra with unit. (The non-unital case is a minor but annoying adaptation.) There are Abelian groups K_{0}(A) and K_{1}(A) associated to A. For separable C^{∗}-algebras, such as all those appearing from tilings, these groups are countable. For physics, K_{0}(A) seems the more interesting; it is basically a calculus for dealing with the projections in the C^{∗}-algebra. If a self-adjoint operator has a spectrum which may be decomposed into disjoint closed pieces, the spectral projections for the pieces determine elements in K_{0}(A). In addition, the simple notion that projections in a C^{∗}-algebra may be compared (determined by containment of their ranges, if they are operators acting on a Hilbert space) produces a natural pre-order on K_{0}(A). In most of our examples here, this seems to be an actual order. This makes K_{0}(A) a rather rich invariant.

To define K_{0}(A), we proceed (in a rather heuristic fashion) as follows. We want to look at all projections or self-adjoint idempotents in A. That is,

P_{1}(A) = {p ∈ A | p^{2} = p = p^{∗}} .

Two are equivalent if they are similar, that is

p ≈ q if p = uqu^{−1},

for some invertible u in A. Two projections p and q are called orthogonal if pq = 0, which implies qp = 0 also. In this case, p + q is again a projection. This definition can be extended to equivalence classes:

[p] + [q] = [p + q], if pq = 0.

We face the question, given two equivalence classes, whether we can find an orthogonal pair of representatives? This cannot always be done (suppose one is the class of the identity!), but we can solve the problem as follows. Let

P (A) = {p | p ∈ M_{n}(A), for some n, p^{2} = p = p^{∗}} ,

where M_{n}(A) denotes the n × n matrices with entries from A. For each n, M_{n}(A) is a C^{∗}-algebra. Here, we implicitly assume M_{n}(A) ⊂ M_{n+1}(A) by identifying (a_{ij}) and

(\begin{matrix}a_{ij} & 0 ⋮ 0 \\ 0 … 0 & 0 \end{matrix}) .

We extend the definition of ≈ to M_{n}(A). Now if p and q are in M_{n}(A), p^{2} = p = p^{∗},

q^{2} = q = q^{∗}, regard both in M_{2n}(A), where q = (\begin{matrix}q & 0 \\ 0 & 0 \end{matrix}) is similar to (\begin{matrix}0 & 0 \\ 0 & q \end{matrix}) which

is orthogonal to p = (\begin{matrix}p & 0 \\ 0 & 0 \end{matrix}). So

[p] + [q] = [(\begin{matrix}p & 0 \\ 0 & q \end{matrix})] .

We are on our way to turning P (A)/ ≈ into an Abelian group. At the moment we have a semigroup with identity (p = 0). The remainder of the construction (usually referred to as the Grothendieck group) is standard. The first problem is that our semigroup may not have cancellation. We define

p ∼ q if (\begin{matrix}p & 0 \\ 0 & 1_{k} \end{matrix}) ≈ (\begin{matrix}q & 0 \\ 0 & 1_{k} \end{matrix}) ,

for some k, 1_{k} denotes the multiplicative identity in M_{k}(A). Then P (A)/ ∼ is a semigroup with an identity and cancellation, but perhaps no inverses. Then

K_{0}(A) = {[p] − [q] | p, q ∈ P (A)}

is all formal differences. The semi-group P (A)/ ∼ appears in K_{0}(A) as

K_{0}(A)^{+} = {[p] − [0] | p ∈ P (A)}

which is a generating cone. If K_{0}(A)^{+} ∩ −K_{0}(A)^{+} = {0} then we may define an order by x ≥ y if and only if x − y ∈ K_{0}(A)^{+}.

Let us compute this for the simplest of all C^{∗}-algebras, the complex numbers. In fact, this will give us some useful insights for later. Let T r denote the trace on M_{n}(ℂ) : T r(a) = ∑_{i} a_{ii}. For a projection p in M_{n}(ℂ), T r(p) is the rank of p, hence an integer. (Observe that, if we view p in M_{n}(ℂ) or M_{n+1}(ℂ), its trace is the same.) Now trace has several important properties. It is invariant under similarity. Hence it is well-defined on P (A)/ ≈. It is additive and hence well-defined on P (A)/ ∼ and is, in fact, a morphism of semigroups. Finally, two projections in M_{n}(ℂ) are similar if and only if they have the same rank or trace. Thus T r induces an isomorphism

T̂ r : K_{0}(ℂ) → ℤ : T̂ r ([p] − [q]) = T r(p) − T r(q).

Another nice feature of T r is that it is positive T r(a^{∗}a) ≥ 0 for all a in M_{n}(ℂ). So T r(p) = T r(p^{∗}p) ≥ 0. This means that T̂ r is a homomorphism of ordered groups (usual order on ℤ) and, in this case, is actually an order isomorphism.

The idea of using the trace on M_{n}(ℂ) is something which can be applied to many more general C^{∗}-algebras. If A is any unital C^{∗}-algebra, a trace, τ, on A is a linear functional τ : A → ℂ such that

(i) τ(ab) = τ(ba), for all a, b in A, (ii) τ(1) = 1 (iii) τ(a^{∗}a) ≥ 0, for all a in A.

Given such a functional, we can define a group homomorphism

τ̂ : K_{0}(A) → ℝ

by

τ̂(p) = ∑_{i=1}^{n} τ(p_{ii}),

for p in M_{n}(A), p^{2} = p = p^{∗}. The fact that similar projections have the same trace follows from (i) above. The rest of the argument that τ̂ is a well-defined group homomorphism is exactly as for the complex numbers. Also, condition (iii) ensures that τ̂ is positive:

τ̂ (K_{0}(A)^{+}) ⊂ [0, ∞).

The two important differences from the special case of M_{n}(ℂ) are that τ̂ may not be integer valued in general, and that it need not be injective.

We will briefly discuss the existence of such functionals for our C^{∗}-algebras C^{∗}(Ω_{T} , ℝ^{d}) and A_{T} associated to a minimal aperiodic tiling, T. For the former algebra, the amenability of ℝ^{d} implies the existence of a probability measure μ on Ω_{T} which is invariant under the action of ℝ^{d}. We can then define a functional on C_{c}(Ω_{T} × ℝ^{d}) by

τ(f) = ∫_{Ω} f(T′, 0)dμ(T′)

for f in C_{c}(Ω_{T} × ℝ^{d}).

This has the correct positivity and trace properties, but some subtleties arise because it does not extend to a continuous linear functional on the completion of C_{c}(Ω_{T} × ℝ^{d}), which is C^{∗}(Ω_{T} , ℝ^{d}). This can still be useful, as it is often finite on the projections in the algebra.

For substitution systems satisfying our earlier hypotheses, there is a natural choice for such a measure, namely the measure which maximizes the entropy of the transformation or the so-called Bowen measure.

If we look at situation for A_{T}, we want to do something similar on the equivalence relation R_{punc}. We say a measure ν on Ω_{punc} is R_{punc}-invariant if, for any open set E in R_{punc} such that the two canonical projection maps from E to Ω_{punc},

r(T_{1}, T_{2}) = T_{1}, s(T_{1}, T_{2}) = T_{2}

are local homeomorhisms to their images, then we have

ν(r(E)) = ν(s(E)).

Using the notation of section 4, this is equivalent to saying that

ν(U(P, t_{1})) = ν(U(P, t_{2})),

for any patch P and any two tiles t_{1}, t_{2} in P.

From such a measure we may construct a functional on C_{c}(R_{punc}) by setting

τ(f) = ∫_{Ω_{punc}} f(T′, T′)dν(T′)

for f in C_{c}(R_{punc}). In terms of our earlier description of the generators of A_{T}, this means

τ(e[P, t_{1}, t_{2}]) = \{ \begin{matrix}ν(U(P, t_{1})) & if t_{1} = t_{2} \\ 0 & if t_{1} ≠ t_{2} \end{matrix}

In this case, the functional will extend continuously to A_{T} and have all the desired properties. Again for substitution tilings, the situation is quite good. Again one takes the Bowen measure and uses the fact that it will decompose into a product measure in the local coordinates. The local contracting coordinate will contain Ω_{punc} and the measure on this will have the desired properties.

For more information on the existence and uniqueness of such invariant measures, see [Kel1, Kel2].

Let us turn briefly to the group K_{1}(A). In this case, our interest is in the invertible elements of A modulo homotopy. We let

U_{n}(A) = {u ∈ M_{n}(A) | u is invertible}

and set

u ∼ v in U_{n}(A)

if there is a continuous path u_{t}, 0 ≤ t ≤ 1 in U_{n}(A) with u_{0} = u, u_{1} = v. We also regard U_{n}(A) ⊂ U_{n+1}(A) by equating a and

(\begin{matrix}a & 0 0 ⋮ \\ 0 … 0 & 1 \end{matrix}) .

The group structure is multiplication. It is a standard calculation to show that, for u, v in U_{n}(A),

(\begin{matrix}uv & 0 \\ 0 & 1 \end{matrix}) , (\begin{matrix}u & 0 \\ 0 & v \end{matrix}) , (\begin{matrix}vu & 0 \\ 0 & 1 \end{matrix})

are all homotopic in U_{2n}(A). This shows that we could have also defined the product by direct sum and that our group operation is commutative. K_{1}(A) is defined as the union of the U_{n}(A)/ ∼.

For any complex, invertible matrix a it is quite easy to construct a path of invertible matrices from a to 1. It follows that K_{1}(ℂ) is the trivial group.

8. Gap-labelling

We want to discuss the relevance to physics of the K-theory of the C^{∗}-algebras which we are discussing, particularly A_{T}. This is summarized by the term “gaplabelling”, which we will explain. A more thorough treatment can be found in [Be2, Kel1]. The one-dimensional case is treated in [BBG].

Suppose that H is the Hamiltonian of a particle moving in our solid which we have modelled by a tiling. More accurately, suppose H is the Hamiltonian in our tight-binding approximation. This means it will be a bounded operator and will lie in our C^{∗}-algebra A_{T}. Its spectrum is a bounded subset of ℝ. A maximal connected subset of its complement in ℝ is an open interval which is called a gap. We let Gap(H) denote the set of all gaps of H. Notice that the gaps are naturally ordered like energy on the real line. As the spectrum is bounded, there is an unbounded gap of the form (−∞, a) and an unbounded gap of the form (b, ∞). These we denote by −∞ and ∞, respectively. For any two gaps, g_{1} < g_{2}, the spectral projection of the operator H associated with the spectrum between g_{1} and g_{2} is an element of the C^{∗}-algebra, since it is the result of an application of a function which is continuous of the spectrum of H. For a single gap g, we let P_{g} denote the spectral projection of the interval from −∞ to g. The gap-labelling is based on the map

g ∈ Gap(H) ⟶ [P_{g}] ∈ K_{0}(A_{T})

and we call [P_{g}] a label for the gap g. Notice the following properties: • [P_{−∞}] = [0]

• [P_{∞}] = [1]

• g_{1} < g_{2} implies [P_{1}] < [P_{2}]

• The label of a gap is a topological invariant in that, if we perturb H along a norm continuous path in such a way that the gap does not dissappear, then the label does not change.

The third property ensures that the labelling is injective. If we can compute the K-theory of A_{T}, we have a list of labels for the gaps in the spectrum of H, even if we cannot exactly determine the spectrum.

Suppose further that we have a normalized trace τ on our C^{∗}-algebra of observables A_{T}. As we noted before, this induces a map, τ̂ from K_{0}(A_{T}) to the real numbers and we may apply this to our gap-labelling scheme. So to any gap g ∈ Gap(H), we associate the real number

τ̂([P_{g}]) = τ(P_{g}).

This labelling is the most interesting for physics. If we use the trace which is the trace per unit volume, then this is the density of eigenstates integrated up to the gap. This density of states is accessible to physical experiments. With this choice of trace, we call τ̂(K_{0}(A_{T})) the gap-labelling group. It is often smaller and easier to compute than the K_{0} group itself. It is an open problem to find a physical interpretation for the elements of the kernel of τ̂.

There is no general reason why, for a specific operator H, g ⟶ τ̂([P_{g}]) should map onto the elements in τ̂(K_{0}(A_{T})) between 0 and 1. In one dimension one has found many examples for which this is the case but in higher dimensions one does not expect this.

Let us remark why the choice of C^{∗}-algebra A_{T} is important. We have already argued that it is the C^{∗}-algebra which contains the Hamitonian, H, we are interested in. We could, in fact, just use the C^{∗}-algebra generated by H. This is a commutative algebra isomorphic to the continuous functions on the spectrum of H. This is something which we were not very optimistic about computing in the first place. With A_{T} as our choice of C^{∗}-algebra, the computation of the range of our labelling scheme, that is the gap-labelling group, is actually independent of the operator H. It is an invariant which characterizes the influence of the structure of the space on the spectrum of an operator and its density of states.

Baake etal. have observed phenomena in other areas of physics which resemble the gap-labelling of Schrödinger operators [BGJ, GrBa]. Although it is not clear how these are related to the K-theory of some C^{∗}-algebra we mention one of these, namely the distribution of zeros for the partition function of a classical quasiperiodic Ising chain in a constant magnetic field. To explain this a little bit consider a one dimensional tiling, i.e. an infinite sequence of intervals, and put spins at the points where the intervals touch. The spins interact with the external magnetic field in the usual way but the constants of interaction between nearest neighbours depend on the interval (e.g. are proportional to its length) which lies between the two spins. One then is interested in the zeroes of the partition function as a function of the strength h of the external magnetic field, or more precisely as a function of z = e^{βh} with β proportional to the inverse of the temperature. It is known that these zeroes lie all on the unit circle. Consider now the integrated density of zeroes, that is the integral of the density of zeros over a segment of the circle starting at the real line. The surprising observation which has been made for the simplest 1-dimensional substitution tilings is that the dependence of this integrated density of zeroes on the length of the segment looks like the devil’s staircase given by the integrated density of states (as a function of energy) of a typical tight binding operator on the tiling. The values of the integrated density of zeroes at points where it is constant seem to belong to the gap-labelling group of the tiling.

9. K-theory of the C^{∗}-algebras of tilings

We begin with a minimal aperiodic tiling T. We first construct two C^{∗}- algebras: C^{∗}(Ω_{T} , ℝ^{d}) and A_{T} and we then want to compute their K-theories. Since these C^{∗}-algebras are strongly Morita equivalent, the answers are the same. But the rather different views we have of the two will provide different information.

Let us begin with C^{∗}(Ω_{T} , ℝ^{d}). The careful reader will have noticed little to recommend this algebra so far. We have done no computations involving its elements. (As we are about to ask “what are the projections in this algebra?”, one might be worried by the fact that we haven’t yet written one down. Actually, we won’t.) The biggest single advantage of C^{∗}(Ω_{T} , ℝ^{d}) is the following theorem of Connes.

Theorem 9.1. [Bl, Co1]

K_{i} (C^{∗}(Ω_{T} , ℝ^{d})) ≅ K_{i−d} (C (Ω_{T}))
≅ K^{i−d} (Ω_{T}) ,

where K^{i−d} is topological K-theory, and i − d is interpreted mod(2).

The result has nothing particular to do with tilings; it is simply a statement about ℝ^{d}-actions on spaces (or even on C^{∗}-algebras). It requires no hypotheses of aperiodicity or minimality. Connes originally referred to this as an analogue of the Thom isomorphism which states that if E is a vector bundle over a space X, then K^{∗}(E) ≅ K^{∗−d}(X), where d is the dimension of E. That is, the K-theory of E is independent of how E twists over X and it is the same for all vector bundles of a fixed dimension. In our situation of ℝ^{d} acting on Ω_{T}, Connes’ theorem says that the K-theory is independent of the action. Recall from Section 4 that if ℝ^{d} acts trivially, then the C^{∗}-algebra is isomorphic to C_{0}(Ω_{T} × ℝ^{d}). Finally,

K_{i} (C_{0} (Ω_{T} × ℝ^{d})) ≅ K_{i−d} (C(Ω_{T}))

is the famous Bott periodicity result. (See both 1.6.4 and 9.1 of [Bl].) So Connes’ result leaves us with the problem of understanding the topology of Ω. One small word of warning; Connes’ isomorphism, like much of the machinery of K-theory, does \underline{not} respect the order structure on K_{0}.

We are left with the problem of computing the K-theory of the space Ω_{T}. For this, we restrict our attention to substitution tiling systems. In this case, we will make use of Theorem 2.1 which expresses the space Ω as an inverse limit. We also use the fact that K-theory is continuous in the sense that the K-theory of an inverse limit of a sequence of topological spaces is isomorphic to the direct limit of their K-theory groups. Putting this together, we obtain the following.

Theorem 9.2. [AP] For a substitution tiling system satisfying our earlier hypotheses, we have

K_{i}(C^{∗}(Ω, ℝ^{d})) = lim_{→} K^{i−d}(Γ) ⟶ K^{i−d}(Γ) ⟶ K^{i−d}(Γ) ⟶ ….

It is important to remember that the space Γ is fundamentally simpler than Ω. In many examples arising from polygonal tiling schemes, it has the structure of a finite cell complex. In practical terms, this allows for the computation of the K-theory of the C^{∗}-algebras C^{∗}(Ω, ℝ^{d}). This is carried out completely for several examples, including the Penrose tilings, in [AP].

As a final remark, we repeat that the method we have provided for computing K_{i} (C^{∗}(Ω_{T} , ℝ^{d})) says nothing about the order on the K_{0}-group. This is unfortunate, since this is a valuable part of the data.

We turn to our other C^{∗}-algebra, A_{T}, where T is generated as above from a substitution system. Again we make the hypotheses that the substitution is primitive, the map ω is injective and the tiling satisfies the finite pattern condition.

The first step in constructing the discrete hull is to select some punctures for our tiles. We will make the assumption (and we lose no generality in doing so) that each of our prototiles contains the origin in its interior. We then select the origin as our puncture.

Recall that if P is a patch in T and t is in P, then U(P, t) is a clopen set in Ω_{punc}, consisting of all tilings with a copy of t ∈ P at the origin. Recall also, our description of A_{T} in Section 4 as being generated by elements e [P, t_{1}, t_{2}], where (P, t_{1}, t_{2}) is a doubly pointed pattern class.

We will discuss a method for the computation of K_{0}(A_{T}) in [Kel1, Kel2]. (We will have nothing to say about K_{1}.)

Recall that the subalgebra generated by the elements e[P, t, t] is isomorphic to C(Ω_{punc}). Our first observation is that the K-theory of this C^{∗}-algebra is computable. If (f_{ij}) is any matrix with elements from C(Ω_{punc}) which is a projection, then its trace, ∑ f_{ii} is a continuous integer-valued function on Ω_{punc}. Just as the case for a matrix algebra, this trace map extends to an isomorphism from

K_{0}(C(Ω_{punc})) ⟶^{≅} C(Ω_{punc}, ℤ),

where the range is the continuous integer-valued functions with pointwise addition. The fact that this is an isomorphism depends on the space Ω_{punc} being totally disconnected. Such a result is certainly not true in higher dimensions. Observe that the map sends the projection e[P, t, t] to the characteristic function of the set U(P, t).

The inclusion of C(Ω_{punc}) in A_{T} induces a map on K_{0} groups. Unlike the map on algebras it is far from injective. To see this, suppose [P, t_{1}, t_{2}] is a doubly pointed pattern class. Let v = e [P, t_{1}, t_{2}] and

u = ( \begin{matrix}v & 1 − vv^{∗} \\ 1 − v^{∗}v & v^{∗} \end{matrix} )

be in M_{2}(A_{T}). It is easy to check that u^{−1} = u^{∗} and that

u ( \begin{matrix}e [P, t_{1}, t_{1}] & 0 \\ 0 & 0 \end{matrix} ) u^{−1} = ( \begin{matrix}e [P, t_{2}, t_{2}] & 0 \\ 0 & 0 \end{matrix} )

so that e [P, t_{1}, t_{1}] and e [P, t_{2}, t_{2}] now determine the same element in K_{0}(A_{T}), while the characteristic function of U(P, t_{1}) and U(P, t_{2}) are distinct elements in K_{0} (C (Ω_{punc})).

Motivated by this observation, we let E_{T} be the subgroup of C (Ω_{punc}, ℤ) generated by all elements of the form

χ_{U(P,t_{1})} − χ_{U(P,t_{2})},

where [P, t_{1}, t_{2}] is a doubly pointed pattern class. We call

H(T) = C (Ω_{punc}, ℤ) /E_{T}

the integer group of coinvariants of T. It is an invariant of the tiling T and R_{punc} (but not of A_{T}).

It is a rather interesting question to ask how close this is to K_{0}(A_{T}). We have seen that there is a homomorphism of C (Ω_{punc}, ℤ) to K_{0}(A_{T}) whose kernel contains E_{T}. Could the kernel be larger? In fact, in nice situations it is not. Is the map onto? That is, can one find projections in A_{T} other than the e[P, t, t]’s? (In the case of a matrix algebra, this amounts to the observation that every projection is similar to a diagonal one.) In fact, there are other, less obvious, projections in many cases.

Suppose for a moment that we are dealing with a situation where all of our tiles are unit squares, but carry labels so that T is minimal and aperiodic. We can put our punctures in the centre of each tile. Then there is an obvious action of ℤ^{2} on Ω_{punc} so that the map

Ω_{punc} × ℤ^{2} → R_{punc}

defined by (T, ν) → (T, T + ν) is a homeomorphism. In this case,

A_{T} = C^{∗}(R_{punc}) = C^{∗} (Ω_{punc}, ℤ^{d})

can be constructed very much like the case for C^{∗} (Ω_{T} , ℝ^{d}) of Section 4. See [Pe, Da] for more details. Moreover, there is machinery which will compute the K-theory (again without order) of such a C^{∗}-algebra. The case d = 1 was a great breakthrough of Pimsner and Voiculescu [Bl, Da, W-O]. It can be extended to higher values of d, although spectral sequences become involved in the calculations. The case of 2-dimensional square tilings has been carefully analysed by van Elst [vEl] and later Forrest and Hunton [FH] have investigated the K-theory of C^{∗}- algebras associated with actions of ℤ^{d} on Cantor sets for general d.

As a sample, in the case d = 2, the result shows

K_{0}(A_{T}) ≅ C (Ω_{punc}, ℤ) /E_{T} ⊕ ℤ.

Let us take a moment to explain the ℤ-term. We let u and v denote the characteristic functions of the graphs of the two maps

T′ → T′ + (1, 0)
T′ → T′ + (0, 1).

These graphs are compact open sets in R_{punc}, so u and v are in A_{T}. They also commute and the C^{∗}-algebra they generate, denoted by C^{∗}(u, v), is isomorphic to C(𝕋^{2}), the continuous functions on the 2-torus. This C^{∗}-algebra contains a projection in M_{2} (C(𝕋^{2})) which is rank one at each point of 𝕋^{2}, but not similar

to (\begin{matrix}1 & 0 \\ 0 & 0 \end{matrix}). (See [W-O] for further details.) The similarity exists pointwise, but

cannot be made continuous. So this projection (or rather its formal difference with

(\begin{matrix}1 & 0 \\ 0 & 0 \end{matrix})) generates the ℤ in K_{0}(A_{T}). It is really present because of the fact the

tiling is in ℝ^{2}. It has little to do with the tiling itself. (To make this statement a little more precise, the intersection of C (Ω_{punc}) and C^{∗}(u, v) in A_{T} is just the scalar multiples of the identity.)

Of course, much of the interest in aperiodic tilings comes from the fact that the tiles aren’t always squares. However, it is shown in [Kel2] that the same techniques as above can be applied much more generally. We say that the tiling T is a decoration of ℤ^{d} if we may choose a set of punctures for some (but perhaps not all) tile types such that there is an action (denoted by ·) of ℤ^{d} on Ω_{punc′} (new punctures!) by homeomorphism such that the map

(T′, x) ∈ Ω_{punc′} × ℤ^{d} ⟶ (T′, x · T′) ∈ R_{punc′}

is a homeomorphism. The topology on Ω_{punc′} × ℤ^{d} is the product topology, while that on R_{punc′} is as defined earlier.

The first question is naturally: how much change do we make in A_{T} by selecting only a subset of tile types to have punctures? Let

P = ∑ e ({t_{i}} , t_{i}, t_{i}) ,

where the sum is over all tile types, t_{i}, having a puncture in the new system. Then the C^{∗}-algebra of the new R_{punc′} is isomorphic to P A_{T} P and P is a projection. Thus, the new C^{∗}-algebra is strongly Morita equivalent to our old one.

The second important question is how often does this situation arise? In fact, this is possible for any tiling obtained by the generalized grid method [SSL], including the Penrose tilings and the Ammann-Beenker tilings [Kel2].

Also, in [FHK], this point of view is developed completely for tilings which are obtained by the so-called projection method. It is shown that generically, there is a natural choice of transversal so that the C^{∗}-algebra, C^{∗}(Ω, ℝ^{d}) is strongly Morita equivalent to the crossed product arising from an action of ℤ^{d} on this transversal.

At this point, we have a description of the K_{0} group of A_{T} in terms of our integer group of coinvariants. Unfortunately, we do not yet have a very good grasp of this invariant. In particular, we want to be able to compute it in specific cases. We now restrict our attention to the case of substitution tilings satisfying the condition of section 3.

To obtain a better description, we will introduce a new C^{∗}-algebra, AF_{T}, which will be intermediate

C(Ω_{punc}) ⊂ AF_{T} ⊂ A_{T}

This new algebra will be from a special class of algebras called AF -algebras (for approximately finite dimensional), which are both well-understood and rather rich [Bl, Da, W-O, Ef]. In particular, the K-theory of this C^{∗}-algebra will be computable (including the order!) and give us a better approximation to that of A_{T}.

Our analysis will now proceed as follows. We will define a sequence of C^{∗}- subalgebras of A_{T}. In fact, these will be nested so that the completion of their union is also a C^{∗}-subalgebra. Moreover, each one of them will be finite dimensional as a vector space and isomorphic to a finite direct sum of matrix algebras. Of course, the dimension and the size of the matrix algebras will grow as we pass out in the sequence. The closure of their union is a so-called “approximately finite dimensional” or AF -algebra, which will be our AF_{T}.

We begin with a small observation. Recall our notation from section 5: for a patch, P and tile t in P, we let U(P, t) denote the set of all tilings T in Ω_{punc} containing P and with t covering the origin. Suppose that p and p′ are two prototiles and x and x′ are points in their respective interiors. Then the sets U({p}, p) − x and U({p′}, p′) − x′ are disjoint in Ω, unless p = p′ and x = x′. Since ω is injective on Ω, the same is true of the sets ω^{N}(U({p}, p))−λ^{N}x and ω^{N}(U({p′}, p′))−λ^{N}x′, for any positive integer N.

We are now ready to begin our definition of the sequence of C^{∗}- subalgebras. Let N be any non-negative integer. For each prototile p, let P unc(N, p) denote the set of all the punctures in ω^{N}(p). Now, for each pair x, y in P unc(N, p), we define the set

E_{p}^{N}(x, y) = {(ω^{N}(T) − x, ω^{N}(T) − y) | T ∈ U({p}, p)}

We note the following properties of this set. First, for any T in U({p}, p), the tilings ω^{N}(T) − x and ω^{N}(T) − y are both in Ω_{punc} and the second is the translate of the first by x − y. This means our set E_{p}^{N}(x, y) is contained in R_{T}. The fact that it is a clopen subset is easy to verify. So we define e_{p}^{N}(x, y) to be the characteristic function of E_{p}^{N}(x, y), which is then an element of A_{T}.

The following relations follow easily from the first of our observation above. For any prototiles p and p′, punctures x, y in P unc(N, p) and x′, y′ in P unc(N, p′), we have

e_{p}^{N}(x, y)e_{p′}^{N}(x′, y′) = 0,  if p ≠ p′
e_{p}^{N}(x, y)e_{p′}^{N}(x′, y′) = 0,  if p = p′ and y ≠ x′
e_{p}^{N}(x, y)e_{p′}^{N}(x′, y′) = e_{p}^{N}(x, y′) if p = p′ and y = x′.

The second and third relations mean that if we fix both N and p and define

A_{N,p} = span{e_{p}^{N}(x, y) | x, y ∈ P unc(N, p)}

then A_{N,p} is isomorphic to the algebra of complex n × n matrices, where n is the number of punctures in ω^{N}(p). Moreover the first relation means that these algebras, for different values of p, are orthogonal. So we define

A_{N} = span{e_{p}^{N}(x, y) | p a prototile and x, y ∈ P unc(N, p)}

and we have

A_{N} = ⨁_{p} A_{N,p}.

Observe that the number of matrix summands is the number of prototiles and this is independent of N. Of course, the sizes of the matices, which is the number of punctures in the inflations of the prototile, will grow with N.

We want to show that, for all N, we have A_{N} ⊆ A_{N+1}. For any prototile p, we let I_{p} denote the set of all pairs (p′, x′), where p′ is a prototile and x′ is in ℝ^{d} satisfying p + x′ ∈ ω(p′). The first step is to verify that

U({p}, p) = ⋃_{(p′,x′)∈I_{p}} ω(U({p′}, p′)) − x′

and the sets in the union are pairwise disjoint. From this it follows that

e_{p}^{0}(0, 0) = ∑_{(p′,x′)∈I_{p}} e_{p′}^{1}(x′, x′).

If we apply the map ω^{N} to the equality of sets above, we also obtain

e_{p}^{N}(x, y) = ∑_{(p′,x′)∈I_{p}} e_{p′}^{N+1}(λ^{N}x′ + x, λ^{N}x′ + y)

for any N and x, y in P unc(N, p). This equation then shows the inclusion of A_{N} in A_{N+1}.

We note that the identity of A_{T} is

∑_{p} e_{p}^{0}(0, 0)

is in A_{0}, hence in all A_{N}. One verifies that the C^{∗}-algebra generated by the elements e_{p}^{N}(x, x), as N, p and x vary is the commutative C^{∗}-algebra C(Ω_{punc}).

As we mentioned above, we can form the union of this sequence of C^{∗}- algebras, which is a subalgebra of A_{T}, but will not be closed. Its closure is a C^{∗}-subalgebra, which we denote by AF_{T}. It is an approximately finite-dimensional C^{∗}-algebra, or AF -algebra. We have seen in the construction that the elements generating this AF -algebra are functions on R_{punc}, just as the elements of A_{T} are. However, they are non-zero only on a proper sub-equivalence relation of R_{punc}.

Having given a description of the algebra AF_{T}, we want to show how its Ktheory may be computed directly in the following manner [Ef, Bl, W-O, Da].

As each A_{N} is contained in A_{N+1}, the inclusion induces a map

K_{0}(A_{N}) ⟶ K_{0}(A_{N+1})

which is a (not necesarily injective) positive group homomorphism. Finally, it is a theorem that, since AF_{T} is the closure of the union of the A_{N}’s, we have

K_{0}(AF_{T}) = lim_{→} K_{0}(A_{1}) ⟶ K_{0}(A_{2}) ⟶ …

where the limit is taken in the category of ordered Abelian groups.

In our case, this is really quite tractible. First of all, recall our calculation from section 7 of the K-theory of the complex numbers. The same calculation shows that, for any n,

K_{0}(M_{n}) ≅ ℤ, K_{1}(M_{n}) ≅ 0.

and that the K_{0} group is generated by the class of any rank one projection in M_{n}. We apply this to A_{N,p}, for any N and prototile p to assert that the group K_{0}(A_{n,p}) is generated by the class of e_{p}^{N}(x, x), where x is any puncture in P unc(N, p). Now the K-theory of a direct sum of C^{∗}-algebras is the direct sum of their K-theories and so

K_{0}(A_{N}) ≅ ⨁_{p} K_{0}(A_{N,p}) ≅ ℤ^{n},

where n is the number of prototiles. The next step is to understand the map induced on K-theory by the inclusion of A_{N} into A_{N+1}. Fix a prototile p and consider the generator [e_{p}^{N}(x, x)] of the pth summand in K_{0}(A_{N}). (Here we have chosen some puncture x in P unc(N, p).) The formula above in the case of x = y becomes

e_{p}^{N}(x, x) = ∑_{(p′,x′)∈I_{p}} e_{p′}^{N+1}(λ^{N}x′ + x, λ^{N}x′ + x)

Each element in the sum on the right is a rank one projection in one of the matrix summands of A_{N+1}. In fact, in the p′-summand, it is the sum of exactly B(p′, p) rank one projections, where B(p′, p) is the number of occurences of copies of p in ω(p′).

Putting all of this together, we see that K_{0}(AF_{T}) is the inductive limit, in the category of ordered Abelian groups, of the system

ℤ^{n} ⟶^{B} ℤ^{n} ⟶^{B} … (9.1)

Here, each ℤ^{n} is given the standard or simplicial order where an element is positive if and only if each entry is non-negative. The structure of such groups is wellunderstood [Ef, Ha]. There is a unique trace, τ, on the algebra AF_{T} given by

τ(e_{p}^{N}(x, y)) = \{ \begin{matrix}λ^{−N}ξ_{p} & if x = y \\ 0 & if x ≠ y \end{matrix}

where (ξ_{p}) is the Perron-Frobenius normalized eigenvector of the matrix B^{t}. The normalization of ξ is related to the order unit of K_{0}(A_{T}), i.e. determined by the requirement that τ̂([∑_{p} e_{p}^{0}(0, 0)]) = 1. Thus it is ∑_{p} ξ_{p} = 1. It follows that τ̂(K_{0}(AF_{T})) is the subgroup of ℝ generated by λ^{−N}ξ_{p}, where N is a non-negative integer and p is a prototile. It is interesting to note that this depends only on the combinatorics of the substitution, not on the geometry.

Recall that AF_{T} is a subalgebra of A_{T} and the inclusion induces a map on K_{0} groups. The range of the map is exactly the same as the range of the map induced on C(Ω_{punc}), namely the integer group coinvariants H(T). The kernel of the map can be computed and this provides a method for computing H(T) and hence, if d ≤ 2, for K_{0}(A_{T}). This is a long calculation for which we refer the reader to [Kel2]. But what becomes quickly clear is that τ̂ applied to the above kernel is 0, or stated differently

τ̂(H(T)) = τ̂(K_{0}(AF_{T})).

For d = 1 we have K_{0}(A_{T}) = H(T). For d = 2 the above may be combined with results of [vEl] provided T reduces to a decoration of ℤ^{2}. We already mentionned that in that case K_{0}(A_{T}) ≅ H(T) ⊕ ℤ and van Elst has shown (by explicit calculation) that τ̂ evaluated on the second summand ℤ already belongs to τ̂(H(T)). Thus in that case

τ̂(K_{0}(A_{T})) = τ̂(H(T)) = τ̂(K_{0}(AF_{T})) = τ̂(C(Ω_{punc})) (9.2)

which effectively solves the problem of computing the gap labelling group in theses cases: it is the group generated by λ^{−N}ξ_{p}, N a non-negative integer and p a prototile. For more general substitution systems, the last two equalities still hold and it seems reasonable to ask whether the first does also.

We mention that in [Kel2] the same result was stated even for d = 3. It was based, however, on the calculations made in [vEl] for d = 3 and the latter are not correct.

We remark that in the case where the substitution does not force its border, then we must use the method of decorated prototiles mentioned earlier.

10. Example: octagonal tilings

The example we provide, the (undecorated) octagonal tilings, gives us also the opportunity to explain a little of what we had to leave out in the general discussion.

In the common version the tiles of an octagonal tiling are squares and rhombi but to make the substitution unique and simpler we divide the squares into triangles and decorate these triangles in a symmetry breaking way. We call the resulting tiling the triangle version and denote it by T_{3}. This operation yields a mutually locally derivable tiling and thus doesn’t change the ordered K-zero group. It does alter, however, the order unit and we have to be careful about this point when it comes to the gap-labelling group. The substitution of the tiling looks as follows:

Figure 1. Substitution of the octagonal tiling (triangle version).

Not only the above two tiles on the l.h.s. appear in the tiling but also all its rotates around \frac{nπ}{4} and reflections along the boundaries of the tiles, the substitution on these is extended in the obvious way: by symmetry. Thus an octagonal tiling has 20 prototiles: 4 of them congruent to the rhombus, the remaining 16 congruent to the triangle. The substitution is primitive, recognizable and forces its border.

We apply Theorem 9.2 to calculate the K-groups. We start with the calculation of K(Γ). What we haven’t explained in the main text is that K(Γ) is isomorphic to H(Γ), the cohomology of the CW-complex Γ, and that the inductive limit lim_{→} H(Γ) ⟶^{γ} H(Γ) yields the cohomology H(Ω) of Ω and is isomorphic to K(Ω), see [AP]. But let us describe H(Γ). Γ gives rise to a chain complex

0⟶C^{2} ⟶^{∂_{2}} C^{1} ⟶^{∂_{1}} C^{0}⟶0

where C^{k} is the ℤ-module generated by the k-cells of Γ and ∂_{k} the boundary operator. ∂_{k} applied to (a generator corresponding to) a k-cell is a signed sum of (the generators corresponding to) the k − 1-cells which make up its boundary. There is some freedom to choose the signs such a choice corresponding to the choice of an orientation for each cell. H(Γ) is the cohomology of the dual complex.

Recall that the 2-cells of the CW-complex Γ for a 2-dimensional tiling are the (interior of) the prototiles. We get Γ by identifying two edges of two prototiles if we can find two tiles in the tiling, one a translate of the first and the other a translate of the second prototile, such that the two corresponding edges become identical. To determine this for the octagonal tiling requires a little work but since the tiling is of finite pattern type this is feasible. For the result see Figure 2.. We have only drawn three of the prototiles. The remaining 17 can be obtained from the above by rotation around \frac{nπ}{4} . The labels on the edges then change as follows: f_{i} and d_{i} have to be replaced by f_{i+n} and d_{i+n} counting the index modulo 8. Equal label on edges means that they have to be identified. In particular, in contrast to what the above picture suggests the complex is connected (as it should be). Note that the identifications imply that there is only one vertex. This is not a general feature. It implies that ∂_{1} is the zero map. We have indicated a choice of orientation on the edges by an arrow. ∂_{2} applied to a 2-cell, i.e. a prototile, is equal to the signed sum of its edges and we choose its sign to be + if the arrow of the edges points left

Figure 2. CW-complex for the octagonal tiling (triangle version).

around the prototile (otherwise −). Hence the dual ∂′_{2} of ∂_{2} applied to an edge (we may again identify the generators for Hom(Γ, ℤ) with the cells) is the signed sum of the prototiles which contain that edge and the sign is + if the prototile lies left of the edge (w.r.t. the direction of the latter). Thus the dual complex looks like

0 ⟶ ℤ ⟶^{0} ℤ^{16} ⟶^{∂′_{2}} ℤ^{20} ⟶ 0

and ∂′_{2} is the 20 × 16-matrix

(\begin{matrix}1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & −1 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 0 & 0 & 1 & −1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & −1 & 0 & 0 & 0 & 0 & 0 & −1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & −1 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ −1 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & −1 \end{matrix} )

Its rank is 11. Hence H^{0}(Γ) ≅ ℤ, H^{1}(Γ) ≅ ℤ^{5}, and H^{2}(Γ) ≅ ℤ^{9}.

It remains to determine the induced maps H^{k}(Γ) ⟶^{γ_{k}} H^{k}(Γ) and to compute the inductive limit. γ_{2} is the map induced from the map ℤ^{20} ⟶^{B} ℤ^{20} of (9.1) which already appeared for the construction of AF_{T}. It turns out that B it is invertible over ℤ and preserves the image of ∂′_{2}. Therefore the inductive limit H^{2}(Ω) = lim_{⟶} H^{2}(Γ) ⟶^{γ_{2}} H^{2}(Γ) ⟶^{γ_{2}} ⋯ is isomorphic to H^{2}(Γ). With the same reason one obtains K_{0}(AF_{T}) ≅ ℤ^{20}. The map γ_{1} is induced from the substitution map for the edges which can be read off the substitution (Fig. 1) if one adds to the tiles on both sides the labels for the edges. It turns out that γ_{1} is as well invertible over ℤ and it preserves the kernel of ∂′_{2}. Therefore H^{k}(Ω) ≅ H^{k}(Γ) in all degrees (again a result which does not hold in general) and the result above was already final:

H^{0}(Ω) ≅ ℤ, H^{1}(Ω) ≅ ℤ^{5}, H^{2}(Ω) ≅ ℤ^{9}.

Thus K_{0}(A_{T}) ≅ ℤ^{9} ⊕ ℤ (H^{2}(Ω) are the coinvariants) and K_{1}(A_{T}) ≅ ℤ^{5}.

To determine the gap-labelling group we note that the octagonal tilings may as well be constructed with the grid method so that we can apply (9.2). For that we have to compute the Perron-Frobenius eigenvalue λ and a corresponding eigenvector ξ of B^{t}. One finds λ = (1 + \sqrt{2})^{2} and

ξ ∝ (2\sqrt{2}, 2\sqrt{2}, 2\sqrt{2}, 2\sqrt{2}, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1) (10.1)

expressed in a basis in which the first four indices are identified with the rhombi and the remaining sixteen with triangles. The proper normalisation of ξ for the triangle version T_{3} is ∑_{p} ξ_{p} = 1. One finds that the group generated by λ^{−N}ξ_{p}, N non-negative integer and 1 ≤ p ≤ 20 is

τ̂(K_{0}(A_{T_{3}})) = \frac{ℤ + 2\sqrt{2}ℤ}{8(2 + \sqrt{2})}. (10.2)

Looking now at the original version T of the octogaonal tiling by squares and rhombi we have to take a different normalization for ξ into account. It corresponds roughly speaking to giving the triangles only half the weight, i.e. ∑_{p=1}^{12} ξ_{p} = 1, see [Kel3]. With this normalization the gap labelling group becomes

τ̂(K_{0}(A_{T})) = \frac{ℤ + 2\sqrt{2}ℤ}{8(1 + \sqrt{2})}. (10.3)

This is in agreement with [BCL] where the authors have computed τ(C(Ω_{punc})) by determining the measures of the clopen sets which generate the topology of Ω_{punc}. (The formulae (2.2) and (2.3) stated in [Kel3] were incorrectly derived from (10.1) and should be replaced by (10.2) and (10.3).)

We finish with a remark on the approach to calculate the coinvariants with the method developped in [Kel2]. We mentionned that H^{2}(Ω) are the coinvariants which according to the main text can be expressed as a quotient K_{0}(AF_{T})/E where E is the kernel of the map on the K_{0}-groups induced from the embedding AF_{T} ↪ A_{T}. But in fact, the similarity with the above calculation for H^{2}(Ω) is deeper. When it comes to the calculations the only difference between the two approaches is that instead of looking at edges and counting which tiles they separate one considers the doubly pointed patterns which are formed by two neighbouring tiles and counts these tiles. The choice of order for these tiles reflects the choice of orientation for their common edge.

References

[AP] J. E. Anderson and I. F. Putnam, Topological invariants for substitution tilings and their associated C^{∗}-algebras, Ergod. Th. & Dyn. Syst. 18 (1998), 509–537.

[BSJ] M. Baake, M. Schlottmann and P. D. Jarvis, Quasiperiodic tilings with tenfold symmetry and equivalence with respect to local derivability, J. Phys. A 24 (1991), 4637–4654.

[BGJ] M. Baake, U. Grimm and D. Joseph Trace maps, invariants, and some of their applications, Intern. J. Mod. Phys. B 7 (1993), 1527–1550.

[Be1] J. Bellissard, K-theory of C^{∗}-algebras in solid state physics, in: Statistical Mechanics and Field Theory: Mathematical Aspects, eds. T. C. Dorlas, N. M. Hugenholtz and M. Winnik, Lecture Notes in Physics, vol. 257, Springer, Berlin (1986), pp. 99–156.

[Be2] J. Bellissard, Gap labelling theorems for Schrödinger’s Operators, in: From Number Theory to Physics, eds. M. Waldschmidt, P. Moussa, J. M. Luck and C. Itzykson, Springer, Berlin (1993), pp. 539–630.

[BBG] J. Bellissard, A. Bovier and J. M. Ghez, Gap labelling theorems for one dimensional discrete Schrödinger operators, Rev. Math. Phys. 4 (1992), 1–38.

[BCL] J. Bellissard, E. Contensou and A. Legrand, K-théorie des quasi-cristaux, image par la trace: le cas du réseau octogonal, Compte Rend. Acad. Sci. Paris (Série I) 326 (1998), 197–200.

[Bl] B. Blackadar, K-theory for Operator Algebras, MSRI Publications, vol. 5, 2nd ed., Cambridge University Press, Cambridge (1998).

[Co1] A. Connes, An analogue of the Thom isomorphism for crossed products of a C^{∗}-algebra by an action of ℝ, Adv. Math. 39 (1981), 31–55.

[Co2] A. Connes, Non-commutative Geometry, Academic Press, San Diego (1994).

[Da] K. R. Davidson, C^{∗}-algebras by example, Fields Institute Monographs, vol. 6, Amer. Math. Soc., Providence, RI (1996).

[Ef] E. G. Effros, Dimensions and C^{∗}-algebras, CBMS Regional Conf. Ser., vol. 46, Amer. Math. Soc., Providence, RI (1981).

[EH] E. G. Effros and F. Hahn, Locally compact transformation groups and C^{∗}-algebras, Memoirs of the Amer. Math. Soc., vol. 75, Providence, RI (1967).

[vEl] A. van Elst Gap-labelling theorems for Schrödinger operators on the square and cubic lattice , Rev. Math. Phys. 6 (1994), 319–342.

[Fi] P. A. Fillmore, A user’s guide to operator algebras, Wiley, New York (1996).

[FH] A. Forrest and J. Hunton, Cohomolgy and K-theory of commuting homeomorphisms of the Cantor set, Ergod. Th. & Dyn. Syst. 19 (1999) 611–625.

[FHK] A. Forrest, J. Hunton and J. Kellendonk, Projection quasicystals I: toral rotations, II: versus substitutions, III: cohomology, preprints (1998/1999).

[GP] W. Geller and J. Propp, The projective fundamental group of a ℤ^{2}-shift, Ergod. Th. & Dyn. Syst. 15 (1995), 1109–1118.

[GR] E. C. Gootman and J. Rosenberg, A proof of the generalized Effros-Hahn conjecture, Invent. Math. 52 (1979), 283–298.

[GrBa] U. Grimm and M. Baake Aperiodic Ising Models in: The Mathematics of Long Range Aperiodic Order, ed. R.V. Moody, Kluwer, (1997), 199–237.

[GS] B. Grünbaum and G. C. Shephard, Tilings and Patterns, Freeman, New York (1987).

[Ha] D. Handelman, Positive matrices and dimension groups associated with topological Markov chains, J. Operator Th. 6 (1981), 55–74.

[Ja] C. Janot, Quasicrystals - a Primer, 2nd ed., Clarendon Press, Oxford (1994).

[KH] A. Katok and B. Hasselblatt, Introduction to the modern theory of dynamical systems, Encyclopedia of Math. and its applications, Cambridge University Press, Cambridge (1995).

[Kel1] J. Kellendonk, Non-commutative geometry of tilings and gap labelling, Rev. Math. Phys. 7 (1995), 1133–1180.

[Kel2] J. Kellendonk, The local structure of tilings and their integer group of coinvariants, Commun. Math. Phys. 187 (1997), 115–157.

[Kel3] J. Kellendonk, Integer groups of coinvariants associated to octagonal tilings, Fields Insitute Communications 13 (1997), 155–169.

[Ken] R. Kenyon, The construction of self-similar tilings, Geom. Funct. Anal. 6 (1996), 471– 488.

[La] J. C. Lagarius, Geometric models for quasicrystals I. Delone sets of finite type and Geometric models for quasicrystals II. Local rules under isometries, to appear in Discrete and Comp. Geom.

[Mi] J. A. Mingo, C^{∗}-algebras associated with one-dimensional almost periodic tilings, Commun. Math. Phys. 183 (1997), 307–337.

[Mo] S. Mozes, Tilings, substitution systems and dynamical systems generated by them, J. d’Analyse Math. 53 (1989), 139–186.

[MRW] P. S. Muhly, J. N. Renault and D. P. Williams, Equivalence and isomorphism for groupoid C^{∗}-algebras, J. Operator Th. 17 (1987), 3–22.

[Pe] G. K. Pedersen, C^{∗}-algebras and their automorphism groups, Academic Press, London [RW] C. Radin, and M. Wolff, Space tilings and local isomorphism, Geom. Dedicata 42 (1992),

355–360.

[Ren] J. N. Renault, A groupoid approach to C^{∗}-algebras, Lecture Notes in Mathematics, vol. 793, Springer, Berlin (1980).

[Ri1] M. A. Rieffel, Morita equivalence for operator algebras, Proc. Symp. Pure Math. 38 (1982), Part 1, 285–298.

[Ri2] M. A. Rieffel, Lie group convolution algebras as deformation quantizations of linear Poisson structures, Amer. J. Math. 112 (1990), 657–686.

[ER1] E. A. Robinson, Jr., The dynamical theory of tilings and quasicrystallography, in: Ergodic Theory of ℤ^{d}-Actions, eds. M. Pollicott and K. Schmidt, London Math. Soc. Lecture Note Series, Cambridge University Press, Cambridge (1996), pp. ...

[ER2] E. A. Robinson, Jr., The dynamics of Penrose tilings, Trans. Amer. Math. Soc. 384 (1996), 4447–4464.

[Rud] D. J. Rudolph, Markov tilings of ℝ^{d} and representations of ℝ^{d} actions, Contemp. Math. 94 (1989), 271–289.

[Rue] D. Ruelle, Thermodynamic Formalism, Encyclopedia of Mathematics and its Applications, vol. 5, Addison-Wesley, Reading, MA (1978).

[Sm] S. Smale, Differentiable dynamical systems, Bull. Amer. Math. Soc. 73 (1967), 747–817.

[SSL] J.E.S. Socolar, P.J. Steinhardt, and D. Levine. Quasicrystals with arbitrary orientational symmetry, Phys. Rev. B, 32 (1985), 5547–5550.

[So1] B. Solomyak, Dynamics of self-similar tilings, Ergod. Th. & Dyn. Syst. 17 (1997), 695– 738.

[So2] B. Solomyak, Nonperiodicity implies unique composition for self-similar translationally finite tilings, Disc. Comp. Geom. 20 (1998), 265–279.

[StO] P. J. Steinhardt and S. Ostlund (eds.), The Physics of Quasicrystals, World Scientific Press, Singapore (1987).

[W-O] N. E. Wegge-Olsen, K-theory and C^{∗}-algebras, Clarendon Press, Oxford (1993).

[W] R. F. Williams, Expanding attractors, Publ. IHES 43 (1974), 169–203. [Z-M] G. Zeller-Meier, Produits croisés d’une C^{∗}-algebre par un group d’automorphisme, J.

Math. Pures et Appl. 47 (1968), 101–239.

Fachbereich Mathematik, TU Berlin, 10623 Berlin, Germany

    E-mail address: kellen@math.tu-berlin.de

Department of Mathematics and Statistics, University of Victoria, Victoria, BC, V8W 3P4, Canada

    E-mail address: putnam@math.uvic.ca