EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA

MIKE BOYLE AND ALEJANDRO MAASS

Abstract. We study expansive invertible onesided cellular automata (i.e., expansive automorphisms of onesided full shifts) and find severe dynamical and arithmetic constraints which provide partial answers to questions raised by M. Nasu [N2]. We employ the images and bilateral dimension groups, measure multipliers, and constructive combinatorial characterizations for two classes of cellular automata.

1. Introduction

Let A be a set of cardinality N, let ℕ denote the nonnegative integers, and denote an element of A^{ℕ} as x = x_{0}x_{1}x_{2} …. An invertible onesided cellular automaton (c.a.) is a bijection F : A^{ℕ} → A^{ℕ} given by some local rule f: A^{r} → A — for all n, (F x)_{n} = f(x_{n} … x_{n+r−1}). The onesided full shift on N symbols, S_{N}, is the local homeomorphism A^{ℕ} → A^{ℕ} defined by setting (S_{N}x)_{i} = x_{i+1} for all i. F and S_{N} commute; in the language of symbolic dynamics, F is an automorphism of S_{N}.

We prove that if F is assumed to be a shift of finite type (which we show follows from weaker assumptions), then F must be shift equivalent to some twosided full shift on J symbols, where the same primes divide J and N, and the maps F and S_{N} have a common measure of maximal entropy. These results are proved in Section 4 by studying the relationship between the images dimension group of S_{N} (introduced in [BFF]) and the bilateral dimension group of F (introduced in [Kr1]), which are reviewed in Section 3.

In Section 6 we prove that if F is assumed to be a shift of finite type and N is a power of a prime p, then the number J above satisfies J ≥ p^{2}. The proof uses “measure multipliers”(reviewed in Section 5), developed in [B] to generalize Welch’s theory [H] of compatible extension numbers to shifts of finite type.

In Section 7, we make three conjectures about the possible dynamics of an expansive automorphism of S_{N}. Two of these were originally introduced by M. Nasu in the form of questions, to which our results give partial answers.

In Section 8 we give a constructive combinatorial characterization of the invertible onesided cellular automata F such that the shortest local rules for F and F^{−1} have radius 1. (Any invertible onesided c.a. is in an obvious way topologically conjugate to such an F.) In Section 9 we use this characterization to develop a constructive combinatorial characterization of a certain class of expansive c.a., and for this class we verify all our conjectures.

2000 Mathematics Subject Classification. Primary: 37B15; Secondary: 37B10.

Key words and phrases. cellular automata, shift of finite type, expansive, symbolic dynamics, dimension group.

The research of the first author was supported by NSF Grant DMS9706852.

The research of the second author was supported by Cátedra Presidencial fellowship and proyecto fondecyt 1980657.

2 MIKE BOYLE AND ALEJANDRO MAASS

In our situation, F is expansive and S = S_{N} is positively expansive (corresponding to F and not S being invertible). For the case that F and S are both positively expansive, see [N2], [N3], [Ku], [BM] and [BFF]. For the case that F and S are both expansive, see [N2] and [BL]. This last case is much less rigid and at present much more mysterious than the others (see Remark 4.7).

The first-named author thanks the Departamento de Ingeniería Matemática of the Universidad de Chile for financial support and warm hospitality in his December 1998 visit to Santiago, which made this collaboration possible.

2. Symbolic background

In this section we recall some elementary facts about symbolic dynamics. For a thorough introduction to the symbolic dynamics, see [K2] or [LM].

For a positive integer J, let J be a set of cardinality J; our default choice will be {0, 1, …, J− 1}. Let Σ_{J} denote the space ∏_{n∈ℤ} J. We view a point x in Σ_{J} as a doubly infinite sequence of symbols from J, so x = … x_{−1}x_{0}x_{1} . . .. The space Σ_{J} is compact metrizable; one metric compatible with the topology is dist(x, y) = 1/(|n| + 1), where |n| is the minimum nonnegative integer such that x_{n} ≠ y_{n}. The shift map σ : Σ_{J} → Σ_{J} is the homeomorphism defined by the rule (σx)_{i} = x_{i+1}. The topological dynamical system (Σ_{J}, σ) is called the full shift on J symbols (J is the symbol set). If Σ is a nonempty compact subset of Σ_{J} and the restriction of σ to Σ is a homeomorphism, then (Σ, σ|_{Σ}) is a subshift. (We may also refer to either Σ or σ|_{Σ} as a subshift, also we may suppress restrictions from the notation.) Equivalently, there is some countable set W of finite words such that Σ equals the subset of Σ_{J} in which no element of W occurs. A subshift (Σ, σ) is a shift of finite type (SFT) if it is possible to choose a finite set to be a defining set W of excluded words.

A homomorphism φ of subshifts is a continuous map between their domains which commutes with the shifts. A homomorphism is N-to-1 if every point in the range space has exactly N preimages. The map is constant-to-1 if it is N-to-1 for some integer N. An endomorphism is a homomorphism from a subshift to itself. (Thus a one-dimensional cellular automaton map is the same thing as an endomorphism of some full shift on J symbols.)

Two continuous maps F and G are topologically conjugate, or isomorphic, if there exists a homeomorphism h such that F h = hG. In this case the map h is a topological conjugacy. A topological conjugacy or isomorphism of subshifts is a bijective homomorphism between them.

Now suppose that X and Y are subshifts, m and a are nonnegative integers (standing for memory and anticipation), Φ is a function from the set of X-words of length m + a + 1 into the symbol set for Y, and φ is a homomorphism from X to Y defined by the local rule φ(x)_{i} = Φ(x_{i−m} … x_{i+a}). The homomorphism φ is called a block code (a k-block code if k = m + a + 1). The “Curtis-Hedlund-Lyndon Theorem”is that every homomorphism of subshifts is a block code.

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 3

If A is an m × m matrix with nonnegative integral entries, let Graph(A) be a directed graph with vertex set {1, …, m} and with A(i, j) edges from i to j. Let E_{A} be the edge set of Graph(A). Let Σ_{A} be the subset of (E_{A})^{ℤ} obtained from doubly infinite walks through Graph(A); that is, a bisequence x on symbol set E_{A} is in Σ_{A} if and only if for every i in ℤ, the terminal vertex of the edge x_{i} equals the initial vertex of the edge x_{i+1}. Let σ_{A} = σ|_{Σ_{A}}. The SFT (Σ_{A}, σ_{A}) (or Σ_{A} or σ_{A}) is called an edge shift. The edge shift σ_{[J]} is a full shift σ_{J}. Any SFT is topologically conjugate to some edge SFT.

Let X_{A} be the space of onesided sequences obtained by erasing negative coordinates in Σ_{A}: that is, if a point x is in Σ_{A}, then the onesided sequence x_{0}x_{1}x_{2} … is in X_{A}, and X_{A} contains only such points. The shift map rule (σx)_{i} = x_{i+1} defines a surjective local homeomorphism S_{A} : X_{A} → X_{A}. The system (X_{A}, S_{A}) is a onesided shift of finite type. We will write a onesided full shift on N symbols as (X_{[N]} = X_{N}, S_{N}), where X_{N} = A^{ℕ} for some alphabet A with N symbols. If X is a nonempty compact subset of X_{N} and the restriction of S_{N} to X_{N} is an endomorphism then (X, S_{N}) is a onesided subshift. Every homomorphism of onesided subshifts is given by a r + 1–block code or local rule with memory m = 0.

