Normal order of an arithmetic function explained

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 f be a function on the natural numbers. We say that g is a normal order of f 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
• Turán–Kubilius inequality

References

• G.H. . Hardy. G. H. Hardy. S. . Ramanujan . S. Ramanujan . The normal number of prime factors of a number n . Quart. J. Math. . 48 . 1917 . 76–92 . 46.0262.03 .
• . p. 473
  • Book: Tenenbaum, Gérald . Introduction to Analytic and Probabilistic Number Theory . Translated from the 2nd French edition by C.B.Thomas . Cambridge studies in advanced mathematics . 46 . . 1995 . 0-521-41261-7 . 0831.11001 . 299–324 .