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 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) = 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 = pα1···pαr 1 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.
Previous Page Next Page