Answer to Question #143553 in Abstract Algebra for Sandra

Question #143553
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.
1
Expert's answer
2020-11-18T18:37:53-0500

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\\ \u03c0\\ be\\ the\\ prime\\ counting\\ function\\ and\\ log\\ be\\ the\\ natural\\ logarithm.\\ Then\\ a\\\\ good\\ asymptotic\\ approximation\\ of\\ \u03c0\\ 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\u22121" .


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

"q_n \u223c nlog\\ n\\\\\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\u00d710^{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\\\\\n\\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}\\\\\nWhich\\ can\\ be\\ bounded\\ by;\\\\\n\\sum_{p}log\\ p\\sum_{k=2}^N \\frac{1}{p^k} \\leq 2 \\sum \\frac{log\\ p}{p^2}<\\infty\\\\\nHence\\\\\n\\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 \u223c nlog\\ n\\\\"

(e) Let "\\widetilde \u03c0(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 \u03c0(N)" , i.e. the prime number theorem for "random\\ primes."


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS