# Multiband linear cellular automata
and endomorphisms of algebraic vector groups

Jakub Byszewski  Wydział Matematyki i Informatyki Uniwersytetu
Jagiellońskiego, ul. S. Łojasiewicza 6, 30-348 Kraków, Polska
<EMAIL_ADDRESS>and  Gunther Cornelissen  Mathematisch Instituut,
Universiteit Utrecht, Postbus 80.010, 3508 TA Utrecht, Nederland
<EMAIL_ADDRESS>
(Date: August 28, 2024)

###### Abstract.

We propose a correspondence between certain multiband linear cellular
automata—models of computation widely used in the description of physical
phenomena—and endomorphisms of certain algebraic unipotent groups over finite
fields. The correspondence is based on the construction of a universal element
specialising to a normal generator for any finite field.
We use this correspondence to deduce new results concerning the temporal
dynamics of such automata, using our prior, purely algebraic, study of the
endomorphism ring of vector groups. These produce ‘for free’ a formula for the
number of fixed points of the $n$-iterate in terms of the $p$-adic valuation
of $n$, a dichotomy for the Artin–Mazur dynamical zeta function, and an
asymptotic formula for the number of periodic orbits.
Since multiband linear cellular automata simulate higher order linear automata
(in which states depend on finitely many prior temporal states, not just the
direct predecessor), the results apply equally well to that class.

###### Key words and phrases:

linear cellular automata, convolutional codes, periodic orbits, algebraic
vector groups

###### 2010 Mathematics Subject Classification:

20G40, 37B15

JB was supported by the National Science Centre, Poland under grant no.
2018/29/B/ST1/01340

## Introduction

This paper proposes a bridge between (small parts of) the world of
computational physics and the world of algebraic geometry in positive
characteristic.

### Context

Cellular automata are concurrent models of computation described in the middle
of the 20th century by Ulam and von Neumann [18], and are helpful in modelling
various biological, chemical, and physical processes, ranging from pigment
distribution on seashells to the Belousov–Zhabotinsky reaction, which forms
the foundation of the construction of a ‘chemical computer’ [7]. From a
mathematical, computer science, and statistical-physics perspective, even one-
dimensional cellular automata show complex behaviour, as pointed out by
Wolfram and others [20]; the very simple looking rules of certain one-
dimensional cellular automata lead to computational universality in the sense
of being able to simulate any Turing machine [4].

Here, we are concerned with a very simple class of linear one-dimensional
cellular automata for which the states are described by elements of an
$r$-dimensional vector space $V:=\mathbf{F}_{p}^{r}$ over a finite field
$\mathbf{F}_{p}$ with $p$ elements, as studied in [12]. Note that by working
over $\mathbf{F}_{p}$, ‘linear’ is the same as ‘additive’, and additive
automata over $\mathbf{F}_{p^{N}}^{r}$ can be seen as linear automata over
$\mathbf{F}_{p}^{Nr}$. Linearity is a restriction: for example, the resulting
machines are never universal [12, Theorem 4.12]; however, in general, linear
cellular automata are transitive dynamical systems with a dense set of
periodic points, so chaotic in the sense of Devaney [9].

An early detailed study of dynamical properties of some examples can be found
in [14]. A very general framework of group-based automata can be found in [3,
Chapter 8], where invertibility and the Garden-of-Eden theorem are discussed
(see also [12, Proposition 3.2]). For $r=1$, Ward connected such automata to
number-theoretical dynamical systems, and used this to provide very clean
proofs of some properties related to periodic points and entropy [19] (see
also [2, Chapter 8]). By contrast, for general $r$ several ‘bits’ (units of
information, in our case elements111Sometimes these are called ‘pits’ for
$\mathbf{F}_{p}$ and ‘qits’ for $\mathbf{F}_{q}$, but we will not use this
terminology. of $\mathbf{F}_{p}$) are stored in one state; the corresponding
systems are called multiband linear cellular automata [11], and the dynamics
of such automata is considered much more complex [5, p. 64].222We will refrain
from referring to $r$ as ‘dimension’, since that word is used in the theory of
automata for the grid size dimension, which in this paper is always $1$;
nevertheless, via our correspondence $r$ becomes the dimension of the
associated vector group. The interest in such multiband automata arises from
the fact that they can be used to simulate higher-order linear cellular
automata, i.e. automata where transition rules depend not only on the
immediately preceding configuration, but on finitely many earlier
configurations [12, Proposition 3.1], [6]. In fact, most (bio-)chemical
applications use state spaces of greater complexity than merely a single bit.

In this paper we link the dynamics of such automata corresponds to that of
endomorphisms of the vector group
$\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$, where
$\overline{\mathbf{F}}_{p}$ is the algebraic closure of $\mathbf{F}_{p}$.
Results on periodic points for the cellular automaton follow in a
straightforward manner from our previous study of dynamics on algebraic groups
[2], similarly to how Ward was able to use prior number-theoretical work for
$r=1$. It applies to general $r\geqslant 1$ (and thus, also to higher order
additive cellular automata over $\mathbf{F}_{p}$) and allows us to avoid
considering special cases, only requiring a bit of algebra as in [2, §4.2].

######  Exercise A.

Let $f_{n}$ denote the number of solutions $x\in\overline{\mathbf{F}}_{p}$ of
the equation $f^{\circ n}(x)=x$ where $f(x)=x^{p}+x$ with the notation
$f^{\circ n}=f\circ\dots\circ f$ for the $n$-fold iterate of $f$, and let
$g_{n}$ denote the number of sequences
$y=(y_{i})\in\mathbf{F}_{p}^{\mathbf{Z}}$ for which $g^{\circ n}(y)=y$ with
$g((y_{i}))=(y_{i}+y_{i+1})$; then $f_{n}=g_{n}$ for all $n$.333 In fact,
$\log_{p}f_{n}=n-p^{v_{p}(n)}$ where $v_{p}$ is the $p$-adic valuation.

Is the equality between the number of periodic points of given period for the
two maps $f$ and $g$ in Exercise A a coincidence? The map $f$ is an
endomorphism of the additive group $\mathbf{G}_{a}(\overline{\mathbf{F}}_{p})$
and the map $g$ describes a linear cellular automaton with alphabet
$\mathbf{F}_{p}$.

### Definitions and main result

Let us specify the definition of the cellular automata we will consider.

######  Definition B.

Let $S=V^{\mathbf{Z}}$ be the set of bi-infinite sequences $(y_{i})$ of
elements of the vector space $V:=\mathbf{F}_{p}^{r}$, carrying the product
topology of the trivial topology on $V$. A ($V$-)_multiband linear cellular
automaton_ is a continuous $\mathbf{F}_{p}$-linear self-map $g\colon
S\rightarrow S$ that commutes with the shift $s\colon S\rightarrow S$ given by
$s((y_{i}))=(y_{i+1})$. We say the automaton is _on the alphabet
$\mathbf{F}_{p}^{r}$_. We will denote the cellular automaton by the map $g$,
or, if we want to stress the space, also by $(S,g)$.

