1 Introduction

Cellular automata (CA) are well-known formal models of natural computing which have been successfully applied in a wide number of fields to simulate complex phenomena involving local, uniform, and synchronous processing (for recent results and an up-to date bibliography on CA, see [1, 6, 7, 16, 25], while for other models of natural computing see for instance [9, 12, 17]). More formally, a CA is made of an infinite set of identical finite automata arranged over a regular cell grid (usually \(\mathbb {Z}^d\) in dimension d) and all taking a state from a finite set S called the set of states. In this paper, we consider one-dimensional CA. A configuration is a snapshot of all states of the automata, i.e., a function \(c:\mathbb {Z}\rightarrow S\). A local rule updates the state of each automaton on the basis of its current state and the ones of a finite set of neighboring automata. All automata are updated synchronously. In the one-dimensional settings, a CA is a structure \(\left\langle S, r, f\right\rangle \) where \(r\in \mathbb {N} \) is the radius and \(f:S^{2r+1}\rightarrow S\) is the local rule which updates, for each \(i\in \mathbb {Z}\), the state of the automaton in the position i of the grid \(\mathbb {Z}\) on the basis of states of the automata in the positions \(i-r, \ldots , i+r\). A configuration is an element of \(S^{\mathbb {Z}}\) and describes the (global) state of the CA. The feature of synchronous updating induces the following global rule \(F:S^{\mathbb {Z}}\rightarrow S^{\mathbb {Z}}\) defined as

$$\begin{aligned} \forall c\in S^{\mathbb {Z}}, \forall i\in \mathbb {Z},\qquad F(c)_i=f(c_{i-r}, \ldots c_{i+r}). \end{aligned}$$

As such, the global map F describes the change from any configuration c at any time \(t\in \mathbb {N} \) to the configuration F(c) at \(t+1\) and summarises the main features of the CA model, namely, the fact that it is defined through a local rule which is applied uniformly and synchronously to all cells.

Because of a possible inadequacy, in some contexts, of every single one of the three defining features, variants of the original CA model started appearing, each one relaxing one among these three features. Asynchronous CA relax synchrony (see [8, 10, 11, 18, 26] for instance), non-uniform CA relax uniformity [13,14,15], while hormonal CA (for instance) relax locality [4]. However, from the mathematical point of view all those systems, as well as the original model, fall in the same class, namely, the class of autonomous discrete dynamical systems (DDS) and one could also precise memoryless systems.

In [27], Toffoli introduced higher-order CA (HOCA), i.e., variants of CA in which the updating of the state of a cell also depends on the past states of the cell itself and its neighbours. In particular, he showed that any arbitrary reversible linear HOCA can be embedded in a reversible linear CA (LCA), where linear means that the local rule is linear. Essentially, the trick consisted in memorizing past states and recover them later on. Some years later, Le Bruyn and Van Den Bergh explained and generalized the Toffoli construction and proved that any linear HOCA having the ring \(S=\mathbb {Z}_m\) as alphabet and memory size n can be simulated by a linear CA over the alphabet \(\mathbb {Z}^n_m\) (see the precise definition in Sect. 2) [2]. In this way, as we will see, a practical way to decide injectivity (which is equivalent to reversibility in this setting) and surjectivity of HOCA can be easily derived by the characterization of the these properties for the corresponding LCA simulating them. Indeed, in [2] and [20], characterizations of injectivity and surjectivity of a LCA over \(\mathbb {Z}^n_m\) are provided in terms of properties of the determinant of the matrix associated with it, where the determinant turns out to be another LCA (over \(\mathbb {Z}_m\)). Since the properties of LCA over \(\mathbb {Z}_m\) (i.e., LCA over \(\mathbb {Z}^n_m\) with \(n=1\)) have been extensively studied and related decidable characterizations have been obtained [3, 5, 24], one derives the algorithms to decide injectivity and surjectivity for LCA over \(\mathbb {Z}^n_m\) and, then, as we will see, also for HOCA over \(\mathbb {Z}_m\) of memory size n, by means of the associated matrix. The purpose of the present paper is to study, in the context of linear HOCA, sensitivity to the initial conditions and equicontinuity, where the former is the well-known basic component and essence of the chaotic behavior of a DDS, while the latter represents a strong form of stability. To do that, we put in evidence that any linear HOCA over \(\mathbb {Z}_m\) of memory size n is not only simulated by but also topologically conjugated to a LCA over \(\mathbb {Z}^n_m\) defined by a matrix having a specific form. Thus, in order to decide injectivity and surjectivity for linear HOCA over \(\mathbb {Z}_m\) of memory size n, one can use the decidable characterization provided in [2] and [20] for deciding the same properties for LCA over \(\mathbb {Z}^n_m\) by means of that specific matrix. As main result, we prove that sensitivity to the initial condition and equicontinuity are decidable properties for linear HOCA over \(\mathbb {Z}_m\) of memory size n (Theorem 2). In particular we provide a decidable characterization of those properties, in terms of the matrix associated with a linear HOCA. Remark that if \(n=1\), starting from our characterizations one recovers exactly the well known characterizations of sensitivity and equicontinuity for LCA over \(\mathbb {Z}_m\).

2 Higher-Order CA and Linear CA

We begin by reviewing some general notions and introducing notations we will use throughout the paper.

