In recent developments, UCLA Professor Raghu Meka and student Zander Kelley from UIUC achieved a breakthrough on a problem in arithmetic combinatorics that had stumped mathematicians for over 70 years. Their breakthrough has earned Meka and coauthor Kelley’s paper “Strong Bounds for 3-Progressions’’ the Best Paper Award at the Foundations of Computer Science (FOCS) 2023 conference.
FOCS 2023 is the top conference in theoretical computer science, alongside ACM Symposium on Theory of Computing (STOC). For those who may have forgotten the February announcement, Raghu’s result concerns the following classic question in combinatorics: how large does a subset S of {1,2,…,n} need to be to guarantee that S contains an arithmetic progression of length 3? In the 1940s, Behrend constructed subsets S of size Omega(n/2^{(log n)^0.5}) without any arithmetic progressions of length 3. Matching this with an upper bound turned out to be very difficult. In 1953, Roth proved that any subset S that does not contain a 3-term arithmetic progression has size o(n). In 2020, Bloom and Sisack improved this upper bound to O(n/(log n)^(1+c)), for some constant c>0. This year, Raghu and Zander gave a vastly expanded upper bound of O(n/2^{(log n)^0.09}), nearly matching Behrend’s lower bound from the 1940s.