Graduate Student Solves Classic Problem About the Limits of Addition
In a sum-free set, no two members of the set add to make a third member of the set.
Nash Weerasekera for Quanta Magazine
Introduction
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.
Jean Bourgain devised a creative strategy for proving the sum-free sets conjecture.
George M. Bergman, Berkeley
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.”
Benjamin Bedert, a graduate student at the University of Oxford, has resolved a decades-old problem that tests the role of addition in sets.
Romana Meereis
He read Bourgain’s 1997 paper and began to muse about how to implement the Littlewood blueprint. Almost immediately, he had an idea for how he might approach the problem of sets with a small Littlewood norm.
So far, it had been too difficult to show that sets with a small Littlewood norm always resemble collections of arithmetic progressions. But Bedert thought it might be useful to prove something more attainable: that even if these sets aren’t literally built from arithmetic progressions, they share certain key, progression-like properties.
In a recent project, Bedert had come across what he saw as a good candidate for a property to focus on. In arithmetic progressions, there are many groups of numbers that have the same sum. For instance, in the set of even numbers (which is an arithmetic progression), 4 + 8 has the same sum as both 2 + 10 and 2 + 4 + 6. Bedert thought it might be enough to show that sets with a small Littlewood norm always obey this property.
Within a couple of weeks, he’d succeeded in proving that the property was true. But would the result give him the level of similarity to arithmetic progressions that he needed to prove the sum-free sets conjecture?
“I was definitely excited,” he said. “Then I realized there was still so much more work to do.”
Waves of Progress
First, Bedert showed that any set with a small Littlewood norm could be “mapped” to a second set that bore an even closer resemblance to arithmetic progressions. He suspected that it was in these new sets that he would find large sum-free subsets.
The final task was to actually show what the size of such a sum-free subset would be. “Over the Christmas break, I was obsessively thinking about this problem,” Bedert said. “By New Year’s, I still hadn’t found the final piece of the puzzle.”
Then, a few days after he returned to Oxford in January, it came to him. “I’m not sure where it came from,” he said. “Maybe these ideas stir in your mind for a while, and then [you] finally get something out that works.”
He represented the structure of his sets using a tool called the Fourier transform, and then modified a 1981 proof to show that some of the individual components of that representation must have a large Littlewood norm. Since Bourgain had already shown how to handle sets with large Littlewood norms, that completed the proof.
In the end, Bedert showed that any set of N integers has a sum-free subset with at least N/3 + log(log N) elements. For many values of N, this gives you a sum-free subset that’s only slightly bigger than Erdős’ average size of N/3. Even if N is as large as 10100, for example, log(log N) is only around 5. But as N inches toward infinity, so does the difference in Bedert’s and Erdős’ bounds — thus settling the conjecture.
“It’s a really amazing result,” said Yifan Jing of Ohio State University. Jing, who was also mentored by Green, credits the achievement to Bedert’s intense focus. “Benjamin really went in depth to modify Bourgain’s proof and make it work,” he said. “He spends much more time than other people on the same problem.”
There’s still more to understand about sum-free subsets — and therefore about the extent to which addition influences the structure of the integers. For instance, Bedert’s result resolves the question of whether the largest sum-free subset gets infinitely bigger than N/3. But mathematicians don’t know precisely how fast that deviation can grow. Thanks to a 2014 paper by Green and two colleagues, they know that the deviation is slower-growing than N. But, Green said, “there remains a massive gap” between that upper bound of N and Bedert’s lower bound of log(log N).
The work also provides new insight into sets that have a small Littlewood norm. Such sets are fundamental objects in the field of analysis but are very difficult to study. Bedert’s result has helped mathematicians better understand their structure, which Green and others now hope to continue to explore. “It’s beautiful, it’s interesting, it feels natural,” Eberhard said. “You want to solve a mystery, don’t you?”
For Sahasrabudhe, the takeaway is simple. “Old and difficult problem solved by brilliant kid,” he said. “The stuff he’s building on, it’s subtle and hard to work with. It’s a really pretty result.”