Williams [W] explained how to associate to a onesided SFT S_{A} an essentially canonical matrix, the “total amalgamation”of A. Correspondingly, onesided SFTs are much more rigid than twosided SFTs ([W], [BFK], [N2], [BFF]). One striking result in this direction is due to Nasu: if F is a totally transitive (every power of F has a dense orbit) automorphism of a onesided SFT S, then S must be topologically conjugate to a onesided full shift ([N2], Thm. 3.12). [This is essentially because F induces a map on the vertices of the total amalgamation (by Lemma 3.10 of [N1], or (2.23) and (2.25) of [BFK]), so some power of F fixes those vertices.] This result of Nasu justifies a focus on the dynamics of automorphisms of S_{N} vs. other onesided SFTs.

An SFT is called irreducible if it has a dense forward orbit, and it is mixing if whenever words U and W occur in points of the SFT, for all but finitely many positive n there is a word V of length n such that UV W occurs. A nonnegative matrix A is irreducible if for every i, j there exists n > 0 such that A^{n}(i, j) > 0, and it is primitive if n can be chosen independent of (i, j). An irreducible matrix A defines an edge shift which is an irreducible SFT, and a primitive matrix A defines an edge shift which is a mixing SFT.

The (topological) entropy h(σ) of a subshift (X, σ) (twosided or onesided) is the growth rate of its words, that is, lim(1/n)log#{x_{1}x_{2} … x_{n} : x ∈ X}. For an SFT σ_{A}, the entropy is log(λ_{A}), where λ_{A} is the spectral radius of A. An irreducible SFT σ_{A} has a unique measure μ of maximal entropy; that is, μ is a σ_{A}-invariant Borel measure, its measure theoretic entropy equals h(σ_{A}), and there is no other such measure.

Twosided SFTs σ_{A}, σ_{B} are shift equivalent if their defining matrices satisfy certain equations which are equivalent to the following condition: for all sufficiently large k, (σ_{A})^{k} and (σ_{B})^{k} are topologically conjugate. An SFT σ_{A} is shift equivalent to a full shift on J symbols iff for

4 MIKE BOYLE AND ALEJANDRO MAASS

some k the characteristic polynomial of A equals x^{k}(x − J). It is still unknown whether such SFTs must be conjugate to full shifts (contrast [KR]).

A continuous map φ from a compact metric space X to itself is positively expansive if there exists ϵ > 0 such that whenever x and x′ are distinct points in X, there is a nonnegative integer k such that dist(φ^{k}(x), φ^{k}(x′)) > ϵ. This property does not depend on the choice of metric compatible with the topology. Now if φ is an endomorphism of a twosided subshift Σ and k ∈ ℤ_{+}, then let x̂^{(k)} denote the sequence of words ([φ^{i}(x)_{−k} … φ^{i}(x)_{k}]: i = 0, 1, 2 …). It is easy to check that φ is positively expansive iff there exists k ∈ ℤ_{+} such that the map x ↦ x̂^{(k)} is injective iff φ is conjugate to a onesided subshift.

Similarly, a homeomorphism F from a compact metric space to itself is expansive if there is some ϵ > 0 such that for all distinct x, x′, there is an integer k such that dist(F^{k}(x), F^{k}(x′)) > ϵ. Expansiveness is an important ([Hi], [AH]) and multifaceted ([BL], Sec. 5) dynamical property. If F is an automorphism of a onesided subshift X and k ∈ ℕ, let x̃^{(k)} denote the sequence of words ([F^{i}(x)_{0} … F^{i}(x)_{k}] : i ∈ ℤ). Then F is expansive iff there exists k ∈ ℕ such that the map η_{k}: x ↦ x̃^{(k)} is injective iff F is conjugate to a twosided subshift. If F is expansive with local rule f: x_{0} … x_{r} ↦ (F x)_{0}, r > 0, then the map η_{r−1} must be injective. (If η_{r−1} collapses x and y, and W = W_{0} … W_{j}, then one easily checks that η_{r+j} collapses W x and W y.)

3. Two dimension groups

In this section we review the information we will need on two dimension groups arising in symbolic dynamics.

Let S be a local homeomorphism of a compact zero dimensional metrizable space X. Let CO(X) be the collection of clopen subsets of X. Let ℤCO(X) denote the free abelian group with generators CO(X). Let H(S) be the subgroup of ℤCO(X) generated by the following relations:

(i) ΣC_{i} ∼ C if C is the disjoint union of the clopen sets C_{i}.

(ii) C ∼ D if C and D are clopen sets and there exists n > 0 such that φ^{n}|_{C} and φ^{n}|_{D} are injective and φ^{n}C = φ^{n}D.

The images group Im(S) defined in [BFF] is the quotient ℤCO(X)/H(S). To an n × n integral matrix A, associate the direct limit group

G(A) = lim ; ⟶_{A} ℤ^{n} .

The group G(A) can be presented concretely as a subgroup of a finite dimensional vector space (see pp. 14-15 of [BMT] and Sec. 7.5 of [LM]). For a onesided SFT S_{A}, we have Im(S_{A}) ≅ G(A) ([BFF], Thm. 4.5). For S = S_{N}, let μ be the uniform measure (the measure of maximal entropy), i.e. if x[0, k] denotes {y ∈ X_{N} : y_{i} = x_{i}, 0 ≤ i ≤ k}, then μ(x[0, k]) = N^{−(k+1)}. Then there is an isomorphism Im(S_{N}) → ℤ[1/N] given by [Σn_{i}C_{i}] ↦ Σn_{i}μ(C_{i}).

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 5

Next, let F : X → X be a subshift. We will similarly define the bilateral dimension group Bilat(F) as a quotient of ℤCO(X). Let K(F) be the subgroup of ℤCO(X) generated by the following relations

(i) ΣC_{i} ∼ C if C is the disjoint union of the clopen sets C_{i}.

(ii) x[i, j] ∼ y[i, j] if for all sequences w = … w_{i−2}w_{i−1} and z = z_{i+1}z_{j+2} …, the point

wx_{i}...x_{j}z is in X if and only if the point wy_{i}...y_{j}z is in X. Then Bilat(F) is the quotient group ℤCO(X)/K(F). This is one of the dimension groups

introduced to symbolic dynamics by Krieger [Kr1]. The definition of Bilat(F) in ([Kr1], Section 2) appeals to a larger theory; we have given an equivalent but more direct definition suitable to our needs. Following Krieger (personal communication), we use the adjective “bilateral”to distinguish this dimension group from the past and future dimension groups of [Kr1], which involve onesided splittings.

The groups Im(S) and Bilat(F) carry order structures which make them dimension groups. We will not need to consider these order structures in the current paper.

