---
abstract: 'A common problem to all applications of linear finite dynamical systems is analyzing the dynamics without enumerating every possible state transition.  Of particular interest is the long term dynamical behaviour.  In this paper, we study the number of iterations needed for a system to settle on a fixed set of elements.  As our main result, we present two upper bounds on iterations needed, and each one may be readily applied to a fixed point system test.  The bounds are based on submodule properties of iterated images and reduced systems modulo a prime.  We also provide examples where our bounds are optimal.' 
author:
- Björn Lindenberg
bibliography:
- 'ref.bib'
title: Stabilization Bounds for Linear Finite Dynamical Systems
---

Introduction
============

A *finite dynamical system* is an ordered pair $(X,f)$, which consists of a finite set $X$ together with an iterating function $f$ over $X$. That is, elements of $X$ evolve by repeated application of $f$. Thus the study of a finite dynamical system is a study of sequences of the form $$\label{eq:intro1}
(  x,f(x),f^2(x),\cdots ),$$ where $f$ is called the *defining function*.  In mathematical modelling, finite dynamical systems emerge in many different areas.  Applications can be found in, for example, computational physics, electrical engineering, artificial intelligence, gene regulatory networks and cellular automata [@hernandez2005linear; @colon2005boolean; @colon2006monomial; @bollman2007fixed].  Hence, $f$ often represents *state transitions* or the *passing of time*. 

In this context, a *linear finite dynamical system* $(M,f)$ is a system where $f$ is a linear map and $M$ is a *finite $R$-module*.  That is, $M$ is a generalized vector space with scalars in a finite commutative ring $R$, and is generated by a finite set of *base elements*.  Therefore, $f$ can be represented by a matrix $A$ over $R$, which describes the mapping of the base elements. 

An important problem in applications of finite dynamical systems, is the determination of long term behaviour without enumeration of all possible state transitions.  The size of the underlying set $X$ may lead to iteration over all elements being computationally intractable.  As an example, a finite dynamical system in the form of a Boolean modeling framework is demonstrated in [@laubenbacher2004computational].  There the framework models a gene regulatory network of 60 nodes, such that $|X| = 2^{60}$. Other frameworks for gene regulatory networks may have more than two states for each node, leading to a further increase in the size of the underlying set [@bollman2007fixed]. 

When a linear finite dynamical system is given by $({{\mathbb{Z}}_p^m}, A)$, where $p$ is prime, the properties and long term behaviour is well understood [@bollman2007fixed; @colon2005boolean; @hernandez2005linear].  Although when dealing with more general linear systems $({{\mathbb{Z}}_{n}^m}, A)$, one faces difficulties due to the lack of unique factorization [@xu2009linear; @deng2015cycles]. 

Fixed Point Systems
-------------------

Let $(X,f)$ be a finite dynamical system and consider an iterated sequence of the form given in .  It is possible that after a certain number of iterations we reach a *fixed point* $x_0$, such that $f(x_0)=x_0$. If every element in $X$ eventually iterates to a fixed point, not necessarily unique, then the system is called a *fixed point system*.  Otherwise elements of $X$ will eventually converge within a subset of $X$, which consists of fixed points and *cycles*, where cycles are closed iteration loops of more than one element.  An extensive study of cycles of linear finite dynamical systems can be found in [@deng2015cycles]. 

A *fixed point system criterion* for $(\mathbb{F}_q^n, A)$, where $\mathbb{F}_q$ is the finite field with $q$ elements, is given by Bollman *et al.*  in [@bollman2007fixed].  It is based on the *minimal polynomial* of $A$, i.e., the polynomial of least degree in $\mathbb{F}_q[x]$ which annihilates $A$.  As an alternative, G. Xu and Y.M. Zou presented another fixed point system criterion in [@xu2009linear].  Given $(R^m,A)$, where $R$ is a finite commutative ring, they showed that if the size of $R$ is a composite integer $n$, then the system is fixed point system if and only if $$\label{eq:intro2}
  A^{k+1}=A^k,$$ where $k = \lceil m \log_2(n)\rceil$. Thus the integer $k$ is a derived bound on the number of iterations needed for the system to stabilize, and the criterion in provides an efficient way of determining if the system exhibits long term *steady state* behaviour. 

That every linear finite dynamical system eventually settles on fixed points and cycles is stated in *Fitting’s Lemma*, see .  In the spirit of [@hernandez2005linear] we define the *height* of a system as the minimum number of iterations needed for the system to settle.  It is easy to show that the bound $k$ in can be replaced by any upper bound on the system height, generating an alternative fixed point system criterion.  Thus, assuming a composite integer $n$ for the size of the ring, one could ask the question of how close $\lceil m \log_2(n)\rceil$ is to the actual system height, and if there is significant improvements to be found. 

In this paper we give sharper height bounds.  We also provide examples where these bounds are optimal.  Issues concerning implementation of our results and possible performance advantages is also addressed. 

We proceed to discuss our main results in more detail. 

Main Results
------------