In the terminology of topological dynamics, $g$ is an endomorphism of the full
shift on $S$. By the Curtis–Hedlund–Lyndon theorem ([10], [3, Theorem 1.8.1])
and additivity, $g$ is determined by its _local rule_

$g((y_{i}))_{0}=\sum_{j}m_{j}y_{j}$

for finitely many matrices
$m_{j}\in\mathrm{End}(V)\cong\mathrm{M}_{r}(\mathbf{F}_{p})$, and we can
consider $g$ as a _convolutional encoder_ [13, §1.6] in the following sense:
we represent the sequence $(y_{i})$ by the bi-infinite power series
$Y(Z):=\sum y_{i}Z^{i}\in V[\\![Z,Z^{-1}]\\!]$, and $g$ by multiplication with
the Laurent polynomial

$G(Z):=\sum_{j}m_{j}Z^{j}\in\mathrm{End}(V)[Z,Z^{-1}].$

We can rewrite $G(Z)$ as a matrix of Laurent polynomials
$G(Z)\in\mathrm{M}_{r\times r}(\mathbf{F}_{p}[Z,Z^{-1}])$. We will call the
cellular automaton _one-sided_ if $G(Z)\in\mathrm{M}_{r\times
r}(\mathbf{F}_{p}[Z])$ is a matrix of polynomials.

######  Remark C.

One may consider $g$ as defining a discrete-time dynamics on $S$; if we
indicate by $y^{(t)}=(y^{(t)}_{i})\in S$ a state ‘at time
$t\in\\{0,1,2,\dots\\}$’, then we set $y^{(t+1)}=g(y^{(t)})$. The dynamical
properties of this system are called ‘temporal’, in order to distinguish them
from properties of the entries of $y$ at a fixed time, e.g. with respect to
the shift map, that are called ‘spatial’. A state is only dependent on the
immediate predecessor in time, but as we remarked above, by allowing $r>1$, we
can simulate any higher order linear cellular automaton, i.e. an additive
automaton in which a state $y^{(t)}$ depends on finitely many predecessors
$y^{(t-1)},\dots,y^{(t-k)}$ in time. If this dependency is written as

$Y^{(t)}(Z)=\sum_{j=1}^{s}G_{j}(Z)Y^{(t-j)}(Z)$

for $Y^{(t)}(Z)=\sum y_{i}^{(t)}Z^{i}$ with $G_{j}(Z)\in\mathrm{M}_{r\times
r}(\mathbf{F}_{p}[Z,Z^{-1}])$, then the first-order simulation corresponds to
the block matrix

${\tiny\left(\begin{array}[]{ccccc}G_{1}(Z)&G_{2}(Z)&\ldots&&G_{s}(Z)\\\
I_{r}&&&&\\\ &I_{r}&&&\\\ &&\tiny{\ddots}&&\\\
&&&I_{r}&\end{array}\right)}\in\mathrm{M}_{rs\times
rs}(\mathbf{F}_{p}[Z,Z^{-1}])\mbox{ acting on
}{\tiny\left(\begin{array}[]{c}Y^{(t-1)}(Z)\\\ Y^{(t-2)}(Z)\\\ {\vdots}\\\
Y^{(t-s)}(Z)\end{array}\right)}\in V^{s}[\\![Z,Z^{-1}]\\!].$

The other objects we consider are the following.

######  Definition D.

We let $\mathbf{G}_{a}$ denote the additive algebraic group, so for a field
$K$, $\mathbf{G}_{a}(K)$ is the additive group of $K$. An algebraic group of
the form $\mathbf{G}_{a}^{r}$ is called a _vector group_ (a particular example
of a unipotent algebraic group); its $K$-points form an $r$-dimensional
$K$-vector space, and we denote them as _column_ vectors. Let $F$ denote the
Frobenius operator of raising to the power $p$. We say an endomorphism of
$\mathbf{G}_{a}^{r}$ is _defined over $\mathbf{F}_{p}$_ if it commutes with
the Frobenius.

Endomorphisms $\sigma\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$ of
the vector group $\mathbf{G}_{a}^{r}$ over a field $K$ of characteristic $p>0$
can be studied using noncommutative algebra: they are described by $r\times r$
matrices $m_{\sigma}$ with entries from the skew polynomial ring
$K\langle\phi\rangle$, where $\phi a=a^{p}\phi$ for all $a\in K$ [2, §4.2].
The endomorphisms defined over $\mathbf{F}_{p}$ form a commutative subring
isomorphic to the matrix ring over the polynomial ring $\mathbf{F}_{p}[\phi]$.
This allows us to identify one-sided automata directly with endomorphisms of
algebraic groups by identifying the variables $\phi$ and $Z$.

We now describe a less obvious result that gives a direct connection between
fixed point sets for multiband linear cellular automata and endomorphisms of
vector groups.

######  Definition E.

Suppose $f\colon X\rightarrow X$ is a self-map on some set $X$.

  * •

We define the _set of fixed points_ as $\mathrm{Fix}(f)=\\{x\in X\colon
f(x)=x\\}.$ A fixed point of $f^{\circ n}$ for some $n\geqslant 1$ is called a
_periodic point_.

  * •

We call the map $f$ _confined_ if $\\#\mathrm{Fix}(f^{\circ n})$ is finite for
all $n\geqslant 1$.

  * •

We denote by $\mathscr{P}\subseteq S$ the subset of sequences that are
periodic for the shift map $s\colon S\rightarrow S$, and call these _shift-
periodic sequences_.

Given a cellular automaton $g$, the finite orbit of a periodic point of
$g\colon S\rightarrow S$ is sometimes called a ‘temporal cycle’ to distinguish
them from cycles for the shift map $s\colon S\rightarrow S$, which are called
‘spatial cycles’.

######  Theorem F.

