Conjectures on iterated polynomial maps on finite fields

Question

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

Answer 1

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