1.6. The hyperbola method 21
Φ(x) =
+ O(x log(x))
by the famous formula

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 sufficiently 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) =
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
· · ·pr

is strict unless n is a power of 2, and it shows that Ω(n) k for
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.
Previous Page Next Page