There is an injective group homomorphism
$\iota\colon\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})\rightarrow(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$
such that the following hold:

  1. (i)

We have $\iota(Fx)=s(\iota(x))$, where $F$ is the Frobenius operator, and $s$
the shift.

  2. (ii)

The image of $\iota$ consists exactly of the subgroup $\mathscr{P}$ of shift-
periodic sequences of $(\mathbf{F}_{p}^{r})^{\mathbf{Z}}.$

  3. (iii)

There is a bijection $\sigma\mapsto g_{\sigma}$ between endomorphisms $\sigma$
of the group $\mathbf{G}_{a}^{r}$ defined over $\mathbf{F}_{p}$ and one-sided
$\mathbf{F}^{r}_{p}$-multiband linear cellular automata $g_{\sigma}$ such that
for all $n\geqslant 1$, the map $\iota$ induces a group isomorphism

$\mathrm{Fix}(\sigma^{\circ
n})\stackrel{{\scriptstyle\iota}}{{\cong}}\mathrm{Fix}(g_{\sigma}^{\circ
n})\cap\mathscr{P}.$ (1)

  4. (iv)

The endomorphism $\sigma$ is confined if and only if the cellular automaton
$g_{\sigma}$ is confined, in which case all periodic points of $g_{\sigma}$
are shift-periodic and $\iota$ induces a group isomorphism

$\mathrm{Fix}(\sigma^{\circ
n})\stackrel{{\scriptstyle\iota}}{{\cong}}\mathrm{Fix}(g_{\sigma}^{\circ n}).$
(2)

The main innovation in the theorem seems to be the link between, on the one
hand, points over _the algebraic closure_ of $\mathbf{F}_{p}$ with Galois
action and, on the other hand, periodic sequences _with entries in_
$\mathbf{F}_{p}^{r}$ with the action of the shift map. Being defined over
$\mathbf{F}_{p}$ is natural from the point of view of the correspondence: it
means invariance under $F$, which translates to the shift-commutation property
of the cellular automaton. The action of the absolute Galois group
$\mathrm{Gal}(\overline{\mathbf{F}}_{p}/\mathbf{F}_{p})$ on the algebraic
group corresponds to profinite shifts in the cellular space, cf. Remark 1.2.4
below. Confinedness is required to match sets of fixed points exactly; for
example, the identity map fixes the countable set
$\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$ on the one side and the
uncountable set $S$ on the other side, and the
$\overline{\mathbf{F}}_{p}$-rational points in the algebraic group correspond
to the shift-periodic sequences only.

### Corollaries of the correspondence

Since the group $G$ is commutative, the number of fixed points of an
endomorphism $\sigma\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$ in
$\mathbf{G}_{a}^{r}(K)$ for any algebraically closed field of characteristic
$p>0$ is equal to the cardinality of $\ker(\sigma-1)(K)$, which can be
computed as the quotient of the degree of the map $\sigma-1$ by its
inseparability degree, and this can be identified with

$p^{\deg_{\phi}(\mathrm{ddet}(m_{\sigma-1}))-v_{\phi}(\mathrm{ddet}(m_{\sigma-1}))}$

where $\mathrm{ddet}$ is the Dieudonné determinant, and $\deg_{\phi}$ and
$v_{\phi}$ are the degrees of the leading and trailing coefficients in $\phi$
[2, Lemma 4.2.2]. If $\sigma$ is defined over $\mathbf{F}_{p}$, one may use
commutative linear algebra of matrices over polynomial rings and the usual
determinant rather than the Dieudonné determinant.

We have used these observations in [2] to understand the orbit structure of
such systems. The results can be directly translated to the setting of _one-
sided_ cellular automata; to the best of our knowledge, in this generality the
results are new. To obtain analogous results for general two-sided automata,
we first perform some shifts and reduce to a counting problem for more general
coincidence sets rather than periodic points (that are coincidence sets for
iterates of a map and the identity map), to which the methods from [2] can
also be applied.

######  Proposition G.

If $g$ is a confined linear multiband cellular automaton on an alphabet
$\mathbf{F}_{p}^{r}$, then for all $n\geqslant 1$ we have

$\log_{p}\\#\mathrm{Fix}(g^{\circ n})=na-t_{n}p^{v_{p}(n)}$ (3)

for some $a\in\mathbf{Z}_{\geqslant 0}$ and some periodic sequence $(t_{n})$
with $t_{n}\in\mathbf{Z}_{\geqslant 0}$ of period $\varpi$ coprime to $p$ and
satisfying $t_{n}=t_{\mathrm{gcd}(n,\varpi)}$, where $v_{p}$ is the $p$-adic
valuation. The exact value of $a,t_{n},\varpi$ is as given in Remark 2.1.3.

Following Artin and Mazur [1], the sequence counting fixed points of iterates
of a confined map can be studied using the _dynamical zeta function_

$\zeta_{g}(z):=\exp\sum_{n\geqslant 1}\left(\\#\mathrm{Fix}(g^{\circ
n})z^{n}/n\right).$

Using our previous results concerning this zeta function for endomorphisms of
additive groups, we can transfer the following results to cellular automata.
The case $a=0$ needs some prior attention, see Lemma 2.1.4.

######  Corollary H.

Let $g$ be a confined multiband linear cellular automaton on an alphabet
$\mathbf{F}_{p}^{r}$ with invariants $a$ and $(t_{n})$ as in Proposition G.
Then the dynamical zeta function of $g$ is either the rational function
$1/(1-p^{a}z)$ or it cannot be analytically continued over any point of the
circle of convergence $|z|=1/p^{a}$. The first case happens if and only if
$t_{n}=0$ for all $n$.

######  Corollary I.

For a confined linear multiband cellular automaton $g$ on an alphabet
$\mathbf{F}_{p}^{r}$, the number $P_{\ell}$ of periodic orbits of length
$\ell$ is asymptotically equal to

${p^{\ell a-t_{\ell}p^{v_{p}(\ell)}}}/{\ell}+O(\sqrt{p^{\ell a}}),$ (4)

where $a$ and $t_{\ell}$ are as in Proposition G.

######  Example J.

For $r=1$ and $g=F$, Corollary I is the so-called Prime Polynomial Theorem
first mentioned in §342–347 of the drafted eighth chapter ‘Disquisitiones
generales de congruentiis’ of Gauß’s Disquisitiones Arithmeticae, cf. [17,
Theorem 2.2], stating that the number of irreducible polynomials of degree
$\ell$ over $\mathbf{F}_{p}$ is asymptotically equal to
$p^{\ell}/\ell+O(p^{\ell/2})$. The dynamical zeta function in this case is the
innocuous Weil zeta function of $\mathbf{A}^{1}_{\mathbf{F}_{p}}$, given by
$1/(1-pz)$. This setup corresponds to the cellular automaton with state space
$\mathbf{F}_{p}^{\mathbf{Z}}$ and map $(y_{i})\mapsto(y_{i+1})$.

######  Remark K.

Equation (4) can be used to study the limit behaviour of the _periodic orbit
counting function_ defined as

$\pi(X)=\sum_{\ell\leqslant X}P_{\ell}.$

If $a=0$, there are finitely many periodic points (cf. Lemma 2.1.4) and
$\pi(X)$ is eventually constant. If $a\neq 0$, then the function
$X\pi(X)/p^{aX}$ has a well-defined limit precisely if $t_{n}=0$ for all $n$,
and that limit then equals $p^{a}/(p^{a}-1)$. In general, the function
$X\pi(X)/p^{aX}$ has uncountably many accumulation points arising from
restricting the values of $X$ to sequences of integers converging
simultaneously modulo the period $\varpi$ and $p$-adically. See [2, Theorems
11.3.3 & 11.4.1] for details.

##  1\. Construction and first properties of the map $\iota$

###  1.1. Traces

