Erdős–Kac theorem

Erdős–Kac theorem is a fundamental result in number theory and probability theory, which illustrates the deep connection between these two fields. It is named after the Hungarian mathematician Paul Erdős and the American mathematician Mark Kac, who formulated the theorem in the mid-20th century. The theorem is often cited as a prime example of the probabilistic method in mathematics, demonstrating how concepts from probability can be used to address and solve problems in number theory.

Statement of the Theorem

The Erdős–Kac theorem states that, given a large natural number n, the number of distinct prime factors of n (denoted as ω(n)) behaves like a normal distribution as n goes to infinity. More precisely, for the normalized function

\[ \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}}, \]

the distribution of values as n varies approaches the standard normal distribution. This result is surprising because it links the distribution of prime numbers, a purely number-theoretic concept, with the bell curve or Gaussian distribution, a fundamental concept in probability theory.

Background

The theorem emerged from the study of the distribution of prime numbers, a central topic in number theory. The Prime Number Theorem, which describes the asymptotic distribution of prime numbers, laid the groundwork for the Erdős–Kac theorem. Erdős and Kac extended the ideas of the Prime Number Theorem by applying probabilistic methods to the study of the multiplicative structure of integers.

Implications

The Erdős–Kac theorem has several important implications. It provides a probabilistic model for the distribution of prime factors of natural numbers, suggesting that prime factorization, despite its deterministic nature, exhibits random-like behavior. This insight has influenced various areas of mathematics, including cryptanalysis and random matrix theory.

Proof and Techniques

The proof of the Erdős–Kac theorem employs techniques from both number theory and probability theory. It involves the use of characteristic functions and the method of moments, tools commonly used in the study of probability distributions. The theorem also relies on properties of the Riemann zeta function and the use of sieve methods, a set of techniques for estimating the distribution of prime numbers.

Extensions and Generalizations

Since its original formulation, the Erdős–Kac theorem has been extended and generalized in various ways. Researchers have explored analogous results for other arithmetic functions and have investigated the behavior of prime factors in other number systems, such as Gaussian integers. These extensions have further demonstrated the versatility of the probabilistic method in number theory.

See Also

• Prime Number Theorem
• Probabilistic method
• Riemann zeta function
• Sieve theory