Difference between revisions of "Normal order of an arithmetic function"
From Encyclopedia of Mathematics
(Start article: Normal order of an arithmetic function) |
(→References: isbn link) |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
| − | {{TEX|done}} | + | {{TEX|done}}{{MSC|11A}} |
| − | |||
| − | {{MSC|11A}} | ||
A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given [[arithmetic function]]. | A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given [[arithmetic function]]. | ||
| Line 12: | Line 10: | ||
hold for ''[[almost all]]'' $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity. | hold for ''[[almost all]]'' $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 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=== |
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$; | * The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$; | ||
| − | * The normal order of $\log d(n))$, where $d(n)$ is the [[number of divisors | + | * The normal order of $\log d(n))$, where $d(n)$ is the [[number of divisors|number of divisors function]] of $n$, is $\log 2 \log\log n$. |
| + | |||
| + | ===See also=== | ||
| + | * [[Asymptotics of arithmetic functions]] | ||
| + | * [[Average order of an arithmetic function]] | ||
| − | ==References== | + | ===References=== |
* G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92 | * G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92 | ||
| − | * G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, Oxford University Press (2008), pp. 473. ISBN 0-19-921986-5 | + | * G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, Oxford University Press (2008), pp. 473. {{ISBN|0-19-921986-5}} |
| − | * Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics '''46''' , Cambridge University Press (1995), pp. 299-324. ISBN 0-521-41261-7 | + | * Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics '''46''' , Cambridge University Press (1995), pp. 299-324. {{ISBN|0-521-41261-7}} |
Latest revision as of 08:12, 4 November 2023
2020 Mathematics Subject Classification: Primary: 11A [MSN][ZBL]
A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given arithmetic function.
Let $f$ be a function on the natural numbers. We say that the normal order of $f$ is $g$ if for every $\epsilon > 0$, the inequalities
$$
(1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n)
$$
hold for almost all $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.
It is conventional to assume that the approximating function $g$ is continuous and monotone.
Examples
- The Hardy–Ramanujan theorem: the normal order of $\omega(n)$, the number of distinct prime factors of $n$, is $\log\log n$;
- The normal order of $\log d(n))$, where $d(n)$ is the number of divisors function of $n$, is $\log 2 \log\log n$.
See also
References
- G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
- G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, Oxford University Press (2008), pp. 473. ISBN 0-19-921986-5
- Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics 46 , Cambridge University Press (1995), pp. 299-324. ISBN 0-521-41261-7
How to Cite This Entry:
Normal order of an arithmetic function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Normal_order_of_an_arithmetic_function&oldid=34707
Normal order of an arithmetic function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Normal_order_of_an_arithmetic_function&oldid=34707