Voir la source de Fonction de compte des nombres premiers

En [[mathématiques]], la '''fonction de compte des nombres premiers''' est la fonction comptant le nombre de [[nombre premier|nombres premiers]] inférieurs ou égaux à un [[nombre réel]] {{mvar|x}}<ref>{{Chapitre|prénom=Jean-Benoît|nom=Bost|titre=Le théorème des nombres premiers et la transformation de Fourier|url=https://books.google.fr/books?id=CfBLG2zPfdgC&pg=PA1|passage=1|auteurs ouvrage=Jean-Benoît Bost, [[Pierre Colmez]] et [[Philippe Biane]]|titre ouvrage=La fonction Zêta|lieu=Paris|éditeur=Éditions de l'École polytechnique|année=2002|isbn=978-2-7302-1011-9}}.</ref>. Elle est notée {{math|π(''x'')}} (à ne pas confondre avec la [[Pi|constante {{math|π}}]]).

L’image ci-contre illustre la fonction {{math|π(''n'')}} pour les valeurs [[Entier naturel|entières]] de la variable. Elle met en évidence les augmentations de 1 que la fonction subit à chaque fois que {{mvar|x}} est égal à un nombre premier.
[[Image:PrimePi.PNG|upright=1.3|thumb|right|Les 60 premières valeurs de {{math|π(''n'')}}]]

== Définition ==
Soit <math>\mathbb{P}</math> l'ensemble des nombres premiers et <math>x</math> un nombre réel. Alors la '''fonction de comptant des nombres premiers''' inférieurs ou égaux à <math>x</math> est définie comme
: <math>\pi (x) := \left |  \{p \in \mathbb{P} \mid p \le x\} \right |.</math>

== Historique ==
{{Voir|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 {{s-|XVIII}}, [[Carl Friedrich Gauss|Gauss]]<ref>C'est en 1849, soit plus de 40 ans après la publication de Legendre, que Gauss indique, dans une correspondance avec [[Franz Johann Encke|Encke]], qu'il a conjecturé en 1792 ou 1793 — donc vers l'âge de 15 ans — que {{math|π(''x'')}} est approximativement égal à {{math|''x''/ln(''x'')}}. {{Ouvrage |langue=en |prénom1=Julian |nom1=Havil |titre=Gamma |sous-titre=Exploring Euler's Constant |éditeur=[[Princeton University Press|PUP]] |année=2010 |pages totales=296 |passage=174-176 |isbn=978-1-4008-3253-8 |lire en ligne=https://books.google.fr/books?id=7-sDtIy8MNIC&pg=PA174}}.</ref> et [[Adrien-Marie Legendre|Legendre]]<ref>A.M. Legendre, ''Essai sur la théorie des nombres'', {{2e}} éd., Paris, Courcier, 1808, {{p.|394}}.</ref> ont [[Conjecture|conjecturé]] que cette quantité était « proche de » {{math|''x''/ln(''x'')}}, où {{math|ln}} est la fonction [[logarithme népérien]].

Plus précisément,

<center>
{| border=1 cellpadding=10 style="border-collapse:collapse"
|-----
| bgcolor="#fff8ff" |<math>\lim_{x\rightarrow +\infty}\frac{\pi(x)}{x/\ln(x)}=1</math>
|}</center>

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

<center><math>\lim_{x\rightarrow +\infty}\frac{\pi(x)}{{\rm li}(x)}=1,</math></center>

où la fonction [[logarithme intégral]] <math>{\rm li}(x)=\int_{0}^{x} \frac{\mathrm dt}{\ln(t)}</math> est en fait une [[Théorie de l'approximation|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  {{math|π(''x'')}} ==

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

Une manière plus élaborée pour trouver  {{math|π(''x'')}} a été inventée par Legendre : étant donné un entier {{math|''x''}}, si {{math|''p''{{ind|1}}, ''p''{{ind|2}},…,''p{{ind|l}}''}} sont des nombres premiers distincts, alors le nombre d'entiers inférieurs ou égaux à {{math|''x''}} qui ne sont divisibles par aucun {{mvar|p{{ind|i}}}} est

:<math> x - \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</math>, où <math>\lfloor\cdot\rfloor</math> désigne la fonction [[Partie entière et partie fractionnaire|partie entière]] (cette formule est une application du [[Principe d'inclusion-exclusion|principe d’inclusion-exclusion]]).<br />

Ce nombre est donc égal à :<math>\pi(x)-\pi\left(\sqrt{x}\right)+1\,</math>
où les nombres {{math|''p''{{ind|1}}, ''p''{{ind|2}},…,''p{{ind|l}}''}} sont les nombres premiers inférieurs ou égaux à la [[racine carrée]] de {{math|''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 {{math|π(''x'')}}. Soit {{math|''p''{{ind|1}}, ''p''{{ind|2}},…,''p{{ind|n}}''}} les premiers ''n ''nombres premiers et notons par {{math|Φ(''m'',''n'')}} le nombre de nombres naturels inférieurs à ''m'' qui ne sont divisibles par aucun <math>p_i\,</math>. Alors

:<math>\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\left[\frac{m}{p_n}\right],n-1\right),\,</math>

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

:<math>\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).\,</math>

En utilisant cette approche, Meissel calcula  {{math|π(''x'')}}, pour ''x ''égal à 5×10<sup>5</sup>, 10<sup>6</sup>, 10<sup>7</sup> et 10<sup>8</sup>.

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'', ''P{{ind|k}}''(''m'', ''n'') comme le nombre de nombres inférieurs à ''m'' avec exactement ''k'' facteurs premiers, tous plus grands que ''p{{ind|n}}''. De plus, fixons ''P''{{ind|0}}(''m'', ''n'') = 1. Alors

:<math>\Phi(m,n)=\sum_{k=0}^{+\infty}P_k(m,n),\,</math>

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

:<math>\pi(m)=\Phi(m,n)+n-1-P_2(m,n)\,</math>.

Le calcul de ''P''{{ind|2}}(''m'', ''n'') peut être obtenu de cette manière :

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

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

# <math>\Phi(m,0)=\lfloor m\rfloor;\,</math>
# <math>\Phi(m,b)=\Phi(m,b-1)-\Phi\left(\frac m{p_b},b-1\right).\,</math>

En utilisant cette méthode et un [[IBM 701]], Lehmer a été capable de calculer {{math|π}}(10{{10}}).
Cette méthode a ensuite été améliorée par Lagarias, Miller, Odlyzko, Deléglise, et Rivat<ref name="pix_comp">{{article|auteur1 = Deléglise, Marc |auteur2 = Rivat, Joel |date=January 1996 |titre=Computing {{math|''π''(''x'')}}: The Meissel, Lehmer, Lagarias, Miller, Odlyzko method  |journal=Mathematics of Computation |volume=65 |numéro=213 |pages=235–245 |doi = 10.1090/S0025-5718-96-00674-6 |accès doi=libre |url=https://www.ams.org/mcom/1996-65-213/S0025-5718-96-00674-6/S0025-5718-96-00674-6.pdf }}</ref>.

Des résultats plus délicats de [[théorie analytique des nombres]], et l'utilisation de machines de plus en plus puissantes, ont permis en 2010 le calcul exact de {{math|π(10{{24}})}} (en admettant l'[[hypothèse de Riemann]])<ref name=conditionalcalculationofpi>{{en}} [http://primes.utm.edu/notes/pi(10%5E24).html primes.utm.edu] Conditional Calculation of pi(10^24).</ref>.

== Autres fonctions de compte des nombres premiers ==

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 {{math|Π(''x'')}} ou {{math|''J''(''x'')}}. Celle-ci possède des sauts de 1/''n'' pour les puissances de nombres premiers ''p''<sup>''n''</sup>, 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

:<math>J(x) = \frac12 \left(\sum_{p^n < x} \frac1n\ + \sum_{p^n \le x} \frac1n\right)</math>

où ''p'' est un nombre premier.

Nous pouvons aussi écrire

:<math>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</math>
où {{math|Λ}} est la [[fonction de von Mangoldt]] et

{{retrait|<math>\pi_0(x)=\lim_{\varepsilon\to0}\frac{\pi(x-\varepsilon)+\pi(x+\varepsilon)}2</math>}}

et ainsi (par [[Formule d'inversion de Möbius|inversion de Möbius]]),

{{Retrait|<math>\pi_0(x)=\sum_{n=1}^\infty \frac{\mu(n)J(x^{1/n})}n</math>.}}

En connaissant la relation entre le logarithme de la fonction zeta de Riemann et la fonction {{math|Λ}}, et la [[formule de Perron]], nous avons pour {{math|Re(s)>1}}:

:<math> \ln( \zeta (s))=s\int_0^{\infty}J(x) x^{-s-1}~{\rm d}x </math> 

La fonction de [[Pafnouti Tchebychev|Tchebychev]] pondère les nombres premiers ou les puissances de nombres premiers {{mvar|p{{exp|n}}}} par {{math|ln ''p''}} :

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

== Inégalités ==
Ci-dessous se trouvent quelques inégalités pour {{math|π(''x'')}}.

Pour tout réel {{math|''x'' ≥ 17}} (et tout entier {{math|''x'' ≥ 11}}), et même pour {{math|''x'' > 1}} en ce qui concerne la majoration
:<math>
\frac{x}{\ln x}< \pi(x) < 1,25506\  \frac {x} {\ln x}
</math><ref>Plus précisément, la fonction {{math|π(''x'')ln(''x'')/''x''}} (qui tend vers 1 quand {{math|''x''}} tend vers l'infini) est strictement supérieure à 1 à partir de {{math|''x''}} = 17 et atteint son [[maximum]] pour {{math|''x''}} = 113 : {{article |lien auteur = John Barkley Rosser | nom = Rosser | prénom = J. Barkley | nom2 = Schoenfeld | prénom2 = Lowell | titre = Approximate formulas for some functions of prime numbers | journal = Illinois J. Math. | année = 1962 | volume = 6 | pages = 64–94 | zbl = 0122.05001 | issn = 0019-2082 | url=https://projecteuclid.org/euclid.ijm/1255631807 }} {{p.|69}} et {{OEIS|id=A209883}}.</ref>.
Pour {{math| ''x'' ≥ 67}}, et même pour {{math|''x'' > e<sup>3/2</sup>}} en ce qui concerne la majoration
:<math>\frac {x} {\ln x - {1\over 2}} < \pi(x) <  \frac {x} {\ln x - {3\over 2}}
</math><ref>{{harvsp|Rosser|Schoenfeld|1962|p=69}}, qui précise entre autres des résultats analogues de 
{{Article|langue=en|lien auteur=Barkley Rosser|prénom=Barkley|nom=Rosser|titre=Explicit bounds for some functions of prime numbers|lien périodique=American Journal of Mathematics|revue=Amer. J. Math|volume=63|année=1941|pages=211-232|url=http://www.ams.org/mathscinet-getitem?mr=2:150e}}.</ref>.

D'autres inégalités fournissent des [[Théorème des nombres premiers#Approximations du n-ième nombre premier|approximations du ''n''-ième nombre premier]].

== L'hypothèse de Riemann ==

L'[[hypothèse de Riemann]] équivaut à une majoration beaucoup plus serrée de l'erreur dans l'approximation de {{math|π(''x'')}}, donc à une distribution plus régulière des nombres premiers :
<center><math>\pi(x)={\rm li}(x)+O\left(\sqrt{x} \ln(x)\right).</math></center>

== Formules pour les fonctions de compte des nombres premiers ==

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 [[Hans Carl Friedrich von Mangoldt|von Mangoldt]], et sont généralement connues comme {{Lien|fr=Formule explicite pour les fonctions L|lang=en|trad=Explicit formulae for L-functions|texte=formules explicites pour les fonctions L}}.

Nous avons l'expression suivante pour
{{retrait|<math>\psi_0(x)=\lim_{\varepsilon\to0}\frac{\psi(x-\varepsilon)+\psi(x+\varepsilon)}{2}~:</math>}}
:<math>\psi_0(x)=x-\sum_\rho \frac{x^\rho}{\rho}-\ln2\pi-\frac12\ln(1-x^{-2}).</math>
Ici, les {{math|ρ}} sont les zéros de la [[fonction zêta de Riemann]] dans la bande critique, où la [[partie réelle]] de {{math|ρ}} est comprise entre 0 et 1. La formule est valide pour les valeurs de {{math|''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 :
:<math>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}.</math>
De nouveau, la formule est valide pour {{math|''x''}} > 1, et {{math|ρ}} représente les zéros non triviaux de la fonction zêta ordonnés en accord avec leurs valeurs absolues. Le premier terme {{math|li(''x'')}} est le logarithme intégral habituel ; néanmoins, il est moins facile de décrire ce que représente {{math|li}} dans les autres termes. La meilleure manière de concevoir cela est de considérer l'expression {{math|li(''x''{{exp|ρ}})}} comme une abréviation de {{math|Ei(ρ ln(''x''))}}, où {{math|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 ==
{{Traduction/Référence|en|Prime-counting function|556132600|type=note}}
=== Notes ===
{{Références}}
=== Références ===
* {{Merveilleux nombres premiers}}
* {{Ouvrage |langue=en |nom1={{Lien|Eric Bach}} |prénom2=Jeffrey |nom2=Shallit |lien auteur2=Jeffrey Shallit |titre=Algorithmic number theory |sous-titre=efficient algorithms |volume=1 |éditeur=MIT Press |lieu=Cambridge, Mass |année=1996 |pages totales=512 |passage=234 |isbn=0-262-02405-5 |numéro chapitre=8.8}}
* {{Ouvrage |langue=en |prénom1=Leonard |nom1=Dickson |lien auteur1=Leonard Eugene Dickson |titre=History of the theory of numbers |volume=1 |titre volume=Divisibility and Primality |éditeur=Dover publications |lieu=Mineola |année=2005 |isbn=0-486-44232-2}}

== Articles connexes ==
* ''[[Sur le nombre de nombres premiers inférieurs à une taille donnée]]''
* [[Fonction R de Riemann]]
* [[Écart entre nombres premiers]]
* [[Conjecture de Brocard]]
* [[Nombre de Skewes]]

== Lien externe ==
* Voir la {{OEIS|id=A000720}}

{{Palette|Classes de nombres premiers}}
{{Portail|analyse|théorie des nombres}}

[[Catégorie:Théorie analytique des nombres]]
[[Catégorie:Fonction remarquable|Compte des nombres premiers]]