La fonction qui compte les premiers

Le paragraphe 7.3 du cours raconte l’essentiel : un adolescent de quinze ans, un recueil de tables de logarithmes, et une ligne écrite au dos d’une page. Les Coulisses n°6 ont montré ce que disait vraiment la lettre de 1849 et pourquoi l’aire vaut mieux que la formule.

La sortie du numéro promettait la table complète du duel. La voici, recalculée d’un bout à l’autre, avec un troisième concurrent que ni le cours ni les Coulisses n’ont mentionné.

La ligne au dos de la page

En 1792 ou 1793, le jeune Gauss reçoit en cadeau un recueil de tables de logarithmes, complété des suppléments de Lambert qui donnent les facteurs des entiers jusqu’à cent deux mille. Il fait ce que font les adolescents obsessionnels : il compte. Par tranches de mille, il dénombre les nombres premiers, et il note au dos d’une page, en un mélange d’allemand et de latin dont la brutalité fait tout le charme :

Primzahlen unter $a$ $(= \infty)$ $\dfrac{a}{\ln a}$

Traduisons : les nombres premiers au-dessous de $a$, quand $a$ tend vers l’infini, sont au nombre de $\frac{a}{\ln a}$. Autrement dit : autour d’un entier $n$, la densité des nombres premiers vaut à peu près $\frac{1}{\ln n}$. Il a quinze ans. Il ne publie rien, ni cette année-là, ni les cinquante-sept années suivantes.

Ce n’est qu’en décembre 1849, répondant à une lettre de l’astronome Encke qui l’entretenait de la raréfaction des premiers, que Gauss raconte le souvenir. Et il y ajoute la précision qui change tout, et que les Coulisses ont détaillée : si la densité vaut $\frac{1}{\ln t}$ en chaque point $t$, alors le bon compte n’est pas la densité du bord appliquée à tout l’intervalle, c’est la densité accumulée, l’aire sous la courbe de $t \longmapsto \frac{1}{\ln t}$, que l’on note $\mathrm{li}(x)$. Une précision de convention : les valeurs de cette page suivent l’usage moderne, qui compte l’aire depuis l’origine, en valeur principale ; l’aire comptée depuis $2$, celle des Coulisses, en diffère d’une constante minuscule, $\mathrm{li}(2) \approx 1{,}045$, invisible à l’échelle du milliard.

Legendre, le rival qui publiait

Pendant que Gauss se tait, un autre cherche la même chose et le dit tout haut.

Adrien-Marie Legendre publie en 1797-98 son Essai sur la théorie des nombres, où il propose une formule pour compter les premiers, et il l’affine dans la deuxième édition, en 1808 :

$\pi(x) \approx \frac{x}{\ln x - 1{,}083\,66}.$

Ce nombre $1{,}083\,66$ n’est pas tombé du ciel : Legendre l’a ajusté sur les tables dont il disposait, c’est-à-dire sur des entiers ne dépassant guère le million. C’est une constante de calage, choisie pour coller aux données observées.

Et elle colle remarquablement. Regardez la colonne « Legendre » ci-dessous : à $10^{4}$, sa formule se trompe de une unité et demie sur mille deux cent vingt-neuf. Aucun des deux autres concurrents n’approche cette précision. Puis, à mesure que $x$ grandit, elle décroche : à $10^{9}$, elle est en retard de soixante-dix mille, quand l’aire de Gauss n’en manque que mille sept cents. On sait aujourd’hui pourquoi : la bonne constante, celle qui rend la formule asymptotiquement exacte, vaut $1$ et non $1{,}083\,66$. Legendre avait ajusté son modèle sur un échantillon trop court, et il avait ajusté trop bien.

C’est un piège que les données n’ont jamais cessé de tendre : une formule qui épouse parfaitement ce que l’on a mesuré n’est pas pour autant celle qui décrit ce que l’on n’a pas encore mesuré.

La table complète

Toutes les valeurs ci-dessous ont été recalculées : $\pi(x)$ est exact (obtenu par crible pour les petites valeurs et par comptage certifié pour $10^{9}$), les trois approximations, dont celle de Legendre, $x/(\ln x - 1{,}083\,66)$, sont évaluées en arithmétique à trente chiffres significatifs et arrondies.

