L. Lov´sz I.Z. Ruzsa, V. T. S´s (eds), a o Erd˝ os Centennial volume , Bolyai Society Mathematical Studies 25 (2013), 651-681.

## Some of Erd˝s' unconventional problems o in number theory, thirty-four years later ∗

G´ erald Tenenbaum

There are many ways to recall Paul Erd˝ os' memory and his special way of doing mathematics. Ernst Straus described him as 'the prince of problem solvers and the absolute monarch of problem posers'. Indeed, those mathematicians who are old enough to have attended some of his lectures will remember that, after his talks, chairmen used to slightly depart from standard conduct, not asking if there were any questions but if there were any answers.

In the address that he forwarded to Mikl´s o Simonovits for Erd˝ os' funeral, Claude Berge mentions a conversation he had with Paul in the gardens of the Luminy Campus, near Marseilles, in September 1995. After Paul's opening lecture for this symposium on Combinatorics, Berge asked him to specify his beauty criteria for a conjecture in discrete mathematics. Erd˝s mainly retained the following five: o

- (i) The simplicity of the statement;
- (ii) The expected difficulty of the solution (which Paul liked to measure in dollars);
- (iii) The posterity of the subsequent theorem, i.e. the set of results arising either directly from the solution of from the methods designed to obtain it;
- (iv) The future of the path opened by the problem, which I would rather call the set of descendants of the problem, in other words the family of new questions opened up by the statement or the solution of the conjecture;
- (v) The intuitive representability of the specific mathematical property that is being dealt with.

Apart, perhaps, the last, for which an adequate transposition should be described with further precision, these criteria are equally relevant to a classification for a conjecture in analytic and/or elementary number theory.

My purpose here mainly consists in illustrating these criteria by revisiting some of the problems stated by Erd˝s in his profound article [24]. o

Aside from updating the status of a number of interesting questions, my hope is to convince the reader that Erd˝s' conjectures, although stated in a condensed and seemingly o particular form, were problematics rather than problems. Day after day, year after year, each of his questions appears, in the light of discussions and partial progress, as a node in a gigantic net, designed not for a single prey but for a whole species.

In the sequel of this paper, quotes from the article [24] are set in italics. I took liberties to correct obvious typographic errors and to slightly modify some notations in order to fit with subsequent works. Erd˝s' paper starts with the following. o

First of all I state a very old conjecture of mine: the density of integers n which have two divisors d 1 and d 2 satisfying d 1 &lt; d 2 &lt; 2 d 1 is 1. I proved long ago [20] that the density of

∗ We include here some corrections with respect to the published version.

these numbers exists but I have never been able to prove that it is 1. I claimed [21] that I proved that almost all integers n have two divisors

$$& ( 1 ) & & d _ { 1 } < d _ { 2 } < d _ { 1 } \left \{ 1 + ( e / 3 ) ^ { ( 1 - \eta ) \log \log n } \right \} \\ & \quad \text{and} \, 4 \text{that} \, / 1 \, \underset { \theta } { \theta } \, \text{and} \, \theta \, \text{and} \, \theta \, 1 + \theta \, 1 \, + \theta \, 1$$

and that (1) is best possible, namely it fails if 1 -η is replaced by 1 + η . R.R. Hall and I confirmed this later statement but unfortunately we cannot prove (1) . We are fairly sure that (1) is true and perhaps it is not hopeless to prove it by methods of probabilistic number theory that are at our disposal.

This is an edifying example of a conjecture meeting the above five requirements. However, before elaborating on this, it may be worthwhile try understanding the process that led Erd˝s to this simple and deep statement. o

An integer n is called perfect if it is equal to the sum of its proper divisors. Thus 6 = 1+2+3 and 28 = 1+2+4+7+14 are perfect. In modern notation, a perfect integer n satisfies σ n ( ) = 2 n where σ n ( ) stands for the sum of all divisors. This is an interesting formulation since σ n ( ) is a multiplicative function of n . In the third century before our era, Euclid proved (IX.36) that 2 p -1 (2 p -1) is perfect whenever 2 p -1 is prime, which of course implies that p itself is prime.

An integer n is called abundant if σ n ( ) &gt; 2 n . In the early thirties, in a book on number theory, Erich Bessel-Hagen asks whether abundant integers have a natural density. Davenport [12], Chowla [11], Erd˝s [16] and Behrend [3] all gave, independently, a positive o answer. All proofs, except that of Erd˝s, rest on the method of (real or complex) moments. o Erd˝ os attacks the problem from another viewpoint: primitive abundant numbers, i.e. abundant numbers having no abundant proper divisor. Writing f ( n ) for σ n /n ( ) , any primitive abundant integer n satisfies

$$2 \leqslant f ( n ) \leqslant f ( n / p ) f ( p ) < 2 ( 1 + 1 / p )$$

whenever p n | . Since the largest prime factor of n is usually large, this restricts the cardinality of primitive abundant numbers not exceeding x , which can be shown to be o x/ ( (log x ) 2 ) . The proof is then completed by noticing that, if we write

$$\mathcal { M } ( \mathcal { A } ) \coloneqq \{ m a \, \colon a \in \mathcal { A }, \, m \geqslant 1 \}$$

for the so-called set of multiples of the set A and d, d, d for natural, upper and lower density respectively, then

$$\mathfrak { d M } ( \mathcal { A } _ { T } ) \leqslant \underline { d } \mathcal { M } ( \mathcal { A } ) \leqslant \overline { d } \mathcal { M } ( \mathcal { A } ) \leqslant \mathfrak { d M } ( \mathcal { A } _ { T } ) + \sum _ { \substack { a > T \\ a \in \mathcal { A } } } \frac { 1 } { a } \\ - \quad \ \.$$

holds for any integer sequence A such that ∑ a ∈ A 1 /a &lt; ∞ , with A T := A ∩ [1 , T ]. This was the starting point of the fruitful concept of set of multiples.

It was once suspected that any set of multiples should have a natural density. However, Besicovitch [5] soon disproved this conjecture by showing that

$$\liminf _ { T \to \infty } \, d M ( | T, 2 T | ) = 0.$$

Indeed, it is easy to deduce from this that, given any ε &gt; 0 and a sequence { T j } ∞ j =0 increasing sufficiently fast, then A := ∪ j ] T , j 2 T j ] satisfies d M A ( ) &lt; ε , d M A ( ) /greaterorequalslant 1 2 .

The reader might ask at this stage: interesting indeed, but how does this link to (1)? We still need a few more steps inside Erd˝s' peculiar way of thinking. o

It is one of the marks of the great: not to accept an obstruction before understanding it completely. This holds outside of mathematics as well as inside. Erd˝s did not accept o Besicovitch's counter-example for itself and continued the quest.

First [18], he improved (2) to the optimal

$$\lim _ { T \to \infty } d \mathcal { M } ( [ T, T ^ { 1 + \varepsilon _ { T } } ] ) = 0$$

provided ε T → 0 as T →∞ .

/negationslash

With this new, crucial piece of information, he progressed in two connected directions: first, to show, with Davenport [13] - see also [14] for another, very interesting proof that any set of multiples has a logarithmic density, equal to its lower asymptotic density, (1) and, second, to show [20] (2) that Besicovitch-type constructions are essentially the only obstacles to the existence of d M A ( ): writing d 1 ( n, A ) := inf { d n | : d ∈ A } with the convention that d 1 ( n, A ) = ∞ whenever n ∈ M A ( ), a necessary and sufficient condition that M A ( ) has a natural density is

$$\lim _ { \varepsilon \to 0 } \overline { d } \{ n \geqslant 1 \, \colon n ^ { 1 - \varepsilon } < d _ { 1 } ( n, \mathcal { A } ) \leqslant n \} = 0.$$

Now, consider the set

$$\mathcal { E } \coloneqq \{ m \in \mathbb { N } ^ { * } \, \colon m = d d ^ { \prime }, d < d ^ { \prime } < 2 d \}.$$

Then n 1 -ε &lt; d 1 ( n, E ) /lessorequalslant n plainly implies that n has a divisor in ] n 1 / 2 -ε , n 1 / 2 ] and it is easy to deduce (4) from (3).

So we now know that the set of integers with two close divisors has a natural density. (By 'close' we mean here that the ratio of the two divisors should lie in ]1 , 2[.) Moreover, as seen above, the existence property follows in a natural way from the theory of sets of multiples: the sequence E defined above is one of simplest examples one can think of that meets the criterion (4).

But what should the density be? Erd˝s stated, as early as 1948 (and probably much o before) [20], that this density should be equal to 1. Here again, a seemingly anecdotal conjecture is actually based on a profound assumption-any answer to it, positive or negative, is bound to enlighten our understanding of the multiplicative structure of integers.

Let us make the convention to use the suffix pp to indicate that a relation holds on a set of asymptotic density 1. As we shall see later in this paper, Erd˝s had known for o long that sufficiently far prime factors behave almost independently pp. Specifically, if we denote by

$$\{ p _ { j } ( n ) \} _ { j = 1 } ^ { \omega ( n ) }$$

the increasing sequence of distinct prime factors of an integer n and if we write

$$U _ { j } ( n ) & \coloneqq \{ \log _ { 2 } p _ { j } ( n ) - j \} / \sqrt { j }, \\. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &. &.$$

then, to a first approximation, U j ( n ) and U h ( n ) resemble independent Gaussian random variables pp provided that j/h → ∞ . (Here and in the sequel, we let log k denote the k -fold iterated logarithm.) Having this in mind, it is reasonable to believe that, in first approximation, the quantities log( d /d ′ ) are evenly distributed pp in the interval

1. We shall make use of this extra information later on.

2. See [29] for a short proof.

[ -log n, log n ]. Since these quantities are 3 ω n ( ) in number, we deduce from the HardyRamanujan estimate ω n ( ) ∼ log 2 n pp that the smallest of these numbers should be of size (log n ) 1 -log 3+ o (1) pp.

This is, perhaps no more, certainly no less, what is hidden behind conjecture (1).

This conjecture, which is now a theorem, due to Erd˝s-Hall [27] for the lower bound o and to Maier-Tenenbaum [55] for the upper bound, has had a wide posterity and many descendants.

In his doctoral dissertation supervised by the author [65], Stef proves that the number R x of exceptional integers not exceeding x and which do not belong to M E ( ) satisfies

$$x / ( \log x ) ^ { \beta + o ( 1 ) } \ll R _ { x } \ll x e ^ { - c \sqrt { \log _ { 2 } x } }$$

for a suitable constant c &gt; 0, with β = 1 -(1 + log 2 3) / log 3 ≈ 0 00415 , . These are the best known estimates to date.

