Notes on perfect numbers

This is cross-posted from Tumblr. If you view it on Tumblr, the equations will look nicer.

[The first few paragraphs of this post provide some background, but, if you want, you can skip ahead to the discussion of perfect numbers; the only thing you need to know for that discussion is that for every positive integer n, σ(n) is the sum of the positive factors of n, and σ is multiplicative: for every pair of integers a and b which are coprime, i.e. the only positive factor they share is 1, σ(ab) = σ(a)σ(b). In this section, I use the concept of a multiset, which is like a set, but can contain multiple instances of objects, because it makes it easier to reason about prime factorisations. For every multiset S and every object x, the number of instances of x in S is called the multiplicity of x in S and denoted [xS]. A submultiset of S is a multiset T such that for every object x, [xT] ≤ [xS]; if T is a submultiset of S we write TS. For every pair of submultisets S and T, the sum of S and T, denoted S + T, is the multiset U such that for every object x, xU] = [xS] + [xT].]

From the prime factorisation of a positive integer, it is possible to determine its factors in general. Suppose n and d are positive integers and N and D are their respective prime factorisations. Then d ∣ n if and only if DN. This is because for every positive integer q, if we let Q be the prime factorisation of q, then n = q d if and only if N = P + Q. Therefore, the number of positive factors that n possesses, which is denoted τ(n), is the number of submultisets that N possesses, i.e.

\tau(n) = \prod_{p \text{ prime}} \left( [p \in P] + 1 \right).

It is easy to see from this formula that the function τ is multiplicative. Another consequence of the determination of the positive factors of n by the prime factorisation of n is that the sum of the positive factors of n, which is denoted σ(n), is given by the formula

\sigma(n) = \sum_{D \subseteq N} \prod_{p \text{ prime}} p^{[p \in D]}

which can be rewritten as

\sigma(n) = \prod_{p \text{ prime}} \sum_{\alpha = 0}^{[p \in N]} p^{\alpha},

which in turn can be rewritten, using the formula for the sum of a geometric series, as

\sigma(n) = \prod_{p \text{ prime}} \frac {p^{[p \in N] + 1} - 1} {p - 1}.

It is easy to see from this formula that σ is multiplicative. It is also easy to see, just from the definition of σ, that if n ≠ 1, then n + 1 ≤ σ(n), because 1 and n are both factors of n, and, furthemore, σ(n) = n + 1 if and only if n is prime. In investigations of the values that σ takes it is therefore useful to consider instead the sum of the proper positive factors of n, which is denoted s(n) and is equal to σ(n) − n, because the infimum of the value taken by s(n) is not dependent on n. Some numbers are invariant under s, e.g. 6 (because s(6) = 1 + 2 + 3 = 6) and 28 (because s(28) = 1 + 2 + 4 + 7 + 14 = 28). The invariants under s are called the perfect numbers. Equivalently, perfect numbers are positive integers n such that σ(n) = 2n.

Perfect numbers have been a topic of great interest since ancient times, despite their almost total lack of practical applications or theoretical significance. Despite their having been studied since ancient times, there are still very basic questions about perfect numbers which remain unanswered. For example, every known perfect number is even, but it is not known whether there are any odd perfect numbers. Even if there are no odd perfect numbers, it is still not known whether there are infinitely many even perfect numbers.

There is, however, a significant and non-obvious result which we can prove concerning the even perfect numbers. Every even positive integer n is of the form 2am where 1 ≤ a and m is odd, and, therefore, by the multiplicativity of σ, σ(n) = (2a + 1 − 1) σ(m), while 2n = 2a + 1m. Hence, n is perfect if and only if

(2^{a + 1} - 1) \sigma(m) = 2^{a + 1} m,

in which case, since 2a + 1 − 1 is odd, 2a + 1 − 1 is a factor of m. Therefore, there is an integer k such that m = k(2a + 1 − 1). So we can divide both sides by 2a + 1, yielding

\sigma(m) = 2^{a + 1} k.

Note also that, expanding the equation for m, we have m = 2a + 1kk and hence m + k = 2a + 1k, i.e. m + k = σ(m). Now, m and k are both positive factors of m, and they are distinct, because, since 1 ≤ a1, 1 < 2a + 1 − 1, and hence k < m. Since σ(m) is the sum of all the positive factors of m it follows that k and m are the only two positive factors of m. But 1 is also a positive factor of m, so one of these must be equal to 1. k is the smaller one, so it is k which is equal to 1. Hence m is prime, m = 2a + 1 − 1 and n = 2a(2a + 1 − 1). Therefore, the even perfect numbers are those of the form 2a(2a + 1 − 1), where 2a + 1 − 1 is prime. Indeed, for every number n of this form we have

