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 . 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 we use Pontryagin duality to characterize strong transitivity in terms of the characteristic polynomial of the associated matrix of Laurent polynomials: the automaton is strongly transitive if and only if and no irreducible factor of 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 , we give an explicit decision procedure whose running time is polynomial in the group size , the number of neighbours, and the neighbourhood radius .
Introduction
Cellular automata (CAs) are discrete-time dynamical systems defined by the synchronous application of a local rule on a regular lattice 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 of a compact metric space is strongly transitive if for every non-empty open set , that is, if every point of 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 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 and whose global map is an endomorphism of the group . GCAs generalize linear CAs over , 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 , 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 . We point out that similar decompositions are used in [7] and in [8].
For a linear CA over with matrix of Laurent polynomials in variables, we prove that strong transitivity holds if and only if and no monic irreducible factor of the characteristic polynomial 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 , runs in time polynomial in the group size , the number of neighbours, and the neighbourhood radius , including the cost of factoring at most 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 , 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 and let be a finite set. A configuration is an element of ; for and we write for the value of at , and for we write for the restriction of to . We endow with the prodiscrete topology, which makes it a compact metrizable space. For a finite set and , the cylinder
is clopen, and cylinders form a basis of the topology. For we let . Every non-empty open set contains a cylinder of the form . For , the shift is defined by . A (-dimensional) CA is a continuous map commuting with every shift. By the Curtis–Hedlund–Lyndon theorem, is given by a local rule and a set of pairwise distinct vectors, the neighborhood, via .
Let be a finite group with identity . Then is a compact group under the componentwise operation, with identity . A CA is a GCA if it is a group endomorphism of . In this case the local rule is a homomorphism , and for endomorphisms of with pairwise commuting images [15]; we write .
Strong transitivity
Definition 1. Let be a compact metric space. A continuous map is strongly transitive if for every non-empty open set ; equivalently, if is dense in for every .
If has at least two points, a strongly transitive map is surjective: if , then for every non-empty open set not containing .
Theorem 1. Let and be compact metric spaces, and let and be continuous. Assume that there is a continuous surjection with . If is strongly transitive, then is strongly transitive.
Proof. Let be non-empty and open, and let . Choose with . Since is non-empty and open and is strongly transitive, there are and with . Then . □
The following lemma generalizes [13 Lemma 15].
Lemma 1. Let be a -dimensional GCA over a finite group . Then is strongly transitive if and only if:
is surjective, and
for every and every there exists such that .
Moreover, if is strongly transitive, then for every there is such that for every .
Proof. The “only if” part follows from the definition and from the remark after Definition 1. Assume that (1) and (2) hold, and fix . For let be the least such that . Since , we have for every . Let ; then
Let and . Since is surjective, there is with . The set is the cylinder with ; by (1) there is with . Then and . This proves the “moreover” part, and, since every non-empty open set contains a cylinder , that 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 proved in [7].
For a group we denote by its center; note that .
Lemma 2. Let be a surjective -GCA over a finite group . Then .
Proof. For let . Let and suppose that for some . Choose with , and let be the configuration with and for . Since is normal, ; moreover, is trivial outside and . Thus and are distinct finite configurations with the same image, so is not pre-injective, and hence not surjective by the Garden of Eden theorem [10], a contradiction.
Theorem 2. Let be a -GCA over a finite non-abelian group . Then is neither strongly transitive nor positively expansive.
Proof. Assume that is strongly transitive. Then is surjective, and so is for every ; by Lemma 2, for every . Since is non-abelian, there is ; let , a non-empty open set disjoint from . Then for every , since otherwise some element of would lie in . This contradicts strong transitivity. For the second assertion, if it suffices to recall that every positively expansive CA is strongly transitive [6 Theorem 2], while for 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 be a finite group and let be a -GCA on with local rule . Let be a normal subgroup of such that ; this holds, for instance, if for every . For let , and for let be defined by . The maps
are well defined GCAs on and on , respectively: does not depend on the representative because with for every .
Proposition 1. Let be a normal subgroup of with . If and are strongly transitive, then is strongly transitive.
Proof. is surjective. (Notice that this same fact, when , has been proved in [7].) Let . Since is surjective, there is with , i.e., . Since is surjective, for some , and .
Condition (2) of Lemma 1. Let , , and . Let , where . Since is strongly transitive, there is with , that is, there are and with . The map is a continuous surjective endomorphism of the compact group , hence it is open by the open mapping theorem for compact groups [17 Theorem 5.29]. Thus is an open set containing , and it contains a cylinder with . The set is non-empty and open in ; since is strongly transitive, there are and with . Writing with , we get . By Lemma 1, is strongly transitive.
Power subgroups of abelian groups
From now on in this section is a finite abelian group. For a prime , a finite group is a -group if its order is a power of , and a finite abelian group is an elementary abelian -group if it is isomorphic to for some , equivalently if for every element . For an integer , the power subgroup is a subgroup of , since . Every endomorphism of satisfies ; in particular for every , so that , and the GCAs on and on are defined.
Theorem 3. Let be a -GCA over a finite abelian group , and let . Then is strongly transitive if and only if both on and on are strongly transitive.
Proof. Let . The “if” part is Proposition 1. Assume that is strongly transitive. is strongly transitive. The map , , is a continuous surjection with ; apply Theorem 1.
is strongly transitive. Let , and . Since the cylinders form a basis of the topology of , it suffices to find and with . Since , there are and with for and for . Since is strongly transitive, there are and with . Let , the power being taken in the group , i.e., cell by cell. Then , , and, since is an endomorphism, .
The decomposition
Whenever a recursive call is made, is non-trivial and not an elementary abelian -group, and is a prime divisor of ; let . 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)\}$
of has a non-trivial kernel, so ; and , since otherwise for every , i.e., would be an elementary abelian -group. Hence and , and PowerDecomp terminates. Since subgroups and quotients of abelian groups are abelian, it returns a finite family of -GCAs over abelian groups. If , the output is ; otherwise, by the stopping condition, every satisfies for some prime and some .
Corollary 1. Let be a -GCA over a finite abelian group , and let be the output of PowerDecomp (Algorithm 1) on . Then, for every , for some prime and some , and is strongly transitive if and only if every 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 , which are studied in § 5.
Linear GCAs over $(\mathbb{Z}/p\mathbb{Z})^n`
Throughout this section the dimension is arbitrary. By Corollary 1, it remains to characterize strong transitivity for GCAs over ; as we show below, these are exactly the linear CAs over .
Linear CAs and their matrices
Let be a prime, , the ring of Laurent polynomials in variables, and its field of fractions. For we write . The ring is a noetherian unique factorization domain, hence integrally closed, and its units are the elements with and . Every endomorphism of is -linear, so a GCA on has the form with . We associate with the matrix ; conversely, every defines in this way a GCA on . Identifying a finite configuration with , acts on finite configurations as the multiplication by , and . We say that is strongly transitive (resp. transitive) if is.
Strong transitivity via Pontryagin duality
For Pontryagin duality we refer to [22].
Let be a compact metrizable abelian group, written additively with identity , and let be a continuous endomorphism. Let
Lemma 3. is strongly transitive if and only if is surjective and .
Proof. Assume that is strongly transitive. Then is surjective (see the remark after Definition 1; if there is nothing to prove). For every non-empty open set there is with , i.e., ; hence is dense.
Conversely, assume that is surjective and is dense. Let be non-empty and open, let , and let be an open neighborhood of with and . For every the open set meets , so . The sets are open and increasing in , so by compactness for some . Let . Since is surjective, for some ; write with and . Then and . Hence .
Let be the Pontryagin dual of , the discrete abelian group of continuous homomorphisms , where is the circle group, written multiplicatively; is written multiplicatively, with identity the trivial character . Let , , be the dual endomorphism. For , the annihilator of is the subgroup
Lemma 4. For every family of subsets of , .
Proof. A character annihilates if and only if it annihilates each .
Lemma 5. For every continuous endomorphism , .
Proof. If , then is trivial on ; hence . Conversely, let . The subgroup is compact, hence closed in . Since is trivial on , the map , , is a well-defined homomorphism. It is continuous: for every closed set , is the image of a compact set, hence closed. By [22 Corollary of Theorem 27], extends to a character of , and .
Applying Lemma 5 to and using , Lemma 4 gives
Lemma 6. For every subgroup , if and only if .
Proof. If and , then is identically on by continuity. Conversely, let . By [22 Proposition 38], is the annihilator of in , i.e., . If , then ; since by continuity, .
Theorem 4. The following conditions are equivalent:
;
.
Proof. By Equation (2) and Lemma 6.
Let be an abelian group and an endomorphism. The set of infinitely -divisible elements is
By Theorem 4 applied with ,
that is, is dense if and only if there are no non-trivial infinitely -divisible elements.
Corollary 2. is strongly transitive if and only if is injective and .
Proof. A character satisfies if and only if annihilates ; thus . Since is compact, hence closed, Lemma 6 gives that is surjective if and only if is injective. The claim follows from Lemma 3 and Theorem 4.
The eventual image of a matrix
Throughout this subsection is a noetherian integrally closed domain and ; for we let , and acts on (resp. ) by left multiplication. We shall use the following facts.
(F1) If is monic and with monic, then [3 Chapter 5, Exercise 8(i)]. In particular in , so that is a unit of whenever is.
(F2) The multiplication by is injective on if and only if . Indeed, if , then shows injectivity, being a domain; if , there is with , and multiplying by a common denominator of its entries gives a non-zero element of the kernel in .
Theorem 5. Let with , and let
Then if and only if has a monic irreducible factor such that is a unit of .
Proof. Recall that every monic factor of in belongs to by (F1).
Assume that .
restricts to an automorphism of . By (F2), is injective on . If , then for every , so . Conversely, let ; for every write with , and put . Then for every , so by injectivity for every , i.e., and . Hence , , is a bijective -linear map.
The subspace . Regard as a subset of , and let be the -span of . Since , . Since , we have ; let be the restriction of the multiplication by . Since is spanned by , is surjective, hence invertible, and extends .
and is a unit of . Since is noetherian, is finitely generated. The maps and are -linear endomorphisms of , so by [3 Proposition 2.4] each of them is annihilated by a monic polynomial with coefficients in . Since is spanned by , the same polynomials annihilate and , respectively. Hence every eigenvalue of in an algebraic closure of is integral over , and so is , which is an eigenvalue of . The coefficients of , as well as and , are polynomial expressions in such eigenvalues, hence elements of integral over [3 Corollary 5.3]. Since is integrally closed, and is a unit of .
Conclusion. Completing a basis of to a basis of , the multiplication by is represented by a block upper triangular matrix whose upper left block represents ; hence divides in . Let be a monic irreducible factor of in ; then divides . Since is a unit of , is a unit of by (F1), applied to .
Let be a monic irreducible factor of with a unit of , and let be its multiplicity in . Since divides , has a root which is an eigenvalue of , so that , and hence , is not injective on ; thus is a non-zero -subspace, and . By (F1), , so we can write with and a unit of . On we have , that is, the restriction of to is invertible with inverse the restriction of . Let be non-zero; it exists, since a non-zero element of multiplied by a common denominator of its entries lies in . For every , since is a polynomial in and , and . Hence for every , i.e., . □
Characterization of strongly transitive linear GCAs
Let be the ring automorphism defined by for ; it extends to an automorphism of , and, acting on coefficients, to automorphisms of and of fixing . For let ; note that , so .
Let . For , with and finitely many , let be defined by , where is the standard scalar product of .
Lemma 7. The map is an isomorphism from the additive group onto . For every we have .
Proof. Clearly is a continuous character and . Let be a continuous character. Since has exponent , takes values in the finite, hence discrete, subgroup of , so its kernel is open and contains all the configurations vanishing on some finite set . Hence depends only on , and since every character of has the form for a unique , we get for a unique . For the second claim, write , so that . Then
and .
Here we reprove the well known (see [19]) characterization of surjectivity for linear cellular automata.
Corollary 3. Let . Then is surjective if and only if .
Proof. By the proof of Corollary 2, is surjective if and only if is injective, that is, by Lemma 7, if and only if the multiplication by is injective on . By (F2), this holds if and only if , i.e., .
Theorem 6. Let , with characteristic polynomial . Then is strongly transitive if and only if and, for every monic irreducible factor of in , is not a unit of .
Proof. Recall that is a noetherian integrally closed domain, so that (F1), (F2) and Theorem 5 apply with . By Corollary 2 and Lemma 7, under which corresponds to the multiplication by , is strongly transitive if and only if the multiplication by is injective on and . By (F2), the first condition is equivalent to , i.e., to . Assume . By Theorem 5, the second condition holds if and only if no monic irreducible factor of has a unit constant term. Now , and is a ring automorphism of preserving and its units; hence the monic irreducible factors of are the polynomials , with a monic irreducible factor of , and is a unit if and only if is.
Corollary 4. Let be a -GCA over a finite group . Then is strongly transitive if and only if is abelian and, denoting by the output of PowerDecomp on , for every with the following holds: , and the matrix of the GCA on corresponding to under such an isomorphism satisfies , and is not a unit of for every monic irreducible factor of in .
Proof. If is non-abelian, is not strongly transitive by Theorem 2. Let be abelian. By Corollary 1, is strongly transitive if and only if every is. If (which happens only if ), then is a singleton and is strongly transitive. Otherwise with ; an isomorphism induces, cell by cell, a homeomorphism conjugating to the GCA . By Theorem 1, applied to and to , is strongly transitive if and only if is, and the latter is characterized by Theorem 6.
Corollary 5. For every fixed , strong transitivity is decidable for -GCAs over finite groups: there is an algorithm which, given a finite group by its multiplication table and the local rule of a -GCA on , decides whether is strongly transitive.
Proof. Whether 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 is computable, since power subgroups and quotients are computed from the multiplication
table. For every , an isomorphism is found by exhaustive search, and the matrix is computed from the local rule of . The determinant and the characteristic polynomial of are computed in and . Multiplying by a suitable monomial yields a polynomial in , whose factorization into irreducibles is effectively computable [20, 23]; by Gauss’s lemma, this factorization yields the monic irreducible factors of in . Finally, an element of is a unit if and only if it is a single monomial with , which is checked directly. By Corollary 4, these computations decide whether 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 , of order , is given by its multiplication table. The -GCA is given by the tables of the endomorphisms of its local rule and by its neighbourhood . Let , where for . We express the running-time bound in terms of the parameters , , , and . We count as one operation a lookup in a table, an arithmetic operation in , 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 over , computes an isomorphism , the matrix of the corresponding GCA on , and the polynomial ; it returns true if and only if and no monic irreducible factor of in has a unit constant term.
Lemma 8. IsST terminates on every input , and it returns true if and only if is strongly transitive.
Proof. PowerDecomp terminates (see the discussion after its definition), and so does IsST. If is non-abelian, is not strongly transitive by Theorem 2. If , is a singleton and is strongly transitive. Otherwise every in the output of PowerDecomp satisfies with , and the claim follows from Corollary 1, Theorem 6 and the conjugation argument in the proof of Corollary 4.
Lemma 9. Let be given by its multiplication table, with , and let be endomorphisms of , given by their tables. One can compute , a basis of over , a table of the coordinates of all the elements of in this basis, and the matrices in of in this basis, in operations.
Proof. The prime is the order of any element , computed in operations. Let . Given the span of , together with the coordinates of its elements, choose by scanning with a membership array. Then , and the coordinates of its elements are obtained from those of , in operations. Since and , the whole construction costs . The -th column of the matrix of is the coordinate vector of , read from the tables in operations. Reading the tables costs , which dominates the operations needed to fill the matrices.
The test of commutativity. Testing whether is abelian costs operations, and it is performed only once.
Size of the recursion tree of PowerDecomp. At every internal node the group is split into two non-trivial groups and with . Hence the orders of the groups attached to the leaves multiply to at most , the tree has at most leaves and at most nodes, and its depth is at most . Moreover, the orders of the groups attached to the nodes at a fixed depth multiply to at most .
Cost at an internal node. Let . A prime divisor of is found in operations, and the powers , , in operations by repeated squaring; they give both the subgroup and the test of whether is an elementary abelian -group, i.e., whether is a power of and for every . Building the multiplication tables of and costs , and the tables of the restrictions and of the induced endomorphisms of cost ; the neighborhood does not change. Since the orders at a fixed depth multiply to at most , the sum of over the nodes at a fixed depth is at most , and all the internal nodes together cost
Cost at a leaf. At a leaf, AbelianTest is called on , with and . By Lemma 9, the matrices of are computed in operations, and in operations. The polynomial is computed by Berkowitz’s division-free algorithm [5], which uses operations in . All the intermediate quantities are polynomials of degree at most in the entries of , hence Laurent polynomials with exponents in ; each of them has at most monomials, and each operation in costs . Then .
If , let and . Then , with and for every . Let be the cost of factoring such a polynomial into irreducibles. By Gauss’s lemma, the irreducible factors of of positive degree in have monomial leading coefficients in , since they divide the leading coefficient of ; dividing them by these coefficients yields the monic irreducible factors of in . Testing whether the constant term of each factor is a single monomial, i.e., a unit of , costs time linear in the size of the factorization.
Overall complexity. Let be the orders of the groups at the leaves of PowerDecomp, and . Since and , we have and ; hence
Adding the costs of the internal nodes and of the leaves, we obtain the following result.
Theorem 7. Let be a -GCA over a group of order , with neighbors and . The procedure IsST decides whether is strongly transitive using
operations, plus the cost of factoring at most polynomials with and , where .
By [20], a polynomial over a finite field can be factored in time polynomial in its degrees and in the field size . For each polynomial , we have and for every . Hence, for fixed , its dense representation has at most
coefficients. Since and , factoring all at most polynomials takes time polynomial in and , for fixed . Consequently, including the factorization step, IsST runs in time polynomial in , , and for every fixed dimension .
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 . 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 , the resulting decision procedure runs in time polynomial in the group size , the number of neighbours, and the neighbourhood radius , 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 , instead of the full shift, as well as for CAs on more general amenable groups than .
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]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]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]M. F. Atiyah and I. G. Macdonald. Introduction to Commutative Algebra. Addison-Wesley Series in Mathematics. Addison-Wesley, Reading, MA, 1969.
- [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]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]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]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]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]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]T. Ceccherini-Silberstein and M. Coornaert. Cellular Automata and Groups. Springer Monographs in Mathematics. Springer, Berlin, 2010.
- [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]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]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]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]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]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]E. Hewitt and K. A. Ross. Abstract Harmonic Analysis I. Number 115 in Grundlehren der mathematischen Wissenschaften. Springer-Verlag, Berlin, 1963.
- [18]J. Kari. Theory of cellular automata: A survey. Theoretical Computer Science, 334(1-3):3–33, 2005.DOI
- [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]A. Lenstra. Factoring multivariate polynomials over finite fields. Journal of Computer and System Sciences, 30(2):235–248, 1985.
- [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]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]J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, Cambridge, 3rd edition, 2013.