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.
Earlier this year one of the top mathematicians in the world dared to confront the problem—and came away with one of the most significant results on the Collatz conjecture in decades.On September 8, Terence Tao posted a proof showing that—at the very least—the Collatz conjecture is “almost” true for “almost” all numbers.
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.”
How Gödel’s Proof Works
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 percent 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 percent of the whole numbers.