If F is SFT and S is a local homeomorphism such that SF = F S, then there is an induced homomorphism S_{∗} : Bilat(F) → Bilat(F), given by [Σn_{i}C_{i}] ↦ [Σn_{i}S(C_{i})] when the restriction of S to each C_{i} is injective. If F is an SFT σ_{A}, with A n × n, then from Prop. 3.1 of [Kr1] we have

(3.1)  Bilat(F) ≅ G(A ⊗ A^{t}) .

Here the tensor product A⊗A^{t} is an n^{2}×n^{2} matrix with (A⊗A^{t})([i, j], [i′, j′]) = A(i, i′)A^{t}(j, j′). When σ_{A} is shift equivalent to a full shift σ_{J}, this means

(3.2)  Bilat(F) ≅ ℤ[1/J] .

Let G be a torsion free abelian group. We will say G has finite rank if it is isomorphic to a subgroup of ℚ^{k} for some k < ∞. In this case, the rank of G is the minimal such k. If α : H → G is a group homomorphism, where H has rank k and G has rank ℓ, then (after identifying G and H with subgroups of ℚ^{k} and ℚ^{ℓ}) it is easily checked that the map α is the restriction of a unique rational vector space homeomorphism α̃ : ℚ^{k} → ℚ^{ℓ}. Consequently, we have the following well known

Fact 3.1. Suppose H and G are countable torsion free abelian groups of equal finite rank and α : H → G is a surjective group homomorphism. Then α is injective, and therefore an isomorphism.

For any subshift (Σ, σ), let W(σ) denote the set of words {x_{i}...x_{j} : x ∈ Σ}. Define an equivalence relation ≈ on W(σ) by setting V ≈ V′ iff for all words U and W,

UV W ∈ W(σ)  ⇔  UV′W ∈ W(σ) .

A subshift is sofic iff the set of ≈ equivalence classes is finite. It is easy to see that for F sofic, the rank of Bilat(F) is finite.

Proposition 3.2. Suppose σ is sofic and rank Bilat(σ) = 1. Then σ is SFT and σ is shift equivalent to some full shift.

Proof. If σ is isomorphic to an SFT σ_{A}, then by equation (3.1) the matrix A has just one nonzero eigenvalue, and therefore σ_{A} is shift equivalent to a full shift.

To deduce that σ must be SFT we will sketch an argument which requires some familiarity with sofic systems. There is an SFT σ_{B} which is a topologically canonical “follower set cover”of the sofic shift σ, and here G(B) is isomorphic to the future dimension group of σ ([Kr2], Thm. 3.5). It is easy to check that the future dimension group of σ must have rank 1 if Bilat(σ) has rank 1. This forces the SFT σ_{B} to be irreducible. However, for a nonSFT sofic shift, this SFT σ_{B} must be reducible, because a nonSFT sofic shift has “non-F -finitary”points ([Kr2], Prop. 4.3). □

Open Problem 3.3. Suppose σ is a subshift and Bilat(σ) has finite rank. Must σ be sofic?

Open Problem 3.4. Suppose σ is a subshift and the rank of Bilat(σ) is 1. Must σ be SFT?

Of course an answer yes to the former problem implies an answer yes to the latter.

4. Full shifts and primes

Throughout this section, let S = S_{N} denote the onesided full shift on N symbols with domain X = X_{N} = ∏_{i=0}^{∞}{0, 1, ..., N − 1}, and let F be an expansive automorphism of S. We will use some dimension group techniques to prove that if F is SFT, then F is shift equivalent to some twosided full shift on J symbols, σ_{J}, where N and J are divisible by the same primes.

Let [i_{0}i_{1} … i_{r}]_{S} denote {x ∈ X : x_{j} = i_{j}, 0 ≤ j ≤ r}. Any clopen set in X is a finite union of sets of this form. Let S_{∗} denote the homomorphism Bilat(F) → Bilat(F) induced by [C] → [SC], when S|_{C} is injective, as described in the previous section.

Proposition 4.1.

(i) The homomorphism S_{∗} : Bilat(F) → Bilat(F) is surjective.

(ii) If S_{∗} is injective then Bilat(F) ≅ ℤ[1/N].

(iii) If Bilat(F) has finite rank (in particular, if F is SFT or sofic), then S_{∗} is an isomorphism.

Proof. (i) Every clopen set is a disjoint union of sets of the form C = [i_{0} … i_{r}]_{S}, so every element of Bilat(F) has the form [Σn_{C}C]. Surjectivity of S_{∗} then follows from the observation

S_{∗} : [[0i_{0} … i_{r}]_{S}] ↦ [[i_{0} … i_{r}]_{S}] .

(ii) Suppose S_{∗} is injective. Then any two S-cylinders of equal length define equivalent

elements of Bilat(F) (that is, [[i_{0} … i_{r−1}]_{S}] = [[i′_{0} … i′_{r−1}]_{S}]), because

(S_{∗})^{r} [[i_{0} … i_{r−1}]_{S}] = [X] = (S_{∗})^{r} [[i′_{0} … i′_{r−1}]_{S}] .

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 7

For every positive integer r, X is the disjoint union of N^{r} S-cylinders of length r. Now there is a unique homomorphism τ: Bilat(F) → ℚ such that τ([X]) = 1; this injective map τ sends each [[x_{0} … x_{r−1}]] to N^{−r}. The image of this map is ℤ[1/N].

(iii) If Bilat(F) has finite rank, then by the Fact 3.1, the surjection S_{∗} must be an isomor-

phism.

□

Corollary 4.2. If F is sofic (in particular, if F is SF T), then F is an SF T which is shift equivalent to some two-sided full shift σ_{J}.

Proof. If F is sofic, then Bilat(F) has finite rank. Then by Proposition 4.1, the rank of Bilat(F) is 1. It follows from Proposition 3.2 that F is an SFT shift equivalent to a full shift. □

Remark 4.3. Let J be the integer such that F is shift equivalent to σ_{J}. Then S_{N} may be viewed as an N-to-1 endomorphism of some power of σ_{J}, and it follows from Welch’s theorem ([H], Theorem 14.9) or its generalizations ([B], [T1], [T2]) that every prime dividing N must also divide J. But to show the same primes divide N and J requires more, since (for example) the rule (φx)_{n} = 3x_{n} + x_{n+1} (mod 6) defines a 2-to-1 but not positively expansive endomorphism φ of σ_{6}.

Proposition 4.4.

(i) The identity map on clopen subsets of X induces a group epimorphism Bilat(F) → Im(S).

(ii) This epimorphism is an isomorphism if the rank of Bilat(F) is finite.

Proof. Recall from Section 3 the definitions

Bilat(F) = ℤCO(X)/K(F)
Im(S) = ℤCO(X)/H(S)

To prove (i), we will prove that H(S) contains K(F). Suppose not. Then there is a formal sum Σn_{i}C_{i} in ℤCO(X) which lies in K(F) but not in H(S). Using the subdivision relation common to both K(F) and H(S), after passing to a different sum we may assume each C_{i} is an S-cylinder of the same length, r. Now Σn_{i} ≠ 0 because Σn_{i}C_{i} ∉ H(S). But then (S_{∗})^{r} : [Σn_{i}C_{i}] ↦ Σn_{i}[X] ≠ 0. This contradicts Σn_{i}C_{i} ∈ K(F), and finishes the proof of (i).

