In
mathematics, specifically in
number theory, the extremal orders of an arithmetic function are best possible bounds of the given
arithmetic function. Specifically, if f(n) is an arithmetic function and m(n) is a non-decreasing
function that is ultimately positive and
we say that m is a minimal order for f. Similarly if M(n) is a non-decreasing function that is ultimately positive and
The subject was first studied systematically by
Ramanujan starting in 1915.[1]: 87
Examples
For the
sum-of-divisors function σ(n) we have the trivial result because always σ(n) ≥ n and for
primes σ(p) = p + 1. We also have proved by
Gronwall in 1913.[1]: 86 [2]: Theorem 323 [3] Therefore n is a minimal order and e−γn ln ln n is a maximal order for σ(n).
For the
Euler totient φ(n) we have the trivial result because always φ(n) ≤ n and for primes φ(p) = p − 1. We also have proven by
Landau in 1903.[1]: 84 [2]: Theorem 328
For the
number of divisors function d(n) we have the trivial lower bound 2 ≤ d(n), in which equality occurs when n is prime, so 2 is a minimal order. For ln d(n) we have a maximal order ln 2 ln n / ln ln n, proved by Wigert in 1907.[1]: 82 [2]: Theorem 317
For the number of distinct
prime factors ω(n) we have a trivial lower bound 1 ≤ ω(n), in which equality occurs when n is a
prime power. A maximal order for ω(n) is ln n / ln ln n.[1]: 83
For the number of prime factors counted with multiplicity Ω(n) we have a trivial lower bound 1 ≤ Ω(n), in which equality occurs when n is prime. A maximal order for Ω(n) is ln n / ln 2[1]: 83
It is
conjectured that the
Mertens function, or summatory function of the
Möbius function, satisfies though to date this limit superior has only been shown to be larger than a small constant. This statement is compared with the disproof of
Mertens conjecture given by Odlyzko and te Riele in their several decades old breakthrough paper Disproof of the Mertens Conjecture. In contrast, we note that while extensive computational evidence suggests that the above conjecture is true, i.e., along some increasing sequence of tending to infinity the average order of grows unbounded, that the
Riemann hypothesis is equivalent to the limit being true for all (sufficiently small) .
^
abcdefg
Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press.
ISBN0-521-41261-7.
In
mathematics, specifically in
number theory, the extremal orders of an arithmetic function are best possible bounds of the given
arithmetic function. Specifically, if f(n) is an arithmetic function and m(n) is a non-decreasing
function that is ultimately positive and
we say that m is a minimal order for f. Similarly if M(n) is a non-decreasing function that is ultimately positive and
The subject was first studied systematically by
Ramanujan starting in 1915.[1]: 87
Examples
For the
sum-of-divisors function σ(n) we have the trivial result because always σ(n) ≥ n and for
primes σ(p) = p + 1. We also have proved by
Gronwall in 1913.[1]: 86 [2]: Theorem 323 [3] Therefore n is a minimal order and e−γn ln ln n is a maximal order for σ(n).
For the
Euler totient φ(n) we have the trivial result because always φ(n) ≤ n and for primes φ(p) = p − 1. We also have proven by
Landau in 1903.[1]: 84 [2]: Theorem 328
For the
number of divisors function d(n) we have the trivial lower bound 2 ≤ d(n), in which equality occurs when n is prime, so 2 is a minimal order. For ln d(n) we have a maximal order ln 2 ln n / ln ln n, proved by Wigert in 1907.[1]: 82 [2]: Theorem 317
For the number of distinct
prime factors ω(n) we have a trivial lower bound 1 ≤ ω(n), in which equality occurs when n is a
prime power. A maximal order for ω(n) is ln n / ln ln n.[1]: 83
For the number of prime factors counted with multiplicity Ω(n) we have a trivial lower bound 1 ≤ Ω(n), in which equality occurs when n is prime. A maximal order for Ω(n) is ln n / ln 2[1]: 83
It is
conjectured that the
Mertens function, or summatory function of the
Möbius function, satisfies though to date this limit superior has only been shown to be larger than a small constant. This statement is compared with the disproof of
Mertens conjecture given by Odlyzko and te Riele in their several decades old breakthrough paper Disproof of the Mertens Conjecture. In contrast, we note that while extensive computational evidence suggests that the above conjecture is true, i.e., along some increasing sequence of tending to infinity the average order of grows unbounded, that the
Riemann hypothesis is equivalent to the limit being true for all (sufficiently small) .
^
abcdefg
Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press.
ISBN0-521-41261-7.