No linear recurrence for the primes

Following Phil Caldero

Theorem. Let $\mathbb K$ be a field of characteristic zero. The sequence $(p_n)_{n\ge 1}$ of prime numbers satisfies no relation
$$a_0\,p_{n+d}=a_1\,p_{n+d-1}+\dots+a_d\,p_n\qquad (n\ge n_0)$$with $d\ge 1$, $a_0,\dots,a_d\in\mathbb K$ and $a_0\neq 0$.

Lemma 1 (descent). If a sequence with values in a subfield $F\subset\mathbb K$ satisfies such a relation with coefficients in $\mathbb K$, it satisfies one of the same order with coefficients in $F$.

Proof. Put $r_n=(p_{n+d-1},\dots,p_n)\in F^d$ and $b_n=p_{n+d}$. By assumption there is $a\in\mathbb K^d$ with $r_n\cdot a=b_n$ for $n\ge n_0$. Choose $r_{n_1},\dots,r_{n_k}$ a basis of the subspace of $F^d$ spanned by the $r_n$. The finite system $r_{n_j}\cdot X=b_{n_j}$ has coefficients in $F$ and a solution in $\mathbb K^d$; since rank is unchanged by field extension, it has a solution $a'\in F^d$. If $r_n=\sum_j c_j r_{n_j}$ with $c_j\in F$, then $r_n\cdot a'=\sum_j c_j b_{n_j}=\sum_j c_j\,(r_{n_j}\cdot a)=r_n\cdot a=b_n$. $\square$

Lemma 2 (periodicity modulo $q$). Let $(u_n)$ be a sequence of integers and $a_0,\dots,a_d\in\mathbb Z$ with $a_0a_d\ne 0$ such that $a_0u_{n+d}=\sum_{i=1}^d a_iu_{n+d-i}$ for $n\ge n_0$. For every prime $q$ not dividing $a_0a_d$, there is $T\ge 1$ such that $u_{n+T}\equiv u_n \pmod q$ for all $n\ge n_0$.

Proof. Modulo $q$, $a_0$ is invertible and the vector $v_n=(u_n,\dots,u_{n+d-1})\in\mathbb F_q^d$ satisfies $v_{n+1}=Av_n$, where $A$ is the companion matrix with entries $\bar a_i=a_ia_0^{-1}$. Since $\det A=\pm\bar a_d\neq 0$, $A$ lies in the finite group $\mathrm{GL}_d(\mathbb F_q)$, so $A^T=I$ for $T=|\mathrm{GL}_d(\mathbb F_q)|$, and $v_{n+T}=v_n$ for $n\ge n_0$. $\square$

Proof of the theorem. Suppose not, and take a relation of minimal order $d\ge 1$, valid for $n\ge n_0$. Since $\mathbb Q\subset\mathbb K$ and $p_n\in\mathbb Q$, Lemma 1 lets us assume the $a_i$ are rational, then integers after clearing denominators. We have $a_d\neq 0$: otherwise the relation, shifted by one index, would have order $d-1$. The integer $a_0a_d$ has only finitely many prime divisors, so there is $k\ge n_0$ such that $q=p_k$ does not divide $a_0a_d$. By Lemma 2, $p_{k+T}\equiv p_k=q\equiv 0\pmod q$. Thus $q$ divides the prime $p_{k+T}$, hence $p_{k+T}=q=p_k$, contradicting the strict monotonicity of $(p_n)$. $\square$

Remarks. The proof uses only two properties of $(p_n)$: every term is prime, and terms with distinct indices are distinct. It therefore applies to any injective sequence of primes. The characteristic-zero assumption is necessary: over $\mathbb F_2$, the sequence $(0,1,1,1,\dots)$ satisfies $u_{n+2}=u_{n+1}$.