Average order of an arithmetic function

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

 \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n)

as x tends to infinity.

It is conventional to choose an approximating function g that is continuous and monotone. But even thus an average order is of course not unique.


  • 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[edit]

This notion is best discussed through an example. From

 \sum_{n\le x}d(n)=x\log x+(2\gamma-1)x+o(x)

(\gamma is the Euler-Mascheroni constant) and

 \sum_{n\le x}\log n=x\log x-x+O(\log x),

we have the asymptotic relation

\sum_{n\le x}(d(n)-(\log n+2\gamma))=o(x)\quad(x\rightarrow\infty),

which suggests that the function \log n+2\gamma is a better choice of average order for d(n) than simply \log n.

See also[edit]