Coloring by Numbers Reveals Arithmetic Patterns in Fractions

A year after he started his Ph.D. in mathematics at McGill University, Matt Bowen had a problem. “I took my qualifying exams and did absolutely horribly on them,” he said. Bowen was sure that his scores didn’t reflect his mathematical skills, and he resolved to prove it. Last fall he did, when he and his adviser, Marcin Sabok, posted a major advance in the field known as Ramsey theory.

For almost a century, Ramsey theorists have been gathering evidence that mathematical structure persists in hostile circumstances. They might break apart big sets of numbers like the integers or the fractions, or slice up the connections between points on a network. They then find ways to prove that certain structures are inevitable, even if you try to avoid creating them by breaking or slicing in a clever way.

When Ramsey theorists talk about splitting up a set of numbers, they often use the language of coloring. Pick several colors: red, blue and yellow, for example. Now assign a color to every number in a collection.  Even if you do this in a random or chaotic way, certain patterns will inevitably emerge so long as you use only a finite number of different colors, even if that number is very large. Ramsey theorists try to find these patterns, searching for structured sets of numbers that are “monochromatic,” meaning their elements have all been assigned the same color.

The first coloring results go back to the late 19th century. By 1916, Issai Schur had proved that however you color the positive integers (also known as natural numbers), there will always be a pair of numbers x and y such that x, y, and their sum x + y are all the same color. Throughout the 20th century, mathematicians continued working on coloring problems. In 1974, Neil Hindman extended Schur’s result to include an infinite subset of the integers. Like Schur’s theorem, Hindman’s applies no matter how the natural numbers are colored (with a finite number of crayons). Not only are these integers in Hindman’s set all the same color, but if you sum up any collection of them, the result will also be that color. Such sets resemble the even numbers in that, just as any sum of even numbers is always even, so too would the sum of any numbers in one of Hindman’s sets be contained in that set.

“Hindman’s theorem is an amazing piece of mathematics,” Sabok said. “It’s a story that we can make a movie of.”

But Hindman thought more was possible. He believed you could find an arbitrarily large (but finite) monochromatic set that contained not only the sums of its members, but also the products. “I have maintained for decades that that is a fact,” he said, adding: “I do not maintain that I can prove it.”

Hindman’s Conjecture

If you give up on the sum and only want to ensure that the products are the same color, it’s straightforward to adapt Hindman’s theorem by using exponentiation to transform sums into products (much as a slide rule does).

Wrestling with sums and products simultaneously, however, is far tougher. “It’s very difficult to make those two talk to each other,” said Joel Moreira, a mathematician at the University of Warwick. “Understanding how addition and multiplication relate — this is, in a way, the basis of all of number theory, almost.”

Even a simpler version that Hindman first suggested in the 1970s proved challenging. He conjectured that any coloring of the natural numbers must contain a monochromatic set of the form {x, y, xy, x + y} — two numbers x and y, as well as their sum and product. “People didn’t really make any progress on this problem for decades,” Bowen said. “And then all of a sudden, around 2010, people started proving more and more stuff about it.”

Bowen learned about the {x, y, xy, x + y} problem in 2016, his second semester of college, when one of his professors at Carnegie Mellon University described the problem in class. Bowen was struck by its simplicity. “It’s one of these cool things where it’s like, well, I don’t know much math, but I can kind of understand this,” he said.

In 2017, Moreira proved that you can always find a monochromatic set containing three of the four desired elements: x, xy, and x + y. Meanwhile, Bowen started tinkering casually with the question during his senior year. “I couldn’t actually solve the problem,” he said. “But I’d come back to it every six months or so.” After his poor showing on his Ph.D. qualifying exams in 2020, he redoubled his efforts. A few days later, he’d proved the {x, y, xy, x + y} conjecture for the case of two colors, a result that Ron Graham had already proved back in the 1970s with the aid of a computer.

With that success, Bowen worked with Sabok to extend the result to any number of colors. But they quickly became entangled in technical details. “The complexity of the problem grows completely out of control when the number of colors is big,” Sabok said. For 18 months, they attempted to extricate themselves, with little luck. “During this year and a half, we had about a million wrong proofs,” Sabok said.

One difficulty in particular kept the two mathematicians from progressing. If you pick two integers at random, you probably won’t be able to divide them. Division only works in the rare case where the first number is a multiple of the second. This turned out to be extremely limiting. With that realization, Bowen and Sabok pivoted to proving the {x, y, xy, x + y} conjecture in the rational numbers (as mathematicians call fractions) instead. There, numbers can be divided with abandon.

Bowen and Sabok’s proof is at its most elegant when all the colors involved appear frequently throughout the rational numbers. Colors can appear “frequently” in several different ways. They might each cover large chunks of the number line. Or it might mean you can’t travel too far along the number line without seeing every color. Usually, however, the colors don’t conform to such rules. In those cases, you can focus on small regions within the rational numbers where the colors do appear more frequently, Sabok explained. “This is where the bulk of the work came,” he said.

In October 2022, Bowen and Sabok posted a proof that if you color the rational numbers with finitely many colors, there will be a set of the form {x, y, xy, x + y} whose elements all have the same color. “It is an incredibly clever proof,” said Imre Leader of the University of Cambridge. “It uses known results. But it combines them in an absolutely brilliant, very original, very innovative way.”

Plenty of questions remain. Can a third number z be added to the collection, along with the ensuing sums and products? Satisfying Hindman’s boldest predictions would mean adding a fourth, a fifth, and eventually arbitrarily many new numbers to the sequence. It would also require moving from the rationals to the natural numbers and finding a way around the division conundrum that hobbled Bowen and Sabok’s efforts.

Leader believes that with Moreira, Bowen and Sabok all working on the problem, that proof may not be far away. “Those guys seem particularly brilliant at finding new ways to do things,” he said. “So I’m kind of optimistic that they or some of their colleagues may find it.”

Sabok is more cautious in his predictions. But he isn’t ruling anything out. “One of the charms of mathematics is that before you get a proof, everything is possible,” he said.