View source for Average order of an arithmetic function

{{TEX|done}}{{MSC|11A25}}

Some simpler or better-understood function which takes the same values "on average" as an [[arithmetic function]].

Let $f$, $g$ be functions on the [[natural number]]s.  We say that $f$ has average order $g$ if the [[asymptotic equality]]
$$
\sum_{n \le x} f(n) \sim \sum_{n \le x} g(n)
$$
holds as $x$ tends to infinity.

It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotonic function|monotone]].

===Examples===
* The average order of $d(n)$, the [[number of divisors]] of $n$, is $\log n$;
* The average order of $\sigma(n)$, the [[sum of divisors]] of $n$, is $ \frac{\pi^2}{6} n$;
* The average order of $\phi(n)$, the [[Euler totient function]] of $n$, is $ \frac{6}{\pi^2} n$;
* The average order of $r(n)$, the number of ways of expressing $n$ as a [[sum of two squares]], is $\pi$;
* The [[Prime number theorem|Prime Number Theorem]] is equivalent to the statement that the [[von Mangoldt function]] $\Lambda(n)$ has average order 1.

===See also===
* [[Asymptotics of arithmetic functions]]
* [[Normal order of an arithmetic function]]

===References===
* G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5 
* Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics '''46'''. Cambridge University Press. ISBN 0-521-41261-7