The objective? Form a collection of numbers such that no three of them are evenly spaced (3, 7, 8, 11 is not allowed, but 3, 7, 8, 14 is.)

It seems like a simple enough problem, but the challenge comes when we try to make the collection as large as possible. It gets harder and harder to add to it while ensuring that we cannot form evenly spaced triplets—sets of three numbers like 3, 7, 11.

Mathematicians have grappled with this problem for the past 87 years. In February, however, Zander Kelley of the University of Illinois Urbana-Champaign co-authored a paper presenting the strongest limit on the maximum size of this collection to date, vastly surpassing past mathematical research. He and his collaborator, Raghu Meka of the University of California, Los Angeles, were featured in Quanta Magazine for their work.

“If you look at the previous results for limits on the maximum size, there has been gradual improvement over the years, but the results don’t stray too far from each other,” Kelley said. “Our result really pushes the limit down.” 

Kelley is a graduate student of computer science studying complexity theory, a subfield that seeks to put limits on how many computational resources are needed to perform tasks. Although he is not a mathematician by training, he was aware of the triplet problem for its connection to issues in complexity theory. As he explained, the expectation is that a collection of numbers with no three evenly spaced becomes sparse as larger numbers are added. Were this expectation false, it would be possible to devise efficient algorithms for computing problems thought to be intrinsically difficult.

The Search for a Solution

Terence Tao, a world-renowned mathematician at UCLA, told Quanta Magazine that Kelley and Meka “leapfrogged” almost 90 years of mathematical work on the problem. It can be traced to a 1936 paper by Paul Erdős and Paul Turán suggesting that a collection of numbers without evenly spaced triplets is necessarily sparse. In 1946, Felix Behrend found a method to construct such a sparse collection, but it was unclear if there might be another method that could add more numbers. Since then, mathematicians have found increasingly tighter constraints on the maximum size, but they remained much larger than the size of Behrend’s collection.

Kelley and Meka’s paper gives a mathematical formula for maximum size of a collection without evenly spaced triplets. Their result is remarkable because it is quite close to Behrend’s formula for the size of his collection. The only difference is the value of one parameter. Kelley and Meka not only showed that such a collection is necessarily sparse, but that Behrend was not far off. In fact, further work may show that it is the largest possible.

While Quanta Magazine reported that this result “stunned” mathematicians, it is just one piece of the puzzle for Kelley. “This problem is a necessary step, but it does not solve the complexity problems by itself,” he said. “It’s also interesting because the techniques used to study this problem have found applications elsewhere in theoretical computer science. By finding this new limit, we’ve advanced the technique, so I’m hopeful for other problems.”