New Erdős Paper Solves Egyptian Fraction Problem

Nearly 20 years after his death, the famed mathematician Paul Erdős keeps on publishing, thanks to the conjectures he left behind and the friends who strive to prove them

Ancient Egyptians were thought to have used different parts of the Eye of Horus to represent unit fractions, up to the first six powers of two Credit: Benoît Stella — Ancient Egyptians were thought to have used different parts of the Eye of Horus to represent unit fractions, up to the first six powers of 2. Credit: Benoît Stella

Writing a paper with Paul Erdős might seem like utter fantasy, considering that the prolific Hungarian mathematician died in 1996. Yet such co-authorship has happened 35 times since his death. The latest co-author is Steve Butler of Iowa State University, who becomes the 512th Erdős collaborator and has earned a coveted Erdős number of 1.

Butler never met Erdős himself, but the new paper, published this December in the journal Integers, is also co-authored by Ronald Graham of the University of California, San Diego, with whom Erdős collaborated on 31 prior occasions. (Definitive data on Erdős’ collaborators and publications — he authored 1,526 papers, including this latest one — can be found at the Erdős Number Project.) The new paper revisits one of Erdős’ earliest interests: Egyptian fractions. Specifically, the paper explores, as its title states, “Egyptian Fractions With Each Denominator Having Three Distinct Prime Divisors” (pdf), a conjecture that Erdős and Graham began working on more than half a century ago.

Egyptian fractions, which date to 1550 BC with examples surviving in the Rhind Mathematical Papyrus at the British Museum, boggle the brain with their convoluted and laborious way of expressing rational numbers. They refer to a series of unit fractions (fractions that have a numerator of 1) with different denominators, each a positive integer, that sum to a rational number. For instance, 47/60 would be expressed as a sum of unit fractions: 1/3 + 1/4 + 1/5.

Perplexed as to why Egyptians would use such a circuitous method to express fractions, Graham once asked the French number theorist and historian André Weil what the reason might be. “It is easy to explain,” Graham recalls Weil answering. “They took a wrong turn!” Indeed, Graham says, “it was a mistake. Like Roman numerals, it wasn’t really the way to go.”

But it was an interesting detour, and despite their impracticality Egyptian numbers proved inspirational. In 1932, the 19-year-old Erdős, in his second published paper, generalized a theorem by the Hungarian mathematician József Kürschák by showing that the sum of the reciprocals of a block of integers — for example, 1/10 + 1/11 + 1/12 — can never produce a whole number.

Graham also explored unit fractions early on, proving the ‘77 theorem’ (pdf) for his doctoral thesis in the early 1960s. “If you take a number like 11, you can write it as 2 + 3 + 6,” he says. “And the reciprocals, 1/2 + 1/3 + 1/6, equal 1. Amazing! Well, you can do the same thing with 24, but not with 77,” he says. “What I proved is that any number 78 or larger can always be broken up into the sum of distinct numbers whose reciprocals add up to 1.” As he explains, “it just shows that there are so many ways to write a number as the sum of unit fractions.”

Having previously corresponded with Erdős, Graham met him in person in 1963. By then Erdős, who had no fixed address, was well-known for his habit of crashing at collaborators’ homes and declaring his brain open — he was always keen to do more proofs. At Graham’s house, the duo pursued many topics, including Egyptian fractions with restrictions — for example, requiring the denominators to be products of distinct prime numbers.

“Erdős and I thought we could show that you could write any whole number, like 1,000,000, as the sum of reciprocals with just two distinct prime factors,” Graham says. For instance, the number 1 can be expressed as a series of 48 unit fractions with the following denominators, each one the product of two distinct primes:

6 21 34 46 58 77 87 115 155 215 287 391

10 22 35 51 62 82 91 119 187 221 299 689

14 26 38 55 65 85 93 123 203 247 319 731

15 33 39 57 69 86 95 133 209 265 323 901

The two worked hard over the decades, whenever Erdős zoomed into town, to prove their conjecture. They had an idea of how to attack the problem but consistently set it aside, planning to work out the details later. They were sufficiently certain of success that they stated their claim about a proof for the two-primes problem in Richard Guy’s 1981 book, Unsolved Problems in Number Theory.

But by the time Erdős died in 1996, the problem remained unsolved. Two decades later, along came Butler, a student of Graham’s wife, Fan Chung, also at UC San Diego. Butler and Graham managed to prove at least a part of the conjecture. “We sat down and spent a week and finally were able to actually push it through, at least for three distinct prime factors,” Graham says.

erdos mathematical diary page — Diary of a mathematician: Erdős’ most prized possessions were his mathematical diaries. Every day he diligently wrote what he was thinking and with whom he was talking. This page from 1963 describes his conversation with Ronald Graham about Egyptian fractions. Credit: Ronald Graham.

Applying the same problem-solving philosophy Graham devised for his doctoral thesis, the two mathematicians used a computationally heavy, iterative process. “Imagine that you look at all the numbers from 1 to 10,000,” Graham says. “Certain numbers are ‘good numbers’” for solving the problem — in this case, they are ‘good fractions’ that are converted to very large good numbers. “By computation, I can say that of the first 10,000, some of them are good but most of them aren’t good. But I can take the pattern of the good ones and translate it — translate just means move the pattern over as a block and put it on top of the next 5,000 numbers.” Crucially, the union of the old good numbers (found in the 10,000 block) and the new good numbers (in the 5,000 block) gives “a denser set of good numbers,” Graham explains. “And then you take that bigger pattern of good numbers, and move that block over by, say, 8,000 and plop it down again, and now there’s an even denser set of good numbers.” Repeating the process again and again yields more and more good numbers, “until finally you have enough good numbers to prove that everything is good from that point on.”

Ultimately, Graham and Butler succeeded with their proof in no small part because of intensive computation, which was primarily Butler’s contribution — he provided verification, cleaned up the arguments, and checked the logic. “They had a great idea,” Butler says of his co-authors. “But they did not seem to carefully go through the details, and in mathematics the details can be important.”

Other challenges remain, such as proving the case with only two prime factors instead of three. And in their paper, the authors ask whether all rational numbers, and not merely all whole numbers, can be expressed with Egyptian fractions in which the denominators are the product of three primes. The authors have different opinions, it seems. “The footnote says one of the authors thinks it’s true, and that’s Ron,” Butler says. “One of the authors has doubts, and that’s me.”

“And the third author,” Butler remarks, “remains silent. And of course, that’s Erdős.”