An Easily Checkable Algebraic Characterization of Positive Expansivity for Additive Cellular Automata over a Finite Abelian Group

Choose arbitrarily three polynomials

such that $\pi=\rho\cdot\tau$. Obviously,

for every $i\in\{0,\ldots,n-1\}$ and, in particular, $\alpha_{0}=\beta_{0}\gamma_{0}$.

Assume that both $\rho$ and $\tau$ are both expansive. Hence, $\alpha_{0}=\beta_{0}\gamma_{0}\neq 0$ and

for every $i_{1}\in\{1,\ldots,n_{1}-1\}$ and $i_{2}\in\{1,\ldots,n_{2}-1\}$ such that $\beta_{i_{1}}\neq 0$ and $\gamma_{i_{2}}\neq 0$ (by Definition 3 a symmetric inequality regarding $\deg^{-}$ also holds). Let $i\in\{1,\ldots,n-1\}$ be any index such that $\alpha_{i}\neq 0$. We can write

for every $i_{1}\in\{1,\ldots,n_{1}-1\}$ and $i_{2}\in\{1,\ldots,n_{2}-1\}$ such that $i=i_{1}+i_{2}$, $\beta_{i_{1}}\neq 0$ and $\gamma_{i_{2}}\neq 0$. Clearly, condition $(ii)$ from Definition 3 also holds, as far as $\deg^{-}(\alpha_{i})$ is concerned. Thus, $\pi$ is expansive.

We prove now that if $\pi$ is expansive then $\rho$ and $\tau$ are both expansive. Assume that the consequent is not true. We deal with the two following cases: (1) $\rho$ is expansive but $\tau$ is not (by symmetry, we do not consider the situation in which $\tau$ is expansive but $\rho$ is not); (2) neither $\rho$ nor $\tau$ are expansive.

1. (1)

   Suppose that $\rho$ is expansive but $\tau$ is not. If $\gamma_{0}=0$ then it trivially follows that $\pi$ is not expansive. Otherwise, let $min$ be the minimum index such that $deg^{+}(\gamma_{min})=\max_{0\leq i_{2}<n_{2}}\{deg^{+}(\gamma_{i_{2}}):\gamma_{i_{2}}\neq 0\}$. Since $\rho$ is expansive, $\beta_{0}\gamma_{min}$ is the (only) addend of maximum degree in the sum from Equation (1) considered for $i=min$. Thus, $deg^{+}(\alpha_{min})=deg^{+}(\beta_{0}\gamma_{min})$. Furthermore, $deg^{+}(\alpha_{min})=deg^{+}(\beta_{0})+\deg^{+}(\gamma_{min})\geq deg^{+}(\beta_{0})+\deg^{+}(\gamma_{0})=deg^{+}(\beta_{0}\gamma_{0})=deg^{+}(\alpha_{0})$. In a symmetric way, one also gets that $deg^{-}(\alpha_{i})\leq deg^{-}(\alpha_{0})$ for some $i\in\{1,\ldots,n-1\}$.