Consider an extension of finite fields
${\mathbf{F}_{p^{N}}}/{\mathbf{F}_{p^{M}}}$ with $M$ dividing $N$. Let
$G_{N,M}$ denote its Galois group—cyclic of order $N/M$—, and write

$\operatorname{tr}_{N,M}(x):=\sum\limits_{\tau\in G_{N,M}}\tau(x)$

for the relative trace map. This is an additive surjective map
$\mathbf{G}_{a}(\mathbf{F}_{p^{N}})\rightarrow\mathbf{G}_{a}(\mathbf{F}_{p^{M}})$
that commutes with the action of the Frobenius operator $F$. Furthermore, the
bilinear map
$\mathbf{F}_{p^{N}}\times\mathbf{F}_{p^{N}}\rightarrow\mathbf{F}_{p^{M}}$
given by

$\langle x,y\rangle:=\operatorname{tr}_{N,M}(xy)$

is non-degenerate [15, §2.1.4, Theorem 2.1.84].

######  Definition 1.1.1.

Taking inverse limits in the category of abelian groups with the relative
trace maps as connecting homomorphisms, define

$\mathscr{F}=\varprojlim\limits_{\stackrel{{\scriptstyle M\mid
N}}{{\operatorname{tr}_{N,M}}}}\mathbf{G}_{a}(\mathbf{F}_{p^{N}}).$

If $\\{G_{i}\\}$ is an inverse system of groups with $G=\varprojlim G_{i}$,
the inverse limit of group rings $\varprojlim\mathbf{F}_{p}[G_{i}]$ is denoted
as $\mathbf{F}_{p}[\\![G]\\!]$ and called the _complete group ring_. This
profinite ring contains the group ring $\mathbf{F}_{p}[G]$ as a dense subset
[16, §5.3].

######  Proposition 1.1.2.

$\mathscr{F}$ is a free $\mathbf{F}_{p}[\\![\widehat{\mathbf{Z}}]\\!]$-module
of rank $1$. Thus, there exists $\alpha\in\mathscr{F}$ that for every $N$
projects to an element $\alpha_{N}\in\mathbf{F}_{p^{N}}$ that generates a
normal basis.

###### Proof.

The existence of a normal basis for a finite extension of finite fields [15,
Theorem 5.2.1] shows that $\mathbf{G}_{a}(\mathbf{F}_{p^{N}})$ is a free
$\mathbf{F}_{p}[G_{N,1}]$-module of rank $1$; a generator of this module is
precisely a normal basis generator of $\mathbf{F}_{p^{N}}$ over
$\mathbf{F}_{p}$.

Let $B_{N}\subset\mathbf{G}_{a}(\mathbf{F}_{p^{N}})$ denote the set of
generators of $\mathbf{G}_{a}(\mathbf{F}_{p^{N}})$ as an
$\mathbf{F}_{p}[G_{N,1}]$-module. The map $\operatorname{tr}_{N,M}$ is
surjective, and so via this map $\mathbf{G}_{a}(\mathbf{F}_{p^{M}})$ can be
regarded as a quotient module of $\mathbf{G}_{a}(\mathbf{F}_{p^{N}})$ (where
$\mathbf{G}_{a}(\mathbf{F}_{p^{M}})$ is regarded as a
$\mathbf{F}_{p}[G_{N,1}]$-module via the surjective map of rings
$\mathbf{F}_{p}[G_{N,1}]\to\mathbf{F}_{p}[G_{M,1}]$). Thus, for any
$\alpha_{N}\in B_{N}$ and $M{\mid}N$, $\operatorname{tr}_{N,M}(\alpha_{N})$
lies in $B_{M}$, and so $B_{N}$ form an inverse system of sets.

Since the inverse limit of a system of nonempty finite sets is nonempty [8,
3.2.13], there is an element $\alpha\in\mathscr{F}$ that maps to some
$\alpha_{N}\in B_{N}$ for all $N$. Using these compatible generators
$\alpha_{N}$, we construct an isomorphism

$\mathscr{F}\cong\varprojlim\mathbf{F}_{p}[G_{N,1}]=\mathbf{F}_{p}[\\![\varprojlim
G_{N,1}]\\!].$

The space $\mathscr{F}$ is indeed an
$\mathbf{F}_{p}[\\![\widehat{\mathbf{Z}}]\\!]$-module of rank $1$ under the
identification of $\widehat{\mathbf{Z}}$ with the absolute Galois group
$\mathrm{Gal}(\overline{\mathbf{F}}_{p}/\mathbf{F}_{p})=\varprojlim\limits_{N}G_{N,1}$
of $\mathbf{F}_{p}$.∎

######  Remark 1.1.3.

In defining $\mathscr{F}$, we use an inverse limit over trace maps to arrive
at an uncountable limit space, which turns out to be a free rank-$1$ module
under the action of the complete modular group ring of the absolute Galois
group of $\mathbf{F}_{p}$. By contrast, the direct limit of these spaces under
inclusions is $\mathbf{G}_{a}(\overline{\mathbf{F}}_{p})$, which is a
countable abelian group. We are using $\mathscr{F}$ as a receptacle for the
existence of a compatible set of normal bases for a tower of additive groups
of finite fields. Finding compatible models of the entire field structure
(i.e. finding the structure constants of the operation of multiplication on
compatible vector space bases) is much more difficult, see [15, §11.7].

###  1.2. Definition of the map $\iota$

Choose an element $\alpha=\varprojlim\alpha_{N}\in\mathscr{F}$ with
$\alpha_{N}\in\mathbf{F}_{p^{N}}$ satisfying

$\operatorname{tr}_{N,M}(\alpha_{N})=\alpha_{M}$

for all $M,N$. Let $y\in\overline{\mathbf{F}}_{p}$. Compatibility with the
relative trace maps implies that the expression
$\operatorname{tr}_{N,1}(\alpha_{N}y)$ for any $N$ with
$y\in\mathbf{F}_{p^{N}}$ is well-defined and independent of the choice of $N$.
We denote it simply by $\operatorname{tr}(\alpha y).$

######  Definition 1.2.1.