If the rank of Bilat(F) is finite, then by Proposition 4.1 this rank is 1, and the surjective homomorphism of rank 1 groups Bilat(F) ↠ Im(S) must be an isomorphism. □

Theorem 4.5. If F is sofic, then F is SFT and F is shift equivalent to some σ_{J}, a full shift on J symbols, where J and N are divisible by the same primes.

Proof. After Corollary 4.2, it remains to show that J and N are divisible by the same primes. However, Bilat(F) ≅ ℤ [\frac{1}{J} ] and Im(S) ≅ ℤ [\frac{1}{N} ]. Now the result follows from Proposition 4.4. □

Theorem 4.6. Suppose F is SF T. Then F and S have the same measure of maximal entropy.

Proof. In this case we have Bilat(F) ≅ Im(S) as quotients of ℤCO(X), and Im(S) ≅ ℤ [\frac{1}{N} ]. There is a unique homomorphism τ from this group into ℝ which sends [X] to 1. Let μ_{S} and μ_{F} denote the measures of maximal entropy for S and F. For [C] in Im(S), it is known that τ: [C] ↦ μ_{S}(C) ([BFF], Sec. 9). Likewise for [C] in Bilat(F), since F is irreducible SFT, τ: [C] ↦ μ_{F} (C) ([Kr1], Theorem 3.2). Therefore μ_{S} = μ_{F}. □

Remark 4.7. A similar dimension group proof scheme was used ([BFF], Theorem 9.1) to show that commuting onesided mixing SFT’s have the same measure of maximal entropy. In contrast, Nasu ([N2], Sec. 10) has given an example of commuting twosided mixing SFTs σ_{A} and σ_{B} such that ℚ(λ_{A}) ≠ ℚ(λ_{B}). This implies that the measures of maximal entropy for σ_{A} and σ_{B} do not assume the same set of values on clopen sets, and therefore are not equal. For this example, in addition G(A) and G(B) do not even have the same rank.

5. Multipliers

In this section we give background for the “multipliers”we use for the entropy constraints of the next section.

Let A be an irreducible nonnegative integral matrix with spectral radius λ > 1. Let σ_{A} : Σ_{A} → Σ_{A} be the associated edge SFT. Let u and v be positive vectors such that uA = λu, Av = λv and uv = 1. For a symbol (edge) e, we let u(e) denote u_{i} where i is the initial vertex of e, and similarly v(e) = v_{j} where j is the terminal vertex of e.

Let x[a, b] = {y ∈ Σ_{A} : y_{i} = x_{i}, a ≤ i ≤ b}. Then the measure μ of maximal entropy for the edge SFT σ_{A} is determined by

μ(x[a, b]) = u(x_{a})λ^{−(b−a+1)}v(x_{b}).

For x = … x_{−1}x_{0}x_{1} … in Σ_{A}, let π_{−}(x) = … x_{−2}x_{−1} and let π_{+}(x) = x_{0}x_{1} …. Let [e] denote {x ∈ Σ_{A} : x_{0} = e}. Let [e]_{+} = π_{+}[e] and [e]_{−} = π_{−}[e]. Then [e] = [e]_{−} × [e]_{+}.

On [e]_{−} determine a Borel measure μ_{−}^{e} by setting

μ_{−}^{e}(x[−n, −1]) = u(x_{−n})λ^{−n}

and on [e]_{+} determine a Borel measure μ_{+}^{e} by

μ_{+}^{e}(x[0, n]) = λ^{−(n+1)}v(x_{n}).

Define the measure μ^{e} as the restriction of μ to [e]. (Abusing notation: μ = ∑_{e} μ^{e}). For any Borel set C in X_{A}, define

μ_{−}(C) = ∑_{e} μ_{−}^{e}(C ∩ [e])
μ_{+}(C) = ∑_{e} μ_{+}^{e}(C ∩ [e]).

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 9

Then for any Borel set C,

μ_{−}(σ_{A}C) = \frac{1}{λ}μ_{−}(C)
μ_{+}(σ_{A}C) = λμ_{+}(C).

We will call (μ_{−}, μ_{+}) a conditional decomposition of μ. (The conditional decomposition is a simplified version of ideas from the ergodic theory of smooth hyperbolic systems [Ma], [S]. The measures μ_{−}^{e} and μ_{+}^{e} can be viewed as conditional measures obtained from μ^{e}, related closely to the conditional measures on stable and unstable sets discussed in Sec. 3 of [B].)

We made a concrete choice of (μ_{−}, μ_{+}) with respect to a particular Markov partition {[e]} and choice of associated eigenvectors u, v. We could have obtained another conditional decomposition of μ with another Markov partition. We could also have obtained a conditional decomposition above using the vertex sets {x ∈ X_{A} : the initial vertex of x_{0} is i} in place of the edge sets [e]. In any of these cases, for the resulting conditional decomposition (μ̃_{−}, μ̃_{+}) of μ, one can see from Prop. 3.2 of [B] that there will be a constant c > 0 such that

μ̃_{−} = cμ_{−}, μ̃_{+} = (\frac{1}{c})μ_{+}.

For the special case that σ_{A} = σ_{J}, a full shift on J symbols, we have an especially simple choice of (μ_{−}, μ_{+}):

μ_{−}(x[−n, −1]) = J^{−n}
μ_{+}(x[0, n]) = J^{−(n+1)}.

We can now summarize the background we need.

Theorem 5.1. Suppose σ_{A} is an irreducible SFT, A has spectral radius λ > 1, and φ is an Nto-1 local homeomorphism commuting with σ_{A}. Let (μ_{−}, μ_{+}) be a conditional decomposition of the measure of maximal entropy μ of σ_{A}. Let C be any nonempty clopen set such that the restriction of φ to C is injective.

(i) The ratios ℓ_{φ} = \frac{μ_{−}(φC)}{μ_{−}(C)}, r_{φ} = \frac{μ_{+}(φC)}{μ_{+}(C)} do not depend on C or the particular choice of conditional decomposition.

(ii) ℓ_{φ}r_{φ} = N.

(iii) μ(φC) = Nμ(C).

(iv) The numbers ℓ_{φ} and r_{φ} are units in the ring O_{λ}[\frac{1}{λ}]. (If λ is an integer J, then this

means the numbers ℓ_{φ} and r_{φ} are products of integral powers of primes dividing J.)

(v) If ψ is also a local homeomorphism commuting with σ_{A}, then ℓ_{φψ} = ℓ_{φ}ℓ_{ψ} and r_{φψ} = r_{φ}r_{ψ}.

(vi) Suppose V is homeomorphism such that V φV^{−1} = φ̃ and V σ_{A}V^{−1} = σÃ, so ℓφ̃ and rφ̃ may be computed w.r.t. σÃ. Then ℓ_{φ} = ℓφ̃ and r_{φ} = rφ̃.

Remark 5.2. If σ_{A} is an irreducible SFT and φ is a continuous map such that φσ_{A} = σ_{A}φ, then φ is open iff φ is constant to 1 iff φ is a local homeomorphism (this is contained in Nasu’s Theorem 6.5 in [N1]).