$x$	$\pi(x)$	$x/\ln x$	Legendre	$\mathrm{li}(x)$
$10^{2}$	$25$	$21{,}7$	$28{,}4$	$30{,}1$
$10^{4}$	$1\,229$	$1\,085{,}7$	$1\,230{,}5$	$1\,246{,}1$
$10^{6}$	$78\,498$	$72\,382$	$78\,543$	$78\,628$

Et à un milliard, le duel au sommet :

Estimateur	Valeur en $x = 10^{9}$
$\pi(x)$ exact	$50\,847\,534$
$x/\ln x$	$48\,254\,942$
Legendre	$50\,917\,519$
$\mathrm{li}(x)$	$50\,849\,235$

Et voici la même chose en écarts, ce qui est plus parlant.

$x$	Erreur de $\dfrac{x}{\ln x}$	Erreur de Legendre	Erreur de $\mathrm{li}(x)$
$10^{2}$	$-3{,}3$ · $13{,}1\,\%$	$+3{,}4$ · $13{,}6\,\%$	$+5{,}1$ · $20{,}5\,\%$
$10^{4}$	$-143{,}3$ · $11{,}7\,\%$	$+1{,}5$ · $0{,}12\,\%$	$+17{,}1$ · $1{,}39\,\%$
$10^{6}$	$-6\,116$ · $7{,}79\,\%$	$+45$ · $0{,}058\,\%$	$+130$ · $0{,}165\,\%$
$10^{9}$	$-2\,592\,592$ · $5{,}10\,\%$	$+69\,985$ · $0{,}138\,\%$	$+1\,701$ · $0{,}003\,35\,\%$

Trois lectures, et elles racontent trois choses différentes.

La formule du cours perd toujours, mais elle perd de moins en moins. L’erreur relative de $\frac{x}{\ln x}$ tombe de $13\,\%$ à $5\,\%$ quand $x$ passe de cent à un milliard. Elle tend vers zéro, c’est précisément l’énoncé du théorème des nombres premiers, mais elle y tend avec une lenteur décourageante : il faut aller très loin pour que le pourcentage devienne présentable.

L’aire de Gauss gagne, et elle gagne de plus en plus. Son erreur relative est divisée par plus de six mille entre $10^{2}$ et $10^{9}$. À un milliard, elle se trompe de mille sept cents sur cinquante millions : trois millièmes de pour cent. La valeur exacte est $\mathrm{li}\left(10^{9}\right) = 50\,849\,234{,}96$, que les Coulisses donnaient tronquée à l’unité et que le tableau ci-dessus arrondit. Une conjecture d’adolescent, écrite au dos d’une table imprimée, tient à cette précision-là.

Legendre gagne au milieu et perd à la fin. Sa colonne est la meilleure de $10^{4}$ à $10^{6}$, puis se fait dépasser. Le croisement se produit quelque part entre le million et le milliard, et c’est le moment où la constante de calage cesse de compenser et commence à nuire.

Une remarque d’honnêteté sur la première ligne : à $x = 10^{2}$, $\mathrm{li}(x)$ est le plus mauvais des trois. L’aire accumulée surestime largement quand l’intervalle est court, parce que la densité $\frac{1}{\ln t}$ y est encore très grande. Le théorème est asymptotique ; il ne promet rien sur les petits nombres, et il tient parole.

Le script

Le cours promettait un programme comparant $\pi(x)$ et $\frac{x}{\ln x}$. Le voici, en entier. Le crible d’Ératosthène ne demande rien de plus que des listes et des boucles.

from math import log

def crible(n):
    """est_premier[k] vaut True si et seulement si k est premier, pour k <= n."""
    est_premier = [True] * (n + 1)
    est_premier[0] = est_premier[1] = False
    d = 2
    while d * d <= n:
        if est_premier[d]:
            for m in range(d * d, n + 1, d):
                est_premier[m] = False
        d += 1
    return est_premier

N = 10**7
tamis = crible(N)

