Introduction
Cellular automata (CAs) are discrete-time dynamical systems defined by the synchronous iteration of a local rule on an infinite lattice. They were originally introduced by von Neumann as abstract models of self-reproducing systems [40 ] , and later studied systematically within symbolic dynamics and theoretical computer science. A cellular automaton consists of a regular grid of variables, typically indexed by Z D \mathbb{Z}^{D} Z D , each taking values in a finite alphabet, and evolving in discrete time according to a rule that updates every variable based only on the states of a finite neighborhood (for an introduction to CA theory, see, e.g., [9 , 22 , 23 ] ).
Despite the simplicity of their local definition, cellular automata are capable of generating a wide range of dynamical behaviors, from highly regular dynamics to complex and chaotic evolutions (see, e.g., [43 ] ).
CAs have been the subject of significant research and are applied in various fields, including computer science, physics, mathematics, biology, and chemistry, for purposes such as simulating natural phenomena, generating pseudo-random numbers, processing images, analyzing universal computation models, and cryptography (see for example [3 , 11 , 12 , 27 , 35 ] ).
From a mathematical perspective, the Curtis-Hedlund-Lyndon theorem provides a complete characterization of cellular automata as exactly the continuous maps on the full shift that commute with the shift action [23 ] .
A central goal in the theory of cellular automata is to quantify dynamical complexity. Among the most important invariants, topological entropy measures the asymptotic rate at which distinguishable orbit segments proliferate, and it is widely used as an indicator of chaotic behavior in symbolic dynamics and cellular systems (see for example [6 , 26 , 32 , 38 ] ). For cellular automata, entropy admits a concrete combinatorial interpretation: it can be expressed through the growth rate of the number of distinct space-time patterns occurring in the evolution of the automaton [26 ] (see Proposition 3 for arbitrary dimension). This viewpoint makes entropy particularly natural for CAs, as it directly quantifies the production of new patterns in space-time.
The problem of computing topological entropy for cellular automata has been extensively studied and is known to exhibit strong algorithmic limitations. In a seminal paper, Hurd, Kari, and Culik proved that the topological entropy of one-dimensional cellular automata is not computable, showing in particular that there is no algorithm deciding whether the entropy is zero [26 ] . This result established topological entropy as an intrinsically intractable invariant for general cellular automata and initiated a line of research on its computational complexity.
Subsequent work further clarified the scope of these negative results. Guillon and Zinoviadis showed that the entropies of one-dimensional cellular automata are exactly the right-computable real numbers, while in dimension two the class of achievable entropies becomes strictly larger, encompassing Σ 2 \Sigma_2 Σ 2 real numbers and infinity [21 ] . These results provide a precise computability-theoretic classification of cellular automaton entropies, highlighting a sharp distinction between dimensions. More recently, it has been shown that undecidability persists even under strong dynamical constraints, such as reversibility, as the problem of deciding whether a reversible one-dimensional cellular automaton has zero entropy remains undecidable [24 ] .
On the positive side, computability of entropy has been established for several restricted but structurally meaningful classes of cellular automata. D’Amico, Manzini, and Margara proved that the entropy is computable for linear cellular automata over Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z and for positively expansive cellular automata [10 ] . These results indicate that additional algebraic or dynamical rigidity can restore algorithmic tractability.
The present work fits into this latter direction. By exploiting the algebraic structure of a finite group alphabet and the endomorphism property of the global rule, we identify a new, natural class of one-dimensional cellular automata for which topological entropy becomes effectively computable. Our results also settle questions left open in the literature. In [8 ] the computation of the topological entropy of a GCA was reduced to the case of alphabets that are either elementary abelian groups ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n or products of isomorphic non-abelian simple groups, and was carried out only in the surjective non-abelian case; the abelian case is treated here (Theorem 4), while the non-surjective non-abelian case is avoided by a refinement of the decomposition, based on normal F \mathcal{F} F -invariant subgroups instead of fully invariant ones (Lemma 11 ). In higher dimensions, Shereshevsky [39 ] showed that a cellular automaton on the two-dimensional full shift cannot be expansive, and conjectured that its topological entropy is either 0 0 0 or + ∞ +\infty + ∞ (see [34 ] ). For general CAs the conjecture does not hold, since in every dimension D ≥ 2 D \ge2 D ≥ 2 there exist CAs with finite positive entropy [33 ] . Morris and Ward pointed out that a special case of the conjecture concerns CAs which are endomorphisms of the group structure of the full shift; they formulated an algebraic analogue of the question and answered it for mixing endomorphisms of compact abelian groups commuting with a completely positive entropy Z d \mathbb{Z}^d Z d -action [34 ] . Theorem 6 settles this special case in every dimension D ≥ 2 D \ge2 D ≥ 2 , for every finite group alphabet and without any mixing assumption: the topological entropy of a D D D -GCA is either 0 0 0 or + ∞ +\infty + ∞ .
In this paper we focus on group cellular automata (GCAs). Let G G G be a finite group. The full shift G Z G^{\mathbb{Z}} G Z inherits a natural group structure via component-wise multiplication, and a GCA is a CA whose global map F : G Z → G Z \mathcal{F}:G^{\mathbb{Z}}\to G^{\mathbb{Z}} F : G Z → G Z is a group endomorphism. Such systems arise naturally in the study of algebraic dynamics and have been systematically investigated in the literature [4 , 8 , 14 ] .
Our main result shows that the algebraic constraints imposed by the group structure lead to a strong structural simplification of the entropy computation. We introduce two families of finite objects that capture, separately, the left-moving and right-moving information in space-time. More precisely, for each time t t t we consider the sets of left and right traces T − ( F , t ) T^{-}(\mathcal{F},t) T − ( F , t ) and T + ( F , t ) T^{+}(\mathcal{F},t) T + ( F , t ) obtained by evolving configurations that are trivial on one side. We then define two one-sided growth rates
H − ( F ) = lim t → ∞ log ∣ T − ( F , t ) ∣ t , H + ( F ) = lim t → ∞ log ∣ T + ( F , t ) ∣ t , \mathcal{H}^{-}(\mathcal{F})=\lim_{t\to\infty}\frac{\log\left|T^{-}(\mathcal{F},t)\right|}{t},\qquad\mathcal{H}^{+}(\mathcal{F})=\lim_{t\to\infty}\frac{\log\left|T^{+}(\mathcal{F},t)\right|}{t}, H − ( F ) = t → ∞ lim t log ∣ T − ( F , t ) ∣ , H + ( F ) = t → ∞ lim t log ∣ T + ( F , t ) ∣ ,
and we prove (Theorems 1 and 2) that for every one-dimensional group cellular automaton F \mathcal{F} F on a finite group alphabet G G G , the topological entropy satisfies
H ( F ) = H − ( F ) + H + ( F ) . \mathcal{H}(\mathcal{F}) = \mathcal{H}^{-}(\mathcal{F}) + \mathcal{H}^{+}(\mathcal{F}). H ( F ) = H − ( F ) + H + ( F ) .
As a consequence, the topological entropy is completely determined by the growth rate of a fixed width family of space-time patterns, denoted by T ( F , t , 0 ) T(\mathcal{F},t,0) T ( F , t , 0 ) , arising in the evolution of the automaton. This reduction from arbitrarily large space-time windows to a uniformly bounded width yields an effective procedure for computing the topological entropy (Theorem 3). We also show that the topological entropy of a one-dimensional GCA is always the logarithm of a positive integer dividing ∣ G ∣ l F + r F |G|^{l_{\mathcal{F}}+r_{\mathcal{F}}} ∣ G ∣ l F + r F , where l F l_{\mathcal{F}} l F and r F r_{\mathcal{F}} r F are the left and right radii of F \mathcal{F} F (Corollary 1).
In Section 5 we turn to linear GCAs over ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^{n} ( Z / p Z ) n , whose global rule is described by a matrix M M M of Laurent polynomials. Following the algebraic approach of Akın, Dikranjan, Giordano Bruno and Toller [2 ] , we pass to the Pontryagin dual, on which the dual of the automaton acts on the discrete group of finite configurations, and we use the Bridge Theorem [15 , 42 ] relating topological and algebraic entropy. The algebraic entropy turns out to be the rank of a module over the polynomial ring F p [ t ] \mathbb{F}_{p}[t] F p [ t ] , which can be read off the characteristic polynomial χ M \chi_{M} χ M of M M M . In dimension one this yields
H ( F ) = ( E M + − E M − ) log p , \mathcal{H}(\mathcal{F}) = (E_{M}^{+} - E_{M}^{-}) \log p, H ( F ) = ( E M + − E M − ) log p ,
where [ E M − , E M + ] [E_{M}^{-},E_{M}^{+}] [ E M − , E M + ] is the smallest interval containing 0 0 0 and all exponents appearing in the coefficients of χ M \chi_{M} χ M (Theorem 4); in dimension D ≥ 2 D \ge2 D ≥ 2 the entropy is either 0 0 0 or + ∞ +\infty + ∞ . Combined with a refinement of the decomposition of GCAs introduced in [8 ] , this provides a second, explicit, proof of the computability of the topological entropy of one-dimensional GCAs (Remark 2). Finally, we prove that a D D D -dimensional GCA, with D ≥ 2 D \ge2 D ≥ 2 , is either equicontinuous with zero topological entropy, or sensitive to initial conditions with infinite topological entropy (Theorem 6). As a consequence, the topological entropy of group cellular automata is computable in every dimension (Corollary 4). Finally, we give an explicit algorithm, running in polynomial time for every fixed dimension, which computes the topological entropy of a GCA from its local rule (Theorem 8).
The paper is organized as follows. Section 2 recalls the basic definitions of CAs and GCAs in arbitrary dimension. In Section 3 we review topological entropy and its space-time characterization for cellular automata. Section 4 contains the proof of the decomposition theorem and the resulting computability statement. Section 5 contains the explicit formula for linear GCAs over ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^{n} ( Z / p Z ) n in every dimension. Section 6 deals with D D D -dimensional GCAs, D ≥ 2 D \ge2 D ≥ 2 . Section 7 analyzes the computational complexity of the resulting procedure.
CAs and GCAs
In this section, we review the fundamental definitions and key results related to CAs and GCAs. For additional definitions and results, we refer the reader to those introduced in [14 ] . We give the definitions in an arbitrary dimension D ≥ 1 D \ge1 D ≥ 1 ; at the beginning of each of the following sections we specify whether the dimension is arbitrary or D = 1 D = 1 D = 1 .
Configurations. Let D ≥ 1 D \ge1 D ≥ 1 be an integer and let G G G be a finite set. A (D D D -dimensional) configuration is any function from Z D \mathbb{Z}^{D} Z D to G G G , i.e., an element of G Z D G^{\mathbb{Z}^{D}} G Z D . Given a configuration c ∈ G Z D c \in G^{\mathbb{Z}^{D}} c ∈ G Z D and v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D , the value of c c c at position v v v is denoted by c v c_v c v , and for B ⊆ Z D B \subseteq\mathbb{Z}^{D} B ⊆ Z D we denote by c ∣ B c|_{B} c ∣ B the restriction of c c c to B B B . For v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D we let ∥ v ∥ ∞ = max i ∣ v i ∣ \lVert v\rVert_{\infty} = \max_i |v_i| ∥ v ∥ ∞ = max i ∣ v i ∣ , and for w ≥ 0 w \ge0 w ≥ 0 we let B w = [ − w , w ] D B_w = [-w,w]^{D} B w = [ − w , w ] D . We equip G Z D G^{\mathbb{Z}^{D}} G Z D with the prodiscrete topology, that is, the product topology obtained by endowing each factor G G G with the discrete topology. With this topology, G Z D G^{\mathbb{Z}^{D}} G Z D is a compact topological space. Since G G G is finite, G Z D G^{\mathbb{Z}^{D}} G Z D is also metrizable. Indeed, the set G Z D G^{\mathbb{Z}^{D}} G Z D can be equipped with the standard Tychonoff distance d d d defined as
∀ c , c ′ ∈ G Z D : d ( c , c ′ ) = { 0 if c = c ′ 2 − Δ ( c , c ′ ) otherwise \forall c,c' \in G^{\mathbb{Z}^{D}}:\quad d(c,c') =
\begin{cases}
0 & \text{if } c=c'\\
2^{-\Delta(c,c')} & \text{otherwise}
\end{cases} ∀ c , c ′ ∈ G Z D : d ( c , c ′ ) = { 0 2 − Δ ( c , c ′ ) if c = c ′ otherwise
where Δ ( c , c ′ ) = min { ∥ j ∥ ∞ : j ∈ Z D and c j ≠ c j ′ } \Delta(c,c') = \min\{\lVert j\rVert_{\infty}: j \in\mathbb{Z}^{D}\ \text{and}\ c_j \ne c'_j\} Δ ( c , c ′ ) = min {∥ j ∥ ∞ : j ∈ Z D and c j = c j ′ } . The topology induced by the Tychonoff distance coincides with the prodiscrete topology. Note that d ( c , c ′ ) < 2 − w d(c,c') < 2^{-w} d ( c , c ′ ) < 2 − w if and only if c c c and c ′ c' c ′ coincide on B w B_w B w . For a finite set B ⊆ Z D B \subseteq\mathbb{Z}^{D} B ⊆ Z D and u ∈ G B u \in G^{B} u ∈ G B , the cylinder determined by u u u is the set
C y l ( B , u ) = { c ∈ G Z D : c ∣ B = u } . Cyl(B,u) = \{c \in G^{\mathbb{Z}^{D}} : c|_{B} = u\}. C y l ( B , u ) = { c ∈ G Z D : c ∣ B = u } .
Cylinders are clopen and form a basis of the prodiscrete topology; in particular, for every c ∈ G Z D c \in G^{\mathbb{Z}^{D}} c ∈ G Z D and w ≥ 0 w \ge0 w ≥ 0 , the open ball of radius 2 − w 2^{-w} 2 − w centered at c c c is the cylinder C y l ( B w , c ∣ B w ) Cyl(B_w,c|_{B_w}) C y l ( B w , c ∣ B w ) .
Cellular automata. For w ∈ Z D w \in\mathbb{Z}^{D} w ∈ Z D , the shift σ w : G Z D → G Z D \sigma^{w}:G^{\mathbb{Z}^{D}} \to G^{\mathbb{Z}^{D}} σ w : G Z D → G Z D is defined by
∀ c ∈ G Z D , ∀ v ∈ Z D : σ w ( c ) v = c v + w . \forall c \in G^{\mathbb{Z}^{D}},\ \forall v \in\mathbb{Z}^{D}:\quad\sigma^{w}(c)_v = c_{v+w}. ∀ c ∈ G Z D , ∀ v ∈ Z D : σ w ( c ) v = c v + w .
A (D D D -dimensional) C A CA C A on G G G is any continuous function F : G Z D → G Z D \mathcal{F}:G^{\mathbb{Z}^{D}} \to G^{\mathbb{Z}^{D}} F : G Z D → G Z D which is also shift commuting, i.e., F ∘ σ w = σ w ∘ F \mathcal{F} \circ\sigma^{w} = \sigma^{w} \circ\mathcal{F} F ∘ σ w = σ w ∘ F for every w ∈ Z D w \in\mathbb{Z}^{D} w ∈ Z D . By the Curtis-Hedlund-Lyndon theorem [23 ] , any C A CA C A can be equivalently defined by means of a local rule f : G k → G f:G^{k} \to G f : G k → G together with a finite set V f = { v 1 , … , v k } ⊆ Z D V_f = \{v_1,\ldots,v_k\} \subseteq\mathbb{Z}^{D} V f = { v 1 , … , v k } ⊆ Z D of pairwise distinct vectors, called the neighborhood , as follows:
∀ c ∈ G Z D , ∀ v ∈ Z D : F ( c ) v = f ( c v + v 1 , … , c v + v k ) . \forall c \in G^{\mathbb{Z}^{D}},\ \forall v \in\mathbb{Z}^{D}:\quad\mathcal{F}(c)_v = f(c_{v+v_1},\ldots,c_{v+v_k}). ∀ c ∈ G Z D , ∀ v ∈ Z D : F ( c ) v = f ( c v + v 1 , … , c v + v k ) .
Group cellular automata. Let G G G be a finite group with identity element e e e . The set G Z D G^{\mathbb{Z}^{D}} G Z D is itself a group under the component-wise operation induced by the group operation of G G G . We denote by e Z D ∈ G Z D e^{\mathbb{Z}^{D}} \in G^{\mathbb{Z}^{D}} e Z D ∈ G Z D the configuration taking the value e e e at every position; that is, e Z D e^{\mathbb{Z}^{D}} e Z D is the identity element of the group G Z D G^{\mathbb{Z}^{D}} G Z D . Clearly, when equipped with the prodiscrete topology, G Z D G^{\mathbb{Z}^{D}} G Z D turns out to be a compact topological group. A configuration c ∈ G Z D c \in G^{\mathbb{Z}^{D}} c ∈ G Z D is said to be finite if the number of positions v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D such that c v ≠ e c_v \ne e c v = e is finite. A (D D D -dimensional) C A CA C A F : G Z D → G Z D \mathcal{F}:G^{\mathbb{Z}^{D}} \to G^{\mathbb{Z}^{D}} F : G Z D → G Z D is said to be a D D D -G C A GCA GC A if F \mathcal{F} F is an endomorphism of the group G Z D G^{\mathbb{Z}^{D}} G Z D . In that case, the local rule of F \mathcal{F} F is a homomorphism f : G k → G f:G^{k} \to G f : G k → G . For 1 ≤ i ≤ k 1 \le i \le k 1 ≤ i ≤ k , setting h i ( g ) = f ( e , … , e , g , e , … , e ) h_i(g)=f(e,\ldots,e,g,e,\ldots,e) h i ( g ) = f ( e , … , e , g , e , … , e ) , with g g g in the i i i -th position, defines endomorphisms h 1 , … , h k h_1,\ldots,h_k h 1 , … , h k of G G G with pairwise commuting images, and f ( g 1 , … , g k ) = h 1 ( g 1 ) ⋯ h k ( g k ) f(g_1,\ldots,g_k)=h_1(g_1)\cdots h_k(g_k) f ( g 1 , … , g k ) = h 1 ( g 1 ) ⋯ h k ( g k ) for all g 1 , … , g k ∈ G g_1,\ldots,g_k \in G g 1 , … , g k ∈ G ; conversely, every family of endomorphisms with pairwise commuting images defines in this way a homomorphism G k → G G^k \to G G k → G (see [14 Thm. 1] ). We then write f = ( h 1 , … , h k ) f=(h_1,\ldots,h_k) f = ( h 1 , … , h k ) .
The one-dimensional case. When D = 1 D=1 D = 1 , or when the dimension is clear from the context, we simply speak of CAs and GCAs. For D = 1 D=1 D = 1 we write σ = σ 1 \sigma=\sigma^1 σ = σ 1 , so that σ ( c ) i = c i + 1 \sigma(c)_i=c_{i+1} σ ( c ) i = c i + 1 , and we denote by ρ = σ − 1 \rho=\sigma^{-1} ρ = σ − 1 the right shift, i.e., ρ ( c ) i = c i − 1 \rho(c)_i=c_{i-1} ρ ( c ) i = c i − 1 . For i ≤ j i\le j i ≤ j we write c [ i , j ] = c i ⋯ c j ∈ G j − i + 1 c_{[i,j]}=c_i\cdots c_j\in G^{j-i+1} c [ i , j ] = c i ⋯ c j ∈ G j − i + 1 . Moreover, for a one-dimensional CA F \mathcal{F} F with neighborhood V f ⊆ Z V_f\subseteq\mathbb{Z} V f ⊆ Z we define l F l_{\mathcal{F}} l F and r F r_{\mathcal{F}} r F as follows
l F = ∣ min ( V f ∪ { 0 } ) ∣ and r F = ∣ max ( V f ∪ { 0 } ) ∣ , (1) l_{\mathcal{F}}=\left|\min(V_f\cup\{0\})\right| \text{ and } r_{\mathcal{F}}=\left|\max(V_f\cup\{0\})\right|, \tag*{(1)} l F = ∣ min ( V f ∪ { 0 }) ∣ and r F = ∣ max ( V f ∪ { 0 }) ∣ , (1)
so that F ( c ) i \mathcal{F}(c)_i F ( c ) i depends only on c [ i − l F , i + r F ] c_{[i-l_{\mathcal{F}},i+r_{\mathcal{F}}]} c [ i − l F , i + r F ] .
Topological entropy
In this section the dimension D ≥ 1 D\ge1 D ≥ 1 is arbitrary, unless otherwise stated.
A central problem in the qualitative theory of dynamical systems is to quantify the complexity of the long-term behavior of orbits in a way that is intrinsic and robust under natural equivalence relations. Topological entropy was introduced precisely to address this issue, providing a numerical invariant that measures the asymptotic complexity of a dynamical system without relying on any probabilistic structure [1 ] . At an intuitive level, topological entropy measures the exponential growth rate of the number of orbit segments that can be distinguished as the system evolves over time. Two orbit segments are regarded as distinguishable if they eventually separate by more than a prescribed resolution, and positive entropy reflects the fact that the number of such distinguishable behaviors grows exponentially when the observation time increases. In this sense, topological entropy provides a quantitative measure of the intrinsic complexity of the dynamics, capturing how rapidly new dynamical patterns are generated. In systems with zero topological entropy, orbit segments remain highly organized, and the amount of information needed to describe the dynamics grows at most sub-exponentially. In contrast, positive topological entropy signals the presence of complex behavior, characterized by an exponential proliferation of distinguishable orbit segments. For this reason, topological entropy is widely regarded as a fundamental indicator of deterministic chaos [7 ] . One of the key features that makes topological entropy particularly powerful is its invariance under topological conjugacy. As a consequence, it provides a robust tool for comparing and classifying dynamical systems up to topological equivalence. Moreover, topological entropy plays a unifying role within dynamical systems theory. Through the variational principle, it is related to measure-theoretic entropy by being equal to the supremum of metric entropies over all invariant probability measures [20 , 41 ] . This connection bridges the topological and ergodic descriptions of dynamical behavior. Since its introduction, topological entropy has become one of the most fundamental and widely used invariants in the study of dynamical systems, with applications ranging from symbolic dynamics and CA to smooth and geometric dynamics.
There are two main and standard approaches to the definition of topological entropy for dynamical systems. The first one, introduced by Adler, Konheim, and McAndrew, is purely topological and is based on open covers of the phase space [1 ] . The second one, developed independently by Dinaburg and Bowen, is metric in nature and relies on the notion of separation of orbits with respect to a compatible distance [7 , 17 ] . The equivalence between the open cover and metric definitions of topological entropy is a classical result.
On compact metrizable spaces the topological entropy defined via open covers in the sense of Adler-Konheim-McAndrew coincides with the topological entropy defined via ( n , ε ) (n,\varepsilon) ( n , ε ) -separated (or spanning) sets associated with any compatible metric (see for example [41 Theorem 7.8] and [29 Section 3.1] ).
The argument relies crucially on compactness, which allows one to relate finite open covers to metric balls and to control the growth of dynamical refinements. As a consequence, topological entropy is a topological invariant and does not depend on the particular compatible metric chosen. This equivalence justifies the interchangeable use of the two approaches: the open cover definition provides an intrinsic, purely topological formulation, while the metric definition is often more convenient for explicit computations and applications.
We now give the formal definition of topological entropy in the sense of Bowen and Dinaburg. Although in the one-dimensional part of this paper (§ 4 ) we only use the equivalent combinatorial formulation for cellular automata given below, the general definition is needed in § 5 and § 6 , where we use the Bridge Theorem and general properties of topological entropy.
The Bowen-Dinaburg definition of topological entropy. Assume that X X X is a compact metrizable space, let d d d be a metric compatible with its topology, and let T : X → X T : X \to X T : X → X be continuous. We define the dynamical metric
d n ( x , y ) = max 0 ≤ k < n d ( T k x , T k y ) . d_n(x,y) = \max_{0 \leq k < n} d\left(T^k x,T^k y\right). d n ( x , y ) = 0 ≤ k < n max d ( T k x , T k y ) .
Given ε > 0 \varepsilon> 0 ε > 0 , a set E ⊂ X E \subset X E ⊂ X is said to be ( n , ε ) (n,\varepsilon) ( n , ε ) -separated if
x ≠ y ∈ E ⇒ d n ( x , y ) ≥ ε . x \ne y \in E \quad\Rightarrow\quad d_n(x,y) \geq\varepsilon. x = y ∈ E ⇒ d n ( x , y ) ≥ ε .
Let s ( n , ε ) s(n,\varepsilon) s ( n , ε ) denote the maximal cardinality of an ( n , ε ) (n,\varepsilon) ( n , ε ) -separated set. By compactness, s ( n , ε ) < + ∞ s(n,\varepsilon) < +\infty s ( n , ε ) < + ∞ . The topological entropy of T T T is defined as
H ( T ) = lim ε → 0 lim sup n → ∞ 1 n log s ( n , ε ) , \mathcal{H}(T) = \lim_{\varepsilon\to0} \limsup_{n \to\infty} \frac{1}{n} \log s(n,\varepsilon), H ( T ) = ε → 0 lim n → ∞ lim sup n 1 log s ( n , ε ) ,
as originally introduced in [7 ] (see also [41 Chapter 7] ). Equivalent formulations can be given using ( n , ε ) (n,\varepsilon) ( n , ε ) -spanning sets instead of separated sets.
Intuitively, two points are considered indistinguishable up to time n n n if their orbit segments remain within distance ε \varepsilon ε at all intermediate times. The quantity s ( n , ε ) s(n,\varepsilon) s ( n , ε ) counts the maximum number of orbit segments that can be distinguished with resolution ε \varepsilon ε over a time window of length n n n . The entropy is the asymptotic exponential growth rate of this number as n → ∞ n \to\infty n → ∞ , observed at arbitrarily fine scales.
Some standard facts. Let T : X → X T : X \to X T : X → X and S : Y → Y S : Y \to Y S : Y → Y be continuous maps of compact metrizable spaces. We shall use the following well-known properties, where entropies may take the value + ∞ +\infty + ∞ (see [41 Chapter 7 and Chapter 8] ): (a) H ( T N ) = N H ( T ) \mathcal{H}(T^N)=N\mathcal{H}(T) H ( T N ) = N H ( T ) for every N ≥ 1 N\ge1 N ≥ 1 ; (b) if π : X → Y \pi:X\to Y π : X → Y is a continuous surjection with π ∘ T = S ∘ π \pi\circ T=S\circ\pi π ∘ T = S ∘ π , then H ( S ) ≤ H ( T ) \mathcal{H}(S)\le\mathcal{H}(T) H ( S ) ≤ H ( T ) ; (c) if Z ⊆ X Z\subseteq X Z ⊆ X is closed and T ( Z ) ⊆ Z T(Z)\subseteq Z T ( Z ) ⊆ Z , then H ( T ∣ Z ) ≤ H ( T ) \mathcal{H}(T|_Z)\le\mathcal{H}(T) H ( T ∣ Z ) ≤ H ( T ) ; moreover H ( T ) = H ( T ∣ T ( X ) ) \mathcal{H}(T)=\mathcal{H}(T|_{T(X)}) H ( T ) = H ( T ∣ T ( X ) ) [41 Corollary 8.6.1(iii)] ; (d) H ( T × S ) = H ( T ) + H ( S ) \mathcal{H}(T\times S)=\mathcal{H}(T)+\mathcal{H}(S) H ( T × S ) = H ( T ) + H ( S ) .
Recall that a continuous map T : X → X T:X\to X T : X → X of a metric space is equicontinuous if for every ε > 0 \varepsilon>0 ε > 0 there is η > 0 \eta>0 η > 0 such that d ( x , y ) < η d(x,y)<\eta d ( x , y ) < η implies d ( T k x , T k y ) < ε d(T^k x,T^k y)<\varepsilon d ( T k x , T k y ) < ε for every k ≥ 0 k\ge0 k ≥ 0 , and that T T T is sensitive to initial conditions if there is ε > 0 \varepsilon>0 ε > 0 such that for every x ∈ X x\in X x ∈ X and every η > 0 \eta>0 η > 0 there exist y ∈ X y\in X y ∈ X and k ≥ 0 k\ge0 k ≥ 0 with d ( x , y ) < η d(x,y)<\eta d ( x , y ) < η and d ( T k x , T k y ) ≥ ε d(T^k x,T^k y)\ge\varepsilon d ( T k x , T k y ) ≥ ε . The two properties are mutually exclusive on non-empty spaces.
Proposition 1. Let T : X → X T:X\to X T : X → X be a continuous map of a compact metric space . If T T T is equicontinuous then H ( T ) = 0 \mathcal{H}(T)=0 H ( T ) = 0 .
Proof. Fix ε > 0 \varepsilon>0 ε > 0 . By equicontinuity there exists η > 0 \eta>0 η > 0 such that d ( x , y ) < η d(x,y)<\eta d ( x , y ) < η implies d ( T k x , T k y ) < ε d(T^k x,T^k y)<\varepsilon d ( T k x , T k y ) < ε for every k ≥ 0 k\ge0 k ≥ 0 , i.e., d n ( x , y ) < ε d_n(x,y)<\varepsilon d n ( x , y ) < ε for every n n n . Hence the points of an ( n , ε ) (n,\varepsilon) ( n , ε ) -separated set are pairwise at distance at least η \eta η , and s ( n , ε ) ≤ s ( 1 , η ) s(n,\varepsilon)\le s(1,\eta) s ( n , ε ) ≤ s ( 1 , η ) for every n n n . By compactness s ( 1 , η ) < ∞ s(1,\eta)<\infty s ( 1 , η ) < ∞ . Therefore lim sup n 1 n log s ( n , ε ) = 0 \limsup_{n}\frac{1}{n}\log s(n,\varepsilon)=0 lim sup n n 1 log s ( n , ε ) = 0 for every ε \varepsilon ε .
Proposition 2. Let F \mathcal{F} F be a D D D -dimensional CA on a finite alphabet A A A , D ≥ 1 D\ge1 D ≥ 1 .
(i) F \mathcal{F} F is equicontinuous if and only if there exist 0 ≤ a < b 0\le a<b 0 ≤ a < b such that F a = F b \mathcal{F}^a=\mathcal{F}^b F a = F b .
(ii) If F \mathcal{F} F is a D D D -GCA, then F \mathcal{F} F is either equicontinuous or sensitive to initial conditions .
Part (i) is [28 Proposition 84] , and part (ii) is [4 Lemma 26] , where it is proved for group cellular automata on arbitrary group shifts (see also the proof of [4 Theorem 27] for (i) in the case of GCAs).
Topological entropy for CA. In [26 ] it is shown that for one-dimensional CA the general definition of topological entropy translates to the following simpler form. For D = 1 D=1 D = 1 , let R ( w , t ) \mathcal{R}(w,t) R ( w , t ) denote the number of distinct rectangles of width w w w and height t + 1 t+1 t + 1 occurring in a space-time evolution diagram of F \mathcal{F} F (see Figure 1 and Equation (8) below for a formal definition). Then,
Figure 1. space-time diagram obtained by iterating F \mathcal{F} F on x x x . The ( t + 1 ) × ( j − i + 1 ) (t+1) \times(j-i+1) ( t + 1 ) × ( j − i + 1 ) rectangle of purple-colored cells represents tr F , t ( x , i , j ) \operatorname{tr}_{\mathcal{F},t}(x,i,j) tr F , t ( x , i , j ) .
H ( F ) = lim w → + ∞ ( lim t → + ∞ log ( R ( w , t ) ) t ) . (2) \mathcal{H}(\mathcal{F})=\lim_{w\to+\infty}\left(\lim_{t\to+\infty}\frac{\log(\mathcal{R}(w,t))}{t}\right). \tag*{(2)} H ( F ) = w → + ∞ lim ( t → + ∞ lim t log ( R ( w , t )) ) . (2)
The inner limit exists since t ↦ log R ( w , t ) t\mapsto\log\mathcal{R}(w,t) t ↦ log R ( w , t ) is sub-additive, and the outer one exists since R ( w , t ) \mathcal{R}(w,t) R ( w , t ) is non-decreasing in w w w . The same formula holds in every dimension, with boxes in place of intervals.
Proposition 3. Let F \mathcal{F} F be a D D D -dimensional CA on a finite alphabet A A A . For w ≥ 0 w\ge0 w ≥ 0 let N F ( w , t ) N_{\mathcal{F}}(w,t) N F ( w , t ) be the number of distinct sequences ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t (\mathcal{F}^j(c)|_{B_w})_{0\le j\le t} ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t , c ∈ A Z D c\in A^{\mathbb{Z}^D} c ∈ A Z D . Then
H ( F ) = lim w → + ∞ ( lim t → + ∞ log N F ( w , t ) t ) . \mathcal{H}(\mathcal{F})=\lim_{w\to+\infty}\left(\lim_{t\to+\infty}\frac{\log N_{\mathcal{F}}(w,t)}{t}\right). H ( F ) = w → + ∞ lim ( t → + ∞ lim t log N F ( w , t ) ) .
Proof. Recall that A Z D A^{\mathbb{Z}^{D}} A Z D is equipped with the Tychonoff distance d d d defined in § 2 ; we use the notation of the Bowen–Dinaburg definition with T = F T=\mathcal{F} T = F . Fix w ≥ 0 w\ge0 w ≥ 0 and t ≥ 0 t\ge0 t ≥ 0 . Recall that d ( c , c ′ ) < 2 − w d(c,c')<2^{-w} d ( c , c ′ ) < 2 − w if and only if c c c and c ′ c' c ′ coincide on B w B_w B w . Hence, for x , y ∈ A Z D x,y\in A^{\mathbb{Z}^{D}} x , y ∈ A Z D ,
d t + 1 ( x , y ) ≥ 2 − w ⟺ F j ( x ) ∣ B w ≠ F j ( y ) ∣ B w for some 0 ≤ j ≤ t , d_{t+1}(x,y)\ge2^{-w}\Longleftrightarrow\mathcal{F}^{j}(x)|_{B_w}\ne\mathcal{F}^{j}(y)|_{B_w}\text{ for some }0\le j\le t, d t + 1 ( x , y ) ≥ 2 − w ⟺ F j ( x ) ∣ B w = F j ( y ) ∣ B w for some 0 ≤ j ≤ t ,
that is, x x x and y y y are ( t + 1 , 2 − w ) (t+1,2^{-w}) ( t + 1 , 2 − w ) -separated if and only if the sequences ( F j ( x ) ∣ B w ) 0 ≤ j ≤ t (\mathcal{F}^{j}(x)|_{B_w})_{0\le j\le t} ( F j ( x ) ∣ B w ) 0 ≤ j ≤ t and ( F j ( y ) ∣ B w ) 0 ≤ j ≤ t (\mathcal{F}^{j}(y)|_{B_w})_{0\le j\le t} ( F j ( y ) ∣ B w ) 0 ≤ j ≤ t are different. Therefore a set E ⊆ A Z D E\subseteq A^{\mathbb{Z}^{D}} E ⊆ A Z D is ( t + 1 , 2 − w ) (t+1,2^{-w}) ( t + 1 , 2 − w ) -separated if and only if distinct points of E E E give distinct sequences; choosing one configuration for each of the N F ( w , t ) N_{\mathcal{F}}(w,t) N F ( w , t ) possible sequences, we obtain
s ( t + 1 , 2 − w ) = N F ( w , t ) . (3) s(t+1,2^{-w})=N_{\mathcal{F}}(w,t). \tag*{(3)} s ( t + 1 , 2 − w ) = N F ( w , t ) . (3)
We now show that the sequence a t = log N F ( w , t ) a_t=\log N_{\mathcal{F}}(w,t) a t = log N F ( w , t ) is subadditive. Let t 1 , t 2 ≥ 0 t_1,t_2\ge0 t 1 , t 2 ≥ 0 and c ∈ A Z D c\in A^{\mathbb{Z}^{D}} c ∈ A Z D . The sequence ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t 1 + t 2 (\mathcal{F}^{j}(c)|_{B_w})_{0\le j\le t_1+t_2} ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t 1 + t 2 is determined by its first part ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t 1 (\mathcal{F}^{j}(c)|_{B_w})_{0\le j\le t_1} ( F j ( c ) ∣ B w ) 0 ≤ j ≤ t 1 and by ( F i ( c ′ ) ∣ B w ) 0 ≤ i ≤ t 2 (\mathcal{F}^{i}(c')|_{B_w})_{0\le i\le t_2} ( F i ( c ′ ) ∣ B w ) 0 ≤ i ≤ t 2 , where c ′ = F t 1 ( c ) c'=\mathcal{F}^{t_1}(c) c ′ = F t 1 ( c ) . Hence N F ( w , t 1 + t 2 ) ≤ N F ( w , t 1 ) N F ( w , t 2 ) N_{\mathcal{F}}(w,t_1+t_2)\le N_{\mathcal{F}}(w,t_1)N_{\mathcal{F}}(w,t_2) N F ( w , t 1 + t 2 ) ≤ N F ( w , t 1 ) N F ( w , t 2 ) , i.e., a t 1 + t 2 ≤ a t 1 + a t 2 a_{t_1+t_2}\le a_{t_1}+a_{t_2} a t 1 + t 2 ≤ a t 1 + a t 2 . Since a t ≥ 0 a_t\ge0 a t ≥ 0 , by Fekete’s lemma the limit lim t a t t \lim_{t}\frac{a_t}{t} lim t t a t exists and is finite. By (3), and since t t + 1 → 1 \frac{t}{t+1}\to1 t + 1 t → 1 ,
lim sup n → ∞ 1 n log s ( n , 2 − w ) = lim t → ∞ log s ( t + 1 , 2 − w ) t + 1 = lim t → ∞ log N F ( w , t ) t . (4) \limsup_{n\to\infty}\frac{1}{n}\log s(n,2^{-w})=\lim_{t\to\infty}\frac{\log s(t+1,2^{-w})}{t+1}=\lim_{t\to\infty}\frac{\log N_{\mathcal{F}}(w,t)}{t}. \tag*{(4)} n → ∞ lim sup n 1 log s ( n , 2 − w ) = t → ∞ lim t + 1 log s ( t + 1 , 2 − w ) = t → ∞ lim t log N F ( w , t ) . (4)
Finally, if 0 < ε ′ < ε 0<\varepsilon'<\varepsilon 0 < ε ′ < ε , then every ( n , ε ) (n,\varepsilon) ( n , ε ) -separated set is ( n , ε ′ ) (n,\varepsilon') ( n , ε ′ ) -separated, so that s ( n , ε ′ ) ≥ s ( n , ε ) s(n,\varepsilon')\ge s(n,\varepsilon) s ( n , ε ′ ) ≥ s ( n , ε ) . Thus lim sup n 1 n log s ( n , ε ) \limsup_n\frac{1}{n}\log s(n,\varepsilon) lim sup n n 1 log s ( n , ε ) is non-increasing in ε \varepsilon ε , its limit as ε → 0 \varepsilon\to0 ε → 0 exists in [ 0 , + ∞ ] [0,+\infty] [ 0 , + ∞ ] , and it can be computed along the sequence ε = 2 − w \varepsilon=2^{-w} ε = 2 − w , w → + ∞ w\to+\infty w → + ∞ . By (4) we obtain
H ( F ) = lim w → + ∞ ( lim t → + ∞ log N F ( w , t ) t ) . \mathcal{H}(\mathcal{F})=\lim_{w\to+\infty}\left(\lim_{t\to+\infty}\frac{\log N_{\mathcal{F}}(w,t)}{t}\right). H ( F ) = w → + ∞ lim ( t → + ∞ lim t log N F ( w , t ) ) .
For D = 1 D=1 D = 1 , Proposition 3 gives Equation (2) (with windows of width 2 w + 1 2w+1 2 w + 1 ; by monotonicity in the width the two limits coincide).
Topological entropy of one-dimensional GCAs
Throughout this section D = 1 D=1 D = 1 .
Let G G G be a finite group with identity element e e e . Let F \mathcal{F} F be any GCA on G G G with local rule f f f and neighborhood V f = { v 1 , … , v k } V_f=\{v_1,\ldots,v_k\} V f = { v 1 , … , v k } . Let l F l_{\mathcal{F}} l F and r F r_{\mathcal{F}} r F be the quantities defined in Equation (1) . Let
L = { x ∈ G Z : ∀ i > 0 , x i = e } and (5) L=\{x\in G^{\mathbb{Z}}:\forall i>0,\ x_i=e\}\quad\text{and} \tag*{(5)} L = { x ∈ G Z : ∀ i > 0 , x i = e } and (5)
R = { x ∈ G Z : ∀ i < 0 , x i = e } . (6) R=\{x\in G^{\mathbb{Z}}:\forall i<0,\ x_i=e\}. \tag*{(6)} R = { x ∈ G Z : ∀ i < 0 , x i = e } . (6)
Note that L L L and R R R are subgroups of G Z G^{\mathbb{Z}} G Z . For an interval I ⊆ Z I\subseteq\mathbb{Z} I ⊆ Z we say that a configuration c c c is trivial on I I I if c i = e c_i=e c i = e for every i ∈ I i\in I i ∈ I .
For t ≥ 0 t \ge0 t ≥ 0 , x ∈ G Z x \in G^{\mathbb{Z}} x ∈ G Z and i , j ∈ Z i,j \in\mathbb{Z} i , j ∈ Z with i ≤ j i \le j i ≤ j , let
tr F , t ( x , i , j ) = [ x i x i + 1 ⋯ x j F ( x ) i F ( x ) i + 1 ⋯ F ( x ) j F 2 ( x ) i F 2 ( x ) i + 1 ⋯ F 2 ( x ) j ⋮ ⋮ ⋱ ⋮ F t ( x ) i F t ( x ) i + 1 ⋯ F t ( x ) j ] \operatorname{tr}_{\mathcal{F},t}(x,i,j)=
\begin{bmatrix}
x_i & x_{i+1} & \cdots& x_j \\
\mathcal{F}(x)_i & \mathcal{F}(x)_{i+1} & \cdots& \mathcal{F}(x)_j \\
\mathcal{F}^{2}(x)_i & \mathcal{F}^{2}(x)_{i+1} & \cdots& \mathcal{F}^{2}(x)_j \\
\vdots& \vdots& \ddots& \vdots\\
\mathcal{F}^{t}(x)_i & \mathcal{F}^{t}(x)_{i+1} & \cdots& \mathcal{F}^{t}(x)_j
\end{bmatrix} tr F , t ( x , i , j ) = x i F ( x ) i F 2 ( x ) i ⋮ F t ( x ) i x i + 1 F ( x ) i + 1 F 2 ( x ) i + 1 ⋮ F t ( x ) i + 1 ⋯ ⋯ ⋯ ⋱ ⋯ x j F ( x ) j F 2 ( x ) j ⋮ F t ( x ) j
denote the ( t + 1 ) × ( j − i + 1 ) (t+1) \times(j-i+1) ( t + 1 ) × ( j − i + 1 ) rectangular portion of the space-time diagram obtained by iterating F \mathcal{F} F on x x x . See Figure 1 for a graphical illustration of tr F , t ( x , i , j ) \operatorname{tr}_{\mathcal{F},t}(x,i,j) tr F , t ( x , i , j ) . For j = i − 1 j=i-1 j = i − 1 we let tr F , t ( x , i , i − 1 ) \operatorname{tr}_{\mathcal{F},t}(x,i,i-1) tr F , t ( x , i , i − 1 ) be the empty array; accordingly, every non-empty set of traces of width 0 0 0 has exactly one element. This convention is only needed in the degenerate cases l F = 0 l_{\mathcal{F}}=0 l F = 0 or r F = 0 r_{\mathcal{F}}=0 r F = 0 below.
Since F \mathcal{F} F , and hence every iterate F s \mathcal{F}^{s} F s , is a group endomorphism of G Z G^{\mathbb{Z}} G Z , for all x , y ∈ G Z x,y \in G^{\mathbb{Z}} x , y ∈ G Z we have F s ( x y ) = F s ( x ) F s ( y ) \mathcal{F}^{s}(xy)=\mathcal{F}^{s}(x)\mathcal{F}^{s}(y) F s ( x y ) = F s ( x ) F s ( y ) and F s ( x − 1 ) = F s ( x ) − 1 \mathcal{F}^{s}(x^{-1})=\mathcal{F}^{s}(x)^{-1} F s ( x − 1 ) = F s ( x ) − 1 ; therefore
tr F , t ( x y , i , j ) = tr F , t ( x , i , j ) ⋅ tr F , t ( y , i , j ) and tr F , t ( x − 1 , i , j ) = tr F , t ( x , i , j ) − 1 (7) \operatorname{tr}_{\mathcal{F},t}(xy,i,j)=\operatorname{tr}_{\mathcal{F},t}(x,i,j)\cdot\operatorname{tr}_{\mathcal{F},t}(y,i,j)
\quad\text{and}\quad
\operatorname{tr}_{\mathcal{F},t}(x^{-1},i,j)=\operatorname{tr}_{\mathcal{F},t}(x,i,j)^{-1} \tag*{(7)} tr F , t ( x y , i , j ) = tr F , t ( x , i , j ) ⋅ tr F , t ( y , i , j ) and tr F , t ( x − 1 , i , j ) = tr F , t ( x , i , j ) − 1 (7)
where products and inverses of traces are taken entrywise. In particular, sets of traces of the form { tr F , t ( x , i , j ) : x ∈ H } \{\operatorname{tr}_{\mathcal{F},t}(x,i,j):x \in H\} { tr F , t ( x , i , j ) : x ∈ H } , with H H H a subgroup of G Z G^{\mathbb{Z}} G Z , are subgroups of G ( t + 1 ) × ( j − i + 1 ) G^{(t+1)\times(j-i+1)} G ( t + 1 ) × ( j − i + 1 ) . (7) is the point where the group structure enters; it is used in an essential way in Lemmata 2 and 3 and in Theorem 1.
The quantity R ( w , t ) \mathcal{R}(w,t) R ( w , t ) introduced in the definition of topological entropy (see (2) ) can be expressed as
R ( w , t ) = ∣ { tr F , t ( x , k , k + w − 1 ) : x ∈ G Z , k ∈ Z } ∣ . (8) \mathcal{R}(w,t)=\left|\left\{\operatorname{tr}_{\mathcal{F},t}(x,k,k+w-1):x \in G^{\mathbb{Z}},\ k \in\mathbb{Z}\right\}\right|. \tag*{(8)} R ( w , t ) = { tr F , t ( x , k , k + w − 1 ) : x ∈ G Z , k ∈ Z } . (8)
Since F \mathcal{F} F commutes with σ \sigma σ , we have tr F , t ( x , k , k + w − 1 ) = tr F , t ( σ k − k ′ ( x ) , k ′ , k ′ + w − 1 ) \operatorname{tr}_{\mathcal{F},t}(x,k,k+w-1)=\operatorname{tr}_{\mathcal{F},t}(\sigma^{k-k'}(x),k',k'+w-1) tr F , t ( x , k , k + w − 1 ) = tr F , t ( σ k − k ′ ( x ) , k ′ , k ′ + w − 1 ) ; hence the set in (8) does not change if k k k is fixed, and R ( w , t ) = ∣ { tr F , t ( x , k , k + w − 1 ) : x ∈ G Z } ∣ \mathcal{R}(w,t)=\left|\left\{\operatorname{tr}_{\mathcal{F},t}(x,k,k+w-1):x \in G^{\mathbb{Z}}\right\}\right| R ( w , t ) = { tr F , t ( x , k , k + w − 1 ) : x ∈ G Z } for every fixed k ∈ Z k \in\mathbb{Z} k ∈ Z .
We now define
T − ( F , t ) = { tr F , t ( x , − l F + 1 , 0 ) : x ∈ L } (9) T^{-}(\mathcal{F},t)=\left\{\operatorname{tr}_{\mathcal{F},t}(x,-l_{\mathcal{F}}+1,0):x \in L\right\} \tag*{(9)} T − ( F , t ) = { tr F , t ( x , − l F + 1 , 0 ) : x ∈ L } (9)
and
T + ( F , t ) = { tr F , t ( x , 0 , r F − 1 ) : x ∈ R } . (10) T^{+}(\mathcal{F},t)=\left\{\operatorname{tr}_{\mathcal{F},t}(x,0,r_{\mathcal{F}}-1):x \in R\right\}. \tag*{(10)} T + ( F , t ) = { tr F , t ( x , 0 , r F − 1 ) : x ∈ R } . (10)
By (7) , T − ( F , t ) T^{-}(\mathcal{F},t) T − ( F , t ) and T + ( F , t ) T^{+}(\mathcal{F},t) T + ( F , t ) are finite groups. If l F = 0 l_{\mathcal{F}}=0 l F = 0 (resp. r F = 0 r_{\mathcal{F}}=0 r F = 0 ), then ∣ T − ( F , t ) ∣ = 1 \lvert T^{-}(\mathcal{F},t)\rvert=1 ∣ T − ( F , t )∣ = 1 (resp. ∣ T + ( F , t ) ∣ = 1 \lvert T^{+}(\mathcal{F},t)\rvert=1 ∣ T + ( F , t )∣ = 1 ) by our convention on empty traces. See
Figure 2. space-time diagram obtained by iterating F \mathcal{F} F on x ∈ L x \in L x ∈ L . The ( t + 1 ) × l F (t+1) \times l_{\mathcal{F}} ( t + 1 ) × l F rectangle of purple-colored cells represents tr F , t ( x , − l F + 1 , 0 ) \operatorname{tr}_{\mathcal{F},t}(x,-l_{\mathcal{F}}+1,0) tr F , t ( x , − l F + 1 , 0 ) which is an element of T − ( F , t ) T^{-}(\mathcal{F},t) T − ( F , t )
Figure 3. space-time diagram obtained by iterating F \mathcal{F} F on x ∈ R x \in R x ∈ R . The ( t + 1 ) × r F (t+1) \times r_{\mathcal{F}} ( t + 1 ) × r F rectangle of purple-colored cells represents tr F , t ( x , 0 , r F − 1 ) \operatorname{tr}_{\mathcal{F},t}(x,0,r_{\mathcal{F}}-1) tr F , t ( x , 0 , r F − 1 ) which is an element of T + ( F , t ) T^{+}(\mathcal{F},t) T + ( F , t )
Figures 2 and 3 for a graphical illustration of the elements of T − ( F , t ) T^{-}(\mathcal{F},t) T − ( F , t ) and T + ( F , t ) T^{+}(\mathcal{F},t) T + ( F , t ) , respectively.
The following two lemmata formalize the fact that information can enter a region of the space-time diagram only through its boundary columns.
Lemma 1. Let s ≥ 0 s \ge0 s ≥ 0 .
(i) Let U ∈ L U \in L U ∈ L and assume that F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] for every 0 ≤ j < s 0 \le j < s 0 ≤ j < s . Then F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) for every 0 ≤ j ≤ s 0 \le j \le s 0 ≤ j ≤ s .
(ii) Let δ ≥ − 1 \delta\ge-1 δ ≥ − 1 and let V ∈ G Z V \in G^{\mathbb{Z}} V ∈ G Z be trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] . Assume that F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] for every 0 ≤ j < s 0 \le j < s 0 ≤ j < s . Then F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] for every 0 ≤ j ≤ s 0 \le j \le s 0 ≤ j ≤ s .
Proof. (i) We proceed by induction on j j j . For j = 0 j=0 j = 0 the claim holds since U ∈ L U \in L U ∈ L . Let 0 ≤ j < s 0 \le j < s 0 ≤ j < s and assume that F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) . For i ≥ 1 i \ge1 i ≥ 1 we have F j + 1 ( U ) i = f ( F j ( U ) i + v 1 , … , F j ( U ) i + v k ) \mathcal{F}^{j+1}(U)_i=f(\mathcal{F}^{j}(U)_{i+v_1},\ldots,\mathcal{F}^{j}(U)_{i+v_k}) F j + 1 ( U ) i = f ( F j ( U ) i + v 1 , … , F j ( U ) i + v k ) . Since − l F ≤ v h ≤ r F -l_{\mathcal{F}} \le v_h \le r_{\mathcal{F}} − l F ≤ v h ≤ r F , every index i + v h i+v_h i + v h satisfies i + v h ≥ 1 − l F i+v_h \ge1-l_{\mathcal{F}} i + v h ≥ 1 − l F , hence it belongs either to [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] , where F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial by hypothesis (because j < s j<s j < s ), or to [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) , where F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial by the inductive hypothesis. Since f f f is a homomorphism, f ( e , … , e ) = e f(e,\ldots,e)=e f ( e , … , e ) = e , and thus F j + 1 ( U ) i = e \mathcal{F}^{j+1}(U)_i=e F j + 1 ( U ) i = e .
(ii) The proof is symmetric: for i ≤ δ i \le\delta i ≤ δ every index i + v h i+v_h i + v h satisfies i + v h ≤ δ + r F i+v_h \le\delta+r_{\mathcal{F}} i + v h ≤ δ + r F , hence it belongs either to [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] or to ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] .
Lemma 2. Let δ ≥ 0 \delta\ge0 δ ≥ 0 and t ≥ 0 t \ge0 t ≥ 0 . Let U ∈ L U \in L U ∈ L and let V ∈ G Z V \in G^{\mathbb{Z}} V ∈ G Z be trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] . If
tr F , t ( U , − l F + 1 , r F + δ ) = tr F , t ( V , − l F + 1 , r F + δ ) , \operatorname{tr}_{\mathcal{F},t}(U,-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta)=\operatorname{tr}_{\mathcal{F},t}(V,-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta), tr F , t ( U , − l F + 1 , r F + δ ) = tr F , t ( V , − l F + 1 , r F + δ ) , then, for every 0 ≤ j ≤ t 0 \le j \le t 0 ≤ j ≤ t , F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] and F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] .
Proof. We proceed by induction on j ∈ { 0 , … , t } j \in\{0,\ldots,t\} j ∈ { 0 , … , t } . Assume that the claim holds for every j ′ < j j' < j j ′ < j (no assumption is needed for j = 0 j=0 j = 0 ). By Lemma 1(i) with s = j s=j s = j , F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) , which contains [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] since δ ≥ 0 \delta\ge0 δ ≥ 0 . By Lemma 1(ii) with s = j s=j s = j , F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] , which contains [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] . Since F j ( U ) \mathcal{F}^{j}(U) F j ( U ) and F j ( V ) \mathcal{F}^{j}(V) F j ( V ) coincide on [ − l F + 1 , r F + δ ] ⊇ [ − l F + 1 , 0 ] ∪ [ δ + 1 , δ + r F ] [-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta] \supseteq[-l_{\mathcal{F}}+1,0] \cup[\delta+1,\delta+r_{\mathcal{F}}] [ − l F + 1 , r F + δ ] ⊇ [ − l F + 1 , 0 ] ∪ [ δ + 1 , δ + r F ] , the claim holds for j j j .
Let δ \delta δ be any non-negative integer, let a ∈ T − ( F , t ) a \in T^{-}(\mathcal{F},t) a ∈ T − ( F , t ) and b ∈ T + ( F , t ) b \in T^{+}(\mathcal{F},t) b ∈ T + ( F , t ) . There is a natural way to define a new trace, denoted by a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b , as follows (see Figure 4 ). Let X ∈ L X \in L X ∈ L be such that tr F , t ( X , − l F + 1 , 0 ) = a \operatorname{tr}_{\mathcal{F},t}(X,-l_{\mathcal{F}}+1,0)=a tr F , t ( X , − l F + 1 , 0 ) = a and Y ∈ R Y \in R Y ∈ R be such that tr F , t ( Y , 0 , r F − 1 ) = b \operatorname{tr}_{\mathcal{F},t}(Y,0,r_{\mathcal{F}}-1)=b tr F , t ( Y , 0 , r F − 1 ) = b . Then
Figure 4. Graphical representation of a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b , obtained from an element a ∈ T − ( F , t ) a \in T^{-}(\mathcal{F},t) a ∈ T − ( F , t ) (yellow-colored cells on the left) and an element b ∈ T + ( F , t ) b \in T^{+}(\mathcal{F},t) b ∈ T + ( F , t ) (green-colored cells on the right). The trace a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b is the ( t + 1 ) × ( l F + δ + r F ) (t+1) \times(l_{\mathcal{F}}+\delta+r_{\mathcal{F}}) ( t + 1 ) × ( l F + δ + r F ) rectangular box delimited by the thick black border. Yellow-colored cells below the dashed arrow can be influenced by green-colored cells on the right and, symmetrically, green-colored cells below the dashed arrow can be influenced by yellow-colored cells on the left.
a ∣ δ ∣ b = tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) . a|\delta|b=\operatorname{tr}_{\mathcal{F},t}\left(X\rho^{\delta+1}(Y),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta\right). a ∣ δ ∣ b = tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) .
Note that X X X is supported in ( − ∞ , 0 ] (-\infty,0] ( − ∞ , 0 ] , ρ δ + 1 ( Y ) \rho^{\delta+1}(Y) ρ δ + 1 ( Y ) is supported in [ δ + 1 , + ∞ ) [\delta+1,+\infty) [ δ + 1 , + ∞ ) , and ρ δ + 1 ( Y ) \rho^{\delta+1}(Y) ρ δ + 1 ( Y ) has the trace b b b on the columns [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] .
Lemma 3. The trace a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b does not depend on the choice of X X X and Y Y Y .
Proof. Let X , X ′ ∈ L X,X' \in L X , X ′ ∈ L with tr F , t ( X , − l F + 1 , 0 ) = tr F , t ( X ′ , − l F + 1 , 0 ) = a \operatorname{tr}_{\mathcal{F},t}(X,-l_{\mathcal{F}}+1,0)=\operatorname{tr}_{\mathcal{F},t}(X',-l_{\mathcal{F}}+1,0)=a tr F , t ( X , − l F + 1 , 0 ) = tr F , t ( X ′ , − l F + 1 , 0 ) = a . Then U = X ′ − 1 X ∈ L U=X'^{-1}X \in L U = X ′ − 1 X ∈ L and, by Equation (7) , F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] for every j ≤ t j \le t j ≤ t . By Lemma 1(i) with s = t + 1 s=t+1 s = t + 1 , F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) for every j ≤ t j \le t j ≤ t . Hence F j ( X ) = F j ( X ′ ) \mathcal{F}^{j}(X)=\mathcal{F}^{j}(X') F j ( X ) = F j ( X ′ ) on [ − l F + 1 , + ∞ ) [-l_{\mathcal{F}}+1,+\infty) [ − l F + 1 , + ∞ ) for every j ≤ t j \le t j ≤ t . In the same way, if Y , Y ′ ∈ R Y,Y' \in R Y , Y ′ ∈ R have the same trace b b b , then V = ρ δ + 1 ( Y ′ − 1 Y ) V=\rho^{\delta+1}(Y'^{-1}Y) V = ρ δ + 1 ( Y ′ − 1 Y ) is trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] and, since F \mathcal{F} F commutes with ρ \rho ρ , F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] for every j ≤ t j \le t j ≤ t ; by Lemma 1(ii) with s = t + 1 s=t+1 s = t + 1 , F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] for every j ≤ t j \le t j ≤ t , so that F j ( ρ δ + 1 ( Y ) ) = F j ( ρ δ + 1 ( Y ′ ) ) \mathcal{F}^{j}(\rho^{\delta+1}(Y))=\mathcal{F}^{j}(\rho^{\delta+1}(Y')) F j ( ρ δ + 1 ( Y )) = F j ( ρ δ + 1 ( Y ′ )) on ( − ∞ , δ + r F ] (-\infty,\delta+r_{\mathcal{F}}] ( − ∞ , δ + r F ] for every j ≤ t . S i n c e j \le t. Since j ≤ t . S in ce [-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta]$ is contained in both [ − l F + 1 , + ∞ ) [-l_{\mathcal{F}}+1,+\infty) [ − l F + 1 , + ∞ ) and ( − ∞ , δ + r F ] (-\infty,\delta+r_{\mathcal{F}}] ( − ∞ , δ + r F ] , Equation (7) gives tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) = tr F , t ( X ′ ρ δ + 1 ( Y ′ ) , − l F + 1 , r F + δ ) \operatorname{tr}_{\mathcal{F},t}(X\rho^{\delta+1}(Y),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta)=\operatorname{tr}_{\mathcal{F},t}(X'\rho^{\delta+1}(Y'),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta) tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) = tr F , t ( X ′ ρ δ + 1 ( Y ′ ) , − l F + 1 , r F + δ ) .
Graphically, as it can be seen in Figure 4 , the red-colored region of the space-time diagram depends solely on the yellow-colored region (on the left) and on the green-colored region (on the right). Note that the first l F l_{\mathcal{F}} l F columns of a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b and the last r F r_{\mathcal{F}} r F columns of a ∣ δ ∣ b a|\delta|b a ∣ δ ∣ b will in general differ from a a a and b b b , respectively. This is due to the fact that a a a and b b b may influence each other when t t t is sufficiently large. We define
T ( F , t , δ ) = { a ∣ δ ∣ b : a ∈ T − ( F , t ) , b ∈ T + ( F , t ) } . (11) T(\mathcal{F},t,\delta)=\{a|\delta|b:a\in T^{-}(\mathcal{F},t),\ b\in T^{+}(\mathcal{F},t)\}. \tag*{(11)} T ( F , t , δ ) = { a ∣ δ ∣ b : a ∈ T − ( F , t ) , b ∈ T + ( F , t )} . (11)
Theorem 1. For every δ ≥ 0 \delta\ge0 δ ≥ 0 and t ≥ 0 t \ge0 t ≥ 0 we have
∣ T − ( F , t ) ∣ ∣ T + ( F , t ) ∣ = ∣ T ( F , t , δ ) ∣ . |T^{-}(\mathcal{F},t)|\,|T^{+}(\mathcal{F},t)|=|T(\mathcal{F},t,\delta)|. ∣ T − ( F , t ) ∣ ∣ T + ( F , t ) ∣ = ∣ T ( F , t , δ ) ∣.
Proof. By Equation (11) we have ∣ T ( F , t , δ ) ∣ ≤ ∣ T − ( F , t ) ∣ ∣ T + ( F , t ) ∣ |T(\mathcal{F},t,\delta)| \le|T^{-}(\mathcal{F},t)||T^{+}(\mathcal{F},t)| ∣ T ( F , t , δ ) ∣ ≤ ∣ T − ( F , t ) ∣∣ T + ( F , t ) ∣ , so it suffices to prove that the map ( a , b ) ↦ a ∣ δ ∣ b (a,b) \mapsto a|\delta|b ( a , b ) ↦ a ∣ δ ∣ b is injective. Note that, a priori, the space–time diagrams generated by a a a and b b b might interfere with each other after a sufficiently large number of iterations, so that different pairs could produce the same trace (see Figure 4 ). We show that the group structure rules this out.
Let a 1 , a 2 ∈ T − ( F , t ) a_1,a_2 \in T^{-}(\mathcal{F},t) a 1 , a 2 ∈ T − ( F , t ) and b 1 , b 2 ∈ T + ( F , t ) b_1,b_2 \in T^{+}(\mathcal{F},t) b 1 , b 2 ∈ T + ( F , t ) with a 1 ∣ δ ∣ b 1 = a 2 ∣ δ ∣ b 2 a_1|\delta|b_1=a_2|\delta|b_2 a 1 ∣ δ ∣ b 1 = a 2 ∣ δ ∣ b 2 . Choose X 1 , X 2 ∈ L X_1,X_2 \in L X 1 , X 2 ∈ L and Y 1 , Y 2 ∈ R Y_1,Y_2 \in R Y 1 , Y 2 ∈ R with tr F , t ( X h , − l F + 1 , 0 ) = a h \operatorname{tr}_{\mathcal{F},t}(X_h,-l_{\mathcal{F}}+1,0)=a_h tr F , t ( X h , − l F + 1 , 0 ) = a h and tr F , t ( Y h , 0 , r F − 1 ) = b h \operatorname{tr}_{\mathcal{F},t}(Y_h,0,r_{\mathcal{F}}-1)=b_h tr F , t ( Y h , 0 , r F − 1 ) = b h for h = 1 , 2 h=1,2 h = 1 , 2 , and write W = [ − l F + 1 , r F + δ ] W=[-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta] W = [ − l F + 1 , r F + δ ] . For every j ≤ t j\le t j ≤ t and i ∈ W i\in W i ∈ W we have
F j ( X 1 ) i F j ( ρ δ + 1 ( Y 1 ) ) i = F j ( X 2 ) i F j ( ρ δ + 1 ( Y 2 ) ) i , \mathcal{F}^{j}(X_1)_i\mathcal{F}^{j}(\rho^{\delta+1}(Y_1))_i=\mathcal{F}^{j}(X_2)_i\mathcal{F}^{j}(\rho^{\delta+1}(Y_2))_i, F j ( X 1 ) i F j ( ρ δ + 1 ( Y 1 ) ) i = F j ( X 2 ) i F j ( ρ δ + 1 ( Y 2 ) ) i ,
and hence
F j ( X 2 ) i − 1 F j ( X 1 ) i = F j ( ρ δ + 1 ( Y 2 ) ) i F j ( ρ δ + 1 ( Y 1 ) ) i − 1 . \mathcal{F}^{j}(X_2)_i^{-1}\mathcal{F}^{j}(X_1)_i=\mathcal{F}^{j}(\rho^{\delta+1}(Y_2))_i\mathcal{F}^{j}(\rho^{\delta+1}(Y_1))_i^{-1}. F j ( X 2 ) i − 1 F j ( X 1 ) i = F j ( ρ δ + 1 ( Y 2 ) ) i F j ( ρ δ + 1 ( Y 1 ) ) i − 1 .
Since F j \mathcal{F}^{j} F j is an endomorphism commuting with ρ \rho ρ , this means that U = X 2 − 1 X 1 ∈ L U=X_2^{-1}X_1\in L U = X 2 − 1 X 1 ∈ L and V = ρ δ + 1 ( Y 2 Y 1 − 1 ) V=\rho^{\delta+1}(Y_2Y_1^{-1}) V = ρ δ + 1 ( Y 2 Y 1 − 1 ) , which is trivial on ( − ∞ , δ ] (-\infty,\delta] ( − ∞ , δ ] , have the same trace on W W W . By Lemma 2, F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] and F j ( V ) \mathcal{F}^{j}(V) F j ( V ) is trivial on [ δ + 1 , δ + r F ] [\delta+1,\delta+r_{\mathcal{F}}] [ δ + 1 , δ + r F ] for every j ≤ t j\le t j ≤ t . By Equation (7) , the first fact gives a 1 = tr F , t ( X 2 U , − l F + 1 , 0 ) = a 2 a_1=\operatorname{tr}_{\mathcal{F},t}(X_2U,-l_{\mathcal{F}}+1,0)=a_2 a 1 = tr F , t ( X 2 U , − l F + 1 , 0 ) = a 2 , and the second one gives tr F , t ( Y 2 Y 1 − 1 , 0 , r F − 1 ) = e \operatorname{tr}_{\mathcal{F},t}(Y_2Y_1^{-1},0,r_{\mathcal{F}}-1)=e tr F , t ( Y 2 Y 1 − 1 , 0 , r F − 1 ) = e , that is, b 1 = b 2 b_1=b_2 b 1 = b 2 .
The groups T − ( F , t ) T^{-}(\mathcal{F},t) T − ( F , t ) and T + ( F , t ) T^{+}(\mathcal{F},t) T + ( F , t ) have a simple structure as t t t varies. For t ≥ 0 t\ge0 t ≥ 0 let
N t − = { F t + 1 ( U ) [ − l F + 1 , 0 ] : U ∈ L , F j ( U ) is trivial on [ − l F + 1 , 0 ] for 0 ≤ j ≤ t } , N_t^{-}=\{\mathcal{F}^{t+1}(U)_{[-l_{\mathcal{F}}+1,0]}:U\in L,\ \mathcal{F}^{j}(U)\text{ is trivial on }[-l_{\mathcal{F}}+1,0]\text{ for }0\le j\le t\}, N t − = { F t + 1 ( U ) [ − l F + 1 , 0 ] : U ∈ L , F j ( U ) is trivial on [ − l F + 1 , 0 ] for 0 ≤ j ≤ t } ,
N t + = { F t + 1 ( U ) [ 0 , r F − 1 ] : U ∈ R , F j ( U ) is trivial on [ 0 , r F − 1 ] for 0 ≤ j ≤ t } . N_t^{+}=\{\mathcal{F}^{t+1}(U)_{[0,r_{\mathcal{F}}-1]}:U\in R,\ \mathcal{F}^{j}(U)\text{ is trivial on }[0,r_{\mathcal{F}}-1]\text{ for }0\le j\le t\}. N t + = { F t + 1 ( U ) [ 0 , r F − 1 ] : U ∈ R , F j ( U ) is trivial on [ 0 , r F − 1 ] for 0 ≤ j ≤ t } .
They are subgroups of G l F G^{l_{\mathcal{F}}} G l F and of G r F G^{r_{\mathcal{F}}} G r F , respectively, being images of subgroups of G Z G^{\mathbb{Z}} G Z under homomorphisms.
Proposition 4. For every t ≥ 0 t \ge0 t ≥ 0 :
(i) ∣ T − ( F , t + 1 ) ∣ = ∣ T − ( F , t ) ∣ ∣ N t − ∣ |T^{-}(\mathcal{F},t+1)|=|T^{-}(\mathcal{F},t)||N^{-}_{t}| ∣ T − ( F , t + 1 ) ∣ = ∣ T − ( F , t ) ∣∣ N t − ∣ and ∣ T + ( F , t + 1 ) ∣ = ∣ T + ( F , t ) ∣ ∣ N t + ∣ |T^{+}(\mathcal{F},t+1)|=|T^{+}(\mathcal{F},t)||N^{+}_{t}| ∣ T + ( F , t + 1 ) ∣ = ∣ T + ( F , t ) ∣∣ N t + ∣ ; moreover ∣ T − ( F , 0 ) ∣ = ∣ G ∣ l F |T^{-}(\mathcal{F},0)|=|G|^{l_{\mathcal{F}}} ∣ T − ( F , 0 ) ∣ = ∣ G ∣ l F and ∣ T + ( F , 0 ) ∣ = ∣ G ∣ r F |T^{+}(\mathcal{F},0)|=|G|^{r_{\mathcal{F}}} ∣ T + ( F , 0 ) ∣ = ∣ G ∣ r F ;
(ii) N t + 1 − ≤ N t − N^{-}_{t+1}\le N^{-}_{t} N t + 1 − ≤ N t − and N t + 1 + ≤ N t + N^{+}_{t+1}\le N^{+}_{t} N t + 1 + ≤ N t + .
Consequently there exist t 0 ≥ 0 t_{0}\ge0 t 0 ≥ 0 and subgroups N ∞ − ≤ G l F N^{-}_{\infty}\le G^{l_{\mathcal{F}}} N ∞ − ≤ G l F , N ∞ + ≤ G r F N^{+}_{\infty}\le G^{r_{\mathcal{F}}} N ∞ + ≤ G r F such that N t ± = N ∞ ± N^{\pm}_{t}=N^{\pm}_{\infty} N t ± = N ∞ ± for every t ≥ t 0 t\ge t_{0} t ≥ t 0 , and
lim t → ∞ log ∣ T − ( F , t ) ∣ t = log ∣ N ∞ − ∣ , lim t → ∞ log ∣ T + ( F , t ) ∣ t = log ∣ N ∞ + ∣ . \lim_{t\to\infty}\frac{\log|T^{-}(\mathcal{F},t)|}{t}=\log|N^{-}_{\infty}|,\qquad\lim_{t\to\infty}\frac{\log|T^{+}(\mathcal{F},t)|}{t}=\log|N^{+}_{\infty}|. t → ∞ lim t log ∣ T − ( F , t ) ∣ = log ∣ N ∞ − ∣ , t → ∞ lim t log ∣ T + ( F , t ) ∣ = log ∣ N ∞ + ∣.
Proof. We prove the statements for T − T^{-} T − ; those for T + T^{+} T + are symmetric, using Lemma 1(ii) with δ = − 1 \delta=-1 δ = − 1 .
(i) The restriction to the first t + 1 t+1 t + 1 rows is a surjective group homomorphism π t : T − ( F , t + 1 ) → T − ( F , t ) \pi_t:T^{-}(\mathcal{F},t+1)\to T^{-}(\mathcal{F},t) π t : T − ( F , t + 1 ) → T − ( F , t ) . Its kernel consists of the traces tr F , t + 1 ( U , − l F + 1 , 0 ) \operatorname{tr}_{\mathcal{F},t+1}(U,-l_{\mathcal{F}}+1,0) tr F , t + 1 ( U , − l F + 1 , 0 ) with U ∈ L U\in L U ∈ L and F j ( U ) \mathcal{F}^{j}(U) F j ( U ) trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] for j ≤ t j\le t j ≤ t ; such a trace is determined by its last row, so the map sending it to its last row is an isomorphism between Ker ( π t ) \operatorname{Ker}(\pi_t) Ker ( π t ) and N t − N^{-}_{t} N t − . Hence ∣ T − ( F , t + 1 ) ∣ = ∣ T − ( F , t ) ∣ ∣ N t − ∣ |T^{-}(\mathcal{F},t+1)|=|T^{-}(\mathcal{F},t)||N^{-}_{t}| ∣ T − ( F , t + 1 ) ∣ = ∣ T − ( F , t ) ∣∣ N t − ∣ . Finally ∣ T − ( F , 0 ) ∣ = ∣ G ∣ l F |T^{-}(\mathcal{F},0)|=|G|^{l_{\mathcal{F}}} ∣ T − ( F , 0 ) ∣ = ∣ G ∣ l F , since the values of U ∈ L U\in L U ∈ L on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] are arbitrary.
(ii) Let g ∈ N t + 1 + g\in N^{+}_{t+1} g ∈ N t + 1 + , say g = F t + 2 ( U ) [ − l F + 1 , 0 ] g=\mathcal{F}^{t+2}(U)_{[-l_{\mathcal{F}}+1,0]} g = F t + 2 ( U ) [ − l F + 1 , 0 ] with U ∈ L U\in L U ∈ L and F j ( U ) \mathcal{F}^{j}(U) F j ( U ) trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] for j ≤ t + 1 j\le t+1 j ≤ t + 1 . By Lemma 1(i) with s = t + 2 s=t+2 s = t + 2 , F ( U ) \mathcal{F}(U) F ( U ) is trivial on [ 1 , + ∞ ) [1,+\infty) [ 1 , + ∞ ) , i.e., U ′ = F ( U ) ∈ L U'=\mathcal{F}(U)\in L U ′ = F ( U ) ∈ L . Moreover F j ( U ′ ) = F j + 1 ( U ) \mathcal{F}^{j}(U')=\mathcal{F}^{j+1}(U) F j ( U ′ ) = F j + 1 ( U ) is trivial on [ − l F + 1 , 0 ] [-l_{\mathcal{F}}+1,0] [ − l F + 1 , 0 ] for j ≤ t j\le t j ≤ t , and F t + 1 ( U ′ ) [ − l F + 1 , 0 ] = g \mathcal{F}^{t+1}(U')_{[-l_{\mathcal{F}}+1,0]}=g F t + 1 ( U ′ ) [ − l F + 1 , 0 ] = g . Hence g ∈ N t − g\in N^{-}_{t} g ∈ N t − .
A decreasing chain of subgroups of the finite group G l F G^{l_{\mathcal{F}}} G l F is eventually constant, which gives t 0 t_{0} t 0 and N ∞ − N^{-}_{\infty} N ∞ − . By (i), log ∣ T − ( F , t ) ∣ = l F log ∣ G ∣ + ∑ j = 0 t − 1 log ∣ N j − ∣ \log|T^{-}(\mathcal{F},t)|=l_{\mathcal{F}}\log|G|+\sum_{j=0}^{t-1}\log|N^{-}_{j}| log ∣ T − ( F , t ) ∣ = l F log ∣ G ∣ + ∑ j = 0 t − 1 log ∣ N j − ∣ , and dividing by t t t we get the limit.
By Proposition 4 the following quantities are well defined:
H − ( F ) = lim t → ∞ log ( ∣ T − ( F , t ) ∣ ) t and H + ( F ) = lim t → ∞ log ( ∣ T + ( F , t ) ∣ ) t . (12) \mathcal{H}^{-}(\mathcal{F})=\lim_{t\to\infty}\frac{\log(|T^{-}(\mathcal{F},t)|)}{t}
\quad\text{and}\quad
\mathcal{H}^{+}(\mathcal{F})=\lim_{t\to\infty}\frac{\log(|T^{+}(\mathcal{F},t)|)}{t}. \tag*{(12)} H − ( F ) = t → ∞ lim t log ( ∣ T − ( F , t ) ∣ ) and H + ( F ) = t → ∞ lim t log ( ∣ T + ( F , t ) ∣ ) . (12)
Let δ \delta δ be any non-negative integer and
C ( δ ) = { x ∈ G Z : x i = e for every i ≤ 0 and every i > δ } C(\delta)=\{x\in G^{\mathbb{Z}}:x_i=e\text{ for every }i\le0\text{ and every }i>\delta\} C ( δ ) = { x ∈ G Z : x i = e for every i ≤ 0 and every i > δ }
(in particular C ( 0 ) = { e Z } C(0)=\{e^{\mathbb{Z}}\} C ( 0 ) = { e Z } ). We define
T ∗ ( F , t , δ ) = { tr F , t ( X h ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) : X ∈ L , Y ∈ R , h ∈ C ( δ ) } . (13) T^{*}(\mathcal{F},t,\delta)=\{\operatorname{tr}_{\mathcal{F},t}(Xh\,\rho^{\delta+1}(Y),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta):X\in L,\ Y\in R,\ h\in C(\delta)\}. \tag*{(13)} T ∗ ( F , t , δ ) = { tr F , t ( X h ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) : X ∈ L , Y ∈ R , h ∈ C ( δ )} . (13)
Looking at Figure 4 , the configuration h h h allows one to replace the sequence of e e e ’s (first row colored in red) with a sequence of δ \delta δ arbitrary elements of G G G .
Lemma 4. For every δ ≥ 0 \delta\ge0 δ ≥ 0 and t ≥ 0 t\ge0 t ≥ 0 :
(i) ∣ T ∗ ( F , t , δ ) ∣ = R ( l F + δ + r F , t ) |T^{*}(\mathcal{F},t,\delta)|=R(l_{\mathcal{F}}+\delta+r_{\mathcal{F}},t) ∣ T ∗ ( F , t , δ ) ∣ = R ( l F + δ + r F , t ) ;
(ii) ∣ T ( F , t , δ ) ∣ ≤ ∣ T ∗ ( F , t , δ ) ∣ ≤ ∣ G ∣ δ ∣ T ( F , t , δ ) ∣ |T(\mathcal{F},t,\delta)|\le|T^{*}(\mathcal{F},t,\delta)|\le|G|^{\delta}|T(\mathcal{F},t,\delta)| ∣ T ( F , t , δ ) ∣ ≤ ∣ T ∗ ( F , t , δ ) ∣ ≤ ∣ G ∣ δ ∣ T ( F , t , δ ) ∣ .
Proof. (i) By (8) and the subsequent remark with k = − l F + 1 k=-l_{\mathcal{F}}+1 k = − l F + 1 , R ( l F + δ + r F , t ) \mathcal{R}(l_{\mathcal{F}}+\delta+r_{\mathcal{F}},t) R ( l F + δ + r F , t ) is the number of traces tr F , t ( c , − l F + 1 , r F + δ ) \operatorname{tr}_{\mathcal{F},t}(c,-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta) tr F , t ( c , − l F + 1 , r F + δ ) , c ∈ G Z c\in G^{\mathbb{Z}} c ∈ G Z . Every element of T ∗ ( F , t , δ ) T^*(\mathcal{F},t,\delta) T ∗ ( F , t , δ ) is such a trace. Conversely, given c ∈ G Z c\in G^{\mathbb{Z}} c ∈ G Z , let X ∈ L X\in L X ∈ L coincide with c c c on ( − ∞ , 0 ] (-\infty,0] ( − ∞ , 0 ] , let h ∈ C ( δ ) h\in C(\delta) h ∈ C ( δ ) coincide with c c c on [ 1 , δ ] [1,\delta] [ 1 , δ ] , and let Y = σ δ + 1 ( c ′ ) Y=\sigma^{\delta+1}(c') Y = σ δ + 1 ( c ′ ) , where c ′ c' c ′ coincides with c c c on [ δ + 1 , + ∞ ) [\delta+1,+\infty) [ δ + 1 , + ∞ ) and is trivial elsewhere. Then Y ∈ R Y\in R Y ∈ R and, since X X X , h h h and ρ δ + 1 ( Y ) \rho^{\delta+1}(Y) ρ δ + 1 ( Y ) have pairwise disjoint supports, c = X h ρ δ + 1 ( Y ) c=Xh\rho^{\delta+1}(Y) c = X h ρ δ + 1 ( Y ) .
(ii) Taking h = e Z h=e^{\mathbb{Z}} h = e Z shows that T ( F , t , δ ) ⊆ T ∗ ( F , t , δ ) T(\mathcal{F},t,\delta)\subseteq T^*(\mathcal{F},t,\delta) T ( F , t , δ ) ⊆ T ∗ ( F , t , δ ) . Conversely, since X X X , h h h and ρ δ + 1 ( Y ) \rho^{\delta+1}(Y) ρ δ + 1 ( Y ) have pairwise disjoint supports, they commute, and by (7)
tr F , t ( X h ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) = tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) ⋅ tr F , t ( h , − l F + 1 , r F + δ ) . \operatorname{tr}_{\mathcal{F},t}\left(Xh\rho^{\delta+1}(Y),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta\right)
=
\operatorname{tr}_{\mathcal{F},t}\left(X\rho^{\delta+1}(Y),-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta\right)\cdot\operatorname{tr}_{\mathcal{F},t}\left(h,-l_{\mathcal{F}}+1,r_{\mathcal{F}}+\delta\right). tr F , t ( X h ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) = tr F , t ( X ρ δ + 1 ( Y ) , − l F + 1 , r F + δ ) ⋅ tr F , t ( h , − l F + 1 , r F + δ ) .
The first factor belongs to T ( F , t , δ ) T(\mathcal{F},t,\delta) T ( F , t , δ ) , and the second one is determined by h [ 1 , δ ] ∈ G δ h_{[1,\delta]}\in G^\delta h [ 1 , δ ] ∈ G δ .
Theorem 2. Let F \mathcal{F} F be a GCA on a finite group G G G . Then, for every δ ≥ 0 \delta\geq0 δ ≥ 0 ,
H ( F ) = lim t → ∞ log ∣ T ( F , t , δ ) ∣ t = lim t → ∞ log R ( l F + δ + r F , t ) t , (14) \mathcal{H}(\mathcal{F})=\lim_{t\to\infty}\frac{\log\lvert T(\mathcal{F},t,\delta)\rvert}{t}=\lim_{t\to\infty}\frac{\log\mathcal{R}(l_{\mathcal{F}}+\delta+r_{\mathcal{F}},t)}{t}, \tag*{(14)} H ( F ) = t → ∞ lim t log ∣ T ( F , t , δ )∣ = t → ∞ lim t log R ( l F + δ + r F , t ) , (14) and
H ( F ) = H − ( F ) + H + ( F ) . (15) \mathcal{H}(\mathcal{F})=\mathcal{H}^{-}(\mathcal{F})+\mathcal{H}^{+}(\mathcal{F}). \tag*{(15)} H ( F ) = H − ( F ) + H + ( F ) . (15)
Proof. Fix δ ≥ 0 \delta\geq0 δ ≥ 0 . By Theorem 1 and Proposition 4,
lim t → ∞ log ∣ T ( F , t , δ ) ∣ t = lim t → ∞ log ∣ T − ( F , t ) ∣ + log ∣ T + ( F , t ) ∣ t = H − ( F ) + H + ( F ) , \lim_{t\to\infty}\frac{\log\lvert T(\mathcal{F},t,\delta)\rvert}{t}
=
\lim_{t\to\infty}\frac{\log\lvert T^{-}(\mathcal{F},t)\rvert+\log\lvert T^{+}(\mathcal{F},t)\rvert}{t}
=
\mathcal{H}^{-}(\mathcal{F})+\mathcal{H}^{+}(\mathcal{F}), t → ∞ lim t log ∣ T ( F , t , δ )∣ = t → ∞ lim t log ∣ T − ( F , t )∣ + log ∣ T + ( F , t )∣ = H − ( F ) + H + ( F ) ,
and this value does not depend on δ \delta δ . By Lemma 4,
log ∣ T ( F , t , δ ) ∣ t ≤ log R ( l F + δ + r F , t ) t ≤ log ∣ T ( F , t , δ ) ∣ t + δ log ∣ G ∣ t , \frac{\log\lvert T(\mathcal{F},t,\delta)\rvert}{t}
\leq
\frac{\log\mathcal{R}(l_{\mathcal{F}}+\delta+r_{\mathcal{F}},t)}{t}
\leq
\frac{\log\lvert T(\mathcal{F},t,\delta)\rvert}{t}
+\frac{\delta\log\lvert G\rvert}{t}, t log ∣ T ( F , t , δ )∣ ≤ t log R ( l F + δ + r F , t ) ≤ t log ∣ T ( F , t , δ )∣ + t δ log ∣ G ∣ ,
so that lim t 1 t log R ( l F + δ + r F , t ) = H − ( F ) + H + ( F ) \lim_{t}\frac{1}{t}\log\mathcal{R}(l_{\mathcal{F}}+\delta+r_{\mathcal{F}},t)=\mathcal{H}^{-}(\mathcal{F})+\mathcal{H}^{+}(\mathcal{F}) lim t t 1 log R ( l F + δ + r F , t ) = H − ( F ) + H + ( F ) for every δ ≥ 0 \delta\geq0 δ ≥ 0 . Since the outer limit in (2) exists, it can be computed along the subsequence w = l F + r F + δ w=l_{\mathcal{F}}+r_{\mathcal{F}}+\delta w = l F + r F + δ , δ → ∞ \delta\to\infty δ → ∞ , and we obtain H ( F ) = H − ( F ) + H + ( F ) \mathcal{H}(\mathcal{F})=\mathcal{H}^{-}(\mathcal{F})+\mathcal{H}^{+}(\mathcal{F}) H ( F ) = H − ( F ) + H + ( F ) . This proves both (15) and (14) .
An alternative interpretation of Theorem 2, obtained by taking δ = 0 \delta=0 δ = 0 in (14) , is given by the following equation:
H ( F ) = lim w → + ∞ ( lim t → + ∞ log R ( w , t ) t ) = lim t → + ∞ log R ( l F + r F , t ) t . (16) \mathcal{H}(\mathcal{F})=\lim_{w\to+\infty}\left(\lim_{t\to+\infty}\frac{\log\mathcal{R}(w,t)}{t}\right)=\lim_{t\to+\infty}\frac{\log\mathcal{R}(l_{\mathcal{F}}+r_{\mathcal{F}},t)}{t}. \tag*{(16)} H ( F ) = w → + ∞ lim ( t → + ∞ lim t log R ( w , t ) ) = t → + ∞ lim t log R ( l F + r F , t ) . (16)
In other words, for GCAs the topological entropy is already detected by space-time windows of the fixed width l F + r F l_{\mathcal{F}}+r_{\mathcal{F}} l F + r F .
Corollary 1. Let F \mathcal{F} F be a GCA on a finite group G G G . Then H ( F ) = log ( ∣ N ∞ − ∣ ∣ N ∞ + ∣ ) \mathcal{H}(\mathcal{F})=\log\left(\lvert N^{-}_{\infty}\rvert\lvert N^{+}_{\infty}\rvert\right) H ( F ) = log ( ∣ N ∞ − ∣ ∣ N ∞ + ∣ ) . In particular, H ( F ) = log k \mathcal{H}(\mathcal{F})=\log k H ( F ) = log k for some positive integer k k k dividing ∣ G ∣ l F + r F \lvert G\rvert^{l_{\mathcal{F}}+r_{\mathcal{F}}} ∣ G ∣ l F + r F , and H ( F ) ≤ ( l F + r F ) log ∣ G ∣ \mathcal{H}(\mathcal{F})\leq(l_{\mathcal{F}}+r_{\mathcal{F}})\log\lvert G\rvert H ( F ) ≤ ( l F + r F ) log ∣ G ∣ .
Proof. The first statement follows from Theorem 2 and Proposition 4. Since N ∞ − ≤ G F N_{\infty}^{-} \leq G^{\mathcal{F}} N ∞ − ≤ G F and N ∞ + ≤ G F N_{\infty}^{+} \leq G^{\mathcal{F}} N ∞ + ≤ G F , Lagrange’s theorem gives the rest.
Theorem 3. There is an algorithm which, given a finite group G G G by its multiplication table and the local rule of a GCA F \mathcal{F} F on G G G , computes H ( F ) \mathcal{H}(\mathcal{F}) H ( F ) .
Proof. Let w = l F + r F w = l_{\mathcal{F}} + r_{\mathcal{F}} w = l F + r F . If w = 0 w = 0 w = 0 , then H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 by Corollary 1, so we may assume w ≥ 1 w \geq1 w ≥ 1 , and we let I = { 0 , … , w − 1 } I = \{0,\ldots,w-1\} I = { 0 , … , w − 1 } . We use the terminology of [4 ] . A bi-infinite orbit of F \mathcal{F} F is a sequence ( c ( s ) ) s ∈ Z (c^{(s)})_{s\in\mathbb{Z}} ( c ( s ) ) s ∈ Z of configurations with c ( s + 1 ) = F ( c ( s ) ) c^{(s+1)} = \mathcal{F}(c^{(s)}) c ( s + 1 ) = F ( c ( s ) ) for every s ∈ Z s \in\mathbb{Z} s ∈ Z ; the limit set Ω F \Omega_{\mathcal{F}} Ω F is the set of configurations lying on some bi-infinite orbit, and the D D D -trace subshift Tr I ( F ) ⊆ ( G I ) Z \operatorname{Tr}_{I}(\mathcal{F}) \subseteq(G^{I})^{\mathbb{Z}} Tr I ( F ) ⊆ ( G I ) Z is the set of sequences ( c ( s ) ∣ I ) s ∈ Z (c^{(s)}|_{I})_{s\in\mathbb{Z}} ( c ( s ) ∣ I ) s ∈ Z , where ( c ( s ) ) s ∈ Z (c^{(s)})_{s\in\mathbb{Z}} ( c ( s ) ) s ∈ Z ranges over the bi-infinite orbits of F \mathcal{F} F . By [4 Lemma 14] , Tr I ( F ) \operatorname{Tr}_{I}(\mathcal{F}) Tr I ( F ) is a one-dimensional group shift over G I G^{I} G I , and by [4 Lemma 15] it can be effectively constructed from the local rule of F \mathcal{F} F , i.e., one can compute a finite set of forbidden words defining it as a subshift of finite type (recall that group shifts are of finite type [31 , 30 ] , see also [4 Theorem 1] ). Let B m \mathcal{B}_{m} B m denote the set of words of length m m m occurring in Tr I ( F ) \operatorname{Tr}_{I}(\mathcal{F}) Tr I ( F ) .
We claim that H ( F ) = lim m → ∞ 1 m log ∣ B m ∣ \mathcal{H}(\mathcal{F}) = \lim_{m\to\infty} \frac{1}{m}\log|\mathcal{B}_{m}| H ( F ) = lim m → ∞ m 1 log ∣ B m ∣ , the entropy of the subshift Tr I ( F ) \operatorname{Tr}_{I}(\mathcal{F}) Tr I ( F ) . By [4 Lemma 18] there is k ≥ 0 k \geq0 k ≥ 0 such that F k ( G G ) = Ω F \mathcal{F}^{k}(G^{G}) = \Omega_{\mathcal{F}} F k ( G G ) = Ω F . Recall that R ( w , t ) \mathcal{R}(w,t) R ( w , t ) is the number of traces tr F , t ( c , 0 , w − 1 ) \operatorname{tr}_{\mathcal{F},t}(c,0,w-1) tr F , t ( c , 0 , w − 1 ) , c ∈ G Z c \in G^{\mathbb{Z}} c ∈ G Z , i.e., of the words ( F s ( c ) ∣ I ) 0 ≤ s ≤ t (\mathcal{F}^{s}(c)|_{I})_{0\leq s\leq t} ( F s ( c ) ∣ I ) 0 ≤ s ≤ t . Every word in B t + 1 \mathcal{B}_{t+1} B t + 1 is of this form, with c c c an element of a bi-infinite orbit, so that ∣ B t + 1 ∣ ≤ R ( w , t ) |\mathcal{B}_{t+1}| \leq\mathcal{R}(w,t) ∣ B t + 1 ∣ ≤ R ( w , t ) . Conversely, for t ≥ k t \geq k t ≥ k , the word ( F s ( c ) ∣ I ) 0 ≤ s ≤ t (\mathcal{F}^{s}(c)|_{I})_{0\leq s\leq t} ( F s ( c ) ∣ I ) 0 ≤ s ≤ t is determined by its first k k k letters, for which there are at most ∣ G ∣ w k |G|^{wk} ∣ G ∣ w k possibilities, and by the word ( F s ( c ′ ) ∣ I ) 0 ≤ s ≤ t − k (\mathcal{F}^{s}(c')|_{I})_{0\leq s\leq t-k} ( F s ( c ′ ) ∣ I ) 0 ≤ s ≤ t − k with c ′ = F k ( c ) ∈ Ω F c' = \mathcal{F}^{k}(c) \in\Omega_{\mathcal{F}} c ′ = F k ( c ) ∈ Ω F ; since c ′ c' c ′ lies on a bi-infinite orbit, the latter word belongs to B t + 1 − k \mathcal{B}_{t+1-k} B t + 1 − k . Hence
∣ B t + 1 ∣ ≤ R ( w , t ) ≤ ∣ G ∣ w k ∣ B t + 1 − k ∣ ( t ≥ k ) . |\mathcal{B}_{t+1}| \leq\mathcal{R}(w,t) \leq|G|^{wk}|\mathcal{B}_{t+1-k}| \qquad(t \geq k). ∣ B t + 1 ∣ ≤ R ( w , t ) ≤ ∣ G ∣ w k ∣ B t + 1 − k ∣ ( t ≥ k ) .
Dividing the logarithms by t t t and letting t → ∞ t \to\infty t → ∞ , Equation (16) gives the claim. Finally, the entropy of a one-dimensional subshift of finite type given by a finite set of forbidden words is the logarithm of the spectral radius of an effectively computable non-negative integer matrix (the adjacency matrix of a suitable higher block presentation, see [32 Chapter 4] ), and it is therefore computable.
A second, independent, proof of Theorem 3, which also yields an explicit formula, is given in Remark 2 below.
Linear GCAs over ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^{n} ( Z / p Z ) n : an explicit formula via Pontryagin duality
In this section the dimension D ≥ 1 D \geq1 D ≥ 1 is arbitrary. Throughout the section p p p is a prime, F p = Z / p Z \mathbb{F}_{p} = \mathbb{Z}/p\mathbb{Z} F p = Z / p Z , n ≥ 1 n \geq1 n ≥ 1 , and L p = F p [ x 1 ± 1 , … , x D ± 1 ] L_{p} = \mathbb{F}_{p}[x_{1}^{\pm1},\ldots,x_{D}^{\pm1}] L p = F p [ x 1 ± 1 , … , x D ± 1 ] denotes the ring of Laurent polynomials in D D D variables with coefficients in F p \mathbb{F}_{p} F p . For u ∈ Z D u \in\mathbb{Z}^{D} u ∈ Z D we write x u = x 1 u 1 ⋯ x D u D x^{u} = x_{1}^{u_{1}}\cdots x_{D}^{u_{D}} x u = x 1 u 1 ⋯ x D u D , and for 0 ≠ q = ∑ u q u x u ∈ L p 0 \ne q = \sum_{u}q_{u}x^{u} \in L_{p} 0 = q = ∑ u q u x u ∈ L p we let supp ( q ) = { u ∈ Z D : q u ≠ 0 } \operatorname{supp}(q) = \{u \in\mathbb{Z}^{D}: q_{u} \ne0\} supp ( q ) = { u ∈ Z D : q u = 0 } . In this section the letter t t t denotes an indeterminate.
Linear GCAs and their matrices. Every endomorphism of the elementary abelian group F p n \mathbb{F}_{p}^{n} F p n is F p \mathbb{F}_{p} F p -linear. Hence the local rule of a D D D -GCA F \mathcal{F} F on F p n \mathbb{F}_{p}^{n} F p n has the form f ( g 1 , … , g k ) = ∑ h = 1 k A v h g h f(g_{1},\ldots,g_{k}) = \sum_{h=1}^{k}A_{vh}g_{h} f ( g 1 , … , g k ) = ∑ h = 1 k A v h g h with A v h ∈ M n ( F p ) A_{vh} \in M_{n}(\mathbb{F}_{p}) A v h ∈ M n ( F p ) , i.e.,
F ( c ) v = ∑ u ∈ V f A u c v + u ( c ∈ ( F p n ) Z D , v ∈ Z D ) . \mathcal{F}(c)_{v} = \sum_{u\in V_{f}} A_{u}c_{v+u} \qquad(c \in(\mathbb{F}_{p}^{n})^{\mathbb{Z}^{D}},\ v \in\mathbb{Z}^{D}). F ( c ) v = u ∈ V f ∑ A u c v + u ( c ∈ ( F p n ) Z D , v ∈ Z D ) .
We associate with F \mathcal{F} F the matrix
M F ( x ) = ∑ u ∈ V f A u x − u ∈ M n ( L p ) . M_{\mathcal{F}}(x)=\sum_{u\in V_f} A_u x^{-u}\in M_n(\mathbb{L}_p). M F ( x ) = u ∈ V f ∑ A u x − u ∈ M n ( L p ) .
Identifying a finite configuration c c c with the vector of Laurent polynomials ∑ v c v x v ∈ L p n \sum_v c_vx^v\in\mathbb{L}_p^n ∑ v c v x v ∈ L p n , the map F \mathcal{F} F acts on finite configurations as the multiplication by M F M_{\mathcal{F}} M F ; since finite configurations are dense and CAs are continuous, it follows that M F ∘ F ′ = M F M F ′ M_{\mathcal{F}\circ\mathcal{F}'}=M_{\mathcal{F}}M_{\mathcal{F}'} M F ∘ F ′ = M F M F ′ and M F k = M F k M_{\mathcal{F}^k}=M_{\mathcal{F}}^k M F k = M F k . Other conventions used in the literature replace x i x_i x i by x i − 1 x_i^{-1} x i − 1 ; all the statements of this section are invariant under this change. For M ∈ M n ( L p ) M\in M_n(\mathbb{L}_p) M ∈ M n ( L p ) we write
χ M ( t ) = det ( t I − M ) = t n + c n − 1 t n − 1 + ⋯ + c 1 t + c 0 , c i ∈ L p , \chi_M(t)=\det(tI-M)=t^n+c_{n-1}t^{n-1}+\cdots+c_1t+c_0,\qquad c_i\in\mathbb{L}_p, χ M ( t ) = det ( t I − M ) = t n + c n − 1 t n − 1 + ⋯ + c 1 t + c 0 , c i ∈ L p ,
for its characteristic polynomial. When D = 1 D=1 D = 1 we set
E M + = max ( { 0 } ∪ { max supp ( c i ) : c i ≠ 0 } ) , E M − = min ( { 0 } ∪ { min supp ( c i ) : c i ≠ 0 } ) . E_M^+=\max\left(\{0\}\cup\{\max\operatorname{supp}(c_i):c_i\ne0\}\right),
\qquad
E_M^-=\min\left(\{0\}\cup\{\min\operatorname{supp}(c_i):c_i\ne0\}\right). E M + = max ( { 0 } ∪ { max supp ( c i ) : c i = 0 } ) , E M − = min ( { 0 } ∪ { min supp ( c i ) : c i = 0 } ) .
In other words, [ E M − , E M + ] [E_M^-,E_M^+] [ E M − , E M + ] is the smallest interval containing 0 0 0 and all the exponents of x x x appearing in the coefficients of χ M \chi_M χ M .
Theorem 4. Let F \mathcal{F} F be a D D D -GCA on F p n \mathbb{F}_p^n F p n and let M = M F M=M_{\mathcal{F}} M = M F , with characteristic polynomial χ M ( t ) = t n + c n − 1 t n − 1 + ⋯ + c 0 \chi_M(t)=t^n+c_{n-1}t^{n-1}+\cdots+c_0 χ M ( t ) = t n + c n − 1 t n − 1 + ⋯ + c 0 .
(1) If D = 1 D=1 D = 1 , then H ( F ) = ( E M + − E M − ) log p \mathcal{H}(\mathcal{F})=(E_M^+-E_M^-)\log p H ( F ) = ( E M + − E M − ) log p .
(2) If D ≥ 2 D\ge2 D ≥ 2 , then H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 if c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p , and H ( F ) = + ∞ \mathcal{H}(\mathcal{F})=+\infty H ( F ) = + ∞ otherwise.
(3) In every dimension, F \mathcal{F} F is equicontinuous if and only if c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p .
An alternative proof of parts (2) and (3), which avoids Pontryagin duality and only uses the one-dimensional results of Section 4, is given in Appendix A. The proof below relies on Pontryagin duality, on the Bridge Theorem relating topological and algebraic entropy, and on a computation of algebraic entropy in terms of ranks of modules over F p [ t ] \mathbb{F}_p[t] F p [ t ] , following the approach of [2 ] , where finitary linear cellular automata over Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z with n = 1 n=1 n = 1 and D = 1 D=1 D = 1 are studied.
Algebraic entropy and the Bridge Theorem. Let A A A be an abelian group and φ \varphi φ an endomorphism of A A A . For a finite subgroup E E E of A A A and m ≥ 1 m\ge1 m ≥ 1 let T m ( φ , E ) = E + φ ( E ) + ⋯ + φ m − 1 ( E ) T_m(\varphi,E)=E+\varphi(E)+\cdots+\varphi^{m-1}(E) T m ( φ , E ) = E + φ ( E ) + ⋯ + φ m − 1 ( E ) . The algebraic entropy of φ \varphi φ is
H a l g ( φ ) = sup E lim m → ∞ log ∣ T m ( φ , E ) ∣ m , \mathcal{H}_{\mathrm{alg}}(\varphi)=\sup_E\lim_{m\to\infty}\frac{\log\lvert T_m(\varphi,E)\rvert}{m}, H alg ( φ ) = E sup m → ∞ lim m log ∣ T m ( φ , E )∣ ,
where E E E ranges over the finite subgroups of A A A (the limit exists, see [15 ] ). For a compact abelian group X X X we denote by X ^ \widehat{X} X its Pontryagin dual, i.e., the discrete group of continuous homomorphisms X → T = R / Z X\to\mathbb{T}=\mathbb{R}/\mathbb{Z} X → T = R / Z , and for a continuous endomorphism ψ \psi ψ of X X X we denote by ψ ^ : X ^ → X ^ \widehat{\psi}:\widehat{X}\to\widehat{X} ψ : X → X , χ ↦ χ ∘ ψ \chi\mapsto\chi\circ\psi χ ↦ χ ∘ ψ , its dual endomorphism.
Theorem 5 (Bridge Theorem [42 ] , see also [15 ] ). Let X X X be a compact metrizable abelian group whose Pontryagin dual X ^ \widehat{X} X is a torsion group, and let ψ \psi ψ be a continuous endomorphism of X X X . Then H ( ψ ) = H a l g ( ψ ^ ) \mathcal{H}(\psi)=\mathcal{H}_{\mathrm{alg}}(\widehat{\psi}) H ( ψ ) = H alg ( ψ ) .
(The Bridge Theorem of [15 ] holds for arbitrary discrete abelian groups, with the algebraic entropy defined by taking the supremum over all finite subsets F F F and replacing T m ( φ , E ) T_m(\varphi,E) T m ( φ , E ) by F + φ ( F ) + ⋯ + φ m − 1 ( F ) F+\varphi(F)+\cdots+\varphi^{m-1}(F) F + φ ( F ) + ⋯ + φ m − 1 ( F ) ; on torsion groups this entropy coincides with the one defined above, and in this paper X ^ \widehat{X} X is always torsion.)
The following lemma extends to matrices and to arbitrary dimension the description of the Pontryagin dual of a one-dimensional linear CA over Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z given in [2 ] .
Lemma 5. The Pontryagin dual of ( F p n ) Z D (\mathbb{F}_p^n)^{\mathbb{Z}^D} ( F p n ) Z D is isomorphic to the discrete group L p n \mathbb{L}_p^n L p n , via the pairing
⟨ c , a ⟩ = ∑ v ∈ Z D a v ⋅ c v ∈ F p ≃ 1 p Z / Z ⊆ T , c ∈ ( F p n ) Z D , a = ∑ v a v x v ∈ L p n . \langle c,a\rangle=\sum_{v\in\mathbb{Z}^D}a_v\cdot c_v\in\mathbb{F}_p\simeq\frac{1}{p}\mathbb{Z}/\mathbb{Z}\subseteq\mathbb{T},\qquad c\in(\mathbb{F}_p^n)^{\mathbb{Z}^D},\quad a=\sum_v a_vx^v\in\mathbb{L}_p^n. ⟨ c , a ⟩ = v ∈ Z D ∑ a v ⋅ c v ∈ F p ≃ p 1 Z / Z ⊆ T , c ∈ ( F p n ) Z D , a = v ∑ a v x v ∈ L p n .
where a v ⋅ c v a_v\cdot c_v a v ⋅ c v is the standard scalar product of F p n \mathbb{F}_p^n F p n . Under this isomorphism, the dual of the GCA F \mathcal{F} F with matrix M = ∑ u A u x u M=\sum_u A_ux^u M = ∑ u A u x u is the multiplication by
M ∗ ( x ) = M ( x − 1 ) T = ∑ u A u T x u . M^*(x)=M(x^{-1})^{\mathsf{T}}=\sum_u A_u^{\mathsf{T}}x^u. M ∗ ( x ) = M ( x − 1 ) T = u ∑ A u T x u .
:::
Proof. Let χ : ( F p n ) Z D → T \chi:(\mathbb{F}_p^n)^{\mathbb{Z}^D}\to\mathbb{T} χ : ( F p n ) Z D → T be a continuous character. Since ( F p n ) Z D (\mathbb{F}_p^n)^{\mathbb{Z}^D} ( F p n ) Z D has exponent p p p , χ \chi χ takes values in the finite, hence discrete, subgroup 1 p Z / Z ≃ F p \frac{1}{p}\mathbb{Z}/\mathbb{Z}\simeq\mathbb{F}_p p 1 Z / Z ≃ F p of T \mathbb{T} T , so that its kernel χ − 1 ( 0 ) \chi^{-1}(0) χ − 1 ( 0 ) is open. Therefore it contains the set of configurations vanishing on some finite set B ⊆ Z D B\subseteq\mathbb{Z}^D B ⊆ Z D ; hence χ ( c ) \chi(c) χ ( c ) depends only on c ∣ B c|_B c ∣ B , and χ \chi χ is induced by a character of ( F p n ) B (\mathbb{F}_p^n)^B ( F p n ) B . Every character of F p n \mathbb{F}_p^n F p n with values in F p \mathbb{F}_p F p has the form g ↦ a ⋅ g g\mapsto a\cdot g g ↦ a ⋅ g for a unique a ∈ F p n a\in\mathbb{F}_p^n a ∈ F p n . Thus χ = ⟨ ⋅ , a ⟩ \chi=\langle\cdot,a\rangle χ = ⟨ ⋅ , a ⟩ for a unique finitely supported a a a , and conversely every such a a a defines a continuous character. This proves the first claim. For the second one, for every c c c and every finitely supported a a a we have
⟨ F ( c ) , a ⟩ = ∑ v a v ⋅ ∑ u A u c v + u = ∑ w ( ∑ u A u T a w − u ) ⋅ c w , \langle\mathcal{F}(c),a\rangle=\sum_v a_v\cdot\sum_u A_uc_{v+u}=\sum_w\left(\sum_u A_u^{\mathsf{T}}a_{w-u}\right)\cdot c_w, ⟨ F ( c ) , a ⟩ = v ∑ a v ⋅ u ∑ A u c v + u = w ∑ ( u ∑ A u T a w − u ) ⋅ c w ,
so that F ^ ( a ) w = ∑ u A u T a w − u \widehat{\mathcal{F}}(a)_w=\sum_u A_u^{\mathsf{T}}a_{w-u} F ( a ) w = ∑ u A u T a w − u , i.e., ∑ w F ^ ( a ) w x w = ( ∑ u A u T x u ) ( ∑ v a v x v ) \sum_w\widehat{\mathcal{F}}(a)_wx^w=\left(\sum_u A_u^{\mathsf{T}}x^u\right)\left(\sum_v a_vx^v\right) ∑ w F ( a ) w x w = ( ∑ u A u T x u ) ( ∑ v a v x v ) . □
For an F p \mathbb{F}_p F p -vector space V V V and an endomorphism φ \varphi φ of V V V we denote by V φ V_\varphi V φ the F p [ t ] \mathbb{F}_p[t] F p [ t ] -module structure on V V V in which t t t acts as φ \varphi φ . For an F p [ t ] \mathbb{F}_p[t] F p [ t ] -module W W W we let rk ( W ) = dim F p ( t ) ( F p ( t ) ⊗ F p [ t ] W ) ∈ N ∪ { ∞ } \operatorname{rk}(W)=\dim_{\mathbb{F}_p(t)}(\mathbb{F}_p(t)\otimes_{\mathbb{F}_p[t]}W)\in\mathbb{N}\cup\{\infty\} rk ( W ) = dim F p ( t ) ( F p ( t ) ⊗ F p [ t ] W ) ∈ N ∪ { ∞ } ; recall that rk ( W ) \operatorname{rk}(W) rk ( W ) is the supremum of the cardinalities of the F p [ t ] \mathbb{F}_p[t] F p [ t ] -linearly independent subsets of W W W , and that rk ( W ′ ) ≤ rk ( W ) \operatorname{rk}(W')\leq\operatorname{rk}(W) rk ( W ′ ) ≤ rk ( W ) for every submodule W ′ W' W ′ of W W W , since F p ( t ) \mathbb{F}_p(t) F p ( t ) is flat over F p [ t ] \mathbb{F}_p[t] F p [ t ] .
Lemma 6. Let V V V be an F p \mathbb{F}_p F p -vector space and φ \varphi φ an endomorphism of V V V . Then H a l g ( φ ) = rk ( V φ ) log p \mathcal{H}_{\mathrm{alg}}(\varphi)=\operatorname{rk}(V_\varphi)\log p H alg ( φ ) = rk ( V φ ) log p (with ∞ ⋅ log p = ∞ \infty\cdot\log p=\infty ∞ ⋅ log p = ∞ ).
Proof. Since F p \mathbb{F}_p F p is a prime field, the finite subgroups of V V V are exactly its finite-dimensional subspaces, and ∣ T m ( φ , E ) ∣ = p dim T m ( φ , E ) |T_m(\varphi,E)|=p^{\dim T_m(\varphi,E)} ∣ T m ( φ , E ) ∣ = p d i m T m ( φ , E ) . Hence H a l g ( φ ) = log p ⋅ ent ( φ ) \mathcal{H}_{\mathrm{alg}}(\varphi)=\log p\cdot\operatorname{ent}(\varphi) H alg ( φ ) = log p ⋅ ent ( φ ) , where ent \operatorname{ent} ent is the algebraic entropy of linear transformations defined via dimensions in [19 Definition 2.4] (see also [19 Remark 2.5] ), and ent ( φ ) = rk ( V φ ) \operatorname{ent}(\varphi)=\operatorname{rk}(V_\varphi) ent ( φ ) = rk ( V φ ) by [19 Corollary 4.8] (see also [36 Equation (1.3) and Uniqueness Theorem] ). □
Lemma 7. Let A \mathcal{A} A be a commutative F p \mathbb{F}_p F p -algebra, let N ∈ M n ( A ) N \in M_n(\mathcal{A}) N ∈ M n ( A ) , and let A N n \mathcal{A}_N^n A N n denote A n \mathcal{A}^n A n regarded as an F p [ t ] \mathbb{F}_p[t] F p [ t ] -module, t t t acting as N N N . Let K = F p ( t ) \mathbb{K} = \mathbb{F}_p(t) K = F p ( t ) and A K = K ⊗ F p A \mathcal{A}_{\mathbb{K}} = \mathbb{K} \otimes_{\mathbb{F}_p} \mathcal{A} A K = K ⊗ F p A . Then
K ⊗ F p [ t ] A N n ≅ A K n / ( t I − N ) A K n . \mathbb{K} \otimes_{\mathbb{F}_p[t]} \mathcal{A}_N^n \cong\mathcal{A}_{\mathbb{K}}^n/(tI-N)\mathcal{A}_{\mathbb{K}}^n. K ⊗ F p [ t ] A N n ≅ A K n / ( t I − N ) A K n .
Proof. Consider the sequence of A [ t ] \mathcal{A}[t] A [ t ] -modules
A [ t ] n → t I − N A [ t ] n → ε A N n ⟶ 0 , ε ( ∑ k t k b k ) = ∑ k N k b k . \mathcal{A}[t]^n \xrightarrow{tI-N} \mathcal{A}[t]^n \xrightarrow{\varepsilon} \mathcal{A}_N^n \longrightarrow0,\qquad\varepsilon\left(\sum_k t^k b_k\right)=\sum_k N^k b_k. A [ t ] n t I − N A [ t ] n ε A N n ⟶ 0 , ε ( k ∑ t k b k ) = k ∑ N k b k .
Clearly ε \varepsilon ε is surjective and ε ∘ ( t I − N ) = 0 \varepsilon\circ(tI-N)=0 ε ∘ ( t I − N ) = 0 . Moreover, modulo the image of t I − N tI-N t I − N we have t k b ≡ t k − 1 N b t^k b \equiv t^{k-1}Nb t k b ≡ t k − 1 N b , so that every element of A [ t ] n \mathcal{A}[t]^n A [ t ] n is congruent to an element of A n \mathcal{A}^n A n (a polynomial of degree 0 0 0 in t t t ), on which ε \varepsilon ε is injective; hence the sequence is exact. Since A [ t ] = F p [ t ] ⊗ F p A \mathcal{A}[t]=\mathbb{F}_p[t]\otimes_{\mathbb{F}_p}\mathcal{A} A [ t ] = F p [ t ] ⊗ F p A , we have K ⊗ F p [ t ] A [ t ] = A K \mathbb{K}\otimes_{\mathbb{F}_p[t]}\mathcal{A}[t]=\mathcal{A}_{\mathbb{K}} K ⊗ F p [ t ] A [ t ] = A K , and the claim follows from the right exactness of K ⊗ F p [ t ] − \mathbb{K}\otimes_{\mathbb{F}_p[t]}- K ⊗ F p [ t ] − .
Proof of Theorem 4. Let K = F p ( t ) \mathbb{K}=\mathbb{F}_p(t) K = F p ( t ) and S = K [ x 1 ± 1 , … , x D ± 1 ] = K ⊗ F p L p \mathcal{S}=\mathbb{K}[x_1^{\pm1},\ldots,x_D^{\pm1}]=\mathbb{K}\otimes_{\mathbb{F}_p}\mathbb{L}_p S = K [ x 1 ± 1 , … , x D ± 1 ] = K ⊗ F p L p . The dual group L p n \mathbb{L}_p^n L p n of Lemma 5 is torsion. By Lemma 5, Theorem 5, Lemma 6 and Lemma 7 (with A = L p \mathcal{A}=\mathbb{L}_p A = L p and N = M ∗ N=M^* N = M ∗ ) we obtain
H ( F ) = log p ⋅ dim K Q , Q = S n / Γ S n , Γ = t I − M ∗ ∈ M n ( S ) . (17) \mathcal{H}(\mathcal{F})=\log p\cdot\dim_{\mathbb{K}}Q,\qquad Q=\mathcal{S}^n/\Gamma\mathcal{S}^n,\qquad\Gamma=tI-M^*\in M_n(\mathcal{S}). \tag*{(17)} H ( F ) = log p ⋅ dim K Q , Q = S n /Γ S n , Γ = t I − M ∗ ∈ M n ( S ) . (17)
Since transposition does not change determinants and x ↦ x − 1 x\mapsto x^{-1} x ↦ x − 1 is a ring automorphism, det Γ = χ M ( t ) ∣ x ↦ x − 1 \det\Gamma=\chi_M(t)|_{x\mapsto x^{-1}} det Γ = χ M ( t ) ∣ x ↦ x − 1 . Write χ M = ∑ u ∈ Z D g u ( t ) x u \chi_M=\sum_{u\in\mathbb{Z}^D}g_u(t)x^u χ M = ∑ u ∈ Z D g u ( t ) x u with g u ∈ F p [ t ] g_u\in\mathbb{F}_p[t] g u ∈ F p [ t ] , and let Supp ( χ M ) = { u : g u ≠ 0 } \operatorname{Supp}(\chi_M)=\{u:g_u\ne0\} Supp ( χ M ) = { u : g u = 0 } . Since g u ( t ) = ∑ i < n ( c i ) u t i + [ u = 0 ] t n g_u(t)=\sum_{i<n}(c_i)_u t^i+[u=0]t^n g u ( t ) = ∑ i < n ( c i ) u t i + [ u = 0 ] t n , we have
Supp ( χ M ) = { 0 } ∪ ⋃ i : c i ≠ 0 supp ( c i ) . (18) \operatorname{Supp}(\chi_M)=\{0\}\cup\bigcup_{i:c_i\ne0}\operatorname{supp}(c_i). \tag*{(18)} Supp ( χ M ) = { 0 } ∪ i : c i = 0 ⋃ supp ( c i ) . (18)
In particular det Γ ≠ 0 \det\Gamma\ne0 det Γ = 0 , Supp ( det Γ ) = − Supp ( χ M ) \operatorname{Supp}(\det\Gamma)=-\operatorname{Supp}(\chi_M) Supp ( det Γ ) = − Supp ( χ M ) , and c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p if and only if Supp ( χ M ) = { 0 } \operatorname{Supp}(\chi_M)=\{0\} Supp ( χ M ) = { 0 } , i.e., if and only if χ M ∈ F p [ t ] \chi_M\in\mathbb{F}_p[t] χ M ∈ F p [ t ] .
Let D = 1 D=1 D = 1 . Then S = K [ x ± 1 ] \mathcal{S}=\mathbb{K}[x^{\pm1}] S = K [ x ± 1 ] is a principal ideal domain. For 0 ≠ q ∈ S 0\ne q\in\mathcal{S} 0 = q ∈ S let wd ( q ) = max Supp ( q ) − min Supp ( q ) \operatorname{wd}(q)=\max\operatorname{Supp}(q)-\min\operatorname{Supp}(q) wd ( q ) = max Supp ( q ) − min Supp ( q ) be its width. We have dim K S / q S = wd ( q ) \dim_{\mathbb{K}}\mathcal{S}/q\mathcal{S}=\operatorname{wd}(q) dim K S / q S = wd ( q ) : indeed q = λ x a g q=\lambda x^a g q = λ x a g with λ ∈ K × \lambda\in\mathbb{K}^{\times} λ ∈ K × , a ∈ Z a\in\mathbb{Z} a ∈ Z and g ∈ K [ x ] g\in\mathbb{K}[x] g ∈ K [ x ] monic of degree wd ( q ) \operatorname{wd}(q) wd ( q ) with g ( 0 ) ≠ 0 g(0)\ne0 g ( 0 ) = 0 , and since x x x is invertible modulo g g g , S / q S = S / g S ≅ K [ x ] / g K [ x ] \mathcal{S}/q\mathcal{S}=\mathcal{S}/g\mathcal{S}\cong\mathbb{K}[x]/g\mathbb{K}[x] S / q S = S / g S ≅ K [ x ] / g K [ x ] . Moreover wd ( q q ′ ) = wd ( q ) + wd ( q ′ ) \operatorname{wd}(qq')=\operatorname{wd}(q)+\operatorname{wd}(q') wd ( q q ′ ) = wd ( q ) + wd ( q ′ ) , since the extreme coefficients of a product are the products of the extreme coefficients, and the units of S \mathcal{S} S have width 0 0 0 . By the Smith normal form, Γ = P diag ( d 1 , … , d n ) P ′ \Gamma=P\operatorname{diag}(d_1,\ldots,d_n)P' Γ = P diag ( d 1 , … , d n ) P ′ with P , P ′ ∈ G L n ( S ) P,P'\in GL_n(\mathcal{S}) P , P ′ ∈ G L n ( S ) and d i ≠ 0 d_i\ne0 d i = 0 , so that Q ≅ ⨁ i S / d i S Q\cong\bigoplus_i\mathcal{S}/d_i\mathcal{S} Q ≅ ⨁ i S / d i S and
dim K Q = ∑ i wd ( d i ) = wd ( ∏ i d i ) = wd ( det Γ ) = wd ( χ M ) = E M + − E M − , \dim_{\mathbb{K}}Q=\sum_i\operatorname{wd}(d_i)=\operatorname{wd}\left(\prod_i d_i\right)=\operatorname{wd}(\det\Gamma)=\operatorname{wd}(\chi_M)=E_M^+-E_M^-, dim K Q = i ∑ wd ( d i ) = wd ( i ∏ d i ) = wd ( det Γ ) = wd ( χ M ) = E M + − E M − ,
where the last equality follows from (18) . By (17) , H ( F ) = ( E M + − E M − ) log p \mathcal{H}(\mathcal{F})=(E_M^+-E_M^-)\log p H ( F ) = ( E M + − E M − ) log p .
Let D ≥ 2 D\ge2 D ≥ 2 . If χ M ∈ F p [ t ] \chi_M\in\mathbb{F}_p[t] χ M ∈ F p [ t ] , then det Γ ∈ F p [ t ] ∖ { 0 } ⊆ K × \det\Gamma\in\mathbb{F}_p[t]\setminus\{0\}\subseteq\mathbb{K}^{\times} det Γ ∈ F p [ t ] ∖ { 0 } ⊆ K × is a unit of S \mathcal{S} S , Γ \Gamma Γ is invertible, Q = 0 Q=0 Q = 0 and H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 . Otherwise Supp ( det Γ ) \operatorname{Supp}(\det\Gamma) Supp ( det Γ ) contains at least two points, so that det Γ \det\Gamma det Γ is not a unit of S \mathcal{S} S (comparing extreme monomials, the units of
S S S are the elements λ x u \lambda x^{u} λ x u with λ ∈ K × \lambda\in\mathbb{K}^{\times} λ ∈ K × ). Since S S S is a unique factorization domain, det Γ \det\Gamma det Γ has an irreducible factor π \pi π , and p = π S \mathfrak{p}=\pi S p = π S is a prime ideal containing det Γ \det\Gamma det Γ .
First, the localization Q p = S p n / Γ S p n Q_{\mathfrak{p}}=S_{\mathfrak{p}}^{n}/\Gamma S_{\mathfrak{p}}^{n} Q p = S p n /Γ S p n is non-zero: otherwise Γ B = I \Gamma B=I Γ B = I for some B ∈ M n ( S p ) B\in M_{n}(S_{\mathfrak{p}}) B ∈ M n ( S p ) , and det Γ \det\Gamma det Γ would be a unit of S p S_{\mathfrak{p}} S p , contradicting det Γ ∈ p S p \det\Gamma\in\mathfrak{p}S_{\mathfrak{p}} det Γ ∈ p S p .
Now assume that dim K Q < ∞ \dim_{\mathbb{K}}Q<\infty dim K Q < ∞ . For 1 ≤ i ≤ D 1\leq i\leq D 1 ≤ i ≤ D , the multiplication by x i x_i x i is a K \mathbb{K} K -linear endomorphism of Q Q Q , so by the Cayley–Hamilton theorem there is 0 ≠ f i ∈ K [ x i ] 0\neq f_i\in\mathbb{K}[x_i] 0 = f i ∈ K [ x i ] with f i Q = 0 f_iQ=0 f i Q = 0 . We claim that f i ∉ p f_i\notin\mathfrak{p} f i ∈ / p for some i i i . For q ∈ S q\in S q ∈ S and j ≤ D j\leq D j ≤ D , let wd j ( q ) \operatorname{wd}_j(q) wd j ( q ) be the width of q q q as a Laurent polynomial in x j x_j x j with coefficients in the domain K [ x h ± 1 : h ≠ j ] \mathbb{K}[x_h^{\pm1}:h\neq j] K [ x h ± 1 : h = j ] ; as in part (1), wd j \operatorname{wd}_j wd j is additive. If π \pi π divides f 1 f_1 f 1 , then wd j ( π ) = 0 \operatorname{wd}_j(\pi)=0 wd j ( π ) = 0 for every j ≠ 1 j\neq1 j = 1 , so that π \pi π is, up to a unit, an element of K [ x 1 ± 1 ] \mathbb{K}[x_1^{\pm1}] K [ x 1 ± 1 ] . If π \pi π also divides f 2 f_2 f 2 , then in the same way wd 1 ( π ) = 0 \operatorname{wd}_1(\pi)=0 wd 1 ( π ) = 0 , and π \pi π would be a unit, a contradiction. Hence some f i f_i f i is not in p \mathfrak{p} p , and it is invertible in S p S_{\mathfrak{p}} S p ; since f i Q p = 0 f_iQ_{\mathfrak{p}}=0 f i Q p = 0 , we get Q p = 0 Q_{\mathfrak{p}}=0 Q p = 0 , a contradiction. Therefore dim K Q = ∞ \dim_{\mathbb{K}}Q=\infty dim K Q = ∞ , and H ( F ) = + ∞ \mathcal{H}(\mathcal{F})=+\infty H ( F ) = + ∞ by Equation (17) .
(3) If c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p , by the Cayley–Hamilton theorem M n M^n M n is an F p \mathbb{F}_p F p -linear combination of I , M , … , M n − 1 I,M,\ldots,M^{n-1} I , M , … , M n − 1 ; hence every power of M M M belongs to the finite set span F p { I , M , … , M n − 1 } \operatorname{span}_{\mathbb{F}_p}\{I,M,\ldots,M^{n-1}\} span F p { I , M , … , M n − 1 } , and there exist a < b a<b a < b with M a = M b M^a=M^b M a = M b . Then F a = F b \mathcal{F}^a=\mathcal{F}^b F a = F b , the family { F k } k ≥ 0 = { F 0 , … , F b − 1 } \{\mathcal{F}^k\}_{k\geq0}=\{\mathcal{F}^0,\ldots,\mathcal{F}^{b-1}\} { F k } k ≥ 0 = { F 0 , … , F b − 1 } is a finite family of uniformly continuous maps, and F \mathcal{F} F is equicontinuous. Conversely, if F \mathcal{F} F is equicontinuous, then H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 by Proposition 1. If D ≥ 2 D\geq2 D ≥ 2 , (2) gives c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p . If D = 1 D=1 D = 1 , (1) gives E M + = E M − = 0 E_M^+=E_M^-=0 E M + = E M − = 0 , i.e., supp ( c i ) ⊆ { 0 } \operatorname{supp}(c_i)\subseteq\{0\} supp ( c i ) ⊆ { 0 } for every c i ≠ 0 c_i\neq0 c i = 0 , which again means c 0 , … , c n − 1 ∈ F p c_0,\ldots,c_{n-1}\in\mathbb{F}_p c 0 , … , c n − 1 ∈ F p . □
Corollary 2. Let D ≥ 2 D\geq2 D ≥ 2 and let F \mathcal{F} F be a D D D -GCA on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n . If F \mathcal{F} F is not equicontinuous (in particular, if F \mathcal{F} F is sensitive to initial conditions), then H ( F ) = + ∞ \mathcal{H}(\mathcal{F})=+\infty H ( F ) = + ∞ .
Remark 1. For n = 1 n=1 n = 1 and D = 1 D=1 D = 1 we have M = m ( x ) M=m(x) M = m ( x ) and χ M ( t ) = t − m ( x ) \chi_M(t)=t-m(x) χ M ( t ) = t − m ( x ) , so that Theorem 4 gives H ( F ) = ( max ( 0 , max supp ( m ) ) − min ( 0 , min supp ( m ) ) ) log p \mathcal{H}(\mathcal{F})=(\max(0,\max\operatorname{supp}(m))-\min(0,\min\operatorname{supp}(m)))\log p H ( F ) = ( max ( 0 , max supp ( m )) − min ( 0 , min supp ( m ))) log p , which is the formula of [10 ] for linear CAs over Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z . Theorem 4(1) shows that, for n > 1 n>1 n > 1 , the relevant quantity is not the degree range of the entries of M M M but the one of the coefficients of its characteristic polynomial. For instance, if M = ( 0 x 0 0 ) M=\begin{pmatrix}0&x\\0&0\end{pmatrix} M = ( 0 0 x 0 ) , then χ M = t 2 \chi_M=t^2 χ M = t 2 and H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 ; indeed F 2 \mathcal{F}^2 F 2 is the null map.
Remark 2. Theorem 4 also yields a second proof of Theorem 3, which does not rely on [4 ] and gives an explicit procedure. Let F \mathcal{F} F be a one-dimensional GCA on a finite group G G G , and let { ( F 1 , G 1 ) , … , ( F k , G k ) } \{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_k,G_k)\} {( F 1 , G 1 ) , … , ( F k , G k )} be the output of the function Decomposition of Subsection 6.1 on ( F , G ) (\mathcal{F},G) ( F , G ) ; this output is effectively computable from the local rule of F \mathcal{F} F . By Corollary 3(2), H ( F ) = ∑ i H ( F i ) \mathcal{H}(\mathcal{F})=\sum_i\mathcal{H}(\mathcal{F}_i) H ( F ) = ∑ i H ( F i ) . If G i ≅ ( Z / p Z ) n G_i\cong(\mathbb{Z}/p\mathbb{Z})^n G i ≅ ( Z / p Z ) n , then H ( F i ) \mathcal{H}(\mathcal{F}_i) H ( F i ) is given by Theorem 4(1). Otherwise, by Lemmata 11 and 12, either F i \mathcal{F}_i F i is constant, and H ( F i ) = 0 \mathcal{H}(\mathcal{F}_i)=0 H ( F i ) = 0 , or F i \mathcal{F}_i F i is surjective and G i G_i G i is minimal with respect to F i \mathcal{F}_i F i , and H ( F i ) \mathcal{H}(\mathcal{F}_i) H ( F i ) is given by Theorem 7(2). All these steps are effective.
Topological entropy of D D D -dimensional GCAs
Throughout this section, D D D denotes an integer greater than 1, except in Subsection 6.3, where D ≥ 1 D\geq1 D ≥ 1 is arbitrary.
We prove that sensitive to initial conditions D D D -GCAs have infinite topological entropy. On the other hand, every D D D -GCA is either equicontinuous or sensitive to initial conditions (Proposition 2), and equicontinuous D D D -GCAs have zero topological entropy (Proposition 1). As a consequence of these results, we obtain the following dichotomy.
Theorem 6. Let D ≥ 2 D \ge2 D ≥ 2 and let F \mathcal{F} F be a D D D -GCA on a finite group G G G . Then either F \mathcal{F} F is equicontinuous and H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 , or F \mathcal{F} F is sensitive to initial conditions and H ( F ) = + ∞ \mathcal{H}(\mathcal{F}) = +\infty H ( F ) = + ∞ .
Our approach is inspired by the one-dimensional case. In [8 ] , three of the present authors showed that the topological entropy of a one-dimensional GCA decomposes as the sum of the topological entropies of finitely many one-dimensional GCAs. More precisely, these factors are defined either on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n , with p p p prime, or on products of isomorphic non-abelian simple groups.
In the same paper, they also proved that a one-dimensional GCA is sensitive to initial conditions if and only if at least one of the factors in this decomposition is sensitive to initial conditions.
We prove the D D D -dimensional versions of these statements in Subsection 6.1 (Corollary 3) for a refined decomposition based on normal F \mathcal{F} F -invariant subgroups. In particular, if a D D D -GCA is sensitive to initial conditions, then at least one of the factors arising from the corresponding decomposition is sensitive to initial conditions. Hence, to establish our main result it suffices to show that every sensitive D D D -GCA defined either on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n (see Subsection 6.2) or on a product of isomorphic non-abelian simple groups (see Subsection 6.3) has infinite topological entropy. This will imply that any D D D -GCA sensitive to initial conditions has infinite topological entropy.
Decomposition of D D D -GCAs
In this subsection we prove the D D D -dimensional versions of two results of [8 ] based on a decomposition of GCAs via quotients by normal F \mathcal{F} F -invariant subgroups. In particular, we state the results related to sensitivity to initial conditions and to topological entropy that will be used throughout this paper.
Let G G G be a finite group and let F \mathcal{F} F be a D D D -GCA on G G G with local rule f = ( h 1 , … , h k ) f = (h_1, \ldots, h_k) f = ( h 1 , … , h k ) . A subgroup H ≤ G H \le G H ≤ G is F \mathcal{F} F -invariant if F ( H Z D ) ⊆ H Z D \mathcal{F}(H^{\mathbb{Z}^D}) \subseteq H^{\mathbb{Z}^D} F ( H Z D ) ⊆ H Z D . Evaluating F \mathcal{F} F on configurations supported on a single cell, and recalling that the vectors of V f V_f V f are pairwise distinct, one sees that H H H is F \mathcal{F} F -invariant if and only if h j ( H ) ⊆ H h_j(H) \subseteq H h j ( H ) ⊆ H for every j j j ; in particular, this property can be checked effectively. Let H H H be a normal F \mathcal{F} F -invariant subgroup of G G G . For g ∈ G g \in G g ∈ G , we denote by [ g ] : = g H [g] := gH [ g ] := g H the coset of g g g in G / H G/H G / H , and for c ∈ G Z D c \in G^{\mathbb{Z}^D} c ∈ G Z D we write [ c ] [c] [ c ] for the element of ( G / H ) Z D (G/H)^{\mathbb{Z}^D} ( G / H ) Z D defined by [ c ] ( v ) : = [ c ( v ) ] [c](v) := [c(v)] [ c ] ( v ) := [ c ( v )] . The maps F ‾ : H Z D → H Z D \overline{\mathcal{F}} : H^{\mathbb{Z}^D} \to H^{\mathbb{Z}^D} F : H Z D → H Z D and F ~ : ( G / H ) Z D → ( G / H ) Z D \widetilde{\mathcal{F}} : (G/H)^{\mathbb{Z}^D} \to(G/H)^{\mathbb{Z}^D} F : ( G / H ) Z D → ( G / H ) Z D defined by
∀ c ∈ H Z D : F ‾ ( c ) : = F ( c ) and (19) \forall c \in H^{\mathbb{Z}^D} : \overline{\mathcal{F}}(c) := \mathcal{F}(c) \text{ and} \tag*{(19)} ∀ c ∈ H Z D : F ( c ) := F ( c ) and (19)
∀ [ c ] ∈ ( G / H ) Z D : F ~ ( [ c ] ) : = [ F ( c ) ] (20) \forall[c] \in(G/H)^{\mathbb{Z}^D} : \widetilde{\mathcal{F}}([c]) := [\mathcal{F}(c)] \tag*{(20)} ∀ [ c ] ∈ ( G / H ) Z D : F ([ c ]) := [ F ( c )] (20)
are well-defined D D D -GCAs on H Z D H^{\mathbb{Z}^D} H Z D and ( G / H ) Z D (G/H)^{\mathbb{Z}^D} ( G / H ) Z D , respectively. We say that ( F , G ) (\mathcal{F},G) ( F , G ) is irreducible if G G G has no non-trivial proper normal F \mathcal{F} F -invariant subgroup.
We use the following variant of the decomposition function of [8 ] , where H H H was required to be fully invariant.
Function Decomposition($\mathcal{F},G$):
if ($\mathcal{F},G$) is irreducible then
return $\{(\mathcal{F},G)\}$;
end
else
Let $H$ be a non-trivial proper normal $\mathcal{F}$-invariant subgroup of $G$;
$a \leftarrow$ Decomposition($\widetilde{\mathcal{F}},G/H$);
$b \leftarrow$ Decomposition($\mathcal{F},H$);
return $a \cup b$;
end
The output { ( F 1 , G 1 ) , … , ( F k , G k ) } \{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_k,G_k)\} {( F 1 , G 1 ) , … , ( F k , G k )} is effectively computable from the local rule of F \mathcal{F} F , since G G G has finitely many subgroups. Recall that a subgroup of G G G is fully invariant if it is mapped into itself by every endomorphism of G G G , and that G G G is invariantly simple if its only fully invariant subgroups are { e } \{e\} { e } and G G G . Every fully invariant subgroup of G G G is normal and F \mathcal{F} F -invariant; hence, if ( F i , G i ) (\mathcal{F}_i,G_i) ( F i , G i ) is irreducible, then G i G_i G i has no non-trivial proper fully invariant subgroup, i.e., it is invariantly simple, and therefore it is a direct product of isomorphic simple groups [8 ] . In particular, if G i G_i G i is abelian, then G i ≅ ( Z / p Z ) n G_i \cong(\mathbb{Z}/p\mathbb{Z})^n G i ≅ ( Z / p Z ) n for some prime p p p and some n ∈ N n \in\mathbb{N} n ∈ N .
We now prove the two facts about Decomposition that will be used in this paper. For one-dimensional GCAs, the fact that sensitivity to initial conditions is detected by the components of the decomposition was proved in [8 ] . Here we give a proof which is valid in every dimension D ≥ 1 D \ge1 D ≥ 1 .
Lemma 8. Let G G G be a finite group, let F \mathcal{F} F be a D D D -GCA on G G G , and let H H H be a normal subgroup of G G G such that F ( H Z D ) ⊆ H Z D \mathcal{F}(H^{\mathbb{Z}^D}) \subseteq H^{\mathbb{Z}^D} F ( H Z D ) ⊆ H Z D . Let F ‾ \overline{\mathcal{F}} F be the restriction of F \mathcal{F} F to H Z D H^{\mathbb{Z}^D} H Z D and F ~ \widetilde{\mathcal{F}} F the induced D D D -GCA on ( G / H ) Z D (G/H)^{\mathbb{Z}^D} ( G / H ) Z D , F ~ ( [ c ] ) = [ F ( c ) ] \widetilde{\mathcal{F}}([c]) = [\mathcal{F}(c)] F ([ c ]) = [ F ( c )] . Then F \mathcal{F} F is equicontinuous if and only if both F ‾ \overline{\mathcal{F}} F and F ~ \widetilde{\mathcal{F}} F are equicontinuous. Consequently, F \mathcal{F} F is sensitive to initial conditions if and only if at least one of F ‾ \overline{\mathcal{F}} F and F ~ \widetilde{\mathcal{F}} F is sensitive to initial conditions.
Proof. The map F ~ \widetilde{\mathcal{F}} F is well defined because F ( c z ) = F ( c ) F ( z ) \mathcal{F}(cz)=\mathcal{F}(c)\mathcal{F}(z) F ( cz ) = F ( c ) F ( z ) with F ( z ) ∈ H Z D \mathcal{F}(z) \in H^{\mathbb{Z}^D} F ( z ) ∈ H Z D for every z ∈ H Z D z \in H^{\mathbb{Z}^D} z ∈ H Z D . If F \mathcal{F} F is equicontinuous, then F a = F b \mathcal{F}^{a}=\mathcal{F}^{b} F a = F b for some a < b a<b a < b by Proposition 2(i), and the same identity holds for F ‾ \overline{\mathcal{F}} F and F ~ \widetilde{\mathcal{F}} F , which are therefore equicontinuous. Conversely, assume that both F ‾ \overline{\mathcal{F}} F and F ~ \widetilde{\mathcal{F}} F are equicontinuous. By Proposition 2(i) there are a 1 , a 2 ≥ 0 a_1,a_2 \ge0 a 1 , a 2 ≥ 0 and p 1 , p 2 ≥ 1 p_1,p_2 \ge1 p 1 , p 2 ≥ 1 with F ‾ a 1 + p 1 = F ‾ a 1 \overline{\mathcal{F}}^{a_1+p_1}=\overline{\mathcal{F}}^{a_1} F a 1 + p 1 = F a 1 and F ~ a 2 + p 2 = F ~ a 2 \widetilde{\mathcal{F}}^{a_2+p_2}=\widetilde{\mathcal{F}}^{a_2} F a 2 + p 2 = F a 2 . If φ a + p = φ a \varphi^{a+p}=\varphi^a φ a + p = φ a , then φ q + p = φ q − a φ a + p = φ q \varphi^{q+p}=\varphi^{q-a}\varphi^{a+p}=\varphi^q φ q + p = φ q − a φ a + p = φ q for every q ≥ a q\ge a q ≥ a , hence φ 2 q = φ q \varphi^{2q}=\varphi^q φ 2 q = φ q whenever p p p divides q q q . Therefore, choosing q ≥ max ( a 1 , a 2 ) q\ge\max(a_1,a_2) q ≥ max ( a 1 , a 2 ) divisible by p 1 p 2 p_1p_2 p 1 p 2 , T = F q T=\mathcal{F}^q T = F q satisfies T 2 ∣ H Z D = T ∣ H Z D T^2|_{H^{\mathbb{Z}^D}}=T|_{H^{\mathbb{Z}^D}} T 2 ∣ H Z D = T ∣ H Z D and T ~ 2 = T ~ \widetilde{T}^2=\widetilde{T} T 2 = T , where T ~ = F ~ q \widetilde{T}=\widetilde{\mathcal{F}}^q T = F q . For x ∈ G Z D x\in G^{\mathbb{Z}^D} x ∈ G Z D put u = T ( x ) u=T(x) u = T ( x ) and h = T ( u ) u − 1 h=T(u)u^{-1} h = T ( u ) u − 1 . Since [ T ( u ) ] = T ~ 2 [ x ] = T ~ [ x ] = [ u ] [T(u)]=\widetilde{T}^2[x]=\widetilde{T}[x]=[u] [ T ( u )] = T 2 [ x ] = T [ x ] = [ u ] and H H H is normal, h ∈ H Z D h\in H^{\mathbb{Z}^D} h ∈ H Z D , so that T 2 ( h ) = T ( h ) T^2(h)=T(h) T 2 ( h ) = T ( h ) . From T ( u ) = h u T(u)=hu T ( u ) = h u we get, by induction on j j j ,
T j + 1 ( u ) = T ( h ) j h u ( j ≥ 0 ) . T^{j+1}(u)=T(h)^j h u \qquad(j\ge0). T j + 1 ( u ) = T ( h ) j h u ( j ≥ 0 ) .
Let m m m be the exponent of H H H . Since T ( h ) ∈ H Z D T(h)\in H^{\mathbb{Z}^D} T ( h ) ∈ H Z D , we have T ( h ) m = e Z D T(h)^m=e^{\mathbb{Z}^D} T ( h ) m = e Z D , hence T m + 1 ( u ) = T ( u ) T^{m+1}(u)=T(u) T m + 1 ( u ) = T ( u ) , that is, T m + 2 ( x ) = T 2 ( x ) T^{m+2}(x)=T^2(x) T m + 2 ( x ) = T 2 ( x ) . As x x x is arbitrary, F q ( m + 2 ) = F 2 q \mathcal{F}^{q(m+2)}=\mathcal{F}^{2q} F q ( m + 2 ) = F 2 q , and F \mathcal{F} F is equicontinuous by Proposition 2(i). The statement on sensitivity follows from Proposition 2(ii), applied to F \mathcal{F} F , F ‾ \overline{\mathcal{F}} F and F ~ \widetilde{\mathcal{F}} F . ▫
Corollary 3. Let ( F , G ) (\mathcal{F},\mathcal{G}) ( F , G ) be a D D D -GCA and let { ( F 1 , G 1 ) , … , ( F k , G k ) } \{(\mathcal{F}_1,\mathcal{G}_1),\ldots,(\mathcal{F}_k,\mathcal{G}_k)\} {( F 1 , G 1 ) , … , ( F k , G k )} be the output of Decomposition on ( F , G ) (\mathcal{F},\mathcal{G}) ( F , G ) . Then:
(1) F \mathcal{F} F is sensitive to initial conditions if and only if some F i \mathcal{F}_i F i is sensitive to initial conditions;
(2) H ( F ) = ∑ i = 1 k H ( F i ) \mathcal{H}(\mathcal{F}) = \sum_{i=1}^{k} \mathcal{H}(\mathcal{F}_i) H ( F ) = ∑ i = 1 k H ( F i ) .
Proof. Both statements are proved by induction on the depth of the recursion of Decomposition. At each step the chosen subgroup H H H is normal and F \mathcal{F} F -invariant. Then (1) follows from Lemma 8, and (2) from the addition formula for the topological entropy of continuous endomorphisms of compact metrizable groups with respect to closed invariant normal subgroups (see, e.g., [7 Theorem 19] , [44 ] and [16 Fact 3.3] ).
D-GCAs on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n
Let p p p be a prime. Since every endomorphism of ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n is F p \mathbb{F}_p F p -linear, D D D -GCAs on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n are exactly the linear cellular automata studied in Section 5; they are represented by n × n n \times n n × n matrices whose entries are multivariate Laurent polynomials with coefficients in Z / p Z \mathbb{Z}/p\mathbb{Z} Z / p Z , i.e., elements of L p = ( Z / p Z ) [ x 1 , x 1 − 1 , … , x D , x D − 1 ] L_p = (\mathbb{Z}/p\mathbb{Z})[x_1,x_1^{-1},\ldots,x_D,x_D^{-1}] L p = ( Z / p Z ) [ x 1 , x 1 − 1 , … , x D , x D − 1 ] .
By Theorem 4, a D D D -GCA F \mathcal{F} F on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n , D ≥ 2 D \ge2 D ≥ 2 , either is equicontinuous and has zero topological entropy (when all the coefficients of the characteristic polynomial of its matrix are constants), or is not equicontinuous and has infinite topological entropy. Since a sensitive CA is not equicontinuous, we obtain the result needed for Theorem 6 (Corollary 2): every D D D -GCA on ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n which is sensitive to initial conditions has infinite topological entropy.
A proof of the same fact which does not use Pontryagin duality is given in Appendix A. We stress that neither argument requires any reduction to the Frobenius normal form of the matrix [13 ] , nor any characterization of sensitivity: the dichotomy between zero and infinite entropy is a purely algebraic consequence of the fact that, for D ≥ 2 D \ge2 D ≥ 2 , the module S n / ( t I − M ∗ ) S n S^n/(tI-M^*)S^n S n / ( t I − M ∗ ) S n appearing in the proof of Theorem 4 is either trivial or infinite-dimensional.
D-GCAs on a product of isomorphic non-abelian simple groups
Throughout this subsection the dimension D ≥ 1 D \ge1 D ≥ 1 is arbitrary. Several of the facts collected below were established in [8 ] for D = 1 D=1 D = 1 . Their proofs only involve the local rule and the algebraic structure of the alphabet, so they hold verbatim in every dimension; we point out explicitly the few places where the lattice Z D \mathbb{Z}^D Z D plays a role.
Fix a finite non-abelian simple group S S S and let G = S 1 × ⋯ × S m G=S_1 \times\cdots\times S_m G = S 1 × ⋯ × S m , with S i ≅ S S_i \cong S S i ≅ S for every i i i . We regard each S i S_i S i as a subgroup of G G G , namely as the set of elements of G G G whose coordinates other than the i i i -th one are trivial.
Every normal subgroup of a finite direct product of non-abelian simple groups is the product of some of the factors (see, e.g., [18 p. 174] ). Applied to kernels, this shows that for every h ∈ End ( G ) h \in\operatorname{End}(G) h ∈ End ( G ) there is a set I ⊆ { 1 , … , m } I \subseteq\{1,\ldots,m\} I ⊆ { 1 , … , m } , possibly empty, such that Ker ( h ) = ∏ t ∈ I S t \operatorname{Ker}(h)=\prod_{t\in I}S_t Ker ( h ) = ∏ t ∈ I S t . Likewise, if H = ∏ t ∈ I S t H=\prod_{t\in I}S_t H = ∏ t ∈ I S t is a normal subgroup of G G G , then G / H ≅ ∏ t ∉ I S t G/H\cong\prod_{t\notin I}S_t G / H ≅ ∏ t ∈ / I S t is again a product of copies of S S S ; in particular, its center is trivial.
Given v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D and a ∈ G a \in G a ∈ G , we write c ( v , a ) c^{(v,a)} c ( v , a ) for the configuration which equals a a a at position v v v and e e e at every other position.
Lemma 9. Let F \mathcal{F} F be a D D D -GCA over G = S 1 × ⋯ × S m G = S_{1} \times\cdots\times S_{m} G = S 1 × ⋯ × S m whose local rule f = ( h 1 , … , h k ) f = (h_{1}, \ldots, h_{k}) f = ( h 1 , … , h k ) has neighborhood V f = { v 1 , … , v k } V_{f} = \{v_{1}, \ldots, v_{k}\} V f = { v 1 , … , v k } , so that F ( c ) w = h 1 ( c w + v 1 ) ⋯ h k ( c w + v k ) \mathcal{F}(c)_{w} = h_{1}(c_{w+v_{1}}) \cdots h_{k}(c_{w+v_{k}}) F ( c ) w = h 1 ( c w + v 1 ) ⋯ h k ( c w + v k ) . Then
Ker ( F ) = ( ⋂ j = 1 k Ker ( h j ) ) Z D . \operatorname{Ker}(\mathcal{F}) = \left(\bigcap_{j=1}^{k} \operatorname{Ker}(h_{j})\right)^{\mathbb{Z}^{D}}. Ker ( F ) = ( j = 1 ⋂ k Ker ( h j ) ) Z D .
Proof. Set H = ⋂ j = 1 k Ker ( h j ) H = \bigcap_{j=1}^{k} \operatorname{Ker}(h_{j}) H = ⋂ j = 1 k Ker ( h j ) , a normal subgroup of G G G . Every configuration with values in H H H is mapped to e Z D e^{\mathbb{Z}^{D}} e Z D , hence H Z D ⊆ Ker ( F ) H^{\mathbb{Z}^{D}} \subseteq\operatorname{Ker}(\mathcal{F}) H Z D ⊆ Ker ( F ) .
For the reverse inclusion, we first determine which configurations supported on a single cell belong to the kernel. Let v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D and a ∈ G a \in G a ∈ G . Since the vectors v j v_{j} v j are pairwise distinct, the value of F ( c ( v , a ) ) \mathcal{F}(c^{(v,a)}) F ( c ( v , a ) ) at position v − v j v-v_{j} v − v j is h j ( a ) h_{j}(a) h j ( a ) . It follows that c ( v , a ) ∈ Ker ( F ) c^{(v,a)} \in\operatorname{Ker}(\mathcal{F}) c ( v , a ) ∈ Ker ( F ) exactly when a ∈ H a \in H a ∈ H .
Now take c ∈ Ker ( F ) c \in\operatorname{Ker}(\mathcal{F}) c ∈ Ker ( F ) , a position v ∈ Z D v \in\mathbb{Z}^{D} v ∈ Z D and an element g ∈ G g \in G g ∈ G , and put d = c ( v , g ) d = c^{(v,g)} d = c ( v , g ) . The kernel is a normal subgroup of G Z D G^{\mathbb{Z}^{D}} G Z D , so the commutator d c d − 1 c − 1 dcd^{-1}c^{-1} d c d − 1 c − 1 belongs to Ker ( F ) \operatorname{Ker}(\mathcal{F}) Ker ( F ) as well. This commutator is trivial outside v v v , and at v v v it equals g c v g − 1 c v − 1 gc_{v}g^{-1}c_{v}^{-1} g c v g − 1 c v − 1 . By the previous paragraph, g c v g − 1 c v − 1 ∈ H gc_{v}g^{-1}c_{v}^{-1} \in H g c v g − 1 c v − 1 ∈ H for every g ∈ G g \in G g ∈ G ; in other words, the coset c v H c_{v}H c v H is central in G / H G/H G / H . As G / H G/H G / H is centerless, c v ∈ H c_{v} \in H c v ∈ H , and since v v v was arbitrary we conclude that c ∈ H Z D c \in H^{\mathbb{Z}^{D}} c ∈ H Z D .
The argument above works cell by cell, and therefore it does not depend on the dimension.
Recall that, by the Garden of Eden theorem of Moore and Myhill, a CA on Z D \mathbb{Z}^{D} Z D is surjective if and only if it is pre-injective. Together with Lemma 9, this yields the following characterization.
Lemma 10. Let F \mathcal{F} F be a D D D -GCA over a product of isomorphic non-abelian simple groups, with local rule f = ( h 1 , … , h k ) f = (h_{1}, \ldots, h_{k}) f = ( h 1 , … , h k ) . Then F \mathcal{F} F is surjective if and only if it is injective, if and only if Ker ( F ) = ( ⋂ j ∈ { 1 , … , k } Ker ( h j ) ) Z D \operatorname{Ker}(\mathcal{F}) = \left(\bigcap_{j \in\{1,\ldots,k\}} \operatorname{Ker}(h_{j})\right)^{\mathbb{Z}^{D}} Ker ( F ) = ( ⋂ j ∈ { 1 , … , k } Ker ( h j ) ) Z D is trivial.
Proof. Let H = ⋂ j Ker ( h j ) H = \bigcap_{j} \operatorname{Ker}(h_{j}) H = ⋂ j Ker ( h j ) . Assume first that H ≠ { e } H \ne\{e\} H = { e } and pick a ∈ H ∖ { e } a \in H \setminus\{e\} a ∈ H ∖ { e } . The finite configurations c ( 0 , a ) c^{(0,a)} c ( 0 , a ) and e Z D e^{\mathbb{Z}^{D}} e Z D are distinct and have the same image; thus F \mathcal{F} F is not injective and not even pre-injective, so that, by the Garden of Eden theorem, it is not surjective. Assume now that H = { e } H = \{e\} H = { e } . By Lemma 9 the kernel of F \mathcal{F} F is trivial, i.e., F \mathcal{F} F is injective; in particular it is pre-injective, and hence surjective by the Garden of Eden theorem.
Lemma 11. Let ( F , G ) (\mathcal{F}, G) ( F , G ) be irreducible, with G G G non-abelian. Then either F \mathcal{F} F is the constant map c ↦ e Z D c \mapsto e^{\mathbb{Z}^{D}} c ↦ e Z D , or F \mathcal{F} F is surjective.
Proof. Denote by f = ( h 1 , … , h k ) f = (h_{1}, \ldots, h_{k}) f = ( h 1 , … , h k ) the local rule of F \mathcal{F} F . By Subsection 6.1, G G G is a product of isomorphic non-abelian simple groups. The subgroup H = ⋂ j Ker ( h j ) H = \bigcap_{j} \operatorname{Ker}(h_{j}) H = ⋂ j Ker ( h j ) is normal and F ( H Z D ) = { e Z D } \mathcal{F}(H^{\mathbb{Z}^{D}}) = \{e^{\mathbb{Z}^{D}}\} F ( H Z D ) = { e Z D } , so H H H is F \mathcal{F} F -invariant and therefore H = G H = G H = G or H = { e } H = \{e\} H = { e } . If H = G H = G H = G , all the h j h_{j} h j are trivial and F \mathcal{F} F is constant. If H = { e } H = \{e\} H = { e } , then F \mathcal{F} F is surjective by Lemma 10.
From now on, F \mathcal{F} F denotes a surjective D-GCA over G = S 1 × ⋯ × S m G=S_1\times\cdots\times S_m G = S 1 × ⋯ × S m with local rule f = ( h 1 , … , h k ) f=(h_1,\ldots,h_k) f = ( h 1 , … , h k ) . Then f f f is surjective as well, since every element of G G G is the value at the origin of some configuration in the image of F \mathcal{F} F . As shown in [8 ] , the endomorphisms h i h_i h i then have the following structure, which only depends on f f f and not on the dimension.
(a) The images of the h i h_i h i are products of pairwise disjoint families of factors: there is a partition J 1 ∪ ⋯ ∪ J k J_1\cup\cdots\cup J_k J 1 ∪ ⋯ ∪ J k of { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } such that Im ( h i ) = ∏ t ∈ J i S t \operatorname{Im}(h_i)=\prod_{t\in J_i}S_t Im ( h i ) = ∏ t ∈ J i S t for every i i i .
(b) The kernels are products of factors as well: for every i i i there is a set I i ⊆ { 1 , … , m } I_i\subseteq\{1,\ldots,m\} I i ⊆ { 1 , … , m } with Ker ( h i ) = ∏ t ∈ I i S t \operatorname{Ker}(h_i)=\prod_{t\in I_i}S_t Ker ( h i ) = ∏ t ∈ I i S t and ∣ I i ∣ = m − r i |I_i|=m-r_i ∣ I i ∣ = m − r i , where r i : = ∣ J i ∣ r_i:=|J_i| r i := ∣ J i ∣ .
(c) For every t ∈ { 1 , … , m } t\in\{1,\ldots,m\} t ∈ { 1 , … , m } there is exactly one index i i i such that S t S_t S t is not a factor of Ker ( h i ) \operatorname{Ker}(h_i) Ker ( h i ) .
Consequently, every h i h_i h i restricts to an isomorphism from ∏ t ∉ I i S t \prod_{t\notin I_i}S_t ∏ t ∈ / I i S t onto ∏ t ∈ J i S t \prod_{t\in J_i}S_t ∏ t ∈ J i S t , both groups being isomorphic to S r i S^{r_i} S r i .
Definition 1. Let π f \pi_f π f be the permutation of the set of factors { S 1 , … , S m } \{S_1,\ldots,S_m\} { S 1 , … , S m } (equivalently, of the indices { 1 , … , m } \{1,\ldots,m\} { 1 , … , m } ) induced by the family of endomorphisms h 1 , … , h k h_1,\ldots,h_k h 1 , … , h k : the factor S t S_t S t is sent to the factor onto which it is mapped by the unique h i h_i h i acting non-trivially on it. We denote by o o o the order of π f \pi_f π f .
Fix i ∈ { 1 , … , m } i\in\{1,\ldots,m\} i ∈ { 1 , … , m } and follow the factor S i S_i S i along π f \pi_f π f . There is a unique h j h_j h j acting non-trivially on S i S_i S i , and it maps S i S_i S i onto a factor S i ( 1 ) S_{i^{(1)}} S i ( 1 ) ; there is a unique h j ( 1 ) h_{j_{(1)}} h j ( 1 ) acting non-trivially on S i ( 1 ) S_{i^{(1)}} S i ( 1 ) , and it maps S i ( 1 ) S_{i^{(1)}} S i ( 1 ) onto a factor S i ( 2 ) S_{i^{(2)}} S i ( 2 ) ; and so on. After o o o steps we are back to S i S_i S i , the last map being the restriction of h j ( o − 1 ) h_{j_{(o-1)}} h j ( o − 1 ) to S i ( o − 1 ) S_{i^{(o-1)}} S i ( o − 1 ) .
Definition 2. The automorphism h ^ i \hat{h}_i h ^ i of S i S_i S i is the composition
h ^ i : = h j ( o − 1 ) ∘ ⋯ ∘ h j ( 1 ) ∘ h j , \hat{h}_i:=h_{j_{(o-1)}}\circ\cdots\circ h_{j_{(1)}}\circ h_j, h ^ i := h j ( o − 1 ) ∘ ⋯ ∘ h j ( 1 ) ∘ h j , and o i o_i o i denotes its order in Aut ( S i ) \operatorname{Aut}(S_i) Aut ( S i ) , i.e., the least positive integer such that h ^ i \hat{h}_i h ^ i composed with itself o i o_i o i times is the identity of S i S_i S i .
Definition 3. Let G = S 1 × ⋯ × S m G=S_1\times\cdots\times S_m G = S 1 × ⋯ × S m be a product of finite, non-abelian, isomorphic simple groups, and let F \mathcal{F} F be a D-GCA over G G G . We say that G G G is minimal with respect to F \mathcal{F} F if { 1 , 2 , … , m } \{1,2,\ldots,m\} { 1 , 2 , … , m } cannot be split into two non-empty disjoint sets I I I and J J J such that both F ( ( ∏ i ∈ I S i ) Z D ) ⊆ ( ∏ i ∈ I S i ) Z D \mathcal{F}\left(\left(\prod_{i\in I}S_i\right)^{\mathbb{Z}^D}\right)\subseteq\left(\prod_{i\in I}S_i\right)^{\mathbb{Z}^D} F ( ( ∏ i ∈ I S i ) Z D ) ⊆ ( ∏ i ∈ I S i ) Z D and F ( ( ∏ i ∈ J S i ) Z D ) ⊆ ( ∏ i ∈ J S i ) Z D \mathcal{F}\left(\left(\prod_{i\in J}S_i\right)^{\mathbb{Z}^D}\right)\subseteq\left(\prod_{i\in J}S_i\right)^{\mathbb{Z}^D} F ( ( ∏ i ∈ J S i ) Z D ) ⊆ ( ∏ i ∈ J S i ) Z D .
For a surjective F \mathcal{F} F , minimality of G G G with respect to F \mathcal{F} F amounts to π f \pi_f π f being a single cycle.
Lemma 12. Let ( F , G ) (\mathcal{F},G) ( F , G ) be irreducible and let F \mathcal{F} F be surjective. Then G G G is minimal with respect to F \mathcal{F} F .
Proof. Using the same notations as above, every sub-product ∏ i ∈ I S i \prod_{i\in I}S_i ∏ i ∈ I S i is a normal subgroup of G G G ; by Lemma 11 it is F \mathcal{F} F -invariant only if I = ∅ I=\varnothing I = ∅ or I = { 1 , … , m } I=\{1,\ldots,m\} I = { 1 , … , m } , and G G G is minimal with respect to F \mathcal{F} F . Since F \mathcal{F} F is assumed to be surjective, only the second case is possible. □
Recall from Section 2 that, for w ∈ Z D w\in\mathbb{Z}^D w ∈ Z D , σ w \sigma^w σ w denotes the shift σ w ( c ) v = c v + w \sigma^w(c)_v=c_{v+w} σ w ( c ) v = c v + w .
Lemma 13. Let G = S 1 × ⋯ × S m G = S_1 \times\cdots\times S_m G = S 1 × ⋯ × S m be a product of finite, non-abelian, isomorphic simple groups, and let F \mathcal{F} F be a surjective D-GCA on G G G , with respect to which G G G is minimal, with local rule f = ( h 1 , … , h k ) f = (h_1,\ldots,h_k) f = ( h 1 , … , h k ) and neighborhood { v 1 , … , v k } \{v_1,\ldots,v_k\} { v 1 , … , v k } . With o o o , r 1 , … , r k r_1,\ldots,r_k r 1 , … , r k and o 1 , … , o m o_1,\ldots,o_m o 1 , … , o m as above, we have
F o lcm ( o 1 , … , o m ) = σ lcm ( o 1 , … , o m ) ∑ i r i v i . \mathcal{F}^{o\operatorname{lcm}(o_1,\ldots,o_m)} = \sigma^{\operatorname{lcm}(o_1,\ldots,o_m)}\sum_i r_i v_i. F o lcm ( o 1 , … , o m ) = σ lcm ( o 1 , … , o m ) i ∑ r i v i .
The proof of Lemma 9 in [8 ] applies without changes; we sketch it to make clear that the dimension plays no role. Since π f \pi_f π f is a single cycle, F o \mathcal{F}^o F o maps S t Z D S_t^{\mathbb{Z}^D} S t Z D into itself for every t t t : the S t S_t S t -component of F o ( c ) v \mathcal{F}^o(c)_v F o ( c ) v is obtained by composing the restrictions of the h i h_i h i along the cycle, and every h i h_i h i occurs exactly r i r_i r i times in this composition, since it acts non-trivially on exactly r i r_i r i factors. Hence the S t S_t S t -component of F o ( c ) v \mathcal{F}^o(c)_v F o ( c ) v is h ^ t \hat{h}_t h ^ t applied to the S t S_t S t -component of c v + β c_{v+\beta} c v + β , where β = ∑ i r i v i ∈ Z D \beta= \sum_i r_i v_i \in\mathbb{Z}^D β = ∑ i r i v i ∈ Z D does not depend on t t t . Iterating lcm ( o 1 , … , o m ) \operatorname{lcm}(o_1,\ldots,o_m) lcm ( o 1 , … , o m ) times turns every h ^ t \hat{h}_t h ^ t into the identity, and the claim follows.
Lemma 14. Let D ≥ 2 D \ge2 D ≥ 2 , let A A A be a finite alphabet with ∣ A ∣ ≥ 2 |A| \ge2 ∣ A ∣ ≥ 2 and let 0 ≠ w ∈ Z D 0 \ne w \in\mathbb{Z}^D 0 = w ∈ Z D . Then the shift σ w \sigma^w σ w on A Z D A^{\mathbb{Z}^D} A Z D has infinite topological entropy.
Proof. Let w 1 ≠ 0 w_1 \ne0 w 1 = 0 , say (the other cases are analogous), and let B n = [ − n , n ] D B_n = [-n,n]^D B n = [ − n , n ] D . The sequence ( σ j w ( c ) ∣ B n ) 0 ≤ j ≤ t (\sigma^{jw}(c)|_{B_n})_{0\le j\le t} ( σ j w ( c ) ∣ B n ) 0 ≤ j ≤ t is the restriction of c c c to U t = ⋃ j = 0 t ( B n + j w ) U_t = \bigcup_{j=0}^t(B_n + jw) U t = ⋃ j = 0 t ( B n + j w ) ; hence N σ w ( n , t ) = ∣ A ∣ ∣ U t ∣ N_{\sigma^w}(n,t) = |A|^{|U_t|} N σ w ( n , t ) = ∣ A ∣ ∣ U t ∣ in the notation of Proposition 3. Let F n = { z ∈ B n : z 1 = n } F_n = \{z \in B_n : z_1 = n\} F n = { z ∈ B n : z 1 = n } , a face of B n B_n B n with ( 2 n + 1 ) D − 1 (2n+1)^{D-1} ( 2 n + 1 ) D − 1 elements. The points z + j w z+jw z + j w , z ∈ F n z \in F_n z ∈ F n , 0 ≤ j ≤ t 0 \le j \le t 0 ≤ j ≤ t , belong to U t U_t U t and are pairwise distinct: if z + j w = z ′ + j ′ w z+jw = z' + j'w z + j w = z ′ + j ′ w with z , z ′ ∈ F n z,z' \in F_n z , z ′ ∈ F n , comparing the first coordinates gives ( j − j ′ ) w 1 = 0 (j-j')w_1 = 0 ( j − j ′ ) w 1 = 0 , hence j = j ′ j=j' j = j ′ and z = z ′ z=z' z = z ′ . Therefore ∣ U t ∣ ≥ ( t + 1 ) ( 2 n + 1 ) D − 1 |U_t| \ge(t+1)(2n+1)^{D-1} ∣ U t ∣ ≥ ( t + 1 ) ( 2 n + 1 ) D − 1 , and lim t 1 t log N σ w ( n , t ) ≥ ( 2 n + 1 ) D − 1 log ∣ A ∣ \lim_{t}\frac{1}{t}\log N_{\sigma^w}(n,t) \ge(2n+1)^{D-1}\log|A| lim t t 1 log N σ w ( n , t ) ≥ ( 2 n + 1 ) D − 1 log ∣ A ∣ . By Proposition 3, H ( σ w ) = + ∞ \mathcal{H}(\sigma^w) = +\infty H ( σ w ) = + ∞ .
Lemma 13 has the following consequences.
Theorem 7. Let G = S 1 × ⋯ × S m G = S_1 \times\cdots\times S_m G = S 1 × ⋯ × S m with S i ≅ S S_i \cong S S i ≅ S for every i i i , where S S S is a finite non-abelian simple group, and let F \mathcal{F} F be a surjective D-GCA on G G G , with respect to which G G G is minimal, with local rule f = ( h 1 , … , h k ) f = (h_1,\ldots,h_k) f = ( h 1 , … , h k ) and neighborhood { v 1 , … , v k } \{v_1,\ldots,v_k\} { v 1 , … , v k } . Let r 1 , … , r k r_1,\ldots,r_k r 1 , … , r k be as in Lemma 13 and β = ∑ i r i v i \beta= \sum_i r_i v_i β = ∑ i r i v i . Then:
(1) the following are equivalent: F \mathcal{F} F is sensitive to initial conditions; F \mathcal{F} F is topologically transitive; β ≠ 0 \beta\ne0 β = 0 ;
(2) the topological entropy of F \mathcal{F} F is
H ( F ) = { ∣ β ∣ log ∣ S ∣ if D = 1 , + ∞ if D > 1 and β ≠ 0 , 0 if D > 1 and β = 0. \mathcal{H}(\mathcal{F}) =
\begin{cases}
|\beta|\log|S| & \text{if } D=1,\\
+\infty& \text{if } D>1 \text{ and } \beta\ne0,\\
0 & \text{if } D>1 \text{ and } \beta=0.
\end{cases} H ( F ) = ⎩ ⎨ ⎧ ∣ β ∣ log ∣ S ∣ + ∞ 0 if D = 1 , if D > 1 and β = 0 , if D > 1 and β = 0.
Proof. Let L = lcm ( o 1 , … , o m ) L = \operatorname{lcm}(o_1,\ldots,o_m) L = lcm ( o 1 , … , o m ) , N = o L N = oL N = o L and s = L β s = L\beta s = L β , so that F N = σ s \mathcal{F}^N = \sigma^s F N = σ s by Lemma 13 .
(1) If β ≠ 0 \beta\ne0 β = 0 , then s ≠ 0 s \ne0 s = 0 , and the shift σ s \sigma^s σ s on G Z D G^{\mathbb{Z}^D} G Z D is sensitive to initial conditions and topologically transitive (indeed mixing). Since the iterates of F N \mathcal{F}^N F N are iterates of F \mathcal{F} F , sensitivity and transitivity of F N \mathcal{F}^N F N imply those of F \mathcal{F} F . If β = 0 \beta= 0 β = 0 , then F N \mathcal{F}^N F N is the identity; hence F \mathcal{F} F is equicontinuous by Proposition 2(i), so it is not sensitive, and it is not transitive: given x x x and y y y outside the finite orbit { x , F ( x ) , … , F N − 1 ( x ) } \{x,\mathcal{F}(x),\ldots,\mathcal{F}^{N-1}(x)\} { x , F ( x ) , … , F N − 1 ( x )} , by continuity there are open sets U ∋ x U \ni x U ∋ x and V ∋ y V \ni y V ∋ y with F j ( U ) ∩ V = ∅ \mathcal{F}^{j}(U) \cap V = \emptyset F j ( U ) ∩ V = ∅ for 0 ≤ j < N 0 \le j < N 0 ≤ j < N , hence for every j ≥ 0 j \ge0 j ≥ 0 .
(2) If β = 0 \beta= 0 β = 0 , then F N \mathcal{F}^{N} F N is the identity and H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 . Let β ≠ 0 \beta\ne0 β = 0 . By fact (a) of § 3 , H ( F ) = H ( σ s ) / N \mathcal{H}(\mathcal{F}) = \mathcal{H}(\sigma^{s})/N H ( F ) = H ( σ s ) / N . If D > 1 D > 1 D > 1 , then H ( σ s ) = + ∞ \mathcal{H}(\sigma^{s}) = +\infty H ( σ s ) = + ∞ by Lemma 14. If D = 1 D = 1 D = 1 , then H ( σ s ) = ∣ s ∣ log ∣ G ∣ \mathcal{H}(\sigma^{s}) = |s| \log|G| H ( σ s ) = ∣ s ∣ log ∣ G ∣ , whence
H ( F ) = ∣ s ∣ log ∣ G ∣ N = ∣ β ∣ log ∣ G ∣ o = ∣ β ∣ log ∣ S ∣ . \mathcal{H}(\mathcal{F}) = \frac{|s| \log|G|}{N} = \frac{|\beta| \log|G|}{o} = |\beta| \log|S|. H ( F ) = N ∣ s ∣ log ∣ G ∣ = o ∣ β ∣ log ∣ G ∣ = ∣ β ∣ log ∣ S ∣.
since o = m o = m o = m , the permutation π f \pi_f π f being a single cycle on the m m m factors, and ∣ G ∣ = ∣ S ∣ m |G| = |S|^m ∣ G ∣ = ∣ S ∣ m . Note that the value of L L L plays no role.
Proof of Theorem 6
Let F \mathcal{F} F be a D D D -GCA, D ≥ 2 D \ge2 D ≥ 2 . If F \mathcal{F} F is equicontinuous, then H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 by Proposition 1. Otherwise F \mathcal{F} F is sensitive to initial conditions by Proposition 2. Let { ( F 1 , G 1 ) , … , ( F k , G k ) } \{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_k,G_k)\} {( F 1 , G 1 ) , … , ( F k , G k )} be the output of Decomposition on ( F , G ) (\mathcal{F},G) ( F , G ) . By Corollary 3(1), some F i \mathcal{F}_i F i is sensitive, and by Corollary 3(2) it suffices to prove that H ( F i ) = + ∞ \mathcal{H}(\mathcal{F}_i) = +\infty H ( F i ) = + ∞ . If G i ≅ ( Z / p Z ) n G_i \cong(\mathbb{Z}/p\mathbb{Z})^n G i ≅ ( Z / p Z ) n , this follows from Corollary 2. Otherwise, by Lemma 11, F i \mathcal{F}_i F i is not constant, since it is sensitive; hence it is surjective and G i G_i G i is minimal with respect to F i \mathcal{F}_i F i , and H ( F i ) = + ∞ \mathcal{H}(\mathcal{F}_i) = +\infty H ( F i ) = + ∞ by Theorem 7.
Corollary 4. For every D ≥ 1 D \ge1 D ≥ 1 there is an algorithm which, given a finite group G G G by its multiplication table and the local rule of a D D D -GCA F \mathcal{F} F on G G G , computes H ( F ) ∈ [ 0 , + ∞ ] \mathcal{H}(\mathcal{F}) \in[0,+\infty] H ( F ) ∈ [ 0 , + ∞ ] .
Proof. For D = 1 D = 1 D = 1 this is Theorem 3. For D ≥ 2 D \ge2 D ≥ 2 , by Theorem 6 we have H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 if F \mathcal{F} F is equicontinuous and H ( F ) = + ∞ \mathcal{H}(\mathcal{F}) = +\infty H ( F ) = + ∞ otherwise, and equicontinuity of group cellular automata is decidable in every dimension [4 Theorem 27] .
For D ≥ 2 D \ge2 D ≥ 2 , the decomposition of Subsection 6.1 also gives a direct decision procedure, which does not rely on [4 ] : H ( F ) = + ∞ \mathcal{H}(\mathcal{F}) = +\infty H ( F ) = + ∞ if and only if some irreducible component of F \mathcal{F} F is either abelian with a non-constant coefficient in its characteristic polynomial, or non-abelian, non-constant and with β ≠ 0 \beta\ne0 β = 0 (see § 7 ).
Computational complexity
In this section we make the procedures of Remark 2 and Corollary 4 explicit and bound their cost.
Input. The group G G G , of order N N N , is given by its multiplication table, and the local rule f = ( h 1 , … , h k ) f = (h_1,\ldots,h_k) f = ( h 1 , … , h k ) of F \mathcal{F} F by the k k k lookup tables of the endomorphisms h j h_j h j together with the neighborhood V f = { v 1 , … , v k } ⊆ Z D V_f = \{v_1,\ldots,v_k\} \subseteq\mathbb{Z}^{D} V f = { v 1 , … , v k } ⊆ Z D . The size of the input is Θ ( N 2 + k N + k D ) \Theta(N^2+kN+kD) Θ ( N 2 + k N + k D ) . We let ϱ = max j ∥ v j ∥ ∞ \varrho= \max_j \|v_j\|_\infty ϱ = max j ∥ v j ∥ ∞ , and we assume that the group operation, the maps h j h_j h j , arithmetic in F p \mathbb{F}_p F p and additions of integers cost O ( 1 ) O(1) O ( 1 ) .
The algorithm. The procedure Entropy first calls Decomposition (Subsection 6.1), and then processes each irreducible pair ( F i , G i ) (\mathcal{F}_i,G_i) ( F i , G i ) of its output: (A) if G i G_i G i is abelian, it computes an isomorphism G i ≅ F p n G_i \cong\mathbb{F}_p^n G i ≅ F p n , the matrix M i = M F i M_i = M_{F_i} M i = M F i and its characteristic polynomial χ M i \chi_{M_i} χ M i ; for D = 1 D = 1 D = 1 it records the pair ( p , E M i + − E M i − ) (p, E_{M_i}^{+} - E_{M_i}^{-}) ( p , E M i + − E M i − ) , and for D ≥ 2 D \ge2 D ≥ 2 it marks F i F_i F i as sensitive if some coefficient of χ M i \chi_{M_i} χ M i is not constant;
(N) if G i G_i G i is non-abelian, it checks whether all the endomorphisms of the local rule of F i F_i F i are trivial; if not, it computes ∣ S ∣ \lvert S\rvert ∣ S ∣ , where G i ≅ S m G_i \cong S^m G i ≅ S m , the integers r j r_j r j defined by ∣ Im ( h j ) ∣ = ∣ S ∣ r j \lvert\operatorname{Im}(h_j)\rvert= \lvert S\rvert^{r_j} ∣ Im ( h j )∣ = ∣ S ∣ r j , and β = ∑ j r j v j \beta= \sum_j r_j v_j β = ∑ j r j v j ; for D = 1 D = 1 D = 1 it records the pair ( ∣ S ∣ , ∣ β ∣ ) (\lvert S\rvert,\lvert\beta\rvert) (∣ S ∣ , ∣ β ∣) , and for D ≥ 2 D \ge2 D ≥ 2 it marks F i F_i F i as sensitive if β ≠ 0 \beta\ne0 β = 0 .
For D = 1 D = 1 D = 1 the output is H ( F ) = ∑ a log b \mathcal{H}(\mathcal{F}) = \sum a\log b H ( F ) = ∑ a log b , the sum ranging over the recorded pairs ( b , a ) (b,a) ( b , a ) . For D ≥ 2 D \ge2 D ≥ 2 the output is + ∞ +\infty + ∞ if some F i F_i F i is marked, and 0 0 0 otherwise.
Correctness. Let D = 1 D = 1 D = 1 . By Corollary 3(2), H ( F ) = ∑ i H ( F i ) \mathcal{H}(\mathcal{F}) = \sum_i \mathcal{H}(F_i) H ( F ) = ∑ i H ( F i ) . In case (A), H ( F i ) = ( E M i + − E M i − ) log p \mathcal{H}(F_i) = (E_{M_i}^{+} - E_{M_i}^{-})\log p H ( F i ) = ( E M i + − E M i − ) log p by Theorem 4(1). In case (N), by Lemmata 11 and 12 either F i F_i F i is constant, and H ( F i ) = 0 \mathcal{H}(F_i) = 0 H ( F i ) = 0 , or F i F_i F i is surjective and G i G_i G i is minimal with respect to F i F_i F i . In the latter case Im ( h j ) = ∏ t ∈ J j S t \operatorname{Im}(h_j) = \prod_{t\in J_j} S_t Im ( h j ) = ∏ t ∈ J j S t by fact (a) of Subsection 6.3, so that r j = ∣ J j ∣ r_j = \lvert J_j\rvert r j = ∣ J j ∣ , and H ( F i ) = ∣ β ∣ log ∣ S ∣ \mathcal{H}(F_i) = \lvert\beta\rvert\log\lvert S\rvert H ( F i ) = ∣ β ∣ log ∣ S ∣ by Theorem 7(2).
Let D ≥ 2 D \ge2 D ≥ 2 . By Theorem 6, H ( F ) = + ∞ \mathcal{H}(\mathcal{F}) = +\infty H ( F ) = + ∞ if F \mathcal{F} F is sensitive and H ( F ) = 0 \mathcal{H}(\mathcal{F}) = 0 H ( F ) = 0 otherwise. By Corollary 3(1), F \mathcal{F} F is sensitive if and only if some F i F_i F i is. In case (A), F i F_i F i is sensitive if and only if some coefficient of χ M i \chi_{M_i} χ M i is not constant, by Theorem 4(3) and Proposition 2(ii). In case (N), a constant F i F_i F i is equicontinuous; otherwise, by Lemma 11 and Theorem 7(1), F i F_i F i is sensitive if and only if β ≠ 0 \beta\ne0 β = 0 .
Auxiliary results
Lemma 15. Let G G G be a finite group of order M M M , given by its multiplication table, and let φ 1 , … , φ s \varphi_1,\ldots,\varphi_s φ 1 , … , φ s be endomorphisms of G G G , given by their tables. One can find a normal subgroup { e } ≠ H ≠ G \{e\} \ne H \ne G { e } = H = G with φ i ( H ) ⊆ H \varphi_i(H) \subseteq H φ i ( H ) ⊆ H for every i i i , or decide that no such subgroup exists, in O ( M 3 + s M 2 ) O(M^3+sM^2) O ( M 3 + s M 2 ) operations. With s = 0 s=0 s = 0 , the same procedure computes the normal closures of all the elements of G G G within the same bound.
Proof. The identity and the table of inverses are computed in O ( M 2 ) O(M^2) O ( M 2 ) operations. For a ∈ G a \in G a ∈ G , let Cl ( a ) \operatorname{Cl}(a) Cl ( a ) be the smallest normal subgroup of G G G that contains a a a and is invariant under φ 1 , … , φ s \varphi_1,\ldots,\varphi_s φ 1 , … , φ s . It is computed by a breadth-first closure: starting from H = { a } H=\{a\} H = { a } , every element x x x added to H H H is processed once, and for each such x x x one adds to H H H the elements x − 1 x^{-1} x − 1 , x y xy x y and y x yx y x for all current y ∈ H y\in H y ∈ H , g − 1 x g g^{-1}xg g − 1 xg for all g ∈ G g\in G g ∈ G , and φ i ( x ) \varphi_i(x) φ i ( x ) for all i i i . When an element y y y enters H H H after x x x , the products x y xy x y and y x yx y x are added when y y y is processed; hence the result is closed under products, inverses, conjugation and the maps φ i \varphi_i φ i , and it is the smallest such set containing a a a . Each element is processed at most once, at a cost of O ( M + s ) O(M+s) O ( M + s ) , so that one closure costs O ( M 2 + s M ) O(M^2+sM) O ( M 2 + s M ) . The algorithm computes Cl ( a ) \operatorname{Cl}(a) Cl ( a ) for every a ≠ e a\ne e a = e and returns the first one different from G G G . This is correct: if K K K is a subgroup with the required properties and a ∈ K ∖ { e } a\in K\setminus\{e\} a ∈ K ∖ { e } , then Cl ( a ) ⊆ K ≠ G \operatorname{Cl}(a)\subseteq K\ne G Cl ( a ) ⊆ K = G . The total cost is O ( M 3 + s M 2 ) O(M^3+sM^2) O ( M 3 + s M 2 ) .
:::
Lemma 16. Let G ≅ F p n G\cong\mathbb{F}_p^n G ≅ F p n be given by its multiplication table, with M = ∣ G ∣ = p n M=\lvert G\rvert=p^n M = ∣ G ∣ = p n , and let h 1 , … , h k h_1,\ldots,h_k h 1 , … , h k be endomorphisms of G G G , given by their tables. One can compute p p p , a basis g 1 , … , g n g_1,\ldots,g_n g 1 , … , g n of G G G over F p \mathbb{F}_p F p , a table of the coordinates of all the elements of G G G in this basis, and the matrices A 1 , … , A k ∈ M n ( F p ) A_1,\ldots,A_k\in M_n(\mathbb{F}_p) A 1 , … , A k ∈ M n ( F p ) of h 1 , … , h k h_1,\ldots,h_k h 1 , … , h k , in O ( M log M + k M ) O(M\log M+kM) O ( M log M + k M ) operations.
Proof. The prime p p p is the order of any element g ≠ e g \ne e g = e , computed in O ( p ) ⊆ O ( M ) O(p) \subseteq O(M) O ( p ) ⊆ O ( M ) operations. Let V 0 = { e } V_0 = \{e\} V 0 = { e } . Given the span V i V_i V i of g 1 , … , g i g_1,\ldots,g_i g 1 , … , g i , together with the coordinates of its elements, choose g i + 1 ∉ V i g_{i+1} \notin V_i g i + 1 ∈ / V i by scanning G G G with a membership array. Then V i + 1 = ⋃ a ∈ F p g i + 1 a V i V_{i+1} = \bigcup_{a\in\mathbb{F}_p} g_{i+1}^{a}V_i V i + 1 = ⋃ a ∈ F p g i + 1 a V i , and the coordinates of its elements are obtained from those of V i V_i V i , in O ( n ∣ V i + 1 ∣ + M ) O(n|V_{i+1}|+M) O ( n ∣ V i + 1 ∣ + M ) operations. Since ∣ V i + 1 ∣ = p i + 1 |V_{i+1}|=p^{i+1} ∣ V i + 1 ∣ = p i + 1 and n ≤ log 2 M n\le\log_2 M n ≤ log 2 M , the whole construction costs O ( n M ) = O ( M log M ) O(nM)=O(M\log M) O ( n M ) = O ( M log M ) . The j j j -th column of A l A_l A l is the coordinate vector of h l ( g j ) h_l(g_j) h l ( g j ) , read from the tables in O ( n ) O(n) O ( n ) operations. Reading the k k k tables costs O ( k M ) O(kM) O ( k M ) , which dominates the O ( k n 2 ) O(kn^2) O ( k n 2 ) operations needed to fill the matrices. □ \square □
Size of the recursion tree. Let λ ( G ) \lambda(G) λ ( G ) be the composition length of G G G , i.e., the length of any composition series of G G G (see [25 p. 108] ). By the Jordan–Hölder theorem, λ ( G ) = λ ( H ) + λ ( G / H ) \lambda(G)=\lambda(H)+\lambda(G/H) λ ( G ) = λ ( H ) + λ ( G / H ) for every normal subgroup H H H (see [25 p. 111] ). Every leaf of the recursion tree of Decomposition carries a non-trivial group, which has composition length at least 1. Hence the tree has at most λ ( G ) ≤ log 2 N \lambda(G)\le\log_2 N λ ( G ) ≤ log 2 N leaves, and, every internal node having two children, at most 2 log 2 N 2\log_2 N 2 log 2 N nodes. Moreover, since ∣ G ∣ = ∣ H ∣ ∣ G / H ∣ |G|=|H||G/H| ∣ G ∣ = ∣ H ∣∣ G / H ∣ , the orders of the groups attached to the nodes at a fixed depth multiply to at most N N N , and the orders M 1 , … , M q M_1,\ldots,M_q M 1 , … , M q of the groups at the leaves multiply to exactly N N N . Since each child has order at most half the order of its parent, the depth of the tree is at most log 2 N \log_2 N log 2 N .
Cost at a node. Consider a node with a group of order M M M . Deciding irreducibility, and finding H H H if the node is internal, costs O ( M 3 + k M 2 ) O(M^3+kM^2) O ( M 3 + k M 2 ) by Lemma 15 with φ j = h j \varphi_j=h_j φ j = h j ; recall from Subsection 6.1 that H H H is F \mathcal{F} F -invariant if and only if h j ( H ) ⊆ H h_j(H)\subseteq H h j ( H ) ⊆ H for every j j j . At an internal node one also builds the multiplication tables of H H H and G / H G/H G / H , in O ( M 2 ) O(M^2) O ( M 2 ) operations, and the tables of the restrictions h j ∣ H h_j|_H h j ∣ H and of the induced endomorphisms [ g ] ↦ [ h j ( g ) ] [g]\mapsto[h_j(g)] [ g ] ↦ [ h j ( g )] of G / H G/H G / H , in O ( k M ) O(kM) O ( k M ) operations. The neighborhood does not change. Since x ↦ x 3 x\mapsto x^3 x ↦ x 3 is superadditive on positive integers, the sum of M 3 + k M 2 M^3+kM^2 M 3 + k M 2 over the nodes at a fixed depth is at most N 3 + k N 2 N^3+kN^2 N 3 + k N 2 . Hence all nodes together cost
O ( ( N 3 + k N 2 ) log N ) . O\bigl((N^3+kN^2)\log N\bigr). O ( ( N 3 + k N 2 ) log N ) .
Cost at a leaf. Let ( F i , G i ) (\mathcal{F}_i,G_i) ( F i , G i ) be a leaf, with M = ∣ G i ∣ M=|G_i| M = ∣ G i ∣ . Testing whether G i G_i G i is abelian costs O ( M 2 ) O(M^2) O ( M 2 ) operations.
Case (A). Let G i ≅ F p n G_i\cong\mathbb{F}_p^n G i ≅ F p n , so that n = log p M ≤ log 2 M n=\log_p M\le\log_2 M n = log p M ≤ log 2 M . By Lemma 16, the matrices of the h j h_j h j are obtained in O ( M log M + k M ) O(M\log M+kM) O ( M log M + k M ) operations, and M i = ∑ j A j x − v j M_i=\sum_j A_jx^{-v_j} M i = ∑ j A j x − v j in O ( k n 2 D ) O(kn^2D) O ( k n 2 D ) operations. We compute χ M i \chi_{M_i} χ M i with Berkowitz’s division-free algorithm [5 ] , which uses O ( n 4 ) O(n^4) O ( n 4 ) ring operations. All intermediate quantities are polynomials of degree at most n n n in the entries of M i M_i M i . They are therefore Laurent polynomials with exponents in [ − n ϱ , n ϱ ] D [-n\varrho,n\varrho]^D [ − n ϱ , n ϱ ] D , hence with at most ( 2 n ϱ + 1 ) D (2n\varrho+1)^D ( 2 n ϱ + 1 ) D monomials, and each ring operation costs O ( D ( 2 n ϱ + 1 ) 2 D ) O(D(2n\varrho+1)^{2D}) O ( D ( 2 n ϱ + 1 ) 2 D ) . Reading off E M i ± E_{M_i}^{\pm} E M i ± , or testing whether the coefficients are constant, is cheaper. The cost of case (A) is
O ( M log M + k M + k n 2 D + D n 4 ( 2 n ϱ + 1 ) 2 D ) . O\bigl(M\log M+kM+kn^2D+Dn^4(2n\varrho+1)^{2D}\bigr). O ( M log M + k M + k n 2 D + D n 4 ( 2 n ϱ + 1 ) 2 D ) .
Case (N). Testing whether all the h j h_j h j are trivial costs O ( k M ) O(kM) O ( k M ) . For a ≠ e a\ne e a = e , the normal closure of a a a in G i ≅ S m G_i\cong S^m G i ≅ S m is the product of the factors in which a a a has a non-trivial coordinate. Hence ∣ S ∣ |S| ∣ S ∣ is the smallest order of the normal closure of an element a ≠ e a \ne e a = e , computed in O ( M 3 ) O(M^3) O ( M 3 ) operations by Lemma 15 with s = 0 s = 0 s = 0 . The orders ∣ Im ( h j ) ∣ |\operatorname{Im}(h_j)| ∣ Im ( h j ) ∣ , and hence the r j r_j r j , cost O ( k M ) O(kM) O ( k M ) , and β \beta β costs O ( k D ) O(kD) O ( k D ) . The cost of case (N) is O ( M 3 + k M + k D ) O(M^3 + kM + kD) O ( M 3 + k M + k D ) .
Overall complexity. Recall that the leaf orders M 1 , … , M q M_1,\ldots,M_q M 1 , … , M q satisfy ∏ i M i = N \prod_i M_i = N ∏ i M i = N and M i ≥ 2 M_i \ge2 M i ≥ 2 ; hence ∑ i M i 3 ≤ N 3 \sum_i M_i^3 \le N^3 ∑ i M i 3 ≤ N 3 and ∑ i M i log M i ≤ N log N \sum_i M_i \log M_i \le N \log N ∑ i M i log M i ≤ N log N . Moreover, the exponents n i n_i n i of the abelian leaves satisfy ∑ i n i ≤ log 2 N \sum_i n_i \le\log_2 N ∑ i n i ≤ log 2 N , so that
∑ i n i 4 ( 2 n i ϱ + 1 ) 2 D ≤ ( log 2 N ) 4 ( 2 ϱ log 2 N + 1 ) 2 D . \sum_i n_i^4(2n_i\varrho+ 1)^{2D} \le(\log_2 N)^4(2\varrho\log_2 N + 1)^{2D}. i ∑ n i 4 ( 2 n i ϱ + 1 ) 2 D ≤ ( log 2 N ) 4 ( 2 ϱ log 2 N + 1 ) 2 D .
Adding the costs of the nodes and of the leaves, we obtain the following result.
Theorem 8. The procedure Entropy computes the topological entropy of a D D D -GCA F \mathcal{F} F on a group of order N N N , with k k k neighbors and ϱ = max v ∈ V f ∥ v ∥ ∞ \varrho= \max_{v\in V_f} \|v\|_\infty ϱ = max v ∈ V f ∥ v ∥ ∞ , in
O ( ( N 3 + k N 2 + k D ) log N + D ( log N ) 4 ( 2 ϱ log 2 N + 1 ) 2 D ) . O\left((N^3 + kN^2 + kD)\log N + D(\log N)^4(2\varrho\log_2 N + 1)^{2D}\right). O ( ( N 3 + k N 2 + k D ) log N + D ( log N ) 4 ( 2 ϱ log 2 N + 1 ) 2 D ) . operations. In particular, for every fixed D D D the running time is polynomial in N N N , k k k and ϱ \varrho ϱ . For D = 1 D = 1 D = 1 it is
O ( ( N 3 + k N 2 ) log N + ϱ 2 ( log N ) 6 ) . O\left((N^3 + kN^2)\log N + \varrho^2(\log N)^6\right). O ( ( N 3 + k N 2 ) log N + ϱ 2 ( log N ) 6 ) .
Tables
Conclusions and Further Work
In this paper we investigate the problem of computing topological entropy for cellular automata, emphasizing the role of algebraic structure on the alphabet and on the local rule. While topological entropy is known to be algorithmically intractable for general cellular automata over arbitrary finite alphabets and local rules, we show that this negative picture changes substantially when the alphabet is endowed with a group structure and the local rule is a group homomorphism.
Our main result proves that the topological entropy of group cellular automata is computable in every dimension. This extends earlier computability results for linear cellular automata over rings of the form Z / m Z \mathbb{Z}/m\mathbb{Z} Z / m Z , obtained in [10 ] , to the much broader class of cellular automata defined over arbitrary finite groups. The key ingredient is a structural decomposition of space-time behavior into independent left and right contributions, which allows the entropy to be recovered from the growth rate of fixed width space-time patterns. As a consequence, the entropy computation can be reduced to an effective procedure, in sharp contrast with the general incomputability results known for unrestricted cellular automata. Moreover, via Pontryagin duality and the Bridge Theorem, we obtained an explicit formula for linear cellular automata over ( Z / p Z ) n (\mathbb{Z}/p\mathbb{Z})^n ( Z / p Z ) n , in terms of the characteristic polynomial of the associated matrix. We also showed that the resulting procedure runs in polynomial time in the size of the group, the number of neighbors and the radius, for every fixed dimension (Theorem 8).
Table 1. Topological entropy of one-dimensional CAs over algebraic alphabets: exact formulas and computability.
Table 2. Topological entropy of D D D -dimensional CAs over algebraic alphabets, D > 1 D > 1 D > 1 .
Beyond the specific result on computability, our work highlights how algebraic constraints on the alphabet and on the local rule can dramatically simplify the dynamical complexity of cellular automata and restore algorithmic tractability of fundamental invariants. This contributes to a finer understanding of the boundary between computability and incomputability phenomena in symbolic and cellular dynamics.
Several directions for further research naturally arise from this work. A first question concerns the extension of our techniques beyond groups. We conjecture that the same approach can be adapted to cellular automata defined over finite monoids, leading again to decidability results for topological entropy. On the other hand, for more general algebraic structures such as semigroups, strong incomputability results are already known, suggesting that the group and monoid cases represent a genuine frontier between tractable and intractable settings.
A second direction concerns higher-dimensional cellular automata. For group cellular automata in dimension D ≥ 2 D \ge2 D ≥ 2 we proved that either the automaton is equicontinuous and has zero topological entropy, or it is sensitive to initial conditions and has infinite topological entropy (Theorem 6). This answers, in the setting of full shifts, the algebraic version of Shereshevsky’s question formulated in [34 ] . For general cellular automata no such dichotomy holds, since in every dimension D ≥ 2 D \ge2 D ≥ 2 there exist cellular automata with finite positive entropy [33 ] . It would be interesting to understand whether the dichotomy extends to cellular automata over finite monoids, and more generally which algebraic constraints force it.
Finally, it would be interesting to investigate whether the techniques introduced here can be applied to other quantitative invariants of cellular automata. In particular, a natural question is whether the decomposition of space-time behavior developed in this paper can be exploited to compute or better understand Lyapunov exponents for group cellular automata, providing a unified framework for the effective analysis of different indicators of dynamical instability.
We believe that these directions offer promising avenues for further research and that the approach developed in this work may prove useful beyond the specific problem of topological entropy, contributing more broadly to the study of algebraic cellular automata and their dynamical properties.
A proof of Theorem 4(2)–(3) without Pontryagin duality
In this appendix we prove parts (2) and (3) of Theorem 4 without using Pontryagin duality and the Bridge Theorem: we only use the one-dimensional results of § 4 and elementary algebra. The idea is to bound from below the entropy of a D D D -GCA by the entropy of its restriction to spatially periodic configurations. Such a restriction is a one-dimensional GCA over a larger alphabet, which splits into many independent one-dimensional linear CAs, each contributing at least log p \log p log p to the entropy unless it is equicontinuous. Part (1) of Theorem 4, i.e., the exact value of the entropy in dimension one, is not recovered by this argument.
In this appendix the dimension D ≥ 1 D \ge1 D ≥ 1 is arbitrary, except in the statements explicitly concerning one-dimensional GCAs. For a finite field E \mathbb{E} E of characteristic p p p we consider linear CAs on ( E n ) Z D (\mathbb{E}^{n})^{\mathbb{Z}^{D}} ( E n ) Z D defined as in § 5 with E \mathbb{E} E in place of F p \mathbb{F}_{p} F p : F ( c ) = ∑ u A u c v + u \mathcal{F}(c)=\sum_{u} A_{u}c_{v+u} F ( c ) = ∑ u A u c v + u with A u ∈ M n ( E ) A_{u}\in M_{n}(\mathbb{E}) A u ∈ M n ( E ) , with associated matrix M F = ∑ u A u x − u ∈ M n ( E [ x 1 ± 1 , … , x D ± 1 ] ) M_{\mathcal{F}}=\sum_{u} A_{u}x^{-u}\in M_{n}(\mathbb{E}[x_{1}^{\pm1},\ldots,x_{D}^{\pm1}]) M F = ∑ u A u x − u ∈ M n ( E [ x 1 ± 1 , … , x D ± 1 ]) . They are D D D -GCAs on the elementary abelian p p p -group E n \mathbb{E}^{n} E n . As in § 5 , M F k = M F k M_{\mathcal{F}^{k}}=M_{\mathcal{F}}^{k} M F k = M F k , and F \mathcal{F} F is determined by M F M_{\mathcal{F}} M F and vice versa.
Lemma 17. Let F \mathcal{F} F be a one-dimensional GCA on a finite group G G G . If H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 , then F \mathcal{F} F is equicontinuous.
Proof. Write l = l F l=l_{\mathcal{F}} l = l F and r = r F r=r_{\mathcal{F}} r = r F . By Corollary 1, N ∞ − N^{-}_{\infty} N ∞ − and N ∞ + N^{+}_{\infty} N ∞ + are trivial, so that, by Proposition 4, N t − N^{-}_{t} N t − and N t + N^{+}_{t} N t + are trivial for every t ≥ t 0 t \ge t_{0} t ≥ t 0 .
Step 1. Let U ∈ L U \in\mathcal{L} U ∈ L be such that F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l + 1 , 0 ] [-l+1,0] [ − l + 1 , 0 ] for 0 ≤ j ≤ t 0 0 \le j \le t_{0} 0 ≤ j ≤ t 0 . Then F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l + 1 , 0 ] [-l+1,0] [ − l + 1 , 0 ] for every j ≥ 0 j \ge0 j ≥ 0 : if this holds for j ≤ t j \le t j ≤ t with t ≥ t 0 t \ge t_{0} t ≥ t 0 , then F t + 1 ( U ) [ − l + 1 , 0 ] ∈ N t − = { e } \mathcal{F}^{t+1}(U)_{[-l+1,0]} \in N_t^{-} = \{e\} F t + 1 ( U ) [ − l + 1 , 0 ] ∈ N t − = { e } . By Lemma 1(i), F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ − l + 1 , + ∞ ) [-l+1,+\infty) [ − l + 1 , + ∞ ) for every j ≥ 0 j \ge0 j ≥ 0 . Symmetrically, if U ∈ R U \in R U ∈ R and F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ 0 , r − 1 ] [0,r-1] [ 0 , r − 1 ] for 0 ≤ j ≤ t 0 0 \le j \le t_0 0 ≤ j ≤ t 0 , then F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on ( − ∞ , r − 1 ] (-\infty,r-1] ( − ∞ , r − 1 ] for every j ≥ 0 j \ge0 j ≥ 0 .
Step 2. Let K = ( t 0 + 1 ) l K=(t_0+1)l K = ( t 0 + 1 ) l and K ′ = ( t 0 + 1 ) r K'=(t_0+1)r K ′ = ( t 0 + 1 ) r . Since F ( c ) i \mathcal{F}(c)_i F ( c ) i only depends on c [ i − l , i + r ] c_{[i-l,i+r]} c [ i − l , i + r ] , if U U U is trivial on ( − K , + ∞ ) (-K,+\infty) ( − K , + ∞ ) then F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on ( − K + j l , + ∞ ) (-K+jl,+\infty) ( − K + j l , + ∞ ) , and in particular on [ − l + 1 , 0 ] [-l+1,0] [ − l + 1 , 0 ] for j ≤ t 0 j \le t_0 j ≤ t 0 . By Step 1 and shift-commutation, for every a ∈ Z a \in\mathbb{Z} a ∈ Z : if U U U is trivial on ( a − K , + ∞ ) (a-K,+\infty) ( a − K , + ∞ ) , then every F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on [ a − l + 1 , + ∞ ) [a-l+1,+\infty) [ a − l + 1 , + ∞ ) . Symmetrically, if U U U is trivial on ( − ∞ , a + K ′ ) (-\infty,a+K') ( − ∞ , a + K ′ ) , then every F j ( U ) \mathcal{F}^{j}(U) F j ( U ) is trivial on ( − ∞ , a + r − 1 ] (-\infty,a+r-1] ( − ∞ , a + r − 1 ] .
Step 3. Let m ≥ 0 m \ge0 m ≥ 0 and let c , c ′ ∈ G Z c,c' \in G^{\mathbb{Z}} c , c ′ ∈ G Z coincide on [ − m − K , m + K ′ ] [-m-K,m+K'] [ − m − K , m + K ′ ] . Then U = c − 1 c ′ = U L U R U=c^{-1}c'=U_LU_R U = c − 1 c ′ = U L U R , where U L U_L U L is trivial on ( − m − K − 1 , + ∞ ) (-m-K-1,+\infty) ( − m − K − 1 , + ∞ ) and U R U_R U R is trivial on ( − ∞ , m + K ′ + 1 ) (-\infty,m+K'+1) ( − ∞ , m + K ′ + 1 ) . By Step 2 with a = − m + l − 1 a=-m+l-1 a = − m + l − 1 (note that − m − K − 1 ≤ a − K -m-K-1 \le a-K − m − K − 1 ≤ a − K ) and with a = m + 1 a=m+1 a = m + 1 , every F j ( U L ) \mathcal{F}^{j}(U_L) F j ( U L ) is trivial on [ − m , + ∞ ) [-m,+\infty) [ − m , + ∞ ) and every F j ( U R ) \mathcal{F}^{j}(U_R) F j ( U R ) is trivial on ( − ∞ , m + r ] (-\infty,m+r] ( − ∞ , m + r ] . Hence F j ( c ′ ) = F j ( c ) F j ( U L ) F j ( U R ) \mathcal{F}^{j}(c')=\mathcal{F}^{j}(c)\mathcal{F}^{j}(U_L)\mathcal{F}^{j}(U_R) F j ( c ′ ) = F j ( c ) F j ( U L ) F j ( U R ) coincides with F j ( c ) \mathcal{F}^{j}(c) F j ( c ) on [ − m , m ] [-m,m] [ − m , m ] for every j ≥ 0 j \ge0 j ≥ 0 , and F \mathcal{F} F is equicontinuous.
Corollary 5. Let F \mathcal{F} F be a one-dimensional GCA on a finite non-trivial group G G G , and let ϖ \varpi ϖ be the smallest prime divisor of ∣ G ∣ |G| ∣ G ∣ . Then either F \mathcal{F} F is equicontinuous and H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 , or F \mathcal{F} F is sensitive to initial conditions and H ( F ) ≥ log ϖ \mathcal{H}(\mathcal{F}) \ge\log\varpi H ( F ) ≥ log ϖ .
Proof. By Propositions 1 and 2 and Lemma 17, F \mathcal{F} F is equicontinuous if and only if H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 , and otherwise it is sensitive. By Corollary 1, H ( F ) = log k \mathcal{H}(\mathcal{F})=\log k H ( F ) = log k with k k k dividing ∣ G ∣ l F + r F |G|^{l_{\mathcal{F}}+r_{\mathcal{F}}} ∣ G ∣ l F + r F ; if k > 1 k>1 k > 1 , then k ≥ ϖ k \ge\varpi k ≥ ϖ .
Lemma 18. Let E \mathbb{E} E be a finite field, D ≥ 1 D \ge1 D ≥ 1 , and let F \mathcal{F} F be a linear CA on ( E n ) Z D (\mathbb{E}^{n})^{\mathbb{Z}^{D}} ( E n ) Z D with matrix M M M . If F \mathcal{F} F is equicontinuous, then all the coefficients of χ M ( t ) \chi_M(t) χ M ( t ) belong to E \mathbb{E} E .
Proof. By Proposition 2(i) there are a < b a<b a < b with F a = F b \mathcal{F}^{a}=\mathcal{F}^{b} F a = F b , hence M a = M b M^{a}=M^{b} M a = M b . Let Ω \Omega Ω be an algebraic closure of the field E ( x 1 , … , x D ) \mathbb{E}(x_1,\ldots,x_D) E ( x 1 , … , x D ) of rational functions. If λ ∈ Ω \lambda\in\Omega λ ∈ Ω is a root of χ M \chi_M χ M , then λ \lambda λ is an eigenvalue of M M M , so λ a = λ b \lambda^{a}=\lambda^{b} λ a = λ b ; hence either λ = 0 \lambda=0 λ = 0 or λ b − a = 1 \lambda^{b-a}=1 λ b − a = 1 , and in both cases λ \lambda λ is algebraic over E \mathbb{E} E . The coefficients of χ M \chi_M χ M are, up to sign, elementary symmetric functions of its roots, so they are algebraic over E \mathbb{E} E . Since E ( x 1 , … , x D ) \mathbb{E}(x_1,\ldots,x_D) E ( x 1 , … , x D ) is a purely transcendental extension of E \mathbb{E} E , the field E \mathbb{E} E is relatively algebraically closed in E ( x 1 , … , x D ) \mathbb{E}(x_1,\ldots,x_D) E ( x 1 , … , x D ) ; as the coefficients of χ M \chi_M χ M belong to E ( x 1 , … , x D ) \mathbb{E}(x_1,\ldots,x_D) E ( x 1 , … , x D ) and are algebraic over E \mathbb{E} E , they belong to E \mathbb{E} E .
Theorem 9. Let D ≥ 2 D \ge2 D ≥ 2 and let F \mathcal{F} F be a D D D -GCA on F p n \mathbb{F}_p^{n} F p n with matrix M M M . If some coefficient of χ M \chi_M χ M does not belong to F p \mathbb{F}_p F p , then H ( F ) = + ∞ \mathcal{H}(\mathcal{F})=+\infty H ( F ) = + ∞ .
Proof. Some coefficient c k c_k c k of χ M \chi_M χ M contains a monomial x u x^u x u with u ≠ 0 u \ne0 u = 0 ; after permuting the coordinates we may assume u 1 ≠ 0 u_1 \ne0 u 1 = 0 . Write x ′ = ( x 2 , … , x D ) x'=(x_2,\ldots,x_D) x ′ = ( x 2 , … , x D ) and c k = ∑ a ∈ Z x 1 a b a ( x ′ ) c_k=\sum_{a\in\mathbb{Z}}x_1^a b_a(x') c k = ∑ a ∈ Z x 1 a b a ( x ′ ) with b a ∈ F p [ x 2 ± 1 , … , x D ± 1 ] b_a\in\mathbb{F}_p[x_2^{\pm1},\ldots,x_D^{\pm1}] b a ∈ F p [ x 2 ± 1 , … , x D ± 1 ] , and let b = b u 1 ≠ 0 b=b_{u_1}\ne0 b = b u 1 = 0 .
Fix s ≥ 1 s \ge1 s ≥ 1 , let q = p s − 1 q=p^s-1 q = p s − 1 , E = F p s \mathbb{E}=\mathbb{F}_{p^s} E = F p s , and let
Y q = { c ∈ ( F p n ) Z D : c v + q e i = c v for every v ∈ Z D and 2 ≤ i ≤ D } . Y_q=\{c\in(\mathbb{F}_p^n)^{\mathbb{Z}^D}:c_{v+qe_i}=c_v\text{ for every }v\in\mathbb{Z}^D\text{ and }2\le i\le D\}. Y q = { c ∈ ( F p n ) Z D : c v + q e i = c v for every v ∈ Z D and 2 ≤ i ≤ D } .
The set Y q Y_q Y q is closed and F ( Y q ) ⊆ Y q \mathcal{F}(Y_q)\subseteq Y_q F ( Y q ) ⊆ Y q , so that H ( F ) ≥ H ( F ∣ Y q ) \mathcal{H}(\mathcal{F})\ge\mathcal{H}(\mathcal{F}|_{Y_q}) H ( F ) ≥ H ( F ∣ Y q ) by fact (c) of Section 3. Let R q = F p [ x 2 ± 1 , … , x D ± 1 ] / ( x 2 q − 1 , … , x D q − 1 ) \mathcal{R}_q=\mathbb{F}_p[x_2^{\pm1},\ldots,x_D^{\pm1}]/(x_2^q-1,\ldots,x_D^q-1) R q = F p [ x 2 ± 1 , … , x D ± 1 ] / ( x 2 q − 1 , … , x D q − 1 ) , the group algebra of ( Z / q Z ) D − 1 (\mathbb{Z}/q\mathbb{Z})^{D-1} ( Z / q Z ) D − 1 . Grouping the cells of a configuration in Y q Y_q Y q according to their first coordinate, Y q Y_q Y q is identified with ( R q n ) Z (\mathcal{R}_q^n)^{\mathbb{Z}} ( R q n ) Z , and F ∣ Y q \mathcal{F}|_{Y_q} F ∣ Y q with the one-dimensional CA which acts on finite configurations, i.e., on R q [ x 1 ± 1 ] n \mathcal{R}_q[x_1^{\pm1}]^n R q [ x 1 ± 1 ] n , as the multiplication by the image M q M_q M q of M M M in M n ( R q [ x 1 ± 1 ] ) M_n(\mathcal{R}_q[x_1^{\pm1}]) M n ( R q [ x 1 ± 1 ]) .
Let Z = ( E × ) D − 1 Z=(\mathbb{E}^{\times})^{D-1} Z = ( E × ) D − 1 ; it is the set of common zeros of x 2 q − 1 , … , x D q − 1 x_2^q-1,\ldots,x_D^q-1 x 2 q − 1 , … , x D q − 1 , and it has q D − 1 q^{D-1} q D − 1 elements. The Frobenius map ϕ ( ζ ) = ( ζ 2 p , … , ζ D p ) \phi(\zeta)=(\zeta_2^p,\ldots,\zeta_D^p) ϕ ( ζ ) = ( ζ 2 p , … , ζ D p ) acts on Z Z Z ; let O 1 , … , O N O_1,\ldots,O_N O 1 , … , O N be its orbits, choose ζ ( j ) ∈ O j \zeta^{(j)}\in O_j ζ ( j ) ∈ O j , and let d j = ∣ O j ∣ d_j=|O_j| d j = ∣ O j ∣ , so that F p ( ζ ( j ) ) = F p d j \mathbb{F}_p(\zeta^{(j)})=\mathbb{F}_{p^{d_j}} F p ( ζ ( j ) ) = F p d j and d j ≤ s d_j\leq s d j ≤ s . Since p ∤ q p\nmid q p ∤ q , the polynomial x q − 1 x^q-1 x q − 1 has q q q distinct roots in E \mathbb{E} E , and the evaluation map
ev : R q ⟶ ∏ j = 1 N F p d j , g ⟼ ( g ( ζ ( j ) ) ) j \operatorname{ev}:\mathcal{R}_q\longrightarrow\prod_{j=1}^{N}\mathbb{F}_{p^{d_j}},\qquad g\longmapsto\left(g(\zeta^{(j)})\right)_j ev : R q ⟶ j = 1 ∏ N F p d j , g ⟼ ( g ( ζ ( j ) ) ) j
is an isomorphism of F p \mathbb{F}_p F p -algebras: it is injective, because R q ⊗ F p E ≅ E Z \mathcal{R}_q\otimes_{\mathbb{F}_p}\mathbb{E}\cong\mathbb{E}^Z R q ⊗ F p E ≅ E Z via evaluation at all points of Z Z Z and g ( ϕ ( ζ ) ) = g ( ζ ) p g(\phi(\zeta))=g(\zeta)^p g ( ϕ ( ζ )) = g ( ζ ) p , and both sides have dimension q D − 1 = ∑ j d j q^{D-1}=\sum_jd_j q D − 1 = ∑ j d j over F p \mathbb{F}_p F p . Applying ev \operatorname{ev} ev coefficientwise and cellwise, we obtain a group isomorphism and homeomorphism Ψ : ( R q n ) Z ⟶ ∏ j ( F p d j n ) Z \Psi:(\mathcal{R}_q^n)^Z\longrightarrow\prod_j(\mathbb{F}_{p^{d_j}}^n)^Z Ψ : ( R q n ) Z ⟶ ∏ j ( F p d j n ) Z which conjugates F ∣ Y q \mathcal{F}|_{Y_q} F ∣ Y q to ∏ j H j \prod_jH_j ∏ j H j , where H j H_j H j is the one-dimensional linear CA on ( F p d j n ) Z (\mathbb{F}_{p^{d_j}}^n)^Z ( F p d j n ) Z with matrix M j = M ( x 1 , ζ ( j ) ) M_j=M(x_1,\zeta^{(j)}) M j = M ( x 1 , ζ ( j ) ) , obtained by substituting ζ ( j ) \zeta^{(j)} ζ ( j ) for x ′ x' x ′ . By fact (d) of § 3 ,
H ( F ) ≥ H ( F ∣ Y q ) = ∑ j = 1 N H ( H j ) . \mathcal{H}(\mathcal{F})\geq\mathcal{H}(\mathcal{F}|_{Y_q})=\sum_{j=1}^{N}\mathcal{H}(H_j). H ( F ) ≥ H ( F ∣ Y q ) = j = 1 ∑ N H ( H j ) .
Each H j H_j H j is a one-dimensional GCA on the p p p -group F p d j n \mathbb{F}_{p^{d_j}}^n F p d j n . By Corollary 5, either H ( H j ) ≥ log p \mathcal{H}(H_j)\geq\log p H ( H j ) ≥ log p , or H j H_j H j is equicontinuous. In the latter case, by Lemma 18, χ M j ∈ F p d j [ t ] \chi_{M_j}\in\mathbb{F}_{p^{d_j}}[t] χ M j ∈ F p d j [ t ] . Since the determinant commutes with ring homomorphisms, χ M j \chi_{M_j} χ M j is obtained from χ M \chi_M χ M by substituting ζ ( j ) \zeta^{(j)} ζ ( j ) for x ′ x' x ′ , and the coefficient of x 1 u 1 t k x_1^{u_1}t^k x 1 u 1 t k in χ M j \chi_{M_j} χ M j is b ( ζ ( j ) ) b(\zeta^{(j)}) b ( ζ ( j ) ) , with u 1 ≠ 0 u_1\ne0 u 1 = 0 ; hence b ( ζ ( j ) ) = 0 b(\zeta^{(j)})=0 b ( ζ ( j ) ) = 0 . Therefore
H ( F ) ≥ log p ⋅ ∣ { j : b ( ζ ( j ) ) ≠ 0 } ∣ . \mathcal{H}(\mathcal{F})\geq\log p\cdot\left|\{j:b(\zeta^{(j)})\ne0\}\right|. H ( F ) ≥ log p ⋅ { j : b ( ζ ( j ) ) = 0 } .
Since b b b has coefficients in F p \mathbb{F}_p F p , b ( ϕ ( ζ ) ) = b ( ζ ) p b(\phi(\zeta))=b(\zeta)^p b ( ϕ ( ζ )) = b ( ζ ) p , so the set of zeros of b b b in Z Z Z is a union of orbits, and each orbit has at most s s s elements. Let b ~ = x ′ w b \widetilde b=x'^wb b = x ′ w b be a polynomial, for a suitable w ∈ Z D − 1 w\in\mathbb{Z}^{D-1} w ∈ Z D − 1 , and let δ \delta δ be its total degree; b ~ \widetilde b b and b b b have the same zeros in Z Z Z , and δ \delta δ does not depend on s s s . By the Schwartz–Zippel lemma [37 , 45 ] , applied to the grid Z = ( E × ) D − 1 Z=(\mathbb{E}^{\times})^{D-1} Z = ( E × ) D − 1 , b ~ \widetilde b b has at most δ q D − 2 \delta q^{D-2} δ q D − 2 zeros in Z Z Z . Hence
H ( F ) ≥ log p ⋅ q D − 1 − δ q D − 2 s = log p ⋅ q D − 2 ( q − δ ) s , q = p s − 1. \mathcal{H}(\mathcal{F})\geq\log p\cdot\frac{q^{D-1}-\delta q^{D-2}}{s}=\log p\cdot\frac{q^{D-2}(q-\delta)}{s},\qquad q=p^s-1. H ( F ) ≥ log p ⋅ s q D − 1 − δ q D − 2 = log p ⋅ s q D − 2 ( q − δ ) , q = p s − 1.
Since D ≥ 2 D\geq2 D ≥ 2 and q / s → ∞ q/s\to\infty q / s → ∞ as s → ∞ s\to\infty s → ∞ , we conclude that H ( F ) = + ∞ \mathcal{H}(\mathcal{F})=+\infty H ( F ) = + ∞ .
Proof of Theorem 4(2)–(3) without duality. If all the coefficients of χ M \chi_M χ M belong to F p \mathbb{F}_p F p , then F \mathcal{F} F is equicontinuous by the Cayley–Hamilton argument given in the proof of Theorem 4(3), and H ( F ) = 0 \mathcal{H}(\mathcal{F})=0 H ( F ) = 0 by Proposition 1. Conversely, if F \mathcal{F} F is equicontinuous, then all the coefficients of χ M \chi_M χ M belong to F p \mathbb{F}_p F p by Lemma 18. This proves (3) in every dimension. For D ≥ 2 D\geq2 D ≥ 2 , part (2) follows from the first sentence and from Theorem 9.
We remark that the subsystems Y q Y_q Y q of spatially periodic configurations make rigorous the intuition that, in dimension D ≥ 2 D\geq2 D ≥ 2 , a non-equicontinuous GCA produces a number of independent contributions to the entropy which grows with the size of the observation window: in the proof above, these contributions are the factors H j H_j H j with b ( ζ ( j ) ) ≠ 0 b(\zeta^{(j)}) \ne0 b ( ζ ( j ) ) = 0 , whose number grows like q D − 1 / s q^{D-1}/s q D − 1 / s .