number theory

Mathematicians Open a New Front on an Ancient Number Problem

For millennia, mathematicians have wondered whether odd perfect numbers exist, establishing an extraordinary list of restrictions for the hypothetical objects in the process. Insight on this question could come from studying the next best things.
A comically long “missing persons” poster for an odd perfect number that shows all the restrictions it has to satisfy.

If odd perfect numbers do exist, they’ll need to satisfy an increasingly absurd number of restrictions.

Jason Chuang for Quanta Magazine

As a high school student in the mid-1990s, Pace Nielsen encountered a mathematical question that he’s still struggling with to this day. But he doesn’t feel bad: The problem that captivated him, called the odd perfect number conjecture, has been around for more than 2,000 years, making it one of the oldest unsolved problems in mathematics.

Part of this problem’s long-standing allure stems from the simplicity of the underlying concept: A number is perfect if it is a positive integer, n, whose divisors add up to exactly twice the number itself, 2n. The first and simplest example is 6, since its divisors — 1, 2, 3 and 6 — add up to 12, or 2 times 6. Then comes 28, whose divisors of 1, 2, 4, 7, 14 and 28 add up to 56. The next examples are 496 and 8,128.

Leonhard Euler formalized this definition in the 1700s with the introduction of his sigma (σ) function, which sums the divisors of a number. Thus, for perfect numbers, σ(n) = 2n.

But Pythagoras was aware of perfect numbers back in 500 BCE, and two centuries later Euclid devised a formula for generating even perfect numbers. He showed that if p and 2p − 1 are prime numbers (whose only divisors are 1 and themselves), then 2p−1 × (2p − 1) is a perfect number. For example, if p is 2, the formula gives you 21 × (22 − 1) or 6, and if p is 3, you get 22 × (23 − 1) or 28 — the first two perfect numbers. Euler proved 2,000 years later that this formula actually generates every even perfect number, though it is still unknown whether the set of even perfect numbers is finite or infinite.

Nielsen, now a professor at Brigham Young University (BYU), was ensnared by a related question: Do any odd perfect numbers (OPNs) exist? The Greek mathematician Nicomachus declared around 100 CE that all perfect numbers must be even, but no one has ever proved that claim.

Like many of his 21st-century peers, Nielsen thinks there probably aren’t any OPNs. And, also like his peers, he does not believe a proof is within immediate reach. But last June he hit upon a new way of approaching the problem that might lead to more progress. It involves the closest thing to OPNs yet discovered.

A Tightening Web

Nielsen first learned about perfect numbers during a high school math competition. He delved into the literature, coming across a 1974 paper by Carl Pomerance, a mathematician now at Dartmouth College, which proved that any OPN must have at least seven distinct prime factors.

“Seeing that progress could be made on this problem gave me hope, in my naiveté, that maybe I could do something,” Nielsen said. “That motivated me to study number theory in college and try to move things forward.” His first paper on OPNs, published in 2003, placed further restrictions on these hypothetical numbers. He showed not only that the number of OPNs with k distinct prime factors is finite, as had been established by Leonard Dickson in 1913, but that the size of the number must be smaller than 24k.

These were neither the first nor the last restrictions established for the hypothetical OPNs. In 1888, for instance, James Sylvester proved that no OPN could be divisible by 105. In 1960, Karl K. Norton proved that if an OPN is not divisible by 3, 5 or 7, it must have at least 27 prime factors. Paul Jenkins, also at BYU, proved in 2003 that the largest prime factor of an OPN must exceed 10,000,000. Pascal Ochem and Michaël Rao have determined more recently that any OPN must be greater than 101500 (and then later pushed that number to 102000). Nielsen, for his part, showed in 2015 that an OPN must have a minimum of 10 distinct prime factors.

