The private life of numbers (3): perfect numbers

This is Part 3 of a set of three posts adapted from Mateja Prešern’s talk at The Burn in November 2011.

In Part 2 we looked briefly at various sets of numbers, culminating in happy numbers. In this final post, we’ll look in more detail at one particular set: perfect numbers. We’ll even prove a nice theorem about them…

First, a bit of history. The first studies of perfect numbers may go back to the earliest times when numbers first aroused curiosity. It is quite likely, although not certain, that the Egyptians would have come across perfect numbers, but the first evidence we have comes from ancient Greece.

The Greek mystic and philosopher Pythagoras and his followers considered it rather remarkable that the number 6 is equal to the sum of its positive divisors, other than itself:

6=1+2+3.

The next number with this feature is 28:

28=1+2+4+7+14.

By the way, Pythagoras is also credited with one of the first statements against the exploitation of animals:

As long as men massacre animals, they will kill each other. Indeed, he who sows the seeds of murder and pain cannot reap the joy of love.

Pythagoras wasn’t the only person to find perfect numbers compelling, though. The 4th-century philosopher Saint Augustine was impressed enough to draw a theological conclusion:

Six is a number perfect in itself, and not because God created all things in six days; rather, the converse is true. God created all things in six days because the number is perfect…

Similarly, in Jewish mysticism, it was because 28 was a perfect number that the mystics believed that God chose it as the number of days that it takes the Moon to travel round the Earth.

Mathematicians, not generally being satisfied with isolated facts, were less impressed than the mystics by the individual numbers 6 and 28, and started to ask whether there was a recipe for producing further perfect numbers. The first progress in this direction is recorded in the Elements of Euclid, in about 300BC:

If as many numbers as we please beginning from a unit be set out continuously in double proportion, until the sum of all becomes a prime, and if the sum multiplied into the last make some number, the product will be perfect.

To illustrate this Proposition, consider 1 + 2 + 4 = 7, which is prime. Then

\mbox{(the sum)} \times \mbox{(the last)} = 7 \times 4 = 28,

which is a perfect number. The next time you get a prime by adding up powers of 2 is 1 + 2 + 4 + 8 + 16 = 31; multiply 31 by 16 and you get 496, the third perfect number. But can every perfect number be discovered this way? It wasn’t until nearly 2000 years later that mathematicians were able to give a partial answer to this!

Perfect numbers and Mersenne primes

Around 1640, both Descartes and Fermat wrote to the French monk Mersenne suggesting that every perfect number must come from the primes related to powers of 2. Although Mersenne is best known for publicising and sharing discoveries rather than making them — Marcus du Sautoy calls him a “medieval internet hub” — it is his name that is now given to these primes.  Mersenne numbers are numbers of the form

M=2^n-1, \qquad n\geq 1.

Those Mersenne numbers that happen to be prime are called Mersenne primes.

It was Leonhard Euler who showed that all the even perfect numbers are of Euclid’s form. To follow this proof, we need to define an arithmetic function, the divisor function \sigma(n).

\sigma(n) := the sum of positive divisors of n,

\mbox{i.e.} \qquad \sigma(n) = \displaystyle\sum_{d|n}d.

We also need a definition. A function f is said to be multiplicative if

f(m)f(n) = f(mn) for all m,n \in\mathbb{N} such that \mathrm{gcd}(m,n)=1.

Before continuing, you should satisfy yourself that \sigma(n) is multiplicative in this sense!

If f is multiplicative, and if we write a given number n in terms of its prime factors as

n = p_1^{\alpha_1}p_2^{\alpha_2}\ldots p_r^{\alpha_r} = \displaystyle\prod_{i=1}^rp_i^{\alpha_i},

then clearly

f(n) = f\left(\displaystyle\prod_{i=1}^rp_i^{\alpha_i}\right) = \displaystyle\prod_{i=1}^rf\left(p_i^{\alpha_i}\right).

We can see that

\sigma(p^\alpha) = 1 + p + \cdots + p^{\alpha} = \displaystyle\frac{p^{\alpha+1}-1}{p-1},

and hence

\sigma(n) = \displaystyle\prod_{i=1}^r\displaystyle\frac{p_i^{\alpha_i+1}-1}{p_i-1}.

We can now return to perfect numbers, with this formal machinery to help us…

Definition. A positive integer n is said to be perfect if n is equal to the sum of all its positive divisors, excluding itself (in more old-fashioned language, n is the sum of its aliquot parts, or proper divisors), i.e.

\sigma(n) = 2n.

