Periods of iterations of functions with restricted preimage sizes

DOI10.1145/3378570zbMATH Open1491.60017arXiv1701.09148OpenAlexW3033801922MaRDI QIDQ4987448FDOQ4987448

Authors: Rodrigo S. V. Martins, Daniel Panario, Claudio Qureshi, Eric Schmutz 

Publication date: 3 May 2021

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1701.09148

Recommendations

• Periods of iterations of mappings over finite fields with restricted preimage sizes
• Periods of iterated rational functions
• Random mappings with restricted preimages
• Period Lengths for Iterated Functions
• scientific article; zbMATH DE number 3994630

zbMATH Keywords

enumerationcomputations in finite fieldspermutations and combinations

Mathematics Subject Classification ID

Combinatorial probability (60C05) Other combinatorial number theory (11B75) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Cited In (7)

• Period Lengths for Iterated Functions
• Iteration entropy
• A survey on iterations of mappings over finite fields
• Periods of iterations of mappings over finite fields with restricted preimage sizes
• Periods of iterated rational functions
• On the heuristic of approximating polynomials over finite fields by random mappings
• Random mappings with restricted preimages

This page was built for publication: Periods of iterations of functions with restricted preimage sizes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987448)