Question

Let π(N) be the number of primes less than or equal to N (example: π(100) = 25). The famous prime number theorem then states (with ∼ meaning asymptotically equal):
π(N) ∼ N/ log(N)
Proving this theorem is very hard. However, we can derive a statistical form of the prime number theorem. For this, we consider random primes which are generated as follows:
(i) Create a list of consecutive integers from 2 to N.

Answer 1

By Euclid's theorem, we know that there exist infinitely many primes. Of course, this means that π is an increasing function and that π(x)→ ∞ as x→ ∞. Intuitively we see that prime numbers appear to be more sporadic as they become larger, but we would like to describe more precisely the asymptotic behavior of π. This is formalized by the following famous theorem.

Theorem: (Prime number theorem). $Let\ π\ be\ the\ prime\ counting\ function\ and\ log\ be\ the\ natural\ logarithm.\ Then\ a\\ good\ asymptotic\ approximation\ of\ π\ is\ given\ by\ the\ function$

(i) Create a list of consecutive integers from $2$ to $N$ .

(ii) Start with $2$ and mark every number $>2$ with a probability of $\frac12$ .

(iii) Let $n$ be the next non-marked number. Mark every number $>n$ with a probability of $\frac1n$ .

(iv) Repeat $(iii)$ until you have reached $N$ .

All the non-marked numbers in the list are called $random\ primes$ .

(a) Let $q_n$ be the probability of $n$ being selected as a random prime during this algorithm. Find an expression for $q_n$ in terms of $q_n−1$ .

(b) Prove the following inequality of $q_n$ and $q_n+1:$

$q_n ∼ nlog\ n\\ \frac{q_n}{n}=log\ log\ n-1+\frac{log\ log\ n-2}{log\ n}- \frac{(log\ log\ n)^2-6log\ log\ n+11}{2(log\ n)^2}+0(\frac{1}{(log\ n)^2})\\$

Again considering the $2×10^{17}th$ prime number 8 512 677 386 048 191 063, this gives an estimate of 8 512 681 315 554 715 386; the first 5 digits match and relative error is about 0.00005%.

Rosser's theorem states that;

${\displaystyle p_{n}>n\log n.}$

This can be improved by the following pair of bounds:

$\therefore log\ n+log\ log\ n-1<\frac{q_n}{n}<log\ n + log\ log\ n,\ \forall n \geq 6\\ \implies \frac{1}{q_n}+\frac{1}{n}< \frac{1}{q_n+1}<\frac{1}{q_n}+\frac{1}{n-1}$

(c) Use the result from $(b)$ to show this inequality:

$\sum_{p^k \leq x,\\ k \geq2} \frac{log\ p}{p^k}\\ Which\ can\ be\ bounded\ by;\\ \sum_{p}log\ p\sum_{k=2}^N \frac{1}{p^k} \leq 2 \sum \frac{log\ p}{p^2}<\infty\\ Hence\\ \implies \sum_{k=1}^N \frac{1}{k}<\frac{i}{q_N}<\sum_{k=1}^N \frac{1}{k}+1$

(d) With this result, derive an asymptotic expression for $q_n$ in terms of $n$ .

$$q_n ∼ nlog\ n\\$$

(e) Let $\widetilde π(N)$ be the number of $random\ primes$ less than or equal to $N$ . Use the result from $(d)$ to derive an asymptotic expression for $\widetilde π(N)$ , i.e. the prime number theorem for $random\ primes.$