Student Solves a Long-Standing Problem About the Limits of Addition

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.

Paul Erdős was famous for his ability to come up with deep conjectures that continue to guide mathematics research today.

Photograph: George Csicsery

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 link

Latest

Guts and Glory – Gastropod

What does it mean when your stomach rumbles? How...

VEGGIE CHILI — Sprouted Kitchen

VEGGIE CHILIServes 6I wrote this recipe for...

Why TOBIAS FORGE Couldn’t Perform His Favorite BLACK SABBATH Songs At Their Final Show

At Black Sabbath's final concert, Back to the Beginning,...

Newsletter

spot_img

Don't miss

Guts and Glory – Gastropod

What does it mean when your stomach rumbles? How...

VEGGIE CHILI — Sprouted Kitchen

VEGGIE CHILIServes 6I wrote this recipe for...

Why TOBIAS FORGE Couldn’t Perform His Favorite BLACK SABBATH Songs At Their Final Show

At Black Sabbath's final concert, Back to the Beginning,...

New look and 451kW charging for updated Xpeng G6

Xpeng has updated its Tesla Model Y rival, the...
spot_imgspot_img

Guts and Glory – Gastropod

What does it mean when your stomach rumbles? How do our bodies extract nutrients and vitamins from food? Does what you eat affect your...

US secretary of state Rubio Marco set to meet Russian foreign minister Sergey Lavrov; lands in Malaysia for Asean summit, what is on agenda?...

Marco Rubio to meet Sergey Lavrov in Malaysia amid rising Russia-Ukraine war US secretary of state Marco Rubio is set to meet Russian...

VEGGIE CHILI — Sprouted Kitchen

VEGGIE CHILIServes 6I wrote this recipe for SKCC, and it’s been popular. Even the omnivorous folks say they don’t miss the meat...