10 MIKE BOYLE AND ALEJANDRO MAASS

Examples 5.3. Let σ_{A} = σ_{J}, the full shift on J symbols. If N is a positive integer dividing a power of J, and ℓ, r are units on ℤ[\frac{1}{J}] such that ℓr = N, then there exists an N-to-1 endomorphism φ of σ_{J} with ℓ_{φ} = ℓ, r_{φ} = r (this can be proved by the method of Proposition 7.4). Here are a few examples.

(1) φ = σ. Then ℓ_{φ} = \frac{1}{J} , r_{φ} = J, N = 1.

(2) (φx)_{n} = x_{n−1} + x_{n+2} (mod J). Then ℓ_{φ} = J, r_{φ} = J^{2}, N = J^{3}.
(3) (φx)_{n} = x_{n+1} + x_{n+3} (mod J). Then ℓ_{φ} = \frac{1}{J} , r_{φ} = J^{3}, N = J^{2}.
(4) J = 6 and (φx)_{n} = 3x_{n} + x_{n+1} (mod 6). Then ℓ_{φ} = \frac{1}{3}, r_{φ} = 6, N = 2.

Remark 5.4. For σ_{A} a full shift, everything in Theorem (5.1) is a translation of (some of) Welch’s results as reported by Hedlund (Sections 14-15 of [H]). Those results have combinatorial statements which do not generalize to arbitrary irreducible SFT’s. The generalizations, using measures, are in Sec. 3 of [B]. The results in [B] like Welch’s are more general than the consequences collected in Theorem 5.1, but proofs for Theorem 5.1 can be obtained from the results of [B]. Caveat: our numbers ℓ_{φ}, r_{φ} are the reciprocals of the numbers L(φ), R(φ) used in [B].

Remark 5.5. In the next section we only need consider endomorphisms φ of σ_{A} in the case that σ_{A} is shift equivalent to some full shift. This means that for large enough k, (σ_{A})^{k} is conjugate to a full shift. The multipliers ℓ_{φ}, r_{φ} obtained by considering φ an endomorphism of σ_{A} are the same as those obtained by considering φ as an endomorphism of (σ_{A})^{k}, so here one may recover the full shift description of the multipliers by passing to a power of σ_{A}.

6. Entropy and primes

Below, S is the full onesided shift on N symbols and F is an automorphism of S such that F is conjugate to an irreducible SFT σ_{A}; that is, there is a homeomorphism U such that UF U^{−1} = σ_{A}. Then USU^{−1} = φ is an N-to-1, positively expansive local homeomorphism commuting with σ_{A}. We regard (σ_{A}, φ) as simply another presentation of (F, S). By Theorem 5.1(vi), the numbers ℓ_{φ}, r_{φ} do not depend on the choice of σ_{A} and U, so we may define ℓ_{S} = ℓ_{φ}, r_{S} = r_{φ}.

Theorem 6.1. Let F be an automorphism of S, the onesided full shift on N symbols with N > 1. Suppose F is conjugate to some SFT σ_{A}. Then ℓ_{S} > 1 and r_{S} > 1. If N is a power of a prime p, then so are ℓ_{S} and r_{S}.

Proof. Let X_{N} = ∏_{n≥0}{0, 1, ..., N − 1}, so F and S act on X_{N}. Let [i_{0}...i_{r}]_{S} denote {x ∈ X_{N} : x_{j} = i_{j}, 0 ≤ j ≤ r}. Then [i_{0} … i_{r}]_{S} ↦ [0i_{0} … i_{r}]_{S} induces a map γ_{0} on clopen sets, γ_{0}C = (S^{−1}C) ∩ [0]_{S}. Now view γ_{0} in the (σ_{A}, φ) presentation and consider C any nonempty clopen set. For k > 0, the restriction of φ^{k} to γ_{0}^{k}C is injective, and φ^{k}(γ_{0}^{k}C) = C. Because the

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 11

diameter of γ_{0}^{k}C goes to zero as k goes to ∞, for large k we must have

\frac{μ_{+}(γ_{0}^{k}C)}{μ_{+}(C)} < 1,

and therefore

(r_{φ})^{k} = \frac{μ_{+}(φ^{k}(γ_{0}^{k}C))}{μ_{+}(γ_{0}^{k}C)} = \frac{μ_{+}(C)}{μ_{+}(γ_{0}^{k}C)} > 1,

so r_{φ} > 1. Similarly ℓ_{φ} > 1. For N a power of a prime p, Theorem 5.1(iv) now implies that ℓ_{φ} and r_{φ} must be positive integers divisible by p. □

Corollary 6.2. Suppose S is the onesided full shift on N symbols, such that N is a power of a prime p and S has some automorphism F which is conjugate to a sofic shift.

Then p^{2} divides N.

Proof. By Corollary 4.2, F must be conjugate to an SFT σ_{A} such that σ_{A} is shift equivalent to a full shift on J symbols, where J is also a power of p. By Theorem 6.1, the numbers ℓ_{S}, r_{S} must be positive powers of p. By Theorem 5.1(iii), N = ℓ_{S}r_{S}, so p^{2} divides N. □

So for example, no automorphism of the onesided full shift on 5 symbols can be conjugate to an SFT (or sofic shift).

7. Conjectures

We will make three conjectures. Let S_{N} be the onesided full shift on N symbols.

Conjecture 7.1. Suppose F is an expansive automorphism of S_{N}. Then F is SFT.

Conjecture 7.2. Suppose F is an automorphism of S_{N} and F is conjugate to an SFT. Then F is conjugate to a full shift.

Conjecture 7.3. Suppose there exists an automorphism F of S_{N} = S, such that F is conjugate to an SFT and p is a prime dividing N. Then p divides both l_{S} and r_{S}, and in particular p^{2} divides N.

The conjectures 7.1, 7.2 are possibilities introduced by Nasu as questions (Question 3.a(2), p. 46, and Question 3.b, p.50, in [N2]). Independently, Nasu [N2] and Shereshevsky and Afraimovich [SA] proved Conjecture 7.2 in the case that (F, S) is conjugate to a pair (σ_{J}, ϕ) such that ϕ is given by a local rule x_{i} … x_{j} ↦ (ϕx)_{0} such that i, j are positive integers and the local rule is bipermutive. Our Theorems 4.5 and 6.1 support 7.1 and 7.2. From Theorem 9.2 it follows that all the conjectures hold for the class of expansive automata we consider in Section 9 (those satisfying r(F) = r(F^{−1}) = r̃(F) = 1). The rigid combinatorics underlying Theorem 9.2 suggest rigid combinatorics in general, as in the algebraic expansive situation considered by Kitchens [K1]. Therefore we elevate Nasu’s questions to conjectures, and add the third conjecture.

The conjectures together with our results imply the following: if F is an expansive homeomorphism of S_{N}, then F is conjugate to a full shift σ_{J}, such that (i) J and N are divisible by the same primes, and (ii) if p is a prime dividing N, then p^{2} divides N.

Proposition 7.4. Suppose J and N satisfy the conditions (i) and (ii) above. Then there is an automorphism F of S_{N} such that F is conjugate to σ_{J}.