A discrete dynamical system (DDS) is a pair \((\mathcal {X}, \mathcal {F})\) where \(\mathcal {X}\) is a space equipped with a metric, i.e., a metric space, and \(\mathcal {F}\) is a transformation on \(\mathcal {X}\) which is continuous with respect to that metric. The dynamical evolution of a DDS \((\mathcal {X}, \mathcal {F})\) starting from the initial state \(x^{(0)}\in \mathcal {X}\) is the sequence \(\{x^{(t)}\}_{t\in \mathbb {N}}\subseteq \mathcal {X}\) where \(x^{(t)}=\mathcal {F}^t(x^{(0)})\) for any \(t\in \mathbb {N} \). When \(\mathcal {X}=S^{\mathbb {Z}}\) for some set finite S, \(\mathcal {X}\) is usually equipped with the metric d defined as follows \(\forall c,c'\in S^{\mathbb {Z}}, d(c,c')=\frac{1}{2^n}\), where \(n=\min \{i\ge 0\,:\,c_i\ne c'_i \;\text {or}\;c'_{-i}\ne c'_{-i}\}\). Recall that \(S^{\mathbb {Z}}\) is a Cantor space.

Any CA \(\left\langle S, r, f\right\rangle \) defines the DDS \((S^{\mathbb {Z}}, F)\), where F is the CA global rule (which is continuous). From now on, for the sake of simplicity, we will sometimes identify a CA with its global rule F or with the DDS \((S^{\mathbb {Z}}, F)\).

Recall that two DDS \((\mathcal {X},\mathcal {F})\) and \((\mathcal {X}',\mathcal {F}')\) are topologically conjugated if there exists a homeomorphism \(\phi : \mathcal {X} \mapsto \mathcal {X}'\) such that \(\mathcal {F}'\circ \phi =\phi \circ \mathcal {F}\), while the product of \((\mathcal {X}, \mathcal {F})\) and \((\mathcal {X}', \mathcal {F}')\) is the DDS \((\mathcal {X}\times \mathcal {X}', \mathcal {F}\times \mathcal {F}')\) where \(\mathcal {F}\times \mathcal {F}'\) is defined as \(\forall (x,x')\in \mathcal {X} \times \mathcal {X}'\), \((\mathcal {F}\times \mathcal {F}')(x,x')=(\mathcal {F}(x), \mathcal {F}'(x'))\).

Notation 1

For all \(i,j\in \mathbb {Z}\) with \(i\le j\), we write \([i,j]=\{i,i+1,\ldots ,j\}\) to denote the interval of integers between i and j. For any \(n\in \mathbb {N} \) and any set Z the set of all \(n\times n\) matrices with coefficients in Z and the set of Laurent polynomials with coefficients in Z will be noted by \(Mat\left( n,Z\right) \) and \(Z\left[ X,X^{-1}\right] \), respectively. In the sequel, bold symbols are used to denote vectors, matrices, and configurations over a set of states which is a vectorial space. Moreover, m will be an integer bigger than 1 and \(\mathbb {Z}_m=\{0, 1, \ldots , m-1\}\) the ring with the usual sum and product modulo m. For any \(\varvec{x} \in \mathbb {Z}^n\) (resp., any matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}\left[ X,X^{-1}\right] \right) \)), we will denote by \(\left[ \varvec{x} \right] _{m}\in \mathbb {Z}_m^n\) (resp., \(\left[ \varvec{M} (X)\right] _{m}\)), the vector (resp., the matrix) in which each component \(x^i\) of \(\varvec{x} \) (resp., every coefficient of each element of \(\varvec{M} (X)\)) is taken modulo m. Finally, for any matrix \(\varvec{M} (X)\in \mathbb {Z}_m\left[ X,X^{-1}\right] \) and any \(t\in \mathbb {N} \), the t-th power of \(\varvec{M} (X)\) will be noted more simply by \(\varvec{M} ^t(X)\) instead of \((\varvec{M} (X))^t\).

Definition 1

(Higher-Order Cellular Automata). A Higher-Order Cellular Automata (HOCA) is a structure \(\mathcal {H}=\left\langle k,S,r,h\right\rangle \) where \(k\in \mathbb {N} \) with \(k\ge 1\) is the memory size, S is the alphabet, \(r\in \mathbb {N} \) is the radius, and \(h:S^{(2r+1)k}\rightarrow S\) is the local rule. Any HOCA \(\mathcal {H}\) induces the global rule \(H:\left( {S^{\mathbb {Z}}}\right) ^k\rightarrow \left( {S^{\mathbb {Z}}}\right) ^k\) associating any vector \(\varvec{e} =(e^1, \ldots , e^k)\in \left( {S^{\mathbb {Z}}}\right) ^k\) of k configurations of \(S^{\mathbb {Z}}\) with the vector \(H(\varvec{e})\in \left( {S^{\mathbb {Z}}}\right) ^k\) such that \(H(\varvec{e})^j=e^{j+1}\) for each \(j\ne k\) and \(\forall i\in \mathbb {Z}, H(\varvec{e})^k_i=h\left( \begin{matrix} e^{1}_{[i-r, i+r]}\\ \vdots \\ e^{k}_{[i-r, i+r]}\end{matrix}\right) \). In this way, \(\mathcal {H}\) defines the DDS \(\left( \left( {S^{\mathbb {Z}}}\right) ^k, H\right) \). As with CA, we identify a HOCA with its global rule or the DDS defined by it.

Remark 1

It is easy to check that for any HOCA \(\mathcal {H}=\left\langle k,S,r,h\right\rangle \) there exists a CA \(\left\langle S^k,r,f\right\rangle \) which is topologically conjugated to \(\mathcal {H}\).

The study of the dynamical behaviour of HOCA is still at its early stages; a few results are known for the class of linear HOCA, namely, those HOCA defined by a local rule f which is linear, i.e., S is \(\mathbb {Z}_m\) and there exist coefficients \(a^j_i\in \mathbb {Z}_m\) (\(j=1, \ldots , k\) and \(i=-r, \ldots , r\)) such that for any element

$$\begin{aligned} \varvec{x} =\left( \begin{matrix} x^{1}_{-r} &{} \ldots &{} x^{1}_{r} \\ \vdots &{} \vdots &{} \vdots \\ x^{k}_{-r} &{} \ldots &{} x^{k}_{r}\end{matrix}\right) \in \mathbb {Z}_m^{(2r+1)k}, \quad f(\varvec{x})=\left[ \sum _{j=1}^{k}\sum _{i=-r}^{r} a^j_i x^{j}_{i}\right] _{m}. \end{aligned}$$

