Crible de Selberg

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₁ 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

${\displaystyle 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

${\displaystyle \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

${\displaystyle g(n)=\sum _{d\mid n}\mu (d)f(n/d)}$

${\displaystyle f(n)=\sum _{d\mid n}g(d)}$

où μ est la fonction de Möbius . Soit

${\displaystyle V(z)=\sum _{\begin{smallmatrix}d<z\\d\mid P(z)\end{smallmatrix}}{\frac {1}{g(d)}}.}$

Alors

${\displaystyle 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₁, d₂] désigne le plus petit commun multiple de d₁ et d₂. Il est souvent utile d'estimer V(z) par

${\displaystyle V(z)\geq \sum _{d\leq z}{\frac {1}{f(d)}}.\,}$

• 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 à ${\displaystyle e^{-\gamma }{\frac {x}{\log \log \log x}}}$.

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Selberg sieve » (voir la liste des auteurs).
• Alina Carmen Cojocaru et M. Ram Murty, An introduction to sieve methods and their applications, vol. 66, Cambridge University Press, coll. « London Mathematical Society Student Texts », 2005, 113–134 p. (ISBN 0-521-61275-6, zbMATH 1121.11063)
• Harold G. Diamond et Heini Halberstam, A Higher-Dimensional Sieve Method: with Procedures for Computing Sieve Functions, vol. 177, Cambridge, Cambridge University Press, coll. « Cambridge Tracts in Mathematics », 2008 (ISBN 978-0-521-89487-6, zbMATH 1207.11099)
• George Greaves, Sieves in number theory, vol. 43, Berlin, Springer-Verlag, coll. « Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge », 2001 (ISBN 3-540-41647-1, zbMATH 1003.11044)
• Heini Halberstam et H.E. Richert, Sieve Methods, vol. 4, Academic Press, coll. « London Mathematical Society Monographs », 1974 (ISBN 0-12-318250-6, zbMATH 0298.10026)
• Christopher Hooley, Applications of sieve methods to the theory of numbers, vol. 70, Cambridge University Press, coll. « Cambridge Tracts in Mathematics », 1976, 7–12 p. (ISBN 0-521-20915-3, zbMATH 0327.10044)
• Selberg, « On an elementary method in the theory of primes », Norske Vid. Selsk. Forh. Trondheim, vol. 19,‎ 1947, p. 64–67 (ISSN 0368-6302, zbMATH 0041.01903)