The cycle structure of unicritical polynomials

DOI10.1093/IMRN/RNY232MaRDI QIDQ5854246zbMATH OpenOpenAlexFDO

Authors Andrew Bridy, Derek Garton

Publication date 16 March 2021

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

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

zbMATH Keywords

conjectural randomnessdynamical systems indexed by primesnumber of cyclesPollard's algorithm

Mathematics Subject Classification ID

Factorization; primality (11A51) Factorization (11Y05) Polynomials in real and complex fields: factorization (12D05) Generation, random and stochastic difference and differential equations (37H10) Arithmetic and non-Archimedean dynamical systems involving polynomial and rational maps (37P05) Arithmetic properties of periodic points (37P35)

Abstract: A polynomial with integer coefficients yields a family of dynamical systems indexed by primes as follows: for any prime $p$, reduce its coefficients mod $p$ and consider its action on the field $mathbb{F}_p$. The questions of whether and in what sense these families are random have been studied extensively, spurred in part by Pollard's famous "rho" algorithm for integer factorization (the heuristic justification of which is the randomness of one such family). However, the cycle structure of these families cannot be random, since in any such family, the number of cycles of a fixed length in any dynamical system in the family is bounded. In this paper, we show that the cycle statistics of many of these families are as random as possible. As a corollary, we show that most members of these families have many cycles, addressing a conjecture of Mans et. al.

Recommendations

• Dynamically distinguishing polynomials
• scientific article; zbMATH DE number 2010177
• Periods of iterated rational functions
• Periodic points of polynomials over finite fields
• Distribution of cycles of monomial p-adic dynamical systems

Cited in

(8)

• Periodic points and tail lengths of split polynomial maps modulo primes
• Dynamically distinguishing polynomials
• Random cyclic dynamical systems
• Univalent (monodentate) substitution on convex polyhedra. II. Listing of cycle indices
• Analytic number theory for 0-cycles
• Periodic points of polynomials over finite fields
• Functional graphs of families of quadratic polynomials
• Choosing iteration maps for the parallel Pollard rho method

This page was built for publication: The cycle structure of unicritical polynomials

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