Theorie des cribles

Théorie des cribles

En mathématiques, la théorie des cribles est une partie de la théorie des nombres ayant pour but d'estimer, à défaut de dénombrer, les cardinaux de sous-ensembles (éventuellement infini) de N en approchant la fonction indicatrice du sous-ensemble considéré.

Cette technique a pour origine le Crible d'Eratosthène, et dans ce cas, le but était d'étudier l'ensemble des nombres premiers.

Un des nombreux résultats que l'on doit aux cribles a été découvert par Viggo Brun en 1919. Il a permis de montrer que la somme des inverses des nombres premiers jumeaux est finie, résultat inattendu qui laisse ouverte la possibilité d'un nombre fini de nombres premiers jumeaux.

Actuellement, les cribles sont considérés comme une branche très prometteuse de la théorie des nombres.

La formule du crible

Les explications du crible d'Eratosthène faisant l'objet d'un article séparé, elles ne seront pas reprises ici. La méthode du crible d'Eratosthène débouche sur une formule attribuée à Da Silva et James Joseph Sylvester appelée formule du crible, mais très probablement beaucoup plus ancienne sous une forme ou sous une autre. Elle est liée notamment au principe d'inclusion-exclusion et à la formule de Poincaré, vue essentiellement dans le cadre ensembliste ou en probabilité, mais de manière assez lâche.

Formule du crible de Da Silva et Sylvester

Dans l'ensemble {1, 2, ..., n }, soient P1,P2,...,Pm m relations portant sur ces entiers et W(r) le nombre des entiers qui satisfont à r relations Pi.

Alors, le nombre des entiers qui ne satisfont à aucune des relations Pi est donné par la formule

$n+\sum_{k=1}^m{(-1)^k W(k)}.$

Donnons un exemple :

Le nombre des entiers plus petits que n qui ne sont pas divisibles par les m nombres a1, a2, ..., am, supposés premiers entre eux deux à deux est égal à

$n - \sum_{1\le i \le m}{\Big[\frac{n}{a_i}\Big]}+\sum_{1\le i<j \le m}{\Big[\frac{n}{a_i a_j}}\Big]+\ldots+(-1)^m\Big[\frac{n}{a_1 a_2 \ldots a_m}\Big],$

où [x] désigne la partie entière de x.

formule du crible de Legendre

On note traditionnellement π(x) le nombre de nombres premiers inférieurs ou égaux à x. Utilisant un procédé voisin de la formule du crible (qui porte ainsi le nom de crible d'Ératosthène-Legendre), Legendre trouve finalement la formule de Legendre (1808)

$\pi(x)-\pi(\sqrt{x})=-1+\sum_{d}{\mu(d)\Big[{x \over d}\Big]},$

où la somme est étendue à tous les diviseurs d du produit $p_1p_2\ldots p_n\,$, $p_1,\ldots ,p_n\,$ désignant les nombres premiers inférieurs ou égaux à $\sqrt{x}$. $\mu(k)\,$ est la fonction de Möbius. Elle vaut $0\,$ si $k\,$ est divisible par le carré d'un entier, et $(-1)^r\,$ si $k\,$ s'écrit comme le produit de $r\,$ nombres premiers distincts.

Legendre déduisit de sa méthode ce premier résultat, nouveau depuis l'antiquité, sur la répartition des nombres premiers

$\lim_{x \rightarrow \infty}{\frac{\pi(x)}{x}}=0$

en montrant que

$\pi(x) \le \frac{x}{\ln \ln x}.$

Donc la proportion des nombres premiers tend vers $0\,$. On retrouve ainsi cette impression naturelle que les nombres premiers sont de plus en plus rares à mesure qu'on va plus loin dans la liste. Ce théorème est appelé théorème de raréfaction des nombres premiers.

La formule du crible se généralise en un procédé systématique appelé méthode du crible et inauguré par Viggo Brun qui démontra ainsi contre toute attente, le théorème de Brun (1919, « La série des inverses des nombres premiers jumeaux est convergente. »)

Depuis, la méthode du crible de Brun a été améliorée (crible de Selberg, entre autres).

Voir aussi

• Crible d'Eratosthène
• Crible de Legendre
• Crible de Brun

Bibliographie

• An introduction to Sieve Methods and their applications, Alina Carmen Cojocaru & M. Ram Murty
• H. Halberstam and H. E. Richert. (1974). Sieve Methods. Academic Press, London, 1974.

Ce document provient de « Th%C3%A9orie des cribles ».