Clearly, linear HOCA are additive, i.e., \(\forall \varvec{c},\varvec{d} \in \left( \mathbb {Z}_m^{\mathbb {Z}}\right) ^k, H(\varvec{c})+H(\varvec{d}) \), where, with an abuse of notation, \(+\) denotes the extension of the sum over \(\mathbb {Z}_m\) to both \(\mathbb {Z}_m^{\mathbb {Z}}\) and \(\left( \mathbb {Z}_m^{\mathbb {Z}}\right) ^k\).

In [2], a much more convenient representation is introduced for the case of linear HOCA (in dimension \(d=1\)) by means of the following notion.

Definition 2

(Linear Cellular Automata). A Linear Cellular Automaton (LCA) is a CA \(\mathcal {L}=\left\langle \mathbb {Z}_m^n, r, f\right\rangle \) where the local rule \(f:(\mathbb {Z}_m^n)^{2r+1}\rightarrow \mathbb {Z}_m^n\) is defined by \(2r+1\) matrices \(\varvec{M} _{-r},\ldots , \varvec{M} _0,\ldots , \varvec{M} _r\in Mat\left( n,\mathbb {Z}_m\right) \) as follows: \(f(\varvec{x} _{-r}, \ldots ,\varvec{x} _0,\ldots ,\varvec{x} _r) = \left[ \sum _{i=-r}^r \varvec{M} _i\cdot \varvec{x} _i\right] _{m}\) for any \((\varvec{x} _{-r}, \ldots ,\varvec{x} _0,\ldots ,\varvec{x} _r)\in (\mathbb {Z}_m^n)^{2r+1}\).

Remark 2

LCA have been strongly investigated in the case \(n=1\) and all the dynamical properties have been characterized in terms of the \(1\times 1\) matrices (i.e., coefficients) defining the local rule, in any dimension too [3, 24].

We recall that any linear HOCA \(\mathcal {H}\) can be simulated by a suitable LCA, as shown in [2]. Precisely, given a linear HOCA \(\mathcal {H}=\left\langle k,\mathbb {Z}_m,r,h\right\rangle \), where h is defined by the coefficients \(a^j_i\in \mathbb {Z}_m\), the LCA simulating \(\mathcal {H}\) is \(\mathcal {L}=\left\langle \mathbb {Z}_m^k, r, f\right\rangle \) with f defined by following matrices

$$\begin{aligned} \varvec{M} _0= \begin{bmatrix} 0&1&0&\dots&0&0\\ 0&0&1&\ddots&0&0\\ 0&0&0&\ddots&0&0\\ \vdots&\vdots&\vdots&\ddots&\ddots&\vdots \\ 0&0&0&\dots&0&1\\ a_0^1&a_0^2&a_0^3&\dots&a_0^{k-1}&a_0^k \end{bmatrix}, \text {and} \quad \varvec{M} _i= \begin{bmatrix} 0&0&0&\dots&0&0\\ 0&0&0&\dots&0&0\\ 0&0&0&\dots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0&0&0&\dots&0&0\\ a_i^1&a_i^2&a_i^3&\dots&a_i^{k-1}&a_i^k \end{bmatrix}, \end{aligned}$$
(1)

for each \(i\in [-r, r]\) with \(i\ne 0\).

Remark 3

We want to put in evidence that a stronger result actually holds (easy proof, important remark): any linear HOCA \(\mathcal {H}\) is topologically conjugated to the LCA \(\mathcal {L}\) defined by the matrices in (1). Clearly, the converse also holds: for any LCA defined by the matrices in (1) there exists a linear HOCA which is topologically conjugated to it. In other words, up to a homeomorphism the whole class of linear HOCA is identical to the subclass of LCA defined by the matrices above introduced. In the sequel, we will call \(\mathcal {L}\) the matrix presentation of \(\mathcal {H}\).

We are now going to show a stronger and useful new fact, namely, that the class of linear HOCA is nothing but the subclass of LCA represented by a formal power series which is a matrix in Frobenius normal form. Before proceeding, let us recall the formal power series (fps) which have been successfully used to study the dynamical behaviour of LCA in the case \(n=1\) [19, 24]. The idea of fps is that configurations and global rules are represented by suitable polynomials and the application of the global rule turns into multiplications of polynomials. In the more general case of LCA over \(\mathbb {Z}_m^n\), a configuration \(\varvec{c} \in (\mathbb {Z}_m^n)^\mathbb {Z}\) can be associated with the fps

$$\begin{aligned} \varvec{P} _{\varvec{c}}(X)=\sum _{i\in \mathbb {Z}}\varvec{c} _i X^i = \begin{bmatrix} c^1(X)\\ \vdots \\ c^n(X) \end{bmatrix} = \begin{bmatrix} \mathop {\sum }\nolimits _{i\in \mathbb {Z}} c_i^1 X^i\\ \vdots \\ \mathop {\sum }\nolimits _{i\in \mathbb {Z}} c_i^n X^i \end{bmatrix}. \end{aligned}$$

Then, if F is the global rule of a LCA defined by \(\varvec{M} _{-r},\ldots , \varvec{M} _0,\ldots , \varvec{M} _r\), one finds \(\varvec{P} _{F(\varvec{c})}(X)=\left[ \varvec{M} (X) \varvec{P} _{\varvec{c}}(X)\right] _{m}\) where

$$ \varvec{M} (X) =\left[ \sum \limits _{i=-r}^{r} \varvec{M} _i X^{-i}\right] _{m} $$

is the finite fps associated with the LCA F. In this way, for any integer \(t>0\) the fps associated with \(F^t\) is \(\varvec{M} (X)^t\), and then \( \varvec{P} _{F^t(\varvec{c})}(X)=\left[ \varvec{M} (X)^t \varvec{P} _{\varvec{c}}(X)\right] _{m}. \) Throughout this paper, \(\varvec{M} (X)^t\) will refer to \(\left[ \varvec{M} (X)^t\right] _{m}\).

A matrix \(\varvec{M} (X)\in Mat\left( n,Z\left[ X,X^{-1}\right] \right) \) is in Frobenius normal form if