To the chapter of posterity certainly belong all results involving the still mysterious Erd˝ os-Hooley Delta-function and the so-called propinquity functions

$$E _ { r } ( n ) \coloneqq \min _ { 1 \leqslant j \leqslant \tau ( n ) - r } \log \{ d _ { j + r } ( n ) / d _ { j } ( n ) \} \quad ( r \geqslant 1 ),$$

where { d j ( n ) } τ ( n ) j =1 stands for the increasing sequence of the divisors of an integer n . One of the most recent achievements in this direction is a very precise confirmation of the heuristic principle leading to (1), as described above: Raouj, Stef and myself prove in [62] that

$$E _ { 1 } ( n ) = \frac { \log n } { 3 ^ { \omega ( n ) } } ( \log _ { 2 } n ) ^ { \vartheta _ { n } } \quad \text{pp},$$

where -5 /lessorequalslant ϑ n /lessorequalslant 10. Many more precise and connected results are actually proved in [62]. The situation is much less satisfactory regarding the functions E r when r /greaterorequalslant 2, for which the precise pp behaviour is still unknown. Using techniques similar to that of the proof of theorem 3 of [36], it can be shown that

$$E _ { 2 } ( n ) > ( \log n ) ^ { - \gamma _ { 2 } + o ( 1 ) } \quad \text{pp}$$

for some γ 2 &lt; log 3 -1. Moreover, the methods and results of [56] yield

$$E _ { r } ( n ) \leqslant ( \log n ) ^ { - \beta _ { r } + o ( 1 ) } \quad \text{pp},$$

with

$$\beta _ { r } \coloneqq \frac { ( \log 3 - 1 ) ^ { m } } { ( \log 3 - 1 / 3 ) ^ { m - 1 } }, \quad 2 ^ { m - 1 } < r + 1 \leqslant 2 ^ { m }.$$

Thus, we have

$$\beta _ { 1 } = \log 3 - 1 \approx 0. 0 9 8 6 1, \ \beta _ { 2 } = \beta _ { 3 } \approx 0. 0 1 2 7 1, \ \beta _ { r } \approx 0. 0 0 1 6 4 \ \ ( 4 \leqslant r \leqslant 7 ).$$

Also, it is proved in [56] (th. 1.1) that E r ( n ) &gt; τ ( n ) -1 /r + (1) o holds pp uniformly in r /greaterorequalslant 1, and thus

$$E _ { r } ( n ) = 1 / ( \log n ) ^ { o ( 1 ) } \quad \text{pp} \quad ( r = r ( n ) \to \infty ),$$

a result which might look surprising at first sight.

We conjecture the existence of a strictly decreasing sequence { α r } ∞ r =1 such that

$$E _ { r } ( n ) = ( \log n ) ^ { - \alpha _ { r } + o ( 1 ) } \quad \text{pp}.$$

It is particularly irritating, for instance, to be unable to find a better pp upper bound for E 2 ( n ) than for E 3 ( n ).

We also mention as a posterity result the proof by Raouj [61] of Erd˝ os' conjecture asserting that

$$d \mathcal { M } ( \cup _ { d | n } ] d, 2 d ] ) = 1 + o ( 1 ) \quad \text{pp}. \\ \shortmid \text{the following fairly strong (and optimal) form}$$

$$\left ( \begin{array} { c c c c } 1 & - r \cdots & \cdots & - & \cdots & \cdots \\ \frac { 1 } { ( \log n ) ^ { F ( \lambda ) + o ( 1 ) } } & < 1 - \delta _ { n } < e ^ { - c _ { \lambda } } \sqrt { \log n } & & ( 0 \leqslant \lambda < \lambda ^ { * } ) \\ & & \delta _ { n } = ( \log n ) ^ { - F ( \lambda ) + o ( 1 ) } & & ( \lambda > \lambda ^ { * } ) \end{array} \right ) \, \quad \, \right )$$

This is established in the following fairly strong (and optimal) form. Put λ ∗ := log 4 -1 and δ n := d M ( ∪ d n | ] d, (1 + 1 / (log n ) λ ) d ] ) . Then where F λ ( ) := β log β -β + 1 with β := -1 + (1 + λ / ) log 2 if λ /lessorequalslant 3 log 2 -1, and F λ ( ) := λ -log 2 if λ &gt; 3 log 2 -1.

The Erd˝ os-Hooley function is defined as

$$\Delta ( n ) \coloneqq \sup _ { \substack { u \in \mathbb { R } \\ e ^ { u } < d \leqslant e ^ { u + 1 } } } 1 \quad ( n \geqslant 1 ).$$

It first appears (implicitly) in [23] and (explicitly) in [30], [31] in the early seventies. It was next studied by Hooley [50] with the aim of developing a variety of applications to several branches of number theory.

The ratio ∆( n /τ ) ( n ) has an immediate probabilistic interpretation: with L´vy's 1937 e definition, it is the value at 1 of the concentration function of the random variable D n taking the values log d ( d n | ) with uniform probability 1 /τ ( n ). It is noteworthy to state here that D n = ∑ p ν ‖ n D p ν where the D p ν are independent.

If we replace the factor 2 by e, which is irrelevant to all intents and purposes, Erd˝s' o initial conjecture

$$d \mathfrak { M } ( \mathcal { E } ) = 1$$

is equivalent to the statement that

$$\Delta ( n ) & > 1 \quad \ p p,$$

so that (8) provides quantitative estimates for the number of exceptions.

The best pp-bounds to date for the ∆-function appear in a joint article with Maier [56]. We prove that

$$( \log _ { 2 } n ) ^ { \gamma + o ( 1 ) } < \Delta ( n ) < ( \log _ { 2 } n ) ^ { \log 2 + o ( 1 ) } \quad \text{pp},$$

where the exponent γ := (log 2) / log 1 -1 / log 27 0 33827 is conjectured to be optimal. .

To show the existence and determine the value of the exact exponent is a challenging problem in probabilistic number theory. There is no doubt that such a result would imply deeper ideas on the structure of the set of divisors of a normal integer.

( 1 -1 / log 3 ) ≈

However, as shown by Hooley in [50], it is mainly information on the average order

$$s ( x ) \coloneqq \frac { 1 } { x } \sum _ { n \leqslant x } \Delta ( n )$$

that has applications to other arithmetical topics such as Waring-type problems [75], Diophantine approximation [50], [69], and Chebyshev's problem on the greatest prime

factor of polynomial sequences [71]. It is thus proved in [71], as a consequence of an average estimate for a variant of s x ( ), that, for any α &lt; 2 -log 4 ≈ 0 61370, the bound .

$$P ^ { + } \left ( \prod _ { n \leqslant x } F ( n ) \right ) > x \, e ^ { ( \log x ) ^ { \alpha } } \quad ( x > x _ { 0 } ( F ) )$$

holds for any irreducible polynomial F X ( ) ∈ Z [ X ] with degree &gt; 1. This is currently the best available result valid for polynomials of arbitrary degree. Here and in the sequel P + ( m ) denotes the largest prime factor of the integer m with the convention that P + (1) = 1.

Established in [44] and [68], the best bounds for s x ( ) at the time of writing are

$$( 1 1 ) & \quad \log _ { 2 } x \ll s ( x ) \ll e ^ { c \sqrt { \log _ { 2 } x \log _ { 3 } x } } \quad ( x \to \infty ) \\ & \quad \quad \quad$$

where c is a suitable constant. See [46], [69] and, for instance, [63] for further references and descriptions on this question.

Still in the area of descendants of the conjecture (1), we mention the recent paper [8] in collaboration with La Bret`che and where sharp, weighted average bounds are given for e functions of the type

$$\Delta ( n, f ) \coloneqq & \sup _ { u \in \mathbb { R }, \, 0 \leqslant v \leqslant 1 } \left | \sum _ { \substack { d | n \\ e ^ { u } < d \le$$

where f is an oscillating function, typical cases being those of a non principal Dirichlet character or of the M¨bius function. All suitably weighted finite integral, even moments o are also studied. This is the key step to the proof, given in [10], of Manin's conjecture, in the strong form conjectured by Peyre and with effective remainder term, for all Chˆtelet a surfaces.

Maier established in [53] normal upper and lower bounds for (12) in the case f = µ , the M¨ obius function, and his method is equally applicable in the case f = χ , a real, non principal Dirichlet character.

Short averages have also been investigated, by Nair-Tenenbaum [57], Henriot [48], and La Bret` eche-Tenenbaum [9]. These may have numerous, sometimes surprising applications. For instance, writing 〈 〉 t for the fractional part of a real number t , we have [57], for any given ε &gt; 0,

$$\sup _ { D \geq 1 } \Big | \sum _ { D \leqslant d \leqslant 2 D } \Big < \frac { x + y } { d } \Big > - \Big < \frac { x } { d } \Big > \Big |$$

a bound which known exponential sums methods, by far, will fail to meet.

This ends our comments and update on conjecture (1).

The next problem in [24] is described as follows.

Denote by τ + ( n ) the number of integers k for which n has a divisor d satisfying 2 k &lt; d /lessorequalslant 2 k +1 . I conjecture that for almost all n

$$\tau ^ { + } ( n ) / \tau ( n ) \to 0$$

which of course implies that almost all integers have two divisors satisfying d 1 &lt; d 2 &lt; 2 d 1 . It would be of some interest to get an asymptotic formula for

$$\mathfrak { T } ( x ) \coloneqq \sum _ { n \leqslant x } \tau ^ { + } ( n ).$$

It is easy to prove that T ( x / x ) ( log x ) → 1 .

This is an example of Erd˝s' way of attacking conjectures from many different angles. o Indeed, it is often the case that a stronger statement is more accessible than a weaker one, because it reveals a deeper feature. Here, τ + ( n ) &lt; τ n ( ) would suffice to prove the desired conjecture, but Erd˝s asks for much more. As it turns out, hypothesis (13) is o wrong (and the constant 1 in the last statement should be replaced by 0, most certainly a lapsus digiti), but the idea of considering the measure of the set ∪ d n | (log d +[ -1 2 , 1 2 ]) was precisely that which eventually led to the solution in [55].

Improving on an estimate of [33] that was already sufficient to invalidate (13), it was shown in [46] (Chapter 4) that the arithmetic function τ + ( n /τ ) ( n ) has a limiting distribution ν z ( ) satisfying

$$& \frac { z } { \sqrt { \log ( 2 / z ) } } \ll \nu ( z ) \ll z \log ( 2 / z ) \quad ( 0 < z < 1 ). \\ & \text{Thus, } \nu \text{ is certainly continuous at the origin. Two interesting open problems a}$$

