Turán–Kubilius inequality

The Turán–Kubilius inequality is a mathematical theorem in probabilistic number theory. It is useful for proving results about the normal order of an arithmetic function. The theorem was proved in a special case in 1934 by Pál Turán and generalized in 1956 and 1964 by Jonas Kubilius.

Statement of the theorem

This formulation is from Tenenbaum. Other formulations are in Narkiewicz and in Cojocaru & Murty.

Suppose f is an additive complex-valued arithmetic function, and write p for an arbitrary prime and ν for an arbitrary positive integer. Write

$A(x)=\sum _{p^{\nu }\leq x}f(p^{\nu })p^{-\nu }(1-p^{-1})$

and

$B(x)^{2}=\sum _{p^{\nu }\leq x}\left|f(p^{\nu })\right|^{2}p^{-\nu }.$

Then there is a function ε(x) that goes to zero when x goes to infinity, and such that for x ≥ 2 we have

${\frac {1}{x}}\sum _{n\leq x}|f(n)-A(x)|^{2}\leq (2+\varepsilon (x))B(x)^{2}.$

Applications of the theorem

Turán developed the inequality to create a simpler proof of the Hardy–Ramanujan theorem about the normal order of the number ω(n) of distinct prime divisors of an integer n. There is an exposition of Turán's proof in Hardy & Wright, §22.11. Tenenbaum gives a proof of the Hardy–Ramanujan theorem using the Turán–Kubilius inequality and states without proof several other applications.