$$\begin{aligned} \varvec{M} (X)= \begin{bmatrix} 0&1&0&\dots&0&0\\ 0&0&1&\ddots&0&0\\ 0&0&0&\ddots&0&0\\ \vdots&\vdots&\vdots&\ddots&\ddots&\vdots \\ \\ 0&0&0&\dots&0&1\\ \\ \mathbbm {m}_0(X)&\mathbbm {m}_1(X)&\mathbbm {m}_2(X)&\dots&\mathbbm {m}_{n-2}(X)&\mathbbm {m}_{n-1}(X) \end{bmatrix} \end{aligned}$$
(2)

where each \(\mathbbm {m}_i(X)\in Z\left[ X,X^{-1}\right] \). From now on, \(\varvec{\mathbbm {m}} (X)\) will always make reference to the n-th row of a matrix \(\varvec{M} (X)\in Mat\left( n,Z\left[ X,X^{-1}\right] \right) \) in Frobenius normal form.

Definition 3

(Frobenius LCA). A LCA F over the alphabet \(\mathbb {Z}^n_{m}\) is said to be a Frobenius LCA if the fps \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_m\left[ X,X^{-1}\right] \right) \) associated with F is in Frobenius normal form.

It is immediate to see that a LCA is a Frobenius one iff it is defined by the matrices in (1), i.e., iff it is topologically conjugated to a linear HOCA. This fact together with Remark 3 and Definition 3, allow us to state the following

Proposition 1

Up to a homeomorphism, the class of linear HOCA over \(\mathbb {Z}_m\) of memory size n is nothing but the class of Frobenius LCA over \(\mathbb {Z}^n_m\).

Remark 4

Actually, in literature a matrix is in Frobenius normal form if either it or its transpose has a form as in (2). Since any matrix in Frobenius normal form is conjugated to its transpose, any Frobenius LCA F is topologically conjugated to a LCA G such that the fps associated with G is the transpose of the fps associated with G. In other words, up to a homeomorphism, such LCA G, linear HOCA, and Frobenius LCA form the same class.

From now on, we will focus on Frobenius LCA, i.e., matrix presentations of linear HOCA. Indeed, they allow convenient algebraic manipulations that are very useful to study formal properties of linear HOCA. For example, in [2] and [20], the authors proved decidable characterization for injectivity and surjectivity for LCA in terms of the matrix \(\varvec{M} (X)\) associated to them. We want to stress that, by Remark 3 and Definition 3, one can use these characterizations for deciding injectivity and surjectivity of linear HOCA. In this paper we are going to adopt a similar attitude, i.e., we are going to characterise the dynamical behaviour of linear HOCA by the properties of the matrices in their matrix presentation.

3 Dynamical Properties

In this paper we are particularly interested to the so-called sensitivity to the initial conditions and equicontinuity. As dynamical properties, they represent the main features of instable and stable DDS, respectively. The former is the well-known basic component and essence of the chaotic behavior of DDS, while the latter is a strong form of stability.

Let \((\mathcal {X}, \mathcal {F})\) be a DDS. The DDS \((\mathcal {X}, \mathcal {F})\) is sensitive to the initial conditions (or simply sensitive) if there exists \(\varepsilon >0\) such that for any \(x\in \mathcal {X}\) and any \(\delta >0\) there is an element \(y\in \mathcal {X}\) such that \(d(y,x)<\delta \) and \(d(\mathcal {F}^n(y),\mathcal {F}^n(x))>\varepsilon \) for some \(n\in \mathbb {N}\). Recall that, by Knudsen’s Lemma [21], \((\mathcal {X}, \mathcal {F})\) is sensitive iff \((\mathcal {Y}, \mathcal {F})\) is sensitive where \(\mathcal {Y}\) is any dense subset of \(\mathcal {X}\) which is \(\mathcal {F}\)-invariant, i.e., \(\mathcal {F}(\mathcal {Y})\subseteq \mathcal {Y}\).

In the sequel, we will see that in the context of LCA an alternative way to study sensitivity is via equicontinuity points. An element \(x\in \mathcal {X}\) is an equicontinuity point for \((\mathcal {X}, \mathcal {F})\) if \(\forall \varepsilon >0\) there exists \(\delta >0\) such that for all \(y\in \mathcal {X}\), \(d(x,y)<\delta \) implies that \(d(\mathcal {F}^n(y),\mathcal {F}^n(x))<\varepsilon \) for all \(n\in \mathbb {N}\). The system \((\mathcal {X}, \mathcal {F})\) is said to be equicontinuous if \(\forall \varepsilon >0\) there exists \(\delta >0\) such that for all \(x,y\in \mathcal {X}\), \(d(x,y)<\delta \) implies that \(\forall n\in \mathbb {N},\;d(\mathcal {F}^n(x),\mathcal {F}^n(y))<\varepsilon \). Recall that any CA \((S^{\mathbb {Z}}, F)\) is equicontinuous if and only if there exist two integers \(q\in \mathbb {N}\) and \(p>0\) such that \(F^q=F^{q+p}\) [22]. Moreover, for the subclass of LCA defined by \(n=1\) the following result holds:

Theorem 1

([24]). Let \((\mathbb {Z}_m^{\mathbb {Z}}, F)\) be a LCA where the local rule \(f:(\mathbb {Z}_m)^{2r+1}\rightarrow \mathbb {Z}_m\) is defined by \(2r+1\) coefficients \(m_{-r},\ldots , m_0,\ldots , m_r\in \mathbb {Z}_m\). Denote by \(\mathcal {P}\) the set of prime factors of m. The following statements are equivalent: (i) F is sensitive to the initial conditions; (ii) F is not equicontinuous; (iii) there exists a prime number \(p\in \mathcal {P}\) which does not divide \(\gcd (m_{-r},\ldots , m_{-1},m_{1},\ldots , m_r)\).

The dichotomy between sensitivity and equicontinuity still holds for general LCA.

Proposition 2

