Tag Archives: Gauss

Primes from a Different World

Every textbook on number theory will begin with a treatise on prime numbers; every treatise on prime numbers will begin by emphasising their importance as building blocks or atoms of our number system: every integer can be expressed as a product of prime numbers in one way and one way only. Six is two times three and there is no other way to decompose it.1 Euclid proved this over two thousand years ago and it is so fundamental (hence the name fundamental theorem of arithmetic) to our thinking about numbers that we take it for granted. It is not!

There are numbers that behave very much like the integers but have a different structure. One rather simple example are the Gaussian integers (usually denoted \mathbb Z[i]) which look just like complex numbers z=x+iy, except that x and y are restricted to integer values. They live in the complex plane, but exclusively on a discrete grid amongst their continuous cousins.

Gaussian_integer_lattice.svg Continue reading Primes from a Different World


  1. Yes, you can write 12 as 3*4 or 2*6, but you can continue either way and eventually reach the unambiguous 2*2*3. 

Integral Madness

We've seen the calculus version

J(x)=\frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\log\zeta(s)x^s\frac{\mathrm{d}s}{s},

of the Euler product, and we know how to express \xi(s) as a product over its roots

\xi(s)=\xi(0)\prod_\varrho\left(1-\frac{s}{\varrho}\right),

where

\begin{align}\xi(s)&=\frac{1}{2}\pi^{-s/2}s(s-1)\Pi(s/2-1)\zeta(s)\nonumber\\&=\pi^{-s/2}(s-1)\Pi(s/2)\zeta(s).\nonumber\end{align}

High time we put everything together -- the reward will be the long expected explicit formula for counting primes! Continue reading Integral Madness

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?