In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, the Erdős–Kac theorem, named after
Paul Erdős and
Mark Kac
Mark Kac ( ; Polish: ''Marek Kac''; August 3, 1914 – October 26, 1984) was a Polish American mathematician. His main interest was probability theory. His question, " Can one hear the shape of a drum?" set off research into spectral theory, the ...
, and also known as the fundamental theorem of
probabilistic number theory
In mathematics, Probabilistic number theory is a subfield of number theory, which explicitly uses probability to answer questions about the integers and integer-valued functions. One basic idea underlying it is that different prime numbers are, in ...
, states that if ''ω''(''n'') is the number of distinct
prime factors of ''n'', then, loosely speaking, the
probability distribution of
:
is the standard
normal distribution
In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is
:
f(x) = \frac e^
The parameter \mu ...
. (
is sequence
A001221 in the
OEIS
The On-Line Encyclopedia of Integer Sequences (OEIS) is an online database of integer sequences. It was created and maintained by Neil Sloane while researching at AT&T Labs. He transferred the intellectual property and hosting of the OEIS to the ...
.) This is an extension of the
Hardy–Ramanujan theorem In mathematics, the Hardy–Ramanujan theorem, proved by , states that the normal order of the number ω(''n'') of distinct prime factors of a number ''n'' is log(log(''n'')).
Roughly speaking, this means that most numbers have about this number ...
, which states that the
normal order
In quantum field theory a product of quantum fields, or equivalently their creation and annihilation operators, is usually said to be normal ordered (also called Wick order) when all creation operators are to the left of all annihilation operator ...
of ''ω''(''n'') is log log ''n'' with a typical error of size
.
Precise statement
For any fixed ''a'' < ''b'',
:
where
is the normal (or "Gaussian") distribution, defined as
:
More generally, if ''f''(''n'') is a strongly
additive function
In number theory, an additive function is an arithmetic function ''f''(''n'') of the positive integer variable ''n'' such that whenever ''a'' and ''b'' are coprime, the function applied to the product ''ab'' is the sum of the values of the func ...
(
) with
for all prime ''p'', then
:
with
:
Kac's original heuristic
Intuitively, Kac's heuristic for the result says that if ''n'' is a randomly chosen large integer, then the number of distinct prime factors of ''n'' is approximately normally distributed with mean and variance log log ''n''. This comes from the fact that given a random natural number ''n'', the events "the number ''n'' is divisible by some prime ''p''" for each ''p'' are mutually independent.
Now, denoting the event "the number ''n'' is divisible by ''p''" by
, consider the following sum of indicator random variables:
:
This sum counts how many distinct prime factors our random natural number ''n'' has. It can be shown that this sum satisfies the
Lindeberg condition In probability theory, Lindeberg's condition is a sufficient condition (and under certain conditions also a necessary condition) for the central limit theorem (CLT) to hold for a sequence of independent random variables. Unlike the classical CLT, wh ...
, and therefore the
Lindeberg central limit theorem guarantees that after appropriate rescaling, the above expression will be Gaussian.
The actual proof of the theorem, due to Erdős, uses
sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The prototypical example of a sifted set is the set of prime numbers up to some prescribed lim ...
to make rigorous the above intuition.
Numerical examples
The Erdős–Kac theorem means that the construction of a number around one billion requires on average three primes.
For example, 1,000,000,003 = 23 × 307 × 141623. The following table provides a numerical summary of the growth of the average number of distinct prime factors of a natural number
with increasing
.
Around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% are constructed from between 7 and 13 primes.
A hollow sphere the size of the planet Earth filled with fine sand would have around 10
33 grains. A volume the size of the observable universe would have around 10
93 grains of sand. There might be room for 10
185 quantum strings in such a universe.
Numbers of this magnitude—with 186 digits—would require on average only 6 primes for construction.
It is very difficult if not impossible to discover the Erdös-Kac theorem empirically, as the Gaussian only shows up when
starts getting to be around
. More precisely,
Rényi and
Turán showed that the best possible uniform asymptotic bound on the error in the approximation to a Gaussian is
.
References
*
*
*
External links
*
Timothy Gowers: The Importance of Mathematics (part 6, 4 mins in) and (part 7)
{{DEFAULTSORT:Erdos-Kac theorem
Kac theorem
Normal distribution
Theorems about prime numbers