Periods of Iterated Rational Functions over a Finite Field

Abstract

Choose a random degree d poly f with coefficients in a finite field F. We estimate the ultimate period of f under compositional iteration. We also determine the joint distribution of the small cycle lengths in the graph with edges (x,f(x)), x in F. The proofs use Lagrange interpolation and the method of factorial moments.

Improved results and exposition. To appearing IJNT

References in corpus (2)

• Graph components and dynamics over finite fields
• On the Heuristic of Approximating Polynomials over Finite Fields by Random Mappings

Cited by in corpus (3)

• Dynamically distinguishing polynomials
• A probabilistic heuristic for counting components of functional graphs of polynomials over finite fields
• The cycle structure of unicritical polynomials