The map
$\iota_{\alpha}\colon\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})\rightarrow(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$
is given by

$\iota_{\alpha}(x):=(\operatorname{tr}(\alpha x^{p^{j}}))_{j\in\mathbf{Z}},$

where we apply the $p$-th power operation and trace map entry-wise to column
vectors.

######  Proposition 1.2.2.

The map $\iota_{\alpha}$ has the following properties:

  1. (i)

$\iota_{\alpha}$ is a group homomorphism for addition.

  2. (ii)

$\iota_{\alpha}$ is injective.

  3. (iii)

The image of $\iota_{\alpha}$ consists exactly of the subgroup $\mathscr{P}$
of all sequences that are periodic for the shift operator in
$(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$.

  4. (iv)

If $F$ denotes the Frobenius operator and $s$ is the shift operation, then
$\iota(Fx)=s(\iota(x))$.

###### Proof.

Part (i) is clear. For (ii), suppose $\operatorname{tr}(\alpha x^{p^{j}})=0$
for some $x\in\mathbf{F}_{p^{N}}$ and all $j$. Then, by invariance of the
trace under Frobenius, also $\operatorname{tr}(\alpha^{p^{-j}}x)=0$. Thus $x$
is orthogonal to the set of generators $\alpha_{N}^{p^{-j}}$ of
$\mathbf{F}_{p^{N}}$ as a vector space over $\mathbf{F}_{p}$, and by the
nondegeneracy of the trace form, $x=0$.

For part (iii), suppose that
$x\in\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$ belongs to
$\mathbf{G}_{a}^{r}(\mathbf{F}_{p^{N}})$. Now $\iota_{\alpha}$ induces an
injective map from $\mathbf{G}_{a}^{r}(\mathbf{F}_{p^{N}})$ to the set of
periodic sequences in $(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$ of period $N$, and
this map is also surjective for cardinality reasons.

For (iv), note that $\iota(F(x))=(\operatorname{tr}(\alpha
F(x^{p^{j}})))=(\operatorname{tr}(\alpha
x^{p^{j+1}}))=s(\operatorname{tr}(\alpha x^{p^{j}}))$. ∎

######  Remark 1.2.3.

As the space $(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$ is compact, we like to think
of these properties as saying that the shift space over the elementary abelian
group of order $p^{r}$ is a ‘dynamical compactification’ of the points of the
affine algebraic group $\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$ (which
correspond to the periodic sequences).

We let $\iota$ denote the map $\iota_{\alpha}$ for any choice of $\alpha$ as
above. The dynamical results will not depend on the many possible choices of
$\alpha$.

######  Remark 1.2.4.

The _profinite shift_ by $\psi\in\widehat{\mathbf{Z}}$ is the map
$s_{\psi}\colon\mathscr{P}\rightarrow\mathscr{P}$ given by

$s_{\psi}((y_{j}))=(y_{j+\psi\bmod{N}})$

for $(y_{j})$ having period $N$. Under our correspondence and the
identification of $\widehat{\mathbf{Z}}$ with
$\mathrm{Gal}(\overline{\mathbf{F}}_{p}/\mathbf{F}_{p})$, profinite shifts on
periodic sequences correspond to the action of the corresponding element of
the absolute Galois group of $\mathbf{F}_{p}$ on the algebraic group
$\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$.

##  2\. Remaining proofs

###  2.1. Results concerning fixed points and periodic orbits

We start with a lemma about general subshifts of
$S=(\mathbf{F}_{p}^{r})^{\mathbf{Z}}$ which is not directly related to
cellular automata. We use the standard terminology of calling a finite string
of symbols from the alphabet $\mathbf{F}_{p}^{r}$ a _word_. A subset $F$ of
$S$ is a _subshift of finite type_ if it is defined by a finite list of
‘excluded’ words, in the sense that $F$ consists of sequences in $S$ that do
not contain any of those excluded words as subwords.

######  Lemma 2.1.1.

Suppose $F\subseteq S$ is a subshift of finite type such that $F$ is a
subgroup and $F\cap\mathscr{P}$ is finite. Then $F$ is contained in
$\mathscr{P}$ and thus $F$ is finite.

###### Proof.

Suppose that $F$ contains a non-shift-periodic sequence $y$. For any
$M\geqslant 0$, $F$ also contains such a sequence $y^{\prime}$ with a block
$0^{M}$ of $M$ consecutive zeros; indeed, some word of length $M$ appears
twice at different positions in $y$, and by shifting so that these become
aligned and then subtracting, the block $0^{M}$ is found in a sequence
$y^{\prime}$ of the form $y^{\prime}=y-s^{\circ k}y$ for some appropriate $k$.
Note that $y^{\prime}\in F$ since $F$ is a shift-invariant subgroup. We will
specify an appropriate value for $M$ later in the proof.

Let $s$ denote an integer strictly larger than both the size of the largest
block of consecutive zeros in the non-zero periodic sequences in $F$ (which is
finite by the assumed finiteness of $F\cap\mathscr{P}$), as well as the length
of the longest excluded word defining $F$ (which is finite by the finite-type
assumption).

Since $y$ is not periodic, $y^{\prime}\neq 0$. Hence either to the left or to
the right of the block $0^{M}$ in $y^{\prime}$ there will be a non-zero symbol
$a$. We assume that such a symbol $a$ occurs to the right (if it occurs to the
left, the argument applies mutatis mutandis). Then there is a word of length
$s$ that will occur twice at different positions in $y^{\prime}$ to the right
of the position of the chosen $a$, where the two occurrences of that word are
at distance at most $p^{rs}$ (by the pigeon-hole principle). We again form a
sequence $y^{\prime\prime}=y^{\prime}-s^{\circ\ell}y^{\prime}\in F$ for some
$\ell\leqslant p^{rs}$ that aligns the two occurrences.

In $y^{\prime\prime}$, the original block of zeros $0^{M}$ might be shortened
to $0^{M^{\prime}}$, but in any case, $M^{\prime}\geqslant M-p^{rs}$. Assuming
$M=p^{rs}+s$, we have $M^{\prime}\geqslant s$ and the constructed sequence
$y^{\prime\prime}$ has two blocks of $s$ consecutive zeros. Furthermore, if
$b$ is the word occurring in between these two blocks, there is at least one
non-zero entry in $b$ since the non-zero symbol $a$ occurs between $0^{M}$ and
the chosen words in $y^{\prime}$.

Finally, we construct an bi-infinite sequence $y^{\prime\prime\prime}=\dots
0^{s}b0^{s}b0^{s}\dots$ by shift-periodically repeating the word $0^{s}b$.
Since $s$ is larger than the maximal length of excluded words defining $F$ and
all words of smaller length occurring in $y^{\prime\prime\prime}$ are not
excluded since they also occur in $y^{\prime\prime}$, we have that
$y^{\prime\prime\prime}\in F$. Thus, $y^{\prime\prime\prime}$ is a non-zero
periodic sequence in $F$ with a block of more than the maximal permitted
number of consecutive zeros (by the choice of $s$), and this is a
contradiction. We conclude that $F\subseteq\mathscr{P}$. ∎

###### Proof of Theorem F.

The injectivity of $\iota$ and statements (i) (ii) were proven in Proposition
1.2.2. For the remaining parts, we first construct the bijection
$\sigma\mapsto g_{\sigma}$.

Let $\sigma\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$ be an
endomorphism defined over $\mathbf{F}_{p}$. It is described by a matrix

$m_{\sigma}=m_{0}+m_{1}\phi+\cdots+m_{N}\phi^{N}\in\mathrm{M}_{r}(\mathbf{F}_{p}[\phi])$

for matrices $m_{i}\in\mathrm{M}_{r}(\mathbf{F}_{p})$. The corresponding
cellular automaton $g_{\sigma}$ on the space
$S=(\mathbf{F}^{r}_{p})^{\mathbf{Z}}$ is defined by the rule

$(y_{i})\mapsto(m_{0}y_{i}+m_{1}y_{i+1}+\cdots+m_{s}y_{i+N}).$

Then $\sigma\mapsto g_{\sigma}$ is a bijection between endomorphisms of
$\mathbf{G}_{a}^{r}$ defined over $\mathbf{F}_{p}$ and one-sided linear
cellular automata on $S$ (the inverse being obvious).

We now consider the matching of fixed points. Suppose
$x=(x_{1},\dots,x_{r})^{\intercal}\in\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$
is a fixed point of $m_{\sigma}$, so $m_{\sigma}(x)=x$, i.e.

$m_{0}x+m_{1}x^{p}+\dots+m_{N}x^{p^{N}}=x$

with the operation of raising to the $p$-th power applied componentwise on
$x$. Recall that $m_{i}$ have entries in $\mathbf{F}_{p}$, so if we raise this
equation to the $p^{j}$-th power, we find that

$m_{0}x^{p^{j}}+m_{1}x^{p^{j+1}}+\dots+m_{N}x^{p^{j+N}}=x^{p^{j}}$

for all $j$. Multiplying this equation by $\alpha$ and taking traces, we find

$m_{0}\operatorname{tr}(\alpha x^{p^{j}})+m_{1}\operatorname{tr}(\alpha
x^{p^{j+1}})+\dots+m_{N}\operatorname{tr}(\alpha
x^{p^{j+N}})=\operatorname{tr}(\alpha x^{p^{j}}).$ (5)

Setting $y_{j}:=\operatorname{tr}(\alpha x^{p^{j}})$ and recalling that

$g_{\sigma}((y_{j}))=m_{0}y_{j}+m_{1}y_{j+1}+\dots+m_{N}y_{j+N},$ (6)

Equation (5) says that $g_{\sigma}((y_{j}))=(y_{j}),$ so $(y_{j})$ is a fixed
point of $g_{\sigma}$. At the same time, by Proposition 1.2.2(iii),
$\iota(x)=y\in\mathscr{P}$. This shows that
$\iota(\mathrm{Fix}(\sigma))\subseteq\mathrm{Fix}(g_{\sigma})\cap\mathscr{P}$.

For the inclusion in the other direction, if $g_{\sigma}(y)=y$ and
$y\in\mathscr{P}$, then $y=\iota(x)$ for some
$x\in\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p})$ and, reversing the above
argument, we see that $\sigma(x)=x$. We can apply the argument to
$\sigma^{\circ n}$ for any $n$, and this proves Equation (1).

Assume that $g_{\sigma}$ is confined, meaning that
$\mathrm{Fix}(g_{\sigma}^{\circ n})$ is finite for all $n$. Since $g_{\sigma}$
commutes with the shift $s$, $\mathrm{Fix}(g_{\sigma}^{\circ n})$ is a finite
shift-invariant subgroup of $S$, and hence consists of shift-periodic
sequences. Thus, $\mathrm{Fix}(g_{\sigma}^{\circ n})\subseteq\mathscr{P}$, and
Equation (2) follows.

Finally, we show that confinedness of $\sigma$ implies that of $g_{\sigma}$.
Note that $F:=\mathrm{Fix}(g_{\sigma}^{\circ n})$ is a shift-invariant
subgroup of $S$ with $F\cap\mathscr{P}$ finite by Equation (1). Furthermore,
$F$ is a subshift of finite type; indeed, let $N$ be as in the local rule (6)
for $g_{\sigma}$ and exclude all words of length $\leqslant nN+1$ that do not
map to zero under the local rule for $g_{\sigma}^{\circ n}-\mathrm{id}$. By
Lemma 2.1.1, it follows that $F$ is finite, which means that $g_{\sigma}$ is
confined. ∎

In the next proof, we will use the following concept.

######  Definition 2.1.2.

The _coincidence set_ $\mathrm{Coin}(f,g)$ of two self-maps $f\colon
X\rightarrow X$ and $g\colon X\rightarrow X$ on a set $X$ is defined as

$\mathrm{Coin}(f,g)=\\{x\in X\colon f(x)=g(x)\\}.$

###### Proof of Proposition G.

For one-sided automata, by Theorem F, we are reduced to proving the statement
for confined $\sigma\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$, and
in that case the formula for the number of fixed points is given in [2,
Theorem 4.2.17]. In the general case, we can reason as follows: assume that
the local rule is given by $g((y_{i}))_{0}=\sum_{k=M}^{N}m_{k}y_{k}$ for some
$M,N\in\mathbf{Z}$ and some matrices $m_{k}\in\mathrm{M}_{r}(\mathbf{F}_{p})$.
Without loss of generality, we can assume $M<0$ (possibly allowing $m_{k}=0$
for some $k$). Consider $\tilde{g}=gs^{-M}$; then

$\mathrm{Fix}(g^{\circ n})=\mathrm{Coin}(\tilde{g}^{\circ n},s^{\circ-Mn}).$

Note that this set is finite (by the assumption that $g$ is confined) and
shift-periodic by the shift-commuting property of $g$; it follows that the set
consists of shift-periodic sequences only. Therefore, letting
$\tilde{\sigma}\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$ be such
that $g_{\tilde{\sigma}}=\tilde{g}$ and using that $s$ corresponds to $F$ on
the algebraic group side, we find, by the same argument used to prove Theorem
F(iv), that

$\mathrm{Coin}(\tilde{g}^{\circ n},s^{\circ-
Mn})\stackrel{{\scriptstyle\iota}}{{=}}\mathrm{Coin}(\tilde{\sigma}^{\circ
n},F^{\circ-Mn}).$

Thus, we can compute

$\displaystyle\log_{p}\\#\mathrm{Fix}(g^{\circ n})$
$\displaystyle=\log_{p}\\#\mathrm{Coin}(\tilde{g}^{\circ n},s^{\circ-Mn})$
$\displaystyle=\log_{p}\\#\mathrm{Coin}(\tilde{\sigma}^{\circ n},F^{\circ-
Mn})$ $\displaystyle=\log_{p}\\#\ker({\tilde{\sigma}}^{\circ n}-F^{\circ-
Mn}|\mathbf{G}_{a}^{r}(\overline{\mathbf{F}}_{p}))$
$\displaystyle\stackrel{{\scriptstyle(\dagger)}}{{=}}\deg_{\phi}(\det(m_{\tilde{\sigma}}^{n}-\phi^{-Mn}))-v_{\phi}(\det(m_{\tilde{\sigma}}^{n}-\phi^{-Mn}))$
$\displaystyle=-Mnr+\deg_{\phi}(\det((m_{\tilde{\sigma}}\phi^{M})^{n}-1))+Mnr-
v_{\phi}(\det((m_{\tilde{\sigma}}\phi^{M})^{n}-1)).$ (7)

