2026-08-10T19:43:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8923 2024-03-06T10:43:45Z ddc:004 open_access

Periods of Iterations of Mappings over Finite Fields with Restricted Preimage Sizes Martins, Rodrigo S. V. Panario, Daniel Qureshi, Claudio Schmutz, Eric random mappings with indegree restrictions Brent-Pollard heuristic periods of mappings 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 log T 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 x^k + a over the integers modulo p, where k divides p - 1. We exhibit and discuss our numerical results on this heuristic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rodrigo S. V. Martins and Daniel Panario and Claudio Qureshi and Eric Schmutz 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.30 urn:nbn:de:0030-drops-89237 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.30 eng https://creativecommons.org/licenses/by/3.0/legalcode