Thus, ν is certainly continuous at the origin. Two interesting open problems are (i) to improve upon (15) and (ii) to determine, if any, the discontinuity points of the distribution function ν .

Regarding the second question, I can prove the following.

Theorem 1. The distribution function ν is continuous at z = 1 .

Proof. We know from theorem 51 of [46] (but this already follows from the analysis given in [55]) that, for every ε &gt; 0, there exists T ε &gt; e 1 /ε such that all integers n except at most those from a sequence of upper density /lessorequalslant ε/ 3 have two divisors d , d ′ , such that d &lt; d ′ &lt; 2 ε d &lt; T ε . We may of course assume that T ε increases with 1 /ε . Write n ε := ∏ p j ‖ n, p /lessorequalslant T ε p j . For a non-exceptional integer n and each m n/n | ( ε ), the two divisors md and md ′ belong to the same interval ]2 k , 2 k +1 [ ( k ∈ N ) unless | (log md / ) log 2 -k - | 1 &lt; ε . However, it has been shown in lemma 48.1 of [46] that the discrepancy of the sequence { (log m / ) log 2 : m n/n | ( ε ) } does not exceed ε on a subsequence of lower density 1 -ε/ 3. Thus, if we discard a sequence of integers n of upper density at most 2 ε/ 3, we have

$$\tau ^ { + } ( n ) & \leqslant \tau ( n ) - ( 1 - \varepsilon ) \tau ( n / n _ { \varepsilon } ). \\ \mathbb { \times } \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \ \nu \.$$

Since, for instance, τ ( n ε ) /lessorequalslant log T ε holds on a sequence of lower density 1 -ε/ 3, we get that

$$\tau ^ { + } ( n ) & \leqslant \tau ( n ) \left \{ 1 - \frac { 1 } { 2 \log T _ { \varepsilon } } \right \} \\ \psi \quad \cdot \quad \cdot \quad \cdot \cdot \cdot \cdot \cdot$$

except at most on a sequence of upper density ε . Writing η := 1 / { 2 log T ε } , we have therefore proved that ν (1 -η ) /greaterorequalslant 1 -ε = ν (1) -ε . Observing that ε tends to 0 as a function of η , we obtain the required result. /intersectionsq /unionsq

According to a copy of the galley-proof that Nicolas forwarded to me at the time, the statement concerning T ( x ) is probably due to some last-minute confusion. It is nevertheless linked to another very interesting problem in probabilistic number theory.

Let H x,y,z ( ) denote the number of integers not exceeding x having a divisor in ] y, z ], so that, with the notation (14),

$$\mathfrak { T } ( x ) = \sum _ { 2 ^ { k } \leqslant x } H ( x, 2 ^ { k }, 2 ^ { k + 1 } ).$$

There is a large literature on H x,y,z ( ), starting with (2) and (3), which can already be seen as evaluations of

$$\lim _ { T \to \infty } \lim _ { x \to \infty } H ( x, T, 2 T ) / x, \text{ and } \lim _ { T \to \infty } \lim _ { x \to \infty } H ( x, T, T ^ { 1 + \varepsilon _ { T } } ) / x,$$

respectively. We refer the reader to the recent paper [38] for the history of estimates of H x,y,z ( ) in the various ranges of the parameters. Here, we only quote the evaluation

$$H ( x, y, 2 y ) \asymp \frac { x } { ( \log y ) ^ { \delta } ( \log _ { 2 } y ) ^ { 3 / 2 } } \quad ( 2 \leqslant y \leqslant \sqrt { x } )$$

with δ := 1 -(1+log 2 2) / log 2 ≈ 0 08607. These bounds improve on those of [67], where it . is shown by a much simpler analysis that e -c 1 √ log 2 y /lessorequalslant H x,y, ( 2 y )(log y ) δ /x /lessorequalslant c 2 / √ log 2 y for suitable constants c 1 , c 2 . Using the symmetry of the divisors of n around √ n , we easily deduce from (14) and (16) the following estimate proved in [38]:

$$\mathcal { I } ( x ) \asymp \frac { x ( \log x ) ^ { 1 - \delta } } { ( \log _ { 2 } x ) ^ { 3 / 2 } } \cdot$$

Thus, we still fall short of an asymptotic formula for T ( x ), although we are now fairly close to one-another challenging problem from an old paper.

Let us continue.

Another interesting and unconventional problem states as follows: let 1 = d 1 &lt; d 2 &lt; · · · &lt; d τ ( n ) = n be the set of divisors of n . Put

$$\mathcal { G } ( n ) \coloneqq \sum _ { 1 \leqslant i < \tau ( n ) } \frac { d _ { i } } { d _ { i + 1 } } \cdot$$

I conjecture that G ( n ) → ∞ if we disregard a sequence of integers n of density 0. This again would imply the conjecture on d 1 &lt; d 2 &lt; 2 d 1 , but needless to say I cannot prove it. It would be of interest to determine the normal order of τ + ( n ) and of G ( n ) (or at least of log τ + ( n ) and log G ( n ) ). Also an asymptotic formula for

$$\sum _ { n \leqslant x } \mathcal { G } ( n )$$

would be of interest. It is easy to prove that (1 /x ) ∑ n /lessorequalslant x G ( n ) →∞ .

It turns out to be almost trivial that G ( n ) →∞ pp. Indeed, if p is the smallest prime factor of n , then pd i | n for at least 1 2 τ ( n ) values of i and hence G ( n ) &gt; τ n / p ( ) 2 . In particular, we have G ( n ) &gt; τ n /ξ n ( ) ( ) pp whenever ξ ( n ) → ∞ . It is, however, not true that this lower bound implies (9). Erd˝s probably had in mind the correct statement o that (9) follows from G ( n ) &gt; 1 2 τ ( n ) pp, in other words that the distribution function of G ( n /τ ) ( n ), if it exists, is supported on [ 1 2 , 1].

Erd˝ os and I proved in [34] that G ( n /τ ) ( n ) does have a distribution function. We actually established a fairly general statement: given any bounded real function ϑ defined on ]0 , 1[, the arithmetical function

$$F ( n ; \vartheta ) \coloneqq \frac { 1 } { \tau ( n ) } \sum _ { 1 \leqslant i < \tau ( n ) } \vartheta \left ( \frac { d _ { i } } { d _ { i + 1 } } \right )$$

has a limiting distribution. (3)

3. Note that, in the case ϑ := 1 [1 / , 2 1] , the continuity at 0 of this distribution follows from Theorem 1 above and in turn implies (9). This, however, does not yield a new proof of (9) since we actually used a refinement of (9) to establish Theorem 1.

But it is not true that the distribution function of G ( n /τ ) ( n ) is supported on [ 1 2 , 1]. Indeed, we can show that

$$\mathrm d \{ n \geqslant 1 \, \colon \mathcal { G } ( n ) / \tau ( n ) \leqslant \varepsilon \} > 0 \quad ( 0 < \varepsilon \leqslant 1 ).$$

This follows from the fact that most integers n free of small prime factors are such that d i &lt; 1 2 εd i +1 for most indices i . We omit the details, which can easily be reconstructed from lemma 4 of [33] and lemma 3 of [34].

As far as average orders are concerned, it is proved in [34] that

$$\sum _ { n \leqslant x } F ( n ; \vartheta ) & = \vartheta ( 1 ) x \log x + O \left ( \frac { x ( \log x ) ^ { 1 - \delta } \log _ { 3 } x } { \sqrt { \log _ { 2 } x } } \right ), \\ \partial \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \cdot \colon$$

provided ϑ is twice continuously differentiable on [0 1]. , Here δ is as in (16) and the exponent of log x is optimal. Moreover, by theorem 3 of [34] and (16), we obtain the improvement

$$\frac { c _ { 1 } x ( \log x ) ^ { 1 - \delta } } { ( \log _ { 2 } x ) ^ { 3 / 2 } } \leqslant x \log x - \sum _ { n \leqslant x } \mathcal { G } ( n ) \leqslant \frac { c _ { 2 } x ( \log x ) ^ { 1 - \delta } } { ( \log _ { 2 } x ) ^ { 3 / 2 } },$$

valid for suitable positive constants c 1 , c 2 .

After a discussion on the normal size of the k -th prime factor p k ( n ) of an integer n and a simple proof, via the Tur´n-Kubilius inequality, of the asymptotic formula a

$$\log _ { 2 } p _ { k } ( n ) \sim k \quad ( k \to \infty ) \quad \text{pp}, ^ { ( 4 ) }$$

Erd˝ os describes a problem on fractional parts of Bernoulli numbers, which does not fit with the focus of this survey. Then, he states two problems related to densities of integer sequences.

Denote by λ k ( p ) the density of the integers n whose k -th prime factor is p . λ k ( p ) can easily be calculated by the exclusion-inclusion principle (essentially the sieve of Eratosthenes). By (18) , for almost all integers, p k ( n ) is about expexp k . On the other hand, it is easy to see that the largest value of λ k ( p ) is assumed for much smaller values of p , in fact for

$$\mathrm e ^ { k ( 1 - \varepsilon ) } < p < \mathrm e ^ { k ( 1 + \varepsilon ) }.$$

By more careful computation it would easily be possible to obtain better estimates. The simple explanation for this apparent paradox is that there are very many more values of p at e e k than at e k . It is not impossible that λ k ( p ) is unimodal, i.e. it first increases with p , then assumes its maximum and then decreases. I in fact doubt that λ k ( p ) behaves so regularly but have not disproved it.

The same problems arise if Λ ( k d ) denotes the density of the integers m whose k -th divisor is d . Here I obtain that if d 1 ( n ) &lt; d 2 ( n ) &lt; · · · are the consecutive divisors of n then for all but εx integers n /lessorequalslant x for k &gt; k 0 ( ε, n )

$$\exp \left \{ k ^ { ( 1 / \log 2 ) - \varepsilon } \right \} < d _ { k } ( n ) < \exp \left \{ k ^ { ( 1 / \log 2 ) + \varepsilon } \right \}. \\ \nu _ { 1 } = e _ { 2 } = e _ { 3 } = e _ { 4 } = e _ { 5 } = e _ { 6 } = e _ { 7 } = e _ { 8 } = e _ { 9 }$$

On the other hand, for fixed k , Λ ( k d ) is maximal for

$$e ^ { ( 1 - \varepsilon ) \log k \log _ { 2 } k } < d < e ^ { ( 1 + \varepsilon ) \log k \log _ { 2 } k }.$$

4. We do not reproduce this and refer the reader to [46] (chapter 1) and to [74] (theorem III.3.10).

It can be shown that Λ ( k d ) is not unimodal.

The existence of the densities λ k ( p ) and Λ k ( d ) immediately follows from the fact that the sequences under consideration are finite unions of congruence classes. The idea of considering the local laws of the distributions of p k ( n ) and d k ( n ) stems naturally from the law of iterated logarithm underlying (18) (and based upon the fact that the variables U j ( n ) defined in (7) are almost Gaussian): indeed, Erd˝s announced in 1969 [22] that o

$$( 2 0 ) \sum _ { \log _ { 2 } p \leqslant k + z \sqrt { k } } \lambda _ { k } ( p ) = \Phi ( z ) + o ( 1 ) \quad ( k \to \infty ), \quad \Phi ( z ) \coloneqq \frac { 1 } { \sqrt { 2 \pi } } \int _ { - \infty } ^ { z } \mathrm e ^ { - t ^ { 2 } / 2 } \, \mathrm d t.$$

Thus, the study of the λ k ( p ) is another way of looking at the asymptotic independence of the small prime factors, while, as it turns out, the study of the Λ k ( d ) is a (positive) test of the dependence of the divisors.

By the sieve of Eratosthenes, we have

$$\lambda _ { k } ( p ) = \frac { 1 } { p } \prod _ { q < p } \left ( 1 - \frac { 1 } { q } \right ) s _ { k - 1 } ( p ) \quad ( k \geqslant 1 ),$$

where q denotes a prime number and we have put

$$s _ { j } ( p ) \coloneqq \sum _ { \substack { P ^ { + } ( m ) < p \\ \omega ( m ) = j } } \frac { 1 } { m } \quad ( j \geqslant 0 ).$$

Thus, we have identically

$$\stackrel { \cdot } { F } ( z, p ) \coloneqq \prod _ { q < p } \left ( 1 + \frac { z } { q - 1 } \right ) = \sum _ { j \geqslant 0 } s _ { j } ( p ) z ^ { j }.$$

As noted by Balazard, (5) this settles, in the affirmative, the question of the unimodality of the sequence { s j ( p ) } j /greaterorequalslant 1 and hence of { λ k ( p ) } k for all p . Indeed, it is well known (see, e.g., [59], Part V, problem 47) that, if a polynomial has only real roots, then the number of sign changes in the sequence of its coefficients is equal to the number of positive roots. Since, for all positive numbers a , . . . , a 1 n , the polynomial

$$( 1 - x ) \prod _ { 1 \leqslant j \leqslant n } ( x + a _ { j } ) = \sum _ { 0 \leqslant r \leqslant n + 1 } ( \sigma _ { n - r } - \sigma _ { n + 1 - r } ) x ^ { r }$$

where σ h := ∑ 1 /lessorequalslant j 1 &lt;j &lt; 2 ··· &lt;j h /lessorequalslant n a j 1 · · · a j h (0 /lessorequalslant j /lessorequalslant n + 1), has exactly one positive root, it follows that the sequence { σ h } n h =0 of elementary symmetric functions of the a j is unimodal. Applying this with { a j } n j =1 = { 1 / q ( -1) : q &lt; p } yields the stated property.

Of course the above argument tells us nothing about the mode. An analysis of λ k ( p ) by the saddle-point method has been achieved by Erd˝s and myself in [35]. I only quote a o few results from this work. Write

$$L \coloneqq \log \left ( \frac { \log p } { \log ( k + 1 ) } \right ), \quad M \coloneqq \log \left ( \frac { \log p } { 1 + \log ^ { + } ( k / L ) } \right ), \quad R \coloneqq L \{ 1 + \log ^ { + } ( k / L ) \}. \\ \tau \colon \quad. \quad. \quad. \.$$

Then, given any ε &gt; 0, we have

$$\Gamma _ { \mu, \,, \, \infty } \, \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \tan \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \ sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \ cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \osigma \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \exp \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \exists \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \lessth \, \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \exp \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \os \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \prod \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sec \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \loss \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \ress \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \colon \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \end{ a } } { \mu } }$$

