🔢 mathematics

On the Hardy-Ramanujan Theorem

This paper establishes an effective version of the Hardy-Ramanujan Theorem by proving that the shifted empirical distribution of the number of distinct prime factors $\omega(n)$ is pointwise dominated by a fixed multiple of a Poisson distribution, while also deriving sharper estimates for squarefree integers, explicit deviation bounds, and uniform moment results for related arithmetic functions.

Original authors: Benjamin Durkan

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Durkan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are walking through a vast, infinite forest of numbers. Every tree in this forest is an integer (2, 3, 4, 5, ...). Some trees are simple, like a pine with just one type of branch (a prime number). Others are complex, like an oak with many different types of branches (a number made of many different prime factors).

Mathematicians have long been fascinated by a specific question: How many different "types of branches" (distinct prime factors) does a typical tree in this forest have?

For example:

The number 12 is made of $2 \times 2 \times 3$ . It has 2 distinct types of branches (2 and 3).
The number 30 is made of $2 \times 3 \times 5$ . It has 3 distinct types.
The number 210 is made of $2 \times 3 \times 5 \times 7$ . It has 4 distinct types.

The Old Map: Hardy and Ramanujan

In the early 20th century, two giants of mathematics, G.H. Hardy and Srinivasa Ramanujan, drew a map of this forest. They discovered a surprising rule: If you pick a very large number $n$ , the number of its distinct prime factors is usually very close to $\log(\log n)$ .

Think of $\log(\log n)$ as the "average height" of the trees in a specific section of the forest. Hardy and Ramanujan proved that almost all trees are roughly this height. However, their map had some blurry edges. They knew where the trees were, but they didn't have a precise ruler to measure exactly how far a tree could stray from the average, nor did they have a perfect formula to predict the odds of finding a very tall or very short tree.

The New Map: Benjamin Durkan's "Effective" Version

Benjamin Durkan's paper is like taking that old, blurry map and redrawing it with a laser-guided GPS. He doesn't just say "most trees are average"; he gives you a strict, mathematical rule that guarantees exactly how rare the outliers are.

Here is the core of his discovery, explained simply:

1. The "Poisson" Shadow

Durkan proves that the distribution of these prime factors follows a specific statistical pattern called the Poisson distribution.

The Analogy: Imagine you are counting raindrops hitting a specific patch of ground. You know the average rate (say, 10 drops per minute). The Poisson distribution tells you the probability of getting 5 drops, 15 drops, or 20 drops.
The Result: Durkan shows that the "prime factor count" of numbers behaves exactly like those raindrops. He proves that the number of integers with a specific count of prime factors is dominated (or "shadowed") by this Poisson pattern.
Why it matters: This means we can use the well-known rules of the Poisson distribution to predict the behavior of these numbers with extreme precision.

2. The "Safety Net" (Explicit Constants)

Previous proofs were like saying, "The tree won't grow taller than a certain vague limit." Durkan's paper is like saying, "The tree will never grow taller than 117.20 times the average deviation."

He calculates specific numbers (like 4.096 and 117.20) that act as safety nets.
These numbers ensure that no matter how far out you look in the forest, you can mathematically guarantee that the number of "weird" trees (those with way too many or way too few prime factors) is smaller than a specific, calculated amount.

3. The "Deletion" Trick

How did he do this? He used a clever counting trick he calls "deletion."

The Analogy: Imagine you have a complex Lego tower. To count how many towers have exactly 5 blocks, you can look at towers with 6 blocks and ask, "If I remove one specific block, do I get a 5-block tower?"
Durkan uses this logic recursively. He counts numbers with $k$ prime factors by looking at numbers with $k+1$ factors and "deleting" a prime part. This creates a chain reaction of counting that allows him to pin down the exact numbers.

What Does This Give Us?

Because he has this precise "shadow" (the Poisson distribution) and these strict safety nets, Durkan can instantly derive several other useful facts:

