24 1. Arithmetic Functions

Proof. We have

D(x) = 2

n≤

√

x

x

n

− [

√

x]2

= 2

n≤

√

x

x

n

+ O(1) − (

√

x +

O(1))2

= 2x(log(

√

x) + γ + O(1/

√

x)) − x +

O(x1/2)

= x log(x) + (2γ − 1)x +

O(x1/2)

by Proposition 1.7.

This estimate is due to J. P. G. Lejeune Dirichlet. It implies that the

arithmetic average of d(n) over the range 1 ≤ n ≤ x is asymptotic to log(x)

as x → +∞. One says that d(n) has average order log(x). From Proposition

1.15 it is easy to see that d(n) is sometimes larger than any fixed power of

log(n). But Proposition 1.16 implies that d(n) is only rarely so large. The

notation Δ(x) = D(x) − x log(x) − (2γ − 1)x is traditional for the error

term in the estimate in Proposition 1.16. The problem of bounding Δ(x) is

known as the Dirichlet divisor problem. More precisely, the divisor problem

is to find the least ϑ for which an estimate Δ(x) =

O(xϑ+ε)

holds for all

ε 0. The result just proved shows that ϑ ≤ 1/2. For x large and h rather

smaller than x, say h x/2, one obtains

1

h

x−hn≤x

d(n) =

D(x) − D(x − h)

h

=

x log(x) + (2γ − 1)x + Δ(x)

h

−

(x − h) log(x − h) + (2γ − 1)(x − h) + Δ(x − h)

h

= log(x) + 2γ + O

h

x

+ O

x1/2

h

by the estimate Δ(x) =

O(x1/2).

The error is a sum of two terms, one of

which dominates when h is large and the other when h is small. In such

situations one would usually try to choose the parameter optimally to obtain

a small error term overall. Minimizing h/x +

x1/2/h

over h for x fixed, one

sees that h =

x3/4

is an optimal choice. Thus

1

h

x−hn≤x

d(n) = log(x) + 2γ +

O(x−1/4),

h =

x3/4.

The asymptotic law of growth log(x) + 2γ for the local average of d(n) was

Dirichlet’s main application in his 1849 paper on the divisor problem. The