Let f be a uniformly random element of the set of all mappings from [n] = {1,... , n} to itself. Let T(f) and B(f) denote, respectively, the least common multiple and the product of the lengths of the cycles of f. Harris proved in 1973 that logT converges in distribution to a standard normal distribution and, in 2011, Schmutz obtained an asymptotic estimate on the logarithm of the expectation of T and B over all mappings on n nodes. We obtain analogous results for uniform random mappings on n = kr nodes with preimage sizes restricted to a set of the form {0, k}, where k = k(r) ≥ 2. This is motivated by the use of these classes of mappings as heuristic models for the statistics of polynomials of the form xk + a over the integers modulo p, where k divides p - 1. We exhibit and discuss our numerical results on this heuristic.

Additional Metadata
Keywords Brent-Pollard heuristic, Periods of mappings, Random mappings with indegree restrictions
Persistent URL dx.doi.org/10.4230/LIPIcs.AofA.2018.30
Conference 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, AofA 2018
Citation
Martins, R.S.V. (Rodrigo S.V.), Panario, D, Qureshi, C. (Claudio), & Schmutz, E. (Eric). (2018). Periods of iterations of mappings over finite fields with restricted preimage sizes. In Leibniz International Proceedings in Informatics, LIPIcs. doi:10.4230/LIPIcs.AofA.2018.30