Dynamics of linear systems over finite commutative rings (Q505656)

Let \(R\) be a finite ring, \(M\) a finite \(R\)-module, and \(f\) an endomorphism of \(M\). Let \(f^0\) denote the identity endomorphism of \(M\), \(f^1=f\), and, for \(n\geq 2\), let \(f^n\) denote \(f\) composed with \(f^{n-1}\). The paper is devoted to a study of possible cycles appearing in the sequences \(\{f^n(m)\}_{n\geq 0}\) (\(m\in M\)). The main theoretical result gives a common multiple for the cycle lengths of an automorphism of a module of the form \(M=\mathbb Z_{p^{a_1}} \times \cdots \times \mathbb Z_{p^{a_t}}\) with \(p\) prime and arbitrary integers \(1\leq a_1\leq \cdots \leq a_t\). Combining this with known techniques and assuming that the cycle lengths over any finite field can be computed, the authors provide an algorithm for computing the cycles in the general setting described at the beginning of the review. Under the hypothesis that the cardinality of the base ring \(R\) is small, the expected running time of the proposed algorithm is \(\tilde O(e^3)\), where \(e\) is the minimal number for which \(M\) admits a presentation as a quotient of the free module \(R^e\). The paper ends with three examples, one of which showing that the bound exhibited for the cycle lengths is sharp.