{'fraction_non_alphanumeric': 0.08222794381253463, 'fraction_numerical': 0.012938760877358797, 'mean_word_length': 3.394099957038522, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 31, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Positive expansiveness versus network dimension in symbolic dynamical systems

A `symbolic dynamical system' is a continuous transformation F:X-->X of a closed perfect subset X of A^V, where A is a finite set and V is countable. (Examples include subshifts, odometers, cellular automata, and automaton networks.) The function F induces a directed graph structure on V, whose geometry reveals information about the dynamical system (X,F). The `dimension' dim(V) is an exponent describing the growth rate of balls in the digraph as a function of their radius. We show: if X has positive entropy and dim(V)>1, and the system (A^V,X,F) satisfies minimal symmetry and mixing conditions, then (X,F) cannot be positively expansive; this generalizes a well-known result of Shereshevsky about multidimensional cellular automata. We also construct a counterexample to a version of this result without the symmetry condition. Finally, we show that network dimension is invariant under topological conjugacies which are Holder-continuous.

Let X be Cantor space (the compact, perfect, zero-dimensional metrizable topological space, which is unique up to homeomorphism). A Cantor dynamical system is a continuous self-map Φ : X −→X . In addition to its intrinsic interest, the class of Cantor systems is important because it has two universal properties. First, any topological dynamical system on a compact metric space is a factor of a Cantor system; see [Kůr03, Corollary 3.9, p.106] or [BS89, p.1241]. Second, the Jewet-Krieger Theorem says that any ergodic measurepreserving system can be represented as a uniquely ergodic, minimal Cantor system [Pet89,§4.4,p.188].
If A is a finite set, and V is a countably infinite set, then the product space A V is a Cantor space. Thus, any Cantor dynamical system can be represented as a self-map Φ : A V −→A V , or more generally, as a self-map Φ : X −→X , where X ⊂ A V is a pattern space (a closed perfect subset of A V ). We refer to the structure (A V , X , Φ) as a symbolic dynamical system. At an abstract topological level, any pattern space X is homeomorphic to Cantor space, so a symbolic dynamical system is simply a Cantor dynamical system. What distinguishes symbolic dynamical systems is a particular way of representing X as a subset of some Cartesian product A V (so that an element of X corresponds to some V-indexed 'pattern' of 'symbols' in the alphabet A).
The network of Φ is the digraph structure ( • →) on V defined as follows: for all v, w ∈ V, we have v • → w if and only if the value of Φ(x) w depends nontrivially on the value of x v . We say that (V, • →) has dimension δ if the cardinality of a ball of radius r grows like r δ as r→∞. (Note that δ is not necessarily an integer.) For example, if Φ : A Z D −→A Z D is a cellular automaton, then its network is just a Cayley digraph on Z D ; the dimension of this network is D.
This paper explores the relationship between network dimension and the properties of (X , Φ) as a topological dynamical system. In §1, we formally define the dimension of a network (V, • →) and the entropy of a pattern space on V. In §2, we generalize an important result of Shereshevsky (later reproved by Finelli, Manzini, and Margara) about multidimensional cellular automata. We show: if dim(V, •→) > 1 (more generally, if (V, • →) has 'superlinear connectivity'), and X has positive entropy and a mild 'mixing' condition, and the system (A V , X , Φ) has some minimal symmetries, then (X , Φ) cannot be positively expansive (Theorem 2.7). In §3, we consider the propagation of a symbolic dynamical system, and its relationship with sensitivity and equicontinuity. In §4, we show that a 'naive' generalization of Shereshevsky's result cannot be true, by constructing a positively expansive symbolic dynamical system with network dimension two. Thus, any result similar to Theorem 2.7 must impose at least some additional technical conditions.
The counterexample in §4 also shows that network dimension is not invariant under topological conjugacy; thus, it cannot be treated as a structural property of an abstract Cantor dynamical system (X , Φ). However, in §5, we propose to augment the system (X , Φ) with a metric which is Lipschitz for Φ; we show that network dimension is a structural property of this 'metric' Cantor system, as it is invariant under all biHölder conjugacies (Corollary 5.8). Sections 2-5 are logically independent, and can be read in any order.

Preliminaries
Let A be a finite set (called an alphabet) endowed with the discrete topology. Let V be a countably infinite set of points (called vertices). Endow A V with the Tychonoff product topology. A pattern space is a closed perfect subset X ⊆ A V . A symbolic dynamical system is triple (A V , X , Φ), where X ⊆ A V is a pattern space and Φ : A V −→A V is a continuous function such that Φ(X ) ⊆ X . (Sometimes we will simply indicate this as (X , Φ) when A and V are clear from context.) Example 1.1. (a) Let V = Z D × N E for some D, E ≥ 0 and let X ⊂ A Z D ×N E be a subshift (i.e. closed, shift-invariant subset). Then X is a pattern space. Fix z ∈ Z D × N E , and let σ z : A Z D ×N E −→A Z D ×N E be the associated shift map. Then (A Z D ×N E , X , σ z ) is a symbolic dynamical system. (c) For all v ∈ V, let A v ⊆ A. Let X := v∈V A v ; then X is a pattern space. If Φ : X −→X is a continuous self-map, then (A V , X , Φ) is a symbolic dynamical system, sometimes called an automaton network, because it can be interpreted as an infinite network of interacting finite-state automata.
(d) Gromov has initiated a study of 'proalgebraic' dynamical systems, which are (loosely speaking) projective limits of polynomial self-mappings of algebraic varieties [Gro99]. If the base field F is finite (e.g. F = Z /p ), then a 'proalgebraic space' can be represented as a pattern space with alphabet F; hence a proalgebraic system is a symbolic dynamical system. ♦ The analysis of subshifts and cellular automata depends heavily on the highly symmetric structure created by shift-invariance. Likewise, Gromov's analysis of proalgebraic systems requires a structure of 'local' symmetries (called holonomies). We will also make use of some minimal symmetry assumptions in §2. However, in general, symbolic dynamical systems do not have any appreciable symmetries.
For any x ∈ X and U ⊂ V, we define Proof. For each v ∈ V, the existence of a local rule φ v is proved by exactly the same argument as the Curtis-Hedlund-Lyndon theorem for cellular automata (see e.g. [Kůr03,Theorem 5.2,p.190]; observe that the construction of the local rule does not depend on shift-invariance). The difference is that there may be different local rules at different vertices. 2 The set U(v) is called the input neighbourhood of Φ at v, and denoted Φ in (v). The function φ v : A Φ in (v) −→A is called the local rule of Φ at w.
is a partial order (it is reflexive and transitive). We write v w if v ; w and w ; v. Thus, ( ) is an equivalence relation; the ( )-equivalence classes of V are called the biconnected components of (V, • →). We say that (V, Let (∼) be the smallest equivalence relation on V which contains ( • →). Equivalently, for any u, w ∈ V, we have u ∼ w if either (1) u ; w; or (2) w ; u; or (3) (inductively) there exists some v ∈ V such that u ∼ v ∼ w. The (∼)-equivalence classes are the connected components of V; if v ∼ w for all v, w ∈ V, then we say that (V, • →) is connected. If Φ : A V −→A V is any continuous function, then we can define a digraph relation ( • →) is as defined by Lemma 1.2 above. This digraph is called the network of Φ. Figure 1 depicts the network of the odometer Φ : A N −→A N from Example 1.3 (b). ♦ Connectivity dimension. Let (V, • →) be an infinite digraph (e.g. the network of a continuous function Φ : , then we refer to their common value as "dim v (V, • →)", the connectivity dimension of (V, • →) at v, and we say that (V, • →) is dimensionally regular at v.
(a) Let δ ∈ [0, ∞), and suppose (For example, suppose β v (r) = C r δ + p(r), where C is a constant and p is a polynomial of degree less than δ.) is any graph whose automorphism group acts transitively, then (V, • →) is 'almost' a Cayley digraph; for a survey of the well-developed dimension theory for such graphs, see [MW89,§5] or [IS91]. ♦ The dimension of a Cayley digraph is always an integer. However, there exist 'selfsimilar' graphs with fractional connectivity dimensions [McC91]. Connectivity dimension is closely related to properties of diffusion processes and electrical conductance on graphs [Tel89,Tel90,Tel95,Tel01], the existence of periodic points in 'majority vote' networks [Mor95,GH00], and also arises in certain models of quantum gravity [NR99,NR98].
Not all digraphs are dimensionally regular. For example, consider a digraph which consists of increasingly large 'clumps' which are spaced at increasingly long intervals along an infinite line-graph; by making the clumps and the intervals between them grow fast enough, one can force dim v (V, Furthermore, not all connected, dimensionally regular digraphs are dimensionally homogeneous. For example, let V 1 ∼ = Z be a biconnected Cayley digraph of Z, and let V 2 ∼ = Z 2 be a biconnected Cayley digraph of Z 2 . Let V = V 1 ⊔ V 2 , with connections n • → (n, 0) for all n ∈ Z ∼ = V 1 . Then V 1 and V 2 are biconnected components of V, with V 1 upstream from V 2 . Clearly, dim v (V k ) = k for all v ∈ V k and k = 1, 2.
Proof. If v ; w, then there exists R > 0 such that v ∈ B(w, R). Thus, for all r ∈ N, we have B(v, r) ⊆ B(w, R + r), hence |B(v, r)| ≤ |B(w, R + r)|. Thus If W ⊂ V is a biconnected component of (V, • →), then Lemma 1.7 says that every vertex in W has the same connectivity dimension. In particular, if (V, • →) is biconnected and dimensionally regular, then it is dimensionally homogeneous.
Entropy. Let (V, • →) be a digraph, and let X ⊂ A V be a pattern space. For any v ∈ V, we define the lower and upper topological entropies of X around v by: (2)

Positive expansion versus network connectivity
An abstract Cantor dynamical system (X , Φ) is posexpansive if it is topologically conjugate to a one-sided shift. In particular, let (A V , X , Φ) be a symbolic dynamical system. Fix a finite subset W ⊂ V, let B := A W and define the function Φ N W : for all x ∈ X .
Then (X , Φ) is posexpansive if and only if there is some finite subset W ⊂ V (called a posexpansive window) such that the function Φ N W is an injection. If Y := Φ N W [X ] ⊆ B N and σ : B N −→B N is the shift map, then σ(Y) ⊆ Y, and Φ N W is a topological conjugacy from (X , Φ) to the system (Y, σ).
For any W ⊂ V and T ∈ N, define Φ for all x ∈ X .
Then we have W = W 0 ⊆ W 1 ⊆ W 2 ⊆ W 3 ⊆ · · ·; the sequence {W t 0 } ∞ t=0 is called the (X , Φ)-panorama of W. Clearly, W is a posexpansive window for Φ if and only if Shereshevsky has shown that multidimensional cellular automata can never be posexpansive. To be precise, he showed: if (G, ·) is any group with growth dimension D ≥ 2 (e.g. G = Z D ), and X ⊂ A G is a subshift with positive topological entropy, and Φ : A G −→A G is an X -preserving cellular automaton, then the system (X , Φ) is not posexpansive; see [She93, Corollary 2] or [She96, Theorem 1.1]. The special case when G = Z D and X = A Z D was later reproved in [FMM98,Theorem 4.4]. In this section, we will generalize this result to any symbolic dynamical system satisfying some mild symmetry and mixing conditions.
Let X ⊆ A V be a pattern space; if τ is a subisometry and τ * (X ) = X , then we say τ is a subsymmetry of X .
Example 2.1. Let V = Z D × N E for some D, E ≥ 0 (or some other finitely generated monoid), with the Cayley digraph structure induced by some finite generating set. Fix w ∈ V, and define the shift map τ w : V−→V by τ w (v) := v + w; then τ is a subisometry of the Cayley digraph. If X ⊆ A Z D ×N E is a subshift, then τ is a subsymmetry of X .
Note. Subsymmetries of X are not necessarily injective. For example, the unilateral shift on A N is a subsymmetry, but it is many-to-one. ♦ (b) Let ψ : A × A−→A be a binary operator (e.g. a group operator). Let (A V , Φ) be an arbitrary symbolic dynamical system (perhaps with no symmetries), such as the one in Figure 2(A). Define V := V × Z, and identify A e V with (A V ) Z in the obvious way; a generic element of A e V could be indicated as a := [a n ] n∈Z , where a n ∈ A V for all n ∈ Z. Let ] for all n ∈ Z and v ∈ V; this yields the connection network in Figure 2(B). Then σ is a subsymmetry of (A e V , Φ). ♦ We say that the pattern space X has weak independence if there is some constant ǫ > 0 such that, for any disjoint balls B 1 , . . . , B N ⊂ V, This can be seen as a kind of 'topological mixing' condition -it means that the information contained in balls B 1 , . . . , B N −1 has limited power to predict the contents of ball B N .
, and X has weak independence.
In particular, the space n .
. (However, there may exist shorter paths from τ (v) to τ (w) which do not arise as τ -images of paths from v to w).
Here (△) is the triangle inequality, and (@) is by part (a).
To see (c), let r := d(v, w) (finite because v ∼ w). Then for any n ∈ N, Here, (@) is by part (a), and  Figure 3. Here, for any (z, n) ∈ V, we have (z, n) • → (z, n ′ ) whenever n ′ = n ± 1, and we also have (z, n) • → (z ′ , n) whenever z ′ = z+2 n . Thus: then v has superlinear connectivity. (For example, if V is a Cayley digraph of a group with growth dimension D ≥ 2, then every vertex has superlinear connectivity.) (b) If v ; w and v has superlinear connectivity, then w has superlinear connectivity. ♦ The main result of this section is the following: Theorem 2.7 Let (A V , X , Φ) be a symbolic dynamical system with a moving subsymmetry. If X has weak independence, and there exists some v ∈ V with superlinear connectivity such that h v (X ) > 0, then the system (X , Φ) is not posexpansive.
Before proving Theorem 2.7, we give two concrete corollaries.
Corollary 2.8 Let (A V , X , Φ) be a symbolic dynamical system with a moving subsymmetry, such that X has weak independence. Suppose that either Proof. If X = A V , then clearly X has weak independence, and h(X ) = log 2 |A| > 0. Now apply Corollary 2.8(a). 2 The proof of Theorem 2.7 consists of two lemmas concerning the 'entropy' of a pattern space relative to a subsymmetry. Let X ⊆ A V be a pattern space and let τ : V−→V be a subsymmetry of X . For any finite F ⊂ V, we define We then define the upper τ -entropy of X by Lemma 2.10 Let (V, • →) be a digraph, and let X ⊆ A V be a pattern space with weak independence. Suppose there exists v ∈ V with superlinear connectivity and h v (X ) > 0. If τ : V−→V is any moving subsymmetry of X , then h(X , τ ) = ∞.
Proof. Let ǫ > 0 be as in equation (5 where ( * ) is by equation (5), and ( †) is because τ is a subsymmetry of X (so |X F | = X τ k (F) for all k ∈ Z). Combining equations (6) and (8), we get h(X , τ, F) : It follows from defining equation (7) that Proof. For any x, x ′ ∈ X , and any T ∈ N, we have Proof. (a) follows from equation (4). To see (b), let x, x ′ ∈ X . Then is by the induction hypothesis, and ( * ) is by part (b).
(d) is the same argument as in part (b), but using part (c) instead of part (a). 3 Claim 2 Now, for any H > 0, we can find some finite subset F ⊂ V such that h(X , τ, F) > H (because h(X , τ ) = ∞). Equation (4) yields some t such that F ⊆ W t 0 . Thus, for any N ∈ N, and all n ∈ [0...N], we have
But clearly, h(Y, σ) ≤ log 2 |B| = log 2 |A W 0 | = |W 0 | · log 2 |A| < ∞, because A and W 0 are finite. Contradiction. 2 Proof of Theorem 2.7. Combine Lemmas 2.10 and 2.11. 2 Remarks. (a) Observe that Lemma 2.11 is really a statement about (X , Φ) as an abstract Cantor dynamical system with a subsymmetry; it does not depend on any specific representation of (X , Φ) as a symbolic dynamical system (i.e. any specific embedding X ⊂ A V for some A and V). As such, Lemma 2.11 is an interesting result in itself. (b) Theorem 2.7 applies even if τ and its iterates are the only symmetries of (A V , X , Φ). In particular, we do not require the symmetry group of (A V , X , Φ) to itself have growth dimension greater than 1.
(c) The 'weak independence' condition in Theorem 2.7 and Lemma 2.10 is probably not necessary. ♦.

Propagation, Sensitivity, and Equicontinuity
If Φ : A V −→A V is continuous, then for all t ∈ N, the function Φ t : A V −→A V is also continuous; hence we can apply Lemma 1.2 to define input T )). In general, this inequality may be strict.
Let (A V , X , Φ) be a symbolic dynamical system, and We say that x is a sensitive point if it is v-sensitive for some v ∈ V. (If d is any compatible metric on X , then there is some ǫ such that, for all x, y ∈ X , x v = y v =⇒ d(x, y) > ǫ ; thus, this definition is equivalent to the ordinary metric definition of 'sensitivity').
Proposition 3.1 Let (A V , X , Φ) be a symbolic dynamical system.
Since X is compact, we find some increasing sequence {r n } ∞ n=1 ∈ N such that the subsequence {y rn } ∞ n=1 converges in X to some point x. Equation (14) implies that the subsequence {z rn } ∞ n=1 also converges to x. But for all n ∈ N, condition (b) says that Φ t(rn) (y rn ) v = Φ t(rn) (z rn ) v , which means that either (i) Φ t(rn) (y rn ) v = Φ t(rn) (x) v or (ii) Φ t(rn) (z rn ) v = Φ t(rn) (x) v (or both). In case (i), define x n := y rn , while in case (ii), define x n := z rn ; then we obtain a sequence {x n } ∞ n=1 converging to x, and satisfying condition (13).
"⇐=" For any R ∈ N, we must find some T ∈ N such that ρ v (T ) > R. Let x ∈ X be a v-sensitive point, and let {x n } ∞ n=1 ⊂ X be a sequence converging to x and satisfying condition (13). Now, there exist some n ∈ N such that x n B(v,R) = x B(v,R) ; but there also exists some T such that Φ Furthermore, this path must have length L > R (even after removing repeated entries), because w T ∈ B(v, R). Thus, (v) ≥ |{w T , . . . , w 2 , w 1 }| = L > R, as desired. This works for any R ∈ N; hence the function ρ v is unbounded.

(b) follows immediately from (a). 2
Let W ⊂ V be some finite subset. We say that Φ is W-equicontinuous if there exists a finite subset U ⊂ V containing W (called the envelope of W), such that: For all x, y ∈ X , We say that Φ is equicontinuous if Φ is W-equicontinuous for every finite subset W ⊂ V.
(If d is any compatible metric on X , then for any ǫ > 0 there is some finite subset W ⊂ V such that for all x, y ∈ X , x W = y W =⇒ d(x, y) < ǫ . Likewise, for any finite U ⊂ V, there is some δ > 0 such that for all x, y ∈ X , d(x, y) < δ =⇒ x U = y U . Thus, our definition is equivalent to the ordinary metric definition of 'equicontinuity'). A topological dynamical system (X , Φ) is an odometer if (X , Φ) is an inverse limit of a sequence of finite, periodic dynamical systems. That is: where, for all n ∈ N, X n is a finite set, φ n : X n −→X n is a cyclic permutation, and π n : (X n+1 , φ n+1 )−→(X n , φ n ) is a factor mapping.
For any x ∈ X , let O x := {Φ t (x) ; t ∈ N} be the Φ-orbit closure of x; then (O x , Φ) is itself a topological dynamical system. The system (X , Φ) is an odometer bundle if, for every x ∈ X , the system (O x , Φ) is an odometer. Thus, (X , Φ) can be decomposed into a (possibly infinite) disjoint union of (possible non-isomorphic) odometers.
For example, for all n ∈ N, let X n be a finite set, and let φ n : X n −→X n be a permutation (possibly with multiple disjoint orbits). Suppose (X , Φ) arises as the inverse limit (16); then (X , Φ) is an odometer bundle. (a) Let W ⊂ V be a finite subset. If ρ w is bounded for all w ∈ W, then Φ is Wequicontinuous.
Proof. (a) For all w ∈ W, there is some R w such that ρ w (t) < R w for all t ∈ N. Let R := max w∈W R w ; then R is finite because W is finite. Let U := B(W, R).
Claim 1: For all w ∈ W, and all t ∈ N, and just as in the proof of Proposition 3.1 "⇐=", construct a path from v to w of length L > R. Conclude that ρ w (t) > R. Contradiction.
3 Claim 1 Suppose x U = y U . Then for all w ∈ W, and all t ∈ N, Claim 1 implies Thus, U is an envelope for W. (c) Let W 1 ⊂ W 2 ⊂ W 3 ⊂ · · · be an increasing sequence of finite sets, with ∞ n=1 W n = V. For all n ∈ N, let B n := X Wn , and let Φ N Wn : For all n ∈ N, let π n : X W n+1 −→X Wn be the projection (i.e. π n (x W n+1 ) := x Wn for all x ∈ X ). Define π n : Y n+1 −→Y n as follows: if y ∈ Y n+1 , write y = [y t ] ∞ t=0 where y t ∈ X W n+1 for all t ∈ N; then define π n (y) := [ π n (y t )] ∞ t=0 . Clearly, π n : (Y n+1 , σ n+1 )−→(Y n , σ n ) is a factor mapping, and (X , Everything so far is true for any symbolic dynamical system. Now we use equicontinuity.
Claim 2: For all n ∈ N, Y n is finite and σ n : Y n −→Y n is a permutation.
Proof. Let U n ⊂ V be the envelope of W n (a finite set). For any x, x ′ ∈ X , if x Un = x ′ Un , then Φ N Wn (x) = Φ N Wn (x ′ ). Thus, |Φ N Wn (X )| ≤ |X Un | -in other words, |Y n | ≤ |X Un |. But |X Un | is finite because U n is finite. Thus, Y n is finite. Thus, σ n is bijective (because it is surjective).
3 Claim 2 Thus, we have represented (X , Φ) as an inverse limit of finite permutation dynamical systems; thus, (X , Φ) is an odometer bundle. 2 For example: any symbolic dynamical system with the network in Figure 1 must be equicontinuous.

An expansive system of dimension two
The symmetry condition in Theorem 2.7 is probably not necessary. However, some sort of condition is required beyond merely superlinear connectivity. To demonstrate this, we will construct an example of a symbolic dynamical system which is posexpansive, despite having connectivity dimension two. For any vertex v n ∈ V, the state of v n is an ordered pair an bn , where a n , b n ∈ Z /2 .
(Clearly h(X ) ≥ log 2 (2) = 1, and X has weak independence.) The local rule of each cell depends entirely upon its one or two input cells, and not on itself, as follows. For any n ∈ V • , we define φ n : X n+1 −→X n by φ n a n+1 b n+1 = a n+1 0 -that is, φ n simply copies the first coordinate of n+1 (or 2 n+1 ) into n .
The cell 2 m k is connected to both (m k )+1 and 2 m (k+1) . Its local rule φ m k : X (m k )+1 × X m (k+1) −→X m k is defined as follows: Proof. Define Γ 1 : X −→Z /2 N and Γ 2 : = [a 0 , a 1 , a 2 , a 3 , a 4 , a 5 , . . .]; Thus, Γ := Γ 1 × Γ 2 : then Φ is conjugate to Φ via Γ, so it suffices to show that the M be some initial state, and let (a t , b t ) := Φ t (a 0 , b 0 ) for all t ∈ N. Let J ∈ N, and consider the sequence of the first m J states of cell 2 0 : Clearly, the information in x J is sufficient to determine the values of a 0 0 , a 0 1 , a 0 2 , . . . , a 0 m J , because for all t ∈ N we have a t 0 = a 0 t , because Φ just acts like a unilateral shift on the 'a' coordinates. It remains to show that x J is also sufficient to determine the values of .
3 Claim 1 In particular, Claim 1 implies that, for any j ∈ [1...J], the information in x J determines b 0 m j . Thus, given x J , we can recover a 0 0 , a 0 2 , a 0 3 , . . . , a 0 m J and also b 0 0 , b 0 2 , b 0 6 , . . . , b 0 m J . This works for all J ∈ N; thus, {2 0 } is a posexpansive window for (X , Φ). 2 Lemma 4.2 (a) Φ has quadratic propagation 2 (lim inf   (b) From (a) we have dim v (V, • →) ≥ 2 for all v ∈ V 2 (because |B(v, r)| ≥ ρ v (r) for all r ∈ N). But every vertex is downstream from some element of V 2 ; thus, Lemma 1.7 implies that dim v (V, • →) ≥ 2 for all v ∈ V. On the other hand, it is easy to see that

Lipschitz metrics on Cantor systems
The counterexample of §4 shows that connectivity dimension is not invariant under topological conjugacy: some systems with dimension two are conjugate to subshifts of (A N , σ), and the system (A N , σ) has dimension one. (Likewise, §4 shows that the growth rate of the propagation function ρ is not a conjugacy invariant.) However, we will now show that connectivity dimension is invariant under a slightly refined notion of conjugacy, once we impose a suitable metric structure on the pattern space X (see Corollary 5.8 below).
Let X be any Cantor space, and let d : X 2 −→R + be a metric compatible with the Cantor topology on X . The pair (X , d) will be called a Cantor metric space. Let Φ : X −→X be any continuous self-map. We say Φ is d-Lipschitz if there is a constant λ > 0 such that, for any x, In this case, d is called a Lipschitz metric for Φ. The smallest λ satisfying eqn.(18) is called the d-Lipschitz constant of Φ. More generally, a Lipschitz pseudometric is a pseudometric d : X 2 −→R + satisfying eqn.(18).
Example 5.1. Let (A V , X , Φ) be a symbolic dynamical system, with network (V, • →). For any v ∈ V and λ > 1, we define the pseudometric d v,λ : The pseudometric d v,λ in Example 5.1 is not necessarily a true metric, unless ∞ r=0 B(v, r) = V, which is not the case unless v is downstream from every element of v. For many digraphs, there is no vertex with this property. Instead, let us say that a subset U ⊂ V is an estuary if, for every v ∈ V, there exists some u ∈ U with v ; u. For example, V itself is an estuary. If (V, • →) is biconnected, then any nonempty subset of V (even a singleton) is an estuary. More generally, if U contains at least one vertex from each biconnected component of V, then U is an estuary.
Example 5.2. Let U ⊂ V be an estuary. Let c := (c u ) u∈U ∈ R U + be a sequence of positive coefficients for the elements in U, such that u∈U c u < ∞ (this is possible because U is always countable, because V is countable). Fix λ > 1, and for all u ∈ U, let d u,λ be the pseudometric from Example 5.1. Define the metric d c,λ : X × X −→R + by Then d c,λ is a true metric, because ∞ r=0 B(U, r) = V, because U is an estuary. Also, d c,λ satisfies eqn.(18), because each of the pseudometrics d u,λ satisfies eqn.(18) (by Example 5.1). Thus, d c,λ is a Lipschitz metric for Φ. We say that d c,λ is based at U. ♦ Observe that the metric on A V in Example 5.2 can be defined for any digraph structure on (V, • →) (without reference to any particular map Φ : A V −→A V ). Any Cantor dynamical system can be represented as a symbolic dynamical system, so Example 5.2 shows that any Cantor dynamical system admits a Lipschitz metric. Indeed, it admits many such metrics, because the Lipschitz constant λ, the estuary U, and the coefficient system c in Example 5.2 can be chosen arbitrarily.
Dimension and Entropy. Let (X , d) be a metric space. For any ǫ > 0, a open ǫ-cover is a covering of X by open sets whose diameters are each at most ǫ. Let N ǫ (X ) be the minimal cardinality of any open ǫ-cover of (X , d). We define (Here, α, β, γ > 1 are any constants, and need not be equal -the limits in (20) are independent of the choice of α, β, γ). If dim(X , d) = dim(X , d), then we refer to their common value as "dim(X , d)", the dimension of (X , d). Note that formula (20)  (23) Let U ⊆ V and let c = (c u ) u∈U be some coefficient sequence. Suppose we enumerate U as U = {u j } ∞ j=0 ; then we can define c ′ j := c u j for all j ∈ N; then we say c has precipitous decay if the sequence {c ′ j } ∞ j=1 has precipitous decay.
Proof. Let W ⊂ V be any finite set. For all w ∈ X W , let w := {x ∈ X ; x W = w} be the cylinder set defined by w. The collection C W := { w ; w ∈ X W } is an open cover of X .
(c) follows immediately from (b), because if U is finite, then clearly (V, • →) has uniform dimension on U, and c has precipitous decay. . If X ⊆ A V is a pattern space, and d : X 2 −→R + is a Cantor metric, then we say that d is dimensionally compatible if dim(X , d) = dim(V, • →). Proposition 5.4 suggests that for 'most' dimensionally homogeneous digraphs, any pattern space with nonzero entropy admits a dimensionally compatible metric. In light of Example 5.2, this means that 'most' symbolic dynamical systems admit dimensionally compatible Lipschitz metrics. For example, we have the following result: Corollary 5.5 Let (V, • →) be a dimensionally homogeneous digraph with a finite estuary U (e.g. a biconnected digraph). There exists a metric d on A V such that, if X ⊆ A V is any pattern space with h u (X ) > 0 for some u ∈ U, then dim(X , d) = dim(V, • →). Furthermore, if Φ : A V −→A V is a continuous map with network ( • →), then Φ is d-Lipschitz.
Proof. Let d be a metric based on U, as in Example 5.2. Then dim(X , d) ≤ If X ⊆ A Z 2 is any subshift with positive topological entropy, then Proposition 5.4 says dim(X , d) = dim(Z 2 , • →) = 2. If Φ : A Z 2 −→A Z 2 is any cellular automaton whose local rule has neighbourhood {0} ⊔ B, then Φ is d-Lipschitz, by Example 5.2.
(b) By a similar argument, if G is any finitely generated group with growth dimension D and a biconnected Cayley digraph structure, then we can construct a Cantor metric d on A G such that, if X ⊆ A G is any subshift with positive topological entropy, then dim(X , d) = D. Furthermore, if Φ is any CA on X , we can design d to be Φ-Lipschitz.
It follows that the connectivity network dimension of a symbolic dynamical system is invariant under biHölder topological conjugacy.
Corollary 5.8 Let (A V , X 1 , Φ 1 ) and (B W , X 2 , Φ 2 ) be two symbolic dynamical systems, and let d 1 and d 2 be dimensionally compatible Lipschitz metrics on X 1 and X 2 respectively (e.g. as given by Corollary 5.5).

Conclusion
For any symbolic dynamical system (A V , X , Φ), one can define a digraph structure ( • →) on V. We have shown that certain topological-dynamical properties of (A V , X , Φ) are related to the connectivity (V, • →), and in particular, to its dimension. What other dynamical properties of (A V , X , Φ) are influenced by the geometry of (V, • →)? One could also go the other way. Starting with an infinite digraph (V, • →), consider a randomly generated self-map Φ : A V −→A V , such that ( • →) is the network of Φ. What are the 'generic' (i.e. almost-certain) properties of (A V , Φ), and how do they depend on the geometry of (V, • →)? For example, §3 suggests the following conjecture: If dim(V, • →) ≤ 1, then almost surely, (A V , Φ) is equicontinuous. If dim(V, • →) > 1, then almost surely, (A V , Φ) is sensitive. (The intuition here comes from percolation theory). However, Figure 4 shows that something more than dimension is required; this network has dimension 2, but it has an infinite number of cut points, so a random mapping Φ with this network is almost-surely equicontinuous. Thus, the conjecture above must be augmented with some kind of 'regularity' condition on (V, • →). A closely related question: Suppose we take a system (A V , Φ) and 'mutate' it, by changing the local rule at a small number of vertices. What topological-dynamical properties are 'robust' under such mutations, and how does this depend on the geometry of (V, • →)?