Average order of an arithmetic function: Difference between revisions

Revision as of 08:51, 19 March 2013

Revision as of 12:44, 29 March 2013

Line 1:

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

Let ''f'' be an [[arithmetic function]]. We say that thean ''average order'' of ''f'' is ''g'' if

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

Line 7:

as ''x'' tends to infinity.

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

==Examples==

* TheAn average order of ''d''(''n''), the [[Divisor function|number of divisors]] of ''n'', is log(''n'');

* TheAn average order of σ(''n''), the sum of divisors of ''n'', is ''n''π² / 6;

* TheAn average order of φ(''n''), [[Euler's totient function]] of ''n'', is 6''n'' / π²;

* TheAn average order of ''r''(''n''), the number of ways of expressing ''n'' as a sum of two squares, is π;

* TheAn average order of ω(''n''), the number of distinct [[prime factor]]s of ''n'', is log log ''n'';

* TheAn 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;

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

==Better average order==

This notion is best discussed through an example. From

:<math> \sum_{n\le x}d(n)=x\log x+(2\gamma-1)x+o(x)</math>

(<math>\gamma</math> is the [[Euler-Mascheroni constant]]) and

:<math> \sum_{n\le x}\log n=x\log x-x+O(\log x),</math>

we have the asymptotic relation

:<math>\sum_{n\le x}(d(n)-(\log n+2\gamma))=o(x)\quad(x\rightarrow\infty),</math>

which suggests that the function <math>\log n+2\gamma</math> is a better choice of average order for <math>d(n)</math> than simply <math>\log n</math>.

==See also==