Discrete mathematics

pages

English

Documents scolaires

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-shawyag-2012

Nombre de lectures

122

Langue

English

Niveau: Secondaire, Collège, Troisième
Discrete mathematics 200 (1999), 181-203. Ensembles de multiples de suites ﬁnies P. Erdo˝s & G. Tenenbaum Abstract. A Behrend sequence is a (necessarily inﬁnite) 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 ﬁnite 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 ﬁnite analogue of the Maier–Tenenbaum theorem conﬁrming Erdo˝s' conjecture on the propinquity of divisors.

distribution function

behrend

behrend sequence

e?n √ log2

entier

limite donnee

?n ?

Voir

Publié par

profil-shawyag-2012

Nombre de lectures

122

Langue

English

Discrete mathematics

200(1999), 181-203.

ples

Ensembles de multi de suites ﬁnies

P.Erd˝os&G.Tenenbaum

Abstract.Behrend sequence is a (necessarily inﬁnite) 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 ﬁnite 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 < aN1+α, a < ba(1 +εN), (a, b) = 1 andεN:= (logN)1−log 3eξN√log2N. This provides, in a strong quantitative form, a ﬁnite analogue of the Maier–Tenenbaum theorem conﬁrming 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 coeﬃcients, and we establish in full generality that this quantity tends to a limit as Napproaches inﬁnity. Finally, we show that, for largeNandq= (logN)log 22−zN√log2NwithzN→z∈R, the divisorsdof an integernwithdNavoid 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 Classiﬁcation : 11N25, 11N37, 11N56, 11N64

1.Introductionet´enonc´edesr´esultats SoitAexrsient’eeditsuise´dnO.1tnade´cgneparuen

M(A) :={ma:m1, 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 ﬁnie, M(A)opsse`ednudeatneuqtne´reoinusienent´uratleelurneocgnec.sedecnﬁniesdelass On a donc dans ce casµA=dM(A).

P. Er ˝ & G T dos . enenbaum

Ilr´esulte´egalementduth´eor`emedeDavenport–Erd˝osque

(1)

µ(A) =Nli→m∞dMA ∩[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 ﬁnie. Ainsi, l’´etudedel’applicationA →µ(Aasucdemele,ant,nteuiediaivtronuep)´rerteˆt suitesAﬁnies. 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 ﬁnie 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 ﬁniesAtelles 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 eﬀet, 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

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

Discrete mathematics

YouScribe

Le catalogue

Le service

Les conditions