# Checking if polynomial can be iterated and only take prime values

I have the polynomial $$f(x) = x^2-x+1$$ and I am wondering if there is a positive prime value $$p$$ such that $$f(p),f^2(p),f^3(p)\dots$$ are all prime.

I have ran some computer simulations and I feel like the answer should be "no" ( because looking at the map $$x^2-x+1 \bmod p$$ I get that the expected number of prime divisors of the first $$M$$ values should be larger than $$M$$). I feel that my analysis is not very good however.

Does anyone know an approach which could be more fruitful?

Note: $$f^2(x) = f(f(x))$$

Edit: I would be happy with any sort of reference regarding a polynomial staying inside the primes under iteration, if there isn't anything particularly useful which can be said about this sort of thing I understand that as well).

• Something curious: for some primes, like $160117$ we get that all but $86$ residues $\bmod p$ stabilize at $1$ (which means they have to pass through $0$ first ), and there seem to be many primes like this. Jul 14, 2021 at 22:48
• FYI, your question is basically a special case of Integer dynamics hitting infinitely many primes, but you ask for $f^{n}(x)$ being prime for all $n$ where $x$ is a prime, instead of this being prime for just infinitely many $n$ which is asked about in the other question. Jul 14, 2021 at 23:33
• I know I've seen a similar question recently. math.stackexchange.com/questions/4182382/… isn't the one I'm thinking of, but it is somewhat related. Jul 15, 2021 at 0:07
• @JohnOmielan: This is a completely different question. It asks for an example of a polynomial, here the polynomial is given. Jul 15, 2021 at 1:04
• I believe that no one can disprove that $2^{2^n}+1$ is prime for all sufficiently large $n$ (although no one believes this to be true). Since $2^{2^n}+1$ is $f^{(n)}(3)$ where $f(x) = (x-1)^2+1$, this means that we can't rule out that the iterates of a quadratic polynomial might always be prime. Jul 15, 2021 at 2:57

This is not an answer to your question, but will point you toward work on the number theoretic properties of such sequences. Iteration of $$x^2-x+1$$ starting at $$a=2$$ is called the Sylvester sequence. A theorem about primes that divide the terms in such sequences was proved by Rafe Jones (The density of prime divisors in the arithmetic dynamics of quadratic polynomials. J. Lond. Math. Soc. (2) 78 (2008), no. 2, 523–544. MR2439638) One of his results is that if $$k\in\mathbb Z$$ with $$k\notin\{0,2\}$$, then the set of primes dividing the integers in the orbit of any $$a\in\mathbb Z$$ under iteration of $$x^2+kx-1$$ has density $$0$$.
In a different direction, one can prove that the numbers in your sequence, for any starting prime $$p$$, grow quadratically exponentially, and in fact $$\lim_{n\to\infty} \frac{1}{2^n} \log f^n(p) \quad\text{converges to a positive real number.}$$ Thus your sequence is growing very rapidly, which means that we have very few tools at our disposal to prove statements of the sort you ask.
• But there are tools to disprove the statement. It is highly unlikely there exists such a prime $p$ and it is quite possible there exists an elementary proof of this statement. Jul 15, 2021 at 3:59
• @MarkSapir That's a good point. For example, it's easy to prove a polynomial cannot take on only prime values, and iteration of "easy" polynomials such as $f(x)=x^d$ are also trivial. However, for $x^2-x+1$, I don't see an easy congruence-type argument, so I'm not sure I'd be so confident as to say "quite possible", but I'd be willing to go with "not inconceivable". :) From a probabilistic perspective, the probability that $f^n(p)$ is prime should be $O(1/2^n)$, so most likely there are only finitely many primes in the sequence. Jul 15, 2021 at 11:25
• @FedorPetrov Very true, so the elementary congruence-divisibility argument for values of polynomials won't work, i.e., there is no identity like $$f\bigl(m+nf(m)\bigr)\equiv0\pmod{f(m)}\quad\text{for all fixed m and all n.}$$ OTOH, there are other ways to prove compositeness, e.g., if $$2^N\not\equiv2\pmod{N},$$ then $N$ is composite. And there are similar criteria using quadratic residues. Not that I have any idea how one might use this to prove compositeness for a number in the sequence $f^n(p)$, but I'd want to think about it a lot more before entirely ruling out such an approach. Jul 15, 2021 at 15:30