Fonction de compte des nombres premiers

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, la fonction de compte des nombres premiers est la fonction comptant le nombre de nombres premiers inférieurs ou égaux à un nombre réel x[1]. Elle est notée π(x) (à ne pas confondre avec la constante π).

L’image ci-contre illustre la fonction π(n) pour les valeurs entières de la variable. Elle met en évidence les sauts (d’amplitude égale à +1) que la fonction subit lorsque x est égal à un nombre premier.

Les 60 premières valeurs de π(n)

Historique[modifier | modifier le code]

Article détaillé : Théorème des nombres premiers.

Depuis Euclide, il est connu qu'il existe des nombres premiers en quantité infinie. Pour affiner la connaissance de ces nombres, la théorie des nombres s'est attelée à en déterminer le taux de croissance. À la fin du XVIIIe siècle, Gauss[2] et Legendre[3] ont conjecturé que cette quantité était « proche de » x/ln(x), où ln est la fonction logarithme népérien.

Plus précisément,

\lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\ln(x)}=1

Cette affirmation constitue le théorème des nombres premiers, prouvé indépendamment par Hadamard et La Vallée Poussin, en 1896, grâce à la fonction zêta de Riemann. Une assertion équivalente est :

\lim_{x\rightarrow +\infty}\frac{\pi(x)}{{\rm li}(x)}=1,

où la fonction logarithme intégral {\rm li}(x)=\int_{0}^{x} \frac{\mathrm dt}{\ln(t)} est en fait une approximation plus précise.

Des preuves du théorème des nombres premiers n'utilisant pas l'analyse complexe furent proposées en 1948 par Atle Selberg et Paul Erdős.

Algorithmes d'évaluation de π(x)[modifier | modifier le code]

Une façon simple de calculer π(x), si x est un nombre petit, est d'utiliser le crible d'Ératosthène de manière à trouver tous les premiers inférieurs à x et ensuite de les compter.

Une manière plus élaborée pour trouver π(x) a été inventée par Legendre : étant donné x, si p_1\,p_2\,, …, p_k\, sont des nombres premiers distincts, alors le nombre d'entiers inférieurs ou égaux à x qui ne sont divisibles par aucun p_i\, est

\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i<j}\left\lfloor\frac{x}{p_ip_j}\right\rfloor - \sum_{i<j<k}\left\lfloor\frac{x}{p_ip_jp_k}\right\rfloor + \cdots, (où \lfloor\cdot\rfloor désigne la fonction Partie entière).

Ce nombre est donc égal à :\pi(x)-\pi\left(\sqrt{x}\right)+1\, où les nombres p_1\,p_2\,, …, p_k\, sont les nombres premiers inférieurs ou égaux à la racine carrée de x.

Dans une série d'articles publiés entre 1870 et 1885, Ernst Meissel décrivit (et utilisa) une manière combinatoire pratique pour évaluer π(x). Soit p_1\,p_2\,, …, p_n\, les premiers n nombres premiers et notons par \Phi(m,n)\, le nombre de nombres naturels inférieurs à m qui ne sont divisibles par aucun p_i\,. Alors

\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right),\,

Soit un nombre naturel donné m, si n=\pi\left(\sqrt[3]{m}\right)\, et si \mu=\pi\left(\sqrt{m}\right)-n\,, alors

\pi(m)=\Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu}{2}-1-\sum_{k=1}^\mu\pi\left(\frac{m}{p_{n+k}}\right).\,

En utilisant cette approche, Meissel calcula π(x), pour x égal à 5×105, 106, 107 et 108.

En 1959, Derrick Lehmer étendit et simplifia la méthode de Meissel. Définissons, pour un réel m et pour des nombres naturels n et k, Pk(m, n) comme le nombre de nombres inférieurs à m avec exactement k facteurs premiers, tous plus grands que pn. De plus, fixons P0(m, n) = 1. Alors

\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n),\,

où la somme actuelle possède seulement de manière finie plusieurs termes différents de zéro. Soit y désignant un entier tel que \sqrt[3]{m}\le y\le\sqrt{m}\,, et fixons n = π(y). Alors P_1(m,n)=\pi(m)-n\, et P_k(m,n)=0\, lorsque k ≥ 3. Par conséquent

\pi(m)=\Phi(m,n)+n-1-P_2(m,n)\,.

Le calcul de P2(m, n) peut être obtenu de cette manière :

P_2(m,n)=\sum_{y<p\le\sqrt{m}}\left(\pi\left(\frac mp\right)-\pi(p)+1\right).\,

D'un autre côté, le calcul de \Phi(m,n) peut être fait en utilisant les règles suivantes :

  1. \Phi(m,0)=\lfloor m\rfloor;\,
  2. \Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right).\,

En utilisant cette méthode et un IBM 701, Lehmer a été capable de calculer π(1010).

Autres fonctions de compte des nombres premiers[modifier | modifier le code]

D'autres fonctions de compte des nombres premiers sont aussi utilisées car elles sont plus pratiques pour travailler. Une d'elles est la fonction de compte des nombres premiers de Riemann, notée \Pi(x)\, ou J(x)\,. Celle-ci possède des sauts de 1/n pour les puissances de nombres premiers pn, qui prennent une valeur à mi-chemin entre les deux côtés des discontinuités. Elle peut être aussi définie par une transformation de Mellin inverse. Formellement, nous pouvons définir J par

J(x) = \frac12 \bigg(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\bigg)

