Joint TCS - Combinatorics Seminar

Wednesday, March 22, 2023 at 3:00pm to 5:00pm

MIT-Math Dept., Room 2-449

Speaker:  Raghu Meka  (UCLA)

Title:  Strong bounds for 3-progressions


Suppose you have a set S of integers from \{1,2,...,N \ that contains at least N / C elements. Then for large enough N , must S contain three equally spaced numbers (i.e., a 3-term arithmetic progression)?

In 1953, Roth showed that this is indeed the case when C > \Omega(\log \log N), while Behrend in 1946 showed that C can be at most 2^{O(\sqrt{\log N})}. 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 that C >2^{\Omega((\log N)^{0.09), thus getting closer to Behrend's construction. Based on joint work with Zander Kelley.

The first hour of the talk will be self-contained and describe the main ideas of the proof. The second hour will be a deeper follow-up of some elements of the proof.


Event Type


Events By Interest


Events By Audience

Public, MIT Community

Events By School

School of Science


Department of Mathematics
Contact Email

Add to my calendar

Recent Activity