View source for Additive function

{{Short description|Function that can be written as a sum over prime factors}}
{{About||the [[Abstract algebra|algebra]]ic meaning|Additive map}}
{{more footnotes|date=February 2013}}

In [[number theory]], an '''{{anchor|definition-additive_function-number_theory}}additive 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'':<ref name="Erdos1939">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]</ref>
<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 [[Logarithm|logarithmic function]] to <math>\N.</math>
* The '''multiplicity''' of a [[Prime number|prime]] factor ''p'' in ''n'', that is the largest exponent ''m'' for which ''p<sup>m</sup>'' [[Divisor|divides]] ''n''.
* {{anchor|Integer logarithm}} ''a''<sub>0</sub>(''n'') – the sum of primes dividing ''n'' counting multiplicity, sometimes called sopfr(''n''), the potency of ''n'' or the '''integer logarithm''' of ''n'' {{OEIS|A001414}}. For example:

::''a''<sub>0</sub>(4) = 2 + 2 = 4
::''a''<sub>0</sub>(20) =  ''a''<sub>0</sub>(2<sup>2</sup> · 5) = 2 + 2 + 5 = 9
::''a''<sub>0</sub>(27) = 3 + 3 + 3 = 9
::''a''<sub>0</sub>(144) = ''a''<sub>0</sub>(2<sup>4</sup> · 3<sup>2</sup>) = ''a''<sub>0</sub>(2<sup>4</sup>) + ''a''<sub>0</sub>(3<sup>2</sup>) = 8 + 6 = 14
::''a''<sub>0</sub>(2000) = ''a''<sub>0</sub>(2<sup>4</sup> · 5<sup>3</sup>) = ''a''<sub>0</sub>(2<sup>4</sup>) + ''a''<sub>0</sub>(5<sup>3</sup>) = 8 + 15 = 23
::''a''<sub>0</sub>(2003) = 2003
::''a''<sub>0</sub>(54,032,858,972,279) = 1240658
::''a''<sub>0</sub>(54,032,858,972,302) = 1780417
::''a''<sub>0</sub>(20,802,650,704,327,415) = 1240681

* The function Ω(''n''), defined as the total number of [[Prime factor#Omega functions|prime factors]] of ''n'', counting multiple factors multiple times, sometimes called the "Big Omega function" {{OEIS|A001222}}. 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) = Ω(2<sup>4</sup> · 3<sup>2</sup>) = Ω(2<sup>4</sup>) + Ω(3<sup>2</sup>) = 4 + 2 = 6
::Ω(2000) = Ω(2<sup>4</sup> · 5<sup>3</sup>) = Ω(2<sup>4</sup>) + Ω(5<sup>3</sup>) = 4 + 3 = 7
::Ω(2001) = 3
::Ω(2002) = 4
::Ω(2003) = 1
::Ω(54,032,858,972,279) = Ω(11 ⋅ 1993<sup>2</sup> ⋅ 1236661) = 4
::Ω(54,032,858,972,302) = Ω(2 ⋅ 7<sup>2</sup> ⋅ 149 ⋅ 2081 ⋅ 1778171) = 6 
::Ω(20,802,650,704,327,415) = Ω(5 ⋅ 7 ⋅ 11<sup>2</sup> ⋅ 1993<sup>2</sup> ⋅ 1236661) = 7.

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

* ω(''n''), defined as the total number of distinct [[Prime factor#Omega functions|prime factors]] of ''n'' {{OEIS|A001221}}. For example:

::ω(4) = 1
::ω(16) = ω(2<sup>4</sup>) = 1
::ω(20) = ω(2<sup>2</sup> · 5) = 2
::ω(27) = ω(3<sup>3</sup>) = 1
::ω(144) = ω(2<sup>4</sup> · 3<sup>2</sup>) = ω(2<sup>4</sup>) + ω(3<sup>2</sup>) = 1 + 1 = 2
::ω(2000) = ω(2<sup>4</sup> · 5<sup>3</sup>) = ω(2<sup>4</sup>) + ω(5<sup>3</sup>) = 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

* ''a''<sub>1</sub>(''n'') – the sum of the distinct primes dividing ''n'', sometimes called sopf(''n'') {{OEIS|A008472}}. For example:

::''a''<sub>1</sub>(1) = 0
::''a''<sub>1</sub>(4) = 2
::''a''<sub>1</sub>(20) = 2 + 5 = 7
::''a''<sub>1</sub>(27) = 3
::''a''<sub>1</sub>(144) = ''a''<sub>1</sub>(2<sup>4</sup> · 3<sup>2</sup>) = ''a''<sub>1</sub>(2<sup>4</sup>) + ''a''<sub>1</sub>(3<sup>2</sup>) = 2 + 3 = 5
::''a''<sub>1</sub>(2000) = ''a''<sub>1</sub>(2<sup>4</sup> · 5<sup>3</sup>) = ''a''<sub>1</sub>(2<sup>4</sup>) + ''a''<sub>1</sub>(5<sup>3</sup>) = 2 + 5 = 7
::''a''<sub>1</sub>(2001) = 55
::''a''<sub>1</sub>(2002) = 33
::''a''<sub>1</sub>(2003) = 2003
::''a''<sub>1</sub>(54,032,858,972,279) = 1238665
::''a''<sub>1</sub>(54,032,858,972,302) = 1780410
::''a''<sub>1</sub>(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|[[multiplicative function]]}} <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> Likewise if <math>f(n)</math> is completely additive, then <math>g(n) = 2^{f(n)} </math> is completely multiplicative. More generally, we could consider the function <math>g(n) = c^{f(n)} </math>, where <math>c</math> is a nonzero real constant.

== 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 number]]s <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 [[normal distribution|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 ==
* [[Sigma additivity]]
* [[Prime omega function]]
* [[Multiplicative function]]
* [[Arithmetic function]]

==References==
{{Reflist}}

== Further reading ==
{{Refbegin}}
* Janko Bračič, ''Kolobar aritmetičnih funkcij'' (''[[Ring (algebra)|Ring]] of arithmetical functions''), (Obzornik mat, fiz. '''49''' (2002) 4, pp.&nbsp;97–108) <span style="color:darkblue;"> (MSC (2000) 11A25) </span>
* Iwaniec and Kowalski, ''Analytic number theory'', AMS (2004). 
{{Refend}}

{{Authority control}}

[[Category:Arithmetic functions]]
[[Category:Additive functions| ]]