Average order of an arithmetic function
In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average".
Let f be an arithmetic function. We say that an average order of f is g if
as x tends to infinity.
- An average order of d(n), the number of divisors of n, is log(n);
- An average order of σ(n), the sum of divisors of n, is nπ2 / 6;
- An average order of φ(n), Euler's totient function of n, is 6n / π2;
- An average order of r(n), the number of ways of expressing n as a sum of two squares, is π;
- An average order of ω(n), the number of distinct prime factors of n, is log log n;
- An average order of Ω(n), the number of prime factors of n, is log log n;
- The prime number theorem is equivalent to the statement that the von Mangoldt function Λ(n) has average order 1;
- An average order of μ(n), the Möbius function, is zero; this is again equivalent to the prime number theorem.
Better average order
This notion is best discussed through an example. From
( is the Euler-Mascheroni constant) and
we have the asymptotic relation
which suggests that the function is a better choice of average order for than simply .
- Divisor summatory function
- Normal order of an arithmetic function
- Extremal orders of an arithmetic function
- Hardy, G. H.; Wright, E. M. (2008) . An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. Zbl 1159.11001. Pp.347–360
- Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7. Zbl 0831.11001.