Extremal orders of an arithmetic function

In mathematics, 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

$\liminf _{n\to \infty }{\frac {f(n)}{m(n)}}=1$

we say that m is a minimal order for f. Similarly if M(n) is a non-decreasing function that is ultimately positive and

$\limsup _{n\to \infty }{\frac {f(n)}{M(n)}}=1$

we say that M is a maximal order for f. The subject was first studied systematically by Ramanujan starting in 1915.

Examples

• For the sum-of-divisors function σ(n) we have the trivial result

$\liminf _{n\to \infty }{\frac {\sigma (n)}{n}}=1$

because always σ(n) ≥ n and for primes σ(p) = p + 1. We also have

$\limsup _{n\to \infty }{\frac {\sigma (n)}{n\ln \ln n}}=e^{\gamma },$

proved by Gronwall in 1913. 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

$\liminf _{n\to \infty }{\frac {\phi (n)}{n}}=1$

because always φ(n) ≤ n and for primes φ(p) = p - 1. We also have

$\liminf _{n\to \infty }{\frac {\phi (n)\ln \ln n}{n}}=e^{-\gamma },$

proved by Landau in 1903.

• 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.
• For the number of distinct prime factors ω(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 ln n.
• 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.

See also

• Average order of an arithmetic function
• Normal order of an arithmetic function

Further reading

• Nicolas, J.-L. (1988). "On Highly Composite Numbers". In Andrews, G. E.; Askey, R. A.; Berndt, B. C.; Ramanathan, K. G.; Rankin, R. A. (eds.). Ramanujan Revisited. Academic Press. pp. 215–244. ISBN 978-0120585601. A survey of extremal orders, with an extensive bibliography.