At <https://dmishin.github.io/js-revca/index.html>, you can play around with reversible cellular automata. I noticed that on that site, that for the reversible linear cellular automata (which I have tested), there is always a small natural number $p$ ($p\leq 12$ in the cases which I have tested) where if the grid is a torus whose dimensions are $2^{n}\times 2^{n}$, then when one runs the cellular automaton $p\cdot 2^{n}$ times, the resulting pattern is the identity function. In other words, if $A$ is the matrix for the linear transformation computing the cellular automaton, then $A^{p\cdot 2^{n}}=I\_{2^{2n}}$ but $A^{r}\neq I\_{2^{2n}}$ whenever $0<r<p\cdot 2^{n}$.


What is the mathematical explanation of this phenomenon? How pervasive is this phenomena of low periods?


Many of these rules have some sort of Sierpinski triangle pattern, but some have more complicated patterns.


For example, for the rule 0,12,10,6,3,15,9,5,11,7,1,13,8,4,2,14, we apparently have p=7.



Why do some linear cellular automata over $Z_{2}$ on the torus have small order?
So I have a proof of the low period phenomenon that works for all cellular automata prime characteristics $p$ and all finite dimensions (i.e. for linear cellular automata whose alphabet is a vector space of characteristic $p$ over a finite $p$-group). The general result can quite easily be verified empirically. These cellular automata could be applied to the reversible symmetric cryptosystems of the future since functions $f$ where $f^{m}=\textrm{Id}$ for some $m$ which are easily computable by a reversible computer will be important components of cryptographic hash functions of the future.


Let $G$ be a group and $A$ be a set. Then define $\phi\_{g}:A^{G}\rightarrow A^{G}$ by letting $\phi\_{g}(x\_{h})\_{h\in G}=(x\_{g+h})\_{h\in G}$.
A cellular automaton over the group $G$ and the alphabet $A$ is a map $\tau:A^{G}\rightarrow A^{G}$ such that
$\tau\phi\_{g}=\phi\_{g}\tau$ for all $g\in G$.


If $G$ is a group and $V$ is a vector space over a finite field $K$, then let $\textrm{LCA}(G;V)$ denote the collection of all linear cellular automata over the group $G$ with alphabet 
$V$. Let $c\_{a}=(a)\_{g\in G}\in V^{G}$ for each $a\in A$. If $V$ is a vector space over a field $K$ and $G$ is a group, the define a homomorphism
$\Gamma:\textrm{LCA}(G;V)\rightarrow\textrm{End}\_{K}(V)$ by letting $c\_{\Gamma(\tau)(a)}=\tau(c\_{a})$.


Theorem: Let $K$ be a finite field of prime characteristic $p$ and let $V$ be a vector space over $K$. Let $G=Z\_{p^{a\_{1}}}\times Z\_{p^{a\_{r}}}$. Let $m=p^{a\_{1}}+...+p^{a\_{r}}$. Let $n'$ be a natural number such that
$p^{n'}\geq m$ and let $n=p^{n'}$.


1. Suppose that $r\in \textrm{LCA}(G;V)$ and $\Gamma(r)=0$. Then $r^{m}=0$.
2. Suppose that $r\in \textrm{LCA}(G;V)$ and $\Gamma(r)=1$. Then $r^{n}=1$.
3. Suppose that $r\in\textrm{LCA}(G;V)$ and $\Gamma(r)^{k}=0$. Then $r^{km}=0$.
4. Suppose that $r\in\textrm{LCA}(G;V)$ and $\Gamma(r)^{k}=1$. Then $r^{kn}=1$.


Proof: Statement 2 follows from statement 1; if $\Gamma(r)=1$, then $\Gamma(r-1)=0$, so $r^{n}-1=(r-1)^{n}=0$, hence $r^{n}=1$.
Statements 2-4 therefore all follow from statement $1$, so it suffices to prove statement 1.


Suppose that $\Gamma(r)=0$. Now, suppose that
 $$r(x\_{\alpha})\_{\alpha\in G}=(\sum\_{\beta\in G}R\_{\beta}x\_{\alpha+\beta})\_{\alpha\in G}.$$
Then since $\Gamma(r)=0$, we know that $\sum\_{\beta\in G}R\_{\beta}=0$, so $$R\_{0}=-\sum\_{\beta\in G^{+}}R\_{\beta}.$$ Therefore,
$$r^{m}(x\_{\alpha})\_{\alpha\in G}=(\sum\_{\beta\_{1},...,\beta\_{m}\in G^{+}}\sum\_{u\_{1},...,u\_{m}\in\{0,1\}^{m}}(-1)^{m+u\_{1}+...u\_{m}}R\_{\beta}x\_{\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m}})\_{\alpha\in G}$$
$$=(\sum\_{\beta\_{1},...,\beta\_{m}\in G^{+}}R\_{\beta}\sum\_{u\_{1},...,u\_{m}\in\{0,1\}^{m}}(-1)^{m+u\_{1}+...u\_{m}}x\_{\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m}})\_{\alpha\in G}.$$


