Average order of an arithmetic function

In number theory, the 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 the average order of f is g if

${\displaystyle \sum _{n\leq x}f(n)\sim \sum _{n\leq x}g(n)}$

as x tends to infinity.

It is conventional to choose an approximating function g that is continuous and monotone.

Examples

• The average order of d(n), the number of divisors of n, is log(n);
• The average order of σ(n), the sum of divisors of n, is π² / 6;
• The average order of φ(n), Euler's totient function of n, is 6 / π²;
• The average order of r(n), the number of ways of expressing n as a sum of two squares, is π;
• The average order of ω(n), the number of distinct prime factors of n, is log log n;
• The 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.

See also

• Divisor summatory function
• Normal order of an arithmetic function

References

• G.H. Hardy (2008). An Introduction to the Theory of Numbers (6th ed. ed.). Oxford University Press. pp. 347–360. ISBN 0-19-921986-5. {{cite book}}: |edition= has extra text (help); Check |isbn= value: checksum (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
• Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. pp. 36–55. ISBN 0-521-41261-7.