\begin{array}{rcl}  \sigma(n) &=& \sigma \left( 2^a \left( 2^{a + 1} - 1 \right) \right) \\  &=& \sigma \left( 2^a \right) \sigma \left( 2^{a + 1} - 1 \right) \\  &=& \left( 2^{a + 1} - 1 \right) \left( 1 + \left( 2^{a + 1} - 1 \right) \right) \\  &=& \left( 2^{a + 1} - 1 \right) 2^{a + 1} \\  &=& 2 n,  \end{array}

so n is perfect.

Prime numbers of the form 2a + 1 − 1, where a is a non-negative integer, are called Mersenne prime numbers. Note that 2a + 1 − 1 = 1 + 2 + 4 + &cdots; + 2a, so another nice characterisation of the Mersenne prime numbers is that they are the prime numbers whose binary expansions contain only the digit 1. For every Mersenne prime number 2a + 1 − 1, if we let p = 2a + 1 − 1, rearranging yields 2a + 1 = p + 1, and hence another way of stating this characterisation of the even perfect numbers is that the even perfect numbers are those of the form p (p + 1)/2 where p is a Mersenne prime number. p (p + 1)/2 is the pth triangular number, so, equivalently, the even perfect numbers are those numbers n such that n points can be arranged into an equilateral triangle with a Mersenne prime number of points along each side.

Unfortunately, the Mersenne prime numbers are not much less mysterious than the perfect numbers. For example, it is not known whether there are infinitely many Mersenne prime numbers, and hence it is not known whether there are infinitely many perfect numbers. But there is one thing we can say about Mersenne prime numbers. For every Mersenne prime number 2a + 1 − 1, a + 1 is prime, because for every positive factor d of a + 1, there is a positive integer k such that a + 1 = kd, hence

\begin{array}{rcl}  2^{a + 1} - 1 &=& 2^{k d} - 1 \\  &=& \left( 2^d \right)^k - 1 \\  &=& \left( 2^d - 1 \right) \left( 1 + 2^d + \left( 2^d \right)^2 + \dotsb + \left( 2^d \right)^k \right),  \end{array}

so 2d − 1 is a positive factor of 2a + 1 − 1. Since 2a + 1 − 1 is prime, it follows that 2d − 1 is either 1 or 2a + 1 − 1. In the former case, we have 2d = 2, hence d = 1. In the latter case, we have 2d = 2a + 1, hence d = a + 1.

This result means that there are less computations we need to make when searching for the even perfect numbers. We only need to see which of the numbers of the form 2p − 1, where p is a prime number, are Mersenne prime numbers. If 2p − 1 is a Mersenne prime, then 2p − 1 (2p − 1) is perfect. Let’s use this strategy to find the first few even perfect numbers.

p 2p − 1 Is 2p − 1 prime? If so, what is 2p − 1 (2p − 1)?
2 4 − 1 = 3 Yes 2 ⋅ 3 = 6
3 8 − 1 = 7 Yes 4 ⋅ 7 = 28
5 32 − 1 = 31 Yes 16 ⋅ 31 = 496
7 128 − 1 = 127 Yes 64 ⋅ 127 = 8128
11 2048 − 1 = 2047 No (2047 = 23 ⋅ 89)
13 8192 − 1 = 8191 Yes 4096 ⋅ 8191 = 33550336

The first 5 even perfect numbers are, therefore, 6, 28, 496, 8128 and 33550336. Note that 211 − 1 is not prime, so checking that each of these numbers, is, in fact, prime is essential. In fact, the start of this list gives you a misleading impression that for most prime numbers p, 2p − 1 is Mersenne prime. But in fact this is increasingly less likely as p gets larger. So far, people have checked the primality of every number of the form 2p − 1 where 1 ≤ p ≤ 43112609, and found that only 47 of these 43112609 numbers are Mersenne prime. (A 48th Mersenne prime number is also known, 257885161 − 1, which is the largest known Mersenne prime number and in fact the largest known prime number in general, but not all of the numbers 2p − 1, where 43112609 < p < 57885161, have been checked for primality.)

As for the odd perfect numbers, lots of conditions have been found that every odd perfect number must satisfy; for example, every odd perfect number must have at least 1500 digits in its decimal expansion. J. J. Sylvester opined that it seemed unlikely that a number could exist satisfying all of these conditions; however, the people at OddPerfect.org, at least, aren’t convinced. I might do a post in future about the question of whether there are odd perfect numbers; at the moment, however, I don’t have any idea whether it is likely or not.

Advertisements

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