Une récurrence pour les nombres premiers ???

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).

Preuve issue de la vidéo de Phil Caldero: https://www.youtube.com/watch?v=CwGdJaZcGV8

Théorème. Soit $\mathbb K$ un corps de caractéristique nulle. La suite $(p_n)_{n\ge 1}$ des nombres premiers ne vérifie aucune relation
$$a_0\,p_{n+d}=a_1\,p_{n+d-1}+\dots+a_d\,p_n\qquad (n\ge n_0)$$avec $d\ge 1$, $a_0,\dots,a_d\in\mathbb K$ et $a_0\neq 0$.

Lemme 1 (descente). Si une suite à valeurs dans un sous-corps $F\subset\mathbb K$ vérifie une telle relation à coefficients dans $\mathbb K$, elle en vérifie une de même ordre à coefficients dans $F$.

Preuve. Posons $r_n=(p_{n+d-1},\dots,p_n)\in F^d$ et $b_n=p_{n+d}$. L’hypothèse donne $a\in\mathbb K^d$ avec $r_n\cdot a=b_n$ pour $n\ge n_0$. Choisissons $r_{n_1},\dots,r_{n_k}$ une base du sous-espace de $F^d$ engendré par les $r_n$. Le système fini $r_{n_j}\cdot X=b_{n_j}$ a ses coefficients dans $F$ et une solution dans $\mathbb K^d$ ; le rang ne changeant pas par extension du corps, il a une solution $a'\in F^d$. Si $r_n=\sum_j c_j r_{n_j}$ avec $c_j\in F$, alors $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$

Lemme 2 (périodicité modulo $q$). Soit $(u_n)$ une suite d’entiers et $a_0,\dots,a_d\in\mathbb Z$ avec $a_0a_d\ne 0$ tels que $a_0u_{n+d}=\sum_{i=1}^d a_iu_{n+d-i}$ pour $n\ge n_0$. Pour tout premier $q$ ne divisant pas $a_0a_d$, il existe $T\ge 1$ tel que $u_{n+T}\equiv u_n \pmod q$ pour tout $n\ge n_0$.

Preuve. Modulo $q$, $a_0$ est inversible et le vecteur $v_n=(u_n,\dots,u_{n+d-1})\in\mathbb F_q^d$ vérifie $v_{n+1}=Av_n$, où $A$ est la matrice compagnon de coefficients $\bar a_i=a_ia_0^{-1}$. Comme $\det A=\pm\bar a_d\neq 0$, $A$ appartient au groupe fini $\mathrm{GL}_d(\mathbb F_q)$, donc $A^T=I$ pour $T=|\mathrm{GL}_d(\mathbb F_q)|$, et $v_{n+T}=v_n$ pour $n\ge n_0$. $\square$

Preuve du théorème. Par l’absurde, prenons une relation d’ordre $d\ge 1$ minimal, valable pour $n\ge n_0$. Comme $\mathbb Q\subset\mathbb K$ et $p_n\in\mathbb Q$, le lemme 1 permet de supposer les $a_i$ rationnels, puis entiers en chassant les dénominateurs. On a $a_d\neq 0$ : sinon la relation, décalée d’un cran, serait d’ordre $d-1$. L’entier $a_0a_d$ n’a qu’un nombre fini de diviseurs premiers, donc il existe $k\ge n_0$ tel que $q=p_k$ ne divise pas $a_0a_d$. Par le lemme 2, $p_{k+T}\equiv p_k=q\equiv 0\pmod q$. Ainsi $q$ divise le nombre premier $p_{k+T}$, d’où $p_{k+T}=q=p_k$, ce qui contredit la stricte croissance de $(p_n)$. $\square$

Remarques. La preuve n’utilise de $(p_n)$ que deux choses : chaque terme est premier, et deux termes d’indices distincts sont distincts. Elle s’applique donc à toute suite injective de nombres premiers. L’hypothèse de caractéristique nulle est nécessaire : sur $\mathbb F_2$, la suite $(0,1,1,1,\dots)$ vérifie $u_{n+2}=u_{n+1}$.