Tata Institute of Fundamental Research

Strong bounds for three-term progressions

STCS Colloquium
Speaker: Raghu Meka (University of California, Los Angeles)
Organiser: Prahladh Harsha
Date: Wednesday, 19 Jul 2023, 16:00 to 17:00
Venue: AG-66

(Scan to add to calendar)
Abstract:  Suppose you have a set $S$ of integers from $\{1,2,...,N\}$ that contains at least $N / C$ elements. Does such a set contain three equally spaced numbers (i.e., a 3-term arithmetic progression)? For example, the set $S$  from $\{1,2,..., 40\}$ comprised of the following 15 numbers $\{1,2,4,5,10,11,13,14,28,29,31,32,37,38,40\}$ avoids every 3-term arithmetic progression.
What is the largest value of $C$ such that for large enough $N$, every such set $S$ necessarily contains a 3-term arithmetic progression?
In 1953, Roth showed this is the case when $C$ is roughly (log log N). Behrend in 1946 showed that $C$ can be at most $exp(\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 showing that $C$ can be as big as $exp((log N)^{0.08})$, thus getting closer to Behrend's construction. Based on joint work with Zander Kelley (Univ of Illinois, Urbana Champaign).