Proof. First suppose N = p^{k} and J = p^{ℓ}, with ℓ ≥ 1 and k ≥ 2. Define an N-to-1 endomorphism φ of σ_{p} by the rule (φ_{x})_{n} = x_{−1} + x_{k−1} (mod p). Then φ is conjugate to S_{N} and it commutes with (σ_{p})^{ℓ} which is isomorphic to σ_{J}.

Next suppose N = p_{1}^{k(1)}...p_{t}^{k(t)}, with each k(i) ≥ 2, and J = p_{1}^{ℓ(1)}...p_{t}^{ℓ(t)} with each ℓ(i) ≥ 1. Let N(i) = p_{i}^{k(i)} and J(i) = p_{i}^{ℓ(i)}. Construct F_{i} as in the preceding paragraph, with F_{i} an automorphism of S_{N(i)} and F_{i} conjugate to σ_{J(i)}. Now F = ∏_{i=1}^{t} F_{i} is an automorphism of

S = ∏_{i=1}^{t} S_{N(i)}. Here S is conjugate to S_{N}, and F is conjugate to σ_{J}. □

8. Construction of one–sided invertible cellular automata

Let F: A^{ℕ} → A^{ℕ} be a onesided invertible cellular automaton. Let r(F) denote the radius of the shortest local rule defining F: that is, r(F) is the minimal nonnegative integer r such that for all x, the symbol (F x)_{0} is determined by x_{0} … x_{r}; analogously we define r(F^{−1}). In this section we give a constructive combinatorial characterization of the invertible F such that r(F) = r(F^{−1}) = 1. We remark, it is possible to have r(F^{−1}) larger than r(F).

For any positive integer k, by grouping symbols into k-blocks we can view F as a map F^{(k)} : (A^{k})^{ℕ} → (A^{k})^{ℕ}; and if 0 < r(F) ≤ k, then r(F^{k}) = 1. So any onesided invertible c.a. is topologically conjugate to a c.a. F such that r(F) = r(F^{−1}) = 1.

Let A^{∗} be the set of words appearing in A^{ℕ}. We say that a word w′ ∈ A^{∗} is an F - successor of w ∈ A^{∗}, and we use the shorthand w ⟶^{F} w′, if there are x, x′ ∈ A^{ℕ} such that F (wx) = w′x′. From F we define an equivalence relation on the alphabet A: a ∼_{F} b if and only if ∃ n ∈ ℕ, ∃ a_{0}, a_{1}, ..., a_{n} ∈ A, ∃ b_{0}, ..., b_{n−1} ∈ A, such that a_{0} = a, a_{n} = b, a_{i} ⟶^{F} b_{i} and a_{i+1} ⟶^{F} b_{i}, for i ∈ {0, ..., n − 1}. For a ∈ A, we denote by c_{F} (a) its equivalence class with respect to ∼_{F}. This gives a partition of A into equivalence classes, P_{F} = {c_{F} (a): a ∈ A}. Given F with r(F) = 1, define π_{F} : A → A by π_{F} (a) = F (aa).

With r(F) = 1, the map F is left permutive if for all α and b in A, there is a unique a in A such that F (ab) = α. In this case we let π_{F,b} denote the permutation a ↦ F (ab). For simplicity we will abbreviate π_{F,b} as π_{b} when the context is clear.

Lemma 8.1. Suppose F is a onesided invertible c.a. such that r(F) = r(F^{−1}) = 1. Then the following hold.

(1) F is left permutive and π_{F} is a permutation.

(2) If c_{F} (a) = c_{F} (b), then π_{a} = π_{b}.

(3) π_{b}(c_{F} (a)) = π_{F} (c_{F} (a)), for all a, b.

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 13

Proof. (1) F is left permutive because F is surjective. The map π_{F} describes the map on fixed points of the shift, so the invertibility of F implies π_{F} is a permutation.

(2) It suffices to show F (ca) = F (cb) under the assumption a ⟶^{F} α and b ⟶^{F} α, where α is some element of A. Let x, x′, y, y′ ∈ A^{ℕ} such that F (ax) = αy and F (bx′) = αy′. Since r(F) = r(F^{−1}) = 1 and F (cax) = βαy, we deduce that F^{−1}(βα) = c. Therefore, F^{−1}(βαy′) = cbx′ and F (cb) = β, which proves the lemma.

(3) Put α = F (ab). Since F is invertible there is a unique a′ ∈ A such that π_{F} (a′) = α. Then α is a common successor of a and a′, which implies that a ∼_{F} a′. This fact proves that α ∈ {π_{F} (a′): a′ ∈ c_{F} (a)}. □

Theorem 8.2. Let P be a partition of A into equivalence classes, with c(a) denoting the class containing a. Let F : A^{ℕ} → A^{ℕ} be a cellular automaton with r(F) = 1 satisfying the following conditions:

(1) F is left permutive and π_{F} is a permutation.

(2) If c(b′) = c(b), then π_{b} = π_{b′}.

(3) π_{b}(c(a)) = π_{F} (c(a)), for all a, b. Then F is an invertible cellular automaton with r(F^{−1}) = 1.

Conversely, if F is a onesided invertible cellular automaton with r(F) = r(F^{−1}) = 1, then the properties (1)-(3) hold for the partition P_{F}.

Proof. Let a_{0}, a_{1} ∈ A. Using the assumption that π_{F} is a permutation, we let b be the symbol such that π_{F} (b) = a_{1}. Using the left permutivity, we let a be the unique symbol such that F (ab) = a_{0}.

Now if b′ is any symbol in A such that b′ ⟶^{F} a_{1}, then by property (3) we have that a_{1} is in π_{F} (b′). Then π_{F} (c(b)) and π_{F} (c(b′)) have nonempty intersection. Since π_{F} is a permutation, it follows that c(b′) = c(b). Then by property (2), F (ab) = F (ab′) = a_{0}. Because F is left permutive, it follows that a is the unique element in A such that a ⟶^{F} a_{0}a_{1}. This exhibits the local rule F^{−1}(a_{0}a_{1}) = a.

The converse claim is the preceding lemma. □

In the preceding theorem, the partition P_{F} refines P. This refinement can be proper (consider the identity map). The construction is practical. To construct, freely pick any partition of A to be P, and freely pick any permutation of A to be π_{F}. Then for each class c(a) = [a], freely pick as π_{a} = π_{[a]} any permutation p satisfying (i) p(b) = b if b ∈ [a] and (ii) for each class [a′], p : [a′] ↦ π[a′].

The following proposition relates the partitions P_{F} and P_{F^{−1}}.

Proposition 8.3. Let F : A^{ℕ} → A^{ℕ} be an invertible cellular automaton with r(F) = r(F^{−1}) = 1. Then for all a, b in A,

a ∼_{F} b  ⟺  π_{F} (a) ∼_{F^{−1}} π_{F} (b) .

In particular c_{F^{−1}}(π_{F} (a)) = π_{F} (c_{F} (a)), and the rule c_{F} (a) ↦ c_{F^{−1}}(π_{F} (a)) induces a bijection P_{F} → P_{F^{−1}}.