5. Private communication, February 28, 1989.

Moreover, we have, for all primes p ,

$$\max _ { k \geqslant 1 } \lambda _ { k } ( p ) = \frac { 1 + O ( 1 / \log _ { 2 } p ) } { p \sqrt { 2 \pi \log _ { 2 } p } } \\ \int _ { \sigma } \text{this maximum satisfies $k=\log_{\wedge} n+}$$

and any value of k realizing this maximum satisfies k = log 2 p + O (1).

For fixed k , the result we found was slightly different from that foreseen by Erd˝ os, probably through a hasty computation. We actually have

$$\max _ { p } \lambda _ { k } ( p ) = \exp \left \{ - k \Big ( \log k - \log _ { 2 } k - 1 + \frac { 2 \log _ { 2 } k + 1 } { \log k } + \frac { 2 ( \log _ { 2 } k ) ^ { 2 } - \log _ { 2 } k + O ( 1 ) } { ( \log k ) ^ { 2 } } \Big ) \right \}$$

and any value of p realizing this maximum satisfies

$$\log p = \frac { k } { \log k } \left \{ 1 + \frac { 2 \log _ { 2 } k } { \log k } + \frac { 2 ( \log _ { 2 } k ) ^ { 2 } - 3 \log _ { 2 } k + O ( 1 ) } { ( \log k ) ^ { 2 } } \right \}.$$

It remains that the phenomenon described by Erd˝ os does hold: modal values of the sequence { λ k ( p ) } p occur at relatively small values. In other words, in the series

$$\sum _ { p } \lambda _ { k } ( p ) = 1$$

the decrease of the general term as a function of p is so slow that the contribution of the very numerous terms around exp exp k dominate, while the 'large' values around e k/ log k are too few, and indeed not sufficiently large, to contribute significantly to the sum.

To my knowledge, the problem of the (probably non) unimodality of the sequence { λ k ( p ) } p is still open.

In [15], De Koninck and I improve on (20). Uniformly for k /greaterorequalslant 1, z ∈ R , we have

$$\sum _ { \log _ { 2 } p \leqslant k + z \sqrt { k } } \lambda _ { k } ( p ) = \Phi ( z ) + \frac { \Phi _ { 0 } ( z ) } { \sqrt { 2 \pi k } } + O \left ( \frac { 1 } { k } \right )$$

with

$$\Phi _ { 0 } ( z ) \coloneqq e ^ { - z ^ { 2 } / 2 } \{ \frac { 1 } { 3 } + A - \frac { 1 } { 3 } z ^ { 2 } \}, \ \ A \coloneqq \gamma - \sum _ { p } \left \{ \log \left ( \frac { 1 } { 1 - 1 / p } \right ) - \frac { 1 } { p } \right \} \approx 0. 2 6 1 5 0.$$

Here γ denotes Euler's constant.

This yields estimates for the median value of the distribution of the k -th prime factor, defined as the largest prime p ∗ = p ∗ k such that ∑ p /lessorequalslant p ∗ k λ k ( p ) &lt; 1 2 . We find that

$$\log _ { 2 } p _ { k } ^ { * } = k - b + O ( 1 / k ) \quad ( k \geqslant 1 )$$

with b = 1 3 + A ≈ 0 59483. Numerical computations provide . p ∗ 2 = 37, p ∗ 3 = 42719.

A clear descendant of this problem is the following formula, also proved in [15], which turns out to be an application of the estimate for partial sums of the exponential series-an ancient problem of Ramanujan-needed to prove (22). We have

$$\sum _ { \substack { n \leqslant x \\ \Omega ( n ) \leqslant \log _ { 2 } x } } 1 = \frac { 1 } { 2 } x - x \frac { C + \langle \log _ { 2 } x \rangle } { \sqrt { 2 \pi \log _ { 2 } x } } + O \left ( \frac { 1 } { \log _ { 2 } x } \right ) \quad ( x \geqslant 3 ),$$

where C := A -2 3 -∑ p 1 / { p p ( -1) } ≈ 0 36798 and . 〈 〉 t denotes the fractional part of the real number t .

As is to be expected, the results on Λ k ( d ) are much less precise. Erd˝s' pp-estimate o for { d k ( n ) } 1 /lessorequalslant k /lessorequalslant τ ( n ) immediately follows from the law of iterated logarithm for the prime factors. We obtain in particular, for all ε &gt; 0,

$$\sum _ { | \log _ { 2 } d - ( \log k ) / \log 2 | > R _ { k } } \Lambda _ { k } ( d ) = o ( 1 ) \quad ( k \to \infty ),$$

with R k := √ { (2 + ε / ) log 2 } log k log 3 k . Thus, we can consider that the problem of normal order of d k ( n ) is essentially solved. In (19), Erd˝s raises the problem of modal o values of Λ k ( d ) i.e. of determining as precisely as possible those d such that

$$\Lambda _ { k } ( d ) = \Lambda _ { k } ^ { * } \coloneqq \max _ { m } \Lambda _ { k } ( m ).$$

He announces a result which we shall see to be slightly incorrect but nevertheless unveils a rather deep phenomenon.

Let τ ( n, z ) denote the number of divisors of n not exceeding z . The following formula, proved in [35], is the analogue of (21):

$$\Lambda _ { k } ( d ) = \frac { 1 } { d } \prod _ { p \leqslant d } \left ( 1 - \frac { 1 } { p } \right ) \sum _ { \substack { P ^ { + } ( m ) \leqslant d \\ \tau ( m d, d ) = k } } \frac { 1 } { m } \cdot$$

Here, the m -sum obviously depends on the arithmetic structure of m and seemingly harmless questions may reveal to be quite delicate, such as the proof given in [35] of the equivalence

$$\Lambda _ { k } ( d ) > 0 \iff \tau ( d ) \leqslant k \leqslant d.$$

Let us put

$$K _ { j } \coloneqq k ^ { ( \log _ { j + 2 } k ) / \log 2 } \quad ( j \geqslant 0 ).$$

It is well known that min τ ( d ) /greaterorequalslant k d = K 1+ (1) o 0 . Now let N y := ∏ p /lessorequalslant y p , where y is the smallest integer such that τ ( N y ) = 2 π y ( ) /greaterorequalslant k . By selecting d = d k ( N y ) and reducing the m -sum above to the single value m = N /d y , we obtain the left-hand side of the double inequality

$$\frac { k ^ { O ( 1 ) } } { K _ { 0 } K _ { 1 } } \leqslant \Lambda _ { k } ^ { * } \leqslant \frac { k ^ { O ( 1 ) } K _ { 1 } } { K _ { 0 } }$$

