Tag Archives: Prime number theorem

Applying the Explicit Formula

It's quite some time since we arrived at Riemann's main result, the explicit formula

J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2,

where J(x) is the prime power counting function introduced even earlier. It's high time we applied this!

First, let's take a look at J(x) when calculating it exactly:

J(x) Continue reading Applying the Explicit Formula

Are Primes Independent?

The question may sound silly, but I hope it will become apparent that it's very reasonable to ask. What we will examine here is the probabilistic interpretation of the prime distribution. So, essentially we ask: "What's the probability that a randomly chosen number is prime?" Those familiar with some basic probability theory know the notion of independency in this context, so the question I'm basically interested in here is if the probability to find a prime is independent of the preceding or following numbers. This post is a little out of the regular narrative, but it's something I have been thinking about recently, and I think it makes a cute article.

But one step back. First consider the following problem: We pick a number X not exceeding some (large) n at random. What are the odds this number is prime? Well, this is a classic example of a discrete probability, so the answer is positive cases over all cases, i.e.,

P(X\in\mathbb{P})=\frac{\pi(n)}{n},

where \mathbb{P} denotes the set of all primes, and \pi(n) is the prime counting function, i.e., the number of primes not exceeding n. Now, the famous Prime Number Theorem states that we can approximate \pi(n) with the elementary function

\pi(n)\sim\frac{n}{\log n}.

Don't worry too much about the exact meaning of the tilde, we will have plenty of opportunity to examine it further. For now just read it as "the left-hand side behaves similarly to the right-hand side". Now we can substitute this approximation in the calculation of the probability above, and obtain

P(X\in\mathbb{P})\sim\frac{n/\log n}{n}=\frac{1}{\log n}.

Continue reading Are Primes Independent?