1.6. The hyperbola method 21

Then

Φ(x) =

3

π2

x2

+ O(x log(x))

by the famous formula

∞

m=1

1

m2

=

π2

6

of Euler.

An Introduction to the Theory of Numbers by G. H. Hardy and E. M.

Wright contains interesting material on arithmetic functions and applica-

tions of elementary techniques in number theory. Another good source for

such material is Introduction to the Theory of Numbers by H. N. Shapiro.

1.6. The hyperbola method

Many arithmetic functions fluctuate rapidly and substantially, but we may

still want precise information about their growth. There are various ways

to approach such questions, differing not just in the methods used, but

more fundamentally in the kind of statement at which one aims. A positive

function g is a maximal order for an arithmetic function f if for any ε 0

the inequality |f(n)| ≤ (1 + ε)g(n) holds for all n suﬃciently large, while

the inequality |f(n)| ≤ (1 − ε)g(n) fails for infinitely many n no matter the

choice of ε 0. For the concept to be useful, the maximal order should be

some simple function that grows reasonably evenly. Otherwise we could just

choose g ≡ f and be done. Naturally there is also an analogous concept of

minimal orders for arithmetic functions, though for functions that fluctuate

greatly, minimal orders are often of little interest. An easy example showing

the strengths and weaknesses of this approach is the function

Ω(n) =

pα|n

1

that counts the prime divisors of n with multiplicity. To see how large Ω(n)

could be for given n, it is natural to look at integers that have many prime

factors for their size. Because repeated prime factors are counted, this leads

us to the powers of 2. Indeed the inequality

n = p1

α1

· · ·pr

αr

≥

2α1+···+αr

=

2Ω(n)

is strict unless n is a power of 2, and it shows that Ω(n) ≤ k for

2k

≤ n

2k+1.

So log(n)/ log(2) is a maximal order for Ω(n). The advantage here is

that the statement is valid for all n individually; the disadvantage is that

Ω(n) is actually very much smaller than the maximal order log(n)/ log(2)

for most n; see Proposition 2.7. The analogous question for the divisor func-

tion d(n) lies a little deeper. This function does not itself have a tractable

maximal order, but its logarithm does.