SUBSTITUTION DYNAMICAL SYSTEMS,

BRATTELI DIAGRAMS AND DIMENSION GROUPS. The present paper explores substitution minimal systems and their relation to stationary Bratteli diagrams and stationary dimension groups. The constructions involved are algorithmic and explicit, and render an effective method to compute an invariant of (ordered) K-theoretic nature for these systems. This new invariant is independent of spectral invariants which have previously been extensively studied. Before we state the main results we give some background.

From Bratteli diagrams to topological dynamics. In 1972 O. Bratteli [Br] introduced special infinite graphs -subsequently called Bratteli diagrams -which conveniently encoded the successive embeddings of an ascending sequence (A n ; n ≥ 0) of finite-dimensional semi-simple algebras over C ("multi-matrix algebras"). The sequence (A n ; n ∈ N) determines a so-called approximately finite-dimensional (AF) C * -algebra. O. Bratteli proved that the equivalence relation on Bratteli diagrams generated by the operation of telescoping is a complete isomorphism invariant for AF-algebras. Inspired by O. Bratteli's results, G. A. Elliott [El] introduced in 1976 the notion of dimension groups. In fact, to a Bratteli diagram is naturally associated a sequence of free abelian groups of finite rank (simplicially ordered) with order-preserving homomorphisms between successive groups. The resulting inductive limit -endowed with the induced ordering -is the dimension group associated to the Bratteli diagram. The K-theoretic underpinning of this notion was soon realized, being in fact order-isomorphic to the (ordered) K 0 -group of the AF-algebra determined by the Bratteli diagram. Bratteli's result could now be given a more succinct formulation: a complete isomorphism invariant for AF-algebras is the associated dimension group (as an ordered group with distinguished order unit). Then, in 1980, E. G. Effros, D. Handelman and C.-L. Shen [EHS] gave an axiomatic characterization of dimension groups, namely as countable, ordered abelian groups which are unperforated and satisfy the Riesz interpolation property. Their result made it possible to easily produce explicit examples of dimension groups and to make certain inroads into the classification problem. From a different direction came the extremely fruitful idea of A. M. Vershik [Ve] to associate dynamics ("adic transformations") with Bratteli diagrams ("Markov compacta") by introducing a lexicographic ordering on the infinite paths of the diagram. By a careful refining of Vershik's construction, R. H. Herman, I. F. Putnam and C. F. Skau [HPS] succeeded in showing that every Cantor minimal system is isomorphic to a Bratteli-Vershik system, i.e. the dynamical system associated to a properly ordered Bratteli diagram. An immediate consequence of their result is that every (simple) dimension group occur as the (ordered) K 0 -group that is associated to a Cantor minimal system, the latter notion being defined in purely dynamical terms. Subsequent work by T. Giordano, I. Putnam and C. F. Skau [GPS] showed that the orbit structure of a Cantor minimal system is intimately related to it's K 0 -group.

The main motivation of this paper is that up to now there has been few explicit and natural examples that have been worked out to illustrate the correspondence between Cantor minimal systems and dimension groups, respectively Bratteli diagrams. In this paper we shall show that the family of substitution minimal systems will yield examples of the desired nature.

General notions of substitutions appeared for the first time in 1963 in a paper of W. H. Gottshalk [Go]. He pointed out that the famous Morse sequence, initially introduced to prove the existence of recurrent geodesics on surfaces of negative curvature, can be defined by a substitution, now known as the "Morse substitution".

Nowadays substitutions arose and are studied in many domains. We briefly recall some of these domains.

Substitutions and topological dynamics. The study of symbolic dynamical systems has been initiated by G. A. Hedlund and M. Morse in [START_REF] Hedlund | Symbolic dynamics[END_REF][START_REF] Hedlund | Symbolic dynamics II. Sturmian trajectories[END_REF]. One of the simplest ways of constructing interesting minimal symbolic dynamical systems is by means of substitutions. For this reason, ergodic and topological properties of substitution systems has been extensively studied (see [Qu] for a good bibliography on this subject). Numerous papers deal with the spectrum of substitution system. First results were obtained for substitutions of constant length [START_REF] Dekking | The spectrum of dynamical systems arising from substitutions of constant length[END_REF][START_REF] Martin | Substitution minimal flows[END_REF] and then for substitutions of non-constant length [FMN,Ho,So].

D0L systems. Independently substitutions (called iterated morphisms) appeared to be attractive objects for the theory of formal languages; where they are studied through the notion of D0L systems. G. Rozenberg and A. Salomaa [RS] proved the decidability of the D0L equivalence problem.

p-recognizable sets of numbers. Cobham's theorem [START_REF] Cobham | On the base-dependence of sets of numbers recognizable by finite automata[END_REF] belongs to the domains of the theory of automata and of Arithmetic. It states that a set of positive integers which is "recognizable" in two multiplicatively independent bases is eventually periodic. Sets of integers which are recognizable in base p (i.e. p-recognizable) are characterized by means of substitutions of constant length p [START_REF] Cobham | Uniform tag sequences[END_REF]. This gives a formulation of Cobham's theorem using substitutions of constant length. Let p be a power of a prime number, in [CKMR] it is shown that a set is p-recognizable if and only if the power series associated to its characteristic sequence is algebraic over some field of rational fractions. These results are connected to some problems of transcendence. For example F. M. Dekking [START_REF] Dekking | Transcendance du nombre de Thue-Morse[END_REF] proved that the number +∞ i=1 x n 2 -n , where (x n ; n ∈ N) is the Morse sequence, is transcendent. Articles [LP] and [FM] give a partial answer to the following question: What can we say about real numbers having an expansion in some base p which is substitutive?

A characterization of sequences generated by substitutions of constant length were given in [BHMV] with the help of the formalism of first order logic.

Geometry. The article [Ra] of G. Rauzy opened a new area of investigation for substitutions. He constructed a partition of the torus T 2 in three fractal sets, and a rotation on T 2 , and looked at the symbolic system obtained in coding the orbits of this rotation by the partition. He found that this system is isomorphic to some substitution subshift. The partition G. Rauzy introduced generates self-similar tilings. In [START_REF] Dekking | Recurrent sets[END_REF] F. M. Dekking gave a method, using substitutions, to generate fractal curves and self-similar tilings; in particular it generates the famous Penrose tiling [Pe].

Theoretical physics. In 1984 D. Shechtman and al. [SBGC] discovered the existence in nature of quasi-periodic tilings: the quasicrystals. Later substitution sequences appeared to be good one-dimensional models for quasicrystals (see [BT]) and were used in a lot of papers of theoretical physics. In particular, several authors have studied the properties of the discrete Schrödinger operator with potential given by a substitution sequence (see [Be,BBG]).

Contents. Before we state the main results of this paper we want to acknowledge the paper by A. H. Forrest [Fo], where the main part of Theorem 1 is proved. However, the proofs given in his paper are mostly of existential nature and do not state a feasible method to compute effectively dimension groups and Bratteli diagrams associated to substitution systems (see also [AP]).

Theorem 1. The family B of Bratteli-Vershik systems associated to stationary, properly ordered Bratteli diagrams is (up to isomorphism) the disjoint union of the family of substitution minimal systems and the family of stationary odometer systems. Furthermore, the correspondence in question is given by an explicit and algorithmic effective construction. The same is true for the computation of the (stationary) dimension group associated to a substitution minimal system.

By invoking the characterization of Kakutani equivalence of Cantor minimal systems in terms of ordered Bratteli diagrams of [GPS; Theorem 3.8] we get the following corollary.

Corollary 2. The family B is stable under Kakutani equivalence.

In this paper we introduce the notion of linearly recurrent subshifts and we prove the following result.

Theorem 3. Let (Y, T ) be a linearly recurrent aperiodic subshift. There exists a constant D such that the length of each proper chain of aperiodic subshift factor maps

(Y n , T ) γ n-1 -→ (Y n-1 , T ) γ n-2 -→ • • • γ 1 -→ (Y 1 , T ) γ 0 -→ (Y 0 , T ) , with (Y n , T ) = (Y, T ), is less than D (i.e. n ≤ D).
We show that substitution minimal systems are linearly recurrent which is helpful, using Theorem 3 also, to prove the following theorem.

Theorem 4. A Cantor factor of a system (X,T) belonging to the family B in the above theorem again belongs to B.

Bratteli diagrams and dimensions groups -Ordered Bratteli diagrams and Cantor minimal systems -Stationary diagrams.

In this section we will recall some basic concepts and results, and also some of the key constructions that are used to obtain these results. This will later be applied in the context of stationary Bratteli diagrams and substitution minimal systems -the focus of this paper. We will introduce some relevant terminology and notation. We refer to [HPS,GPS,Ef] for further details.

1.1. Bratteli diagrams.

1.1.1. Definition 1. A Bratteli diagram is an infinite directed graph (V, E), such that the vertex set V and the edge set E can be partitioned into finite sets

V = V 0 ∪ V 1 ∪ V 2 ∪ • • • and E = E 1 ∪ E 2 ∪ • • •
with the following properties:

ı) V 0 = {v 0 } is a one-point set. ıı) r(E n ) ⊆ V n , s(E n ) ⊆ V n-1 , n = 1, 2, . . . ,
where r is the associated range map and s is the associated source map. Also,

s -1 (v) = ∅ for all v ∈ V and r -1 (v) = ∅ for all v ∈ V \V 0 .
There is an obvious notion of isomorphism between Bratteli diagrams (V, E) and (V ′ , E ′ ) ; namely, there exist a pair of bijections between V and V ′ and between E and E ′ , respectively, preserving the gradings and intertwining the respective source and range maps. It is convenient to give a diagrammatic presentation of the Bratteli diagram with V n the vertices at (horizontal) level n, and E n the edges (downward directed) connecting the vertices at level n -1 with those at level n. Also, if |V n-1 | = t n-1 and |V n | = t n then E n determines a t n × t n-1 incidence matrix. (See Figure 1 for an example.)

n 0 1 1 0 2 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 E n E n +1 n n +1 -1 s(e) e r(e) V n V n -1 V n +1 LEVEL INCIDENCE MATRIX Figure 1. 1.1.2. Telescoping. Let k, l ∈ Z + with k < l and let E k+1 • E k+2 • • • • • E l denote all paths from V k to V l . Specifically, E k+1 • • • • • E l = {(e k+1 , • • • , e l )|e i ∈ E i , i = k + 1, • • • , l ; r(e i ) = s(e i+1 ), i = k + 1, • • • , l -1}.
We define r((e k+1 , • • • , e l )) = r(e l ) and s((e k+1 , • • • , e l )) = s(e k+1 ). Given a Bratteli diagram (V, E) and a sequence

m 0 = 0 < m 1 < m 2 < • • • in Z + , we define the telescoping of (V, E) to {m n ; n ∈ N} as the new Bratteli diagram (V ′ , E ′ ), where V ′ n = V m n and E ′ n = E m n-1 +1 • • • • • E m n
and the range and source maps are as above. For example, if we remove level n of Figure 1 we get a telescoping to levels n -1 and n + 1 as indicated in Figure 2. Note that the new incidence matrix is the product of the two incidence matrices of Figure 1.

2 1 2 2 E n E n V n -1 V n +1 +1 Figure 2.
We say that (V, E) is a simple Bratteli diagram if there exists a telescoping (V ′ , E ′ ) of (V, E) so that the incidence matrices of (V ′ , E ′ ) have only non-zero entries at each level. We let ∼ denote the equivalence relation on ordered Bratteli diagrams generated by isomorphism and telescoping. It is not hard to show that (V 1 , E 1 ) ∼ (V 2 , E 2 ) if and only if there exists a Bratteli diagram (V, E) so that telescoping (V, E) to odd levels 0 < 1 < 3 < • • • yields a telescoping of either (V 1 , E 1 ) or (V 2 , E 2 ), and telescoping (V, E) to even levels 0 < 2 < 4 < • • • yields a telescoping of the other.

1.2. Ordered Bratteli diagrams and Bratteli-Vershik systems.

1.2.1. Definition 2. An ordered Bratteli diagram (V, E, ≥) is a Bratteli diagram (V, E)
together with a partial order ≥ on E so that edges e, e ′ in E are comparable if and only if r(e) = r(e ′ ) ; in other words, we have a linear order on each set r -1 ({v}), where v belongs to

V \ V 0 . Note that if (V, E, ≥) is an ordered Bratteli diagram and k < l in Z + , then the set E k+1 • E k+2 • • • • • E l of paths from V k to V l
may be given an induced (lexicographic) order as follows:

(e k+1 , e k+2 ,

• • • , e l ) > (f k+1 , f k+2 , • • • , f l )
if and only if for some i with k + 1 ≤ i ≤ l, e j = f j for i < j ≤ l and e i > f i . It is a simple observation that if (V, E, ≥) is an ordered Bratteli diagram and (V ′ , E ′ ) is a telescoping of (V, E) as defined above, then with the induced order

≥ ′ , (V ′ , E ′ , ≥ ′ ) is again an ordered Bratteli diagram. We say that (V ′ , E ′ , ≥ ′ ) is a telescoping of (V, E, ≥).
Again there is an obvious notion of isomorphism between ordered Bratteli diagrams. We let ≈ denote the equivalence relation on ordered Bratteli diagrams generated by isomorphism and by telescoping. One can show that B 1 ≈ B 2 , where

B 1 = (V 1 , E 1 , ≥ 1 ), B 2 = (V 2 , E 2 , ≥ 2
), if and only if there exists an ordered Bratteli diagram B = (V, E, ≥) so that telescoping B to odd levels 0 < 1 < 3 < • • • yields a telescoping of either B 1 or B 2 , and telescoping B to even levels 0 < 2 < 4 < • • • yields a telescoping of the other. This is analogous to the situation for the equivalence relation ∼ on Bratteli diagrams as we discussed above.

