A Landmark Math Proof Clears a Hurdle in the 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.

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

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.

Thomas Bloom of the University of Cambridge.Courtesy of Thomas Bloom

“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 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.

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?

Olof Sisask of Stockholm University.Courtesy of Olof Sisask

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 of at least about 1/5; up through 20-digit numbers, it should have density of 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 percent, and then below 0.1 percent, and then below 0.01 percent, 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.

Photograph: Lucy Reading-Ikkanda and Samuel Velasco/Quanta Magazine

This question (which is not just about the standard Set game but also about larger versions with more cards) is a natural toy model for the corresponding question about whole numbers. So mathematicians hoped that Bateman and Katz’s breakthrough might offer an avenue into proving the Erdős conjecture, especially when combined with other recent advances. Soon after Bateman and Katz’s paper came out, Gowers convened a Polymath project—a massive online collaboration—to make the attempt.

But the project quickly ground to a halt. “There was such a high degree of technical arguments involved,” Gowers said. “It was more of a project that was suited to one or two individuals slogging away for a long, long time.”

Fortunately, a pair of mathematicians was gearing up to do just that. Bloom and Sisask had already started thinking about the Erdős conjecture problem, separately at first, both captivated by the beauty of the techniques involved. “This was one of the first research problems that I ever came to,” said Sisask, who like Bloom is now in his mid-30s.

Bloom and Sisask joined forces in 2014, and by 2016 they thought they had pushed through to a solution. Bloom even announced the result in a lecture, only to realize afterward that some of their shortcuts were untenable. The pair kept going, diving into the inner workings of Bateman and Katz’s method and eventually figuring out what new ideas would allow them to transfer it over from the world of Set to the whole numbers.

The new paper seems to have all the right pieces, Katz said. “I didn’t believe their previous claims, and I do believe this.”

Bloom and Sisask’s work is “a great accomplishment,” Fox said. He and other mathematicians are eager to explore whether the new paper’s techniques will have applications to other problems. “I think it’s really going to be the methods that will have the greatest impact,” Fox said.

As for the full Erdős conjecture, the work is far from done. Bloom and Sisask have only proved the conjecture for evenly spaced triples, not for longer arithmetic progressions, a task that currently seems out of reach.

And even in the case of triples, which Bloom and Sisask have now solved, many mathematicians view Erdős’ conjecture as something of a red herring. As difficult as it was to show that the Erdős density guarantees you evenly spaced triples, mathematicians suspect that the true density at which this guarantee lapses is probably much lower—perhaps just a shade higher than the density of the sets Behrend constructed that avoid arithmetic progressions.

“It’s not like we’ve solved it completely,” Bloom said. “We’ve only just shed a little more light on the subject.”

Bloom and Sisask have probably pushed the current methods as far as they can go, Fox said. “There need to be really new tools that would do a lot, to get something fundamentally better,” he said. But “this is probably not the end of the story.”

Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

A Landmark Math Proof Clears a Hurdle in the Top Erdős Conjecture

Author: sgadmin

Related Posts