6
$\begingroup$

Let $f\in \mathbb{Q} [x]$ be a polynomial, and $a_0 = a$ be an arbitrary integer. Let us define a sequence $\{a_n \} $ by the recurrence relationship : $$a_n = f(a_{n-1} ). $$ I want to show that $a_n $ cannot always be a prime number, with $\{a_n \}$ being pairwise distinct. I am pretty sure that this is a very well known fact, but I cannot easily find this.

Note : I posted this question also in SE Math.

https://math.stackexchange.com/questions/1568513/non-existence-of-a-prime-generating-polynomial-recurrence-relation

Improve this question
$\endgroup$

1 Answer 1

Reset to default
13
$\begingroup$

Let $a_0 = 2^{2^k} + 1$ for $k$ sufficiently large, and let

$$a_n = (a_{n-1} - 1)^2 + 1.$$

Then $a_n = 2^{2^{k+n}} + 1$, so this sequence can't always be prime regardless of the value of $k$ iff there are infinitely many composite Fermat numbers, and as far as I know this is wide open.

Improve this answer
$\endgroup$
5
  • $\begingroup$ What about if $f$ is linear - is it a then a well known (trivial?) result? $\endgroup$
    – Yaakov Baruch
    Dec 10, 2015 at 7:43
  • 1
    $\begingroup$ @Yaakov: even then I think it's hard. In that case $a_n = a r^n + b$ for integers $a, r, b$ and I'm not sure how to rule out the possibility that some such sequence has all prime values. For example, you might try finding some large prime $p$ with respect to which $r$ is a primitive root, and thereby hope to find a term divisible by $p$, but I don't know how to guarantee that such a $p$ exists (and as far as I know this sort of thing is also wide open). $\endgroup$
    – Qiaochu Yuan
    Dec 10, 2015 at 7:52
  • $\begingroup$ @QiaochuYuan Repeatedly applying linear function will give you not $a+n=ar^n+b$, but rather $a_n=a^na_0+a^{n-1}b+...+ab+b$. $\endgroup$
    – Wojowu
    Dec 10, 2015 at 13:49
  • 4
    $\begingroup$ Regarding $a r^n + b$ -- Let $p=ar+b$, by hypothesis it is prime. Then $a r^p+b \equiv ar+b \equiv 0 \bmod p$. So $a r^p+b$ is not prime. $\endgroup$
    – David E Speyer
    Dec 10, 2015 at 14:47
  • $\begingroup$ @Wojowu: that's a geometric series; you can sum it. $\endgroup$
    – Qiaochu Yuan
    Dec 10, 2015 at 17:13

Your Answer

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

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