proved in [35], while the upper bound already needs a rather involved analysis of the sum. This led Erd˝s and I in [35] to express the belief that the correct version of (19) should o be d = K 1+ (1) o 0 .

Indeed, there are essentially two sound models for the structure of those d realizing the mode. Either τ ( d ) ≈ k and hence d ≈ K 0 and therefore the m -sum has size /equivasymptotic 1, or m and d contribute evenly to the divisors counted by τ ( md,d ) and τ ( d ) ≈ τ ( m,d ) ≈ √ k , so that d and the values of m appearing in the sum are all at least of size √ K 0 . This latter possibility is of course much more complex than the former, since it implies the existence of many integers m having divisors combining with those of d in such a way that τ ( md,d ) = d . The above belief corresponded to the conviction that the simplest situation did prevail. However, in [7], La Bret`che and I show that this is not the case: e for large k , we have

$$\infty \ e n d { \mathbb { S } ^ { \times } } \nu, \ e n d { \mathbb { S } ^ { \times } } \\ \frac { k ^ { O ( 1 ) } } { K _ { 0 } \sqrt { K _ { 1 } } K _ { 2 } } & \leqslant \Lambda _ { k } ^ { * } \leqslant \frac { \sqrt { K _ { 2 } } k ^ { O ( 1 ) } } { K _ { 0 } \sqrt { K _ { 1 } } }, \quad \Lambda _ { k } ( d ) = \Lambda _ { k } ^ { * } \Rightarrow d = K _ { 0 } ^ { 1 / 2 + o ( 1 ) }.$$

(See [7] for a more precise statement and some further information.)

Here again, Erd˝s' question led to a deeper understanding of the structure of the set of o divisors of certain classes of integers and revealed an unexpected phenomenon.

The conjecture (19), although inaccurate, clearly satisfies all criteria quoted at the beginning of this paper. As far as criterion (iv) is concerned, we quote from [7] the following estimate, where Ψ ( 1 x, y ) denotes the number of y -friable squarefree integers not exceeding x , i.e. Ψ ( 1 x, y ) := ∑ n /lessorequalslant x, P + ( n ) /lessorequalslant y µ n ( ) 2 . Given any κ /greaterorequalslant 1, we have

$$\Psi _ { 1 } ( x + x / z, y ) - \Psi _ { 1 } ( x, y ) \ll \Psi _ { 1 } ( x, y ) / z \quad \left ( x \geqslant 2, \, y \geqslant 2, \, 1 \leqslant z \leqslant \min ( x, y ^ { \kappa } ) \right ). \\ \intertext { T h o c t o m o n t o m i n e t h o n m i n e d i t t. e f f $ \Lambda $ ( \Lambda ) $. $ f $ a l $ m o n t o m i n e d i t t $. $ f $ m $ }$$

The statement concerning the non-unimodality of { Λ ( k d ) } d follows easily from (23), since, for any ε &gt; 0, we can construct four integers such that

$$K _ { 0 } ^ { 1 + \varepsilon } < p _ { 1 } < d _ { 1 } < p _ { 2 } < d _ { 2 } < 2 K _ { 0 } ^ { 1 + \varepsilon },$$

where the p j are primes and the d j satisfy τ ( d j ) &gt; k and hence Λ k ( d j ) = 0 ( j = 1 2). ,

In the next paragraphs of [24], Erd˝s quotes a number of results related to the normal o distribution of prime factors, some of which are stated in [22]. For instance, he explains that, with the notation (7), the statement that U j ( n ) and U h ( n ) are asymptotically independent provided j/h →∞ follows from the methods of [28], his epoch-making paper with Kac on the Gaussian distribution of prime factors. He also comments on the fact that (18) shouldn't be taken too literally by stating the following theorem, which I reproduce with a few changes in the notation.

Let { α k } ∞ k =0 tend monotonically to 0 as k → ∞ . Denote by h α ( n ) the number of k such that | log 2 p k ( n ) -k | /lessorequalslant α k . Then, if ∑ k α / k √ k &lt; ∞ , for every integer m the set { n /greaterorequalslant 1 : h α ( n ) = m } has a natural density β m and ∑ m β m = 1 , in other words h α ( n ) has a limiting distribution, while, if ∑ k α / k √ k = ∞ , h α ( n ) →∞ pp .

As far as I know, none of these results has ever been proved in full detail and no effective versions of the statements have been investigated. It would be quite interesting to pursue these tasks with the powerful analytical tools that have been devised since Erd˝s' paper o was written.

The next section of [24] introduces a fundamental concept.

Let p 1 &lt; p 2 &lt; . . . be an infinite sequence of primes. It is quite easy to prove that

$$\sum \frac { 1 } { p _ { i } } = \infty$$

is the necessary and sufficient condition that almost all integers n should have a prime factor p i . It seems very difficult to obtain a necessary and sufficient condition that if a 1 &lt; a 2 &lt; . . . is a sequence of integers then almost all integers n should be a multiple of one of the a 's.

I just want to illustrate the difficulty by a simple example. Let n i +1 &gt; (1+ ) c n i . Consider the integers m which have a divisor d satisfying n k &lt; d /lessorequalslant n k (1+ η k ) . If ∑ k /greaterorequalslant 1 η k &lt; ∞ , then it is easy to see that the density of these integers exists and is less than 1. If ∑ k /greaterorequalslant 1 η k = ∞ , it seems difficult to get a general result, e.g. if η k = 1 /k the density in question exists and is less than 1. It seems certain that there is an α , 0 &lt; α &lt; 1 , so that if β &lt; α and η k = 1 /k β the density of the m having a divisor d , n k &lt; d /lessorequalslant n k (1 + η k ) is 1 and if β &gt; α it is less than 1.

The problem raised here may be reformulated as follows: characterise those integer sequences A such that d M A ( ) = 1. Following Hall [41], we call such a sequence A

a Behrend sequence . This concept has been a constant concern for Erd˝s during more o than fifty years: while, as he remarks in the above excerpt, the corresponding problem is easy when one considers a sequence of primes, or, more generally, a sequence of pairwise coprime integers, delicate and interesting questions arise immediately in the general case, corresponding to the study of strongly dependent random variables.

By the Davenport-Erd˝s theorem [13] quoted earlier, a necessary and sufficient condition o that A should be a Behrend sequence is that δ M A ( ) = 1 where δ stands for the logarithmic density. Thus, we have obviously that δ A = 1 is a sufficient condition for A to be a Behrend sequence. For a long time, I thought that this should have a simple, direct proof, but I could not find one that wasn't essentially equivalent to the Davenport-Erd˝s general and o deep result that d M A ( ) = δ M A ( ) for any sequence A . I eventually came up with the following.

Theorem 2. Let A be an integer sequence such that δ A = 1 . Then d M A ( ) = 1 .

Proof. Recall that we defined P + ( n ) as the largest prime factor of an integer n with the convention that P + (1) = 1. Symmetrically we let P -( n ) denote the smallest prime factor of n and set P -(1) = ∞ . For y /greaterorequalslant 1, let us write A y := { n ∈ A : P + ( n ) /lessorequalslant y } , n y := ∏ p ν ‖ n p /lessorequalslant y p ν . As n y ∈ M A ( ) implies n ∈ M A ( ), we plainly have for any fixed y /greaterorequalslant 1 and x →∞ ,

$$\text{and } x \rightarrow \infty, \\ \frac { 1 } { x } \sum _ { \substack { n \leqslant x \\ n \in M ( A ) } } \ 1 \geqslant \frac { 1 } { x } \sum _ { r \in M ( A _ { y } ) } \sum _ { s \leqslant x / r \\ P ^ { + } ( r ) \leqslant y } } \ 1 & = \frac { 1 } { x } \sum _ { r \in M ( A _ { y } ) } \left \{ \frac { x } { r } \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) + O ( 1 ) \right \} \\ & \rightarrow m ( y ) \coloneqq \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) \sum _ { \substack { r \in M ( A _ { y } ) } \\ P ^ { + } ( r ) \leqslant y } } \frac { 1 } { r }. \\ \text{There was an ink have to show that $m(\mu) \rightharpoonup 1$ as $m\rightharpoonup \sim W(\omega$ have to trivial/r$}$$

Thus, we only have to show that m y ( ) → 1 as y →∞ . We have trivially

$$m ( y ) \geqslant \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) \sum _ { r \in \mathcal { A } _ { y } } \frac { 1 } { r } \cdot \\ \psi \psi \psi \cdot \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \PSi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi\psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psigma \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \psi \vend{pmatrix}$$

Writing a for an element of A , we deduce from our hypothesis δ A = 1 that there is a non-increasing function ε x ( ) tending to 0 as x →∞ such that, for 1 /lessorequalslant y /lessorequalslant x ,

$$\{ 1 - \varepsilon ( x ) \} \log x \leqslant \sum _ { a \leqslant x } \frac { 1 } { a } \leqslant \sum _ { r \in \mathcal { A } _ { y } } \frac { 1 } { r } + \sum _ { \substack { n \leqslant x \\ P ^ { + } ( n ) > y } } \frac { 1 } { n }.$$

Setting u := (log x / ) log y , we may rewrite the last sum in (24) as

$$\text{Setting } u \coloneqq ( \log x ) / \log y, \, \text{we may rewrite the last sum in } ( 2 4 ) \, \text{as} \\ \sum _ { n \leqslant x } \frac { 1 } { n } - \sum _ { P ^ { + } ( n ) \leqslant y } \frac { 1 } { n } + \sum _ { \substack { n > x \\ P ^ { + } ( n ) \leqslant y } } \frac { 1 } { n } \\ \leqslant \log x + O ( 1 ) - \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) ^ { - 1 } + x ^ { - 1 / \log y } \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p ^ { 1 - 1 / \log y } } \right ) ^ { - 1 } \\ \leqslant \left \{ 1 + O ( e ^ { - u } \right \} \log x + O ( 1 ) - \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) ^ { - 1 }. \\ \text{Inserting back into } ( 2 4 ), \, \text{we get}$$

Inserting back into (24), we get

$$\sum _ { r \in \mathcal { A } _ { y } } \frac { 1 } { r } \geqslant \prod _ { p \leqslant y } \left ( 1 - \frac { 1 } { p } \right ) ^ { - 1 } + O \left ( 1 + \{ e ^ { - u } + \varepsilon ( x ) \} u \log y \right ).$$

It remains to select u = 1 / √ ε y ( ) and let y →∞ to obtain lim y m y ( ) = 1. /intersectionsq /unionsq

The paper [14] (see also [74], Exercises 247-249) contains another fundamental formula, viz.

$$\underline { d } \mathcal { M } ( A ) = \lim _ { T \to \infty } d \mathcal { M } ( \mathcal { A } \cap [ 1, T ] ).$$

We call the right-hand side the sequential density of the set of multiples M A ( ). From Behrend's fundamental inequality, valid for finite sequences, we hence deduce from (25) that

$$1 - \underline { d } \mathcal { M } ( \mathcal { A } \cup \mathcal { B } ) \geqslant \{ 1 - \underline { d } \mathcal { M } ( \mathcal { A } ) \} \{ 1 - \underline { d } \mathcal { M } ( \mathcal { B } ) \}$$

holds for all integer sequences A B , . (6) It follows in particular that

$$\sum _ { a \in \mathcal { A } } \frac { 1 } { a } = \infty$$

is a necessary condition for A to be a Behrend sequence, and that any tail A /integerdivide [1 , T ] of a Behrend sequence is still a Behrend sequence.

The structure of Behrend sequences long intrigued Erd˝s. The problem is indeed quite o intricate and even seemingly innocent questions, such as that of a criterion for A to be a Behrend sequence in the special case when the members of A only have a bounded number of, or even at most two, prime factors, do not have a simple answer: such a criterion is given in Ruzsa-Tenenbaum [64] in the case of two prime factors; in Erd˝s-Hall-Tenenbaum [29], o it is shown that d M A ( ) always exists when the number of prime factors is bounded but that this condition is optimal.

Another interesting feature of Behrend sequences, proved in [47], is that, if A is a Behrend sequence, then ∑ d n, d | ∈ A 1 →∞ pp.

Since it seems hopeless to find an effective criterion for the general situation, we are led to consider sequences with a special structure. The sequence E in (5) is one example. Another instance is that of block sequences, appearing implicitly in Erd˝s' formulation o above. As in [47], we formally define a block sequence by the property that it can be written in the form

$$\mathcal { A } = \bigcup _ { j \geqslant 1 } \mathcal { A } _ { j }, \quad \mathcal { A } _ { j } \coloneqq & [ T _ { j }, H _ { j } T _ { j } ] \cap \mathbb { N } ^ { * } \ \ ( j \geqslant 1 ),$$

where the (disjoint) blocks A j satisfy some growth condition that guarantees some local regularity, namely that, for some fixed parameter η &gt; 0,

$$1 + 1 / T _ { j } ^ { 1 - \eta } \leqslant H _ { j } \leqslant \min ( T _ { j }, T _ { j + 1 } / T _ { j } ) \quad ( j \geqslant 1 ).$$

When the T j grow sufficiently fast, we might then expect a Borel-Cantelli type criterion enabling us to decide whether A is a Behrend sequence according to whether a certain series involving the quantities d M A ( j ) diverges or not.

These questions have had a fairly wide posterity and many descendants. We refer the reader, in particular, to the papers [41], [47], [64], [73] and to the book [42], for a number of results and conjectures on Behrend sequences and uniform distribution on divisors. Here, we only quote two significant results which confirm, at least in the case of block sequences, that a criterion of Borel-Cantelli type is relevant.

6. This has been nicely improved by Ahlswede and Khachatrian [1].

In order to avoid technical hypotheses, we restrict to special cases which still reflect the general picture. We start with a result concerning the situation when the blocks are somewhat short. (7) The necessity part is due to Hall-Tenenbaum [47], and the sufficiency to Tenenbaum [72].

Theorem 3 ([47], [72]). Let A = ∪ j A j be a block sequence such that, for suitable real constants α γ , , σ , τ , with σ &gt; -1 , we have

Put σ 0 := (log 2) / (1 -log 2) and define

$$& \log ( T _ { j + 1 } / T _ { j } ) \asymp j ^ { \sigma } ( \log j ) ^ { \tau }, \quad \log H _ { j } \asymp ( \log j ) ^ { \gamma } / j ^ { \alpha } \quad ( j \to \infty ). \\ P i t \, \pi _ { \infty } \, \div = ( \log \sigma ) \, \slash / ( 1 - \log \sigma ) \, \text{ and define}$$

$$\lambda _ { 0 } ^ { \prime } ( \sigma ) \coloneqq \begin{cases} ( 1 - \log 2 ) ( \sigma _ { 0 } - \sigma ) & \text{if $-1<\sigma\leqslant\sigma_{0}$,} \\ \sigma _ { 0 } - \sigma & \text{if $\sigma>\sigma_{0}$.} \end{cases} \\ \text{Bhethread sequence if $\alpha<\alpha_{0}(\sigma)$ and $\mathcal{A}$ is not a Behrend sequence $i$}$$

Then A is a Behrend sequence if α &lt; α 0 ( σ ) and A is not a Behrend sequence if α &gt; α 0 ( σ )

.

Note that (28) implies σ + α &gt; 0 or σ + α = 0 and γ /lessorequalslant τ .

If we set σ = τ = γ = 0, we obtain that, provided 1 + c 1 /lessorequalslant T j +1 /T j /lessorequalslant 1 + c 2 for suitable constants c 1 &gt; 0, c 2 &gt; 0, and H j := 1 + 1 /j α ( j /greaterorequalslant 1), then the block sequence A is a Behrend sequence if α &lt; log 2 and is not if α &gt; log 2. This settles Erd˝s' conjecture o quoted above. His original claim was that the critical exponent α 0 should exist under the sole condition T j +1 /T j &gt; 1 + c 1 , but this cannot hold as it stands since it follows from theorem 1 of [47] that A is not a Behrend sequence for any α if we set, for instance, T j := exp exp j ( j /greaterorequalslant 1). However, he explained later on, in private conversation, that he really had in mind a two-sided condition.

From Behrend's inequality (26), the condition

$$\sum _ { j } d \mathcal { M } ( \mathcal { A } _ { j } ) = \infty$$

is necessary for a block sequence to be a Behrend sequence. However, this is in general much weaker than the sufficient condition obtained in [47]. For instance, if we assume, in the setting of Theorem 3, that -σ &lt; α /lessorequalslant 0 or that α = -σ /lessorequalslant 0 and γ &lt; τ , then we have from Ford's estimates in [38] that

$$\Delta _ { \Phi ( \mathcal { A } _ { j } ) } \asymp \frac { ( \log 2 j ) ^ { ( \gamma - \tau ) \delta - 3 / 2 } } { j ^ { ( \sigma + \alpha + 1 ) \delta } } \quad ( j \geqslant 1 ), \\ \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Phi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi_ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ {\Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phis } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi } \quad \Psi _ { \Phi }$$

where δ is as in (16), while Theorem 3 tells us that A is a Behrend sequence if

$$\sum _ { j } \frac { 1 } { j ^ { ( \sigma + \alpha + 1 ) \beta } } = \infty \\. \. \. \. \ - \.$$

for some β &gt; 1 -log 2 and, moreover, that A is not a Behrend sequence if the above series converges for some β &lt; 1 -log 2. Hence, we have a pseudo Borel-Cantelli criterion of the shape

$$\sum _ { j } \{ d \mathcal { M } ( \mathcal { A } _ { j } ) \} ^ { c + o ( 1 ) } = \infty,$$

with c := (1 -log 2) /δ ≈ 3 566509. It would be very interesting to have a probabilistic . interpretation for conditions of this type.

For the special sequence

$$\mathcal { A } _ { \lambda } \coloneqq \bigcup _ { j \geqslant 1 } ] \exp j ^ { \lambda }, 2 \exp j ^ { \lambda } ] \cap \mathbb { N } ^ { * },$$

a refined approach of the same technique yields in [47] a complete proof of Erd˝s' so o called B λ -conjecture (8) dating at least from the seventies and referred to in [46] pp. 49

7. See [72] for an explanation of the fact that any criterion for block Behrend sequences can be split into one in which the block are assumed to be short, in some precise way, and one in which the blocks are assumed to be long.

8. The name of the conjecture comes from the former notation B ( λ ) = M A ( λ ).

and 63: A λ is a Behrend sequence if, and only if, λ /lessorequalslant 1 / (1 -log 2). This is heuristically justified by the assumption that, for almost all n , the numbers (log d ) 1 /λ are uniformly distributed modulo 1 when d runs through the divisors of n . (9) However, the limiting case λ = 1 (1 / -log 2) is not covered by this argument and indeed needs a more delicate proof.

In the same spirit, and as a clear descendant of this class of problems, I quote the theorem of Kerner and myself [51], according to which

$$\min _ { d | n } \| d \vartheta \| = 1 / \tau ( n ) ^ { 1 + o ( 1 ) } \ \ p p,$$

provided the sequence of convergents { p /q j j } ∞ j =0 of the real number ϑ satisfies

$$\log q _ { j + 1 } < ( \log q _ { j } ) ^ { 1 + o ( 1 ) }.$$

Here we used the standard notation ‖ ‖ t = min n ∈ Z | t -n | . Note that, as explained in [51], it is easy to construct real numbers ϑ contravening (29). A challenging open question is to determine precisely the set of real numbers ϑ such that (29) holds. We know from [51] that (30) cannot be replaced by log q j +1 &lt; q (1 -ε / ) log 2 j with some ε &gt; 0.

When the blocks are long, in a suitable sense, we obtain a similar pseudo-criterion, but with c = 1- hence closer to a classical probabilistic approach.

Theorem 4 ([47]). Let A be a block sequence. Assume that, for some ε &gt; 0 , we have

$$\log H _ { j + 1 } > 2 ( \log T _ { j + 1 } ) ^ { \varepsilon } ( \log T _ { j } ) ^ { 1 - \varepsilon } \quad ( j \geqslant 1 ).$$

Then ∑( j log H j log T j ) δ 1 = ∞ for some δ 1 &gt; δ implies that A is a Behrend sequence, while

∑( j log H j log T j ) δ 2 &lt; ∞ for some δ 2 &lt; δ implies that A is not a Behrend sequence.

We refer the reader to chapter 1 of [42] for further results and comments on Behrend sequences. Once more, we see how fertile Erd˝ os' problems and conjectures revealed themselves along the years.

Erd˝ os follows with refined questions concerning the set of multiples of an interval. I slightly alter the notation in order to match subsequent works.

Denote by ε y, z ( ) the density of integers having a divisor d satisfying y &lt; d /lessorequalslant z and by ε 1 ( y, z ) the density of integers having precisely one divisor d , y &lt; d /lessorequalslant z . Besicovitch proved lim inf ε y, ( 2 y ) = 0 and I proved that if (log z / ) log y → 1 , then lim ε y, z ( ) = 0 [40] (chapter V). It is easy to see that this result is best possible, i.e. lim ε y, z ( ) = 0 implies (log z / ) log y → 1 .

Further I can prove that ε 1 ( y, z ) &lt; c/ (log y ) α for a certain 0 &lt; α &lt; 1 . Perhaps ε 1 ( y, z ) is unimodal for z &gt; y + 1 , but I know nothing about this. I do not know where ε 1 ( y, z ) assumes its maximum.

I am sure that ε 1 ( y, z ) /ε y, z ( ) → 0 for z = 2 y . If z -y is small then clearly ε 1 ( y, z ) /ε y, z ( ) → 1 and I do not know where the transition occurs.

Some time ago the following question occurred to me: let k be given and n &gt; n 0 ( k ) . Is there an absolute constant α so that for every n &lt; m /lessorequalslant n k there is a t , 0 &lt; t /lessorequalslant (log n ) α , so that m + t has a divisor in ] n, 2 n ] ? More generally: if n +1 = a 1 &lt; a 2 &lt; . . . is the sequence of integers which have a divisor d , n &lt; d /lessorequalslant 2 n , determine or estimate max a &lt;n i k ( a i +1 -a i ) .

9. This is actually proved in [66]. See also [45] and [73].

/negationslash

To my knowledge, the question of unimodality of ε 1 ( y, z ) as a function of z is still open. The last problem seems difficult and represents a deep open question. Let M x n ( ) denote the counting function of M (] n, 2 n ]) and set

Nearly all these questions are now essentially settled. In [70], I proved that if z -y →∞ and z /lessorequalslant y { 1+(log y ) 1 -log 4 e -ξ √ log 2 y } with ξ →∞ , then /rho1 1 ( y, z ) := ε 1 ( y, z ) /ε y, z ( ) → 1, while /rho1 1 ( y, z ) /greaterorequalslant e -c √ log y log 2 y when z 0 ( y ) := y { 1 + (log y ) 1 -log 4 } &lt; z /lessorequalslant 2 y . On seeing this, Erd˝ os changed his mind concerning the asymptotic behaviour of /rho1 1 ( y, z ) and conjectured that this quantity should tend to a positive limit for z = 2 . Ford [38] y then proved that /rho1 1 ( y, z ) /equivasymptotic 1 when y + 1 /lessorequalslant z /lessmuch y . Thus, the transition imagined by Erd˝ os should ideally be seen as a frontier between the cases when /rho1 1 ( y, z ) tends to 1 or to a constant less than 1. We still do not know whether /rho1 1 ( y, z ) tends to a limit when z 0 ( y ) &lt; z /lessmuch y but it follows from Ford's estimates in [38] that /rho1 1 ( y, z ) → 0 if z/y → ∞ . I conjecture that /rho1 1 ( y, z ) → 1 when y , z tend to infinity in such a way that z &gt; y { 1 + (log y ) 1 -log 4+ ε } .

$$M _ { n } ( x ) = \varepsilon _ { n } x + R _ { n } ( x ) \quad ( x \geqslant 1 ).$$

Then a i +1 -a i = { 1 -R n ( a i +1 ) + R n ( a i ) } /ε n . Since 1 /ε n /equivasymptotic (log n ) δ (log 2 n ) 3 / 2 , the first question amounts to asking whether max a i /lessorequalslant n k | R n ( a i +1 ) -R n ( a i ) | /lessmuch k (log n ) β for some β independent of k .

Note that Hall [42] studied the quadratic mean of R n ( x ). His lower bound implies that sup x | R n ( x ) | /greatermuch n c with c := 1 2 -log( π / 2 6) / log 4 ≈ 0 14098. However, he recently observed . [43] that the results obtained in [42] imply much more, namely

$$\sup _ { x } | R _ { n } ( x ) | > 2 ^ { \{ 1 + o ( 1 ) \} n / ( 2 \log n ) }.$$

This follows on noticing that ] n, 2 n ] = A ∪ B where A comprises all primes in the interval and B includes all remaining, composite integers. Then ( a, b ) = 1 whenever a ∈ A , b ∈ B . It only remains to apply equations (3.26), (3.10) and (3.20) from [42]. (10) Although this does not contradict Erd˝s' conjecture, it shows that it must be delicate. o

I conclude this survey of posterity and descendants of Erd˝s' paper [24] o by quoting a problem that was for him a constant concern even though he thought it might be intractable by any technique at our disposal. Here again, I slightly alter some notations and correct a confusion.

Finally I state an old problem of mine which is probably very difficult and which seems to be unattackable by the methods of probabilistic number theory: denote by P + ( n ) the greatest prime factor of n . Is it true that the density of integers n satisfying P + ( n +1) &gt; P + ( n ) is 1 2 ? Is it true that the density of integers for which

$$P ^ { + } ( n + 1 ) > P ^ { + } ( n ) n ^ { \alpha }$$

exists for every α ? Pomerance and I proved [32] that the upper density of the integers satisfying

$$n ^ { - \varepsilon } < P ^ { + } ( n + 1 ) / P ^ { + } ( n ) < n ^ { \varepsilon }$$

tends to 0 with ε .

Let E := { n /greaterorequalslant 1 : P + ( n ) &gt; P + ( n +1) . The conjecture that } E has asymptotic density 1 2 stems for the general hypothesis that n and n +1 should be multiplicatively independent. It lies in the same class of problems than the famous abc -conjecture.

10. The author takes pleasure in thanking Richard R. Hall for letting him include this proof here.

A general theorem of Hildebrand [49] implies that E has positive lower asymptotic density, but I did not check the numerical value that can be derived from this result. In [32] it is shown that if N is large, then for at least 0 0099 . N values of n /lessorequalslant N we have P + ( n ) &gt; P + ( n +1), and for at least 0 0099 . N values of n /lessorequalslant N we have P + ( n ) &lt; P + ( n +1). It follows from theorem 1.2 of [6] that each inequality occurs on a set of integers n of lower asymptotic density

$$\log \left ( \frac { 1 } { 1 - c } \right ) - 2 \int _ { 0 } ^ { c } \log \left ( \frac { 1 - v } { 1 - v - 2 c } \right ) \frac { \mathrm d v } { 1 - v }$$

provided 0 &lt; c &lt; 1 / 5. The maximum of this expression is greater than 0 05544, which . improves the result from [32].

In [32] it is shown that P + ( n ) &lt; P + ( n + 1) &lt; P + ( n + 2) holds infinitely often, and it is conjectured that too P + ( n ) &gt; P + ( n + 1) &gt; P + ( n + 2) holds infinitely often. This conjecture was proved by Balog [2].

Among several, two further very interesting problems are described in Erd˝s' seminal o article. I chose not to discuss them in detail since they lie somewhat aside of the main stream of the paper, concentrated on the distribution of divisors and typical multiplicative structure of integers.

Thus, I only mention (too) briefly the questions of the number Φ( x ) of distinct values of Euler's totient ϕ n ( ) in [1 , x ] and that of an infinite sequence { p j } ∞ j =1 of primes such that p j +1 ≡ 1 (mod p j ) ( j /greaterorequalslant 1).

On the first problem, a crucial and impressive progress was made by Ford [37]. Improving on results by Pillai [58], Erd˝s [17], [19], Erd˝s-Hall [25], [26], Pomerance [60] and Maiero o Pomerance [54], he could show that, for large x , we have

$$\Phi ( x ) \asymp \frac { x } { \log x } \text{e} ^ { C ( \log _ { 3 } x - \log _ { 4 } x ) ^ { 2 } } ( \log _ { 2 } x ) ^ { D } ( \log _ { 3 } x ) ^ { E },$$

where C and D are positive, explicitly defined constants and E = D -2 C + 1 2 .

On the second problem, Erd˝s asks whether we necessarily have o lim p 1 /j j = ∞ and expresses the belief that p j &lt; exp { j (log j ) 1+ (1) o } is possible. To my knowledge, both questions are still open. However, Ford, Konyagin and Luca made significant progress in [39].

In conclusion and in the spirit described in the introduction of this article, I hope that this paper will meet two goals. The first is, as for any survey paper, to set records straight, isolate problems and stimulate further research.

Intimately linked to the personality of this so special and so moving (in every sense) man Paul Erd˝ os was, the second goal consists in modestly helping to maintain a fair picture of his offering to mathematics. His problems have too often been considered as tricky, disconnected questions. All those who worked with him for some time will agree that, even unformulated, he had in mind the bases of many theories and of even more links between these theories. Now that he can read in the Great Book all answers to his innumerable questions, and indeed select the most elegant ones, no doubt he grins once in a while, realizing how close he has been and pondering how many clues he left for us, even if we still cannot understand them all.

Acknowledgements. The author takes pleasure in expressing here warm thanks to R. Balasubramanian, N. Bingham, R. de la Bret` eche, C. Dartyge, I.Z. Ruzsa and T. Stoll for their help during the preparation of this paper.