1.2.2. Dynamics for ordered Bratteli diagrams. Let B = (V, E, ≥) be an ordered Bratteli diagram. Let X B denote the associated infinite path space, i.e.

X B = {(e 1 , e 2 , • • •)|e i ∈ E i , r(e i ) = s(e i+1 ); i = 1, 2, • • •}.
We will exclude trivial cases and assume henceforth that X B is an infinite set. Two paths in X B are said to be cofinal if they have the same tails, i.e. the edges agree from a certain stage. We topologize X B by postulating a basis of open sets, namely the family of cylinder sets

U (e 1 , e 2 , • • • , e k ) = {(f 1 , f 2 , • • •) ∈ X B |f i = e i , 1 ≤ i ≤ k}. Each U (e 1 , • • • , e k
) is also closed, as is easily seen, and so we observe that X B becomes a compact Hausdorff space with a countable basis of clopen sets, i.e. a zero-dimensional space. We call X B with this topology the Bratteli compactum associated to B = (V, E, ≥).

If (V, E) is a simple Bratteli diagram, then X B has no isolated points, and so is a Cantor set.

Notation. Let x = (e 1 , e 2 , • • •) be an element of X B . We will call e n the n'th label of x and denote it by x(n). We let X max B (resp. X min B ) denote those elements x of X B so that x(n) is a maximal edge (resp. minimal edge) for each n = 1, 2,

• • •. A simple argument shows that X max B (resp. X min B ) is non-empty. Definition 3. The ordered Bratteli diagram B = (V, E, ≥) is properly ordered (called simple ordered in [HPS]) if ı) (V, E) is a simple Bratteli diagram. ıı) X max B , resp. X min B
, consists of only one point x max , resp. x min . We can now define a minimal homeomorphism V B : X B → X B , called the Vershik map (or the lexicographic map), associated to the properly ordered Bratteli diagram B = (V, E, ≤). We will call the resulting Cantor minimal system (X B , V B ) a Bratteli-Vershik system. We let V B (x max ) = x min . If x = (e 1 , e 2 , • • •) = x max , let k be the smallest number so that e k is not a maximal edge. Let f k be the successor of e k (and so r(e

k ) = r(f k )). Define V B (x) = y = (f 1 , • • • , f k-1 , f k , e k+1 , e k+2 , • • •), where (f 1 , • • • , f k-1 ) is the minimal edge in E 1 • E 2 • • • • • E k-1 with range equal to s(f k ).
It is a theorem that every Cantor minimal system is isomorphic to a Bratteli-Vershik system. A sketch of the proof of this result ("The Bratteli-Vershik model theorem") will be presented in the next subsection.

1.3. The Bratteli-Vershik model theorem -Kakutani-Rohlin partitions.

We shall sketch a proof of the following theorem using Kakutani-Rohlin partitions. We shall apply this later in the context of substitution minimal systems.

Theorem 5. [START_REF] Herman | Ordered Bratteli diagrams, dimension groups and topological dynamics[END_REF]Theorem 4.7] Let (X, T, x) be a (pointed) Cantor minimal system. Then there exists a properly ordered Bratteli diagram B = (V, E, ≥) so that (X, T, x) is pointedly isomorphic to (X B , V B , x min ), where x min is the unique minimal path of X B . Definition 4. A Kakutani-Rohlin partition of the Cantor minimal system (X, T ) is a clopen partition P of the kind:

P = {T j Z k |k ∈ A and 0 ≤ j < h k }
where A is a finite set and h k is a positive integer. The k ′ th tower of P is {T j Z k |0 ≤ j < h k }, and the base of P is the set

Z = ∪ k∈A Z k .
Note that in [HPS] the roles of the base Z and the top floors of the towers are reversed.

Sketch of proof of Theorem 5: Let (P n ; n ∈ N) be a sequence of Kakutani-Rohlin partitions with

P n = {T j Z n,k |k ∈ A n and 0 ≤ j < h n,k }, P 0 = {X} and with base Z n = ∪ k∈A n
Z n,k . We say that this sequence is nested if, for each n, ı) Z n+1 ⊂ Z n . ıı) P n+1 ≻ P n as partitions.

To the nested sequence (P n ; n ∈ N) we associate an ordered Bratteli diagram B = (V, E, ≥) as follows:

The |A n | towers in P n are in 1-1 correspondence with V n , the set of vertices at level n. Let v n,k ∈ V n correspond to the tower S n,k = {T j Z n,k |0 ≤ j < h n,k } in P n . S n,k will traverse towers in P n-1 in a certain order, say S n-1,i 1 , • • • , S n-1,i m . (Thus S n,k is partitioned into m parts.) We associate m edges, ordered as e 1,k < e 2,k < • • • < e m,k , with r(e j,k ) = v n,k and s(e j,k ) = v n-1,i j . E n is the disjoint union over k ∈ A n of the edges with range equal to v n,k . Suppose moreover that:

ııı) The intersection of the bases (Z n ; n ∈ N) of the partitions (P n ; n ∈ N) consists of one point only, say x. ıν) The sequence of partitions spans the topology of X.

Then the systems (X, T, x) and (X B , V B , x min ) are pointedly isomorphic, where B = (V, E, ≥) is a properly ordered Bratteli diagram with unique minimal path x min . In fact, the isomorphism F : X → X B is defined as follows: For y ∈ X, the path F (y) passes through the vertex in V n that corresponds to the tower in P n where y is located. Say F (y) passes through the vertices w of V n-1 and v of V n , corresponding to the tower S w in P n-1 , S v in P n , respectively. Then F (y)(n) is the i ′ th edge among the ordered edges e with r(e) = v, y being "picked up" the i ′ th time S v traverses one of the towers at level n -1. (Necessarily, S v will traverse the tower S w the i ′ th time.) It is easily seen that F (x) = x min by this correspondence. Finally, one obtains Kakutani-Rohlin partitions (P n ; n ∈ N) with the properties listed above by choosing a nested sequence (Z n ; n ∈ N) of clopen sets shrinking to x, i.e. Z n ⊇ Z n+1 and ∩ n Z n = {x}. The partition P n is obtained by building towers over Z n by considering the return map to Z n (For details, cf. [HPS]).

1.4. Dimension groups.

1.4.1. Definition 5. A dimension group is an ordered, countable, torsion free abelian group G which is unperforated and satisfies the Riesz interpolation property. Specifically, let G + denote the positive cone of G and let a ≤ b denote ba ∈ G + . Then

ı) G + + G + ⊆ G + ıı) G + -G + = G ııı) G + ∩ (-G + ) = {0} ıν) If a ∈ G and na ∈ G + for some n ∈ N, then a ∈ G + (unperforation). ν) If a 1 , a 2 , b 1 , b 2 ∈ G with a i ≤ b j (i, j = 1, 2), there exists c ∈ G with a i ≤ c ≤ b j (Riesz interpolation property).
We say that (G, G + ) is simple if G has no non-trivial order ideals J, i.e. J is a proper subgroup so that J = J + -J + (where J + = J ∩ G + ) and so that if b is an element of J and a an element of G with 0 ≤ a ≤ b, then a belongs to J. We say that an element u of G + \ {0} is an order unit if G + = {a ∈ G|0 ≤ a ≤ nu for some n ∈ N}. (Observe that for G simple any u ∈ G + \ {0} is an order unit.) To the Bratteli diagram (V, E) is associated a dimension group which we denote by K 0 (V, E) -the notation is motivated by the connection to K-theory, see below. In fact, to the Bratteli diagram (V, E) is associated a system of ordered groups and order-preserving homomorphisms

Z |V 0 | ϕ 1 -→ Z |V 1 | ϕ 2 -→ Z |V 2 | ϕ 3 -→ Z |V 3 | ϕ 4 -→ • • •
where ϕ n is given by matrix multiplication with the incidence matrix between levels n -1 and n of the Bratteli diagram. By definition K 0 (V, E) is the inductive limit of the system above endowed with the induced order. K 0 (V, E) has a distinguished order unit, namely the element of K 0 (V, E) + corresponding to the element 1

∈ Z |V 0 | = Z. One can show that (V, E) ∼ (V ′ , E ′ ) if and only if K 0 (V, E) is order isomorphic to K 0 (V ′ , E ′ ) by a map sending the distinguished order unit of K 0 (V, E) to the distinguished order unit of K 0 (V ′ , E ′ ). The dimension group K 0 (V, E) associated to (V, E) is simple if and only if (V, E) is simple.
Remark. It is a theorem that all dimension groups arise from Bratteli diagrams as described above [EHS].

1.4.2. We now introduce the definition which will relate Cantor minimal systems to dimension groups.

Definition 6. Let (X, T ) be a Cantor minimal system. Let C(X, Z) denote the continuous functions on X with values in Z -so C(X, Z) is a countable abelian group under addition.

Let K 0 (X, T ) = C(X, Z)/∂ T C(X, Z) where ∂ T : C(X, Z) → C(X, Z) denotes the coboundary operator ∂ T (f ) = f -f • T , and f -f • T is called a coboundary. Define the positive cone K 0 (X, T ) + = {[f ]|f ∈ C(X, Z + )}
where [ • ] denotes the quotient map and

Z + = {0, 1, 2, • • •}. K 0 (X, T ) has a distinguished order unit, namely [1] = 1
, where 1 denotes the constant function one.

Theorem 6. [HPS; Theorem 5.4 and Corollary 6.3] Let (X, T ) be a Cantor minimal system. Let B = (V, E, ≥) be the associated properly ordered Bratteli diagram (having chosen a base point in X, cf. Theorem 5). Then

K 0 (X, T ) = K 0 (V, E)
as ordered groups with distinguished order units. Furthermore, every simple dimension group G (G = Z) arises in this manner.

Remarks. ı)

In [GPS] it is shown that K 0 (X, T ), as an ordered group with distinguished order unit, is a complete invariant for strong orbit equivalence of Cantor minimal systems. ıı) K 0 (X, T ) is order isomorphic, by a map preserving the distinguished order units, to the K 0 -group of the C * -crossed product associated to (X, T ).

ııı) The group K 0 (X, T ), as an abstract group without order, is isomorphic to the first Cech cohomology group H 1 ( X, Z) of the suspension X of (X, T ), where X is obtained from X × [0, 1] by identifying (x, 1) and (T x, 0).

1.4.3. We will describe an alternative method to associate a dimension group to a nested sequence of Kakutani-Rohlin partitions (cf. subsection 1.3) without invoking Bratteli diagrams explicitly. This method, close to the approach taken in [GW], will later be applied to substitution miminal systems. (Incidentally, the proof of the first part of Theorem 6 is an immediate consequence of the lemma below.) So let (P n ; n ∈ N) be a nested sequence of Kakutani-Rohlin partitions (not necessarily satisfying conditions ııı) and ıν) of 1.3), with

P n = {T j Z n,k |k ∈ A n , 0 ≤ j < h n,k }, P 0 = {X} and with base Z n = ∪ k∈A n Z n,k .
For each n, let C n be the subgroup of C(X, Z) consisting of functions which are constant on each element of the partition P n , and let

C + n = C n ∩ C(X, Z + )
. Let H n be the subgroup of C n consisting of the functions f ∈ C n which have a null sum over each tower of P n , i.e. such that

h n,k -1 j=0 f (T j x) = 0 ∀k ∈ A n , ∀x ∈ Z n,k . Let K n be the quotient group C n /H n , K +
n the projection of C + n in this quotient, and 1 n the projection of the constant function 1. (K n , K + n , 1 n ) is an ordered group with order unit. Obviously, C n ⊂ C n+1 , C + n ⊂ C + n+1 and H n ⊂ H n+1 ; these inclusions induce a morphism j n+1 : K n -→ K n+1 of ordered groups with order units. The direct limit (K(P), K(P) + , 1) of the sequence

K 0 j 1 -→ K 1 j 2 -→ K 2 j 3 -→ • • • j n -→ K n j n+1 -→ K n+1 j n+2 -→ • • •
of ordered groups with order units is called the dimension group of the sequence of partitions, and written K(P n ; n ∈ N). It is easy to check that every element of H n is a coboundary. Thus the inclusions C n ֒→ C(X, Z) induce a morphism λ : K(P n ; n ∈ N) -→ K 0 (X, T ) of ordered groups with order units.

Lemma 7. As an ordered group with order unit, K(P n ; n ∈ N) is isomorphic to the dimension group K 0 (V, E), where B = (V, E, ≥) is associated to the sequence (P n ; n ∈ N) of partitions as described in subsection 1.3 (disregard the ordering of the edges).

Proof. For each f of C n , let γ n (f ) be the vector of Z |V n | obtained by summing the values of f over each tower of P n : For each v n,k belonging to V n (corresponding to the tower with base Z n,k ), let

(γ n (f )) k = h n,k -1 j=0 f (T j x) for an arbitrary point x ∈ Z n,k . Now γ n is a positive homomorphism from C n onto Z |V n | , it maps C + n onto (Z |V n | ) +
, and its kernel is H n . Thus we can identify the ordered groups

K n = C n /H n and Z |V n | for n = 0, 1, 2, • • • . By these identifications the homomorphism j n+1 : K n -→ K n+1 corresponds to the homomorphism Z |V n | -→ Z |V n+1 |
that we get from the Bratteli diagram (V, E). Therefore the two inductive limits are order isomorphic. Furthermore, it is easy to verify that the distinguished order units are mapped to each other by this isomorphism.

1.5. Stationary diagrams and dimension groups.

1.5.1. Definition 7. A Bratteli diagram (V, E) is stationary if k = |V 1 | = |V 2 | = • • • and if (
by an appropriate labeling of the vertices) the incidence matrices between level n and n + 1 are the same k × k matrix C for all n = 1, 2, • • • . In other words, beyond level 1 the diagram repeats. (Clearly we may label the vertices in E) is stationary, and the ordering on the edges with range V (n, a i ) is the same as the ordering on the edges with range