compte = 0
seuils = [10**k for k in range(2, 8)]
prochain = 0
for k in range(2, N + 1):
    if tamis[k]:
        compte += 1
    if prochain < len(seuils) and k == seuils[prochain]:
        x = float(k)
        print(f"10^{prochain+2}  pi = {compte:>9}   x/ln x = {x/log(x):>12.0f}"
              f"   rapport = {compte/(x/log(x)):.4f}")
        prochain += 1

Le programme met quelques secondes et affiche :

10^2  pi =        25   x/ln x =           22   rapport = 1.1513
10^3  pi =       168   x/ln x =          145   rapport = 1.1605
10^4  pi =      1229   x/ln x =         1086   rapport = 1.1320
10^5  pi =      9592   x/ln x =         8686   rapport = 1.1043
10^6  pi =     78498   x/ln x =        72382   rapport = 1.0845
10^7  pi =    664579   x/ln x =       620421   rapport = 1.0712

C’est la dernière colonne qu’il faut lire, et lentement. Le rapport $\pi(x) \big/ \frac{x}{\ln x}$ descend : $1{,}15$ ; $1{,}16$ ; $1{,}13$ ; $1{,}10$ ; $1{,}08$ ; $1{,}07$. Le théorème des nombres premiers affirme exactement que cette suite tend vers $1$. Vous la voyez descendre sous vos yeux, sur une machine de bureau, en quelques secondes, et vous n’avez utilisé aucun outil au-delà du programme de terminale.

Remarquez au passage la deuxième ligne : le rapport remonte entre $10^{2}$ et $10^{3}$. La convergence n’est pas monotone au début, et c’est un rappel utile : une suite qui converge n’a aucune obligation d’être sage sur ses premiers termes.

1896 : la démonstration, et ce que ln dit vraiment

La conjecture du dos de table a attendu cent quatre ans. Elle est démontrée en 1896, indépendamment et à quelques mois d’intervalle, par le Français Jacques Hadamard et le Belge Charles-Jean de La Vallée Poussin. La route qu’ils empruntent passe par un mémoire de Riemann de 1859, une dizaine de pages qui relient les nombres premiers aux zéros d’une fonction de variable complexe, et dont une hypothèse, toujours ouverte aujourd’hui et mise à prix un million de dollars, dirait précisément à quel point $\mathrm{li}(x)$ approche bien $\pi(x)$.

Retenez surtout ce que la densité signifie, parce que c’est la phrase la plus concrète de toute cette histoire. Si les nombres premiers autour de $n$ ont une densité de $\frac{1}{\ln n}$, alors deux premiers consécutifs sont séparés, en moyenne, de $\ln n$. Autour d’un milliard, cela fait

$\ln\left(10^{9}\right) = 9 \ln 10 \approx 20{,}7.$

Vingt et un entiers, en moyenne, entre deux nombres premiers voisins d’un milliard. Contre environ $\ln(100) \approx 4{,}6$ autour de cent. Les premiers ne s’arrêtent jamais, Euclide l’a prouvé il y a vingt-trois siècles, mais ils s’espacent, et c’est le logarithme qui donne la cadence.

Une fonction inventée en 1614 pour faire gagner du temps aux astronomes gouverne la répartition des briques élémentaires de la multiplication. Peu d’outils ont connu pareille promotion.

Sources

• Cours F3, paragraphe 7.3 ; Coulisses n°6, pièce 52 La note au dos de la table, dont cette page fournit la table complète promise en sortie de numéro.
• Lettre de Gauss à Johann Franz Encke, 24 décembre 1849, où il rapporte le souvenir de 1792-93 et propose $\mathrm{li}(x)$.
• Adrien-Marie Legendre, Essai sur la théorie des nombres, Paris, 1797-98, et deuxième édition, 1808, pour la constante $1{,}083\,66$.
• Jacques Hadamard et Charles-Jean de La Vallée Poussin, démonstrations indépendantes du théorème des nombres premiers, 1896 ; Bernhard Riemann, Über die Anzahl der Primzahlen unter einer gegebenen Grösse, 1859.
• Toutes les valeurs de cette page ont été recalculées : $\pi(x)$ par crible et par comptage exact, $\mathrm{li}(x)$ par quadrature, en arithmétique à trente chiffres significatifs. Le script ci-dessus reproduit les six premières lignes du tableau des rapports.