p est un nombre premier.

Nous pouvons aussi écrire

J(x)=\sum_2^x\frac{\Lambda(n)}{\ln(n)}-\frac{\Lambda(x)}{2\ln(x)}=\sum_{n=1}^\infty \frac{\pi_0(x^{1/n})}n

Λ est la fonction de von Mangoldt et

\pi_0(x)=\lim_{\varepsilon\to0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2

et ainsi (par inversion de Möbius),

\pi_0(x)=\sum_{n=1}^\infty \frac{\mu(n)J(x^{1/n})}n.

En connaissant la relation entre la fonction log de la fonction Riemann et la fonction Λ, et la formule de Perron, nous avons :

 \ln( \zeta (s))=s\int_0^{\infty}J(x) x^{-s+1}~{\rm d}x

La fonction de Tchebychev pondère les nombres premiers ou les puissances de nombres premiers p^n par \ln p :

\theta(x)=\sum_{p\le x}\ln p,
\psi(x) =\sum_{p^n \le x} \ln p=\sum_{n=1}^\infty\theta(x^{1/n})=\sum_{n\le x}\Lambda(n).

Inégalités[modifier | modifier le code]

Ci-dessous se trouvent quelques inégalités pour π(x).

\forall x>1,\quad 
\pi(x) < 1,25506\  \frac {x} {\ln x}
[4].
 \forall x\ge55,\quad
\frac {x} {\ln x + 2} < \pi(x) <  \frac {x} {\ln x - 4}
[5].

D'autres inégalités fournissent des approximations du n-ième nombre premier.

L'hypothèse de Riemann[modifier | modifier le code]

L'hypothèse de Riemann équivaut à une majoration beaucoup plus serrée de l'erreur dans l'approximation de π(x), donc à une distribution plus régulière des nombres premiers :

\pi(x)={\rm li}(x)+O\left(\sqrt{x} \ln(x)\right).

Formules pour les fonctions de compte des nombres premiers[modifier | modifier le code]

Celles-ci sont de deux sortes, les formules arithmétiques et les formules analytiques. Ces dernières sont celles qui nous permettent de prouver le théorème des nombres premiers. Elles proviennent des travaux de Riemann et de von Mangoldt, et sont généralement connues comme formules explicites pour les fonctions L (en).

Nous avons l'expression suivante pour \psi_0(x)=\lim_{\varepsilon\to0}\frac{\psi(x-\varepsilon)+\psi(x+\varepsilon)}{2}~:

\psi_0(x)=x-\sum_\rho \frac{x^\rho}{\rho}-\ln2\pi-\frac12\ln(1-x^{-2}).

Ici, les ρ sont les zéros de la fonction zêta de Riemann dans la bande critique, où la partie réelle de ρ est comprise entre 0 et 1. La formule est valide pour les valeurs de x plus grandes que 1, qui est la région qui nous intéresse, et la somme des racines est convergente sous conditions, et devrait être prise en ordre croissant des valeurs absolues des parties imaginaires.

Pour J, nous avons une formule plus compliquée :

J(x) = \operatorname{li}(x) - \sum_{\rho}\operatorname{li}(x^{\rho}) - \ln 2 + \int_x^\infty \frac{{\rm d}t}{t(t^2-1) \ln t}.

De nouveau, la formule est valide pour x > 1, et ρ représente les zéros non triviaux de la fonction zêta ordonnés en accord avec leurs valeurs absolues. Le premier terme li(x) est le logarithme intégral habituel ; néanmoins, il est moins facile de décrire ce que représente li dans les autres termes. La meilleure manière de concevoir cela est de considérer l'expression \operatorname{li}(x^\rho)\, comme une abréviation de \operatorname{Ei}(\rho\ln x)\,, où Ei est le prolongement analytique de la fonction exponentielle intégrale à partir des réels positifs vers le plan complexe muni d'une coupure le long des réels négatifs.

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Prime-counting function » (voir la liste des auteurs)

Notes[modifier | modifier le code]

  1. Jean-Benoît Bost, « Le théorème des nombres premiers et la transformation de Fourier », dans Jean-Benoît Bost, Pierre Colmez et Philippe Biane, La fonction Zêta, Paris, Éditions de l'École polytechnique,‎ 2002 (ISBN 978-2-7302-1011-9, lire en ligne), p. 1.
  2. C'est en 1849, soit plus de 40 ans après la publication de Legendre, que Gauss indique, dans une correspondance avec Encke, qu'il a conjecturé en 1792 ou 1793 — donc vers l'âge de 15 ans — que π(x) est approximativement égal à x/ln(x). (en) Julian Havil, Gamma: Exploring Euler's Constant, PUP,‎ 2010 (ISBN 978-1-40083253-8, lire en ligne), p. 174-176.
  3. A.M. Legendre, Essai sur la théorie des nombres, 2e éd., Paris, Courcier, 1808, p. 394.
  4. Plus précisément, la fonction π(x)ln(x)/x (qui tend vers 1 quand x tend vers l'infini) est strictement supérieure à 1 à partir de x = 17 et atteint son maximum pour x = 113 : suite A209883 de l'OEIS.
  5. (en) Barkley Rosser, « Explicit bounds for some functions of prime numbers », Amer. J. Math, vol. 63,‎ 1941, p. 211-232 (lire en ligne).

Références[modifier | modifier le code]

Articles connexes[modifier | modifier le code]