Iteration of Quadratic Polynomials Over Finite Fields

Abstract

For a finite field of odd cardinality $q$, we show that the sequence of iterates of $a{X}^2+c$, starting at $0$, always recurs after $O(q/\log \log q)$ steps. For $X^2+1$ the same is true for any starting value. We suggest that the traditional "Birthday Paradox" model is inappropriate for iterates of $X^3+c$, when $q$ is 2 mod 3.

This revision acknowledges prior work by Juul, Kurlberg, Madhu and Tucker, and by Shao, proving results that are closely related to those of the current paper

References in corpus (1)

• Forms in many variables and differing degrees