From Systems in Motion, Infinite Patterns Appear

In December 1977, a revolutionary paper quietly appeared in the Journal d’Analyse Mathématique, a specialty mathematics journal. The author, Hillel Furstenberg, did not claim any thrilling — or even new — results. He’d simply offered a proof of a theorem that another mathematician, Endre Szemerédi, had already proved two years before.

Despite that, Furstenberg’s paper left a lasting imprint on mathematics. His new argument contained a kernel of insight with far-reaching consequences: You could reword problems like the one Szemerédi had solved, about sets of integers, into questions about points moving around in space.

In the years since, Furstenberg’s techniques have been used again and again, and little by little they’ve been adjusted and improved. Earlier this year, they were supercharged, appearing in two new papers that uncover infinite patterns in sets of integers — progressing by leaps and bounds past Szemerédi’s now 47-year-old theorem.

Furstenberg’s Proof

Szemerédi had been examining sets that contain a “positive fraction” of all the integers. Take, for example, the set containing all multiples of 5. As you look at bigger and bigger swaths of the number line, multiples of 5 continue to appear regularly. Mathematicians say that the set containing all multiples of 5 has the fraction of a fifth of all the integers.

In contrast, while there are an infinite number of prime numbers, they get so rare as numbers get bigger that the set of all primes doesn’t contain a positive fraction of the integers, or put another way, doesn’t have a positive density. The primes are instead said to have density zero.

Szemerédi was looking for examples of so-called arithmetic progressions, or chains of evenly spaced numbers. For example, imagine you have an infinite sequence of numbers such as the perfect squares: {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, …}. The perfect squares have an arithmetic progression of length three hiding in the first several terms: {1, 25, 49}. Each number in this progression is 24 more than its predecessor.

Szemerédi proved that any set comprising a positive fraction of the integers must contain arbitrarily long arithmetic progressions. The result was a landmark in the subfield of mathematics called additive combinatorics.

Szémeredi’s proof, though brilliant, was nearly impossible to follow. “To this day, I think there’s maybe only three or four people who really understand [Szemerédi’s] proof,” said Terence Tao, a mathematician at the University of California, Los Angeles.

So Furstenberg’s more comprehensible argument was welcome. To write it, Furstenberg relied on methods from his own field of math, dynamical systems. A dynamical system is any process that changes with time. This could be something as simple as a billiard ball rolling around a pool table. All you need is a way to mathematically represent your system, and a rule for how it evolves. A ball, for example, can be described by its position and velocity. That system progresses in a prescribed way over time, following the laws of classical physics.

Furstenberg was most interested in something called ergodic theory. Rather than looking at the state of a system at any given point in time, ergodic theorists study statistics over long periods. For a billiard ball, that could mean figuring out whether the ball ends up in some spots on the table more than others because of the way it tends to bounce off the walls.

Furstenberg’s key idea was to view sets of integers not as fixed objects, but as momentary states in a dynamical system. It might seem like a small change in perspective, but it allowed him to use tools from ergodic theory to prove results in combinatorics. At the time, Furstenberg had no idea that his ideas would take on a life of their own. “It was just, I liked to have this other proof,” he said. But others saw the promise of the connection between ergodic theory and combinatorics. “A whole generation of ergodic theorists started sort of charging into combinatorics and solving all these problems, and vice versa,” said Tao.

Over the past few years, four mathematicians — Bryna Kra, Joel Moreira, Florian Richter and Donald Robertson — have developed Furstenberg’s techniques to find not just arbitrarily long progressions within any set containing a positive fraction of the integers, but infinite versions of structures called sumsets.

“Sumsets are much less specific than progressions; they’re much less special-looking,” said Robertson. “But it’s more interesting and more delicate, because sumsets are infinite configurations, whereas progressions are finite.”

If Furstenberg built a bridge between ergodic theory and combinatorics, Kra, Moreira, Richter and Robertson have enlarged it into “a six-lane highway,” said Tao.

B + C Conjecture