Let \(\mathcal {L}=\left\langle \mathbb {Z}_m^n, r, f\right\rangle \) be a LCA where the local rule \(f:(\mathbb {Z}_m^n)^{2r+1}\rightarrow \mathbb {Z}_m^n\) is defined by \(2r+1\) matrices \(\varvec{M} _{-r},\ldots , \varvec{M} _0,\ldots , \varvec{M} _r\in Mat\left( n,\mathbb {Z}_m\right) \). The following statements are equivalent: (i) F is sensitive to the initial conditions; (ii) F is not equicontinuous; (iii) \(\left| \{\varvec{M} (X)^i, i\ge 1 \} \right| = \infty \).

Proof

It is clear that conditions (ii) and (iii) are equivalent. The equivalence between (i) and (ii) is a consequence of linearity of F and Knudsen’s Lemma applied on the subset of the finite configurations, i.e., those having a state different from the null vector only in a finite number of cells.    \(\square \)

An immediate consequence of Proposition 2 is that any characterization of sensitivity to the initial conditions in terms of the matrices defining LCA over \(\mathbb {Z}_m^n\) would also provide a characterization of equicontinuity. In the sequel, we are going to show that such a characterization actually exists. First of all, we recall a result that helped in the study of dynamical properties in the case \(n=1\) and we now state it in a more general form for LCA over \(\mathbb {Z}_m^n\) (immediate generalisation of the result in [3, 5]).

Let \(\left( (\mathbb {Z}_m^n)^{\mathbb {Z}}, F \right) \) be a LCA and let q be any factor of m. We will denote by \(\left[ F\right] _{q}\) the map \(\left[ F\right] _{q}: (\mathbb {Z}_q^n)^{\mathbb {Z}}\rightarrow (\mathbb {Z}_q^n)^{\mathbb {Z}}\) defined as \(\left[ F\right] _{q}(\varvec{c})=\left[ F(\varvec{c})\right] _{q}\), for any \(\varvec{c} \in (\mathbb {Z}_q^n)^{\mathbb {Z}}\).

Lemma 1

([3, 5]). Consider any LCA \(\left( (\mathbb {Z}_m^n)^{\mathbb {Z}}, F \right) \) with \(m=pq\) and \(\gcd (p,q)=1\). It holds that the given LCA is topologically conjugated to \(\left( (\mathbb {Z}_p^n)^{\mathbb {Z}} \times (\mathbb {Z}_q^n)^{\mathbb {Z}}, \left[ F\right] _{p}\times \left[ F\right] _{q} \right) \).

As a consequence of Lemma 1, if \(m=p_1^{k_1} \cdots p_l^{k_l}\) is the prime factor decomposition of m, any LCA over \(\mathbb {Z}_m^n\) is topologically conjugated to the product of LCAs over \(\mathbb {Z}^n_{p_{i}^{k_i}}\). Since sensitivity is preserved under topological conjugacy for DDS over a compact space and the product of two DDS is sensitive if and only if at least one of them is sensitive, we will study sensitivity for Frobenius LCA over \(\mathbb {Z}_{p^{k}}^n\). We will show a decidable characterization of sensitivity to the initial conditions for Frobenius LCA over \(\mathbb {Z}_{p^{k}}^n\) (Lemma 8). Such a decidable characterization together with the previous remarks about the decomposition of m, the topological conjugacy involving any LCA over \(\mathbb {Z}_m^n\) and the product of LCAs over \(\mathbb {Z}^n_{p_{i}^{k_i}}\), and how sensitivity behaves with respect to a topological conjugacy and the product of DDS, immediately lead to state the main result of the paper.

Theorem 2

Sensitivity and Equicontinuity are decidable for Frobenius LCA over \(\mathbb {Z}_m^n\), or, equivalently, for linear HOCA over \(\mathbb {Z}_m\) of memory size n.

4 Sensitivity of Frobenius LCA over \(\mathbb {Z}^n_{p^k}\)

In order to study sensitivity of Frobenius LCA over \(\mathbb {Z}^n_{p^k}\), we introduce two concepts about Laurent polynomials.

Definition 4

(\(deg^+\) and \(deg^-\)). Given any polynomial \(\mathbbm {p}(X)\in \mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \), the positive (resp., negative) degree of \(\mathbbm {p}(X)\), denoted by \(deg^+[\mathbbm {p}(X)]\) (resp., \(deg^-[\mathbbm {p}(X)]\)) is the maximum (resp., minimum) degree among those of the monomials having both positive (resp., negative) degree and coefficient which is not multiple of p. If there is no monomial satisfying both the required conditions, then \(deg^+[\mathbbm {p}(X)]=0\) (resp., \(deg^-[\mathbbm {p}(X)]=0)\).

Definition 5

(Sensitive Polynomial). A polynomial \(\mathbbm {p}(X)\in \mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \) is sensitive if either \(deg^+[\mathbbm {p}(X)]>0\) or \(deg^-[\mathbbm {p}(X)]<0\). As a consequence, a Laurent polynomial \(\mathbbm {p}(X)\) is not sensitive iff \(deg^+[\mathbbm {p}(X)]=deg^-[\mathbbm {p}(X)]=0\).

Trivially, it is decidable to decide whether a Laurent polynomial is sensitive.

Remark 5

Consider a matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form. The characteristic polynomial of \(\varvec{M} (X)\) is then \(\mathscr {P}(y)=(-1)^n(-\mathbbm {m}_0(X)-\mathbbm {m}_1(X) y -\cdots - \mathbbm {m}_{n-1}(X) y^{n-1} + y^n)\). By the Cayley-Hamilton Theorem, one obtains

$$\begin{aligned} \varvec{M} ^n(X) = \mathbbm {m}_{n-1}(X) \varvec{M} (X)^{n-1} +\dots + \mathbbm {m}_{1}(X) \varvec{M} (X)^{1} + \mathbbm {m}_{0}(X) I . \end{aligned}$$
(3)

We now introduce two further matrices that will allow us to access the information hidden inside \(\varvec{M} (X)\).

Definition 6

(\(\varvec{U} (X)\), \(\varvec{L} (X)\), \(d^+\), and \(d^-\)). For any matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form the matrices \(\varvec{U} (X), \varvec{L} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) associated with \(\varvec{M} (X)\) are the matrices in Frobenius normal form where each component \(\mathbbm {u}_i(X)\) and \(\mathbbm {l}_i(X)\) (with \(i=0, \ldots , n-1\)) of the n-th row \(\varvec{\mathbbm {u}} (X)\) and \(\varvec{\mathbbm {l}} (X)\) of \(\varvec{U} (X)\) and \(\varvec{L} (X)\), respectively, is defined as follows:

