Difference between revisions of "Average order of an arithmetic function"
From Encyclopedia of Mathematics
m (typo) |
m (→References: isbn link) |
||
| (2 intermediate revisions by one other user not shown) | |||
| Line 9: | Line 9: | ||
holds as $x$ tends to infinity. | holds as $x$ tends to infinity. | ||
| − | It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[ | + | It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotone function|monotone]]. |
===Examples=== | ===Examples=== | ||
| Line 16: | Line 16: | ||
* The average order of $\phi(n)$, the [[Euler totient function]] of $n$, is $ \frac{6}{\pi^2} 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 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. | + | * The [[Prime number theorem|Prime Number Theorem]] is equivalent to the statement that the [[Mangoldt function|von Mangoldt function]] $\Lambda(n)$ has average order 1. |
===See also=== | ===See also=== | ||
| Line 23: | Line 23: | ||
===References=== | ===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.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 | + | * 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}} |
Latest revision as of 19:41, 17 November 2023
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=39076
Average order of an arithmetic function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Average_order_of_an_arithmetic_function&oldid=39076