Additive functions

A functionf from positive integers to real numbers is defined to be additive if for relatively prime numbers m and n,

f(mn) = f(m) + f(n).

The function f is called completely addititive if the above holds for all positive integers m and n, i.e. we drop the requirement that m and n are relatively prime.

Example: total prime factors

One example of an additive function is the function (n) defined to be the number of prime factors of n, counted with multiplicity. For example, (12) = 3 because 12 = 2 * 2 * 3. The numbers 10 and 63 are relatively prime, and

(630) = 5 = (10) + (63).

Example: distinct prime factors

Another example of an additive function is (n) defined to be the number of distinct prime factors of n, i.e.not counting with multiplicity. So, for example, (12) = 2.

This function is additive but not completely additive because, for example,

(20) = 2 (2) + (10) = 3

A theorem of Erds

Here is a remarkable theorem due to Paul Erds [1]. Suppose f is an additive function such that

f(n + 1) - f(n)

converges to zero as n goes to infinity. Then

f(n) = c log(n)

for some constant c. And since a multiple of a logarithm is a logarithm to a different base, we can restate the conclusion by simply saying f is a logarithm.

Logarithms are completely additive functions, so even though we only assumed f was additive, this combined with the limit condition proves that in fact f is completely additive.

Related posts

• Numbers typically don't have many prime factors
• Poisson distribution and prime numbers
• Six degrees of Paul Erds

[1] Paul Erds, On the distribution function of additive functions," Ann. of Math., Vol. 47 (1946), pp. 1-20.

The post Additive functions first appeared on John D. Cook.