Discrete mathematics
23
pages
English
Documents scolaires
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
23
pages
English
Documents scolaires
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Niveau: Secondaire, Collège, Troisième
Discrete mathematics 200 (1999), 181-203. Ensembles de multiples de suites finies P. Erdo˝s & G. Tenenbaum Abstract. A Behrend sequence is a (necessarily infinite) integer sequence A with elements exceeding 1 and whose set of multiples M(A) has logarithmic density µ(A) = 1. By a famous theorem of Davenport and Erdo˝s, this implies that M(A) also has natural density equal to 1. An ?-pseudo-Behrend sequence is a finite sequence of integers exceeding 1 with µ(A) > 1 ? ?. We show that for any given ? ?]0, 1[ and any function ?N ?∞, the maximal number of disjoint ?-pseudo-Behrend sequences included in [1, N ] is (logN)log 2eO(?N √ log2 N). We also prove that, for any given positive real number ?, there is a positive constant c = c(?) such that c < µ(AN ) < 1?c where AN = AN (?) is the set of all products ab with N < a N1+?, a < b a(1 + ?N ), (a, b) = 1 and ?N := (logN)1?log 3e?N √ log2 N . This provides, in a strong quantitative form, a finite analogue of the Maier–Tenenbaum theorem confirming Erdo˝s' conjecture on the propinquity of divisors.
Voir
Discrete mathematics 200 (1999), 181-203. Ensembles de multiples de suites finies P. Erdo˝s & G. Tenenbaum Abstract. A Behrend sequence is a (necessarily infinite) integer sequence A with elements exceeding 1 and whose set of multiples M(A) has logarithmic density µ(A) = 1. By a famous theorem of Davenport and Erdo˝s, this implies that M(A) also has natural density equal to 1. An ?-pseudo-Behrend sequence is a finite sequence of integers exceeding 1 with µ(A) > 1 ? ?. We show that for any given ? ?]0, 1[ and any function ?N ?∞, the maximal number of disjoint ?-pseudo-Behrend sequences included in [1, N ] is (logN)log 2eO(?N √ log2 N). We also prove that, for any given positive real number ?, there is a positive constant c = c(?) such that c < µ(AN ) < 1?c where AN = AN (?) is the set of all products ab with N < a N1+?, a < b a(1 + ?N ), (a, b) = 1 and ?N := (logN)1?log 3e?N √ log2 N . This provides, in a strong quantitative form, a finite analogue of the Maier–Tenenbaum theorem confirming Erdo˝s' conjecture on the propinquity of divisors.
- distribution function
- behrend
- behrend sequence
- e?n √ log2
- entier
- limite donnee
- ?n ?
Discrete mathematics
200(1999), 181-203.
ples
Ensembles de multi de suites finies
P.Erd˝os&G.Tenenbaum
Abstract.Behrend sequence is a (necessarily infinite) integer sequenceA Awith elements exceeding 1 and whose set of multiplesM(A) has logarithmic densityµ(A) = 1. By a famous theorem of Davenport and Erd˝os, this implies thatM(A) also has natural density equal to 1. Anε-pseudo-Behrend sequence is a finite sequence of integers exceeding 1 withµ(A)>1−ε. We show that for any givenε∈]0,1[ and any functionξN→ ∞, the maximal number of disjoint ε-pseudo-Behrend sequences included in [1, N] is (logN)log 2eO(ξN√log2N). We also prove that, for any given positive real numberα, there is a positive constantc=c(α) such thatc <µ(AN)<1−cwhereAN=AN(α) is the set of all productsabwithN < aN1+α, a < ba(1 +εN), (a, b) = 1 andεN:= (logN)1−log 3eξN√log2N. This provides, in a strong quantitative form, a finite analogue of the Maier–Tenenbaum theorem confirming Erd˝os’ conjecture on the propinquity of divisors. A similar result holds for the natural density of the set of all integersnsuch thatF(n) has a divisor in the interval ]N, N1+α], whereFis any polynomial with integer coefficients, and we establish in full generality that this quantity tends to a limit as Napproaches infinity. Finally, we show that, for largeNandq= (logN)log 22−zN√log2NwithzN→z∈R, the divisorsdof an integernwithdNavoid no invertible residue class modqwith probability approximately Φ(z), where Φ denotes the distribution function of the Gaussian Law.
Keywords :distribution of divisors, Erd˝os conjecture, distribution of prime factors, distribution of arithmetic functions, sieve, multiplicative properties of polynomial values.
1991 Mathematics Subject Classification : 11N25, 11N37, 11N56, 11N64
1.Introductionet´enonc´edesr´esultats SoitAexrsient’eeditsuise´dnO.1tnade´cgneparuen
M(A) :={ma:m1, a∈ A}
l’ensemble des multiples deAd-a`leri’c,-tseetedsaiuelesotsursayntieuanta moins un diviseur dansA. Davenport et Erd˝os ont montr´e en 1937 ([2], voir aussi [3]) queM(A)ssopde`eecn´saesemireuqimhtiraglo´eitnsdenetuenδM(Ae`aegal),´ sadensite´asymptotiqueinf´erieuredM(A). Nous posons µ(A) :=δM(A) =dM(A).(1)
1. Ici et dans la suite, nous notonsdS(resp.dS) la densit´e naturelle (resp. la densit´e naturelleinfe´rieure)d’unesuited’entiersS. Il est clair que, lorsqueAest une suite finie, M(A)opsse`ednudeatneuqtne´reoinusienent´uratleelurneocgnec.sedecnfiniesdelass On a donc dans ce casµA=dM(A).
2
P. Er ˝ & G T dos . enenbaum
Ilr´esulte´egalementduth´eor`emedeDavenport–Erd˝osque
(1)
µ(A) =Nli→m∞dMA ∩[1, N],
autrement dit la densit´e logarithmique d’un ensemble de multiples peut ˆetre approch´ee d’arbitrairement pr`es par celle des multiples d’une partie finie. Ainsi, l’´etudedel’applicationA →µ(Aasucdemele,ant,nteuiediaivtronuep)´rerteˆt suitesAfinies. L’un des premiers r´esultats importants de la th´eorie des ensembles de multiples, duˆ`aBesicovitch[1],stipulequeliminfN→∞µ{n: nN <2N}= 0. Cette estimation a permis `a Besicovitch de construire un exemple de suiteApour laquelle M(Aso`sn)peasdeedepit´edens],[5osd˝Erd’tltae´usutrnrona´elie.Amrellnatu Tenenbaum a montr´e dans [25] que l’on a
(2)
δN:=µ{n: nN <2N}= 1/(logN)δ+o(1)
avecδ:= 1−(1 + log log 2)/log 2≈0,nsioatisgsesrevilare´ne´r´es7.Cetetdulta8006 et cons´equences sont ´etablis en d´etail au chapitre 2 de [16]. On dit qu’une suiteAest une suite de Behrend siµ(A) = 1. Ce concept est l’un des plus profonds de la th´eorie des ensembles de multiples, et aussi l’un des plusmyste´rieux.Ende´pitdenombreusestentatives,onchercheencoreuncrit`ere simple et maniable permettant de d´ecider si une suite donn´ee est de Behrend. Des avanc´eespartiellesont´et´eobtenuesdans[13],[17],[22],[29],[30]. L’ine´galit´efondamentaledeBehrend
1−µ(A ∪ B)1−µ(A)1−µ(B),
valable pour toutes suitesAetB, montre qu’une suite finie ne peut ˆetre de Behrend, et,pluspr´ecise´ment,quelacondition
1/a= +∞ a∈A estne´cessairepourqueµ(A) = 1.Cependant, au vu de (1), il est naturel de consid´erer, pour chaqueεde ]0,1[, les suites finiesAtelles queµ(A)>1−ε. Nous dirons qu’une telle suite estε-pseudo-Behrend, ce que nous ´ecrirons sous forme abr´eg´eeε-pB. L’inte´reˆtdelanotionr´esideencequ’ellepermetd’apprehenderquantitativement ´ la mesure relative de l’ensemble des suites de Behrend dans celui de toutes les ` suites d’entiers. A cet effet, nous introduisons la fonctionβ(N;εbmeruaonagel,)e´ maximal de suitesε-pB disjointes contenues dans ]1, N]. Ici et dans la suite, nous notons logklake.hmittcnofaleragolnoire´tdee´`-ieme