V n as V (n, a 1 ), • • • , V (n, a k ), where A = {a 1 , • • • , a k } is a set of k distinct symbols.) B = (V, E, ≥) is a stationary ordered Bratteli diagram if (V,
V (m, a i ) for m, n = 2, 3, • • • and i = 1, • • • , k.
In other words, beyond level 1 the diagram with the ordering repeats. (For each a

i in A = {a 1 , • • • , a k } and each n = 2, 3, • • • ,
we thus get an ordered list of edges whose range is V (n, a i ). By the stationarity of the ordering of B we thus get a well defined map from A to A + (the set of non-empty words on A), by taking the sources of the edges in question.) E) is completely determined by the incidence matrix C of (V, E) -we disregard the distinguished order unit. Also, K 0 (V, E) is simple if and only if C is a primitive matrix, i.e. a certain power of C has only non-zero entries.

(G, G + ) is a stationary dimension group if G is order isomorphic to K 0 (V, E), where (V, E) is a stationary Bratteli diagram. K 0 (V,
In this paper we will only encounter stationary Bratteli diagrams. In Figure 3 we exhibit two examples of stationary ordered Bratteli diagrams; the one on the left is properly ordered, while the one on the right is not properly ordered (having in fact two max and two min paths). The dimension group associated to the two diagrams (strip the order structure) is Z[1/2], the dyadic rationals, with obvious ordering and with distinguished order unit equal to 1.

1 2 1 2 1 2 2 1 Figure 3.
1.5.2. The question of the unicity of the Bratteli-Vershik model is addressed in the following proposition.

Proposition 8. [HPS; Theorem 4.7] Let B i = (V i , E i , ≥ i ) be associated to the pointed Cantor minimal system (X i , T i , x i ), i = 1, 2, according to Theorem 5. Then

(X 1 , T 1 , x 1 ) is pointedly isomorphic to (X 2 , T 2 , x 2 ) if and only if B 1 ≈ B 2 (cf. part 1.2.1).
By a modification of the "symbol splitting" procedure in [GPS; Sect. 3], Forrest proved the following lemma, which will be useful to us.

Lemma 9. [Fo; Lemma 15] Let B = (V, E, ≥) be a stationary, properly ordered Bratteli diagram. Then B ≈ B ′ = (V ′ , E ′ , ≥ ′ )
, where B ′ is again stationary and properly ordered, and with the added property that there are no multiple edges between level 0 and level 1.

(By the above proposition, (X B , V B ) and

(X B ′ , V B ′ ) are isomorphic.)
Proof. By taking a sufficiently high power of the incidence matrix C of (V, E) (this corresponds to a periodic telescoping of the diagram), we may assume that each row sum of C is greater or equal to the maximum number of edges between a vertex at level 1 and the top vertex (i.e. level 0). We now proceed by introducing new vertices between two successive levels, the number of which is the same as |E 1 |, i.e. the number of edges between level 0 and level 1. One may now construct a properly ordered Bratteli diagram with these added levels, so that one gets the original by telescoping. (This construction is not unique.) By instead telescoping to the new levels introduced one gets the desired

B ′ = (V ′ , E ′ , ≥ ′ ).
We will give a diagrammatic example which will illustrate how to proceed in the general case (cf. Figure 4).

2 3 1 1 4 3 2 1 4 1 2 3 1 1 2 1 2 1 2 3 1 2 1 2 1 2 1 2 3 2 3 4 5 3 2 Figure 4.
1.6. Kakutani equivalence.

Definition 8. The Cantor minimal systems (X, T ) and (Y, S) are Kakutani equivalent if they have (up to isomorphism) a common derivative, i.e. there exist clopen sets U (in X) and V (in Y ), respectively, so that the induced systems on U and V , respectively, are isomorphic.

We will relate Kakutani equivalence to Bratteli diagrams -the relevant fact being change of the order unit.

Observe first that if (V, E) is a Bratteli diagram with associated dimension group G = K 0 (V, E), then any finite change of (V, E), i.e. adding and/or removing a finite number of edges (vertices), thus changing (V, E) into a new Bratteli diagram(V ′ , E ′ ), does not change the isomorphism class of G, but does change the order unit. In fact,

G ′ = K 0 (V ′ , E ′ ) is order isomorphic to G,
(Z, ψ) is Kakutani equivalent to (X B , V B ) if and only if (Z, ψ) is isomorphic to (X B ′ , V B ′ ), where B ′ = (V ′ , E ′ , ≥ ′
) is obtained from B by a finite change as described above.

We indicate briefly the ingredients of the proof: Every clopen set of X B is a finite union of cylinder sets. By telescoping appropriately one may assume that the clopen sets in question are disjoint unions of cylinder sets of the form U (e), where e ∈ E 1 (cf. 1.2.2.). This is achieved by making a finite change of the original diagram. One may thus assume at the outset that the only changes that are done to the diagram occur between level 0 and level 1. With this simplification the proof follows by observing that removing edges corresponds to inducing on a clopen set.

2. Basic facts about substitution dynamical systems.

2.1. Notations: words, sequences, morphisms.

An alphabet is a finite set of symbols called letters. If A is an alphabet, a word on A is a finite (non empty) sequence of letters; A + is the set of words. For u = u 1 u 2 . . . u n ∈ A + , |u| = n is the length of u; for each letter a, we write |u| a the number of occurrences of a in u; the vector (|u| a ; a ∈ A) is sometimes called the composition vector of u. A * consists of A + and the empty word ∅ of length 0. . Given a word u = u 1 . . . u m and an interval J = {i, . . . , j} contained in {1, . . . , m}, we write u J to denote the word u i u i+1 . . . u j . We extend this notation in an obvious way to infinite intervals. A factor of v is a word u such that u = v J for some interval J ⊂ {1, . . . , m}; we write u ≺ v.

Elements of A Z are called sequences over the alphabet A. For a sequence x we use the notation x J and the term factor exactly as for a word; the language L(x) of the sequence x is the set of words which are factors of x.

Let A, B be two alphabets, and φ : A → B + a map. By concatenation, φ can be extended to a map A + → B + and also to a map A Z → B Z . As a general rule, these maps will be denoted by φ also.

The following definitions will be used in Section 4:

Definition 9. Let A be an alphabet, and R a finite subset of A + . ı) R is a code if every word u ∈ A + admits at most one decomposition in a concatenation of elements of R. ıı) R is a circular code if it is a code and moreover: if w 1 , . . . , w j , w, w ′ 1 , . . . , w ′ k ∈ R ; s ∈ A + and t ∈ A * are such that w = ts and w 1 . . . w j = sw ′ 1 . . . w ′ k t then t is the empty word. (it follows that j = k + 1, w i+1 = w ′ i for 1 ≤ i ≤ k and that w 1 = s.) Circular codes have a property of unique decomposition of sequences: Suppose that R is a circular code on the alphabet A, and that some x ∈ A Z can be decomposed in a the concatenation of the words (w k ; k ∈ Z) belonging to R, i.e. that x = . . . w -3 w -2 w -1 | w 0 w 1 w 2 . . . where the vertical bar separates x (-∞,-1] from x [0,+∞) . Then this decomposition is unique. Moreover, for n ∈ Z, the shifted sequence T n x (given by (T n x) k = x n+k for all k) can be decomposed in a concatenation of elements of R if and only if n is one of the numbers:

-|w r w r+1 . . . w -1 | (r < 0) ; 0 ; |w 0 w 1 . . . w r | (r ≥ 0) .

Subshifts.

For every alphabet A we denote by T the shift on A Z , except when some ambiguity can occur; T is defined by (T x) n = x n+1 for every x ∈ A Z and every n ∈ Z .

A is endowed with the discrete topology, and A Z with the product topology; thus A Z is a compact metric space, and T a homeomorphism of this space. When B is an alphabet and φ : A → B + a map, the corresponding map φ : A Z → B Z is continuous, and satisfies

φ(T x) = T |φ(x 0 )| φ(x) .
A subshift (X, T ) on the alphabet A is a closed T -invariant subset X of A Z , endowed with the restriction of T to X, we denote it T too. Given a subshift (X, T ) on the alphabet A, and two words u, v on A, we write:

[u] = {x ∈ X ; x [0,|u|) = u} and [u.v] = {x ∈ X ; x [-|u|,|v|) = uv} ;
subsets of X of this kind are called cylinder sets. Remark that these notations depend on the given subshift, which is supposed to be determined by the context. The language L(X) of the subshift (X, T ) is the set of words which are factors of at least one element of X, and we have

X = {x ∈ A Z ; L(x) ⊂ L(X)} .
The subshift (X, T ) is minimal if and only if L(x) = L(X) for all x ∈ X.

The subshift spanned by a sequence x ∈ A Z is the closure O x of the T -orbit of x endowed with the restriction of the shift to O x ; it is characterized by L(O x ) = L(x). This subshift is minimal if and only if x is uniformly recurrent i.e.:

(∀u ∈ L(x))(∃n ≥ 1)(∀v ∈ L(x))(|v| ≥ n ⇒ u ≺ v).
2.3. Definition of substitution dynamical systems.

2.3.1.

A substitution on the alphabet A is a map σ : A → A + . Using the extension to words by concatenation, σ can be iterated; for each integer n > 0, σ n : A → A + is again a substitution.

In this paper we only consider primitive substitutions, i.e. substitutions σ on A such that:

(∃n > 0)(∀a, b ∈ A)(b ≺ σ n (a)) and (∃a ∈ A)( lim n→+∞ |σ n (a)| = +∞).
We denote by L(σ) the language of σ, i.e. the set of words on A which are factors of σ n (a) for some a ∈ A and some n ≥ 1, and X σ the subshift of A Z associated to this language, i.e. the set of x ∈ A Z whose every finite factor belongs to L(σ); X σ is closed in A Z , and invariant under the shift; we denote by T σ the restriction of the shift to X σ . The dynamical system (X σ , T σ ) is called the substitution dynamical system associated to σ. It is classical [Qu] that Every substitution dynamical system is minimal and uniquely ergodic.

2.3.2. In the literature, substitution dynamical systems are often defined by a different (but equivalent) method, using fixed points: For every integer p > 0, the substitution σ p defines the same language, thus the same system, as σ does. Substituting σ p for σ if needed, we can assume that there exist two letters r, ℓ ∈ A such that: ı) r is the last letter of σ(r); ıı) ℓ is the first letter of σ(ℓ) ııı) rℓ ∈ L(σ).

Whenever r and ℓ satisfy the conditions ı) and ıı), it is easy to check that there exists a unique ω ∈ A Z such that

ω -1 = r ; ω 0 = ℓ and σ(ω) = ω .
Such an ω is called a fixed point of σ. If r and ℓ satisfy also ııı), we say that ω is an admissible fixed point of σ.

If ω is an admissible fixed point of σ, then X σ is the closure of the orbit of ω for the shift. This property is often taken of the definition of X σ in the literature. More precisely, we have:

Given a fixed point ω of the primitive substitution σ, the following conditions are equivalent:

ı) ω is admissible. ıı) ω ∈ X σ .
ııı) X σ is the subshift spanned by ω. ıν) ω is uniformly recurrent.

In all this paper, we shall use the following convention: when we say that ω is a fixed point of σ, we mean that ω is a fixed point of σ p for some p; as σ and σ p define the same system, this convention can't lead to any misunderstanding; moreover, with this convention, every substitution has at least one admissible fixed point.

2.3.3. Some technical difficulties in the study of substitution dynamical system arise from the fact that a given substitution can have several admissible fixed points. We now introduce a class of substitutions which are easier to study:

Definition 10. A substitution σ on the alphabet A is proper if there exists an integer p > 0 and two letters r, ℓ ∈ A such that: ı) For every a ∈ A, r is the last letter of σ p (a); ıı) For every a ∈ A, ℓ is the first letter of σ p (a)

A proper substitution has only one fixed point. We shall see later (in Section 5) that every substitution dynamical system is isomorphic to the system associated to some proper substitution, which can be explicitly constructed.

2.4. Structure of substitution dynamical systems.

In the sequel, (X σ , T σ ) is the system associated to the primitive substitution σ on the alphabet A, ω is an admissible fixed point of σ, r = ω -1 and ℓ = ω 0 .

There exist substitutions σ such that the system X σ is finite, i.e. that every x in X σ is periodic, or equivalently, that ω is periodic. As these substitutions are of little interest from a dynamical point of view, we consider henceforth only here aperiodic substitutions, i.e. substitutions giving rise to infinite systems. Note that there is an algorithm [Pa,HL] which decides whether a given substitution is aperiodic or not.

The systems arising from (primitive, aperiodic) substitutions have a simple self-similar structure we explain now. Remark first that by the first definition of X σ we have σ(X σ ) ⊂ X σ . The result below says that, although neither σ : A → A + is assumed to be one to one, nor {σ(a) ; a ∈ A} assumed to be a code, the restriction of σ to X σ behaves almost as these properties were true; let's begin with some notation.

As ω = σ(ω), it can be written

ω = . . . σ(ω -2 )σ(ω -1 ) | σ(ω 0 )σ(ω 1 ) . . .
where the vertical bar separates ω (-∞,-1] and ω [0,+∞) . Let E = {e j ; j ∈ Z} be the set of "natural cutting points" arising from this decomposition, defined by

e j =    -σ ω [j,0) if j < 0 0 if j = 0 σ ω [0,j) if j > 0
Theorem 11. [START_REF] Mossé | Puissances de mots et reconnaissabilité des points fixes d'une substitution[END_REF][START_REF] Mossé | Reconnaissabilité des substitutions et complexité des suites automatiques[END_REF] Let σ be an aperiodic primitive substitution on the alphabet A. ı) [START_REF] Mossé | Puissances de mots et reconnaissabilité des points fixes d'une substitution[END_REF] There exists L > 0 such that