Szemerédi’s theorem was first proposed, but not proved, in 1936 by two mathematicians. One of them was a Hungarian mathematician famous for making conjectures: Paul Erdős. In 2016, as Moreira was working on his doctoral dissertation at Ohio State University, he stumbled across another conjecture that Erdős had made about the structures called sumsets.

A sumset is made from two other sets; call those B and C. The sumset, written as B + C, is built by adding every possible pair of numbers together, taking one number from B and the other from C. Erdős conjectured that for any set A that contains a positive fraction of integers, there exist other infinite sets B and C whose sumset is contained within A. In the paper Moreira was reading, the authors had proven Erdős’ conjecture when A contains a large fraction of the integers. But for smaller positive density sets, the result was still unknown.  “As soon as I read the statement, I thought it was a really good question, because it’s so simple,” said Moreira. “It’s either false, or it shouldn’t be difficult. Which of course was wrong. It was neither false nor easy.”

Moreira brought Richter and Robertson, friends of his from graduate school, in on the project. Robertson, now at the University of Manchester, had graduated a year before Moreira, and Richter was a couple of years behind. All three were well versed in applying ergodic theory techniques to combinatorics. But this problem posed new challenges.

“There was virtually no precedent for finding infinite sumsets inside a set of positive density,” said Daniel Glasscock, a mathematician at the University of Massachusetts, Lowell who attended graduate school with Moreira, Richter and Robertson.

Perhaps for that reason, the sumset problem proved difficult to corral. “We kind of have to force, a bit, the ergodic theory to come through,” said Moreira. Their efforts eventually paid off, and in what Marcin Sabok of McGill University called an “astonishing accomplishment,” they succeeded in proving Erdős’ conjecture in 2018. Their proof was later published in the Annals of Mathematics, one of math’s most prestigious journals.

The New Proofs

That paper left two big questions open. One of these was another sumset conjecture of Erdős’ called the B + B + t conjecture.

Moreira, Richter and Robertson had also come up with a question of their own: If you have a positive-density set A, can you find three infinite sets — B, C and now D — where B + C + D is inside A? What about four infinite sets? Five?

After they posed the multi-set version, the mathematicians were stuck for a time. It seemed that the techniques they’d used for the two-set conjecture had reached their limit.

“We could not find a dynamical reformulation of this problem,” said Richter. Their approach, he said, “just failed at the very beginning.”

Two years passed before they saw real progress. By this time, Richter was a postdoctoral fellow at Northwestern University, where Bryna Kra was a professor. In 2020, prevented from meeting in person by the Covid-19 pandemic, Kra and Richter found themselves discussing the sumset problem over Zoom.

“Eventually, we came up with some other variations that we understood,” said Kra.

Kra and Richter started talking to Moreira and Robertson every week, reexamining the 2018 proof.

“What we had to do is rethink every step of the proof, starting with that translation into a dynamical system,” said Kra.

Helpful to their cause was a 2019 paper by a French mathematician named Bernard Host. Host had re-proved Moreira, Richter and Robertson’s result and had figured out how to make the ergodic theory sing. In Moreira’s opinion, Host “saw how to write our proof the way it should have been written.”

With Host’s improvements in hand, Kra, Moreira, Richter and Robertson continued to tweak their proof, trying to extract the simplest, most elegant argument possible. “We were just dissecting it, I guess, over and over again, to really see: What’s the crux of the issue?” said Richter. “At the end, we had a proof that had very little resemblance with the initial proof.”

The proof they ended up with, like Furstenberg’s, viewed the infinite sets of integers as time stamps in a dynamical system. This dynamical system, though, is better envisioned as points jumping around in space.

Here’s a rough picture of how it works: Begin by standing in one corner of a closed room, call it Corner 0. You’re equipped with a list of times A. That set, A, is a positive-density set of integers.

You’re also equipped with a rule for moving around the room. Every second, you move to a new spot, based on where you were just standing. The exact rule you follow will be designed to match your set of times A — whenever the time stamp is in A, you’ll find yourself in one special area of the room.

