Saturday, August 21, 2010

The Girl Who Played with… Euclid’s perfect theorem:

Like most of the northern hemisphere, I’m in the middle of reading Stieg Larsson’s books “The Girl with the Dragon Tatoo” series. In the second volume, (“The Girl who Played with Fire”) our heroine, the punked out antisocial hacker, Lisbeth Salander, gets absorbed in recreational mathematics.

Now, in almost any popular novel, when the author starts delving into math, I am usually pretty familiar with whatever theorem, or unproven conjecture the author is mentioning -- frequently much more so than the author. I applaud the attempt to bring more science into popular fiction, but I don’t usually learn much from it.

However, on page 21 of the “The Girl who Played with Fire” the author mentions an ancient – and very beautiful! – theorem by Euclid, which rather shockingly I had never seen before. (A major gap in my education!) I scratched my head for a moment, then figured out Euclid’s proof (despite the fact that Lisbeth Salander sort of gets it wrong).

First of all: Here is the statement in the novel:

She was fascinated by Euclid’s discovery in about 300 B. C. that a perfect number is always a multiple of two numbers, in which one number is a power of 2 and the second consists of the different the difference between the next power of 2 and 1. This was a refinement of Pythagoras’ equation and she could see the endless combinations

 6 = 2^1 ( 2^2 -1) 28 = 2^2 \times ( 2^3-1) 496 = 2^4 \times( 2^5-1) 8128 = 2^6 \times ( 2^7 -1)

She could go on indefinitely without finding any numbers that would break the rule.

(Yes, Larsson likes to write in Italics). OK, now the proper statement of the theorem.

Definition: A perfect number is a number where the sum of the number's factors adds up to the number itself. For example:

The factors of 6 are 1, 2 and 3. 1+2+3 = 6 so 6 is a perfect number.
The factors of 28 are 1,2,4,7,14. 1+2+4+7+14=28 so 28 is a perfect number
and so forth.

Euclid’s theorem: IF  (2^k-1)  is a prime number THEN 2^{k-1}\times (2^k-1)  is a perfect number.

Salander does not mention the IF required of this theorem, but note that on her list of perfect numbers, she lists k=2,3,5,7 which are cases where  (2^k-1)  is prime. This type of prime is known as a Mersenne Prime]. How Euclid proved this theorem is beyond me. He was brilliant, but he did everything with geometry – and very little algebra (which is how I intend to prove it).

Almost 2000 years after Euclid’s proof, Euler proved that if an even number is perfect, then it is the form given by Euclid’s theorem. It is still not known if any odd perfect numbers exist --- although if they do exist they have to be ginormous since it has been proven that no odd perfect numbers exist less than 10^{300} . Assuming there are no odd perfect numbers, then there is exactly one perfect number for each Mersenne prime. It is not known how many of these there are.

OK, a quick proof of Euclid’s theorem: Consider the number  2^{k-1} (2^k-1) . If  p = (2^k-1)  is prime, then the only factors of  (2^{k-1})p  are

 1,2,4, \ldots, 2^{k-1}

and

 p,2p,4p, \ldots, 2^{k-2}p .

Now the sum of the series

 1 + 2 + 4 +\ldots, + 2^{k-1} = 2^k -1

And similarly

 p + 2p + 4 p + \ldots + 2^{k-2}p = p ( 1 + 2 + 4 + \ldots 2^{k-2}) = p(2^{k-1} -1)

So the sum of all the factors of the number gives

 (2^k-1) + p(2^{k-1}-1) = (2^k-1) + (2^k-1)(2^{k-1}-1) = 2^k(2^{k-1}-1)
which is the number itself!