Average order of an arithmetic function
From Encyclopedia of Mathematics
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
2020 Mathematics Subject Classification: Primary: 11A25 [MSN][ZBL]
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 numbers. 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 and 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 is equivalent to the statement that the von Mangoldt function $\Lambda(n)$ has average order 1.
See also
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
How to Cite This Entry:
Average order of an arithmetic function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Average_order_of_an_arithmetic_function&oldid=54520
Average order of an arithmetic function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Average_order_of_an_arithmetic_function&oldid=54520