We present theorems which are height bounds for a linear finite dynamical system of the form $({{\mathbb{Z}}_{n}^m},f)$. As such they may be readily applied to a fixed point convergence test found in [@xu2009linear Section 3].  The main results come in two varieties.  One is independent of the defining function, and the other is based on the structure of smaller reduced systems.  In addition we will see examples and numerical applications of the main theorems. 

[A]{} \[thm:a\] Let $({\mathbb{Z}}_{n}^m, f)$ be a linear finite dynamical system, and let $s$ be the system height.  If the prime factorization of $n$ is $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\omega}^{\alpha_{\omega}}$, then the height is bounded as $$s \leq  m \cdot \max\left \{ \alpha_1, \alpha_2, \dots, \alpha_{\omega}\right \},$$ where $\max\left \{ \alpha_1, \alpha_2, \dots, \alpha_{\omega}\right \}$ is the largest prime factor exponent. 

The function independent bound $m \alpha_{\max}$ of , where $\alpha_{\max}$ is the largest prime factor exponent of $n$, may be precalculated for any endomorphism given a certain module.  Its proof relies on submodule properties of iterated images and reduced systems derived from the *primary decomposition* of the underlying ring. 

[B]{} \[thm:b\] Let $({{\mathbb{Z}}_{n}^m},f)$ be a finite dynamical system with a defining matrix $A$ over ${\mathbb{Z}}_n$, and let $s$ be the system height.  If the prime factorization of $n$ is $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\omega}^{\alpha_{\omega}}$, then the height is bounded as $$s \leq  \max\left \{ \alpha_1 s_1, \alpha_2 s_2, \dots, \alpha_{\omega} s_{\omega} \right \},$$ where each $s_i$ is the height of the reduced system $({\mathbb{Z}}_{p_i}^m, A {\ \text{\normalfont mod}\ p_i })$, $i = 1,2, \dots, \omega$.

The proof of is based upon properties derived from *reduced* systems involving factor modules of prime powered orders. 

The function dependent bound is the sharpest bound of this paper.  When implementing one needs to find the height of systems of the form $({{\mathbb{Z}}_p^m},f)$, where ${{\mathbb{Z}}_p^m}$ is a vector space.  Therefore one possible algorithm is as follows: For each distinct prime factor $p$ of $n$ calculate the product of the exponent of $p$ and the height of $({{\mathbb{Z}}_p^m}, A {\ \text{\normalfont mod}\ p })$.  The height is found by checking the rank of successive powers of $A {\ \text{\normalfont mod}\ p }$.  The largest such product $h_{\max}$ is then used in the fixed point convergence test.  Although this naive implementation may require large scale linear finite dynamical systems to be effective, there is room for improvements concerning algorithms implementing it.  The naive complexity for rank calculations and matrix multiplications is $O(m^3)$, although faster methods exists, see [@von2013modern].  Thus, the worst case complexity of the naive algorithm is on par with the function independent bounds, whose algorithms execute pure matrix multiplications. 

In practice for smaller systems, the bound of will be fast and efficient enough to outweigh any possible improvements gained by .  However given an application of a large scale linear finite dynamical system we know that the true height is bounded by a product of an exponent and the height of some subsystem over a field.  Thus the probability of the true height being significantly less than the exponent times the dimension of the matrix grows both with the prime of this subsystem and the dimension, see [@laksov1994counting].  Therefore any sufficient implementation of will with high probability yield a performance advantage concerning fixed point system tests on these large scale systems. 

Examples and Numerical Comparisons
----------------------------------

With a system of the form $({\mathbb{Z}}_{210}^{16}, f)$ we have $m = 16$ and $210 = 2^1 3^1 5^1 7 ^1$, thus by the system height cannot be larger than $16\cdot1=16$.

Consider instead a system of the form $({\mathbb{Z}}_{1960}^{4}, f)$. We have $m = 4$ and $1960 = 2^3 5^1 7^2$, yielding a maximal exponent of 3, as such the system height is less than or equal to $4\cdot3=12$.

gives an upper bound that is only dependent on the prime factor exponents.  A system of the form $({\mathbb{Z}}_6^3, f_1)$ has a height less than or equal to $3$, since $6 = 2^1 3^1$ and $3\cdot1=3$. The same bound applies to a system of the form $({\mathbb{Z}}_{400827403}^3, f_2)$. Here we have the prime factorization $$400827403 = 10333^1 38791^1,$$ thus in spite of ${\mathbb{Z}}_{400827403}^3$ being a set many orders of magnitude larger than ${\mathbb{Z}}_6^3$, the system will settle on cycles within three iterations. 

