Additive function: Difference between revisions

Revision as of 21:27, 6 February 2016

Latest revision as of 01:40, 2 February 2025

(23 intermediate revisions by 16 users not shown)

Line 1:

{{Short description|Function that can be written as a sum over prime factors}}

{{more footnotes|date=February 2013}}

{{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]] <math>''f''(''n'')</math> of the positive [[integer]] <math>variable ''n</math>'' such that whenever <math>''a</math> '' and <math>''b</math> '' are [[coprime]], the function ofapplied to the product ''ab'' is the sum of the functionsvalues 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. [httphttps://www.ncbi.nlm.nih.gov/pmc/articles/PMC1077746/ online]</ref>

:<math display=block>f(aba 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.

An additive function <math>f(n)</math> is said to be '''completely additive''' if <math>f(ab) = f(a) + f(b)</math> holds ''for all'' positive integers <math>a</math> and <math>b</math>, even when they are not co-prime. '''Totally additive''' is also used in this sense by analogy with [[totally multiplicative]] functions. If <math>f</math> is a completely additive function then <math>f(1) = 0</math>.

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

Line 13:

== Examples ==

ExampleExamples of arithmetic functions which are completely additive are:

* The restriction of the [[logarithmLogarithm|logarithmic function]] to <math>\mathbb{N}.</math>.

* The '''multiplicity''' of a [[Prime number|prime]] factor ''p'' in ''n'', that is the largest exponent ''m'' for which ''p^m'' [[Divisor|divides]] ''n''.

* {{anchor|Integer logarithm}} ''a''₀(''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''₀(4) = 2 + 2 = 4

* The '''multiplicity''' of a prime factor <math>p</math> in <math>n</math>, that is, the largest <math>m \in \mathbb{N}</math> for which <math>p^m | n</math> is true.

::''a''₀(20) = ''a''₀(2² · 5) = 2 + 2 + 5 = 9

::''a''₀(27) = 3 + 3 + 3 = 9

::''a''₀(144) = ''a''₀(2⁴ · 3²) = ''a''₀(2⁴) + ''a''₀(3²) = 8 + 6 = 14

::''a''₀(2000) = ''a''₀(2⁴ · 5³) = ''a''₀(2⁴) + ''a''₀(5³) = 8 + 15 = 23

::''a''₀(2003) = 2003

::''a''₀(54,032,858,972,279) = 1240658

::''a''₀(54,032,858,972,302) = 1780417

::''a''₀(20,802,650,704,327,415) = 1240681

* <math>a_0The function Ω(''n'')</math>, defined -as the sumtotal number of primes[[Prime dividingfactor#Omega <math>functions|prime factors]] of ''n</math>'', counting multiplicity,multiple sometimesfactors calledmultiple <math>\text{sopfr}(n)</math>times, thesometimes potency of <math>n</math> orcalled the integer"Big logarithmOmega of <math>n</math>function" {{OEIS|A001414A001222}}. For example:;

::<math>a_0Ω(41) = 20, +since 21 =has no prime 4</math>factors

::Ω(4) = 2

::<math>a_0(20) = a_0(2^2 \cdot 5) = 2 + 2+ 5 = 9</math>

::<math>a_0Ω(2716) = 3 + 3 + 3Ω(2·2·2·2) = 9</math>4

::Ω(20) = Ω(2·2·5) = 3

::<math>a_0(144) = a_0(2^4 \cdot 3^2) = a_0(2^4) + a_0(3^2) = 8 + 6 = 14</math>

::Ω(27) = Ω(3·3·3) = 3

::<math>a_0(2,000) = a_0(2^4 \cdot 5^3) = a_0(2^4) + a_0(5^3) = 8 + 15 = 23</math>

::Ω(144) = Ω(2⁴ · 3²) = Ω(2⁴) + Ω(3²) = 4 + 2 = 6

::<math>a_0(2,003) = 2,003</math>

::Ω(2000) = Ω(2⁴ · 5³) = Ω(2⁴) + Ω(5³) = 4 + 3 = 7

::<math>a_0(54,032,858,972,279) = 1,240,658</math>

::Ω(2001) = 3

::<math>a_0(54,032,858,972,302) = 1,780,417</math>

::Ω(2002) = 4

::<math>a_0(20,802,650,704,327,415) = 1,240,681</math>

::Ω(2003) = 1

::Ω(54,032,858,972,279) = Ω(11 ⋅ 1993² ⋅ 1236661) = 4

::Ω(54,032,858,972,302) = Ω(2 ⋅ 7² ⋅ 149 ⋅ 2081 ⋅ 1778171) = 6

::Ω(20,802,650,704,327,415) = Ω(5 ⋅ 7 ⋅ 11² ⋅ 1993² ⋅ 1236661) = 7.

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

* The [[prime factor#Omega functions|omega function]] <math>\Omega(n)</math>, defined as the total number of prime factors of <math>n</math>, counting multiplicity. It is sometimes called the "Big Omega function" {{OEIS|A001222}}. For example;

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

::<math>\Omega(1) = 0</math>, since 1 has no prime factors

::<math>\Omega(4) = 2</math>

::<math>\Omega(16) = \Omega(2 \cdot 2 \cdot 2 \cdot 2) = 4</math>

::<math>\Omega(20) = \Omega(2 \cdot 2 \cdot 5) = 3</math>

::<math>\Omega(27) = \Omega(3 \cdot 3 \cdot 3) = 3</math>

::<math>\Omega(144) = \Omega(2^4 \cdot 3^2) = \Omega(2^4) + \Omega(3^2) = 4 + 2 = 6</math>

::<math>\Omega(2,000) = \Omega(2^4 \cdot 5^3) = \Omega(2^4) + \Omega(5^3) = 4 + 3 = 7</math>

::<math>\Omega(2,001) = 3</math>

::<math>\Omega(2,002) = 4</math>

::<math>\Omega(2,003) = 1</math>

::<math>\Omega(54,032,858,972,279) = 3</math>

::<math>\Omega(54,032858972,302) = 6</math>

::<math>\Omega(20,802,650,704,327,415) = 7</math>

::ω(4) = 1

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

::ω(16) = ω(2⁴) = 1

::ω(20) = ω(2² · 5) = 2

::ω(27) = ω(3³) = 1

::ω(144) = ω(2⁴ · 3²) = ω(2⁴) + ω(3²) = 1 + 1 = 2

::ω(2000) = ω(2⁴ · 5³) = ω(2⁴) + ω(5³) = 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

* The other omega function, ''a''<mathsub>\omega(n)1</mathsub>,(''n'') defined as– the numbersum of the distinct primes dividing ''distinctn'', primesometimes factorscalled of <math>sopf(''n</math>'') {{OEIS|A001221A008472}}. For example:

::''a''<mathsub>1</sub>\omega(41) = 1</math>0

::''a''₁(4) = 2

::<math>\omega(16) = \omega(2^4) = 1</math>

::''a''<mathsub>1</sub>\omega(20) = \omega(2^2 \cdot+ 5) = 2</math>7

::''a''<mathsub>1</sub>\omega(27) = \omega(3^3) = 1</math>

::''a''<mathsub>1</sub>\omega(144) = \omega''a''₁(2^⁴ \cdot· 3^²) = \omega''a''₁(2^⁴) + \omega''a''₁(3^²) = 12 + 13 = 2</math>5

::''a''<mathsub>1</sub>\omega(2,0002000) = \omega''a''₁(2^⁴ \cdot· 5^³) = \omega''a''₁(2^⁴) + \omega''a''₁(5^³) = 12 + 15 = 2</math>7

::''a''<mathsub>1</sub>\omega(2,0012001) = 3</math>55

::''a''<mathsub>1</sub>\omega(2,0022002) = 4</math>33

::''a''<mathsub>1</sub>\omega(2,0032003) = 1</math>2003

::''a''<mathsub>1</sub>\omega(54,032,858,972,279) = 3</math>1238665

::''a''<mathsub>1</sub>\omega(54,032,858,972,302) = 5</math>1780410

::''a''<mathsub>1</sub>\omega(20,802,650,704,327,415) = 5</math>1238677

== Multiplicative functions ==

* <math>a_1(n)</math> - the sum of the distinct primes dividing <math>n</math>, sometimes called <math>\text{sopf}(n)</math> {{OEIS|A008472}}. For example:

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>a_1(1) = 0</math>

::<math display=block>a_1g(4a b) = 2g(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.

::<math>a_1(20) = 2 + 5 = 7</math>

::<math>a_1(27) = 3</math>

::<math>a_1(144) = a_1(2^4 \cdot 3^2) = a_1(2^4) + a_1(3^2) = 2 + 3 = 5</math>

::<math>a_1(2,000) = a_1(2^4 \cdot 5^3) = a_1(2^4) + a_1(5^3) = 2 + 5 = 7</math>

::<math>a_1(2,001) = 55</math>

::<math>a_1(2,002) = 33</math>

::<math>a_1(2,003) = 2003</math>

::<math>a_1(54,032,858,972,279) = 1,238,665</math>

::<math>a_1(54,032,858,972,302) = 1,780,410</math>

::<math>a_1(20,802,650,704,327,415) = 1,238,677</math>

== MultiplicativeSummatory functions ==

FromGiven anyan additive function <math>f(n)</math>, itlet isits easysummatory tofunction createbe adefined related [[multiplicative function]]by <math display="inline">g\mathcal{M}_f(nx)</math> i.e.:= with\sum_{n the\leq propertyx} that whenever <math>af(n)</math>. The average andof <math>bf</math> areis coprimegiven weexactly have: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>

:<math>g(ab) = g(a) \cdot g(b)</math>.

One such example is <math>g(n) = 2^{f(n)}</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 92 ⟶ 124:

== Further reading ==

{{refbeginRefbegin}}

* 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}}

{{Refend}}

{{Authority control}}

[[Category:Arithmetic functions]]

[[Category:Additive functions| ]]