Additive function: Difference between revisions

Revision as of 22:43, 5 April 2015

Revision as of 21:27, 6 February 2016

Line 2:

{{About||the [[Abstract algebra|algebra]]ic meaning|Additive map}}

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>n''</math> such that whenever ''<math>a''</math> and ''<math>b''</math> 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>

:''<math>f''(''ab'') = ''f''(''a'') + ''f''(''b'')</math>.

== Completely additive ==

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 15:

Example of arithmetic functions which are completely additive are:

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

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

* ''a''<sub>0</submath>a_0(''n'')</math> - the sum of primes dividing ''<math>n''</math>, counting multiplicity, sometimes called <math>\text{sopfr}(''n'')</math>, the potency of ''<math>n''</math> or the integer logarithm of ''<math>n''</math> {{OEIS|A001414}}. For example:

::''a''<sub>0</submath>a_0(4) = 2 + 2 = 4</math>

::''a''<sub>0</submath>a_0(20) = ''a''₀a_0(2^{^2} ·\cdot 5) = 2 + 2+ 5 = 9</math>

::''a''<sub>0</submath>a_0(27) = 3 + 3 + 3 = 9</math>

::''a''<sub>0</submath>a_0(144) = ''a''₀a_0(2^{^4} ·\cdot 3^{^2}) = ''a''₀a_0(2^{^4}) + ''a''₀a_0(3^{^2}) = 8 + 6 = 14</math>

::''a''<sub>0</submath>a_0(2,000) = ''a''₀a_0(2^{^4} ·\cdot 5^{^3}) = ''a''₀a_0(2^{^4}) + ''a''₀a_0(5^{^3}) = 8 + 15 = 23</math>

::''a''<sub>0</submath>a_0(2,003) = 20032,003</math>

::''a''<sub>0</submath>a_0(54,032,858,972,279) = 12406581,240,658</math>

::''a''<sub>0</submath>a_0(54,032,858,972,302) = 17804171,780,417</math>

::''a''<sub>0</submath>a_0(20,802,650,704,327,415) = 12406811,240,681</math>

* The [[prime factor#Omega functions|omega function]] Ω<math>\Omega(''n'')</math>, defined as the total number of [[prime factor#Omega functions|prime factors]] of ''<math>n''</math>, counting multiplemultiplicity. factorsIt multiple times,is sometimes called the "Big Omega function" {{OEIS|A001222}}. 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,032,858,972032858972,302) = 6</math>

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

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

* ωThe other omega function, <math>\omega(''n'')</math>, defined as the total number of ''differentdistinct'' [[prime factor#Omega functions|prime factors]] of ''<math>n''</math> {{OEIS|A001221}}. For example:

::ω<math>\omega(4) = 1</math>

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

::ω<math>\omega(20) = ω\omega(2^{^2} ·\cdot 5) = 2</math>

::ω<math>\omega(27) = ω\omega(3^{^3}) = 1</math>

::ω<math>\omega(144) = ω\omega(2^{^4} ·\cdot 3^{^2}) = ω\omega(2^{^4}) + ω\omega(3^{^2}) = 1 + 1 = 2</math>

::ω<math>\omega(2,000) = ω\omega(2^{^4} ·\cdot 5^{^3}) = ω\omega(2^{^4}) + ω\omega(5^{^3}) = 1 + 1 = 2</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,032,858,972,302) = 5</math>

::ω<math>\omega(20,802,650,704,327,415) = 5</math>

* ''a''<sub>1</submath>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:

::''a''<sub>1</submath>a_1(1) = 0</math>

::''a''<sub>1</submath>a_1(4) = 2</math>

::''a''<sub>1</submath>a_1(20) = 2 + 5 = 7</math>

::''a''<sub>1</submath>a_1(27) = 3</math>

::''a''<sub>1</submath>a_1(144) = ''a''₁a_1(2^{^4} ·\cdot 3^{^2}) = ''a''₁a_1(2^{^4}) + ''a''₁a_1(3^{^2}) = 2 + 3 = 5</math>

::''a''<sub>1</submath>a_1(2,000) = ''a''₁a_1(2^{^4} ·\cdot 5^{^3}) = ''a''₁a_1(2^{^4}) + ''a''₁a_1(5^{^3}) = 2 + 5 = 7</math>

::''a''<sub>1</submath>a_1(2,001) = 55</math>

::''a''<sub>1</submath>a_1(2,002) = 33</math>

::''a''<sub>1</submath>a_1(2,003) = 2003</math>

::''a''<sub>1</submath>a_1(54,032,858,972,279) = 12386651,238,665</math>

::''a''<sub>1</submath>a_1(54,032,858,972,302) = 17804101,780,410</math>

::''a''<sub>1</submath>a_1(20,802,650,704,327,415) = 12386771,238,677</math>

== Multiplicative functions ==

From any additive function ''<math>f''(''n'')</math> it is easy to create a related [[multiplicative function]] ''<math>g''(''n'')</math> i.e. with the property that whenever ''<math>a''</math> and ''<math>b''</math> are coprime we have:

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

One such example is ''<math>g''(''n'') = 2<sup>''^{f''(''n'')}</supmath>.

== See also ==