A function *f* 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 Erdős

Here is a remarkable theorem due to Paul Erdős [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 Erdős

[1] Paul Erdős, “On the distribution function of additive functions,” Ann. of Math., Vol. 47 (1946), pp. 1–20.