$$\begin{aligned} \mathbbm {u}_i(X)&= {\left\{ \begin{array}{ll} \text {monomial of degree } deg^+[\mathbbm {m}_i(X)] \text { inside } \mathbbm {m}_i(X) &{} \text {if } d_i^+=d^+\\ 0 &{} \text {otherwise} \end{array}\right. } \\ \mathbbm {l}_i(X)&= {\left\{ \begin{array}{ll} \text {monomial of degree } deg^-[\mathbbm {m}_i(X)] \text { inside } \mathbbm {m}_i(X) &{} \text {if } d_i^-=d^-\\ 0 &{} \text {otherwise} \end{array}\right. } , \end{aligned}$$

where \(d_i^+=\frac{deg^+[\mathbbm {m}_i(X)]}{n-i}\), \(d_i^-=\frac{deg^-[\mathbbm {m}_i(X)]}{n-i}\), \(d^+=\max \{d_i^+\}\), and \(d^-=\min \{d_i^-\}\).

Definition 7

(\(\widehat{\varvec{M}}(X)\) and \(\overline{\varvec{M}}(X)\)). For any Laurent polynomial \(\mathbbm {p}(X)\in \mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \), \(\widehat{\mathbbm {p}}(X)\) and \(\overline{\mathbbm {p}}(X)\) are defined as the Laurent polynomial obtained from \(\mathbbm {p}(X)\) by removing all the monomials having coefficients that are multiple of p and \(\overline{\mathbbm {p}}(X)= \mathbbm {p}(X)-\widehat{\mathbbm {p}}(X)\), respectively. These definitions extend component-wise to vectors. For any matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form, \(\widehat{\varvec{M}}(X)\) and \(\overline{\varvec{M}}(X)\) are defined as the matrix obtained from \(\varvec{M} (X)\) by replacing its n-th row \(\varvec{\mathbbm {m}} (X)\) with and \(\overline{\varvec{M}}(X)=\varvec{M} (X)-\widehat{\varvec{M}}(X)\), respectively.

Definition 8

(Graph \(G_{\varvec{M}}\)). Let \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) be any matrix in Frobenius normal form. The graph \(G_{\varvec{M}}=\langle V_{\varvec{M}}, E_{\varvec{M}}\rangle \) associated with \(\varvec{M} (X)\) is such that \(V_{\varvec{M}}=\{1, \ldots , n\}\) and \(E_{\varvec{M}}=\{(h,k)\in V^2_{\varvec{M}} | \, \varvec{M} (X)^{h}_k \ne 0\}\). Moreover, each edge \((h,k)\in E_{\varvec{M}}\) is labelled with \(\varvec{M} (X)^{h}_k\).

Clearly, for any matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form, any natural \(t>0\), and any pair (h, k) of entries, the element \(\varvec{M} ^t(X)^{h}_k\) is the sum of the weights of all paths of length t starting from h and ending to k, where the weight of a path is the product of the labels of its edges.

Lemma 2

Let \(p>1\) be a prime number and \(a, b\ge 0\), \(k>0\) be integers such that \(1\le a < p^k\) and \(\gcd (a,p)= 1\). Then, \(\left[ a+p b\right] _{p^k}\ne 0\).

Lemma 3

Let \(p>1\) be a prime number and h, k be two positive integers. Let \(l_1,\dots ,l_h\) and \(\alpha _1,\dots ,\alpha _h\) be positive integers such that \(l_1<l_2<\cdots <l_h\) and for each \(i=1, \ldots , h\) both \(1\le \alpha _i< p^k\) and \(\gcd (\alpha _i,p)=1\) hold. Consider the sequence \(b:\mathbb {Z}\rightarrow \mathbb {Z}_{p^k}\) defined for any \(l\in \mathbb {Z}\) as \(b_l=\left[ \alpha _1 b_{l-l_1}+\cdots + \alpha _h b_{l-l_h}\right] _{p^k}\) if \(l>0\), \(b_0=1\), and \(b_l=0\), if \(l<0\). Then, it holds that \(\left[ b_l\right] _{p} \ne 0\) for infinitely many \(l\in \mathbb {N} \).

For any matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form, we are now going to study the behavior of \(\varvec{U} ^{t}(X)\) and \(\varvec{L} ^{t}(X)\), and, in particular, of their elements \(\varvec{U} ^{t}(X)^n_n\) and \(\varvec{L} ^{t}(X)^n_n\). These will turn out to be crucial in order to establish the sensitivity of the LCA defined by \(\varvec{M} (X)\).

Notation 2

For a sake of simplicity, for any matrix \(\varvec{M} (X)\in Mat\left( {n}{\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] }\right) \) in Frobenius normal form, from now on we will denote by \(\mathbbm {u}^{(t)}(X)\) and \(\mathbbm {l}^{(t)}(X)\) the elements \((\varvec{U} ^t(X))_{n}^n\) and \(\varvec{L} ^{t}(X)^n_n\), respectively.

Lemma 4

