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

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

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

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