thesublimeblog

Science Bytes: Prime Attraction

I have long been fascinated by prime numbers. A prime number is a whole number greater than 1 whose only factors are 1 and itself. Examples of primes are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29. Like stars on the night sky, prime numbers are ubiquitous (as far as we known, there is an infinite number of them). At the same time, some prime numbers (known as Mersenne primes) are extremely rare and they give rise to so-called perfect numbers that seem to possess “mystical” properties.

I am also awed by the fact that prime numbers appear in so many disparate areas of number theory – objects like the Riemann zeta function and their modified versions, the Dirichlet L-functions, random matrix theory, elliptic curves (which became famous for its role in Andrew Wiles’ proof of the celebrated Fermat’s Last Theorem). The list goes on. The connections between these objects and prime numbers are deep and difficult territory (at least for me), so I will omit them from discussion. But demonstrating the infinity of prime numbers and how Mersenne primes are related to perfect numbers is relatively easy. These are topics I will dwell on in this post.

Euclid, Euler and Gauss had different proofs of the infinite number of prime numbers. Their proofs are surprisingly simple, but if forced to choose one, Euler’s is my favorite. I will begin with the Riemann zeta-function which plays a central role in the elusive and still unproven Riemann Hypothesis (named after the renowned German mathematician, Bernhard Riemann (1826 – 1866).

The Riemann zeta-function is the infinite series:

{\displaystyle \zeta(x) = 1+ \frac{1}{2^s} + \frac{1}{3^s} + ... =\sum\limits_{n=1}^{\infty} \frac{1}{n^s} \hspace{20em} (1) }

As you may have learnt from calculus, this series converges for every s > 1 and diverges for every s \leq 1 . The borderline case s = 1 is the well-known harmonic series, \sum\limits_{n=1}^{\infty} \frac{1}{n}

The connection between the zeta-function and prime numbers comes from another formula for \zeta(x) , derived by Euler in 1737. This is:

{\displaystyle \zeta(x) =\frac{1}{1-\frac {1}{2^s}} \times \frac{1}{1-\frac {1}{3^s}} \times \frac{1}{1-\frac {1}{5^s}} \times ... = \prod\limits_{p \, prime} =\frac{1}{1-\frac {1}{p^s}} \hspace{10em} (2) }

This expression is an infinite product rather than a sum, and the variable p runs through all prime numbers 2, 3, 5, 7, …

Equations (1) and (2) are equivalent analytically. To see this, we first expand the factor \frac {1}{1-\frac{1}{p^s}} via the formula for a geometric series:

\displaystyle { \frac{1}{1-\frac {1}{p^s}} = 1+ \frac{1}{p^s} + (\frac{1}{p^s})^2 + (\frac{1}{p^s})^3 +... = 1+ \frac{1}{p^s} + \frac{1}{(p^2)^s} + \frac{1}{(p^3)^s} + ... }

Then we multiply together these geometric series for all choices of p. To do this, we have to imagine every conceivable product of the terms \displaystyle {\frac {1}{{(p^k})^s} } for various primes p and exponents k. For example, one term that arises is

\displaystyle { \frac{1}{(3^2)^s} \times \frac{1}{13^s} = \frac{1}{117^s} }

which comes from the corresponding terms p = 3 and p = 13. More generally, it is easy to see that every product of terms will take the form \displaystyle {\frac{1}{n^s} } for some positive integer n. In fact, for every n, the term \displaystyle { \frac{1}{n^s} } will eventually appear once (and only once) because the prime factorization of n is unique.

All of these manipulations make sense and can be made completely rigorous whenever s > 1. Euler had the clever idea of letting s tend to 1, so that (1) tends to the harmonic series, which diverges. This in turn implies that (2) gets arbitrarily large as s gets close to 1. From this, Euler inferred that there must be infinitely many prime numbers, otherwise (2) would remain bounded even as s approaches 1. This clever proof may seem redundant, given that Euclid had already given an proof some 2000 years earlier. But mathematicians adore beauty of proof, and Euler’s proof is elegant and beautiful.

Okay, so there are an infinite number of prime numbers. Now comes a surprise in the form of a rare class of primes known as Mersenne primes, named after a French monk, who in 1644 predicted that {2^n} -1 is prime for a small set of prime numbers, namely n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257, and no other values of n less than 258. Mersenne was right for all but the last two numbers. He also omitted n = 61, 89 and 107 which do yield primes. Nevertheless, the name stuck!

Mersenne primes got a lot of attention because it turns out to be easier to find prime numbers among Mersenne primes {2^n} -1 , than for more general classes of numbers. In particular, if {2^n} -1 is prime, then n itself is prime. This is convenient since it helps weed out most of the non-primes [see Note 1]. There is a very fast algorithm known as the Lucas-Lehmer algorithm for testing the primality of {2^n} -1. [Note 2]

Another reason for studying Mersenne primes has to do with perfect numbers. For every Mersenne prime p, there is an even perfect number computed as p(p+1)/2. For example, consider 7 (which is a Mersenne prime). The corresponding perfect number is 7 x 8/2 = 28. What’s special about 28 is that: (1) it is equal to the sum of its proper divisors. That is, 28 = 1 + 2+ 4 + 7 + 14 and (2) it is also the sum of the first 7 integers: 28 = 1 + 2 + 3…+7! No wonder that ancient mathematicians regarded these numbers as mystical and thus call them “perfect”.

In general, every Mersenne prime gives rise to an even perfect number. The fabulous Euler proved that the converse is also true (every even perfect number is produced by a Mersenne prime). In other words, there is a direct correspondence between Mersenne primes and even perfect numbers. Two interesting questions can be asked. First, how many even perfect numbers exist? Answer: we don’t know, because as of now, we don’t know whether there are infinitely many Mersenne primes. In fact, only 51 Mersenne primes have been found so far by a global community of math enthusiasts (see https://www.mersenne.org/ ). Second, are there odd perfect numbers? Again, we don’t know. In fact, the Odd Perfect Number Conjecture is one problem that has escaped proof for centuries [3]. Perhaps, there are things nature prefers to keep as eternal secrets.

Notes
[1] This test works only one way. That is, n prime does not guarantee a Mersenne prime. As as example, it is easy to verify that this is true for n = 11.

[2] http://mathworld.wolfram.com/Lucas-LehmerTest.html

3] https://blogs.ams.org/mathgradblog/2013/07/25/odd-perfect-numbers-exist/


Leave a Reply