Proof. Let a, b ∈ A such that a ∼_{F} b. By definition, there are b_{0}, ..., b_{N} ∈ A and c_{0}, ..., c_{N−1} ∈

A verifying: a = b_{0}, b = b_{N} and for i ∈ {0, ..., N − 1} b_{i} ⟶^{F} c_{i}, b_{i+1} ⟶^{F} c_{i}. On the other

hand, since for α, β ∈ A, α ⟶^{F} β if and only if β ⟶^{F^{−1}} α, we can deduce that π_{F} (b_{0}) ⟶^{F^{−1}} b_{0},

c_{0} ⟶^{F^{−1}} b_{0}, c_{0} ⟶^{F^{−1}} b_{1}, c_{1} ⟶^{F^{−1}} b_{1}, ......, c_{N−1} ⟶^{F^{−1}} b_{N−1}, c_{N−1} ⟶^{F^{−1}} b_{N}, π_{F} (b_{N}) ⟶^{F^{−1}} b_{N}. This

fact implies that π_{F} (b_{0}) = π_{F} (a) ∼_{F^{−1}} π_{F} (b_{N}) = π_{F} (b). Using the same arguments with respect to F^{−1} we conclude that a ∼_{F} b if and only if π_{F} (a) ∼_{F^{−1}} π_{F} (b).

The concluding sentence of the proposition follows directly. □

9. A class of expansive examples

In this section, F will denote an invertible onesided cellular automaton, F : A^{ℕ} → A^{ℕ}, such that r(F) = r(F^{−1}) = 1. We write a point of A^{ℕ} as x = x_{0}x_{1} …. We let x̃_{i} = (F^{i}x)_{0}, x̃ = (x̃_{i})_{i∈ℤ}, and X̃ = {x̃: x ∈ A^{ℕ}}. Here the map F is expansive if and only if the map x ↦ x̃ is injective, and if the map is injective then it defines a topological conjugacy from (A^{ℕ}, F) to the subshift (X̃, σ). In this case the onesided shift on A^{ℕ} can be presented by some block code of radius r̃ = r̃(F), so x̃_{−r̃} … x̃r̃ determines x_{1}.

We will give a constructive combinatorial characterization of those F for which r̃(F) = 1, and we will describe their dynamics. (For an interesting example in this class giving an idealized physical model, see [C]).

Theorem 9.1. Let F : A^{ℕ} → A^{ℕ} be an invertible cellular automaton with r(F) = r(F^{−1}) = 1. The cellular automaton F is expansive with r̃(F) = 1 if and only if

(1) ∀ a, b ∈ A, |c_{F} (a) ∩ c_{F^{−1}}(b)| ≤ 1, and

(2) ∀ a, b, b′ ∈ A, (F (ab) = F (ab′) ⇒ b ∼_{F} b′) .

In this case, 1*. ∀ a, b ∈ A, |c_{F} (a) ∩ c_{F^{−1}}(b)| = 1, 2*. ∀ a, b, b′ ∈ A, (F^{−1}(ab) = F^{−1}(ab′) ⇒ b ∼_{F^{−1}} b′), and 3*. |A| = J^{2} for some J in ℕ such that |c_{F} (a)| = J for all a in A.

Proof. First let us see that property (2) implies property (2*). Suppose F^{−1}(ab) = F^{−1}(ab′). Then there exist symbols α, β, γ, β′, γ′ such that F (αβγ) = ab and F (αβ′γ′) = ab′. Now property (2) implies β ∼_{F} β′. Also β ⟶^{F} b and β′ ⟶^{F} b′, and therefore b ∼_{F^{−1}} b′, proving (2*).

For the sufficient conditions let us assume F is an invertible cellular automaton with r(F) = r(F^{−1}) = 1 satisfying properties (1) and (2) (and therefore also (2*)). To prove that F is expansive it is enough to show x̃_{−1}x̃_{0}x̃_{1} determines x_{1}. Suppose x ∈ A^{ℕ}. From properties (2) and (2*) we deduce there are unique classes c_{F} ∈ P_{F} and c_{F^{−1}} ∈ P_{F^{−1}}, depending on x̃_{−1}x̃_{0}x̃_{1}, such that x_{1} ∈ c_{F} ∩ c_{F^{−1}}. Therefore, by property (1), x_{1} is the unique element of c_{F} ∩ c_{F^{−1}}. This procedure provides the required block map x̃_{−1}x̃_{0}x̃_{1} ↦ x_{1}.

EXPANSIVE INVERTIBLE ONESIDED CELLULAR AUTOMATA 15

Now we turn to the necessary conditions. Suppose F is expansive with r̃(F) = 1. Take a^{∗} ∈ A such that |c_{F} (a^{∗})| = max{ |c_{F} (a)|: a ∈ A }. It follows from Proposition 8.3 that |c_{F} (a^{∗})| = max{ |c_{F^{−1}}(a)|: a ∈ A }. On the other hand, from Theorem 8.2 we have F (ba′) = F (ba′′) for any b ∈ A and a′, a′′ ∈ c_{F} (a^{∗}), and since r̃(F) = 1, F^{−1}(ba′) ≠ F^{−1}(ba′′). Therefore,

|c_{F^{−1}}(b)| ≥ |{ b′ ∈ A: b →^{F^{−1}} b′}| ≥ |c_{F} (a^{∗})| = max{ |c_{F^{−1}}(a)|: a ∈ A }. We conclude there is a

positive integer J such that for any a in A, |c_{F} (a)| = |c_{F^{−1}}(a)| = J.

To prove property (2) holds, suppose it does not. Then there are b, b′, a ∈ A such that F (ab) = F (ab′) and c_{F} (b) ≠ c_{F} (b′). In this case, by using the same arguments as in the last paragraph we deduce that |c_{F^{−1}}(a)| ≥ 2J. This is a contradiction. This verifies property (2), and therefore also (2*).

Next note that for any x = x_{0}x_{1} …, the triple (x_{0}, c_{F} (x_{1}), c_{F^{−1}}(x_{1})) determines x̃_{−1}x̃_{0}x̃_{1}, which determines x_{1}. Therefore c_{F} (x_{1}) ∩ c_{F^{−1}}(x_{1}) = {x_{1}}. This proves (1).

Now put m = |P_{F} | = |P_{F^{−1}}|. By property (1), every element of P_{F} intersects J distinct elements of P_{F^{−1}}, so m ≥ J. On the other hand, from property (2) we deduce that for each symbol a, there are at least J distinct symbols b such that a ⟶^{F} b; these F -successors of a must lie in the same element of P_{F^{−1}}, so m ≤ J. Therefore m = J. Because A is the disjoint union of the J members of P_{F}, and each member contains exactly J symbols, we have |A| = J^{2}, and (3*) holds. Finally, by (1) each member of P_{F} must intersect at least J members of P_{F^{−1}}, so each member of P_{F} must intersect every member of P_{F^{−1}}. This verifies (1*) and finishes the proof. □

Theorem 9.2. Let F : A^{ℕ} → A^{ℕ} be an expansive invertible onesided cellular automaton such that r(F) = r(F^{−1}) = r̃(F) = 1. Then S_{F} is topologically conjugate to a full shift on \sqrt{|A|} symbols.

