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 q**uanta/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.**