Divisors (Cambridge Tracts in Mathematics)

1 - p)

<< 0x (log t)y-'

uniformly for 0 < y < yo, by Theorem 01. Let X(n) denote the characteristic function of the set of integers n for which Ico(n, t) - loge tI I> E loge t.

We apply (0.23) with N = (1- E) loge t and y = 1 - E, and (0.24) with

0 Preliminaries

8

N = (1 + 8) 1092 t and y = 1 + s, to obtain Y X(n) << x(log t)-Q(1 -E) + x(log t)-Q(1 +E) n < x

with Q as in (0.22). Since Q(1 + u) = Zu2 +O(u3) (Jul 51), we obtain our result on setting s =)/i(t)/.,/log2 t. An analysis of the above proof shows that it belongs to the same family as Rankin's method: one tries to mimic the characteristic function of a certain set of integers by a multiplicative function which is easy to sum. The choice of this multiplicative function is of course crucial and is usually performed in two steps: first the general shape is determined, allowing a free parameter (e.g. (x/n)a in Rankin's method, y'(") in the proof of Theorem 010), and secondly this parameter is optimized. Thus the idea of the proof of Theorem 010 is that the sum E yro(n,t) n5x

is dominated by the n for which cw(n, t) = (y + 0(1)) loge t. This had already

been noticed by Turan in the case t = x (see the Notes). The method is still effective in the study of large deviations.

9

Notes on Chapter 0 §0.2.

The Halberstam-Richert theorem generalizes a result of Hall (1974).

Although we are not yet able to take advantage of this in many of our applications, it should be noticed that the constant x on the right of (0.3) is sharp. To see this, set

'k

P(f, x) = F1 (

P

p

p2

so that (0.3), (0.4) and Mertens' Theorem yield f (n) 5 keyxP (f,x)(1+0( nSx

(1)

lolg x))'

Set

0

