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.READ ALSO:
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.”READ ALSO:
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.