HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, specifically in
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, the extremal orders of an arithmetic function are best possible bounds of the given
arithmetic function In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function whose domain is the set of positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition th ...
. Specifically, if ''f''(''n'') is an arithmetic function and ''m''(''n'') is a non-decreasing function that is ultimately positive and :\liminf_ \frac = 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_ \frac = 1 we say that ''M'' is a maximal order for ''f''. Here, \liminf_ and \limsup_ denote the
limit inferior and limit superior In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting (that is, eventual and extreme) bounds on the sequence. They can be thought of in a similar fashion for a function (see limit of a function). For ...
, 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 \liminf_ \frac = 1 because always σ(''n'') ≥ ''n'' and for primes σ(''p'') = ''p'' + 1. We also have \limsup_ \frac = e^\gamma, proved by Gronwall in 1913. Therefore ''n'' is a minimal order and is a maximal order for σ(''n''). * For the Euler totient φ(''n'') we have the trivial result \limsup_ \frac = 1 because always φ(''n'') ≤ ''n'' and for primes φ(''p'') = ''p'' − 1. We also have \liminf_ \frac = e^, proven by
Landau Landau (), officially Landau in der Pfalz (, ), is an autonomous (''kreisfrei'') town surrounded by the Südliche Weinstraße ("Southern Wine Route") district of southern Rhineland-Palatinate, Germany. It is a university town (since 1990), a long ...
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 , 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 In mathematics, a prime power is a positive integer which is a positive integer power of a single prime number. For example: , and are prime powers, while , and are not. The sequence of prime powers begins: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 1 ...
. 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
conjecture In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
d that the
Mertens function In number theory, the Mertens function is defined for all positive integers ''n'' as : M(n) = \sum_^n \mu(k), where \mu(k) is the Möbius function. The function is named in honour of Franz Mertens. This definition can be extended to positive r ...
, or summatory function of the
Möbius function The Möbius function \mu(n) is a multiplicative function in number theory introduced by the German mathematician August Ferdinand Möbius (also transliterated ''Moebius'') in 1832. It is ubiquitous in elementary and analytic number theory and m ...
, satisfies \limsup_ \frac = +\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 In mathematics, the Mertens conjecture is the statement that the Mertens function M(n) is bounded by \pm\sqrt. Although now disproven, it had been shown to imply the Riemann hypothesis. It was conjectured by Thomas Joannes Stieltjes, in an 1885 ...
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 \sqrt , M(x_n), grows unbounded, that the
Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in pure ...
is equivalent to the limit \lim_ M(x) / x^ = 0 being true for all (sufficiently small) \varepsilon > 0.


See also

*
Average order of an arithmetic function In number theory, an average order of an arithmetic function is some simpler or better-understood function which takes the same values "on average". Let f be an arithmetic function. We say that an ''average order'' of f is g if \sum_ f(n) \sim \su ...
*
Normal order of an arithmetic function In number theory, a normal order of an arithmetic function is some simpler or better-understood function which "usually" takes the same or closely approximate values. Let ''f'' be a function on the natural numbers. We say that ''g'' is a normal o ...


Notes


Further reading

* {{cite book , last1=Nicolas , first1=J.-L. , editor1-first=G. E. , editor1-last=Andrews , editor1-link=George Andrews (mathematician) , editor2-first=R. A. , editor2-last=Askey , editor2-link=Richard Askey , editor3-first=B. C. , editor3-last=Berndt , editor3-link=Bruce Berndt , editor4-first=K. G. , editor4-last=Ramanathan , title=Ramanujan Revisited , year=1988 , publisher=Academic Press , isbn=978-0-12-058560-1 , page
215–244
, chapter=On Highly Composite Numbers , url=https://archive.org/details/ramanujanrevisit1987rama/page/215 A survey of extremal orders, with an extensive bibliography. Arithmetic functions