Английская Википедия:Additive function
Шаблон:Short description Шаблон:About Шаблон:More footnotes
In number theory, an Шаблон:Anchoradditive function is an arithmetic function f(n) of the positive integer variable n such that whenever a and b are coprime, the function applied to the product ab is the sum of the values of the function applied to a and b:[1] <math display=block>f(a b) = f(a) + f(b).</math>
Completely additive
An additive function f(n) is said to be completely additive if <math>f(a b) = f(a) + f(b)</math> 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 <math>\N.</math>
- The multiplicity of a prime factor p in n, that is the largest exponent m for which pm divides n.
- a0(n) – the sum of primes dividing n counting multiplicity, sometimes called sopfr(n), the potency of n or the integer logarithm of n Шаблон:OEIS. 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" Шаблон:OEIS. For example;
- Ω(1) = 0, since 1 has no prime factors
- Ω(4) = 2
- Ω(16) = Ω(2·2·2·2) = 4
- Ω(20) = Ω(2·2·5) = 3
- Ω(27) = Ω(3·3·3) = 3
- Ω(144) = Ω(24 · 32) = Ω(24) + Ω(32) = 4 + 2 = 6
- Ω(2000) = Ω(24 · 53) = Ω(24) + Ω(53) = 4 + 3 = 7
- Ω(2001) = 3
- Ω(2002) = 4
- Ω(2003) = 1
- Ω(54,032,858,972,279) = Ω(11 ⋅ 19932 ⋅ 1236661) = 4 ;
- Ω(54,032,858,972,302) = Ω(2 ⋅ 72 ⋅ 149 ⋅ 2081 ⋅ 1778171) = 6
- Ω(20,802,650,704,327,415) = Ω(5 ⋅ 7 ⋅ 112 ⋅ 19932 ⋅ 1236661) = 7.
Examples of arithmetic functions which are additive but not completely additive are:
- ω(n), defined as the total number of distinct prime factors of n Шаблон:OEIS. For example:
- ω(4) = 1
- ω(16) = ω(24) = 1
- ω(20) = ω(22 · 5) = 2
- ω(27) = ω(33) = 1
- ω(144) = ω(24 · 32) = ω(24) + ω(32) = 1 + 1 = 2
- ω(2000) = ω(24 · 53) = ω(24) + ω(53) = 1 + 1 = 2
- ω(2001) = 3
- ω(2002) = 4
- ω(2003) = 1
- ω(54,032,858,972,279) = 3
- ω(54,032,858,972,302) = 5
- ω(20,802,650,704,327,415) = 5
- a1(n) – the sum of the distinct primes dividing n, sometimes called sopf(n) Шаблон:OEIS. 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 <math>f(n)</math> it is possible to create a related Шаблон:Em <math>g(n),</math> which is a function with the property that whenever <math>a</math> and <math>b</math> are coprime then: <math display=block>g(a b) = g(a) \times g(b).</math> One such example is <math>g(n) = 2^{f(n)}.</math>
Summatory functions
Given an additive function <math>f</math>, let its summatory function be defined by <math display="inline">\mathcal{M}_f(x) := \sum_{n \leq x} f(n)</math>. The average of <math>f</math> is given exactly as <math display=block>\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).</math>
The summatory functions over <math>f</math> can be expanded as <math>\mathcal{M}_f(x) = x E(x) + O(\sqrt{x} \cdot D(x))</math> where <math display=block>\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}</math>
The average of the function <math>f^2</math> is also expressed by these functions as <math display=block>\mathcal{M}_{f^2}(x) = x E^2(x) + O(x D^2(x)).</math>
There is always an absolute constant <math>C_f > 0</math> such that for all natural numbers <math>x \geq 1</math>, <math display=block>\sum_{n \leq x} |f(n) - E(x)|^2 \leq C_f \cdot x D^2(x).</math>
Let <math display=block>\nu(x; z) := \frac{1}{x} \#\!\left\{n \leq x: \frac{f(n)-A(x)}{B(x)} \leq z\right\}\!.</math>
Suppose that <math>f</math> is an additive function with <math>-1 \leq f(p^{\alpha}) = f(p) \leq 1</math> such that as <math>x \rightarrow \infty</math>, <math display=block>B(x) = \sum_{p \leq x} f^2(p) / p \rightarrow \infty.</math>
Then <math>\nu(x; z) \sim G(z)</math> where <math>G(z)</math> is the Gaussian distribution function <math display=block>G(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{z} e^{-t^2/2} dt.</math>
Examples of this result related to the prime omega function and the numbers of prime divisors of shifted primes include the following for fixed <math>z \in \R</math> where the relations hold for <math>x \gg 1</math>: <math display=block>\#\{n \leq x: \omega(n) - \log\log x \leq z (\log\log x)^{1/2}\} \sim x G(z),</math> <math display=block>\#\{p \leq x: \omega(p+1) - \log\log x \leq z (\log\log x)^{1/2}\} \sim \pi(x) G(z).</math>
See also
References
Further reading
- Janko Bračič, Kolobar aritmetičnih funkcij (Ring of arithmetical functions), (Obzornik mat, fiz. 49 (2002) 4, pp. 97–108) (MSC (2000) 11A25)
- Iwaniec and Kowalski, Analytic number theory, AMS (2004).
