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_prightarrow 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 $xsqrt 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!]
No comments:
Post a Comment