Even in the 19th century, enough constraints were in place to prompt Sylvester to conclude that “the existence of [an 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.” After more than a century of similar developments, the existence of OPNs looks even more dubious.

“Proving that something exists is easy if you can find just one example,” said John Voight, a professor of mathematics at Dartmouth. “But proving that something does not exist can be really hard.”

The main approach so far has been to look at all the conditions placed upon OPNs to see if at least two are incompatible — to show, in other words, that no number can satisfy both restriction A and restriction B. “The patchwork of conditions established so far makes it extremely unlikely that [an OPN] is out there,” Voight said, echoing Sylvester. “And Pace has, for a number of years, been adding to that list of conditions.”

Unfortunately, no incompatible properties have yet been found. So in addition to needing more restrictions on OPNs, mathematicians probably need new strategies, too.

To this end, Nielsen is already considering a new plan of attack based on a common tactic in mathematics: learning about one set of numbers by studying close relatives. With no OPNs to study directly, he and his team are instead analyzing “spoof” odd perfect numbers, which come very close to being OPNs but fall short in interesting ways.

Tantalizing Near Misses

The first spoof was found in 1638 by René Descartes — among the first prominent mathematicians to consider that OPNs might actually exist. “I believe that Descartes was trying to find an odd perfect number, and his calculations led him to the first spoof number,” said William Banks, a number theorist at the University of Missouri. Descartes apparently held out hope that the number he crafted could be modified to produce a genuine OPN.

But before we dive into Descartes’ spoof, it’s helpful to learn a little more about how mathematicians describe perfect numbers. A theorem dating back to Euclid states that any integer greater than 1 can be expressed as a product of prime factors, or bases, raised to the correct exponents. So we can write 1,260, for example, in terms of the following factorization: 1,260 = 22 × 32 × 51 × 71, rather than listing all 36 individual divisors.

If a number takes this form, it becomes much easier to calculate Euler’s sigma function summing its divisors, thanks to two relationships also proved by Euler. First, he demonstrated that σ(a × b) = σ(a) × σ(b), if and only if a and b are relatively prime (or coprime), meaning that they share no prime factors; for example, 14 (2 × 7) and 15 (3 × 5) are coprime. Second, he showed that for any prime number p with a positive integer exponent a, σ(pa) = 1 + p + p2 + … pa.

So, returning to our previous example, σ(1,260) = σ(22 × 32 × 51 × 71) = σ(22) × σ(32) × σ(51) × σ(71) = (1 + 2 + 22)(1 + 3 + 32)(1 + 5)(1 + 7) = 4,368. Note that σ(n), in this instance, is not 2n, which means 1,260 is not a perfect number.

Now we can examine Descartes’ spoof number, which is 198,585,576,189, or 32 × 72 × 112 × 132 × 22,0211. Repeating the above calculations, we find that σ(198,585,576,189) = σ(32 × 72 × 112 × 132 × 22,0211) = (1 + 3 + 32)(1 + 7 + 72)(1 + 11 + 112)(1 + 13 + 132)(1 + 22,0211) = 397,171,152,378. This happens to be twice the original number, which means it appears to be a real, live OPN — except for the fact that 22,021 is not actually prime.

That’s why Descartes’ number is a spoof: If we pretend that 22,021 is prime and apply Euler’s rules for the sigma function, Descartes’ number behaves just like a perfect number. But 22,021 is actually the product of 192 and 61. If Descartes’ number were correctly written as 32 × 72 × 112 ×132 × 192 × 611, then σ(n) would not equal 2n. By relaxing some of the normal rules, we end up with a number that appears to satisfy our requirements — and that’s the essence of a spoof.

It took 361 years for a second spoof OPN to come to light, this one thanks to Voight in 1999 (and published four years later). Why the long lag time? “Finding these spoof numbers is akin to finding odd perfect numbers; both are arithmetically complex in similar ways,” Banks said. Nor was it a priority for many mathematicians to look for them. But Voight was inspired by a passage in Richard Guy’s book Unsolved Problems in Number Theory, which sought more examples of spoofs. Voight gave it a try, eventually coming up with his spoof, 34 × 72 × 112 × 192 × (−127)1, or −22,017,975,903.

Unlike in Descartes’ example, all the divisors are prime numbers, but this time one of them is negative, which is what makes it a spoof rather than a true OPN.

After Voight gave a seminar at BYU in December 2016, he discussed this number with Nielsen, Jenkins and others. Shortly thereafter, the BYU team embarked on a systematic, computationally based search for more spoofs. They would choose the smallest base and exponent to start from, such as 32, and their computers would then sort through the options for any additional bases and exponents that would result in a spoof OPN. Nielsen assumed that the project would merely provide a stimulating research experience for students, but the analysis yielded more than he anticipated.

Sifting Through the Possibilities

After employing 20 parallel processors for three years, the team found all possible spoof numbers with factorizations of six or fewer bases — 21 spoofs altogether, including the Descartes and Voight examples — along with two spoof factorizations with seven bases. Searching for spoofs with even more bases would have been impractical — and extremely time-consuming — from a computational standpoint. Nevertheless, the group amassed a sufficient sample to discover some previously unknown properties of spoofs.

The group observed that for any fixed number of bases, k, there is a finite number of spoofs, consistent with Dickson’s 1913 result for full-fledged OPNs. “But if you let k go to infinity, the number of spoofs goes to infinity too,” Nielsen said. That was a surprise, he added, given that he didn’t know going into the project that it would turn up a single new odd spoof — let alone show that the number of them is infinite.

Another surprise stemmed from a result first proved by Euler, showing that all the prime bases of an OPN are raised to an even power except for one — called the Euler power — which has an odd exponent. Most mathematicians believe that the Euler power for OPNs is always 1, but the BYU team showed it can be arbitrarily large for spoofs.

Some of the “bounty” obtained by this team came from relaxing the definition of a spoof, as there are no ironclad mathematical rules defining them, except that they must satisfy the Euler relation, σ(n) = 2n. The BYU researchers allowed non-prime bases (as with the Descartes example) and negative bases (as with the Voight example). But they also bent the rules in other ways, concocting spoofs whose bases share prime factors: One base could be 72, for instance, and another 73, which are written separately rather than combined as 75. Or they had bases that repeat, as occurs in the spoof 32 × 72 × 72 × 131 × (−19)2. The 72 × 72 term could have been written as 74, but the latter would not have resulted in a spoof because the expansions of the modified sigma function are different.

Given the significant deviations between spoofs and OPNs, one might reasonably ask: How could the former prove helpful in the search for the latter?

A Path Forward?

In essence, spoof OPNs are generalizations of OPNs, Nielsen said. OPNs are a subset sitting within a broader family that includes spoofs, so an OPN must share every property of a spoof, while possessing additional properties that are even more restrictive (such as the stipulation that all bases must be prime).

“Any behavior of the larger set has to hold for the smaller subset,” Nielsen said. “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.” If one could show, for instance, that spoofs must be divisible by 105 — which can’t be true for OPNs (as Sylvester demonstrated in 1888) — then that would be it. Problem solved.

So far, though, they’ve had no such luck. “We’ve discovered new facts about spoofs, but none of them undercut the existence of OPNs,” Nielsen said, “although that possibility still remains.” Through further analysis of currently known spoofs, and perhaps by adding to that list in the future — both avenues of research established by his work — Nielsen and other mathematicians might uncover new properties of spoofs.

Banks thinks this approach is worth pursuing. “Investigating odd spoof numbers could be useful in understanding the structure of odd perfect numbers, if they exist,” he said. “And if odd perfect numbers don’t exist, the study of odd spoof numbers might lead to a proof of their nonexistence.”

Other OPN experts, including Voight and Jenkins, are less sanguine. The BYU team did “a great job,” Voight said, “but I’m not sure we’re any closer to having a line of attack on the OPN problem. It is indeed a problem for the ages, [and] perhaps it will remain so.”

Paul Pollack, a mathematician at the University of Georgia, is also cautious: “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.”

It is a long shot, Nielsen conceded, but if mathematicians are ever going to solve this ancient problem, they need to try everything. Besides, he said, the concerted study of spoofs is just getting started. His group took some early steps, and they already discovered unexpected properties of these numbers. That makes him optimistic about uncovering even more “hidden structure” within spoofs.

Already, Nielsen has identified one possible tactic, based on the fact that every spoof found to date, except for Descartes’ original example, has at least one negative base. Proving that all other spoofs must have a negative base would in turn prove that no OPNs exist — since the bases of OPNs, by definition, must be both positive and prime.

“That sounds like a harder problem to solve,” Nielsen said, because it pertains to a larger, more general category of numbers. “But sometimes when you convert a problem to a seemingly more difficult one, you can see a path to a solution.”

Patience is required in number theory, where the questions are often easy to state but difficult to solve. “You have to think about the problem, maybe for a long while, and care about it,” Nielsen said. “We are making progress. We’re chipping away at the mountain. And the hope is that if you keep chipping away, you might eventually find a diamond.”

This article was reprinted on Wired.com.

Comment on this article