Course de nombres premiers de Chebyshev

On sait depuis Euclide qu’il y a une infinité de nombres premiers. En voici une preuve : supposons au contraire qu’il existe seulement un nombre fini de nombres premiers, disons $p_1,p_2,\ldots, p_k$. Alors, l’entier
\[ N:= p_1\cdots p_k +1 \]
n’est divisible ni par $p_1$ (car sinon $1= N- p_1\cdots p_k$ serait un multiple de $p_1$), ni par $p_2$, et ainsi de suite. L’entier $N$ n’est donc divisible par aucun nombre premier, ce qui est impossible (noter qu’on utilise le fait que tout entier $\geq 2$ admet un diviseur premier...).

Parmi cette infinité de nombres premiers, certains s’écrivent sous la forme $4n + 1$ (avec $n$ entier) comme par exemple $5, 13, 17, 29, 37, 41,...$ et les autres, $3, 7, 11, 19, 23, 31, 43,...$ sous la forme $4n + 3$ (la seule exception est $2$, l’unique nombre premier pair). Un précédent article à IDM traite très joliment de l’adaptation de cet argument à la preuve de l’infinité de l’ensemble des nombres premiers de la forme $4n+3$, et donne l’astuce supplémentaire nécessaire pour établir qu’il y a aussi une infinité de nombres premiers de la forme $4n+1$.

À la lumière de ce résultat, Chebyshev s’est posé la question suivante : est-ce que les nombres premiers d’une de ces formes, $4n+1$ ou $4n+3$, sont plus rares que ceux de l’autre forme ? Il résume ses recherches dans une lettre envoyée à Fuss (un arrière-petit-fils d’Euler) en 1853 : (on pourra sauter les deux dernières phrases de cette lettre en première lecture)

En cherchant l’expression limitative des fonctions qui déterminent la totalité des nombres premiers de la forme $4n+1$ et de ceux de la forme $4n+3$, pris au-dessous d’une limite très grande, je suis parvenu à reconnaître que ces deux fonctions diffèrent notablement entre elles par leurs seconds termes, dont la valeur, pour les nombres $4n+3$, est plus grande que celle pour les nombres $4n+1$ ; ainsi, si de la totalité des nombres premiers de la forme $4n+3$, on retranche celle des nombres premiers de la forme $4n+1$, et que l’on divise ensuite cette différence par la quantité $\frac{\sqrt x}{\log x}$, on trouvera plusieurs valeurs de $x$ telles, que ce quotient s’approchera de l’unité aussi près qu’on le voudra. Cette différence dans la répartition des nombres premiers de la forme $4n+1$ et $4n+3$, se manifeste clairement dans plusieurs cas. Par exemple, à mesure que $c$ s’approche de zéro, la valeur de la série
\[ e^{-3c}-e^{-5c}+e^{-7c}+e^{-11c}-e^{-13c}-e^{-17c}+e^{-19c}+e^{-23c} +\cdots\qquad(1) \]
s’approche de $+\infty$.

Voyons si ce phénomène de biais, que Chebyshev annonce avoir découvert, est confirmé par des données numériques. On regroupe dans le tableau ci-dessous [1], pour un certain nombre de valeurs de $x$, le nombre de nombres premiers inférieurs à $x$ dans chacune des deux « équipes » étudiées par Chebyshev (l’équipe des nombres premiers de la forme $4n+1$ et l’équipe de ceux de la forme $4n+3$) :

Pour chaque ligne, on remarque que les valeurs obtenues dans les deux colonnes de droite sont proches, mais que l’équipe des nombres premiers de la forme $4n+3$ l’emporte toujours d’une courte tête dans tous nos exemples de « ligne d’arrivée » $x$. Pour une étude plus approfondie, regardons le graphe de la fonction $f(x)$ qui à $x$ associe la différence entre le nombre de nombres premiers $\leq x$ qui sont de la forme $4n+3$ et ceux de la forme $4n+1$ :

Pour l’instant ce graphe est assez erratique et ressemble un peu à une « marche aléatoire » [2].
Toutefois, il est très souvent au-dessus de l’axe des abscisses, comme l’a deviné Chebyshev. Voyons maintenant ce qui arrive si on normalise par $\sqrt x/\log x$, comme ce dernier l’a suggéré.

Ce graphe paraît beaucoup moins aléatoire. Il semble qu’il y ait beaucoup plus d’oscillations pour des petites valeurs de $x$, comme si les fluctuations étaient guidées par un mouvement global de la forme suivante :

La théorie développée par Riemann montre que la bonne chose à faire ici est de changer d’échelle : on peut utiliser une échelle logarithmique pour l’axe des $x$. En d’autres termes, plutôt que de tracer le graphe d’une fonction $g(x)$, on trace le graphe de $g(e^x)$. Si on applique cette idée à la fonction $g(x)=f(x)/(\sqrt x/\log x)$, on obtient le graphe suivant :

