In
number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, 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
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s. We say that ''g'' is a normal order of ''f'' if for every ''ε'' > 0, the inequalities
:
hold for ''
almost all
In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
'' ''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 and
monotone.
Examples
* The
Hardy–Ramanujan theorem: the normal order of ω(''n''), the number of distinct
prime factors of ''n'', is log(log(''n''));
* The normal order of Ω(''n''), the number of prime factors of ''n'' counted with
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
*
* . p. 473
*
*
External links
*
Arithmetic functions
{{numtheory-stub