Content deleted Content added
(30 intermediate revisions by 22 users not shown) | |||
Line 1:
{{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
▲In [[number theory]], an '''additive function''' is an [[arithmetic function]] ''f''(''n'') of the positive [[integer]] ''n'' such that whenever ''a'' and ''b'' are [[coprime]], the function of the product is the sum of the functions:<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. [http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1077746/ online]</ref>
== Completely additive ==
An additive function ''f''(''n'') is said to be '''completely additive''' if
▲An additive function ''f''(''n'') is said to be '''completely additive''' if ''f''(''ab'') = ''f''(''a'') + ''f''(''b'') holds ''for all'' positive integers ''a'' and ''b'', even when they are not co-prime. '''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.
Line 20 ⟶ 13:
== Examples ==
* 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 restriction of the [[logarithm|logarithmic function]] to '''N'''.
▲* The '''multiplicity''' of a prime factor ''p'' in ''n'', that is the largest exponent ''m'' for which ''p<sup>m</sup>'' divides ''n''.
▲* ''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>(
::''a''<sub>0</sub>(
::''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 [[
::Ω(1) = 0, since 1 has no prime factors
Line 48 ⟶ 37:
::Ω(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
::Ω(
::Ω(
::Ω(
::Ω(
::Ω(54,032,858,972,279) =
::Ω(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.
* ω(''n''), defined as the total number of
::ω(4) = 1
Line 65 ⟶ 54:
::ω(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
::ω(
::ω(
::ω(
::ω(
::ω(54,032,858,972,279) = 3
::ω(54,032,858,972,302) = 5
::ω(20,802,650,704,327,415) = 5
* ''a''<sub>1</sub>(''n'')
::''a''<sub>1</sub>(1) = 0
Line 80 ⟶ 69:
::''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>(
::''a''<sub>1</sub>(
::''a''<sub>1</sub>(
::''a''<sub>1</sub>(
::''a''<sub>1</sub>(54,032,858,972,279) = 1238665
::''a''<sub>1</sub>(54,032,858,972,302) = 1780410
Line 90 ⟶ 79:
== Multiplicative functions ==
From any additive function
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==
Line 101 ⟶ 124:
== Further reading ==
{{
* Janko Bračič, ''Kolobar aritmetičnih funkcij'' (''[[Ring (algebra)|Ring]] of arithmetical functions''), (Obzornik mat, fiz. '''49''' (2002) 4, pp. 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| ]]
|