f(W")

(p 5 x/log x),

K (x/lOgx
The left-hand side of (1) is - Kn(x), and P(f, x) - e -1/log x. A more precise form of the inequality (0.4) was found by Hildebrand (1984). This has the effect of multiplying the right-hand side of (1) by a factor 5 1, depending on f. The more often f (p) > 1 for p > x`, the better the gain, but nothing more than a factor (e ' + o(1)) can be expected here: Hildebrand

(1984a) stated that when f :Z

y lolx g n<x

[0, 1] it may be shown elementarily that fnn)> P(f,x) (1+0(logX g

By Rankin's method, we mean the device of majorizing the characteristic function of the set {n: n 5 x} by the weight (x/n)Q with a suitable a > 0 which may be optimized. This can be surprisingly effective, cf. Rankin (1938).

The usual form of the right-hand side in Theorem 04, obtained by contour integration, is ((for x > 2),

y x log' - l x { 1+ lagyx + ... + logN x +0 (logN+ CN(Y)

T

l

x)}.

For a recent study of kP(x, y), in particular an estimate of the loss involved in Rankin's method, see Hildebrand & Tenenbaum (1986). This paper contains an extensive list of references to previous work on q'(x,y). The proof of Theorem 06 suggested in Exercise 02 is quite different from that of Halberstam & Roth (1966) (q.v.). A stronger form of Theorem 07 appears in Tenenbaum (1984). In particular we have §0.3.

O(x,y,z)<xexp{

loge u -u(logu+log2U-1+0(09 logu ))

0 Preliminaries

10

with u: = log z/logy, uniformly for u < y'12

E.

Turin's variance proof of the Hardy-Ramanujan theorem is now classical - see e.g. Elliott (1979) - and is regarded as the actual birth of Probabilistic Number Theory. In the same year, 1934, Turin noticed in his Doctoral Dissertation (published in Hungarian) that the theorem could also be proved analytically, starting with the asymptotic formula (uniform §0.5.

for suitable y),

Y_ Y" =(C(Y)+o(1))xlogy

x,

(2)

n<x

obtained by contour integration. This is explained in detail by Elliott (1979,

Part II, pp. 18-20) where an enlightening letter of Turin is quoted. As Turin remarked, (2), extended to complex y, is closer to the Erdos-Kac Theorem than to the Hardy-Ramanujan Theorem. On the other hand the method set out in §0.5 requires just the 0-form of (2). This explains the fairly wide range of applicability of the principle: the finer analytical tools which

are not always available are replaced by simple and general inequalities such as that of Halberstam and Richert.

11

Exercises on Chapter 0 00. Let f satisfy the conditions in Theorem Y_{ f (n): n 5 x}, M(x) _ F{ f (n)/n: n 5 x}. Prove

01 and set S(x) = that

S(x) log x 5

S1 + S2 + S3 where

S 1= Y-f(p) log p Y- f (M), p<x

m<x/p

S2 = Y- E f (p°) log pv Y- f (m) m<x/p°

v,>2p°<s

and S3 5 xM(x). Prove that S1 < AxM(x), and, by first showing that S(z) < zM(z), for any z, prove that S2 ,< BxM(x). Deduce the Theorem. 01.

Let y >, 2, s << 1/logy. Prove that

(pE-1)=0(1). YP

p
Let X(n, y) = 1 if P' (n) < y, = 0 else. Show that, for s > 0, `P(x, y)

Jx + E (_)cXfl, y) n<x

(V)

and apply Theorem 01 to the sum on the right, and choose e suitably, to prove (0.15). 02.

By means of Theorem 02, show that 1

dl (x, z) = x f 1 - - + O(x/log2 z), p
P

uniformly for x > exp(2 log z loge z). Show that'D(x, z) << x/log z (2 < z <, x) by using Theorem 01, and that D(x, z) ,>it(x) - it(z) >>x/log z for

xl/4 < z < -2x by the Prime Number Theorem. Now let 2 < z < x 1/4. By means of the inequality log x >, Y_ {log p: p I n} (1 <, n <, x), show that, for x > x0,

I(x, z) log x >>x Y- X(m)/m M -<'/X

where X is the multiplicative function such that X(p) = 1 (z < p <, x1/3), X(p") = 0 (else). Prove that

Y X(m) m

(1+_)_2 /

-

X(m) log m

m logx

By logarithmically differentiating rj(1 + p-S) at s = 1, or otherwise, prove

Preliminaries

0

12

that the sum on the right is 113(1

+pJ

and hence complete the proof of Theorem 06. 03.

Show that 0(x, y, z) < E (D (x/a, y) + `1' (x, y), z
and deduce Theorem 07, using in turn Theorems 01, 05 and partial summation. 04.

Show that, for y

)1 respectively,

card {n < x: w(n) < (>,)y log log x} << 0 x(log x) - Q(y),

(with Q as in (0.22)) uniformly in any finite range 0 < y < yo. Show that, provided yo < 2, these estimates hold with co replaced by Q. 05.

By writing y'(n) = Eding(d), prove that, for 1 < y < 2,

Yn(n)<x n n<x

(l +Y- 11<< xl°gx

psx

p - Y

2 --y

By choosing y = 2 - 1/k, prove that k

card {n < x: S1(n) = k} << xk 2 _ log x,

uniformly for k 1, x > 2. This improves on Erdos-Sarkozy (1980); for an asymptotic formula see Nicolas (1984). 06.

Let S be fixed, 0 < 6 < 2, and set sl(S): = (m: m >, 3, w(m) 5 (2 + S) loge m}.

Show that dd(S) = 0. The remainder of this exercise is devoted to proving

Y 1 - i(n)

p.p.

dIn

dEd(d)

(a) Show that, for any fixed ce(0,1), card { p: pin, loge p > (1 - e) loge n} - ew(n) P.P.,

card {d: din, loge d > (1 -8)1092n) - i(n) p.p.

(1)

Exercises on Chapter 0

13

(b) Establish the inequality Yru(d)

, (1 + y)'(") (y 3 0, n e Z ),

din

and use it to prove that, for any ne(0, Z card {d: din, cw(d), (2 + ry)S2(n)} - i(n) p.p.

Deduce (1). [d (8) is an example of a sequence having asymptotic density 0 and divisor

density 1- see the Notes on Chapter 3 and Hall (1978) for the definition of divisor density, and for further developments Hall (1981), Tenenbaum (1982), Dupain, Hall & Tenenbaum (1982), Hall & Tenenbaum (1986)].

1

The normal distribution of the prime factors 1.1

The law of the iterated logarithm

The distribution of the prime factors of an integer determines that of the divisors: in order to study the latter in principle we only need to know the behaviour of the step-function 0(n, t): = Y, a P'lln P
For the reason explained below, we ignore multiplicity and consider instead w(n, t):

Y1

.

pin

p
If fi (n) -+ oo as n -+ oo, we have S2(n, t) - w (n, t) <, 0(n) - co (n) < fi (n) p.p.

(because Y_ p- 2 < oo), and, within the approximations in the following theorems, the two functions are interchangeable. In this chapter we are concerned primarily with normal behaviour: our interest is in properties of integers belonging to a suitable sequence of asymptotic density 1. Let fi (t) -* oo as t -+ oo, 0 (t) << (log2 t)' "6. We have seen in Theorem 010

that, for fixed t, 2 < t < x, the inequality Iw(n, t) -1og2 ti < 0) ",/1092 t

(1.1)

holds for all except << x exp (- (>li (t))2) of the integers n < x. Thus we Z essentially know p.p.x the pointwise behaviour of w(n, t). This is insufficient for our purpose: we need a uniform approximation for co(n, t) as t varies if we are to describe the distribution of the divisors, and our aim now is to achieve an optimal result of this sort. We begin with an

easy first attempt, just taking advantage of the explicit bound for the number of exceptions to (1.1). Theorem 10. Let c (x) -> oo as x -> oo. For each fixed s > 0 we have

lw(n, t) -loge tl < (1 + e)/(2 1og2

t 1< x)

p.p.x.

(1.2)

1

The law of the iterated logarithm

15

We restate this as a result about the sequence {p;(n): 1 <j <, co(n)} of distinct prime factors of n. Corollary. Let fi(n) -* co as n ->oo. Then 11092 p (n) -j j < (1 + E) J(2j logj) (fi(n) <j < co(n)) p.p.

(1.3)

This is immediate from (1.2), taking t = p;(n).

Proof of Theorem 10. We remark that, since (o (n, t) is non-decreasing, it will be sufficient to prove that (1.2) holds, with r replaced by e/2, at a set of , provided loge tk+ 1- loge tk < discrete checkpoints tk, t1 < t2 <

6",100924-10934) and E'=d(e)

is

sufficiently small. We put tk =

exp exp k, and >li(t) = J((2 + 2s) log3 t) in (1.1). This gives the desired inequality at all the checkpoints in the range fi(x) < tk < x, and a total of

Y xk-1-`=o(x)

<< k>_

exceptional integers n <x. This completes the proof. Next, we envisage the best possible form of Theorem 10. Let XP denote the

characteristic function of the multiples of p; then it is fundamental in Probabilistic Number Theory that the XP behave in many respects like independent random variables - this is the basis of the Kubilius Model (cf. Elliott (1979)). Now we have co(n,t) _

xP(n) p5t

and the expectation of the right-hand side is Y_ { 1/p: p < t} =1og2 t + 0(1); if

the law of the iterated logarithm applied we should have limsup A(n, t) = + 1, liminf A(n, t) = - 1 p.p.,

(1.4)

where

(n, t) - loge t J(21og2 t. log, t)'

A(n, t):= (0

in particular the 1093 t in (1.2) would become logo t. Erdos (1946) announced (1.4) without proof. We supply the details here, since the matter is not as straightforward as might be assumed - see also the Notes. The general principle described in §0.5 will be employed systematically to ease the technical computations, playing effectively the role of the so called `exponential bounds' which occur in probability theory. Theorem 11. Let (x) -+ oo as x -> oo. Then IA(n,t)I < 1 + E

(c(x) < t ,<x)

p.p.x.

(1.5)

16

The normal distribution of the prime factors

1

Furthermore, if g(x) increases sufficiently slowly, we have

inf A(n, t) <, - 1 + e, sup A(n, t) > 1- a p.p.x. (x)
(1.6)

fi(x)
Proof of Theorem 11. We begin with (1.5). First we observe that we may restrict our attention to the range fi(x) < t < xl : = exp exp (loge x - fi(x)), provided the growth of (x) is sufficiently slow. For, if t > x1, we have

Ico(n,t)-log2tl x

p.p.x;

to see this, notice first that, since

Y (w(n)-(o(n,xl)),< n<x

Y x/p<< x1
plainly w(n) - w(n, x1) < fi(x) Jlog2 x p.p.x - a 3

similar bound for

Iw(n) -log2xl follows from the Hardy-Ramanujan Theorem. We shall therefore have

sup IA(n,t)l =o(1) p.p.x x1
provided, and we assume this henceforth, fi(x) = o(,/log4 x).

Second, we note that we may also neglect a priori those integers n z x which do not satisfy 11

p"5x14.

(1.8)

P" Iln

P<x1

Indeed by Theorem 07 the number of exceptional n 5x is o(x). Now let S be the set of integers n 5 x such that (1.8) holds. We are going to prove card {neS: sup

IA(n, t)I > 1 + e} = o(x).

(1.9)

fi(x)
In order to modify the proof of Theorem 10 we need checkpoints Tj increasing so rapidly that the series Y_ exp (- zj (Tj)2) is convergent, with T). However, we cannot then obtain a 0(T) essentially (1 + satisfactory bound for Iw(n, t) - loge tl between the checkpoints merely from the monotonicity of w(n, t), and another idea - involving some technical complication - is needed. Basically this is to use the old checkpoints as well, and to appeal to Theorem 01 to estimate l w(n, tk) - co(n, Tj) - (loge tk 1092 Tj)I when tkE(Tj, Tj+1]. As before we put tk = exp exp k (k > 1); it will be sufficient to prove (1.9) with t confined to the sequence {tk}, and is replaced by a/2. For convenience

1

The law of the iterated logarithm

17

we write s/2 = b. We set I =16-'1093 (x)], J = [b -1 log3 x, ] + 1, and, for each j, I < j 5 J, we write K3 = exp (b j) so that K1 I< loge fi(x), K j> loge x,. The new checkpoints are T3 = exp exp K; = exp exp exp 6j and for each of

these j we denote by SJ the set of those neS such that sup

IA(n, tk)I > 1 + b,

(Si)

K1
and by A J the set of those n < x for which

(A)

Iw(n,TJ+1)-log2TJ+iI >ii(T;).,/log2T;, where we shall actually take ,Ii(T) = (1 + 6),1(21og4 T) - c,

with a suitably large constant c (to be specified later). We show that

Z card Si = o(x). 15153

In fact we shall prove that, for x > xo(b), we have card S; < 2 card A3

(I <j <, J),

(1.10) (1.11)

cardAJ<< xj-1-614 (I'<jSJ),

thus establishing (1.9) and so (1.5). The proof of (1.11) is easy. Condition (A3) implies for x > xo(b) that Iw(n, TJ+1) -1og2 TJ+, I > (1 + 30),J(21og2

TJ)

and, noticing that log2TJ=e-S1og2TJ+,, and substituting ',(TJ+,)_ (1 +3b),/(2e-alog4 T) in (1.1), we see that (1.11) follows.

To obtain (1.10), we split SJ into KJ+, - KJ disjoint subsets SJ,k, KJ < k < KJ+,, defined by the conditions max IA(n, tm)I < 1 + b < IA(n, tk)I

(SJ,k)

K1<m
Evidently card SJ <

Y-

card SJ,k.

(1.12)

K1
Let BJ,k c S comprise the integers satisfying the extra condition I w(n, TJ+,) - w(n, tk) - (loge TJ+, - loge tk) I c1/log2 TJ (KJ < k ,
(BJ.k)

Now the second condition (SJ,k) implies that la) (n, tk) - loge tkI > (1 + 0),/(21og2

TJ)

whence we see that any n belonging to SJ,k n B J,k satisfies (A J), that is SJ,knBJ,k s A3. Since the sets SJ,k (j fixed) are disjoint, we infer that

I

KJ
card (SJ,k n BJ,k) < card AJ,

(1.13)

18

1

The normal distribution of the prime factors

so, in view of (1.12), (1.10) will follow from card (S; k n B;,k) < card S;,k,

(1.14)

i

where BI,k = S\B;,k. We shall see that (1.14) holds if c is sufficiently large. Denote by a and b respectively generic integers for which P+ (a) < tk, P- (b) > tk. We have

cardS;,k= Y

a-1

Y, 1>> xe -k a<x /4

a<x1/4b-<x/a aESj,k

aESi,k

by Theorem 06. The hypothesis that (1.8) is satisfied is crucial at this point: it

enables us to assume a < xl/4 and hence tk = o(x/a) so that the sum over b above may be estimated by Theorem 06. At this stage we notice that, for any y1, Y2 satisfying i yl < 1 < Y2 2, we have card (S;,k n B,,k)1< 1

(y i(b) + Yi2( ))

a<x1/4 b<-x/a aESj,k

where ai(b): = co(b, T;+ 1) - (K;+ 1 - k) - cic Kj, E1 = - 1, s2 = + 1. deed, for n = ab, we have co(n, T j+ 1) - co(n, tk) = co(b, T;+ 1), and if then either al (b) < 0 or (X2 (b) > 0, whence yil + yz2 > 1.

In-

We apply Theorem 01. For i = 1, 2, Y".(b) << e -k exp { (Ki + 1 - k)(Yi - l - log yi) - c Ilog yi l JK j } b < x/a

a

and we select y i = 1 + ei/2 or y i = 1 + eicK J 12/(Kj+ 1 - k) according as k > Kj+ 1 - 2cKi l2 or not. A straightforward calculation shows that

the expression in curly brackets in the exponential above is then - (3c, where $ is an absolute constant, whence we have e-O`card SJ,k.

card (S,,knBj,k) << a<xl/4 a aESj,k

For suitable c, this yields (1.14), and hence (1.10).

Let us embark on the proof of (1.6). The required inequalities are symmetrical and we confine our attention to the second. We put X: =exp {log x/loge x} and we shall prove that sup A(n, t) > I - s p.p.x.

(1.15)

(x)
Let D = D(e) be a large constant, to be specified later, and put K = [log3 c(x)/log D], L = [log3 X/log D]. For K < k < L, put tk = exp exp Dk

The law of the iterated logarithm

1

19

and Ik = (tk _ 1, tk], finally Cok(n): = card {p: pln, pelk}.

The basic strategy now is to establish quasi-independence of the Cok(n),

sufficiently strong to permit us to follow the classical probabilistic approach. To this end, we estimate the characteristic function (in the sense of probability theory) of the vector (o(n): = ((K+ 1(n), (OK+ 2 (n).... , CoL(n))'.

We apply Theorem 02, with A = 3, B = 2 and y = X. This gives

fl zk k(n) = x ij i C 1 + Zk

Y_

K
n-<xK
+ 0 (x/log x)

/

P

I

(1.16)

uniformly for complex Zk, IZkI < 2, K < k < L. It will be convenient to employ the following terminology: if f and g are

functions of many complex variables zK+1, ZK+2, ,ZL defined by the power series

f(ZK+I,...ZL)=am

mLZK++11

MK

...ZmL

Z

9(ZK+1,...1ZL)=Ebm

ZLL

mL

we say that g majorizes f and write f < g if, for every mK+ 1, mK+ 2,

, mL,

I

It is then almost trivial that f 1 < g 1 and f 2 < 92 imply f 1 f2 < 9 192 Because a > 1 - 1/p we have

l+z-1<exp P

(z-1 +

'

1

P(P-1)

P-1

and hence

H(I+Zk-<exp{1+ \ P

K
Y_

K
(Zk-1)Hk}

where

Hk:= Y

PEIkP-1

(K
It follows that for vectors je(Z )L-K we have

N(x,j):=card {n:n< x,o(n)=j}<ex F1

(e_H)+.e

K
Jk'

with

9 =(2n)K-L l

fc"+1

...

fO( CL

x log x

f IdzkIIZkI

Jk

,

K
in which, for each k, Ck is the circle 14 1 = rk, 0 <, rk <, 2. We allow rk = 0 only

20

1

The normal distribution of the prime factors

when jk = 0: if C has radius 0 it is to be understood that 1

c

27C

Idzllzl-'=1.

Let jk < 2Hk for all k, K < k < L. We choose rk = jk/Hk above to deduce

that X <<

fl

(Hk/lk)j" «x H e-HkHk" //

logx K
K
jk!

(since Y_ Hk 5 loge x + 0(1)), whence HJk

He-'k k

N(x,j)<< x

(1.17)

.lk!

K
provided jk < 2Hk (K < k < L). We set hk = Hk + ,/(2Hk log (k log D)) (K < k < L). Since Hk = Dk - Dk-' + 0(1), certainly hk < 2Hk for sufficiently large D. Let M(x) be the number of integers n < x such that wk(n) < hk for every k, K < k < L. From (1.17),

M(x)<< x f (e-H" Y Hk/J!). K
j
Uniformly for H >, 1, 0 > 1, we have

e-HH'/j!»9-1j2e-e.

Y j> H+,1(2H0)

this just requires Stirling's formula and a straightforward computation. Therefore for a suitable absolute constant co, M(x)<< xK
CO =o(x),

whence we have sup ((oi(n) - hk) > 0

p.p.x.

(1.18)

K
Let n be an integer not exceeding x such that both (1.5) and (1.18) hold, and let coi(n) - h1 > 0. By (1.5), w(n, t1_ 1) >, D1-' - (1 + c),/(2D1-'log (I log D)), whence w (n, t1) = co(n, t1-1) + w1(n)

,D1-1+H,

+(,/H1-(1 +c),/D1-1)V(2log(llogD)) > D' + (1 - e) /(2D1log (l log D)) provided D = D(E) is sufficiently large. This proves (1.15).

The normal size of pj(n) and d3(n)

2

21

1.2 The normal size of pj (n) and dd (n)

An immediate corollary of Theorem 11 is the following sharpening of (1.3).

Theorem 12. Let c > 0, and fi(n) -+ oo sufficiently slowly as n -+ oo. Then

loge p;(n) -j I z (1 + s) V(2j logzj) (fi(n) <j < w(n))

(1.19)

furthermore, if 1 + e be replaced by 1 - e on the right, the set of integers for which (1.19) is satisfied will have zero asymptotic density.

We have therefore reached a best possible result concerning uniform approximation to cw(n, t) by the elementary function loge t; and Theorem 11,

and variants of it, will have applications in later chapters, where it is indispensable as a global statement about the distribution of prime factors. Regarding local information about neighbouring prime factors, Theorem 12 must be treated with caution if it is to be interpreted as meaning that p1(n) is approximately exp exp j. For example, this might lead us to expect, for almost all n and j> l;(n), that p;(n) > fl pi(n),

(1.20)

i<j

and this is completely false. The point is important and we give two demonstrations. First, following Erdos & Katai (1971) we define M(n, z) _ Y µ(d), M(n) = sup JM(n, z)J.

(1.21)

Z

dIn d-< z

If (1.20) held for j > fi(n) then M(n) <

hence we should have

But H. Maier (1987) has shown

p.p., provided

recently that M(n) > (log2 n)"

p.p.

- log 2 K' = log (1 -1/log 3)

confirming a conjecture of Erdos & Hall (1980). In fact the truth about (1.20) is as follows. For neZ+ (not necessarily squarefree) and y > 1, let y(y, n) be defined by the relation max {d: din, P+ (d) < y} =

yv(v,")

Then there exists a continuous, strictly increasing G: R+ -> [0, 1), G(0) = 0, G(c) -+ 1 as c -> co, such that 1

to g2 n

card { j: y(p;(n), n) <, c} -+ G(c) p.p.

(1.22)

22

1

The normal distribution of the prime factors

(Erd6s(1966)). For a more precise result, see Bovey (1977). Bovey showed

that G(c)=e_I JC p(u)du 0

where y is Euler's constant and p is Dickman's function (defined by (2.17)). In particular, (1.20) holds, p.p., for (G(1) + o(1))co(n) values of j - indeed the influence of multiple factors can be neglected here since, plainly, fP,iin p° -' < (n), p.p. Notice that this implies a real difference between the two orderings of the divisors mentioned in the introduction.

A consequence of Theorem 12 is the following result about the jth divisor dj(n). A sketch proof is given in Exercise 12. Theorem 13. Let e > 0 and g(n) -+ oo as n-> oo. Then we have 2

log2d;(n)-logj

(fi(n) <j < i(n)) p.p.;

(1.23)

moreover the right-hand side is best possible (in the same sense as in Theorem 12).

The right-hand side is much too large to cope with delicate questions about divisors in short intervals or the propinquity of divisors. Once again we have an approximate formula, in this case d;(n)

exp(j'j1og2)

(1.24)

which, taken too literally, will lead to falsehood. Thus, if we define, for

0
we might expect, arguing roughly from (1.24) that Fn(u) _ Ulog2

p.p.

(1.25)

with some meaningful quality of approximation. The reality is quite different: if ul and u2 are freely chosen from (0, 1) then Fn(ul) = Fn(u2) on a sequence of positive density. The following `principle of uncertainty' (to be proved in §2.3) shows in a rather strong way that Fn has no normal order. (See §4.4).

Theorem 14. Let sl be a sequence of integers such that F converges weakly

when n -+ oo through .4. Then dsi = 0. These results on F.(u) may be found in Tenenbaum (1980). As we might

2

expect,

The normal size of pj(n) and dj(n)

23

has an average order. Uniformly for 0 < u 51, X

E Fn(u)=2aresinJu+0(1)

(x-->cc).

(1.26)

71

n,<x

(Deshouillers, Dress & Tenenbaum (1979)). So (1.25) is not even correct on average. We end this chapter with a final, but important example warning against incautious use of (1.24). Erdos conjectured that

min (dj+1(n)/dj(n))<2 p.p.,

(1.27)

1-<j
and this is established in Chapter 5; much more is true. All we need here is that, on a suitable sequence of asymptotic density 1, the minimum ratio in (1.27) converges to 1, and consequently is attained for a large j. Of course the sequence on the right of (1.24) has increasing ratios. Hence Theorems 12 and 13 should be regarded as useful and important

tools in the fine study of divisors which are best possible as they stand. Nevertheless, for certain important problems they are inappropriate - and they cannot be `improved'. We have to look at these things another way.

24

Notes on Chapter 1 An easy proof, based on the Turan-Kubilius inequality, of a slightly weaker result than Theorem 10 appears in Erdos (1979). It is remarkable that one does not have §§1.1-1.2.

card {k < w(n):log2 pk(n) > k} - 211092 n

p.p.,

(1)

although the weighted analogue holds: Y { 1/k: loge pk(n) > k} - i log3 n p.p.

(2)

In fact the left-hand side of (1) divided by log log n has a distribution function equal to the arcsine law - see Erdos (1969). For the sake of completeness, we have presented here a direct proof of the law of iterated logarithm stated in Theorem 12. That is we use only

number theoretical estimates and we do not borrow any result from Probability Theory. One could also follow an indirect approach, as in Kubilius' book (Theorem 7.2), with the aim of applying Kolmogorov's classical law after having established a suitable strong approximation theorem. Since the necessary details are not quite provided there, we have decided to give a complete, self contained proof. For recent generalizations to other arithmetic functions, and to Strassen's form, see Manstavicius (1986a, b).

In his 1979 paper Erdos introduced the densities Ak(d), resp..t (p), of those integers n such that dk(n) = d, resp. pk(n) = p. Although pk(n) is `about' exp exp k for most n, .1k (p) assumes its maximum value around exp (k/log k), (there seems to be a slip about this in Erdos' paper, cf. Exercise 12). Similarly

Ak(d) is maximal for values of d much smaller than the `normal' order exp(kl/1og2): cf. Exercise 13.

According to Theorem 11, the expected value of w(n, s, t): = w(n, t) -

w(n, s) is loge t - loge s, but we need this to be large compared with Erdos (1969) proved that Cw(n, s, t) - log

log t

logs)

P.P.

uniformly for s 5 t < n restricted so that the right-hand side exceeds t/i(n) 1093 n, i/i(n) -> oo; moreover this condition is necessary. Both papers contain other striking results on the normal distribution of prime factors. Bovey (1977) is also fundamental.

25

Exercises on Chapter 1 10.

By setting up checkpoints at t = tok, show that the sequence

.4 = R(K, to) of integers n for which su p

l

(n, t)

loge t

-> 1

K

has upper asymptotic density d-4 <<Jlog to) -K, (1 + K) log (1 + K) - K, uniformly for to >, 3.

where

K=

Let , (p) denote the asymptotic density of the set of integers n such that pk(n) = p. Show that 11.

Ak(P) = H I 1- 1 P w(m)=k-1 P P,
m i

1

P+(m)
and deduce that, for p - oo, loge k = o(log2 p), e-Y

(1ogep+O(log2k))k-1

1k(P)=PlogP

(k- 1)! Deduce that, for given k, '.k(p) assumes its maximal value when p = exp {(1 + o(1))k/log k}. How can this last statement be compatible with the law of the iterated logarithm for prime factors? 12.

Let fi(t) -* co arbitrarily slowly and put L(t) _ j(21og2 t log4 t)

(t >1 to).

(a) Show that, p.p.x, lff(n, t) - loge ti < (1 + c)L(t) (fi(x) < t < x).

(b) Put D(n, t) = card {d: din, d < t}. Deduce from (a) that, p.p.x, log D (n, t)/log 21< loge t + (1 + e)L(t) (fi(x) < t < x).

(c) Put D (n; t, u) = card {d: din, d > t, P + (d) , u}. Show that, uniformly for

2,
(d) Put a = 1/log 2, tj = exp j" (j >, 1) and uj = exp {coj"/4log j} where co

is the constant appearing in part (c). Prove that, p.p.x, D (n; t j, u j) = 0 ( (x) < j '<(log x)1og 2)

where fi(x)-> oc arbitrarily slowly. (e) Deduce from (d), using the trivial inequality (n, t, u >, 1), that, p.p.x,

D (n, t) + D(n; t, u)

log D(n, t) > 1092 t; - (1 + c)L(t,) (fi(x) <j 5 (log X) 10g2); log 2

26

1

The normal distribution of the prime factors

moreover, for at least one j in this range, log D(n, t3)

log 2

> 1092 t; + (1 - s)L(t;).

(f) Deduce Theorem 13 from part (e). 13.

For k, d >, 1 let Ak(d) denote the density of those integers n for which

dk(n) = d. Set j =1 + [log k/log 2] and let N be the product of the first j primes. Find a lower bound for Ak(dk(N)) and deduce that Ak(d) is maximal when

k
Compare this result with Theorem 13.

log

)))

2 Sieving by an interval Introduction Amongst the integer sequences defined by multiplicative constraints, 2.1

certainly one of the simplest and most natural is the set of multiples of the integers lying in a given interval: this is a sieve problem, with the emphasis on the sifted rather than the unsifted numbers! Let H(x, y, z) denote the number of integers n not exceeding x which have at least one divisor d such that y < d < z. Estimates for H(x, y, z) are needed

in many arithmetical problems; in particular they provide one of the approaches to the propinquity of divisors. Historically the problem about H(x, y, z) was first introduced in a special but, as we shall see, important case in connection with the theory of sets of multiples. For any integer sequence sl, let ^4):= {ma: meZ+, ae.4} be the set of multiples of .sad. Such a set -4 may of course be generated by many sequences sad, but there is a unique, minimal sequence Q' such that R(.sz7') = mo(d), characterized by the property that no element of d' divides any other. Sequences with this property are called primitive. In fact d' is the

intersection of all the sequences that generate -4 (see the Notes, also

Halberstam & Roth (1966), Chapter V). An example of a finite primitive sequence is

d(y):={a:y
In the early thirties it was conjectured that any set of multiples had asymptotic density. A counterexample was constructed by Besicovitch (1934) (cf. Exercise 20), who proved as a key step liminf lim x-'H(x, y, 2y) = 0. (2.1) Y-'I Erdos (1935) showed that liminf could be replaced by lim, and more than 40 years later gave another consequence of this strong form of (2.1), that the average order of Hooley's function 0(n): = max card {d: dln, e" < d < e"+ u

tends to infinity (cf. Hooley (1979), and Theorem 60).

28

2

Sieving by an interval

One of the main results of the present chapter is a strong quantitative version of (2.1), H(x, y, 2y) <

(log

y

y < 1 x),

(2.2)

where the exponent b

- 1-

1 +10922 logg 2

= 0.08607 ...

(2.3)

will be shown to be optimal. In Exercise 22, the reader will see how to apply

(2.2) in Erdos' method to obtain E A(n) >> x 1093 x.

(2.4)

n_< x

Another topic for which H(x, y, z) proves to be important is the study of relations between consecutive divisors - often the subject of Erdos' 'unconventional' problems. For instance, let

F(n; 9) _ Y 6(d;/di+,) 1

i
where d. = d.(n) and 6eC2[0,1] is given. Then (Erdos & Tenenbaum (1983)),

Y F(n,0)=9(1)xlogx-2 n_< x

(' x Jx

fl

J

cp(

yz)H(x,y,z) dy dz zZ

+O(x),

(2.5)

1

where ap(t) = 9'(t) + t6"(t). A detailed proof and several applications are to be found in Exercises 23-25. Finally let Dn be the random variable whose distribution function is F,, (v): = i(n) card {d: din, d 5 n°}.

(2.6)

In principle any question about the divisors of n can be posed in terms of Fn and, since we know from Theorem 14 that Fn does not converge weakly in

any subsequence of Z+ of positive density, we must seek an alternative description of its limiting behaviour. A result of this sort is (Tenenbaum (1979)):

Theorem 20. For each fixed pair of real numbers u, v (0 < u < v < 1), the arithmetical function nF-F,, (v) - F,, (u) =

_

card {d: din, nu < d < n°}

has a purely discrete distribution function all of whose step-points are dyadic rationals (a,be7L+).

2 Statement of results concerning H(x, y, z)

29

In this application one needs upper bounds for H(x, y, z) when y and z are fixed powers of x.

2.2

Statement of results concerning H(x, y, z)

There are essentially four possibilities for the asymptotic behaviour of this function depending on the values of y and z. We introduce some notation to help describe what happens. We recall the constant S of (2.3) and from (0.18) the function

Q(v)=vlogv-v+l (v>0). We define G(v) =

Q

C1 +v+/ log 2

(v < log 4 - 1),

(v > log 4 -1),

v

L(v) = exp {../(log

3v)} (v

1).

Notice that Q is increasing when v > 1 and Q(1/log 2) = 8. Thus G(v) = 8 for

v < 0; for v > 0, G increases and since G'(log 4 - 1- 0) = 1 it is continuously differentiable. Moreover G' (v) < 1 for v < log 4 - 1 so that in this range we have G(v) > v. For 2 < y < z we define u = u(y, z), Q = f3(y, z), and _ (y, z) implicitly from the relations

z=yl+u=y+y(logy)-P, /3=1og4-1+

(2.8) /loge Y*

Theorem 21. (i) Let y --> oo, z - y -. oo, y < z < ,Jx, and suppose in addition

that c-> + oo. Then

H(x,y,z)=(1 +o(1))xlog-ey. (ii) Let 2 < y < z < min (2y, .Ix), and

(2.9)

be bounded above. Then

x(logy)-o(6)L(logy)-" << H(x,y,z)<< x(logy)-o(e)/(1 +(- )+),

(2.10)

where c, is an absolute constant.

(iii) There exists an absolute constant c2 so that in the range y 3 2, 2y < z < min (y3"2, Vx) we have xusL(1/u)-C2

<< H(x, y, z) << xua

1092 (3/u)

Vlog(2/u)

(2.11)

moreover, for each fixed B >, 2, if z < By we may strike out the factor 1092 (3/u) provided we replace << by << B on the right.

30

2

Sieving by an interval

(iv) Uniformly for 2 < y < z

x we have

H(x,y,z)=x( 1+o

1 gg Z)).

(2.12)

Part (iv) is very simple, and it is non-trivial only if z > y` for a suitably

large c. However, H(x, y, z) is an increasing function of z and so for y3/2
are sufficiently independent (the various of g.c.d.'s being small) for us to have (we assume y -> oo, fi large) 1x1 [xlog(z/y)x(logyyP. d-

H(x, Y, z) - E y
This is the state of affairs in (2.9). In fact the threshold of dependence occurs

at fi = log 4 - 1: when fi is smaller than this critical value the interaction between the implied congruence conditions has a perceptible effect on the exponent of logy which is now smaller than - fi. The factor lost due to dependence increases as z increases towards 2y, when it is (log y)a+o(1) When z > 2y a new phenomenon appears owing to the influence of the `small' primes < z/y. By Theorem 07, we may asssume that usually

n(zly):= fI p°` P°Iln

P6z/Y

is itself fairly small: the small prime factors of n may be expected to affect not so much the existence of divisors in (y, z] but their number, given that this is

positive, and this is irrelevant. So we are concerned largely with divisors made up of primes from (z/y, z] = (yu, yl +n], and I/log y gives way to u when we pass from (2.10) to (2.11). The fact that S now remains constant reveals some sort of saturation in the dependence. Finally, when z becomes so large that u itself is large, almost all integers have not just a divisor but a prime factor in (y, z]. This simple remark is half-

way to a proof of the easy, but as we shall see practically optimal formula (2.12).

It is worthwhile to grasp at the outset why the threshold of dependence is at /i = log 4 - 1. It is well-known that the sum E {i(n): n < x} is dominated

by the n with 0(n) - 21092 x. Similarly (and both these statements may readily be justified by the method of §0.5), E i(n; Y, z) nsx

is dominated by those n for which S2 (n, z) - 2 log log z.

(2.13)

3 More applications

31

Now (2.13) is a trivial upper bound for H(x, y, z). But in the case of quasiindependence we must have

x-'H(x,y,z)-1-

1- -d 1

y
=1-[Y],,,x-' ET(n;Y,z)

[z]

(2.14)

n ,x

(we are assuming z - y = o(y), z 5 ,/x), and so the dominant contribution in (2.13) must come from terms with T (n; y, z) = 0 or 1. If, as is acceptable for the present discussion, we identify T(n; 0, z) with 21(n,Z) and further assume

that the set {log d: djn, d < z} is more or less evenly distributed over [0, log z], we see that T(n; y, z) should be about 2"(n,2) log (z/Y) =

log z

(log

Y)tog4 - 1- B +0(1)

for the dominant integers n in (2.13). The reader should see Erdos (1967), where log 4 - 1 is also a threshold. Let us write

H(x,Y,z)=:n(x;Y,z) Y T(n;Y,z) n<x

Then q(x; y, z) < 1, moreover if we combine the upper bound (2.10) and (2.42) below, we see that for l; = O((log2 y)116) we have 11(x;Y,z)<< (1+(-

Equally, the proof of (2.9) would give a bound for 1 -?I (x; y, z) for large Conjecture.

.

There exists a probability distribution function F such that, if

x, y, z -+ oo with l; e Fl constant,

n(x,y,z)-+F(c).

2.3 More applications First we return to the sequence of random variables D. We have already

mentioned that the upper bound in (2.11) is vital for the proof of Theorem 20: an immediate corollary of that result and (2.11) itself is Theorem 22. Let t, u be real numbers, t >- 1, 0 < u < 1. Then the sequence of

the integers n which have at least one divisor d such that n(1-u)/t < d <, n'/t

(2.15)

possesses asymptotic density h(u, t); furthermore for t > 2, 0 < u < 1 we have uaL(1/u)

<< h(u, t) << u°

log2(3/u) Vlog(2/u)

(2.16)

32

2

Sieving by an interval

(The restriction t >, 2 is unimportant because of the symmetry of the divisors about Vn.)

If we replace `divisor' by `prime factor' above, it is much easier to establish

the existence of the density - such a result has probably been known implicitly for a long time. (For a complete proof see Tenenbaum (1980).) A

famous special case concerns the integers n such that P+(n) < ni/c: the density is p(v) where p is Dickman's function defined by p(v) = 1

(0 < v < 1),

vp'(v)= - p(v- 1) (v> 1).

(2.17)

Prime factors are easier to deal with because Buchstab's identity is available: this reads

`P(x,y)=1+

YgI\p,p/

(2.18)

P-
in the Dickman problem. There is nothing analogous to (2.18) for divisors. A typical feature of the proofs of Theorems 20 and 22 is that a relatively sharp

upper bound for the counting function is needed prior to the proof that the

density exists. We prove Theorem 22 in full detail in the next section, assuming (2.11).

Our second application also concerns the random variables D. It consists of the rather surprising `incertitude principle' already stated in Theorem 14: if d is an integer sequence such that {Dn: nEd} has a limit law, then dd = 0. We are now in a position to prove this as an easy consequence of Theorem 22.

Proof of Theorem 14. This is by contradiction: we assume dd > 0. We

may assume that i(n)-goo (ned) as the complementary set has zero density. Now let F be the distribution function of the limit law so that by hypothesis lim F,,(u) = F(u)

n- 00

(ue'(F)).

(2.19)

ned

Recall that F is symmetric if F(u) + F(1 - u) = 1 (ueW(F)): this is the case because each Fn in (2.19) is symmetric. In particular if u is a point of increase

of F (i.e. F(u + s) - F(u - s) > 0 for all e > 0), so is 1 - u. We are going to show that F has at least one point of increase and hence at least one in [0,

Z].

This follows from the Radon-Nykodym decomposition dF = v + f du, where v is a singular measure and f >, 0. Indeed if v 0- 0 the quantity 1 Em onf 2c

(F(u + r.) - F(u - s))

(2.20)

3 More applications

33

is infinite for v-almost all, and hence for at least one, u. Alternatively, if v - 0, (2.20) is identically f (u) and is positive for some u. Thus F does have a point of increase in [0, Z]. We consider two cases according as u may be taken in (0, 2] or not. In case (i), for arbitrarily small e both u + 8c-W(F) and

card {d:dln,u°-E oo through a. As i(n) -+ oo, the left-hand side above is > 1 for large

ned. By Theorem 22, we deduce that d,4 <, h (

u+2EE

,

u1+E)= 0 W) (E -+ 0),

and da = 0 as required. In case (ii), dF concentrates all its mass at the endpoints u = 0, 1: by the symmetry, we must have

0 (u < 0),

F(u) = ' (0u<1), 1

(u

and so, for fixed u > 0, Fn(u) >, ' for all sufficiently large ned, and

dd < limsup 3x-' Y F,, (u). X_ 00

(2.21)

n6x

The result of Deshouillers, Dress & Tenenbaum (1979) (1.25) implies that the right-hand side of (2.21) is equal to (6/ir)aresin s/u, and since u may be taken arbitrarily small we again have dsd = 0. (We leave to the reader, as an exercise on Theorem 01, a self-contained proof that the right-hand side of (2.21) is << ,,/u.) This completes the proof. Our third application concerns a question of Linnik and Vinogradov: to determine as exactly as possible the number A (x) of distinct products ab <, x such that a 5 _11x, b 5 Jx. We obtain the following result, sharpening that of Erdos (1960).

Theorem 23. For x >, 3, we have (log x)a L(log x) -e5 << A(x)

<<

(log x)a

(loge x)-'i2

with 6 as in (2.3).

Proof. The result follows from Theorem 21 (iii) and

HCx Jx '/x 4

4

2

-
k

x /-

x H 4k,4+', 2k

(x 3 4).

(2.22)

C

To prove (2.22), we establish inclusions between the various sets. If n is

34

2 Sieving by an interval

counted on the left, then n = and < x/4 with Jx/4 < d <, Jx/2 say, whence m < ..lx and n is counted by A(x). If n is counted by A(x) let k be such that x/4k+ 1 < n < x/4k. By hypothesis n = md, maxim, d) < Jx. Suppose for instance that d <, m. Then d < ../n < /x/2k, d = n/m > n/Vx > Jx/4k + 1 and n is counted on the right. In the fourth application we consider the sums

M(n,Y):= Y µ(d) din d
For n > 1, M(n, y) = 0 when y > n, but one may be interested in M(n, y) as a

function of y < n. For example it occurs in Vaughan's method for binary forms (Vaughan (1980)). Maier (1987) has established that M(n): = max I M(n, y) I-+ oo

p.p.

1
and we have the following result sharpening that of Erdos & Hall (1980). Theorem 24. For y > 1, let ey denote the asymptotic density of the sequence {n: M(n, y) 0 0}. Then ey << (logy)-1.

For a (sketch) proof see Exercise 211. We obtain the slightly inferior exponent - 8/(1 + 6) here. The density exists, the condition M(n, y) 0 0 involving only congruences (mod d), d < y. Let m = rj {p: pl n} be the core of n and q = P- (n) = P- (m). Then

M(n, y) _ E µ(d) + Y u(qd) = Y p(d), dlm/q d
dlm/q

dlm/q

qd
y/q
and so M(n, y) 0 0 implies n has a divisor dc(y/P- (n), y]. Let xe(0,1) be at our disposal. Either P - (n) > exp { (logy)"} or n is counted by H(x, y exp { - (log y)"}, y). The number of such n is << x{(log Y)-"+ (log y)-a(t-")}

by Theorem 06 and (2.11) respectively. We choose x = S/(1 + 8). 2.4 Proof of Theorem 22 We employ Theorem 21 to establish the existence of the density h(u, t) of integers n with at least one divisor satisfying (2.15), for all t > 1, ue [0, 1]. We notice that it is sufficient to deal with the range t >, 2, ue(0,1). The cases u = 0 or 1 are trivial since h(0, t) = 0, h(1, t) =1 for all t > 1, and in view of

Proof of Theorem 22

4

35

the symmetry of the divisors about ,/n we also have h

h(u, t) =

t

u

t+ u- 1't+u- 1

h( 2 - t t '

2)

(1
{h(t+2u2,2)

(2.23)

(2-u
We assume t > 2, ue(0,1) and put H(x): = card {n < x: 3d: din, n('

d < n'1`}.

It is natural to expect that H(x) = H(x, y, z) + o(x) (x -oo)

with

y=x(i-u)lr z=xlIr

(2.24) (2.25)

and (2.24) is our first goal. Once its existence is established, the bounds (2.16) for h(u, t) will follow from (2.11) and (2.24). Let ne(x/log x, x] be counted by one, but not both, of H(x) and H(x, y, z).

Then n has a divisor in ((x/log x)", x] with a = (1- u)/t or 1/t, and by (2.11) the number of such n is <<.,, x (log x)-b. Hence (2.24) (with this upper bound for the remainder). It remains to establish the existence of

lim x-'H(x, y, z) = h(u, t)

(2.26)

X- 00

where here and throughout this section y and z are as in (2.25). Eratosthenes' sieve gives °°

H(x,y,z)= Y (k=1

1)k-1 y
[d1id2,...,dk]

but it would be very difficult to use this for a proof - for fixed k the inner sum is not O(x). We should have more hope if the d; were restricted to be primes or had a bounded number of prime factors and with this in mind we define an auxiliary quantity H, (x, y, z) which counts the integers n < x with a divisor de(y, z] satisfying P- (d) > yE. We show that lim limsup x-' (H(x, y, z) - H,(x, y, z)) = 0, X-'0

(2.27)

again by means of (2.11). Indeed, let n be counted by H(x, y, z) but not HE(x, y, z), and let d be the smallest divisor of n in (y, z]. Then necessarily d/P - (d) ,
+E)

<< tx

36

2

Sieving by an interval

by (2.11), and (2.27) follows. It will therefore be sufficient to show that

lim x-1HE(x,y,z)=:hE(u,t)

(2.28)

X- OD

exists for each fixed positive s. By the sieve of Eratosthenes, 00

HE(x,y,z)= Y (-

1)k-1Bk(x)

k=1

where x

Bk(x) =

Y yy`

If {d, d2, ... , dk} is a k-tuple of integers with non-zero contribution to Bk(x), we must have

d:= [dl,...,dk] <x, P-(d)> yE whence 2`1E(1- ).

k < T (d) < 2n(d) <

(2.29)

Hence the limit he(u, t) in (2.28) exists if, for each fixed k, lim Bk(x)/x exists.

Let p(d) denote the number of representations of d in the form
d=[d1,d2,.... dk] with y
pd(d)+O(

P(d)Ld = x

Bk(x) _

P(d) d5x P (d)>y'

d=1 P (d)>Y`

d5x P (d)>y`

and the error term is << x/log x because 11(d) «<,,,,E 1, p(d) <

(t(d))

<< "U" 1.

The main term may be re-written as 00

00

xY ErY,'

1

(2.30)

r=1i=1

where the dash means that summation is over all j-tuples of primes {p1, p2,..., pi} such that

YE
P1P2 ... Pi < x, P(P1 ... pi) = r.

Also r and j are bounded, independently of x, and for every pair {r, j} we may re-write (2.31) in the form x

logP1 109P2 log x ' log x

logpi - 1 log x

where x is the characteristic function of a subset of [c(1 - u)/t, 1]i defined by

a bounded number of linear inequalities. The following lemma therefore

Proof of Theorem 22

4

37

implies that, as x -> co, D1/p1P2 ...p;) tends to a limit, as does x-1Bk(x) via (2.30).

Lemma 22.1. Let X: (U8+)i -> 118 be Riemann integrable with support contained in a compact subset of (08+)i. Then we have logp1 A.

lim

log p;

logx'

'log x )

°°

°°

...

P1P2...Pi

du1

X( o

0

u1,...,u;)-... u1

du; u1

Proof. On the hypercube [a, b] i (0
du;

U2

U;

dvx(u1,...,u;)= rIx-u'd7C(xui). t,; By the Prime Number Theorem and partial integration we readily obtain that for any product domain P = rj [a;, b;] c [a, b] i we have lim

x-'oo fp

dvx(u1,...,u;)= f dv(u1,...,u;). JP

Hence the family of positive measures vx (x > 0) is uniformly bounded (take

P = [a, b] j) and converges weakly to v on the set of finite linear combinations of characteristic functions of product domains. Therefore it also converges weakly to v on the set of continuous functions supported on [a, b] j. Since X is Riemann integrable there exist such functions f and g with

(g-f)dv<e

.f<X
for arbitrary e > 0. We obtain from

J f dv+o(1)= J fdvJXdvx= Jdvx Jdv + o(1) and

Jfdv<, Jxdv<, Jgdv that

Jx dv - Jx dv ,< e+o(1) and we let x --,, oo, e - 0. The result follows.

38

Sieving by an interval

2

2.5 Proof of Theorem 21(i) - small z

In this section, we put rl = (z - y)/y = (log

y)-R

and our aim is to prove

H(x, y, z) = (1 +

(2.32)

under the conditions y --> oo, z - y -+ oo, y < z < -I/x, and (/3 + 1- log 4)Vlog2 y -+ 00-

Under these hypotheses x

Y i(n; Y, z) = Y

- rlx

(2.33)

y
n<x

from which the upper bound in (2.32) is clear.

For the lower bound we consider two cases. First, suppose that i log2 y < 1. We have x

Y z(n; y, z)2 ,

1

+ 2x

(2.34)

y
n<x

The first sum on the right is - x log (z/y) '' rlx. In the second we put m = (d, d'), d = mt, d = mt' and observe that y < d < d' z implies that t'/(t' - 1), t'/t < 1 + it whence t' > 1 + 1/ll and m, z/t' rly. Therefore 1

1

1

yd J

m
2

m \y//

Y

logy.

We insert these estimates into (2.34) to obtain

Z i(n;y,z)2 <(1 +o(1))rlx+O(i 2xlogy)'rlx n<x

(because q logy < 1/log y = o(1)), and so Cauchy's inequality 2

i(n;Y,z)

H(x,Y,z) Y, i(n;Y,z)2

(2.35)

n<x

(n-<x

yields the required lower bound for (2.32).

Now consider the second case when n log2 y , 1. Let x denote the characteristic function of the set of integers satisfying (2.36) L)(n,y)< Y(Y):=21og2Y+i(Y)/log2Y, y)116. We have, uniformly for where ((y) -. oo as y -> oo, ky) << (log2 1

v
v°(n,Y)-r(Y)T (n;Y,z) vn(d) <<xv-Y(Y)(logy)°-1

Y,

y
5

Proof of Theorem 21 (i) - small z

39

Theorem 04 gives, for every NEIL+, z <
vn(d)

(2.37)

Y_

y
and we put N = 2, so that the right-hand side is << q(log y)v 1 because n loge y >' 1. So we have

Y (1 -X(n))t(n;y,z)«rlxv-''(y)(log

y)2v-2

n<x

and we put v = Y(y)/21og2 y: the right-hand side is

<< x exp (-

O(/i(y)3/0og2 Y)) = o01x).

Next, n5x

/ i (n; Y, z)

r(

1,

N(x,Y,z),>

YX(n){i(n;y,z)-2I n-<x

2

\

l

z(n;y,z)= 1

(1 + o(1))rjx - 2S say, where r(n,Y,z)1

S:= Y X(n)1 n-<x

\

J

2

\ E vn(n,y)-r(y) n_<x

Y

1

d,d'ln y
provided ve(0,1]. In the inner sum we introduce the g.c.d. m = (d, d') and remark that, as before, for a non-empty sum we must have m < 11Y. We invert summations and apply Theorem 01 to obtain vn(m)

vn(t,Y)

(log 2m)'-'(,,. Y

S <<xv-Y(y) , m5ryy m

2

(2.38)

t


We claim that, uniformly for 0 < v < I and m < r1Y, we have v

1 -v

n(t)

ylm t z/m t

<<

(log 1

)v-'. (lo) gm Y

(2.39)

There are two cases according as y/m < 11-3/2 or not. In the first case, the trivial bound Y_ t - ' << log(z/y) + m/y << suffices. In the second case, we note that (z - y)/m > (y/m)'l3 and we apply Shiu's result, Theorem 03. For t < y2, c2 (t, y) '> Q(t) - 1. We insert (2.39) into (2.38) to deduce that 1

S«uxv-Y(y) 12 log

2-2v

2v-2

vn(m) mryy m

(log2m)v

1

log y

m

and we put v = Z . By partial summation, the inner sum is << 1092 y/log y, whence S << x112 (log y)1og 4

We put 0 (y) = min desired result.

y(log2 y)2.

(2.40)

(log2 y)1/6) and we have S = o(r1x). This gives the

40

Sieving by an interval

2

2.6

Proof of Theorem 21 (ii), (iii) - upper bounds

Lemma 21.1. Let IIk(y) denote the number of integers <, y with exactly k

odd prime factors (counted according to multiplicity). Then for any fixed c, z > y + y(log y)-, and uniformly f o r 0 < k < (3 - E) log2 y, we have z - Y (loge y)k rlk(z) - nk(Y) < < `logy kl

Proof. We need a modification of Theorem 04 in which SZ' counts odd prime factors: for Ivj < 3 - E, x >, 2, N e Z , we have x N

Y- vn(")n5x

av(v)(logt)v-l-vdt+OE,N(x(logx)Rev-2-N)

(2.41)

Y-

2v=0

where av(v) <<e N 1. Now put v = re'°, r,<3 - s. We have f21r

{H(z) -rlk(Y)}rk=

2n

0 z

«e,N

e-ik°

v"(")dO y
2n

(log t)r cos B -1 dO + Z (log y)r - 2 - N

JyJO l

(log

Y)r-1

« E,N(z - Y) I(r1og2Y)+z(logy)r 2-N and we put r = k/(log2 y) and employ Stirling's formula. We take N = [c]. Now we consider the upper bound in (2.10). If >, - 1 we observe simply that i (n; Y, z) << x (log y) -

H (x, Y, z) n<- x

Now if /3 < log 4 - 1, hence - 1 < < 0, we have G(19)=13+

(log 4 -1- /3)2 +O((log4-1-Q) s) log24

(2.42)

by Taylor's theorem: notice that Q(2) = log 4 - 1, Q'(2) = log 2. Thus in fact H(x, y, z) << x (log y) - c(fl)

which is the result stated. Next assume S < - 1. We require Theorem 08, and we set E = {p:3 <, p AE (x) or not. Here 2 = (1 + /)/log 2. We have

H1 5

I

card {n: n < x, KI(n, E) = k} +

AE(x)
Y n<- x (1(n,E)> 2.51og2 z

<< xe-E(x) Y E(x)k/k? + x(log k> AE(x)

z)-Q(2.5)

1

7

Proof of Theorem 21 (ii), (iii) - lower bounds

41

by Theorem 08 and an obvious variant of Exercise 04 respectively. Since E(x) =1og2 y + 0(1), Theorem 09 yields H 1 << x (log Y) - Q(a) (log2 Y)

which is within the upper bound stated. Next r(n;Y,z)<,

E

H2

E

Y

1.

h+kS1E(x) y
n_< x

12(n,E)SAE(x)

For d ,
m<x/d 0(d,E)=h S2(m,E)=k

E(x/d) = E(x), and

)(d, E) = SY(d).

Theorem 08 and Lemma 21.1 give H2 << xe - E(x)

Y 1(H (z)-nn(Y))E(x)k/kt h+k<-2E(x)Y

<< x(log

y)-1-ee-E(x) E 21E(x)1/l! I S AE(x)

<<(1 - 2/2) - l x (log y) - 1 - P eE(x) - 2 Q(A/ 2)E(x) E, (x\ - 1/2

by Theorem 09. Since 2Q (A/2) + /3 = Q(A) = G(/3), H2 is /also within the

bound stated in (2.10). This establishes this part of the theorem. The upper bound in part (iii), in which 2y < z < y3/2, is treated similarly, but the technical details are slightly more complicated because of the effect of the primes S z/y. We give a brief indication of the necessary modifications

here, and refer the reader to Tenenbaum (1984) for a complete proof. We now have E = {p: z/y < p < z}, and as before there are two classes of integers, split according as 0(n, E) > 2E(x) or not. In this case 2 = 1/log 2.

The first class goes as before, using Theorem 08 or Halasz' original theorem. The upper bound for H2 is more delicate. We write n = ab, with P+ (a) < z/y < P - (b), and use Theorem 07 to show that, with negligible exceptions, we have a 5 (z/y)`E(x) for a suitable constant c. There is a further split according as 1(b, z) > 2E(x) or not. In the process of counting this last

class we introduce the function r(b; y/a, z): sums involving this can be estimated more precisely for small a, say a < (z/y)`'ogE(x)' and when (z/y)`logE(x) < a <(z/y)`E(x) effective use of the bounds for the W-function, given in Theorem 05, is possible.

2.7 Proof of Theorem 21 (ii), (iii) - lower bounds

We give a detailed proof for part (ii) and indicate the modifications needed for part (iii). Let 2 < y < z < min(2y,.,/x) and log 4 - 1 + O (1)/../loge y. We assume to begin with that /3 log 4 - 1; the other case will be dealt with very briefly.

If x denotes the characteristic function of an arbitrary set of integers,

42

2

Sieving by an interval

Cauchy's inequality gives

( n<x

X(n)i(n;y,z))2H(x,y,z) E X(n)x(n;y,z)2.

(2.43)

n < x

This is the basis of our method - of course the critical step is a good choice for X. Our idea is to impose the weakest condition which will ensure that for the dominant n in both the sums in (2.43) we have 2(n; y, z) < L(log y)`. To this extent X(n)i(n; y, z) will mimic the characteristic function of the set counted by H(x, y, z). We set 2 = (1 + #)/log 2 < 2. Simple heuristic arguments then suggest that we put X(n) = X(n, A), where X(n, A) =1 if and only if 0(n, t) < 2 loge 3t + 4log (L(log y)) (2 < t ,
(2.44)

We are going to show that, with this choice of X, we have both R: = E X(n)r(n;y,z)>> x(log y)-Q(x)L(logy)-",

(2.45)

n<x

and

S:= I x(n)

yz)1«x(logy)-Q(-)L(logy)".

CT(n

n<x

(2.46)

//

We begin with (2.45). We have

R = Y X(md) = Y_ md<x y
X(qd)

md-<x

y
where m = qr, P + (q) 5 y < P - (r). Certainly X (qd) = 1 will follow from f (q, t), fl(d, t) <, 21og2 3t + 2 log (L(log y)) (t,
(2.47)

and we construct such integers q, d in the following manner. Put L = L(log y), and define the intervals I(j) = (exp L', exp Lj+ i]

(j > l).

We set

h = [ log L11

k

= [ logL

],

and assume y sufficiently large that k > 3. Let aj denote, generically, an integer equal to the product of h primes, distinct or not, from I (j), and a denote an integer of the form

a = H aj.

(2.48)

t <j
We shall restrict q and d to be of the form q = a, d = pa', y < pa' <, z. It is then

easy to check that (2.47) holds - we leave this as an exercise.

7

Proof of Theorem 21 (ii), (iii) - lower bounds

43

We need an upper bound for la. We have

a,<exp{h Y l

L'+1}<exp{2hLk-1}
16j
)))

whence for large y, we have (since q is an a), qd \ y1/2z \ y- 1/2x.

(2.49)

We may now embark on the lower bound computation. From the above, R

Y 1 = Y 1( d,Y g

gdr<x

qd<x

y
y
By (2.49) and Theorem 06, we have

0( -,y)»x/gdlogy moreover the condition qd < x is redundant. So x

1

1

1

R» log y,aa,ay/Q
(log y) -1- , and we obtain

By the Prime Number Theorem, the p sum is x

2

1

R»(logx)2+g H 1<j
Ya. J

h

x

1

H

>>(logY)2+# 1<j
2

1

h1

peltylp

Using the modest approximation Y- 1=1 pEI() p

\

1+0logL (1 J) LJJJ

and Stirling's formula, we readily find that the product above is Y)-Q())+2+fiL-C,

>> (log

which yields (2.45). Notice that Stirling's formula gives rise to a factor h-2k, and it is to keep this in check that we need L so large. It remains to deal with (2.46). We shall need convenient upper bounds for x(n) and we fall back on the general principle of §0.5, writing x(n) < v'(na) (log

3t)-zlogvL-41ogv

(2.50)

1 (2.51)

where ve(0,1] and te[1, y] are parameters at our disposal. We shall also use

(r(n;Yz))1 d,d'In

y
min

tt In/m

y/m
44

2

Sieving by an interval

and we bear in mind that, as in §2.5, the inner sum on the right is empty unless m < ny: = z - y. Let a be fixed, 0 < a\<, 1. From (2.50) and (2.51), we deduce that

S: = Y nx

x(n)(t(n;z)

IL4lo(S1+S2)

(2.52)

where 3y)- llogv Y wn(n,m)(log 3m) - tlogw

S1: _ Y_ vn(n,Y)(log n<x

1

min

tt In/m

m<Jy

Y/m
S2:= Y_ vn(n,Y)(log 3y)-Alogv

wU(n,y/m)

n<x

(log

min

,/Y<m<7y

)iogw

3y

1,

m /l

Y/m
provided v < 1, w 5 1, vw > a. Notice that we have used the fact that x(n) = x(n)2, applying (2.50) twice in each sum, and that v and w need not take the same values in S1 and S2. In S1 we write n = mtt'd and sum over d first. This gives 3y)- llogv

S1 = (log

`

x

Y_ (vw)'(m)(log

3m)- llogw

m <,/y

vS2(d,Y)w)(d,m)

v12(tt',Y)wS2(tt',m) d<[x//mti

y/m
We have v'(d'y) < va(d,m) and x/mtt' > xm/z2 > in. Hence the inner sum is << (x/mtt')(log 3m)vw-1 by Theorem 01. Also S2(tt', y) > fl(tt') - 2, and so 3y)- l logv Y (vw)a(m)(log 3m)v ` _ 1- llogwm- 1 Z

S1 << x(log

m <,/y

where

Z=

1 vn(t) wfl(t,m) <<(log y)v -'-'(log

Y_

3m)vw-v

Y/m < t
by Shiu's theorem: this applies because y/m > ,Jy. Thus S1 <<

x(logy)2v-2-2Q-xlogv

Y

1

(vw)'(m)(Iog3m)3vw-2v-l-A logw

m <,/y m

The m-sum may now be majorized by partial summation using Theorem 01

again. It is << (log

y)4vw- 2v- 2logw- 1 loge

provided

Y

4vw - 2v - A log w - 1 > 0

(2.53)

(else it is the partial sum of a convergent series). Assuming this last condition is realized, we find that S1 <
Proof of Theorem 21 (ii), (iii) - lower bounds

7

45

and the exponent takes its minimum value - Q(A) when vw = A/4. We choose v = A/2, w = 2: the left-hand side of (2.53) then equals /3 ? 0, and we have (2.54)

S 1 << a x (log Y) - Q(z) 1092 Y

We turn our attention to S2. Arguing as above, we arrive at S2 << ax(log y)V - 1 - xlogv

(

1 vi2(m) wf2(m,y/m)

`

,/y<m
3

vw--alogw

1

log y

x

(vw)fl(t)2

y
m

/J

We cannot appeal to Shiu's theorem to bound the sum over t, because (z - y)/m may be smaller than any power of y/m, indeed it may equal 1. We use (2.39) instead; we have m < ny so 3Y vw- 1

(vw)S2(t)

y/m
t

<< (log y) -

log m

loge y,

and

S2 «a x(log y)u l- 2P - l log v(loge

y)2

Jy <m
1m vf2(m) w 0:(m,y/m)

log

Y

m

where

A=A(v,w)= 3vw -v-2-A,logw. Put K(s):= E v"(m)wS2(m,Y/m) mss

Since 12(m, y/m) >, S)(m, y/s) and w < 1, we have for '/y 5 s'< y 3Y vw-v K(s) \ E V0 (m) wf2(m,Y/s) <<S(log S)V - 1 log S

m<s

by Theorem 01. Whence the inner sum above is )AdK(s)<< (log y)A+vwlog2Y (log Sy

J

by partial integration, provided

A+vw-v=4vw-2v-2-.1logw? -1.

(2.55)

We then have S2 <
y)4vw-2logvw-20-3(log2y)3.

The exponent is a minimum when vw = A14, and we select v = )/2, w =1 as before, so that (2.55) is satisfied. This yields S2 << x(log Y)-Q("' (log2 y)3

A

2

46

Sieving by an interval

and we deduce from this, (2.52) and (2.54) that S << x(log y)-Q(')L(log y)12,

(taking a = 1/log 16). This proves (2.46). We may now obtain the lower bound for H(x, y, z). Notice that (2.43) may be re-written in the form

H(x,y,z)>, R2/(2S+R) and that the right-hand side is an increasing function of R. We insert (2.45) and (2.46); this yields the lower bound in (2.10) provided f3 5 log 4 - 1, because Q(2) = G(fl).

To complete the proof of part (ii), we have to consider the case > log 4 - 1, = 0(1). Let $1, 1 and z1 be related in the same way as Q, c and z, that is by (2.8), and let 1 = i (y) -* oo as y -> oo. For large y, b l > i; and z1 < z, so that H(x, y, z) >, H(x, y, zl). By part (i) of the theorem, we have H(x, y, z1) =(I + o (1))x(log y)-1' >>

x(log y)-c(e)L(log y)-"

provided b l c1 ",/log3 y. The result follows. The lower bound in (2.11), valid for the range 2y < z ,<min (y3i2, x 1i2 )

may be proved in a similar fashion, a slight extra complication arising from

the `small' primes < z/y. We have to consider, instead of z(n; y, z) the quantity i(b; y, z) where b is the largest divisor of n free of prime factors 5 z/y. The definition of x has to be modified too: we ignore `small' prime factors. There is a simplification in the computations inasmuch as z - y > y. Thus there are no `short' sums of multiplicative functions. We shall not give a complete proof here, hoping that the reader who has reached this point will be able to see the main lines of the argument and moreover cope with the rather similar technical difficulties which arise. For a detailed proof we refer him to Tenenbaum (1984).

2.8

Proof of Theorem 21 (iv) - large z

We prove here that the formula (2.12),

H(x,y,z)=x(I+OI ll

gy I/I,

holds, uniformly for 1 5 y < z < x. Let P be the product of the primes

8 Proof of Theorem 21 (iv) - large z

47

pE(y, z]. Then

05[x]-H(x,y,z)< E 1«x H (i_)<<xb02Y logz P 1

n<x

y
(n.P)= I

by Theorem 01 and Mertens' Formula. This is all we need. We remark that, although easy, the upper bound for [x] - H(x, y, z) is essentially optimal. Notice that

Y 0 -,mx z

[x] - H(x, y, z)

m
>>

tog

zlogmin(2z,y)

by Theorem 06. Suppose ae(0,1) fixed, z 5 xy-', y > yo(a). Then log Y

[x] - H (x, y, z) >> axlog

z

We see that if (log z)/(logy) is large it is almost the same to ask for a divisior as a prime factor in (y, z].

48

Notes on Chapter 2 Sets of multiples. Let d' be the intersection of all the sequences d such that M(sd) _ -4. It is clear that d' will be both minimal and primitive, provided .4(d') _ -4. It is sufficient to prove that for two sequences d1, d2 such that -4(S12) = -A, we have -4(d1 r) S12) = -4. Suppose not, and that b is the least member of -4\2(d1 n d2). Then b = m1 a1 = m2a2 where a1 E.d1, a2ESI2 and plainly a1 # a2. Suppose for example a1 < a2. §2.1.

Then m,>1. Also ate-4(s11)=.4, and since a1
§2.2.

Hk(x,y,z):=card {n:n<x,i(n;y,z)=k} 00

Ek (Y): x= co lim x -' Hk (x, Y, 2Y), a(y)= E EJA k=1

Erdos has conjectured for some time that lim Ek(Y) = 0; Y-- E(y)

(1)

indeed at one time this was considered by him as a possible strategy for his conjecture dealt with in Chapter 5. At present (1) is unsettled, but we think it may be false. Recent work of Tenenbaum (1988) shows that El(y)/E(y)= (logy)'U1), more precisely (with L as in §2.2), L(log y)-` «E1(Y)/E(Y) ,<1

(y>,2).

In the same paper, estimates comparable to those of Theorem 21 are given for Hk(x, y, z), keZL+ fixed. In view of these results it is tempting to formulate

the following conjecture. Conjecture.

For each k >, 1, there exists limy-. (Ek(y)/E(y)) =: dk with dk > 0

and Y_dk = 1.

Erdos has also conjectured that E1(y, z): = limx. x _ 1H1(x, y, z) is a unimodular function of z. Precisely where E1(y, z) reaches its maximum is then a very interesting question. From Tenenbaum's results, it follows that E1(y, z) is unimodular to within a factor of incertitude L(logy)o(')

49

Exercises on Chapter 2 20. Put d(y) = limx-,,,x-1H(x, y, 2y) and suppose that (2.1) holds, i.e.

liminf d(y) = 0. Show that given EE(0,12) there exists {yk -+ 00 } such that

(k>0),

(1)

(ii)

H (x, Yk, 2Yk) ,< 2xd (Yk)

(k '>0, x > Yk + 1)

Now set d: = Uk(Yk, 2Yk] n 7L+ and let B(x) denote the counting function

of J(d). Show that (iii)

limsup x -1 B (x) > i,

(iv)

liminfx-1B(x),<E.

Deduce from Theorem 21 that, for sufficiently large c, we may take Yk = exp{c(2k/E)11a}, 6 as in (2.3).

For

2>0

and -4,, _ set da,:= Uk(exp kA, 2 exp kz] n Z+ that 2 > 1/8 = d-4,1 < 1. [Hint: Use Behrend's inequality (1948): if T(a1,a2,.... a.) denotes the density of the integers divisible by no ai, then for any ai, b; 21.

(d ).

Prove

T(al,...,am,bli...,bn)>T(a1,...,am)T(b...... bn)

(1)

(For alternative proofs of (1) see Halberstam & Roth (1966), Chapter 5, or Ruzsa (1976).) Hall & Tenenbaum (1986) prove that d.4a, = 1 for 2 < 20 = 1.314 57..., and conjecture that dR2 =1 pl < Al = 1/(1 - log 2).] 22.

Put 0(n, t):= i(n; t, et), A(n) =max 4(n, t) and E(n, t) = 0 or 1 according

as 0(n, t) = 0 or not. Show that, uniformly for x > t > 1, both (i)

Y A (n, t) = x + O (x/t) n<x

and

(ii)

Y 0(n, t)2 << x log 2t. n<x

Now let c > log (1/6) (b as in (2.3)), and for 1 <j s k = [(log3 x)/2c] set tj = exp exp exp (cj). Set j(n) = max t j: 1 <j < k, 4(n, tj) 0}. Show that (iii)

Y 0(n, tf(n)) > Y Y 0(n, t,)(1 n<x

1<'
-Y

J<m
and for all j, m, 1 <j < m < k, that (iv)

E 0(n,t3)e(n,tm)<< xexp{-12(b-e-`)e`m}. n < x

2

50

Sieving by an interval

Deduce that (v)

Y L(n)

x(k + O(log k)).

n<x

23.

Let OeC2 [0, 1] be real, F(n; 0): _ Y-i<x(n) 0(di/di+1), where di = di(n).

Put k = [i(n)/2]. Show that (i)

F(n;0)=2 Y 0(di/di+1)+O(1) 1si
Put (p (t) = 0'(t) + t0" (t), s(n; y, z) = 1 or 0 according as n has a divisor in (y, z] or not. Prove Jdk fz (P ()n;yz) -'4 = (k - 2)0(1) +o (ii) Jx ('z (iii)

J

J

(P

dk

+1

i
1

(_)(n;Yz)___<
(i-)

(n < x).

1

Hence obtain the formula (2.5). 24.

With the same notation as in Exercise 23, prove that

F(n;0)=(0(1)+O(009 n<x

,/10g2x))xlogx,

x)

and show that the exponent b is best possible. 25.

Let ae(0, 1) be fixed, and define Prop (n) = card {i: 1 < i < i(n), di+ 1(n) < (1 + e)di(n)}.

Use Exercise 24 to establish Prop (n) _ 1 + O nix 26.

\ Clog x) , jlog2

x)) x log X.

Define

Y (di(n)ldi+1(n))'.

k,(n):

1
Prove that

Y k,(n) _ (1 - K,(x)/(log x)b)x log x n-< x

with e -"L(log x) -` << K,(x) <ro > 0. [Hint: use (2.5).] 27.

Estimate

n

_ di(n) )2

C

Y1

i<x(n)

1

di+1(n)

Exercises on Chapter 2 28.

51

Let T + (n):= Y_E(n; 2k 2"'), that is the number of k for which (2', 2k + 1]

contains at least one divisor of n. Prove that T+(n) < min (T(n), [log n/log 2] + 1) and deduce by the method of §0.5 that T+(n)<<x(logx)i_b

Y_

n<x

Use Theorem 21 to divide the right-hand side by %/1og2 X-

Let g(n):=card {i:15i
29.

between g(n) and T+(n) and deduce an upper bound for Y_ {g(n): n < x}. [This sum is >>x(log x)1- 6L(log x) (cf. Tenenbaum (1988)).]

For x > z > y > t > 1 set H(x, y, z; t) _ Y_,,<x P oo>ta(n; y, z). Show that, for ve(0, l], w > 1, an upper bound for H(x; y, z; t) is 210.

log Y C

logy/Iog2

l

t/

vt2(n,y)T(n; Y_

y, z) +

n<x

(Iogy

loges/Iog2

tog t

I wSl(n,Y) n<x P (n)>t

P (n)>t

Hence show that, for 2y'< z < min (y2, Jx), H(x, y, z; t) <<x(log 2y)-b(log 2t)b-2 log

tz

tz Y

211.

Let ey denote the density of the integers n for which M(n,Y) _ Y_ µ(d) 0 0. dIn

d
s

Prove that c << (logy) _ by first establishing

Eye li mx-1 Y

P<'y

\P P

and using the result of Exercise 210.

3 Imaginary powers 3.1

Introduction

For each n and real 0 we define T(n,0)=

d'° din

and we have e-'be

1

dIn

*1

2n

0) ao

T (n'

-e - iaO iB

dB

(3.2)

aS logd-
(where the * denotes that if e° or e"In, their contribution to the sum on the left is Thus in principle any question about the divisors of n can be re?).

stated in terms of T(n, 0), and this is a useful idea because T(n, 0) is multiplicative. It makes an appearance in some form in each of the next three chapters of this book. If IT(n, 0) 1 is appreciably smaller than T(n), and this for a suitable range of values of 0, we may infer some degree of uniformity in the distribution of the divisors of n. Thus the information that is usually needed is an upper bound for a suitable average, possibly over both n and 0, of IT(n, 0)1. For fixed non-zero 0, the function I T(n, 0) 1 has average order c(0) loga n (a = 4/it - 1 = 0.273 23...), whereas the average order of T(n) is log n. What is perhaps surprising is that, for almost all n, T(n, 0) << T(n)E, and we begin by

proving this. We avoid the phrase `normal order' which has a precise technical meaning, inapplicable here (cf. §4.4 for a discussion of this point).

3.2 A p.p. upper bound for IT (n, 0)1 Theorem 30. Let 0 be fixed, real, and non-zero, and c(n)-* oo as n -+ oo. Then JT(n, 0)( < b

(n)Ooglogn

p.p.

(3.3)

The function T(n, 0) oscillates rapidly as 0 varies, vanishing wherever T(p°, 0) vanishes for every p, pn 11 n. Because the numbers log p are indepen-

dent over the rationals these zeros are simple, and there are about (2n) -' (b - a) log n of them on the interval a < 0 < b.

2 A p.p. upper bound for l r(n, 0)1

53

A lower bound complementing (3.3) would require arithmetic conditions

on 0. Another open problem is to determine a p.p. upper bound for (3.4)

max I T (n, 0) I

ase
where a < b, 0 < ab. What is the infimum of the numbers y such that this is «µ(logn)o p.p.? The proof of (3.3) depends on the method of low moments. The name will become clear as we proceed. We need some preliminary results which will also be useful in later chapters. Lemma 30.1. Let f be a periodic function of bounded variation over the period [0, 2ir] and having mean value 2a

1

f: = 2n

f (v) dv. o

Then, for real 0, w, z such that 0

0, 1 < w < z, and every positive c, we have

W Zpf(0logp)=flog

)+O

Cg

)

(og.f)

\

loges

w

10 l

+O,((M(.f)+(1+I0I)V(f))e_ hb0 W) where

(3.5)

z('nldf(v)I

M(f):= sup If(v)I, V(f):= V

,J

o

Proof. We may assume 0 > 0. We require the Prime Number Theorem in the form 9(t): = n(t) - lit «at exp (- 2c1/log t). Partial summation yields 1 W

p

Z

pf

(0log p) =

Jf(Olot)dt ,

t og

+ [-'(t) .f (0 log

= f log ('

(los z logw j

t)J W

-J

ai°gz elagw

w

e (t)d

-

(r f (0 log t) / \ v

Z'(t)

JJ

W

t

d f (0 log t) + O,(M(.f )e-`J'O9W ).

The second term here is << V(f)/I0)log w, applying the second mean value

theorem to the real and imaginary parts, and noticing that for all a, b

54

Imaginary powers

3

The third term is (using the periodicity of f), << a

B1ogw+2rz

logw

W

df (v)I

k=o

(v + 2nk 11

exp

0

lI

I01)V(f)e-cIlogw

<<,(I +

since the sum over k is <<,(I + 101) uniformly for v >, 0. This proves (3.5).

Lemma 30.2. Uniformly for % > 0 and real 0, 101 > 1/log x, we have, for every positive c,

Y

IT(P,0)Iz=F(d)1092x+(2'-F(A))log+

Bl

P

+ A(.1, 0) + O

2z I0I

log X

/ + O,((1 +

where A (2, 0) << 2'(A + loge (3 + 101)), and 1

2rz

I1+e'vlzdv=

F(.1). 21r

1

)

(1 I(1+22.1).

(3.8)

o

Explicitly

A('1,0)=F(2)y+

{1- P)}

- (22 - F(A)) log+ IeI

where y is Euler's constant. (Another formula for A(.1, 0) appears in Exercise 34.)

Proof. We apply Lemma 30.1 with f (v) = It + e'° IA, j= F(.1), M(f) = 2z, V(f) = 2M(f). Hence

1 Ii(P,0)Iz-F(.1)logl loges logz

wzp =0

The right-hand side tends to zero as w - oo, whence, by Cauchy's criterion for convergence, there exists a constant A' = A'(2, 0) such that 1

IT(p,0)Iz=F(.1)log2z+A'(A,0)+8(z;.1,B)

(3.10)

p,z P

say, where E(z; ), 0) = o(1) (z - oo). Put w = x in (3.9) and subtract the result

2 A p.p. upper bound for I r(n, 0)1

55

from (3.10), then let z -> oo. This yields E - I T (p, 0) 1 = F(A)1092 x + A' (A, 0) p<x P

+0(

2A

+ 0,((1 + I0I)21e

I0I log x

(3.11)

,/1ogx),

and it remains to find a uniform estimate for A'(2, 0). If 101 > 1, we substitute x = exp (log2 (3 + 101)) in (3.11), taking c = 1, to deduce that A'(2, 0) << 2.1og2 (3 + 101). If 101 <, 1, we put x = exp (1/101). For p <,x we have 101 log p <,I, so that IT(p, 0)1= 2 cos (2 0log p) > 2 cos (xc/6). By

the mean value theorem, Z log p) < 4 sec 6.02log2 p

I- Cos.' whence

I p<xp Y_

Y IT (P, OW = 2 Y 1 + p<xp

= 2 log

log2

0

p

P

p<x

+ O((A +

1011

Comparing this with (3.11) we see that in this case and so for all 0, 0

(2 - F()..))log(1/101) + O((1

A'(A, 0)

0, we have

A'(A, 0) = (2 - F(A)) log+ CBI + O(21(2 + loge (3 + 101)))

and we set 181

to obtain (3.7). For the explicit formula for A(2, 0) we recall (Hardy & Wright, (1938), Theorem 428) that 1

1

E -=log2x+y+

p<xp

p

jlo(1 --P) +P-'f +0(1),

and we multiply this by F(2), subtract it from (3.7), and let x -+ oo. Lemma 30.3. Uniformly for 0 < y < yo, 0 < 2 < 2 1/log x < 101 < exp(,/(log x)), we have

and real

0,

0,x0x(logx)F(I)r-1

Y_

Ii(n,0)I'y"")<<

n<x

x where B = B(yo, Ao).

,

(1

2zY-F(A)Y

1

+ 1e1

I

/

logB(3 + 101)

(3.12)

56

3

Imaginary powers

Proof. We apply first Theorem 01 to deduce that the sum above is <<

11+pIx(p,0)IA+...1«

log X

loggX o<x

exp{y I l

I Ii(p,0)Iz

Psx p

g

and then apply Lemma 30.2.

Proof of Theorem 30. Since 0 0, we may assume that x is so large that 101 > 1/log x. We fix 0, and put y = yo = 1o =1 in Lemma 30.3 so that we have, uniformly for 0 < A < 1, Y_ h(n, 0)I2 <<x(log x)F(;L)-1

(3.13)

n_< x

We have F(0) = 1, and 1

F'(0)=2

2n

log Ii +e"Idv=0. 0

Moreover from (3.8), F(2) is analytic except for poles at A

1, - 3, - 5,... ,certainly FEC2 [0, 1]. Taylor's theorem therefore implies that, for a suitable constant K, F(1) < 1 + x22, 0 < A < 1. We put A = 11V 1092X so that the right-hand side of (3.13) is O(x). Now let fi(n) -+ oo as n - oo, and let E be the sequence of integers n such that I r(n, 0)1 > S

(n),Jloglogn

We put c1 (x) = min {fi(n): n > Jx}. Then if n e E n (.,/x, x] and x is sufficiently large, we have IT (n, 0)12 > 1(x)1/2 whence

E Ii(n,0)12=o(x),

card {En [1,

n-<x

and E has asymptotic density 0 as required. 3.3 Ratios of divisors

Many questions concerning divisors, in particular some of the questions about propinquity, are better stated in terms of the ratios r = d/d' (d, d' In). In some cases it is appropriate to count only distinct ratios: if n = pi' pz2... pkk

then these are the rational numbers

r-

11' P2=...pkk (-a<
(3.14)

and their number is

= U(n)

k

fl (2ai + 1).

(3.15)

U(n) < 3il(n);

(3.16)

=1

Notice that, for every n, we have 3 w(n) <

57

Average orders

4

this 3 will make its appearance in several results in Chapters 4 and 5. We label the distinct ratios in increasing order, r1 < r2 <
P(n, 0) = Y r'u = u=1

Y,

(d/d')le

d,d'in

(d,d')=1

_ fl (1 +2cos(9logp)+

+2cos(9alog p)).

(3.17)

Palln

This is analogous to the definition (3.1) of T(n, 0), and the two functions are connected by the relation 2

(3.18)

P(n, 0) _ Yµ(t) tin

Of course if we count the ratios according to the number of representations r = d/d', the function corresponding to p(n, 0) is just IT(n, 0)12. There are analogues to the results of §3.2: we state without proof the following. Theorem 31. Let 0 be fixed, real, and non-zero, and (n) -> oo as n -p oo. Then x(n)'b0 0gn p.p. IP(n, o)I <

3.4 Average orders We consider the average order of IT(n, 9)IA (A > 0), weighted with yw(n) or when appropriate yn)n). Theorem 32. Let y > 0, A > 0, 0

0. Then o)IAyw(n)x(logx)F(A)y-1

IT(n

r(F11Y)

n5x 1

F(A)Y

X (1-p)

Y (l+,o)IA+...)

(3.19)

where F(A) is as defined in (3.8).

This is implied by a general theorem of Wirsing (1967) on sums of multiplicative functions together with Lemma 30.2. For the applications in Chapter 4, we need the case A = 2, and a variant in which 1T(n, 0)12 is replaced

by p(n, 0). We require a uniform error term. This can be quite modest and we avoid a more complicated formula and proof. We shall have y t 1 and it is convenient, though inessential, to replace w by fl.

58

3

Imaginary powers

Theorem 33. Uniformly for real non-zero 0 we have 6

IT(n,0)12 =nz 12 (1 +iB)IZ(xlogx+(2y- 1)x) n5x

+ {A(0) + Re(A2(0,1)x'B)}x + O {x112(1e11i3 + 1og512x)log'12x},

(3.20)

where

A(0)=_2 {('(1 +i0)1'(1-i0)+C(1 +i0)C'(1-i0)-2

1;(2)

IC(l +iO)I2},

and, fork=1,2,0o0,IYI<2, Ak(0, y).- 2

k(1 + i0, y)((1 + 2i0, y) (1 + i0)C(2 + 2i0, y2)

For each fixed y, 0< y < 1, and uniformly for real 0, 1 /log x ,<10I exp /log x, we have Y IT(n,0)12yn(")= H2(Y)IK(1 +i0,Y)12x1og2y-lx n5x logy- 1

H(y) {Re(A2(0, y)xi0)} x

x

F(Y) +Oy{(I0I-1-2y+1og13y+2(3+I0I))xlog2y-2x}

(3.21)

and also p(n,0)yn(")=H(Y) f I((1+i02Y)IZ+Re(A1(0,Y)x'°)lxlogy-'x

Y

n5x

r(Y) l

(2, y')

J

+0 y{(IBI 1-2y + log'oy+2(3 + I0I))x logy-2x}

(3.22)

where

Y )-I= jo yfl(n) 1

n

H(Y)= H

(3.23)

(3.24)

The function t (s, y) is initially defined in the region a = Re s > 1, y < 2.The

product formula extends the range of definition toy > 2, but there are then

poles on the lines a = log y/log p, for each p < y. We are interested in analytic continuation across the line a = 1. The function

H(s,Y):=exp{nYmmsy} Pm

p

(3.25)

4

Average orders

59

is analytic in the half-plane a > max (Z, log y/log 2), and, in any simply connected sub-region of this half-plane which does not contain zeros of C(s) or the point s = 1, we may define C(s, y) = H(s, y)((s)''

(3.26)

as a single-valued, analytic function of s. We note that H(y) = H(l, y). Notice the differences between (3.21) and (3.22). The function p(n, 0) is not

of fixed sign and there is some cancellation. The main term in (3.22) is smaller, and oscillates. The substitution of f) for the more usual w in Theorem 33 enables us to employ a generalization of a formula of Ramanujan (1915), cc,

l r(n 0)12

Yflsn)

_ (2(s, Y)4(s + i0, y)((s - i0, Y) ((2s, y')

n

n=1

(3.27)

but is unimportant - there is an analogue of the theorem, with co throughout, identical error terms, and slightly clumsier main terms. Proof of Theorem 33. We denote the function (3.27) by R(s) and employ Perron's formula in the form given by Titchmarsh (1951, Lemma 3.12). We make x half an odd integer (which does not affect the final result),

c = 1 + 1/log x, and we note that

Ix(n, 0)1 , no)

(Hardy & Wright (1938), Theorem 317). We choose T = x + 101 if y = 1, T = x4/l °g log s else, and we have 1

g)I2y"")=

IT(n 4

21r1

(`c+iTR(s)xds J c-iT

S

OE(x`)

+ O(x1-1/log logs)

(Y = 1),

(Y<1). When y = 1 we follow Titchmarsh (1951, §12.3 in the case k = 4, in which Titchmarsh has ?4(s) instead of R(s)), moving the line of integration across the poles to a = Z. The main terms in (3.20) come from the residues. On

a = 2 we have 1/C(2s) << log T, and we apply the Cauchy-Schwarz inequality twice to obtain << (x 112 log T)J(0)l/2 J(0)114J(- 0)1/4

where J(0)=

f IS(2+10+it)14 T

/dt l << 1e12/s+log5T.

t + 4)

This last inequality may be derived from the fourth power moment of IK(z + iu) I (Titchmarsh (1951), eq. (7.6.1)), combined with any upper bound C(2 + iu) << I u I" with q < -l1 (Titchmarsh (1951) §5.18). We obtain (3.20).

60

3

Imaginary powers

Now let y < 1. We have

(a>, 1-2c1

c(s)00,c(s)<< log, 1tI

i t°I

(3.28)

(Titchmarsh (1951), Theorem 5.17), and we deduce that (s) «log2 t 1 1109 C(S) I < < 1092 I t I,

(3.29)

1092 It I

C(s)

for a > 1- c 1(log21 t I)/log I t I (It I >, t 1). To obtain the upper bound for

Ilog-C(s)I we apply the Borel-Caratheodory inequality (Titchmarsh (1939), §5.5) with concentric circles centred at 1 + it, radii r1 = 1 - a, r2 = 3r1/2, using the upper bounds Re log C(s) = log I C(s) I z log log I t I + O(1) on the large circle, I log C(1 + it) I < log log I t I + O(1) at the centre. To estimate the logarithmic derivative we apply Cauchy's formula C'(s)

1

log C(z) dz

2lti D (z - s)2

S(s)

D is the circle Iz - sl = ac1(1og2 It1)/log Iti.

We move the path of integration in Perron's formula to a= 1 t' = max (It1, t1), where c2 S c1, c21og2 t 1/log t1 < ?, joined up to c ± iT by horizontal segments, and with three lacets around the algebraic singularities of R. Note that 101 5 exp,/(log x) < T/2 =

c21og2 t'/log t',

exp {4(log x)/loge x} when x is large. Except on the lacets we have R(s) << (log T)20 and the contribution of this part of the contour is «6xe-acloglogx>2 log2lx

0 <4C2),

which is negligible. On the lacet around s=1 we write s1 R (s) _: S(s)/(s - 1)2y, where 1

S(s) = S NZ(s, Y){(s -

C(s + i6, y)C(s - i6, y) C(2s,Y2)

and we approximate to S(s) with S(1). We need an upper bound for IS'(s)I and, differentiating S logarithmically, we find from (3.28), (3.29) that S'(s)<<

{101-1-2y+logl0y+2(3+161)}.

An integration from s to 1 yields

S(s) = S(1) + O(Is-

11(161-1-2y +logloy+2(3+101)))

and integrating the error term along the cut gives <<

{161-1-2y+logloy+2(3+161)}xlog2y-2x.

For the main term, we extend the lacet to a loop from - co around s = 1.

4

Average orders

61

The error at this point is negligible, and we obtain

Xs-1(s-1)-2Yds= S(1)

S(1)x 211

f(-

x(logx)2y-1

r(2Y)

Go)

by Hankel's formula. (Whittaker & Watson (1927),

§12.22). Since

H(1, y) = H(y), this is the main term in (3.21). The second term there arises from a similar calculation on the lacets around 1 ± i9, the error involved being then <<x{j0j-1-'Y +1og15y+2(3+IOD)}logy-2x

which does not exceed the error term exhibited in (3.21). The left-hand sides of (3.21) and (3.22) are related via (3.18), but we cannot deduce (3.22) directly from (3.21). Rather, we proceed as above, replacing R(s) in (3.27) by c(s, Y)4(s + i9, YMs - i6, Y)

R 1(s):-

C(2s, y2)

Notice that the three singularities now carry equal weight.

62

Notes on Chapter 3 We may write i(n, 0), rather clumsily, as aie(n), employing the familiar notation aa(n) = Y_ da. The first genuine application of aa(n) with complex a

seems to be the proof that 4(1 + i9) 0 0 of Ingham (1930) (cf. Titchmarsh (1951), §3.4), which depends on Ramanujan's formula ' aa(n)ab(n)

- C(s)C(s - a)C(s -

b)

a b = - i9: this is (3.27) with y = 1), and a theorem of Landau. The same method is useful for L(1 + i9, x) # 0, x real. Envisaged as a means of coping with divisors, i(n, 0) was formally defined in the modern notation by Hall (1975); but it had already appeared in Hall (1974), where it was used to show that, on a suitable sequence of integers n of asymptotic density 1, the set of real numbers {log d: dln} is asymptotically uniformly distributed (mod 1). Indeed it follows from the upper bound for discrepancy of Erdos & Turan (1948) (cf. Kuipers & Niederreiter (1974)), that if we define

D(n):=

sup 0
I Y- x(a,b] (log d) - (b - a)i(n)I, din

where X(a,b] is the characteristic function of the intervals (a, b] (mod 1), then the discrepancy D satisfies D(n) < log"+En p.p., with K = log (4/it). This result was obtained independently by Katai (1976). It is an open problem whether it holds with K = 0. The functions (loge d)a (a > 1) (Hall (1978)), (log d)a (a > 0), (Tenenbaum

(1982)), )d(A irrational) (Dupain, Hall & Tenenbaum (1982)) are all uniformly distributed (mod 1) in a similar sense, that is D(n) = o(i(n)) p.p. If we think of the divisors as having broadly exponential growth the results concerning (loge d)a and (log d)a above correspond very well to those for (log n)a, na in 7L+. In this scenario da grows very rapidly; it is shown to be

uniformly distributed in Hall & Tenenbaum (1986): this paper gives a background and survey of the area. Divisor density was defined by Hall (1978). If sat is an integer sequence and z(n, d) denotes the number of divisors d of n such that dEd, we say .4 has divisor density z, and write D d = z, if T (n, d) - zi (n) p.p. For example, since (log d)" is uniformly distributed (mod 1), the sequence

d(z):={d:(log d)a 0 we may also infer that the set of multiples

R(d) has d-4 = 1.

Notes on Chapter 3

63

An intriguing conjecture of Erdos, related to that studied in Chapter 5, was that there exists A > 1 such that almost all numbers have a divisor in at least one of the intervals (exp k2, 2 exp kA] (k = 1, 2, 3, ... ), and this was proved by Hall & Tenenbaum (1986), for all A < 1.314 57..., using divisor density. The method is to set a = 1/) in 4(z) above, with z -+ 0 essentially like (log n)°`-'.

Since zt(n) is then relatively small (we only need it to be > 1) a good estimate for the discrepancy is required. An open problem is to determine how large A may be in Erdos' conjecture.

64

Exercises on Chapter 3 30. Use the method of low moments and Theorem 01 to show that if (n) -> oo then (log n) log 2 fi(n)- Jloglogn < T(n) < (log n) log 2 (n)Jloglogn

p.p.

31. Let 0 be fixed. Prove that infinitely often lT(n, 0)l > 2Xn where Xn

_

log n 1092 n

clog n (log2 n2 1093 n

and c is a suitable constant. 32. Let F be as in (3.8). Prove that for each 6 > 0 the equation 2F'(2)

-

F(2) + 1 = 6 has a unique positive root 2 = 2(S). Prove that if 0 is fixed, 0 0, then, except for << x/(log x)s exceptional integers n < x, we have IT(n, 0)l < (log n)°, where D = F'(A(6)). 33.

Prove Theorem 31.

34.

Prove that, for real t, and 2 > 0, oo

I1 + elt Iz = F(A) +

Y am(A)elmt m=-.0 m*0

where am(A) << I ml -1-µ, µ = min (1, A). Prove that

A(2, 0) = AF(2) - (2' - F(2)) log+

00

1

le

+

am(2)Z(mO)

m

l

m#0

where

A=1im{ Y 1-log2x}, Z(6)_YpiB-1, 0*0. X-O lP<XP

))

P

35. Use the first part of Exercise 34 to show that, if (a, b) = 1, max (a, b) > 1, then

1 f2,,

l(l+e'°°)(l+ei6v)ldv< A<2

2>t

where A is an absolute constant. Use Lemma 30.1 and Theorem 01 to show

that if 0/cp is rational and not zero or ± 1 then Y I T (n, 0)T (n, (p) I <<x log" - 1 x. n_< x

36. Prove that as max (a, b) -+ oo the value of the integral in Exercise 35

converges to 16/n2. Find out how the << in Exercise 35 depends on 0 and (p when 01(p is rational. Hence prove that, if 0/qp is irrational, then Y IT(n,0)T(n,(p)I << n-<x

x(logx)16/rz2-1+E.

4 Measures of propinquity Introduction

4.1

We investigate to what extent the divisors of a large `random' integer n lie relatively close together. We define four functions, T (n, a), U(n, a), i+ (n) and A(n), each of which measures in some sense the propinquity of the divisors,

and we discuss relations between these functions. We are interested in p.p. upper and lower bounds where these are available, and suitably weighted average orders. 4.2

T and U -preliminary matters

For a < 1 we set T (n, a) = card {d, d': din, d'I n, Ilog (d/d') I <, logn n}

i(n/S8') (n

2),

(4.1)

Sb'In

(5,5')=1 Ilog(b/b')I 5lognn

U (n, a) =

E

1

(n > 2),

(4.2)

66TH

(b,b') =1 jIog(b/b)5 log° n

and T (l, a) = U (1, a) = 1 (for every a). Notice that in the first line of (4. 1) we have only to add the extra condition

(d, d') = 1 to obtain U(n, a) instead of T (n, a). However the two functions behave quite differently. In particular T (n, a) counts all the pairs d = d' which U(n, a) does not. By setting t = (d, d') in (4.1) we see that, for a > 0, we have (4.3) T (n, a) Y U (n/t, a) tin

with equality when a = 0. We have (cf. (3.15)) T(n, 1) = i(n)2,

U(n, 1) = U(n): = fl (2v + 1);

(4.4)

P Iln

of course we are more interested in the case a < 1. We begin with an elementary result about T (n, 0).

66

4

Measures of propinquity

Theorem 40. Let mel+ and n be any multiple of m. Then

T n, 0)

T (m, 0) T(m)

1<

T(n)

Proof. The left-hand inequality is clear. For that on the right, observe first that, for any integers a > 1, D >, 1, dID, T(aD)T(D)-1 < T(ad)T(d)-1.

(4.6)

This follows immediately on writing the left-hand side as 7

v

+1+V

fi

1

D)

where vp(D) is the p-adic valuation of D. Now, from (4.1), T (m, 0) T (M)

=

1

E * T (M/66%

T (M) 65'Jm

where the star indicates that the sum is restricted to those pairs 6, 6' for which (6, S') = 1, flog (6/6') I < 1. We apply (4.6) with a = n/m, D = m, d = m/66' which yields T (m/(5 5')/T (m) S T (n/bb')/T (n). Therefore T (m, 0)

T(m)

S

1

Y_ * T (nI66') <, T(n) swim

T (n, 0)

T(n)

as required. Theorem 40 has an immediate consequence. For X > 1, put .4'(X):= {nc-

: T(n,0)> XT(n)J.

Then, for each X, the logarithmic density 6M(X) exists.

To see this, notice that .A'(X) has the primitive sub-sequence 9(X) comprising those ne.i such that T (d, 0)/T (d) < X for every proper divisor d of n. By the theorem, . #(X) is just the set of multiples of Y(X). An important

theorem of Davenport & Erdos (1937) (cf. Halberstam & Roth (1966), Chapter V) states that any set of multiples possesses logarithmic density (equal to its lower asymptotic density); and this implies our result. More is true: this will emerge later. The function T (n, 0) is important in the study of Erdos' T+-function and Hooley's A-function, both to be defined later. However, the contribution to T (n, a) from the admissible coprime pairs 6, 6' for which T(n/bb') is large (e.g.

b = 6'= 1) tends to be rather over-emphasized when a is small, and for this reason when considering T (n, (x) we restrict our attention to the range a > 0. The definition of U avoids this phenomenon and some very interesting questions arise when a < 0.

3 T and U - average orders

67

T and U - average orders

4.3

The average orders of divisor functions of this sort tend to be dominated by

the contribution from integers with abnormally many, or abnormally distributed, prime factors. We can reduce this effect by introducing a weight yn(") with y < 1. This device can be particularly helpful when we seek p.p. upper bounds but it should be emphasized that, with functions like T and U which depend on the distribution of prime factors as well as their number,

we can only go so far in this direction with such a simple weight. Theorem 41. Let 0 < a < 1, 0 < y < z. Then T(n,a)yn(")=x(logx)(2"+2)y-1(To(y)+O((logx)-K)),

Y

(4.7)

n_< x

where K = K((X, y): = min { (1 - a) (1 - 2y), (1 + 2a) y, 2O/(2 - y) j,

f(1 - 2y)H4(y) To(y) =

r(2y)r(1- y)T(1 +

y2)'

and C(s, y), H(y) are as in (3.23), (3.24). Also

Y_ U(n,(x)yn(")=x(logx)(2a+1)y-1(Uo(y)+O((logx)-K')),

(4.8)

nsx

where

K' = K '(0t, y): = min { (1 - a)(1 - 2y), 2ay},

F (l - 2y)H3(y) Uo(Y) =

r(y)r(1 - y)F(1 + y)((2, y2)

The reader will observe that, if (4.3) had been an equality, the ratio between the main terms in (4.7) and (4.8) would have been (H(y)l7(20y + y)/ F(2ay + 2y)) logy x whereas in fact T0(y)/U0(y) = H(y)I'(y)/T'(2y), re-

vealing that, as we might expect, the inequality in (4.3) becomes more pronounced as a increases, but not enough to upset the orders of magnitude of the main terms. Theorem 42. Let 0 < a < 1. Then T(n, a)/2n(") =

2H4(i)

0 - O)x log"

x

n((2, 4)

x

+ O {x log' X + x(log3 x)2}

(4.9)

and 3(1f)

U(n,a)/2°`"'= n5z

2HC(2, 4

+ O {x loga-112 x + x(log3

x}.

(4.10)

Measures of propinquity

4

68

In both these theorems we have excluded the case a = 1: T (n, 1) and U(n, 1) are multiplicative functions (cf. (4.4)) for which it is a straightforward

matter to write down the corresponding asymptotic formulae, with very good error terms and main terms which are not obtained by substituting a = 1 in (4.7)-(4.10). This discontinuity in the main terms explains the deterioration in the quality of the error terms above when a -+ 1.

We may choose y optimally as a function of a to obtain p.p. upper bounds. Corollary.

Let ae(0,1), aE(2, 1) respectively. Then

=

T(n,a) (2a + 2)n(n)

U(n,a) n

(2a + 1)n(n)

T1(a)x + O(x(log x)

«(i

«)ni+

_ U1(a)x + O(x(log x)- (2a-1)(1-a)/(1+2a)

(4.11)

(4.12)

where T, (00 = To(1/(2a + 2)), U,(a) = Uo(1/(2a + 1)). Furthermore, if fi(n) --> oo as n --> oo we have, for 0 < a 5 1, T(n, (x) < (log

n)log(2a+2)+c(n)/,/loglogn

P.P.,

P.P.,

U(n, a) < (log

(4.13) (4.14)

where l(a)

_

cc

2+log2 (0<,a,<),

log (2a + 1)

(2 < a < 1).

We obtain (4.11) from (4.7) and (4.12) from (4.8); notice that we require

a > i in (4.12) to make y = (2a + 1)-1 < 2. To obtain (4.13), we insert the p.p. upper bound for 0(n) from the Hardy-Ramanujan Theorem into (4.9) (a = 0) and (4.11) (0 < a < 1). Similarly (4.14) depends on (4.10) (0 <, a 5 Z) and (4.12) (2 < a < 1). When a = 1 we employ (4.4). The exponent of log n in (4.13) is sharp when a = 0 or 1, and that in (4.14) when a = 1. We determine the normal orders of log T (n, a), log U(n, a) later (cf. Theorems 44,45 and 53), and except in the cases mentioned we see that the exponents in (4.13), (4.14) are not sharp, although the true values are not exceeded by as much as 0.06, 0.1 respectively for any a.

There are asymptotic formulae corresponding to those given in Theorem 41, valid for ye(Z, 2) (for larger y we should have to replace S2 by co), in which the exponents of log x become 4y - 2 + a in (4.7) and 3y - 2 + a in (4.8). To(y) and U0(y) alter as well. A different method is needed when y > I, and we do not treat this case in our book (see the Notes). However we

quote a particular formula of this sort without proof - it should be compared with (4.12).

T and U - average orders

3

69

Theorem 43. Let - 1 5 a < Z. Then

2-a

Y U(n,a)

3

n-< x

where now

fl(n)

U1(a)x,

)

_

41-Qr(2f3 - 1)H3(/1) r2(/l)r(3Q - 1)C(2, f32)

U,(a)

( = (2 - a)/3).

In particular the average value of U(n, - 1) is 6/it2. The proofs of Theorems 41 and 42 depend on Theorem 32, the main idea being to approximate T (n, a) or U(n, a) by Fourier integrals involving the functions lr(n, 0)12 or p (n, 0) respectively - see (4.18). We need a result which copes efficiently with the oscillating term involving x'° in (3.21) and (3.22).

This is the following. Lemma 41.1. Let 0 < Re z < 1. Then, for real w

0,

f sint J

0

Rez-1 itw tl+ze dt«ZIWI

(4.15)

In addition, for w > 0 we have sin t " 2 ewdt=O(1). 1/w

(4.16)

t

Proof of (4.15). We may assume Iwl >, 2. The integral equals

fOsint

1

F(Z)

e'tw

t

0

r(z)

lOOe-`vz-ldvdt o

vz -1 arctan

1

v

o

iw

dv

0o vRez-1


dv<
Proof of (4.16). We may assume w > 2. The integral equals Zi {g(w + 1) - g(w - 1) + O(1)} where

dt

g(w):= 1/w

z = wg(1) t

The result follows.

Proofs of Theorems 41 and 42. We shall concentrate on T (n, a), U(n, a) being similar except for one point which requires explanation. We need

70

4

Measures of propinquity

formula (3.21) for T and (3.22) for U: in each formula there are really two main terms, the second involving cos (0 log x) and sin (0 log x) and so rapidly oscillating as 0 varies. It is treated as an error term, and this needs some care in dealing with U because the two main terms in (3.22), unlike (3.21), have

the same order of magnitude. The same analysis might just as well be applied to T: hence the slightly better error term in this case. f(u;h,q)=(1-q-'(Iul-h)) Forh,q>Oput f(u;h,q)=1iflul
transform of f is

f(o;h,q)__02(coshO-cos(h+rl)O)<<min{h+q,1/IoI,1/gIoI2}.

(4.17)

We define W (n; h, q) _ Y Y f (log (d/d'); h, q) din d'In

=2

f.D f(0;h,q)Iz(n,0)I2d0;

(4.18)

if h _ log" n and q is small this approximates T (n, a). Notice that when we come to U(n, a) the extra summation condition (d, d') = I is needed in (4.18) and It(n, 0)12 has to be replaced by p(n, 0). Put h1 = log"(x/log x), h2 = log" x. We have (n 5 x)

T (n, a) < W (n; h2, q)

W (n; h 1- q, q) (x/log x < n ,<x),

(4.19)

and we set q =1/log2 x if a = 0. For a > 0 it will be chosen later, from the range (1/logx,1). In what follows, h will be either h1 - rl or h2. We deduce from (4.18) that

Y W(n;h,q)yn("'=2nJ 1(0;h,q) Z I

nix

+ O(hx log4y- 2 x),

where I: _ {0:1/log x < 101 < exp /log x}. The error term follows from (4.17) and the upper bound

Y Ii(n,0)I2y '°< E i(n)2yn(") «x(log

x)4y-1

nSx

nfix

(which is a consequence of Theorem 01). Notice that it has the order of magnitude of the main term which one obtains when y > 2, restricting this method. We insert (3.21) so that the right-hand side becomes 1

f 1(0; h, q)(Main Terms) do

2n JI

x).

(4.20)

3 T and U - average orders

71

Since y > 0 and h >> 1 the right-hand error term here is negligible. We begin

with the second (oscillating) main term. We have to estimate

xlogy -1x f 2(1+i0,y'(1+2i0,y)xBf(0;h,q)d0 2i0, y2) , (1 + and we notice first that, since (1 + i0) << log 101 for large 101, the contribution

from the range 101 > s is << x logy' x. Now consider the range I/log x < 101 5: we may suppose 0 > 0. We have (say) (2(1 + i0, yg(1 + 2i0, y) _ 0 _ 3y(co + CIO + c202 + 2i0,y2) (1 +

where the infinite series has radius of convergence 4: recall that (s, y) _ H(s, y)4(s)y where H(s, y) is analytic for Re s > 2 if y < 1. If y > 3, we apply (4.17) to obtain 1/s

h0-3yd0 << hxlog4y-2 X.

<< xlog''-1 x gX

1

Let y < 3. The terms from c10 onward contribute << (log 2h)' 3y. 1) x logy - 1 x

(4.21)

and we are left with 1/5

coxlogy-lx' f

1/logx-

sin h+2

110.

2

We approximate sin(rl0/2) by n0/2: the error is absorbed by (4.21). Similarly the upper limit of integration may be changed to co. If y =1', we substitute 0 = t/(h + n/2), put w = (log x)/(h + 1/2) and apply Lemma 41.1 (4.16). We

obtain <
«hxlog4y-2x+xlogy-lx (0
Moreover this absorbs all-the previous error terms. The first main term in (4.20) is H2(Y)xlog2y-1

x

27rI (2y)S(2, y2)

I

I (1 + i0, y)I2 f(0; h, q) dB

(4.23)

and we write =:H2

I ((1 + i0, Y) 12

l(Y)

+ Z(0, Y).

(4.24)

72

4

Measures of propinquity

We have Z(0,Y)=181-2y(b202+b404+...)

and we employ this for 101

(101 <21),

from (4.24) we have Z(0,y)<< log2y(6101),

3; Z'(0, y) < 3.

We begin by estimating the integral involving Z(0, y). From (4.17) and the above,

f,

(4.25)

Z(0, y) f (0; h,11) dO < log2y+ 1 (2/q).

When a = 0 (in Theorem 42) we put 11= 1/log log x so that this is << (log3 x)2.

When a> 0, we can improve on (4.25). Put A= (11 log" x)- 12 and assume that 2 S 3. Then

Z(0,y)f(0;h,rl)d6<< I 01-2yd0<<

J s

1

22-2y

o

and an integration by parts yields fexp,/Iogx

cos h0

Z(0, Y) n82

a

d0«n-1h-1A-2y

so that we obtain (4.26)

Z(0, y) f (0; h, r1) dO << (11log" x)y-1.

i

Next, we consider the leading term in (4.24). If y < Z, we extend the range of integration in (4.23) to (- oo, oo) (for this term only), which introduces an error << hx log4y-2 x, absorbed by (4.22). We then obtain the integral

{coshO-cos(h+q)0}0-2-2yd0

4H2(y)h-1 J

0

h+ 11)2y+ -h2y+1 1

=4CH2(Y)(

=4Cl2(Y)h2y+O(rlh2y-1)

(2y + 1)n

where

C=(2y+1) Jf 1-Costdt= t2+2y

"cr(1-2y)

2r(l - y)r(1 + Since y < i we have only the case a > 0 to consider. We put q = A.

(log x)-"y/(2 -y) and combine the above with (4.26) to deduce that the first main term (4.23) equals To(y)h2yxlog2y-1x+0(hxlog4y-2x+xlog2y-l-Yx)

(4.27)

where Y = 2a(1 - y)2/(2 - y). We put this together with (4.20) and (4.22) to

3 T and U - average orders

73

obtain, for y < 2, To(y)h2yxlogzy-1 x+O(xlog4y-2+"x

E W(n;h,n)yn(") = n<, x

x+xlog2y-1-rx).

+xlogy-1

(4.28)

Now let y = 2. Since we already have an error term 0(hx) in (4.20), (4.22) an error 0 (h) in the evaluation of the integral in (4.23) would be acceptable:

we cannot quite achieve this when a = 0 but when a > 0 it is easy to do better (which maybe points to a reappraisal of our method in this case). We insert the leading term from (4.24) into the integral in (4.23) to obtain 1 /n

8e + O(h-1n2)

{cos h9 - cos (h +

4H2(2)n- 1

1 /log x

(' 1/1/logqx

=4H2(2)J

de sin(h+2 0.d

+O(h-1q2),

replacing g sin (r1O/2) by qO/2 and estimating the error by an integration by

parts. In the present treatment, we shall not be able to maintain the error term on the right. Put

C1=

lsint-t dt + t2

o

°°sint

1 7 - =1- y

(where y denotes Euler's constant), w = log x/(h + q/2), and substitute (where

0 = t/(h + ?1/2), to obtain

4H2(2)(h+!)(logw+C1

+O(w-2))+O(h-1n2).

(4.29)

/h2.

Recall that h = h1- n or

In either case

loges=(1 -a)log2x+O(h-17+1og2x/logx), whence (4.29) becomes

4H2(2 )h{(1 - 0)log2 x + 1 - y}

+O{r1log2x+h3log-2x+hlog2x/logx}. We have to consider two cases according as a >0 or not. In the first case, there is an error (rllog, x)-1/2 from (4.26), and we choose 11=

log-"/3

x)-2/3.

The first main term (4.23) becomes

2H4(i) a)

hx { (1 - a) loge x + 1- y}

+ 0 (x

log-"/3 x(log2 x)1/3

+x

log3"-2 x)

74

4

Measures of propinquity

(the error term O(hx loge x/log x) being absorbed). Therefore Y W(n; h, rl)2-n(n) =

2H4(f)

hx{(1- x)log2 x + 0(1)}.

(4.30)

7rS(2, 4)

n_< x

In the second case, a = 0, we put ry = 1/loge x. There is an error << x(log3 x)2

from (4.25) and the 0(1) in (4.30) becomes O((log3 x)2). Now we put h = h2 = log' x and recall (4.19): (4.28) and (4.30) yield (4.7) and (4.9) respectively with <. Put h = h1 - n. If y < z, hey = hiy + O(ylhly- 1)

= log2ay x + O(log- r x + (log x)2 ay -11og2 x)

(4.31)

with Y as in (4.27), and (4.28) gives

Y W(n;h1 -11,n)yn(n)=xlog

(2a+2)y-1(To(y)+(log x) K),

ncx

the second error term in (4.31) being absorbed because (2x + 2) y - 2 < 4y - 2 + x. For the same reason, that part of the sum on the left above over the range n < x/log x is negligible, and for x/log x < n ` x we may We obtain (4.9) with 3 from apply (4.19) to deduce (4.7) with (4.30) in a similar fashion. We indicate briefly the changes needed to prove the corresponding results for U(n, x). The error involved in the formula parallel to (4.20) together with the contribution from the second main term is

<< hxlog3y-2x+xlogy-1 x

and comparing this with (4.22) we see that the term on the right is unchanged and is now relatively more serious. Indeed the first main term, parallel to (4.23), is H(y)x

logy- 1 x

2irF(y)c(2,y2)

rlC(1+i8,Y)IZf(e;h,q)de

and we can afford a simpler treatment of the integral on the right.

4.4 The normal orders of log T and log U It may be as well to recall the definition of the normal order of an arithmetical function of Hardy & Ramanujan (1917): `If then g(n) is an arithmetical function of n, and (p (n) an elementary increasing function, and if, for every positive s, we have (1 - e)cp(n) < g(n) < (1 + e)cp(n)

for almost all values of n, we shall say that the normal order of g(n) is tp(n)'. Thus T(n) does not have a normal order (cf. Exercise 42). However it has

4

The normal orders of log T and log U

75

become traditional to say rather loosely that T(n) has normal order (logn)1o92 when we mean r(n) _ (log n)ios 2 +0(1) P.P.,

and we can talk about the `normal order of T (n, a)' in a similar cavalier fashion. The idea is useful, and this is what matters; but we stress from the outset that it is log T (n, a) and log U(n, a) that have normal orders (for suitable values of a). Theorem 44. Let ae[0,1]. The function logT(n,a) has normal order (1 + a) log 2 loge n, more precisely if g(n) -> oo as n -> oo then

logT(n,n a)

_ (1 + (x) log 2 + O

1092

ion) ga n

P.P.

(4.32)

This should be compared with (4.13). Proof. Let mIn and log m < log" n. If 61m, 6'l m, tI n/m then bt, 5't area pair of

divisors counted by T(n, a), and so T(n, a) >, T(m)2T(n/m) >, T(n)T(m) >,

2°°"°.

Let m be the product of all the prime factors p of n such that log p < log" n/21og2 n. Since Q(n) < 21092 n p.p. we have log m < log' n p.p.

and, by Theorem 010, both w(n)1>loge n - fi(n) J1og2 n p.p.,

and ai(m) 1> a loge n - l;(n),/log2 n

p.p.,

from which (4.32), with >,, follows. Now put w = exp log" x and for each n define

n(a) _ fl p p°Iln p-< w

Let d, d' I n, Ilog(d/d') I < log" n, and set S = (n(a), d), b' _ (n(ot), d'), t = d/S,

t' = d'/8'. Then Ilog (t/t') I < Ilog (d/d') I + Ilog (b/b') I


(4.33)

76

Measures of propinquity

4

We consider the sum

'

E T(n/n((x))-1 W (n/n(a); h, 1) n5x

=

J

1(0;h, 1) Y T(n/n(a))-1

i(na)B

2

d9

n5x xlog"-1x.

<<

f If(O;h,1)leXp{1 Y

P-1IT(P,O)12}dO

(4.34)

2w
,J 0

by Theorem O1. We split this integral into four ranges. The first

is

[0,1/log x): its contribution is 1 /Iog x

h exp {2(1- 00092 x} dO << x loge x,

<< x log"-1 x 0

using (4.17). The second range is [log-1 x,log-"x), and we notice that in this range, w < exp (1/0)//< x. We have 2

_ P-1Ii(P,0)I2<21logI-1og2w)+0(1)+2 \\

w
Y

P-1IT(p,O)I2

exp(1/B)
and we apply (3.9) to the sum on the right to obtain altogether log (1/B) + (1- 2a)1og2 x + O(1).

Hence the contribution from the second range is (' log °x

hlog1-2ax <<x(log2x)2.

<< xloga-1x J l /tog x

0

The third range is [log-'x, 1). Since w > exp (1/0) here, (3.9) gives 1

Y p-1IT(p,0)I2 =(1 -a)log2x+O(1)

2 w
and we obtain << x log" -1

I

X. flog °x 0 -11og 1-" x d9 « x loge x.

In the fourth range [1, oo) this B-1 becomes 0-2 giving << x. The sum (4.34) is << X(1092 x)2 and we deduce that W(n/n(a); h, 1)
for all but o(x) integers n < x. Together with (4.33) this implies T (n, a) < 2`(n)+a(n("))(log2 n)3

p.p.

from which (4.32), with <, readily follows. This completes the proof of Theorem 44. Now we consider U(n, L%). We shall prove in this and the next chapter that,

4

The normal orders of log T and log U

77

for 0 5 a <, 1, log U(n, a) has normal order (log 3 -1 + a)log n. Thus U (n, 0) > (log n)'og 3 - 1 -E p.p., in particular for almost all n there exist divisors

d, d' such that d < d' < ed. Apart from the constant, this is Erdos' conjecture referred to in the introduction. Because of this, the p.p. lower bound for U(n, a) belongs in Chapter 5 (cf. Theorem 53), and we confine our attention

to the upper bound here. Then

Theorem 45. Let 0 < a < 1, and B > U(n, a) < (log n)log 3 -1

(4.35)

P.P.

This should be compared with (4.14). Of course when a = 1 a slightly stronger (and sharp) upper bound is available from the Hardy-Ramanujan Theorem: from (4.4) we have 3'(") 5 U(n, 1) < 3a("). The exponent log 3 - 1 + a is suggested by a simple heuristic argument. The numbers log (d/d') where d, d'In, (d, d') =1 are distinct and lie in the interval [ - log n, log n], U (n, a) of them in [ - log" n, log" n]. We might expect the proportion of these numbers in the shorter interval to be about log"- 1 n, that is

U(n,a)_ U(n,1)loga-1 n, which would lead to the correct result. The normal order of log T (n, a) is not (log 4 - 1 + a) loge n (unless

a = 1) - of course in this case the numbers log (d/d') are not distinct; but the difference in the behaviour of T and U lies deeper than this. Write n = PQ where P is the product of all the prime factors < exp (log" n). Then normally T (n, a) behaves like TZ (P)T (Q), that is a typical pair of

divisors counted by T (n, a) will have (more or less!) (d, Q) = (d', Q). If such were true of U(n,a) it would behave like U(P,1), and the normal order of log U(P,1) is easily seen to be a log 3.1092 n. To fly higher than this U(n, a) needs a substantial involvement from the `large' prime factors.

Lemma 45.1.

Let 0, 0, 3
u
`

dJ

v/

Y

Y log2x

<<(log2u)y-1

I

fU\

t

dt t

+ (log 2u)y 2 log-'(2x/v).

This follows from Theorem 04.

Proof of Theorem 45. The Fourier transform method is not applicable here (without serious modification) because p(n, 0) is not positive.

4

78

Measures of propinquity

We put z = exp log' x and define

V1(n)=Y{1:dd'In,dx1"4}. Plainly U(n, a) <, 1 + 2(V1(n) + V2(n)). We begin with an upper bound, valid for y < 1, for S2:= Y V2(n)y'("1<<

Yn(a) X dd,

Y

x x114
n-<x

v-1

log

d
dd'

6min(dz,x/d)

We apply Lemma 45.1 to obtain n(d')

Yd' d< Sm in( dz,x/d)

log

2x 2x v-1

(log d)Y-1(log z)y (d> x1(21z),

«

ily

(4.36)

1

(else).

J

A

When d < xl/2/z, we notice that logy-1(2x/d2z) <
x

<<

1/4

-

Y

12d log T2


C

xlog3y-2+ax.

We put y = 3. If 1(n) -+ co as n -- oc, we deduce that p.p. P.P.

< (log

(4.37)

by the Hardy-Ramanujan theorem (putting 1(n) =1og2 n for example). We introduce the weighted sum V1(n):=Y{w(n,d):dd'In,d
(4.38)

where

w(n d) =

yS2(n,d)-loglog3d

(y < 1).

Let 2(x)- 00, E2 > 0. By Theorem 11 we have sup

(o (n, d) - loge 3d

< 1 + e2

(4.39)

.2(x)
for almost all integers n <, x. Let d comprise the integers n such that (4.39) holds, and in addition S2(n) - cw(n) < E2V(2log2 S2(n, 2(x)) < 21092 b 2 (x). Then card (d n [0, x]) = x + o(x), and if we further suppose that 2 log2 2(x) < V(2log2 x), we shall have, for ned and every d, w(n d) > wo:=

y(1+2E2)J(2log2x'log4x)

whence V', (n) > wo V1(n)

(n < x, n e.4).

(4.40)

The function T(n,0)/z(n)

79

S1: = Y V,(n) < wo 1 Y V 1(n).

(4.41)

5

We consider the sum n<x

n<x

neat

From (4.38) we have

Y

Y V1(n) = Y n<x

Y w(mdd', d)

d<x1/4 d
«

3d)-l09y

yn(d)(log

Y_

d
d<x1/4

yn(d,'d)- -(log dd'

3d)''-1

applying Theorem Of to the sum over m. Since d < x1/4 we may assume d < x/dd'. To bound the sum over d' we consider two cases according as d > z or not. When d > z, we have d' < d2 and n(d) - KI(d', d) < 1. So Lemma 45.1 gives Y

d
n(d',d) ,

Q(d')

y

< y- 1

d

d

d
«y(log 3d)y 1 log z.

Alternatively when d < z we drop the condition d' > d and we have n(d',d)

1- Y

Y d'
d

p
P

i\'

1

HC1--I d
<<(log 3d)y -'log z.

P

Hence n(d)

V'1(n)<< xlogax Y_ n<x

(1og3d)2y-2-1ogy

d<x1/4 3y - 2 - log y

«y x (log x)a+

by partial summation, provided 3y - 2 - logy > 0. We put y = 3: from (4.41) we have Y V1(n)<< w- 1x(logx)log3-1+a n<x

l

neat

and from this and (4.40), V1(n) < (log n)`1'- 1 + a BI/(log2 mlog4 n)

provided B > 30 and E2 = E2(B) is sufficiently small. Together with (4.37), this gives the result stated.

4.5 The function T(n,0)/i(n) This function is important for the study of Erdos' i+-function in the next section. In §4.2 we defined the sequence .'(X) = {n: T (n, 0) > X i(n) }

(4.42)

and showed that X (X) possesses logarithmic density &#(X) equal to its lower asymptotic density.

80

4

Measures of propinquity

For a general integer sequence .4, the upper and lower asymptotic and logarithmic densities satisfy

0
(4.43)

(Halberstam & Roth (1966), Ch. V, Lemma 1). If the asymptotic density exists so therefore does the logarithmic density, and the two densities are equal. The question arises whether d.'(X) exists for every X. We leave this

open; it follows from the next theorem that d4'(X) exists for all but countably many values of X. Theorem 46. For X > 1 we have

d4'(X) << X -'log 2X.

(4.44)

At any continuity point X of &#(X), d.Al(X) exists; that is T(n, 0)/T(n) has the distribution function

F(X) =

(X<1),

0

1 - &&(X + 0) (X >, 1).

Later we shall obtain the lower bound d4(X) >>X - 1 log-1/2 2X (Theorem 47, Cor., (4.61)).

Proof of Theorem 46. We begin with (4.44). We are going to construct a sequence .4 such that, for large x, Y T(n,0)/T(n) < c(s,*4)x,

(4.45)

n<x neat

where c(d) is not too large but nevertheless dd is nearly 1. For then

d.I(X)<X-1c(sa')+ 1-dd.

(4.46)

We refer the reader to Exercise 10. For each x > 0 there exists a K > 0 such that, uniformly for to > 3, the sequence 9 = M(,c, to) of integers n for which sup r,>ro

w(n, t) tog2 t > I + K

(4.47)

satisfies d_j << (log to) - K

We fix x = 3, and write to in the form to = exp (1/00) where 00 is small, and

at our disposal. sad is to be the complement of 9 so that 1- dsad = d «60 .

5

The function T(n,0)/T(n)

81

Now we consider the sum

Y

t(n)-1 W(n;1,1) (W as in (4.18))

n<x ned

11(0; 1,1)I Y r(n)-1IT(n,0)12d0

<< 0

n<x ne.d

T(n) -' IT(n, 0) I2 d0 + x log (2/00).

<< fjOO

(4.48)

/logx n<x fled

Here we have used the trivial bound << x log x for the inner sum in the range 0 < 0 < 1/log x, and Lemma 30.3 with A = 2, y = i for 0 > 00, together with (4.17).

By the definition of sad, we have, from (4.47),

w(n, exp (1/0)) < (1 + K) log (1/0) (0<0 < 00, ned),

and so the integral above does not exceed 500

2(1+K)1og(1/e) E

IJ logx

x logX

T(n)-12-(o(n,exp(1/0))IT(n 0)I2 d0

n<x

500 1/log x

exp

p-1IT(p,0)12 +1 2exp(1/B)
4p<exp(1/0)

p 11T(p,0)12 d0, 0

where it = (1 + K)log 2. The first sum in the exponent is < log (1/0) + 0(1) (estimating crudely), the second is < 1092 x - log (1/0) + 0 (1) by (3.9). So we

obtain eo

<< x

0-µd0<<x

l /log x

because µ < 1. Since T (n, 0) < W (n; l,1) we now have (4.45) with c(.4) << log(2/00) so that (4.46) becomes d.

(X) << X - 1 log(2/00) + 00

and we set 00 = X - 1. This is (4.44). To prove the second part of the theorem, it will be sufficient after (4.43) to establish

dA' (X) < S. t (X) (X e' (& # (X)) ).

(4.49)

We restrict our attention to integers ned, where sl= Z+\ (PJ(K, t0) u .41(l)), M1(l): _ {n: Cl(n) - w(n) > l}. We write f (n) = T (n, 0)/T(n).

82

Measures of propinquity

4

Then

logx Y 1'< Y Elogp+ nx

nx Plln

nx

(iogx_logp plln

f(n)>X

f(n)>X nEd

nE.,l

and the second term on the right is << x. Let rl > 0, z = eto. We split the first

term into three sums S1, S21 S3 in which respectively: p < z; p > z and f (n/p) > X - n; p > z but f (n/p) .c X - p. Plainly Sl

x - log p << x log to. Pszp

y

(4.50)

Next,

I'<

S2 <1 Y log p

Y

z
m<_ x/p

f(m)>X-q ,< x

Y_

Y log p

Y

m6x p-<x/m f(m)>X-17

1 +O(x)<,(&///(X-q)+o(1))xlogx

m5x m

(4.51)

f(m)>X-q

by the Prime Number Theorem and the definition of logarithmic density. Notice that so far we have not used the condition ned. We have

S3= Y_

plln

n_< x

nes?

p>z

ned

f(n)>X f(n/p)SX-q

log p.

E

logp<- Y_

Y_

n_< x

plln

p>z

f(n)-f(n/P)>q

Put n/p = m. Then

T(n,0)=2

Y_

Z

1+

d,d'Im

1,<2T(m,0)+

nlldd'

Iog(d/d')I 5 1

Y,

i(n/SS'),

Sb'In

d,d'In

.1166' 11og0/1) )I 5 1

lIo (d/d' < I

whence .f (n) - .f (m) 5

i(n)-1

Y,

i(n/bb'),

SS'In

P' (5 ')>z Ilog(b/6 )I _< 1

and we denote the function on the right by f (n, z). Evidently the conditions P+ (8S') > z, Ilog (8/S') I < 1 involve min (S, 8') > z/e = to, and so for ne,d and y <, 1 we have f (n, z) < 2` + 1 g (n; to, y) where

g(n;t y):=

Y

2-n(sb')yn(n,b)-(1+K)1og1og36.

(4.52)

bb'In

tp<1Sb'<eb

hence in S3 we have g(n; to, y) > S3

2-1- In and so

<21+lg-1logx

Y g(n;to,y).

(4.53)

n_< x

Put It = - (1 +)c)log Y. We may assume to > e so that 6' < 82 and

Erdos' function T + (n)

6

83

f (8', b) , SZ(8') -1. Hence, by Theorem 01, 9(n; to, y) «y

(y12)`(6'1 E yIcm,b)

(y/2)"(b"(log 3S)µ

Y_

to
n<x

b
Y xS -' (y/2)10) (log 3S)µ+y/2 -1 max

<<

t0
<< x(log

m<x/bb'

{(log3_ 1,

log

3x 32

' ' I

to)µ+2y-2

provided this last exponent is negative. This is the case if Ke(0,1), y = (1 + K)/2: (4.53) yields

S3 << 2'rl-1(logto)-Oxlogx with /3 = Q(1 + K) - (1 + K)log 2 + 1. We put this together with (4.50),(4.5 1),

and let x

oo to obtain

d(.t(X)nd)<S.1t(X-rl)+2'i

1(logto)-fl.

We also have j(-4(K, to) uR1(l)) <<(log

to)-K

+ l-1,

(since the average order of S2(n) - (o(n) is a constant). We let to -+ oo, l -> co, r1-> 0: (4.49) follows.

Erdos' function T+(n)

4.6

For neZ_+ and real u, let E(n,u)= 1 or 0 according as n has, or has not, a divisor dc-(2",2"'1]. We define

T+(n):= >E(n,k) kE7L

= card { k e l: 3d: din, 2k < d 1<

2k + 1 }.

(4.54)

Plainly

n(n)+1,< T+ (n) < min T(n),

[10n] n+1

(4.55)

the sequence n = 2m showing that all three inequalities are best possible. If T + (n) < T(n), then n has divisors d, d' such that d < d' < 2d. A number such as 15 shows that the converse is false. Lemma 47.1. For every n,

T(n)2
(4.56)

84

4

Measures of propinquity

Then

r(n)= yv(n,k)=Ys(n,k)v(n,k), k

k

T+ (n) = y s(n, k) = Y s(n, k)2. k

k

Cauchy's inequality gives

T(n)2
and we have

Yv(n,k)2=YYcard {k:2k
k

5 card {d, d': d, d'In, Ilog d'/dl < log 2} < T(n, 0).

Theorem 47. Let .N'(a):= {n: T+(n) < o r(n)}

Then, for 0 < a < 1, d.iY(a) «a log (2/a)

(4.57)

d.K(a) >> a log-1'2 (2/a).

(4.58)

Proof. We begin with (4.57). Let T (n) < aT(n). By Lemma 47.1, T (n, 0) > a-tr(n), whence .X(a) g J1(1/a) and the result is a corollary of Theorem 46. It remains to prove (4.58). We introduce the supplementary function T * (n) : = max card { k: 3d: d I n, 2k + z \ d < 2k + z + t } 0-
Clearly T+(n) < T* (n), moreover T* satisfies

r*(mn),
(4.59)

which T+ may not: witness m = 19, n = 35. We set

n(w):= HP' (w > 3) p'lln

p6w

where w will depend on a, and we consider the sequence sad of integers n for which w(n(w)) > 21092 w,

n(w) <, w.

(4.60)

We have 1

dam= fl 1-1psw

p

E

a-

a-< w

w(a) 3 21092 w

Put k: = [2 log log w] + 1. By the classical estimate of Sathe and Selberg (see

Erdos' function T + (n)

6

85

Exercise 48) we deduce that

a-'

4,4 >> (log w) WMa)k

>409W'(1092 w + O(1))k/k! >>(log

w)-Q(2)(log2 w)- 112.

Now, by (4.59) and (4.60), for nEd, T*(n)/T(n) < r*(n(w))/T(n(w)) < ([(log w)/(log 2)] + 1)2- 2 1og2 W < 3(log w)1 -log4

We fix w = w(a) so that the right-hand side equals a. Since Q(2) = log 4 - 1 and T+(n)
d.i#(X)>>X-' log-112(2X) (X 3 1).

(4.61)

At one time Erdos was almost certain that r+(n) = o(r(n)) p.p., and thought that his old conjecture could perhaps be proved in this way. But this

was shown to be false by Erdos and Tenenbaum (1981) who obtained a slightly weaker form of (4.57). They suggested that r+(n)/T(n) might have a distribution function, which is continuous and strictly increasing on [0, 1]. We shall establish here the first part of this conjecture. One of the intrinsic difficulties in the study of r+ (n) arises essentially from the special role played by the powers of 2 in the definition. It will be useful to first introduce a modification which avoids this drawback. Put, for 0 < 2 < 1,

T+(n,A)= Y, s(n,k+2) kElL

so that

T+(n)=r+(n,0), T*(n) = sup r+(n,2). 0-<1
The reader may check by means of examples that T + (n, 2) is quite sensitive to changes in A, varying by a factor as much as 2. It is natural to average over 2 and, accordingly, we write +00

1

Tt(n):=

I

T+(n,A)d2= o

s(n,u)du. -ao

For u - 1 < v < u, we have s(n, u) 5 s(n, v) + c(n, v + 1), and this implies that for all n

Zr*(n)5T+(n), T'(n)<,T*(n). This seems hard to improve, even only for large n. However we shall show the following.

86

Measures of propinquity

4

Theorem 48. We have r+(n) - rt(n) - T*(n), p.p.

Thus the distribution problem mentioned above may be tackled by dealing with any of the three functions. Naturally, Tt(n) is the most convenient. Theorem 49. Corollary.

The function rt(n)/r(n) has a distribution function. The above statement also holds for the functions r+ (n)/r(n), and

T * (n)/ v (n)

The proofs of both theorems rely on the following Lemma, established in Erdos-Tenenbaum (1983), pp. 135-7. Lemma 48.1. For each e > 0 there exists a sequence .te(e) with dsd(E) < e,

and such that if nEll+\d(e) then we may write n = ab, where a < P- (b),

r(a) >s-', and b possesses a sequence of at least (1 - e)T(b) divisors b1 < b2 < ... < bS with the property that bi is the only divisor of b in [bi/2a, 2abi] (1 5 i < s). Moreover, the function a(n,E).

_ (a n

(nO.d(e),n = ab)

(ned(E))

satisfies conditions (i) and (iii) of Lemma A2.

This may seem rather technical, but the first part is a standard device worth bearing in mind. Broadly, it states that it is possible to split the prime factors of an integer so that most ratios of consecutive divisors made up of the large primes exceed the product of all the small primes. It is relevant for problems concerning the two orders of the divisors.

Proof of Theorem 48. We show that r+ (n) - rt(n), p.p. An obvious extension of the argument would yield that for almost all n, r+ (n, A) - Tt(n) holds uniformly in ),e [0, 1), whence the required assertion concerning r* (n). In this section only we employ the notation Log v: = (log v)/(log 2). With a(n, e) defined as in Lemma 48.1, we put b(n, E): = n/a(n, e) and let D(n, E)

denote the discrepancy of the numbers Log#, fIb(n,e).

Lemma 48.2. We have

lim d{n:D(n,s)>e}=0. 0+

Proof. Let n > 0 be given. We show that for suitable e(n) > 0 the upper density above is <, n whenever 0 < e < v(rl). Let P4(e, T) comprise the

6

Erdos' function T+(n)

87

integers n such that a(n, e) < T. By the last statement of Lemma 48.1, we have

d(Z+\R(e, T)) < fore < t(q) and T = T (e, n) suitably chosen. Now observe that for any fixed, real 6 36 0 we have by a straightforward application of Theorem 01 and Lemma 30.2

Y IT(b(n,e),O)I/t(b(n,c))s Y E IT(b,O)I/T(b) n5x

a<_T b<x/a P (b)>a

ne..P(e,T)

«E,e x (log x)2/' - 1 = oE,e (x).

In view of the Erdos-Turan inequality (see Kuipers & Niederreiter (1974), Theorem 2.5)

D(n,e)<<-1 M

+

m IT(b(n,e),h/log2)I hT(b(n,e))

h=1

(m%1),

this shows that D(n, e) = o(1) for almost all n in R(e, T). This is all we need. For our next lemma, we introduce some extra notation. We write B, (t): _ {t} -'z the first Bernouilli function. For n > 1, we say that a divisor d of n is isolated if d is the only divisor of n in [d/2, 2d]. When [d/2, d) (resp. (d, 2d] ) contains a divisor of n but (d, 2d] (resp. [d/2, d)) does not, we call d rightisolated (resp. left-isolated). We denote respectively by f (n), R (n) and 2'(n) the sets of isolated, right-isolated and left-isolated divisors of n.

Lemma 48.3. We have for all n T+(n) - T +(n) = Z B1(Log d) - Y B1(Log d). deR(n)

(4.62)

der(v)

Proof. Let 1 = dl
T + (n) = card / (n) + Y (1 + [Log d;,,, ] - [Log dim ] ), 15m5r

Tt(n)=card/(n)+ Y_ (1+Logdd,,-Logdim). 1<m_
This yields the asserted formula. We are now able to complete the proof of Theorem 48. By (4.57), it is sufficient to show that T + (n) - T t (n) = o (T (n) ), p. p.

Let R(n) denote the first sum on the right of (4.62). We set out to prove that

Measures of propinquity

4

88 for arbitrary E, h > 0,

d{n:IR(n)I>Er(n)} Of course we can assume here that E 5 E(Yi). By Lemmas 48.1, 48.2, we may

hence restrict our attention to the case n0d(E), D(n, E) S E. Then, we have

R(n)= E B1(Log d) _ E E B1(Log(afl)) ala

de-4(n)

Sub

afle-4(n)

_

E B1(Log(ab;)) + O(Er(n)) ala 15i5s abieR(n)

where the b, are as in Lemma 48.1. Now for any d = abi, all the possible divisors d' of n in [d/2, 2d] are of the form a'bi with a'I a. Hence abi ePA(n) if, and

only if, aeg(a). It follows that

R(n)= E Y B1(Log(ab;))+O(ET(n)) ala

1-
ae9P(a)

Y EB1(Log(afi))+O(sT(n)). ala

flub

aeq(a)

From Koksma's inequality (see e.g. Kuipers and Niederreiter (1974), Theorem 5.1) the fl-sum above has modulus at most D(n, E)r(b) 5 ET(b), whence R(n) << ET(n). The second sum in (4.62) may be treated similarly. This completes the proof.

Proof of Theorem 49. We first notice that for (m, n) =1 rt(mn) =

f

+00

+00

e(mn, u) du <, - 00

f

E JE(n, u - Log d) du - 00 dIm

r(m)rt(n)

so that rt(mn) r(mn)

: r(n)

((m, n) = 1)

(4.63)

In view of this and Lemmas 48.1 and A2 it will therefore be sufficient to establish that for all n rt(a(n,E))

Tt(n)

r(n)

T(a(n,E))

and we may assume neZ+\d (E), n = ab. With {b(} as in Lemma 48.1, evidently i s

Logabi

rt(ab) >, Y=1

E(ab, u) du Log (bi/a)

Hooley's function A(n)

7

89

(the ranges not overlapping), whence s

Tt(ab)>

Loga

s

i Y-

=1

e(ab,u+Log bi)du > i=1

-Loga

Loga

f -Loga E(a,v)dv

(since we may demand that the divisor of ab should be a multiple of b;). For vo [ - 1, Log a), E(a, v) = 0, and we may assume that Log a > 1. Therefore the integral above equals Tt(a) and we have Tt(ab) > (1 - E)T(b)Tt(a).

The desired inequality follows. The average order of T+(n) presents an open problem. The following is known. Theorem 410. For a suitable constant c, we have x (log x)' - a exp { - c. J (loge x log3 x) } << Y, T+(n) nsx

(x> 16), where 6 =.08607 ... is as in (2.3). We recall the definition of H(x, y, z) from Chapter 2: this is the number of integers n < x having at least one divisor in (y, z]. Evidently x(logx)1-a(log2x)-112

<<

ET+(n)= nsx

w

Y, H(x,2k,2k+1). k=-1

By the symmetry of the divisors of n about n, we see that those k < [(log x)/(log 4)] contribute together at least one half of the initial sum. Appealing then to Theorem 21 (iii), we obtain the asserted upper estimate. For the lower bound, we restrict to the range log x < k < [(log x)/(log 4)] and apply (2.11) with y = 2k, z = 2k +' < V x, uz =1/k. Presumably the upper bound above is nearer the truth; the lower bound derivation is somewhat inefficient. 4.7 Hooley's function A (n)

This is the greatest number of divisors of n contained in any interval of logarithmic length 1, that is A(n) = max card {d: din, z < d < ez}.

(4.64)

Z

This function and its generalization Ar(n) receive extensive attention in Chapter 6 (where Or(n) is defined) and Chapter 7, partially because of the interest arising from the applications to other branches of number theory envisaged by Hooley, and carried through by Hooley (1979) and Vaughan (1986, 1986a) for particular problems. However the applications rather

90

4

Measures of propinquity

focus our attention on the average orders of A(n) and 0,(n), and the normal order of A(n) is also important: it is obviously related to ErdSs' conjecture concerning divisors d < d' < 2d and is tackled in Chapter 5. We restrict ourselves here to partial solutions of two extremal problems:

suppose that we are given the value of T (n, 0) or U(n,O) but no other information about n. What are the best upper bounds for A(n)? It is clear that (4.65)

A(n) < T(n, 0) 112;

moreover this is nearly best possible: let heZ , 11 < pl < p2 < < p2h < (1 + 1/2h)p1 and n=p1p2...P2h For d,d'In, we have Ilog(d/d')I < 1 if and only if co(d) = co(d'), whence

0(n)

2h)2 _ (4h),

C2h)' T(n,0) _ h

i=o

j

2h

and so A(n)2 >> T (n, 0)/ /log T (n, 0). It is an open problem whether or not A(n) = o(,/T(n, 0)) (T (n, 0) -+ oo). In this example we also have

1( 1

U(n, 0) = i C2h II

(4.66) 27 I - ch-1/2.32h, 2j whence A(n)fl >> U(n, 0)/(log U (n, 0))(fl -1)/2 where fi = log 3/log 2. In fact we 1=0

j

can have A(n)1+E> U(n,0). Let n=(p1p2...pk)'. Then U(n,0)<, (2a+ 1)k,

and, by taking the primes close together, we can arrange that A(n) > i(n)/(S2(n) + 1) = (a + 1)k/(ak + 1). However, we do have

A(n) < U(n,0)1/0 for squarefree n.

(4.67)

We need the following general result. Theorem 411. Let n be squarefree, and R, S be (not necessarily disjoint) sets of respectively JRI, ISI divisors of n. Then there are at least (IRI BSI)#12 distinct

ratios of the form r/s, rER, seS. This is best possible: let R = S = {d: dl m} where m is any divisor of n. Then IRI = ISI = 2o(') and there are 30(m) ratios.

Before the proof, we deduce (4.67). Let A(n) = t, and zo < dal) < < d(`) < ezo. Put R = S = {dal), d(2), ... , P) }. By the theorem, there are at least to distinct ratios P°/d'> and we may write O°/d(i) =: S;;/5 in its lowest terms. The pair 5.;, 8;; contributes to U(n,0) and plainly the pairs are distinct. Hence U(n, 0) t' as required. d(2) <

Lemma 411.1 (Woodall (1977)). Let R and S be (not necessarily disjoint) sets of vertices of a k-dimensional hypercube, and M comprise all vectors of the form m = r +s, reR, seS. Then IMO >, (IRIISI)012.

For the proof we refer the reader to Woodall's paper.

7

Hooley's function A(n)

91

Proof of Theorem 411. Let n = PI p2 ... pk and K be the hypercube with vertex set {0,1}k. With each divisor r = p1 p`? ... pkkER we associate the vector r=( 8 1 ,8 2 ,9 0 ' , which is a vertex of K, and with each divisor s = pi' p22 ... pkk c -S we associate the vector s = (1 - 81,1- 82, ... ,1 - 8k)'. By the lemma, there are at least (IRI ISO )fl'2 distinct vectors m = r + s, and

m = (1 +µ1,l +P2,---,' +µk)' where pi = -1, 0 or 1 (15 i ,
92

Notes on Chapter 4 The method of proof used here is not applicable when y >12 . As we remarked, in this case the exponents of log x in Theorem 41 §4.3.

become 4y - 2 + a and 3y - 2 + a (the formula involving U(n, a) is given,

with a sketch proof, in Hall & Tenenbaum (1981)). Now let I(#3) = {9:(logx)-fl i. We have (for h ^ (logx))

E I(Q)

It(n,o)I2yn(n)d9«x(logx)(i+6)(2y-u+"

n_<x

which is negligible, so that the main term comes essentially from the range 101 < 1/log x where the results of Chapter 3 do not apply. §4.5. The idea needed for the proof of (4.45) is due to A. Hildebrand, who

proved that if fi(n)-+oo then

p.p., using essentially

Theorem 11 rather than Exercise 10 to construct a suitable sad with dsy = 1. §4.7. In analogy to the definition of a highly composite number (Ramanujan (1915a)), Erdos & Nicolas (1976) call n A-abundant if A(n) > max {A(m): m < n}. They show that if n is A-abundant then A(n) ^ i(n)/,,/(lognlog2n).

93

Exercises on Chapter 4 40. Prove as simply as possible, using Fourier analysis and results from

Chapter 3, that, for 0 < a < 1, z' < y < 1, T(n,a)yn(n)=x(logx)4''-2+a

n G.x

41. Combine Exercise 40 with Holder's inequality to obtain for p < 2 that Y T(n, 0()'/P«x(logx)4"P- 1 -(1 -a)/P n5x

Show that, if a < 1 and p > po(a), this is false.

42. Deduce from the proposition that r(n) has a normal order that if fi(n) -+ oo then co(n) - w(n - 1) > - fi(n) p.p. Why is this false? [Hint: cf. Kubilius (1964) Chapter V.]

43. Let S c [ 1, x] be a set of integers such that x - BSI << x/(log x)Q(a) (Q (a) = a log a - a + 1), where 0 < a < 1. Prove that Y2w(tl)>>E

x(log

x)alog2-Q(a)-E

neS

44. Combine Exercise 43 with Theorem 47 to prove that Y- i+(n)>>

x(logx)2(./2-l)-E.

n5x

Examine why this result is weaker than Theorem 410.

45. Deduce from (4.65) that

Y n5x

46. Let 0(n;u):=i(n,eu,e4+1). Show that

< T (n, 0).

A (n;

47. Show that, for m, ne7L+, 0(mn) < max Y A(n; u - log d) U

and deduce

(i)

(ii)

L (mn)
dim

(1)

94

Measures of propinquity

4

[Hint: majorize the right-hand side of (1) by a suitable convolution integral. Apply Exercise 46.] 48.

Put F(z) = F(z + 1)-' [p(1 - 1/p)Z(1 + z/(p - 1)) and assume that

Selberg's formula (1954) Y_ zw(°

zF(z)x(logx)Z-

+OB(x(logx)Z-z)

n-<x

holds for x > 2, zeC, IzI < B. Deduce the estimate 1NF Ix

(loge V ' (log2x)logx (k-1)!. k-1

m(n)=k

uniformly for x --> cc, k 5 B loge x.

x

5

Erdos' conjecture 5.1

Introduction and results

Historically, Erdos' conjecture first appeared as an epiphenomenon. In the

thirties, the main interest in this circle of ideas was in the structure of sequences rather than the structure of numbers - and the focus of attention was the concept of a set of multiples. After Chowla, Davenport and Erdos had proved (independently) in 1934 that the abundant(*) numbers have asymptotic density, a deeper understanding of the situation was sought, possibly in the form of a general theorem stating that every set of multiples had a density. However Besicovitch disproved this by an explicit construction (cf. Chapter 2) based on the observation that for fixed, large y it is unlikely that an integer has a divisor in (y, 2y]. Certainly not the least of Erdos' achievements was to have recognized that the occurrence of such questions about divisors in `short' intervals was by no means a matter of chance. The attempt to answer these questions has proved to be exactly the way to improve the model of normal integers as based purely on the double exponential growth of the prime factors and in accordance (as we saw in Chapter 1) with the fact that the expected value for d,(n) is exp(Jtnogz) (1 <J T(n)) Consider the function L(n; y): = card {d: dl n, e' < d < ey+' }.

In the above model, this would just take the values 0 and 1 - and Besicovitch's result also points in this direction. But Erdos conjectured that almost all integers have two divisors d, d' such that

d
speculative questions help to further our knowledge of the structure of integers. In the light of the rest of the theory, this very simple conjecture is (*) An abundant number has a(n) =Y_{d: dIn} > 2n.

96

5

Erdos' conjecture

revealed as both deep and delicate, reflecting the crudity of the available model. The conjecture can be put in a probabilistic framework where it raises the fundamental problem of the estimation of the concentration of a sum of random variables - see the Notes. The sequence of those n with Erdos' required property is easily seen to be a set of multiples. In 1948 Erdos gave a criterion for such a sequence to have

asymptotic density which applied, positively, in the present case. The question as to whether or not this density equals 1 was to remain open for another 35 years! The heuristic argument which let Erdos to formulate his conjecture was based on the assumption that the numbers {log (d/d' ): d, d' I n, (d, d') = 11 are

evenly distributed in [ - log n, log n]. As we saw in §4.3 this suggests that

U(n,0):=card {d, d':dd'In,(d,d')=1,Ilog(d/d')I < 1} = (log n)1og3-

1 +o(1)

P.P.,

and we proved in Theorem 45 that the upper bound implied by this formula

valid. We need the corresponding lower bound. Having various applications in mind, and to avoid repetition of a similar underlying is

argument in different contexts, we make a generalization in two directions. First, we introduce the distribution function V (n, t): = card {d, d' I n: (d, d') = 1, Ilog (d/d') I < t}

and second, we consider for each n the partial product

fl pv

n(u,v):=

p'iln u
where u and v are free parameters. The usual order of either w(n(u, v)) or S2(n(u, v)) is

log v

w: = log (logu)

(u

< v),

(5.1)

whence the number of pairs d, d' In (u, v), (d, d') = 1, is as expected, 3'". Moreover by Theorem 07 we may also expect log n(u, v) to be not much larger than log v. This suggests that the average distance between numbers of the form log (d/d'), with d, d'In(u, v) should have order of magnitude about

h:=3-Wlogv,

(5.2)

and further, assuming reasonably even distribution in [ - log v, log v], we are led to expect that

V(n(u,v),t)=h-1t (0,
Introduction and results

1

97

Theorem 50. Let u, v, x be such that

2< u3
(5.3)

and w and h be as in (5.1) and (5.2). Then, for all t > 0 and e(0, ,Iw], we have V (n (u, v), t) < 1 + h -1 t exp ( Jw)

(5.4)

for all except << xwexp(- 2/11) of the integers n < x. Theorem 51. Let u, v, x, w, h and

be as above, and

l:=1-(1+1og23)/log3=0.00415....

(5.5)

Then for all to [0, log v] we have

V(n(u,v),t)>h-'texp(-l;Jw) for all except

(5.6)

<< x {exp (- X2/50) + -1w-1/2 (log w)41}

of the integers n < x.

We now derive, by various specializations of the parameters, the following consequences. First things first: we have the following. Theorem 52. Almost all integers have two divisors d, d' such that d < d',< 2d; moreover the number of integers n < x without such divisors is << x(log2 x)

(1og3 x)41.

_ 51 with u = 2, v = x, t = log 2, (log 3 - O V1092 X. We obtain 0(n, log 2) >, 3 with no more exceptions than given above; and this is sufficient. Proof. We apply Theorem

Next, we determine to within a factor (log n)0) the p.p. order of magnitude of the function U (n, a) defined in §4.2. It will be convenient to put Z2/11),

Ri (x, 0: =1og2

(5.7)

(log3x)41

(5.8)

Theorem 53. Let - oo < a 5 1. Then

U(n, a) -1 + (log

n)'°g3- 1 +«exp {O(J(log2

n))}

p.p.

(5.9)

More precisely, if = fi(x)--+ cc, l; 1< JIog2 x, then we have

logU(za) o g2

+

,< log3-1+a+

lox)x g2

\\\

(5.10)

for all except << xR, (x, l;) of the integers n < x and log U (n, a)

to g2 x

log 3 - 1+ aC

l; (x)

V1092 x

for all except << xR2(x, ) of the integers n < x.

(5.11)

98

5

Erdos' conjecture

When a < 1 - log 3, the conclusion is that U(n, a) = 1 p.p., that is the only pair of divisors counted is d = d' = 1. Since U(n, a) is an increasing function of a we may assume in the proof that a > - 1(say). We put u = 2, v = x, and

notice that, for - 1 < a < 1,,/x < n < x, 0(n, R log x)") <, U(n, a) < 0(n, 2(log x)").

The result follows from Theorems 50 and 51. Remark. R1(x, ) , ,/(111og3 x), so that the upper bound (5.10) is useless unless the last term on the right is >> V(log3 x/log2 x). When

0 < a < 1 this is a weaker result than Theorem 45 where this term could be

taken to be c ,/ (1og4 x/log2 x). This is because the law of the iterated logarithm (Theorem 11) utilized in the proof of Theorem 45 is not available in the more general context of Theorem 50.

We now turn our attention to the function E(n): = min {log (d'/d): d, d' In, d < d').

Theorem 54. We have E(n) = (log

n)1-1og3

exp {O(,/(l092

n))}

p.p.;

(5.12)

more precisely, if 0 (x)-> 001 0 (x) s,/log2 x, then E(n) < (log x)1-1og3 exp {1/i(x),1log2x}

(5.13)

for all except << xR2(x,>y(x)) of the integers n<x and E (n) > (log x)1 -log 3 exp { - >/i (x),Jlog2 x}

(5.14)

for all except << xR i (x,1/i(x)) of the integers n <, x.

Proof. We use the fact that E(n) > t if and only if V (n, t) = 1. We apply Theorems 50, 51 with u = 2, v = x and to check that the h in (5.2) satisfies (logx)1-log3 `h

=1/i (x) + 2/,/loge x. It is then easy

<

2(logx)1-log3

The conclusion follows on setting t = to = Zh exp(- ,/w) in Theorem 50, and t = t 1 = h exp in Theorem 51. Indeed we obtain (in each case with the relevant number of exceptions) V(n, to) <2 (whence = 1), 0(n, t1) > 1. In view of Theorems 53 and 54 it is tempting to conjecture that, if we define the functions u(n, a), e(n) implicitly by the relations U (n, a) _ : (log n)1og 3 -1 +"exp {u(n, a),/log2 n},

E(n) =:(log n)1 -log3 exp {e(n),/log2 n},

then u(n, a) and e(n) both have distribution functions, but the present techniques to not seem delicate enough to decide this.

2 Proof of Theorem 50

99

We close this section with a p.p. lower bound for the A-function. An upper bound follows in §5.4.

Theorem 55. Let y < log 2/log {log 3/(log 3 - l) J = 0.287 54 .... Then we have A(n) > (log2 n)7

p.p.

Proof. Fix p > log 3/(log 3 - 1) so that pY < 2. Set J1: = I V1093 x],

J2 = [log3 x/log p], and for each je(J1i J2] put u:= exp exp pj and nj = n(uj, uj+1). Theorem 51, with u = uj, v = uj+, t = 1 and _ (log 3 - p/(p - 1))../(pj(p - 1)) yields V(nj,1)> 1

(5.15)

for all except << xp-'flj4fl of the integers n <,x. Hence (5.15) holds simultaneously for all je(J1i J2] and all but o(x) integers n < x. In this circumstance, for every j there exist divisors djo, dj1 of nj such that 0 < log (d1/d0) < 1, and all the products

f djEu,

(E(j) = 0 or 1)

J1
are divisors of n and fall in an interval of logarithmic length J2 - J 1. Clearly this implies that A(n) > 2(J2-Ji)/(J2 - J1)

and the result follows. 5.2 Proof of Theorem 50 Lemma 50.1. Let ? max

u < x, A >, 1, se(0, 2). Then

{f1(n;u,z)-(1+E)log(jogz

u-
g

<EA )

for all except << xE-2(1 +e)-Ez of the integers n<x. Proof. This is an exercise on the parametric method of §0.5 and we just

sketch the argument. Put K =I+ [log (log x/log u)] and introduce the check-points zk =exp (ek log u) (0 ,
The number of integers n 5 x such that

max {c2(n;u,zk)-(1+E)(k-1)}>e). 0
(5.16)

100

Erdos' conjecture

5

does not exceed (for arbitrary ye[l,2]), y4(n;u,zk)-Q+e)(k-1)-ei. O-
<<x Y exp{k(y- 1 -(l +e)logy)-e2logy} 0-
and we put y= I +e. The k-sum is «e-2(1 +e) `2. Now let ze[u,x]. There exists a k < K such that Zk < z 1< zk+ 1. If n does not satisfy (5.16) then

92(n;u,z)<, S2(n;u,zk+1)<(I +e)k+el

(1 +e)log

log Cl log uJJ u)

as required. In the remainder of the chapter we use the notation u,v

(5.17)

Yn

to mean that the sum is restricted to integers n for which u < P-(n) and P+(n) < v. Note that n = 1 always satisfies these conditions if i < u < v. Lemma 50.2. Let 0 < yo < 2. Then there exists a constant co = co(yo) > 0 such that, uniformly for 0 < y < yo, 2 < u 5 min (v, x), u,v

E yn("'<<

x(logx)y-1(logu)-Yexp

n5x

-co

log x to g v)

Proof. We may assume co < io so that the sum over n Vx may be easily n < x we use Rankin's seen to be negligible. In the remaining range method, in the form y0(n) < x-a/2fa(n) (a > 0)

where fa is the multiplicative function such that ,,(p") = (pay)". We put a = 2c1/log v where cl = cl (yo) is such that yoe2" = I + iyo < 2. Hence Theorem 01 applies to fa and we get u,v

/

x-a/2

fa(n)

yU(")

,/n
n<- x

<
x)-lexp{

ypa-11

lu
which is within the asserted order of magnitude. We may now embark on the proof of Theorem 50 which is similar to that of Theorem 45 except that the details are more cumbersome owing to the presence of the various parameters. co where o is any First, we note that we may suppose henceforth that absolute constant, because the result is trivial otherwise. We may also

2 Proof of Theorem 50

101

without loss of generality restrict the parameter t to the range (5.18)

For, if t is the lower limit here, (5.4) already implies V(n(u, v), t) = 1, and for smaller t we use the fact that V decreases with t. If t > 10-1 log v, we apply

Lemma 50.1 with e = /3 Vw(<

3)

and A= w, and we have

V(n(u, v), t) < 3f(n;u,v) <

xwexp(- 2/11) integers n < x. This

for all except << xe-2(1 is sufficient because v


log

if o, and so , is large enough. Now we assume that (5.18) is realized and define u,v

V1(n):= Y {1:d1n,1
V2(n):= Y {1:dd'In, l
Plainly, for all n, we have (5.19)

V (n(u, v), t) < 1 + 2 (V 1(n) + V2 (n))

and we begin by establishing an upper bound for V 1(n). We may suppose e'> u, else V1 (n) = 0. By Lemma 50.1 with e = /3 vw, A = w, we have in this circumstance t

fl(n;u,e)<(1+s)log (

t

)+8w
l2

logg U

3v/w

g

for all except wxexp(- Y2/11) of the integers n <x. Provided o is large enough, we then have V1 (n)<20)n;ue') <4h-1t

(5.20)

We turn our attention to V2(n). If the pair d, d' is to be counted, we must have

t > log (d'ld) > log (d'l(d' -1)) > 1/d' > ed 1, moreover d > 1, P- (d) > u. Hence

d > max (u, e-`t(5.21)

Define 11: = (u, max (u, t - 2) ], 12: = (max (u, t-2), X1/4 ] and 13: = (x 1/4, x 1/2 ]

and for j = 1, 2,3 let V2,;(n) denote the contribution to V2(n) from pairs {d,d'} such that dn1j. I1 is empty unless u < t-2. In this case, u,v

V21 (n) < n<x

u,v

yY

dell d
x dd'

102

Erdos' conjecture

5

and the sum over d' is < d -1(d(e' - 1) + 1)<< t + d-1 <
1

t-1 « w 1--PI)-,< loglogu logu

fl

<

.
u
(by (5.18)), and so Y- V21 (n) << xtw (log u)-' = xh -

1 tw

(3/e) -'.

n<x

This implies that (5.22)

V21(n)
xw(3/e)-w<< xexp(- g2/11) of the integers n <x. for all but << The quantities V22(n) and V23(n) will be dealt with by the parametric method of §0.5; we begin by applying Lemma 50.1 with e = /3 Jw, A = w, to obtain, with << xwexp(- X2/11) exceptional n <x,

S2(n;u,d')<(1+e)log(log

g u

+Ew

(5.23)

simultaneously for all d', d' In(u, v). For the integers n for which (5.23) holds, we have y-E vV ,,(n)

with

(j=2,3)

(5.24)

E y(5.25)

V 2,;(n) < u,v

w"

din

d'in/d

i,i(n): =

d,)(logd')-(1+e)logy log u

delj d
where ye(0,1] is a free parameter to be chosen later. We are going to show that, for suitable y, o2 ;(n) is small on average. We begin with j = 2. We have S22: _

u,v

u,v

022(n) < Y-

Y-

n<x

yt2(dd')

deI2 d
x (log dr -(1+e)logy E y(l(m,u,d ),

logu

m<x/dd'

Now dd' < d2e' < x112v1/1° < x315 by (5.18), whence the innermost sum may

be estimated by Theorem 01 and we obtain S22<< X u"' &I,

yn(d)

u,v

d

d
yu(d) ulogd'A d logu

where A = y - 1 - (1 + s)log y. When t > 1 the inner sum may be majorized by partial summation, using the estimate u,v

yn(d')<u) d'
2 Proof of Theorem 50

103

which follows from Theorem 01 (dropping the condition involving v). We obtain that the sum over d' above is a+6

«

zB dz a

with a = log d/log u, b = t/log u, B = 2y - 2 - (1 + s) log y. If we assume, as will be the case, that B < 0, this is

(logd). B

<< baB = lot

(5.26)

g u log u

From Theorem 03 (Shiu), this bound is equally valid when t < 1 provided

d > t-2. Hence the d'-sum is majorized by (5.26) for all dC12 and we infer that

xt 22 << S22

a'° yn(d)

log u d

logd B<< xt exp{(B+y)w}

d

log u

log a

(B + y)

by partial summation, appealing to Lemma 50.2. We select y = (1 + E)/3,

so that B,3log2- 9 <0 and B+y=log3-1+Elog3-Q(1+E)>, log 3 - 1. Hence S22 << xh-'t exp (log g 3 "/w)

and by (5.24) we obtain that

Jw)

V22 (n) < ii h - l t exp

(5.27)

for all but << x exp (1 - S log 3) Vw} << xw exp (- 2 /11) of the integers n < x satisfying (5.23).

The case of o23(n) is very similar and we only give the main steps. By Theorem 01, S23

l og u

n<x

yn(d)

UIV

x

Y-

deli

U'V

Yd
d

(1+E)Ioey

logx

:= 7 Q 23 (n)<<x

yrna) /log(2x/dd')lY d'

I\

logo

i

J

< min(de`,x/d)

We drop the condition P+ (d') 5 v in the inner sum and, if t , 2, we estimate by Theorem 01 again, and partial integration. We obtain

/

(log d)y 1 I log

2e

Y-1

7

-1(log d)y- l l log d2

t(log u)1 - 2y (de`

\/x),

y

(log u)1

2y

(de` > ,,/x).

104

5

Erdos' conjecture

Now, when de, < ,Jx, we have every d the d'-sum is

(log(2x/d2e`))y- 1 <<(log 2x/d2y'-1 and so for

))y-It (log u)1- 2y.

<
(5.28)

If t < Z, we apply Theorem 03 (Shiu) which is applicable because d > t-2 We find that the upper bound (5.28) is still valid. Whence Q(d)

S23<<

2xly-1

( log d2 )

xy-1t(logx)°(logU)-y-ndK

where D: = y - 1 - (1 + e) log y. By Lemma 50.2, and partial summation, the sum over d is c0(1)logx y-1(logx)2y-1(logu)-y expF <<

4

and so S23 «xy

log u)

t ( exp log u jl

log v}

c0(1)logxl 4

log v jj'

with E = 3y - 2 - (1 + a) logy. We select y = (1 + s)/3 as before and obtain S23 << xh-1texp

(log 3

Vw/

Thus, the upper bound (5.27) is equally valid for V23(n), with the same estimate for the number of exceptional integers n < x. Together with (5.22) and (5.19), this completes the proof of Theorem 50. 5.3 Proof of Theorem 51 Our method is based on an induction process. The basic idea is to consider the product of the first k prime factors of n and try to keep as close control as possible over what happens when we multiply by the (k + 1)st prime factor. However the function n - F I {p;(n): j <, k} has the drawback of not being multiplicative, and we introduce the slightly different function nk (which also takes account of u) to ease the technical difficulties.

The parameters u, v, w, h, , x being fixed as in the statement of the theorem, we put L = [w - s /w], M: = and define uk: = exp (ek log u) (k = 0, 1, 2.... )

so that U <- uk 1< V for all k < M; moreover

exp (- 5 Jw -1) < log uk/log v <, exp (- s Jw) for L < k < M. Now we define, for every n, nk: =

fl p. Pin

U
(5.29)

Proof of Theorem 51

3

105

This is a multiplicative function of n and when k z M it is a squarefree divisor of n(u, v). The normal order of co(nk) is k (if k -+ oo) and so nk mimics

the product of the first k prime factors of n(u, v). Lemma 51.1. For each fixed k, L <, k < M, we have

k-

co(nk) < 2k

(5.30)

for all but << x exp (- X2 /50) of the integers n < x. This is a straightforward application of the parametric method of §0.5 and we omit the proof. Lemma 51.2. Let 1 < T < w, 0 < a < 1. Then we have

min m-1(co(nk)-w(nk_m))>a

(5.31)

T<m
for all except <<xQ (a) -1 exp(- TQ (a)) of the integers n,<x (with Q(a)=alog a-a+l as in (0.22)). Proof. The number of exceptional n does not exceed aw(nk)-w(nk-m)-ma

Y Y_

T<m
<< Y xe-mQ(')<<xQ(a)-'exp(-TQ(a)) T<m5k

using Theorem 01. Our next lemma concerns the function p(n,0) defined in (3.17). Recall that, for squarefree n,

p(n,0)= fl(1 + 2 cos (0 log p)). pin

We also use the notation coo(n): = co(n, exp (1/0))

(0>0).

Lemma 51.3. Let 0 > 0, L <, k < M. Then we have Y 3 - w(nk) - wo(nk) p (rik, 0)2 << x (log (3 + 0))'.

(5.32)

n<x

Proof. We distinguish several cases, according to the value of 0. When 0 < (log uk)- 1, we have wo(nk) = co(nk) for all n and the summand in (5.32) is

1. The conclusion is trivial. When (log uk) -1 < 0 < (log u) -1, we apply Theorem 01 to the left-hand side of (5.32) which yields the bound << xexp{

1(-l+p(P,0)2/9)+

Y_ u

E

1(-l+p(p,0)2/3)

exp(1/0)

)))

106

Erdos' conjecture

5

The first of the p-sums is < 0. The second falls within the range of applicability of Lemma 30.1 with f (v) = - I + (1 + 2 cos v)2/3. Since f has mean value zero over [0, 2n) we find that the sum is O(1). This implies the asserted result. When 0 > (log u)-' we have co9(nk) - 0 and Theorem 01 provides the bound << xexp{

Y_

u
1(-l+p(p,6)2/3) Uk t'

If 0 < exp /log u, we see again that the sum over p is O(1) by Lemma 30.1. If

0 > exp /log u, we apply the lemma to the sub-sum corresponding to the range exp {(log(3 + 0))2} < p < uk - this is O(1) - and the complementary sub-sum is majorized trivially, just writing p(p, 0)2 < 9. It does not exceed 41og2(3 + 0) + O(1), which gives the result stated. Our next lemma is the key to the proof. Here /3 is the small positive number defined by (5.5). Furthermore, we set H: = h exp(2 /w).

(5.33)

Lemma 51.4 (Fundamental Lemma). Let L < k < M, 0 <.s < 1/100. Then we have 1/H

p(nk, 6)2 dO < 32w("k)(c log uk)-'

(5.34)

J - 1/H for all except << x(Es + exp(- i 2/50)) of the integers n < x. Proof. Set 21: _ [0, (6E log uk)-'], -92:= ((6E log uk)-', (1og 0-11 -93: _

((log u)-', H-'], and define AJ(nk):= J

3-20c"k)p(nk,6)2d0 (1<j<3).

(5.35)

Our conclusion will follow if we can show that A;(nk) < (6e log uk)-'

(1 <j < 3)

(5.36)

for non-exceptional integers; and since the integrand in (5.35) is < 1, this is certainly true for j = 1. Let 6 = S (e), 1 < 6 < log 3, be a parameter to be chosen later. We apply Lemma 51.2 with T = [log (1/6E)] and a = S/log 3. Since m:= [log(Bloguk)] >, T for 0E-92, we obtain that w(nk) - ce(nk) i cw(nk) - ww(nk-m) > a[log(0log uk)]

holds simultaneously for all 0e22 and all n < x except those which belong to a fixed set (independent of 0) of cardinality <<xQ (a) -' EQ(").

(5.37)

Proof of Theorem 51

3

107

For the remaining integers, we have 3 - w(nk) < 31- we(nk) (0 log uk) - a

whence A2(nk) < 3A2 (nk) where 14

(0 log

2

ub.

Now Lemma 51.3 implies (because 0 = 0(1)),

(0loguk)d0«x(S-1)-'sa-1(1oguk)

Y AZ(nk)<<x I J -92

n<x

whence AZ (nk) 5 (1861og uk) 1 for all except << x(8 - 1) Y of the integers

n < x, and we deduce that (5.36) holds for j = 2 and all but <<x{(5- 1) -'S'+ Q (a) -' 6Q(") }

(5.38)

integers n < x.

Next we consider A3(nk). From Lemma 51.1 we have *(nk)

A3(nk) <

with

A*(nk):=

f

(5.39)

3-w(nk)p(nk, 0)2 dO

f3

for all except <<x exp(- X2/50) of the integers n < x. Noticing that coe(nk) - 0 for Oe-93, we may infer from Lemma 51.3 that Y A3(nk)<<x I n4X

(log(3+0))4d0<<xH-1w4.

(5.40)

,J-93

It may be checked that, for L < k <, M, we have

H- 1W4 3-

3wa(loguk )

exp

{-C7-6log3) 10

}

1, we may deduce from (5.39) and so that, assuming as we may that (5.40) that (5.36) holds for j = 3 with << x(s + exp(- X2/50)) exceptions among the integers n < x. We put 6 = 1 + 2 V6 (< log 3) and we see that (5.38) is within the order of magnitude asserted. Collecting the various estimates together we obtain the result stated. We are now in a position to embark on the proof of the second main theorem.

Proof of Theorem 51. We assume that > o where o is a sufficiently large absolute constant. We shall establish that the slightly better bound V(n(u, v), t) > H-'t

(5.41)

(where H is as in (5.33)) holds with the number of exceptions claimed, in the

narrower range

H 5 t < log v exp(-'-2 Vw).

(5.42)

108

5

Erdos' conjecture

This is sufficient to imply (5.6) for 0 < t < log v. For t < H, (5.6) is weaker than the trivial lower bound V >- 1. If t1 denotes the upper limit in (5.42) then, for t1 < t ,,V (n(u, v), t 1) >

H-'t1 > h-1t exp(- .,/w) as required. It remains to obtain (5.41). With the notation (5.17) as before we introduce the function u,v

V(n,z):= Y { 1: d, d'In, (d, d') = 1,Ilog(d'/d)-zI s t} d,d'

so that V (n (u, v), t) = V (n, 0). For Jzi > t + log n, evidently V (n, z) = 0. The idea is as follows: suppose we know that, for some particular zo, V (n, zo) is large. Then, if p%n, log p ;:z zo, V(pn, 0) should be large. With this in mind we

aim to show that, for any k, L < k < M, V(nk, z) is so often large that, for small r, V(nk+r,0) cannot be small too frequently. The argument can be viewed in terms of conditional probabilities, and concludes with an iterative procedure. Thus we introduce the set of points 2'(n): = {z e tJ: V (n, z) > H-1 t}

where V(n,z) is large. The Lebesgue measure of It(n) is denoted by 2(n). Plainly 2(nk) < 2(t + log nk) and we begin by showing that this easy upper bound, if it be multiplied by s, persists as a lower bound valid for most of the integers n < x. Let m be squarefree, u < P - (m) < P + (m) < v. Then

0)2it2(m)t2 f-1 r1/t

H

1/2

p(m, 0)2 d6)

.

(5.43)

1/

To see this, observe that V(m,z)dz

2.3w(m)t=

J

and majorize the integrand by H-1t for z0Y(m). This yields

2.3w(m)t<2H-1t(t+log m)+ J

V(m,z)dz.

(5.44)

f"(m)

Now sin((log (d'/d) - z)/2t) 2 (log (d'/d) - z)/2t )

V (m, z) S 2 Y dd'Im (d,d') =1

1/t

=2t

f

e`az(1-I0tl)p(m,0)dO

and Parseval's formula yields 1 /t

V (M' z)2 dz < 8irt2 f 00 00

(1 - J0t1)2 p(m, 0)2 d0. -11t

(5.45)

Proof of Theorem 51

3

109

We apply Cauchy's inequality to the integral in (5.44) and obtain (5.43). w) > w-1 be a small positive number to be chosen later and Let e = put 11= e0 + exp(- X2/50) with /1 as in (5.5). For any kE[L, M] we have by Lemma 51.4 1/H

P(nk, 0)2 d9 5 32W(nk)(a log

uk)- 1

(5.46)

J -1/H for all except << x of the integers n 5 x. Let us prove that for t satisfying (5.42) we have, also with << Ix exceptions H-1t(t + log nk) < 16.30("k)t.

(5.47)

To see this, first note that by Theorem 07 there exists an absolute constant co such that (5.48)

log nk <1 co log w log uk

for all but << qx of the integers n < x. Next, observe that, for k >, L w - 5 c Jw - 1, Lemma 51.1 implies for (1 + O(q))x integers n < x. When this inequality and (5.48) hold, we have H-1lognk=3w(logv)-l

o

g

p{

l

(10

7

/w

3

4.3w("k)

provided o, and hence , is sufficiently large: we have used the inequality immediately following (5.40). Moreover, by (5.42) and the definition of H, (

H-1t<

3 log 31

l

g 4.3(O("k)

and (5.47) follows. Substituting m = nk in (5.43) and taking (5.46) and (5.47) into account, we finally obtain the desired lower bound for A(nk). For t as in

(5.42) and ke[L, M], we have A(nk)1> 8n 109 Uk

(5.49)

for all except «rlx of the integers n S x. We may now take up the final part of the proof. We proceed by induction

on k, our aim being to establish a non-trivial upper bound for Nk: = card {n: n 5 x, V (nk, t) < H - 1 t}.

It will be useful to bear in mind that this is a decreasing function of k. We

110

5

Erdos' conjecture

introduce the number of those n counted by Nk which satisfy, in addition, the three conditions (a) (b)

log nk < R log uk,

(c)

2(nk) >, Clog Uk,

where we have set R:= co log w. From (5.48), Lemma 51.1, and (5.49) we deduce that (5.50)

Nk < Ni* + c,71x

where c, is absolute. Let D. denote the number of those n counted by N,* which have two prime factors p, q such that (d)

2R log uk < log p ,<3R log uk,

(e)

logp
(f)

Condition (f) implies V (nk, log q - log p) > H- 1t so that the inequality Ilog (pd'/qd) I ,
(5.51)

Denote generically by m* an integer equal to nk for some n counted by N* and by b an integer for which P - (b) > exp (4R log uk). Then Dk counts at least all the integers of the form n = am*dpqb, with a <, u, dim*, p, q as in

(d)-(f) (with .(m*) in (f)). Hence Y

Dk%Y_ Y_ Y_ Y_

1.

a_< u m* dlm* P,9 b<x/am*dpq

The innermost sum may be estimated by Theorem 06, on noticing that adm*pq 5 u(m*)2pq < exp(1OR log uk) (by (a), (d), (e) above), whence, provided o is sufficiently large, exp(4R log Uk) < 2x/am*dpq. We obtain Dk>> xe-kR-1

1 ZM

*

1

.

(5.52)

When m* and p are fixed, q covers a union of at most 3u'(m*) < 9k intervals

with total logarithmic length at least equal to the Lebesgue measure of 22(m*) n [0, oo) = .1(m*)/2 and with end-points having logarithms R log Uk. By (c) above, and the Prime Number Theorem, we have

Yq»(Rloguk)-1y >> 2(m*)(R log

logq uk)-1

+ 0(9k exp(- .,/(R log uk))).

We shall choose E > w- 1 > (2k)-1, and the error term above is therefore

4 A p.p. upper bound for the A-function

111

negligible - the q-sum is >> eR - 1. The p-sum is then >> 1 and (5.53)

Dk >> xe -k eR -2 Z 1P (m*) - 1. M

Now we also have Nk

\

1

d5 m*

where the dash denotes that summation is restricted to those d for which pjd implies either plm* or uk] - writing the integers n counted by Nk in the form n = m*d, where m* = nk. Since log m* < R log uk this inner sum can be estimated by Theorem 01 and we obtain

xe-k (P(m*)-1 m

which, compared with (5.53), yields Dk 1> c2eR-2N*.

(5.54)

Suppose now that NM > 2clrlx where c1 is the constant appearing in (5.50). Then we have, for all ke [L, M],

N*>Nk-c111x>Nk-2NMiNk, whence Dk > - 2c2eR -2 Nk by (5.54) and Nk+r < Nk(1 - 2

c2sR-2 ) by (5.51).

By iteration, 2)[(M -L)/r] NM < NL(1 - Zc2eR-xexp - C3 R2log R 1

,

and so, in any event,

NM<x{2clrl+exp\-c3R2 ll

We select e =

log R

1 w -112 (log w)4 > w - 1 which yields NM << x (el + exp (- X 2/50) )

and achieves the conclusion of Theorem 51.

5.4 A p.p. upper bound for the A-function We have seen that the A-function plays a central role in the theory of divisors and the question of its `normal order' is naturally of interest. As a complement to Theorem 55 we prove the following result. Theorem 56. Let di(n) -* oo as n -+ co. Then A(n) < t/i (n)1og2 n p.p.

(5.55)

In the next chapter (Theorem 60) we prove that the average order of A(n)

112

5

Erdos' conjecture

is at least c loge n. We believe that this mean is dominated by those integers n such that co(n) - loge n and make the following Conjecture.

0(n)/log2 n has a continuous distribution function.

Notice that, if this were true, Theorem 56 would be optimal and Theorem 55 could be sharpened to 0(n) > 0 (n)-11og2 n p.p. The proof of Theorem 56 is based on a study of the high moments of the function

A(n;u)=card {d:dln,e"
Mq(n):=

JA(n;udu (n,geZ ).

It is plain that, for fixed n and q -* oo, Mq(n)11q-->e(n). Moreover we have (Theorem 72) that A(n) < 2Mq(n)1lq.

(5.56)

We use an induction analogous to that involved in the proof of Theorem 51 but we must now consider the occurrence of the prime factors one at a time, separately. For technical reasons we rule out the very small, and very large, prime factors from this process. Thus we fix a function L = L(x) such that L(x) -+ oo, L(x) < Jlog2 x, and define, for n < x,

K=K(n):=max{k:1
nk. -

L1k p;(n) (L
(k > K(n)).

We may assume that L is integer valued, so that, for each n, w(nk) = min (k, K) - L (k, K > L). From Theorem 10 we also have L < K(n) < M:= [21og2 x] p.p.x.

(5.57)

We shall need an improvement, p.p.x, on the factor 2 on the right of (5.56)

when n = nk. This is provided by the following result which is an easy application of Theorem 50. Lemma 56.1. Let ee(0,1). Then we have max {A(nk) - (3/e)"1+&)klgMq(nk)11q} 5 1

p.p.x.

Ll

Proof. Let k, q be fixed, and uo chosen so that A(nk; uo) = A(nk). Let d be the smallest divisor of nk in (e"O, a"O+ 1 ] We may assume d nk, for we should

then have 0(nk) = 1 and could set uo = - 1, d = 1. Let d' be the smallest

4 A p.p. upper bound for the A-function

113

divisor of nk greater than d. By definition of the function E (see §5.1) we have

log d' - log d and, since A(nk; U) > A(nk) - 1 for log d

E(nk)

u < log d',

log d'

Mq(nk) i

(A(nk) - 1)' du i (A(nk) - 1)'E(nk) logd

Therefore the desired result will follow from min (3/e)"1+e)kE(nk) 1> 1

p.p.x.

(5.58)

L
To establish this, observe that, by the corollary to Theorem 10, there exists a subset S of the integers n <, x, with cardinality (1 + o(1))x, on which

max {loge P+(nk) - (1 + e/2)k} z 0. L
For neS, we have, in the notation of §5.1, that nkln(u, v) ( u =3 v = min(x,expexp((1 +e/2)k))) for every ke(L,M). We apply Theorem 50 with this u and v, and = ZSe Vk. We obtain 2,

D(nk, (3/e)-(1 +,)k) = 1

(L< k < M)

(5.59)

for all but <<x exp (- elk/7000) members of S: that is, (5.59) holds, simultaneously for all ke(L, M], p.p.x. This implies (5.58) and concludes the proof of Lemma 56.1.

Proof of Theorem 56. We are going to prove that 0(nk) <
(5.60)

It follows from Lemma 50.1 that cl(n/nK) < (2 + o(1))L p.p.x; moreover from one of the elementary properties of A (see Lemma 61.1) we also have 0(n) < r(n/nK)A(nK), whence L(n) < 5LA(nK) p.p.x.

Together with (5.60), this implies (5.55).

The starting point is the identity

A(mp;u)=4(m;u)+A(m;u-logp) (plm).

(5.61)

When L < k < K (n) we may apply this with m = nk, P = Pk+ 1(n), raising both

sides to the power q, performing the binomial expansion on the right and the integration w.r.t. u over (- oo, co). We obtain Mq(nk+ 1) = 2Mq(nk) + Rq(nk+ 1)

(5.62)

where Rq(nk+1):= 9_1

J

IX

(nk;u)q-iA(nk;u-logPk+1(n))'du.

(5.63)

114

Erdbs' conjecture

5

We want to average Rq(nk+1) over `normal' numbers n with fixed nk and variable Pk+ 1(n) in order to obtain an upper bound for Mq(nk+ 1) in terms of

nk, p.p.x. To this end we first have to define a set Ak of integers a that are good `candidates' to being the nk of some normal n. We let Ak be the set of all

integers a such that (Akl)

µ(a)2 = 1, w(a)=k-L, logP+(a)<e-Llogx,

(Ak2) (Ak3)

log2a
(1-E)(j+L)
where a is a small positive number, fixed until the end of the proof. Set

A:={n:n<x,nkeAk (L
range for

k),

(Ak2) follows p.p.x from Theorem 07, and (Ak3) is a

consequence of the corollary to Theorem 10. Now put Sk(x, a):= card {n: n < x, nk = a}.

Lemma 56.2. Let L < k < M, aeAk, P+ (a) < p < exp exp (loge x - L). Then Sk+1( x, ap) <<

x log P - (a)

aplogP+(a)

Proof. Let b denote generically an integer such that w(b) = L, 11(b)2 = 1, P+ (b) < P- (a). Then Sk+ 1(x, ap) counts the integers n = bapdm < x where all prime factors of d divide bap, and P - (m) > p. Hence

Sk+ 1(x, ap) = Y E x(t) b t-x/bap

where x is the completely multiplicative function such that x(p') = 1 if p' Ibap or p' > p, x(p') = 0 else. The conditions imposed on b, a, p imply bap = x°(1) provided L - oo suitably slowly: hence Theorem 01 implies that the t-sum

We notice that (Ak3) implies that

above is pp(ap) >> ap and use the trivial bound

Y(p(b)-1< n I1+ P'

b

I<
which yields the required estimate. We may now carry out the averaging process. We summarize the estimate which results as follows. Lemma 56.3. Define q-1

Wq(m):=,Y1

(q) M;(m)Mq-1(m).

j

4 A p.p. upper bound for the 0-function

115

Then, for kc(L, M), q 3 2, aeAk, we have

xlogP-(a)

Y R 9(n k+1 )<<

alog2P+(a)

neA

W4 (a)(1+29ex

pl- togP+(/a))) //

(5.64) l

l

nk=a K(n)>k

Proof. We have

Tj(a):= Y J

A(a;u)9-jA(a;u-logpk+,(n))jdu

neA

00

nk=a K(n)>k

Y p>P+(a)

J -oo

A (a; u)9 -' A (a; u -log p)' du Sk + 1 (x, ap)

apeAk + 1

«

P

aD

a loge P+((a)

A(a; u)9 -' Y A(a; u - log p)' - oo

p> P

log p

du

P

(a)

by Lemma 56.2. We expand L(a; u - log p)' as a multiple sum, and invert summations. The sum over p involved is eu+, ' {lOP eu < (5.65) p > P+(a) } p

\

*

max di

in di

dl,.

))

i

where the star denotes that summation is restricted to j-tuples of

of a such that log (max di/min di) < 1. Put a = max(u - log min di, log P+(a)), /3 = u + 1 - log max di. By the Prime divisors {dl, d2, ... , di}

Number Theorem, the sum over p above is /3 - a + O(exp(and we rearrange the main terms and add the remainders in (5.65) to obtain

J ,og P+ (a)

where

A(a;u-v)'dv+O(M*(a)exp(- JlogP+(a)))

Mj*(a):=

Y*

1 ,<2'M;(a) (a, jEiZ+).

(5.66) (5.67)

d1,d2,...,djIa

To establish the inequality on the right, notice that M*(a)<,

f.

Y

min di

d1,d2,...,d;Ia

J

(A(a;u)+A(a;u+1))'du

{A(a;;u)'+A(a;u+ 1)'}du=2'Mi(a).

<, 2j-1 J

W_ CO

We insert (5.67) into (5.66), observing that the main term in (5.66) does not exceed Mi(a). We obtain x log P- (a)

T' (a) «alog2P+(a) MQ-i(a)Mj(a)(1 + 2'exp(-,/log P+(a))). Referring to (5.63) we see that this yields (5.64).

116

5

Erdos' conjecture

We may embark on the final stage of the proof. Since Mq(nk+ 1) - Mq(nk) when k > K(n), Lemma 56.3 gives, for ke(L, M], aeAk, q > 2, Y (Mq(nk+ 1) - 2Mq(nk))+

Wq(nk)-1

nEA

nk=a

<<xa -1 exp { (1 +)L-2(1 - e) k} (1 +2q exp (-(I. 5)k))

fore
Y-

aAka

<

ij

(1+i)<<exP(1+c)k_(1_)L} 17

(1)e
+s)k

and we get

Y (Mq(nk+1)-2Mq(nk))+Wq(nk)-1 <<

xe-(1-5e)k

(5.68)

neA

For each ke(L, M], the following set of inequalities hold (simultaneously), for all except << xe-ek of the integers neA: Mq(nk+1)<2Mq(nk)+e-(1-7e)kWq(nk)

(1
(5.69)

After consideration of all the exceptions for different ke(L, M], we see that (5.69) holds p.p.x, simultaneously for all these k. Let I < 6 < (1 - 7e)/log 2. We are going to prove by induction on k that for each fixed ke(L, M] Mq(nk) < 2akq! (1 < q < k) p.p.x.

(5.70)

For convenience put e1 = exp (1 - 7E). For k = L + 1 we have Mq(nk) - 2 for q >, 1, neA, and (5.70) holds. Suppose it holds for k. When q < k, we may appeal to (5.69) to estimate Mq(nk+1). This yields Mq(nk+ 1) <

21(k+ 1)q! (21-a

+ k(2b/e1)k) < 26(k+ 1)q!

if L, and therefore k, is large enough. When q = k + 1 we can still use (5.70) to majorize Wq(nk) (which is a function of the M;(nk), j < q - 1 = k), but we need some extra information to estimate Mk+I (nk) which is provided by Lemma 56.1 applied with q = k. Thus Mk+ 1(nk) < A(nk)Mk(nk) < Mk(nk) 1+

C1

Mk(nk)1)k

because (3/e)'+' < 3/e1. Whence, by (5.70) (with q = k), 8

Mk+1(nk)2,b(k+1)(k+1)!

k+

) )Ilk

3

1 + e1( k+1

(

<2a(k+1)(k+l)!{ 3 +0(1) } e-e1 1 ))

4 A p.p. upper bound for the A-function

117

by Stirling's formula, and (5.69) gives

6 +o(1)+k(2a/ei)k} e-el

5

26(k+' (k

+ 1)!

provided s is suitably chosen, and k is large enough. This completes the induction and so proves (5.70). In particular we have Mx(nx) 5 2a'K! p.p.x, and (5.60) follows, on taking Kth roots and applying (5.56). This completes the proof of Theorem 56.

118

Notes on Chapter 5 §5.1. The concept of concentration function was introduced in 1937 by Paul Levy as a tool for the study of sums of random variables. For any random variable X with distribution function F the concentration function is defined by the formula

Q(l):= sup(F(x+l)-F(x)) (1>0). xeP

An account of the subject may be found in the book of Hengartner and denotes the concentration function of the r.v. Theodorescu (1973). If D taking the values log d(n) with uniform probability 1/r(n), then A(n) = r(n)Q.(1).

However the results available from Probability Theory do not go very far

in the study of the A-function. The Kolmogorov-Rogozin inequality reads here A(n) << T (n) w (n) -1 /2,

(1)

as an immediate consequence of the canonical expansion as a sum of independent r.v.'s,

D Y D. v"Il n

The example following (4.65) shows that (1) is optimal (apart from the constant) and it seems that no finer general result has been obtained so far

that could, for instance, yield a better p.p. estimate than (1), using information about the prime factor distribution of normal numbers. The first proof of Erdos' conjecture appears in Maier & Tenenbaum (1984), where it is shown that the upper bound (5.13) for E(n) holds p.p.x when i/i -+ oo - the cardinality of the exceptional set is not estimated. As we mentioned in the remarks following Theorem 53, R1 (x, fi(x)) = o(1) only if tli(x) > C V1093 x: this limits (5.14) as a p.p. lower bound for E(n) and a slightly better result can be found in Erdos & Hall (1979): for every s > 0 we have E(n) > (log n)l -',g3 exp { - (1 + c) log 3 ,/(21og2 n logo n) 1.

(2)

If the Fourier transform method could somehow be applied to the problem of the p.p. upper bound for 0(n, t), it is likely that the factor ,,/log4 n above could be replaced by any function tending to infinity.

The p.p.x lower bound (5.11) for U(n,a) was conjectured in Hall & Tenenbaum (1981).

Notes on Chapter 5

119

§5.2. The main idea of the proof (that is the inequalities (5.24)) is essentially that of Erdos & Hall (1979).

§5.3. Theorem 56 is due to Maier & Tenenbaum (1985). The proof presented here is almost identical to the one in their paper. It is easy to see that the upper asymptotic density of those integers which have two prime factors p, q such that p < q < 2p is less than 1. Several questions about the propinquity of prime factors were discussed by Erdos (1959).

120

Exercises on Chapter 5 Let .9 denote the set of `Erdos primitive' numbers, that is numbers having two divisors d, d' such that d < d' < 2d but such that no proper divisor has this property. (i) Use Theorem 21 to show that 50.

Y{1:n<x,nel}<< x(logx)-a(loglogx)-112 (with 6 as in (2.3)).

(ii) Let -4 = .4(I) be the set of multiples of S. Show that Behrend's Inequality (see Exercise 21) implies that dR <, I - fl {(1 - l/n):nel}. Deduce from Theorem 52 that Y { 1/n: neI} = + oo.

(1)

51. (Sequel to Exercise 50). Let a1 < a2 < be the sequence of those integers having no divisor in I. Show that, if (1) were false, then {a;} would have positive lower asymptotic density. Show that all numbers n = pal, with (a1, 6) = 1, p < a; < 2p, belong to 9, and deduce from this a contradiction i.e. a direct proof of (1). [This argument, due to Erdos, was known to him long before the proof of his conjecture.] 52.

Define h(n):= Y_{d,(n)/d,+ 1(n): 1 <j
that h(n) 3 co 1093 n p.p. What value of co can you obtain?. [Hint: see the proof of Theorem 55.] 53.

Let F(a) denotes the distribution function of Tt(n)/T(n) (cf. Theorem 49),

that is, for aeWF, the asymptotic density of the sequence {ne7Z+: rt(n) < ar(n) }. By applying Theorem 51 with u = z and v large but fixed, prove that 1 e'F. Define T*(n) = T(n, 0) -T(n), and show that, for all n, T*(n) > r(n) T+(n). Let F* denote the distribution function of T*(n)/T(n) (cf. §4.5) and deduce from Exercise 53 that Oe'F*. 54.

55.

Let ee(0, 1) be fixed and define Prop (n): = card Q: 1 <j < T(n), di+ 1(n) < (1 + e)dj(n) }

.

Show that Prop(n)/T(n) has a distribution function which is continuous at 0 and 1.

6 Hooley's Or functions - sharp bounds 6.1

Introduction

We have already met the function A(n) in Chapters 4 & 5: it is the maximum

number of divisors of n contained in any interval of logarithmic length 1. More generally, we set A(n;u1,U2,...) Ur-1)

uj+1 (1<,i
=card

(6.1)

so that the definition of the A; function in Hooley (1979) is equivalent to Ar(n)=

max

A(n;u1,u2,...,ur_1),

(6.2)

U1,UZ....,Ur_ 1

in particular A2(n) = A(n). It is convenient to define A1(n) = 1.

We note that Ar(n) is a non-decreasing function of r: we have only to restrict the range for the maximum in (6.2) by setting ur-1 = 0, and take d,.-,=I. Also, for fixed r the renormalized function 21-rAr(n) is supermultiplicative, that is for relatively prime m and n we have 21-TAr(mn) >,(21-rAr(m))(21-rAr(n)). For if did2 ... dr_ 11m, t1 t2 ... 4-11n, u; < log d1 u; + 1, v1 < log t; ,
JA(mn;u1+V1+eli...,ur_1+Vi_1+er-1)

(6.3)

E

where the sum is over the 2r-1 vectors e=(E1,e2,...,Er_1)e{0,1}r-1. The result follows on taking the maximum on the left of (6.3). Often Ar(mn) is larger than Ar(m)Ar(n). For example, we have A(2") = 2 (a >, 1), A(p") = 1

(p >, 3, a >, 1). But A(2"3a) >, /i + 1 whenever 2°` > Y. To see this, set u1 = # log 3. For each b, 0 < b < f3, there exists a, 0 < a < a, such that d:= 2'3' satisfies u1 < log d < u1 + 1. The reader may find it helpful to evaluate Ar(n) in a few simple cases (cf. Exercise 60). The function A(n) is a measure of the propinquity of divisors: it is also

a concentration function in the sense of Paul Levy (1937). At first sight the extension to Ar(n) seems a little artificial; however, the function

122

6 Hooley's A; functions - sharp bounds

presents itself in a natural way in Hooley's `New Technique' (1979). This is a method which is effective in a wide range of problems in the areas of Diophantine Approximation and Waring's Problem. What is needed in these applications is an upper bound for the sum Sr(x):= Y_ Ar(n) ncx

(6.4)

appreciably better than what would be obtained from the trivial inequality Ar(n) < ir(n). Since Ar(n) > 1, and the average order of Xr(n) is (log n)r-'/(r - 1)!, we can of course only save a power of a logarithm here. However there are circumstances where this is exactly what is needed. For example Hooley used his upper bound S2 (x) << x(log x)41" -' to show that the number of integers n < x expressible in the form n = a2 + b4 + c4 is >>Ex/(log x)4/" -' +E. The results of Chapter 7 enable us to replace the denominator here by an (explicit) slowly oscillating function of log x - see Tenenbaum (1986). Generally, Hooley's technique is at its best when the result envisaged is sharp except for a power of a logarithm, or when such a saving in an error term is the only way to obtain an asymptotic formula. Vaughan (1986, 1986a) is the most recent application at the time of writing. We consider a more general sum than Sr(x), namely Sr(x, y):= Y A&(n)y-(°°.

(6.5)

Definition. For r >, 2, y > 0 we denote by a(r, y) the infimum of the numbers such that Sr(x, y) << x(log x)4. By applying Holder's inequality to (6.5) we see that a(r, y) is a convex function of logy: as such it is continuous. In Chapter 7 (cf. Theorems 70,71) we shall prove

a(r,y)=y-1+(r-1)(y-1)+ (r,>2,y>0).

(6.6)

The value y = 1 emerges as quite special independently of its importance

in the New Technique and S,(x) itself is better understood within this slightly more general setting. 6.2 Lower bounds We begin with a simple lower bound for Sr(x, y) which helps to fix our ideas; it also serves as a target for our upper bounds. Let k = [log n] + 1. Then Y ... Y A(n;hl,h2,...,hr-i) ir(n) 05h1
06hr_1
kr- 1Ar(n) < (log en)r - 1A,(n)

3

For r

Theorem 60.

The critical interval

123

2, y > 0 we have

max (1, 2r(n)/(log en)r(6.7)

Ar(n)

Y)>>r,yx(logx)y-1+(r-1)(y-1)+(log2 x)a(y,1),

SAX,

(6.8)

a(r,y) > y - 1 + (r - 1)(y - 1)+.

(6.9)

Proof. We have to prove (6.8). For r >, 2, y > 0 there exists a constant Cr(y) > 0 such that Y_ T,.(n)YW(")

Cr(Y)x(log

X)ry-

n<x

this may be proved by the usual analytic technique starting from Perron's formula. Together with (6.7) it yields (6.8) provided y 0 1.

Erdos had an unpublished proof that S2(x)/x-> oo and this was reproduced by Hooley (1979). The method used can be made to give a specific, but too slow, rate of growth. Instead we employ the following result - we recall the definition (4.1) of the function T(n, a). Lemma 60.1 A(n) 3 T(n, 0)/2i(n) Proof.

(n >, 1).

(6.10)

By definition T(n, 0) = card {d1, d2: d1 I n, d2 I n, I log (dl/d2) I < 11

_ Y(A(n;logd1-1)+A(n;logd1)) dlln

2i(n)A(n).

A corollary is that A(n) > 1 T(n, 0)/21("), and (6.8) (with y = 1) follows from

(4.9). For r > 2 we just use the inequality A,(n) >, i(n). 6.3 The critical interval

The title of the present chapter arises from the fact that for certain values of y the lower bound (6.8) is actually sharp, apart from constants; that is we can replace >>r,y in (6.8) by -=-,Y. More precisely, we are going to show

that there exist non-empty intervals 0 < y < y', y" < y < co on which Sr(X,Y) ^r,yx(logxl

-1+(r-1)(y-1)+

(6.11)

Definition. A,- is the supremum of the numbers y' such that (6.11) holds for each ye(0, y'). A, is the infimum of the numbers y" such that (6.11) holds for each ye(y", oo). Ar

Notice that these bounds are attained. Also, from Theorem 60, 1 Ar .

124

6

Hooley's Ar-functions - sharp bounds

We show in Theorem 62 that if Ar
For each r > 2, the critical interval is the non-empty interval

[Ar,Ar]. The scheme of this and the next chapter is as follows. In the remainder of this chapter we prove the existence of Ar-, A; and establish bounds for these functions. In Chapter 7 we give upper bounds for Sr(x, y) in the critical interval which are sharp except for factors involving certain explicit slowly oscillating functions of log x. A corollary is (6.6), the formula for a(r, y).

Technical preparation

6.4

At several points of our treatment of upper bounds for Sr(x, y) in this and the next chapter, it will be convenient to restrict our attention to squarefree numbers, moreover to deal with the weighted sum

.

Theorem 61.

n

For each r >, 2 and y > 0 we have Sr(x, Y) <
Lemma 61.1.

(6.12)

µ2(n) A (n)y'(n).

n5x

x Zr(x, Y). log x

(6.13)

For all integers m, n (not necessarily coprime) we have (6.14)

Ar(mn) < rr(m)A,(n).

Proof of lemma. Every divisor of mn can be written in the form dt, where d1m, t1n. Hence

A(n;ul-logdl,...,ui_1-logdr-1)

A(mn;ul,...,ur-1)< dl /..d,_ lam

Trlm)er(n)

The result follows on maximizing the left-hand side. Proof of Theorem 61. Every integer n may be written in the form d2k where k is squarefree. Put yl = max (y, 1). Then w(d)

co(n)

Ar(n) y n<_ x

`+ Tr(d2) n

d=1 <
Y12

d

Y

ksx

µ2

(k

k

Ar(k)Y'"(k)

4

Technical preparation

125

because the infinite series on the right is convergent. Next, Sr(x, y) log x =

Ar(n)Yw(") log x + Y Ar(n)YW (") log n, n

n<x

n<x

and since log (x/n) < x/n the first sum on the right is <
n<x

n<x

din

and we write n = md, invert the order of summation on the right, and employ Lemma 61.1 again. The sum above is Y A(d) Y Tr(d)Ar(m)YiYG'(m)

d<x

m<x/d

Yi Y Ar(m)YG'(m) Y A(d)ir(d) m<x

d<x/m

and the inner sum on the right is «,x/m. So we have <<,,yxZ,(x, y) on the right. Putting these inequalities together, we get Sr(x, y)log x <<,,y xZr(x, y) which is (6.13).

Lemma 62.1. For every r >, 2 and 0 < y < z we have x)rz-ry,

Zr(x, Z) <
and, for0
x)z-y r A,(n)

yo(n) n

n<x

Proof. We begin with the first part. We have p2(d)

Zr(x, z) _ Y µ2(n) Ar(n)Y"(") n<x

n

r

1

an

and we write n = md, A,(n) <, i,(d)A,(m). Hence '02(d)

p2(m)

Tr(d)(Z -

Zr(x, Z) d<x

m<x

and the first sum on the right is << ,y,Z(logx)rz-ry. This is the result stated.

Next, let z < y < 4, so that z(y - z) 5 y. Then Z,(Jx,z)(logx)y-z <
M<./x

Z)w(n/m)'

«,>Y>z

n<x

i1

A,(n) mIn

\\

on putting and = n and A,(m) < Ar(n). The inner sum is multiplicative and

6

126

Hooley's A; functions - sharp bounds

for n = p" it equals y if a = 1, z(y - z) < y if a = 2, and 0 if c x>,3. So it is S yu'(") in general, and this is the required result.

If Ar < A, then (6.11) is false throughout (A , A; ).

Theorem 62.

Proof.

Let y > 1 and (6.11) hold. By partial summation, Zr(x, y) << x)r''-r+1, and so, by the first part of Lemma 62.1 and (6.13), (6.11)

(log

holds for z > y. Hence y > A; A. If y < 1 and (6.11) holds, it holds for z < y

by a similar argument, using the second part of Lemma 62.1. Therefore

y,
following inequalities. Lemma 63.1 A(n; u)2 5 Y_* A(n/bb'; u - log b),

(6.15)

66'In

where * denotes that summation is restricted by the conditions Ilog(b/b')1 < 1,

(6j)

1.

Proof. Let A(n; u) = k, and d 1, d2, ... , dk E (e", e" + 1 ] be the divisors of n in this range. For each of the k2 choices of i, j k write bi; = di/(di, d;), 6;; = d;l(di, d;), so that I log (bi;lb j) I < 1, (bi;, b';) = 1. If we now sum over all possible 6,6' allowed by the summation conditions in (6.15) we shall

account for all k2 choices of i, j if we reckon how many pairs can give rise to the same 6, b', that is have bi; = b, b;; = 6'. Let di = bt, d; = b't. Then t is restricted in two ways. Firstly t I n/bb', secondly u - log 6 < t u - log b + 1. (We ignore the similar condition involving 6'.) The number of these t is A(n/bb'; u - log 6), and this proves (6.15). A corollary is A(n)2'< 37,* A(n/bb').

(6.16)

66'In

This is the case r = 2 of the following result. Theorem 63.

For r > 2 and all n, we have Ar(n)2 < Ar-1(n) Y* Ar(n/bb'). 66'In

where * has the meaning defined in the previous lemma.

(6.17)

6 Small y - the lower bound for Ar

127

Proof. Choose v1,V2i...,yr_1 so that 0(n;vi,...,vr-1)=Ar(n). Then we have (we may assume r > 3)

Ajn)_

L(n/dld2...dr-2;vr-1),

Y_

dl...d,_21n vt
whence by the Cauchy-Schwarz inequality Or(n)2 <, Ar- 1(n)

A (n/d1 d2...dr-2,vr-1)2

Y_

d,...dr_21n

vi
We apply (6.15) to the summand, and invert the resulting double sum. This yields 1 r(n)2 < A, _ 1(n) E* In

A(n/88'd1... dr-2;Vr-1- log 8).

E

dld2...dr_2In/66'

v;
But the inner sum is A(n/88'; v 1, ... , vr- 2, yr - 1 - log 6) which does not exceed Ar(n/88'). This gives (6.17).

6.6 Theorem 64.

Small y - the lower bound for A,

For every r >, 2 we have A , 2. More precisely, for

O
1(log2x)(r- 1)a(2y,1).

(6.18)

Proof. We work with Zr(x, y), relating this to Zr-1(x, y) via the inequality (6.17) to set up an induction over r. Let r >, 2. By Cauchy-Schwarz, Zr(x,Y)2

Ar(n)2 ya(n), µ2(n)Ar-1(n)Yu'(n) Y_ µ2(n) n<x n n<x n Ar-1(n)

Y

and we notice that the first sum on the right is Zr-1(x, y). We apply (6.17) to the second sum, which does not exceed µ2(n) yU,(n) E* nsx

din

0r(n/S8')

µ2(S8')

< SS'<x

Sxfq

88'

I log(S/S')(< 1

We make the trivial estimate Zr(x/88', y) <, Zr(x, y). Of course such a step

applied to Sr would be quite useless. We divide through by Zr(x, y) so

6 Hooley's A, -functions - sharp bounds

128

that we have Zr(x, Y) 1< Zr - 1(x, Y)

P2(661) y0,(66') SS'

Y_ 66'Sx 1100/01 < 1

(Y

w(6)

1< Zr-1(x,Y) Y

6<e,/x

Y

6/e<6<6e

-

m(6') V

yw(a)

<
6<e,/x

(logbe)y-1

S

We estimate the sum on the right by partial summation: <<

it is

(logx)(2y-1)+(1og2x)6(2y, 1). For y<2 this gives

Zr(X, Y) «yZ,.-1(x,

Y)(log2x)6(2y,1)

and, since Z, (x, y) << y(log x)y for all y, we obtain, by induction on r, Zr(x, Y) << r,y(log

x)y(log2x)(r-1)6(2y,1)

(r >, 2, y _ i)

We apply Theorem 61 to complete the proof. This method works with partial success and can be refined in various ways when y > Z. First, in the application of the Cauchy-Schwarz inequality we can replace the factor y(") which appears in both sums on the right by (y2/z)°'(") and zw(") respectively, where z may then be chosen optimally. Second, there is a more general inequality than (6.17) in which the factor Ar_s+1(n) appears outside the sum, with s>, 2 at our disposal. The sum on the right of (6.17) becomes somewhat more complicated. These ideas were exploited in Hall & Tenenbaum (1982, 1984). They lead to the iteration inequality 2a(r, y) < a(r, z) + (s - 1)(sz - 1)+ + a(r - s + 1, y2/z),

(6.19)

valid for 1 < s <, r, y, z > 0 - there is a more precise version involving Zr(x, y), Zr(x, Z), Zr _S+ 1(x, y2/z) and a power (depending on the various parameters) of 1092 x; and this yields bounds for a(r, y) or Zr(x, y) in the critical interval by means of an iterative procedure in which s and z have to be chosen optimally at each stage. In its present form this method has been superseded by that of Chapter 7, which evaluates a(r, y). However,

it is possible that the argument leading to (6.19) can be refined to yield a deeper inequality, so that the iteration method would not only evaluate a(r, y) but give new, finer, estimates for Sr(x, y) in the critical interval. 6.7 Fourier transforms - initial treatment We now turn to a method, rooted in the ideas of Chapter 3, which is very successful in the study of the sum S,(x, y) when y is rather larger than 1.

Fourier transforms - initial treatment

7

129

We begin with a result due to Hooley (1979), generalized by the simple insertion of the parameter y. Theorem 65 (C. Hooley). 1

Sr(X Y) <<,.,Y

Let r > 2, y > 0. Then 1

...

L

JL .exp Y

1

Il+e'B'`+ei02`+...+e'Br-,tIdt

dOi...dor-1

(6.20)

1

where L = log x.

Proof. We bound A,(n) from above by a multiple integral involving a multiplicative function of n. Put w(u)

=

=

(sin-f' u)2

fl

(1 - IOI)e"d9.

(6.21)

-fu

-1 Then w(u) > 0 for real u, w(u) >, w(1) > 0 for I u I < 1. Hence

A(n;U1iU2,...,U,-1)<<,

Y_

f w(logdJ-u)).

did2...d,_iIn J
We insert the integral representation (6.21) for each factor in the product on the right, and reverse the order of summation and integration. The integral involves the function

d'i'di

T(n,0,,02,...,Or-1): dld2...dr_ l In

which is of course a generalization of i(n, 0) as in (3.1). We deduce that 1

Ar(n)

<< r

1

f.1

...

Ii(n;01,02,...,0,-1)Id01...dO,-1

1

(6.23)

1

The insertion of modulus signs removes the dependence on u1,u2,...,Ur_ 1

in the integrand and so provides an upper bound for the maximum value of the integral - this step occurs in the theory of concentration functions in a similar fashion. Unfortunately it is the Achilles heel of the method as a means of estimating S,(x,1). This point will become clearer as we proceed. When n is squarefree, we have 'e,

102

;e_,

pin

and we insert the weight yw(")/n and sum, to obtain Zr(x, Y) <<, J

... J

1 1

1

fl (1 + Y I 1 + pi01 + ... + pier-

- 1 p-<x

P

I

d01... d0,-1

6 Hooley's A, -functions - sharp bounds

130

and then, via (6.13) and the inequality 1 + u < e°, 11+p9e1+...+pie,-,I 1

S,( x,y)«, L J

)}d91...dBr_1. -1 -1 p p_<x It remains to relate the sum over p above to the integral w.r.t. tin (6.20). We write ... J

exp{Y

Y_

1

f(r):= It+r'B' +r'B=+...+r'Br-=I (r>o), so that f is differentiable except at the isolated points where it vanishes. We have x

7r(r)f'(r)dr,

f (p) = 7r(x)f(x) J2

p6x

and we employ the Prime Number Theorem in the form n(r) - lit << r/log2r (r > 1). Together with the inequalities f(t) ,
+ 10, _ 1 I)/r2 < 2r/r2, this yields

I f (p) =

pox

L

etf (et) 1

t dt

+ O(r),

and (6.20) follows.

It is important to understand why (6.20) is weak when y is too small. Let I denote the multiple integral in (6.20) with the ranges restricted to 0 < 9; < 1 (1 < i < r). The logarithmic function is concave and Jensen's inequality gives L

1

'

...

log I >

y

dt

d91... d9, - i 0 t fo We integrate w.r.t. t last. For t fixed, substitute 9; = cp;lt (15 j < r) and set N = [t/2t]. Then 11 + e'B't + ... + e'Br-'t l

1

L

logI >, y

2, N

t-rdt

2itN

...

>y

e'9.-1

Il+

IdcP1 ... d9r-1

0

0

L t-r(27rN)r-1

H,dt > yH,(log L+ O(r)),

fl

where 2n

Hr

2n

... 0

0

11+e'

(6.24)

Hence I>> r,yOry and the right-hand side of (6.20) is >> r.y X(log x)

Hry - 1

The integral (6.24) is familiar in the theory of random walks. We may

Fourier transforms - initial treatment

7

131

deduce from the Central Limit Theorem that H,. - 2 what is more relevant now is that for every r >, 2 we have H, > 1 (cf. Exercise 62). It follows that when y < 1 an upper bound for S,(x, y) derived from (6.20), far from being sharp, will have the wrong exponent of log x. Indeed a(r, y) = y - 1 + (r - 1)(y - 1) + < H,y - l for y < (r - 1)/(r - H,). For these values of y the method is inefficient and we can trace the weakness back to the introduction of the modulus signs in (6.23). A rather surprising method of improving (6.23) (in certain applications) used this weakness (Hall & Tenenbaum (1984)): for A >, 0 it is easy to see that A(n) <<

1

fl J2p-'e + 1 + p'° + ,lp2iO d6

J -1 pin

for squarefree n. We allow A(n; u) to count not just divisors in the relevant interval but fractions of the form d2/d' where d and d' divide n, suitably weighted. For 2 < 3, we have 2n

J2e 'B+1+ e'°+2e21° dO=4l 1-A/

2zc

n\

o

3

which is less than H2 = 4/t if 2 > 0. This idea led to an improvement in the then best upper bound for a(2, 1). For larger values of y (6.20) is very useful. We work out the case r = 2, when the integral can be estimated fairly precisely because I 1 + e'Bis a periodic function of t. In fact the integral w.r.t. t is

4logL+ 2 log L

l

1/L).

Hence x(logx)2y-2

S2(x,Y)<<

0-(2-4in)yd9.

+x(logx)(4/n)y-1

1/L

The reader can now see the important role played by the parameter y: if y < 1/(2 - H2), we obtain S2(x, y) << x(log x)H2Y- 1, an unsharp bound which includes Hooley's original upper estimate for S2(x). For certain y,

it can be improved by the '2-method' described in the last paragraph. If y > 1/(2 - H2) we obtain the sharp bound S2(x, y) << x(logx)2y-2 (cf. (6.8));

when y = 1/(2 - H2) there is an extra factor log log x. Thus we have obtained the following.

Theorem 66. AZ 5 1/(2 - H2) = 1.375 96.... more precisely for y 1/(2-H2) we have S2(x, Y) «yx log2q-

2x(log2 x)au2 -H2)y,1)

(6.25)

6 Hooley's A, -functions - sharp bounds

132

Fourier transforms - an upper bound for A;

6.8

1/2

For r >, 3 we have A; < 1 + r

Theorem 67.

More precisely, for

y+r-'/z

(6.26)

Slightly better numerical bounds are available in the range 4 < r < 8 from Hall (1986). These are 1.469 80, AS <1.40309, A6 <1.37350, A; <1.35748, A4 '<1.46980,

A$ < 1.347 72.

An open problem of some interest is to reduce the upper bound 1 + 1/ J3 for A3 . In each of Theorems 64, 66, 67 we have an inequality A, > w, A; < z say, and the proofs also yield useful, if unsharp, results on the boundaries, respectively Sr(x, w) «x 109'-'X(1092 x)A, Sr(x, z) << x log'r X(1092 x)' for

suitable A, B. However this is a feature of these particular proofs: there is no implication that such estimates involving just an additional power of logz x hold if w, z be replaced by A,-, A, . The following proof is based on the argument to be found on p. 124 of Hooley (1979).

Proof of Theorem 67.

We write

G(t;61> 8z, ... , 0 r, _- 1J .

11+e'elw+ei02W+...+e'B'-1'"ldw 1

so that the innermost integral in (6.20) is J

L G(t) dz

+ O(r);

indeed 1

1

...

`Sr(x, Y) <4,v x

exp y

fL G(t)

dt

dO1 ... dOr-1.

(6.27)

The Cauchy-Schwarz inequality applied to the integral defining G yields

r + E 2 cos w9; +

G(t)2 < t 1

J
rtz+2t Y
Y

0
1+2t

2 cos w(8, - Ok) dw

Y

0
I

mint,

2

101-ekl

The right-hand side is largest when the B; have the same sign. Because of this, and the symmetry of the integral (6.27), we may restrict our attention to the range in which 0 < 01 < 02 < 5 Or-1 < 1, and we put 91 = x1,

Fourier transforms - an upper bound for A;

8

133

02 - 01 =X2,--,0r-1 -0,-2 - xr-1 so that the x;E [0, l]. We employ the simple lower bounds

Oj>max{xm:l <m<j}, 6,-9k>,max{xm:k<m<,l}; since we have to integrate we may assume that the x, are distinct so that

m above is uniquely determined. Of course the integral (6.27) is not symmetric in these new variables. We split the range of integration into (r - 1)! regions, in each of which

there is a permutation p on r - 1 symbols such that xP(1) < xp(2) < < X p(r _ 1), and for each m and p we denote by v(m, p) the number of times XP(m) is chosen as maximum above. In the region associated with the permutation p we then have r-1

G(t)2 < rt2 + 2t Y v(m, p) min (t, 2/xp(m)), M=1

and so, if xp(a) < 1/t'< Xp(a + 1) (we put a = 0 when 1/t < xP(1), a = r - 1 when

Xp(r-1) < I/t), we have r-1

G(t),
(6.28)

(tv(m, p)/xp(m))1/2 m=a+1

where R(a):= Cr +

2M=1i V*

p)(6.29) 1/z

J

Now let b be such that x p(b) < 1/L < xp(b + 1) (with b = 0 or r - 1 if 1/L, xp(1) or xp(r-1) < 1/L). Then

f

dt

1

l/xp(r-1)rdt

G(t) t2 <_

Ji

+f

fl

t

/xp1-21

(R(r-2)+2(v(r- 1,P))1/2)dt

tXP(r-1)

1/xp ,r_1)

+

L

+

AM, P)

R(b) + 2

Uxp(a+1)

The integrals involving the factor

dt t

txP(m)

6<m
t-1/2

t 1/2

on the right-hand side are either

<< v(m, p)"2 (b + 1 < m < r), or (b < m < r),

<
so that their' total contribution is <
+

d2

t

5 R(b) log L+ (R(b + 1) - R(b)) log

+ (r - R(r - 2))log

1

XP(n+1) 1

+ Or(1).

XP(r - 1)

(The right-hand side is simply r log L + Or(1) if b = r - 1).

(6.30)

134

6

Hooley's A,-Junctions - sharp bounds

Lemma67.1. Let b1 1,

with exactly a cases of equality. Then 1

J 1/L

dub+l

dub+2Ju,_2 du-«LZ-r+(logL)uZb+l

b+1 fub+

UZ

b+2

1

+ zr-1, and the implied constant depends only

where Z = Zb+1 + Zb + 2 +

on the z;.

This is by induction on r. The result holds for r = b + 2 and we suppose it holds for r - 1, where r >, b + 3. We have Proof.

(log L)(Zr __ dur-1 u Zr_I << uZ,_,ur_2 r-1 r-2

(' 1

J

because zr _ 1 1> 1, Ur _ 2 >11/L. Hence we may reduce to an (r - b - 2)-fold

integral with exponents zb+1,Zb+2'.... Zr-3,Zr-2 where z_2=zr_2+

zr_1-1. Forb<m
as

required, and there are a' = a - b(zr_ 1, 1) cases of equality. By the induction hypothesis, we obtain altogether << (log

where Z'= Zb+ 1 + Zb + 2 +

L)s(Zr_,,1>L -(r-1)+b+I(log L)'

+Z_2=Z=Z-

and this is all we need.

Now we consider the integral (6.27), confining our attention to the region associated with the permutation p, and the range where xvcb) < 1/L < xp(b+ 1) If b = r - 1, we have x,,, < 1/L for every m so that the

volume to be integrated over is < L1-r. So we obtain <<

logx x

Ll-rexp(rylogL)<< xlog"''-rx

using (6.30). Now let b < r - 1. We multiply (6.30) by y, exponentiate, and insert in (6.27). We apply Lemma 67.1, with u, = xp( ), Z; = y(R(i) - R(i - 1)), b + 1 < i < r. We must establish the inequalities (r - R(r - 2))y >,> 1,

(r - R(r - 3))y >, 2,

(6.31)

z = (r - R(b))y >, r-1-b, and determine how often equality occurs. To this end we maximize R(s) as a function of p.

Let us write s = r - 1 - q (q > 1). We have to maximize v(1, p) + + v(s, p), which is the number of times one or other of Xp(t ), v(2, p) + +x1(0 < k < l < r). xp(2), ... , xv(5) is the largest x1 in the sum xk + 1 + xk + 2 +

Since these are the smallest variables, equivalently none of xp(r_q), Xp(r_q+1),...,Xp(r_1) occur in this sum. We write the numbers p(r - q),...,

8 Fourier transforms - an upper bound for A,

135

p(r- 1) in increasing order, as m1,m2,...,mq say, and for convenience in what follows we introduce mo = 0, m9+ 1 = r. If, for all i, m) 0(k, I], then there exists u (0 u < q) such that m k < I < mu+ 1, which gives in total mu+ 1- mu

uY

9

1

/

2

2

= 2 ut (mu+ l - mu) - 1it

choices for k and 1. Thus 1

S

=1

v(i, P) _

N

2u=o

/

2

lmu+ 1 - mu) - zr

<(r-q)

(6.32)

2

observing that the positive integers mu+ 1 - mu have sum r: the sum on the right of (6.32) is maximal when mu+ 1 - mu takes the value r - q once and equals 1 else. From (6.29) and (6.32), we deduce that (since r - q = s + 1),

R(s) < J(r + s(s + 1)) (0 < s < r).

(6.33)

We show that, when y >, 1 + r 1J2, the inequalities (6.31) hold, whatever the value of b, that is

(r-R(s))y>,r-1-s (0,<s
(r+s)y2-2ry+r-s-1>, 0 and this holds: the left-hand side is at least r(y - 1)2 - 1 > 0. Moreover equality requires both y = 1 + r- 1/2 and s = 0. That part of the integral (6.27) under consideration is «xLR(b)y-b-1

f

J

1

dxP(6+1) (R(b+1) R(6))y

1/LxP(b+1)

I

J

1

dXP(r-1)

(r-R(r-2))y'

X (r-2)xp(r-1)

and we have shown that the conditions of Lemma 67.1 are satisfied. Since z = (r - R(b))y, the above is << xLry-r(log L)°

where a 5 1, with equality if and only if y = 1 + r-1/2, b = 0. We put all these integrals together to obtain (6.26). This completes the proof. The exact order of magnitude of the right-hand side of (6.20) has not been determined in any of the cases r >, 3, y < 1 + r-1/2. Let us denote by P(r, y) the infimum of the numbers for which it is << LL. We must have

-

1, ry - r) and we see that there is equality when r = 2. We prove in the notes that fl(r, y) < max (yV r - 1, ry - r). The fl(r, y) > max (HrY

simplest hypothesis is that the exact order of magnitude is Lmax (Hry - 1, ry - r) (log L)8(y, (r- 1)1(r-H,))

136

Notes on Chapter 6 The original definition of Ar , A, which appeared in Hall (1986) was different. When that paper was written the function a(r, y) had not been evaluated for every y. In view of Hooley's opinion (Hooley (1979), p. 116)

that a(2,1) > 0 it was not at all clear that the graph consisted of two straight lines - a(r, y) might have been differentiable. Hall defined A, - =sup {y: a(r, z) = z - 1

(0 < z ,
A; =inf{y:a(r,z)=rz-r (y,
from above, and so it pre-dates the iteration inequalities of Hall & Tenenbaum (1982, 1984) which were used to show that a(2, 1) < H2 - 1, a(3, 1) < H3 - 1, a(4, 1) < 1, and (more significantly now), to evaluate a(r, y), y < 2. Hooley stated (Theorem 1B) a result equivalent to Sr(x,1) << x(log X)''r-1, proving this when r = 3, and the mistaken conviction of Hall & Tenenbaum (1984) that the proof could not be extended beyond r = 4 has led to some confusion. To set the record straight, we show now that the method can be made to yield S,(x, y) <
for y
I

+

sr1t2logL+(R(1)-R(0))log

1

a+xvcl)

1

+(r-R(r-2))log a+xp(r-1) +Or(1).

The contribution to (6.27) is <<

xly`lr-1

f

1

1

dxPcl)

o (a+XP(M

))zi

dxp(r-1)

j,(2)(a + Xp(r_1))Zr_

1

where, as before, zi = (R(i) - R(i - 1))y. We claim that for y < 1 + r- 1/2 we have z1 + z2 + + zs < s (1 < s < r), and that this latter condition implies that the multiple integral above is bounded as a -> 0. A similar assertion (with z1 + z2 + + z, ,<s, and the integral <
Notes on Chapter 6

137

and proved in Hall (1986): the stronger hypothesis and conclusion may

be treated in the same way. The former part of our claim is that (R(s) - .,/r)y < s, or, from (6.33), that (V(r + s(s + 1)) - V r) (1 + 1 / Jr) < s.

This last inequality is valid for s = 0, s = r - 1; and we just observe that the left-hand side is a convex function of s. This gives the result stated: a corollary is /3(r, y) < max (y -I/r - 1, ry - r).

138

Exercises on Chapter 6 60.

Prove that

Or(2")r 0 11+(r 11+...+(r a 1

61.

11

Prove that, for y, z > 0, Zr(x, y)2 '< Zr - 1(x, Y2/Z)Zr(x, Z)

E dd'Sx

µ2(dd') Zm(dd') dd'

IIog(d/d')I < 1

and hence that 2a(r, y) <, a(r, z) + (2z -1)+ + a(r - 1, y2/z).

(This is (6.19) with s = 2). Put z = i and deduce that , - 1)

- z (Y % z) Now substitute a(2, z) z2 - 4 in the iteration inequality above and a(r,Y) < 2-r((2Y)2r

estimate a(r,1) by choosing z optimally. 62.

Prove that for keZ+ the moment

-

M' 2k).-

2n

1 (2it)r-1

fo2. ...

1

0

is a polynomial in r of degree k, with leading term k!r'. Evaluate M(2) and M(4), and deduce (by Holder) that r312 /(2r2 - r) 1/2 < Hr 1<

Vr.

7 Hooley's Dr functions interval 7.1

- the critical

Introduction

We continue our study of Hooley's function Or(n), defined by (6.2), and we recall Theorem 60 which states that Sr(x, y):° Y Or(n)y-(n) n<x J J r.

Yx

(log x) Y - 1 + (r - 1)(Y - 1)' (1092 x)8(Y1)

The simplest hypothesis is that the right-hand side represents the exact order of magnitude of Sr(X, y). Conjecture.

For each r > 2 and y > 0 there exists a constant A(r, y) such that Sr(x, y) '- A(r, y)x(log x)Y

-1 +(r- 1)(Y - 1)' (loge

x)a(Y.1)

(7.1)

This is quite strong, and we review what we know so far. There is no question about the order of magnitude as a lower bound; moreover for each r there exists a `critical interval' [A , A, ] outside of which (7.1) actually holds if we replace - by _ . Moreover we know that i z Ar 1
Since this method does not (and seems unlikely to) yield sharp bounds, it is only employed in the critical interval. We obtain the following results.

140

7

Theorem 70.

Hooley's A, -Junctions - the critical interval 2 we have that)\/(rlog2

For each r

Sr(x, 1)<<,xexp{

l

l

(r- 1 +1 gs x

(7.2)

)

and, for y> 1, Sr(x, Y) <
Theorem 71.

{(r - 1) A 2r loge

For each r >, 2 and 0 < y < 1 we have that tSJX, Y) «r,vx(log

x)v-1

exp

4 log(r + 1)

(1- Y)

(log3 x)2

(7.3)

An immediate corollary is the formula (6.6) for a(r, y). The proofs of these results rest on a common foundation, the fundamental lemma of §7.2. However, the method has two variants in which the lemma is used in ways which at first sight appear to differ only in a matter of technical preference, but emerge as much more divergent. In the proof of each theorem, the argument breaks down if y is not in the correct range. This is not yet perfectly understood, and the reader who has studied both proofs is encouraged to consider the matter for himself. To complicate

it further, we mention that there is in fact a `unified' treatment of the whole range 0 < y < oo, resembling the first variant presented here, but giving an inferior result to (7.3) when 0 < y < 1 and, apparently, requiring the introduction of an extra parameter. (See the Notes.)

Notation. The fundamental lemma

7.2

We recall from (6.1) the definition

A(n;uj,u2,...,Ur-1) = card {did2 ... dr_ 1 I n: uj < log dj < uj + 1

(1 ,
and we set (suppressing the variable r on the left) 0

M,(n):= f-

...

A(n;u1,u2,...,ur-1)gdu1due...du,-1

(7.4)

for q 1. Of course the integrand is supported on a finite range and the integral is finite. We expect that, for large q, the integral will be dominated by the largest values of the integrand, in fact lim Mq(n)11q =' r(n)

(7.5)

(cf. Exercise 74). We do not use this; we prove instead the following

Notation. The fundamental lemma

2

141

proposition which does not include (7.5) but is similar in content, and in an applicable form. Theorem 72.

For each r >, 2 and q > 1 we have M1(n) = ir(n),

(7.6)

Mq(n)

(7.7)

Or(n)q-1M1(n) < Tr(n)q,

Ar(n)q <

2(r-1)(q-1)Mq(n).

(7.8)

We prove (7.8), the rest being clear. Let Or(n) = 0(n; v1, v2, ... , yr _ 1) say, and v; < u; < vi + 1, &j=0 or 1, for 1 < i < r. Then

0(n;vl,v2,...,vr-1)
and we integrate this over the cube vi < u; < v; + 1 (1 < i < r). We obtain

(7.8) because there is no overlapping of the ranges of integration for different choices of (E1,E2,...,Er-1 ) Definition.

For non-negative ao,a1,...,ar-1 and real w, set

N(n;w;ao, a,,...,ar-1)

_ -

-oo X

cc

A(/ n, U1, U2,

.... Ur- 1)yo

, (n;Ul-W,UZ,...,Ur-1 aa2

..X n;ul,UZ-W,U3,...,Ur-1

'

X L(n;u1,...,Ur-1 - w)ar-1 du, ...dUr-1

(7.9)

where w is subtracted in turn from each ui in the last r - 1 factors. From Holder's inequality, we always have N(n; w;ao,a,,..., ar- 1) < Mao+a,+...+ar_I (n)

Definition.

For

s >, 1, set

D5(m):= Y Os(d)

(7.10)

dim

(so that for example D1(m) = i(m)). We can now state the result which lies at the centre of the method presented in this chapter in any of its forms. From now on q, and the exponents a;, are restricted to integer values.

Theorem 73 (Fundamental Lemma). Let q be an integer > 2, and

142 ao,

Hooley's A; functions - the critical interval

7

a,,..., ar _ 1 be integers + ar _ , = q. Then

that 0 ,
such

ao + a 1 +

YN(n;logp;ao,a1,...,ar-1)

log p (7.11)

p

5 where the sum is over all primes p and C is an absolute constant, precisely log p

C:= sup Z

Y,

p

z
It may be helpful at this point to write down a simple upper bound for the left-hand side of (7.11) for comparison. To do this we first show that the sum over p is really over a finite range. Now if A(n; u,, u,,. .. , ur _ 1) 0 then - 1 5 ui < log n for every i. Next, there must be at least two non-zero exponents ai, (because each is less than their sum), and so each ui appears at least once in the integrand in (7.9) without w subtracted. Hence the ranges of integration in (7.9) could as well be restricted to [ -1, log n]. If n is to have any divisor such that ui - w < log d < ui + 1 - w we also see that we must have ui - log n < w < ui + 1, that is I w I < log n + 1, and this condition actually applies because a,, a2, ... , a,._ 1 are not all zero. So the sum over p in (7.11) could just as well be restricted to the range 2 5 p < en, and then << Mq(n) log n is a valid upper bound. That given is not always as good: it is, however, what we want. Proof of Theorem 73. The first step is to show that it is sufficient to prove (7.11) when just two of the ai are non-zero. Suppose then that there are at least three, namely aio, ail,..., ais. Let ail + ail + + ais = a, and for 1 < t < s set kt = a/ai, so that Y_k, 1 = 1. We apply Holder's inequality, with exponents k, to show that the left-hand side of (7.11) does not exceed log 1ik s p

N(n;logp;0,0,...,a,0,...,a,...,0)

}

p

and it will be sufficient to establish the desired inequality for each of these inner sums. There are now two cases to consider (unless r = 2) according as io = 0 or not. We begin with the first case, io = 0: we may suppose that i, = 1.

We have ao=q-a, a, =a, ai=0 (2<, i
log

p,u2,...,ur-1)a

log p p

p

_

Y' d(')...d4)1)Ind1(2)...d(2))In

Y"

d(l)...d(,"))In p

log p p

(7.12)

2

Notation. The fundamental lemma

143

where the dash denotes the following conditions of summation:

(1zk.a), u;
(7.13)

Therefore max log dlk - min log dik) < 1, k

k

u1 -min log dike

(7.14)

log p < u1 + 1 -max log

k

k

whence, from the second part of (7.14), we always have in (7.12) Y-,

log p \

C.

P

Hence the sum (7.12) does not exceed

Y

CY t)...

1)

z)

Y1 °)

z)

°)

(7.15)

In

where the double dash means that the summation conditions are now the second line of (7.13) and the first line of (7.14). For ae7L+, U2,U3,...,Ur_1ER,

Definition.

V°(n;u2,...,ur-1):=

0(n;ut,U2,...,ur_1)adu1.

(7.16)

Consider the integral

{0(n; U1 - 1,U2,...,Ur-)+A(n; U1,U2t...,Ur-1)}°du1 _co

which, firstly, does not exceed 2°V°(n;u2,...,ur_1). But, secondly, this integral may be written as

C2 -log {(7.17)

d(11..1lln

k

k

where the * means that the summation condition is simply the second line of (7.13). If we compare (7.15) with (7.17), noting that in (7.15) the first line of (7.14) is an extra summation condition, we may deduce that the sum (7.12) does not exceed C 2°V°(n; u2, ... , U,-,), and hence that log p

N (n; to 00

A(n;u1,U2,...,Ur-1)9-°

ao

- ao

x V°(n;u2,...,ur_1)duldu2...dur_1

144

7

Hooley's A, -functions - the critical interval

- oo

- ap

Vq-a(n;U2,...,Ur-1)

X Va(n;U2,...,ur-1)dU2...dUr-1

,

(7.18)

Recall that a, q - ae[1, q - 1]. Holder's inequality gives V. (n (n; u2,

ur- 1) 1< V1 (n u2,

, Ur- 1 )(q-a)l(q

1)

)(a-11/(q-1)

X Vq(

du

together with a corresponding inequality for Vq_a. Therefore the last integral in (7.18) does not exceed

C.2q- 1 fooo ... f V1(n; U2,..., Urao

x

1)(q-2)1(q-1)dU 2

and we notice that V1(n;U2,...,ur-1)=Y_ 0 djIn

n

1)gl(q- 1)

r-1

;U2,....

1

where D was defined in (7.10). We apply this last inequality to the factor V1 in the integrand above, removing Dr _ 1(n) as a constant factor and leaving behind V;l(g-1). Finally, we apply Holder's inequality (again!) with exponents q - 1, (q - 1)/(q - 2). We have OD

.. -00

Vl(n;U2,...,Ur-1)dU2...dur-1=Mi(n)=rr(n), Vq(n;U2i...,u,-1) dU2...dur-1=Mq(n),

and we obtain the inequality (7.11) for the special sum (7.18). This completes

our treatment of the first of our two cases. It remains to deal with the second case, in which io > 0: we may suppose io = 1,

i1 = 2. First, we reduce to the case where the only non-zero

exponents a1 and a2 are I and q - 1. Suppose min (a1, a2) > 1 (so that q > 4). We write N(n; w; 0, at, a2, 0, 0, ... ) 0) in the form

J...JA(n;u - oo

1

-w,...,ur-1)bI0(n; U1, U2- W,...,Ur-1/ 2-b2

- ao

x 0(n;u1-w,...,u,_1)aI-b,A(n;u1,u2-W,...,Ur_1)62dU1...du,-1 and solve the equations k1b1 = 1, k1(a2 - b2) = q - 1, k2(a1 - b1) = q - 1, k2b2 =1, k1 1 + k2 1=1, for b1, b2, k1, k2. We find that k1= (q - 2)/(a2 -1),

k2 = (q - 2)/(a1 - 1) and we apply Holder's inequality, with these

Notation. The fundamental lemma

2

145

exponents, to the integral above to obtain that

N(n;w;0,a,,a2,0,...,0) N(n; w; 0, 1, q - 1, 0'. .. , 0)1l'`1N(n; w; 0, q - 1, 1, 0'. .. , 0)1/'`2.

(7.19)

We substitute log p for w, insert (7.19) into (7.11), and apply Holder again to the sum over p. This gives the required reduction.

We assume now that al = 1, a2 = q - 1, so that the left-hand side of (7.11) is

i pp

... f . A(n;u,-logp,u2,...,ur-1)

f.0

x

A(n;u1,u2-logp,u3,...,ur_1)q-1dul...dUr_1

(7.20)

and we make the substitution u2 = w + log p. The second factor in the integrand above is then independent of p, and we therefore seek an upper bound for the sum A (n; u

log p

logp, w + to Y-,

log p

Y, P 11...dr-i1n

(7.21)

P

where the dash implies the summation conditions u1- log p < log d, < u1 - log p + 1, w + log p < log d2 5 w + log p + 1, u1 < log di ` u1 + 1

(3 . i < r).

The first two conditions involve

ul+w
Y_ did2In

P

ui+w6logd1d2
where the double dash means that we require max (u, - log d 1, w - log d2 - 1) 1< log p

z min (u, - log d, + 1, w - log d2), so that the inner sum in (7.22) does not exceed C. Hence the sum (7.21) is

CY

fA(n ;u,+w-logd,,u3,...,ur-1

ii

+Dl a ;ul+w-logd,+l,u3,...,ur_I 1

/))

146

7

Hooley's 0; functions - the critical interval

after the definition (7.10) of D. We insert this last upper bound into (7.20) to deduce that 1,0,...,0)logp

Y N(n; log p; 0, 1, q -

P

P

<2CDr-1(n)J

0(n;U1,W,U3,...,Ur-1)9-1dU1dW...dUr-1.

-o0

- ao

The final application of Holder's inequality may be left to the reader: he must be an expert on this by now. 7.3

First variant - differential inequalities

The method of this chapter begins with the identity, valid for integers n and primes p not dividing n, A(np;u1,u2,...,Ur-1)=0(n;U1,U2,...,Ur- 1)

+i(n;u1 -logp,U2,...,ur_1)+... +A(n;u1,...,ur-1 -loge)

(7.23)

in which there are r terms on the right, log p being subtracted in turn from

each u; in the last r - 1 of these terms. We raise to a high power q and integrate, obtaining Mq(np) on the left and on the right r diagonal terms each equal to Mq(n) (since the shift of any variable by log p does not affect the integral), and rq - r off-diagonal terms N(n; log p; ao, a,,..., a,- J The treatment of these off-diagonal terms will involve the fundamental lemma, Theorem 73. Thus the idea is to use high moments to show that the terms

on the right of (7.23) usually behave almost independently, so that, for most n and p, Mq(np) is not too large compared with Mq(n). As explained above, there are two variants of the method, just according to how the extra prime p is introduced. However this affects the technical 'working-out' in such a way that one variant yields Theorem 70, the other Theorem 71.

In either case we work with squarefree numbers only (which is inherent in the form of (7.23)), finally switching over to all numbers very much as in the previous chapter. In the first variant, we require two lemmas. Lemma 70.1.

For a > 1 we have Y_ P

log p < P°

- NO < a - 1

(7.24)

C(a)

Proof. We have 1

1

(a) = a- 1+ 2+

{x}(1-{x})

a(a+1) 2

f"O

xQ+ z

dx

3

First variant - differential inequalities

147

where {x} denotes the fractional part of x. The integral is positive, and

C(a)>a

+1 (a> I).

I

1

Differentiation yields

- (a)

_

a(a+1) °°{x}(1-{x})logx

1

a -1)2 +

xa+2

dx

{x}(1 - {x})

(2a+ 1) 2

fl

2

dx,

xa+2

floo

in which the third term on the right is negative, and the second does not exceed

a(a + 1)

a

log x

f1'O xa+2dx=8(a+1).

8

Hence

(a- 1)-2+-8la(a+ I)-I

2(a) <

1

(I

<

(a-1)-1+1

)

For a > 5 it is enough to check that log n < log 2 + ('' log x

-('(a) < C(O-)

n

na

2

dx <

xa

I a - 1

Lemma 70.2. Let L(a), X(a) be continuously differentiable for I < a < ao and satisfy respectively

- L'(a)

cp(a, L(a)),

- X'(a) = W(a, M CA),

where qp(a, x) is a non-decreasing function of x for each fixed a. Let L(ao) < X(ao). Then L(a) < X(a) throughout the range 1 < a < co. Proof. Suppose the contrary. Then there exists a1 (1 < a1 < ao) such that L(a1) = X(a1), L(a) < X(a) for a1 < a < ao. And f00

L(a1) =L(ao) -

E(a) da a,

L(ao) + Ea (p(a, L(a)) da i a0

(p(a, X(a)) da = X(a1)

< X(ao) + J a,

which is a contradiction. This completes the proof.

148

7

Hooley's 0, functions - the critical interval For y >, 1, a > 1, and integers q >, 2, define

Proof of Theorem 70.

ao

L(a)

=*

Mq(m)I/q

y

w(m)

m

M=1

where the * denotes that summation is restricted to squarefree m. We have yw(m)

00

Y log p

- L'(a) = Y* Mq(m)1/q m-1

= yy

m

log

Plm

w(n)

0o

p Y

n=1

(7.25)

Mq(np\1/gyna

l

/

P pin

We raise (7.23) to the power q and integrate, to obtain Mq(np)_

q

Y C al,..., aras+a1+...ao,

JN(n;logp;ao,...,ar-1)

(7.26)

+a,-, =q

There are r diagonal terms on the right (in which one a; is equal to q), and for these we have N(n; log p; ao,... , a,. -1) = Mq(n). Lemma 70.1 and the Fundamental Lemma (7.11) yield log p p°

Y M (np) P

q

\

rMg(n)

a-1

r)C. 2q - 'D,- j(n)Tr(n)1/(g - 1)Mq(n)(q - 2)l(q -1)

+ (r'1 -

so that p\rl/_Mg(n)1/q

Mq(np)1/q log

(6-1)

p°

p

+

2rC1/q

Dr-1(n)1/gZr(n)1/q(q-1)Mq(n)(q-2)/q(q-1) 1

(a - 1)1 - 1/q

employing Holder's inequality, Lemma 70.1, and the inequality (a + b)1 /q al/q + b1/q. From this and (7.25) we deduce that r1/q

E(U) '<

+

(6-1) L(a)

2rC1/qy

w(n)

0o

(n)11 (n)11q(q-1)M (n)(q-2)lq(q-Iy r q na (a- 1)1-1/g Y*Dr _ 1

(7.27)

n=1

and we apply Holder's inequality with three exponents q, q(q - 1), (q -1)/(q -2) to the sum on the right, which therefore does not exceed 0o

n=I

w(n)

na

1/q

(*(fl)Y) oo

w(n)

1/q(q- 1)

L(a)(g-2)1(4-1)

no

The occ urrence of Dr-1(n) here suggests an induction on r. To make this work, we find that q needs to increase with r and we set q = l + r, where lc-7L+.

First variant - differential inequalities

3

149

Induction hypothesis. Let y > 1 be fixed, lo(y) be sufficiently large. For each r >, 1, the proposition 9(r, y) is that for every 1 > la(y) there exists a constant C(l, r, y) such that, for 1 < a 5 2, co ((

*Ar( d )

C(l, r, y)

Yw(d)

d=1

(7 . 28)

/6- 1)ry-r+ 1+r(r-1)/2(I+r)'

do

moreover we may take f 28

1)=Cr-1.4r{fl (56)S

C(l,r,

is
C(l,r,Y

)

S

r2

l0

)=Cr-1.4r'C

(

{l(r

1

1

- 1)!

(l+ r

)(r-1)(l+r

1) ,

(7.29)

(r-1)l 1)1 '

5

Y 1/ Y-

(Y

,

> 1).

The induction hypothesis is that 9(r - 1, y) holds. We notice that Y(1, y) is valid, because the left-hand side of (7.28) is

simply fl(l + yp-a) <,2y(a -

1)-y

(1
from Y(r - 1, y). From the definition (7.10) of D, we have ao

/

yw(n)

Y*Dr-1(n) n=1 n

u,(d)

ao

,
d

oo

yw(m)

Y* 1n m=1

a

C(l, r - 1, y)2y/(a -

1)ry-r+2+(r-1)(r- 2)/2(l+r-1)

and (7.27) becomes (remembering that q = l + r)

-L'(a) <

yrl/g

\(a-1)

L( a) +

2rC1/gyC(I,r-

1,y)119.2y/g+ry19(9-1)

(a-1)1+(ry-r+1)/(9-1)+r(r-1)/29(9-1)

1 /a) (g-2)l(9-1)

(7.30)

This differential inequality is the heart of the matter. The corresponding differential equation has solution X(a) = K(a - 1)-y, where y satisfies

y+1=i+.ry-r+1+ r(r-1) +q-2 q-1 2q(q-1) q-1y or

y=ry-r+1+r(r-1)/2q, and

K - (2ryC1/"C(l, r

-1,Y)1/92y/9+ry/9(9-1) )9-1

y _ yrl/g

We want to apply Lemma 70.2 with ao = 2, and we need L(2) < X(2) = K. Now y < ry, C >, 1, C(l, r - 1, y) > 4(r-1)y from (7.29). For q > r >, 2 this implies K > 2ry. From (7.7), 00

42)
n)

n

150

7

Hooley's A,. -functions - the critical interval

The lemma now yields L(a) < X(a) for 1 < o < 2, and together with (7.8) this gives (7.28), with

C(l,r,y)<2'-1K. We have r1/9 < 1 + min {3r(r - 1)/7q, 1.4 log r/q} for q > r >, 2. When y = 1, the first bound here yields ry/(y - ry1/9) < 14q/(r - 1) and

\ l+r-1 28q J1 C

so that q(r - 1, 1 ) = ( r , 1), with l0(1) = 1. When y > 1, we use the second bound for r1/9 and we have 2ry/(y - yr1/9) < 2ry/{(r -1)(y -1)1.4y log r/q} < 5y/(y - 1) if 7y log r/q < (3r - 5) (y - 1): this holds for every r >, 2 if l0(y) is large enough. Thus C(1,r,Y)2(5Y)r_ 1

y-1

5

Y

y-1

and 9(r, y) again follows. This completes the induction. Now let Zr(x, y) be the function defined by (6.12). We put a =1 + 1/log x in (7.28) to deduce that JBI(l+r)t+r-1(logx)r(r-1)/2(l+r)

Zr(x,Y)

(logx)rY r+l «r,Yt(5Y/(Y-

1))(r-1)!(log

x)r(r-1)/2(1+r)

(Y= 1), (Y> 1),

where B:= 2827/27! < e30. We choose l such that l + r = [(r loge x/log3 x)1/2] + I

I = [(r loge x/21og (5y/(y -1)))1/2]

(y = 1), (y > 1),

and apply Theorem 61 to obtain the result stated. 7.4 Second variant - double induction This version of the method still relies on the Fundamental Lemma, Theorem 73; and this being so the comparison of Mq(np) with M,(n)

remains. We now demand that p = P+(np) which alters the mechanism by which the extra prime is introduced (requiring another induction over a new parameter k). This suits values of y less than unity, and leads to a proof of Theorem 71.

We need some extra notation. Of course P+(n) and P-(n) denote, as usual, the greatest and least prime factors of n, and p,{n) the jth least. For squarefree n, we set nk =

IZ p;(n)

((o(n) > k),

n

(else).

sk

(7.31)

Second variant - double induction

4

Lemma 71.1.

151

Uniformly for lc-7L+ and z > 0, we have

1 (loge+(m))-z<
*

(7.32)

Y- m M=1 0)(M) =l

(where * still means that summation is restricted to squarefree numbers). Proof.

For fixed p, we have

0*

< 1(1og2 p + map (1-1)! 1

M=1

c)`- 1

w(m) =1

P+(m)= p

where c is an absolute constant. Hence the sum on the left of (7.32) is 1

Y-

(1- 1)! P

(loge p + C)'-' p(log p)=

and the result follows from the Prime Number Theorem and partial summation. Uniformly for 0 < y < 1,

Lemma 71.2.

kE7L+, and squarefree m for which

co(m) = k, we have w(n)

ao

k

Y* yn > mo(a - 1) v(log P+(m))-';

(7.33)

n=1 nk=m m(n)>- k

moreover the same sum is <<

YQ(a

-

1)-YP+(m)o-1(log P+(m))-y.

(7.34)

Proof. The integers n on the left take the form n = mh, where h is

squarefree and either h = 1 or P-(h) > P+(m). So the sum is y

yco(m)

m p>P+(m)

yk

m

P

P
By the mean value theorem, there exists pc(1,a) such that YPSP+(m)

P-a=

YP
P-'-(Or-1)

Y-

p-°logp,

P
so that the sum on the left on the one hand is < loge P+(m) + 0(1), which yields (7.33), and on the other hand is > 1092 P+(m) - (a - 1) log P+(m) + 0(1) (since p > 1), which yields (7.34).

152

7

Hooley's 0; functions - the critical interval

Proof of Theorem 71. For k, ge71+ and a > 1 we define yW()

ao

L(a; k, q) = * Mq(nk)1/a n=1

n

where nk is defined in (7.31) and * means that µ(n) # 0. We consider 1 and we apply (7.26),

L(a; k + 1, q). If w(n)>k, we have nk+1 = nkPk+ writing

Mq(nk+ 1) = rMq(nk) + Eq(nk, Pk+ 1)

where Eq denotes the sum of the off-diagonal terms in which max a, < q. Thus Mq(nk + 1)1 /9 < r l /9Mglnk//l l /9 + Eq(nk

, Pk + 1)1 /9

and, if we define Eq(nk, Pk+ 1) = 0 when co(n) < k, this holds for all n. Hence co

Y

Y E9(m, p)1/e n=1 y*

L(a; k + 1, q) ,
n

M=1 p>P+(m)

W(m)=k

W(n)

W(n)>_k+1 nk+ 1 =MP

We estimate the innermost sum on the right by Lemma 71.2, which yields

*

Yk+1

Eq(m,P)1/9

y

L(a; k + 1, q) - r1/9L(a; k, q) << M=1

W(m)=k

M6

P>P+(m)

P(Iogp)y (7.35)

By the Fundamental Lemma (7.11) we have 1(m)rk/(q -1) Mq(m)(q - 2)/(q -1),

Y Eq (m, p) log P < r9C. 29 -'D,. P P

and by the Prime Number Theorem, for z > 0, Y_ P> P+(m)

1(log P)-z<<(logP+(m))-Z P

We apply this with z = (qy + 1)/(q - 1). Holder's inequality, with exponents q, q/(q - 1), then implies that the inner sum in (7.35) is

« 2r C1/9D,_

1

(m)1/4 r k14(9-1)Mq(m)(9-2)/9(9-1) (loge + (m)) -Y-1/q

Y

whence, employing (7.33), we have

L(o;k+ 1, q)-r1/9L(a;k,q) 00

00

Y*

<<

M=1

rDr-1(m)1/9j.k/4(9-1)Mq(m)(9-2)/Q(4-1)(logp+(m))-1/q E* (n) n=1

cu(m) = k

n°

Wln)3k

Dr-1(nk) \ 1/9rk19(q-1)M

«Y

0k

n=1 o) (n)> k

(log P+(nk)

9

1(q-2)/9(9-1)YW(n)

(nk

no

(7.36)

4 Second variant - double induction

153

We apply Holder's inequality with exponents q, (q -1)/(q - 2), q(q - 1) to infer that this is << r

1 + k/9(9 - 1)

Rk(a)1 /9L(a; k, q)(9 - 2)/(q - 1)(a - 1) -Y/4(4 -1)

where w(n) 0* D r-1 (n) kY n°

Rk(c)._

n

OD

> n=1 logPk(n)

(ni

w(n)

o

m 1 loge+(m) ',

w(m)=k

w(n)-> k

no

w(n) -> k

nk=m

-7

Dr - 1 (m)

CO

= yk

Y*

(l+)Yk_l)_Y Y

11 M=1 m°logP+(m)p>P+(m) w(m)=k

Po

Do X M=1 Y* mg pm)(m)p
w(m) = k k

oo* Or-1(d)

X Y-

j=0 d=1

w(d)=j

y

fl cs(d)

d°

ao

1

(l+)P°

h-o

*

h

1

w(h)=k-j

loge+(dh)

(7.37)

on letting d run through the divisors of m and putting m = A. We put 1 + y = 2z, so that z < 1, and we apply the lower bound log P+(dh) >> (log P+(d))1-Z(logP+(h))Z (where we adopt the temporary convention that

logP+(1)= 1) to the denominator in the innermost sum, and note that, with this convention,

Y)

r7

(logP+(d))z-1

11P+(d) p

C1+ P JJ

/1+ Q\-1 <<

P

p-