5
$\begingroup$

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).

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Gorka
    Jul 14, 2021 at 22:48
  • 1
    $\begingroup$ 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. $\endgroup$
    – John Omielan
    Jul 14, 2021 at 23:33
  • 2
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Jul 15, 2021 at 0:07
  • 1
    $\begingroup$ @JohnOmielan: This is a completely different question. It asks for an example of a polynomial, here the polynomial is given. $\endgroup$
    – markvs
    Jul 15, 2021 at 1:04
  • 5
    $\begingroup$ 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. $\endgroup$
    – David E Speyer
    Jul 15, 2021 at 2:57

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ 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. $\endgroup$
    – markvs
    Jul 15, 2021 at 3:59
  • 2
    $\begingroup$ @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. $\endgroup$
    – Joe Silverman
    Jul 15, 2021 at 11:25
  • $\begingroup$ the difficulty is that the members of the sequence are mutually coprime: each member is congruent to 1 modulo all previous, that does not allow to look for prime divisors from the same sequence $\endgroup$
    – Fedor Petrov
    Jul 15, 2021 at 15:05
  • 3
    $\begingroup$ @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. $\endgroup$
    – Joe Silverman
    Jul 15, 2021 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.