The mathematician Ben Green of the University of Oxford has made a major stride toward understanding a nearly 100-year-old combinatorics problem, showing that a well-known recent conjecture is “not only wrong but spectacularly wrong,” as Andrew Granville of the University of Montreal put it. The new paper shows how to create much longer disordered strings of colored beads than mathematicians had thought possible, extending a line of work from the 1940s that has found applications in many areas of computer science.

The conjecture, formulated about 17 years ago by Ron Graham, one of the leading discrete mathematicians of the past half-century, concerns how many red and blue beads you can string together without creating any long sequences of evenly spaced beads of a single color. (You get to decide what “long” means for each color.)

This problem is one of the oldest in Ramsey theory, which asks how large various mathematical objects can grow before pockets of order must emerge. The bead-stringing question is easy to state but deceptively difficult: For long strings there are just too many bead arrangements to try one by one.

“Sometimes there’s these very basic-looking questions where we really don’t understand almost anything,” said Jacob Fox of Stanford University. “I think this was one of those questions that really surprised a lot of people, how little we understood.”

Mathematicians have known for nearly a century that you can’t keep stringing beads indefinitely. Once you’ve chosen your parameters for each color, you can string only so many beads before being forced to create an evenly spaced sequence that is longer than you are willing to tolerate. As you increase the red and blue parameters, the overall number of beads you can string increases — but how quickly?

In a version of the problem in which you forbid even the shortest evenly spaced blue sequences, Graham speculated that a simple relationship holds: The length of the longest possible bead string is roughly the square of the red-bead parameter. All the numerical data mathematicians have accumulated supports Graham’s conjecture.

Ben Green at the University of Oxford in 2017.

A.K.Purkiss

But now Green has proved the conjecture wrong. In a 68-page paper, he has shown how to create much longer bead strings than Graham predicted.

“I was shocked when Ben sent me a draft,” said Sarah Peluse of the Institute for Advanced Studies in Princeton, New Jersey. “I think it’s amazing.”

Green’s construction, which blends geometry and dynamical systems to fashion the disordered bead strings, builds on an earlier bead-stringing construction that has found applications in subjects from matrix multiplication to cryptography. This kind of construction is “very important for questions in computer science,” Fox said.

An Implausible Pattern

If you have a strong taste for disorder, you might prohibit any evenly spaced sequences at all in your string. It doesn’t make sense to talk about evenly spaced sequences of only two beads, so you’re trying to avoid sequences of three or more beads.

You can string a few beads easily, but you’ll soon run into difficulties. For example, if your first six beads are RBBRBR, there’s no way to continue. Stringing a blue bead puts evenly spaced beads in spots 3, 5 and 7; stringing a red bead puts evenly spaced beads in spots 1, 4 and 7. A simple computer search shows that no matter how you start your bead string, you’ll be stuck by bead 9.

If you want to string more than eight beads, you have to give a little. Perhaps you’ll decide that you’re OK with evenly spaced blue sequences of fewer than five beads and red sequences of fewer than 12 beads. In 1927, Bartel Leendert van der Waerden proved that for any pair of parameters you pick, there is some finite length by which you’ll get stuck. These lengths are now called van der Waerden numbers. (Like the mathematicians who came after him, van der Waerden phrased this problem in terms of coloring numbers rather than stringing beads, but the two formulations are equivalent.)

Bartel Leendert van der Waerden in Bonn, Germany, around 1985.

Gerd Fischer; source: Archives of the
Mathematisches Forschungsinstitut Oberwolfach

It’s hard for mathematicians to figure out precisely how the van der Waerden numbers change as you change the parameters. But if you decide not to tolerate any evenly spaced blue sequences — in other words, if you fix the blue parameter at 3 — then a pattern seems to emerge. We saw that if the red parameter is also 3, you’ll get stuck by bead 9. Mathematicians have calculated that if the red parameter is 10, you’ll get stuck by bead 97; if it’s 15, you’re stuck by bead 218; and if it’s 20, you’re stuck by bead 389. In each case, the number of beads you can string is remarkably close to the square of the red parameter. All the data collected so far fits this pattern.

Sometime around 2004, Graham conjectured that the pattern continues for all values of the red parameter (let’s call it r). Within a few years, mathematicians did find ways to make bead strings whose length was close to r2. But that’s not enough to prove the conjecture. It shows that you can string approximately r2 beads without getting stuck, but it leaves open the possibility that you could continue stringing beads for much longer.

When Graham told Green about the conjecture, Green’s gut instinct was that it must be wrong. “It just didn’t seem at all plausible,” he said.

Green thought it should be possible to disprove the conjecture quickly using constructions developed for a related problem — one where you’re trying to avoid evenly spaced blue sequences, but you don’t care what the red beads do. For that problem, researchers had found ways to pack in many blue beads without creating blue sequences. Green suspected that these abundant blue beads would disrupt any potential long red sequences, even though the bead strings hadn’t been specifically designed for that purpose.

