In an exciting new development in mathematics, Zander Kelley (a student at UIUC) and UCLA CS faculty Raghu Meka have obtained a new result for a 70-year-old number theory problem.
The question is whether a set S of integers in [1, N] containing at least N/C elements must have three equally spaced numbers (i.e., a 3-term arithmetic progression) for a large enough N.
In 1953, Klaus Roth proved this for any constant C. Since then, the problem has been a cornerstone of arithmetic combinatorics, an area of number theory, and has led to the development of deep mathematics. Following a series of remarkable results, a celebrated paper written in 2020 by Bloom and Sisask where they improved this problem to C = (log N)^(1+c), for some constant c>0. This was called “breaking the logarithmic barrier”. An excellent description of the development can be found in this quanta/wired article.
Then, two weeks ago, Kelley and Meka broke past this barrier with a nearly exponential improvement, proving that the result must hold for C = 2^{(log N)^0.09}. This is a significant step forward for the mathematical community, as mathematicians have worked on this question extensively throughout the past century. The new bound is tantalizingly close to the upper bound on C proved in the 1940s by Behrend. Fields medalist Timothy Gowers tweeted his excitement saying “… pleased that I lived to see what the answer was. ” Mathematician Gil Kalai called the new result an “absolutely amazing breakthrough.”
With broad interests in the foundations of computer science, particularly algorithm design, complexity theory, and machine learning, Meka’s findings on 3-progressions are only one of his many accomplishments in the field.
The paper can be accessed at https://arxiv.org/abs/2302.05537.