n ∈ E, m ∈ Z, ω [n-L,n+L) = ω [m-L,m+L) ⇒ m ∈ E . ıı) [Mo2] There exists M > 0 such that i, j ∈ Z, ω [e i -M, e i + M ) = ω [e j -M, e j + M ) ⇒ ω i = ω j .
Remark. Earlier proofs of the same (or similar) results do exist [Ma], but are false. Until Mosse's papers, people working with substitutions had to make extra hypothesis ('recognizability', injectivity) on the substitution they were dealing with.

The theorem has the following topological interpretation ( for proofs, see [Qu] or [Ho]):

Corollary 12.

ı) The map σ : X σ → X σ is one-to-one and open. ıı) Every x ∈ X σ can be written in a unique way

x = T k σ σ(y) with y ∈ X σ and 0 ≤ k < |σ(y 0 )| .
ııı) For every x ∈ X σ , |σ(x 0 )| is the first return time of σ(x) to σ(X σ ), i.e. the smallest positive integer k such that T k σ σ(x) ∈ σ(X σ ). ıν) The map σ : X σ → σ(X σ ) is an isomorphism of the system (X σ , T σ ) onto the system induced by T σ on σ(X σ ).

The same results hold for σ n for each n > 0. For every letter a ∈ A, we write [a] = {x ∈ X σ ; x 0 = a}. From the preceding corollary we get immediately:

Corollary 13. For every n > 0,

P n = T k σ n ([a]) ; a ∈ A, 0 ≤ k < |σ n (a)| is a clopen partition of X σ .
It is worth noticing that the partition P n is a Kakutani-Rohlin partition in the sense of [START_REF] Herman | Ordered Bratteli diagrams, dimension groups and topological dynamics[END_REF]section 4]. The base of this partition is

a∈A σ n ([a]) = σ n (X σ ) .
Proposition 14. The sequence of partitions (P n ) is nested (see subsection 1.3) i.e.: ı) The sequence of bases (σ n (X σ ); n ∈ N) is decreasing. ıı) For every n, P n+1 P n as partitions. Moreover, if the substitution σ is proper, then ııı) The intersection of the bases consists in only one point (which is the unique fixed point of σ). ıν) The sequence of partitions spans the topology of X σ .

Proof. ı) is obvious. Remember that, for every x ∈ X σ ,

σ n (T σ x) = T |σ n (x 0 )| σ σ n (x) .
Let a be a letter, and k an integer with 0

≤ k < |σ n+1 (a)|. Set b 1 . . . b m = σ(a), so that we have |σ n (b 1 . . . b m )| = |σ n+1 (a)| > k .
Let j ∈ {0, . . . m -1} be the integer defined by

|σ n (b 1 . . . b j )| ≤ k < |σ n (b 1 . . . b j+1 )| .
It follows immediately that

T k σ n+1 ([a]) ⊂ T ℓ σ n ([b j ])
where ℓ = k -|σ n (b 1 . . . b j )|, and ıı) is proved.

We assume now that σ is proper. Then ııı) is obvious. Let us prove ıν): Let p, r, ℓ be as in the definition of a proper substitution (Definition 10).

Given an integer m > 0, we claim that, for n large enough, x [-m,m] is constant on each element of P n .

For n ≥ p, we write R n = |σ n-p (r)| and L n = |σ n-p (ℓ)|. Choose n so large that R n and L n are both greater than m. Fix a ∈ A and 0

≤ k < |σ n (a)|. For each x ∈ T k σ n ([a]
), there exists y ∈ X σ with y 0 = a and x = T k σ n (y). The word σ n (a)σ n (y 1 ) is a prefix of σ n (y) [0,∞) , and σ n-p (ℓ) is a prefix of σ n (y 1 ), thus σ n (a)σ n-p (ℓ) is a prefix of

σ n (y) [0,∞) . The same way, σ n-p (r) is a suffix of σ n (y)) (-∞,-1] ,
and

σ n (y) [-R n , K n + L n ) = σ n-p (r)σ n (a)σ n-p (ℓ)
where K n = |σ n (a)|, and we get:

x [-m,m] = σ n-p (r)σ n (a)σ n-p (ℓ) [R n + k -m, R n + k + m]
which does not depend on x, but only on a and k: our claim is proved, and ıν) follows.

3. From Bratteli diagrams to substitutions.

In this section, we prove the first part of Theorem 1. More precisely, we show here that:

The system associated to a stationary, properly ordered Bratteli diagram is isomorphic, either to the substitution dynamical system associated to some proper substitution, or to an odometer with a stationary base.

3.1. The substitution read on a stationary ordered Bratteli diagram.

Let B be a stationary, properly ordered Bratteli diagram. Remember that, for each integer n ≥ 0, V n denotes the set of vertices at level n. Let us choose a stationary labeling of V n (for n > 0) by an alphabet A, i.e. V n = {V (n, a); a ∈ A} for all n ∈ N. For n ≥ 1 and a ∈ A, V (n, a) is the vertex of label a at level n. Fix an integer n > 1. For every letter a ∈ A, consider the ordered list (e 1 , . . . , e k ) of edges which range at V (n, a), and let (a 1 , . . . , a k ) be the ordered list of the labels of the sources of these edges. The map a → a 1 . . . a k from A to A + doesn't depend of n. We consider it as a substitution on the alphabet A, and call it the substitution read on B.

Lemma 15. The substitution σ read on B is primitive and proper.

Proof. As B is simple, there exists an integer n > 1 such that, for every a, b ∈ A, the vertex V (1, b) is connected to the vertex V (n, a); by definition of σ, it means that b occurs in σ n-1 (a): the substitution σ is primitive.

For each a ∈ A, let i(a) be the first letter of σ(a): for each n > 1, the minimum edge which ranges at V (n, a) sources at V (n -1, i(a)). Suppose that, for every n ≥ 1, the range of the map i n : A → A contains at least two letters. Then there exist two distinct sequences (a n ; n ≥ 1) and (b n ; n ≥ 1) of letters, with i(a n+1 ) = a n and i(b n+1 ) = b n for every n; by definition of i, there exist two minimal paths x, y ∈ X B such that, for every n ≥ 1, x goes through V (n, a n ) and y through V (n, b n ). But B is properly ordered, and we get a contradiction. We have showed that, for p large enough, the first letter of σ p (a) doesn't depend on a, and by the same method the last letter of σ p (a) doesn't depend on a: σ is proper.

A particular case.

Let (d n ; n ∈ N) be a sequence of positive integers. We recall that the inverse limit of the sequence of groups (Z/d

0 d 1 • • • d n Z),
properly topologized, endowed with the addition of 1 is called the odometer with base

(d n ; n ∈ N). If d = d n = d n+1 = d n+2 = • • • for a certain
n, then we say that the odometer is stationary with stationary base d.

We can now prove the result in a particular case:

Proposition 16. Let B be a stationary, properly ordered Bratteli diagram with only simple edges between the top vertex and the first level, and σ : A → A + the substitution read on B. ı) If σ is aperiodic, then the system (X B , V B ) is isomorphic to the system (X σ , T σ ). ıı) If σ is periodic, the system (X B , V B ) is isomorphic to an odometer with a stationary base.

Proof of ı): Consider the sequence (P n ) of partitions associated to σ as in 2.4. The ordered Bratteli diagram associated to this sequence of partitions as in 1.3 is clearly B. By Proposition 14 and Lemma 15, this sequence of partitions satisfies the hypotheses ııı) an ıν) of subsection 1.3, thus (X σ , T σ ) is isomorphic to (X B , V B ). This proves ı), but we find it interesting to give an independent proof, based on an explicit construction of an isomorphism. The notations introduced here will be used in the proof of ıı).

Let π : X B → A Z be defined by:

∀x ∈ X B , ∀k ∈ Z, ∀a ∈ A, π(x) k = a if V k B x goes through V (1, a) .
We claim that π is an isomorphism between (X B , V B ) and (X σ , T σ ). The proof of this claim uses some definitions, which will be also used in the proof of ıı). So we don't suppose that σ is aperiodic for the moment. π is clearly continuous, and

π • V B = T • π (1)
where T is the shift on A Z . Remember that X B is naturally endowed with a sequence (Q n ) of Kakutani-Rohlin partitions where Q n is defined by the first n + 1 levels: two paths x, y ∈ X B belong to the same element of Q n if they agree until the level n + 1. In our case, Q n is easy to describe: Let K(n, a) be the set of paths x ∈ X B such that: α) x goes through V (n + 1, a); β) From the top vertex to the level n + 1, x consists of only minimal edges. By induction, the number of paths from the origin to the vertex V (n + 1, a) is equal to |σ n (a)| for all a ∈ A and all n ≥ 0, and the partition Q n can be written:

Q n = V k B K(n, a) ; a ∈ A, 0 ≤ k < |σ n (a)| .
We now define a map f : X B → X B . Let x ∈ X B be a path; for n ≥ 1, let x(n) be the label of the edge between the levels n -1 and n the path x goes through; remark that, for the class of Bratteli diagrams we consider, the sequence (x(n) ; n ≥ 2) completely determines x: the edge x(1) of x between the top vertex and the first level is determined by its range, which is the source of x(2). For all n > 2, let y(n) be x(n -1) and y(2) be the label of the minimal element in E 2 of the set of edges which range at the source of x(2). The sequence (y(n) ; n ≥ 1) determines a path y ∈ X σ , and we define f (x) = y.

Clearly we have f (x min ) = x min .

(2)

Suppose that the path x ∈ X B goes through V (1, a). By construction of the Vershik map we have

f (V B x) = V |σ(a)| B f (x) and f n (V B x) = V |σ n (a)| B f (x) for all n ≥ 1 ; (3) moreover, if σ(a) = b 1 . . . b m , then for 0 ≤ j < |σ(a)| the path V j B f (x) goes through V (1, b j+1 ); therefore we have π • f = σ • π . (4)
It follows that σ(π(x min )) = π(x min ), thus π(x min ) is the unique fixed point ω of σ. By (1), (2), and continuity we get π(X B ) ⊂ X σ , and π(X B ) = X σ by minimality. By definition of f , for every letter a we have f K(0, a) = K(1, a), and f n K(0, a) = K(n, a) for every n ≥ 1 by induction. From (1) and (4) we get:

∀a ∈ A, ∀n ≥ 1, ∀j with 0 ≤ j < |σ n (a)|, π V j B K(n, a) ⊂ T j σ σ n ([a]) . (5)
Suppose now that σ is aperiodic. By (5), π maps different elements of the partition Q n in different elements of the partition P n ; as the sequence (Q n ) of partitions spans the topology of X B , π is one-to-one and our claim is proved.

Proof of ıı):

We suppose that σ is periodic. Let p be the smallest period of its fixed point ω, and u = ω [0,p) , so that ω is an infinite concatenation of the word u. As σ(ω) = ω, it is also an infinite concatenation of the word σ(u), and it follows that σ(u) = u . . . u (d times) for some integer d > 1. Thus, for every a ∈ A, In other words, the composition vector (|u| a ; a ∈ A) of u is a left eigenvector of M (σ) for the eigenvalue d. Thus, for every n ≥ 0 and every a ∈ A,

|σ n (u)| a = d n |u| a and |σ n (u)| = pd n .
As π maps X B onto X σ and K(0, a) onto [a] for each a, the partition Q 0 is periodic of period p for V B ; it means that every V B -orbit visits the elements of Q 0 with period p; moreover, each interval of length p in each V B -orbit visits the set K(0, a) |u| a times.

For n ≥ 1, let K n be the base of the partition Q n , i.e. the union of the sets K(n, a), and W n be the transformation induced by V B on K n . For each x ∈ K(0, a), f n (x) ∈ K(n, a) and the first return time of

f n (x) to K n is |σ n (a)|, thus W n f n (x) = V |σ n (a)| B f n (x) = f n (V B x)
by ( 3), and f n is an isomorphism of (X B , V B ) to (K n , W n ). This isomorphism maps the partition Q 0 to the partition R n = {K(n, a) ; a ∈ A} of K n . Therefore, the partition R n is periodic for W n with period p, and every interval of length p of each W n -orbit visits the set K(0, a) |u| a times. As (K n , W n ) is the system induced by (X B , V B ) on K n , it follows that the partition Q n is periodic for V B , with a period equal to

a∈A |σ n (a)| |u| a = |σ n (u)| = pd n .
Finally, the sequence of partitions Q n is nested, and spans the topology of X B ; Q n is periodic of period pd n : it follows that (X B , V B ) is isomorphic to the odometer with base (p, d, d, . . .).

The general case.

We turn now to the general case, i.e. without the assumption that the edges from the top vertex to the first level are simple. The result follows immediately from [START_REF] Forrest | K-groups associated with substitution minimal systems[END_REF]Lemma 15] that we recalled in subsection 1.5 (Lemma 9).

Return words and derivatives of a sequence

We present here a modification of the method of return word and derivative sequences introduced in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF]. This method will be used in the next section to prove that every substitution dynamical system is isomorphic to the system associated to some stationary, properly ordered Bratteli diagram; and also in section 7 in the study of factors of substitution dynamical systems. As it can be interesting in itself, we present it here with more generality than we actually need. The proofs which are not given here can be found in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF][START_REF] Durand | A generalization of Cobham's theorem[END_REF].

Return words.

and ts = w ∈ R u.v ; by the discussion above again, 0 is not an occurrence of u.v in y, except if t is the empty word.

Derivatives of a sequence.

It will be convenient to label the return words. Put

