Misplaced Pages

Extremal orders of an arithmetic function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

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

lim inf n → ∞ f ( n ) m ( n ) = 1 {\displaystyle \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

lim sup n → ∞ f ( n ) M ( n ) = 1 {\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{M(n)}}=1}

we say that M is a maximal order for f. Here, lim inf n → ∞ {\displaystyle \liminf _{n\to \infty }} and lim sup n → ∞ {\displaystyle \limsup _{n\to \infty }} 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) we have the trivial result lim inf n → ∞ σ ( n ) n = 1 {\displaystyle \liminf _{n\to \infty }{\frac {\sigma (n)}{n}}=1} because always σ(n) ≥ n and for primes σ(p) = p + 1. We also have lim sup n → ∞ σ ( n ) n ln ⁡ ln ⁡ n = e γ , {\displaystyle \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 lim sup n → ∞ ϕ ( n ) n = 1 {\displaystyle \limsup _{n\to \infty }{\frac {\phi (n)}{n}}=1} because always φ(n) ≤ n and for primes φ(p) = p − 1. We also have lim inf n → ∞ ϕ ( n ) ln ⁡ ln ⁡ n n = e − γ , {\displaystyle \liminf _{n\to \infty }{\frac {\phi (n)\ln \ln n}{n}}=e^{-\gamma },} 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 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 a prime power. 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
  • It is conjectured that the Mertens function, or summatory function of the Möbius function, satisfies lim sup n → ∞ | M ( x ) | x = + ∞ , {\displaystyle \limsup _{n\to \infty }{\frac {|M(x)|}{\sqrt {x}}}=+\infty ,} 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 { x n } n ≥ 1 {\displaystyle \{x_{n}\}_{n\geq 1}} tending to infinity the average order of x n | M ( x n ) | {\displaystyle {\sqrt {x_{n}}}|M(x_{n})|} grows unbounded, that the Riemann hypothesis is equivalent to the limit lim x → ∞ M ( x ) / x 1 2 + ε = 0 {\displaystyle \lim _{x\to \infty }M(x)/x^{{\frac {1}{2}}+\varepsilon }=0} being true for all (sufficiently small) ε > 0 {\displaystyle \varepsilon >0} .

See also

Notes

  1. ^ Tenenbaum, Gérald (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics. Vol. 46. Cambridge University Press. ISBN 0-521-41261-7.
  2. ^ Hardy, G. H.; Wright, E. M. (1979). An Introduction to the Theory of Numbers (5th ed.). Oxford: Clarendon Press. ISBN 0-19-853171-0.
  3. Gronwall, T. H. (1913). "Some asymptotic expressions in the theory of numbers". Transactions of the American Mathematical Society. 14 (4): 113–122. doi:10.1090/s0002-9947-1913-1500940-6.

Further reading

Category: