# Arbitrarily many primes in a Fibonacci-type sequence

It is conjectured that the standard Fibonacci sequence contains infinitely many primes. While this is perhaps too difficult, I am wondering about the following simpler version:

Question. For any $K$, does there necessarily exist positive integers $a, b$ such that the sequence given by $x_1 = a, x_2 = b, x_{n} = x_{n-1} + x_{n-2}~(n \geq 3)$ contains at least $K$ primes?

I feel this bears some relation to the Green-Tao theorem, but I can't make the connection formal.

• I don't know, but there exist relatively prime positive integers $a$, $b$ such that your sequence contains no primes. (R. L. Graham, A Fibonacci-like sequence of composite numbers, Math Mag 37 (1964) 322-324) – Gerry Myerson Apr 28 '16 at 4:49

I think the answer to this question is yes. The theorem of Green, Tao and Ziegler says that a collection of $K$ linear forms over the integers will all take prime values infinitely often provided that they are nondegenerate (which, in the homogeneous case, means not multiples of one another) and there are no local obstructions. Thus you can't make $a, b , a+b$ all prime infinitely often (there's an obstruction mod 2) but you can make $a, b, a+ 2b$ prime infinitely often.

Let me explain how to find 5 prime elements in such a sequence (the argument clearly generalises). The nth term of your sequence is $F_{n-2} a + F_{n-1}b$. Since the Fibonacci sequence is periodic modulo any integer $Q$, I can find 5 values $n_1,\dots,n_5$ such that $F_{n_i-2} = 0 \pmod{30}$ and $F_{n_i-1} = 1 \pmod{30}$. The linear forms $F_{n_i-2} a + F_{n_i-1}b$ are a nondegenerate system, and when $b = 1 \pmod{30}$ they all take the value $1 \pmod{30}$. Hence there is no obstruction modulo $2$, $3$ or $5$ to all five of these forms being prime. Since consecutive Fibonacci numbers are coprime, none of the forms $F_{n_i-2} a + F_{n_i-1} b$ vanishes identically $\pmod{7}$. Thus the image of the map $(a,b) \mapsto (F_{n_1-2} a + F_{n_1 - 1}b, \dots, F_{n_5 - 2} a + F_{n_5 - 1} b)$ is a subspace $V$ of $(\mathbb{Z}/7\mathbb{Z})^5$ on which each of the five coordinate maps $\pi_i : (\mathbb{Z}/7\mathbb{Z})^5 \rightarrow (\mathbb{Z}/7\mathbb{Z})$ is nontrivial. By a counting argument, $V$ cannot be the union of the $\ker \pi_i|_V$, so there is some choice of $a,b$ for which the five linear forms are nonzero modulo $7$: that is, there are no local obstructions modulo 7 to all these forms being prime. Same modulo $11$, $13$ etc.