For instance, say A consists of all the numbers divisible by 4, and every second, you move clockwise to the next corner of the room. After one second, you move to Corner 1; after two seconds, Corner 2, and so on. Then, every four steps — meaning for every time that’s in A — you’ll have returned to the original Corner 0.

This process goes on forever. Traveling from corner to corner in a clockwise circle, you’ll visit each corner infinitely many times. A point that you get close to an infinite number of times is called an accumulation point.

Kra, Moreira, Richter and Robertson proved that you can cleverly choose one of these spots to find your sumset B + C. In the corner example, take Corner 1. You arrive there at times 1, 5, 9 and 13 — times that look like 4n + 1 for some integer n. Let B be the set of those times.

Now imagine that instead of starting out at Corner 0, you begin at Corner 1. This means that at times divisible by 4, you’ll find yourself back at Corner 1, and you’ll get to Corner 0 three steps later: at times 3, 7, 11, or any number of the form 4n + 3. Call the set of those times C.

Now, start your process from Corner 0 again. This time, look at what happens if you take a number from B and a number from C — say, 13 from B and 3 from C — and add them up.

This would take 13 + 3 = 16 seconds. Since 16 is a multiple of 4, it’s in A. But you can also predict that 13 + 3 will be divisible by 4, and thus in A, without actually adding 13 and 3 together. Just follow what happens in the dynamical system when you wait 13 + 3 seconds: First, 13 seconds go by. At that point, you find yourself in Corner 1. Then, starting from Corner 1, you move three more steps, which takes you back to Corner 0. Since you started from Corner 0 and ended up back there, you must have waited for a multiple of four seconds, meaning that the total amount of time was a number in the original set A.

To make this argument work, the group had to deal with many finicky mathematical details. For example, in most cases you have an infinite number of spots available to move to, not just four corners. That means you won’t actually return to a spot infinitely many times; you’ll only get close to it infinitely many times. That introduced new mathematical complications to the argument. But once they figured out how the process would work, they knew they’d be able to tackle the harder questions they were after.

“We came up with this proof here, and it was immediately clear how to generalize it,” said Richter, who is now at the Swiss Federal Institute of Technology Lausanne. To prove the multi-set version of the conjecture, for instance, the researchers could just add an  accumulation point to the path. The overall argument was the same, just with a new layer of complication.

Hammering out all the technicalities wasn’t easy. After they settled on their dynamical setup, it took Kra, Moreira, Richter and Robertson over a year to work out proofs of the more difficult conjectures. In June of this year, the group finally posted two papers. One proved the multi-set version of the sumset conjecture. The other proved the B + B + t version of the conjecture, which requires that the second set C be equal to the first set B, shifted by some constant, t.

Next Steps

Though the June papers resolve two questions about sumsets, Kra, Moreira, Richter and Robertson envision a long future for their line of research. “As with everything Erdős asked, he just wants us to put our foot in the door,” said Moreira, now at the University of Warwick. “But now we need to open the door and go explore what else is there.”

In their new papers, the four mathematicians lay out several possible directions of exploration, in the form of as yet unanswered questions. One relies on the fact that, though any positive-density set A contains an infinite sumset B + C, it doesn’t necessarily contain the two components B and C. When can you insist that B and C must also be contained inside A? The authors also challenge mathematicians to figure out whether they can find an infinite sequence of infinite sets whose sumsets are contained in A.

Another open question in the field has already been answered by Matt Bowen, a graduate student of Sabok’s at McGill University. In October, he posted a proof that if you assign each integer one of a few colors, you can find a sumset B + C and a product of sets BC within only one of the colors.

Exactly where else the new work from Kra, Moreira, Richter and Robertson will lead is still unknown. But Tao, at least, is optimistic about the new techniques the group has developed. What they achieve with their methods is “actually quite amazing,” he said. “There are other questions involving infinite sets that were considered hopeless before, now within reach.”