Let \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) be a matrix such that \(\varvec{M} (X)=\widehat{\varvec{N}}(X)\) for some \(\varvec{N} (X) \in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form. For any natural \(t>0\), \(\mathbbm {u}^{(t)}(X)\) (resp., \(\mathbbm {l}^{(t)}(X)\)) is either null or a monomial of degree \(td^+\) (resp., \(td^-\)).

Proof

We show that the statement is true for \(\mathbbm {u}^{(t)}(X)\) (the proof concerning \(\mathbbm {l}^{(t)}(X)\) is identical by replacing \(d^+\), \(\varvec{U} (X)\) and related elements with \(d^-\), \(\varvec{L} (X)\) and related elements). For each \(i\in V_{\varvec{U}}\), let \(\gamma _i\) be the simple cycle of \(G_{\varvec{U}}\) from n to n and passing through the edge (n, i). Clearly, \(\gamma _i\) is the path \(n\rightarrow i\rightarrow i+1\ldots \rightarrow n-1\rightarrow n\) (with \(\gamma _n\) the self-loop \(n\rightarrow n\)) of length \(n-i+1\) and its weight is the monomial \(\mathbbm {u}_{i-1}(X)\) of degree \((n-i+1)d^+\). We know that \(\mathbbm {u}^{(t)}(X)\) is the sum of the weights of all cycles of length t starting from n and ending to n in \(G_{\varvec{U}}\) if at least one of such cycles exists, 0, otherwise. In the former case, each of these cycles can be decomposed in a certain number \(s\ge 1\) of simple cycles \(\gamma _{j_1}^1,\ldots , \gamma _{j_s}^s\) of lengths giving sum t, i.e., such that \(\sum _{i=1}^{s} (n-j_i+1) = t\). Therefore, \((\varvec{U} ^t(X))_{n}^n\) is a monomial of degree \(\sum _{i=1}^{s} (n-j_i+1)d^+ = t d^+\).   \(\square \)

Lemma 5

Let \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) be any matrix in Frobenius normal form. For every integer \(t\ge 1\) both the following recurrences hold

$$\begin{aligned} \mathbbm {u}^{(t)}(X)\!= & {} \! \mathbbm {u}_{n-1}(X)\mathbbm {u}^{(t-1)}(X)+ \cdots + \mathbbm {u}_{1}(X)\mathbbm {u}^{(t-n+1)}(X)+ \mathbbm {u}_0(X)\mathbbm {u}^{(t-n)}(X)\qquad \end{aligned}$$
(4)
$$\begin{aligned} \mathbbm {l}^{(t)}(X)= & {} \mathbbm {l}_{n-1}(X)\mathbbm {l}^{(t-1)}(X)+ \cdots + \mathbbm {l}_{1}(X)\mathbbm {l}^{(t-n+1)}(X)+ \mathbbm {l}_0(X)\mathbbm {l}^{(t-n)}(X) \end{aligned}$$
(5)

with initial conditions \(\mathbbm {u}^{(0)}(X) = \mathbbm {l}^{(0)}(X) = 1\), and \(\mathbbm {u}^{(l)}(X) = \mathbbm {l}^{(l)}(X) =0\) for \(l<0\).

Proof

We show the recurrence involving \(\mathbbm {u}^{(t)}(X)\) (the proof for \(\mathbbm {l}^{(t)}(X)\) is identical by replacing \(\varvec{U} (X)\) and its elements with \(\varvec{L} (X)\) and its elements). Since \(\varvec{U} (X)\) is in Frobenius normal form too, by (3), Recurrence (4) holds for every \(t\ge n\). It is clear that \(\mathbbm {u}^{(0)}(X)=1\). Furthermore, by the structure of the graph \(G_{\varvec{U}}\) and the meaning of \(\varvec{U} (X)^n_{n}\), Equation (4) is true under the initial conditions for each \(t=1, \ldots , n-1\).    \(\square \)

Lemma 6

Let \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) be a matrix such that \(\varvec{M} (X)=\widehat{\varvec{N}}(X)\) for some matrix \(\varvec{N} (X) \in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form. Let \(\upsilon (t)\) (resp., \(\lambda (t)\)) be the coefficient of \(\mathbbm {u}^{(t)}(X)\) (resp., \(\mathbbm {l}^{(t)}(X)\)). It holds that \(\gcd [\upsilon (t),p]=1\) (resp., \(\gcd [\lambda (t),p]=1\)), for infinitely many \(t\in \mathbb {N} \).

In particular, if the value \(d^+\) (resp., \(d^-\)) associated with \(\varvec{M} (X)\) is non null, then for infinitely many \(t\in \mathbb {N} \) both \(\left[ \mathbbm {u}^{(t)}(X)\right] _{p^k}\ne 0\) and \(deg(\left[ \mathbbm {u}^{(t)}(X)\right] _{p^k})\ne 0\) (resp., \(\left[ \mathbbm {l}^{(t)}(X)\right] _{p^k}\ne 0\) and \(deg(\left[ \mathbbm {l}^{(t)}(X)\right] _{p^k})\ne 0\)) hold. In other terms, if \(d^+>0\) (resp., \(d^-<0\)) then \(|\{\mathbbm {u}^{(t)}(X), t\ge 1\}|= \infty \) (resp., \(|\{\mathbbm {l}^{t}(X), t\ge 1\}| =\infty \)).

Proof

We show the statements concerning \(\upsilon (t)\), \(\varvec{U} (X)\), \(\mathbbm {u}^{(t)}(X)\), and \(d^+\). Replace X by 1 in the matrix \(\varvec{U} (X)\). Now, the coefficient \(\upsilon (t)\) is just the element of position (n, n) in the t-th power of the obtained matrix \(\varvec{U} (1)\). Over \(\varvec{U} (1)\), the thesis of Lemma 5 is still valid replacing \(\mathbbm {u}^{(t)}(X)\) by \(\upsilon (t)\). Thus, for every \(t\in \mathbb {N} \), \(\upsilon (t) = \mathbbm {u}_{n-1}(1)\upsilon (t-1)+ \cdots + \mathbbm {u}_1(1) \upsilon (t-n+1)+\mathbbm {u}_0(1) \upsilon (t-n) \) with initial conditions \(\upsilon (0)= 1\) and \(\upsilon (l)=0\), for \(l<0\), where each \(\mathbbm {u}_i(1)\) is the coefficient of the monomial \(\mathbbm {u}_i(X)\) inside \(\varvec{U} (X)\). Thus, it follows that \( \left[ \upsilon (t)\right] _{p^k} = \left[ \mathbbm {u}_{n-1}(1)\upsilon (t-1)+ \cdots + \mathbbm {u}_1(1) \upsilon (t-n+1)+\mathbbm {u}_0(1) \upsilon (t-n)\right] _{p^k} \). By Lemma 3 we obtain that \(\gcd [\upsilon (t),p]=1\) (and so \(\left[ \upsilon {(t)}\right] _{p^k}\ne 0\), too) for infinitely many \(t\in \mathbb {N} \). In particular, if the value \(d^+\) associated with \(\varvec{M} (X)\) is non null, then, by the structure of \(G_{\varvec{U}}\) and Lemma 4, both \(\left[ \mathbbm {u}^{(t)}(X)\right] _{p^k}\ne 0\) and \(deg(\left[ \mathbbm {u}^{(t)}(X)\right] _{p^k})\ne 0\) hold for infinitely many \(t\in \mathbb {N} \), too. Therefore, \(|\{\mathbbm {u}^{(t)}(X), t\ge 1\}|= \infty \). The same proof runs for the statements involving \(\lambda (t)\), \(\varvec{L} (X)\), \(\mathbbm {u}^{(t)}(X)\), and \(d^-\) provided that these replace \(\upsilon (t)\), \(\varvec{U} (X)\), \(\mathbbm {u}^{(t)}(X)\), and \(d^+\), respectively.    \(\square \)

Lemma 7

Let \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) be a matrix in Frobenius normal form. If either \(|\{\mathbbm {u}^{(t)}(X), t\ge 1\}|=\infty \) or \(|\{\mathbbm {l}^{(t)}(X), t\ge 1\}|=\infty \) then \(|\{\widehat{\varvec{M}}^{\, t}(X)_n^n, t\ge 1\}|=\infty \).