On voit donc apparaître un graphique qui démontre une certaine périodicité [3], et qui confirme l’existence du biais de Chebyshev pour beaucoup de valeurs de $x$. Sous certaines hypothèses (voir section suivante), on sait de nos jours démontrer que ce dernier graphe est au-dessus de l’axe des abscisses pour environ $99,59\%$ des valeurs de $x$.

Lien avec l’hypothèse de Riemann

Dirichlet a démontré en 1837 que si $a$ et $q$ sont des entiers premiers entre eux (c’est-à-dire que pgcd$(a,q)=1$), alors il existe une infinité de nombres premiers de la forme $qn+a$. Sa démonstration très astucieuse utilise des outils beaucoup plus avancés et a donné naissance aux très importantes fonctions $L$ de Dirichlet, qui généralisent la fonction zêta de Riemann (qui, elle, a été introduite par Euler). Par exemple, l’étude des nombres premiers de la forme $4n+3$ conduit à l’étude de la fonction
\[ \qquad \qquad\qquad \phantom{(1)} L(s):= \frac{1}{1^s}-\frac 1{3^s} +\frac 1{5^s} - \frac 1{7^s} +\frac 1{9^s}-\frac 1{11^s}+\cdots \qquad \qquad\qquad(2) \]
Noter que dans cette somme qui fait apparaître uniquement les entiers impairs, les signes $+1$ et $-1$ alternent.

Maintenant que nous avons vu une « démonstration numérique » de l’existence du biais de Chebyshev, on peut se demander s’il est possible d’en faire la preuve rigoureusement. Chebyshev avait déjà affirmé dans sa lettre avoir démontré que l’expression (1) tend vers l’infini lorsque $c$ tend vers $0$.
Malheureusement, la marge de cette lettre était trop petite pour inclure une démonstration des affirmations de Chebyshev [4]. C’est regrettable, car Hardy—Littlewood et Landau ont démontré que cette affirmation de Chebyshev est équivalente à une conjecture qui est maintenant considérée comme un des plus importants problèmes en mathématiques : l’hypothèse de Riemann pour la fonction $L(s)$ définie par (2). Pour énoncer correctement ce problème, notons tout d’abord que la série définissant $L(s)$ converge pour tout nombre réel $s>1$. On peut montrer qu’on a aussi convergence pour tout $s>0$ ; ceci provient du fait que l’alternance des signes $+1$ et $-1$ aide à la convergence. Par exemple, pour $s=1$ nous avons la formule classique (et néanmoins remarquable ; certains reconnaitront peut être la formule de Leibniz liée au développement en série entière de la fonction arc tangente)
\[ L(1)= 1-\frac 1{3} +\frac 15- \frac 19+\dots = \frac \pi 4. \]
Riemann a eu l’idée d’étudier $L(s)$ pour des valeurs complexes de $s$, ce qui lui a permis de découvrir une formule révolutionnaire (dite formule explicite) pour compter les nombres premiers inférieurs à une valeur $x$ donnée. On peut montrer que la fonction donnée par (2) est définie [5] pour tout nombre complexe $s$ dont la partie réelle $\Re(s)$ est strictement positive. L’hypothèse de Riemann (généralisée) affirme que tous les zéros [6] de $L(s)$ dans le demi-plan $\{s\in\mathbb{C} \colon\Re(s)>0\}$ sont situés sur la droite $\Re(s)=\frac 12$. Cette hypothèse est équivalente à l’affirmation de Chebyshev sur l’expression (1), et elle justifie son choix de normalisation $\sqrt x/\log x$. Preuve que les découvertes mathématiques ne suivent pas toujours un ordre chronologique, l’hypothèse de Riemann a été formulée en 1859, six ans après la lettre de Chebyshev.

Revenons au dernier graphe de la précédente section. Nous avons vu qu’après une normalisation par $\sqrt x/\log x$ et en utilisant une échelle logarithmique pour l’axe des $x$, une certaine périodicité apparaît. En réalité, la grande oscillation qu’on observe est expliquée par la formule explicite de Riemann, et on peut calculer la fréquence de cette oscillation : elle est d’environ $6.0209$. On a aussi une oscillation secondaire de fréquence environ $10.2437$, une tertiaire de fréquence environ $ 12.9880 $, et ainsi de suite. Ces fréquences correspondent aux parties imaginaires des zéros les plus proches de l’axe des abscisses pour la fonction $L(s)$ ; ils sont donnés par $ \rho_{1} \approx \frac 12 + 6.0209 i $, $\rho_{-1} \approx \frac 12 - 6.0209 i$, $\rho_2\approx \frac 12+ 10.2437 i$, $\rho_{-2}\approx \frac 12- 10.2437 i $, $\rho_3 \approx \frac 12+ 12.9880 i$, $\rho_{-3} \approx \frac 12- 12.9880 i $, $\dots$ Notons que ces zéros confirment la prédiction de Riemann : leur partie réelle vaut $\frac 12$. Voici une comparaison graphique de la fonction $g(x)$ définie à la section précédente, et d’une approximation (en rouge) qui utilise tout d’abord $2$ zéros :

