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
    Commented 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
    Commented 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
    Commented 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
    Commented Dec 10, 2015 at 14:47
  • $\begingroup$ @Wojowu: that's a geometric series; you can sum it. $\endgroup$
    – Qiaochu Yuan
    Commented Dec 10, 2015 at 17:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .