Students Find New Evidence of the Impossibility of Complete Disorder
Forty years later, in 1975, a mathematician named Endre Szemerédi proved the conjecture. His work spawned multiple lines of research that mathematicians are still exploring today. “Many of the ideas from his proof grew into worlds of their own,” said Yufei Zhao, Sah and Sawhney’s doctoral adviser at MIT.
Mathematicians have built on Szemerédi’s result in the context of finite sets of numbers. In this case, you start with a limited pool—every integer between 1 and some number N. What’s the largest fraction of the starting pool you can use in your set before you inevitably include a forbidden progression? And how does that fraction change as N changes?
For example, let N be 20. How many of these 20 numbers can you write down while still avoiding progressions that are, say, five or more numbers long? The answer, it turns out, is 16—80 percent of the starting pool.
Now let N be 1,000,000. If you use 80 percent of this new pool, you’re looking at sets that contain 800,000 numbers. It’s impossible for such large sets to avoid five-term progressions. You’ll have to use a smaller fraction of the pool.
Szemerédi was the first to prove that this fraction must shrink to zero as N grows. Since then, mathematicians have tried to quantify exactly how quickly that happens. Last year, breakthrough work by two computer scientists nearly solved this question for three-term progressions, like {6, 11, 16}.
But when you’re instead trying to avoid arithmetic progressions with four or more terms, the problem becomes tougher. “The thing I love about this problem is it just sounds so innocent, and it’s not. It really bites,” Sawhney said.
That’s because longer progressions reflect an underlying structure that is difficult for classical mathematical techniques to uncover. The numbers x, y and z in a three-term arithmetic progression always satisfy the simple equation x – 2y + z = 0. (Take the progression {10, 20, 30}, for instance: 10 – 2(20) + 30 = 0.) It’s relatively easy to prove whether or not a set contains numbers that satisfy this kind of condition. But the numbers in a four-term progression have to additionally satisfy the more complicated equation x2 – 3y2 + 3z2 – w2 = 0. Progressions with five or more terms must satisfy equations that are even more elaborate. This means that sets containing such progressions exhibit subtler patterns. It’s harder for mathematicians to show whether such patterns exist.
