Normal order of magnitude

In number theory , the normal order of magnitude of a number theoretic function is a simpler or better understood function that “generally” takes on the same or approximate values.

definition

Let it be a function over the natural numbers. It is said that it is of the normal order of magnitude if for each the inequality ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \varepsilon >0}$

${\displaystyle |f(n)-g(n)|<\varepsilon \cdot g(n)}$

for "almost all" is fulfilled. This means here that the asymptotic density of the numbers that satisfy it is equal to 1: So if the number of these numbers in the interval is defined as the limit for each . ${\displaystyle n}$ ${\displaystyle a(N,\varepsilon )}$ ${\displaystyle n\in [1,N]}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \lim _{N\to \infty }{\frac {a(N,\varepsilon )}{N}}=1}$

Usually one uses approximation functions that are continuous and monotonic . ${\displaystyle g}$

Of course, not every number theoretic function is of normal magnitude. So has z. B. the function

${\displaystyle f(n):=0}$( even), ( odd) not a normal order of magnitude (but it has the average order of magnitude .) ${\displaystyle n}$ ${\displaystyle f(n):=2}$ ${\displaystyle n}$ ${\displaystyle f(n)\sim 1}$

Examples

Values ​​and normal order of magnitude of ω (n) and Ω (n)

Values ​​and normal order of magnitude of ln (d (n))

• The normal size of the order of , that is the number of (not necessarily distinct) primes from , as well as a number of distinct prime factors, is and is therefore equal to its average magnitude ( set of Hardy and Ramanujan ). Since the function grows very slowly, this means that e.g. For example, a number near (approximately the number of protons in the visible universe) is generally composed of 5 or 6 prime factors. ${\displaystyle \Omega (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \omega (n)}$ ${\displaystyle \ln \ln n}$
  ${\displaystyle \ln \ln n}$ ${\displaystyle 10^{80}}$
• The normal order of magnitude of the logarithm of the divisor number function is (Hardy / Ramanujan). That is, for anything , the inequality holds for almost all . ${\displaystyle \ln d(n)}$ ${\displaystyle \ln 2\cdot \ln \ln n}$ ${\displaystyle \varepsilon >0}$
  ${\displaystyle 2^{(1-\varepsilon )\ln \ln n}<d(n)<2^{(1+\varepsilon )\ln \ln n}}$ ${\displaystyle n}$

See also

• Average order of magnitude

Web links

• Eric W. Weisstein : Normal Order . In: MathWorld (English).

Individual evidence

1. ↑ E. Krätzel: Number theory . VEB Deutscher Verlag der Wissenschaften, Berlin 1981, p. 145 .
2. ↑ Godfrey Harold Hardy , EM Wright: Introduction to Number Theory . R. Oldenbourg, Munich 1958, p. 404 .