Average order of an arithmetic function: Difference between revisions

Revision as of 11:03, 10 August 2008

Revision as of 15:22, 8 October 2008

Line 1:

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

Let ''f'' be a function on thean [[naturalarithmetic numberfunction]]s. We say that the ''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 assumechoose that thean approximating function ''g'' that is [[Continuous function|continuous]] and [[Monotonic function|monotone]].

==Examples==

Line 13:

* The average order of &sigma;(''n''), the sum of divisors of ''n'', is &pi;² / 6;

* The average order of &phi;(''n''), [[Euler's totient function]] of ''n'', is 6 / &pi;²;

* The average order of ''r''(''n''), the number of ways of expressing ''n'' as a [[sum of two squares]], is &pi; ;

* The [[Primeaverage Numberorder Theorem]]of is equivalent to&omega;(''n''), the statementnumber thatof thedistinct [[vonprime Mangoldt functionfactor]]s of &Lambda;(''n''), hasis averagelog orderlog 1.''n'';

* The average order of &Omega;(''n''), the number of [[prime factor]]s of ''n'', is log log ''n'';

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

==See also==