Equality $(\dagger)$ holds for the following reason: (a) for an endomorphism
$\tau$ of a commutative algebraic group with finite kernel (equivalently, a
surjective endomorphism), $\\#\ker(\tau)$ is the quotient of the degree of
$\tau$ by the inseparability degree of $\tau$ [2, Formula (3.1)]; (b) the map
$\tau={\tilde{\sigma}}^{\circ n}-F^{\circ-
Mn}\in\operatorname{\mathrm{End}}(\mathbf{G}_{a}^{r})$ has finite kernel,
since by the above formula its cardinality equals $\\#\mathrm{Fix}(g^{\circ
n})$ and we assumed $g$ to be confined; (c) we can apply the formula for the
degree and inseparability degree of an endomorphism of a vector group in terms
of valuation of the determinant given in [2, Lemma 4.2.2] (notice that since
we work over $\mathbf{F}_{p}$, the Dieudonné determinants in that reference
can be replaced by usual determinants).

We now apply [2, Lemma 4.2.5] to the valuation $v_{\phi^{-1}}=-\deg_{\phi}$
and $v_{\phi}$ and for matrices in the field of rational functions
$\mathbf{F}_{p}(\phi)$. For $v$ either one of these valuations, we find that

$v(\det((m_{\tilde{\sigma}}\phi^{M})^{n}-1))=-a_{v}n+t_{n}^{v}p^{v_{p}(n)}$

