Math’s ‘Oldest Problem Ever’ Gets a New Answer

Number theorists are always looking for hidden structure. And when confronted by a numerical pattern that seems unavoidable, they test its mettle, trying hard — and often failing — to devise situations in which a given pattern cannot appear.

One of the latest results to demonstrate the resilience of such patterns, by Thomas Bloom of the University of Oxford, answers a question with roots that extend all the way back to ancient Egypt.

“It might be the oldest problem ever,” said Carl Pomerance of Dartmouth College.

The question involves fractions that feature a 1 in their numerator, like $latex\frac{1}{2}$, $latex\frac{1}{7}$ or $latex\frac{1}{122}$. These “unit fractions” were especially important to the ancient Egyptians because they were the only types of fractions their number system contained: With the exception of a single symbol for $latex\frac{2}{3}$, they could only express more complicated fractions (like $latex\frac{3}{4}$) as sums of unit fractions ($latex\frac{1}{2}$ + $latex\frac{1}{4}$).

The modern-day interest in such sums got a boost in the 1970s, when Paul Erdős and Ronald Graham asked how hard it might be to engineer sets of whole numbers that don’t contain a subset whose reciprocals add to 1. For instance, the set {2, 3, 6, 9, 13} fails this test: It contains the subset {2, 3, 6}, whose reciprocals are the unit fractions $latex\frac{1}{2}$, $latex\frac{1}{3}$ and $latex\frac{1}{6}$ — which sum to 1.

More exactly, Erdős and Graham conjectured that any set that samples some sufficiently large, positive proportion of the whole numbers — it could be 20% or 1% or 0.001% — must contain a subset whose reciprocals add to 1. If the initial set satisfies that simple condition of sampling enough whole numbers (known as having “positive density”), then even if its members were deliberately chosen to make it difficult to find that subset, the subset would nonetheless have to exist.

“I just thought this was an impossible question that no one in their right mind could possibly ever do,” said Andrew Granville of the University of Montreal. “I didn’t see any obvious tool that could attack it.”

Bloom’s involvement with Erdős and Graham’s question grew out of a homework assignment: Last September, he was asked to present a 20-year-old paper to a reading group at Oxford.

That paper, by a mathematician named Ernie Croot, had solved the so-called coloring version of the Erdős-Graham problem. There, the whole numbers are sorted at random into different buckets designated by colors: Some go in the blue bucket, others in the red one, and so on. Erdős and Graham predicted that no matter how many different buckets get used in this sorting, at least one bucket has to contain a subset of whole numbers whose reciprocals sum to 1.

Croot introduced powerful new methods from harmonic analysis — a branch of math closely related to calculus — to confirm the Erdős-Graham prediction. His paper was published in the Annals of Mathematics, the top journal in the field.

“Croot’s argument is a joy to read,” said Giorgis Petridis of the University of Georgia. “It requires creativity, ingenuity and a lot of technical strength.”

Yet as impressive as Croot’s paper was, it could not answer the density version of the Erdős-Graham conjecture. This was due to a convenience Croot took advantage of that’s available in the bucket-sorting formulation, but not in the density one.

When sorting numbers into buckets, Croot wanted to dodge composite numbers with large prime factors. The reciprocals of those numbers tend to add to fractions with a massive denominator instead of reducing to simpler fractions that more easily combine to make 1. So Croot proved that if a set has sufficiently many numbers with lots of relatively small prime factors, it must always contain a subset whose reciprocals add to 1.

Croot showed that at least one bucket always satisfies that property, which was enough to prove the coloring result. But in the more general density version, mathematicians cannot simply choose whichever bucket happens to be most convenient. They might have to look for a solution in a bucket that contains no numbers with small prime factors — in which case, Croot’s method does not work.

“It was something I couldn’t quite get around,” Croot said.

But two decades later, as Bloom was preparing to present Croot’s paper to his reading group, he realized that he could get even more out of the techniques Croot had introduced.

“I thought, hold on, Croot’s method [is] actually stronger than it first seemed,” said Bloom. “So I played around for a few weeks, and this stronger result came out of it.”

Croot’s proof relied on a type of integral called an exponential sum. It’s an expression that can detect how many integer solutions there are to a problem — in this case, how many subsets contain a sum of unit fractions that equals 1. But there’s a catch: It’s almost always impossible to solve these exponential sums exactly. Even estimating them can get prohibitively difficult.

Croot’s estimate allowed him to prove that the integral he was working with was positive, a property that meant that at least one solution existed in his initial set.

“He solves it in an approximate way, which is good enough,” said Christian Elsholtz of the Graz University of Technology in Austria.

Bloom adapted Croot’s strategy so that it worked for numbers with large prime factors. But doing this required surmounting a series of obstacles that made it harder to prove that the exponential sum was greater than zero (and therefore that the Erdős-Graham conjecture was true).

Both Croot and Bloom broke the integral into parts and proved that one main term was large and positive, and that all the other terms (which could sometimes be negative) were too small to make a meaningful difference.

But whereas Croot disregarded integers with large prime factors to prove that those terms were small enough, Bloom’s method gave him better control over those parts of the exponential sum — and, as a result, more wiggle room when dealing with numbers that might otherwise spell trouble. Such troublemakers could still get in the way of showing that a given term was small, but Bloom proved that there were relatively few places where that happened.

“We’re always estimating exponential sums,” said Greg Martin of the University of British Columbia. “But when the exponential itself has so many terms, it takes a lot of optimism to trust that you’ll find a way to estimate [it] and show that [it’s] big and positive.”

Instead of using this method to hunt for sets of numbers whose reciprocals sum to 1, Bloom employed it to find sets with reciprocals that add up to smaller constituent fractions. He then used these as building blocks to get to the desired result.

“You’re not finding 1 honestly,” Bloom said. “You’re finding maybe $latex\frac{1}{3}$, but if you do that three times in three different ways, then just add them to each other and you’ve got 1.”

That left him with a much stronger statement about how robust this numerical pattern really is: So long as a set contains some tiny but sufficiently large sliver of the number line — no matter what that sliver looks like — it’s impossible to avoid finding these neat sums of unit fractions.

“It’s an outstanding result,” said Izabella Łaba of the University of British Columbia. “Combinatorial and analytic number theory has evolved a lot over the last 20 years. That made it possible to come back to an old problem with a new perspective and with more efficient ways to do things.”

At the same time, it also leaves mathematicians with a new question to solve, this time about sets in which it’s not possible to find a sum of unit fractions that equals 1. The primes are one example — there’s no subset of primes whose reciprocals sum to 1 — but this property can also hold true for other infinite sets that are “larger,” in the sense that the sum of their reciprocals approaches infinity even more quickly than the reciprocals of the primes do. Just how quicky can those sums grow before hidden structure reemerges and some of their reciprocals inevitably add to 1?

“The Erdős-Graham conjecture was a very natural question, but it’s not the full answer,” Petridis said.