Proof

Assume that \(|\{\mathbbm {u}^{(t)}(X), t\ge 1\}|=\infty \). Since \(G_{\varvec{U}}\) is a subgraph of \(G_{\widehat{\varvec{M}}}\) (with different labels), for each integer t from Lemma 6 applied to \(\widehat{\varvec{M}}(X)\), the cycles of length t in \(G_{\widehat{\varvec{M}}}\) with weight containing a monomial of degree \(td^+\) are exactly the cycles of length t in \(G_{\varvec{U}}\). Therefore, it follows that \(|\{\widehat{\varvec{M}}^{\, t}(X)_n^n, t\ge 1\}|=\infty \). The same argument on \(G_{\varvec{L}}\) and involving \(d^-\) allows to prove the thesis if \(|\{\mathbbm {l}^{(t)}(X), t\ge 1\}|=\infty \).

We are now able to present and prove the main result of this section. It shows a decidable characterization of sensitivity for Frobenius LCA over \(\mathbb {Z}_{p^k}^n\).

Lemma 8

Let \(\left( (\mathbb {Z}_{p^k}^n)^{\mathbb {Z}}, F \right) \) be any Frobenius LCA over \(\mathbb {Z}_{p^k}^n\) and let \((\mathbbm {m}_0(X), \ldots , \mathbbm {m}_{n-1})\) be the n-th row of the matrix \(\varvec{M} (X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form associated with F. Then, F is sensitive to the initial conditions if and only if \(\mathbbm {m}_i(X)\) is sensitive for some \(i\in [0,n-1]\).

Proof

Let us prove the two implications separately.

Assume that all \(\mathbbm {m}_i(X)\) are not sensitive. Then, \(\widehat{\varvec{M}}(X)\in Mat\left( n,\mathbb {Z}_{p^k}\right) \), i.e., it does not contain the formal variable X, and \(\varvec{M} (X)=\widehat{\varvec{M}}(X)+p\varvec{M} '(X)\), for some \(\varvec{M} '(X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) in Frobenius normal form. Therefore, for any integer \(t>0\), \(\varvec{M} ^t(X)\) is the sum of terms, each of them consisting of a product in which \(p^j\) appears as factor, for some natural j depending on t and on the specific term which \(p^j\) belongs to. Since every element of \(\varvec{M} ^t(X)\) is taken modulo \(p^k\), for any natural \(t>0\) it holds that in each term of such a sum \(p^j\) appears with \(j\in [0, k-1]\) (we stress that j may depend on t and on the specific term of the sum, but it is always bounded by k). Therefore, \(|\{\varvec{M} ^i(X): i>0\}|<\infty \) and so, by Proposition 2, F is not sensitive to the initial conditions.

Conversely, suppose that \(\mathbbm {m}_i(X)\) is sensitive for some \(i\in [0,n-1]\) and \(d^+>0\) (the case \(d^-<0\) is identical). By Definition 7, for any natural \(t>0\) there exists a matrix \(\varvec{M} '(X)\in Mat\left( n,\mathbb {Z}_{p^k}\left[ X,X^{-1}\right] \right) \) such that \(\varvec{M} ^t(X)=\widehat{\varvec{M}}^t(X) + p\varvec{M} '(X)\). By a combination of Lemmata 6 and 7, we get \(|\{\widehat{\varvec{M}}^{\, t}(X)_n^n, t\ge 1\}|=\infty \) and so, by Lemma 2, \(|\{\varvec{M} ^t(X)_n^n, t\ge 1\}|=\infty \) too. Therefore, it follows that \(|\{\varvec{M} ^t(X), t\ge 1\}|=\infty \) and, by Proposition 2, we conclude that F is sensitive to the initial conditions.    \(\square \)

5 Conclusions

In this paper we have studied equicontinuity and sensitivity to the initial conditions for linear HOCA over \(\mathbb {Z}_m\) of memory size n, providing decidable characterizations for these properties. We also proved that linear HOCA over \(\mathbb {Z}_m\) of memory size n form a class that is indistinguishable from a subclass of LCA (namely, the subclass of Frobenius LCA) over \(\mathbb {Z}_m^n\). This enables to decide injectivity and surjectivity for linear HOCA over \(\mathbb {Z}_m\) of memory size n by means of the decidable characterizations of injectivity and surjectivity provided in [2] and [20] for LCA over \(\mathbb {Z}^n_m\). A natural and pretty interesting research direction consists of investigating other chaotic properties for linear HOCA and all the mentioned dynamical properties, including sensitivity and equicontinuity, for the whole class of LCA over \(\mathbb {Z}_m^n\).