Discrete mathematics

Description

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.

• distribution function


• behrend


• behrend sequence


• e?n √ log2


• entier


• limite donnee


• ?n ?

Subjects

• Academic document
• Education
• Secondary scrool
• Troisième
• Mathématiques
• Distribution function
• Behrend
• Entier relatif

Informations

• Published by: profil-shawyag-2012
• Reads: 121
• Language: English

Exrait

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 2 e O(ξ N √ log 2 N) . We also prove that, for any given positive real numberα, there is a positive constantc=c(α) such thatc < µ (A N )<1−cwhereA N =A N (α) is the set of all productsabwithN < aN 1+α , a < ba(1 +ε N ), (a, b) = 1 andε N := (logN) 1−log 3 e ξ N √ log 2 N . 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, N 1+α ], 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 2 2 −z N √ log 2 N withz N →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 Classification : 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 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) = N li → 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 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],stipulequeliminf N→∞ µ {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 log k lake.hmittcnofaleragolnoire´tdee´`-ieme