Additive function: Difference between revisions

Revision as of 03:31, 10 October 2013

Latest revision as of 01:40, 2 February 2025

(33 intermediate revisions by 23 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 [[mathematics]] the term '''additive function''' has two different definitions, depending on the specific field of application.

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

In [[algebra]] an '''additive function''' (or '''additive map''') is a function that preserves the addition operation:

:''<math display=block>f''(''x'' +a ''y''b) = ''f''(''x''a) + ''f''(''y''b).</math>

for any two elements ''x'' and ''y'' in the ___domain. For example, any [[linear map]] is additive. When the ___domain is the [[real numbers]], this is [[Cauchy's functional equation]].

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>

:''f''(''ab'') = ''f''(''a'') + ''f''(''b'').

The remainder of this article discusses number theoretic additive functions, using the second definition.

For a specific case of the first definition see [[additive polynomial]]. Note also that any [[homomorphism]] ''f'' between [[abelian group]]s is "additive" by the first definition.

== Completely additive ==

An additive function ''f''(''n'') is said to be '''completely additive''' if ''<math>f''(''ab''a b) = ''f''(''a'') + ''f''(''b'')</math> holds ''for all'' positive integers ''a'' and ''b'', even when they are not co-primecoprime. '''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 ''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 ==

ExampleExamples of arithmetic functions which are completely additive are:

* The restriction of the [[logarithmLogarithm|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^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:

* The '''multiplicity''' of a prime factor ''p'' in ''n'', that is the largest exponent ''m'' for which ''p^m'' divides ''n''.

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

::''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''₀(2,0002000) = ''a''₀(2⁴ · 5³) = ''a''₀(2⁴) + ''a''₀(5³) = 8 + 15 = 23

::''a''₀(2,0032003) = 2003

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

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

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

* The function Ω(''n''), defined as the total number of [[primePrime 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

Line 46 ⟶ 37:

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

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

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

::Ω(2,0012001) = 3

::Ω(2,0022002) = 4

::Ω(2,0032003) = 1

::Ω(54,032,858,972,279) = 3Ω(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.

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

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

::ω(4) = 1

Line 63 ⟶ 54:

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

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

::ω(2,0002000) = ω(2⁴ · 5³) = ω(2⁴) + ω(5³) = 1 + 1 = 2

::ω(2,0012001) = 3

::ω(2,0022002) = 4

::ω(2,0032003) = 1

::ω(54,032,858,972,279) = 3

::ω(54,032,858,972,302) = 5

::ω(20,802,650,704,327,415) = 5

* ''a''₁(''n'') -– the sum of the distinct primes dividing ''n'', sometimes called sopf(''n'') {{OEIS|A008472}}. For example:

::''a''₁(1) = 0

Line 78 ⟶ 69:

::''a''₁(27) = 3

::''a''₁(144) = ''a''₁(2⁴ · 3²) = ''a''₁(2⁴) + ''a''₁(3²) = 2 + 3 = 5

::''a''₁(2,0002000) = ''a''₁(2⁴ · 5³) = ''a''₁(2⁴) + ''a''₁(5³) = 2 + 5 = 7

::''a''₁(2,0012001) = 55

::''a''₁(2,0022002) = 33

::''a''₁(2,0032003) = 2003

::''a''₁(54,032,858,972,279) = 1238665

::''a''₁(54,032,858,972,302) = 1780410

Line 88 ⟶ 79:

== Multiplicative functions ==

From any additive function ''<math>f''(''n'')</math> it is easypossible to create a related {{em|[[multiplicative function]]}} ''<math>g''(''n''),</math> i.e.which is a function with the property that whenever ''<math>a''</math> and ''<math>b''</math> are coprime we havethen:

:''<math display=block>g''(''ab''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.

One such example is ''g''(''n'') = 2^''f''(''n'').

== 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 99 ⟶ 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| ]]