No linear recurrence for the primes

Si cette récurrence existe, alors on peut la résoudre et obtenir l’existence de polynômes complexes $Q_1,\dots, Q_r$ ainsi que de complexes $\alpha_1,\dots,\alpha_r$ tels que $\forall n\in\N, p_n=\sum_{i=1}^r Q_i(n) \alpha_i^n$. Ce résultat est issu du théorème sur les suites récurrentes à coefficients constants.

Ainsi, pour $n\to+\infty$, on a que $p_n$ serait équivalent à quelque chose de la forme $c\,n^a \sum_{j\in J}\alpha_j^n$ où $c$ est une constante complexe, $J$ l’ensemble des $\alpha_i$ de module maximal et $a$ le degré maximal des polynômes $Q_j, j\in J$.

Mais on sait pourtant que $p_n\underset{n\to+\infty}{\sim} n\ln(n)$ par le théorème des nombres premiers. Ce qui contredit ce qu’on vient de dire par croissance comparée (le log est négligeable que toutes les puissances de $n$ ou exponentielles).

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}$.