Periods of iterations of functions with restricted preimage sizes

DOI10.1145/3378570MaRDI QIDQ4987448zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

computations in finite fieldsenumerationpermutations and combinations

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

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

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)