Let $({\mathbb{Z}}_{27720}^4,A)$ be a linear finite dynamical system, with a defining matrix $$A = \begin{pmatrix}
        
 17453 & 19126 & 430 & 13601  \\
        3116 & 18264 & 19275 & 26452 \\
        22825 & 2401 & 22534 & 173 \\
        4496 & 13083 & 3885 & 12974
        \end{pmatrix},$$ over ${\mathbb{Z}}_{27720}$. The prime factorization of 27720 is $2^3 3^2 5^1 7^1 11^1$. For each distinct prime $p$, we find the height of $({\mathbb{Z}}_p^4, A {\ \text{\normalfont mod}\ p })$ and multiply it with the corresponding exponent.  This leads to a set of products $$\left \{3\cdot3,2\cdot2,1\cdot0,1\cdot1,1\cdot0 \right \}=\left \{9,4,0,1,0 \right \},$$ and according to , the system height is less than or equal to 9. 

![ A number of sampled linear systems $({\mathbb{Z}}_{25}^3,f)$ for a bound comparison.  Here demonstrates that it is a least upper bound over all endomorphisms, and follows closely the actual height.[]{data-label="fig:h1"}](hcomp1){width="0.8\linewidth"}

![ A number of sampled linear systems $({\mathbb{Z}}_{7560}^{32},f)$ for a bound comparison.[]{data-label="fig:h3"}](hcomp3){width="0.8\linewidth"}

In height bounds are calculated for a number of sampled non-invertible matrices, and for reference the true height is included, which the data is sorted by.  As can be seen, follows closely the actual height of the systems, and provides a least upper bound concerning all endomorphisms.  shows bounds for systems over a larger module.  Here the number of distinct prime factors and base elements has increased compared to the former figure, which leads to relatively larger differences between the bounds.  The figure shows that the function independent bounds may vastly overshoot the actual height of a system, where the height will be some integer less than or equal to the function dependent bound of .  In both figures the function independent bound $\lceil m \log_2(n)\rceil$ derived in [@xu2009linear] is added for comparison. 

Organization and Strategy
-------------------------

We will follow the framework laid out in [@hernandez2005linear; @bollman2007fixed; @deng2015cycles] and start with some basic notions concerning vertices in the associated state space and structural properties of product systems in . 

After the preliminaries, the proofs will be presented in and .  First a small addition to the train of thought used by Xu and Zou in [@xu2009linear Theorem 2.1].  Iterated images of any linear map yields a descending chain of submodules, hence the minimum number of iterations is bounded by the maximum chain length over all functions.  This produces an intermediary bound in , which involves $\Omega(n)$, the number of prime factors of $n$ counting multiplicity.  Furthermore the main theorems are partially a consequence of , which equates the number of iterations needed for stabilization to that of subsystems arising from the primary decomposition of the underlying ring. 

In we will derive properties of systems of the form $({{\mathbb{Z}}_{p^r}^m}, f)$. This is done by looking at smaller reduced systems $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$ and $({\langle p \rangle}^m, f)$, where $\overline{f}$ is a function *induced* by the natural homomorphism from the module to its factor module.  This will lead us to a bound when $M = {{\mathbb{Z}}_{p^r}^m}$ in , which combined with proves : A function dependent bound when $M = {{\mathbb{Z}}_{n}^m}$.

