Additive function

Completely additive

An additive function f(n) is said to be completely additive if f(a b) = f(a) + f(b) holds for all positive integers a and b, even when they are not coprime. Totally additive is also used in this sense by analogy with totally multiplicative functions. If f is a completely additive function then f(1) = 0.

Every completely additive function is additive, but not vice versa.

Examples

Examples of arithmetic functions which are completely additive are:

• The restriction of the logarithmic function to \N.
• The multiplicity of a prime factor p in n, that is the largest exponent m for which pm divides n.
• Integer logarithm a0(n) – the sum of primes dividing n counting multiplicity, sometimes called sopfr(n), the potency of n or the integer logarithm of n . For example:

::a0(4) = 2 + 2 = 4 ::a0(20) = a0(22 · 5) = 2 + 2 + 5 = 9 ::a0(27) = 3 + 3 + 3 = 9 ::a0(144) = a0(24 · 32) = a0(24) + a0(32) = 8 + 6 = 14 ::a0(2000) = a0(24 · 53) = a0(24) + a0(53) = 8 + 15 = 23 ::a0(2003) = 2003 ::a0(54,032,858,972,279) = 1240658 ::a0(54,032,858,972,302) = 1780417 ::a0(20,802,650,704,327,415) = 1240681

• The function Ω(n), defined as the total number of prime factors of n, counting multiple factors multiple times, sometimes called the "Big Omega function" . For example;

Examples of arithmetic functions which are additive but not completely additive are:

• ω(n), defined as the total number of distinct prime factors of n . For example:

• a1(n) – the sum of the distinct primes dividing n, sometimes called sopf(n) . For example:

::a1(1) = 0 ::a1(4) = 2 ::a1(20) = 2 + 5 = 7 ::a1(27) = 3 ::a1(144) = a1(24 · 32) = a1(24) + a1(32) = 2 + 3 = 5 ::a1(2000) = a1(24 · 53) = a1(24) + a1(53) = 2 + 5 = 7 ::a1(2001) = 55 ::a1(2002) = 33 ::a1(2003) = 2003 ::a1(54,032,858,972,279) = 1238665 ::a1(54,032,858,972,302) = 1780410 ::a1(20,802,650,704,327,415) = 1238677

Multiplicative functions

From any additive function f(n) it is possible to create a related multiplicative function g(n), which is a function with the property that whenever a and b are coprime then: g(a b) = g(a) \times g(b). One such example is g(n) = 2^{f(n)}. Likewise if f(n) is completely additive, then g(n) = 2^{f(n)} is completely multiplicative. More generally, we could consider the function g(n) = c^{f(n)} , where c is a nonzero real constant.

Summatory functions

Given an additive function f, let its summatory function be defined by \mathcal{M}f(x) := \sum{n \leq x} f(n). The average of f is given exactly as \mathcal{M}f(x) = \sum{p^{\alpha} \leq x} f(p^{\alpha}) \left(\left\lfloor \frac{x}{p^{\alpha}} \right\rfloor - \left\lfloor \frac{x}{p^{\alpha+1}} \right\rfloor\right).

The summatory functions over f can be expanded as \mathcal{M}f(x) = x E(x) + O(\sqrt{x} \cdot D(x)) where \begin{align} E(x) & = \sum{p^{\alpha} \leq x} f(p^{\alpha}) p^{-\alpha} (1-p^{-1}) \ D^2(x) & = \sum_{p^{\alpha} \leq x} |f(p^{\alpha})|^2 p^{-\alpha}. \end{align}

The average of the function f^2 is also expressed by these functions as \mathcal{M}_{f^2}(x) = x E^2(x) + O(x D^2(x)).

There is always an absolute constant C_f 0 such that for all natural numbers x \geq 1, \sum_{n \leq x} |f(n) - E(x)|^2 \leq C_f \cdot x D^2(x).

Let \nu(x; z) := \frac{1}{x} #!\left{n \leq x: \frac{f(n)-A(x)}{B(x)} \leq z\right}!.

Suppose that f is an additive function with -1 \leq f(p^{\alpha}) = f(p) \leq 1 such that as x \rightarrow \infty, B(x) = \sum_{p \leq x} f^2(p) / p \rightarrow \infty.

Then \nu(x; z) \sim G(z) where G(z) is the Gaussian distribution function G(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{z} e^{-t^2/2} dt.

Examples of this result related to the prime omega function and the numbers of prime divisors of shifted primes include the following for fixed z \in \R where the relations hold for x \gg 1: #{n \leq x: \omega(n) - \log\log x \leq z (\log\log x)^{1/2}} \sim x G(z), #{p \leq x: \omega(p+1) - \log\log x \leq z (\log\log x)^{1/2}} \sim \pi(x) G(z).

References

References

1. Erdös, P., and M. Kac. On the Gaussian Law of Errors in the Theory of Additive Functions. Proc Natl Acad Sci USA. 1939 April; 25(4): 206–207. [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1077746/ online]