2. (2)

   Suppose that neither $\rho$ nor $\tau$ are expansive. If $\beta_{0}=0\vee\gamma_{0}=0$ then it trivially follows that $\pi$ is not expansive. Otherwise, let $max_{1}$ and $max_{2}$ be the maximum indexes such that $\deg^{+}(\beta_{max_{1}})=\max_{0\leq i_{1}<n_{1}}\{\deg^{+}(\beta_{i_{2}}):\beta_{i_{2}}\neq 0\}$ and $\deg^{+}(\gamma_{max_{2}})=\max_{0\leq i_{2}<n_{2}}\{\deg^{+}(\gamma_{i_{2}}):\gamma_{i_{2}}\neq 0\}$, respectively. Consider now Equation 1 for $i=max_{1}+max_{2}$. Take any pair of indexes $i_{1},i_{2}$ of the sum such that $i_{1}\neq max_{1}$, $i_{2}\neq max_{2}$, $\beta_{i_{1}}\neq 0$, and $\gamma_{i_{2}}\neq 0$. If $i_{1}<max_{1}$ (and then $i_{2}>max_{2}$), resp., if $i_{1}>max_{1}$ (and then $i_{2}<max_{2}$), we get that

   $$\deg^{+}(\beta_{i_{1}})+\deg^{+}(\gamma_{i_{2}})<\deg^{+}(\beta_{i_{1}})+\deg^{+}(\gamma_{max_{2}})\leq\deg^{+}(\beta_{max_{1}})+\deg^{+}(\gamma_{max_{2}})\enspace,$$

   resp.,

   $$\deg^{+}(\beta_{i_{1}})+\deg^{+}(\gamma_{i_{2}})<\deg^{+}(\beta_{max_{1}})+\deg^{+}(\gamma_{i_{2}})\leq\deg^{+}(\beta_{max_{1}})+\deg^{+}(\gamma_{max_{2}})\enspace.$$

   Hence, $\deg^{+}(\beta_{i_{1}}\gamma_{i_{2}})<\deg^{+}(\beta_{max_{1}}\gamma_{max_{2}})$. This implies that $deg^{+}(\alpha_{max_{1}+max_{2}})=\deg^{+}(\beta_{max_{1}}\gamma_{max_{2}})$. Moreover, $deg^{+}(\alpha_{max_{1}+max_{2}})=\deg^{+}(\beta_{max_{1}}\gamma_{max_{2}})\geq\deg^{+}(\beta_{0}\gamma_{0})=\deg^{+}(\alpha_{0})$ and in a symmetric way, one also gets that $deg^{-}(\alpha_{i})\leq deg^{-}(\alpha_{0})$ for some $i\in\{1,\ldots,n-1\}$.

Therefore, in both cases it follows that $\pi$ is not expansive and this concludes the proof. ∎

It is an immediate consequence of the fact that ${\cal F}$ is open and, hence, it is both left and right closing. ∎

We start to prove that if $\mathcal{G}$ is positively expansive then ${\cal F}$ is too. Let us suppose that ${\cal F}$ is not positively expansive and the first condition from Lemma 6 holds, i.e., there exists $\upsilon\in Left(\mathbb{S}^{n}_{p},0)$ with $\upsilon\neq 0$ such that $A^{\ell}\upsilon\in Left^{*}(\mathbb{S}^{n}_{p},s)$ for every natural $\ell>0$, where $s>0$ is some integer constant depending on ${\cal F}$ (the proof is symmetric if one supposes that the second condition holds). Set $\omega=p^{k-1}\upsilon$. Clearly, $\omega\in Left(\mathbb{S}^{n}_{p^{k}},0)$ and $\omega\neq 0$. Since $B$ can be written as $A+pN$ for some matrix $N\in\mathbb{L}_{p^{k-1}}^{n\times n}$, it holds that for every natural $\ell>0$

where all the sums and products of coefficients of the Laurent polynomials/series inside the previous equalities are now meant in $\mathbb{Z}_{p^{k}}$. Hence, although $A\in\mathbb{L}_{p}^{n\times n}$ and $\upsilon\in\mathbb{S}_{p}^{n}$, in general $A^{\ell}\upsilon$ now belongs to $\mathbb{S}^{n}_{p^{k}}$ instead of $\mathbb{S}^{n}_{p}$ and, as a consequence, we can not immediately conclude that $B^{\ell}\omega=p^{k-1}A^{\ell}\upsilon\in Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$ immediately follows just from the hypothesis as it is, i.e., $A^{\ell}\upsilon\in Left^{*}(\mathbb{S}^{n}_{p},s)$ when $A^{\ell}\upsilon$ is considered as an element of $\mathbb{S}^{n}_{p}$. However, since $A^{\ell}\upsilon\in\mathbb{S}^{n}_{p^{k}}$ can be written as $(A^{\ell}\upsilon)\,\mathrm{mod}\,p+p\omega^{\prime}$ for some $\omega^{\prime}\in\mathbb{S}^{n}_{p^{k-1}}$ and, by hypothesis, $(A^{\ell}\upsilon)\,\mathrm{mod}\,p\in Left^{*}(\mathbb{S}^{n}_{p},s)$, we get that $B^{\ell}\omega=p^{k-1}[(A^{\ell}\upsilon)\,\mathrm{mod}\,p+p\omega^{\prime}]=p^{k-1}[(A^{\ell}\upsilon)\,\mathrm{mod}\,p]\in Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$ for every natural $\ell>0$. Therefore, by Lemma 6, $\mathcal{G}$ is not positively expansive.

