Published In

International Mathematics Research Notices

Document Type

Article

Publication Date

11-1-2020

Subjects

Polynomials -- Dynamical systems

Abstract

A polynomial with integer coefficients yields a family of dynamical systems indexed by primes as follows: for any prime p" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; border: 0px; font-variant: inherit; font-stretch: inherit; line-height: normal; font-family: inherit; vertical-align: baseline; display: inline; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;">pp⁠, reduce its coefficients mod p" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; border: 0px; font-variant: inherit; font-stretch: inherit; line-height: normal; font-family: inherit; vertical-align: baseline; display: inline; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;">pp and consider its action on the field Fp" role="presentation" style="box-sizing: border-box; margin: 0px; padding: 0px; border: 0px; font-variant: inherit; font-stretch: inherit; line-height: normal; font-family: inherit; vertical-align: baseline; display: inline; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; position: relative;">FpFp⁠. 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 conjectural 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 that 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.

Rights

© The Author(s) 2018. Published by Oxford University Press. All rights reserved. For permissions, please e-mail: journals.permission@oup.com. This article is published and distributed under the terms of the Oxford University Press, Standard Journals Publication Model (https://academic.oup.com/journals/pages/open_access/funder_policies/chorus/standard_publication_model)

DOI

10.1093/imrn/rny232

Persistent Identifier

https://archives.pdx.edu/ds/psu/35739

Download

Share

COinS