1
$\begingroup$

A Linear recurrent sequence is $x_{i+m} = a_{m-1}x_{i+m-1} + a_{m-2}x_{i+m-2} + ... + a_1x_{i+1} + a_0x_i$, where m is the order of sequence and $a_i$ is integer. Is the sequence of prime numbers ${2, 3, 5, 7, 11, 13, 17, 19, 23, ...}$ a linear recurrent sequence? And how can we validate our answer? Please write the answer in detail!

$\endgroup$
3
$\begingroup$

Suppose otherwise and fix the sequence $\{x_i\}$.

Pick a prime $p$ which doesn't divide any of the $a_i$. Clearly the sequence $\{x_i\}$ is eventually periodic $\pmod p$, as there are only finitely many $m-$tuples of residues $\pmod p$. since the recursion is reversible it must be periodic from the start.

Since the prime $p$ is included in the sequence, by definition, there must be infinitely many entries in the sequence which are divisible by $p$. A contradiction.

$\endgroup$
  • $\begingroup$ what is mean that "recursion is reversible"? And if we fix the sequence ${x_i} (mod p)$ there will be finitely many entries which are divisible by p. So, there initially can't be infinitely many entries which are divisible by p. $\endgroup$ – alexhak May 13 '18 at 12:28
  • 1
    $\begingroup$ Saying a recursion is reversible means that given enough of the succeeding terms we can compute the term which preceded them (this is where we use the fact that $p$ doesn't divide the coefficients). I don't understand your second concern...say the period is $\psi$ and that $x_i\equiv 0 \pmod p$ then $x_{i+n\psi}\equiv 0 \pmod p$ for all $n$. $\endgroup$ – lulu May 13 '18 at 12:31
  • $\begingroup$ My second concern is about "there must be infinitely many entries in the sequence which are divisible by p". Why is it so? $\endgroup$ – alexhak May 13 '18 at 12:44
  • $\begingroup$ For the reason I said. Read over my last comment carefully. $\endgroup$ – lulu May 13 '18 at 12:44
  • $\begingroup$ Do you know how to solve this problem click here? $\endgroup$ – alexhak May 13 '18 at 17:58
1
$\begingroup$

If it were, if all $a_i\geq0$ and $m>0$, then for any $k\in\mathbb N$ there would be an $N\in\mathbb N$ such that for all $n\geq N$ the difference between two primes $p_{n+1}-p_n$ would be greater than $k$.[1] Zhang proved that this is not true, see here. $m=0$ wouldn't work either obviously (As then $x_2=a_0 x_1$ would either be $x_1$ or not prime.)

I do not know how it would be with some $a_i <0$, but my guess is that here is a similar counter argument.

[1] This would also proof the twin prime conjecture false, but there is strong evidence it's true.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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