imported>The Anome: Importing Wikidata short description: "Type of asymptotic behavior useful in number theory"

2024-08-25T22:04:28Z

Importing Wikidata short description: "Type of asymptotic behavior useful in number theory"

New page

{{Short description|Type of asymptotic behavior useful in number theory}}
In [[number theory]], a '''normal order of an arithmetic function''' is some simpler or better-understood function which "usually" takes the same or closely approximate values.

Let ''f'' be a function on the [[natural number]]s. We say that ''g'' is a '''normal order''' of ''f'' if for every ''ε'' > 0, the inequalities

:<math> (1-\varepsilon) g(n) \le f(n) \le (1+\varepsilon) g(n) </math>

hold for ''[[Asymptotically almost surely|almost all]]'' ''n'': that is, if the proportion of ''n'' ≤ ''x'' for which this does not hold tends to 0 as ''x'' tends to infinity.

It is conventional to assume that the approximating function ''g'' is [[Continuous function|continuous]] and [[Monotonic function|monotone]].

==Examples==
* The [[Hardy–Ramanujan theorem]]: the normal order of ω(''n''), the number of distinct [[prime factor]]s of ''n'', is log(log(''n''));
* The normal order of Ω(''n''), the number of prime factors of ''n'' counted with [[multiplicity (mathematics)|multiplicity]], is log(log(''n''));
* The normal order of log(''d''(''n'')), where ''d''(''n'') is the number of divisors of ''n'', is log(2) log(log(''n'')).

==See also==
* [[Average order of an arithmetic function]]
* [[Divisor function]]
* [[Extremal orders of an arithmetic function]]
* [[Turán–Kubilius inequality]]

==References==
* {{cite journal| first1=G.H. | last1=Hardy| author1-link=G. H. Hardy| first2=S. | last2=Ramanujan | author2-link=S. Ramanujan |title=The normal number of prime factors of a number ''n'' |journal= Quart. J. Math. | volume= 48 | year=1917 | pages= 76–92 | url=http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper35/page1.htm | jfm=46.0262.03 }}
* {{Hardy and Wright | citation=cite book | page=473 }}. p. 473
* {{citation | last1=Sándor | first1=Jozsef | last2=Crstici | first2=Borislav | title=Handbook of number theory II | location=Dordrecht | publisher=Kluwer Academic | year=2004 | isbn=1-4020-2546-7 | page=332 | zbl=1079.11001 }}
* {{cite book | title=Introduction to Analytic and Probabilistic Number Theory | first=Gérald | last=Tenenbaum | others=Translated from the 2nd French edition by C.B.Thomas | series=Cambridge studies in advanced mathematics | volume=46 | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-41261-7 | zbl=0831.11001 | pages=299–324 }}

==External links==
* {{MathWorld|urlname=NormalOrder|title=Normal Order}}

[[Category:Arithmetic functions]]

{{numtheory-stub}}

Normal order of an arithmetic function - Revision history

imported>The Anome: Importing Wikidata short description: "Type of asymptotic behavior useful in number theory"