R u.v = 1, . . . , Card(R u.v )
and let φ u.v : R u.v → R u.v be the bijection defined as follows: let R u.v be ordered according to the rank of first occurrence in x [0,+∞) , and φ u.v (k) defined to be the k th element of R u.v for this order. When u is the empty-word we set φ u.v = φ v . We consider R u.v as an alphabet, and φ u.v as a map from R u.v to A + . The last lemma can be stated as follows:

Corollary 18. φ u.v : R + u.v → A + and φ u.v : R Z u.v → A Z are one to one. The sequence x itself is by construction a concatenation of return words, thus we can define:

Definition 12. The u.v-derivative of x is the unique sequence D u.v (x) on the alphabet R u.v such that:

φ u.v D u.v (x) = x .

Topological interpretation.

The notion of derivative sequence is the combinatorial analogue to the notion of induced system, as we explain now. Using the bijection φ u.v , this partition can also be written:

Q = T j [u.φ u.v (k)v] ; k ∈ R u.v and 0 ≤ j < |φ u.v (k)| .
Let S be the shift on R Z u.v and Y the subshift spanned by D u.v (x). Lemma 19. φ u.v is an isomorphism of (Y, S) onto the system induced by (X, T ) on the cylinder set [u.v].

Proof. We know that φ u.v : R Z u.v → A Z is one to one. As

φ u.v (D u.v (x)) = x and, for all y ∈ R Z u.v , φ u.v (Sy) = T |φ u.v (y 0 )| φ u.v (y) we get φ u.v (S n D u.v (x)) ∈ X for all n, thus φ u.v (Y ) ⊂ X. By definition of φ u.v , we have φ u.v (Y ) ⊂ [u.v]. Let z ∈ [u.v].
There exists a sequence (n i ) of integers such that

T n i x → z; as [u.v] is open in X, for i large enough T n i x ∈ [u.v],
and n i is an occurrence of u.v in x; it follows that

T n i x = φ u.v (S k i D u.v (x)
) for some k i , and

T n i x ∈ φ u.v (Y ); finally we get z ∈ φ u.v (Y ) and φ u.v (Y ) = [u.v].
Let y ∈ Y and z = φ u.v (y); the first return time of z to [u.v] is n = |φ u.v (y 0 )|; thus the image of z by the first return time transformation is T n z = φ u.v (Sy), and the lemma is proved.

Return words and Bratteli diagrams.

We consider now return words for longer and longer prefixes of x [0,+∞) and suffixes of x (-∞,-1] . To avoid unnecessary heavy notations, we write, for all n ≥ 1:

R n = R x [-n,-1] .x [0,n) ; R n = R x [-n,-1] .x [0,n) ; φ n = φ x [-n,-1] .x [0,n) .
We get a sequence of Kakutani-Rohlin partitions P n where ) , each word belonging to R n+1 can be written a concatenation of words belonging to R n , and it can be done in a unique way. It follows that there exists a unique map σ n : R n+1 → R + n with:

P n = T j x [-n,-1] .wx [0,n) ; w ∈ R n and 0 ≤ j < |w| = T j B n,k ; k ∈ R n and 0 ≤ j < |φ n (k)| where B n,k = x [-n,-1] .φ n (k)x [0,n) for k ∈ R n . The base of P n is B n = x [-n,-1] .x [0,n) . Fix n ≥ 1. As x [-n,-1] is a suffix of x [-n-1,-1] , and x [0,n) a prefix of x [0,n+1
φ n • σ n = φ n+1 .
Clearly B n+1 ⊂ B n . Let k belong to R n+1 , j 1 . . . j m = σ n (k) and y ∈ B n+1,k . By definition, y ∈ B n,j 1 . The orbit of y climbs the j th 1 tower of P n , then goes to B n,j 2 , climbs the j th 2 tower of P n . . . goes to B n,j m , climbs the j th m tower of P n and comes back to B n+1 . The sequence of elements of P n the orbit of y visits before it returns to B n+1 doesn't depend on the point y ∈ B n+1,k , thus the partition P n+1 is finer than P n . The sequence (P n ) of partitions is nested in the sense of subsection 1.3. Moreover, n B n consists exactly of the point x, and the sequence (P n ) spans the topology of X because y [-n,n) is constant on each element of P n . Thus this sequence satisfy all the hypotheses ı), ıı), ııı) and ıν) of subsection 1.3: it can be used to construct a properly ordered Bratteli diagram B with (X B , V B ) isomorphic to (X, T ), or to compute the dimension group of (X, T ). It may be interesting to remark that the incidence matrices of this diagram -which are used to compute the dimension group -are the matrices M (σ n ) associated to the maps σ n and defined by

For i ∈ R n+1 and j ∈ R n , M (σ n ) i,j
= number of occurrences of j in σ n (i) .

Proof. Recall that φ(1) is the first element in the decomposition of x [0,+∞) in return words, i.e. that φ(1)ℓ is a prefix of x [0,+∞) . Let n be so large that |σ n (ℓ)| > |φ(1)|. As σ n (ℓ) and φ(1)ℓ are both prefixes of x [0,+∞) , φ(1)ℓ is a prefix of σ n (ℓ). Let j ∈ R, and w = φ(j). As ℓ is the first letter of w, σ n (ℓ) is a prefix of σ n (w), thus φ(1)ℓ also. It follows that φ(1) is the first element in the decomposition of σ n (w) = φ(τ n (j)) in a concatenation of return words, i.e. that 1 is the first letter of τ n (j). Let m = D(x) -1 : rφ(m) is a suffix of x (-∞,-1] , and the same argument shows that, for every n large enough and every j ∈ R, m is the last letter of τ n (j): τ is proper. Let k > 0 be an occurrence of r.ℓ so large that every return word w ∈ R appears in the decomposition of x [0,k) , i.e. that every j ∈ R occurs in the word u ∈ R + defined by

φ(u) = x [0,k) ; let n be so large that |σ n (ℓ)| > k. Let i, j ∈ R. As above, x [0,k) ℓ is a prefix of σ n (ℓ), which is a prefix of σ n (φ(i)) = φ(τ n (i))
. Thus u is a prefix of τ n (i), and j occurs in τ n (i): τ is primitive. Moreover

φ(τ (D(x))) = σ(φ(D(x))) = σ(x) = x = φ(D(x))
thus τ (D(x)) = D(x) by the unique decomposition property, and D(x) is the unique fixed point of τ . As φ(D(x)) = x is not periodic, D(x) is not periodic and the substitution τ is aperiodic.

Proof of the Proposition 20.

The proof of the announced result is almost immediate from this point: Let A be the stationary, properly ordered Bratteli diagram naturally associated to τ : it has simple edges between the top level and the first level, and τ is the substitution read on it. Let B be the stationary, properly ordered diagram which is identical to A except that, for each j ∈ R, the top level is joined by |φ(j)| edges to the vertex V (1, j). We claim that (X σ , T σ ) is isomorphic to (X B , V B ).

In Section 3 we have constructed an isomorphism π -1 from (X τ , T τ ) to (X A , V A ). For every j ∈ R, this isomorphism maps the cylinder set [j] of X τ to the subset of X A consisting of the paths which go through the vertex V (1, j). Thus the systems (X σ , T σ ) and (X B , V B ) are constructed in putting Kakutani-Rohlin towers of the same height over subsets of X τ and X A respectively, which correspond via this isomorphism: hence these systems are isomorphic.

The dimension group of a substitution dynamical system.

The construction above allows us to compute the dimension group of any substitution dynamical system, including the order and the order unit. When σ is a substitution on an alphabet A, we let M (σ) denote its matrix; it is the |A|×|A| matrix, with rows and columns indexed by A, defined by: For a, b ∈ A, M (σ) a,b is the number of occurrences of b in σ(a).

Let us recall the definition of the dimension group (K, K + , 1) of a d × d matrix M with nonnegative integer entries. Define:

G = -→ m ∈ Q d ; ∃n > 0 such that M n -→ m ∈ Z d G + = -→ m ∈ Q d ; ∃n > 0 such that M n -→ m ∈ Z d + H = -→ m ∈ Q d ; ∃n > 0 such that M n -→ m = -→ 0 K = G/H ; K + is the image of G + in K
and 1 is the image in K of the vector -→ 1 = (1, . . . , 1).

Theorem 22. Let σ be a (primitive, aperiodic) substitution on the alphabet A. ı) If σ is proper, then K 0 (X σ , T σ ) is isomorphic to the dimension group of the matrix of σ as ordered groups with order units. ıı) In the general case, let τ be the substitution on the alphabet R, and φ : R → A + the morphism defined in 5.2. Then K 0 (X σ , T σ ) is isomorphic as ordered group to the dimension group of the matrix of τ ; through this isomorphism, the order unit of K 0 (X σ , T σ ) corresponds to the image of the vector |φ(j)| ; j ∈ R in the dimension group of this matrix.

Proof. If σ is proper, then (X σ , T σ ) is isomorphic to (X B , V B ) where B is a stationary, properly ordered Bratteli diagram (see 5.1.) with simple edges between the top vertex and the first level, and σ is the substitution read on B. The incidence matrix of B is M (σ) at each level, and the result follows immediately from the computation of the dimension group of the system associated to a Bratteli diagram (Theorem 6).

In the general case, let B be the Bratteli diagram constructed in 5.3. At each level, its incidence matrix is the matrix of τ ; it has |φ(j)| edges between the top vertex and the vertex of label j in the first level, and the result follows.

An example.

The sets R and R, the map φ and the substitution τ on R can be computed in an explicit way from the substitution σ, as shown in the following example. Let σ be the substitution defined on the alphabet A = {a, b} by:

σ(a) = aba ; σ(b) = baab .
This substitution is clearly primitive, and it can be checked that it is aperiodic. Let x be the fixed point of σ such that x -1 = b and x 0 = a: x = . . . abaababaab | ababaababa . . .

where the vertical bar separates x (-∞,-1] of x [0,+∞) as usual. As ba is a factor of σ(a), x is admissible.

As baba is a factor of x, w 1 = ab is a return word to b.a; w 1 is in fact the first return word in the decomposition of x [0,+∞) , thus we set φ(1) = w 1 . We have:

σ(w 1 ) = ababaab = w 1 w 1 w 2
where w 2 = aab is necessarily a return word; we set φ(2) = w 2 , and we get τ (1) = 112. We have: σ(w 2 ) = abaababaab = w 1 w 2 w 1 w 2 thus τ (2) = 1212. As the substitution τ is primitive, the alphabet R cannot contain any other letter, thus R cannot contain any other return word. We get:

R = {1, 2} ; R = {ab, aab} ; φ(1) = ab ; φ(2) = aab ; τ (1) = 112 ; τ (2) = 1212
We can check that, as announced, the substitution τ is primitive, aperiodic and proper; its fixed point is y = . . . 12121121212 | 1121121212 . . . which is equal to D(x), and thus satisfies φ(y) = x.

Let us compute the dimension group of the substitution dynamical system (X σ , T σ ); we use the notations of 5.4..

Here the matrix M (τ ) is

M (τ ) = 2 1 2 2 . The determinant of M (τ ) is not 0, thus H = {0} and K 0 (X σ , T σ ) = G.
As the determinant of M (τ ) is 2, for every -→ m ∈ G there exists an integer k > 0 with 2 k -→ m ∈ Z 2 . Moreover, it is easily checked that, for every integer k > 0 there exists an integer n > 0 such that all the coefficients of M (τ ) n are multiples of 2 k . It follows that

K 0 (X σ , T σ ) = G = (2 -k a, 2 -k b) ; a, b ∈ Z, k ≥ 0 ⊂ Q 2 . With ρ = 2 + √ 2 (the Perron-Frobenius eigenvalue) we have 2 √ 2ρ -n M (τ ) n → √ 2 1 2 √ 2 as n → +∞ .
It follows that

K 0 + (X σ , T σ ) = G + = (α, β) ∈ K 0 (X σ , T σ ) ; α √ 2 + β ≥ 0 .
The order unit is 1 = (2, 3).

Construction of a proper substitution.

We use here the notations of the preceding section. By Lemma 9, there exists a stationary, properly ordered Bratteli diagram C with simple edges between the origin and the first level, which is order equivalent to B, thus defines an isomorphic system. From Proposition 16 we know that (

X σ , T σ ) is isomorphic to (X ζ , T ζ ),
where ζ is the substitution read on C; this substitution is proper by Lemma 15. In Figure 4 (Section 1) this is illustrated. In fact the leftmost diagram corresponds to B (and τ ), while the rightmost diagram corresponds to C (and ζ).

It is perhaps interesting to give an explicit and direct construction of such a ζ, without the use of Bratteli diagrams. This will provide an alternative proof of Proposition 20, in the formalism of substitutions. Moreover, this construction is perhaps more algorithmic than the one arising from Lemma 9 proved by A. Forrest. The work is done by the following proposition, which is a modification of an unpublished result of G. Rauzy.

Proposition 23. Let y be an admissible fixed point of a primitive substitution τ on the alphabet R, A an alphabet, φ : R → A + a one-to-one map, x = φ(y), and (X, T ) the subshift spanned by x.

There exist a primitive substitution ζ on an alphabet B, an admissible fixed point z of ζ and a map θ : B → A such that:

ı) θ(z) = x. ıı) If φ(R) is a circular code, then θ is an isomorphism from (X ζ , T ζ ) to (X, T ). ııı) If τ is proper, then ζ is proper.
From ı) it follows that ζ is aperiodic whenever the sequence x is not periodic.

Proof. The proof below is very simple, but the notations are, in an inescapable way, a bit heavy. Substituting a power of τ for τ if needed, we can assume that |τ (j)| ≥ |φ(j)| for all j ∈ R. For all j in R, we write m j = |τ (j)| and n j = |φ(j)|. We define: an alphabet B by B = (j, p)

