The original version of this story appeared in Quanta Magazine.
So far this year, Quanta has chronicled three major advances in Ramsey theory, the study of how to avoid creating mathematical patterns. The first result put a new cap on how big a set of integers can be without containing three evenly spaced numbers, like {2, 4, 6} or {21, 31, 41}. The second and third similarly put new bounds on the size of networks without clusters of points that are either all connected, or all isolated from each other.
The proofs address what happens as the numbers involved grow infinitely large. Paradoxically, this can sometimes be easier than dealing with pesky real-world quantities.
For example, consider two questions about a fraction with a really big denominator. You might ask what the decimal expansion of, say, 1/42503312127361 is. Or you could ask if this number will get closer to zero as the denominator grows. The first question is a specific question about a real-world quantity, and it’s harder to calculate than the second, which asks how the quantity 1/n will “asymptotically” change as n grows. (It gets closer and closer to 0.)
“This is a problem plaguing all of Ramsey theory,” said William Gasarch, a computer scientist at the University of Maryland. “Ramsey theory is known for having asymptotically very nice results.” But analyzing numbers that are smaller than infinity requires an entirely different mathematical toolbox.
Gasarch has studied questions in Ramsey theory involving finite numbers that are too big for the problem to be solved by brute force. In one project, he took on the finite version of the first of this year’s breakthroughs—a February paper by Zander Kelley, a graduate student at the University of Illinois, Urbana-Champaign, and Raghu Meka of the University of California, Los Angeles. Kelley and Meka found a new upper bound on how many integers between 1 and N you can put into a set while avoiding three-term progressions, or patterns of evenly spaced numbers.
Though Kelley and Meka’s result applies even if N is relatively small, it doesn’t give a particularly useful bound in that case. For very small values of N, you’re better off sticking to very simple methods. If N is, say, 5, just look at all the possible sets of numbers between 1 and N, and pick out the biggest progression-free one: {1, 2, 4, 5}.
But the number of different possible answers grows very quickly and makes it too difficult to employ such a simple strategy. There are more than 1 million sets consisting of numbers between 1 and 20. There are over 1060 using numbers between 1 and 200. Finding the best progression-free set for these cases takes a hefty dose of computing power, even with efficiency-improving strategies. “You need to be able to squeeze a lot of performance out of things,” said James Glenn, a computer scientist at Yale University. In 2008, Gasarch, Glenn, and Clyde Kruskal of the University of Maryland wrote a program to find the biggest progression-free sets up to an N of 187. (Previous work had gotten the answers up to 150, as well as for 157.) Despite a roster of tricks, their program took months to finish, Glenn said.
Source link
