The original version of this story appeared in Quanta Magazine.
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.
Source: Wired
