## § Heuristics for the prime number theorem

"It is evident that the primes are randomly distributed but, unfortunately, we don't know what 'random' means."
• The prime number theorem says that at $n$, the number of primes upto $n$ is (approx.) $(n/\log n)$. Formally:
$P(n) \equiv |\{ p \text{ prime } : 2 \leq p \leq n \}| \sim \frac{n}{\log n}$
• Consider sieving. In the beginning, everything is potentially prime.
• When we remove the multiples of a prime p, we decrease the density of potential primes.
• As we remove 1/p of the remaining potential primes (eg. removing 2 drops density of potential primes by half. Sieving by 3 reduces the density by one-third).
• See that the reduction is additive not multiplicative . That is, upon removing the 5, we lose 1/5 of our potential primes, so the new density is D2 = D - D/5. Said differently, we have 4/5th the number of potential primes we used to have, so D2 = 4D/5.
• Furthermore, removing 5 only begins to affect the density of primes after 5*5 = 25, since smaller multiples of 5 ( 5*1, 5*2, 5*3, 5*4) have been removed at earlier iterations of the sieve (on sieving 5, 2, 3, and 2, respectively).
• In general: On removing a prime p, Our new density becomes D2 = D - D/p which is (1-1/p)D.
• In general: On removing a prime p, the density till p*p remains untouched. Density after p*p is multiplicatively scaled by (p-1)/p.
• Define a function $f(x)$ which estimates density of primes around $x$.
• We consider the effect of the primes in the interval $A \equiv [x, x+dx]$ on the interval $B \equiv [x^2, (x+dx)^2]$
• Each prime $p$ in interval $A$ decreases the density of primes in interval $B$ by subtracting $f(x^2)/p$, since we lose those many primes. Since each number in $[x, x+dx]$ is basically $x$, we approximate this subtraction to $f(x^2)/x$.
• In interval $A$, there are $f(x)dx$ primes.
\begin{aligned} &f((x+dx)^2) = \\ &= f(x^2) - \text{killing of from primes in x} \\ &= f(x^2) - \sum_{p \in [x, x+dx]} [\texttt{Prob}(p \text{ prime})] \cdot f(x^2)/p \\ &= f(x^2) - \sum_{p \in [x, x+dx]} [f(p)] \cdot f(x^2)/p \\ &= \text{(p \sim x in [x, x+dx]):} \\ &= f(x^2) - \texttt{length}([x,x+dx]) \cdot [f(x)] \cdot f(x^2)/p \\ &= f(x^2) - (dx) f(x) \cdot f(x^2)/x \\ &f((x+dx)^2) = f(x^2) - f(x^2)f(x)dx/x \\ &f((x+dx)^2) - f(x^2) = -\frac{f(x^2)f(x)dx}{x} \end{aligned}
From this, we now estimate $f'(x^2)$ as:
\begin{aligned} &f((x+dx)^2) - f(x^2) = -\frac{f(x^2)f(x)dx}{x} \\ &\frac{f((x+dx)^2) - f(x^2)}{dx} = -\frac{f(x^2)f(x)}{x} \\ &\frac{f(x^2 + 2dx + dx^2) - f(x^2)}{dx} = -\frac{f(x^2)f(x)}{x} \\ &\text{Ignore O(dx^2):} \\ &\frac{f(x^2 + 2dx) - f(x^2)}{dx} = -\frac{f(x^2)f(x)}{x} \\ &\frac{f(x^2 + 2dx) - f(x^2)}{dx \cdot 2x} = -\frac{f(x^2)f(x)}{x\cdot 2x} \\ &\frac{f(x^2 + 2dx) - f(x^2)}{2xdx} = -\frac{f(x^2)f(x)}{2x^2} \\ & \text{Let u = x^2} \\ &\frac{f(u + du) - f(u)}{du} = -\frac{f(u)f(\sqrt u)}{2u} \\ &f'(u) = -\frac{f(u)f(\sqrt u )}{2u} \end{aligned}

#### § An immediate consequence

Sice $u$ is large, we approximate $u \sim \sqrt{u}$ to get:
\begin{aligned} &f'(u) = -\frac{f(u)f(\sqrt u )}{2u} \\ &f'(u) \sim -\frac{f^2(u)}{2u} \\ &\frac{df}{du} \sim -\frac{f^2(u)}{u} \\ &\frac{df}{f^2} \sim -\frac{du}{u} \\ &\int \frac{df}{f^2} \sim - \int \frac{du}{u} \\ &-\frac{1}{f(u)} \sim -\ln(u) \\ &\frac{1}{f(u)} \sim \ln(u) \\ &f(u) \sim \frac{1}{\ln(u)} \end{aligned}
So the density of primes around $f(u)$ is $1/\ln(u)$. So upto $n$, the number of primes is $\int_0^n f(x) dx$ which is $\int_0^n 1/ln(x) dx$, bounded by $n/ln(n)$. This "proves" the prime number theorem.