Average order of an arithmetic function: Difference between revisions

Revision as of 16:48, 13 August 2015

Revision as of 20:02, 13 August 2015

Line 1:

In [[number theory]], an '''average order of an arithmetic function''' is some simpler or better-understood function which takes the same values "on average".

Let {{math|''f''}} be an [[arithmetic function]]. We say that an ''average order'' of {{math|''f''}} is {{math|''g''}} if

:<math> \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) </math>

as {{math|''x''}} tends to infinity.

It is conventional to choose an approximating function {{math|''g''}} that is [[Continuous function|continuous]] and [[Monotonic function|monotone]]. But even so an average order is of course not unique.

In cases where the limit

Line 13:

: <math>\lim_{N\rightarrow \infty}\frac{1}{N}\sum_{n \le N} f(n)=c</math>

exists, it is said that {{math|''f''}} has a '''mean value''' ('''average value''') {{math|''c''}}.

==Examples==<!-- &#x200A; is hair space (&hairsp; doesn't work). -->

==Examples==

* An average order of {{math|''d''&#x200A;(''n'')}}, the [[Divisor function|number of divisors]] of {{math|''n''}}, is {{math|log( ''n'')}};

* An average order of {{math|''σ''&#x200A;(''n'')}}, the [[Divisor function|sum of divisors]] of {{math|''n''}}, is {{math|''n''&#x200A;π² {{thinsp|/ }}6}};

* An average order of {{math|''φ''&#x200A;(''n'')}}, [[Euler's totient function]] of {{math|''n''}}, is {{math|6&#x200A;''n'' {{thinsp|/ }}π²}};

* An average order of {{math|''r''&#x200A;(''n'')}}, the number of ways of expressing {{math|''n''}} as a sum of two squares, is {{math|π&#x200A;''n''}};

* The average order of representations of a natural number as a sum of three squares is {{math|4π&#x200A;''n''{{thinsp|/}}3}};

* The average ordernumber of representationsdecompositions of a natural number asinto a sum of threeone squaresor more consecutive prime numbers is 4πn/3{{math|''n'' log&#x200A;2}};

* An average order of Ω{{math|''ω''&#x200A;(''n'')}}, the [[Prime factors|number of distinct prime factors]] of {{math|''n''}}, is {{math|log &#x200A;log ''n''}};

* TheAn average numberorder of decompositions{{math|Ω&#x200A;(''n'')}}, ofthe a natural[[Prime factors|number intoof aprime sumfactors]] of one or{{math|''n''}}, more consecutive primeis numbers is{{math|log&#x200A;log ''nlog2n''.}};

* The [[prime number theorem]] is equivalent to the statement that the [[von Mangoldt function]] {{math|Λ&#x200A;(''n'')}} has average order 1;

* An average order of ω{{math|''μ''&#x200A;(''n'')}}, the number of distinct [[primeMöbius factorfunction]]s, ofis ''n'',zero; this is logagain logequivalent ''n'';to the [[prime number theorem]].

* An average order of Ω(''n''), the number of prime factors of ''n'', is log log ''n'';

* The [[prime number theorem]] is equivalent to the statement that the [[von Mangoldt function]] Λ(''n'') has average order 1;

* An average order of μ(''n''), the [[Möbius function]], is zero; this is again equivalent to the [[prime number theorem]].

==Calculating mean values using Dirichlet series==