Acknowledgements {#acknowledgements .unnumbered}
================

I would like to thank Karl-Olof Lindahl and Per-Anders Svensson at Linnæus University for productive discussions, pointers to literature, and for corrections and improvements of earlier drafts of this paper. 

Preliminaries {#sec:prelim}
=============

In a finite dynamical system $(X,f)$ every element is a vertex in the associated directed graph $\mathscr{G}_f$, called the *state space*, whose edges are given by the ordered pairs $\set{(x,f(x)) | x \in X}$. We hereby define two different instances of vertices. 

\[def:fds-cycle\] Let $(X,f)$ be a finite dynamical system with an associated state space ${\mathscr{G}_f}$. A *cycle vertex* is an element $x_0$ in $X$, such that $f^l (x_0) =x_0$ for some positive integer $l$, i.e., there exists a path from $x_0$ to itself in ${\mathscr{G}_f}$. The smallest such integer is called the *period* of $x_0$. Furthermore, when cycle vertices are of period 1 they are called *fixed points*. 

\[def:fds-leaf\] Let $(X,f)$ be a finite dynamical system with an associated state space ${\mathscr{G}_f}$. A *leaf vertex* is an element $y$ in $X$, such that $y$ is a leaf in the associated state graph ${\mathscr{G}_f}$, i.e., the equation $f(x)=y$ has no solution. 

Of special interest to us is the subgraph of ${\mathscr{G}_f}$ consisting of only cycle vertices and their internal edges.  When an element reaches a cycle vertex during iteration, the future iterated images will remain as cycle vertices.  This is an immediate consequence of , i.e., if $x_0$ is a cycle vertex then $f^k(x_0)$ is a cycle vertex of the same period for all nonnegative integers $k$.

Thus given a finite dynamical system $(X,f)$ and an element $x$ in $X$, one could ask the questions: How many iterations does it take for $x$ to reach a cycle vertex in the associated state space?  How many iterations does it take to have a guaranteed cycle vertex regardless of starting element?  These quantities are defined as follows. 

\[def:fds-height\] Let $(X,f)$ be a finite dynamical system and let $x$ be an element in $X$. The number of iterations it takes for $x$ to reach a cycle vertex during iteration is called the *height* of $x$, and is denoted $h(x)$.

\[def:fds-systemheight\] Let $(X,f)$ be a finite dynamical system.  The *system height* $s$, defined by $$s = \max_{x \in X} \left \{ h(x) \right \},$$ is the largest possible height of all $x \in X$.

When furnishing the set ${{\mathbb{Z}}_{n}^m}$ as a ${\mathbb{Z}}_n$-module and choosing any $m \times m$ matrix $A$ over ${\mathbb{Z}}_n$, we get a linear finite dynamical system $({{\mathbb{Z}}_{n}^m}, f)$, where $f$ is a ${\mathbb{Z}}_n$-endomorphism defined by $A$.  We now state a theorem which shows its *primary decomposition* in the form of factor systems.  The isomorphism ultimately has its root in the Chinese Remainder Theorem, and the primary decomposition of the underlying ring. 

\[thm:lfdsiso\] Let $({\mathbb{Z}}_{n}^m, A)$ be a linear finite dynamical system with a defining $m \times m$ matrix $A$ over ${\mathbb{Z}}_n$. If the prime factorization of $n$ is given by $$n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_{\omega}^{\alpha_{\omega}},$$ then $({\mathbb{Z}}_{n}^m, A)$ is isomorphic to $$\Pi_{k=1}^{\omega}({\mathbb{Z}}_{p_k^{\alpha_k}}^m, A {\ \text{\normalfont mod}\ p_k^{\alpha_k} }),$$ a product of linear finite dynamical systems. 

Given a system of the form $({{\mathbb{Z}}_{p^r}^m}, f)$, where $p$ is prime, there is a natural reduction defined by the projective homomorphism to the quotient module ${{\mathbb{Z}}_{p^r}^m}/ {\langle p \rangle}^m$.

\[def:indf\] Let $({{\mathbb{Z}}_{p^r}^m}, f)$ be a linear finite dynamical system, where $p$ is a prime number.  Let ${\langle p \rangle}^m$ be the submodule of ${{\mathbb{Z}}_{p^r}^m}$ created by $m$ copies of the principal ideal ${\langle p \rangle}$ in ${{\mathbb{Z}}_{p^r}}$. Let $$\pi \colon {{\mathbb{Z}}_{p^r}^m}\rightarrow {{\mathbb{Z}}_{p^r}^m}/ {\langle p \rangle}^m \qquad x \mapsto x+{\langle p \rangle}^m$$ be the natural homomorphism.  We say that $\overline{f} \colon {{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m \rightarrow {{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m$ defined by $\overline{f} \pi = \pi f$, is the function *induced by the natural homomorphism*, and where $$\overline{f}(x+{\langle p \rangle}^m) = f(x) + {\langle p \rangle}^m$$ for all $x+{\langle p \rangle}^m \in {{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m$.

By *Fitting’s Lemma* the state space of a linear system consists of copies of a single tree attached to cycle vertices.  In particular, there will always be a copy of this tree in isolation converging to the zero element. 

\[thm:fitting\] Let $(M,f)$ be a linear finite dynamical system over commutative ring $R$. Then there exists a positive integer $s$ and submodules $N$ and $T$ such that

(i) $N = f^s(M)$,

(ii) $T = f^{-s}(0)$,

(iii) $(M,f)$=$(N \oplus T,f|_N \oplus f|_T )$,

(iv) $f|_N$ is invertible,

(v) $f|_T$ is nilpotent,

where $f|_N$ and $f|_T$ are the restrictions of $f$ to each submodule. 

Let $(M,f)$ be a linear finite dynamical system over a commutative ring $R$. Let $T$ be the submodule of $M$, where for all $t \in T$, $f^k(t)=0$ for some nonnegative integer $k$. Then we will say that $T$ forms the *nilpotent component* of the system. 

Proof of the Function Independent Bound {#sec:proofa}
=======================================

In this section we will prove , a function independent bound on the height of a linear finite dynamical system of the form $({{\mathbb{Z}}_{n}^m}, f)$. The proof is at the end of this section. 

Consider linear finite dynamical systems $(M, f)$ where $M = {{\mathbb{Z}}_{n}^m}$. We can derive an upper bound on the height of these systems which is independent of the defining function.  By continuing the line of reasoning used in [@xu2009linear] we find the following lemma based on the prime factorization of $n$.

\[res11\] Let $({{\mathbb{Z}}_{n}^m},f)$ be a linear finite dynamical system and denote by $s$ the height of the system.  Then $$s \leq m \Omega(n),$$ where $\Omega(n)$ is the number of prime factors of $n$ counting multiplicity. 

By the properties of the linear function every iterated image $f^k({{\mathbb{Z}}_{n}^m})$ must be a submodule of the previous iteration.  Since a module is an abelian group under addition, each iterated image must also yield an additive subgroup of the previous iteration $f^{k-1}({\mathbb{Z}}_n^m)$. By Lagrange’s theorem $|f^{k}({\mathbb{Z}}_n^m)|$ divides $|f^{k-1}({\mathbb{Z}}_n^m)|$, i.e., the number of elements in the current iteration divides the number of elements in the previous iteration. 

Let the prime factorization of $n$ be $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\omega}^{\alpha_{\omega}}$, where $\omega$ is the number of distinct prime factors of $n$. Then the size of the module can be expressed as $n^m=\sum_{i=1}^{\omega} p_i^{m \alpha_i}$. The longest possible chain of proper submodules will be for linear maps, whose iterations reduce in each step the number of elements with a factor of a single prime.  This means that the maximum number of iterations $s$, for a chain of proper submodules is bounded above by $$s \leq \sum_{i=1}^{\omega} m \alpha_i = m \sum_{i=1}^{\omega} \alpha_i = m \Omega(n),$$ proving the lemma. 

suggests that the height of a linear finite dynamical system $({{\mathbb{Z}}_{n}^m},f)$, is intimately connected to the possible heights of subsystems modulo $p^r$, which are derived from the primary decomposition.  This is put on firm ground by the following lemma. 

\[res12\] Let $({\mathbb{Z}}_{n}^m, f)$ be a linear finite dynamical system with a defining matrix $A$ over ${\mathbb{Z}}_n$. If $n$ has the prime factorization $p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_{\omega}^{\alpha_{\omega}}$, then the height of the system is given by the largest height of $$\left \{ ({\mathbb{Z}}_{p_k^{\alpha_k}}^m,A {\ \text{\normalfont mod}\ p_k^{\alpha_k} }) \right \},$$ the collection of subsystems derived from its primary decomposition. 

We want to show that for the product system given in , the height is the largest height of the smaller factor systems.  The result will then follow from the isomorphism. 

The system is isomorphic to a product of subsystems of the form $$({\mathbb{Z}}_{p_k^{\alpha_k}}^m,A {\ \text{\normalfont mod}\ p_k^{\alpha_k} }),$$ for each distinct prime factor of $n$. Let the product set be $X=X_1 \times X_2 \times \cdots \times X_\omega$, where $X_k={\mathbb{Z}}_{p_k^{\alpha_k}}^m$. Let $\overline{f}$ be the function of the product system, such that $$\overline{f}(x_1,x_2,\dots,x_\omega) = (f_1(x_1),f_2(x_2),\dots,f_\omega(x_\omega)),$$ and where each $f_k$ is defined by the matrix $A {\ \text{\normalfont mod}\ p_k^{\alpha_k} }$.  Let $s_1,s_2,\dots,s_\omega$ be the subsystem heights and let $s$ be the largest one.  We have $s\geq s_k$ for each $k$ and according to Fitting’s Lemma $f_k^{s+1}(X_k)=f_k^s(X_k)$ for all $k$. This is now the smallest possible nonnegative integer which settles each subsystem in the product system.  Thus $s$ is the smallest nonnegative integer such that $\overline{f}^{s+1}(X)=\overline{f}^s(X)$, which yields $s$ as the system height of the product system.  The result follows from the isomorphism. 

We can now state the proof of the function independent part of the main result. 

By , we know that the system height $s$ is given by $$s = \max \left \{s_1, s_2, \dots, s_\omega \right \},$$ where each $s_k$ is the height of a subsystem of the form $({\mathbb{Z}}_{p_k^{\alpha_k}}^m,A {\ \text{\normalfont mod}\ p_k^{\alpha_k} })$, derived from the primary decomposition.  In addition, we know from , that each $s_k$ is bounded above by $m \alpha_k$, where $\alpha_k$ is the prime factor exponent of $p_k$. Hence for each $s_k$, we have an upper bound $m \alpha_{\max}$, where $\alpha_{max}$ is the largest exponent in the prime factorization of $n$. Therefore we also have an upper bound on $s$ given by $m \alpha_{\max}$.

Proof of the Function Dependent Bound {#sec:proofb}
=====================================

In this section we will prove , a function dependent bound on the height of a linear finite dynamical system of the form $({{\mathbb{Z}}_{n}^m}, f)$. The proof is at the end of this section. 

We will assume that the prime factorization of $n$ is known.  By looking at factor subsystems, derived from the primary decomposition, and examining their links to corresponding reduced systems over fields, an upper bound is found for each subsystem.  This bound will be function dependent and derived from the reduced system.  The main result then follows when considering , which states that the system height is given by the largest height of the factor systems.  Hence by taking the largest derived bound of all subsystems, we get the result. 

We now consider the relation between $({{\mathbb{Z}}_{p^r}^m}, f)$, where $p$ is prime, and a reduced system $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$, where $\overline{f}$ is given in .  Our ultimate goal is to derive from the reduction structural properties and height bounds for the larger system. 

We will start with a lemma showing a link between cycle vertices of both systems.  This will provide a basis for other results and our understanding of how the state graphs are related. 

\[res2\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system, and let ${\langle p \rangle}$ be the maximal ideal in ${{\mathbb{Z}}_{p^r}}$. Let $\overline{f}$ be the function induced by the natural homomorphism.  Then $x_0+{\langle p \rangle}^m$ is a cycle vertex in $$({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$$ if and only if the coset contains a cycle vertex in $({{\mathbb{Z}}_{p^r}^m},f)$.

We want to show that every cycle vertex $x+{\langle p \rangle}^m$ in the reduced system, contains, as a coset, a cycle vertex in the larger system.  We do this by demonstrating that for every element $x$ in the coset, there exists an element $w'$ in ${\langle p \rangle}^m$, such that $x+w'$ is a cycle vertex in $({{\mathbb{Z}}_{p^r}^m}, f)$. Conversely, if the coset contains a cycle vertex $x_0$ such that $f^k(x_0)=x_0$ for some positive integer $k$, we demonstrate that the properties of the induced function must yield $x+{\langle p \rangle}^m$ as a cycle vertex in $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$.

$(\Rightarrow)$ Let $x+{\langle p \rangle}^m$ be a cycle vertex in $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$. Then there exists a $k\geq 1$ such that $$(\overline{f})^k(x+{\langle p \rangle}^m)=f^k(x)+{\langle p \rangle}^m=x+{\langle p \rangle}^m.$$ Hence $f^k(x)=x+w$ for some $w \in {\langle p \rangle}^m$. Iterating in multiples of $k$ we get $$f^{2k}(x)=f^k(f^k(x))=f^k(x+w)=f^k(x)+f^k(w)=x+w+f^k(w),$$ and in general for positive integers $q$ we have $$f^{qk}(x)=x+w+f^k(w)+\cdots+f^{(q-1)k}(w),$$ by the linearity of the function.  We recall that ${\langle p \rangle}^m$ is a submodule of ${{\mathbb{Z}}_{p^r}^m}$, hence $$w+f^k(w)+\cdots+f^{(q-1)k}(w)=w',$$ for some $w'$ in ${\langle p \rangle}^m$. Choose integer $q$ such that $qk>h(x)$, where $h(x)$ is the height of $x$. Then $f^{qk}(x) = x_0$, where $x_0$ is a cycle vertex in $({{\mathbb{Z}}_{p^r}^m},f)$. We get $$x_0=f^{qk}(x)=x+w',$$ which implies that $x_0$ is in $x + {\langle p \rangle}^m$.

($\Leftarrow$) Assume $x+{\langle p \rangle}^m$ contains a cycle vertex $x_0$. Then there exists a $k\geq1$ such that $f^k(x_0)=x_0$. Hence $$x+{\langle p \rangle}^m=x_0+{\langle p \rangle}^m = f^k(x_0)+{\langle p \rangle}^m=(\overline{f})^k(x_0+{\langle p \rangle}^m)=(\overline{f})^k(x+{\langle p \rangle}^m),$$ yielding a cycle vertex in $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$.

A natural question is how the heights are related for elements of both systems.  gives us some information.  An element $x$ cannot reach a cycle vertex $y$ in $({{\mathbb{Z}}_{p^r}^m}, f)$ without turning $y+{\langle p \rangle}^m$ into a cycle vertex in the reduced system.  Hence $x$ cannot have a smaller height than $x+{\langle p \rangle}^m$ in the reduced system.  This effectively puts a lower bound on the height of all elements in the coset $x+{\langle p \rangle}^m$. The following lemma makes it precise. 

\[res4\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system, and let ${\langle p \rangle}$ be the maximal ideal in ${{\mathbb{Z}}_{p^r}}$. Let $\overline{f}$ be the function induced by the natural homomorphism.  If $x+{\langle p \rangle}^m$ has the height $t$ in $$({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f}),$$ then all $y \in x+{\langle p \rangle}^m$ have heights larger than or equal to $t$ in $({{\mathbb{Z}}_{p^r}^m}, f)$.

We will do a proof by contradiction.  Assume there exists an element $y$ in $x+{\langle p \rangle}^m$ of height $k$ less than $t$. Then $f^k(y) = y_0$, where $y_0$ is some cycle vertex in $({{\mathbb{Z}}_{p^r}^m}, f)$. Therefore, the $k$th iteration of $x+{\langle p \rangle}^m$, $$(\overline{f})^k(x+{\langle p \rangle}^m)=f^k(x)+{\langle p \rangle}^m = f^k(y)+{\langle p \rangle}^m = y_0 + {\langle p \rangle}^m,$$ contains a cycle vertex and according to , the coset must be a cycle vertex.  Hence $x+{\langle p \rangle}^m$ iterates to a cycle vertex in less than $t$ steps.  This contradicts the assumption. 

An immediate consequence of is a lower bound on the height of the larger system by the height of the reduced system. 

\[cor1\] If $t$ is the height of $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$, then the height $s$ of $({{\mathbb{Z}}_{p^r}^m},f)$ is bounded below by $t$.

If $t$ is the height of $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$, then there exists an element $x+{\langle p \rangle}^m$ with this height.  By every element of the coset must have a height equal to or larger than $t$. Hence for the maximal height $s$ of $({{\mathbb{Z}}_{p^r}^m},f)$ we have $s\geq t$.

We now turn our attention to leaf elements.  By Fitting’s Lemma the system height can be found by the height of the nilpotent component, i.e., there exists a leaf element in the nilpotent component of maximum height.  The next two lemmas show that we can deduce properties of $({{\mathbb{Z}}_{p^r}^m}, f)$ by examining leaf elements of the reduced system. 

\[res5\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system, and let ${\langle p \rangle}$ be the maximal ideal in ${{\mathbb{Z}}_{p^r}}$. Let $\overline{f}$ be the function induced by the natural homomorphism.  If $v+{\langle p \rangle}^m$ is a leaf in $$({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f}),$$ then the coset contains only leaf elements in $({{\mathbb{Z}}_{p^r}^m}, f)$.

We will do a proof by contradiction. 

Let $v+{\langle p \rangle}^m$ be a leaf in $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$. Assume there exists a $y \in v+{\langle p \rangle}^m$ and an $x \in {{\mathbb{Z}}_{p^r}^m}$, such that $f(x) = y$. This implies that $$\overline{f}(x+{\langle p \rangle}^m)=f(x)+{\langle p \rangle}^m=y+{\langle p \rangle}^m=v+{\langle p \rangle}^m,$$ contradicting the assumption that $v+{\langle p \rangle}^m$ is a leaf. 

\[res6\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system, and let ${\langle p \rangle}$ be the maximal ideal in ${{\mathbb{Z}}_{p^r}}$. Let $\overline{f}$ be the function induced by the natural homomorphism.  If $v+{\langle p \rangle}^m$ is a leaf in the nilpotent component of $$({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f}),$$ then it contains a leaf in the nilpotent component of $({{\mathbb{Z}}_{p^r}^m}, f)$.

Let $v+{\langle p \rangle}^m$ be a leaf of height $t$ in the nilpotent component of $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$. Then $$(\overline{f})^t(v+{\langle p \rangle}^m)=f^t(v)+{\langle p \rangle}^m={\langle p \rangle}^m,$$ therefore $t$ is the smallest positive integer such that $f^t(v) = w$, for some $w \in {\langle p \rangle}^m$. According to , every $y \in v+{\langle p \rangle}^m$ is a leaf, and by the corollary of , the height $s$ of $({{\mathbb{Z}}_{p^r}^m},f)$ is bounded from below by $t$.

Since ${\langle p \rangle}^m$ is a submodule, $f^k(w)$ is an element in ${\langle p \rangle}^m$ for all $w \in {\langle p \rangle}^m$ and positive integers $k$. Therefore, given a system height of $s$, $f^s(v)=w_0$, where $w_0$ is some cycle vertex in ${\langle p \rangle}^m$.

If $w_0$ is of period $l$, i.e., $f^{l}(w_0)=w_0$, we choose an integer $q$ such that $r = q l - s$ is nonnegative.  Then $y = v-f^r(w_0) =v-w'$, is in $v+{\langle p \rangle}^m$, and $$f^s(y)=f^s(v-w')=f^s(v)-f^s(f^{ql-s}(w_0))=w_0-w_0=0,$$ proving the lemma. 

In dealing with the relevant reduced subsystems of $({{\mathbb{Z}}_{p^r}^m}, f)$, it is handy to work with isomorphic systems.  The next proposition shows that the induced functions have simple representations based on the matrix of the linear function. 

\[res8\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system with a defining matrix $A$ over ${{\mathbb{Z}}_{p^r}}$. Let ${\langle p \rangle}$ be the maximal ideal in ${{\mathbb{Z}}_{p^r}}$ and let $\overline{f}$ be the function induced by the natural projective homomorphism.  Then $ ({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$ is isomorphic to $({{\mathbb{Z}}_p^m}, A {\ \text{\normalfont mod}\ p })$, and $({\langle p \rangle}^m,f)$ is isomorphic to $({\mathbb{Z}}_{p^{r-1}}^m, A {\ \text{\normalfont mod}\ p^{r-1} })$. 

The proof is a simple examination of induced functions of bijective morphisms between systems. 

Consider $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$. Let $\pi \colon {{\mathbb{Z}}_{p^r}^m}\rightarrow {{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}$ be the natural homomorphism, where $$\pi(x) =x+{\langle p \rangle}^m = x {\ \text{\normalfont mod}\ p } + {\langle p \rangle}^m,$$ for all $x \in {{\mathbb{Z}}_{p^r}^m}$. We may express the induced function $\overline{f}$ of $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$ by $$\overline{f}(x + {\langle p \rangle}^m) =f(x)+ {\langle p \rangle}^m = (Ax) {\ \text{\normalfont mod}\ p } + {\langle p \rangle}^m,$$ for all $x+{\langle p \rangle}^m$. Consider the bijection $$\psi \colon {{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}\rightarrow {{\mathbb{Z}}_p^m}\qquad x +{\langle p \rangle}^m \mapsto x {\ \text{\normalfont mod}\ p },$$ which we take as a morphism between systems $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$ and $({{\mathbb{Z}}_p^m}, \overline{g})$. Here we have an induced function $$\overline{g}\colon {{\mathbb{Z}}_p^m}\rightarrow {{\mathbb{Z}}_p^m}\qquad \overline{g}(x)=\psi \overline{f} \psi^{-1} (x) = Ax {\ \text{\normalfont mod}\ p },$$ for all $x \in {{\mathbb{Z}}_p^m}$, and therefore $\psi$ acts as an isomorphism between $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$ and $({{\mathbb{Z}}_p^m}, A {\ \text{\normalfont mod}\ p })$. 

Consider $({\langle p \rangle}^m,f)$. Here every element $w \in {\langle p \rangle}^m$ can be represented uniquely by $p v$ for some element $v \in {\mathbb{Z}}_{p^{r-1}}^m$. Hence there exists a bijection $\phi: {\langle p \rangle}^m \rightarrow {\mathbb{Z}}_{p^{r-1}}^m$, by $$\phi(p v) = v,$$ which induces a function $g(v) = \phi f \phi^{-1}=\phi(A p v)=Av {\ \text{\normalfont mod}\ p^{r-1} }$.  As such, $({\langle p \rangle}^m,f)$ is isomorphic to $({\mathbb{Z}}_{p^{r-1}}^m, A {\ \text{\normalfont mod}\ p^{r-1} })$. 

The next lemma shows, that it is possible to put a lower and upper bound on the height of $({{\mathbb{Z}}_{p^r}^m}, A)$ by the height of the reduced system $({{\mathbb{Z}}_p^m},A {\ \text{\normalfont mod}\ p })$. 

\[res16\] Let $({{\mathbb{Z}}_{p^r}^m},f)$ be a linear finite dynamical system with a defining matrix $A$ over ${{\mathbb{Z}}_{p^r}}$. Let $s$ be the height of the system.  Then $$s_1 \leq s \leq r s_1,$$ where $s_1$ is the height of the system $({{\mathbb{Z}}_p^m}, A {\ \text{\normalfont mod}\ p })$. 

Let $z$ be a leaf of maximal height $s$ in the nilpotent component of $({{\mathbb{Z}}_{p^r}^m},f)$. Since $$f^s(z)+{\langle p \rangle}^m = 0 + {\langle p \rangle}^m = {\langle p \rangle}^m,$$ $z+{\langle p \rangle}^m$ is a coset in the nilpotent component of $({{{\mathbb{Z}}_{p^r}^m}/{\langle p \rangle}^m}, \overline{f})$. As such $z$ reaches ${\langle p \rangle}^m$ within $t$ iterations, where $t$ is the system height of the reduced system.  Assuming maximal height, the reached element $w$ within ${\langle p \rangle}^m$ is of system height $k$ of $({\langle p \rangle}^m,f)$. Hence $s$ is bounded by $t \leq s \leq t + k$.

Working instead in the isomorphic systems of , and denoting by $s_k$ the height of systems of the form $({\mathbb{Z}}_{p^k}^m, A {\ \text{\normalfont mod}\ p^k })$, we have $t = s_1$, $k = s_{r-1}$ and $s = s_r$. Hence by recursion $$s_1 \leq s_r \leq s_1 + s_{r-1} \leq 2 s_1 + s_{r-2} \leq \cdots \leq r s_1,$$ proving the lemma. 

We are now ready to state the proof of the function dependent part of the main result. 

As we know from , the height is determined by the largest height of factor systems in the primary decomposition.  Applying to each such factor system and taking the largest bound yields the result. 

Let $h_i, i=1,2,\dots,\omega$ be the heights of the factor subsystems $({\mathbb{Z}}_{p_i^{\alpha_i}}^m,A {\ \text{\normalfont mod}\ p_i^{\alpha_i} })$ derived from the primary decomposition.  According to each $h_i \leq \alpha_i s_i$, where $s_i$ is the height of $({\mathbb{Z}}_{p_i}^m,A {\ \text{\normalfont mod}\ p_i })$.  Thus for all $i$, $h_i \leq \alpha_k s_k$, for some maximum product $\alpha_k s_k$ in $$\left \{ \alpha_1 s_1, \alpha_2 s_2, \dots, \alpha_{\omega} s_{\omega} \right \},$$ therefore we have a system height $s$ bounded by $a_k s_k$ according to . 

\[rem:thmb\] Given the system $({{\mathbb{Z}}_{n}^m}, f)$, we consider the largest product $\alpha s$, where $\alpha$ is an exponent of some prime $p$ in the factorization of $n$, and where $s$ is the height of the system mod $p$. The function independent bound of yields a bound $\alpha_{\max} m$, where $\alpha_{\max}$ is the largest of all exponents in the prime factorization.  Since $\alpha \leq \alpha_{\max}$ and $s \leq m$, offers the sharpest bound in this article. 

References {#references .unnumbered}
==========
