Additive function: Difference between revisions

Revision as of 19:37, 23 August 2021

Latest revision as of 01:40, 2 February 2025

(8 intermediate revisions by 5 users not shown)

Line 4:

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 applied to the product ''ab'' is the sum of the values 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. [https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1077746/ online]</ref>

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

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

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

Line 15:

Examples of arithmetic functions which are completely additive are:

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

* The '''multiplicity''' of a [[primePrime number|prime]] factor ''p'' in ''n'', that is the largest exponent ''m'' for which ''p^m'' [[divisorDivisor|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

Line 29:

::''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 41:

::Ω(2002) = 4

::Ω(2003) = 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.

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

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

::ω(4) = 1

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

:<math> \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}

:<math> \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>

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

:<math>\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>

:<math>\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>

:<math>\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>

:<math>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 \mathbb{R}</math> where the relations hold for <math>x \gg 1</math>:

:<math>G(z) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{z} e^{-t^2/2} dt.</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>

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 \mathbb{R}</math> where the relations hold for <math>x \gg 1</math>:

:<math>\#\{n \leq x: \omega(n) - \log\log x \leq z (\log\log x)^{1/2}\} \sim x G(z), </math>

:<math>\#\{p \leq x: \omega(p+1) - \log\log x \leq z (\log\log x)^{1/2}\} \sim \pi(x) G(z). </math>

== See also ==