Let pp be a prime, and consider the sequence x0,x1,dotsx0,x1,dots of elements of the finite field mathbfFpmathbfFp given by x0=0x0=0 and xi+1=x2i+1xi+1=x2i+1 for all ige0ige0. This sequence must eventually start repeating; let's write T(p)T(p) and U(p)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 pp, T(p)T(p) and U(p)U(p) should behave like the period and preperiod of the sequence of iterates of a randomly chosen function mathbfFprightarrowmathbfFpmathbfFprightarrowmathbfFp. For example, it's expected that the quantity T(p)+U(p)T(p)+U(p) (that is, the index of the first repeated value in the sequence) is comparable in magnitude to sqrtpsqrtp, exceeding xsqrtpxsqrtp with 'probability' exp(−x2/2)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 Mge2Mge2, let XMXM be a discrete random variable that takes values in the set of primes not greater than MM, with all primes in [2,M][2,M] being equally likely to occur. Let XinftyXinfty be a continuous random variable on [0,infty)[0,infty) that satisfies mathbfP(Xinfty>x)=e−x2/2mathbfP(Xinfty>x)=e−x2/2.
Conjecture. The sequence fracT(XM)+U(XM)sqrtXM,quadMge2fracT(XM)+U(XM)sqrtXM,quadMge2
of random variables converges (in distribution, say) to XinftyXinfty.
Similarly, one might conjecture that T(XM)/(T(XM)+U(XM))T(XM)/(T(XM)+U(XM)) is, in the limit, uniformly distributed on (0,1](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))T(XM)/(T(XM)+U(XM)) and (T(XM)+U(XM))/sqrtXM(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