for some $a_{v}\in\mathbf{Z}_{\geqslant 0}$ and periodic sequence
$(t^{v}_{n})$ with $t^{v}_{n}\in\mathbf{Z}_{\geqslant 0}$ having period
$\varpi_{v}$ coprime to $p$ and satisfying
$t^{v}_{n}=t^{v}_{\mathrm{gcd}(n,\varpi_{v})}$. Equation (3) follows by adding
these formulæ. ∎

######  Remark 2.1.3.

From the proof of [2, Lemma 4.2.5] emerge the following exact formulas for
$a,t_{n}$ and $\varpi$. Choose some extensions $\tilde{v}_{\phi^{-1}}$ and
$\tilde{v}_{\phi}$ of the valuations $v_{\phi^{-1}}=-\deg_{\phi}$ and
$v_{\phi}$ to a fixed algebraic closure $\overline{\mathbf{F}_{p}(\phi)}$, and
let $\lambda_{1},\ldots,\lambda_{r}\in\overline{\mathbf{F}_{p}(\phi)}$ denote
the eigenvalues of $m_{\tilde{\sigma}}\phi^{M}$, taken with multiplicities.
Note that none of the $\lambda_{i}$ is a root of unity by the assumed
confinedness of $g$. The formula for $a$ is

$a=\sum_{i}\max(-\tilde{v}_{\phi^{-1}}(\lambda_{i}),0)+\max(-\tilde{v}_{\phi}(\lambda_{i}),0).$
(8)

Given a valuation $v$ on $\overline{\mathbf{F}_{p}(\phi)}$ and an element
$\lambda\in\overline{\mathbf{F}_{p}(\phi)}$, let