We now prove that if ${\cal F}$ is positively expansive then $\mathcal{G}$ is too. Let us suppose that $\mathcal{G}$ is not positively expansive and the first condition from Lemma 6 holds, i.e., there exists $\omega\in Left(\mathbb{S}^{n}_{p^{k}},0)$ with $\omega\neq 0$ such that $B^{\ell}\omega\in Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$ for every natural $\ell>0$, where $s>0$ is some integer constant depending on $\mathcal{G}$ (again, the proof is symmetric if one supposes that the second condition holds). We deal with the following two mutually exclusive cases.

• If there is no $\omega^{\prime}$ such that $\omega=p\omega^{\prime}$, then set $\upsilon=\omega\,\mathrm{mod}\,p$. Clearly, $\upsilon\neq 0$ and $\upsilon\in Left(\mathbb{S}^{n}_{p},h)$ for some integer $h\leq 0$. Moreover, it holds that $A^{\ell}\upsilon=(B\,\mathrm{mod}\,p)^{\ell}(\omega\,\mathrm{mod}\,p)=(B^{\ell}\omega)\,\mathrm{mod}\,p\in Left^{*}(\mathbb{S}^{n}_{p},s)$ for every natural $\ell>0$.

• Otherwise, let $j\in\{1,\ldots,k-1\}$ and $\omega^{\prime}\in\mathbb{S}^{n}_{p^{k}}$ be such that $\omega=p^{j}\omega^{\prime}$, where $j$ is the largest natural such that all the coefficients of the $n$ Laurent series forming $\omega$ are multiple of $p^{j}$. Set $\upsilon=\omega^{\prime}\,\mathrm{mod}\,p$. Clearly, $\upsilon\neq 0$ and $\upsilon\in Left(\mathbb{S}^{n}_{p},h)$ for some integer $h\leq 0$. Since $p^{j}B^{\ell}\omega^{\prime}=B^{\ell}\omega\in Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$, either $B^{\ell}\omega^{\prime}\in Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$ or $B^{\ell}\omega^{\prime}\notin Left^{*}(\mathbb{S}^{n}_{p^{k}},s)$ happens, but, in both situations it must hold that $(B^{\ell}\omega^{\prime})\,\mathrm{mod}\,p\in Left^{*}(\mathbb{S}^{n}_{p},s)$. Therefore, it follows that $A^{\ell}\upsilon=(B\,\mathrm{mod}\,p)^{\ell}(\omega^{\prime}\,\mathrm{mod}\,p)=(B^{\ell}\omega^{\prime})\,\mathrm{mod}\,p\in Left^{*}(\mathbb{S}^{n}_{p},s)$ for every natural $\ell>0$.

In both cases, the first condition of Lemma 6 is satisfied as far as ${\cal F}$ is concerned. Thus, ${\cal F}$ is not positively expansive and this concludes the proof that $\mathcal{G}$ is positively expansive if and only if ${\cal F}$ is positively expansive. By Theorem 8, it follows that $\mathcal{G}$ is positively expansive if and only if the matrix $B\,\mathrm{mod}\,p$ is expansive. ∎

Consider an arbitrary LCA ${\cal F}$ over $(\mathbb{Z}/m\mathbb{Z})^{n}$ and let $A\in{\mathbb{L}_{m}}^{n\times n}$ be the matrix associated with ${\cal F}$. Let $m=p_{1}^{k_{1}}\cdots p_{l}^{k_{l}}$ be the prime factor decomposition of $m$ and, for each $i\in\{1,\ldots,l\}$, let ${\cal F}_{i}$ be the LCA over $(\mathbb{Z}/(p_{i})^{k_{i}}\mathbb{Z})^{n}$ having $(A\,\mathrm{mod}\,(p_{i})^{k_{i}})\in{\mathbb{L}^{n\times n}_{(p_{i})^{k_{i}}}}$ as associated matrix. Since ${\cal F}$ is positively expansive if and only if every LCA ${\cal F}_{i}$ is too, by Lemma 9 and Theorem 8, it follows that ${\cal F}$ is positively expansive if and only if every matrix $(A\,\mathrm{mod}\,p_{i})\in{\mathbb{L}}_{p_{i}}^{n\times n}$ is expansive, the latter being a decidable property. Therefore, the statement is true. ∎