; j ∈ R, 1 ≤ p ≤ n j , a map θ : B → A by θ(j, p) = φ(j) p , a map ψ : R → B + by ψ(j) = (j, 1)(j, 2) . . . (j , n j ). Clearly θ • ψ = φ.
We define a substitution ζ on B by:

For j in R and 1 ≤ p ≤ n j , ζ(j, p) =    ψ τ (j) p if 1 ≤ p < n j ψ τ (j) [n j , m j ] if p = n j
So that, for every j ∈ R, ζ ψ(j) = ζ(j, 1) . . . ζ(j, n j ) = ψ τ (j) , i.e.

ζ • ψ = ψ • τ (2)
and it follows that

ζ n • ψ = ψ • τ n for all n ≥ 0 .
We claim that ζ is primitive. Let n be an integer such that b occurs in τ n (a) for all a, b ∈ R. Let (j, p) and (k, q) belong to B. By construction, ζ(j, p) contains ψ τ (j) p as a factor, thus ζ n+1 (j, p) contains ζ n ψ τ (j) p = ψ τ n τ (j) p as a factor. By the choice of n, k occurs in τ n τ (j) p , thus ψ(k) is a factor of ψ τ n τ (j) p , and also of ζ n+1 (j, p). As (k, q) is a letter of ψ(k), (k, q) occurs in ζ n+1 (j, p) and our claim is proved. Proof of ıı). As θ commutes with the shift and maps z to x, it maps X ζ onto X. It remains to prove that θ : X ζ → X is one-to-one. Let α ∈ X. By definition of X, there exist γ ∈ X τ and an integer p, with 0 ≤ p < |φ(γ 0 )|, such that α = T p φ(γ). Let β be an element of X ζ with θ(β) = α. By definition of ψ, there exist some δ ∈ X τ and some integer q, with In this section we prove Theorem 3 and Theorem 4.

Let z = ψ(y). From (2) we get ζ(z) = ψ(τ (y)) = ψ(y) = z,
In subsection 7.1 we introduce the notion of linearly recurrent subshifts and prove some properties of such subshifts. In part 7.2 we prove Theorem 3 and we show that a minimal Cantor system which is a factor of a linearly recurrent subshift is either isomorphic to a subshift or to an odometer. This last result is the core of the proof of Theorem 4, given in part 7.3.

7.1. Linearly recurrent sequences and subshifts.

Definition 13. We say that a sequence x on a finite alphabet is linearly recurrent (with constant K ∈ N) if it is recurrent and if, for every factor u of x, the difference between two successive occurrences of u in x is less than K|u|.

Theorem 24. Let x be a linearly recurrent aperiodic sequence with constant K. Then:

ı) The number of distinct factors of length n of x is less or equal to Kn. ıı) x is (K + 1)-power free (i.e. u K+1 ∈ L(x) if and only if u = ∅). ııı) For all u ∈ L(x) and for all w ∈ R u we have

1 K |u| < |w|. ıν) For all u ∈ L(x), Card(R u ) ≤ K(K + 1) 2 .
Proof. We begin with a remark. Let n be a positive integer and u ∈ L(x) a word of length (K + 1)n -1. Let v ∈ L(x) be a word of length n. The difference between two successive occurrences of v is less than Kn, consequently u has at least one occurrence of v. We have proved that: For each n, all words of length n occurs in each word of length (K + 1)n -1. From this remark we deduce ı). Let u ∈ L(x) be a word such that u K+1 ∈ L(x). Each factor of x of length |u| occurs in u K+1 . But in u K+1 occurs at the most |u| distinct factors of length |u| of x. This contradicts the aperiodicity of x. Assume there exist u ∈ L(x) and w ∈ R u such that |u|/K ≥ |w|. The word w is a return word to u therefore u is a prefix of wu. We deduce that w K is a prefix of u. Hence w K+1 belongs to L(x) because wu belongs to L(x). Consequently w = ∅ and ııı) is proved. Let u be a factor of x and v ∈ L(x) be a word of length (K + 1) 2 |u|. Each word of length (K + 1)|u| occurs in v, hence each return word to u occurs in v. It follows from ııı) that in v will occur at the most K(K + 1) 2 |u|/|u| = K(K + 1) 2 return words to u, which proves ıν).

We say that a subshift is linearly recurrent (resp.K-power free) if it is minimal and contains a linearly recurrent (resp. K-power free) sequence. If a subshift (Y, T ) is linearly recurrent (resp. K-power free) then by minimality all sequences belonging to Y are linearly recurrent (resp. K-power free). The following proposition was first proved in [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF].

Proposition 25. All substitution subshifts are linearly recurrent.

Proof. Let τ be a substitution on A. Let u be a word of L(τ ) and v be a return word to u. A well-known property of substitutions (see [Qu]) asserts that there exists a constant C such that for all positive integers k

S k = sup{|τ k (a)|; a ∈ A} ≤ C inf{|τ k (a)|; a ∈ A} = CI k .
Let k be the smallest integer such that I k ≥ |u|. The choice of k entails that there exists a word ab ∈ L(τ ) of length 2 such that u occurs in τ k (ab). Let R be the largest difference between two successive occurrences of a word of length 2 of L(τ ). We have

|v| ≤ RS k ≤ RCI k ≤ RCS 1 I k-1 ≤ RCS 1 |u| .
The subshift spanned by τ is linearly recurrent with constant RCS 1 .

Remarks. Let ϕ be a factor map from the subshift (X, T ) on the alphabet A onto the subshift (Y, T ) on the alphabet B. A classical result (Theorem 6.2.9 in [LM]) asserts that ϕ is a sliding block code. That is to say there exists a non-negative integer r and r-block map f : -r,i+r] ) for all i ∈ Z and x ∈ X. We shall say that f is a r-block map associated to ϕ. When r = 0 (i.e. when f is a map from A to B), then ϕ is the restriction to X of the extension from A Z to B Z of f introduced in subsection 2.1. Suppose now that r is a positive integer.

A 2r+1 → B such that (ϕ(x)) i = f (x [i
If u = u 0 u 1 • • • u n is a word of length n ≥ 2r + 1 we define f (u) by (f (u)) i = f (u [i,i+2r] ), i ∈ {0, 1, • • • n -2r}. Let C denote the alphabet A 2r+1 and Z = {((x [-r+i,r+i] ); i ∈ Z) ∈ C Z ; (x n ; n ∈ Z) ∈ X}.
It is easy to check that the subshift (Z, T ) is isomorphic to (X, T ) and that f induces a 0-block map from C onto B which defines a factor map from (Z, T ) onto (Y, T ).

Proposition 26. Let (X, T ) and (Y, T ) be aperiodic subshifts such that (Y, T ) is a factor of (X, T ). Then ı) If (X, T ) is linearly recurrent with constant K then (Y, T ) is linearly recurrent. Moreover there exists n 0 such that: For all u ∈ L(Y ), of length greater than n 0 , and for all w ∈ R u we have |u|/2K ≤ |w| ≤ 2K|u| and Card(R u ) ≤ 2K(2K + 1) 2 . ıı) If (Y, T ) is K-power free, then (X, T ) is L-power free for some L.

Proof. We denote by A the alphabet of X and by B the alphabet of Y . Let ϕ : (X, T ) → (Y, T ) be a factor map. Let f : A 2r+1 → B be a block map associated to ϕ. Let u be a word of L(X) of length |u| ≥ 2r + 1 and v be a word of L(Y ) defined by f (u) = v. We have |v| = |u| -2r. If w is a return word to v then |w| ≤ max{|s|; s ∈ R u } ≤ K|u| ≤ K(|v| + 2r). The subshift (Y, T ) is linearly recurrent with constant K(2r + 1). Moreover: For all v ∈ L(Y ) such that |v| ≥ 2r, and for all w ∈ R v , |w| ≤ 2K|v|. Suppose there exists a word α of length n ≥ 2r such that α 2K+1 belongs to L(Y ). Each word of length n occurs in α 2K+1 . But in α 2K+1 occurs at the most |α| = n words of length n. This contradicts the aperiodicity of (Y, T ), therefore α is the empty word. The same arguments we used to prove point ııı) of Theorem 24 complete the proof of ı). Assume that (Y, T ) is K-power free. Suppose that there exists a word u, greater than 2r + 1, such that u (K+1) is a factor of x. Let w be f (uu [0,2r-1] ). The word w K is a prefix of f (u (K+1) ), hence w is the empty word and the same for u. This completes the proof.

Corollary 27. Let (X, T ) and (Y, T ) be two isomorphic aperiodic subshifts. Then: ı) If (X, T ) is linearly recurrent, then (Y, T ) is linearly recurrent. ıı) If (X, T ) is K-power free for some K, then (Y, T ) is K-power free.

Chains of factors.

A chain of factor maps of length n is a finite sequence (γ i : (Y i+1 , T i+1 ) → (Y i , T i ); 0 ≤ i ≤ n -1) of factor maps of minimal Cantor systems :

(Y n , T n ) γ n-1 -→ (Y n-1 , T n-1 ) γ n-2 -→ • • • γ 1 -→ (Y 1 , T 1 ) γ 0 -→ (Y 0 , T 0 ) .
The notion of subchain is implicitly defined. A chain is proper when none of the γ i 's is are isomorphisms. Let (γ i : (Y i+1 , T ) → (Y i , T ); 0 ≤ i ≤ n -1) be a chain of subshift factor maps. A remark in subsection 7.1 implies that by substituting, if needed, some (Y i , T ) by an isomorphic subshift, we can suppose that for each i ∈ {0, • • • , n -1} the factor map γ i is defined by a 0-block map.

Proof of Theorem 3. The subshift (Y, T ) on the alphabet A is linearly recurrent with constant K. Let (γ i : (Y i+1 , T ) → (Y i , T ); 0 ≤ i ≤ n -1) be a proper chain of aperiodic subshift factor maps of length n such that (Y n , T ) = (Y, T ). Substituting, if needed, some (Y i , T ), 0 ≤ i ≤ n -2, by an appropriate isomorphic subshift we can assume that the factor maps γ i , 0 ≤ i ≤ n -2, are given by 0-block maps γ i from the alphabet of Y i+1 to the alphabet of Y i . We do not change (Y, T ) and γ n-1 because it would change the constant K. It follows from Proposition 26 that there exists a positive integer n 0 such that: For all 0 ≤ i ≤ n -1, for all v ∈ L(Y i ) such that |v| ≥ n 0 and for all w ∈ R v we have |v|/2K ≤ |w| ≤ 2K|v|. We choose a word

v n-1 of L(Y n-1 ) such that |v n-1 | ≥ n 0 . Let i ∈ {0, • • • , n -2}. The factor map γ i γ i+1 • • • γ n-2 is given by the 0-block-map ψ = γ i γ i+1 • • • γ n-2 . Let v i = ψ(v n-1
). If w is a return word to v n-1 , then ψ(w) is a concatenation of return words to v i . Therefore we can define a unique map

λ i : R v n-1 → R * v i by φ v i λ i = ψφ v n-1 (see 4.2).
Let y be a word of L(Y i ). A word of length n of L(Y i ) has at the most 2Kn/|y| occurrences of y. From this we deduce that for all a in R v n-1

|λ i (a)| ≤ 2K|ψ(φ v n-1 (a))| |v i | ≤ 2K|φ v n-1 (a)| |v i | ≤ 2K 2 |v n-1 | |v i | = 2K 2 .
Recall that Card(R v i ) ≤ 2K(2K + 1) 2 (Theorem 24). The length of the image of each letter under the map λ i , 0 ≤ i ≤ n -2, and the cardinality of the alphabets R v n-1 and R v i are bounded independently of n and i. Hence the set of maps λ i , 0 ≤ i ≤ n -2, is bounded independently of n and i, more precisely it is bounded by (2K(2K + 1) 2 ) 4K 3 (2K+1) 2 = D.

Assume that n is greater than D +2, in this case there exists two integers 0 ≤ p < q ≤ n-2 such that λ p = λ q . Let ρ be the 0-block map γ p γ p-1 • • • γ q-1 . It defines a factor map from (Y q , T ) onto (Y p , T ). We want to prove that ρ

(R v q ) = R v p .
The definition of v p and v q implies that ρ(v q ) = v p . Let w be a return word to v q . The word ρ(w) is a concatenation of return words to v p . Suppose that ρ(w) is a concatenation of at least two return words to v p . There exists b

∈ R v n-1 such that γ q • • • γ n-2 (φ v n-1 (b)v n-1
) has an occurrence of wv q . Consequently the number of occurrences of return words to

v p in γ p • • • γ n-2 (φ v n-1 (b)v n-1
) is greater than the number occurrences of return words to

v q in γ q • • • γ n-2 (φ v n-1 (b)v n-1 ). That is to say, |λ q (b)| < |λ p (b)|, which contradicts that λ p = λ q . Therefore ρ(R v q ) ⊂ R v p .
Let w be a return word to v p . If there is no return word x to v q such that ρ(x) = w, then as above we can prove that there exists a letter b belonging to R

v n-1 such that |λ q (b)| < |λ p (b)|. We obtain ρ(R v q ) = R v p . Moreover Card(R v q ) = Card(R v p )
, hence the letter to letter morphism ρ, restricted to the set of concatenations of return words to v q , is a bijection from the set of concatenations of return words to v q onto the set of concatenations of return words to v p . This induces an isomorphism from (Y q , T ) onto (Y p , T ) and proves that γ p γ p+1 • • • γ q-1 is an isomorphism. This contradicts the fact that n is the length of (γ i : (Y i+1 , T ) → (Y i , T ); 0 ≤ i ≤ n -1).

Proposition 28. Let (Y, S) be a Cantor system which is a factor of a linearly recurrent subshift. Then (Y, S) is either isomorphic to a subshift or to an odometer.

