Landmark Math Proof Clears Hurdle in Top Erdős Conjecture

A pair of mathematicians has solved the first chunk of one of the most famous conjectures about the additive properties of whole numbers. Proposed more than 60 years ago by the legendary Hungarian mathematician Paul Erdős, the conjecture asks when an infinite list of whole numbers will be sure to contain patterns of at least three evenly spaced numbers, such as 26, 29 and 32.

Erdős posed thousands of problems over the course of his career, but the question of which number lists contain evenly spaced numbers (what mathematicians call arithmetic progressions) was one of his all-time favorites. “I think many people regarded it as Erdős’ number-one problem,” said Timothy Gowers of the University of Cambridge. Gowers, who won the Fields Medal in 1998, has spent many hours trying to solve it. “Pretty well any additive combinatorialist who’s reasonably ambitious has tried their hand at it,” he said, referring to the branch of mathematics to which the conjecture belongs.

As a rule, a denser list of numbers has a higher chance of containing arithmetic progressions than a sparser list, so Erdős proposed a simple density test: Just add up the reciprocals of the numbers on your list. If your numbers are plentiful enough to make this sum infinite, Erdős conjectured that your list should contain infinitely many arithmetic progressions of every finite length — triples, quadruples and so forth.

Now, in a paper posted online on July 7, Thomas Bloom of Cambridge and Olof Sisask of Stockholm University have proved the conjecture when it comes to evenly spaced triples, like 5, 7 and 9. The pair has shown that whenever a number list’s sum of reciprocals is infinite, it must contain infinitely many evenly spaced triples.

“This result was kind of a landmark goal for a lot of years,” said Nets Katz of the California Institute of Technology. “It’s a big deal.”

One set whose reciprocals sum to infinity is the primes, those numbers divisible by only 1 and themselves. In the 1930s, Johannes van der Corput used the special structure of the primes to show that they do indeed contain infinitely many evenly spaced triples (such as 17, 23 and 29).

But Bloom and Sisask’s new finding means that you don’t need a deep knowledge of the primes’ unique structure to prove that they contain infinitely many triples. All you need to know is that prime numbers are abundant enough for the sum of their reciprocals to be infinite — a fact mathematicians have known for centuries. “Thomas and Olof’s result tells us that even if the primes had a completely different structure to the one they actually have, the mere fact that there are as many primes as there are would ensure an infinitude of arithmetic progressions,” wrote Tom Sanders of the University of Oxford in an email.

The new paper is 77 pages long, and it will take time for mathematicians to check it carefully. But many feel optimistic that it is correct. “It really looks the way a proof of this result should look,” said Katz, whose earlier work laid much of the groundwork for this new result.

Bloom and Sisask’s theorem implies that as long as your number list is dense enough, certain patterns must emerge. The finding obeys what Sarah Peluse of Oxford called the fundamental slogan of this area of mathematics (originally stated by Theodore Motzkin): “Complete disorder is impossible.”

Density in Disguise

It’s easy to make an infinite list with no arithmetic progressions if you make the list sparse enough. For example, consider the sequence 1, 10, 100, 1,000, 10,000, … (whose reciprocals sum to the finite decimal 1.11111…). These numbers spread apart so rapidly that you can never find three that are evenly spaced.

You might wonder, though, if there are significantly denser number sets that still avoid arithmetic progressions. You could, for example, walk down the number line and keep every number that doesn’t complete an arithmetic progression. This creates the sequence 1, 2, 4, 5, 10, 11, 13, 14, … , which looks pretty dense at first. But it becomes incredibly sparse as you move into higher numbers — for instance, by the time you get to 20-digit numbers, only about 0.000009% of the whole numbers up to that point are on your list. In 1946, Felix Behrend came up with denser examples, but even these become sparse very quickly — a Behrend set that goes up to 20-digit numbers contains about 0.001% of the whole numbers.

At the other extreme, if your set includes almost all the whole numbers, it will definitely contain arithmetic progressions. But between these extremes is a vast, largely uncharted middle. How sparse can you make your set, mathematicians have wondered, and still be sure that it will have arithmetic progressions?

Erdős (perhaps in collaboration with the Hungarian mathematician Pál Turán, some say) provided one possible answer. His condition about the sum of reciprocals is a statement about density in disguise: It turns out to be the same as saying that the density of your list up to any number N is at least approximately 1 over the number of digits in N. In other words, it’s OK for your list to grow sparser as you go out along the number line, but only if it does so very slowly: Up through 5-digit numbers your list should have density at least about 1/5; up through 20-digit numbers it should have density at least about 1/20; and so forth. Provided this density condition is met, Erdős conjectured, your list should contain infinitely many arithmetic progressions of every length.

In 1953, Klaus Roth started mathematicians on a path toward proving Erdős’ conjecture. In work that helped earn him a Fields Medal five years later, he established a density function that guarantees evenly spaced triples — not a density as low as Erdős’, but nevertheless one that approaches zero as you go out along the number line. Roth’s theorem meant that a list of numbers whose density eventually slips below 1%, and then below 0.1%, and then below 0.01%, and so on, must contain arithmetic progressions as long as it slips below those thresholds slowly enough.

Roth’s approach relied, first of all, on the fact that most lists with his chosen density “want” to have arithmetic progressions — they have enough different pairs of numbers that almost surely, some of the midpoints between these pairs will also belong to the list, creating evenly spaced triples. The tricky part was how to get from “most” number lists to “all” number lists, even those whose structure might be specially concocted to try to avoid arithmetic progressions.

Given one of these highly structured lists, Roth had the idea to distill its structure by mapping its “frequency spectrum,” using what’s called the Fourier transform. This detects which repeating patterns show up especially strongly — it’s the same mathematics that underlies technologies like X-ray crystallography and radio spectroscopy.

Some frequencies will show up more strongly than others, and these variations highlight patterns — for instance, a strong frequency might indicate that the list contains more odd numbers than even ones. If so, you can just focus on the odd numbers, and now you have a denser set (relative to all odd numbers) than the set you started with (relative to all numbers). Roth was able to show that after a finite number of such distillations, you have a set so dense that it must contain arithmetic progressions.

Roth’s approach has inspired many developments in analytic number theory over the past half-century, said Jacob Fox of Stanford University. “These were very influential ideas.”

Game, Set, Match

Roth’s argument worked only for sets that were fairly dense to begin with — otherwise the repeated distillations simply made the set evaporate. Other mathematicians gradually found ways to squeeze more juice out of Roth’s method, but they couldn’t quite get down to the density in the Erdős conjecture. “This seemed to be a really hard barrier to cross,” Fox said.

Then in 2011, Katz and Michael Bateman figured out how to overcome this barrier in a simpler setting: the card game Set, in which you search for matching triples of patterned cards. There’s a precise way in which a matching Set triple can be thought of as an arithmetic progression, and just as with lists of whole numbers, you can ask what fraction of the cards you must lay down to be sure of finding at least one triple.