Can the same recursion pattern define several sequences of primes?

Question

First, some definitions:

Let $A$ be a shorthand for an infinite sequence $( a(1), a(2), a(3), \dots )$ of positive integers, likewise $B$ is an infinite sequence of positive integers $( b(1), b(2), b(3) , \dots)$, and C is an increasing infinite sequence of positive integers $( c(0), c(1), c(2), c(3), \dots)$. Call $c(0)$ the initial value of $C$.

We say that the pair $(A,B)$ is a recursion pattern for $C$ if for each positive integer n we have $c(n) = a(n) * c(n-1) + b(n)$. Given a recursion pattern $(A,B)$, and an initial value for $C$, we can reconstruct all the sequence $C$.

Clearly, for any increasing infinite sequence $C$ we can find a pair $(A,B)$ which is a recursion pattern for $C$, simply by taking all the $a(n)$ to be equal to $1$, and defining the $b(n)$ as required. If the sequence $C$ is increasing quickly, there will be many pairs $(A,B)$ which will be recursion patterns for $C$.

In particular, for any increasing sequence of primes, we can find recursion patterns, many of them if the sequence grows quickly.

Now the question: can a pair $(A,B)$ be a recursion pattern for more than one sequence of primes? In other words, given $A$ and $B$ as a recursion pattern, is it possible there is more than one initial value for $c(0)$ which will lead to an infinite sequence of primes?

Comments: If the answer is yes, and we can prove that, I would expect the proof to be quite difficult. Maybe a conditional proof would be possible. On the other hand, it may be elementary to show that the answer is no. This question was written up by Moshe Newman.

Answer 1

The answer is yes, there are "recursion patterns" which result in sequences of primes for more than one choice of $c(0)$. In fact, if you are given any two "starting points", it is possible to find such sequences. The proof comes from the pigeonhole principle.

Start with $c(0), c'(0)$. These are two prime numbers with difference $d(1) := c'(0) - c(0)$. Then as the set of prime numbers is infinite, there is some pair $p_1 < p'_1$ such that $p_1 \equiv p'_1 (\text{mod }d)$. Let $a(1) = \frac{p'_1 - p_1}{d(1)}$; let $b(1) = p_1 - a(1) c(0)$. (Note: I've slightly cheated here, and will explain the cheat at the end). Then $c(1) = a(1) c(0) + b(1) = a(1) c(0) + p_1 - a(1) c(0) = p_1$, while $c'(1) = a(1) c(0) + b(1) = \frac{p'_1 - p_1}{c'(0) - c(0)} c'(0) + p_1 - \frac{p'_1 - p_1}{c'(0) - c(0)} c(0) = p'_1$, as desired.

This is a pattern that can be repeated in the obvious way. We therefore have a recursion pattern that results in sequences of primes for multiple "starts".

Now for the cheat: there's no reason so far why this would make $b(i)$ positive. I don't have a completely elementary reason for that, but the prime number theorem should be enough to guarantee it. Essentially, the $n$th prime number doesn't grow "quickly enough" to escape such pairs.

Answer 2

There are very good reasons to think that for every even $g$ there are infinitely many primes $p$ with $p+g$ also prime. For this to be true for even one $g$ makes the answer to to your question yes (and it is known that there is a $g \leq 246$ which works). I’ll give the reasons at the end along with an extension to several sequences of primes.

For $g=10$ the primes with $p+10$ also prime also start out

$$3, 7, 13, 19, 31, 37, 43, 61, 73, 79, 97, 103, 127, 139, 157, 163, 181, 223, 229,\cdots$$

If this is indeed infinite, then one can pick any sub-sequence and the shift by $10$ such as

$$3,19,73,79,157,229,\cdots$$ $$13,29,83,89,167,239,\cdots.$$

Then $(A,B)$ is a recursion pattern for both sequences of primes where $A=1,1,1,\cdots$ and $B=16,54,6,78,72,\cdots$ is the correct $B$ sequence.

There is known to be at least one $g \leq 246$ with infinitely many primes $p,p+g.$ (in fact infinitely many with the two primes successive, not that we care here.) So that alone shows that the answer to your question is yes.

Assuming what I said about even $g$ is true, it follows that there is great freedom in finding recursion patterns which describe two prime sequences. Specifically: suppose we play a game where you give me two odd primes $p_0 \lt p_0',$ a multiplier $a_1,$ and an integer $\beta_1.$ Then I need to give you a shift $b_1 \gt \beta_1$ so that $p_1=a_1p_0+b_1$ and $p'_1=a_1p'_0+b_1$ are both prime. Then, after I tell you this, you can give me any $a_2$ and $\beta_2$ and I must give $b_2 \gt \beta_2$ so that $p_2=a_2p_1+b_2$ and $p'_2=a_2p'_1+b_2$ are both prime. We continue in this way forever or until I get stuck.

If I can always manage the first step of finding $b_1$ then I will never get stuck. It is just the same problem over and over with a different given $p,p',a,\beta$ each time. Just pick $g=a_0(p'_0-p_0)$ and, since there are infinitely many pairs $p,p+g,$ just pick one with $p-a_1p_0 \gt \beta_1.$

Here are details on the claim at the top. Define $\pi_g(x)$ to be the number of primes $p \lt x$ with $p+g$ also prime. Then there are good simple reasons to expect that $\pi_2(x)$ is asymptotic to $C_2\frac{x}{(\ln x)^2} $ for $C_2=\Pi_{p \geq 3}(1-\frac1{(p-1)^2}).$ Numerical calculations up to high $x$ match this quite well. The same reasoning suggests that there is a similar $C_g$ for each $g$ which depends only on the prime divisors of $g$ So $C_{2^k}=C_2$ and for any $g=2^k3^j$ , $C_g=2C_2$. In general, $C_g=C_2\Pi_{p \mid g}\frac{p-1}{p-2}.$ Again, the numerical evidence fits the prediction.

Extension There is an obvious conditions on $g$ for it to be conceivable that there is an arithmetic progression $p,p+g,p+2g,\cdots, p+(s-1)g$ of $s$ primes (say with $p\gt 2s$. ) Namely, $g$ needs to be divisible by all primes up to $s.$ Given an appropriate $g$ it is conjectured that there are infinitely many such progressions of $s$ primes and even that their density should be $c_{s,g}\frac{x}{(\ln x)^s}.$ If so, given any initial progression of $s$ primes with gap $g$ (all these primes greater than $s$) and a sequence of multipliers $A$ , revealed one step at a time, then these would be the starts of $s$ sequences of primes all with the same recursion pattern $(A,B)$ and I can build the jump sequence $B$ with great freedom.