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
:
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''.
[
] Here,
and
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
because always σ(''n'') ≥ ''n'' and for
primes σ(''p'') = ''p'' + 1. We also have
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
because always φ(''n'') ≤ ''n'' and for primes φ(''p'') = ''p'' − 1. We also have
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
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
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
being true for all (sufficiently small)
.
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