Erdős–Kac theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In number theory, the Erdős–Kac theorem, named after Paul Erdős and Mark Kac, and also known as the fundamental theorem of probabilistic number theory, states that if ω(n) is the number of distinct prime factors of n, then, loosely speaking, the probability distribution of

 \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}}

is the standard normal distribution. This is a deep extension of the Hardy–Ramanujan theorem, which states that the normal order of ω(n) is log log n with a typical error of size \sqrt{\log\log n}.

Precise Statement[edit]

For any fixed a < b,

\lim_{x \rightarrow \infty}  \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{\omega(n) - \log \log n}{\sqrt{\log \log n}} \le b \right\} \right ) = \Phi(a,b)

where \Phi(a,b) is the normal (or "Gaussian") distribution, defined as

\Phi(a,b)= \frac{1}{\sqrt{2\pi}}\int_a^b e^{-t^2/2} \, dt.

More generally, if f(n) is a strongly additive function (\scriptstyle f(p_1^{a_1}\cdots p_k^{a_k})=f(p_1)+\cdots+f(p_k)) with \scriptstyle |f(p)|\le1 for all prime p, then

\lim_{x \rightarrow \infty}  \left ( \frac {1}{x} \cdot \#\left\{ n \leq x : a \le \frac{f(n) - A(n)}{B(n)} \le b \right\} \right ) = \Phi(a,b)

with

A(n)=\sum_{p\le n}\frac{f(p)}{p},\qquad B(n)=\sqrt{\sum_{p\le n}\frac{f(p)^2}{p}}.

Kac's Original Heuristic[edit]

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 n_{p}, consider the following sum of indicator random variables:

I_{n_{2}} + I_{n_{3}} + I_{n_{5}} + I_{n_{7}} + \ldots

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, 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 to make rigorous the above intuition.

Numerical Examples[edit]

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 n with increasing n.

n Number of

Digits in n

Average number

of distinct primes

standard

deviation

1,000 4 2 1.4
1,000,000,000 10 3 1.7
1,000,000,000,000,000,000,000,000 25 4 2
1065 66 5 2.2
109,566 9,567 10 3.2
10210,704,568 210,704,569 20 4.5
101022 1022+1 50 7.1
101044 1044+1 100 10
1010434 10434+1 1000 31.6
A spreading Gaussian distribution of distinct primes illustrating the Erdos-Kac theorem

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 1033 grains. A volume the size of the observable universe would have around 1093 grains of sand. There might be room for 10185 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 this result empirically, as the Gaussian only shows up when n starts getting to be around 10^{100}. More precisely, Renyi and Turan showed that the best possible uniform asymptotic bound on the error in the approximation to a Gaussian is O\left(\frac{1}{\sqrt{\log(\log(n))}}\right)[citation needed].

References[edit]

External links[edit]