$m^{v}(\lambda):=\left\\{\begin{array}[]{ll}\min\\{m\in\mathbf{Z}_{>0}\colon
v(\lambda^{m}-1)>0\\}&\mbox{ if it exists, }\\\ \infty&\mbox{
otherwise.}\end{array}\right.$

The formula for $t_{n}$ is

$t_{n}=\sum_{v\in\\{\tilde{v}_{\phi},\tilde{v}_{\phi^{-1}}\\}}\,\sum_{m^{v}(\lambda_{i})\mid
n}v(\lambda_{i}^{m^{v}(\lambda_{i})}-1),$ (9)

with the convention that $\infty{\mid}n$ holds for no integer $n$. Finally,
the period $\varpi$ is

$\varpi=\mathrm{lcm}\\{m^{v}(\lambda_{i})\colon
m^{v}(\lambda_{i})\neq\infty,v\in\\{\tilde{v}_{\phi},\tilde{v}_{\phi^{-1}}\\},i=1,\dots,r\\}.$
(10)

The next lemma describes when $a=0$, a case that will deserve special
attention in subsequent proofs.

######  Lemma 2.1.4.

Let $g$ be a confined multiband linear cellular automaton on an alphabet
$\mathbf{F}_{p}^{r}$ with invariants $a$ and $(t_{n})$ as in Proposition G.
The following conditions are equivalent:

  1. (i)

$a=0$;

  2. (ii)

the zero sequence is the unique periodic point of the automaton;

  3. (iii)

some power $g^{\circ n}$ of the map $g$ is the zero map.

###### Proof.

From Equation (8), we see that $a=0$ if and only if
$\tilde{v}_{\phi^{-1}}(\lambda_{i})\geqslant 0$ and
$\tilde{v}_{\phi}(\lambda_{i})\geqslant 0$ for every $i$. Since
$\\{\lambda_{i}\\}$ is invariant under the action of the absolute Galois
group, this implies that $\tilde{v}(\lambda_{i})\geqslant 0$ for every
valuation $\tilde{v}$ of $\overline{\mathbf{F}_{p}(\phi)}$ lying above
$v_{\phi^{-1}}$ and $v_{\phi}$. Since $\lambda_{i}$ are zeros of a monic
polynomial over $\mathbf{F}_{p}[\phi,\phi^{-1}]$, we automatically have
$\tilde{v}(\lambda_{i})\geqslant 0$ for any valuation lying above the
remaining valuations $v\neq v_{\phi^{-1}},v_{\phi}$ of $\mathbf{F}_{p}[\phi]$.
By the product formula, whenever $\lambda_{i}\neq 0$, the sum of all
valuations of $\lambda_{i}$ is zero.

Thus, $a=0$ if and only if for all $i$ either $\lambda_{i}=0$ or
$\tilde{v}(\lambda_{i})=0$ for all valuations $\tilde{v}$ of
$\overline{\mathbf{F}_{p}(\phi)}$. The latter condition simply means that
$\lambda_{i}$ lies in $\overline{\mathbf{F}_{p}}$. However, $\lambda_{i}$
cannot take values in $\overline{\mathbf{F}_{p}}^{*}$ by confinedness. Hence,
$a=0$ if and only if $\lambda_{i}=0$ for all $i$, which is equivalent to the
matrix $m_{\tilde{\sigma}}\phi^{M}$ (or simply $m_{\tilde{\sigma}}$) being
nilpotent. Thus, $a=0$ implies that some power of $g$ is the zero map.

Conversely, if some power of $g$ is the zero map, the constant zero sequence
is the only periodic point, and so $\\#\mathrm{Fix}(g^{\circ n})=1$ for all
$n$, which implies that $a=0$. ∎

###### Proof of Corollaries H and I.

This follows from Lemma 2.1.4 if $a=0$, so let $a\neq 0$. For the dichotomy
for the zeta function in Corollary H, see [2, Theorem 12.2.1] (note that our
system is hyperbolic with ‘entropy’ $a\log p$ in the sense of that reference).
For Corollary I concerning the orbit length formula, see [2, Theorem
11.1.1(i)]; this applies in the general (not necessarily one-sided) case given
that the formula (3) holds in that generality too. ∎

##  3\. Open problems

We finish the paper with a few open problems and questions related to
extending the ‘bridge’ between the theory of algebraic groups and cellular
automata.

  1. (i)

A vector group is a particular kind of unipotent group. If $G$ is a general
connected unipotent algebraic group and
$\sigma\in\operatorname{\mathrm{End}}(G)$ is a surjective algebraic group
endomorphism, there exists a finite filtration of $G$ by characteristic (hence
$\sigma$-invariant) algebraic subgroups such that all quotients are isomorphic
to vector groups $\mathbf{G}_{a}^{r}$ (of possibly different dimensions $r$),
and $\sigma$ induces an endomorphism of those [2, Chapter 7]. Furthermore, the
number of fixed points of $\sigma$ on $G$ (if finite) is the product of that
on the different quotients [2, Proposition 3.4.3]. Thus, the study of dynamics
of endomorphisms $\sigma$ of unipotent algebraic groups (which can be assumed
to be surjective by replacing $G$ by $\sigma^{n}G$ for suitable $n$) is
reduced to the case where the group is a vector group. For a general unipotent
group $G$ with an endomorphism $\sigma$ defined over $\mathbf{F}_{p}$, is
there a generalisation of additive cellular automata that are filtered by
structures whose quotients are linear cellular automata, corresponding to the
filtration of $G$ with vector group quotients stable by $\sigma$?

  2. (ii)

Can one generalise the main theorem from vector groups to more general
algebraic groups? For which algebraic groups $G$ is there a map $\iota\colon
G(\overline{\mathbf{F}}_{p})\rightarrow G(\mathbf{F}_{p})^{\mathbf{Z}}$ with
similar properties? It seems best to specialise first to the case where $G$ is
commutative or where $G$ is unipotent. In other examples, such as
$G=\mathrm{SL}_{2}$ for $p=2$, any homomorphism
$\iota\colon\mathrm{SL}_{2}(\overline{\mathbf{F}_{2}})\rightarrow\mathrm{SL}_{2}(\mathbf{F}_{2})^{\mathbf{Z}}$
is trivial since for no $N\geqslant 2$ there exists a nontrivial group
homomorphism from the simple group
$\mathrm{SL}_{2}(\mathbf{F}_{2^{N}})\cong\mathrm{PSL}_{2}(\mathbf{F}_{2^{N}})$
to $\mathrm{SL}_{2}(\mathbf{F}_{2})\cong S_{3}$.

  3. (iii)

What happens if $\overline{\mathbf{F}}_{p}$ is replaced by $\overline{K}$ for
an arbitrary field $K$ of characteristic $p>0$ with $r>1$? The results and
proofs from [2] do not apply anymore. In this case, it might be interesting to
construct an appropriate theory for cellular automata and then apply it to the
algebraic group side, reversing the philosophy of this paper.

## References

  * [1] Michael Artin and Barry C. Mazur, _On periodic points_ , Ann. of Math. (2) 81 (1965), 82–99.
  * [2] Jakub Byszewski, Gunther Cornelissen, and Marc Houben, _Dynamics of endomorphisms of algebraic groups and related systems_ , preprint arXiv:2209.00085, 150pp., 2022.
  * [3] Tullio Ceccherini-Silberstein and Michel Coornaert, _Cellular automata and groups_ , Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010.
  * [4] Matthew Cook, _Universality in elementary cellular automata_ , Complex Systems 15 (2004), no. 1, 1–40.
  * [5] Alberto Dennunzio, Enrico Formenti, Darij Grinberg, and Luciano Margara, _An efficiently computable characterization of stability and instability for linear cellular automata_ , J. Comput. System Sci. 122 (2021), 63–71.
  * [6] Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Luciano Margara, and Antonio E. Porreca, _On the dynamical behaviour of linear higher-order cellular automata and its decidability_ , Information Sciences 486 (2019), 73–87.
  * [7] Marta Dueñas-Díez and Juan Pérez-Mercader, _How chemistry computes: Language recognition by non-biochemical chemical automata. From finite automata to Turing machines_ , iScience 19 (2019), 514–526.
  * [8] Ryszard Engelking, _General topology_ , second ed., Sigma Series in Pure Mathematics, vol. 6, Heldermann Verlag, Berlin, 1989.
  * [9] Paola Favati, Grazia Lotti, and Luciano Margara, _Additive one-dimensional cellular automata are chaotic according to Devaney’s definition of chaos_ , Theoret. Comput. Sci. 174 (1997), no. 1-2, 157–170.
  * [10] Gustav A. Hedlund, _Endomorphisms and automorphisms of the shift dynamical system_ , Math. Systems Theory 3 (1969), 320–375.
  * [11] Jarkko Kari, _Linear cellular automata with multiple state variables_ , STACS 2000 (Lille), Lecture Notes in Comput. Sci., vol. 1770, Springer, Berlin, 2000, pp. 110–121.
  * [12] Lieven Le Bruyn and Michel Van den Bergh, _Algebraic properties of linear cellular automata_ , Linear Algebra Appl. 157 (1991), 217–234.
  * [13] Douglas Lind and Brian Marcus, _An introduction to symbolic dynamics and coding_ , Cambridge University Press, Cambridge, 1995.
  * [14] Olivier Martin, Andrew M. Odlyzko, and Stephen Wolfram, _Algebraic properties of cellular automata_ , Comm. Math. Phys. 93 (1984), no. 2, 219–258.
  * [15] Garry L. Mullen and Daniel Panario (eds.), _Handbook of finite fields_ , Chapmann and Hall/CRC Press, Hoboken, NJ, 2013.
  * [16] Luis Ribes and Pavel Zalesskii, _Profinite groups_ , second ed., Ergebnisse der Math. und ihrer Grenzgebiete. 3. Folge, vol. 40, Springer-Verlag, Berlin, 2010\.
  * [17] Michael Rosen, _Number theory in function fields_ , Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002.
  * [18] John von Neumann, _Theory of self-reproducing automata_ , University of Illinois Press, Urbana, 1966, edited and completed by Arthur W. Burks.
  * [19] Thomas B. Ward, _Additive cellular automata and volume growth_ , Entropy 2 (2000), no. 3, 142–167.
  * [20] Stephen Wolfram, _Statistical mechanics of cellular automata_ , Rev. Modern Phys. 55 (1983), no. 3, 601–644.