Turán sieve

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\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. But even thus an average order is of course not unique.

Examples

• 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π² / 6;
• An average order of φ(n), Euler's totient function of n, is 6n / π²;
• 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

$\sum _{n\leq x}d(n)=x\log x+(2\gamma -1)x+o(x)$

($\gamma$ is the Euler-Mascheroni constant) and

$\sum _{n\leq x}\log n=x\log x-x+O(\log x),$

we have the asymptotic relation

$\sum _{n\leq 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

• Divisor summatory function
• Normal order of an arithmetic function
• Extremal orders of an arithmetic function

References

• Template:Hardy and Wright Pp.347–360
• 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.
  
  My blog: http://www.primaboinca.com/view_profile.php?userid=5889534