Let p be a prime, and consider the sequence x0,x1,dots of elements of the finite field mathbfFp given by x0=0 and xi+1=x2i+1 for all ige0. 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 mathbfFprightarrowmathbfFp. 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 sqrtp, exceeding xsqrtp with 'probability' exp(−x2/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 Mge2, let XM 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 Xinfty be a continuous random variable on [0,infty) that satisfies mathbfP(Xinfty>x)=e−x2/2.
Conjecture. The sequence fracT(XM)+U(XM)sqrtXM,quadMge2
of random variables converges (in distribution, say) to Xinfty.
Similarly, one might conjecture that T(XM)/(T(XM)+U(XM)) 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(XM)/(T(XM)+U(XM)) and (T(XM)+U(XM))/sqrtXM.
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