The "Gaussian" Window: He can calculate the odds of finding a number that is slightly taller or shorter than average. It turns out these odds look like a bell curve (the famous "Normal Distribution"), but he provides the exact formula for the edges of the curve.
The "Extreme" Outliers: He can tell you exactly how rare it is to find a number with massive amounts of prime factors (like a tree with 100 different branch types). The odds drop off so fast they are almost zero.
Squarefree vs. Regular: He also refined this for "squarefree" numbers (numbers that don't have any repeated prime factors, like $2 \times 3 \times 5$ but not $2 \times 2 \times 3$ ). The rules are slightly different there, and he gave the precise numbers for that case too.

Summary

In short, Benjamin Durkan took a classic, slightly fuzzy mathematical rule about prime numbers and turned it into a precise, quantitative law.

He didn't just say, "Prime factors usually follow a bell curve." He said, "Here is the exact bell curve, here is the exact multiplier, and here is the exact mathematical guarantee that no number will break these rules." It's the difference between a weather forecast that says "it might rain" and one that says "there is a 99.9% chance of rain between 2:00 PM and 2:15 PM."

Technical Summary: An Effective Version of the Hardy–Ramanujan Theorem

Problem Statement
The paper addresses the distribution of the number of distinct prime factors, $\omega(n)$ , and the total number of prime factors, $\Omega(n)$ , for integers $n \le x$ . While the classical Hardy–Ramanujan theorem establishes that both functions have a normal order of $\log \log n$ , the original proof relies on a counting inequality for level sets $A_k(x) = \#\{n \le x : \omega(n) = k\}$ that provides exponential upper tails but lacks explicit constants. Subsequent proofs, such as Turán's second-moment method, are shorter but yield only polynomial tail bounds via Chebyshev's inequality. The probabilistic Erdős–Kac theorem identifies the limiting Gaussian distribution but does not provide effective, non-asymptotic bounds for finite $x$ . This note aims to bridge these gaps by providing an effective, explicit version of the Hardy–Ramanujan counting inequality, packaging the result as a domination inequality against a Poisson distribution with fully explicit constants.

Methodology
The author employs the original "deletion argument" used by Hardy and Ramanujan but refines it to make all constants explicit. The core methodology involves:

Deletion Recurrence: Establishing a recurrence relation for $A_k(x)$ by counting integers multiple times. Specifically, for an integer $n$ with $k+1$ distinct prime factors, deleting exact prime-power divisors yields a recurrence linking $A_{k+1}(x)$ to sums of $A_k(x/p^a)$ .
Inductive Principle: Formulating a general induction principle (Proposition 3.2) that, given explicit bounds for the base case $A_1(x)$ and a specific sum involving prime powers, yields an explicit upper bound for $A_k(x)$ of the form $C \frac{x}{\log x} \frac{(\log \log x + B)^{k-1}}{(k-1)!}$ .
Explicit Prime Estimates: Utilizing explicit bounds from prime number theory (Rosser and Schoenfeld) to verify the hypotheses of the induction principle. This includes precise estimates for $\sum_{p \le x} 1/p$ , $\pi(x)$ , and sums over prime powers.
Poisson Domination: Translating the counting inequality into a probabilistic statement. By recognizing the factorial structure of the bound, the author shows that the shifted empirical distribution of $\omega(n)$ is pointwise dominated by a Poisson random variable $Z_\xi$ with parameter $\xi = \log \log x + 4.096$ .
Extension to $\Omega(n)$ and $\omega_1(n)$ : The results are extended to the total number of prime factors $\Omega(n)$ and the number of prime factors occurring exactly once $\omega_1(n)$ by analyzing the "squarefull excess" $R(n) = \Omega(n) - \omega(n)$ and proving an exponential tail bound for $R(n)$ .

Key Contributions and Results

Explicit Counting Inequality (Theorem 1.2): The paper proves that for every $x \ge 2$ and integer $k \ge 1$ :
$A_k(x) \le 1.95 \frac{x}{\log x} \frac{(\log \log x + 4.096)^{k-1}}{(k-1)!}$
This improves upon the classical $O(\cdot)$ notation by providing the specific constant $1.95$ and the shift $4.096$.
Poisson Domination (Theorem 1.1): For any non-negative function $F$ , the shifted empirical average is bounded by a Poisson expectation:
$\frac{1}{x} \sum_{2 \le n \le x} F(\omega(n) - 1) \le Q \mathbb{E}[F(Z_\xi)]$
where $Q = 1.95 e^{4.096} < 117.20$ and $\xi = \log \log x + 4.096$ . This implies that the distribution of $\omega(n)$ is dominated by a fixed multiple of a Poisson law.
Explicit Tail Bounds:
- Large Deviations (Corollary 1.3): The paper derives large-deviation estimates with the standard Poisson rate function $I(\alpha) = \alpha \log \alpha - \alpha + 1$ , showing that the count of integers with $\omega(n) \ge \alpha \log \log x$ is bounded by $x (\log x)^{-I(\alpha)}$ .
- Gaussian-Scale Bounds (Theorem 1.4): For deviations of the form $A \sqrt{\log \log x}$ , the paper provides explicit upper bounds resembling Gaussian tails. For example, for $1 \le A \le \sqrt{\log \log x}/4$ :
  $\frac{1}{x} \#\{n \le x : |\omega(n) - \log \log x| > A \sqrt{\log \log x}\} \le \frac{305}{A} \exp\left(-\frac{A^2}{2} + \frac{7.31 A^3}{\sqrt{\log \log x}}\right)$
- Moderate Deviations (Theorem 1.5): It is shown that for $A \to \infty$ with $A = o(\sqrt{\log \log x})$ , the probability decays as $\exp(-(1/2 + o(1))A^2)$ .
Uniform Moment Estimates (Theorem 1.6): The paper establishes uniform bounds for moments of order $r$ :
$\left( \frac{1}{x} \sum_{2 \le n \le x} |f(n) - \log \log x|^r \right)^{1/r} \le C(\sqrt{r(\log \log x + 1)} + r)$
for $f \in \{\omega, \Omega, \omega_1\}$ . This recovers the Gaussian-order central moment estimate for fixed $r$ .
Squarefree Analogue: A sharper estimate is derived for squarefree integers, with a smaller constant ($1.25506$) and a smaller shift ($1.174$) in the Poisson parameter.

Significance and Claims
The paper claims to provide a "different aim" from modern refinements like the Sathe–Selberg theorem or probabilistic treatments (Erdős–Kac, Kubilius). Instead of seeking asymptotics for growing $k$ or limiting distributions, the author focuses on elementary, explicit, and non-asymptotic bounds.

The significance lies in:

Explicit Constants: Making the Hardy–Ramanujan argument quantitative with specific numerical constants ($1.95$, $4.096$, $Q < 117.20$ ), which are often omitted in classical treatments.
Poisson Domination: Framing the result as a domination inequality against a Poisson distribution, which allows for the immediate derivation of Chernoff bounds, moment estimates, and tail bounds by choosing appropriate test functions $F$ .
Elementary Nature: The proof relies on the original deletion argument and explicit prime number estimates, avoiding complex analytic machinery or probabilistic limit theorems, yet yielding results that are sharper than Turán's polynomial bounds and comparable in shape to the Gaussian tails of the Erdős–Kac theorem (though strictly as upper bounds).
Generality: The approach naturally extends to $\Omega(n)$ and $\omega_1(n)$ via the analysis of the squarefull part, providing a unified effective theory for these arithmetic functions.

The author notes that the shift $4.096$ is not claimed to be optimal but serves to keep the finite- $x$ argument transparent. The primary contribution is the functional form of the domination, which unifies various estimates (pointwise, tail, generating function, moment) under a single explicit inequality.