Let $p$ be a prime, and consider the sequence $x_0, x_1, \dots$ of elements of the finite field $\mathbf F_p$ given by $x_0 = 0$ and $x_{i+1} = x_i^2 + 1$ for all $i \ge 0$. This sequence must eventually start repeating; let's write $T(p)$ and $U(p)$ for the period and preperiod (resp.) of the sequence.
There's an informal idea, used for example as the basis of Pollard's Rho method for integer factorisation, that for a 'randomly chosen' prime $p$, $T(p)$ and $U(p)$ should behave like the period and preperiod of the sequence of iterates of a randomly chosen function $\mathbf F_p\rightarrow \mathbf F_p$. For example, it's expected that the quantity $T(p) + U(p)$ (that is, the index of the first repeated value in the sequence) is comparable in magnitude to $\sqrt p$, exceeding $x\sqrt p$ with 'probability' $\exp(-x^2/2)$.
Question: Does anyone know of formal statements to this effect in the literature? I'm looking for a conjecture that would imply the following (or something similar) as a special case:
Notation. For each positive integer $M \ge 2$, let $X_M$ be a discrete random variable that takes values in the set of primes not greater than $M$, with all primes in $[2, M]$ being equally likely to occur. Let $X_\infty$ be a continuous random variable on $[0, \infty)$ that satisfies $\mathbf P(X_\infty > x) = e^{-x^2/2}$.
Conjecture. The sequence $$\frac{T(X_M) + U(X_M)}{\sqrt{X_M}}, \quad M \ge 2$$
of random variables converges (in distribution, say) to $X_\infty$.
Similarly, one might conjecture that $T(X_M) / (T(X_M) + U(X_M))$ is, in the limit, uniformly distributed on $(0, 1]$, and it should be possible to make (not prove!) some sort of statement about the independence of $T(X_M) / (T(X_M) + U(X_M))$ and $(T(X_M) + U(X_M)) / \sqrt{X_M}$.
I've so far failed to find any concrete statements of this form in the literature. Any pointers?
[It's difficult to know how to tag this. I guess it's really about discrete dynamical systems; please retag as appropriate!]
Best Answer
"ds.Dynamical-Systems" and "nt.Number-Theory" are good tags. Another one you could add is "Arithmetic-Dynamics". You might look at the arithmetic dynamics bibliography that I've assembled at
http://www.math.brown.edu/~jhs/ADSBIB.pdf
and search for titles that include the words "finite field". (Sorry, it hasn't been updated in a while.)
I'll also mention the following three articles.
(The summary says " "We consider dynamical systems generated by iterations of rational functions over finite fields and residue class rings. We present a survey of recent developments and outline several open problems.")
Here's a paper of mine which might be relevant, although the estimates are pretty weak:
And one more whose summary says "The orbits produced by the iterations of the mapping $x\mapsto x^2+c$, defined over $\mathbb{F}_q$, are studied. Several upper bounds for their periods are obtained, depending on the coefficient $c$ and the number of elements $q$."
If you forward and backward reference these papers, you'll certainly find other papers dealing with iteration over finite fields.