betaFeedback

WorksComputer Science

Strong Transitivity of Group Cellular Automata: Characterization and Decidability

Abstract

A discrete-time dynamical system is strongly transitive if every point can be reached, in finitely many steps, from every non-empty open set. We study this property for group cellular automata, \ie cellular automata over a finite group alphabet whose global map is a group endomorphism, in every dimension d≥1d\geq1. We prove that no group cellular automaton over a non-abelian group is strongly transitive, and we develop a decomposition of group cellular automata over abelian groups, via quotients by power subgroups, which preserves strong transitivity. For linear cellular automata over (Z/pZ)n(\mathbb Z/p\mathbb Z)^n we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial χAχ_A of the associated matrix AA of Laurent polynomials: the automaton is strongly transitive if and only if det⁡(A)≠0\det(A)\neq0 and no irreducible factor of χAχ_A has an invertible constant term. Combining these results, we obtain that strong transitivity is decidable for group cellular automata in every dimension. For every fixed dimension dd, we give an explicit decision procedure whose running time is polynomial in the group size NN, the number kk of neighbours, and the neighbourhood radius ϱ\varrho.

Introduction

Cellular automata (CAs) are discrete-time dynamical systems defined by the synchronous application of a local rule on a regular lattice Zd\mathbb{Z}^d of cells, each of which takes values in a finite alphabet. Despite their simple definition, they exhibit a wide range of dynamical behaviors, and many of their dynamical properties are undecidable in general [18]. This motivates the search for natural classes of CAs in which such properties become decidable and admit explicit characterizations.

A continuous map ff of a compact metric space XX is strongly transitive if ⋃n≥0fn(U)=X\bigcup_{n\ge0} f^n(U) = X for every non-empty open set U⊆XU \subseteq X, that is, if every point of XX can be reached from every open set. Strong transitivity is a strong form of topological transitivity: a strongly transitive map is surjective, and the backward orbit of every point is dense. For CAs, strong transitivity is closely related to expansivity: every positively expansive one-dimensional CA is strongly transitive [6], while in dimension d≥2d \ge2 there are no positively expansive CAs [18].

Strong transitivity has been investigated for general CAs [1, 2, 6, 11, 16] and, in particular, for linear and additive CAs and, more generally, for GCAs (including linear and additive CA) [9, 12, 13, 15, 21].

For additive cellular automata over finite abelian groups, previous work provided a first structural characterization of strong transitivity, showing that it is preserved under spatial translations and temporal iterations [12, 13]. That work explicitly raised the question of whether the same result extends to general cellular automata [12]. Moreover, while the decidability of the weaker property of topological transitivity has been established for group cellular automata over arbitrary finite groups and in every dimension [8], a complete effective criterion for deciding strong transitivity from the local rule was still missing. Thus, determining strong transitivity remained a natural outstanding problem in the algorithmic study of group cellular automata.

In this paper we study strong transitivity for group cellular automata (GCAs), i.e., CAs whose alphabet is a finite group GG and whose global map is an endomorphism of the group GZdG^{\mathbb{Z}^{d}}. GCAs generalize linear CAs over (Z/mZ)n(\mathbb{Z}/m\mathbb{Z})^{n}, and their algebraic structure makes many dynamical properties accessible to exact analysis. Decidability results for GCAs have been obtained for injectivity and surjectivity and for several properties of the limit set [4], for topological transitivity [8], for positive expansivity [14], and for topological entropy [7]. In these works, a central role is played by a decomposition of a GCA into simpler components via quotients by suitable subgroups of the alphabet, which reduces the analysis to alphabets that are direct products of isomorphic simple groups.

