Strong Bounds for 3-Progressions

Strong Bounds for 3-Progressions

Abstract: Suppose you have a set A of integers from {1, 2, …, N} that contains at least N / C elements. Then for large enough N, must A contain three equally spaced numbers (i.e., a 3-term arithmetic progression)? In 1953, Roth showed that this is indeed the case when C ≈ log ⁡ log ⁡ N, while Behrend in 1946 showed that C can be at most 2^√log(N) by giving an explicit construction of a large set with no 3-term progressions. Since then, the problem has been a cornerstone of the area of additive combinatorics. Following a series of remarkable results, a celebrated paper from 2020 due to Bloom and Sisask improved the lower bound on C to C = (log N)^(1 + c), for some constant c > 0. This talk will describe a new work which shows that the same holds when C ≈ 2^(log ⁡ N)^(1/11), thus getting closer to Behrend's construction. Based on a joint work with Raghu Meka.
Bio: Zander is currently a PhD Student in the Theory and Algorithms group at the University of Illinois Urbana-Champaign. Broadly interested in pseudorandomness and its application to computational complexity, as well as its application to extremal combinatorics and number theory.