The extremal orders of an arithmetic function in number theory, a branch of mathematics, are the 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

we say that M is a maximal order for f. denote the limit inferior and limit superior, respectively.

The subject was first studied systematically by Ramanujan starting in 1915.

Examples

• For the sum-of-divisors function σ(n because always σ(n) ≥ n and for primes σ(p) = p+ proved by Gronwall in 1913. Therefore n is a minimal order and is a maximal order for σ(n).

• For the Euler totient φ(n because always φ(n) ≤ n and for primes φ(p) = p− proven 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 lnd(n) we have a maximal order , 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 a prime power. A maximal order for ω(n) is .

• 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

• It is conjectured that the Mertens function, or summatory function of the Möbius function 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 grows unbounded, that the Riemann hypothesis.

See also

• Average order of an arithmetic function

• Normal order of an arithmetic function

Notes

Further reading

• A survey of extremal orders, with an extensive bibliography.