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!]



Conjectures on iterated polynomial maps on finite fields
"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. 


* H. Niederreiter and I. E. Shparlinski. Dynamical systems generated by rational functions.
In *Applied Algebra, Algebraic Algorithms and Error-Correcting Codes* (Toulouse, 2003),
volume **2643** of Lecture Notes in Comput. Sci., pages 6–17. Springer, Berlin, 2003.


(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:


* Variation of periods modulo p in arithmetic dynamics, *New York J. Math.* **14** (2008), 601-616.


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$."


* A. Peinado, F. Montoya, J. Munoz, and A. J. Yuste. Maximal periods of $x^2 + c$ in $\mathbb{F}\_q$. In *Applied Algebra, Algebraic Algorithms and Error-Correcting Codes* (Melbourne, 2001),
volume **2227** of Lecture Notes in Comput. Sci., pages 219–228. Springer, Berlin, 2001.


If you forward and backward reference these papers, you'll certainly find other papers dealing with iteration over finite fields.


