Euclid, from Rafael’s “School of Athens”, Vatican Museum, Rome, photo courtesy Clay Mathematics Institute
Perfect numbers
A perfect number is a positive integer whose divisors (not including itself) add up to the integer. The smallest perfect number is $6$, since $6 = 1 + 2 + 3$. The next is $28 = 1 + 2 + 4 + 7 + 14$, followed by $496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248$ and $8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64$ $+ 127 + 254 + 508 + 1016 + 2032 + 4064$.
The notion of a perfect number is at least 2300 years old. In approximately 300 BCE, Euclid showed (using modern notation) that if $2^p – 1$ is a prime number (which implies, by the way, that $p$ itself is prime), then $2^{p-1} (2^p – 1)$ is a perfect number. For example, when $p = 5$, we have $2^5 – 1 = 31$, which is prime, and $2^4 (2^5 – 1) = 16 \cdot 31 = 496$ is perfect. In approximately 100 CE, the Greek mathematician Nicomachus noted that 8128 is a perfect number, and stated, without proof, that every perfect number is of the form $2^{n-1} (2^n – 1)$ (also omitting the clear condition that $n$ must be prime). In the first century CE, the Hebrew theologian Philo of Alexandria asserted that Earth was created in $6$ days and the moon orbits Earth in $28$ days, since $6$ and $28$ are perfect. In the early fifth century CE, the Christian theologian Augustine of Hippo repeated the assertion that God created Earth in $6$ days because $6$ is the smallest perfect number.
In the 12th century, the Egyptian mathematician Ismail ibn Fallūs calculated the 5th, 6th and 7th perfect numbers $(33550336, 8589869056$ and $137438691328$), plus some additional ones that are incorrect. The first known mention of the 5th perfect number in European history is in a manuscript written by an unknown writer between 1456 and 1461. The 6th and 7th were identified by the Italian mathematician Pietro Cataldi in 1588; he also proved that every perfect number obtained using Euclid’s formula ends in $6$ or $8$.
In the 18th century, Euler proved that Euclid’s formula $2^{p-1} (2^p – 1)$, for prime $2^p – 1$, yields all even perfect numbers. He also introduced the $\sigma (N)$ notation (also known as the divisor function) for the sum of the divisors of $N$, including $N$ itself. Thus we may write his result as follows: If $N$ is a positive even integer, then $\sigma(N) = 2N$ (i.e., $N$ is perfect) if and only if $N = 2^{p-1} (2^p – 1)$ for some prime of the form $2^p – 1$. This result is now known as the Euclid-Euler theorem. For additional history and background on perfect numbers, see this Wikipedia article.
Odd perfect numbers
The Euclid-Euler theorem pretty well wrapped up the case for even perfect numbers. But what about odd perfect numbers (OPNs)? Do any such integers exist? This question has remained stubbornly unanswered for centuries. Numerous restrictions are known on the properties of any possible OPN, with more restrictions being proved with every passing year. Present-day mathematicians echo the sentiment of James Sylvester, who wrote
a prolonged meditation on the subject has satisfied me that the existence of any one such [odd perfect number] — its escape, so to say, from the complex web of conditions which hem it in on all sides — would be little short of a miracle.
Here are some of the known restrictions on any possible OPN $N$, listed in roughly chronological order:
- $N$ must not be divisible by 105 (Sylvester, 1888).
- If $N$ is not divisible by $3, 5$ or $7$, it must have at least $27$ prime factors (Norton, 1960).
- $N$ must have at least seven distinct prime factors (Pomerance, 1974).
- $N$ must have at least $75$ prime factors and at least $9$ distinct prime factors (Hare, 2005 and Nielsen, 2006). This was later extended to $101$ prime factors (Ochem and Rao, 2012).
- $N$ must be congruent to either $1 (\bmod 12)$ or $117 (\bmod 468)$ or $81 (\bmod 324)$ (Roberts, 2008).
- The largest prime factor $p$ of $N$ must satisfy $p > 10^8$ (Goto and Ohno, 2008).
- $N \gt 10^{1500}$ (Ochem and Rao, 2012).
(See this MathWorld article for references to these and other items.)
Spoof odd perfect numbers
Recently mathematicians have taken a slightly different tack on the problem — searching for spoof odd perfect numbers, namely integers that resemble odd perfect numbers but don’t quite meet all the requirements. There is historical precedent here: in 1638 Rene Descartes observed that $198585576189 = 3^2 \cdot 7^2 \cdot 11^2 \cdot 13^2 \cdot 22021$ almost satisfies Euclid’s formula.
To see this, first note two properties of the sigma function: (a) $\sigma(pq) = \sigma(p)\sigma(q)$, if $p$ and $q$ are relatively prime; and (b) $\sigma(p^m) = 1 + p + p^2 + \cdots p^m$ if $p$ is prime and $m \gt 0$. With regards to Descartes’ number, one might be tempted to write $$\hat{\sigma}(198585576189) = \sigma(3^2) \sigma(7^2) \sigma(11^2) \sigma(13^2) \sigma(22021)$$ $$= (1 + 3 + 3^2)(1 + 7 + 7^2) (1 + 11 + 11^2) (1 + 13 + 13^2) (1 + 22021) = 397171152378 = 2 \cdot 198585576189.$$ However, this calculation is incorrect, since $22021$ is not prime; in fact $\sigma(22021) = 23622$, not $22022$ as in the above. Thus the above calculation, which appears at first glance to certify that $198585576189$ is an OPN, is invalid. The correct sigma value for Descartes’ number is $\sigma(198585576189) = 426027470778$.
In 1999, John Voight of Dartmouth University discovered a different variety of spoof odd perfect number: $−22017975903 = 3^4 \cdot 7^2 \cdot 11^2 \cdot 19^2 \cdot (−127)$. Here again one might be tempted to write $$\hat{\sigma}(−22017975903) = \sigma(3^4) \sigma(7^2) \sigma(11^2) \sigma(19^2) \sigma(-127)$$ $$= (1 + 3 + 3^2 + 3^3 + 3^4) (1 + 7 + 7^2) (1 + 11 + 11^2) (1 + 19 + 19^2) (1 + (-127)) = -44035915806 = 2 \cdot (−22017975903).$$ But again, this calculation is invalid, in this case because the integer in question is negative, and $\sigma(-127) = -128$ not $-126$ as used above. But in both cases, these “spoofs” are definitely interesting, and possibly might inspire a line of attack to certify that OPNs simply cannot exist.
Computer searches
The most recent development here is due to a team led by Pace Nielsen and Paul Jenkins of Brigham Young University, subsequently joined by Michael Griffin and Nick Andersen, who embarked on a computer search for additional spoof odd perfect numbers. After roughly 60 CPU-years of computing, the team found 21 spoofs with six or fewer prime bases. Here the team relaxed the criteria in several ways, allowing non-prime bases (as with Descartes), negative bases (as with Voight), and also spoofs whose bases share the same prime factors (by the rules, a given prime may appear only once in the factorization list).
Why the interest in spoofs? According to Nielsen,
Any behavior of the larger set has to hold for the smaller subset. … So if we find any behaviors of spoofs that do not apply to the more restricted class, we can automatically rule out the possibility of an OPN.
So far, they have discovered some interesting facts about the spoofs, but none of these properties would preclude the existence of real odd perfect numbers. For example, the team has found that every one of the 21 spoofs that they have uncovered, with the exception of Descartes’ example, has at least one negative base. If this numerical observation could be proven, then this would prove that no odd perfect numbers exist, since by definition the bases of odd perfect numbers must be both positive and prime numbers.
So the search continues. Will this approach work? Voight, for instance, is not sure that even with the BYU team’s result that we are close to a final attack on the problem. Paul Pollack of the University of Georgia adds,
It would be great if we could stare at the list of spoofs and see some property and somehow prove there are no OPNs with that property. That would be a beautiful dream if it works, but it seems too good to be true.
For additional details and background, see this Quanta article by Steve Nadis, from which some of the above information was taken.