Our contributions.

  • We prove that, in every dimension, no GCA over a non-abelian group is strongly transitive (Theorem 2). Hence the alphabet of a strongly transitive GCA is abelian.

  • For GCAs over abelian groups we introduce a decomposition via quotients by power subgroups Gm={gm:g∈G}G^{m}=\{g^{m}:g\in G\}, and we prove that it preserves strong transitivity: a GCA is strongly transitive if and only if all of its components are (Theorem 3 and Corollary 1). Such components are linear CAs over groups of the form (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^{n}. We point out that similar decompositions are used in [7] and in [8].

  • For a linear CA over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^{n} with matrix AA of Laurent polynomials in dd variables, we prove that strong transitivity holds if and only if det⁡(A)≠0\det(A)\ne0 and no monic irreducible factor of the characteristic polynomial χA\chi_{A} has a unit constant term (Theorem 6). The proof combines Pontryagin duality, which translates strong transitivity into the triviality of the eventual image of the dual endomorphism (Corollary 2), with an algebraic characterization of the eventual image of a matrix over a noetherian integrally closed domain (Theorem 5).

  • As a consequence, strong transitivity is decidable for GCAs in every dimension (Corollaries 4 and 5). We give an explicit decision procedure which, for every fixed dimension dd, runs in time polynomial in the group size N=∣G∣N=|G|, the number kk of neighbours, and the neighbourhood radius ρ\rho, including the cost of factoring at most log⁡2N\log_{2}N multivariate polynomials over finite fields (Theorem 7 and the subsequent complexity analysis). Unlike the procedure for deciding topological transitivity in [8], it does not require a search over arbitrary verbal subgroups: it immediately rejects non-abelian alphabets and decomposes abelian ones by means of power subgroups.

Organization of the paper. Section 2 recalls the basic definitions and a characterization of strong transitivity for GCAs. Section 3 shows that GCAs over non-abelian groups are never strongly transitive. Section 4 presents the decomposition of GCAs over abelian groups via power subgroups and proves that it preserves strong transitivity, and Section 5 deals with linear CAs over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^{n}, where the characterization via Pontryagin duality is obtained. Section 6 analyzes the computational complexity of deciding strong transitivity. Section 7 contains some concluding remarks and open problems.

Preliminaries

Cellular automata and group cellular automata

Let d≥1d \ge1 and let AA be a finite set. A configuration is an element of AZdA^{\mathbb{Z}^{d}}; for c∈AZdc \in A^{\mathbb{Z}^{d}} and v∈Zdv \in\mathbb{Z}^{d} we write cvc_v for the value of cc at vv, and for S⊆ZdS \subseteq\mathbb{Z}^{d} we write c∣Sc|_S for the restriction of cc to SS. We endow AZdA^{\mathbb{Z}^{d}} with the prodiscrete topology, which makes it a compact metrizable space. For a finite set S⊆ZdS \subseteq\mathbb{Z}^{d} and p∈ASp \in A^S, the cylinder

Cyl⁡A(S,p)={c∈AZd:c∣S=p}\operatorname{Cyl}_A(S,p) = \{c \in A^{\mathbb{Z}^{d}} : c|_S = p\}

is clopen, and cylinders form a basis of the topology. For ℓ≥0\ell\ge0 we let Bℓ=[−ℓ,ℓ]d∩ZdB_\ell= [-\ell,\ell]^d \cap\mathbb{Z}^{d}. Every non-empty open set contains a cylinder of the form Cyl⁡A(Bℓ,p)\operatorname{Cyl}_A(B_\ell,p). For u∈Zdu \in\mathbb{Z}^{d}, the shift σu:AZd→AZd\sigma^u : A^{\mathbb{Z}^{d}} \to A^{\mathbb{Z}^{d}} is defined by σu(c)v=cv+u\sigma^u(c)_v = c_{v+u}. A (dd-dimensional) CA is a continuous map F:AZd→AZdF : A^{\mathbb{Z}^{d}} \to A^{\mathbb{Z}^{d}} commuting with every shift. By the Curtis–Hedlund–Lyndon theorem, FF is given by a local rule f:Ak→Af : A^k \to A and a set Vf={v1,…,vk}⊆ZdV_f = \{v_1,\ldots,v_k\} \subseteq\mathbb{Z}^{d} of pairwise distinct vectors, the neighborhood, via F(c)v=f(cv+v1,…,cv+vk)F(c)_v = f(c_{v+v_1},\ldots,c_{v+v_k}).

Let GG be a finite group with identity ee. Then GZdG^{\mathbb{Z}^{d}} is a compact group under the componentwise operation, with identity eZde^{\mathbb{Z}^{d}}. A CA F:GZd→GZdF : G^{\mathbb{Z}^{d}} \to G^{\mathbb{Z}^{d}} is a GCA if it is a group endomorphism of GZdG^{\mathbb{Z}^{d}}. In this case the local rule is a homomorphism f:Gk→Gf : G^k \to G, and f(g1,…,gk)=h1(g1)⋯hk(gk)f(g_1,\ldots,g_k) = h_1(g_1)\cdots h_k(g_k) for endomorphisms h1,…,hkh_1,\ldots,h_k of GG with pairwise commuting images [15]; we write f=(h1,…,hk)f = (h_1,\ldots,h_k).

Strong transitivity

Definition 1. Let XX be a compact metric space. A continuous map f:X→Xf : X \to X is strongly transitive if ⋃n≥0fn(U)=X\bigcup_{n\ge0} f^n(U) = X for every non-empty open set U⊆XU \subseteq X; equivalently, if ⋃n≥0f−n(x)\bigcup_{n\ge0} f^{-n}(x) is dense in XX for every x∈Xx \in X.

If XX has at least two points, a strongly transitive map ff is surjective: if x∉f(X)x \notin f(X), then x∉⋃n≥0fn(U)x \notin\bigcup_{n\ge0} f^n(U) for every non-empty open set UU not containing xx.

Theorem 1. Let XX and YY be compact metric spaces, and let f:X→Xf : X \to X and g:Y→Yg : Y \to Y be continuous. Assume that there is a continuous surjection h:X→Yh : X \to Y with h∘f=g∘hh \circ f = g \circ h. If ff is strongly transitive, then gg is strongly transitive.

Proof. Let U⊆YU \subseteq Y be non-empty and open, and let yˉ∈Y\bar{y} \in Y. Choose xˉ∈X\bar{x} \in X with h(xˉ)=yˉh(\bar{x}) = \bar{y}. Since h−1(U)h^{-1}(U) is non-empty and open and ff is strongly transitive, there are n≥0n \ge0 and x∈h−1(U)x \in h^{-1}(U) with fn(x)=xˉf^n(x) = \bar{x}. Then yˉ=h(fn(x))=gn(h(x))∈gn(U)\bar{y} = h(f^n(x)) = g^n(h(x)) \in g^n(U). □

The following lemma generalizes [13 Lemma 15].

Lemma 1. Let FF be a dd-dimensional GCA over a finite group GG. Then FF is strongly transitive if and only if:

  1. FF is surjective, and

  2. for every ℓ≥0\ell\ge0 and every p∈GBℓp \in G^{B_\ell} there exists n≥0n \ge0 such that eZd∈Fn(Cyl⁡G(Bℓ,p))e^{\mathbb{Z}^{d}} \in F^n(\operatorname{Cyl}_G(B_\ell,p)).

Moreover, if FF is strongly transitive, then for every ℓ≥0\ell\ge0 there is nℓ≥0n_\ell\ge0 such that Fnℓ(Cyl⁡G(Bℓ,p))=GZdF^{n_\ell}(\operatorname{Cyl}_G(B_\ell,p)) = G^{\mathbb{Z}^{d}} for every p∈GBℓp \in G^{B_\ell}.

Proof. The “only if” part follows from the definition and from the remark after Definition 1. Assume that (1) and (2) hold, and fix ℓ≥0\ell\ge0. For p∈GBℓp \in G^{B_\ell} let npn_p be the least nn such that eZd∈Fn(Cyl⁡G(Bℓ,p))e^{Z^d} \in\mathcal{F}^n(\operatorname{Cyl}_G(B_\ell,p)). Since F(eZd)=eZd\mathcal{F}(e^{Z^d})=e^{Z^d}, we have eZd∈Fn(Cyl⁡G(Bℓ,p))e^{Z^d} \in\mathcal{F}^n(\operatorname{Cyl}_G(B_\ell,p)) for every n≥npn \ge n_p. Let nℓ=max⁡{np:p∈GBℓ}n_\ell=\max\{n_p:p\in G^{B_\ell}\}; then

eZd∈Fnℓ(Cyl⁡G(Bℓ,p))for every p∈GBℓ.(1)e^{Z^d} \in\mathcal{F}^{n_\ell}(\operatorname{Cyl}_G(B_\ell,p)) \qquad\text{for every }p\in G^{B_\ell}. \tag*{(1)}

Let y∈GZdy\in G^{Z^d} and p∈GBℓp\in G^{B_\ell}. Since F\mathcal{F} is surjective, there is c∈GZdc\in G^{Z^d} with Fnℓ(c)=y\mathcal{F}^{n_\ell}(c)=y. The set c−1Cyl⁡G(Bℓ,p)c^{-1}\operatorname{Cyl}_G(B_\ell,p) is the cylinder Cyl⁡G(Bℓ,q)\operatorname{Cyl}_G(B_\ell,q) with qv=cv−1pvq_v=c_v^{-1}p_v; by (1) there is c′∈Cyl⁡G(Bℓ,q)c'\in\operatorname{Cyl}_G(B_\ell,q) with Fnℓ(c′)=eZd\mathcal{F}^{n_\ell}(c')=e^{Z^d}. Then cc′∈Cyl⁡G(Bℓ,p)cc'\in\operatorname{Cyl}_G(B_\ell,p) and Fnℓ(cc′)=Fnℓ(c)Fnℓ(c′)=y\mathcal{F}^{n_\ell}(cc')=\mathcal{F}^{n_\ell}(c)\mathcal{F}^{n_\ell}(c')=y. This proves the “moreover” part, and, since every non-empty open set contains a cylinder Cyl⁡G(Bℓ,p)\operatorname{Cyl}_G(B_\ell,p), that F\mathcal{F} is strongly transitive.

Non-abelian components

In this section we prove that there are no strongly transitive d-GCA over a non-abelian group. This extends the same result for d=1d=1 proved in [7].

For a group Γ\Gamma we denote by ZΓZ_\Gamma its center; note that ZGZd=ZGZdZ_{G^{Z^d}}=Z_G^{Z^d}.

Lemma 2. Let F\mathcal{F} be a surjective dd-GCA over a finite group GG. Then Ker⁡(F)⊆ZGZd\operatorname{Ker}(\mathcal{F})\subseteq Z_G^{Z^d}.

Proof. For b,c∈GZdb,c\in G^{Z^d} let [b,c]=b−1c−1bc[b,c]=b^{-1}c^{-1}bc. Let c∈Ker⁡(F)c\in\operatorname{Ker}(\mathcal{F}) and suppose that cv∉ZGc_v\notin Z_G for some v∈Zdv\in Z^d. Choose g∈Gg\in G with [cv,g]≠e[c_v,g]\ne e, and let b∈GZdb\in G^{Z^d} be the configuration with bv=gb_v=g and bw=eb_w=e for w≠vw\ne v. Since Ker⁡(F)\operatorname{Ker}(\mathcal{F}) is normal, [c,b]∈Ker⁡(F)[c,b]\in\operatorname{Ker}(\mathcal{F}); moreover, [c,b][c,b] is trivial outside vv and [c,b]v=[cv,g]≠e[c,b]_v=[c_v,g]\ne e. Thus [c,b][c,b] and eZde^{Z^d} are distinct finite configurations with the same image, so F\mathcal{F} is not pre-injective, and hence not surjective by the Garden of Eden theorem [10], a contradiction.

Theorem 2. Let F\mathcal{F} be a dd-GCA over a finite non-abelian group GG. Then F\mathcal{F} is neither strongly transitive nor positively expansive.

Proof. Assume that F\mathcal{F} is strongly transitive. Then F\mathcal{F} is surjective, and so is Fm\mathcal{F}^m for every m≥1m\ge1; by Lemma 2, Ker⁡(Fm)⊆ZGZd\operatorname{Ker}(\mathcal{F}^m)\subseteq Z_G^{Z^d} for every mm. Since GG is non-abelian, there is g∈G∖ZGg\in G\setminus Z_G; let U={c∈GZd:c0=g}U=\{c\in G^{Z^d}:c_0=g\}, a non-empty open set disjoint from ZGZdZ_G^{Z^d}. Then eZd∉Fm(U)e^{Z^d}\notin\mathcal{F}^m(U) for every m≥0m\ge0, since otherwise some element of UU would lie in Ker⁡(Fm)⊆ZGZd\operatorname{Ker}(\mathcal{F}^m)\subseteq Z_G^{Z^d}. This contradicts strong transitivity. For the second assertion, if d=1d=1 it suffices to recall that every positively expansive CA is strongly transitive [6 Theorem 2], while for d≥2d\ge2 there are no positively expansive CAs at all [18 Section 8].

A decomposition that preserves strong transitivity

By Theorem 2, a GCA over a non-abelian group is never strongly transitive. Hence, in order to decide strong transitivity, we may always assume that the alphabet is abelian, and in this section we develop a decomposition of GCAs over abelian groups which preserves strong transitivity.

Quotients by invariant subgroups

Let GG be a finite group and let F\mathcal{F} be a dd-GCA on GG with local rule f=(h1,…,hk)f=(h_1,\ldots,h_k). Let HH be a normal subgroup of GG such that F(HZd)⊆HZd\mathcal{F}(H^{Z^d})\subseteq H^{Z^d}; this holds, for instance, if hj(H)⊆Hh_j(H) \subseteq H for every jj. For g∈Gg \in G let [g]=gH∈G/H[g] = gH \in G/H, and for c∈GZdc \in G^{\mathbb{Z}^d} let [c]∈(G/H)Zd[c] \in(G/H)^{\mathbb{Z}^d} be defined by [c]v=[cv][c]_v = [c_v]. The maps

F‾:HZd→HZd,F‾(c)=F(c),F~:(G/H)Zd→(G/H)Zd,F~([c])=[F(c)],\overline{\mathcal{F}} : H^{\mathbb{Z}^d} \to H^{\mathbb{Z}^d}, \quad\overline{\mathcal{F}}(c) = \mathcal{F}(c), \qquad\widetilde{\mathcal{F}} : (G/H)^{\mathbb{Z}^d} \to(G/H)^{\mathbb{Z}^d}, \quad\widetilde{\mathcal{F}}([c]) = [\mathcal{F}(c)],

are well defined GCAs on HH and on G/HG/H, respectively: F~\widetilde{\mathcal{F}} does not depend on the representative because F(cz)=F(c)F(z)\mathcal{F}(cz) = \mathcal{F}(c)\mathcal{F}(z) with F(z)∈HZd\mathcal{F}(z) \in H^{\mathbb{Z}^d} for every z∈HZdz \in H^{\mathbb{Z}^d}.

Proposition 1. Let HH be a normal subgroup of GG with F(HZd)⊆HZd\mathcal{F}(H^{\mathbb{Z}^d}) \subseteq H^{\mathbb{Z}^d}. If F~\widetilde{\mathcal{F}} and F‾\overline{\mathcal{F}} are strongly transitive, then F\mathcal{F} is strongly transitive.

Proof. F\mathcal{F} is surjective. (Notice that this same fact, when d=1d=1, has been proved in [7].) Let y∈GZdy \in G^{\mathbb{Z}^d}. Since F~\widetilde{\mathcal{F}} is surjective, there is x∈GZdx \in G^{\mathbb{Z}^d} with [F(x)]=[y][\mathcal{F}(x)] = [y], i.e., z:=F(x)−1y∈HZdz := \mathcal{F}(x)^{-1}y \in H^{\mathbb{Z}^d}. Since F‾\overline{\mathcal{F}} is surjective, z=F(z′)z = \mathcal{F}(z') for some z′∈HZdz' \in H^{\mathbb{Z}^d}, and y=F(xz′)y = \mathcal{F}(xz').

Condition (2) of Lemma 1. Let ℓ≥0\ell\ge0, p∈GBℓp \in G^{B_\ell}, and B=Cyl⁡G(Bℓ,p)B = \operatorname{Cyl}_G(B_\ell,p). Let B~=Cyl⁡G/H(Bℓ,p~)\widetilde{B} = \operatorname{Cyl}_{G/H}(B_\ell,\widetilde{p}), where p~v=[pv]\widetilde{p}_v = [p_v]. Since F~\widetilde{\mathcal{F}} is strongly transitive, there is n~\widetilde{n} with F~n~(B~)\widetilde{\mathcal{F}}^{\widetilde{n}}(\widetilde{B}), that is, there are b∈Bb \in B and h∈HZdh \in H^{\mathbb{Z}^d} with Fn~(b)=h\mathcal{F}^{\widetilde{n}}(b) = h. The map Fn~\mathcal{F}^{\widetilde{n}} is a continuous surjective endomorphism of the compact group GZdG^{\mathbb{Z}^d}, hence it is open by the open mapping theorem for compact groups [17 Theorem 5.29]. Thus Fn~(B)\mathcal{F}^{\widetilde{n}}(B) is an open set containing hh, and it contains a cylinder CC with h∈Ch \in C. The set C∩HZdC \cap H^{\mathbb{Z}^d} is non-empty and open in HZdH^{\mathbb{Z}^d}; since F‾\overline{\mathcal{F}} is strongly transitive, there are n‾\overline{n} and a∈C∩HZda \in C \cap H^{\mathbb{Z}^d} with Fn‾(a)=eZd\mathcal{F}^{\overline{n}}(a) = e^{\mathbb{Z}^d}. Writing a=Fn~(b′)a = \mathcal{F}^{\widetilde{n}}(b') with b′∈Bb' \in B, we get Fn~+n‾(b′)=eZd\mathcal{F}^{\widetilde{n}+\overline{n}}(b') = e^{\mathbb{Z}^d}. By Lemma 1, F\mathcal{F} is strongly transitive.

Power subgroups of abelian groups

From now on in this section GG is a finite abelian group. For a prime pp, a finite group is a pp-group if its order is a power of pp, and a finite abelian group is an elementary abelian pp-group if it is isomorphic to (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n for some n≥0n \ge0, equivalently if gp=eg^p = e for every element gg. For an integer m≥0m \ge0, the power subgroup Gm={gm:g∈G}G^m = \{g^m : g \in G\} is a subgroup of GG, since gmhm=(gh)mg^m h^m = (gh)^m. Every endomorphism φ\varphi of GG satisfies φ(Gm)=φ(G)m⊆Gm\varphi(G^m) = \varphi(G)^m \subseteq G^m; in particular hj(Gm)⊆Gmh_j(G^m) \subseteq G^m for every jj, so that F((Gm)Zd)⊆(Gm)Zd\mathcal{F}((G^m)^{\mathbb{Z}^d}) \subseteq(G^m)^{\mathbb{Z}^d}, and the GCAs F‾\overline{\mathcal{F}} on GmG^m and F~\widetilde{\mathcal{F}} on G/GmG/G^m are defined.

Theorem 3. Let F\mathcal{F} be a dd-GCA over a finite abelian group GG, and let m≥0m \ge0. Then F\mathcal{F} is strongly transitive if and only if both F‾\overline{\mathcal{F}} on GmG^m and F~\widetilde{\mathcal{F}} on G/GmG/G^m are strongly transitive.

Proof. Let H=GmH = G^m. The “if” part is Proposition 1. Assume that F\mathcal{F} is strongly transitive. F~\widetilde{\mathcal{F}} is strongly transitive. The map π:GZd→(G/H)Zd\pi: G^{\mathbb{Z}^d} \to(G/H)^{\mathbb{Z}^d}, c↦[c]c \mapsto[c], is a continuous surjection with π∘F=F~∘π\pi\circ\mathcal{F} = \widetilde{\mathcal{F}} \circ\pi; apply Theorem 1.

F‾\overline{\mathcal{F}} is strongly transitive. Let ℓ≥0\ell\ge0, p∈HBℓp \in H^{B_\ell} and y∈HZdy \in H^{\mathbb{Z}^d}. Since the cylinders Cyl⁡H(Bℓ,p)=Cyl⁡G(Bℓ,p)∩HZd\operatorname{Cyl}_H(B_\ell,p) = \operatorname{Cyl}_G(B_\ell,p) \cap H^{\mathbb{Z}^d} form a basis of the topology of HZdH^{\mathbb{Z}^d}, it suffices to find n≥0n \ge0 and c∈Cyl⁡H(Bℓ,p)c \in\operatorname{Cyl}_H(B_\ell,p) with Fn(c)=y\mathcal{F}^n(c) = y. Since H=GmH = G^m, there are a∈GBℓa \in G^{B_\ell} and b∈GZdb \in G^{\mathbb{Z}^d} with pu=aump_u = a_u^m for u∈Bℓu \in B_\ell and yu=bumy_u = b_u^m for u∈Zdu \in\mathbb{Z}^d. Since F\mathcal{F} is strongly transitive, there are n≥0n \ge0 and c′∈Cyl⁡G(Bℓ,a)c' \in\operatorname{Cyl}_G(B_\ell,a) with Fn(c′)=b\mathcal{F}^n(c') = b. Let c=(c′)mc = (c')^m, the power being taken in the group GZdG^{\mathbb{Z}^d}, i.e., cell by cell. Then c∈HZdc \in H^{\mathbb{Z}^d}, c∣Bℓ=pc|_{B_\ell} = p, and, since Fn\mathcal{F}^n is an endomorphism, Fn(c)=Fn(c′)m=bm=y\mathcal{F}^n(c) = \mathcal{F}^n(c')^m = b^m = y.

The decomposition

Whenever a recursive call is made, GG is non-trivial and not an elementary abelian pp-group, and pp is a prime divisor of ∣G∣|G|; let H=GpH = G^p. By Cauchy’s theorem, the endomorphism

Algorithm 1: Abelian GCA decomposition
Input: An abelian GCA $(\mathcal{F},G)$
Output: A finite set $\{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_q,G_q)\}$ of GCA where each $G_i$ is an elementary abelian $p_i$-group, or $G_i=G=\{e\}$
Function PowerDecomp$(\mathcal{F},G)$:
    if $G$ is non-trivial and is not an elementary abelian $p$-group then
        $p\leftarrow$ a prime divisor of $|G|$;
        return PowerDecomp$(\mathcal{F},G^p)\cup$ PowerDecomp$(\widetilde{\mathcal{F}},G/G^p)$
    else
        return $\{(\mathcal{F},G)\}$

g↦gpg\mapsto g^p of GG has a non-trivial kernel, so H≠GH\ne G; and H≠{e}H\ne\{e\}, since otherwise gp=eg^p=e for every g∈Gg\in G, i.e., GG would be an elementary abelian pp-group. Hence ∣H∣<∣G∣|H|<|G| and ∣G/H∣<∣G∣|G/H|<|G|, and PowerDecomp terminates. Since subgroups and quotients of abelian groups are abelian, it returns a finite family {(F1,G1),…,(Fq,Gq)}\{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_q,G_q)\} of dd-GCAs over abelian groups. If G={e}G=\{e\}, the output is {(F,G)}\{(\mathcal{F},G)\}; otherwise, by the stopping condition, every GiG_i satisfies Gi≅(Z/piZ)niG_i\cong(\mathbb{Z}/p_i\mathbb{Z})^{n_i} for some prime pip_i and some ni≥1n_i\ge1.

Corollary 1. Let F\mathcal{F} be a dd-GCA over a finite abelian group G≠{e}G\ne\{e\}, and let {(F1,G1),…,(Fq,Gq)}\{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_q,G_q)\} be the output of PowerDecomp (Algorithm 1) on (F,G)(\mathcal{F},G). Then, for every ii, Gi≅(Z/piZ)niG_i\cong(\mathbb{Z}/p_i\mathbb{Z})^{n_i} for some prime pip_i and some ni≥1n_i\ge1, and F\mathcal{F} is strongly transitive if and only if every Fi\mathcal{F}_i is strongly transitive.

Proof. The first assertion follows from the stopping condition of PowerDecomp, as observed above; the second from Theorem 3 and induction on the depth of the recursion.

Hence, by Theorem 2 and Corollary 1, in order to decide strong transitivity of GCAs it suffices to decide it for GCAs over groups of the form (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n, which are studied in § 5.

Linear GCAs over $(\mathbb{Z}/p\mathbb{Z})^n`

Throughout this section the dimension d≥1d\ge1 is arbitrary. By Corollary 1, it remains to characterize strong transitivity for GCAs over (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n; as we show below, these are exactly the linear CAs over Fpn\mathbb{F}_p^n.

Linear CAs and their matrices

Let pp be a prime, Fp=Z/pZ\mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}, Lp=Fp[x1±1,…,xd±1]\mathbb{L}_p=\mathbb{F}_p[x_1^{\pm1},\ldots,x_d^{\pm1}] the ring of Laurent polynomials in dd variables, and Kp=Fp(x1,…,xd)\mathbb{K}_p=\mathbb{F}_p(x_1,\ldots,x_d) its field of fractions. For u∈Zdu\in\mathbb{Z}^d we write xu=x1u1⋯xdudx^u=x_1^{u_1}\cdots x_d^{u_d}. The ring Lp\mathbb{L}_p is a noetherian unique factorization domain, hence integrally closed, and its units are the elements axua x^u with a∈Fp∖{0}a\in\mathbb{F}_p\setminus\{0\} and u∈Zdu\in\mathbb{Z}^d. Every endomorphism of Fpn\mathbb{F}_p^n is Fp\mathbb{F}_p-linear, so a GCA F\mathcal{F} on Fpn\mathbb{F}_p^n has the form F(c)v=∑u∈VFAucv+u\mathcal{F}(c)_v=\sum_{u\in V_{\mathcal{F}}}A_u c_{v+u} with Au∈Mn(Fp)A_u\in M_n(\mathbb{F}_p). We associate with F\mathcal{F} the matrix MF=∑u∈VFAux−u∈Mn(Lp)M_{\mathcal{F}}=\sum_{u\in V_{\mathcal{F}}}A_u x^{-u}\in M_n(\mathbb{L}_p); conversely, every A∈Mn(Lp)A\in M_n(\mathbb{L}_p) defines in this way a GCA FA\mathcal{F}_A on Fpn\mathbb{F}_p^n. Identifying a finite configuration cc with ∑vcvxv∈Lpn\sum_v c^v x^v\in\mathbb{L}_p^n, FA\mathcal{F}_A acts on finite configurations as the multiplication by AA, and FAB=FA∘FB\mathcal{F}_{AB}=\mathcal{F}_A\circ\mathcal{F}_B. We say that AA is strongly transitive (resp. transitive) if FA\mathcal{F}_A is.

Strong transitivity via Pontryagin duality

For Pontryagin duality we refer to [22].

Let XX be a compact metrizable abelian group, written additively with identity 00, and let F:X→XF:X\to X be a continuous endomorphism. Let

K(F)=⋃n≥0Ker⁡(Fn).\mathcal{K}(F)=\bigcup_{n\geq0}\operatorname{Ker}(F^n).

Lemma 3. FF is strongly transitive if and only if FF is surjective and K(F)‾=X\overline{\mathcal{K}(F)}=X.

Proof. Assume that FF is strongly transitive. Then FF is surjective (see the remark after Definition 1; if X={0}X=\{0\} there is nothing to prove). For every non-empty open set UU there is nn with 0∈Fn(U)0\in F^n(U), i.e., U∩Ker⁡(Fn)≠∅U\cap\operatorname{Ker}(F^n)\ne\varnothing; hence K(F)\mathcal{K}(F) is dense.

Conversely, assume that FF is surjective and K(F)\mathcal{K}(F) is dense. Let U⊆XU\subseteq X be non-empty and open, let u0∈Uu_0\in U, and let VV be an open neighborhood of 00 with V=−VV=-V and u0+V⊆Uu_0+V\subseteq U. For every z∈Xz\in X the open set z−Vz-V meets K(F)\mathcal{K}(F), so X=K(F)+V=⋃n≥0(Ker⁡(Fn)+V)X=\mathcal{K}(F)+V=\bigcup_{n\geq0}(\operatorname{Ker}(F^n)+V). The sets Ker⁡(Fn)+V\operatorname{Ker}(F^n)+V are open and increasing in nn, so by compactness X=Ker⁡(FN)+VX=\operatorname{Ker}(F^N)+V for some NN. Let x∈Xx\in X. Since FNF^N is surjective, x=FN(y)x=F^N(y) for some y∈Xy\in X; write y−u0=k+vy-u_0=k+v with k∈Ker⁡(FN)k\in\operatorname{Ker}(F^N) and v∈Vv\in V. Then u0+v∈Uu_0+v\in U and FN(u0+v)=FN(y−k)=xF^N(u_0+v)=F^N(y-k)=x. Hence x∈FN(U)x\in F^N(U).

Let X^\widehat{X} be the Pontryagin dual of XX, the discrete abelian group of continuous homomorphisms χ:X→T\chi:X\to\mathbb{T}, where T\mathbb{T} is the circle group, written multiplicatively; X^\widehat{X} is written multiplicatively, with identity the trivial character 11. Let F^:X^→X^\widehat{F}:\widehat{X}\to\widehat{X}, F^(χ)=χ∘F\widehat{F}(\chi)=\chi\circ F, be the dual endomorphism. For S⊆XS\subseteq X, the annihilator of SS is the subgroup

S⊥={χ∈X^:χ(s)=1 for every s∈S}.S^\perp=\{\chi\in\widehat{X}:\chi(s)=1\text{ for every }s\in S\}.

Lemma 4. For every family (Hi)i∈I(H_i)_{i\in I} of subsets of XX, (⋃iHi)⊥=⋂iHi⊥\left(\bigcup_{i}H_i\right)^\perp=\bigcap_i H_i^\perp.

Proof. A character annihilates ⋃iHi\bigcup_i H_i if and only if it annihilates each HiH_i.

Lemma 5. For every continuous endomorphism φ:X→X\varphi:X\to X, (Ker⁡φ)⊥=Im⁡(φ^)(\operatorname{Ker}\varphi)^\perp=\operatorname{Im}(\widehat{\varphi}).

Proof. If ψ∈X^\psi\in\widehat{X}, then φ^(ψ)=ψ∘φ\widehat{\varphi}(\psi)=\psi\circ\varphi is trivial on Ker⁡φ\operatorname{Ker}\varphi; hence Im⁡(φ^)⊆(Ker⁡φ)⊥\operatorname{Im}(\widehat{\varphi})\subseteq(\operatorname{Ker}\varphi)^\perp. Conversely, let χ∈(Ker⁡φ)⊥\chi\in(\operatorname{Ker}\varphi)^\perp. The subgroup Y=φ(X)Y=\varphi(X) is compact, hence closed in XX. Since χ\chi is trivial on Ker⁡φ\operatorname{Ker}\varphi, the map ψ0:Y→T\psi_0:Y\to\mathbb{T}, ψ0(φ(x))=χ(x)\psi_0(\varphi(x))=\chi(x), is a well-defined homomorphism. It is continuous: for every closed set C⊆TC\subseteq\mathbb{T}, ψ0−1(C)=φ(χ−1(C))\psi_0^{-1}(C)=\varphi(\chi^{-1}(C)) is the image of a compact set, hence closed. By [22 Corollary of Theorem 27], ψ0\psi_0 extends to a character ψ\psi of XX, and φ^(ψ)=ψ∘φ=χ\widehat{\varphi}(\psi)=\psi\circ\varphi=\chi.

Applying Lemma 5 to φ=Fn\varphi=F^n and using Fn^=F^ n\widehat{F^n}=\widehat{F}^{\,n}, Lemma 4 gives

K(F)⊥=⋂n≥0Ker⁡(Fn)⊥=⋂n≥0Im⁡(F^ n).(2)\mathcal{K}(F)^\perp=\bigcap_{n\geq0}\operatorname{Ker}(F^n)^\perp=\bigcap_{n\geq0}\operatorname{Im}(\widehat{F}^{\,n}). \tag*{(2)}

Lemma 6. For every subgroup H≤XH\leq X, H‾=X\overline{H}=X if and only if H⊥={1}H^\perp=\{1\}.

Proof. If H‾=X\overline{H}=X and χ∈H⊥\chi\in H^\perp, then χ\chi is identically 11 on XX by continuity. Conversely, let A=H‾⊥A=\overline{H}^{\perp}. By [22 Proposition 38], H‾\overline{H} is the annihilator of AA in XX, i.e., H‾={x∈X:χ(x)=1 for every χ∈A}\overline{H}=\{x\in X:\chi(x)=1\text{ for every }\chi\in A\}. If H‾≠X\overline{H}\ne X, then A≠{1}A\ne\{1\}; since H⊥=H‾⊥H^\perp=\overline{H}^\perp by continuity, H⊥≠{1}H^\perp\ne\{1\}.

Theorem 4. The following conditions are equivalent:

  1. K(F)‾=X\overline{K(F)}=X;

  1. ⋂n≥0Im⁡(F^n)={1}\bigcap_{n\geq0}\operatorname{Im}(\widehat{F}^{n})=\{1\}.

Proof. By Equation (2) and Lemma 6.

Let Λ\Lambda be an abelian group and ψ:Λ→Λ\psi:\Lambda\to\Lambda an endomorphism. The set of infinitely ψ\psi-divisible elements is

Div⁡∞(ψ)={m∈Λ: for every n≥0 there is xn∈Λ with m=ψn(xn)}=⋂n≥0Im⁡(ψn).\operatorname{Div}_{\infty}(\psi)=\{m\in\Lambda:\text{ for every }n\geq0\text{ there is }x_n\in\Lambda\text{ with }m=\psi^n(x_n)\}=\bigcap_{n\geq0}\operatorname{Im}(\psi^n).

By Theorem 4 applied with ψ=F^\psi=\widehat{F},

K(F)‾=X⟺Div⁡∞(F^)={1},\overline{K(F)}=X\quad\Longleftrightarrow\quad\operatorname{Div}_{\infty}(\widehat{F})=\{1\},

that is, K(F)K(F) is dense if and only if there are no non-trivial infinitely F^\widehat{F}-divisible elements.

Corollary 2. FF is strongly transitive if and only if F^\widehat{F} is injective and Div⁡∞(F^)={1}\operatorname{Div}_{\infty}(\widehat{F})=\{1\}.

Proof. A character χ\chi satisfies F^(χ)=χ∘F=1\widehat{F}(\chi)=\chi\circ F=1 if and only if χ\chi annihilates F(X)F(X); thus Ker⁡(F^)=F(X)⊥\operatorname{Ker}(\widehat{F})=F(X)^{\perp}. Since F(X)F(X) is compact, hence closed, Lemma 6 gives that FF is surjective if and only if F^\widehat{F} is injective. The claim follows from Lemma 3 and Theorem 4.

The eventual image of a matrix

Throughout this subsection LL is a noetherian integrally closed domain and K=Frac⁡(L)K=\operatorname{Frac}(L); for M∈Mn(L)M\in M_n(L) we let χM(t)=det⁡(tI−M)\chi_M(t)=\det(tI-M), and MM acts on LnL^n (resp. KnK^n) by left multiplication. We shall use the following facts.

(F1) If f∈L[t]f\in L[t] is monic and f=ghf=gh with g,h∈K[t]g,h\in K[t] monic, then g,h∈L[t]g,h\in L[t] [3 Chapter 5, Exercise 8(i)]. In particular g(0)h(0)=f(0)g(0)h(0)=f(0) in LL, so that g(0)g(0) is a unit of LL whenever f(0)f(0) is.

(F2) The multiplication by M∈Mn(L)M\in M_n(L) is injective on LnL^n if and only if det⁡(M)≠0\det(M)\ne0. Indeed, if det⁡(M)≠0\det(M)\ne0, then adj⁡(M)M=det⁡(M)I\operatorname{adj}(M)M=\det(M)I shows injectivity, LL being a domain; if det⁡(M)=0\det(M)=0, there is 0≠v∈Kn0\ne v\in K^n with Mv=0Mv=0, and multiplying vv by a common denominator of its entries gives a non-zero element of the kernel in LnL^n.

Theorem 5. Let M∈Mn(L)M\in M_n(L) with det⁡(M)≠0\det(M)\ne0, and let

N=⋂k≥0Im⁡(Mk)⊆Ln.N=\bigcap_{k\geq0}\operatorname{Im}(M^k)\subseteq L^n.

Then N≠{0}N\ne\{0\} if and only if χM\chi_M has a monic irreducible factor g∈K[t]g\in K[t] such that g(0)g(0) is a unit of LL.

Proof. Recall that every monic factor of χM\chi_M in K[t]K[t] belongs to L[t]L[t] by (F1).

(⇒)(\Rightarrow) Assume that N≠{0}N\ne\{0\}.

MM restricts to an automorphism of NN. By (F2), MM is injective on LnL^n. If x∈Nx\in N, then Mx∈Im⁡(Mk+1)⊆Im⁡(Mk)Mx\in\operatorname{Im}(M^{k+1})\subseteq\operatorname{Im}(M^k) for every kk, so Mx∈NMx\in N. Conversely, let x∈Nx\in N; for every k≥0k\geq0 write x=Mk+1zkx=M^{k+1}z_k with zk∈Lnz_k\in L^n, and put yk=Mkzky_k=M^kz_k. Then Myk=xMy_k=x for every kk, so by injectivity y:=y0=yk∈Im⁡(Mk)y := y_0 = y_k \in\operatorname{Im}(M^k) for every kk, i.e., y∈Ny \in N and My=xMy = x. Hence M′:N→NM': N \to N, M′(x)=MxM'(x) = Mx, is a bijective LL-linear map.

The subspace WW. Regard LnL^n as a subset of KnK^n, and let W⊆KnW \subseteq K^n be the KK-span of NN. Since N≠{0}N \ne\{0\}, r=dim⁡KW≥1r = \dim_K W \ge1. Since MN⊆NMN \subseteq N, we have MW⊆WMW \subseteq W; let φ:W→W\varphi: W \to W be the restriction of the multiplication by MM. Since φ(W)\varphi(W) is spanned by M′(N)=NM'(N) = N, φ\varphi is surjective, hence invertible, and φ−1\varphi^{-1} extends M′−1M'^{-1}.

χφ∈L[t]\chi_\varphi\in L[t] and det⁡(φ)\det(\varphi) is a unit of LL. Since LL is noetherian, N⊆LnN \subseteq L^n is finitely generated. The maps M′M' and M′−1M'^{-1} are LL-linear endomorphisms of NN, so by [3 Proposition 2.4] each of them is annihilated by a monic polynomial with coefficients in LL. Since WW is spanned by NN, the same polynomials annihilate φ\varphi and φ−1\varphi^{-1}, respectively. Hence every eigenvalue λ\lambda of φ\varphi in an algebraic closure K‾\overline{K} of KK is integral over LL, and so is λ−1\lambda^{-1}, which is an eigenvalue of φ−1\varphi^{-1}. The coefficients of χφ\chi_\varphi, as well as det⁡(φ)\det(\varphi) and det⁡(φ)−1\det(\varphi)^{-1}, are polynomial expressions in such eigenvalues, hence elements of KK integral over LL [3 Corollary 5.3]. Since LL is integrally closed, χφ∈L[t]\chi_\varphi\in L[t] and det⁡(φ)\det(\varphi) is a unit of LL.

Conclusion. Completing a basis of WW to a basis of KnK^n, the multiplication by MM is represented by a block upper triangular matrix whose upper left block represents φ\varphi; hence χφ\chi_\varphi divides χM\chi_M in K[t]K[t]. Let gg be a monic irreducible factor of χφ\chi_\varphi in K[t]K[t]; then gg divides χM\chi_M. Since χφ(0)=(−1)rdet⁡(φ)\chi_\varphi(0) = (-1)^r \det(\varphi) is a unit of LL, g(0)g(0) is a unit of LL by (F1), applied to f=χφf = \chi_\varphi.

(⇐)(\Leftarrow) Let gg be a monic irreducible factor of χM\chi_M with g(0)g(0) a unit of LL, and let e≥1e \ge1 be its multiplicity in χM\chi_M. Since gg divides χM\chi_M, gg has a root which is an eigenvalue of MM, so that g(M)g(M), and hence g(M)eg(M)^e, is not injective on KnK^n; thus Wg=Ker⁡(g(M)e)⊆KnW_g = \operatorname{Ker}(g(M)^e) \subseteq K^n is a non-zero KK-subspace, and MWg⊆WgMW_g \subseteq W_g. By (F1), g∈L[t]g \in L[t], so we can write g(t)e=tq(t)+cg(t)^e = tq(t) + c with q∈L[t]q \in L[t] and c=g(0)ec = g(0)^e a unit of LL. On WgW_g we have Mq(M)=−c id⁡Mq(M) = -c\,\operatorname{id}, that is, the restriction of MM to WgW_g is invertible with inverse the restriction of B=−c−1q(M)∈Mn(L)B = -c^{-1}q(M) \in M_n(L). Let v∈Wg∩Lnv \in W_g \cap L^n be non-zero; it exists, since a non-zero element of WgW_g multiplied by a common denominator of its entries lies in Wg∩LnW_g \cap L^n. For every k≥0k \ge0, since BB is a polynomial in MM and MWg⊆WgMW_g \subseteq W_g, Bkv∈Ln∩WgB^k v \in L^n \cap W_g and Mk(Bkv)=vM^k(B^k v) = v. Hence v∈Im⁡(Mk)v \in\operatorname{Im}(M^k) for every kk, i.e., 0≠v∈N0 \ne v \in N. □

Characterization of strongly transitive linear GCAs

Let σ:Lp→Lp\sigma: L_p \to L_p be the ring automorphism defined by σ(xi)=xi−1\sigma(x_i) = x_i^{-1} for 1≤i≤d1 \le i \le d; it extends to an automorphism of KpK_p, and, acting on coefficients, to automorphisms of Mn(Lp)M_n(L_p) and of Kp[t]K_p[t] fixing tt. For A∈Mn(Lp)A \in M_n(L_p) let A∗=σ(A)TA^* = \sigma(A)^T; note that (AB)∗=B∗A∗(AB)^* = B^*A^*, so (Ak)∗=(A∗)k(A^k)^* = (A^*)^k.

Let ω=e2πi/p\omega= e^{2\pi i/p}. For a=∑vavxv∈Lpna = \sum_v a_v x^v \in L_p^n, with av∈Fpna_v \in\mathbb{F}_p^n and finitely many av≠0a_v \ne0, let χa:(Fpn)Zd→T\chi_a : (\mathbb{F}_p^n)^{\mathbb{Z}^d} \to\mathbb{T} be defined by χa(c)=ω∑vav⋅cv\chi_a(c) = \omega^{\sum_v a_v \cdot c_v}, where av⋅cva_v \cdot c_v is the standard scalar product of Fpn\mathbb{F}_p^n.

Lemma 7. The map a↦χaa \mapsto\chi_a is an isomorphism from the additive group LpnL_p^n onto (Fpn)Zd(\mathbb{F}_p^n)^{\mathbb{Z}^d}. For every A∈Mn(Lp)A \in M_n(L_p) we have FA^(χa)=χA∗a\widehat{F_A}(\chi_a) = \chi_{A^*a}.

Proof. Clearly χa\chi_a is a continuous character and χa+b=χaχb\chi_{a+b} = \chi_a\chi_b. Let χ\chi be a continuous character. Since (Fpn)Zd(\mathbb{F}_p^n)^{\mathbb{Z}^d} has exponent pp, χ\chi takes values in the finite, hence discrete, subgroup {ωs:s∈Fp}\{\omega^s : s \in\mathbb{F}_p\} of T\mathbb{T}, so its kernel is open and contains all the configurations vanishing on some finite set S⊆ZdS \subseteq\mathbb{Z}^d. Hence χ(c)\chi(c) depends only on c∣Sc|_S, and since every character of Fpn\mathbb{F}_p^n has the form g↦ωb⋅gg \mapsto\omega^{b\cdot g} for a unique b∈Fpnb \in\mathbb{F}_p^n, we get χ=χa\chi= \chi_a for a unique a∈Lpna \in L_p^n. For the second claim, write A=∑uAux−uA = \sum_u A_u x^{-u}, so that FA(c)v=∑uAucv+uF_A(c)_v = \sum_u A_u c_{v+u}. Then

∑vav⋅FA(c)v=∑w(∑uAuTaw−u)⋅cw,\sum_v a_v \cdot F_A(c)_v = \sum_w \left(\sum_u A_u^T a_{w-u}\right)\cdot c_w,

and ∑w(∑uAuTaw−u)xw=(∑uAuTxu)a=A∗a\sum_w \left(\sum_u A_u^T a_{w-u}\right)x^w = \left(\sum_u A_u^T x^u\right)a = A^*a.

Here we reprove the well known (see [19]) characterization of surjectivity for linear cellular automata.

Corollary 3. Let A∈Mn(Lp)A \in M_n(\mathbb{L}_p). Then FAF_A is surjective if and only if det⁡(A)≠0\det(A) \ne0.

Proof. By the proof of Corollary 2, FAF_A is surjective if and only if F^A\widehat{F}_A is injective, that is, by Lemma 7, if and only if the multiplication by A∗A^* is injective on Lpn\mathbb{L}_p^n. By (F2), this holds if and only if det⁡(A∗)=σ(det⁡(A))≠0\det(A^*) = \sigma(\det(A)) \ne0, i.e., det⁡(A)≠0\det(A) \ne0.

Theorem 6. Let A∈Mn(Lp)A \in M_n(\mathbb{L}_p), with characteristic polynomial χA(t)=det⁡(tI−A)\chi_A(t) = \det(tI-A). Then FAF_A is strongly transitive if and only if det⁡(A)≠0\det(A) \ne0 and, for every monic irreducible factor gg of χA\chi_A in Kp[t]\mathbb{K}_p[t], g(0)g(0) is not a unit of Lp\mathbb{L}_p.

Proof. Recall that Lp\mathbb{L}_p is a noetherian integrally closed domain, so that (F1), (F2) and Theorem 5 apply with L=LpL = \mathbb{L}_p. By Corollary 2 and Lemma 7, under which F^Ak=F^Ak\widehat{F}_A^k = \widehat{F}_{A^k} corresponds to the multiplication by (A∗)k(A^*)^k, FAF_A is strongly transitive if and only if the multiplication by A∗A^* is injective on Lpn\mathbb{L}_p^n and ⋂k≥0Im⁡((A∗)k)={0}\bigcap_{k\ge0}\operatorname{Im}((A^*)^k) = \{0\}. By (F2), the first condition is equivalent to det⁡(A∗)=σ(det⁡(A))≠0\det(A^*) = \sigma(\det(A)) \ne0, i.e., to det⁡(A)≠0\det(A) \ne0. Assume det⁡(A)≠0\det(A) \ne0. By Theorem 5, the second condition holds if and only if no monic irreducible factor of χA∗\chi_{A^*} has a unit constant term. Now χA∗(t)=det⁡(tI−σ(A)T)=σ(χA)(t)\chi_{A^*}(t) = \det(tI-\sigma(A)^T) = \sigma(\chi_A)(t), and σ\sigma is a ring automorphism of Kp[t]\mathbb{K}_p[t] preserving Lp\mathbb{L}_p and its units; hence the monic irreducible factors of χA∗\chi_{A^*} are the polynomials σ(g)\sigma(g), with gg a monic irreducible factor of χA\chi_A, and σ(g)(0)=σ(g(0))\sigma(g)(0) = \sigma(g(0)) is a unit if and only if g(0)g(0) is.

Corollary 4. Let F\mathcal{F} be a dd-GCA over a finite group GG. Then F\mathcal{F} is strongly transitive if and only if GG is abelian and, denoting by {(F1,G1),…,(Fq,Gq)}\{(\mathcal{F}_1,G_1),\ldots,(\mathcal{F}_q,G_q)\} the output of PowerDecomp on (F,G)(\mathcal{F},G), for every ii with Gi≠{e}G_i \ne\{e\} the following holds: Gi≅FpiniG_i \cong\mathbb{F}_{p_i}^{n_i}, and the matrix Ai∈Mni(Lpi)A_i \in M_{n_i}(\mathbb{L}_{p_i}) of the GCA on Fpini\mathbb{F}_{p_i}^{n_i} corresponding to Fi\mathcal{F}_i under such an isomorphism satisfies det⁡(Ai)≠0\det(A_i) \ne0, and g(0)g(0) is not a unit of Lpi\mathbb{L}_{p_i} for every monic irreducible factor gg of χAi\chi_{A_i} in Kpi[t]\mathbb{K}_{p_i}[t].

Proof. If GG is non-abelian, F\mathcal{F} is not strongly transitive by Theorem 2. Let GG be abelian. By Corollary 1, F\mathcal{F} is strongly transitive if and only if every Fi\mathcal{F}_i is. If Gi={e}G_i = \{e\} (which happens only if G={e}G = \{e\}), then GiZdG_i^{\mathbb{Z}^d} is a singleton and Fi\mathcal{F}_i is strongly transitive. Otherwise Gi≅FpiniG_i \cong\mathbb{F}_{p_i}^{n_i} with ni≥1n_i \ge1; an isomorphism ψ:Gi→Fpini\psi:G_i \to\mathbb{F}_{p_i}^{n_i} induces, cell by cell, a homeomorphism Ψ:GiZd→(Fpini)Zd\Psi:G_i^{\mathbb{Z}^d} \to(\mathbb{F}_{p_i}^{n_i})^{\mathbb{Z}^d} conjugating Fi\mathcal{F}_i to the GCA FAi=Ψ∘Fi∘Ψ−1F_{A_i} = \Psi\circ\mathcal{F}_i \circ\Psi^{-1}. By Theorem 1, applied to Ψ\Psi and to Ψ−1\Psi^{-1}, Fi\mathcal{F}_i is strongly transitive if and only if FAiF_{A_i} is, and the latter is characterized by Theorem 6.

Corollary 5. For every fixed d≥1d \ge1, strong transitivity is decidable for dd-GCAs over finite groups: there is an algorithm which, given a finite group GG by its multiplication table and the local rule of a dd-GCA F\mathcal{F} on GG, decides whether F\mathcal{F} is strongly transitive.

Proof. Whether GG is abelian is decided from its multiplication table; if it is not, the answer is negative by Corollary 4. Otherwise, the output of PowerDecomp on (F,G)(\mathcal{F},G) is computable, since power subgroups and quotients are computed from the multiplication

table. For every Gi≠{e}G_i \ne\{e\}, an isomorphism Gi≅FpiniG_i \cong\mathbb{F}_{p_i}^{n_i} is found by exhaustive search, and the matrix AiA_i is computed from the local rule of FiF_i. The determinant and the characteristic polynomial of AiA_i are computed in LpiL_{p_i} and Lpi[t]L_{p_i}[t]. Multiplying χAi\chi_{A_i} by a suitable monomial xwx^w yields a polynomial in Fpi[x1,…,xd,t]\mathbb{F}_{p_i}[x_1,\ldots,x_d,t], whose factorization into irreducibles is effectively computable [20, 23]; by Gauss’s lemma, this factorization yields the monic irreducible factors of χAi\chi_{A_i} in Kpi[t]K_{p_i}[t]. Finally, an element of LpiL_{p_i} is a unit if and only if it is a single monomial axua x^u with a≠0a \ne0, which is checked directly. By Corollary 4, these computations decide whether F\mathcal{F} is strongly transitive. An explicit procedure, together with a bound on its cost, is given in § 6.

Computational complexity

In this section we give an explicit decision procedure for strong transitivity and bound its cost. By Theorem 2, a GCA over a non-abelian group is never strongly transitive; hence only GCAs over abelian groups need to be decomposed, and for them we use the procedure PowerDecomp.

Input and cost model. The group GG, of order NN, is given by its multiplication table. The dd-GCA F\mathcal{F} is given by the tables of the endomorphisms h1,…,hkh_1,\ldots,h_k of its local rule and by its neighbourhood Vf={v1,…,vk}⊆ZdV_f=\{v_1,\ldots,v_k\}\subseteq\mathbb{Z}^d. Let ϱ=max⁡j∥vj∥∞\varrho=\max_j\|v_j\|_\infty, where ∥u∥∞=max⁡h∣uh∣\|u\|_\infty=\max_h|u_h| for u∈Zdu\in\mathbb{Z}^d. We express the running-time bound in terms of the parameters NN, kk, dd, and ϱ\varrho. We count as one operation a lookup in a table, an arithmetic operation in Fp\mathbb{F}_p, and an addition or comparison of integers.

The decision procedure. The decision procedure IsST is given in Algorithm 2: it rejects non-abelian alphabets, decomposes abelian ones by PowerDecomp (Algorithm 1), and applies to every component the function AbelianTest described below.

Algorithm 2: Testing whether a GCA is strongly transitive

Input: A GCA $(\mathcal{F},G)$
Output: true if $(\mathcal{F},G)$ is strongly transitive, false otherwise
Function IsST$(\mathcal{F},G)$:
    if $G$ is non-abelian then
        return false;
    if $G=\{e\}$ then
        return true;
    $A=$PowerDecomp$(\mathcal{F},G)$;
    foreach $(\mathcal{F}_i,G_i)\in A$ do
        if not AbelianTest$(\mathcal{F}_i,G_i)$ then
            return false;
    return true;

The function AbelianTest, applied to a GCA F\mathcal{F} over G≅FpnG\cong\mathbb{F}_p^n, computes an isomorphism G≅FpnG\cong\mathbb{F}_p^n, the matrix A∈Mn(Lp)A\in M_n(L_p) of the corresponding GCA on Fpn\mathbb{F}_p^n, and the polynomial χA\chi_A; it returns true if and only if det⁡(A)≠0\det(A)\ne0 and no monic irreducible factor of χA\chi_A in Kp[t]K_p[t] has a unit constant term.

Lemma 8. IsST terminates on every input (F,G)(\mathcal{F},G), and it returns true if and only if F\mathcal{F} is strongly transitive.

Proof. PowerDecomp terminates (see the discussion after its definition), and so does IsST. If GG is non-abelian, F\mathcal{F} is not strongly transitive by Theorem 2. If G={e}G=\{e\}, GZdG^{\mathbb{Z}^d} is a singleton and F\mathcal{F} is strongly transitive. Otherwise every GiG_i in the output of PowerDecomp satisfies Gi≅FpiniG_i\cong\mathbb{F}_{p_i}^{n_i} with ni≥1n_i\ge1, and the claim follows from Corollary 1, Theorem 6 and the conjugation argument in the proof of Corollary 4.

Lemma 9. Let G≅FpnG\cong\mathbb{F}_p^n be given by its multiplication table, with M=∣G∣=pnM=|G|=p^n, and let h1,…,hkh_1,\ldots,h_k be endomorphisms of GG, given by their tables. One can compute pp, a basis g1,…,gng_1,\ldots,g_n of GG over Fp\mathbb{F}_p, a table of the coordinates of all the elements of GG in this basis, and the matrices in Mn(Fp)M_n(\mathbb{F}_p) of h1,…,hkh_1,\ldots,h_k in this basis, in O(Mlog⁡M+kM)O(M\log M+kM) operations.

Proof. The prime pp is the order of any element g≠eg\ne e, computed in O(p)⊆O(M)O(p)\subseteq O(M) operations. Let V0={e}V_0=\{e\}. Given the span ViV_i of g1,…,gig_1,\ldots,g_i, together with the coordinates of its elements, choose gi+1∉Vig_{i+1}\notin V_i by scanning GG with a membership array. Then Vi+1=⋃a∈Fpgi+1aViV_{i+1}=\bigcup_{a\in\mathbb{F}_p}g_{i+1}^aV_i, and the coordinates of its elements are obtained from those of ViV_i, in O(n∣Vi+1∣+M)O(n|V_{i+1}|+M) operations. Since ∣Vi+1∣=pi+1|V_{i+1}|=p^{i+1} and n≤log⁡2Mn\le\log_2M, the whole construction costs O(nM)=O(Mlog⁡M)O(nM)=O(M\log M). The jj-th column of the matrix of hlh_l is the coordinate vector of hl(gj)h_l(g_j), read from the tables in O(n)O(n) operations. Reading the kk tables costs O(kM)O(kM), which dominates the O(kn2)O(kn^2) operations needed to fill the matrices.

The test of commutativity. Testing whether GG is abelian costs O(N2)O(N^2) operations, and it is performed only once.

Size of the recursion tree of PowerDecomp. At every internal node the group GG is split into two non-trivial groups HH and G/HG/H with ∣H∣∣G/H∣=∣G∣|H||G/H|=|G|. Hence the orders of the groups attached to the leaves multiply to at most NN, the tree has at most log⁡2N\log_2N leaves and at most 2log⁡2N2\log_2N nodes, and its depth is at most log⁡2N\log_2N. Moreover, the orders of the groups attached to the nodes at a fixed depth multiply to at most NN.

Cost at an internal node. Let M=∣G∣M=|G|. A prime divisor pp of MM is found in O(M)O(\sqrt{M}) operations, and the powers gpg^p, g∈Gg\in G, in O(Mlog⁡p)O(M\log p) operations by repeated squaring; they give both the subgroup GpG^p and the test of whether GG is an elementary abelian pp-group, i.e., whether MM is a power of pp and gp=eg^p=e for every g∈Gg\in G. Building the multiplication tables of HH and G/HG/H costs O(M2)O(M^2), and the tables of the restrictions hj∣Hh_j|_H and of the induced endomorphisms [g]↦[hj(g)][g]\mapsto[h_j(g)] of G/HG/H cost O(kM)O(kM); the neighborhood does not change. Since the orders at a fixed depth multiply to at most NN, the sum of M2+kMM^2+kM over the nodes at a fixed depth is at most N2+kNN^2+kN, and all the internal nodes together cost

O((N2+kN)log⁡N).O\bigl((N^2+kN)\log N\bigr).

Cost at a leaf. At a leaf, AbelianTest is called on G≅FpnG\cong\mathbb{F}_p^n, with M=∣G∣=pnM=|G|=p^n and n≤log⁡2Mn\le\log_2M. By Lemma 9, the matrices A1,…,Ak∈Mn(Fp)A_1,\ldots,A_k\in M_n(\mathbb{F}_p) of h1,…,hkh_1,\ldots,h_k are computed in O(Mlog⁡M+kM)O(M\log M+kM) operations, and A=∑jAjx−vjA=\sum_jA_jx^{-v_j} in O(kn2d)O(kn^{2d}) operations. The polynomial χA\chi_A is computed by Berkowitz’s division-free algorithm [5], which uses O(n4)O(n^4) operations in Lp\mathbb{L}_p. All the intermediate quantities are polynomials of degree at most nn in the entries of AA, hence Laurent polynomials with exponents in [−nϱ,nϱ]d[-n\varrho,n\varrho]^d; each of them has at most (2nϱ+1)d(2n\varrho+1)^d monomials, and each operation in Lp\mathbb{L}_p costs O(d(2nϱ+1)2d)O(d(2n\varrho+1)^{2d}). Then det⁡(A)=(−1)nχA(0)\det(A)=(-1)^n\chi_A(0).

If det⁡(A)≠0\det(A)\ne0, let w=(nϱ,…,nϱ)∈Zdw=(n\varrho,\ldots,n\varrho)\in\mathbb{Z}^d and P=xwχAP=x^w\chi_A. Then P∈Fp[x1,…,xd,t]P\in\mathbb{F}_p[x_1,\ldots,x_d,t], with deg⁡tP=n\deg_tP=n and deg⁡xhP≤2nϱ\deg_{x_h}P\le2n\varrho for every hh. Let Tfact(p,n,nϱ,d)T_{\mathrm{fact}}(p,n,n\varrho,d) be the cost of factoring such a polynomial into irreducibles. By Gauss’s lemma, the irreducible factors of PP of positive degree in tt have monomial leading coefficients in tt, since they divide the leading coefficient xwx^{w} of PP; dividing them by these coefficients yields the monic irreducible factors of χA\chi_A in Kp[t]\mathbb{K}_p[t]. Testing whether the constant term of each factor is a single monomial, i.e., a unit of LpL_p, costs time linear in the size of the factorization.

Overall complexity. Let M1,…,MqM_1,\ldots,M_q be the orders of the groups at the leaves of PowerDecomp, and ni=log⁡piMin_i=\log_{p_i} M_i. Since ∏iMi≤N\prod_i M_i\leq N and Mi≥2M_i\geq2, we have ∑iMilog⁡Mi≤Nlog⁡N\sum_i M_i\log M_i\leq N\log N and ∑ini≤log⁡2N\sum_i n_i\leq\log_2 N; hence

∑ini4(2niϱ+1)2d≤(log⁡2N)4(2ϱlog⁡2N+1)2d.\sum_i n_i^4(2n_i\varrho+1)^{2d}\leq(\log_2 N)^4(2\varrho\log_2 N+1)^{2d}.

Adding the costs of the internal nodes and of the leaves, we obtain the following result.

Theorem 7. Let F\mathcal{F} be a dd-GCA over a group of order NN, with kk neighbors and ϱ=max⁡j∥vj∥∞\varrho=\max_j\lVert v_j\rVert_\infty. The procedure IsST decides whether F\mathcal{F} is strongly transitive using

O((N2+kN)log⁡N+kd(log⁡N)2+d(log⁡N)4(2ϱlog⁡2N+1)2d)O\left((N^2+kN)\log N+kd(\log N)^2+d(\log N)^4(2\varrho\log_2 N+1)^{2d}\right)

operations, plus the cost of factoring at most log⁡2N\log_2 N polynomials Pi∈Fpi[x1,…,xd,t]P_i\in\mathbb{F}_{p_i}[x_1,\ldots,x_d,t] with deg⁡tPi=ni\deg_t P_i=n_i and deg⁡xhPi≤2niϱ\deg_{x_h}P_i\leq2n_i\varrho, where ∑ini≤log⁡2N\sum_i n_i\leq\log_2 N.

By [20], a polynomial over a finite field Fpi\mathbb{F}_{p_i} can be factored in time polynomial in its degrees and in the field size pip_i. For each polynomial PiP_i, we have deg⁡tPi=ni\deg_t P_i=n_i and deg⁡xhPi≤2niϱ\deg_{x_h}P_i\leq2n_i\varrho for every hh. Hence, for fixed dd, its dense representation has at most

(ni+1)(2niϱ+1)d(n_i+1)(2n_i\varrho+1)^d

coefficients. Since ni≤log⁡2Nn_i\leq\log_2 N and pi≤Np_i\leq N, factoring all at most log⁡2N\log_2 N polynomials takes time polynomial in NN and ϱ\varrho, for fixed dd. Consequently, including the factorization step, IsST runs in time polynomial in NN, kk, and ϱ\varrho for every fixed dimension dd.

Conclusions

We have shown that strong transitivity is decidable for group cellular automata over every finite group and in every dimension. GCAs over non-abelian groups are never strongly transitive, and for GCAs over abelian groups the decision reduces, via a decomposition by power subgroups which preserves strong transitivity, to linear CAs over groups of the form (Z/pZ)n(\mathbb{Z}/p\mathbb{Z})^n. For these, strong transitivity is characterized by the absence of irreducible factors of the characteristic polynomial with an invertible constant term. Pontryagin duality is the key tool in this characterization: it turns strong transitivity into the triviality of the eventual image of the dual endomorphism, a purely algebraic condition. For every fixed dimension dd, the resulting decision procedure runs in time polynomial in the group size N=∣G∣N=|G|, the number kk of neighbours, and the neighbourhood radius ϱ\varrho, including the factorization step.

Several questions remain open.

  • The cost of our procedure is dominated, for large neighbourhoods, by the computation and the factorization of the characteristic polynomials. It would be interesting to know whether the existence of an irreducible factor with an invertible constant term can be decided without computing a complete factorization.

  • Strong transitivity of GCAs could be studied on group shifts, i.e., closed shift-invariant subgroups of GZdG^{\mathbb{Z}^d}, instead of the full shift, as well as for CAs on more general amenable groups than Zd\mathbb{Z}^d.

  • Finally, it would be interesting to extend our results to CAs over finite monoids, and to other dynamical properties related to strong transitivity, such as openness and the various notions of expansivity.

References

  1. [1]L. Acerbi, A. Dennunzio, and E. Formenti. Shifting and lifting of cellular automata. In S. B. Cooper, B. Löwe, and A. Sorbi, editors, Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18-23, 2007, Proceedings, volume 4497 of Lecture Notes in Computer Science, pages 1–10. Springer, 2007.
  2. [2]L. Acerbi, A. Dennunzio, and E. Formenti. Conservation of some dynamical properties for operations on cellular automata. Theoretical Computer Science, 410(38-40):3685–3693, 2009.DOI
  3. [3]M. F. Atiyah and I. G. Macdonald. Introduction to Commutative Algebra. Addison-Wesley Series in Mathematics. Addison-Wesley, Reading, MA, 1969.
  4. [4]P. Béaur and J. Kari. Effective projections on group shifts to decide properties of group cellular automata. Int. J. Found. Comput. Sci., 35(1&2):77–100, 2024.arxiv.org/abs/2301.11133
  5. [5]S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Information Processing Letters, 18(3):147–150, mar 1984.DOI
  6. [6]F. Blanchard, J. Cervelle, and E. Formenti. Some results about the chaotic behavior of cellular automata. Theoretical Computer Science, 349(3):318–336, 2005.DOI
  7. [7]N. Castronuovo, A. Dennunzio, and L. Margara. A divide and conquer algorithm for deciding group cellular automata dynamics. Journal of Computer and System Sciences, 157:103749, 2026.arxiv.org/abs/2507.09761
  8. [8]N. Castronuovo, A. Dennunzio, and L. Margara. Topological transitivity of group cellular automata is decidable, 2026. arXiv:2601.16243.arxiv.org/abs/2601.16243
  9. [9]G. Cattaneo, A. Dennunzio, and L. Margara. Solution of some conjectures about topological properties of linear cellular automata. Theoretical Computer Science, 325(2):249–271, 2004.DOI
  10. [10]T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin, 2010.
  11. [11]A. Dennunzio and E. Formenti. Decidable properties of 2D cellular automata. In M. Ito and M. Toyama, editors, Developments in Language Theory, 12th International Conference, DLT 2008, Kyoto, Japan, September 16–19, 2008, Proceedings, volume 5257 of Lecture Notes in Computer Science, pages 264–275, Berlin, Heidelberg, 2008. Springer.
  12. [12]A. Dennunzio, E. Formenti, D. Grinberg, and L. Margara. Additive cellular automata over finite abelian groups: Topological and measure theoretic properties. In 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, volume 138 of LIPIcs, pages 68:1–68:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.DOI
  13. [13]A. Dennunzio, E. Formenti, D. Grinberg, and L. Margara. Dynamical behavior of additive cellular automata over finite abelian groups. Theoretical Computer Science, 843:45–56, 2020.DOI
  14. [14]A. Dennunzio, E. Formenti, and L. Margara. An easy to check characterization of positive expansivity for additive cellular automata over a finite abelian group. IEEE Access, 11:121246–121255, 2023.DOI
  15. [15]A. Dennunzio, E. Formenti, and L. Margara. On the dynamical behavior of cellular automata on finite groups. IEEE Access, 12:122061–122077, 2024.DOI
  16. [16]A. Dennunzio, E. Formenti, and M. Weiss. Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues. Theoretical Computer Science, 516:40–59, 2014.DOI
  17. [17]E. Hewitt and K. A. Ross. Abstract Harmonic Analysis I. Number 115 in Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1963.
  18. [18]J. Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334(1-3):3–33, 2005.DOI
  19. [19]L. Le Bruyn and M. Van den Bergh. Algebraic properties of linear cellular automata. Linear Algebra and its Applications, 157:217–234, 1991.DOI
  20. [20]A. Lenstra. Factoring multivariate polynomials over finite fields. Journal of Computer and System Sciences, 30(2):235–248, 1985.
  21. [21]G. Manzini and L. Margara. A complete and efficiently computable topological classification of d-dimensional linear cellular automata over Z_m. Theoretical Computer Science, 221(1–2):157–177, 1999.
  22. [22]S. A. Morris. Pontryagin Duality and the Structure of Locally Compact Abelian Groups, volume 29 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1977.DOI
  23. [23]J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, 3rd edition, 2013.

Paper details

vlnc:W_2328tn6w
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents