Journal article
Periods of Iterations of Functions with Restricted Preimage Sizes
ACM transactions on algorithms, v 16(3), pp 1-28
01 Jun 2020
Abstract
Let [n] = {1, ..., n} and let On be the set of all mappings from [n] to itself. Let f be a random uniform element of Omega(n) and let T(f) and B(f) denote, respectively, the least common multiple and the product of the length 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 random uniform 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, with p equivalent to 1 (mod k). We exhibit and discuss our numerical results on this heuristic.
Metrics
9 Record Views
Details
- Title
- Periods of Iterations of Functions with Restricted Preimage Sizes
- Creators
- Rodrigo S. Martins - Federal University of Technology – ParanáDaniel Panario - Carleton UniversityClaudio Qureshi - University of the RepublicEric Schmutz - Drexel University
- Publication Details
- ACM transactions on algorithms, v 16(3), pp 1-28
- Publisher
- Assoc Computing Machinery
- Number of pages
- 28
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000582617500003
- Scopus ID
- 2-s2.0-85088694635
- Other Identifier
- 991019169795504721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Theory & Methods
- Mathematics, Applied