Proof. Let (X, T ) be a linearly recurrent subshift with constant K and λ : (X, T ) → (Y, S) be a factor map. Let (P n = {P (n, 1),

(x)) i = δ(S i (x)) for all i ∈ Z. We set Y n = ϕ n (Y ). The map ϕ n is a factor map from (Y, S) onto (Y n , T ).
Property ıı) implies that there exists a 0-block map from A n+1 onto A n , which induces a factor map γ n : (Y n+1 , T ) → (Y n , T ) satisfying γ n ϕ n+1 = ϕ n . We have the following scheme:

(X, T ) λ -→ (Y, S) ϕ n+1 -→ (Y n+1 , T ) γ n -→ (Y n , T ) γ n-1 -→ • • • γ 1 -→ (Y 1 , T ) γ 0 -→ (Y 0 , T ) . Let Ω be the set {(x 0 , x 1 , • • •) ∈ Π +∞ i=0 Y i ; γ i (x i+1 ) = x i , i ∈ N}.
It is the inverse limit of the sequence ((Y i , T ), ϕ i ; i ∈ N). We endow Ω with the topology induced by the infinite product topology. Endowed with this topology Ω is a Cantor set. Clearly, the map

U : Ω → Ω defined by U ((x 0 , x 1 , • • •)) = (T x 0 , T x 1 , • • •) is a homeomorphism. The reader can check that (Ω, U ) is a minimal Cantor system.
In what follows we prove that (Ω, U ) is isomorphic to (Y, S). Let γ : (Y, S) → (Ω, U ) be the map defined by γ(x) = (ϕ 0 (x), ϕ 1 (x), • • •). It is easy to see that γ is a factor map. It remains to prove that γ is one-to-one. Let x and y be elements of Y . It follows from property ııı) that there exists an integer n and 1 ≤ i < j ≤ p n such that x ∈ P (n, i) and y ∈ P (n, j). Hence we have ϕ n (x) 0 = i = j = ϕ n (y) 0 . This implies that γ(x) = γ(y). Therefore γ is an isomorphism. Taking the sequence of partitions (P n ; n ≥ l) for some l ∈ N, if needed, we can suppose that either ı) none of the subshifts (Y n , T ) are periodic, or ıı) each subshift (Y n , T ) is periodic. Assume that (P n ; n ∈ N) fulfills ı). The subshift (X, T ) is linearly recurrent; consequently Theorem 3 implies that there exists n 0 ∈ N such that for all n ≥ n 0 the subshift factor Now we suppose that (Y, S) is isomorphic to the odometer with base (p n ; n ∈ N). To prove that this odometer has a stationary base it suffices to prove that the subset Γ of prime numbers dividing some p n is finite. We choose r, l ∈ A satisfying the requirement ı), ıı) and ııı) in subsection 2.3.2. Let u be a return word to r.l. Let p be a prime number of Γ. The system (Z/pZ, x → x + 1 (mod p)) is a factor of (X τ , T ). Consequently there exists a positive integer n 0 such that p divides |τ n (u)| = a∈A (M (τ ) n (|u| a ; a ∈ A)) a for all n ≥ n 0 . Let P (X) = |A| i=0 c i X i be the characteristic polynomial of M (τ ) n . We know that c 0 = det(M (τ ) n ) and, by the Theorem of Cayley-Hamilton, that P (M (τ ) n )(|u| a ; a ∈ A) = 0. It follows that p divides c 0 |u|, hence p divides |u|detM (τ ). We conclude that the set Γ is finite.

Suppose now that (Y, S) is a minimal Cantor system which is a factor of an odometer with stationary base (p, q, q, • • •). Let (P n ; n ∈ N) be a nested sequence of partitions of Y . Let n ∈ N. Let (Y n , T ) be the subshift associated to the partition P n (see the proof of Proposition 28). It is easy to check that this subshift is finite and its period k n divides pq i for some i. Hence the set of prime numbers dividing some k n is finite and (Y, S) is isomorphic to an odometer with stationary base.

One-sided systems.

The motivation of this section lies in the fact that people working with substitutions often consider only one-sided fixed points, bypassing the difficulty of admissibility which occurs when considering two-sided ones. One is lead to consider one-sided substitution dynamical systems, defined as the closure of the orbit of some one-sided fixed point in A N . After the basic definitions, we shall introduce here the dimension group of an one-sided system, and explain its relations with the dimension group of (ordinary, i.e. two-sided) dynamical systems. It will lead us to an alternative method -which could be called one-sided -to compute the dimension group of a substitution dynamical system; more precisely, it uses the return words on ℓ only, instead of the return words on r.ℓ used in Section 5.

Definitions

Definition 14. A one-sided dynamical system (X, T ) is a compact metric space X endowed with a map T : X → X which is continuous and onto.

Recall that we say that (X, T ) is a dynamical system when in addition T is also one-to-one. The most classical examples of one-sided systems are one-sided subshifts: Definition 15. Let A be an alphabet, T the shift on A N defined by (T x) n = x n+1 for all x ∈ A N and all n ∈ N, and X a closed subset of A N with T X = X. We say that (X, T ) is a one-sided subshift on A.

The one-sided subshift (X, T ) is said to be minimal if the only closed sets F of X with T F = F are ∅ and X; it implies that the only closed sets F with T F ⊂ F are ∅ and X. Some of the one-sided dynamical systems can also be associated to ordered Bratteli diagrams: A simple ordered Bratteli diagram is said to be semi-proper if it has only one minimal path. For such a diagram B and x ∈ X B , we define V B x as usual if x is not maximal, and V B x to be the minimal path x min if x is maximal. The system (X B , V B ) is then a minimal one-sided system. But such a system is very particular: it has only one point -namely x min -with several preimages. In fact, there is no clear method to associate a Bratteli diagram to minimal one-sided Cantor systems in general.

The natural extension.

Given a one-sided system (X, T ) there exists a dynamical system ( X, T ) and a factor map π : X → X such that: For every dynamical system (Y, S) and every factor map φ : Y → X there exists a unique factor map φ : Y → X with π • φ = φ.

The triple ( X, T , π) with this property is unique up to isomorphism in an obvious sense. It is called the natural extension of (X, T ). Let us recall one of the possible constructions. Let X Z be endowed with the product topology, and X be the subset of X Z consisting of the points x = (x n ; n ∈ Z) with x n+1 = T x n for all n ∈ Z. X is closed in X Z , it is not empty because T is onto, and it is invariant under the shift of X Z . Let T be the restriction of this shift to X, and π : X → X be defined by π(x) = x 0 . ( X, T , π) satisfies all the announced properties, thus can be called the natural extension of (X, T ). From this construction it follows that: ı) X is a Cantor set if X is a Cantor set. ıı) ( X, T ) is minimal if and only if (X, T ) is minimal. ııı) For every clopen set U of X there exists n ≥ 0 such that π( T -n U ) is clopen and

T -n U = π -1 π( T -n U ).
An alternative construction is possible when (X, T ) is a one-sided subshift on some alphabet A: Let L(X) be the language of X, i.e. the set of words on A which are factors of x for some x ∈ X; let ( X, T ) be the (two-sided) subshift associated to this language: X is the set of y ∈ A Z every factor of which belongs to L(X), and T be the restriction of the shift of A Z to X. The projection π : A Z → A N maps X onto X, and ( X, T , π) is the natural extension of (X, T ).

8.3. The dimension group of a one-sided system.

In this subsection we assume the spaces we encounter are Cantor sets.

A dimension group can be associated to every Cantor minimal one-sided system (X, T ), exactly as for dynamical systems [HPS]: Let ∂ T C(X, Z) be the group of coboundaries, i.e. the set of functions which can be written gg • T for some g ∈ C(X, Z). K 0 (X, T ) is the quotient group C(X, Z)/∂ T C(X, Z); K 0 + (X, T ) is the image of C(X, Z + ) in this quotient; and 1 the image of the constant function 1. (K 0 (X, T ), K 0 + (X, T )) is an ordered group, and 1 an order unit. The triple (K 0 (X, T ), K 0 + (X, T ), 1) is called the dimension group of the one-sided system (X, T ). (That it actually is a dimension group follows from Proposition 32.)

The dimension groups of one-sided systems share some of the properties of those of dynamical systems. In particular, as in [GW], we have: Lemma 30. Let φ : (X, T ) → (Y, S) be a factor map between two one-sided systems. Then the corresponding homomorphism φ * : K 0 (Y, S) → K 0 (X, T ) is one-to-one, and φ * (K 0 + (Y, S)) = K 0 + (X, T ) ∩ φ * (K 0 (Y, S)).

Moreover, we have:

Proposition 31. Let ( X, T , π) be the natural extension of the one-sided system (X, T ). Then π * : K 0 (X, T ) → K 0 ( X, T ) is an isomorphism of ordered groups with order units.

Proof. By Lemma 30 above, we have only to prove that π * is onto. Let α ∈ K 0 ( X, T ), and f ∈ C( X, Z) a representative of α. From the remark ııı) of subsection 8.2 it follows that there exists an integer n ≥ 0 such that f • T n factorizes through X, i.e. is equal to g • π for some g ∈ C(X, Z). If β is the class of g ∈ K 0 (X, Z), then π * (β) is the class of f • T n in K 0 ( X, T ), which is α.

Let (Y, S) be a Cantor minimal one-sided system, (X, T, π) its natural extension. When we want to compute the dimension group of (Y, S) or of (X, T ), we are often lead to use a sequence of Kakutani-Rohlin partitions of X which doesn't satisfy neither the hypotheses ııı) nor ıν) of subsection 1.3. We have to work with weaker conditions, and the next result can't be obtained by simple modifications of the proofs of [HPS]. As the use of Bratteli diagrams seems of little help, we prefer use the formalism of [GW], associating directly a dimension group to the sequence of partitions 1.4.

Theorem 32. Let (X, T, π) be the natural extension of the one-sided Cantor minimal system (Y, S). Let (P n = {T j B n,k ; k ∈ A n , 0 ≤ j < h n,k }; n ∈ N) be a nested sequence of clopen Kakutani-Rohlin partitions of X, where B n is the base of P n , such that: ı) If x, x ′ ∈ X are such that π(x) = π(x ′ ), then for n large enough they belong to different elements of P n . ıı) For each n there exists p > n and k ∈ A n such that B p ⊂ B n,k Then K 0 (X, T ) is isomorphic as ordered group with order unit to the dimension group K(P n ; n ≥ 1) defined in subsection 1.4.

Proof. We use here freely the notations of subsection 1.4. Let x, x ′ be two points in p B p , and suppose that π(x) = π(x ′ ). By ı) there exists n such that x and x ′ belong to different elements of P n . Let p and k be as in ıı); x and x ′ both belong to B n,k , and we get a contradiction. We have proved: π p B p consists of one point.

(1)

We claim that inf k∈A n h(n, k) → +∞ when n → +∞ .

(2)

Suppose it is false. There exists an integer J > 0 and, for infinitely many values of n, a point x n ∈ B n and an integer j n with 0 < j n ≤ J and T j n x n ∈ B n . By compactness, there exists a point x ∈ n B n and an integer j > 0 such that T j x ∈ n B n . By (1), S j π(x) = π(T j x) = π(x), and it is impossible because (Y, S) is minimal and Y is infinite: our claim is proved.

We prove now that λ maps K + (P) onto K 0 + (X, T ). Let f ∈ C(X, Z + ). By Proposition 31, f is cohomologuous to g • π for some g ∈ C(Y, Z + ). From ı) it follows by compactness that, for every clopen set A of Y , π -1 (A) is a union of elements of P n for n large enough. Thus g • π ∈ C + n for n large enough. It follows that λ(K + n ) = K 0 + (X, T ), and it implies immediately that λ is onto.

It remains to prove that λ is one-to-one. Let α be an element of K(P) with λ(α) = 0. α is the image in K(P) of an element β ∈ K r for some r ≥ 1; let f ∈ C r be a representative of β. As λ(α) = 0, the definition of λ implies that f is the coboundary of some g ∈ C(X, Z). As in the proof of Proposition 31, there exist i ≥ 0 and h ∈ C(Y, Z) such that g •T i = h•π. By (2), there exists n ≥ r such that h(n, k) > i for every k ∈ A n . Let p and k be associated to n as in ıı). For 0 ≤ j < i, T j B p ⊂ T j B(n, k), and f is constant on this set because it belongs to P n and f ∈ C n : f is constant on T j B p and f • T j is constant on B p . By (1), there exists q ≥ p such that the function h is constant on π(B q ), and it follows that g is constant on T i B q , and that g • T i is constant on B q . As f = gg • T ,

g = g • T i + i-1 j=0 f • T j ;
each of the functions on the right side of this expression is constant on B q , thus g is constant on B q . Moreover, f belongs to C q and, for all k ∈ A n and all x ∈ B q , h(q,k)-1 j=0 f (T j x) = g(x)g(T h(q,k) x) = 0 because x and T h(q,k) x both belong to B q and g is constant on this set. Thus f belongs to H q , and the projection of f in K q is 0. But this projection is equal to i

q-1 • • • • • i r (β).
From the definition of a direct limit, it follows that α = 0.

An Application: one-sided return words. In section 4.3. we have considered a point x in a minimal subshift (X, T ), and we have seen how to compute the dimension group of (X, T ) by using the return words on x [-n,-1] . x [0,n) . We could make the same construction but with the return words on x [0,n) , and it would produce a sequence (Q ′ n ) of partitions instead of (Q n ). Let Y be the projection of X in A N and S the shift on A N : (X, T ) is the natural extension of (Y, S). The sequence (Q ′ n ) satisfy the hypotheses of Theorem 32, thus it can be used to compute the dimension group of the system. 8.4. Application to substitution dynamical systems. Definition 16. We say that the substitution σ on the alphabet A is left-proper if there exist a letter ℓ ∈ A and an integer p > 0 such that ℓ is the first letter of σ p (a) for all a ∈ A.

