Periods of iterations of functions with restricted preimage sizes

2017/01/31 by Martins, Rodrigo S. V., Panario, Daniel, Qureshi, Claudio +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.09148

Abstract

We consider random mappings on n = kr nodes with preimage sizes restricted to a set of the form 0,k, where k = k(r) is greater than 1. We prove that T, the least common multiple of the cycle lengths, and B= the product of the cycle lengths, are both asymptotically lognormal. The expected values of these random variables are also also estimated and compared with numerical results. This work is motivated, in part, by the use of these mappings as heuristic models for polynomials of the form x^k + a over the integers modulo p with p congruent to 1 mod k.

Related

• Period Lengths for Iterated Functions
• Components and Cycles of Random Mappings
• Cycles in random k-ary maps and the poor performance of random random number generation
• Long cycle of random permutations with polynomially growing cycle weights
• Stochastic perturbations of iterations of a simple, non-expanding,\n nonperiodic, piecewise linear, interval-map