## References

- [1] R. Ahlswede &amp; L.H. Khachatrian, Density inequalities for sets of multiples, J. Number Theory 55 n o 2 (1995), 170-180.

[2]

A. Balog, On triplets with

descending largest prime factors,

Studia

Sci.

Math. Hungar.

38

(2001), 45-50.

- [3] F.A. Behrend, Three reviews; of papers by Chowla, Davenport and Erd˝s, o Jahrbuch ¨ber die u Forschritte der Mathematik 60 (1935), 146-149.
- [4] F.A. Behrend, Generalizations of an inequality of Heilbronn and Rohrbach, Bull. Amer. Math. Soc. 54 (1948), 681-684.
- [5] A.S. Besicovitch, On the density of certain sequences, Math. Annalen 110 (1934), 336-341.
- [6] R. de la Bret`che, C. Pomerance &amp; G. Tenenbaum, On products of ratios of consecutive integers, e Ramanujan J. 9 (2005), 131-138.
- [7] R. de la Bret`che &amp; G. Tenenbaum, Sur les lois locales de la r´partition du e e k -i`me diviseur d'un e entier, Proc. London Math. Soc. (3) 84 (2002), 289-323.
- [8] R. de la Bret`che &amp; G. Tenenbaum, Oscillations localis´es sur les diviseurs, e e J. London Math. Soc. (2) 85 (2012) 669-693.
- [9] R. de la Bret`che &amp; G. Tenenbaum, Moyennes de fonctions arithm´ etiques de formes binaires, e Mathematika , to appear.
- [10] R. de la Bret`che &amp; G. Tenenbaum, Conjecture de Manin pour certaines surfaces de Chˆtelet, e a preprint.
- [11] S. Chowla, On abundant numbers, J. Indian Math. Soc. (2) 1 (1934), 41-44.
- [12] H. Davenport, Uber numeri abundantes, ¨ Sitzungsber. Preuß. Akad. Wiss. , Phys.-Math. Kl. 2629 (1933), 830-837.
- [13] H. Davenport &amp; P. Erd˝s, On sequences of positive integers, o Acta Arith. 2 (1937), 147-151.
- [14] H. Davenport &amp; P. Erd˝s, On sequences of positive integers, o J. Indian Math. Soc. 15 (1951), 19-24.
- [15] J.-M. De Koninck &amp; G. Tenenbaum, Sur la loi de r´ epartition du k -i`me facteur premier d'un e entier, Math. Proc. Camb. Phil. Soc. 133 (2002), 191-204.
- [16] P. Erd˝s, On the density of the abundant numbers, o J. London Math. Soc. 9 , n o 4 (1934), 278-282.

[17]

P. Erd˝s, On the normal number of prime factors of

o

p

-

1 and some related problems concerning

Euler's

ϕ

-function,

Quart. J. Math. (Oxford)

6

(1935), 205-213.

[18]

P. Erd˝s, A generalization of a theorem of Besicovitch,

o

J. London Math. Soc.

11

(1936), 92-98.

- [19] P. Erd˝s, Some remarks on Euler's o ϕ -function and some related problems, Bull. Amer. Math. Soc. 51 (1945), 540-544.
- [20] P. Erd˝ os, On the density of some sequences of integers, Bull. Amer. Math Soc. 54 (1948), 685-692.
- [21] P. Erd˝s, On some applications of probability to analysis and number theory, o J. London Math. Soc. 39 (1964), 692-696.
- [22] P. Erd˝s, On the distribution of prime divisors, o Aequationes Math. 2 , (1969), 177-183.
- [23] P. Erd˝s, Problem 218 and solution, o Canad. Math. Bull. 17 (1974), 621-622.
- [24] P. Erd˝s, Some unconventional problems in number theory, o Ast´ erique 61 (1979), 73-82, Soc. math. France.
- [25] P. Erd˝s &amp; R.R. Hall, On the values of Euler's o ϕ -function, Acta Arith. 22 (1973), 201-206.
- [26] P. Erd˝s and R.R. Hall, Distinct values of Euler's o ϕ -function, Mathematika 23 (1976), 1-3.
- [27] P. Erd˝s &amp; R.R. Hall, The propinquity of divisors, o Bull. Lodon Math. Soc. 11 (1979), 304-307.
- [28] P. Erd˝ os &amp; M. Kac, The Gaussian law of errors in the theory of additive number theoretic functions, Amer. J. Math. 62 (1940), 738-742.
- [29] P. Erd˝s, R.R. Hall &amp; G. Tenenbaum, On the densities of sets of multiples, o J. reine angew. Math. 454 (1994), 119-141.
- [30] P. Erd˝s &amp; J.-L. Nicolas, R´partition des nombres superabondants, o e Bull. Soc. Math. France 103 (1975), 65-90.
- [31] P. Erd˝s &amp; J.-L. Nicolas, M´thodes probabilistes et combinatoires en th´orie des nombres, o e e Bull. sc. math. (2) 100 (1976), 301-320.
- [32] P. Erd˝s &amp; C. Pomerance, On the largest prime factors of o n and n +1, Aequationes Math. 17 (1978), no. 2-3, 311-321.
- [33] P. Erd˝s &amp; G. Tenenbaum, Sur la structure de la suite des diviseurs d'un entier, o Ann. Inst. Fourier (Grenoble) 31 , 1 (1981), 17-37.
- [34] P. Erd˝s &amp; G. Tenenbaum, Sur les diviseurs cons´cutifs d'un entier, o e Bull. Soc. Math. de France 111 (1983), 125-145.
- [35] P. Erd˝s &amp; G. Tenenbaum, Sur les densit´ es de certaines suites d'entiers, o Proc. London Math. Soc., (3) 59 (1989), 417-438.
- [36] P. Erd˝s &amp; G. Tenenbaum, Sur les fonctions arithm´ etiques li´es aux diviseurs cons´cutifs, o e e J. Number Theory, 31 (1989), 285-311.
- [37] K. Ford, The distribution of totients, Ramanujan J. 2 (1998), n os 1-2, 67-151.
- [38] K. Ford, The distribution of integers with a divisor in a given interval. Ann. of Math. (2) 168 , n o 2 (2008), 367-433.
- [39] K. Ford, S.V. Konyagin &amp; F. Luca, Prime chains and Pratt trees, Geom. Funct. Anal. 20 n o 5 (2010), 1231-1258.

- [40] H. Halberstam &amp; H.-E. Richert, Sieve Methods , Academic Press, London, New York, San Francisco, 1974.
- [41] R.R. Hall, Sets of multiples and Behrend sequences, A tribute to Paul Erd˝s o , 249-258, Cambridge Univ. Press, Cambridge, 1990.
- [42] R.R. Hall, Sets of multiples , Cambridge Tracts in Mathematics, 118, Cambridge University Press, Cambridge, 1996.
- [43] R.R. Hall, Private communication, November 11, 2012.
- [44] R.R. Hall &amp; G. Tenenbaum, On the average and normal orders of Hooley's ∆-function, J. London Math. Soc (2) 25 (1982), 392-406.
- [45] R.R. Hall &amp; G. Tenenbaum, Les ensembles de multiples et la densit´ divisorielle, e J. Number Theory 22 (1986), 308-333.
- [46] R.R. Hall &amp; G. Tenenbaum, Divisors , Cambridge tracts in mathematics 90, Cambridge University Press (1988, paperback ed. 2008).
- [47] R.R. Hall &amp; G. Tenenbaum, On Behrend sequences, Math. Proc. Camb. Phil. Soc. 112 (1992), 467-482.
- [48] K. Henriot, Nair-Tenenbaum bounds uniform with respect to the discriminant, Math. Proc. Camb. Phil. Soc. 152 (2012),n o 3, 405-424.
- [49] A. Hildebrand, On a conjecture of Balog, Proc. Amer. Math. Soc. 95 , n ◦ 4 (1985), 517-523.
- [50] C. Hooley, A new technique and its applications to the theory of numbers, Proc. London Math. Soc. (3) 38 (1979), 115-151.
- [51] S. Kerner &amp; G. Tenenbaum, Sur la r´ epartition divisorielle normale de ϑd (mod1), Math. Proc. Camb. Phil. Soc. 137 (2004), 255-272.
- [52] P. L´ evy, Th´ eorie de l'addition des variables al´atoires e , Gauthier-Villars, Paris (1937, 2nd ed. 1954).
- [53] H. Maier, On the M¨bius function, o Trans. Amer. Math. Soc. 301 , n o 2 (1987), 649-664.
- [54] H. Maier &amp; C. Pomerance, On the number of distinct values of Euler's ϕ -function, Acta Arith. 49 (1988), 263-275.
- [55] H. Maier &amp; G. Tenenbaum, On the set of divisors of an integer, Invent. Math. 76 (1984), 121-128.

[56]

H. Maier &amp; G. Tenenbaum, On the normal concentration of divisors, 2,

Math. Proc. Camb. Phil.

Soc.

147

n

o

3 (2009), 593-614.

- [57] M. Nair &amp; G. Tenenbaum, Short sums of certain arithmetic functions, Acta Math. 180 , (1998), 119-144.
- [58] S. Pillai, On some functions connected with ϕ n ( ), Bull. Amer. Math. Soc. 35 (1929), 832-836.
- [59] G. P´ olya &amp; G. Szeg˝, o Problems and theorems in analysis, II , Classics in Mathematics, SpringerVerlag, Berlin, 1998.
- [60] C. Pomerance, On the distribution of the values of Euler's function, Acta Arith. 47 (1986), 63-70.
- [61] A. Raouj, Sur la densit´ de certains ensembles de multiples, I, II, e Acta Arith. 69 , n o 2 (1995), 121-152, 171-188.
- [62] A. Raouj, A. Stef &amp; G. Tenenbaum, Mesures quadratiques de la proximit´ des diviseurs, e Math. Proc. Camb. Phil. Soc. 150 (2011), 73-96.
- [63] O. Robert, Sur le nombre des entiers repr´sentables comme somme de trois puissances, e Acta Arith. 149 n o 1 (2011), 1-21.
- [64] I.Z. Ruzsa &amp; G. Tenenbaum, A note on Behrend sequences, Acta Math. Hung. 72 , n o 4 (1996), 327-337.
- [65] A. Stef, L'ensemble exceptionnel dans la conjecture d'Erd˝s o concernant la proximit´ e des diviseurs , Th` ese de doctorat de l'Universit´ Nancy 1, UFR STMIA, juin 1992. e
- [66] G. Tenenbaum, Sur la densit´ e divisorielle d'une suite d'entiers, J. Number Theory 15 , n ◦ 3 (1982), 331-346.
- [67] G. Tenenbaum, Sur la probabilit´ qu'un entier poss`de un diviseur dans un intervalle donn´, e e e Compositio Math. 51 (1984), 243-263.
- [68] G. Tenenbaum, Sur la concentration moyenne des diviseurs, Comment. Math. Helvetici 60 (1985), 411-428.
- [69] G. Tenenbaum, Fonctions ∆ de Hooley et applications, S´ eminaire de Th´orie des nombres, Paris e 1984-85, Prog. Math. 63 (1986), 225-239.
- [70] G. Tenenbaum, Un probl` eme de probabilit´ conditionnelle en Arithm´tique, e e Acta Arith. 49 (1987), 165-187.
- [71] G. Tenenbaum, Sur une question d'Erd˝s et Schinzel, II, o Inventiones Math. 99 (1990), 215-224.
- [72]
- G. Tenenbaum, On block Behrend sequences, Math. Proc. Camb. Phil. Soc. 120 (1996), 355-367.
- [73] G. Tenenbaum, Uniform distribution on divisors and Behrend sequences, L'Enseignement Math´ ematique 42 (1996), 153-197.
- [74] G. Tenenbaum, Introduction ` la th´orie analytique et probabiliste des nombres a e , third ed., coll. ´ chelles, Belin, 2008, 592 pp. E
- [75] R.C. Vaughan, Sur le probl`me de Waring pour les cubes, e C. R. Acad. Sci. Paris S´r. I Math. e 301 , n o 6 (1985), 253-255.

Universit´ Henri Poincar´-Nancy 1 e e BP 239

54506 Vandœuvre Cedex

France

internet: gerald.tenenbaum@iecn.u-nancy.fr
Gérald Tenenbaum
Some of Erd\H os' unconventional problems in number theory, thirty-four years later
We give an historical account, including recent progress, on some problems of
Erd\H os in number theory.