5.3. UN CRIBLE COMBINATOIRE SIMPLE
5.3. Un crible combinatoire simple
On suppose dans cette section que les éléments a, de la suite d sont positifs,
an 2 O. Parmi les nombreuses variantes du crible, nous allons présenter un crible
combinatoire simple, relativement proche de la méthode originale de Brun [Br].
Pour une présentation beaucoup plus exhaustive, voir [HR], ainsi que [Bo] et [Te].
Soit D > z un paramètre supplémentaire. Un crible de niveau D, tel que défini
par Brun, est essentiellement une « déformation » h+ (n) ou h (n) de la fonction de
Mobius, supportée sur les entiers d < D, qui vérifie h+ (1) = 1 (resp. A- (1) = 1 ) et
l'inégalité
pour n 2 2. Dans le cas de hf , on parle de crible majorant et dans celui de A- de crible
minorant. Cette terminologie est justifiée par le lemme suivant.
Lemme 5.3.1. - Soit A+, resp. A-, un crible majorant, resp. minorant, de niveau D > z . Si
a, 2 O, on apourtout 2 < z < x
Démonstration. - Il suffit de suivre la démonstration de (1.9) et d'insérer (5.3) au
lieu de la formule d'inversion exacte en utilisant la positivité des coefficients a,.
O
Si D est assez petit, on obtient des majorants faisant intervenir assez peu de termes
pour être évalués dans de nombreuses circonstances, et Brun parvint à démontrer
que l'on peut cependant faire cela en conservant au moins le bon ordre de grandeur
pour la somme S ( d , z) quand z < xa , O < a < 1 étant une constante (assez petite)
dépendant de la suite, tant en majorant qu'en minorant la somme. Si un entier n < x
n'a pas de facteurs premiers < xa, il est clair qu'il a (strictement) moins de a-'
facteurs premiers avec multiplicité : en effet, si pi 1 n, 1 < i < o, on a
donc oa < 1. De tels entiers sont souvent appelés presque premiers.
Le choix de h+ et h- peut être l'objet d'efforts tout à fait subtils. Indiquons deux
des méthodes les plus efficaces.
(1) Le crible combinatoire, tel que créé par Brun [Br]. Dans ce cas, h+ et h- sont
données par restriction de la fonction de Mobius à des suites 9 + , 9- c [ l , Dl
contenant n = 1. On a alors h+ (1) = h- (1) = 1, et le problème de vérifier (5.3)
devient celui de bien choisir les ensembles 9+, 9'-, ce qui est fait par des considérations combinatoires sur les diviseurs d'un entier n (cJ: plus bas).
SOCIÉTÉ MATHEMATIQUE DE FRANCE 2004
5.3. Un crible combinatoire simple
On suppose dans cette section que les éléments a, de la suite d sont positifs,
an 2 O. Parmi les nombreuses variantes du crible, nous allons présenter un crible
combinatoire simple, relativement proche de la méthode originale de Brun [Br].
Pour une présentation beaucoup plus exhaustive, voir [HR], ainsi que [Bo] et [Te].
Soit D > z un paramètre supplémentaire. Un crible de niveau D, tel que défini
par Brun, est essentiellement une « déformation » h+ (n) ou h (n) de la fonction de
Mobius, supportée sur les entiers d < D, qui vérifie h+ (1) = 1 (resp. A- (1) = 1 ) et
l'inégalité
pour n 2 2. Dans le cas de hf , on parle de crible majorant et dans celui de A- de crible
minorant. Cette terminologie est justifiée par le lemme suivant.
Lemme 5.3.1. - Soit A+, resp. A-, un crible majorant, resp. minorant, de niveau D > z . Si
a, 2 O, on apourtout 2 < z < x
Démonstration. - Il suffit de suivre la démonstration de (1.9) et d'insérer (5.3) au
lieu de la formule d'inversion exacte en utilisant la positivité des coefficients a,.
O
Si D est assez petit, on obtient des majorants faisant intervenir assez peu de termes
pour être évalués dans de nombreuses circonstances, et Brun parvint à démontrer
que l'on peut cependant faire cela en conservant au moins le bon ordre de grandeur
pour la somme S ( d , z) quand z < xa , O < a < 1 étant une constante (assez petite)
dépendant de la suite, tant en majorant qu'en minorant la somme. Si un entier n < x
n'a pas de facteurs premiers < xa, il est clair qu'il a (strictement) moins de a-'
facteurs premiers avec multiplicité : en effet, si pi 1 n, 1 < i < o, on a
donc oa < 1. De tels entiers sont souvent appelés presque premiers.
Le choix de h+ et h- peut être l'objet d'efforts tout à fait subtils. Indiquons deux
des méthodes les plus efficaces.
(1) Le crible combinatoire, tel que créé par Brun [Br]. Dans ce cas, h+ et h- sont
données par restriction de la fonction de Mobius à des suites 9 + , 9- c [ l , Dl
contenant n = 1. On a alors h+ (1) = h- (1) = 1, et le problème de vérifier (5.3)
devient celui de bien choisir les ensembles 9+, 9'-, ce qui est fait par des considérations combinatoires sur les diviseurs d'un entier n (cJ: plus bas).
SOCIÉTÉ MATHEMATIQUE DE FRANCE 2004