Corollary 33. (Compare with Theorem 22 in 5.4) Let σ be a left-proper (primitive, aperiodic) substitution on the alphabet A. Then the dimension group of (X σ , T σ ) is isomorphic to the dimension group of its matrix (as ordered groups with order units).

Proof. Let π be the natural projection of A Z to A N , S the one-sided shift on A N , and Y = π(X σ ); (Y, S) is the one-sided substitution dynamical system associated to σ, and (X σ , T σ , π) is the natural extension of (Y, S). We have only to check that the sequence of partitions (P n ) introduced in subsection 2.4 satisfies the two conditions of Theorem 32. But it is immediate, using the same method as in the proof of the point ıı) of Corollary 12.

F

  . Durand † , B. Host ‡ , C. Skau* 0. Introduction.

  but the distinguished order units are not necessarily preserved by the isomorphism. Clearly, any change of order unit of G may be obtained by such a procedure. Likewise, if B = (V, E, ≥) is a properly ordered Bratteli diagram we may change B into a new properly ordered Bratteli diagram B ′ = (V ′ , E ′ , ≥ ′ ) by making a finite change, i.e. adding and/or removing any finite number of edges (vertices), and then making arbitrary choices of linear orderings of the edges meeting at the same vertex (for a finite number of vertices). So B and B ′ are cofinally identical, i.e. they only differ on finite initial portions. (Observe that this defines an equivalence relation on the family of properly ordered Bratteli diagrams.) Theorem 10. [GPS; Theorem 3.8] Let (X B , V B ) be the Bratteli-Vershik system associated to the properly ordered Bratteli diagram B = (V, E, ≥). Then the Cantor system

b∈AM

  (σ) b,a |u| b = |σ(u)| a = d|u| a where M (σ) is the matrix of σ, defined by for all a, b ∈ A, M (σ) b,a is the number of occurrences of a in σ(b).

  Let u, v be as above. The cylinder sets [u.wv] for w ∈ R u.v are obviously pairwise disjoint; they are included in the cylinder set [u.v] by the property ıı) of return words. Let y ∈ [u.v], and n be the smallest positive occurrence of u.v in y; then w = y [0,n) is a return word, and y ∈ [u.wv]. Thus {[u.wv] ; w ∈ R u.v } is a partition of [u.v]. Moreover, if w ∈ R u.v and y ∈ [u.wv], the first return time of y to [u.v] is |w| by the property ııı) of return words. It follows that Q = T j [u.wv] ; w ∈ R u.v and 0 ≤ j < |w| is a Kakutani-Rohlin partition of X, with base [u.v].

  and z is a fixed point of ζ. By construction, z is uniformly recurrent, thus it as an admissible fixed point of ζ. Moreover, θ(z) = θ(ψ(y)) = φ(y) = x, and ı) is proved.

  • • • , P (n, p n )}; n ∈ N) be a sequence of partitions of Y such that: ı) Each element of these partitions is clopen. ıı) P n ≺ P n+1 .

ııı) The sequence (P n ; n ∈ N) separates the points of Y .

Let n be a positive integer. We set A n = {1, • • • , p n } and we define a map δ : Y → A n by δ(x) = i if and only if x belongs to P (n, i). Let ϕ n : Y → A Z n be the map defined by (ϕ n

† University of Aix-Marseille II and Institut de Mathématiques de Luminy-CNRS, France. ‡ University of Marne la Vallée, France. * Norwegian University of Science and Technology, Trondheim, Norway.

In all this section, (X, T ) is a minimal subshift on the alphabet A, and x a given point of X; x is uniformly recurrent (see subsection 2.2). Let u be a suffix of x (-∞,-1] and v a prefix of x [0,+∞) , and we assume that at least one of them is not the empty word. We define an occurrence of u.v in x to be an integer n such that x [n-|u|,n+|v|) = uv. Definition 11. A word w on A is a return word to u.v in x if there exist two consecutive occurrences j, k of u.v in x such that w = x [j,k) .

As x is uniformly recurrent, the difference between two consecutive occurrences of u.v in x is bounded, and the set R u.v of return words to u.v is finite. It is immediate to check that a word w ∈ A + is a return word if and only if: ı) uwv ∈ L(x) (i.e. uwv is a factor of x); ıı) v is a prefix of wv and u is a suffix of uw; ııı) the word uwv contains only two occurrences of uv.

Remarks and notations.

1) The statement ıı) cannot be simplified: it is not equivalent to v is a prefix and u a suffix of w. For example, if aaaaa is a factor of x then the word a is a return word to aa.aa.

2) From this characterization, it follows that the set of return words doesn't depend on the choice of the point x, but only on the subshift X.

3) If the sequence x, or the subshift (X, T ) in which we consider return words, is not clear from the context, we write

To avoid unnecessary heavy notations, we write R u instead of R ∅.u .

Lemma 17. The set R u.v is a code. Moreover, it is a circular code (Definition 9).

Proof. Let m be a word, and assume that m can be written an a concatenation m = w 1 . . . w k of return words. From the property ıı) of return words, it follows by induction on j that u is a suffix of uw 1 . . . w j for 1 ≤ j ≤ k. By backwards induction, v is a prefix of w j . . . w k v for 1 ≤ j ≤ k. Thus u.v has at least k + 1 occurrences in umv = uw 1 . . . w k v, namely between u and w 1 ; between w j and w j+1 for 1 ≤ j < k;

By the discussion above, 0 is an occurrence of u.v in y. But

5. From substitutions to Bratteli diagrams.

5.1. In this section, we prove the second part of Theorem 1 in the form of the following proposition:

Proposition 20. The system associated to any (primitive, aperiodic) substitution is isomorphic to the system associated to some stationary, properly ordered Bratteli diagram.

Suppose first that the (primitive, aperiodic) substitution σ is proper. We can clearly define a stationary ordered Bratteli diagram B, with simple edges between the top vertex and the first level, such that the substitution read on B in the sense of Section 3 is exactly σ. This diagram is simple because σ is primitive, and properly ordered because σ is proper. As σ is aperiodic, Proposition 16 of Section 3 says that (X σ , T σ ) is isomorphic to (X B , V B ), and our result is proved. We consider now the general case, without assuming that the substitution is proper.

Remark. The proposition is partially proved in [Fo]. Our approach differs from Forrest's in that we give an explicit (algorithmic) construction of a properly ordered Bratteli diagram, and also of a proper substitution, defining a system isomorphic to (X σ , T σ ); in particular, it leads to an explicit method to compute completely (i.e.: with the order and the order unit) the dimension group of any substitution dynamical system: we don't make any assumption on the given substitution -except of course that it is primitive and aperiodic.

A derivative of a fixed point of a substitution.

Let σ be a (primitive, aperiodic) substitution on the alphabet A, and x one of its fixed points. We write r = x -1 and ℓ = x 0 , so that r is the last letter of σ(r) and ℓ the first letter of σ(ℓ).

We use here freely the notations introduced in Section 4. But, as we consider here return words to r.ℓ only, we write R, R, φ, D(x) instead of R r.ℓ , R r.ℓ , φ r.ℓ and D r.ℓ (x) respectively.

We define now a substitution τ on the alphabet R. Let j ∈ R, and w = w 1 . . . w k = φ(j) ∈ R. By the characterization of return words (see subsection 4.1), we have rwℓ ∈ L(σ), w 1 = ℓ and w k = r. As σ(x) = x, the word σ(rwℓ) = σ(r)σ(w)σ(ℓ) belongs also to L(σ). But r is the last letter of σ(r), and ℓ the first of σ(ℓ); it follows that rσ(w)ℓ ∈ L(σ); and also that the first letter of σ(w) is ℓ and its last letter r: rℓ is a prefix and also a suffix of rσ(w)ℓ. Therefore, the word σ(w) appears in x between two occurrences of r.ℓ, thus it is a concatenation of return words, i.e. belongs to φ(R + ); as φ : R → A + is a code (Lemma 17), there exists a unique word u ∈ R + such that σ(w) = φ(u).

We define τ (j) = u; τ is a substitution on the alphabet R, characterized by

Lemma 21. τ is proper, primitive, aperiodic, and D(x) is its fixed point.

| by construction of ψ, and φ(R) is a circular code, it follows that δ = γ and q = p, thus β = T p ζ ψ(γ): β is uniquely determined by α, and θ is one-to-one. Proof of ııı). Let ℓ ∈ R be the letter such that ℓ is the first letter of τ (k) for every k ∈ R. Let (j, p) ∈ B, and k = τ (j) p . By definition of ζ, the first letter of ζ(j, p) is (k, 1), and the first letter of ζ 2 (j, p) is the first letter of ζ(k, 1), i.e. (ℓ, 1). By the same method, if r is the last letter of τ (k) for every k ∈ R, then the last letter of ζ 2 (j, p) is (r, n r ) for every (j, p) ∈ B.

The example of subsection 5.5 continues.

As |τ (j)| ≥ |φ(j)| for j = 1, 2, we need not to consider a higher power for τ . We have n 1 = 2, m 1 = 3, n 2 = 3 and m 2 = 4. The alphabet B is: B = (1, 1), (1, 2), (2, 1), (2, 2), (2, 3)

The maps θ : B → A and ψ : R → B + are given by:

We compute now the substitution ζ on B:

To get easier notations, we put: α = (1, 1) ; β = (1, 2) ; γ = (2, 1) ; δ = (2, 2) ; ǫ = (2, 3) and B = {α, β, γ, δ, ǫ}. The substitution ζ and the map θ : B → A can be written:

ζ is proper: for every m ∈ B, α is the first and ǫ the last letter of ζ 2 (m). The fixed point of ζ is: z = . . . αβγδǫαβγδǫαβγδǫ | αβαβγδǫαβαβγδǫ . . .

We have θ(z) = x; θ is an isomorphism from (X ζ , T ζ ) to (X σ , T σ ), and hence (X σ , T σ ) is isomorphic to the Bratteli-Vershik system associated to the stationary, properly ordered Bratteli diagram naturally derived from ζ.

Cantor factors of substitution subshifts

) is an isomorphism. Then it is easy to check that (Y n 0 , T ) is isomorphic to (Ω, U ) and a fortiori to (Y, S). Suppose ıı). For each n ∈ N the subshift is finite and we set k n = Card Y n . Clearly (Y, S) is isomorphic to the odometer with base (k n ; n ∈ N).

Cantor factors of substitution subshifts.

In this part we give a condition for a subshift to be isomorphic to a substitution subshift.

Then we prove that under some assumptions a Cantor factor of a substitution subshift is isomorphic to a substitution subshift. We conclude this section with the proof of Theorem 4.

Proposition 29. Let x be a uniformly recurrent sequence.

is a substitution fixed point and ıı) the subshift spanned by x is isomorphic to a substitution subshift.

Proof. We have

It follows from the hypothesis that each return word to v is a concatenation of return words to u. This allows us to define a morphism ζ : R → R + by φ u ζ = φ v . The reader can check it is a substitution. Moreover, we have

The unicity of D u (x) implies that ζ(D u (x)) = D u (x). This prove ı).

We have x = φ u (D u (x)) and Lemma 17 asserts that φ u (R) = R u is a circular code. Proposition 23 completes the proof.

Proof of Theorem 4. Let (Y, S) be a minimal Cantor system which is the factor of a subshift spanned by a substitution τ : A → A + . Two cases appear (Proposition 28): ı) (Y, S) is isomorphic to a subshift (W, T ). ıı) (Y, S) is isomorphic to an odometer.

Assume that (Y, S) fulfills ı). Let B be the alphabet of W . Let ϕ : (X τ , T ) → (W, T ) be a factor map and f : A 2r+1 → B an associated block-map. Consider A 2r+1 as an alphabet that we denote C. Let X be the set { ((x [n-r,n+r] ); n ∈ Z) ∈ C Z ; (x n ; n ∈ Z) ∈ X τ }. The subshift (X, T ) is isomorphic to (X τ , T ) and f induces a 0-block map from C to B which defines a factor map γ : (X, T ) → (W, T ). In [Qu] is defined a substitution σ : C → C + in the following way

is a fixed point of σ and belongs to X. Therefore σ spans X. In [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF] it is proved that the image z by a 0-block map of a one-sided substitution fixed point has a finite number of derivative sequences. The proof can be adapted to bi-infinite sequences to obtain that the set {D u (z) ; u = z [0,n] , n ∈ N} is finite. We apply this result to the uniformly recurrent sequence γ(y ′ ) which spans W : There exists u and v fulfilling the hypothesis of Proposition 29. Hence (W, T ), and a fortiori (Y, S), is isomorphic to a substitution subshift.

The preceeding remarks lead to an alternative method to compute the dimension group of an arbitrary substitution dynamical system. Let σ be a (primitive, aperiodic) substitution on the alphabet A, z one of its one-sided fixed points, and ℓ = z 0 . There exists an admissible two-sided fixed point x with x [0,+∞) = z. We use the notations of Section 4, following the same method as in subsection 5.2, except that we consider the return words on ℓ instead of r.ℓ. Let y = D ℓ (x). As in subsection 5.2, there exists a substitution ρ on R ℓ such that φ ℓ • ρ = σ • φ ℓ , and y is a fixed point of ρ. ρ is primitive and left-proper, and (X ρ , T ρ ) is isomorphic to the system induced by (X σ , T σ ) on the cylinder set [ℓ]. From the Corollary 33 we get: Proposition 34. With the definitions above, the dimension group of (X σ , T σ ) is the dimension group of the matrix of ρ, except that the order unit is the image of the vector |φ ℓ (j)| ; j ∈ R ℓ .

Remark. This method to compute the dimension group could be called one-sided: The two-sided fixed point x appears here only because we have no defined return words for one-sided sequences.