The distribution of integers with a divisor in a given interval By Kevin Ford Abstract We determine the order of magnitude of H(x; y; z), the number of in-tegers n x having a divisor in (y; z], for all x; y and z. We also study Hr (x; y; z), the number of integers n x having exactly r divisors in (y; z]. When r = 1 we establish the order of magnitude of H1 (x; y; z) for all x; y; z sat-isfying z x 1=2 " . For every r 2, C > 1 and " > 0, we determine the order of magnitude of Hr (x; y; z) uniformly for y large and y + y=(log y) log 4 1 " z min(y C ; x 1=2 " ). As a consequence of these bounds, we settle a 1960 con-jecture of Erd}os and some conjectures of Tenenbaum. One key element of the proofs is a new result on the distribution of uniform order statistics. Contents 1. Introduction 2. Preliminary lemmas 3. Upper bounds outline 4. Lower bounds outline 5. Proof of Theorems 1, 2, 3, 4, and 5 6. Initial sums over L(a; ) and Ls (a; ) 7. Upper bounds in terms of S (t; ) 8. Upper bounds: reduction to an integral 9. Lower bounds: isolated divisors 10. Lower bounds: reduction to a volume 11. Uniform order statistics 12. The lower bound volume 13. The upper bound integral 14. Divisors of shifted primes References 1. Introduction For 0 < y < z, let (n; y; z) be the number of divisors d of n which satisfy y < d z. Our focus in this paper is to estimate H(x; y; z), the number of positive integers n x with (n; y; z) > 0, and Hr (x; y; z), the number of 368 KEVIN FORD n x with (n; y; z) = r. By inclusion-exclusion, H(x; y; z) = X k1 ( 1) k 1 X y<d1<<dkz x lcm[d 1 ; ; d k ] ; but this is not useful for estimating H(x; y; z) unless z y is small. With y and z xed, however, this formula implies that the set of positive integers having at least one divisor in (y; z] has an asymptotic density, i.e. the limit "(y; z) = lim x!1 H(x; y; z) x exists. Similarly, the exact formula Hr (x; y; z) = X kr ( 1) k r k r X y<d1<<dkz x lcm[d 1 ; ; d k ] implies the existence of " r (y; z) = lim x!1 Hr (x; y; z) x for every xed pair y; z. 1.1. Bounds for H(x; y; z). Besicovitch initiated the study of such quan-tities in 1934, proving in [2] that (1.1) liminf y!1 "(y; 2y) = 0; and using (1.1) to construct an in nite set A of positive integers such that its set of multiples B(A ) = fam : a 2 A ;m 1g does not possess asymptotic density. Erd}os in 1935 [5] showed lim y!1 "(y; 2y) = 0 and in 1960 [8] gave the further re nement (see also Tenenbaum [38]) "(y; 2y) = (log y) +o(1) (y ! 1); where = 1 1 + log log 2 log 2 = 0:086071 : : : : Prior to the 1980s, a few other special cases were studied. In 1936, Erd}os [6] established lim y!1 "(y; y 1+u ) = 0; provided that u = u(y) ! 0 as y ! 1. In the late 1970s, Tenenbaum ([39], [40]) showed that h(u; t) = lim x!1 H(x; x (1 u)=t ; x 1=t ) x exists for 0 u 1, t 1 and gave bounds on h(u; t).