A Universe of Sorts

§ 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)

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.