Proof. By Theorem 9.1(3*), \sqrt{|A|} is a positive integer J = |P_{F} |. Let Σ_{J} denote the full shift on J symbols, with alphabet P_{F}. We already have (A^{ℕ}, F) topologically conjugate to (X̃, σ), so it suffices to define a shift commuting bijection c : X̃ → Σ_{J}. We define c(x̃) = cx̃ by setting (cx̃)_{i} = c_{F} (x̃_{i}). By Theorem 9.1(2) and Lemma 8.1(2), we have for all a, b in A that

(9.3)  c_{F} (a) = c_{F} (b)  ⟺  π_{a,F} = π_{b,F} .

If a ⟶^{F} b, then π_{b,F^{−1}} = (π_{a,F})^{−1}. It follows that if a ⟶^{F} b, then c_{F} (a) determines c_{F^{−1}}(b), and therefore the pair (c_{F} (a), c_{F} (b)) determines c_{F} (b) ∩ c_{F^{−1}}(b) = {b}. It follows that for all x̃, the word c_{F} (x̃_{−1})c_{F} (x̃_{0}) determines x_{0}. This proves that the map c is injective.

By induction we also observe that for all n > 0 and for all x̃,

(9.4)  x̃_{0} and (cx̃)_{1} … (cx̃)_{n} determine x̃_{0} … x̃_{n} .

To prove that c is surjective, it suffices to prove the claim: for all n ≥ 0, there are J^{n+1} distinct words (cx̃)_{0} … (cx̃)_{n}. The claim is obvious for n = 0. Suppose n > 0 and the claim holds for n − 1. Using the induction hypothesis, let E be a set of J^{n} points x such that the restriction to E of the map x ↦ (cx̃)_{0} … (cx̃)_{n−1} is injective. Let E′ = {ax: a ∈ A, x ∈ E}, so |E′| = J^{n+1}. Using 9.3 above, one can see that the restriction to E′ of the map x ↦ x̃_{0} … x̃_{n}

is injective. This shows there are J^{n+1} distinct words x̃_{0} … x̃_{n}.

On the other hand, by 9.4 the number of words x̃_{0} … x̃_{n} is at most |{x̃_{0}}||{(cx̃)_{1} … (cx̃)_{n}}| ≤

(J)(J^{n}), and equality implies that for every a ∈ A and x ∈ A^{ℕ} there is some y such that ỹ_{0} = a

and (cỹ)_{i} = (cx̃)_{i}, 1 ≤ i ≤ n. Thus there are J^{n+1} words (cx̃)_{0} … (cx̃)_{n}. □

References

[AH] N. Aoki and K. Hiraide, Topological theory of dynamical systems, recent advances, North-Holand, Amsterdam, 1994.

[BM] F. Blanchard and A. Maass, Dynamical properties of expansive onesided cellular automata, Israel J. Math., 99 (1997), 149-174.

[B] M. Boyle, Constraints on the degree of a sofic homomorphism and the induced multiplication of measures on unstable sets, Israel J. Math. 53 (1986), no.1, 52-68.

[BFF] M. Boyle, D. Fiebig and U. Fiebig, A dimension group for local homeomorphisms and endomorphisms of onesided shifts of finite type, J. reine angew. Math., 497 (1997), 27-59.

[BFK] M. Boyle, J. Franks and B. Kitchens, Automorphisms of onesided subshifts of finite type, Ergod. Th. & Dynam. Sys. 10 (1990), 421-449.

[BL] M. Boyle and D. Lind, Expansive subdynamics, Trans. AMS 349 (1997), no.1, 55-102.

[BMT] M. Boyle, B. Marcus and P. Trow, Resolving maps and the dimension group for shifts of finite type, Memoirs AMS 377, 1987.

[C] M. Courbage, On the approach to statistical equilibrium in an infinite particle lattice dynamic model, J. Math. Phys. 30, (1989), no.8, 1840-1850.

[H] G.A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math.Systems Th. 3 (1969), 320-375.

[Hi] K. Hiraide, Dynamical systems of expansive maps on compact manifolds, Sugaku Expositions 5 (1992), no.2, 133-154.

[KR] K.H. Kim and F.W. Roush, Williams Conjecture is false for irreducible subshifts, Annals of Math., to appear.

[K1] B. Kitchens, Expansive dynamics on zero dimensional groups, Ergod. Th. & Dynam. Sys. 7 (1987), 249-261.

[K2] B. Kitchens, Symbolic Dynamics, One-sided, two-sided and countable state Markov shifts, Springer-Verlag, 1998.

[Kr1] W. Krieger, On dimension functions and topological Markov chains, Inventiones Math. 56 (1980), 239-250.

[Kr2] W. Krieger, On sofic systems I, Israel J. Math 48(1984), no.4, 305-330.

[Ku] P. Kůrka, Languages, equicontinuity and attractors in cellular automota, Ergod. Th. & Dynam. Sys., 17 (1997), 417-433.

[LM] D. Lind and B. Marcus, Symbolic Dynamics and Coding, Cambridge University, 1995.

[Ma] G.A. Margulis, Certain measures associated with U-flows on compact manifolds, Functional Anal. Appl. 4 (1970), No. 1, 55-67.

[MM] G. Manzini and L. Margara, Invertible linear cellular automata over Z_{m}: algorithmic and dynamical aspects, J. Comput. System Sci. 56 (1998), no. 1, 60–67.

[N1] M. Nasu, Constant-to-one and onto global maps of homomorphisms between strongly connected graphs, Ergod. Th. & Dynam. Sys. (1983), 3, 387-413.

[N2] M. Nasu, Textile systems for endomorphisms and automorphisms of the shift, Memoirs AMS 546 (1995).

[N3] M. Nasu, Maps in symbolic dynamics, in: Lecture Notes of the Tenth KAIST Mathematics Workshop 1995, ed. Geon Ho Choe, Korea Advanced Institute of Science and Tenology Mathematics Research Center, Taejon, Korea (1996), 67 pages.

[SA] M.A. Shereshevsky and V.S. Afraimovich, Bipermutative cellular automata are topologically conjugate to the one-sided Bernoulli shift, Random & Computational Dynamics 1 (1992), 91-98.

[S] Ya. G. Sinai, Markov partitions and C-diffeomorphisms, Functional Anal. Appl. 2 (1968), 64-89.

[T1] P. Trow, Degrees of constant-to-one factor maps, Proc. Amer. Math. Soc. 103 (1988), no. 1, 184-188.

[T2] P. Trow, Degrees of finite-to-one factor maps, Israel J. Math. 71 (1990), no. 2, 229–238.

[W] R.F. Williams, Classification of subshifts of finite type, Annals of Math 98 (1973), 120-154; erratum 99 (1974), 380-381.

Department of Mathematics, University of Maryland, College Park, MD 20742-4015, U.S.A.

   E-mail address: mmb@math.umd.edu

Departamento de Ingeniería Matemática, Universidad de Chile, Casilla 170/3 correo 3, Santiago, Chile.

   E-mail address: amaass@dim.uchile.cl