History

Please fill in your query. A complete syntax description you will find on the General Help page.
Cycle structure of baker transformation in one dimension. (English)
J. Cell. Autom. 5, No. 1-2, 51-78 (2010).
Summary: In an earlier paper, we have been concerned with obtaining estimates for cycles lengths in the State Transition Diagrams (STD) for finite one-dimensional additive cellular automata. As part of this work, the discrete baker transformation was defined as a mapping on the rule space of linear cellular automata. In one application of this transformation we showed that the transition diagram of the baker transformation has the property that if two cellular automata rules lie on the same cycle of this diagram they have isomorphic STDs. In this paper, we focus attention on cycle periods of the baker transformation itself. To do this, we consider orbits generated by elements of $\{0,\dots, n-1\}$ under the baker transformation for different numbers $n$ and primes $p$. The general problem is reduced to the case $n = q$ where $q$ is a prime different from $p$. The complete description of orbits is obtained. Since in particular there are finitely many primes $q$ on which the baker transform modulo $p$ generates cycles of a given length $s$ we introduce universal numbers that are products of all numbers $q^{\hbar_q}(p)$ for such primes $q$ (where $\hbar_q(p)$ is an exponent of $q$ in $\text{ord}_qp$). We show that these numbers contain important information about collections of baker cycles. Results about relation of some of the universal numbers to the classical Mersenne and Fermat numbers are obtained.