Normal order of an arithmetic function

In number theory, a normal order of an arithmetic function is some simpler or better-understood function which "usually" takes the same or closely approximate values.

Let ƒ be a function on the natural numbers. We say that g is a normal order of ƒ if for every ε > 0, the inequalities

$(1-\varepsilon) g(n) \le f(n) \le (1+\varepsilon) g(n) \,$

hold for almost all n: that is, if 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 ω(n), the number of distinct prime factors of n, is log(log(n));
• The normal order of Ω(n), the number of prime factors of n counted with multiplicity, is log(log(n));
• The normal order of log(d(n)), where d(n) is the number of divisors of n, is log(2) log(log(n)).

See also

• Average order of an arithmetic function
• Divisor function
• Extremal orders of an arithmetic function

References

• Hardy, G.H.; Ramanujan, S. (1917). "The normal number of prime factors of a number n". Quart. J. Math. 48: 76–92. JFM 46.0262.03.
• Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (6th ed.). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.. p. 473
• Sándor, Jozsef; Crstici, Borislav (2004), Handbook of number theory II, Dordrecht: Kluwer Academic, p. 332, ISBN 1-4020-2546-7, Zbl 1079.11001
• Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Translated from the 2nd French edition by C.B.Thomas. Cambridge University Press. pp. 299–324. ISBN 0-521-41261-7. Zbl 0831.11001.

External links

• Weisstein, Eric W., "Normal Order", MathWorld.