Graduate Student Solves Classic Problem About the Limits of Addition

The simplest ideas in mathematics can also be the most perplexing.

Take addition. It’s a straightforward operation: One of the first mathematical truths we learn is that 1 plus 1 equals 2. But mathematicians still have many unanswered questions about the kinds of patterns that addition can give rise to. “This is one of the most basic things you can do,” said Benjamin Bedert, a graduate student at the University of Oxford. “Somehow, it’s still very mysterious in a lot of ways.”

In probing this mystery, mathematicians also hope to understand the limits of addition’s power. Since the early 20th century, they’ve been studying the nature of “sum-free” sets — sets of numbers in which no two numbers in the set will add to a third. For instance, add any two odd numbers and you’ll get an even number. The set of odd numbers is therefore sum-free.

In a 1965 paper, the prolific mathematician Paul Erdős asked a simple question about how common sum-free sets are. But for decades, progress on the problem was negligible.

“It’s a very basic-sounding thing that we had shockingly little understanding of,” said Julian Sahasrabudhe, a mathematician at the University of Cambridge.

Until this February. Sixty years after Erdős posed his problem, Bedert solved it. He showed that in any set composed of integers — the positive and negative counting numbers — there’s a large subset of numbers that must be sum-free. His proof reaches into the depths of mathematics, honing techniques from disparate fields to uncover hidden structure not just in sum-free sets, but in all sorts of other settings.

“It’s a fantastic achievement,” Sahasrabudhe said.

Stuck in the Middle

Erdős knew that any set of integers must contain a smaller, sum-free subset. Consider the set {1, 2, 3}, which is not sum-free. It contains five different sum-free subsets, such as {1} and {2, 3}.

Erdős wanted to know just how far this phenomenon extends. If you have a set with a million integers, how big is its biggest sum-free subset?

In many cases, it’s huge. If you choose a million integers at random, around half of them will be odd, giving you a sum-free subset with about 500,000 elements.

In his 1965 paper, Erdős showed — in a proof that was just a few lines long, and hailed as brilliant by other mathematicians — that any set of N integers has a sum-free subset of at least N/3 elements.

Still, he wasn’t satisfied. His proof dealt with averages: He found a collection of sum-free subsets and calculated that their average size was N/3. But in such a collection, the biggest subsets are typically thought to be much larger than the average.

Erdős wanted to measure the size of those extra-large sum-free subsets.

Mathematicians soon hypothesized that as your set gets bigger, the biggest sum-free subsets will get much larger than N/3. In fact, the deviation will grow infinitely large. This prediction — that the size of the biggest sum-free subset is N/3 plus some deviation that grows to infinity with N — is now known as the sum-free sets conjecture.

“It is surprising that this simple question seems to present considerable difficulties,” Erdős wrote in his original paper, “but perhaps we overlook the obvious.”

For decades, nothing obvious revealed itself. No one could improve on Erdős’ proof. “The longer it went without people being able to improve on that simple bound, the more cachet this problem acquired,” said Ben Green, Bedert’s doctoral adviser at Oxford. And, he added, this was precisely the kind of problem where “it’s very, very hard to do any better at all.”

Confronting the Norm

After 25 years without improving on Erdős’ original result, mathematicians finally began inching forward. In 1990, two researchers proved that any set of N integers has a sum-free subset with at least N/3 + 1/3 elements, more commonly written as (N + 1)/3.

But since the size of a set is always a whole number, an increase of 1/3 is often inconsequential. For example, if you know that a sum-free subset has to have at least 5/3 elements, that means its size is guaranteed to be 2 or more. If you add 1/3 to 5/3, your answer is still 2. “It’s funny, it means that it doesn’t actually always improve it,” said David Conlon of the California Institute of Technology. “It’s only when N is divisible by 3 that it improves it.”

In 1997, the mathematical legend Jean Bourgain nudged the bound up to (N + 2)/3. The result might have seemed hardly worth mentioning, but buried in Bourgain’s paper was a startling breakthrough. He described an idea for how to prove that the biggest sum-free subsets would be arbitrarily bigger than that. He just couldn’t pin down the details to turn it into a full proof.

“The paper’s almost like, here’s how I tried to solve the problem and why it didn’t work,” Sahasrabudhe said.

Bourgain relied on a quantity called the Littlewood norm, which measures a given set’s structure. This quantity, which comes from a field of mathematics called Fourier analysis, tends to be large if a set is more random, and small if the set exhibits more structure.

Bourgain showed that if a set with N elements has a large Littlewood norm, then it must also have a sum-free set that’s much larger than N/3. But he couldn’t make progress in the case where the set has a small Littlewood norm.

“Bourgain is famously competent,” said Sean Eberhard of the University of Warwick. “It’s a very striking marker of how difficult this problem is.”

Bourgain ultimately had to use a different argument to get his bound of (N + 2)/3. But mathematicians read between the lines: They might be able to use the Littlewood norm to completely settle the conjecture. They just had to figure out how to deal with sets with a small Littlewood norm.

There was reason to be optimistic: Mathematicians already knew of sets with a small Littlewood norm that have massive sum-free subsets. These sets, called arithmetic progressions, consist of evenly spaced numbers, such as {5, 10, 15, 20}. Mathematicians suspected that any set with a small Littlewood norm has a very specific structure — that it’s more or less a collection of many different arithmetic progressions (with a few tweaks). They hoped that if they could show this, they’d be able to use that property to prove that any set with a small Littlewood norm has a large sum-free subset.

But this task wasn’t easy. “I certainly tried to prove the sum-free conjecture using [Bourgain’s] ideas,” Green said, but “we still don’t understand much about the structure of sets with small Littlewood norm. Everything to do with Littlewood is difficult.”

And so, though mathematicians continued to have faith in Bourgain’s Littlewood-based strategy, nothing happened.

More than two decades passed. Then, in the fall of 2021, Benjamin Bedert started graduate school.

Notorious Problems

With Green as his doctoral adviser, it was inevitable that Bedert would come across the sum-free sets conjecture. Green’s website lists 100 open problems; this one appears first.

Bedert perused the list shortly after he began his graduate studies. At first, he shied away from the sum-free sets problem. “I was like, this is super difficult, I’m not going to think about this,” he recalled. “I’ll leave this for the future.”

The future arrived soon enough. In summer 2024, Bedert decided he was ready for a riskier project. “I’d proved some reasonably good results in my Ph.D. so far, and kind of put a thesis together already,” he said. “I started thinking about these more, I guess, notorious problems.”