(The integer n is called abundant if \sigma(n) > 2n and deficient if \sigma(n) < 2n.)

By means of these conditions one can check whether a number is perfect:

\sigma(6)= \sigma(2\cdot 3) = \sigma(2)\cdot\sigma(3) = (2^0+2^1)(3^0+3^1) = 3\cdot4 = 12.

\sigma(28) = \sigma(2^2\cdot 7) = (1+2+4)(1+7) = 7\cdot8 = 56.

\sigma(200) = \sigma(2^3\cdot 5^2) = (1+2+4+8)(1+5+25) = 15\cdot31 = 465.

Theorem. (i) If 2^{k}-1 is prime, then 2^{k-1}(2^k-1) is perfect; and (ii) every even perfect number is of this form.

Proof. We’ll do this in two parts.

(i) First, let 2^k-1 = p be a prime. We want to show that n = 2^{k-1}p is perfect.

Since \mathrm{gcd}\left(2^{k-1},p\right)=1 and \sigma is multiplicative,

\sigma(n) = \sigma(2^{k-1}p) = \sigma(2^{k-1})\sigma(p) = (2^k-1)(p+1) = (2^k-1)2^k = 2n,

making n a perfect number. (That was the easy part!)

(ii) Now we want to prove the converse. We now assume that n is an even perfect number. Write n=2^{k-1}m, where m is odd and k\geq 2. Then

\sigma(n) = \sigma(2^{k-1})\sigma(m)= (2^k-1)\sigma(m).

Since \sigma(n)=2n, we have

(2^k-1)\sigma(m) = 2\cdot 2^{k-1}m = 2^km.

Now write \sigma_0(m) for the sum of proper divisors of m, so \sigma_0(m)=\sigma(m)-m. Then the equation above becomes

(2^k-1)(\sigma_0(m)+m) = 2^km, \qquad \mbox{i.e.}\qquad (2^k-1)\sigma_0(m)=m.

This implies that \sigma_0(m) is a proper divisor of m (that is, \sigma_0(m)|m and \sigma_0(m)<m). On the other hand, \sigma_0(m) was the sum of all proper divisors of m (including \sigma_0(m) itself), so there cannot be any other proper divisors besides \sigma_0(m). Thus \sigma_0(m)=1 and m=2^k-1 is a prime number.

Thus the even perfect number n=2^{k-1}m is of Euclid’s type, as required. 8)

Incorrect guesses and open questions

Only four perfect numbers were known to the ancient Greeks. Nicomachus in his Introductio Arithmeticae (circa 100 AD) lists P_1=6, P_2=28, P_3=496 and P_4=8128. He says that they are formed in an “orderly” fashion, one among the units, one among the tens, one among the hundreds, and one among the thousands. He conjectured:

(i) The r-th perfect number contains exactly r digits.

(ii) The even perfect numbers end, alternately, in 6 and 8.

In fact, both conjectures are wrong. There is no perfect number with 5 digits; the next perfect number (given correctly in an anonymous 15th century manuscript) is P_5=33 550 336. And although the final digit of P_5 is indeed 6, the succeeding perfect number also ends in 6, P_6=8 589 869 056.

However, the following theorem does hold.

Theorem. An even perfect number n ends in the digit 6 or 8.

(If you know of a neat proof for this then let us know!)

Finally, two questions that have remained open for a very long time.

The number of digits in the largest known Mersenne prime, by year. Note the log scale!

Are there infinitely many perfect numbers? Whenever a new Mersenne prime is discovered it leads to the discovery of a new perfect number. So far we have discovered 47 perfect numbers, the largest of which has nearly 26 million digits, and the unfortunately-named GIMPS project continues to search for more. Are there infinitely many of them? Or is the 47th perfect number the last one? Nobody (yet) knows…

Are there any odd perfect numbers? It is not known if there are any odd perfect numbers, but there are certainly no odd perfect numbers smaller than 10^{400}. Indeed most mathematicians believe none exists… but the history of perfect numbers is so strewn with incorrect guesses that maybe it would be sensible to keep an open mind for now…

A closing thought from Marcus du Sautoy (The Times, 1 July 2009):

As a mathematician I was beginning to feel a bit left out. We got Pi Day, which we celebrate on March 14, but how about adding a World Maths Day to the June calendar? On Sunday, when I looked at the date, it suddenly dawned on me why 28/6 would be the pefect day to celebrate World Maths Day — literally the perfect day because 28 and 6 are what mathematicians call perfect numbers.

If you’re planning a Perfect Day party,  do let us know!

(MG/DP)

Advertisements
This entry was posted in Articles. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s