Cycle Structure of Baker Transformation in One Dimension
Valeriy Bulitko and Burton Voorhees
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, . . . , 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 [upsilon] p(s) that are products of all numbers q hq(p) for such primes q (where hq(p) is an exponent of q in ord hq). We show that these numbers contains important information about collections of baker cycles. Results about relation of some of universal numbers to the classical Mersenne and Fermat numbers are obtained.
Keywords: Additive cellular automata, estimates of cycle’s lengths, discrete baker transformation.