title: Crible de Selberg
text: # Crible de Selberg
  
  En mathématiques, et plus précisément en théorie des nombres, le crible de Selberg est une technique permettant d'estimer la taille des "ensembles criblés" d'entiers positifs qui satisfont à un ensemble de conditions qui sont exprimées par des congruences. Il a été développé par Atle Selberg dans les années 1940.
  
  ## Description
  
  En termes de théorie des cribles, le crible de Selberg est de type combinatoire : c'est-à-dire qu'il découle d'une utilisation subtile du principe d'inclusion-exclusion . Selberg a remplacé les valeurs de la fonction de Möbius en un système de poids qui sont ensuite optimisés pour s'adapter au problème donné. Le résultat donne une limite supérieure pour la taille de l'ensemble.
  
  Soit A un ensemble d'entiers positifs ≤ x et P un ensemble de nombres premiers. Soit $A_d$ l'ensemble des éléments de A divisible par d lorsque d est un produit de nombres premiers distincts de P. De plus, soit $A_1$ désignant A lui-même. Soient z un nombre réel positif et P(z) représentant le produit des nombres premiers de P étant ≤ z. L'objet du crible est d'estimer
  
      $S(A,P,z)=\left\vert A\setminus \bigcup _{p\mid P(z)}A_{p}\right\vert .$
  
  Nous supposons que |A $_d|$ peut être estimé par
  
      $\left\vert A_{d}\right\vert ={\frac {1}{f(d)}}X+R_{d}.$
  
  où f est une fonction multiplicative et X = |A|. Soit la fonction g obtenue à partir de f par inversion de Möbius, c'est-à-dire
  
      $g(n)=\sum _{d\mid n}\mu (d)f(n/d)$
      $f(n)=\sum _{d\mid n}g(d)$
  
  où μ est la fonction de Möbius . Soit
  
      $V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.$
  
  Alors
  
      $S(A,P,z)\leq {\frac {X}{V(z)}}+O\left({\sum _{\begin{smallmatrix}d_{1},d_{2}<z\\d_{1},d_{2}\mid P(z)\end{smallmatrix}}\left\vert R_{[d_{1},d_{2}]}\right\vert }\right)$
  
  où $[d_1,$ $d_2]$ désigne le plus petit commun multiple de $d_1$ et $d_2.$ Il est souvent utile d'estimer V(z) par
  
      $V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,$
  
  ## Applications
  
  * Le théorème de Brun-Titchmarsh (en) sur le nombre de nombres premiers dans une progression arithmétique ;
  * Le nombre de n ≤ x tel que n est premier avec φ(n) est asymptotique à $e^{-\gamma }{\frac {x}{\log \log \log x}}$.
  