Additive function: Difference between revisions

Revision as of 21:27, 6 February 2016

Revision as of 22:08, 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 <math>exponent ''m \in \mathbb{N}</math>'' for which ''p<mathsup>p^m | n</mathsup>'' isdivides true''n''.

* ''a''<mathsub>a_0(n)0</mathsub>(''n'') - 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''<mathsub>0</sub>a_0(4) = 2 + 2 = 4</math>

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

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

::''a''<mathsub>0</sub>a_0(144) = a_0''a''₀(2^⁴ \cdot· 3^²) = a_0''a''₀(2^⁴) + a_0''a''₀(3^²) = 8 + 6 = 14</math>

::''a''<mathsub>0</sub>a_0(2,000) = a_0''a''₀(2^⁴ \cdot· 5^³) = a_0''a''₀(2^⁴) + a_0''a''₀(5^³) = 8 + 15 = 23</math>

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

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

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

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

* 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 multiplicity.multiple Itfactors ismultiple times, 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^⁴ \cdot· 3^²) = \OmegaΩ(2^⁴) + \OmegaΩ(3^²) = 4 + 2 = 6</math>

::<math>\OmegaΩ(2,000) = \OmegaΩ(2^⁴ \cdot· 5^³) = \OmegaΩ(2^⁴) + \OmegaΩ(5^³) = 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,032858972032,858,972,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 ''distinctdifferent'' [[prime factor#Omega functions|prime factors]] of <math>''n</math>'' {{OEIS|A001221}}. For example:

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

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

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

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

::<math>\omegaω(144) = \omegaω(2^⁴ \cdot· 3^²) = \omegaω(2^⁴) + \omegaω(3^²) = 1 + 1 = 2</math>

::<math>\omegaω(2,000) = \omegaω(2^⁴ \cdot· 5^³) = \omegaω(2^⁴) + \omegaω(5^³) = 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''<mathsub>1</sub>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''<mathsub>1</sub>a_1(1) = 0</math>

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

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

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

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

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

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

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

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

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

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

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

== 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'')}</mathsup>.

== See also ==