puis 10 zéros :

et enfin 50 zéros :

Une remarque en passant : Littlewood a démontré que la fonction représentée (en bleu) par ce graphe prend des valeurs arbitrairement grandes, ce qui n’est pas du tout clair visuellement.

Autres courses de nombres premiers

La généralisation la plus naturelle de la question de Chebyshev est l’étude d’une progression arithmétique générale. Fixons des entiers $a,b$ et $q\geq 3$ tels que pgcd$(ab,q)=1$ (jusqu’ici, on s’est concentré sur le cas $q=4$, $b=1$, $a=3$). Existe-t-il (au moins sous certaines conditions sur $a$, $b$, $q$) plus de nombres premiers $p$ de la forme $p=qn+a$ que de la forme $p=qn+b$ ? Plus précisément on peut s’intéresser aux entiers $x$ tels que parmi les nombres premiers $p$ inférieurs ou égaux à $x$, il en existe plus de la forme $p=qn+a$. Kaczorowski a démontré que la « proportion limite » de ces entiers $x$ n’existe pas, c’est-à-dire que la quantité

\[ \frac{\#\big\{1\leq x \leq X : \text{ il y a plus de } p\leq x \text{ de la forme } qn+a \text{ que de la forme } qn+b\big\}}{X} \]
n’a pas de limite quand $X\rightarrow \infty$.
Cette (absence de) propriété nous est en fait déjà suggérée par l’avant dernier graphe de la première section. (Sur le graphe en question, on note qu’il est possible de trouver d’une part des intervalles arbitrairement grands de $x$ pour lesquels la proportion de points $(x,y)$ du graphe situés au-dessus de l’axe des abscisses est majoritaire, et d’autre part des intervalles arbitrairement grands où cette proportion est minoritaire, démontrant que la limite considérée n’existe pas.) Malgré cela, Rubinstein et Sarnak ont prouvé sous certaines hypothèses (dont l’hypothèse de Riemann) qu’une « bonne » notion de proportion limite modifiée existe (c’est la forme plus régulière du dernier graphe de la section 1 qui suggère cette modification). De plus, ils ont conçu un algorithme pour le calcul explicite de ces proportions. En particulier, pour la question originale de Chebyshev, ils ont calculé que la probabilité qu’un intervalle borné d’entiers contienne plus de nombres premiers de la forme $4n+3$ que de la forme $4n+1$ est d’environ $99,59\%$ (on retrouve le pourcentage mentionné en fin de première section).

Plus généralement, Rubinstein et Sarnak ont démontré (sous ces mêmes hypothèses) qu’il y a un biais de Chebyshev en faveur des nombres premiers de la forme $qn+a$ et au détriment de ceux de la forme $qn+b$ si et seulement si $a$ est un non-résidu quadratique [7] modulo $q$ et $b$ est un résidu quadratique modulo $q$. En particulier, l’observation originale de Chebyshev s’explique par le fait qu’il n’existe pas [8] d’entier $x$ tel que $4\mid (x^2-3)$ (donc $3$ n’est pas un résidu quadratique modulo $4$) alors que, par exemple $4\mid (5^2-1)$ (autrement dit, $1$ est un résidu quadratique modulo $4$). Aussi, les mêmes travaux montrent que ce type de biais prononcé est caractéristique des petites valeurs de $q$ ; lorsque $q$ augmente, le phénomène se dissipe...

En conclusion de leur travail, Rubinstein et Sarnak suggèrent l’étude de « généralisations algébriques » de ce phénomène. Notons tout d’abord que la question originale de Chebyshev consiste à savoir s’il y a une prépondérance de nombres premiers $p$ pour lesquels il existe un entier $x$ tel que $x^2+1$ est divisible par $p$ (autrement dit une prépondérance de nombres premiers $p$ tels que $-1$ est un résidu quadratique modulo $p$). En effet, on peut montrer [9] que $-1$ est un résidu quadratique modulo $p$ si et seulement si $p$ est soit égal à $2$, soit de la forme $4n+1$.
Considérons maintenant les nombres premiers $p$ pour lesquels il existe un entier $x$ tel que $x^3-2$ est divisible par $p$ (c’est-à-dire $2$ est un résidu cubique modulo $p$). Observe-t-on un excès ou un défaut de nombres premiers de ce type par rapport à ce qui est attendu (« ce qui est attendu », ici, c’est ce que prédit un résultat de 1926, le théorème de Chebotarev, vaste généralisation du théorème des nombres premiers [10]) ?

Généraliser à ce nouveau cadre le décompte analogue à celui fait par Chebyshev est assez délicat. Donnons simplement une esquisse de la démarche. Tout d’abord, il est possible d’associer à (presque) tout nombre premier une permutation (ou plutôt un « type » de permutation) des zéros complexes de $x^3-2$. Ce polynôme ayant trois zéros complexes distincts, il peut y avoir trois « types » distincts de permutations. Précisément si $p$ est un nombre premier (qu’il faut choisir supérieur ou égal à $5$), le type de permutation associé à $p$ correspond au nombre $s_p$ d’entiers $x$ entre $0$ et $p-1$ tels que $p$ divise $x^3-2$. Illustrons chacun de ces trois types :

• si $p=31$ alors les entiers $x$ entre $0$ et $30$ tels que $31\mid x^3-2$ sont $4$, $7$, et $20$. Donc $s_{31}=3$ et on dit que « $31$ est de type (I) ».

• si $p=5$ alors le seul entier $x$ entre $0$ et $4$ tel que $5\mid x^3-2$ est $3$. Donc $s_5=1$ et on dira que « $5$ est de type (II) ».

• si $p=7$, il n’y a pas d’entier $x$ tel que $7\mid x^3-2$. Donc $s_7=0$ et on dit que « $7$ est de type (III) ».

On voit que le problème que l’on se pose est celui de la prépondérance des nombres premiers de type (I) ou (II) par rapport à ceux de type (III). Il y a une rupture d’équité ici dont il faut tenir compte : on oppose une équipe formée de deux concurrents à un concurrent seul... Il suffit [11] pour cela de multiplier par deux la contribution des nombres premiers de type (III). On est alors prêt à développer une analyse analogue à celle de Rubinstein et Sarnak (travail initié par Ng dans sa thèse, en 2000). Là encore ce sont des fonctions de nature proche de $L(s)$ (ainsi que leurs zéros !) qui recèlent entièrement tous les secrets de cette nouvelle situation. Celle-ci étant plus délicate, une seule fonction $L$ ne suffit pas à tout expliquer, il en faut deux :
\[ L_\varepsilon(s):=1-\frac1{2^s} +\frac 1{4^s} -\frac 1{5^s} + \frac 1{7^s} - \frac 1{8^s} + \frac 1{10^s} - \frac 1{11^s} + \cdots \]

\[ L_\chi(s):= 1-\frac 1{7^s} -\frac 1{13^s} - \frac 1{19^s} +\frac 1{25^s}+ \frac 2{31^s}-\frac 1{37^s}+ \cdots \]
D’où viennent ces fonctions ? Ici encore, chaque fois qu’un terme $\frac{a_p}{p^s}$ avec $p$ premier apparaît, c’est le type du nombre premier $p$ qui va déterminer la valeur de $a_p$. Dans le cas de $L_\varepsilon$, on a $a_p=1$ si $p$ est de type (I) ou (III) et $a_p=-1$ si $p$ est de type (II). Pour $L_\chi$, on a $a_p=s_p-1$ pour tout nombre premier $p\geq 5$. Pour comprendre d’où proviennent les termes $\frac{a_n}{n^s}$ quand $n$ n’est pas premier, il faut rentrer plus avant dans la théorie, ce que nous ne ferons pas ici (on se contentera d’affirmer, sans preuve, que la valeur des $a_p$, pour $p$ premier, détermine celle des $a_n$, pour tout entier $n$).

Dans sa thèse, Ng a démontré sous certaines hypothèses (en particulier l’hypothèse de Riemann, à nouveau) sur $L_\varepsilon$ et $L_\chi$ qu’il existe un biais de Chebyshev entre les nombres premiers de type (I) ou (II) et ceux de type (III). Récemment, dans ce contexte généralisé, nous sommes parvenus à mettre en lumière l’existence de biais de Chebyshev encore plus extrêmes (nous dépassons les $99,59\%$ et atteignons les $100\%$...) que celui découvert par Chebyshev et évalué précisément par Rubinstein et Sarnak. Mais contrairement à ces derniers, et de manière assez surprenante, notre preuve ne nécessite aucune hypothèse sur les fonctions $L$ intervenant (en d’autres termes, elle est inconditionnelle). Le graphique final ci-dessous, produit avec l’aide de Bill Allombert et du logiciel Pari/gp, est un analogue du dernier graphique de la section 1 et résume notre découverte [12].