But when he looked closely at these bead strings, he found that the blue beads were distributed in ways that left wide swaths of red territory in which patterns could form. These examples, he realized, would not lead to an easy answer for the van der Waerden problem.

Green periodically returned to the problem, and he spent a while trying to prove Graham’s conjecture, since he couldn’t disprove it. He included it on a list of 100 unsolved problems in mathematics, writing, “I now believe that the answer to this question may be affirmative.”

Even so, he said, “I don’t think I ever felt it with any great conviction, that it was true.” Repeating the conjecture was less a statement of his beliefs than “a challenge to other people,” he said.

Structure and Randomness

Green wasn’t content to leave the problem to other mathematicians. When he strongly believes a conjecture is false but all the data says it’s true, “I find that a very attractive situation to try and work on,” he said.

His intuition said there should be much longer disordered bead strings than Graham had predicted. If the earlier constructions couldn’t disprove the conjecture, he still felt that some modification of them might work.

The late Ron Graham was an accomplished mathematician and juggler.

Courtesy of the Graham family

These earlier bead strings started with a 1946 construction by Felix Behrend that relies on a basic geometric fact. Imagine a blue circle on a red sheet of paper. If you connect two points on the circle with a line segment, the midpoint of the segment lies inside the circle, so it is red. These three points are evenly spaced, and they’re not all blue. It’s an elementary observation, but by translating points on the plane (or in higher dimensions) into bead locations, Behrend used this geometry as the basis for constructing bead strings with no evenly spaced blue sequences.

Over the years, this construction has found a wide range of applications. Late last year, for example, it formed one of the key components in a record-breaking algorithm for multiplying matrices. “Behrend’s construction comes up in a surprising number of places,” said David Conlon of the California Institute of Technology.

To tackle the van der Waerden problem, Green zeroed in on an extension of Behrend’s work developed in 2008 by Michael Elkin of Ben-Gurion University of the Negev in Israel, and then adapted later that year by Green himself and Julia Wolf of the University of Cambridge. In this adaptation, we again envision a blue circle (slightly thickened) on a red background. But this time, we picture this design as a square tile, and use identical copies of the tile to fill the entire plane, creating a repeating pattern of blue circles on a red background.

Then we envision knotting the starting end of our bead string at some point in the plane and pulling the string tight in a randomly chosen direction, so it lies flat on the plane, crossing the red and blue terrain unpredictably. We slide beads onto the string, choosing each bead’s color to match the color at the point where the bead’s center will land. The dynamics of the string’s path across the tiles, Green and Wolf showed, will often generate bead strings that have many blue beads but no evenly spaced blue sequences.

The problem with this construction, from the point of view of the van der Waerden question, is that to prevent blue sequences from forming, the blue circles must be kept fairly small. That leaves huge expanses of red, making it impossible to string many beads without creating a long red sequence.

A sketch Green used in talks explaining how he disproved Graham’s conjecture.

Ben Green

But in the final days of 2020, while out for a leisurely walk with his wife and children, Green suddenly had an insight: What if instead of one smallish blue circle per tile, you used many minuscule circles, scattered randomly? Over the following month, Green figured out that if you choose just the right size and quantity of circles and manage a few additional wrinkles (for instance, the circles get slightly squashed), then the scattered blue circles will thoroughly disrupt the red territory without creating significant opportunities for blue sequences to form. This makes it possible to string many beads without creating any long red sequences, or any blue sequences at all.

Green was able to show that as the red parameter (r) increases, the longest bead strings will eventually grow bigger than r2. Then, as r continues to increase, the bead strings will eventually grow bigger than r3 — and then r4, r5, and every higher power of r. In other words, for large values of r, the bead strings are vastly longer than Graham predicted.

These jumps to higher powers of r occur only after r gets very large. This may explain why Graham was fooled in the first place: The data mathematicians have collected only goes through the first few dozen values of r, which are way too small to undergo the jumps to higher exponents.

“It’s a really great result,” Conlon said. When Green posted his paper in February, Conlon emailed him: “I’m rarely surprised by results anymore, but that surprised me.”

The construction lives halfway between structure and randomness. There’s the carefully chosen geometry of the circles, plus an assortment of random choices: the direction of the string, the size of the beads, how the circles are squashed and where they are scattered. It’s “a random union of structured objects,” Green said. “I think this kind of intuition is something that probably comes up in other problems.”

Most coloring constructions in Ramsey theory lean more exclusively on randomness, Peluse said. “It’s really hard to come up with colorings that aren’t random,” she said. “You have to have a really, really insightful idea, like Ben.”

Green’s construction is not the final word on the van der Waerden problem. Just as with earlier constructions, he can’t prove that there aren’t significantly longer bead strings out there. Already, last month, Zach Hunter, an Oxford undergraduate, managed to nudge the length of the bead strings upward by modifying Green’s construction so the circle diameters are varied randomly. But Fox is inclined to think that Green’s result may be in the same ballpark as the true van der Waerden numbers. “I find it a very satisfying answer,” he said.

Graham died last year at age 84, seven months before Green posted his paper. “Ron would have been very excited,” Fox said.