It therefore suffices to show that 
$$\sum\_{u\_{1},...,u\_{m}\in\{0,1\}^{m}}(-1)^{m+u\_{1}+...u\_{m}}x\_{\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m}}=0$$
for all $\alpha,\beta\_{1},...,\beta\_{m}\in G$.


To verify this claim, we shall verify that $$\sum\_{u\_{1},...,u\_{m}\in\{0,1\}^{m}}(-1)^{m+u\_{1}+...u\_{m}}\cdot(\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m})=0$$ where the element $$(-1)^{m+u\_{1}+...u\_{m}}\cdot(\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m})$$
is considered as an object in the group ring $K[G]$, Take note that
$$\sum\_{u\_{1},...,u\_{m}\in\{0,1\}^{m}}(-1)^{m+u\_{1}+...u\_{m}}\cdot(\alpha+u\_{1}\beta\_{1}+...u\_{m}\beta\_{m})=\alpha\cdot(\beta\_{1}-1)\cdot...\cdot(\beta\_{m}-1).$$


Now, take note that the group-ring $K[G]$ is isomorphic to the ring $$K[x\_{1},...,x\_{r}]/\langle x\_{1}^{p^{a\_{1}}}-1,...,x\_{r}^{p^{a\_{r}}}-1\rangle,$$ and by this isomorphism, $\alpha\cdot(\beta\_{1}-1)\cdot...\cdot(\beta\_{m}-1)$ is sent to
$$\mathbf{x}^{\alpha}\cdot(\mathbf{x}^{\beta\_{1}}-1)\dots(\mathbf{x}^{\beta\_{m}}-1)+\langle x\_{1}^{p^{a\_{1}}}-1,...,x\_{r}^{p^{a\_{r}}}-1\rangle.$$
 Now, 
 $$K[x\_{1},...,x\_{r}]/\langle x\_{1}^{p^{a\_{1}}}-1,...,x\_{r}^{p^{a\_{r}}}-1\rangle=
K[x\_{1},...,x\_{r}]/\langle (x\_{1}-1)^{p^{a\_{1}}},...,(x\_{r}-1)^{p^{a\_{r}}}\rangle$$ and the automorphism $\Phi:K[x\_{1},...,x\_{r}]\rightarrow K[x\_{1},...,x\_{r}]$ defined by $\Phi(x\_{i})=x\_{i}+1$ induces an isomorphism on the quotient rings $$\Phi^{\*}:K[x\_{1},...,x\_{r}]/\langle x\_{1}^{p^{a\_{1}}}-1,...,x\_{r}^{p^{a\_{r}}}-1\rangle
\rightarrow K[x\_{1},...,x\_{r}]/\langle x\_{1}^{p^{a\_{1}}},...,x\_{r}^{p^{a\_{r}}}\rangle$$
and
$$\Phi^{\*}(\mathbf{x}^{\alpha}\cdot(\mathbf{x}^{\beta\_{1}}-1)\dots(\mathbf{x}^{\beta\_{m}}-1)+\langle x\_{1}^{p^{a\_{1}}}-1,...,x\_{r}^{p^{a\_{r}}}-1\rangle)$$
$$=p(\mathbf{x})f\_{1}(\mathbf{x})\dots f\_{m}(\mathbf{x})+\langle x\_{1}^{p\_{a\_{1}}},\dots,x\_{r}^{p\_{a\_{r}}}\rangle$$
for some polynomials
$f\_{1},...,f\_{m}$ with $f\_{1}(\mathbf{0})=\dots=f\_{m}(\mathbf{0})=0$. Since $$f\_{1}(\mathbf{0})=\dots=f\_{m}(\mathbf{0})=0,$$
we conclude that
$f\_{i}=\sum\_{\beta\neq 0}a\_{i,\beta}\mathbf{x}^{\beta}$. However,
$$f\_{1}(\mathbf{x})\dots f\_{m}(\mathbf{x})=\sum\_{\beta\_{1}\neq 0,...,\beta\_{m}\neq 0}a\_{1,\beta\_{1}}...a\_{m,\beta\_{m}}\mathbf{x}^{\beta\_{1}+...+\beta\_{m}}\in
\langle x\_{1}^{p\_{a\_{1}}},\dots,x\_{r}^{p\_{a\_{r}}}\rangle.$$
Therefore,
$$p(\mathbf{x})f\_{1}(\mathbf{x})\dots f\_{m}(\mathbf{x})+\langle x\_{1}^{p\_{a\_{1}}},\dots,x\_{r}^{p\_{a\_{r}}}\rangle=0.$$
We therefore conclude that
$r^{m}(x\_{\alpha})\_{\alpha\in G}=0$. $\mathbf{QED}$


